On mapping processes to processors in distributed systems |
| |
Authors: | Shlomit S Pinter Yaron Wolfstahl |
| |
Affiliation: | (1) Faculty of Electrical Engineering, Technion, Israel Institute of Technology, 32000 Haifa, Israel;(2) Faculty of Computer Science, Technion, Israel Institute of Technology, 32000 Haifa, Israel |
| |
Abstract: | This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. Anoptimal path cover of a simple graphG is a set of vertex-disjoint paths that cover all the vertices ofG and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a cover and augment scheme can be used for optimal implementation of parallel programs in line-like networks.A preliminary version of this paper was presented at the 6th IEEE Conference on Computer Communications (INFOCOM '87).This reseach is supported in part by National Semiconductor (Israel), Ltd. |
| |
Keywords: | Cacti distributed systems graph covering mapping network computers |
本文献已被 SpringerLink 等数据库收录! |
|