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

fYear

1996

fDate

11-13 Jun 1996

Firstpage

53

Lastpage

60

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Algorithms & Architectures for Parallel Processing, 1996. ICAPP 96. 1996 IEEE Second International Conference on

Print_ISBN

0-7803-3529-5

Type

conf

DOI

10.1109/ICAPP.1996.562857

Filename

562857