Y-Invalidate: A New Protocol for Implementing Weak Consistency in DSM Systems

Ben-Asher, Yosi; Podvolny, Dimitry
December 2001
International Journal of Parallel Programming;Dec2001, Vol. 29 Issue 6, p583
Academic Journal
In this work we propose and implement a new variant of the well-known write invalidate protocol called “Y-invalidate.” Whereas the former protocol required that every copy of a page be invalidated every time that page is updated, our variant invalidates a copy of a page at process A only at the next synchronization point which is relevant to Aand or if the copy was modified by the owner's process after the page was copied to A. We thus avoid invalidating copies of pages that were modified but never read after modification, and avoid, of course, the associated overhead. Y-Invalidate is basically a weak-consistency protocol. Its main advantage is that it implements weak consistency without the need to “merge” copies of a page that were updated in different machines. To the best of our knowledge, this is the first variant of weak consistency protocols which does not “merge” multiple copies of pages. Unlike other variants of weak consistency, Y-invalidate supports implicit synchronization points in the program by invalidating copies of shared memory pages that are referenced by while-loops. In this way, Y-invalidate approximates strict consistency. The Y-invalidate protocol was implemented in the ParC system, which is a powerful parallel extension of the C language. The ParC compiler was modified to detect some of the implicit synchronization points in the source code. Experimental results show significant improvement compared to both the traditional write-invalidate protocol and weak consistency.


Related Articles

  • Distcc.  // Network Dictionary;2007, p155 

    A definition of the term "Distcc" in computer software is presented. The term refers to a computer program that distributes processes of compiling C and its derivatives like C++ and Objective C source code over a computer network. With the right configuration, the program has the capability to...

  • Source Code Analysis of Flight Software using a SonarQube based Code Quality Platform. Martignano, Maurizio; Jung, Andraes; Lehmann, Tobias; Schmidt, Christian // Ada User Journal;Jun2015, Vol. 36 Issue 2, p99 

    Since 2012, Spazio IT and Inopus have been working on a code quality platform for the analysis of both Ada and C/C++ flight software. For Ada (e.g. AIRBUS Helicopters NH90 and Tiger flight software), the emphasis has been on maintenance and particularly on the adoption of ISO/IEC 25010:2011...

  • Realization of UML Class and State Machine Models in the C# Code Generation and Execution Framework. Dereziñska, Anna; Pilitowski, Romuald // Informatica (03505596);Nov2009, Vol. 33 Issue 4, p431 

    Many benefits are expected due to usage of code generation tools. A reliable application should be created effectively based on complex structural and behavioral models. Model driven approach for program development is realized in Framework for eXecutable UML (FXU). The tool transforms UML...

  • Rgtsp: a generalized top scoring pairs package for class prediction. Popovici, Vlad; Budinská, Eva; Delorenzi, Mauro // Bioinformatics;Jun2011, Vol. 27 Issue 12, p1729 

    Summary: A top scoring pair (TSP) classifier consists of a pair of variables whose relative ordering can be used for accurately predicting the class label of a sample. This classification rule has the advantage of being easily interpretable and more robust against technical variations in data,...

  • Contract.- Checking, Wrappers for C++ Classes. Edwards, Stephen H.; Sitaram, Murali; Weide, Bruce W.; Hollingsworth, Joseph // IEEE Transactions on Software Engineering;Nov2004, Vol. 30 Issue 11, p794 

    Two kinds of interface contract violations can occur in component-based software: A client component can fail to satisfy a requirement of a component it is using, or a component implementation can fail to fulfill its obligations to the client. The traditional approach to detecting and reporting...

  • Recovering Traceability Links between Code and Documentation. Antoniol, Giuliano; Canfora, Gerardo; Casazza, Gerardo; de Lucia, Andrea; Merlo, Ettore // IEEE Transactions on Software Engineering;Oct2002, Vol. 28 Issue 10, p970 

    Software system documentation is almost always expressed informally in natural language and free text. Examples include requirement specifications, design documents, manual pages, system development journals, error logs, and related maintenance reports. We propose a method based on information...

  • Lack of modern tools prevents chip sales. Saul, George // Electronics Weekly;5/25/2005, Issue 2195, p16 

    This article asserts that the promise of objects, encapsulation, single and multiple inheritance, polymorphism, class libraries, data hiding and code reusability, has produced a broad range of sophisticated "visual" tools for the software application developer. While software application...

  • Dynamic Verification of C++ Generic Algorithms. Changqing Wang; Musser, David R. // IEEE Transactions on Software Engineering;May97, Vol. 23 Issue 5, p314 

    Dynamic verification is a new approach to formal verification, applicable to generic algorithms such as those found in the Standard Template Library (STL, part of the Draft ANSI/ISO C++ Standard Library). Using behavioral abstraction and symbolic execution techniques, verifications are carried...

  • A C++ Data Model Supporting Reachability Analysis and Dead Code Detection. Chen, Yih-Farn; Gansner, Emden R.; Koutsofios, Eleftherios // IEEE Transactions on Software Engineering;Sep98, Vol. 24 Issue 9, p682 

    A software repository provides a central information source for understanding and reengineering code in a software project. Complex reverse engineering tools can be built by analyzing information stored in the repository without reparsing the original source code. The most critical design aspect...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics