Disjoint Task Allocation Algorithms for MIN Machines with Minimal Conflicts

Chita R. Das, Chansu Yu

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)373-387
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
StatePublished - Apr 1995

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Disjoint Task Allocation Algorithms for MIN Machines with Minimal Conflicts'. Together they form a unique fingerprint.

Cite this