PDF de programación - Tesis: Gustavo Tellez - KerneL Escalable Para Una Red de Transputer - En Topologia Hipercubo

C P T • t t ! INVESTIS ACI U Y t t
U T UD itJS AV~ '-l 08S ~H

I. F'. N .
l _ ! O T E O I \
•
INGENIE RI A ELECTRIC ~

I Ei

Centro de lnvestigaci6n y de Estudios Avanzados del

lnstituto Politecnico Nacional

CINVESTA V -lPN

Departamento De Ingenielia Electlica

Secci6n Computaci6n

KHipeR:

KerneL Escalable Para Una Red de Transputer

En Topologia Hipercubo

Tesis que preseota el lng. Gustavo Serfo Te!Jez Rangel para obtener el grado de ~AESTRO EN

ClENCIAS en Ia especialida<l de INGENIERIA ELECTRICA coo opci6n eo COMPUT A CION

Trabajo dirigido por el M.en C. Jose Oscar Olmedo.

CIN v'EST AV

I P N

ADOU151CION
D£ LIBROS

\

Meltico D.F .• Mayo de 1995

llfK'~Ii 9£ IHvtST;«,rlt' y 04

~l("tl.' '~:···

(\'4.' 1·''9'". 'ft

L P. ! ... ~.

l Iii< L.

Gi
1"1G£NIERIA ELECTRIC~

' -' - E C "'

1.2. Transputer ..
1.3. Breve Nomenclatura Gr3fica

IN DICE

. . .. . 4
. 6

2 PRESENTACION DEL SISTEMA .

. . 6
11.1 . Elecci6n de los componentes del sistema .. . . . .. . .. . . . . . . . .. . . . . . . . . . ...... .......... 6
6
.. . ..... ... .......... .... ..... ........ .. .. .. .... ... 7
. .. .. .. . !

II. 1.1 ElecciOO de Ia topologia . .
0 .1.2 Elecci6n del modelo
IU .3 ElecciOn de procesador
ll .l .4 Elecci6n dellenguaje ..

...... .. ... . ... . .. .. .

.

U.2 Problemas. ..

. ..... .. .. .. .. .

.

11.2.1 Portabilidad y Abstracci6n..
0 .2.2 Comunic.aci6o entre procesos ..
ll.2 .3 Mapeode los procesos
11.2.4 Control de los procesos ..

UJ Soluci6o planteada

. .. .

. .. . ...

. .... ..

. ..... 9
. ....... 9
. . .... 10
.... 10
. ...... 11
. .. . ......... II
12
17
. ..... .... 17
20
21
22
...... ..... .. . ... . ..... ..... .. ..... . .. .. ....... 28

.

11.3.1 Extensiones a Ia sintaxis delleoguaje C. . .
ll .3.2 Kernel
11.3.3 Modelaci6n del trafico en Ia red ..

0 .3.3.1 Modelo 1..

113.3.2

113.4. KHtperyel modelo OSL.

VISTA DEL USUARIO..

lll.l DescripciOO...
IU.2 Uso de Ia capa de cootrol de procesos ..

. .... 30
. . . . . . . . . . . . . . . . . .. .... .... .... . .... ...... . .... ....... . 30
. .... ....... 31
. .. 31
. .. . ....... . .. ... ..... 32
. 34
. .. ... ......... ....... .. 37
. .. . .. .......... 38
. ... 40
. . . ........ . . .. .. ... ... ... .. 42
. ... 44
. ... . ... .... .. .... .. . ...... ...... . 44
. .. 46
. . .. ... . .. . .. . . . . . . .. . .. . .. ... . . ... .. . . . . . ... . 47
m .3 Uso de Ia capa de conumicaciooes abstractas ........... ... ......... ... . ... . .. .... .. ... ... 49
. . 49

m .2.1 CoostrucciOO Par..
lll.2.2 Como funciona KHiper
ffi .2.3 Paso de parimetros...
III.2.4 ColocaciOO en procesadores especificos .. .. . .. .... ...
ill .2.5 PatrOO de Comunicacion.es y Mapeo... .
ITI.2.6 Canales ..
m .2. 7 Arreglos de identificadores y de canales .. .
111.2.8 ObtenciOn del mejor mapeo .
m .2.9 ConstrucciOO Seq...
lll.2.10 Cilculo del Mapeo segUn el Tr.\fico ..
m .2.ll ConstrucciOO Alt .

lli.3.1 Un ejemplo seocillo. ..

. ..

4 Capa de Comunicaciones. ..

. .. ...............

. ... . .. . .. . .. . .. . . . . . . . . . .. . . . . . . . .. . ... ... .. . . . . . .. .. 51
. . . . . . . . . . . . . . ............ 51
IV. l. Estructura . . .
. .. . 53
IV.2. Canales Virtuales y Extremos... .
.. ........ ......... ...................... 55
IV.3 Ruteo.
. . ..... 56
IV.4 Protocolo de comunicaciones...
61
!V.5
!V.6
61
IV.7. Funci6n ah De Comunicaciones ............... ........ ........ .............................. 63
. ............................................... ............. ................ ...... . 64
IV.8. Broadcast ..
IV.9. HabilitaciOn De Canales.. .
. .................................... ..... . 64
IV.IO.Escalamiento De La Capa De Comunicaciooes
66
IV . ll.Medida de Ia sobrecarga .
. ....... .............................................. 6 7
IV.I 2.1nicializ.aci6n y Ftnaliz.aciOn ...... ..... .............................. ....................... .. 67

Capa de Control de Procesos .

. ....

V.4.l. La coostrucci6n PAR...

V. I. Estructura...
V.2. C6digo simetrico
V.3. ldentificador del proceso ..
V.4 Control de procesos concurrentes . ..

. .. ..... 69
. ..... .......... .. .. ....... .. . .............. 69
... ............ ............................ ....... ........................ 71
................... 71
... ........................................................ 73
. ................... 74
V.4.1.1 Infonnaciro de los hijos y Serializ.aciOn ..
. 74
V.4.1.2 Condiciones de RecalendarizaciOn ........................................ 76
V.4.2. La construcci6n ALT .................................. ....................................... 77
V.4 .3. Pasodeparimetros
77
...................... ....... 79
V.4.4. Mapoo
... 79
Algoritmo r~rsivo .. . .. . ... .. . ... ... . .. ... . .. ... . .. . . . . ... . .. ... .. ... ... .. 79
ElecciOn del siguiente . ... . .. . .. . .. ... . ... .. .. . . ........... ............... . 82
. ............... .. ......................... 84
Algoritmo secuencial ...
Adqu.isiciOn del patr6n de comunicaciones . .
. .. 85
86
V.5. Control de los Canales Virtuales . ... ... ... ... . ... . . . . . . . .. . . . . . . ................................ 90
.............. .. ....... .. ............................................. 90
.................. 90
V.6. Mandar y recibir informaciOn a pant.1lla y teclado . ............................................ 93

V.4.4 .l Mapeo segUn el modelo 1.. ...... ................................

V.4.4.2. Mapeo segUn el modelo II

lnicializaciOn
HabilitaciOo

Funciones de las Capas...

Vl.l DescripciOO. de las funciones de Ia capa de comunicaciones .

Familia ahwait....
Familia broadCJist. .
Familia guardin....
inhibit .
Familia in ...
Familia out ..
Familia set ..

. . ..........................

. ................................................... 94
. . . . . . ................ 94
. . ....................................................... 94
.. ......... ....................... 95
. ........... .... .. .............. ............................ 95
. .............. 96
96
. ··········································· 96
. ... ..... 96

.............................. .

c.I.-TRt at lMVESl iG>n• Y h
!

UT\J81tl~ H ~

,

v

I. P . N.
I. L

& IS& L IC..'
" 'r,ENIERIA EltC: .;.;,

Vl.2. Descripci6n de las funciones de Ia capa de control

chaninit .....
Familia getchan ...
Familia get.
Familia newpid
hmanybytes ...
toScreen.

.. ........ ········ 97
................................ 97
. ... . 97
. ............................ 97
98
......... .... ........ 98

Vl.l.

100

Conclusiones y Resultados .

VII. I Resultados
VU.2 Aplicaciooes

Vll.3 Perspe<:tivas de desarrollo .

Implementar KHiper sobre un hipercubo de 80x86 ...

Vll.2.1 Graficaci6n de autOmatas c.elulares .. .
VII.2.1 40,320 anillos en wt hipercubo d-3

102
102
103
. .... .......... 103
103
.. ............ 105
VII.3. 1 Limite Din:Unico de Canales Virtuales ................ ........ ................... 105
Vll3.2 Aumentar Ia dimensiOn de KHiper a orden 4 ..
.. .......... 105
VII.3.3
......................... 106
.. ........ ....... 106
Vll.3.4 MigratiOn de proc.esos...
VII.3 .5 KHiper..Com para otras topologias
106
lncremeotar Ia eficiencia de las funciones a anfitri6n ......................... 106
VD.3.6
VII.3. 7 Acc.eder archivos desde cualquier procesaddr . ..................................... 107
VII.3.8 Convertir KHiper multiusuario
107
VII.3 .. 9 Mejorar las funciones vecindad .. ...... .. .. ....... .......... ............ . .. 107
VI1.3. 10 lmplementar metodos para simular memoria compartida ...
.. 107
VII.3 .11 Medir el overhead causado por las capas de KHiper ..
.. .................... I 07
VU.3.12 Mapeo estocastico ..................................................................... 107
VU.3.Cootexto de programaciOO ......................... ........ . .............
..................... 108
. .. .. ..................................................... I 09
Vll.4 Transparencia del sistema ..
VU.5 Ventajas y desventajas ..................................................................................... I 10
VII.6 Conclusiooes...
.. .......................... Il l

CU Tftt O! r~vEsllu cro• y,.

nruDuJs AVANZ ttit) ~o

I. P. N .

I 8 L

•
i'I':ENI£RIA Ell: ; fi"!C•

I () T E C A

La necesidad de una mayor potencia computaciona/ crece continuamente. La
soluci6n tradiciona/ de crear procesadores m6s r6pidos se muestra cada vez m6s
inadecuada El costo de las supercomputadoras, sistemas que usan estos
procesadores especiales, es sumamente restrictivo. Ademils con Ia cercania coda
vez mayor a/limite de Ia velocidad en los circuitos de silicio se ha visto Ia
necesidad de investigar intensamente sobre otras alternativas. Por los resultados
que se han obtenido hasta este momenta se observa que los sistemas concurrentes
pueden ser una exce/enre so/uciOn

Una so/uci6n a/ requerimiento de computadoras m6s veloces se encuentra en
formar redes de procesadores, una que ha mostrado amplias ventajas es e/
hipercubo. Un procesador diseiiodo para este tipo de redes se llama transputer.

Conecrar varios transputers paraformar una red es extremadamente simple,
sin embargo esta simplicidad en hardware se paga a/ momenta de disenar y
codificar Ia comunicaci6n y sincronizaci6n de los procesos que conslituyen a/
programa.

Dentro de lo soluci6n desorro/lada se encuentra una extensiOn al/enguaje de
programaci6n C con sintaxis que permife e/ uso de construcciones concurrenres.
esto bajo e/ modelo c.s.p. el cual ha mostrado amplios venrojas

l:la'Ut D< .'

fSTUr-1 ·· ·

g

I E;

objetivos

Se puede