Analyzing Execution Orderings on Hybrid Memory Consistency Models
Resumo
The behavior of Distributed Shared Memory Systems is dictated by the memory consistency model. To provide a better understanding on the semantics of the various consistency models, researchers have proposed formalisms to define them. Even with formal definitions, it is still difficult to say what kind of execution histories can be produced on a particular memory model. In this paper, we propose a visualization tool that generates the operations orderings that could have led to user-defined execution histories on different memory models. We also describe a prototype of our tool that analyses execution histories for two memory consistency models: Release Consistency and Scope Consistency. Some preliminary results are also presented.
Palavras-chave:
Memory Consistency Models, Distributed Shared Memory
Referências
ADVE, Sarita et al. Detecting Data Races on Weak Memory Systems, Proceedings of the 18th International Symposium on Computer Architecture (ISCA91), 1991, p.234–243.
ADVE, Sarita. Designing Multiple Memory Consistency Models for Shared-Memory Multiprocessors. University of Wisconsin–Madison, 1993 (PhD Thesis).
AGRAWAL, Divyakant et al. Evaluating Weak Memories with Maya, Proc. of the 8th Workshop on Parallel and Distributed Simulation (1994) 151–155.
BEST, Eike. Semantics of Sequential and Parallel Programs, Prentice Hall Int. Series in Computer Science, 1996, 352p.
CHILIMBI, Trishul M.; BALL, Thomas; EICK, Stephen G.; LARUS, James R. StormWatch: a Tool for Visualizing Memory System Protocols, Proc. of the ACM Int. Conf. on Supercomputing'95, 1995.
GHARACHORLOO, Kourosh et al. Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors, Proceedings of the International Symposium on Computer Architecture (ISCA90), May, 1990, p.15–24.
GOODMAN, James. Cache Consistency and Sequential Consistency, Technical Report 61, IEEE Scalable Coherent Interface Working Group, March, 1989.
HEDDAYA Abdelsalam; SINHA Himanshu. An Implementation of Mermera: a Shared Memory System that Mixes Coherence with Non-coherence, Tech Report BU-CS-93-006, Boston University, 1993.
IFTODE, Liviu; SINGH, Jaswinder P.; LI, Kai. Scope Consistency: A Bridge between Release Consistency and Entry Consistency, Proceedings of the 8th ACM Annual Symposium on Parallel Algorithms and Architectures (SPAA96), June 1996, p.277–287.
MELO, Alba C. Defining Uniform and Hybrid Memory Consistency Models on a Unified Framework, Proc. of the 32nd Hawaii International Conference on System Sciences, January, 1999.
MELO, Alba C.; CHAGAS Simone C. Visual-MCM: Visualising Execution Histories on Multiple Memory Consistency Models, in Lecture Notes in Computer Science 1557, February 1999, p.500–509.
MOSBERGER, David. Memory Consistency Models, Operating Systems Review, p.18–26, 1993.
NETZER, Robert; MILLER, Barton P. On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions, Technical Report TR-908, University of Wisconsin–Madison, 1990.
PARK, Seungjoon; DILL, David L. An Executable Specification and Verifier for Relaxed Memory Order, IEEE Transactions on Computers, v.48, n.2, February 1999, p.227–235.
PREUSS, Gara; RUSKEY, Frank. Generating Linear Extensions Fast, SIAM Journal on Computing, Vol.23, No.2, p.373–386, April 1994.
ADVE, Sarita. Designing Multiple Memory Consistency Models for Shared-Memory Multiprocessors. University of Wisconsin–Madison, 1993 (PhD Thesis).
AGRAWAL, Divyakant et al. Evaluating Weak Memories with Maya, Proc. of the 8th Workshop on Parallel and Distributed Simulation (1994) 151–155.
BEST, Eike. Semantics of Sequential and Parallel Programs, Prentice Hall Int. Series in Computer Science, 1996, 352p.
CHILIMBI, Trishul M.; BALL, Thomas; EICK, Stephen G.; LARUS, James R. StormWatch: a Tool for Visualizing Memory System Protocols, Proc. of the ACM Int. Conf. on Supercomputing'95, 1995.
GHARACHORLOO, Kourosh et al. Memory Consistency and Event Ordering in Scalable Shared-Memory Multiprocessors, Proceedings of the International Symposium on Computer Architecture (ISCA90), May, 1990, p.15–24.
GOODMAN, James. Cache Consistency and Sequential Consistency, Technical Report 61, IEEE Scalable Coherent Interface Working Group, March, 1989.
HEDDAYA Abdelsalam; SINHA Himanshu. An Implementation of Mermera: a Shared Memory System that Mixes Coherence with Non-coherence, Tech Report BU-CS-93-006, Boston University, 1993.
IFTODE, Liviu; SINGH, Jaswinder P.; LI, Kai. Scope Consistency: A Bridge between Release Consistency and Entry Consistency, Proceedings of the 8th ACM Annual Symposium on Parallel Algorithms and Architectures (SPAA96), June 1996, p.277–287.
MELO, Alba C. Defining Uniform and Hybrid Memory Consistency Models on a Unified Framework, Proc. of the 32nd Hawaii International Conference on System Sciences, January, 1999.
MELO, Alba C.; CHAGAS Simone C. Visual-MCM: Visualising Execution Histories on Multiple Memory Consistency Models, in Lecture Notes in Computer Science 1557, February 1999, p.500–509.
MOSBERGER, David. Memory Consistency Models, Operating Systems Review, p.18–26, 1993.
NETZER, Robert; MILLER, Barton P. On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions, Technical Report TR-908, University of Wisconsin–Madison, 1990.
PARK, Seungjoon; DILL, David L. An Executable Specification and Verifier for Relaxed Memory Order, IEEE Transactions on Computers, v.48, n.2, February 1999, p.227–235.
PREUSS, Gara; RUSKEY, Frank. Generating Linear Extensions Fast, SIAM Journal on Computing, Vol.23, No.2, p.373–386, April 1994.
Publicado
24/10/2000
Como Citar
MELO, Alba Cristina; SILVA, Nilo Sergio Barros.
Analyzing Execution Orderings on Hybrid Memory Consistency Models. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 12. , 2000, São Pedro/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2000
.
p. 201-208.
DOI: https://doi.org/10.5753/sbac-pad.2000.41221.
