ing the parallel code is assigned a unique thread ID, designated $. The spawn statement takes as arguments the lowest ID and highest ID of the threads to be spawned. For the hardware implementation (discussed later), XMTC threads can be as short as eight to 10 machine instructions that are not difficult to get from PRAM algorithms. Programmers from high school to graduate school are pleasantly surprised by the flexibility of translating PRAM algorithms to XMTC multi-threaded programs. The ability to code the whole merging algorithm using a single spawn-join pair is one such surprise (see the sidebar “ Merging with a Single Spawn-Join”).

To demonstrate simple code, con-
sider two code examples:
The first is a small XMTC program
for the parallel exchange algorithm
discussed in the “Parallel Algorithms”
sidebar:

 

spawn ( 0 , n− 1){
A( ):=B( ) ;
B( ):=x
}

 

The program spawns a concurrent thread for each of the depth- 3 serial-exchange iterations using a local variable x. Note that the join command is implied by the right parenthesis at the end of the program.

The second assumes an array of n integers A. The programmer wishes to “compact” the array by copying all non-zero values to another array, B, in an arbitrary order. The XMTC code is:

 

psBaseReg x=0;
spawn ( 0 , n− 1){
int e ;
e= 1;
i f (A[ ] ) !=0) {
ps ( e , x ) ;
B[ e ]=A[ ]
}
}

It declares a variable x as the base
value to be used in a prefix-sum com-
mand (ps in XMTC), initializing it to 0.
It then spawns a thread for each of the
n elements in A. A local thread variable
e is initialized to 1. If the element of
the thread is non-zero, the thread per-
forms a prefix-sum to get a unique in-
dex into B where it can place its value.