For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Sg-Lattice: A Model for Processor Allocation for the Star Graph
Fan WU Ching-Chi HSU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1999/03/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Hardware and Design
allocation, star graph, first-fit, star code, Sg-lattice,
Full Text: PDF(322.6KB)>>
The star graph has been known as an attractive alternative to the hypercube multiprocessor. Like the hypercube, the star graph possesses the properties of symmetry, partionability and fault tolerance, but with a smaller diameter and degree than those of the hypercube. When tasks arrive at the star graph, the tasks should be assigned appropriate free processors before execution. A new model, called Star graph (Sg)-lattice, is proposed to model the construction and free configuration of the star graph. Based on this model, the Sg-lattice scheme can fully recognize the substars. Finally, mathematical analyses and simulation results show that the Sg-lattice scheme outperforms the previous work in the storage and time complexities and the average allocation time.