A fast recursive mapping algorithm
Song Chen, Mary Mehrnoosh Eshaghian‐Wilner · Concurrency Practice and Experience · 1995
Abstract The paper presents a generic technique for mapping parallel algorithms onto parallel architectures. The proposed technique is a fast recursive mapping algorithm which is a component of the Cluster‐M programming tool. The other components of Cluster‐M are the Specification module and the Representation module. In the Specification module, for a given task specified by a high‐level machine‐independent program, a clustered task graph called Spec graph is generated. In the Representation module, for a given architecture or computing organization, a clustered system graph called Rep graph is generated. Given a task (or system) graph, a Spec (or Rep) graph can be generated using one of the clustering algorithms presented in the paper. The clustering is done only once for a given task graph (system graph) independent of any system graphs (task graphs). It is a machine‐independent (application‐independent) clustering, and therefore it is not repeated for different mappings. The Cluster‐M mapping algorithm presented produces a sub‐optimal matching of a given Spec graph containing M task modules, onto a Rep graph of N processors, in O(MN) time. This generic algorithm is suitable for both the allocation problem and the scheduling problem. Its performance is compared to other leading techniques. We show that Cluster‐M produces better or similar results in significantly less time and using fewer or an equal number of processors as compared to the other known methods.