Computadores Paralelos

Vista previa del material en texto

COMPUTADORES 
PARALELOS 
 
 
Computación de Alta Velocidad 
 
 
 
 
 
 
 
 
 
A. Arruabarrena — J. Muguerza 
 
Konputagailuen Arkitektura eta Teknologia saila 
Informatika Fakultatea — Euskal Herriko Unibertsitatea 
 
 
 
 
 
 
 
COMPUTADORES 
PARALELOS 
 
 
Computación de Alta Velocidad 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
A. Arruabarrena — J. Muguerza 
 
Konputagailuen Arkitektura eta Teknologia saila 
Informatika Fakultatea — Euskal Herriko Unibertsitatea 
 
 
 
 
 
 
 
 
septiembre 2011 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ÍNDICE 
 
 
 Introducción ......................................................................... 1 
Capítulo 1. Computadores Vectoriales ............................................... 7 
1.1 ¿Qué es un computador vectorial? ................................................................... 7 
1.1.1 Algunos problemas ............................................................................................... 10 
1.1.1.1 La memoria de un computador vectorial .......................................... 10 
1.1.1.2 Unidades funcionales vectoriales ........................................................ 11 
1.1.1.3 Registros vectoriales ............................................................................... 11 
1.1.1.4 Programas vectoriales ............................................................................ 12 
1.1.2 Arquitectura y lenguaje-máquina ...................................................................... 13 
1.2 Dependencias de datos ..................................................................................... 15 
1.2.1 Encadenamiento (chaining) ........................................................................................... 16 
1.2.1.1 Encadenamiento con dos instrucciones ............................................ 17 
1.2.2 Tablas de ejecución de las instrucciones ........................................................ 18 
1.3 Dependencias estructurales .............................................................................. 20 
1.3.1 Buses de memoria (unidades funcionales LV/SV) ........................................ 20 
1.3.2 Conflictos en el uso de los módulos de memoria ........................................ 22 
1.3.2.1 Una sola operación de memoria ......................................................... 22 
1.3.2.2 Varias operaciones de memoria .......................................................... 26 
1.3.3 Longitud de los registros vectoriales (strip mining) ...................................... 29 
1.4 Velocidad de cálculo de los computadores vectoriales ............................ 30 
1.4.1 Velocidad de cálculo en función de la longitud de los vectores .............. 31 
1.4.1.1 R∞ y N1/2..................................................................................................... 31 
1.4.1.2 Speed-up o factor de aceleración ....................................................... 33 
1.4.1.3 Nv ................................................................................................................. 34 
1.4.2 Influencia del código escalar. Ley de Amdahl. .............................................. 34 
1.5 Técnicas de compilación para generar código vectorial ........................... 37 
1.5.1 Dependencias de datos entre instrucciones .................................................. 38 
1.5.2 Vectorización ......................................................................................................... 40 
1.5.2.1 Vectores de una dimensión .................................................................. 40 
1.5.2.2 Vectores de N dimensiones ................................................................. 44 
1.5.2.3 Condición para vectorizar un bucle ................................................... 45 
1.5.2.4 Test de dependencias ............................................................................ 46 
1.5.3 Optimizaciones...................................................................................................... 50 
1.5.3.1 Sustitución global hacia adelante (global forward substitution) ................... 50 
▪ vi ▪ ÍNDICE 
1.5.3.2 Eliminación de las variables de inducción ......................................... 51 
1.5.3.3 Antidependencias (DR, WAR) ...................................................................... 52 
1.5.3.4 Dependencias de salida (RR, WAW) ........................................................ 53 
1.5.3.5 Intercambio de bucles (loop-interchanging) .......................................... 54 
1.5.3.6 Expansión escalar (scalar expansion) ........................................................ 56 
1.5.3.7 Fusión de bucles (loop fusion) ..................................................................... 57 
1.5.3.8 Colapso de bucles (loop collapsing) ......................................................... 58 
1.5.3.9 Otras optimizaciones ............................................................................. 59 
1.5.4 Vectores de máscara y vectores de índices ................................................... 60 
1.5.4.1 Uso de máscaras ..................................................................................... 60 
1.5.4.2 Vectores de índices ................................................................................ 61 
1.6 Resumen ................................................................................................................ 64 
Capítulo 2. Computadores Paralelos (conceptos básicos) ................. 69 
2.1 Introducción ......................................................................................................... 69 
2.2 Computadores DM-SIMD ................................................................................. 71 
2.3 Computadores MIMD ........................................................................................ 73 
2.3.1 Memoria compartida (shared memory) .................................................................. 73 
2.3.2 Memoria privada o distribuida (distributed memory) ....................................... 74 
2.3.3 Memoria lógicamente compartida pero físicamente distribuida 
(distributed shared memory) ......................................................................................... 75 
2.3.4 Clusters, constellations... y otros ....................................................................... 76 
2.4 Algunos problemas ............................................................................................. 77 
2.5 Rendimiento del sistema paralelo (leyes de Amdahl y Gustafson) ......... 79 
Capítulo 3. Coherencia de los Datos en los Computadores 
SMP ...................................................................................... 83 
3.1 Presentación del problema y revisión de conceptos .................................. 83 
3.1.1 Coherencia de los datos en los sistemas de un solo procesador ............. 84 
3.1.2 Coherencia de los datos en los multiprocesadores de memoria 
compartida (SMP) ................................................................................................. 85 
3.1.3 Falsa compartición ................................................................................................ 86 
3.1.4 Definición de la coherencia................................................................................ 87 
3.2 Protocolos de coherencia snoopy .................................................................. 88 
3.2.1 Estados de los bloques en la memoria cache y señales de control .......... 90 
3.2.2 Protocolos de invalidación ................................................................................. 93 
3.2.2.1 Un protocolo de tres estados, MSI ..................................................... 94 
3.2.2.2 El protocolo Illinois, MESI ...................................................................... 97 
3.2.2.3 El protocoloBerkeley, MOSI ................................................................ 99 
3.2.2.4 Resumen de los protocolos de invalidación................................... 100 
ÍNDICE ▪ vii ▪ 
3.2.3 Protocolos de actualización ............................................................................. 101 
3.2.3.1 El protocolo Firefly, MSE(I) .................................................................. 101 
3.2.3.2 El protocolo Dragon, MOES(I) ........................................................... 103 
3.2.4 Resumen de los protocolos de tipo snoopy ................................................ 105 
3.3. Implementación de los protocolos snoopy ................................................ 105 
3.3.1 Problemas ............................................................................................................. 105 
3.3.1.1 Directorio de la memoria cache ........................................................ 106 
3.3.1.2 Búferes de escritura .............................................................................. 107 
3.3.1.3 Protocolo de petición de bus ............................................................. 108 
3.3.1.4 Atomicidad: estado del controlador snoopy .................................. 109 
3.3.2 El protocolo Illinois y la atomicidad ................................................................ 110 
3.3.2.1 Carreras: estados transitorios, señales BRQ y BGN ..................... 110 
3.3.2.2 Deadlock, livelock, starvation ............................................................ 112 
3.4 Snoopy jerárquico ............................................................................................. 113 
3.4.1 Lecturas .................................................................................................................. 115 
3.4.2 Escrituras ................................................................................................................ 116 
Capítulo 4. Sincronización de Procesos en los Computado-
res SMP .............................................................................. 119 
4.1 Introducción ....................................................................................................... 119 
4.2 Exclusión mutua (mutual exclusion) ............................................................. 123 
4.2.1 Instrucciones Test&Set y Swap ........................................................................ 125 
4.2.1.1 Instrucción Test&Set ............................................................................. 125 
4.2.1.2 Instrucción Swap ................................................................................... 125 
4.2.1.3 Análisis del tráfico ................................................................................. 126 
4.2.1.4 Procedimiento Test&Set with backoff .............................................. 127 
4.2.1.5 Procedimiento Test-and-Test&Set ...................................................... 128 
4.2.1.6 Resumen de características ................................................................ 130 
4.2.2 Instrucciones Load Locked / Store Conditional y Compare&Swap ....... 131 
4.2.2.1 Instrucciones LL y SC ........................................................................... 132 
4.2.2.2 Instrucción Compare&Swap ............................................................... 134 
4.2.2.3 Algunos problemas con las instrucciones LL/SC ........................... 135 
4.2.3 Instrucciones Fetch&Op .................................................................................... 136 
4.2.4 Alternativas para reducir el tráfico .................................................................. 137 
4.2.4.1 Tickets ...................................................................................................... 137 
4.2.4.2 Vectores de cerrojos ............................................................................ 139 
4.3 Sincronización "punto a punto" mediante eventos ................................... 141 
4.4 Sincronización mediante barreras ................................................................. 142 
4.4.1 Una barrera sencilla ............................................................................................ 142 
4.4.2 Barreras reutilizables .......................................................................................... 143 
4.4.3 Eficiencia ................................................................................................................ 145 
4.5 Resumen .............................................................................................................. 146 
▪ viii ▪ ÍNDICE 
Capítulo 5. Consistencia de la Memoria en los Computa-
dores Paralelos ................................................................ 149 
5.1 Introducción ....................................................................................................... 149 
5.1.1 Sistemas de un solo procesador ...................................................................... 149 
5.1.2 Sistemas multiprocesador ................................................................................. 150 
5.1.3 Semántica de los programas y orden de ejecución de las 
instrucciones ......................................................................................................... 151 
5.1.4 Atomicidad de las instrucciones ...................................................................... 153 
5.1.5 Modelos de consistencia ................................................................................... 154 
5.2 Consistencia secuencial (SC, sequential consistency) .............................. 155 
5.2.1 Orden y atomicidad de las instrucciones de memoria .............................. 156 
5.2.2 Efectos en el hardware y en el compilador .................................................. 158 
5.3 Modelos relajados (relaxed) ........................................................................... 159 
5.3.1 Total Store Ordering (TSO) / Processor Consistency (PC) ....................... 160 
5.3.2 Partial Store Ordering (PSO) ............................................................................ 162 
5.3.3 Modelos más relajados ...................................................................................... 163 
5.3.3.1 Weak Ordering (WO) .......................................................................... 164 
5.3.3.2 Release Consistency (RC) ................................................................... 164 
5.4 Resumen y perspectivas .................................................................................. 166 
Capítulo 6 La Red de Comunicación de los Computadores 
Paralelos. Comunicación mediante Paso de 
Mensajes. .......................................................................... 169 
6.1 Introducción ....................................................................................................... 169 
6.2 Topología de la red ........................................................................................... 171 
6.3 Redes formadas por conmutadores .............................................................. 173 
6.3.1 El conmutador (switch) .................................................................................................. 174 
6.3.2 Red crossbar ......................................................................................................... 175 
6.3.3 Redes multietapa (multistage) .................................................................................... 176 
6.3.3.1 La red Omega ........................................................................................ 176 
6.3.3.2 Encaminamiento en la red Omega ................................................... 178 
6.3.3.3 Conflictos de salida y bloqueos ......................................................... 179 
6.3.3.4 Otro patrón de comunicación: broadcast. ..................................... 181 
6.3.3.5 Otras redes .............................................................................................181 
6.3.3.6 Resumen .................................................................................................. 183 
6.4 Redes formadas por encaminadores de mensajes .................................... 184 
6.4.1 Encaminadores de mensajes ............................................................................ 184 
6.4.2 Topologías de red más utilizadas .................................................................... 185 
6.4.2.1 Redes de una dimensión: la cadena y el anillo .................................. 186 
6.4.2.2 Mallas y Toros (mesh, torus) ....................................................................... 187 
ÍNDICE ▪ ix ▪ 
6.4.2.3 Hipercubos (hypercube) ............................................................................... 188 
6.4.2.4 Árboles y árboles densos (fat tree) ........................................................... 190 
6.4.2.5 Resumen de topologías ....................................................................... 191 
6.4.2.6 Los enlaces físicos ................................................................................. 193 
6.5 La comunicación a través de la red en los sistemas paralelos ............... 193 
6.5.1 Los mensajes ........................................................................................................ 194 
6.5.2 Patrones de comunicación: con quién y cuándo hay que 
efectuar la comunicación. ................................................................................. 195 
6.5.3 Construcción del camino (switching strategy) ................................................... 198 
6.5.4 Encaminamiento de los mensajes (routing) ......................................................... 199 
6.5.4.1 El registro de encaminamiento .......................................................... 200 
6.5.4.2 Elección del camino: estático o adaptativo .................................... 203 
6.5.5 Control del flujo de información ..................................................................... 206 
6.5.5.1 Avance de los paquetes: Store-and-forward, 
Wormhole y Cut-through .................................................................... 206 
6.5.5.2 Conflictos en el uso de recursos: los búferes ................................. 210 
6.5.6 Eficiencia de la comunicación: latencia y throughput ............................... 214 
6.5.6.1 Tiempo de comunicación en la red .................................................. 215 
6.5.6.2 Considerando el tráfico en la red ...................................................... 217 
6.5.6.3 Cálculo del throughput máximo ........................................................ 219 
6.5.6.4 Análisis global ......................................................................................... 221 
6.5.7 Problemas de la comunicación ....................................................................... 222 
6.5.7.1 Deadlock (interbloqueos) Canales virtuales. Giros 
controlados (Turn model). Control de la inyección de 
paquetes. Utilización de caminos seguros ..................................... 222 
6.5.7.2 Problemas de livelock y starvation.................................................... 229 
6.5.8 Protocolos de comunicación ........................................................................... 230 
6.6 Evolución de los computadores paralelos ................................................... 232 
 
Apéndice. Cálculo de las distancias medias en diferentes topologías .......... 235 
Capítulo 7. Coherencia de los Datos en los Computadores 
DSM .................................................................................... 241 
7.1 Introducción ....................................................................................................... 241 
7.2 Directorios de coherencia ............................................................................... 243 
7.2.1 Introducción y clasificación ................................................................................ 243 
7.2.1.1 Problemas................................................................................................ 245 
7.2.2 Estructura de los directorios ............................................................................. 246 
7.2.2.1 Directorios implementados en memoria principal ....................... 246 
7.2.2.2 Directorios implementados en memoria cache ............................ 251 
7.2.3 Optimización del tráfico de coherencia ........................................................ 254 
7.2.4 Atomicidad de las operaciones: carreras ...................................................... 257 
▪ x ▪ ÍNDICE 
7.3 Implementación de los protocolos de coherencia: dos 
ejemplos .............................................................................................................. 259 
7.3.1 Protocolo de coherencia de los multicomputadores SGI Origin ............ 259 
7.3.1.1 Lecturas .................................................................................................... 260 
7.3.1.2 Escrituras .................................................................................................. 263 
7.3.1.3 Actualización de la memoria principal ............................................ 268 
7.3.2 El protocolo de coherencia estándar SCI en la máquina NUMA-Q 
de Sequent. ........................................................................................................... 269 
7.3.2.1 SCI: estados y operaciones ................................................................. 270 
7.3.2.2 Lecturas .................................................................................................... 272 
7.3.2.3 Escrituras .................................................................................................. 273 
7.3.2.4 Actualización de la memoria principal ............................................ 277 
7.3.2.5 Atomicidad y carreras .......................................................................... 277 
7.4 Resumen .............................................................................................................. 279 
Capítulo 8. Paralelización y Planificación de Bucles .................. 281 
8.1 Introducción ....................................................................................................... 281 
8.1.1 Ideas básicas sobre paralelización de bucles ............................................... 287 
8.2. Estructuras básicas para expresar el paralelismo de los bucles .............. 290 
8.2.1 Bucles sin dependencias entre iteraciones: bucles doall .......................... 290 
8.2.2 Bucles con dependencias entre iteraciones ................................................. 291 
8.2.2.1 Bucles forall (sincronización global .................................................. 292 
8.2.2.2 Bucles doacross (sincronización punto a punto) .......................... 293 
8.2.3 Efecto de las antidependencias y de las dependencias de salida ........... 298 
8.2.4 Atención con las instrucciones if ..................................................................... 299 
8.3 Implementación de la sincronización........................................................... 300 
8.3.1 Sincronización mediante contadores ............................................................. 301 
8.3.2 Un único contador por procesador................................................................ 303 
8.4 Optimizaciones para paralelizar bucles de manera eficiente ................. 304 
8.4.1 Eliminación del efecto de las dependencias que no son esenciales ...... 304 
8.4.2 Fisión de bucles ................................................................................................... 305 
8.4.3 Ordenación de las dependencias ................................................................... 306 
8.4.4 Alineación de las dependencias (peeling) .................................................... 307 
8.4.5 Extracción de threads independientes (switching) .....................................309 
8.4.6 Minimización de las operaciones de sincronización ................................. 310 
8.4.7 Tratamiento de bucles (reordenación...) ........................................................ 311 
8.4.7.1 Intercambio de bucles.......................................................................... 311 
8.4.7.2 Cambio de sentido................................................................................ 314 
8.4.7.3 Desplazamientos (skew) ....................................................................... 314 
8.4.7.4 Colapso y coalescencia de bucles .................................................... 315 
8.5 Planificación de bucles (scheduling) ............................................................... 316 
8.5.1 Reparto de las iteraciones: consecutivo o entrelazado ............................. 317 
ÍNDICE ▪ xi ▪ 
8.5.2 Planificación estática o dinámica .................................................................... 318 
8.5.2.1 Planificación estática ............................................................................ 319 
8.5.2.2 Planificación dinámica: autoplanificación (self/chunk 
scheduling), autoplanificación guiada (GSS) y trapezoidal 
(trapezoid self scheduling) ........................................................................... 319 
8.6 Secciones paralelas: Fork / Join ..................................................................... 323 
8.7 Análisis del rendimiento................................................................................... 325 
Capítulo 9. Computadores de Alta Velocidad. Herramientas 
para Programar Aplicaciones Paralelas 
(introducción). ..................................................................... 327 
9.1 Computadores paralelos de alto rendimiento ............................................ 328 
9.2 Herramientas para programar aplicaciones paralelas (introducción) ... 331 
9.2.1 OpenMP ................................................................................................................ 332 
9.2.2 MPI ......................................................................................................................... 336 
 
 
 
 
 
 
Introducción 
 
 
 
 
 
 
 
 
 
 
 
 
¿Qué tiempo hará mañana en esta ciudad? ¿Cómo evolucionan las 
galaxias? ¿Cómo interaccionan los electrones en una molécula de clorofila? 
¿Se comportarán de manera adecuada las alas de un avión en una 
turbulencia? Para dar respuesta adecuada a esas y otras muchas preguntas, 
científico/as e ingeniera/os utilizan potentes computadores, la herramienta 
principal de cualquier laboratorio en la actualidad. Las aplicaciones técnico-
científicas requieren de grandes cantidades de cálculo, casi de manera 
ilimitada, y además hay que obtener resultados en el menor tiempo posible, 
(prever mañana las lluvias torrenciales de hoy no sirve para mucho!). A 
pesar del espectacular incremento en la velocidad de cálculo de los 
procesadores, las necesidades van siempre muy por delante. A lo largo de la 
evolución de los computadores tres han sido las líneas principales que han 
▪ 2 ▪ INTRODUCCIÓN 
permitido aumentar de manera continuada la velocidad de los mismos: los 
avances en la tecnología electrónica, el desarrollo de nuevas estructuras o 
arquitecturas de computadores, y el uso de tecnologías del software 
(compiladores, etc.) cada vez más eficientes. 
Mediante la tecnología electrónica se ha conseguido integrar en un sólo 
chip una cantidad ingente de transistores: hoy en día por encima de 1.000 
millones (y cada vez más). A consecuencia de este avance, cada vez son más 
las "partes" del computador que se van integrando en un solo chip junto con 
el procesador: unidades funcionales específicas, registros, memoria cache... e 
incluso varios procesadores o núcleos (core). Del mismo modo, la frecuencia 
del reloj del computador es cada vez más alta (aunque la carrera para usar 
relojes cada vez más rápidos está detenida en este momento), actualmente en 
el intervalo 1-4 GHz, lo que quiere decir que el tiempo de ciclo está por 
debajo del nanosegundo (F = 1 GHz → T = 1 ns) y, como consecuencia, se 
pueden hacer más operaciones por unidad de tiempo. 
Desde el punto de vista de la arquitectura del sistema, todos los 
procesadores actuales son superescalares o de tipo VLIW (la ejecución de las 
instrucciones es segmentada y se intenta ejecutar más de una instrucción 
cada ciclo); la jerarquía de memoria cache permite accesos más rápidos, los 
registros se organizan para optimizar el uso de los datos, etc. 
Las técnicas de compilación también han avanzado mucho. El objetivo 
principal es eliminar el efecto de las dependencias existentes entre las 
instrucciones, y ocultar la latencia de la unidades funcionales (aprovechando 
ese tiempo para realizar trabajo útil). 
Sin embargo, a pesar de que tenemos procesadores superescalares muy 
rápidos —que llegan a superar la velocidad de cálculo de 10 Gflop/s— para 
muchas aplicaciones, tales como previsiones meteorológicas, simulaciones 
de procesos físicos y químicos, diseños de aeronáutica, prospecciones 
geológicas, diseño de nuevos materiales, desarrollos diversos en ingeniería, 
avances en biología, genética y farmacia, etc., dicha velocidad no es 
suficiente. En el periodo 1986-2002, la tasa de crecimiento del rendimiento 
de los procesadores fue de un %52 anual (!), pero dicho crecimiento se ha 
reducido notablemente estos últimos años, situándose en torno al 20%: la 
velocidad que se puede conseguir con un procesador está llegando a sus 
límites físicos (y económicos). Por tanto, se necesita de desarrollar otro tipo 
de estrategias para conseguir las velocidades de cálculo —Teraflop/s, 
Petaflop/s, es decir, 1012, 1015 operaciones de coma flotante por segundo— 
que demandan las aplicaciones citadas. 
INTRODUCCIÓN ▪ 3 ▪ 
El paso que hay que dar es bastante claro: utilizar muchos procesadores, 
para repartir la ejecución de un programa entre ellos; es decir, utilizar 
sistemas paralelos. Además, las tecnologías de fabricación facilitan esta 
posibilidad: construido un procesador (chip), se hacen fácilmente miles de 
ellos y de manera relativamente barata. Por tanto, ¿por qué no utilizar 100, 
1.000, 10.000... procesadores para resolver un problema? Teóricamente, y si 
supiéramos cómo hacerlo, utilizando P procesadores podríamos ejecutar un 
programa P veces más rápido. Por desgracia, esto no va a ser así, ya que van 
a aparecer importantes problemas nuevos: ¿cómo se reparte el trabajo entre 
los procesadores? ¿son independientes los procesos o hay que 
sincronizarlos? ¿cómo se implementa la comunicación entre procesadores?... 
Existen muchas maneras de estructurar un computador de P procesadores. 
Algunas características serán comunes en todos ellos, y otras, en cambio, no. 
Existen diferentes formas de clasificar estas arquitecturas o estructuras. De 
entre ellas, la más conocida o utilizada es, seguramente, la de Flynn (1966), 
quizás por lo simple que es. En esta clasificación se tienen en cuenta dos 
parámetros: el número de flujos de instrucciones (es decir, el número de PCs 
o contadores de programa) y el número de flujos de datos que operan 
simultáneamente. La siguiente figura recoge dicha clasificación: 
 
 flujos de datos 
 uno muchos 
flujos de 
instrucciones 
uno SISD SIMD 
muchos MIMD 
 
• Computadores de tipo SISD (Single-Instruction-Single-Data) 
 Se ejecuta un único programa sobre un único conjunto de datos; por 
tanto, a esta clase pertenecen los sistemas clásicos de un sólo 
procesador (ordenadores personales, estaciones de trabajo…). Aunque 
en algunos casos dispongan de más de un procesador, éstos realizan el 
trabajo de manera independiente. 
 Como ya hemos comentado, las instrucciones se ejecutan de manera 
segmentada, dividida en varias fases —búsqueda, descodificación, 
lectura de operandos, memoria, unidad aritmética, escritura de 
resultados…—, y en cada fase habrá una instrucción (o varias, en el 
casode los procesadores superescalares). Así pues, se utiliza 
▪ 4 ▪ INTRODUCCIÓN 
paralelismo a nivel de instrucción (ILP, Instruction Level 
Parallelism). Además, el procesador (con ayuda del hardware o del 
compilador) es capaz de modificar el orden de ejecución de las 
instrucciones para conseguir la mayor eficiencia (velocidad) posible. 
 A lo largo del texto supondremos que todos esos conceptos son 
conocidos. 
• Computadores de tipo SIMD (Single-Instruction-Multiple-Data) 
 En este tipo de computadores se ejecuta simultáneamente el mismo 
programa en todos los procesadores, pero sobre diferentes conjuntos 
de datos; se aprovecha, por tanto, el paralelismo de datos (DLP, Data 
Level Parallelism). Dentro de este grupo podemos distinguir dos 
subgrupos: los denominados processor-array (distributed memory 
SIMD) y los procesadores vectoriales (shared memory SIMD). 
 En el primer caso, el computador dispone de muchos procesadores 
normalmente muy "simples" (por ejemplo, 16 k procesadores de un 
bit); todos los procesadores ejecutan el mismo programa de manera 
sincronizada, pero sobre datos diferentes. Se han construido muchas 
máquinas de tipo SIMD, sobre todo en los años 80-95, y para ciertas 
aplicaciones, tales como cálculo numérico, procesamiento de señal, 
etc., ofrecen muy buen rendimiento. 
 Sin embargo, hoy en día no se fabrican computadores de este modelo 
(aunque ideas similares se utilizan para generar entornos virtuales de 
dos y tres dimensiones); sí, en cambio, computadores vectoriales. 
 
• Computadores de tipo MIMD (Multiple-Instruction-Multiple-Data) 
 Es el caso general de un sistema paralelo. Se ejecutan muchos 
procesos (muchos PCs) sobre diferentes conjuntos de datos. ¡Ojo! no 
se trata de un conjunto de máquinas SISD, ya que los programas que 
se ejecutan no son independientes. 
 Este es el modelo que permite obtener elevadas velocidades de 
cómputo: computadores de paralelismo masivo, en los que P 
procesadores (un número alto) colaboran en la resolución de un 
problema; es decir, se explota el paralelismo a nivel de hilo o proceso 
(TLP, Thread Level Parallelism). En cualquier caso, surgen muchos 
problemas nuevos, a los que, si se quiere conseguir un buen 
rendimiento, habrá que buscar soluciones adecuadas. 
INTRODUCCIÓN ▪ 5 ▪ 
 Tal y como veremos en los próximos capítulos, podemos hacer una 
subclasificación en el grupo de las máquinas MIMD: 
 
• Sistemas de memoria compartida, en los que todos los 
procesadores utilizan el mismo espacio de direccionamiento. La 
memoria puede estar centralizada (SMP, symmetric 
multiprocessors) o distribuida (DSM, distributed shared 
memory). La comunicación entre procesos se realiza mediante el 
uso de variables compartidas. 
 
• Sistemas de memoria privada distribuida, en los que cada uno 
de los procesadores utiliza su espacio propio de memoria. LA 
comunicación entre procesos se realiza mediante paso de 
mensajes. 
 
 
A lo largo de los capítulos del texto vamos a analizar las máquinas 
paralelas de tipo MIMD, pero en el primero vamos a tratar sobre un tipo 
especial de computador SIMD de muy alto rendimiento: los computadores 
vectoriales. Se trata de una arquitectura de procesador específica, destinada 
al procesamiento de vectores, que ha conseguido un lugar destacado en la 
historia de la computación. En el capítulo 2 haremos una breve presentación 
de los sistemas paralelos: principales modelos y arquitecturas, problemas 
más importantes, la ley de Amdahl, etc. En el capítulo 3 analizaremos el 
problema de la coherencia de los datos en sistemas SMP; en el 4, las 
instrucciones y procedimientos básicos para sincronizar procesos paralelos: 
T&S, LL, SC...; y en el 5, los modelos de consistencia, secuencial y 
relajados, de la memoria de un sistema paralelo. En el capítulo 6, 
analizaremos la topología, estructura y funcionamiento de la red de 
comunicación de un sistema paralelo, así como la eficiencia de los 
mecanismos de comunicación entre procesadores. En el capítulo 7 
analizaremos nuevamente el problema de la coherencia de los datos, pero en 
los sistemas DSM: los directorios de coherencia. Dedicaremos el capítulo 8 a 
presentar las técnicas de paralelización de bucles y el reparto de tareas a los 
procesadores. Finalmente, en el capítulo 9 haremos un breve resumen de la 
situación actual de los sistema paralelos, analizando la lista top500, así como 
una breve presentación de las herramientas básicas para programar 
aplicaciones en paralelo: OpenMP, para los sistemas de memoria compartida 
SMP, y MPI, para el caso de paso de mensajes (en sistemas DSM o MPP). 
▪ 6 ▪ INTRODUCCIÓN 
 
 
 
 
▪ 1 ▪ 
 
 
Computadores Vectoriales 
 
 
 
 
 
 
 
 
 
1.1 ¿QUÉ ES UN COMPUTADOR VECTORIAL? 
Como hemos comentado en la introducción, las arquitecturas de tipo 
MIMD son las más adecuadas para resolver en paralelo aplicaciones de tipo 
general. Existen, sin embargo, algunos problemas importantes, desde el 
punto de vista del cálculo requerido, en los que es posible utilizar otro tipo 
de arquitecturas para lograr ejecuciones con un alto rendimiento. 
Como ya se sabe, en los programas de cálculo científico la mayor parte 
del tiempo de ejecución se invierte en la ejecución de bucles. Por ejemplo: 
 
do i = 0, N-1 
 C(i) = A(i) + B(i) 
enddo 
 
Si N es muy grande (N = 109, por ejemplo) el tiempo de ejecución de ese 
bucle será muy alto, a pesar de su estructura tan simple. Si lo ejecutamos en 
un procesador escalar, el código ensamblador será, por ejemplo, el siguiente: 
▪ 8 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
buc: FLD F1,A(R1) 
 FLD F2,B(R1) 
 FADD F3,F2,F1 
 FST C(R1),F3 
 
 ADDI R1,R1,#8 
 SUBI R2,R2,#1 
 BNZ R2,buc 
 
En un procesador escalar se ejecutaría, en el mejor de los casos, una 
instrucción por ciclo1, por lo que para ejecutar una iteración del bucle se 
necesitarían 7 ciclos; por tanto, el tiempo de ejecución de todo el programa 
sería de TE = 7N. 
El bucle anterior tiene dos características específicas. Por un lado, las 
estructuras de datos que utiliza —los vectores A, B y C— son muy regulares; 
y, por otro lado, todas las iteraciones del bucle se pueden ejecutar de manera 
independiente, ya que no existen dependencias de datos entre ellas. 
Para comenzar, definamos qué es, en este contexto, un vector. Un vector 
es una estructura que se puede definir mediante tres parámetros: 
 
• dirección de comienzo: dirección de memoria del primer elemento 
del vector. 
• longitud: número de elementos del vector. 
• paso (stride): distancia en memoria entre dos elementos consecutivos 
del vector. 
 
Por ejemplo, un vector que esté almacenado en las posiciones 1000, 1002, 
1004, 1006, 1008, 1010, 1012 y 1014 de memoria (cada componente ocupa 
una posición de memoria) se definiría así: 
 
 dirección de comienzo = 1000 longitud = 8 paso = 2 
 
Un procesador escalar, como su nombre indica, trabaja con escalares. Sin 
embargo, en las áreas de Ciencia e Ingeniería es muy común el uso de 
vectores y el tiempo de ejecución se invierte, principalmente, en la 
ejecución, una y otra vez, de bucles como el anterior. ¿Por qué no definir una 
arquitectura y un lenguaje máquina que directamente sean capaces de tratar 
con vectores? ¿Por qué no escribir el programa anterior de la siguiente 
manera? 
 
1 Si el procesador fuera superescalar, quizás se podría conseguir algo más de una instrucción por ciclo. 
1.1 ¿QUÉ ES UN COMPUTADOR VECTORIAL? ▪ 9 ▪ 
LV V1,A(R1) ; leer el vector A 
LV V2,B(R1) ; leer el vector B 
ADDV V3,V1,V2 ; sumar ambos vectores 
SV C(R1),V3 ; escribir el resultado en el vector C 
 
En este nuevo juego de instrucciones, la instrucción LV V1,A(R1) 
implicaría lo siguiente (utilizando, a modo de ejemplo, el esquema de 
segmentación que se muestra2): 
 
LV V1,A(R1) BD L AM M M M E 
 M M M E 
 M M M E 
 ... ... ... 
 M M M E 
 
Podríamos representar la ejecuciónanterior, de manera simplificada, de la 
siguiente forma: 
 
LV V1,A(R1) BD L AM M M M E E ... ... E 
 
Así pues, mediante una única instrucción leemos de memoria un vector 
completo de N elementos. Para que esto sea posible la memoria debe de estar 
segmentada, con lo que, si no existe algún otro impedimento, en cada ciclo 
proporcionará un elemento del vector, que se irán escribiendo en un registro 
vectorial. 
El siguiente esquema presenta la ejecución del programa anterior fase a 
fase (las latencias de las unidades funcionales son un simple ejemplo): 
 
LV V1,A(R1) BD L AM M M M E ... (N ciclos) ... 
LV V2,B(R1) BD L AM M M M E ... (N ciclos) ... 
ADDV V3,V1,V2 BD . . . . L A A E ... (N ciclos) ... 
SV C(R1),V3 BD L AM . . . . L M M M E ... ... E 
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... ... 14+N 
 
 ti N 
 
(Por ahora, supongamos que los operandos que necesitan las instrucciones ADDV y SV se 
pueden obtener en los ciclos 8 y 11, tal como se indica en la tabla). 
 
2 Las fases de ejecución habituales: BD, búsqueda y descodificación de la instrucción; L, lectura de los 
operandos; AM, cálculo de la dirección de memoria; A, una operación en una unidad funcional; M, una 
operación en memoria; E, escritura del resultado en los registros. Cada instrucción utiliza solamente 
las fases que necesita para su ejecución. 
▪ 10 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
Si el modelo de ejecución es ese, podemos hacer un análisis sencillo para 
obtener el tiempo de ejecución del bucle (de manera simplificada; un poco 
más adelante formalizaremos este cálculo): existe un tiempo de inicio —ti— 
antes de que la última instrucción comience a escribir, y después, para 
terminar la ejecución, se necesitan N ciclos, uno por cada elemento del 
vector. Por tanto: 
 
TV = ti + N 
 
 
Si comparamos esta expresión con la que hemos obtenido para un 
procesador escalar, la mejora es clara. Por ejemplo, si el número de 
elementos de los vectores es N = 128, y si ti = 14 ciclos, tendríamos los 
siguientes tiempos de ejecución: 
 
TE = 7 N = 896 ciclos 
TV = ti + N = 142 ciclos (un 16%) 
 
No es ésta la única ventaja. Por un lado, han desaparecido las 
dependencias de control3 debida al bucle, ya que, por definición, ha 
desaparecido el propio bucle. Por otro lado, sólo se han ejecutado 4 
instrucciones, y no las 7N que componían el bucle escalar. Esto implica que 
el uso de la cache de instrucciones es mucho más bajo, y, por consiguiente, 
el tráfico en el bus también. 
Pero, por supuesto, todas esas ventajas no salen “gratis”. A decir verdad, 
tenemos que analizar con más detalle el esquema de ejecución anterior, para 
conocer los recursos que se necesitan para poder ejecutar de esa manera las 
instrucciones vectoriales. 
1.1.1 Algunos problemas 
1.1.1.1 La memoria de un computador vectorial 
Un procesador vectorial utiliza la memoria de modo intensivo. Por 
ejemplo, en el caso anterior tenemos 3 instrucciones, 2 LV y 1 SV, que están 
utilizando simultáneamente la memoria y, además, cada instrucción realiza N 
accesos a memoria. Por tanto, hay que solucionar dos aspectos: 
 
3 Las responsables de las dependencias de control son las instrucciones de salto. En general, después 
de la instrucción de dirección i se ejecuta la instrucción de dirección i+1, salvo en el caso de los 
saltos. Cuando ejecutamos un salto no sabemos qué instrucción será la siguiente hasta que el salto 
termine, por lo que hay que parar al procesador (aunque existen muchas técnicas para evitar esos 
ciclos "muertos"). 
1.1 ¿QUÉ ES UN COMPUTADOR VECTORIAL? ▪ 11 ▪ 
1. ¿Cuántos buses hay para acceder a memoria? El procesador y el 
sistema de memoria se comunican mediante el bus de datos. Una 
operación vectorial de memoria va a ocupar el bus de datos durante N 
ciclos (supongamos que se transfiere una palabra por ciclo). Por tanto, 
si sólo hubiera un bus, sólo una instrucción podría acceder a memoria 
en cada momento, y todas las demás deberían esperar a que ésta 
terminara. Por consiguiente, el tiempo de ejecución no sería de orden 
N, sino de kN (con k = 2, 3, 4..., número de instrucciones de memoria). 
 
2. ¿No habrá conflictos en el uso de los módulos de memoria? A pesar 
de que el espacio de memoria esté entrelazado entre los diferentes 
módulos de memoria, puede suceder que en un momento determinado 
se necesite acceder a elementos de vectores almacenados en el mismo 
módulo. Si sucede esto, para poder comenzar un acceso habrá que 
esperar a que termine el anterior acceso al mismo módulo, con lo que 
aumentará el tiempo de ejecución. 
 
Queda claro que el sistema de memoria de un computador vectorial juega 
un papel muy importante en el rendimiento final del sistema: hacen falta 
múltiples buses, y la memoria debe estar entrelazada en muchos módulos, 
para reducir los conflictos de acceso a los mismos. 
1.1.1.2 Unidades funcionales vectoriales 
Analizando el esquema de ejecución anterior, queda claro que las 
unidades funcionales deben estar segmentadas. Una única instrucción 
(ADDV, por ejemplo) realiza N operaciones en la unidad funcional, una por 
ciclo. Si no estuviera segmentada, no sería posible generar un dato por ciclo. 
De la misma manera, parece necesario poder disponer de varias unidades 
funcionales de cada tipo, ya que una instrucción ocupa cada unidad 
funcional durante N ciclos. 
1.1.1.3 Registros vectoriales 
¿Qué es un registro vectorial? ¿De qué tamaño son? ¿Cómo se leen y se 
escriben? En un registro vectorial se guardan los elementos de un vector. 
Cada elemento, normalmente, será un escalar representado en coma flotante, 
por ejemplo en 64 bits. Por tanto, en un registro tendremos 64 × N bits. El 
tamaño de los registros es, en todo caso, limitado. Es habitual que un registro 
vectorial permita almacenar 64 o 128 (Lmax) elementos de un vector, con lo 
▪ 12 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
que su capacidad sería de 64 (o 128) × 64 = 4 (u 8) kilobits. Si nos fijamos 
en el tamaño, se comprende fácilmente que no se disponga de un número 
muy elevado de registros vectoriales. Normalmente dispondremos de 8-16 
registros (16 × 8 = 128 kilobits). En algunas máquinas, el tamaño de los 
registros es variable; es decir, el "espacio de memoria" de que se dispone se 
puede utilizar para definir muchos registros de pocos elementos o unos 
pocos de muchos elementos. 
 
 
 
 
 
¿Qué se debe hacer cuando la longitud de los vectores que tenemos que 
procesar es mayor que Lmax (64 o 128 elementos)? No hay más remedio que 
formar un bucle, y en cada iteración del mismo procesar Lmax elementos 
(strip mining). Por tanto, aparecen de nuevo las dependencias de control, 
aunque esta vez cada 64 (128) elementos. 
En los primeros computadores vectoriales los registros se trataban como 
una “unidad”, por lo que no era posible leer y escribir sobre el mismo 
registro a la vez. Hoy en día, los elementos que conforman un registro 
vectorial se tratan como unidades independientes que pueden direccionarse 
de manera separada, con lo que es posible acceder a los primeros elementos 
de un vector ya almacenados en un registro mientras se sigue escribiendo el 
resto de elementos. Por otro lado, dado que diferentes instrucciones irán 
produciendo datos para escribir en el banco de registros vectoriales, y que 
cada una de ellas necesitará muchos ciclos para escribir el vector resultado, 
serán necesarios varios (muchos) buses de escritura (evidentemente, también 
se necesitan “muchos” buses de lectura). Con todo ello, el banco de registros 
de un procesador vectorial resulta ser un dispositivo complejo. 
1.1.1.4 Programas vectoriales 
¿Qué tipo de programas se pueden ejecutar en un computador vectorial? 
Los procesadores vectoriales están optimizados para procesar vectores, pero 
en los programas reales, además de procesar vectores, habrá que procesar 
código escalar.¿Cómo se hace eso? ¿Qué influencia tiene en la velocidad de 
cálculo? (como veremos, el efecto del código escalar puede ser muy grande). 
registros vectoriales U.F. 
1.1 ¿QUÉ ES UN COMPUTADOR VECTORIAL? ▪ 13 ▪ 
Analicemos de nuevo qué se hace cuando se procesan vectores. Veamos el 
siguiente ejemplo: 
 
do i = 0, N-1 
 A(i) = A(i) + 1 
enddo 
 
Si se ejecutara escalarmente, y simplificando, el orden de ejecución de las 
diferentes operaciones sería el siguiente (L = load; S = store; + = suma; i = 
elemento del vector): 
 
L0 +0 S0 / L1 +1 S1 / L2 +2 S2 / L3 +3 S3 / ... / LN–1 +N–1 SN–1 
 
Si lo ejecutáramos vectorialmente (LV - ADDV - SV), el orden pasaría a 
ser el siguiente: 
 
L0 L1 L2 ... LN–1 / +0 +1 +2 ... +N–1 / S0 S1 S2 ... SN–1 
 
Esto es, la ejecución vectorial implica desordenar el código original. Y 
como ya sabemos, esto no siempre es posible, ya que hay que respetar las 
dependencias de datos entre las instrucciones. Por tanto, para decidir si un 
programa se puede ejecutar vectorialmente o no, hay que hacer un 
meticuloso análisis de las dependencias, tarea que, como veremos, va a 
recaer, en gran medida, en un buen compilador vectorial. 
Resumiendo todo lo anterior: aunque hemos definido un modelo de 
computador con un rendimiento teórico muy elevado, en la realidad tenemos 
que superar muchos problemas para poder llegar a esa velocidad de cálculo. 
1.1.2 Arquitectura y lenguaje máquina 
Existen diferentes arquitecturas para los computadores vectoriales, casi 
tantas como fabricantes. En los primeros diseños, los computadores 
vectoriales no tenían registros, y todas las operaciones se hacían con los 
operandos en memoria. A este modelo se le denomina "Memoria-Memoria" 
(M/M). Pero pronto se añadieron los registros vectoriales; como 
consecuencia, los operandos de las operaciones vectoriales se obtienen de 
registros y los resultados se dejan en registros (modelo R/R). 
En la siguiente figura se muestra un esquema lógico, muy simple, de un 
computador vectorial. Podemos distinguir dos secciones: la sección escalar y 
la vectorial. El procesador escalar se encarga de la búsqueda y 
descodificación de las instrucciones. Si la instrucción es escalar, la ejecuta él 
▪ 14 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
mismo, utilizando los registros escalares necesarios; pero si es vectorial, 
pasa el control al procesador vectorial para que la ejecute. Salvo que 
especifiquemos alguna otra opción, vamos a suponer que la unidad de 
control es de tipo Tomasulo (desorden/desorden). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Tal y como hemos comentado, aunque vamos a trabajar con vectores, en 
la realidad tendremos una mezcla de código vectorial y escalar. Por tanto, 
tendremos que utilizar tanto instrucciones vectoriales como escalares. Las 
instrucciones escalares son las habituales en cualquier procesador RISC. En 
función del computador, existen diferentes juegos de instrucciones 
vectoriales y de formatos de instrucciones; las más habituales son las 
siguientes (más tarde veremos algunas otras): 
 
OPV Vi,Vj,Vk Vi = Vj OP Vk 
 (OP = ADD, SUB, MUL, DIV...) 
 Operación entre dos vectores. El resultado es otro 
vector. 
 
OPVS Vi,Vj,Fk Vi = Vj OP Fk 
OPVI Vi,Vj,#inm Vi = Vj OP #inm 
 (OP = ADD, SUB, MUL, DIV...) 
 Operación entre un vector y un escalar. El 
resultado es un vector. 
 
 
Registros 
 
 
Unidades 
funcionales 
Procesador 
escalar 
(completo) 
Control del 
procesador 
vectorial 
Unidad de 
direcciones 
(datos) 
M
em
o
ri
a 
(op.) 
1.2 DEPENDENCIAS DE DATOS ▪ 15 ▪ 
LV Vi,A(Rj) Se lee a partir de la dirección de memoria A+Rj 
un vector, y se deja en el registro Vi (puede 
haber más modos de direccionamiento). 
 
SV A(Rj),Vi Similar a la anterior, pero, en lugar de leer, 
escribe un vector en memoria. 
 
Para identificar un vector en memoria, hay que dar tres parámetros: 
dirección de comienzo, longitud y paso. La dirección de comienzo se indica 
en la propia instrucción LV/SV (de acuerdo al modo de direccionamiento que 
se utilice). La longitud del vector y el paso, en cambio, hay que indicarlos 
previamente a la operación de lectura o escritura. Para ello utilizaremos dos 
registros especiales: VL (vector length), para indicar el número de elementos 
del vector, su longitud, y VS (vector stride), para indicar el paso. Si el 
contenido de VL es mayor que Lmax (tamaño de los registros vectoriales), 
sólo se procesarán Lmax elementos. 
Así pues, tenemos que ejecutar las siguientes instrucciones para, por 
ejemplo, leer un vector: 
 
 MOVI VL,#64 ; los vectores son de 64 elementos 
 MOVI VS,#8 ; el paso es 8 
 LV V1,A(R1) 
 
De esta manera se cargarán en el registro V1 64 elementos de un vector, 
correspondientes a las direcciones A+R1, A+R1+8, A+R1+16… 
En algunos computadores es necesario indicar explícitamente el paso de 
los vectores en la propia instrucción, utilizando para ello un registro de 
propósito general. 
 
1.2 DEPENDENCIAS DE DATOS 
Al igual que sucede con los procesadores (super)escalares, la velocidad de 
cálculo de los procesadores vectoriales está limitada por las dependencias de 
datos. Una instrucción depende de otra anterior si uno de sus operandos es el 
resultado de dicha instrucción, por lo que deberá esperar a que finalice antes 
de poder ejecutarse. Ya sabemos que, en los procesadores escalares, para 
▪ 16 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
atenuar la pérdida de rendimiento debida a las dependencias de datos se 
utilizan cortocircuitos (forwarding) entre las unidades funcionales; una idea 
similar se aplica también en los procesadores vectoriales. 
Para los siguientes ejemplos utilizaremos el siguiente esquema de 
segmentación (Tomasulo): 
 
 LV/SV → BD L AM M M M E 
 ADDV → BD L A A E 
1.2.1 Encadenamiento (chaining) 
Se dice que dos instrucciones se encadenan si la segunda utiliza el vector 
generado por la primera sin esperar a que ésta lo haya guardado en el 
registro vectorial. Veamos un ejemplo sencillo: 
 
do i = 0, N-1 LV V1,A(R1) 
 A(i) = A(i) + 1 → ADDVI V2,V1,#1 
enddo SV A(R1),V2 
 
El bucle presenta dependencias de datos muy claras: LV → ADDVI (V1) y 
ADDVI → SV (V2). Entonces ¿cómo se ejecutará ese programa? Tenemos 
dos alternativas: sin realizar encadenamiento entre las dos instrucciones, o 
encadenándolas. 
 
a. Si no se realiza encadenamiento, la segunda instrucción deberá esperar 
a que termine la primera, para poder leer el registro vectorial 
correspondiente (V1). En la figura se muestra un esquema de 
ejecución, en el que se puede ver cuándo se realizan las lecturas (L). 
 
LV V1,A(R1) BD L AM M M M E ... E 
ADDVI V2,V1,#1 BD . . . . . ... . L A A E ... E 
SV A(R1),V2 BD L AM . . ... . . . . . ... . L M M M E ... 
ciclos ← 6 → ← N → ← 3 → ← N → ← 4 → ← N 
 
 Por tanto, el tiempo de ejecución en este caso es TV = 13 + 3N ciclos. 
 
b. En cambio, si se realiza encadenamiento, según se van generando los 
vectores se van utilizando en la siguiente unidad funcional; es decir, se 
utiliza el cortocircuito E → L. 
1.2 DEPENDENCIAS DE DATOS ▪ 17 ▪ 
LV V1,A(R1) BD L AM M M M E E ... (N cicl.) ... 
ADDVI V2,V1,#1 BD . . . . L A A E E ... (N cicl.) ... 
SV A(R1),V2 BD L AM . . . . L M M M E ... ... E 
ciclos ← 6 → ← 3 → ← 4 → ← N → 
 
 En este segundo caso, el tiempo de ejecución es TV = 13 + N ciclos. 
 
Podemos analizar el mismo comportamiento de manera cualitativa. Por 
ejemplo, la siguiente figura muestra un esquema de ejecución muy 
simplificado del programa anterior (LV / ADDVI / SV), en función de si se 
encadenan o no las instrucciones: 
 
 
 
 
 sin encadenamiento: T ~ 3N con encadenamiento: T ~ N 
 
La diferencia entre ambas opciones es clara. En el primer caso, el tiempo 
de ejecución es del orden de 3N; en el segundo, en cambio, es deorden N. 
Por ejemplo, para N = 64 el tiempo de ejecución bajaría de 13 + 3×64 = 205 
ciclos a 13 + 64 = 77 ciclos (un 38%). Así pues, necesitamos poder 
encadenar las instrucciones para conseguir un buen rendimiento. 
 
1.2.1.1 Encadenamiento con dos instrucciones 
En el ejemplo del apartado anterior, el encadenamiento se ha realizado 
con una única instrucción anterior: la instrucción ADDVI con la instrucción 
LV, o la instrucción SV con la instrucción ADDVI. En un caso más general, 
tendríamos que poder encadenar una instrucción con dos instrucciones 
anteriores. Veamos un ejemplo (C = A + B): 
 
LV V1,A(R1) BD L AM M M M E E ... (N ciclos) ... 
LV V2,B(R1) BD L AM M M M E E ... (N ciclos) ... 
ADDV V3,V1,V2 BD . . . . L A A E E ... (N ciclos) ... 
SV C(R1),V3 BD L AM . . . L M M M E ... ... E 
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14+N 
LV 
ADDVI 
SV 
ADDVI 
SV 
LV 
▪ 18 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
La tercera instrucción (ADDV) necesita los vectores V1 y V2, que son 
generados por las dos primeras instrucciones respectivamente. Pero estos dos 
vectores no se generan sincronizados: el primero se comienza a generar en el 
ciclo 7 y el segundo en el 8 (y a partir de ahí el resto de elementos). Por 
tanto, en el ciclo 7 no está preparado el primer elemento del segundo 
operando (V2), y en el ciclo 8 se pierde la posibilidad de tomar el primer 
elemento del primer operando (V1) (los datos no se “pierden”, claro ya que 
se están cargando en el registro vectorial). ¿Qué se puede hacer? 
Para poder efectuar el encadenamiento hay que coger un operando según 
sale de la unidad funcional y leer el otro del registro correspondiente (V1), 
donde ya se está escribiendo. Para ello es necesario que el banco de registros 
permita la lectura y escritura simultánea del mismo registro (lo habitual en 
las máquinas vectoriales actuales, y que se conoce como flexible chaining o 
encadenamiento flexible); si eso no es posible, se perderá la posibilidad de 
encadenar (salvo que se aplique alguna otra solución) y habrá que esperar a 
que finalice la escritura de ambos operandos. 
1.2.2 Tablas de ejecución de las instrucciones 
Representar los esquemas de ejecución de un conjunto de instrucciones 
vectoriales fase a fase es un poco pesado. Por ello, en lugar de hacer ese tipo 
de esquemas, vamos a resumir en una tabla las acciones principales que 
suceden cuando se ejecutan las instrucciones: 
 
• Inicio de ejecución: cuántos ciclos han pasado, desde el comienzo, 
hasta el momento previo a iniciar la operación en la UF. El inicio 
puede ser tras la lectura de los registros, o mediante encadenamiento, 
en cuyo caso indicaremos el número de ciclos entre [ ]. 
 (La ejecución de instrucciones es segmentada, y las instrucciones se ejecutan de una 
en una, no es superescalar.) 
• Latencia de la unidad funcional. 
• Ciclo en el que se genera el primer elemento. 
• Ciclo en el que se genera el último (N) elemento. 
 
Por ejemplo, para una instrucción LV la tabla correspondiente sería: 
 
BD L AM M M M E ... ... E 
comienzo (3) lat. UF (3) dato 1 (6+1) dato N (6+N) 
1.2 DEPENDENCIAS DE DATOS ▪ 19 ▪ 
Las ejecuciones de los dos ejemplos anteriores se pueden resumir así: 
 
 sin encadenamiento con encadenamiento 
A = A + 1 inic. lat. UF dato 1 dato N inic. lat. UF dato 1 dato N 
LV V1,A(R1) 3 3 6+1 6+N 3 3 6+1 6+N 
ADDVI V2,V1,#1 6+N+1 2 9+N+1 9+2N [7] 2 9+1 9+N 
SV A(R1),V2 9+2N+1 3 13+2N+1 13+3N [10] 3 13+1 13+N 
 
Si la ejecución de las instrucciones no se encadena, la instrucción ADDVI 
tiene que esperar a que termine la escritura en el registro V1 (ciclo 6+N) y 
luego leer del registro (+1). Lo mismo le sucede a la instrucción SV: tiene 
que esperar a que la instrucción ADDVI termine (9+2N), y entonces leer V2 
y escribir en memoria. 
Si la ejecución de las instrucciones se encadena, la suma puede comenzar 
en el ciclo 7 (en ese ciclo llega de memoria el primer elemento del vector), y 
la escritura en memoria puede comenzar en el ciclo 10 (ciclo en que la suma 
genera el primer dato). 
 
En el segundo ejemplo podemos observar el mismo comportamiento. Si 
no se puede encadenar, la instrucción ADDV tiene que esperar a tener listos 
ambos operandos (ciclo 7+N) y entonces leerlos. Cuando se encadena, uno 
de los operandos (V2) se obtiene directamente de la memoria y el otro (V1) 
del registro (donde se ha escrito en el ciclo anterior); el ciclo de 
encadenamiento es, por tanto, el ciclo 8. 
 
 sin encadenamiento con encadenamiento 
C = A + B inic. lat. UF dato 1 dato N inic. lat. UF dato 1 dato N 
LV V1,A(R1) 3 3 6+1 6+N 3 3 6+1 6+N 
LV V2,B(R1) 4 3 7+1 7+N 4 3 7+1 7+N 
ADDV V3,V1,V2 7+N+1 2 10+N+1 10+2N [8] 2 10+1 10+N 
SV C(R1),V3 10+2N+1 3 14+2N+1 14+3N [11] 3 14+1 14+N 
 
Nota: estamos aplicando un modelo “didáctico” de ejecución vectorial, y el objetivo 
es mostrar el comportamiento general, no los detalles particulares. Lo computadores 
comerciales utilizan estrategias similares, aunque los detalles de implementación 
pueden variar. 
▪ 20 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
1.3 DEPENDENCIAS ESTRUCTURALES 
Después de analizar las dependencias de datos, analicemos las 
dependencias estructurales. Recuerda que un conflicto o dependencia 
estructural surge cuando se quiere utilizar un recurso mientras está ocupado 
por otra instrucción. Además de las unidades funcionales, el recurso más 
importante en un computador vectorial es la memoria. Para poder utilizar la 
memoria, primeramente hay que disponer de un bus libre. ¿Cuántos buses 
tenemos para acceder a la memoria? Por otro lado, se utilizan los propios 
módulos de memoria. ¿Están libres los módulos que hay que utilizar? Si 
están ocupados, ¿cuánto tiempo hay que esperar? 
1.3.1 Buses de memoria (unidades funcionales LV/SV) 
La ejecución de las instrucciones LV y SV implica una transferencia con 
memoria en la que se utilizan los buses. Cuando se ejecuta una instrucción 
LV o SV, el bus se ocupa durante N ciclos; mientras una instrucción está 
utilizando el bus, la siguiente deberá esperar hasta que se libere el bus. Por 
tanto, si el computador no tuviera un número suficiente de buses, la 
velocidad de cálculo de la máquina no sería muy alta. 
Analicemos la influencia del número de buses mediante el ejemplo 
anterior (A = A + 1; LV / ADDVI / SV). Supongamos que la máquina puede 
encadenar las instrucciones, pero que sólo posee un bus para trabajar con 
memoria (LV o SV)4. En estas condiciones, cuando la instrucción SV quiere 
empezar a escribir en memoria, en el ciclo de encadenamiento, el bus no está 
disponible, ya que lo ocupa la instrucción LV (y lo mantendrá ocupado 
muchos ciclos). Por tanto, deberá esperar hasta que termine la primera 
instrucción (y se libere el bus) y leer entonces el registro en el que se están 
escribiendo los resultados (V2)5. 
Este sería el esquema de ejecución: 
 
 
 
4 Los buses de memoria pueden usarse tanto para una lectura como para una escritura; en algunas 
máquinas, en cambio, los buses están "dedicados": unos son sólo para leer y otros sólo para escribir. 
5 Si no puede leerse un registro mientras se está escribiendo, entonces habrá que esperar a que finalice 
la escritura. 
1.3 DEPENDENCIAS ESTRUCTURALES ▪ 21 ▪ 
LV V1,A(R1) BD L AM M M M E E ... (N ciclos) ... E 
ADDVI V2,V1,#1 BD . . . . L A A E E ... (N ciclos) ... E 
SV A(R1),V2 BD L AM . . . . ? . ... ... L M M M E ... (N cicl.) 
 bus ocupado... libre 
 
o, esquemáticamente: 
 
 
 
 
La tabla correspondiente a la ejecución sería la siguiente: 
 
 un bus / encadenamiento 
A = A + 1 inic. lat. UF dato 1 dato N 
LV V1,A(R1) 3 3 6+1 6+N 
ADDVI V2,V1,#1 [7] 2 9+1 9+N 
SV A(R1),V2 [6+N] 3 9+N+1 9+2N 
 
Repitamos el análisis, pero con el segundo ejemplo que hemos visto antes. 
En ambos casos, las instrucciones se encadenan, pero en el primer caso la 
máquinacuenta con un solo bus de memoria, y en el otro caso cuenta con 
dos buses. 
 
 un bus / encadenamiento dos buses / encadenamiento 
C = A + B inic. lat. UF dato 1 dato N inic. lat. UF dato 1 dato N 
LV V1,A(R1) 3 3 6+1 6+N 3 3 6+1 6+N 
LV V2,B(R1) 6+N 3 9+N+1 9+2N 4 3 7+1 7+N 
ADDV V3,V1,V2 [10+N] 2 12+N+1 12+2N [8] 2 10+1 10+N 
SV C(R1),V3 [9+2N] 3 12+2N+1 12+3N [6+N] 3 9+N+1 9+2N 
 
Cuando sólo hay un bus, la segunda instrucción LV no puede utilizar la 
memoria hasta que el primer LV la deje de utilizar, y lo mismo le sucede a la 
instrucción SV (para cuando se libera el bus, la escritura en el registro V3 
está terminando). Por tanto, el tiempo de ejecución es de orden 3N. Si la 
ADDVI 
SV 
LV 
T ~ 2N 
▪ 22 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
máquina tiene dos buses, las instrucciones LV se ejecutarán a la vez, pero la 
instrucción SV tendrá que esperar. 
Esquemáticamente: 
 
 
 
 
 un bus / encadenamiento: 3N dos buses / encadenamiento: 2N 
 
La conclusión es sencilla: si no existen suficientes recursos (buses) para 
poder ejecutar las instrucciones de memoria, a pesar de tener la posibilidad 
de encadenar las instrucciones el tiempo de ejecución será elevado. 
 
En resumen, los resultados que hemos obtenido con ambos ejemplos son 
los siguientes: 
 
1. A = A + 1 (N = 64) 
sin encadenamiento 13 + 3N = 205 ciclos → 3,20 ciclos/dato 
encadenamiento / 1 bus 9 + 2N = 137 ciclos → 2,14 c/d 
encadenamiento / 2+ buses 13 + N = 77 ciclos → 1,20 c/d 
 
2. C = A + B (N = 64) 
sin encadenamiento / 1 bus 16 + 4N = 272 ciclos → 4,25 c/d 
sin encadenamiento / 3 buses 14 + 3N = 206 ciclos → 3,22 c/d 
encadenamiento / 1 bus 12 + 3N = 204 ciclos → 3,19 c/d 
encadenamiento / 2 buses 9 + 2N = 137 ciclos → 2,14 c/d 
encadenamiento / 3 buses 14 + N = 78 ciclos → 1,22 c/d 
 
Los datos muestran claramente la importancia de disponer de suficientes 
buses a memoria y de que las instrucciones puedan encadenarse para que las 
instrucciones se ejecuten eficientemente. 
1.3.2 Conflictos en el uso de los módulos de memoria 
1.3.2.1 Una sola operación de memoria 
Tras haber analizado el problema de los buses en un procesador vectorial, 
analicemos ahora el uso de la propia memoria. La memoria de cualquier 
computador está entrelazada en varios módulos; así, las direcciones i e i+1 
LV 
LV 
SV 
ADDV 
LV 
LV 
SV 
ADDV 
1.3 DEPENDENCIAS ESTRUCTURALES ▪ 23 ▪ 
no corresponden al mismo módulo de memoria, sino a módulos 
consecutivos. De esta manera es posible, por ejemplo, efectuar una 
operación simultánea en dos (en general nm, el número de módulos) 
direcciones consecutivas; si estuvieran en el mismo módulo tendríamos que 
esperar a que finalizara una operación antes de empezar con la siguiente. 
Cuando se ejecuta una instrucción LV o SV se efectúan N lecturas o 
escrituras en memoria, una por ciclo. Para que se haga de manera eficiente, 
es necesario que se acceda a módulos que estén libres; si no, tendríamos un 
conflicto estructural, y no lograríamos efectuar una operación por ciclo. 
Veamos el problema con un ejemplo. Hay que leer el vector A(A0:A15); la 
memoria está entrelazada en 4 módulos, y el vector se encuentra en módulos 
consecutivos (s = 1) a partir de m0. La latencia de la memoria es de 3 ciclos. 
La situación de la memoria según se lee el vector A es la siguiente: 
 
m0 m1 m2 m3 
A0 A1 A2 A3 
A4 A5 A6 A7 
A8 A9 A10 A11 
A12 A13 ... 
 
→ tiempo (ciclos) 
m0 M M M M M M ... 
m1 M M M M M M ... 
m2 M M M M M M 
m3 M M M M M M 
 
La lectura comienza en m0, y sigue en m1, m2, m3, y se vuelve a m0, 
para seguir leyendo más elementos del vector. En ese momento, m0 está 
libre, puesto que ya ha terminado el primer acceso, y por tanto no tendremos 
ningún problema. 
Pero si, por ejemplo, la latencia de la memoria fuera de 8 ciclos, al ir a 
utilizar nuevamente m0 lo encontraríamos ocupado, ejecutando todavía la 
operación anterior. Tendríamos, por tanto, que esperar a que finalizara antes 
de poder seguir leyendo el vector. Como consecuencia del conflicto 
estructural, el tiempo de ejecución de la operación sería más alto. 
El problema puede ser grave, en función de la definición del vector. Por 
ejemplo, si el paso del vector del ejemplo anterior fuera s = 4, entonces todos 
los elementos del vector estarían en el mismo módulo, m0: todos los accesos 
significarían un conflicto, ya que cada acceso dura 3 ciclos. 
▪ 24 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
Para analizar si surgirán o no conflictos en memoria, hay que considerar 
tres parámetros: el tiempo de acceso o latencia de la memoria —tm—, el 
número de módulos en que está entrelazada la memoria —nm—, y el paso 
de los vectores —s—. Dos de esos parámetros, latencia y número de 
módulos, son decisiones de diseño: se deciden al construir la máquina y no 
son modificables por el usuario. El tercero, en cambio, el paso de los 
vectores, corresponde al programa concreto que se ejecuta, y puede 
modificarse para intentar evitar conflictos. 
Cuando s = 1, se utilizan todos los módulos de memoria al acceder a un 
vector (m0-m1-m2-...). Por tanto, para que no haya conflictos se debe 
cumplir que: 
 
mtnm ≥ 
De esa manera, cuando hay que reutilizar un determinado módulo ya han 
pasado al menos nm ciclos, y por tanto estará libre. 
Para el caso general, s > 1, hay que calcular cuántos módulos se utilizan 
en una determinada operación. Por ejemplo, en el caso anterior, cuando s = 
4, sólo se utiliza un módulo de memoria, siempre el mismo (m0). Puede 
demostrarse fácilmente que el número de módulos que se utilizan en una 
operación de memoria es: 
),( snmMCD
nm
 (MCD = máximo común divisor) 
Así pues, y generalizado el resultado anterior, no habrá conflictos en 
memoria si el número de módulos que se van a utilizar es mayor o igual que 
la latencia: 
mtsnmMCD
nm
≥
),( 
 
Analizando la expresión anterior. se observa que la mejor situación se 
corresponde con el caso MCD(nm,s) = 1, es decir cuando, nm y s son primos 
entre sí, ya que se utilizan todos los módulos de memoria. En los casos más 
habituales, nm es una potencia de 2 (8, 16, 32, 64...). En esos casos, y si no 
hay conflicto cuando s = 1, no habrá conflictos para cualquier vector de paso 
impar (1, 3, 5...), pero podría haberlos para los casos de s par. 
Existe una situación óptima. Si el número de módulos de memoria, nm, es 
un número primo, entonces cualquier paso s será primo con él (salvo sus 
múltiplos). Por ejemplo, si nm = 5, no hay problemas con los vectores de 
1.3 DEPENDENCIAS ESTRUCTURALES ▪ 25 ▪ 
paso s = 1, 2, 3, 4, 6, 7, 8... Por desgracia, cuando la memoria se entrelaza en 
un número primo de módulos, 17 por ejemplo, calcular el módulo y la 
dirección dentro del módulo que corresponden a una palabra dada es una 
operación “compleja” (operación que debe realizar el controlador de 
memoria, para efectuar cualquier acceso a memoria), ya que habrá que 
efectuar una división para obtener el cociente y el resto (cuando nm = 2i, los 
i bits de menos peso indican el módulo, y el resto la dirección dentro del 
módulo). Debido a esa división, no se suele entrelazar la memoria en un 
número primo de módulos. 
El valor de s es muy variable en los programas vectoriales. Por ejemplo, al 
procesar matrices pueden definirse diferentes tipos de vectores: filas, 
columnas, diagonales... Para multiplicar dos matrices, por ejemplo, hay que 
usar filas en una y columnas en la otra. En algunos casos, para optimizar el 
acceso a memoria, las matrices no se guardan en posiciones consecutivas de 
memoria, sino que se dejan huecos sin ocupar (padding). 
Veamos un ejemplo de la utilidad de esta estrategia. Sea una memoria 
entrelazada en 4 módulos y una matriz de tamaño 4×4, de la que se van a 
utilizar las filas y las columnas. Como puede verse, no hay problemas en el 
acceso a una fila (s = 1), ya que los elementos están en módulos de memoria 
diferentes, pero el acceso a cualquier columna es muy conflictivo,ya que 
todos los elementos están en el mismo módulo de memoria. Sin embargo, si 
se dejan huecos en memoria entre los elementos de la matriz (en la tabla se 
muestra un ejemplo), entonces es posible acceder tanto a filas (s = 1) como a 
columnas (ahora s = 5) sin conflictos (aunque se generen conflictos en el 
acceso a las diagonales6). 
 
m0 m1 m2 m3 m0 m1 m2 m3 
A00 A01 A02 A03 A00 A01 A02 A03 
A10 A11 A12 A13 → - A10 A11 A12 
A20 A21 A22 A23 A13 - A20 A21 
A30 A31 A32 A33 A22 A23 - A30 
 A31 A32 A33 - 
 
sf = 1 sin conflictos sf = 1 sin conflictos 
sc = 4 conflictos (todos en m0) sc = 5 sin conflictos 
sD = 5 sin conflictos sD = 6 conflictos 
sd = 3 sin conflictos sd = 4 conflictos 
 
6 Como hemos comentado, el ideal sería que nm fuera un número primo. Por ejemplo, si nm fuera 5, 
los cuatro vectores del ejemplo (f, c, D y d) podrían accederse sin problemas si se dejan los 
correspondientes huecos (lo dejamos como ejercicio para el lector). 
▪ 26 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
1.3.2.2 Varias operaciones de memoria 
Como acabamos de ver, la ejecución de una instrucción vectorial de 
memoria, LV o SV, puede producir problemas en el acceso a los módulos de 
memoria. Lo mismo ocurre cuando se están ejecutando más de una 
instrucción de memoria. Aunque cada una de ellas no tuviera conflictos 
consigo misma, es posible que existan colisiones entre ellas; es decir, que 
una segunda instrucción quisiera utilizar un módulo de memoria ocupado en 
ese instante por otra instrucción. 
Analicemos el problema mediante un ejemplo. Supongamos que la 
memoria está entrelazada en 8 módulos y que la latencia es 3 ciclos (con el 
mismo esquema de segmentación de los ejemplos anteriores). Hay 
suficientes buses a memoria y las instrucciones pueden encadenarse. El 
primer elemento de A esta en el módulo m0 y el paso es s = 1. 
 
 2 buses / encadenamiento 
A = A + 1 inic. lat. UF dato 1 dato N 
LV V1,A(R1) 3 3 6+1 6+N 
ADDVI V2,V1,#1 [7] 2 9+1 9+N 
SV A(R1),V2 [10] 
 
Como hemos visto antes, la instrucción SV puede encadenarse en el ciclo 
10, e ir a memoria. Pero, ¿cómo se encuentran en ese momento los módulos 
de memoria, libres u ocupados? El esquema siguiente muestra el uso de los 
módulos de memoria ciclo a ciclo. La instrucción LV comienza la lectura en 
el ciclo 4, en el módulo m0, por ejemplo. Supongamos, por simplificar el 
problema, que el paso de A es 1. Por tanto, tras el módulo m0 se accederá a 
m1, m2..., m7, y nuevamente a m0, m1... Dado que la latencia es 3 ciclos, la 
instrucción no tiene ningún conflicto consigo misma (nm ≥ tm). 
 
 t (ciclos) 
mem. 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
m0 M M M - M M M m m m 
m1 M M M - - M M M m m m 
m2 M M M M M M 
m3 M M M M M M 
m4 M M M M M M 
m5 M M M M M M 
m6 M M M M M 
m7 M M M M 
1.3 DEPENDENCIAS ESTRUCTURALES ▪ 27 ▪ 
La instrucción SV puede encadenarse en el ciclo 10, para empezar en 
memoria en el ciclo 11, en el módulo m0 (hay que guardar el mismo vector, 
A). ¿Cómo se encuentra en ese momento ese módulo? La instrucción LV está 
en ejecución, y mantiene ocupados varios módulos. Primeramente debemos 
calcular qué módulo va a acceder LV en ese ciclo, para lo que basta con 
saber cuántos ciclos lleva ya en memoria y de qué módulo partió. En este 
ejemplo, la distancia en ciclos es de 10 – 3 = 7, y dado que partió del módulo 
m0 (y que s = 1), en el ciclo 11 irá a utilizar el módulo m7. Ese módulo, por 
tanto, no estará disponible. 
Pero habrá más módulos ocupados, ya que todavía estarán ejecutándose 
accesos que comenzaron en ciclos anteriores. Si la latencia de la memoria es 
tm, se mantiene ocupados tm–1 módulos anteriores. En el ejemplo tm = 3, 
por lo que tendremos dos módulos ocupados, m6 y m5. Utilizando el mismo 
razonamiento, es necesario dejar libres por delante otros tm–1 módulos, para 
que la instrucción LV pueda seguir ejecutándose sin interferencias; en el 
ejemplo, los módulos m0 y m1 (si no, LV “chocaría” con SV en el siguiente 
ciclo). 
Así pues, en este ejemplo en el ciclo 11 están ocupados o reservados los 
módulos <m5 – m6 – m7 – m0 – m1>. Si alguna instrucción quiere utilizar 
esos módulos, deberá esperar a que se liberen. Ése es el caso de la 
instrucción SV, que tiene que utilizar m0, y que tendrá que esperar. 
¿Cuántos ciclos? Tantos como la posición que ocupa el módulo a utilizar en 
la lista de módulos ocupados. En el ejemplo, 4 ciclos. En el ciclo 11 están 
ocupados los módulos m5-...-m1; en el siguiente ciclo, por tanto, los 
módulos m6-...-m2; en el siguiente, m7-...-m3, y, en el siguiente, m0-...-m4. 
Finalmente, en el siguiente ciclo se liberará m0, que podrá ser utilizado por 
la instrucción SV para comenzar la escritura del vector A. 
En resumen, para analizar los conflictos en memoria entre las 
instrucciones j y k, el procedimiento es el siguiente (todas las operaciones son 
módulo nm, siendo nm el número de módulos de memoria): 
 
a. Se calcula qué módulo va a comenzar a utilizar la instrucción j cuando 
la instrucción k quiere acceder a memoria: 
 
 (inik – inij) + módulo_inij (ini = ciclo inicio en memoria) 
 
b. Se crea la lista de módulos ocupados, añadiendo tm–1 módulos por 
delante y por detrás al módulo anterior (tm, latencia de la memoria). 
 
 < tm–1 módulos | (inik – inij) + módulo_inij | tm–1 módulos> 
▪ 28 ▪ Capítulo 1: COMPUTADORES VECTORIALES 
c. Si el primer módulo de memoria que va a utilizar la instrucción k está 
ocupado, se calcula el tiempo de espera, que habrá que añadir al 
tiempo de inicio de la instrucción (antes de la UF). 
 
El procedimiento anterior se puede generalizar para el caso de acceso a vectores con 
paso s, siempre que los pasos de las instrucciones que están accediendo a memoria 
sean iguales. En este caso, dado que en cada paso se avanzan s módulos, por un 
lado, habrá que hacer (inik – inij) × s + módulo_inij y luego habrá que contar tm–1 
módulos de s en s. En caso de que no coincida el paso de todas las instrucciones a 
memoria el análisis es más complejo y, normalmente, en función de la máquina, no 
se comenzará a ejecutar la segunda instrucción hasta que haya terminado la primera. 
 
Repitamos el ejercicio anterior, pero teniendo en cuenta los conflictos en 
memoria. Tal y como se muestra en la tabla, la instrucción SV quiere realizar 
un encadenamiento en el ciclo 10. Dado que la instrucción LV está aún en 
memoria, no podrá utilizar los siguientes módulos: el módulo (10 – 3) + 0 = 
7, los dos anteriores, 6 y 5, y los dos siguientes, 0 y 1. Como necesita 
acceder al módulo 0, el tiempo de espera será de 4 ciclos. Tras ese tiempo, 
ciclo 14, el encadenamiento no se podrá realizar directamente del sumador, 
sino que habrá que realizarlo desde el registro (si esto no fuera posible, 
habría que esperar a que la suma terminara de escribir en el registro V2). 
 
 2 buses / encadenamiento 
A = A + 1 inic. mod. ocup. t. esp. lat. UF dato 1 dato N 
LV V1,A(R1) 3 - - 3 6+1 6+N 
ADDVI V2,V1,#1 [7] - - 2 9+1 9+N 
SV A(R1),V2 [10] ?? 5 / 6 –7– 0 / 1 +4 3 17+1 17+N 
 
En general, para calcular el número de ciclos que hay que esperar para 
utilizar la memoria, hay que hacer el análisis con todas las instrucciones que 
estén en memoria, ya que cada una de ellas ocupará tm módulos de memoria. 
Como consecuencia de ello, no se pueden permitir más de nm div tm 
operaciones de memoria simultáneamente, ya que con ese número de 
instrucciones se ocupan todos los módulos de memoria. Por ejemplo, para el 
anterior caso (nm = 8 y tm = 3) no se pueden procesar simultáneamente más 
de 8 div 3 = 2; estaría de sobra, por tanto, un hipotético tercer bus a 
memoria. 
1.3 DEPENDENCIAS ESTRUCTURALES ▪ 29 ▪ 
De los párrafos anteriores se pueden deducir dos consecuencias 
importantes: por un lado, se necesita que el nivel de entrelazado del sistema 
de memoria sea grande, para que se