PARALLEL ALGORITHM DEVELOPMENT FOR A SPECIFIC MACHINE INMOS T800 TRANSPUTER BY WILLIAM STAUB 1 WHAT IS A TRANSPUTER 2 WHY SELECT A TRANSPUTER Figure 1 Transputer block diagram and examples of interconnection networks Figure 1 shows the basic block diagram of a transputer along with some interconnection schemes a linear chain a offering the simplest of connections a ring b and a mesh c Figure2 T800 Transputer block diagram THE PROCESSOR RISC STACK BASED OPERATION MULTITASKING TASK ACTIVE OR INACTIVE IF WAITING FOR COMMUNICATION BLOCKED TASK TIMERS MEMORY HIERARCHY ON CHIP 4KBYTES OFF CHIP UP TO 1 GBYTES ON CHIP 3X FASTER SERIAL I O PORTS LINKS SYNCHRONIZATION UNBUFFERED COMMUNICATION DATA TRANSFER RATES 10 Mbits sec one dir TRANSPARENT PORTS I O PORTS ARE MEMORY MAPPED Figure 3 The transputer as an attached processor One of the transputers in the network is a designated driver ROOT ROOT DESIGNATES LINK0 TO COMMUNICATE WITH PC HOST OPERATES AS AN ATTACHED PROCESSOR FOR PC ONLY SOFTWARE WRITTEN WITH THE LOGICAL SYSTEMS C COMPILER ALLOWS US TO UTILIZE THE ATTACHED MULTIPROCCESSORS OTHER NODES ARE IDENTICAL TO ROOT NODE EXCEPT DON T HAVE 8 BIT I O PORT ONLY NEED 5VOLTS GROUND The Compilation Process FIGURE 4 THE PROCESS OF RUNNING A TRANSPUTER PROGRAM WRITTEN IN LS C 3 4 Loading The Program Loading the transputer program on the transputer network and launching it requires ld net to perform several tasks It must load the program into the root transputer Once the parallel program is loaded the loader must give the signal to the root transputer to start execution It must start the execution of a program on the PC host computer so that input and output requests by the root transputer can be carried out Network information file buffer size host server level timeout decode timeout 1 first R0 0 200 cio exe 1000 1000 Listing 3 5 contents of nif file first nif for program first c Figure 5 The transputer chain Notation and convention The network topology The PC host will be referred to as the parent of the root node In turn the root node is the parent of the Rule 1 next node down the chain Rule We will assume that the parent node is always on the left of its child node if any The leftmost entity is 2 therefore the PC host The next to leftmost is the root node A child node will therefore be on the right of its parent Each transputer will communicate with its parent via its Link0 and with its child if any through its Rule 3 Link1 The Root Transputer will be given the numeral 1 its child node will be labeled 2 and so on prime v1 c DESCRIPTION Computes primes on 2 nodes Node 2 computes the primes and sends them to Node 1 Node 1 Root collects the numbers and prints them TO COMPILE AND RUN make f prime v1 chainnif 2 1 prime v1 nif prime v1 nif ASSOCIATED NIF FILE buffer size host server level timeout decode timeout 200 CIO EXE 400 2000 1 prime v1 R0 0 2 2 prime v1 R1 1 include stdio h include stdlib h include conc h transputer library GLOBALS define INTSIZE int sizeof int define INTERVAL 100 define SENTINEL 1 MAIN main int NoPrimes 0 x j NODE 1 Receive information and prints it if node number 1 while numbers are coming get them and print them do get input channel address ChanIn LINK1IN x INTSIZE if x SENTINEL printf 8d x NoPrimes while x SENTINEL printf nReceived d primes n NoPrimes exit 0 else NODE 2 scan interval for x 1 x INTERVAL x if prime then send number to Node 1 if IsPrime x ChanOut LINK0OUT x INTSIZE signal Node 1 that we are done x SENTINEL ChanOut LINK0OUT x INTSIZE ISPRIME Semi efficient prime finding function which given x returns 1 if it is prime and 0 otherwise int IsPrime int x int i 0 1 2 3 4 5 6 7 8 9 static int SmallPrimes 10 0 0 1 1 0 1 0 1 0 0 if x 10 return SmallPrimes x if x 2 0 return 0 if x 3 0 return 0 if x 5 0 return 0 for i 2 i i x i if x i 0 return 0 return 1 The output of the program is shown below 2 3 5 7 23 29 31 37 59 61 67 71 97 Received 25 primes 11 41 73 13 43 79 17 47 83 19 53 89 Figure 4 1 Timing of a ChanOut operation occurring before its matching ChanIn
View Full Document
Unlocking...