A Repeated Mapping Scheme of Task Modules with Minimum Communication Cost in Hypercube Multicomputers, ETRI Journal, vol.20, no.4, Dec. 1998, pp.327-345.

A Repeated Mapping Scheme of Task Modules with Minimum Communication Cost in Hypercube Multicomputers

Abstract :

This paper deals with the problem of one-to-one mapping of 2ⁿtask modules of a parallel progeam to an n-dimensional hypercube multicomputer so as to minimize the total communication cost during the execution of the task. The problem of finding an optimal

Key word :

cutset, mincut, maxcut, NP-Complete, gain admissibility, balanced partition

DOI :

http://dx.doi.org/10.4218/etrij.98.0198.0402

Cite this :

Joo-Man Kim, and Cheol-Hoon Lee, "A Repeated Mapping Scheme of Task Modules with Minimum Communication Cost in Hypercube Multicomputers," ETRI Journal, vol. 20, no. 4, Dec. 1998, pp. 327-345.
http://dx.doi.org/10.4218/etrij.98.0198.0402

References :

1. M.-S. Chen and K.G. Shin, "Embedding of Interacting Task Modules into a Hypercube," Proc. of the Second Conf. on Hypercube Concurrent Computers and Applications, Oct. 1986, pp. 122-129.

2. Bernd Becker and Hans-Ulrich Simon, "HOW ROBUST IS THE N-CUBE?," Annual Symposium on Foundations of Computer Science (Proceedings), 1986, pp. 283-291.

3. Jong Kim, Chita R. Das and Woei Lin, "Processor allocation scheme for hypercube computers, " Proceedings of the International Conference on Parallel Processing, 1989, pp. 231-238.

4. Justin Rattner, "CONCURRENT PROCESSING: A NEW DIRECTION IN SCIENTIFIC COMPUTING," AFIPS Conference Proceedings, vol. 54, 1985, pp. 157-166.

5. John P. Hayes, Trevor N. Mudge, Quentin F. Stout, Stephen Colley and John Palmer, "ARCHITECTURE OF A HYPERCUBE SUPERCOMPUTER," Proceedings of the International Conference on Parallel Processing, 1986, pp. 653-660.

6. J.C. Peterson, J.O. Tuazon, D. Lieberman and M. Pniel, "MARK III HYPERCURVE-ENSEMBLE CONCURRENT COMPUTER," Proceedings of the International Conference on Parallel Processing, 1985, pp. 71-73.

7. W.D. Hills, The Connection Machine, MIT Press, Cambridge, MA, 1985.

8. Shahid H. Bokhari, "ON THE MAPPING PROBLEM," IEEE Transactions on Computers, vol. C-30, no. 3, 1981, pp. 207-214.

9. Ming-Syan Chen and Kang G. Shin, "PROCESSOR ALLOCATION IN AN N-CUBE MULTIPROCESSOR USING GRAY CODES," IEEE Transactions on Computers, vol. C-36, no. 12, 1987, pp. 1396-1407.

10. Andre M. Van Tilborg and Larry D. Wittie, "WAVE SCHEDULING - DECENTRALIZED SCHEDULING OF TASK FORCES IN MULTICOMPUTERS," IEEE Transactions on Computers, vol. C-33, no. 9, 1984, pp. 835-844.

11. D.W. Krumme, K.N. Venkataraman and G. Cybenko, "Hypercube Embedding is NP-Complete," Proc. of the First Conf. on Hypercube Concurrent Computers and Applications, Aug. 1985, pp. 148-157.

12. W.-K. Chen and E.F. Gehringer, "A Graph-oriented Mapping Strategy for a Hypercube," Proc. of the Third Conf. on Hypercube Concurrent Computers and Applications, Jan. 1988, pp. 200-209.

13. F. Ercal, J. Ramanujan and P. Sadayappan, "Task Allocation onto a Hypercube by Recursive Mincut Bipartitioning," Proc. of the Third Conf. on Hypercube Concurrent Computers and Applications, Jan. 1988, pp. 210-221.

14. B.W. Kernighan and S. Lin, "An Efficient Heuristic Procedure for Partitioning Graphs," Bell Syst. Tech. J., vol. 49, Feb. 1970, pp. 291-307.

15. C.-H. Lee, C.-I. Park and M. Kim, "Efficient algorithm for graph-partitioning problem using a problem transformation method," Computer-Aided Design, vol. 21, no. 10, 1989, pp. 611-618.

16. B.-R. Tsai and K.G. Shin, "Communication-oriented Assignment of Task Modules in Hypercube Multicomputers," Proc. of 12-th Int'l Conf. on Distributed Comput. Syst., June 1992, pp. 38-45.

17. P. Kermani and L. Kleinrock, "Virtual cut-through: A new computer communication switching technique," Computer Networks (1976), vol. 3, no. 4, 1979, pp. 267-286.

18. Harold S. Stone, "MULTIPROCESSOR SCHEDULING WITH THE AID OF NETWORK FLOW ALGORITHMS," IEEE Transactions on Software Engineering, vol. SE-3, no. 1, 1977, pp. 85-93.

19. Cheol-Hoon Lee, Dongmyun Lee and Myunghwan Kim, "Optimal task assignment in linear array networks," IEEE Transactions on Computers, vol. 41, no. 7, 1992, pp. 877-880.

20. C.-H. Lee and K.G. Shin, "Optimal task assignment in homogeneous networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 2, 1997, pp. 119-129.

Reader
Evaluation :

Important Innovative Insightful Useful

This article has been downloaded 2,942 times.

Regular Papers

	Evaluation of Cluster-based System for the OLTP Application
	Woo-Jong Hahn, Suk-Han Yoon, Kangwoo Lee, and Michel Dubois ETRI Journal, vol.20, no.4, Dec. 1998, pp.301-326 http://dx.doi.org/10.4218/etrij.98.0198.0401

	A Repeated Mapping Scheme of Task Modules with Minimum Communication Cost in Hypercube Multicomputers
	Joo-Man Kim, and Cheol-Hoon Lee ETRI Journal, vol.20, no.4, Dec. 1998, pp.327-345 http://dx.doi.org/10.4218/etrij.98.0198.0402

	An Asynchronous Algorithm for Balancing Unpredictable Workload on Distributed-Memory Machines
	Yongwha Chung, Jin-Won Park, and Suk-Han Yoon ETRI Journal, vol.20, no.4, Dec. 1998, pp.346-360 http://dx.doi.org/10.4218/etrij.98.0198.0403

	Improved Multi-band Transfer Matrix for Calculating Eigenvalues and Eigenfunctions of Quantum Well and Superlattice Structure
	Byoung-Whi Kim, Yong Il Jun, and Hee Bum Jung ETRI Journal, vol.20, no.4, Dec. 1998, pp.361-378 http://dx.doi.org/10.4218/etrij.98.0198.0404

	Temperature Distribution of a Low Temperature Heat Pipe with Multiple Heaters for Electronic Cooling
	Hong-Koo Noh, and Kyu-Sub Song ETRI Journal, vol.20, no.4, Dec. 1998, pp.379-393 http://dx.doi.org/10.4218/etrij.98.0198.0405