Mapping Arbitrary Non-Uniform Task Graphs onto Arbitrary Non-Uniform System Graphs.
Song Chen, M.M. Eshaghian, Ying-Chieh Wu · 1995
this paper, a generic technique for clustering and mapping arbitrary task graphs onto arbitrary system graphs is presented. The task and system graphs studied in this paper have non-uniform computation and communication weights associated with the nodes and edges. The task graphs are directed graphs, while the system graphs are undirected. Using two clustering algorithms presented, a multi-level clustered graph called Spec graph can be obtained from a given task graph, and a multi-level clustered graph called Rep graph can be obtained from a given system graph. We present a mapping algorithm which produces a sub-optimal matching of a given Spec graph containing M task modules, onto a Rep graph of N processors, in O(MP ) time, where P = max(M;N ). This algorithm is the first technique which can map arbitrary task graphs with non-uniform nodes and edges onto arbitrary system graphs with non-uniform nodes and edges. A number of algorithms exist which can map an arbitrary non-uniform task graph onto a specific uniform system graph. Even though our algorithm is more generic, we still compare ours with these specialized techniques and show that our technique produces similar results with lower time complexity. 1 Introduction The mapping problem is one of the most challenging problems in parallel and distributed computing [9, 16]. It is known to be NP-complete in its general form as well as several restricted forms [16]. The mapping problem has been studied in a number of different ways in literature. Mapping can be either static or dynamic. In static mapping, the assignments of the nodes