Article

Free access

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

Authors:

J. E. Jang,

S. W. Choi,

W. K. ChoAuthors Info & Claims

Supercomputing '89: Proceedings of the 1989 ACM/IEEE conference on Supercomputing

Pages 314 - 325

https://doi.org/10.1145/76263.76297

Published: 01 August 1989 Publication History

PDF eReader

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 _nC_k, the gray strategy by _nC_k/2 and Al-Dhelaan [8] by _nC_k/(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]

K. Hwang and F.A. Briggs, Computer Architecture and Parallel Processing, New York: McGraw_Hill, 1984

Digital Library

Google Scholar

[2]

R. M. Chamberlain, "Gray codes, Fast Fourier Transformations and Hypercubes", Parallel Computing, 6, 1988, pp. 225- 233.

Crossref

Google Scholar

[3]

M. Chen and K.G. Shin, "Processor Allocation in an N-cube Multiprocessor Using Gray Codes", IEEE Trans. Computer, Dec. 1987 pp. 1396-1407.

Digital Library

Google Scholar

[4]

M. Chert and K.G. Shin, "task Migration in Hypercube Multiprocessor", Proc. 16th Annual Int'l Syrup. on Computer Architecture. Jun 1989, pp. 105-111

Digital Library

Google Scholar

[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

Google Scholar

[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.

Digital Library

Google Scholar

[7]

H. P. Kattesff, "Incomplete hypercubes", IEEE Trans. Computer, May 1988, pp. 604-608.

Digital Library

Google Scholar

[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.

Google Scholar

[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

Google Scholar

[10]

P. Ramanathan and K.G. Shin, "Reliable Broadcasting in Hypercube Multicomputers", IEEE Trans. on Comp. Dec 1988, pp 1654-1657.

Digital Library

Google Scholar

[11]

Y. S ead and M.H. Schultz, 'Topological properties of Hypercubes", IEEE Trans. on Computer, Jul 1988, pp 867-872

Digital Library

Google Scholar

[12]

Z. Kohavi, Switching and Finite Automata Theory, New York: McGraw-Hill, 1978

Digital Library

Google Scholar

Cited By

View all

Jang JSood A(1990)An optimal fault-tolerant broadcasting algorithm for a hypercube multiprocessorProceedings of the 1990 ACM annual conference on Cooperation10.1145/100348.100363(96-102)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1145/100348.100363
Jang J(1990)Reliable broadcasting algorithm for a cube-connected cycles networkNinth Annual International Phoenix Conference on Computers and Communications. 1990 Conference Proceedings10.1109/PCCC.1990.101593(3-9)Online publication date: 1990
https://doi.org/10.1109/PCCC.1990.101593

Index Terms

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

Recommendations

Processor allocation in an N-cube multiprocessor using gray codes

The processor allocation problem in an n-dimensional hypercube (or an n-cube) multiprocessor is similar to the conventional memory allocation problem. The main objective in both problems is to maximize the utilization of available resources as well as ...
Processor Allocation in k-ary n-cube Multiprocessors
ISPAN '97: Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks

Composed of various topologies, the k-ary n-cube system is desirable for accepting and executing topologically different tasks. In this paper, we propose a new allocation strategy to utilize the large amount of processor resources in the k-ary n-cubes. ...
A processor allocation strategy using cube coalescing in hypercube multicomputers
SPDP '93: Proceedings of the 1993 5th IEEE Symposium on Parallel and Distributed Processing

We propose a new processor allocation strategy for hypercube multicomputers. The allocation strategy is called cube coalescing (CC) strategy since it uses a cube coalescing method to find an available subcube which is formed by the non-neighbored nodes. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Supercomputing '89: Proceedings of the 1989 ACM/IEEE conference on Supercomputing

August 1989

849 pages

ISBN:0897913418

DOI:10.1145/76263

Chairman:
F. Ron Bailey

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Los Alamos National Labs: Los Alamos National Labs
NASA: National Aeronatics and Space Administration
Argonne Natl Lab: Argonne National Lab

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SC '89

Sponsor:

SIGARCH
IEEE-CS

SC '89: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 17, 1989

Nevada, Reno, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
219
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jang JSood A(1990)An optimal fault-tolerant broadcasting algorithm for a hypercube multiprocessorProceedings of the 1990 ACM annual conference on Cooperation10.1145/100348.100363(96-102)Online publication date: 1-Jan-1990
https://dl.acm.org/doi/10.1145/100348.100363
Jang J(1990)Reliable broadcasting algorithm for a cube-connected cycles networkNinth Annual International Phoenix Conference on Computers and Communications. 1990 Conference Proceedings10.1109/PCCC.1990.101593(3-9)Online publication date: 1990
https://doi.org/10.1109/PCCC.1990.101593

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Processor allocation in an N-cube multiprocessor using gray codes

Processor Allocation in k-ary n-cube Multiprocessors

A processor allocation strategy using cube coalescing in hypercube multicomputers