TY - JOUR
T1 - Disjoint Task Allocation Algorithms for MIN Machines with Minimal Conflicts
AU - Das, Chita R.
AU - Yu, Chansu
N1 - Funding Information:
Manuscript received June 17, 1992; revised August 31, 1994. This work was supported in part by the National Science Foundation under Grant MIP-9104485. This paper was presented in part at the 12th International Conference on Distributed Computing Systems, June 1992. C. R. Das is with the Department of Computer Science and Engineering. the Pennsylvania State University, University Park, PA 16802 USA (e-mail: [email protected]). C. Yu is with the Information Technology R&D Laboratory, Goldstar Co., Seoul, Korea. IEEE Log Number 9409337.
PY - 1995/4
Y1 - 1995/4
N2 - Two types of allocation policies, cubic and noncubic, are discussed here. Conflicts through the network and inability to partition the system effectively are the main bottlenecks in a MIN-based system. To solve both the problems, a renaming scheme for input and output ports of a MIN is proposed. We use the baseline MIN as an example in this work and call the renaming scheme as bit reversal (BR) matching pattern. Allocation with the new matching pattern minimizes conflicts and partitions the system completely into independent subsystems. The novelty of this matching pattern is that we can use any dynamic cubic allocation and/or scheduling scheme developed for the hypercubes also for the MIN machines. The BR matching pattern can be used with any kind of MIN. An allocation policy for noncubic tasks is also presented with this matching pattern. Various performance measures with different allocation algorithms are compared via simulation. The advantages of the algorithms with the proposed matching pattern are shown in terms of system efficiency, delay and task miss ratio. This paper addresses task allocation schemes for MIN-based multiprocessors.
AB - Two types of allocation policies, cubic and noncubic, are discussed here. Conflicts through the network and inability to partition the system effectively are the main bottlenecks in a MIN-based system. To solve both the problems, a renaming scheme for input and output ports of a MIN is proposed. We use the baseline MIN as an example in this work and call the renaming scheme as bit reversal (BR) matching pattern. Allocation with the new matching pattern minimizes conflicts and partitions the system completely into independent subsystems. The novelty of this matching pattern is that we can use any dynamic cubic allocation and/or scheduling scheme developed for the hypercubes also for the MIN machines. The BR matching pattern can be used with any kind of MIN. An allocation policy for noncubic tasks is also presented with this matching pattern. Various performance measures with different allocation algorithms are compared via simulation. The advantages of the algorithms with the proposed matching pattern are shown in terms of system efficiency, delay and task miss ratio. This paper addresses task allocation schemes for MIN-based multiprocessors.
UR - http://www.scopus.com/inward/record.url?scp=0029289860&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029289860&partnerID=8YFLogxK
U2 - 10.1109/71.372791
DO - 10.1109/71.372791
M3 - Article
AN - SCOPUS:0029289860
SN - 1045-9219
VL - 6
SP - 373
EP - 387
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 4
ER -