Um Framework para Definição e Análise de Modelos de Consistência de Memória

• Hammurabi C. Mendes UnB
• Diego F. Aranha UnB
• Alba C. M. A. Melo UnB
• Mário A. R. Dantas UnB

DOI: https://doi.org/10.5753/wscad.2002.20760

Resumo

A Memória Distribuída Compartilhada (DSM) foi proposta para permitir que o paradigma de programação por memória compartilhada seja utilizado em arquiteturas distribuídas. O comportamento dos sistemas DSM é determinado pelo modelo de consistência da memória. De modo a prover melhor compreensão sobre a semântica dos modelos de consistência da memória, vários pesquisadores propuseram formalismos para defini-los. Mesmo com definições formais, ainda é dificil dizer que tipos de históricos de execução podem ser produzidos em um determinado modelo de consistência. Neste artigo, é proposto um framework que serve como base para a implementação da análise de históricos de execução em diversos modelos de consistência, provendo os algoritmos e estruturas de dados convenientes para tal. O nosso framework é organizado em módulos e permite que o usuário defina novos modelos de consistência de uma maneira simples. Um protótipo foi implementado em C, incluindo também os programas que lidam com históricos em PipelinedRAM e Release Consistency. Quando comparados com suas implementações originais, o uso do framework permitiu uma redução de em torno de 70% no tamanho do código para os dois modelos.

Referências

S. V. Adve, "Designing Multiple Memory Consistency Models for Shared-Memory Multiprocessors". PhD dissertation, University of Wisconsin-Madison, 1993.

E. Best, "Semantics of Sequential and Parallel Programs", Prentice Hall Int. Series in Computer Science, 1996, 352p.

K. Gharachorloo, D. Lenoski, J. Laudon, P. Gibbons, A. Gupta, J. Hennessy, "Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors", Proc. Int. Symp. On Computer Architecture, May, 1990, p. l5-24.

A. Heddaya and H. Sinha, "An Implementation of Mermera: a Shared Memory System that Mixes Coherence with Non-Coherence", Tech Report BU-CS-93-006, Boston University, 1993.

Iftode, L., Singh, J. P., and Li, K. "Scope Consistency: A Bridge between Release Consistency and Entry Consistency". Proc 8th ACM Annual Symp. on Parallel Algorithms and Architectures (SPAA'96). pages 277-287, June 1996.

A. Melo, "Defining Uniform and Hybrid Memory Consistency Models on a Unified Framework", Proceedings of the 32nd Hawaiian International Conference on System Sciences, Vol. VIII, Software Technology, Maui, 1999.

R. Netzer, B. Miller, "On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions", Technical Report TR-908, University of Wisconsin Madison, (1990).

Yaakov L. Varol, Doron Rotem: An Algorithm to Generate all Topological Sorting Arrangements. The Computer Journal 24(I): 83-84, 1981.

D. Mosberger, "Memory Consistency Models", Operating Systems Reviews, January, 1993.

Lamport L., How to Make a Multiprocessor Computer that Correctly Executes Multiprocess Programs, IEEE Transactions on Computers, 1979, 690-691.

R. Lipton, J. Sandberg, "PRAM: A Scalable Shared Memory, Technical Report 180-88, Princeton University, 1988.

W. Hu., W. Shi., Z. Tang.: JIAJIA: An SVM System Based on A New Cache Coherence Protocol. In Proc. of HPCN'99, LNCS 1593, pp. 463-472, Springer-Verlag, April, 1999.

E. Speight, J. Bennet, "Brazos: a Third Generation DSM System", Proc. Of the USENIX/WindowsNT Workshop, p.95-106, August, 1997.

A. Melo, N. Silva, "Visualizing Execution Histories on Release Consistency and Scope Consistency Memory Models", Proc. Of the 2nd Int. Workshop on Software Distributed Shared Memory, Santa Fe, USA, May, 2000.