๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An efficient heuristic for code partitioning

โœ Scribed by Moez Ayed; Jean-Luc Gaudiot


Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
326 KB
Volume
26
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis


In this paper, we propose a heuristic for code partitioning for distributed memory multiprocessors (DMMs). Our method is data-ยฏow based where all levels of parallelism can potentially be exploited. Given a weighted directed acyclic graph (DAG) representation of the program, our partitioning algorithm automatically determines the granularity of parallelism by partitioning the graph into tasks to be scheduled on the DMM. The granularity of parallelism depends only on the program to be executed and on the target machine parameters. The output of our algorithm is passed on as input to the scheduling phase. Unlike the scheduling problem as deยฎned by Yang [A. Gerasoulis, T. Yang, IEEE Transactions on Parallel and Distributed Systems 4 (6) (1993) 686ยฑ701; T. Yang, Ph.D. Thesis, Rutgers University, New Brunswick, NJ, May 1993; T. Yang, A. Gerasoulis, IEEE Transactions on Parallel and Distributed Systems 5 (9) (1994) 951ยฑ967], the method presented in this paper uses task merging rather than task clustering. Finding an optimal solution to this problem is NPcomplete. Due to the high cost of graph algorithms, it is nearly impossible to come up with close to optimal solutions that do not have very high cost (higher order polynomial). Therefore, our goal is to ยฎnd a heuristic that gives good performance, and that has relatively low cost. Given a DAG with E edges and N nodes, the time complexity of our partitioning algorithm is OE ร N 3 in the worst case. For some cases, the average time complexity of the algorithm is ON E N .


๐Ÿ“œ SIMILAR VOLUMES


An efficient heuristic for large set cov
โœ Francis J. Vasko ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 477 KB

## Abstract A heuristic solution procedure for set covering is presented that works well for large, relatively dense problems. In addition, a confidence interval is established about the unknown global optimum. Results are presented for 30 large randomly generated problems.

An efficient clustering algorithm for pa
โœ Piyush Maheshwari; Hong Shen ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 254 KB

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