zbMATH — the first resource for mathematics

Preemptive scheduling of independent jobs on a hypercube. (English) Zbl 0658.68041
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.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.