Sg-Lattice: A Model for Processor Allocation for the Star Graph

Fan WU  Ching-Chi HSU  

IEICE TRANSACTIONS on Information and Systems   Vol.E82-D   No.3   pp.637-644
Publication Date: 1999/03/25
Online ISSN: 
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)>>
Buy this Article

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.