BM/C(3) Algorithm Mapping Onto Concurrent Processors
Krishna Rao Pattipati, Peter B. Luh, Rong-Tay Lee, Samir Shah, Somanth Deb · 1989
Abstract : This report is concerned with the mapping of large scale resource allocation algorithms onto parallel computing architectures. The mapping problem is viewed as one of assigning the nodes of a finite, directed, acylic task graph (representing the logical and data dependencies among the tasks constituting the algorithm) onto the nodes of a finite, undirected processor graph (denoting the parallel computing architecture). The objective is to minimize the completion time of the algorithm such that the redundancy, processor memory and security constraints are satisfied. The delays introduced by task queueing, message transmission, message collision and precedence constraints are explicitly modeled. We present four algorithms to solve the mapping problem.