%PDF-1.3
%
1 0 obj
<>
endobj
2 0 obj
<>stream
2010-07-12T12:16:25+02:00
2010-07-12T12:16:25+02:00
2010-07-12T12:16:25+02:00
Canon
application/pdf
uuid:2f6fb573-2581-4a12-9433-78efa63d19db
uuid:b7494f77-cc83-4c58-9ea6-ba2b339128da
endstream
endobj
3 0 obj
<>
endobj
5 0 obj
<>
endobj
6 0 obj
<>
endobj
17 0 obj
<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI]/Subtype 26 0 R/XObject<>>>/Type/Page>>
endobj
18 0 obj
<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI]/Subtype 31 0 R/XObject<>>>/Type/Page>>
endobj
19 0 obj
<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI]/Subtype 36 0 R/XObject<>>>/Type/Page>>
endobj
20 0 obj
<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI]/Subtype 41 0 R/XObject<>>>/Type/Page>>
endobj
21 0 obj
<>/ProcSet[/PDF/Text/ImageB/ImageC/ImageI]/Subtype 46 0 R/XObject<>>>/Type/Page>>
endobj
46 0 obj
<>stream
114por el gran nmero de posib'les elecciones que tenemos, en general,para el conjunto U'CU, lU'l< n.Debi do a el I o, en esta secci n damos un a'l gori tmo para obtener djversos grafos mnimos a partir de *r,n gu, si bien no per-mite 11egar a todas las configuraciones posibles, tene al menos laventaja de que es fci I mente ap1 i cabl e. En primer 'l ugar di scuti re-mos dicho a'l goritmo usando la terminol oga propia de nuestro sistema multiprocesador.Partimos pues de la interconexin total entre buses y memoriar (Kr,n) y queremos decid'ir, en cada "paso", cuando podenoselimjnar una conexin establecida entre una memoria y un bus.Consideremos que la memoria i est conectada a los N+1buses i1, iZ, ..., iN, itt*t , d(i) - N+1 y deseamos saber si sepuede o no eliminar 1a conexin (i,in+t). Si as lo hacemos, nosquedar d(i) = N, y ahora el problema slo puede surgir cuando en-tre las n memorias solicitadas est incluida la i. En este caso elsjstema degradar (el grafo obtenido no ser l.-centroconexo) cuandoexista al menos un conjunto formado por n-L memorias ms la memorai ta'l que a N memorias de entre estas n-1 tengamos que asignarlesforzosamente los buses i1, i2,..., iN. Ver figura 5.3.1.
J1
1"2
JN
JN*12
N memorias
Fi g.
5.3.1
a
Una condi ci nca es gue, en cual qui er(o sea, el total menos
n memorl assuficienteconj unto dela memoria i
para que este caso noN memorias tomadas de) exista al menos una
se produz-entre m- 1que est
endstream
endobj
47 0 obj
<>stream
JFIF ,,
$.' ",#(7),01444'9=82<.342
2!!22222222222222222222222222222222222222222222222222
} !1AQa"q2#BR$3br
%&'()*456789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz w !1AQaq"2B #3Rbr
$4%&'()*56789:CDEFGHIJSTUVWXYZcdefghijstuvwxyz
! ? Ӛ) PRE S
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
( 9@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ TZ* (`PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE gQp
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
J`PE S
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
( ր
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
) Q@( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (@ Q@ Q@ Q@% `R
)Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@% `PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE Z( Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ RP@ QH`PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PE PIJ-( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (E S
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
) QL ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( (E0
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
( - Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@!*- Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@ Q@}8CG7~U-X),@4
\E6Æ66хUl>+x#`{QkW֛:u"