Preemptive scheduling of independent jobs on a hypercube. (English) Zbl 0658.68041

Chen, Guan-Ing; Lai, Ten-Hwang

Inf. Process. Lett. 28, No. 4, 201-206 (1988).

We consider the problem of scheduling n independent jobs on an m- dimensional hypercube system to minimize the finishing time, where each job \(J_ i\) is associated with a dimension \(d_ i\) and a processing time \(t_ i\), meaning that \(J_ i\) requires a \(d_ i\)-dimensional subcube for \(t_ i\) units of time. An \(O(n^ 2)\) algorithm is presented that decides if all n jobs can be finished by a given deadline T. Using this algorithm, one may obtain a minimum-finishing-time schedule in polynomial time.

MSC:

68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25	Analysis of algorithms and problem complexity

Keywords:

preemptive scheduling; hypercube

References:

[1]	Chen, G.-I.; Lai, T.-H., Scheduling independent jobs on hypercubes, Proc. conf. on theoritical aspects of computer science, 273-280, (1988)
[2]	Chen, M.-S.; Shin, K.-G., Embedment of interacting task modules into a hypercube multiprocessor, Proc. 2nd hypercube conf., 121-129, (1986)
[3]	Chen, M.-S.; Shin, K.-G., Processor allocation in an N-cube multiprocessor using gray codes, IEEE trans. comput., C-36, 1396-1407, (1987)
[4]	Hayes, J.P.; Mudge, T.N.; Stout, Q.F.; Colley, S.; Palmer, J., Architecture of a hypercube supercomputer, Proc. internat. conf. on parallel processing, 653-660, (1986)
[5]	Intel corporation, ipsc/2, (1988), Intel Corporation Beaverton, OR
[6]	Peterson, J.C.; Tuazon, J.O.; Lieberman, D.; Pniel, M., The mark III hypercube-ensemble concurrent computer, Proc. internat. conf. on parallel processing, 71-75, (1985)
[7]	Seitz, C.L., The cosmic cube, Comm. ACM, 28, 22-33, (1985)