Publishing House SB RAS:

Publishing House SB RAS:

Address of the Publishing House SB RAS:
Morskoy pr. 2, 630090 Novosibirsk, Russia



Advanced Search

Avtometriya

2003 year, number 3

Mapping parallel program structures onto structures of robust distributed computer systems

M.S.Tarkov
Novosibirsk
Pages: 72–83

Abstract

A technique for mapping parallel program structures onto structures of robust distributed computer systems (CS) is proposed. Effective algorithms are developed for implementation of the technique stages: 1) a heuristic algorithm for mapping nodes of the parallel program graph onto the graph of the distributed CS; the algorithm substantially reduces the mapping time with respect to the well-known Bokhari algorithm; 2) a decent- ralized algorithm for mapping the program graph edges which do not coincide with edges of the CS graph onto shortest paths on the CS graph. Mapping one-dimensional (line, ring) and two-dimensional (mesh, torus) parallel program structures onto regular structures (torus, two-dimensional circulant, and hypercube) of robust computer systems with faulty components (computers and intercomputer connections) is investigated. It is shown that: one-dimensional parallel program structures are mapped onto structures of distributed CS better than two-dimensional ones; and if defects (failures of the CS components) arise in the CS structure, the quality of mapping one-dimensional structures deteriorates less than the quality of mapping two-dimensional structures.