On mapping processes to processors in distributed systems
type: Item
instance of: scholarly article
title: On mapping processes to processors in distributed systems
zbMATH Open document ID: 0632.68029
DOI: 10.1007/BF01408172
author: Shlomit S. Pinter
author: Yaron Wolfstahl
published in: International Journal of Parallel Programming
publication date: 1987-01-01T00:00:00Z
review text: 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. An optimal path cover a simple graph G is a set of vertex-disjoint paths that cover all the vertices of G 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.
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4028885
zbMATH Keywords: graph covering
zbMATH Keywords: mapping
zbMATH Keywords: network computers
zbMATH Keywords: parallel programs
zbMATH Keywords: networks of processors
zbMATH Keywords: optimal path cover
MaRDI profile type: Publication
cites work: Quotient Networks
cites work: Q4198056
cites work: Augmentation Problems
cites work: Optimal Sorting Algorithms for Parallel Computers
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Q4052166
cites work: Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization
full work available at URL: https://doi.org/10.1007/bf01408172
OpenAlex ID: W2052162800
description: scientific article; zbMATH DE number 4028885