Title :
H-lattice: a geometric model for processor allocation in hypercubes
Author :
Wu, Fan ; Hsu, Ching-Chi
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
The H-lattice is a geometric model for describing the construction and occupied configuration of the hypercube multiprocessors. In addition, it can model the faulty hypercube in the presence of faulty processors and/or links. The H-lattice scheme, based on this model, can allocate fault free subcubes for various allocations, such as first/best/worst/next fit, and subcube inclusion/ exclusion allocations, in a more simple and efficient manner than ever. In this scheme, the viewpoint of the minimum destroyed degree is introduced to select the best-fit subcube, which is proved to be better than that of other schemes. Mathematical analyses and simulation are also derived to demonstrate the efficiency of the proposed scheme
Keywords :
computational geometry; fault tolerant computing; hypercube networks; processor scheduling; reliability; resource allocation; H-lattice; best-fit subcube; fault free subcubes; faulty hypercube modelling; faulty processors; first/best/worst/next fit; geometric model; hypercube multiprocessors; mathematical analyses; minimum destroyed degree; occupied configuration; processor allocation; subcube inclusion/ exclusion allocations; Computer science; Concurrent computing; Costs; Hypercubes; Lattices; Mathematical analysis; Memory management; Resource management; Solid modeling; Topology;
Conference_Titel :
Algorithms & Architectures for Parallel Processing, 1996. ICAPP 96. 1996 IEEE Second International Conference on
Print_ISBN :
0-7803-3529-5
DOI :
10.1109/ICAPP.1996.562857
