The Elephant and the Mouse: Non-Strict Fine-Grain Synchronization for Many-Core Architectures

A new synchronization mechanism created under the dataflow model of computation was introduced during the late 1970s and called I-Structure. I-Structure exhibited the following important features: (1) it is a dataflow style synchronization, i.e., synchronization only occurs between an I-Structure producer and consumer operations that are accessing the same memory location; (2) it is fine-grain i.e., it synchronizes at a finer memory granularity than only at the whole data structure level (for instance, it would synchronize at each individual array element instead of barrier synchronization which synchronizes at the data structure level.); (3) it is a lenient (non-strict) synchronization- i.e., an I-Structure load can be issued (non-blocking) even before the corresponding I-Structure store is issued/completed. This paper reports a study of I-Structures in the context of modern many-core chip architectures. The major points examined include: • The creation of an I-Structure style design that exploits a lenient synchronization model using a modern many-core architecture- the IBM Cyclops-64 architecture. • The implementation and integration of our design in the DEEP emulation system that can simulate the entire Cyclops-64 chip at gate level. This allows us to assess the feasibility of its hardware design and implementation. • The demonstration of the advantages of I-Structure style synchronization- especially its lenient synchronization feature on the Cyclops-64 architecture through an experi-mental case study using wavefront computation. A quantitative comparison to tradi-tional control-flow based synchronization, such as signal-wait, is reported.