Preemptive Job Scheduling in Star Graph Networks

In this paper we develop a feasibility algorithm for preemptively scheduling a given set of jobs with dimension and time requirements on a star graph network of given size with a given deadline. We show that the algorithm runs in O(n log n) time where n is the number of jobs. 1 Introduction One of the attractive topologies for constructing the symmetric interconnection networks is the star graph [AK89, AK87]. The star graph, being a member of the class of Cayley graphs, has been shown to possess appealing features including low degree of the node, small diameter, partitionability, symmetry, and high degree of fault-tolerance. For this reason, recently much research has been directed toward studying properties of these star graphs [DT94, QMA92], its fault-tolerance aspects [Lat93], or implementing various algorithms on it [QAM94, MS90, FA91, MS92]. When parallel algorithms are mapped and implemented on a massively parallel architecture, the dimension of the network plays an important r..