Algoritmos de Escalonamento em Multiprocessadores com Arquitetura Heterogênea
Resumo
Arquiteturas Paralelas Heterogêneas têm-se mostrado uma área promissora de pesquisa no desenvolvimento de computadores de alto desempenho. O escalonamento de tarefas neste ambiente computacional implica em diversos problemas, já que decisões sobre quais processadores serão alocados (e não apenas quantos processadores devem ser alocados) tem que ser tomadas. Este artigo apresenta vários algoritmos de escalonamento estático para multiprocessadores heterogêneos.
Referências
M.S. Pittler, D.M. Powers, D.L. Schanabel, "System development and technology aspects of the IBM 3081 processor complex", IBM Journal of Rescarch and Development, Vol.26, No.1, January 1982 New York, IBM.
A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAullffe, L. Rudolph, and M. Snir, "The NYU Ultracomputer - Designing a MIMD, Shared Memory Parallel Machine", IEEE Transactions on Computers, February 1983, pp.175-189.
Cray Research Inc., "Cray X-MP Series Mainframe Reference Manual", HR-0032, 1982.
W.D. Daniel Hillis, "The Connection Machine", MIT Press, 1985.
Kenneth C. Sevcik, "Characterization of Parallelism in Adaptation and Their Use in Scheduling", Performance Evaluation Review, Vol.17, No.1, May 1989.
Shikharesh Majumbar, Derek L. Eager and Richard B. Bunt, "Scheduling in Multiprogrammed Parallel Systems", ACM - 1988
Thomas L. Casavant and Jon G. Kuhl, "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems", IEEE Transactions on Software Engineering, Vol.14, No.2, Feb. 1988
Mario Gonzalez Jr., "Deterministic Processor Scheduling", Computing Surveys, Vol.9, No.3, Sept. 1977.
John Zahorjan and Cathy McCann, "Scheduling Processors in Shared Memory Multiprocessors", Technical Report.
Clyde P. Kruskal and Alan Weiss, "Allocating Subtasks on Parallel Processors", IEEE Trans. on Software Engineering, Vol.SE-11, No.10, Oct. 1985.
Thomas I. Casavant and Jon G. Kuhl, "Effects of Response and Stability on Scheduling in Distributed Computing Systems", IEEE Trans. on Software Engineering, Vol.14, No.11, Nov. 1988.
Zarka Cvetanovic, "The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems", IEEE Transactions on Computers, Vol.C-36, No.4, April 1987.
Jacek Blazewicz, Mieczyslaw Drabowski and Jan Weglarz, "Scheduling Multiprocessors Tasks to Minimize Schedule Length", IEEE Transactions on Computers, Vol.C-35, No.5, May 1986.
Thomas L. Adam, K.M. Chandy & J.R. Dickson, "A Comparison of List Schedules for Parallel Processing Systems", Communication of the ACM - December 1974, Vol.17, No.12.
Ernest Davis and Jeffrey M. Jaffe, "Algorithms for Scheduling Tasks on Unrelated Processors", Journal of the ACM - October 1981, Vol.28, No.4, pp.721-736.
Daniel Menascé and Virgilio Almeida, "Cost-Performance Analysis of Heterogencity in Supercomputer Architectures, Proceedings of the Supercomputing'90 Conference, New York, EUA, Nov. 1990.
Ellis Horowitz and Sartaj Sahni, "Exact and Approximate Algorithms for Scheduling Nonidentical Processors", Journal of the ACM - April 1976, Vol.23, No.2, pp.317-327.
G. Amdahl, "Validity of the Single Processor Approach to Achieving Large Scale Computing Capability", Proc. AFIPS Spring Joint Comp. Conf. 30, 1967.
Hinori Kasahara and Seinosuke Narita, "Practical Multiprocessor Scheduling Algorithms for Efficient by Parallel Processing", IEEE Transactions on Computers - November 1984, Vol.C-33, No.11.
A. Gottlieb, R. Grishman, C.P. Kruskal, K.P. McAullffe, L. Rudolph, and M. Snir, "The NYU Ultracomputer - Designing a MIMD, Shared Memory Parallel Machine", IEEE Transactions on Computers, February 1983, pp.175-189.
Cray Research Inc., "Cray X-MP Series Mainframe Reference Manual", HR-0032, 1982.
W.D. Daniel Hillis, "The Connection Machine", MIT Press, 1985.
Kenneth C. Sevcik, "Characterization of Parallelism in Adaptation and Their Use in Scheduling", Performance Evaluation Review, Vol.17, No.1, May 1989.
Shikharesh Majumbar, Derek L. Eager and Richard B. Bunt, "Scheduling in Multiprogrammed Parallel Systems", ACM - 1988
Thomas L. Casavant and Jon G. Kuhl, "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems", IEEE Transactions on Software Engineering, Vol.14, No.2, Feb. 1988
Mario Gonzalez Jr., "Deterministic Processor Scheduling", Computing Surveys, Vol.9, No.3, Sept. 1977.
John Zahorjan and Cathy McCann, "Scheduling Processors in Shared Memory Multiprocessors", Technical Report.
Clyde P. Kruskal and Alan Weiss, "Allocating Subtasks on Parallel Processors", IEEE Trans. on Software Engineering, Vol.SE-11, No.10, Oct. 1985.
Thomas I. Casavant and Jon G. Kuhl, "Effects of Response and Stability on Scheduling in Distributed Computing Systems", IEEE Trans. on Software Engineering, Vol.14, No.11, Nov. 1988.
Zarka Cvetanovic, "The Effects of Problem Partitioning, Allocation, and Granularity on the Performance of Multiple-Processor Systems", IEEE Transactions on Computers, Vol.C-36, No.4, April 1987.
Jacek Blazewicz, Mieczyslaw Drabowski and Jan Weglarz, "Scheduling Multiprocessors Tasks to Minimize Schedule Length", IEEE Transactions on Computers, Vol.C-35, No.5, May 1986.
Thomas L. Adam, K.M. Chandy & J.R. Dickson, "A Comparison of List Schedules for Parallel Processing Systems", Communication of the ACM - December 1974, Vol.17, No.12.
Ernest Davis and Jeffrey M. Jaffe, "Algorithms for Scheduling Tasks on Unrelated Processors", Journal of the ACM - October 1981, Vol.28, No.4, pp.721-736.
Daniel Menascé and Virgilio Almeida, "Cost-Performance Analysis of Heterogencity in Supercomputer Architectures, Proceedings of the Supercomputing'90 Conference, New York, EUA, Nov. 1990.
Ellis Horowitz and Sartaj Sahni, "Exact and Approximate Algorithms for Scheduling Nonidentical Processors", Journal of the ACM - April 1976, Vol.23, No.2, pp.317-327.
G. Amdahl, "Validity of the Single Processor Approach to Achieving Large Scale Computing Capability", Proc. AFIPS Spring Joint Comp. Conf. 30, 1967.
Hinori Kasahara and Seinosuke Narita, "Practical Multiprocessor Scheduling Algorithms for Efficient by Parallel Processing", IEEE Transactions on Computers - November 1984, Vol.C-33, No.11.
Publicado
07/11/1990
Como Citar
PORTO, Stella C. da S.; MENASCÉ, Daniel A..
Algoritmos de Escalonamento em Multiprocessadores com Arquitetura Heterogênea. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 3. , 1990, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1990
.
p. 97-112.
DOI: https://doi.org/10.5753/sbac-pad.1990.23111.
