An efficient clustering algorithm for partitioning parallel programs

Piyush Maheshwari, Hong Shen

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


This paper presents a clustering algorithm that partitions node-labelled and edge-labelled directed acyclic precedence graphs (APG) into clusters such that all the clusters have balanced amount of computation load and there is only one communication path between any pair of clusters. The algorithm initially demonstrates all exploitable parallelism instances in a tree structure, then balances the computation load among the parallelism instances, and finally partitions the parallelism instances into clusters which can be scheduled on a set of processors belonging to an MIMD multiprocessor. The comparison results show that the clusters generated by our algorithm could be scheduled in less completion time than the clusters obtained by using other approaches.

Original languageEnglish
Pages (from-to)893-909
Number of pages17
JournalParallel Computing
Issue number5-6
Publication statusPublished - Jun 1998
Externally publishedYes


  • Clustering
  • Granularity
  • Multiprocessor scheduling
  • Parallel processing
  • Partitioning


Dive into the research topics of 'An efficient clustering algorithm for partitioning parallel programs'. Together they form a unique fingerprint.

Cite this