Name
Abstract | ||
|---|---|---|
Modern hardware and software systems promote a view of parallel systems in which interprocessor communications are uniform and rather expensive in cost. Such systems demand efficient clustering algorithms that aggregate atomic tasks in a way that diminishes the impact of the high communication costs. We develop here a linear-time algorithm that optimally clusters computations that comprise a sequence of disjoint complete up- and/or down-sweeps on a complete binary tree for such parallel environments. Such computations include, for instance, those that implement broadcast, accumulation, and the parallel-prefix operator; such environments include, for instance, networks of workstations or BSP-based programming systems. The schedules produced by our clustering are optimal in the sense of having the exact minimum makespan驴not just an approximation thereof驴accounting for both computation and communication time. We show by simulation that the makespans of the schedules produced by our algorithm are close to half of those produced by the algorithm that yielded the best schedules previously known. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1109/71.790599 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
interprocessor communication,aggregate atomic task,tree-sweep computations,high-latency parallel environments,linear-time algorithm,complete binary tree,bsp-based programming system,efficient clustering algorithm,communication time,parallel environment,parallel system,high communication cost,optimal clustering,scheduling,scheduling algorithm,binary tree,clustering algorithms,cluster computing,parallel systems,software systems,concurrent computing,computer networks,hardware,binary trees,clustering,tree data structures,parallel processing | Disjoint sets,Computer science,Scheduling (computing),Tree (data structure),Parallel computing,Binary tree,Software system,Schedule,Cluster analysis,Distributed computing,Computation | Journal |
Volume | Issue | ISSN |
10 | 8 | 1045-9219 |
Citations | PageRank | References |
3 | 0.43 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lixin Gao | 1 | 2898 | 233.01 |
| Arnold L. Rosenberg | 2 | 2107 | 640.21 |
| Ramesh K. Sitaraman | 3 | 1928 | 141.68 |