TASK ALLOCATION IN THE STAR GRAPH

The star graph has been known as an attractive candidate for interconn ecting a large number of processors. The hierarchy of the star graph a llows the assignment of its special subgraphs (substars), which have t he same topological features as the original graph, to a sequence of i ncoming tasks. The paper proposes a new code, called star code (SC), t o recognize available substars of the required size in the star graph. It is shown that task allocation based on the SC is statically optima l. 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 recogni tion in an n-dimensional star is shown to be 2(n-2).