ISSN:
1573-0484
Keywords:
parallel architectures
;
initialization
;
linear arrays
;
rings
;
binary trees
;
meshes
;
tori
;
meshes with broadcasting
;
hypercubes
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract The incremental and dynamic construction of interconnection networks from smaller components often leaves the fundamental problem of assigning addresses to processors to be contended with at power-up time. The problem is fundamental, for virtually all parallel algorithms known to the authors assume that the processors know their global coordinates within the newly created entity. We refer to this problem as the initialization problem. Rather surprisingly, the initialization problem has not received much attention in the literature. Our main contribution is to present parallel algorithms for the initialization problem on a number of network topologies, including complete binary trees, meshes of trees, pyramids, linear arrays, rings, meshes, tori, higher dimensional meshes and tori, hypercubes, butterflies, linear arrays with a global bus, rings with a global bus and meshes with multiple broadcasting, under various assumptions about edge labels, leader existence, and a priori knowledge of the number of nodes in the network. With two exceptions, the proposed algorithms are optimal.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1023/A:1008120609055
Permalink
