Task Allocation in the Star Graph

Document Type

Article

Publication Date

11-1994

Publication Title

IEEE Transactions on Parallel and Distributed Systems

Volume

5

First page number:

1220

Last page number:

1224

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.

Keywords

Cayley graphs; Computer network resources; Graph theory; Parallel algorithms; Parallel processing (Electronic computers); Resource allocation--Data processing

Disciplines

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

Language

English

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.

UNLV article access

Search your library

Share

COinS