Parix Implementation

Parix is a the native operating system for the Parsytec GC transputer systems. It provides UNIX functionality at the frontend with library extensions for the needs of the parallel system. Parix is available for the massively parallel transputer based GCel series, the medium-sized PowerXplorer (with PowerPC 601), and the new high-performance GC/PowerPlus series with two PowerPC 601 and four transputers per node.

On the GCel-1024, the processing elements are organized in a 2D-grid. A virtual topologies library provides a set of commonly used topologies for application programs, that are optimally mapped onto the underlying hardware. We used the ring and torus topologies for our implementation.

  
Figure 1: Process model on Parix (ring topology)

Figure 1 depicts the process model of our AIDA* implementation on Parix, with five threads running on a single node. In Parix, all threads created by a program are executed in the same context. They share the same global variables defined by the program. The worker and receiver threads in Figure 1 access the common frontier node array for retrieving new work packets. The communication threads (sender and receiver) serve incoming messages and send work requests when asked by the worker. On a torus topology, nine threads are used instead of the shown five.

Performance results [4][3] obtained on a 1024-node system indicate that our scheme works well for problems taking more than, say, a minute parallel computing time. Only few communication is necessary at the end of an iteration when some of the processors get idle. On a -node torus, we achieved an average efficiency of 93 % for some random instances of the -puzzle [4]. For the smaller -puzzle we achieved 79% efficiency on Korf's [1] 25 largest random problem instances [4]. The detailed analysis [4][3] exhibits that the Parix implementation scales well on large MIMD systems and has only low communication overheads.