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.