WILLIAM STAUBFigure2 T800 Transputer block diagramTHE PROCESSOR:FIGURE 4 : THE PROCESS OF RUNNING A TRANSPUTER PROGRAM WRITTEN IN LS C 3-4Loading The ProgramThe network topologyRule 1Rule 2Rule 3PARALLEL ALGORITHM DEVELOPMENT FOR ASPECIFIC MACHINE (INMOS T800 TRANSPUTER)BY WILLIAM STAUB1. 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)- TIMERSMEMORY 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 dirTRANSPARENT 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 ProgramLoading 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 200; host_server cio.exe; level_timeout 1000; decode_timeout 1000;1, first, R0, 0, , ,;Listing 3-5: contents of nif file first.nif for program first.c.Figure 5 : The transputer chain. Notation and convention. The network topologyRule 1The PC host will be referred to as the parent of the root node. In turn, the root node is the parent of the next node down the chain. Rule 2We will assume that the parent node is always on the left of its child node (if any). The leftmost entity is therefore the PC host. The next to leftmost is the root node. A child node will therefore be on the right of its parent. Rule 3Each transputer will communicate with its parent via its Link0, and with its child (if any) through its 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 200; host_server CIO.EXE; level_timeout 400; decode_timeout 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 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97Received 25 primesFigure 4.1: Timing of a ChanOut operation occurring before its matching