Portal de Periódicos da CAPES

Clustering task graphs for message passing architectures

1990; ACM SIGARCH; Volume: 18; Issue: 3b Linguagem: Inglês

10.1145/255129.255188

1943-5851

Apostolos Gerasoulis, Sesh Venugopal, Tao Yang,

Distributed and Parallel Computing Systems

Clustering is a mapping of the nodes of a task graph onto labeled clusters. We present a unified framework for clustering of directed acyclic graphs (DAGs). Several clustering algorithms from the literature are compared using this framework. For coarse grain DAGs two interesting properties are presented. For every nonlinear clustering there exists a linear clustering whose parallel time is less than the nonlinear one. Furthermore, the parallel time of any linear clustering is within a factor of two of the optimal. Two clustering algorithms are presented with near linear time complexity for coarse grain DAGs. The conclusion is that linear clustering is an efficient and accurate operation.