Title

Task allocation in the star graph

Document Type

Article

Abstract

The star graph has been known as an attractive candidate for interconnecting a large number of processors. The hierarchy of the star graph allows the assignment of its special subgraphs (substars), which have the same topological features as the original graph, to a sequence of incoming tasks. The paper proposes a new code, called star code (SC), to recognize available substars of the required size in the star graph. It is shown that task allocation based on the SC is statically optimal. The recognition ability of a given SC or a class of SC's is derived. The optimal number of SC's required for the complete substar recognition in an n-dimensional star is shown to be 2n-2.

Disciplines

Computer and Systems Architecture | Digital Communications and Networking | Electrical and Computer Engineering | Systems and Communications

Permissions

Use Find in Your Library, contact the author, or interlibrary loan to garner a copy of the item. Publisher policy does not allow archiving the final published version. If a post-print (author's peer-reviewed manuscript) is allowed and available, or publisher policy changes, the item will be deposited.