International Journal of High Speed Computing

This paper describes research conducted at ONERA using the Transputer as building block for experimentation in the field of scientific multiprocessing. The first part describes our experimental systems based on T800–20 Transputers and gives performance measurements of some kernel operations. The second part is devoted to the implementation of two simulation codes on a network of forty Transputers. The first concerns a finite element dynamic analysis of a large scale structural problem. The aim is to compute the dynamic response of a clamped cylindrical beam subjected to a time dependent force. The second code simulates the behaviour of particles in an accelerator. This chromaticity correction code, called PATRICIA [17], has been adapted to our multi-Transputer system. All these experiments were conducted using OCCAM2, the parallel programming language of the Transputer.

Circuit simulation is a highly compute-intensive task as it involves solving thousands of ordinary differential equations (ODEs) describing the VLSI circuit under consideration. This paper describes an effort towards speeding up this task using a hypercube-based architecture. The paper focusses on the design and development of HIRECS (Hypercube Implementation of RElaxation-Based Circuit Simulation). HIRECS is based on the relaxation approach of solving the ODEs describing the circuit. The natural decomposition of the problem makes the relaxation algorithms amenable to parallel implementation. HIRECS employs the Waveform Relaxation (WR) algorithm. The special feature of WR algorithm is that the latency of the circuit can be exploited better, effecting a saving in the total computation time. The concept of ’windowing’ has been incorporated in HIRECS to effect a saving in the memory requirement. Another important feature of HIRECS is a novel synchronization scheme called partial synchronization. HIRECS runs on a DEC-1090 system and is developed using SIMULA. Performance studies of HIRECS based on parameters such as speedup, efficiency, and utilization of processors have been carried out. The performance evaluation of HIRECS in the simulation of some bench mark circuits like inverter chains and multiplexers indicates that a significant speedup, almost linear, can be obtained using a hypercube. For circuits with large number of nodes, such an implementation can result in tremendous saving in the computation time.

This paper presents the results of an experiment to study the performance of multitasking techniques on the CRAY Y-MP using a single algorithm. The algorithm is a compact difference scheme for the solution of the incompressible, two-dimensional, time-dependent Navier-Stokes equations. Three implementations of multitasking on the CRAY Y-MP are considered. These are: macrotasking (parallelism at the subroutine level), microtasking (parallelism at the do-loop level), and autotasking (automatic multitasking). The three techniques are briefly described. The implementation of the algorithm is discussed in relation to these techniques and the results for four problem sizes are presented. The timing results for the three techniques using few processors are in general comparable. For the eight processor case, this algorithm achieved a speedup of seven and a processing rate of over one GFLOPS using macrotasking. The results are also compared to earlier results on the CRAY-2.

The class of hypercubes is one of the most important and popular topologies for interconnection networks of multicomputer systems. This class includes the binary hypercube and generalized hypercube. Based on the observation that these two graphs can be constructed using a graph theoretic operation known as the product of graphs, we propose a new method for generating large symmetric graphs for networks of multicomputer systems. This method is essentially algebraic in nature, and makes use of the product of a class of graphs known as quasi-group graphs. We call the graphs we obtain PQG graphs. Because these graphs are constructed by an algebraic operation, it simplifies the analysis of their performance. Many of the well-known topologies can in fact be expressed as PQG graphs; this makes the method a very general one. We also investigate the problem of routing in a PQG graph, and propose a hardware implementation of the routing algorithm to reduce the delay in the routing of messages. We then apply our results to the Petersen graph and show that the product of such graphs has vastly superior topological properties than hypercubes of the same degree.

A systolic array processing technique is applied to implementing the stack algorithm form of the sequential decoding algorithm. It is shown that sorting, a key function in the stack algorithm, can be efficiently realized by a special type of systolic arrays known as systolic priority queues. Compared to the stack-bucket algorithm, this approach is shown to have the advantages that the decoding always moves along the optimal path, that it has a fast and constant decoding speed and that its simple and regular hardware architecture is suitable for VLSI implementation. Three types of systolic priority queues are discussed: random access scheme, shift register scheme and ripple register scheme. The property of the entries stored in the systolic priority queue is also investigated. The results are applicable to many other basic sorting type problems.

This paper evaluates the performance of hypercube machines on a computational fluid dynamics problem. Our evaluation focuses on a prototype of a class of widely used fluid dynamics codes, FLO52, written by Antony Jameson, which solves the two-dimensional steady Euler equations describing flow around an airfoil. In this paper, we give a description of FLO52, its hypercube mapping, and the code modifications to increase machine utilization. Results from two hypercube computers (a 16 node iPSC/2, and a 512 node NCUBE/ten) are presented and compared. In addition, we develop a mathematical model of the execution time as a function of several machine and algorithm parameters. This model accurately predicts the actual run times obtained. Predictions about future hypercubes are made using this timing model.

The FORTRAN code for the three-dimensional Ising model is optimized on the Floating Point Computing M64/60 computer system and a good cost-effectiveness (dollar/MFLIP) rate is achieved.