Mapping Tasks onto Heterogeneous Computing Systems
Resumo
The goal of this invited tutorial paper is to provide an overview of three current research efforts in heterogeneous computing that focus on methods for determining a mapping of an application onto a heterogeneous suite of machines. The first study involves a genetic-algorithm approach for mapping the subtasks of an application task onto the machines in a distributed heterogeneous system. This is a static compile-time approach that must be used off-line (prior to task execution) due to its long run time. The second topic is the high-level design of components of an intelligent operating system for mapping and dynamically remapping automatic target recognition tasks onto a heterogeneous parallel platform. The intelligent operating system uses a new technique for dynamically selecting new mappings on-line during task execution from among choices precomputed off-line. Last, some initial preliminary results from a new research project for designing a dynamic mapping heuristic that does not use precomputed mappings is described. This dynamic heuristic is fast and is suitable for operation during application execution. Future research directions are discussed for all three projects.
Palavras-chave:
automatic target recognition, distributed computing, genetic algorithms, heterogeneous computing, mapping, matching, MSHN, parallel processing, scheduling
Referências
J. R. Budenske, R. S. Ramanujan, and H. J. Siegel, "On-line use of off-line derived mappings for iterative automatic target recognition tasks and a particular class of hardware platforms," 6th Heterogeneous Computing Workshop (HCW '97), Apr. 1997, pp. 96-110.
J. R. Budenske, R. S. Ramanujan, and H. J. Siegel, "Modeling ATR applications for intelligent execution upon a heterogeneous computing platform," 1997 IEEE Int'l Conf. Systems, Man, and Cybernetics (SMC '97), Oct. 1997, to appear.
C. H. Chu, E. J. Delp, L. H. Jamieson, H. J. Siegel, F. J. Weil, and A. B. Whinston, "A model for an intelligent operating system for executing image understanding tasks on a reconfigurable parallel architecture," J. of Parallel and Distributed Computing, Vol. 6, No. 3, June 1989, pp. 598-622.
P. David, S. Balakirsky, and D. Hillis, "A real-time automatic target acquisition system," Conf. on Unmanned Vehicle Systems, July 1990, pp. 183-198.
P. David, P. Emmerman, and S. Ho, "A scalable architecture system for automatic target recognition,'' 13th AIAA/IEEE Digital Avionics Systems Conf., Oct. 1994, pp. 414-420.
L. Davis, ed., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, NY, 1991.
M. M. Eshaghian, ed., Heterogeneous Computing, Artech House, Norwood, MA, 1996.
D. Femandez-Baca, "Allocating modules to processors in a distributed system," IEEE Trans. on Software Engineering, Vol. SE-15, No. 11, Nov. 1989, pp. 1427-1436.
R. F. Freund, B. R. Carter, D. Watson, E. Keith, F. Mirabile, and H. J. Siegel, "Generational scheduling for heterogeneous computing systems," Information Science Journal, Special Issue on Parallel and Distributed Processing Techniques and Applications, accepted and scheduled to appear in 1997.
R. F. Freund, T. Kidd, D. Hensgen, and L. Moore, "SmartNet: A scheduling framework for meta-computing," 2nd Int'l Symp. Parallel Architectures, Algorithms, and Networks (ISPAN '96), June 1996, pp. 514-521.
R. F. Freund and H. J. Siegel, "Heterogeneous processing,'' IEEE Computer, Special Issue on Heterogeneous Processing, Vol. 26, No. 6, June 1993, pp. 13-17.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
B. Hamidzadeh, D. J. Lilja, and Y. Atif, "Dynamic scheduling techniques for heterogeneous computing systems," Concurrency: Practice and Experience, Vol. 7, No. 7, Oct. 1995, pp. 633-652.
J. H. Holland, Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, MI, 1975.
M. A. Iverson, F. Ozguner, and G. J. Follen, "Parallelizing existing applications in a distributed heterogeneous environment," 4th Heterogeneous Computing Workshop (HCW '95), Apr. 1995, pp. 93-100.
A. Khokhar, V. K. Prasanna, M. Shaaban, and C. L. Wang," Heterogeneous computing: Challenges and opportunities,'' IEEE Computer, Vol. 26, No. 6, June 1993, pp. 18-27.
A. E. Klietz, A. V. Malevsky, and K. Chin-Purcell, "A case study in metacomputing: Distributed simulations of mixing in turbulent convection," 2nd Workslwp on Heterogeneous Processing (WHP '93), Apr. 1993, pp. 101-106.
C. Leangsuksun, J. Potter, and S. Scott, "Dynamic task mapping algorithms for a distributed heterogeneous computing environment," 4th Heterogeneous Computing Workshop (HCW '95), Apr. 1995, pp. 30-34.
J. L. Ribeiro Filho and P. C. Treleaven, "Genetic-algorithm programming environments," IEEE Computer, Vol. 27, No. 6, June 1994, pp. 28-43.
J. Rosenman and T. Cullip, "High-performance computing in radiation cancer treatment," CRC Critical Reviews in Biomedical Engineering, Vol. 20, 1992, pp. 391-402.
G. Rudolph, "Convergence analysis of canonical genetic algorithms," IEEE Trans. Neural Networks, Vol. 5, No. 1, Jan. 1994, pp. 96-101.
H. J. Siegel, J. K. Antonio, R. C. Metzger, M. Tan, and Y. A. Li, "Heterogeneous computing," in Parallel and Distributed Computing Handbook, A. Y. Zomaya, ed., McGraw-Hill, New York, NY, 1996, pp. 725-761.
H. J. Siegel, H. G. Dietz, and J. K. Antonio, "Software support for heterogeneous computing," in The Computer Science and Engineering Handbook, A. B. Tucker, Jr., ed., CRC Press, Boca Raton, FL, 1997, pp. 1886-1909.
"Special report: Gigabit network testbeds," IEEE Computer, Vol. 23, No. 9, Sep. 1990, pp. 77-80.
M. Srinivas and L. M. Patnaik, "Genetic algorithms: A survey," IEEE Computer, Vol. 27, No. 6, June 1994, pp. 17-26.
V. S. Sunderam, "Design issues in heterogeneous network computing," Workshop on Heterogeneous Processing (WHP '92), revised edition, Mar. 1992, pp. 101-112.
M. Tan, H. J. Siegel, J. K. Antonio, and Y. A. Li, "Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system," IEEE Trans. on Parallel and Distributed Systems, accepted and scheduled to appear in 1997.
D. Tolmie and J. Renwick, "HiPPI: Simplicity yields success," IEEE Network, Vol. 7, No. 1, Jan. 1993, pp. 28-32.
L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski. "Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach," J. of Parallel and Distributed Computing, Special Issue on Parallel Evolutionary Computing, accepted and scheduled to appear in 1998. (A preliminary version appeared in the 5th Heterogeneous Computing Workshop (HCW '96), Apr. 1996, pp. 72-85.)
J. R. Budenske, R. S. Ramanujan, and H. J. Siegel, "Modeling ATR applications for intelligent execution upon a heterogeneous computing platform," 1997 IEEE Int'l Conf. Systems, Man, and Cybernetics (SMC '97), Oct. 1997, to appear.
C. H. Chu, E. J. Delp, L. H. Jamieson, H. J. Siegel, F. J. Weil, and A. B. Whinston, "A model for an intelligent operating system for executing image understanding tasks on a reconfigurable parallel architecture," J. of Parallel and Distributed Computing, Vol. 6, No. 3, June 1989, pp. 598-622.
P. David, S. Balakirsky, and D. Hillis, "A real-time automatic target acquisition system," Conf. on Unmanned Vehicle Systems, July 1990, pp. 183-198.
P. David, P. Emmerman, and S. Ho, "A scalable architecture system for automatic target recognition,'' 13th AIAA/IEEE Digital Avionics Systems Conf., Oct. 1994, pp. 414-420.
L. Davis, ed., Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, NY, 1991.
M. M. Eshaghian, ed., Heterogeneous Computing, Artech House, Norwood, MA, 1996.
D. Femandez-Baca, "Allocating modules to processors in a distributed system," IEEE Trans. on Software Engineering, Vol. SE-15, No. 11, Nov. 1989, pp. 1427-1436.
R. F. Freund, B. R. Carter, D. Watson, E. Keith, F. Mirabile, and H. J. Siegel, "Generational scheduling for heterogeneous computing systems," Information Science Journal, Special Issue on Parallel and Distributed Processing Techniques and Applications, accepted and scheduled to appear in 1997.
R. F. Freund, T. Kidd, D. Hensgen, and L. Moore, "SmartNet: A scheduling framework for meta-computing," 2nd Int'l Symp. Parallel Architectures, Algorithms, and Networks (ISPAN '96), June 1996, pp. 514-521.
R. F. Freund and H. J. Siegel, "Heterogeneous processing,'' IEEE Computer, Special Issue on Heterogeneous Processing, Vol. 26, No. 6, June 1993, pp. 13-17.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989.
B. Hamidzadeh, D. J. Lilja, and Y. Atif, "Dynamic scheduling techniques for heterogeneous computing systems," Concurrency: Practice and Experience, Vol. 7, No. 7, Oct. 1995, pp. 633-652.
J. H. Holland, Adaptation in Natural and Artificial Systems, Univ. of Michigan Press, Ann Arbor, MI, 1975.
M. A. Iverson, F. Ozguner, and G. J. Follen, "Parallelizing existing applications in a distributed heterogeneous environment," 4th Heterogeneous Computing Workshop (HCW '95), Apr. 1995, pp. 93-100.
A. Khokhar, V. K. Prasanna, M. Shaaban, and C. L. Wang," Heterogeneous computing: Challenges and opportunities,'' IEEE Computer, Vol. 26, No. 6, June 1993, pp. 18-27.
A. E. Klietz, A. V. Malevsky, and K. Chin-Purcell, "A case study in metacomputing: Distributed simulations of mixing in turbulent convection," 2nd Workslwp on Heterogeneous Processing (WHP '93), Apr. 1993, pp. 101-106.
C. Leangsuksun, J. Potter, and S. Scott, "Dynamic task mapping algorithms for a distributed heterogeneous computing environment," 4th Heterogeneous Computing Workshop (HCW '95), Apr. 1995, pp. 30-34.
J. L. Ribeiro Filho and P. C. Treleaven, "Genetic-algorithm programming environments," IEEE Computer, Vol. 27, No. 6, June 1994, pp. 28-43.
J. Rosenman and T. Cullip, "High-performance computing in radiation cancer treatment," CRC Critical Reviews in Biomedical Engineering, Vol. 20, 1992, pp. 391-402.
G. Rudolph, "Convergence analysis of canonical genetic algorithms," IEEE Trans. Neural Networks, Vol. 5, No. 1, Jan. 1994, pp. 96-101.
H. J. Siegel, J. K. Antonio, R. C. Metzger, M. Tan, and Y. A. Li, "Heterogeneous computing," in Parallel and Distributed Computing Handbook, A. Y. Zomaya, ed., McGraw-Hill, New York, NY, 1996, pp. 725-761.
H. J. Siegel, H. G. Dietz, and J. K. Antonio, "Software support for heterogeneous computing," in The Computer Science and Engineering Handbook, A. B. Tucker, Jr., ed., CRC Press, Boca Raton, FL, 1997, pp. 1886-1909.
"Special report: Gigabit network testbeds," IEEE Computer, Vol. 23, No. 9, Sep. 1990, pp. 77-80.
M. Srinivas and L. M. Patnaik, "Genetic algorithms: A survey," IEEE Computer, Vol. 27, No. 6, June 1994, pp. 17-26.
V. S. Sunderam, "Design issues in heterogeneous network computing," Workshop on Heterogeneous Processing (WHP '92), revised edition, Mar. 1992, pp. 101-112.
M. Tan, H. J. Siegel, J. K. Antonio, and Y. A. Li, "Minimizing the application execution time through scheduling of subtasks and communication traffic in a heterogeneous computing system," IEEE Trans. on Parallel and Distributed Systems, accepted and scheduled to appear in 1997.
D. Tolmie and J. Renwick, "HiPPI: Simplicity yields success," IEEE Network, Vol. 7, No. 1, Jan. 1993, pp. 28-32.
L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski. "Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach," J. of Parallel and Distributed Computing, Special Issue on Parallel Evolutionary Computing, accepted and scheduled to appear in 1998. (A preliminary version appeared in the 5th Heterogeneous Computing Workshop (HCW '96), Apr. 1996, pp. 72-85.)
Publicado
07/10/1997
Como Citar
SIEGEL, Howard Jay; MEHESWARAN, Muthucumaru.
Mapping Tasks onto Heterogeneous Computing Systems. In: TUTORIAIS - INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 9. , 1997, Campos do Jordão/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1997
.
p. 3-17.
DOI: https://doi.org/10.5753/sbac-pad_estendido.1997.22647.
