MIGRATION OF TASKS IN INTERCONNECTION NETWORKS BASED ON THE STAR GRAPH

The hierarchy of the star graph allows the assignment of its special s ubgraphs (substars), which have the same topological features as the o riginal graph, to a sequence of incoming tasks, The procedure for task allocation in the star graph can be done using the star code and the allocation tree constructed based on this code. In this paper, the opt imal set of codes which can collectively recognize a set of distinct s ubstars is derived. It is shown that using only (n - 1) codes, almost half of the existing substars in an n-dimensional star is recognizable for n less than or equal to 9. When relinquishment of tasks is consid ered, task migration could potentially improve the utilization of netw ork resources by reducing/eliminating the fragmentation caused as a re sult of task deallocation, A deadlock-free procedure is presented to m igrate a task, distributed over the nodes of one substar, to the nodes of the other substar wherein: (i) subtasks travel in parallel via dis joint paths; (ii) the adjacency among the mapped nodes is preserved. T he procedure can be made distributed with a slight modification, The w ork can be extended to other hierarchical networks based on permutatio n group. (C) 1995 Academic Press, Inc.