Isotach
PapersIsotach
PapersPaul F. Reynolds, Jr., Craig Williams, R.R. Wagner, Jr.
Abstract.
We introduce a class of networks called isotach networks designed to reduce the cost of synchronization in parallel computations. Isotach networks maintain an invariant that allows each process to control the logical times at which its messages are received and consequently executed. This control allows processes to pipeline operations without sacrificing sequential consistency and to send isochrons, groups of operations that appear to be received and executed as an indivisible unit. Isochrons allow processes to execute atomic actions without locks. Other uses of isotach networks include ensuring causal message delivery and consistency among replicated data. Isotach networks are characterized by this invariant, not by their topology. They can be implemented in a wide variety of configurations, including NUMA (nonuniform memory access) multiprocessors. Empirical and analytic studies of isotach synchronization techniques show that they outperform conventional techniques, in some cases by an order of magnitude or more. Results presented here assume fault-free systems; we are exploring extension to selected failure models.PostScript
Bronis R. de Supinski
Advisor: Paul F. Reynolds, Jr.
May 1988
Abstract.
We apply techniques based on isotach logical time to the problem of maintaining a coherent shared memory. In isotach logical time systems, processes can predict and control the logical times at which their messages are received. This control over the logical receive time of messages provides a powerful basis for implementing coherence protocols. Existing isotach-based memory coherence protocols are more concurrent than other protocols, but are limited in the topologies on which they work and the reference patterns for which they are suited. We define a new framework for isotach shared memory systems that supports protocols that work for arbitrary topologies and are suited to a wide range of reference patterns. By extending isotach protocols to a wider class of applications and networks, we contribute to the solution of the memory coherence problem.In addition to extending isotach-based coherence protocols, we advance the theory of isotach systems. We redefine isotach systems to be consistent with potential causality, a new relation among events that captures causality in a less conservative way than Lamport's happens before relation. This redefinition expands the class of correct implementations of isotach systems. We introduce the flex algorithm, a new implementation of isotach logical time that allows different links to be assigned different logical distances. We expect that increased flexibility in assigning logical distances will improve the performance of isotach systems in cases in which links have significantly different real time latencies.
Lance Hopenwasser
Abstract.
We have developed a simulator of Isotach systems which run on a Myrinet network. The simulator allows us to study the performance characteristics of the system and provides a means for experimenting with alternative implementations of Isotach networks. The rate at which tokens flow through the network determines the rate at which Isotach logical time progresses; therefore, token behavior is of keen interest. The simulator gathers performance data that is used to examine the behavior of tokens within the network under several different conditions. The simulator is also capable of obtaining similar data on barriers that make use of the Isotach network. These barriers are of interest, because they can be used to establish network-wide checkpoints in addition to other application-level uses. The simulator can provide data on characteristics of the network that most affect barrier completion time. Furthermore, the simulator can be used to compare the Isotach barrier algorithm to a simple centralized non-Isotach barrier algorithm. We present some of the issues that influenced the design of the simulator.
Anand Natrajan
Abstract.
Timestamp-based authentication protocols rely on real-time synchronisation between the principals involved. This synchronisation, which involves all concerned principals agreeing on the notion of their time, is often difficult to achieve, and hence nonce-based protocols were developed. However, the principals in a timestamp-based authentication protocol can be made to synchronise to logical time. Efficient logical time systems can guarantee that processors (or principals in this case) agree on a logical time. Using this property, new protocols can be developed for various communication paradigms. We show one such protocol for interactive communication between two parties using a trusted authentication server.
John Regehr
Abstract.
An isotach network provides strong guarantees about message delivery order. We show that an isotach network can be efficiently implemented entirely in software, on off-the-shelf hardware. Parts of this implementation could be performed much more efficiently in hardware - we are currently developing hardware components to do this. The all-software version then serves several purposes: to rapidly develop a working isotach system to use as a platform for development of higher level software, to find potential problems in the hardware design, and to pre-test software components of the system so that they won't have to be debugged at the same time as the hardware.
Bronis de Supinski, Craig Williams, Paul F. Reynolds, Jr.
Abstract.
This paper presents the results of a simulation study designed to evaluate the performance of the late delta cache coherence protocol and a conventional directory based invalidation protocol. Delta cache protocols are a highly concurrent directory based family of coherence protocols which exploit an isotach logical time system to provide support for sequential consistency and atomicity. The late delta protocol is an update based member of this family of protocols. Our results demonstrate the efficacy of the late delta protocol across a wide range of workloads. We show that this protocol provides comparable performance to the conventional invalidation protocol under workloads with no atomicity requirements and little contention, but outperforms the conventional invalidation protocol as atomicity requirements and contention increase.
Craig Williams, Paul F. Reynolds, Jr.
February 1995, pp. 152-163
Abstract.
A combining network can combine concurrently issued operations on the same variable and fan out responses to the processes that issued the operations. Combining networks have been proposed with the goals of reducing message traffic, hotspots within the network, and contention for shared variables. This paper extends the class of operations that can be combined to include operations from flat atomic actions. We describe a class of networks called isotach networks and show that isotach networks can correctly combine operations from different flat atomic actions. Also we show that isotach combining networks can combine pipelined operations without sacrificing sequential consistency.
Raymond R. Wagner, Jr.
Advisor, Paul F. Reynolds, Jr.
Abstract.
Local synchrony is a distributed approach to providing logically synchronous capabilities in an asynchronous system. Local synchrony provides a logical timeline to memory access, and thus a total ordering to the steps of a distributed computation, without many of the inherent consequences of global synchronization. Local synchrony offers a framework for the implementation of various concurrency control mechanisms, including combining and isochrons (parallel operations). We show the implementability of local synchrony, and demonstrate its compatibility with existing protocols for fault-tolerance in general purpose multiprocessors. The results of our research are threefold. We show first that practical implementation of local synchrony is feasible in general, asynchronous, MIMD architectures. We show that such implementations are compatible with existing hardware fault tolerance systems and present a correct rollback algorithm for our general implementation. Finally, we present both analytic and empirical studies which illustrate the performance characteristics of such implementations. Our analytic modeling technique extends in novel ways probabilistic modelling methods often employed for interconnection networks. Our work establishes the practicality and feasibility of local synchrony as a means of providing support for concurrency control.
Craig Williams
Advisor: Paul F. Reynolds, Jr.
January 1993
Abstract.
When independently executing processes share data, some form of concurrency control is needed to enforce the atomicity and sequencing constraints imposed by the program. We believe that concurrency control is hard largely because existing architectural support is inadequate. We define a new class of interconnection networks called isotach networks and explore isotach-based concurrency control by describing techniques that use the isotach network to achieve causal message delivery, atomicity, sequential consistency, and cache coherence. We show processes can pipeline their accesses to shared data in an isotach system without sacrificing sequential consistency. We define the isochron, a multicast with strong ordering properties implemented on an isotach network, and describe techniques by which processes can use isochrons to execute atomic actions without obtaining locks or other exclusive access rights. We describe compatible techniques for enforcing data dependences and show that the isotach network is capable of combining concurrently issued operations on the same shared variable while maintaining atomicity and sequential consistency. We describe a family of new cache coherence protocols called delta-cache protocols that extend isotach-based concurrency control techniques to systems that replicate and migrate shared variables, yielding protocols that are both scalable and more highly concurrent than existing protocols. We report results of a simulation study comparing the performance of isotach and conventional systems. The study shows that isotach systems outperform conventional systems under workloads with atomicity and sequencing constraints.[Main Page][About][Papers][People][Projects]