A new approach to processor allocation and task migration in an N-cube multiprocessor

ABSTRACT

We propose a new strategy to recognize the maximum subcube in an n-cube multiprocessor. This subcube recognition algorithm can be done in both serial and parallel and analyzed. This strategy will enhance the performance drastically so that our algorithm will outperform the buddy system by a factor nCk, the gray strategy by nCk/2 and Al-Dhelaan [8] by nCk/(k(n-k)+1) in cube recognition. We present a very efficient processor allocation strategy which makes larger contiguous spaces for the new coming job than buddy, gray strategy and Al-Dhelaan [8] do. Furthermore, this new strategy is suitable for static as well as dynamic processors allocation and it results in a less fragmentation and higher fault tolerance. Also we describe an efficient procedure for task migration under the new strategy: 1) goal configuration under the new strategy 2) node-mapping between source and destination node 3) the shortest deadlock-free routing algorithm.

REFERENCES

• 1: Kai Hwang , Faye A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, Inc., New York, NY, 1990
• 2: R. M. Chamberlain, "Gray codes, Fast Fourier Transformations and Hypercubes", Parallel Computing, 6, 1988, pp. 225- 233.
• 3: M.-S. Chen , K. G. Shin, Processor allocation in an N-cube multiprocessor using gray codes, IEEE Transactions on Computers, v.36 n.12, p.1396-1407, Dec. 1987 [doi>10.1109/TC.1987.5009493]
• 4: M.-S. Chen , K. G. Shin, Task migration in hypercube multiprocessors, Proceedings of the 16th annual international symposium on Computer architecture, p.105-111, April 1989, Jerusalem, Israel
• 5: M. Chen and K.G. Shin, "Embedment of interesting task modules into a hypercubemultiprocessor", in Proc. Second Hypercube Conf., Oct 1986, pp. 121-129
• 6: B Becker and H.U. Simon, "How robust is the n-cube. , in Proc. 27th Ann. Syrup. Foundations of Comp. Sci. Oct. 1986 pp. 283-291.
• 7: Howard P. Katseff, Incomplete Hypercubes, IEEE Transactions on Computers, v.37 n.5, p.604-608, May 1988 [doi>10.1109/12.4611]
• 8: A. A1-Dhelaan and B. Bose, "A New strategy for Processor Allocation in an N-cube Multiprocessor", Phoenix Conference on Computer and Communication, Mar 1989. pp. 114-118.
• 9: A. A1-Dhelaan and B. Bose, "Efficient Fault Tolerant Broadcasting Algorithm for the Hypercube", The fourth Conf. on Hypercube Concurrent Comp. and Applications, Monterey, Mar 1989
• 10: P. Ramanathan , K. G. Shin, Reliable Broadcast in Hypercube Multicomputers, IEEE Transactions on Computers, v.37 n.12, p.1654-1657, December 1988 [doi>10.1109/12.9743]
• 11: Youcef Saad , Martin H. Schultz, Topological Properties of Hypercubes, IEEE Transactions on Computers, v.37 n.7, p.867-872, July 1988 [doi>10.1109/12.2234]
• 12: Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling; Routing and layout

General Terms:
Algorithms, Design, Performance