RECONFIGURABLE MULTI-MICROPROCESSOR SYSTEMS 
INFORMATICA1/88 
UDK 681.519.7 
Peter Kolbezen 
Institut »Jožef Štefan« 
A communi cation mechaniam based on the exchange o-f the distri-
buted topologv in-formation is di3cua«ed. A particular recon-figur— 
ation tBchnlque is treated to handle the exchange o-f topology 
in-formation and thus to maintain tho neco«Bary routing tablea. 
ThiB mechanism handlee thfe recon-f iguratl on dynamically. Inmos 
Tranaputer concepts aro introduced and applicated on tho .two-
dimensional epuare interconhection otructure. 
"Rakon-f Igurabilni" veeprocaa.orBki siatami. Prispevek obravnava 
komunikacijski mehanizem, ki je zasnovan na spremembah topologije 
komunikacijskih poti med mikroprocesorskimi enotami sistema. 
Namenjen je posebni t.im. "rekon-f igurabi Ini " tehniki, ki obravna­
va spremembo in-formacije o topologiji in na ta naCin vzdrHuje 
potrebne razpredelnice povezav medprocesorskih komunikacij, V 
predlogu so vpeljani koncepti Intnosovega transputerja, kot voz-
littCnega procesorja v povezovalni dvodimenzionalni kvadratni 
strukturi. 
1. INTRODUCTION 
Hlghly parallel computing structures promlce to 
ba a major application area -for the milion-
tranaistor chips that Mili be poesible in Just 
a -feN yeBrs, Such computing systems hava atruc-
tural properties that are suitable -for VLSI 
implaroentatlon. The kBy attributea o-f VLSI 
computing atructures are 
- almplicity and regularity 
- concurrrency and communication 
- computation intenaiva VLSI. 
The choice o-f an appropriate architecture -for 
any alectronlc «yBtem ia very clQsely related 
to the implemantatipn technology. Thia is es-
pecially true in VLSI. The «uporvi»ory overhaad 
incurrad in general-purpooe supercomputers 
o-ften fflakes them too SIOM and eKpensive -for 
reel.-time and signal and Image procasBing. 
Progreas in VLSI technology has lawered imple-
mentation costs -for large array processors to 
an acceptable level. Algorithmically special-
ized procesBora o-ften use di-f-ferent intercon-
hection atructures. The matching o-f the struc-
ture to the right algorithm has a -fundamental 
in-fluance on per-formance and coat o-f-fectiva-
nBEE. 
An alternative to the design o-f a globally 
•ynchronoua array i a to achiava a sal-f-timed 
ByBtem through the use o-f aaynchronous handsha-
king mschanisma eBtabllshad betMean neighboring 
procesBing elemants, These sel-f-timed -implemen-
tatians ara commonly ro-ferred to as wavafront 
«rrays /8,12,21,23,25/. Th 
combines the Eystolic pipeli 
the data-floM computing con 
array processor may be used 
tached processor inter-facing 
host machine or as a stai 
eguipped Mith a global contr 
system conaists o-f the p 
interconnection nBtwork(s), 
inter-face unit. 
e wavB-front array 
ning principi« with 
cept. A wave-front 
either as an at-
Mith a compatible 
nd-alone processor 
ol processor. Such 
rocBSBor array(s), 
a host Computer and 
EKploitation o-f the data-floM principle makes 
the oHtractiona o-f parallelism and programming 
•for wave-front arrays relatlvely simpler. 
A -fa 
figur 
to s 
struc 
overh 
based 
be U9 
toler 
cone 
cauee 
thBy 
mlly dynamica 
able VLSI pro 
upport a larg 
tures usually 
ead. f^econ-flg 
on swltching 
ful for »olv 
ance. Fault 
rn in ByBtol 
o-f the large 
may hava. 
lly Interconn 
cesBor arrayB 
e- cl ans o-f a 
involve sign 
urabl.lity o-f 
lattices has 
ing problema 
tolerance i 
le and yia.vefr 
number o-f pr 
eted or 
allow an 
Igorithma 
iflcant h 
rray str 
been pro 
related t 
3 an i mi 
ont arra 
oeessor e 
recon-
array 
Such 
ardMare 
uctures 
ven to 
o fault 
portant 
ys be-
iements 
The paper concludes Mith euggestion« as to hOM 
a reeofIgurable sistem may be designed Mith 
constructing a Mave-front array Mith the -family 
o-f Inmo« Tranaputers /20/. Transputer chip ia 
an Occam-language-based design that providea 
hardware aupport -for both concurrent computa-
tion and communieation. It adopts the now-
popular RISC architačtura. Its -featurea make it 
* poMerful bullding block for constructing 
cofKurrent procesaing netMorks. Tha trans­
puter 's linkfi »re the hardware repreaantation 

18 
of the channela -far proiresB comraunicatian. 
There is an intimate relationship between 
transputer channel links and the Communications 
protocol envisaged -for wavefront arrays. 
2. ADAPTIVE SVSTEMS 
The' treatmented reconfigurations technique in 
first part oi the -first work on this topic is 
diseussed in connections with uniform and dense 
netvsiorks. It is based on Baran's hot-potato 
routine /2/. A correctness proof o-f a similer 
algorithm hn.2 also been presented by Tajibnapis 
One o-f the major objectives o-f the adaptive 
systems is to be rearrange the canfigurations 
to match the needs of dif-ferent appl i cat ions. A 
such -fleKible Recon-fIgurable Multi-micropro-
caasor SyBt»mB (RMmS) should include provisions 
-for insertions (extensions) and deletions (re-
duct i ons). 
In general, a node in a system becomes aware o-f 
the entire con-f i gurat i on either by a central 
network control (CNC) or as result of diatribu--
ted ej<change of the conf i gurat ion (topology) 
information. The CNC approach can be utilizod 
to implement a fixed routing mechanism. The 
necessary routig tables, Mhich are computed 
using the system topology information, sire 
distributed to the part icipating nodes, once 
and for ali. For a RMmSystems which does not 
have an CNC, it is necessary to compute-routing 
tables externally and to provide each node with 
a ccipy of the full conf i gurat i on information. 
Given the network topology, the shartest dis-
tance algorithems, such as DijkGtra's algo­
rithm, can be used to compute ali the shortest 
paths between the local node and the rest of 
the system /5,6/. 
The provision of a distributed reconfigurati on 
mechanism eliminates the need for a central 
network control and a copy of the full con-
figuration information at each node, Instead, 
each node is responsible for maintaining par--
tial routing information so as to be ablo to 
communicate to its neighbouring nodes. 
The handling of configurational changes /5,7, 
12/ in mul t i-Computer/processor systema is či 
necessary part of their design. It is required 
for realiabi1 ity, modularlty, and CKtensibl-
lity. It is the dynamical reconfigurati on which 
is important. The routing mechanisms, such as 
- random 
- flooding 
- ideal obnerver, and 
- adaptive 
can 
f rst 
and 
the 
need 
is 
resp 
logy 
rout 
whic 
in t 
respond 
two tec 
node. A 
full sy 
s a cen 
assumed 
onsible 
changes 
ing , is 
h can al 
erms of 
dynamical1 
hniguss can 
node is not 
stem topolog 
tral network 
to watch the 
for incorpor 
. The last t 
basi cal1y a 
šo respond t 
some delay f 
y to the changes. The 
utilize any live link 
necessarily aiiare of 
y. The third tBchnique 
control which ideally 
sntire system and is 
ating traffic and topo-
chnique, i,e. adaptive 
flow control mechanism 
o the topologv changes 
uncti on. 
INITIALIZATION 
The j discussed reconfigurati on algorithm is 
basically an adaptive algorithm. It is intend-
ed , !howevc'r, to be ' control 1 ed by the configura-
tiorial changes rather than traffic changes. It 
wi11 initialize the system by setting the ini-
tial •configuration and then adapt the syatem, 
din4mically, to further passible changes in 
topologv. The changes occur either as a result 
of ifailures or unexpected occupation (link, 
node link, and node) or as a result of new 
links, nodes, or links and nodes joining the 
3ystem. The topologv message format is as 
shawns as: 
lihaadcr Idaetination laourca !distanc»lcrc I 
II II l_ 1 
Gi v 
an 
tec 
EK C 
nod 
sta 
new 
top 
nod 
SCd 
ed 
i s 
i s 
e,n a networ 
ji ni t i al i ^a 
ts the ad 
ha n g e s t h i 
e's. The inf 
n,dard forma 
neighbour 
ologv infor 
e', in the 
essible nod 
jto be bi~d 
l'ive so is 
n'ot always 
k of N nodes, it 
tion phase where 
jacent operable 
i nformati on 
ormation is pass 
t units (topolog 
receives the ful 
mation availatile 
form of one topo 
e. Nate that the 
irectional, i.e. 
the link (b,a>. 
the čase. 
first undergoes 
by each node de­
li nka and thua 
lith neighbouring 
ed in the form of 
V messages). The 
I accaunt of the 
at the detecting 
logv meeaage per 
links are aesum-
if a link (a,b) 
In practice thia 
The topologv message contains tiMO fields rele-
vant tO reconfiguration: Identification of 
destination node i and the shortest distance 
betweGn the sending node s and node i. A node 
generates, and may madify, a shortest distance 
table as shown in f-ig. 1. 
I )3esti-
I nation n~l 
I Distance D(O) d(l) d(2) ... d(k) ... d(n-n 
I i 
Fig. 1 Shortest distance table at node k 
The entries srs inde^ed by the node identifica-
tionjand the entries themselvea &ra the short­
est distance betneen the corresponing destina­
tion 'node and the local node. 
In this 
on the 
i nforma 
gurat io 
SKchang 
mai ntai 
logv mo 
cati on 
mechani 
cally. 
res or-
changes 
node, 
made kn 
a f i n i t 
pap 
a>: 
ti on 
t 
o 
n th 
ssag 
of 
srn 
The 
une 
I i 
or n 
own 
e ti 
er, a commun 
change of th 
is discusse 
echnique ie 
f topologv i 
e necessarv 
o is sent on 
a change in 
handles the 
link, node, 
Kpected occu 
e. new or 
w or freo 1 
to every liv 
me. 
icati on 
e di 6t 
d. A pa 
propose< 
nformat 
routing 
ly if t 
the con 
reconf i 
or link 
pati on 
f ree '. i 
ink and 
e node 
mech 
ribut 
rtiču 
d to 
ion a 
tabl 
here 
figur 
gurat 
and 
and 
n k , n 
node 
in th 
ani sm 
ed t 
lar r 
hand 
nd t 
es. A 
i s an 
ation 
ion 
node 
the 
ew a 
čase 
ays 
based 
opology 
econf i -
i e t hi e 
hus to 
topo-
i n d i -
This 
dynami-"-
fai1u-
reverse 
r free 
Are 
tem in 
HANDLINB INBERTION OF A NEM NODE 
Now, j suppose that node 1 of Fig. 2 detocts a 
new neighbour, say node 17 in the same figure, 
and -the rest of the system is uniform with the 
configuration known and node 17 has no tiss 
with!any other node in the Bystem, except node 
1. This ie a major change in the network. The 
topologv message ei<change propagatas until the 
configurational change has been detected at 
everv node in the syatem. recoiving node 

19 
needs to send tppology messages to its neighbo-
uring nodea only if tha tQpology message recei-
ved has changed the previous topolDgy Informa­
tion, i.e. the shorteat distanca table. 
This procese can best be visualired by a top-
dQwn tree, as shown in Fig. 3. 
17" 
f— 
... 
+ --
f _ 
•f-
1 
+•-
+ -
_. 
1; 
h 
5-
?-
5-
— 
+-
1 
• ! 
1 
1 
2-
6 
--to-
1 
— 14-
-
... 
— 
---3- • 
1 
— ••7 
— 15 
+ .._ 
1 
! 
1-
- -4-
-—B-
-12-
1 
1 
--16-
distance and the routing tables alter every 
tirne a topolpgy change on a shorter path at— 
rives. Every change is then -fanned through the 
syBtem. 
e ROOT. node 1 , t 
ission. The syst 
17, is e>!pected 
. For node 17, h 
reguired to reče 
orraation -froni th 
of nodes in the 
cause the ROOT n 
vector to node 
ted in the -form 
In practice, a new lirik does not always belong 
to a -first-time node joining the 3ystem. The 
node tnight alread/ have been taking part in the 
systein. On the other hand, more than one link 
can become 1 i ve at the same tirne. This occurs 
if one or more nodes join the sy3tem ali at 
once, with ali the adjacent links coming up 
si multaneously. 
5. HANDLING FAILED LINKS 
Star 
leve 
e!<ce 
f i ve 
ma i n 
lete 
n 1 
wor k 
the 
path 
C h a n 
t ing 
Is o 
ption 
mai n 
pen. 
topo 
s the 
Th 
shor t 
i š 
from th 
f transm 
of node 
peri oda 
ods are 
logy inf 
nuraber 
is is be 
est path 
transmi t 
ge message. 
here 
em. 
to 
are 
wi th 
settl 
owever, 
i ve the 
e ROOT, 
on g 
eeds 
17. 
of- a 
inal 
to 
where 
five 
the 
e in 
(n-1) 
comp-
Mhere 
net-
eend 
each 
tDpology 
• H +-
+ ^ 
Fig. 2 Node insertion 
The tree is extracted from the netnork shown in 
Fig. 2. The messages on tho topological changoa 
originated at node 1 stop at the terminal nodes 
when the configurati on Information, i.e. the 
shortest distance tabele, has reached settle-
ment. Note that the branches represent the 
communication links and the vertices represent 
the nodes as numbered in Fig. 3. 
A node is crossed if it haa already been, tra-
versed once by an equivalent topolDgy message. 
Two topol ogy messages s.re considered equivalent 
if the destination fild, the distance field, 
and the sending node are the same. For this 
example a node is traversed at least once for 
the configurational change to be transparent -ta 
the tiystem since node 17 has no tiea wi th the 
rest of the network. However, the r-iode may have 
to be traversed more than once in cases where 
the network is loaded with other traffic which 
may cause delays on certoiin paths. The topalogy 
messages that then take longer paths can reach 
a node before those taking sorter patha. The 
Link fiiilures or occupationes handled differ — 
ently. Obviau3ly a failed or occupated link 
cannot take part in a transmission. Upon detec-
tion of a such link out of m+1 links, the pre-
pared-topology message anly naeds to ba broad-
čast over the remaining m links. From then on, 
the procedure for handling a topology message 
is the same ae for the 1 i ve link datoction 
casB. Now, for clarity suppose that the 
failure/occupation of a particular link dis-
connects the adjacent node from the rest of the 
system, which is tha reverse of the node inser­
tion čase discuBsed in the previous example. 
The fai1ure/occupati on of the link (1,17) caus-
es the system in Fig. 2 to settle in five main 
periods. This is because the sy3tem reguires 
five levels of transmission (see Fig. 3). 
TRANSPUTER NODES 
The transputer /13,15,20/ is a comporati vely 
new hardware concept. The transputer producta 
sra aimed at highly parallel concurrent comput-
ing applications. The range of these products 
from Inmos offer system designers high band-
17 
I • Root 
13 
4 7 15 
6 14 3 B 16 6 8 9 9 14 16 
rr~i r~ r" I rr"i ;~~i i r~r"i 
5 7 io 10 13 15 5 7 12 12 13 15 10 12 13 
6 8 ir 14 14 16 9 11 14 9 11 13 
10 13 15 
Fig. 3 Topol Dgy messčige c?;ichange tree. 

20 
width interprocessor Communications without a 
shared iriemory bus. It is a programmable VLSI 
device with Communications links for point-to-
point connection to other transputers. The 
software concept upon which transputer inter-
process communication is based waa originally 
propounded by C.A.R. Hoare /3/. AH transputer 
range products share same basic common logical 
properties. These aroi 
- the ability o-f the processor chip to aopport 
e:<ternal memory, but wi th the recommendati on 
that processors should not share memory; 
- the provision of high bandwidth aerial links 
•for interprocessor communi cati on ; 
- hardware support -for on--chip simulated concu-
rrency, and -for mul ti-processor parallel com-
puting; 
~ low level so-ftware development in a high 1 e-
vel structured notation. 
A link between two transputers provides a pair 
o-f "occam" channels, one in oach direction. A 
link between two transputers implemented by 
connecting a link interface on one transputer 
to a link inter-face on the other transputer by 
two one-directional signal lines. Each signal 
line carri.es data and control Information. 
Eac 
si n 
pr 
ing 
los 
sen 
The 
was 
tha 
ano 
sen 
the 
cei 
h message 
gle bytB c 
sence o-f a 
transputer 
t. A-fter 
der waits u 
acknowled 
able to r 
t the rec 
ther byte. 
ding proces 
-f inal by 
ved. 
i s tr 
ommun 
singl 
to e 
trans 
ntil 
ge si 
ecei v 
ei vi n 
The a 
s oni 
te of 
ansm 
i cat 
e by 
nsur 
mi tt 
an a 
gni -f 
e th 
g li 
endi 
y af 
the 
itted 
ion, r 
te bu-f 
e that 
ing a 
cknowl 
i es bo 
B ackn 
n k is 
ng lin 
ter th 
messa 
as a sequen 
equiring oni 
fer in the r 
na in-(-Drmat 
data byte 
edge i s rec 
th that a p 
owledge byte 
able to r 
k -reschedule 
e acknowledg 
ge has bee 
ce o-f 
y thii' 
ecei V-
i on is 
the 
ei ved. 
rocBss 
and 
ecei ve 
the 
e -f or 
n re-
Data bytes and acknowledges are multiplexed 
down each signal line. An acknowledge is trana-
mitted as soon as reception o-f a data byte 
starts ( -f there is room to bu-f fer another 
one). Consequently transmission may be continu-
ous, wi th no delays betvvesn data bytes. 
Transpute 
the poss 
part o-f t 
reside a 
wh i C h p r 
part i cul a 
transpute 
contradi c 
o-f the ne 
the tran 
present 
cross-bar 
support. 
because 
on 1 y a f 
o-f links 
r al 
ibil 
he n 
nd a 
ocee 
t 
r ar 
ts t 
twor 
sput 
by. 
sw 
The 
the 
i ni t 
f rom 
so supp 
i ty of 
etwork 
degree 
sor sh 
asks, 
chi tect 
h e i d e a 
k. But 
er net 
Inmos e 
i ch wi t 
reconfi 
hardwar 
e (and 
each n 
ort.program 
late decisioi 
particular s 
of run tirne 
Duld be use 
There is n 
ure and orga 
of dynamic 
dynamic reco 
work is not 
xcept that t 
h some 1ow 
guration is 
e for transp 
normaly very 
ode. 
modu 
ns a 
of tw 
C h 
d f 
othi 
niza 
reco 
nf i g 
su 
hBy 
1 ewe 
need 
uter 
srna 
1 ari 
bout 
are 
oi se 
or 
ng 
t i on 
n f i g 
ur at 
ppor 
pro 
1 
ed 
s 
11) 
ty with 
whi ch 
should 
about 
runni ng 
i f-i the 
whi C h 
urati on 
i on of 
ted at 
vi de a 
of tware 
n part 
upports 
number 
For the configurati on above on the 
use ali four links of every trans 
arr ay node may be used the E-i003 I 
puter board. There is no provision 
the code which on the B003 must be 
transputer link. The problem has b 
so far since it de3troys the syminB 
netHork and makes the program u 
complicated for these esamples. It 
way that the problem may be salve 
node 4 K 4 two-dimansional array on 
An extra transputer, which may be o 
B002 board, is used as the boot nod 
connected vi a a UART to a host ma 
processor is node 17 on the Fig 
Fig. 
pute 
nmos 
for 
d on 
een 
try 
nnec 
is s 
d fo 
the 
n a 
e wh 
chi n 
and 
1 
tr 
boo 
e vi 
avo 
of 
essa 
howB 
r a 
Fig 
BOO 1 
ich 
B. 
it 
hich 
n a 
ana-
ti ng 
a a 
i ded 
the 
r i 1 y 
one 
16 
2. 
or 
can 
This 
may 
be include in the loop of nodes 1,5,9 and 13. 
IMPLEMENTINB THE RECONFIGURATION ALGORITHM 
A network of needs to be reconfigurated if one 
of the following topological changes occurs: 
1. a new link is introduced (or a failed / 
pccupated link is repairod or again free and 
returned to the Eystem); 
2. a new node is joined to the system (or a 
failed node is repaired or again free and 
rei nserted)i 
3. a link fails 
4. a node fai13. 
It 
perm 
netw 
reco 
the 
trib 
temp 
node 
f ann 
bloc 
the; 
uriti 
beca 
use 
comm 
woul 
i n f o 
ure s 
pay5 
and : 
1 s 
ar-ie 
ork 
nf i 
f 1 
ute 
ora 
I 
ed 
kag 
ad 
1 
usie 
up 
uni 
d 
rma 
of 
»it 
i rnpor 
nt n 
in a 
gurat 
ow of 
dl y a 
ry C 
or 1 
throu 
e on 
jacen 
the 
the 
an i 
cat io 
other 
ti on 
howev 
f wit 
ensi b 
tan 
atu 
f i 
i an 
to 
nd 
han 
ink 
gh 
t h 
t n 
f ai 
gl 
mpo 
n 
1 s 
tr 
er , 
h h 
i li 
t that topological change of s 
re is made known to the entire 
nite tirne /5/, This is where the 
mechanism comes in. It controls 
pological Information both dis-
dynamically. On the other hand, 
ges such as short tirne link, 
and node failures need not be 
the system. Instead a temporary 
G failed unit, or rerrouting at 
odes, can be more advantageous 
lure state is removed. This is 
obal reconf i gurat i on mechaiiisma 
rtant fraction of the available 
capacity af the network which 
bo utilized for the actual 
missipn. For permanent fail-
e r-econf i gurat i on mechanism 
er reliability, adaptabi1 ity, 
th 
i gh 
ty. 
In a real life system, permanen 
configurati on changes need to 
befdre taking any action. This 
by employing a rB-try and tirne 
Before declaring a failure as 
detecting node waits for a fin 
tirne during which the failure i 
porary and the necessary precau 
accardingly. This mechanism cai 
for ithe new links or nodes join 
However, a 1 i ve link or a 1 i ve 
mechanism can be incorporated w 
joining, i.e. whether it is a p 
ment or a temporary one. f\'ec 
considered only for the practic 
manent topological changes. 
t and temparary 
be distiguished 
can be handled 
out mechanism. 
permanent the 
ite duration of 
s declared tem-
tiona are taken 
n al so be used 
ing the systeni. 
node detection 
ith the type of 
ermanent attach-
onfiguration is 
al čase of per-
B. DATA BASE OF THE f?ECONFI6URATI0N ALGOf^ITHM 
The 'reconfigurations alghorithm operates basi-
call!y an two tables. The distance table (DT) 
which records the distance (path length) of 
each node in the system from the host node via 
eacK of the neighbouring nodesj the routing 
tablle (RT) which records the sHortest paths 
oni v. For each destination a maKimum of m paths 
can i be identified, where m is the number of 
neiglhbours. The DT is an n by m table, where n 
is network sise. 
Figure 4 shows the DT a node 1 of the 16-nade 
netw:ork given in Fig. 2. In a reQularly 
conn|ected homogenous network ali the distance 
tables are of equal sise. An entry d(k,i,J) is 
the j distance of path (k,i) via the neighbour 
X(j), where i'=l,2,...,n and j = l,2,...,m. The 
nodels that are not accessible from node k have 
a correspoding entry of infinity in the table. 
For ' example, node 1 appears inaccessible from 
itsellf via any of its neighbours. 
I 
The feize of routing table (RT> depends upon the 

21 
Destination Via neighbouring nodes 
2 4 S 13 
1 
infinity in-finity infinity in-finity 
13 3 3 
2 2 4 4 
16 
Fig. 4 Distance table for riode 1 
o-f a 16-node ne?twork 
speci-fic routing mechanism being employd. In 
•fact, RT is arranged using the distance table. 
An entry rii,k) or RT indicates the neighbour 
node, say X<j) , via which the riode i is at a 
minimum distance -from the host node k, i.e. 
d,n(k,i , j) min (d (k , i , j) ) , 
1 < m 
The entries of RT change anly i-f the minimum o-f 
the correaponding DT row changes. It would save 
processing time i-f a shortest distance (SD) 
table were used alongsids the distance table. 
We have 
GD(i ) = d,n(k,i , j) . 
Figure 5 gives the routing table and the 
shortest distance table given in Fig, 4. Note 
that r(l,i) = O and SD < 1) is in-finity which 
means that node 1 cannot send a message to 
itself by means o-f routing tables. For 
applications where the communicati on protocols 
maintain in-formation -f 1 ow between the processE^s 
rather than the processors (nodes) independent 
of where they are residing, we can have GD(k) 
noninfinity, where r(k,k) •-= G. 
The recon 
entri es 
changes. 
concerns 
^i stance, 
need to 
excepti on 
requires 
be sent 
f i gurati on 
whi Ch ar s 
For Gi<amp 
node 1, 
routi ng, 
al g 
r e 1 a 
le, 
on 
and 
be re-ferred t 
is the d 
either the 
to the new 
the distance table 
link to h e updated. 
etec 
sho 
ne i 
corr 
orithm op 
•ted to t 
i f a topo 
ly the 
shortest 
o a f t e r 
tion of t 
rtest dis 
ghbour ar 
espondi ng 
erates on th 
he topolog i 
1ogi cal. cha 
ith level' 
distance tab 
detect i on. 
he change wh 
tance table 
the column 
to the fai 
ose 
cal 
nge 
of 
lea 
fin 
i ch 
to 
of 
led 
9. THE RECONFIGURftTlDN ALGHDRITHM 
The reconfiguration algorithm is structured 
into three basic subalgorithms. Algorithm 1 
handles the link and/or node failures (or 
occupation). A node failure or occupation are 
interpreted as the the simultaneous -failures 
(or occupation) of the links. Algorithms 2 
handles a new link and/or node coming up. A 
node is declared new/free i-f ali the links 
connected to it become al i ve si mulfaneously. 
Algorithm 3 handles the topology messages which 
indicate the configurational changes. These 
algorithms 3.re given in detail down. A 
reconfigurati on protocol is complete only with 
a speč i f^ i C routing mechanism, gueue management 
algorithms, and input-output handling routines 
at the lawer 1 ever o-f communi cat i on. 
Figure 6 «ihowes a system f 1 ow diagram o-f the 
reconf i gurat i on mechanism e;<cluding the f 1 ow 
level communicati on protocol routines. fl more 
detailed description of three algorithm has 
been written by Bo2yigit. Some simulation 
resulta using the reconfiguration algorithms 
are reported by E<02yigit and F'aker /6/, 
L- i n k f a i 1 Li r c-) 
New 1 i 1-1 V\ 
coming up 
V 
Send 
i nformati on 
to new 
ne i ghbour 
Topolagy 
change 
message 
Modify distance and routing tables 
V 
Route topology 
M / Has S Y 
/ shortest path \ 
I \ changed / I 
: ^ ? / I 
V ~ V 
/ \ 
I Terminate I 
\ / 
-ig. 6 Orqani:-:ati on tjf reconf i gur at i on 
al gor i thm 
.Destination 1 
Ne>it node O 
16 
13 
(a) Routing table (RT). 
Ghortest 
distance in-finity 1 
(b) Shortest distance table (SD) 
Fig. filoutirig and shortesit t.--!5les at node 1 
-of a 16-node network 
10. DESCRIBTION DF THE RECONFIGURATION ALGO­
RITHMS 
A. NomenclaturB -for the recon-figuration algo­
rithms 
a --•- sourcE node ' 
n =- destination node 
C ~ node adjacent (neighbour) to node a 
d[-|j == distance between a and b via the jth 
neighbour o-f a (tlie superscript a is 
ofiiitted wtierever it is obvious) 
rtJ, » the first neighbour on shiortest path 
between a and b indicated by a neighbour 
of- a on tl-iat path 

22 
TMt, -- topologv me&sage compiled at a to be 
sent to b 
a a 
C <- TM[-| = send TMtj to c 
a 
V|3 ~ shortest distčince between a and C 
Wc = ith neighbour o-f a 
čl 
Xi = ith neighbour o-f a 
t = (a temporary variable) 
B. Algorithmc li Handlas a n«H link coming 
up at node a 
1. (a new link detected at the local node a) 
Link (a,c) becomss llvei 
Vj : = min Idi I j I , j e m 
rf ! = X^ where vf = df,j, 
TMf : = v], 
(send topology meeeage). 
TMi' : = TMf (where Y = Xj) far 
j = 1,2,...,m, except -for 
od J 
4. Ekit 
(update distance and rauting tables) 
C. Algorithem 3i Handlee arrivBd topologv 
messag« at noda a 
= 1, 
=-- c; 
1. (detect topologv message at local node a) 
j 
TMtj arrives at a; 
(preparate topolc)gy tiiesEiage) 
(set distanca topol.ogy F i al d of topologv 
niessage) 
•Jist (TM^) : -•: 1, 
(set destination ficld of topologv mesviagei 
dest (TM;.) C! 
(send topologv message to neighbouring 
nodes) 
Xj <- Tfl^ ^or j - 1,2,...,m and Xj J* CJ 
(send available topology i n-f ormat i on to nei» 
neighbour) 
(form topologv message) 
= V 
dest (TMT) 
1 • 
i -for- i 1,2,, 
,n. 
(send topologv change mesaages to new 
neighbour-) 
TMV 
Ex i t. 
TMf. 
(update distance and routing tables) 
(assign new distance for (a,b) path) 
d|p,j : = TM§ + w2, 
(find new min distance (a,b) path) 
t^ ! = min ld|3 j I , jem 
(assign the shortest path) 
if ttj not Vjj then 
= Xb where tb = dg^j 
Vg 
(prepare topologv messages) 
dist (TMg) 
dest (TMb) 
(send topologv message to neighbours) 
I Xj <-• TMb for al 1 j e m 
•fi; 
Exit 
B. Algorithm 2i Handles link failures at node a 
1. (a link failure or occupation detected at 
node a) 
link (a,c) failed or occupated; 
2. (update the distance table) 
(save distance vector currespoding to 
fai1ed/occupatsd link) 
ti ' = di,j . 
(set vector dj j to infinity) 
d^ j : = infinity where Xj = c, and 
i = 1,2,3 n; 
j = index of the -failed ar 
occupated link 
3. (update r-outing tables and prepare topologv 
messages) 
E. Algorithm 4i Round-rabin rauting algorithm 
I 
1. (input a message at a) Th^ arrives 
I 
2. (find the shortest path (c,b)) 
i f C = (m-1> then 
! C i = O 
•fi!. 
(ne;<t node) 
i 
a 
C ! = rt,; 
3. (message joins output queue) 
aa^ : = TM^i 
4. Exit. 
for i ; = from 1 to n with step 1 do 
i-f v" = ti then 

23 
11. CONCUUSION 
Algorithmlcally specialized proč 
use di-f-ferent • interconnection a 
reconfigurable wavefront array 
/16,25/. There are a number of 
algorlthma which set up data struc 
flrst phase o-f .processing, then 
instance matrix arlthmetic techni 
česa the data, and in a file phas 
data uaing a di-f-ferent data patha 
e«ample is the hardware -far a ah 
Mith parallel In/eerial out ar 
seri al in and out. The maah is 
namic programming and the hvkaagon 
•d ineah for L-U decompoaition /12 
ia uaed -for transitivo. cloaure. Th 
ia uaed for aorting and the doubl 
ia uaed for aearching. 
esBors often 
tructures of 
proceasors 
tradi tional 
tures in the 
applay for 
ques to pro-
e accesa the 
A trivial 
ift regiater 
parallel and 
uaed for dy-
ally connect-
/. The toura 
e binary trse 
-rootod tree 
Each B003 board from the Inmoa farnily has four 
tranaputera .connected in as ring. There are 
therefore two links per transputer which can be 
connected axterally. In thia manner there are a 
wide variety of networkB that can be configured 
ueing only B003 boardsi 
- In the axample of the shift regiater a ring 
of n tranaputera can be implemented with n/4 
B003 boards. The tranaputera are connected 
oerially as the process "node" together with 
four channela (two input, two output). 
- A two dimenaional array of 64 transputers 
(S X 8) can be implemented with aixtean B003 
boards. Four arrays of n channels (for s. 
etructure n x n B003 boards) are connected 
(left to right, right to left, top to bottom 
and bottam to top) so that each node can send 
or receivB data to or from any of its four 
neighboura. Elght placed channels. for n=4 
(four input, four output) are passed to the 
procass "node". 
A folded bin 
be implement 
boarda are c 
af channels 
ia of *ize 
manneri adj 
diag.right ai 
for adjacen 
"diag" for a 
thia exa(nple 
put, four ou 
"node". 
ary structure 
ed with 16 
onnected Bxte 
of dimension 
2 X 2 ) are 
left, adj.r 
nd so on Mher 
t conection 
diagonal con 
sight plače 
tput) are pas 
of siae 4 x 
B003 boards t 
rnally. Four 
n (where the 
connected in 
ight, diag.l 
e "adJ is a m 
and "diag" 
nection. And 
d channels ( 
sed to the 
16 can 
oo. The 
arrays 
network 
such a 
eft and 
nemoni c 
for a 
alao in 
for in-' 
procesa' 
A cube connected 
implemented with 
configured on a s 
ray3 of cannala 
(where the natwor 
wiBe.rote, anti.c 
te, where "clock 
represent channel 
same row, and "c 
connected to a di 
nacted cycle is t 
a four-dimenciona 
at each "corner", 
input, three out 
"nodea". A mappi 
for thia configur 
has the same lin 
nels. 
cycle of B 
16 B003 b 
ingle B003 
are defin 
k ie of si 
lockvMise. r 
Mise" and 
s connect 
ross" rep 
fferent ro 
opographi c 
1 hipercub 
Six plače 
put) are 
ng functio 
ation sin 
k addreas 
ize 4 
oards.. 
board 
ed of 
ze 2 X 
ote an 
ant 
ed to 
reaent 
w. Th 
al 1 y e 
e wi t 
d chan 
passe 
n is n 
ce eac 
for i 
X 16 C 
Eačh r 
Three 
dimens 
2")i C 
d crosB 
i. clock 
nodes i 
a a ch 
is cube 
qui valei 
h four 
nels ( 
d to p 
ot nece 
h trans 
ts six 
an be 
ow is 
ar-
ion n 
lock-
. rou-
Mi ae" 
n the 
annel 
con--
nt to 
ngdes 
three 
roces 
Bsary 
puter 
chan-
Ideally it would be desirable to allocate each 
procBSB PJEP (where P ia collection of proces-
aes Pj) to exactly one transputer and to allo­
cate each channel Cj^^POV.C (where C is the col­
lection of Channels Cj^^) to one intertransputer 
link between tranaputera t^ and t\^ - given that 
tha matching pair of channela Ci|^ and, cj^j may 
be allocated to the one link Ij^. Ideally if 
there are mul tipie channels 
each should be allocated to 
Howev«r there are practical 
ber of links available to e 
there are posaible electrica 
problema with geographical1y 
large nstMork. It some cases 
forward messages passively t 
puters at nodea in a network 
not enough linka on each dev 
the . direct communicati on 
There are some examples wh 
forwarding is a heavy overh 
deairable to avoid it by dy 
configuration between the d 
the program Bxecution. Then 
the ey3tBm may be improved 
more complex hardware. 
12. REFERENCES 
betMeen , processes: 
different links. 
limita to. the num-
ach transputer and 
1 si-gnal and wiring 
remote links in a 
it is necesarv to 
hrough eome trans-
because there are 
ice.to provide ali 
that. is required. 
ere . auch messages 
ead and it may be 
namic hardware re-
ifferent phases of 
the performance of 
at the eKpense of 
/1/ A correctneaa proof of a.topQlogy Infor­
mation malntenance protocol for diatribu-
ted Computer netwark. M.B.Tajibnapis, 
Comm.ACM, July 1977. 
/2/ On diatributed communication networks. 
P.Baran, IEEE Trans, on Communication 
By3temB, Vol. Comm-12, 1967. 
/3/ Communicating Sequential Processaa. 
C.Hoare, Comma ACM, vol.21, No.8, 
Auguat 197B. 
/4/ Diatributed fault tolerant computer 
syatem. D.A.Renels, IEEE Computer, 
March 1980. 
/5/ Hardwired Resource Allocators for Recon-
figurable Arcitectures. 
B.D.Rathi, A.R.Tripathi and G.J.Lipovski, 
Proc.Infl Conference on Parallel Proces­
sing, IEEE, Auguat 1980. 
/6/ A topology reconfiguration mechanism for 
distributed computer system. 
M.Bazylgit and V.Paker, The Computer 
Journal, 23, No.1, 1982. 
/7/ Introduction to the Configurable, 
,Hlghly Parallel Computer. 
L.Snyder, Computer, January 19B2. 
/B/ "Why Systolic Architectures?. H.T.Kung, 
Computer, Vol.15, No.l, January 1982. 
/9/ On the design of algorithms for VLSI 
sy8tolic arraya. D.I.holdova, Procaedings 
of the IEEE 71, No.l, January 1983. 
/10/ Flexlbile Architectura Microcamputer 
Design. E.Zager and D.Tabak, hicroproces-
sing and Microcomputer Design 11, 1983. 
/11/ Reconfigurable architecture for VLSI 
processing arrays. M.Sami and R.Stefanel-
li, National Computer Conference, 1983. 
/12/ Computer Architectures and Parallel 
proceaeing. K.Hwang and F.Briggs, 
McGraw-Hill ,- New York, 1984. 
/13/ OCCAM - an overview. D.May arid R.Taylor, 
Microproceaoors and microsystems, Vol.2, 
No.2, March 1984. 
/14/ Concurrent VLSI Architectures. C.L.Seits, 
IEEE Trans, on Computer, Vol.c-33, No.12, 
December 1984. 
/15/ The transputer implementation of occam. 
D.M«y and Shepherd, Proceedinga of the 
International conference on fifth gene-
ration computer ByBtems, ICOT, 1984. 
/16/ On Supercomputing With Syatolic/Wavefront 
Array Proceaaors. Kung S.Y., Proč. IEEE, 
July 1904. 
/17/ Poat-failure reconfiguration of CSP 
programa. M.Šhati, IEEE Tranaaction on 
Software Engineering, Vol.SE-11, No.10, 
October 19B5. 
/18/ An Engineerable and Reconfigurable 
Cellular Array Processor. J.M.Cotton,-
Parallel Computing 05, 1986. 
/19/ Hisrarchical array processor (HAP) 

24 
•featuring high realibility and high 
aystem per-formance. T.Ishikawa, S.Momoi, 
S.Shimada, Y.Ogawa, Proč. o-f the 19B6 
International Conference on Parallal 
Processing, Auguet 1986. 
/20/ Product In-f ormation, The Transputer 
Farnily. Inmos Corporation, Part No.72, 
198i. 
/21/ 8ynthesizing non-uni-form systolic 
designs. C.Guerra and R.Melhem, Proč. o-f 
the International Con-ference on Paral lel 
Processing, IEEE, Auguat 1986. 
/22/ Hardware recon^iguration o-f transputer 
networks -far distributed objekt-orientc3d 
programming. D.Q.M.Fay and P.K.Dae, 
Microprocessing and Microprogramming 21, 
1987. 
/23/i Systalic Arrays--From Concept to Implemen-
I tation. J.A.F.Fortas and B.W.Wah, 
Computer, Vol.20, No.7, July 1987. 
/24/I Mapping Data Flow Programs on a VLSI Ar— 
i ray of Processors. Mendelson B. and 
i e.M.Silberman. Proč. 1987 Int'l Con-f. 
i Computer Architecture, June 1987. 
/25/ i Wave-f ront Array Processors-Concept to 
Implementation. S.V.Kung, S.C.Lo, 
S.N.Jean and J.N.Hwang, Computer, Vol.20, 
No.7, July 1987.