Primitivas para Programação Paralela no MULTIPLUS
Resumo
Este artigo apresenta uma definição do modelo básico de programação paralela que será provido pelo sistema operacional MULPLIX, para a família de computadores paralelos de alto desempenho MULTIPLUS. O modelo representa simultaneamente uma extensão ao conceito de processo suportado pelos sistemas operacionais com filosofia UNIX — considerado um modelo bem sucedido de computação seqüencial — e uma versão mais realista do modelo PRAM, atualmente o principal modelo para estudo de algoritmos paralelos em memória compartilhada. O texto explica os mecanismos definidos para execução paralela, alocação de memória e sincronização. A utilização destes mecanismos é exemplificada através de um programa paralelo para a resolução de sistemas lineares pelo método de Eliminação Gaussiana.
Referências
A. Aggarwal, A. K. Chandra, M. Snir; "Communication Complexity of PRAMs"; IBM Research Report RC 14998, fevereiro de 1989.
A. V. Aho, J. E. Hopcroft, J. D. Ullman; "The Design and Analysis of Computer Algorithms"; Addison-Wesley, Reading, Mass., 1974.
A. V. Aho, R. Sethi, J. D. Ullman; "Compilers, Principles, Techniques, and Tools"; Addison-Wesley, Reading, Mass., 1986.
B. Alpern, L. Carter, E. Feig; "Uniform Memory Hierarchies"; IBM Research Report RC 16069, agosto de 1990.
T. E. Anderson; "The Performance of Spin Lock Alternatives for Shared Memory Multiprocessors"; IEEE Trans. on Parallel and Distributed Systems, January 1990, Vol 1, Number 1, pp. 6-16.
J. S. Aude; "Uma Proposta de Implementagao do Algoritmo de Lee no Multiprocessador MULTIPLUS"; pp. 555-568.
J. S. Aude et al; "MULTIPLUS: A Modular High-Performance Multiprocessor"; Proceedings of the Euromicro 91, Microprocessing and Microprogramining Vol. 32 (1991).
G. P. de Azevedo, R. P. de Azevedo, N. R. Figueira, J. S. Aude; "MULPLIX: Um Sistema Operacional tipo UNIX para o Multiprocessador MULTIPLUS"; Relatério Técnico RT 91-1, NCE/UFRJ, janeiro de 1991. Este texto é uma versão revista e ampliada do trabalho homônimo apresentado no III SBAC-PP em novembro de 1990.
M. Bach; "The Design of the UNIX Operating System"; New Jersey, Prentice-Hall, 1986.
J. L. Boldrini, S. I. Costa, V. L. Ribeiro, H. G. Wetaler; "Álgebra Linear"; Harper & Row do Brasil, São Paulo, 1980.
P. Brinch Hansen; "Concurrent Programming Concepts"; ACM Computing Surveys, Vol. 5, No. 4, dezembro de 1973; pp. 223-245.
G. Bronstein, A. J. O. Cruz, O. C. M. B. Duarte; "Análise de Desempenho de Redes de Interconexão para Máquinas Paralelas"; Anais do II SBAC-PP, Rio de Janeiro, novembro de 1990, pp. 345-360.
D. R. Cheriton, H. A. Goosen, P. D. Boyle; "ParaDiGM: A Highly Scalable Shared-Memory Multicomputer Architecture"; IEEE Computer, Vol. 24, No. 2, fevereiro de 1991; pp. 33-46.
R. Cole, O. Zajicek; "The APRAM: Incorporating Asynchrony into the PRAM Model"; Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, junho de 1989, pp. 169-178.
T. H. Cormen, C. E. Leiserson, R. L. Rivest; "Introduction to Algorithms"; MIT Press. Cambridge, Massachusetts, 1990.
N. Faller et al; "O Projeto Pegasus-32X/Plurix"; Anais do XVII Congresso Nacional de Informatica, 1984.
N. Faller, P. Salenbauch; "PLURIX, O Sistema Operacional Multiprocessador do NCE-UFRJ: (1) Sincronização de Processos"; Data News, 24 de setembro de 1985.
S. Fortune, J. Wyllie; "Parallelism in Random Access Machines"; Proceedings of the 10th ACM Symposium on Theory of Computing, 1978, pp.114-118.
A. Gibbons, W. Rytter; "Efficient Parallel Algorithms"; Cambridge University Press, 1988.
P. B. Gibbons; "A More Practical PRAM Model"; Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, junho de 1989, pp. 158-168.
J. R. Goodman, M. K. Vernon, P. J. Woest; "Efficient Synchronization Primitives for Large Scale Cache-Coherent Multiprocessors"; Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 3 Boston, Mass., 3-6 de abril de 1989; pp. 64-75.
R. M. Karp, V. Ramachandran; "A Survey of Parallel Algorithms for Shared Memory Machines"; In Handbook of Theoretical Computer Science, ed. J. van Leeuwen, North Holland, Amsterdam, 1989.
T. J. LeBlanc, J. M. Mellor-Crummey, N. M. Gafter; "The Elmwood Multiprocessor Operating System"; Software - Practice & Experience V.19, No.110, novembro de 1989, pp. 1029-1055.
T.J. LeBlanc, M. L. Scott, C. M. Brown; "Large Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor"; Proceedings of the ACM SIGPLAN PPEALS 1988 - Parallel Programming: Experience with Applications, Languages and Systems, julho de 1988, pp. 161-172.
U. Manber; "Introduction to Algorithms: A Creative Approach"; Addison-Wesley, 1989.
E. P. Markatos, T. J. LeBlanc; "Shared-Memory Multiprocessor Trends and the Implications for Parallel Program Performance"; Relatório Técnico 420, Computer Science Departament, The University of Rochester, maio de 1992.
A. M. Meslim, A. Pacheco; "Sistema de Memória Multicache para uma Máquina Paralela MIMD - Projeto MULTIPLUS"; Anais do III SBAC-PP, Rio de Janeiro, novembro de 1990, pp. 179-193.
S. C. Oliveira, J. S. Aude; "O Sistema de Memória de Massa do Multiprocessador MULTIPLUS", Anais do III SBAC-PP, Rio de Janeiro, novembro 1990, pp. 298-313.
D. A. Patterson, J. L. Hennessy; "Computer Architecture: A Quantitative Approach"; Morgan Kaufmann Publishers, Palo Alto, California, 1990.
R. Rashid, A. Tevanian Jr., M. Young, D. Golub, R. Baron, D. Black, W. Bolosky, J. Chew; "Machine Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures"; IEEE Transactions on Computers, Vol. 37, No. 8, agosto de 1988; pp. 896-908.
H. S. Stone; "High-Performance Computer Architecture"; Addison-Wesley, Reading, Massachusetts, 1987.
H.-M. Su, P.-C. Yew; "On Data Synchronization for Multiprocessors"; ACM Computer Architecture News, Vol. 17, No. 3, junho de 1989; pp. 416-423.
Sun Microsystems Inc.; "The SPARC Architecture Manual"; outubro de 1987.
L. G. Valiant; "Bulk-Synchronous Parallel Computers"; Technical Report 'TR-08-89, Harvard University, Cambridge Mass., 1989.
L. G. Valiant; "General Purpose Parallel Architectures"; In Handbook of Theoretical Computer Science, ed. J. van Leeuwen, North Holland, Amsterdam, 1989.
A. V. Aho, J. E. Hopcroft, J. D. Ullman; "The Design and Analysis of Computer Algorithms"; Addison-Wesley, Reading, Mass., 1974.
A. V. Aho, R. Sethi, J. D. Ullman; "Compilers, Principles, Techniques, and Tools"; Addison-Wesley, Reading, Mass., 1986.
B. Alpern, L. Carter, E. Feig; "Uniform Memory Hierarchies"; IBM Research Report RC 16069, agosto de 1990.
T. E. Anderson; "The Performance of Spin Lock Alternatives for Shared Memory Multiprocessors"; IEEE Trans. on Parallel and Distributed Systems, January 1990, Vol 1, Number 1, pp. 6-16.
J. S. Aude; "Uma Proposta de Implementagao do Algoritmo de Lee no Multiprocessador MULTIPLUS"; pp. 555-568.
J. S. Aude et al; "MULTIPLUS: A Modular High-Performance Multiprocessor"; Proceedings of the Euromicro 91, Microprocessing and Microprogramining Vol. 32 (1991).
G. P. de Azevedo, R. P. de Azevedo, N. R. Figueira, J. S. Aude; "MULPLIX: Um Sistema Operacional tipo UNIX para o Multiprocessador MULTIPLUS"; Relatério Técnico RT 91-1, NCE/UFRJ, janeiro de 1991. Este texto é uma versão revista e ampliada do trabalho homônimo apresentado no III SBAC-PP em novembro de 1990.
M. Bach; "The Design of the UNIX Operating System"; New Jersey, Prentice-Hall, 1986.
J. L. Boldrini, S. I. Costa, V. L. Ribeiro, H. G. Wetaler; "Álgebra Linear"; Harper & Row do Brasil, São Paulo, 1980.
P. Brinch Hansen; "Concurrent Programming Concepts"; ACM Computing Surveys, Vol. 5, No. 4, dezembro de 1973; pp. 223-245.
G. Bronstein, A. J. O. Cruz, O. C. M. B. Duarte; "Análise de Desempenho de Redes de Interconexão para Máquinas Paralelas"; Anais do II SBAC-PP, Rio de Janeiro, novembro de 1990, pp. 345-360.
D. R. Cheriton, H. A. Goosen, P. D. Boyle; "ParaDiGM: A Highly Scalable Shared-Memory Multicomputer Architecture"; IEEE Computer, Vol. 24, No. 2, fevereiro de 1991; pp. 33-46.
R. Cole, O. Zajicek; "The APRAM: Incorporating Asynchrony into the PRAM Model"; Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, junho de 1989, pp. 169-178.
T. H. Cormen, C. E. Leiserson, R. L. Rivest; "Introduction to Algorithms"; MIT Press. Cambridge, Massachusetts, 1990.
N. Faller et al; "O Projeto Pegasus-32X/Plurix"; Anais do XVII Congresso Nacional de Informatica, 1984.
N. Faller, P. Salenbauch; "PLURIX, O Sistema Operacional Multiprocessador do NCE-UFRJ: (1) Sincronização de Processos"; Data News, 24 de setembro de 1985.
S. Fortune, J. Wyllie; "Parallelism in Random Access Machines"; Proceedings of the 10th ACM Symposium on Theory of Computing, 1978, pp.114-118.
A. Gibbons, W. Rytter; "Efficient Parallel Algorithms"; Cambridge University Press, 1988.
P. B. Gibbons; "A More Practical PRAM Model"; Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, Santa Fe, NM, junho de 1989, pp. 158-168.
J. R. Goodman, M. K. Vernon, P. J. Woest; "Efficient Synchronization Primitives for Large Scale Cache-Coherent Multiprocessors"; Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 3 Boston, Mass., 3-6 de abril de 1989; pp. 64-75.
R. M. Karp, V. Ramachandran; "A Survey of Parallel Algorithms for Shared Memory Machines"; In Handbook of Theoretical Computer Science, ed. J. van Leeuwen, North Holland, Amsterdam, 1989.
T. J. LeBlanc, J. M. Mellor-Crummey, N. M. Gafter; "The Elmwood Multiprocessor Operating System"; Software - Practice & Experience V.19, No.110, novembro de 1989, pp. 1029-1055.
T.J. LeBlanc, M. L. Scott, C. M. Brown; "Large Scale Parallel Programming: Experience with the BBN Butterfly Parallel Processor"; Proceedings of the ACM SIGPLAN PPEALS 1988 - Parallel Programming: Experience with Applications, Languages and Systems, julho de 1988, pp. 161-172.
U. Manber; "Introduction to Algorithms: A Creative Approach"; Addison-Wesley, 1989.
E. P. Markatos, T. J. LeBlanc; "Shared-Memory Multiprocessor Trends and the Implications for Parallel Program Performance"; Relatório Técnico 420, Computer Science Departament, The University of Rochester, maio de 1992.
A. M. Meslim, A. Pacheco; "Sistema de Memória Multicache para uma Máquina Paralela MIMD - Projeto MULTIPLUS"; Anais do III SBAC-PP, Rio de Janeiro, novembro de 1990, pp. 179-193.
S. C. Oliveira, J. S. Aude; "O Sistema de Memória de Massa do Multiprocessador MULTIPLUS", Anais do III SBAC-PP, Rio de Janeiro, novembro 1990, pp. 298-313.
D. A. Patterson, J. L. Hennessy; "Computer Architecture: A Quantitative Approach"; Morgan Kaufmann Publishers, Palo Alto, California, 1990.
R. Rashid, A. Tevanian Jr., M. Young, D. Golub, R. Baron, D. Black, W. Bolosky, J. Chew; "Machine Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures"; IEEE Transactions on Computers, Vol. 37, No. 8, agosto de 1988; pp. 896-908.
H. S. Stone; "High-Performance Computer Architecture"; Addison-Wesley, Reading, Massachusetts, 1987.
H.-M. Su, P.-C. Yew; "On Data Synchronization for Multiprocessors"; ACM Computer Architecture News, Vol. 17, No. 3, junho de 1989; pp. 416-423.
Sun Microsystems Inc.; "The SPARC Architecture Manual"; outubro de 1987.
L. G. Valiant; "Bulk-Synchronous Parallel Computers"; Technical Report 'TR-08-89, Harvard University, Cambridge Mass., 1989.
L. G. Valiant; "General Purpose Parallel Architectures"; In Handbook of Theoretical Computer Science, ed. J. van Leeuwen, North Holland, Amsterdam, 1989.
Publicado
07/09/1993
Como Citar
AZEVEDO, Rafael Peixoto de; AZEVEDO, Gustavo Peixoto de; SILVEIRA, Júlio Tadeu Carvalho da; AUDE, Júlio Salek.
Primitivas para Programação Paralela no MULTIPLUS. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 761-775.
DOI: https://doi.org/10.5753/sbac-pad.1993.23074.
