Systolic loop

Smith has also described the implementation of MD on parallel machines, with particular reference to hypercube computers. In work designed to introduce a novice to the main aspects of parallel computing in MD, Smith described three particular algorithms replicated data (RD), systolic loop (SLS-G), and parallelized link cells (PLC), all of which have good load balancing. The performance characteristics of each algorithm and the factors affecting... 

Two categories of force decomposition algorithm have appeared in the literature those that systolically cycle atom data around a ring, and those based on the force-matrix formalism discussed by Plimpton.i o A variety of systolic loop methods have been implemented on both and... 

A Transputer-based systolic loop implementation for the simulation of rigid polyatomic molecules described by Craven and Pawley revealed that in contrast to many problems on MIMD computers, the main loss of efficiency arose not from the time spent in communication between processors but, rather, from certain extra calculation and addressing work that was deemed inevitable in the parallel decomposition of the problem, and from a slight load imbalance. This study provided an excellent practical example of the ability of the Transputer to communicate and calculate in parallel, with minimal degradation of the computation rate, and provided very encouraging timing comparisons with the Cray X-MP. 

Windemuth and Schulten described a further variant of the systolic loop algorithm, the replicated systolic loop for the efficient calculation of macromolecular force fields on the Connection Machine (e.g., CM-1, CM-2, CM-5). The full force field was separated into bond interactions and nonbonding interactions only the latter were implemented on the Connection Machine, and parallelized by the replicated systolic loop algorithm. The former, less computationally intensive tasks were performed by an existing, conventional MD code on the front end. 

Systolic Loop A message-passing mechanism where groups of processors pass data simultaneously with point-to-point communications. A basic systolic loop would pass part of the data structure around a ring executing tasks based on the particular data. 

A. R. C. Raine, D. Fincham, and W. Smith, Comput. Phys. Commun., 55, 13 (1989). Systolic Loop Methods for Molecular Dynamics Simulation Using Multiple Transputers. 

Which one of these variations one should use is mostly a question of the balance between communication and calculation of the parallel computer being used. In any case as the systems grow larger the RD method will be limited by the all-to-all global communication steps. However, there is an improvement of the RD method which avoids global all-to-all communication [102]. Also it is possible to combine the ideas of RD with systolic loop algorithms. The main reason to do this would be to decrease the need for node memory and it also opens up the possibility for overlapping communication and calculation [46,103-105]. 

A. Raine, Systolic Loop Methods for Molecular Dynamics Simulation, Generalised for Macromolecules, Mol. Simul., 7 (1991), 59-69. 

Data movement in systolic loop algorithm for aU-to-aU broadcast involving four processes, P0-P3. Using p processes, the algorithm requires p - 1 steps. Initially, process Pi owns data Di, and upon completion, the full data set Do, Di, D2, D3 has been copied to every process. 

Example 6.6 Using a Systolic Loop Communication Pattern... 

A systolic loop communication pattern using p processes, Po - Pp-i. Execution requires p steps, and in each step every process first performs computations on its local data and then exchanges data with its neighbors. The activity on process P in one step is shown first, computation is performed on the locally residing block of data, a, and a is then sent to the downstream neighbor while a new block, is received from the upstream neighbor. 

Outline of systolic loop communication scheme using point-to-point message-passing (cf. Figure 6.8). The number of processes and the process ID are designated p and this proc, respectively. Non-blocking receive operations are employed to prevent deadlock. 

---