SCHEDULING OF JOBS IN A HYPERCUBE PROCESSING SYSTEM

When a job is processed in a hypercube multi-processor, it is allocate d 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 (relocat ion) and the cost of not meeting the due date (tardiness). Traditional ly, research in this area has focused on finding efficient algorithms for allocating a free cube (if any) in the hypercube system. The reloc ation cost has been treated as an independent cost metric. The role of scheduling has not received much attention and present subcube alloca tion methods assume a first-come-first-serve (FCFS) approach over the input job set. This paper considers the underlying scheduling issues i n a hypercube processing system and shows how techniques other than FC FS scheduling of the incoming jobs can help in reducing the relocation cost and hence the overall subcube resource assignment cost. We discu ss five simple and easily implementable dispatching heuristics, and co mpare their relative performance with the FCFS scheduling rule to demo nstrate the advantages of scheduling in subcube allocation.