Scheduling of Jobs in a Hypercube Processing System

When a job is processed in a hypercube multi-processor, it is allocated a cube of processing elements of the requisite size. There are three distinct costs involved in the hypercube scheduling problem: the cost of detecting a free cube (allocation), the cost of migrating jobs and merging the free spaces to accommodate a larger cube request (relocation) and the cost of not meeting the due date (tardiness). Traditionally, research in this area has focused on finding efficient algorithms for allocating a free cube (if any) in the hypercube system. The relocation cost has been treated as an independent cost metric. The role of scheduling has not received much attention and present subcube allocation methods assume a first-come-first-serve (FCFS) approach over the input job set.This paper considers the underlying scheduling issues in a hypercube processing system and shows how techniques other than FCFS scheduling of the incoming jobs can help in reducing the relocation cost and hence the overall subcube resource assignment cost. We discuss five simple and easily implementable dispatching heuristics, and compare their relative performance with the FCFS scheduling rule to demonstrate the advantages of scheduling in subcube allocation.