UNIVERSIDAD NACIONAL DE TRUJILLO

FACULTAD DE INGENIERIA
ESCUELA DE INGENIERIA DE SISTEMAS

CURSO: ARQUITECTURA DE COMPUTADORAS

TEMA: PROCESAMIENTO SEGMENTADO (PARALELO)

DOCENTE: ING. ARELLANO SALAZAR, CESAR

INTEGRANTES:

 Azabache Noriega, Jorge

 Medina Febre, Héctor
 Vargas Soto, Enrique Segundo
 Quezada Rivera, María Mercedes

TRUJILLO – PERÚ

2018
1
ÍNDICE
I. INTRODUCCIÓN.................................................................................................................................................... 3
II.PROCESAMIENTO PARALELO ............................................................................................................................... 4
III.SEGMENTACIÓN.................................................................................................................................................. 6
IV.REQUISITOS PARA SEGMENTACIÓN………………………………………………………………………………………………………………8

V. RENDIMIENTO DEL PROCESAMIENTO SEGMENTADO ........................................................................................ 9

VI. SEGMENTACIÓN DE PROCESADORES .............................................................................................................. 10
VII. ARQUITECTURA RISC Y CISC ……………………………………….…………………………………………………………………………..…11

VIII. PROCESAMIENTO SEGMENTADOS............................................................................................................... 10

IX. TIPOS DE PROCESAMIENTO SEGMENTADO .............................................................................................. 20
X. CONFLICTOS DE LOS PROCESADORES SEGMENTADOS ................................Error! Bookmark not defined.
XIV. TAXONOMÍA DE FLYNN ............................................................................................................................. 45
 Computadores SISD (Single Instruction Single Data): ............................................................................. 45
 Computadores SIMD (Single Instruction Multiple Data): ....................................................................... 46
 Computadores MIMD (Multiple Instruction Multiple Data): ................................................................. 47
 Computadores MISD (Multiple Instruction Single Data): ....................................................................... 48
XV. TIPOS DE PROCESAMIENTO PARALELISMO SEGÚN LA TAXONOMÍA DE FLYNN ...................................... 49

2
I. INTRODUCCIÓN

En la actualidad, hay una gran demanda de computadores rápidos para muchos

campos de aplicación de tipo científico, técnico, médico, etc. Para muchas de
estas áreas de aplicación, se necesita un gran volumen de cálculo. Sin el empleo
de computadores muy potentes, muchos de los cálculos precisos para este tipo
de aplicaciones no podrían realizarse a una velocidad razonable. Por otra parte,
las tendencias actuales de la ciencia y la técnica siguen planteando problemas
que exigen cada vez más y más potencia de cálculo.

Todo esto hace que las prestaciones de los computadores deben mejorar
continuamente. Para ver de una forma más palpable la necesidad actual de
computadores más rápidos pondremos un ejemplo: los satélites artificiales
envían información a la tierra al ritmo de 1020 bits/sg. Todo este volumen de
información se utiliza para efectuar predicciones meteorológicas, etc. Si
queremos procesar esta información con el fin de que los resultados de ese
proceso sean útiles, deben procesarse con una velocidad suficiente. Teniendo
en cuenta que los cálculos para este tipo de aplicaciones no son sencillos, se
podría estimar que la velocidad de proceso necesaria, para que los resultados
se obtengan antes de dejar de ser útiles, debe ser de unas 1023 operaciones/sg.

Es conocido que la velocidad de los computadores ha ido aumentando con el

tiempo según las evoluciones de la Tecnología. En cualquier caso, existen límites
físicos para el aumento indefinido de la velocidad de las máquinas (velocidad de
la luz, capacidad de los conductores, disipación de calor en los circuitos
integrados, etc.). Estas limitaciones provocan que se busquen nuevas
alternativas para aumentar las prestaciones de las máquinas. Una de las
alternativas que resulta más evidente es poner a trabajar varios elementos de
proceso simultáneamente, dicho de otra forma, tratar de desarrollar el
paralelismo; así el trabajo se repartirá y se tardará menos tiempo en completar
el proceso de cálculo.

3
 II. PROCESAMIENTO PARALELO

El Procesamiento en paralelo consiste en emplear un grupo de técnicas

utilizadas para proporcionar tareas simultáneamente de procesamiento de datos.
Esto con la finalidad de aumentar la velocidad computacional de un sistema de
computadoras. Ofrece una gran ventaja en cuanto a costos. Sin embargo, su
principal beneficio, la estabilidad puede ser difícil de alcanzar aun permitiendo
ejecutar procesos en donde cada procesador se encarga de uno u otro y
aceleran de esta forma el cálculo.
Se basa en un procesamiento recurrente de datos para conseguir un menor
tiempo de ejecución. Implica:
 Sucesos Paralelos: Ocurren en múltiples recursos durante el mismo
intervalo de tiempo.
 Sucesos Simultáneos: Ocurren en el mismo instante.
 Sucesos Pipeline: Ocurren en lapsos superpuestos.
Permite sobrellevar algunas dificultades, particularmente en lo que respecta a la
velocidad de procesamiento; siempre que la arquitectura del computador sea la
correcta. Lo cual mejoran: La velocidad de procesamiento y E/S, mediante la
utilización de CPU y discos en paralelos. El Tiempo de respuesta, así como la
productividad realizando en paralelo las distintas sub-tareas de cada
transacción. Logrando así, muchas operaciones simultáneamente.
Cuenta con los diseños:
 Multiprocesamientos simétricos/ SMP: Diseño simple pero aun así efectivo.
Los procesadores comparten Memoria RAM y BUS del Sistema, esto
permite que se distribuya las tareas entre varios procesadores y que una
aplicación obtenga la memoria que necesita para una simulación compleja.
Esto genera un problema: Genera tráfico en el bus de memoria por lo que
se satura, debido a esto SMP no es escalable.
 Procesamiento masivamente paralelo/MPP: Para evitar los cuellos de
botella en el bus de memoria, MPP no utiliza memoria compartida. Usa
tecnología altamente escalable.
La Memoria RAM es distribuida entre los procesadores. Este Sistema es
escalable, porque permite reducir el tráfico en el bus del sistema. Sus

4
 desventajas: Difícil de programar, La sincronización de datos entre tareas
es difícil, requiere estar al tanto de la organización de la memoria.
 Procesamiento paralelo escalable / SPP: Hibrido de SMP y MPP, que
utiliza una memoria jerárquica de dos niveles para alcanzar la
escalabilidad, esto permite reducir el tráfico de bus del sistema. Aprovecha
las ventajas de MPP y SMP (facilitar la programación).

PROGRAMACIÓN CONCURRENTE
Existen algoritmos para la exclusión mutua:
ALGORITMO DE DEKKER
Implementado por Edsger Dijkstra. Le permite a dos procesos: A) Compartir un
recurso sin conflictos. B) Si ambos procesos intentan acceder a la sección critica
al mismo tiempo. Un proceso es elegido según una variable de turno. El otro
proceso espera la finalización del otro proceso.
ALGORITMO DE PETERSON
Desarrollado en 1981 para dos procesos, posteriormente para más de dos
procesos. Le permite a dos procesos, compartir un recurso sin conflictos usando
sólo memoria compartida.
En la EXCLUSIÓN MUTUA, se usa la programación concurrente para evitar que
fragmentos de código accedan al mismo tiempo a recursos que no deben ser
compartidos. Empleando una técnica, inhabilitando las interrupciones durante el
conjunto de instrucciones más pequeño, esto impide la corrupción de la
estructura compartida.
NIVELES DE PARALELISMO:

A. PARALELISMO TEMPORAL (SEGMENTACIÓN)

Descomponer las operaciones que realizan las unidades de control y
aritmético- lógica.
B. PARALELISMO ESPECIAL O REPLICACIÓN
Varios procesadores operan sobre diferentes datos. Cada uno de estos
procesadores puede tener su propia unidad de control.

5
 C. PARALELISMO FUNCIONAL
La ejecución de diferentes funciones (lógicas, adición, multiplicación) es
realizada en un mismo procesador, simultáneamente por varias unidades
especiales.

III. SEGMENTACIÓN
El procesamiento segmentado aprovecha la misma filosofía de trabajo de la
fabricación en cadena: cada etapa de la segmentación (o segmento) completa
una parte (subtarea) de la tarea total. Los segmentos están conectados cada uno
con el siguiente, de forma que la salida de uno pasa a ser la entrada del siguiente.
Así, los segmentos configuran un cauce a través del que se va procesando la
tarea deseada (por ello, en algunas ocasiones, a los procesadores segmentados
también se les llama procesadores encauzados o, simplemente, cauces). Lo más
interesante de la segmentación es que las diferentes subtareas pueden
procesarse de forma simultánea, aunque sea sobre diferentes datos.
Una contribución clave de la segmentación es la posibilidad de comenzar una
nueva tarea sin necesidad de que la anterior se haya terminado. La medida de
la eficacia de un procesador segmentado no es el tiempo total transcurrido desde
que se comienza una determinada tarea hasta que se termina (tiempo de latencia
del procesador), sino el tiempo máximo que puede pasar entre la finalización de
dos tareas consecutivas.
Evidentemente, la segmentación no es posible sin incrementar los recursos de
proceso, de la misma manera que la fabricación en cadena no es posible sin
aumentar el número de operarios. Por ello, los procesadores segmentados
necesitan redundancia de muchos recursos: registros, circuitos aritméticos, etc.
Considérese una tarea, compuesta por n subtareas. Si estas subtareas se
procesan de forma totalmente secuencial, el tiempo necesario para procesar la
tarea total será la suma de los tiempos necesarios para la terminación de cada
una de las subtareas.

6
En este esquema Tij representa la subtarea j dentro de la tarea i. Por otra parte,
para comenzar el tratamiento de una nueva tarea será necesario esperar ese
mismo tiempo. Esto se debe a que habrá algunas unidades funcionales que
serán necesarias para llevar a cabo varias de las subtareas y por ello, esas
subtareas no podrán superponerse en el tiempo.
Si, para procesar esa misma tarea, se emplea un procesador segmentado, basta
que se haya terminado la primera subtarea para poder empezar a procesar una
nueva tarea.

En la figura anterior puede verse el continuo flujo de tareas que se van

procesando a través de los n segmentos encargados de procesar cada una de
las subtareas. Puede observarse que el tiempo total de procesamiento de una
tarea completa puede ser el mismo, aunque frecuentemente será mayor, que el
tiempo empleado para el procesamiento secuencial de la misma tarea mostrada
en la primera figura.
Esto, sin embargo, carece de importancia ya que lo verdaderamente importante
es el ritmo al que las tareas van saliendo del procesador (velocidad de emisión
de tareas). Al número de segmentos del procesador, n, se le llama, en muchas
ocasiones, profundidad de la segmentación.
Para que el tiempo de latencia del procesador segmentado sea el mínimo
posible, es necesario que el procesador esté equilibrado, es decir, que todas

7
las subtareas en que se ha dividido la tarea total tarden en procesarse el mismo
tiempo. Esto es debido a que las tareas no podrán evolucionar al segmento
siguiente hasta que no se haya terminado la subtarea más lenta. Por ello, si el
procesador no está equilibrado, los segmentos más rápidos estarán cierto tiempo
sin hacer trabajo alguno, lo que disminuirá el rendimiento del procesador.
La relación de precedencia de un conjunto de subtareas Ti , … , Tn , que
componen cierta tarea T, específica para cada subtarea Tj , que ésta no puede
comenzar hasta que haya terminado ciertas subtareas Ti. Las relaciones de
precedencia para todas las subtareas de T forman su grafo de precedencia.
En el ejemplo de la figura anterior se ha supuesto que las tareas que se procesan
en el cauce tienen un grafo de precedencia lineal. Esto significa que una
subtarea Tj, no puede comenzar hasta que todas las subtareas previas, es decir
Ti, para todas las i menores que j, hayan finalizado. A los procesadores
segmentados que sólo pueden procesar tareas con grafo de precedencia de este
tipo, se les denomina cauces lineales.

IV. REQUISITOS PARA UN PROCESAMIENTO SEGMENTADO

Características del proceso necesarias para poder aplicar segmentación:
 Se debe poder descomponer en etapas.
 Es necesario que las entradas de una etapa estén determinadas
únicamente por las salidas de la anterior.
 Cada etapa debe poder ser realizada por un circuito específico de forma
más rápida que el conjunto del proceso.
 Los tiempos de ejecución de cada etapa deben parecidos.

V. RENDIMIENTO DEL PROCESAMIENTO SEGMENTADO

Para estudiar el rendimiento de los procesadores segmentados empezaremos

por calcular la ganancia de velocidad ideal en un procesador de este tipo. Esta
ganancia ideal sólo se podrá obtener si el procesador está equilibrado y, además,
si no se pierden ciclos de reloj. La ganancia de velocidad en un procesador
segmentado de n segmentos vendrá dada por la relación entre el tiempo de

8
ejecución de m tareas en un procesador convencional, t(1), y el tiempo de
ejecución de esas mismas m tareas, en un procesador segmentado, t(n). En las
mejores condiciones y si el procesador está equilibrado se puede suponer que
el periodo de reloj es el mismo en ambos casos. Observando la primera figura,
podemos deducir fácilmente que el tiempo empleado en ejecutar m tareas en un
procesador convencional, medido en ciclos de reloj será
t(1) = nm
Por otra parte, para un procesador segmentado, el tiempo empleado en ejecutar
esas m tareas tendrá dos partes: el tiempo empleado en llenar el cauce, o lo que
es lo mismo, el tiempo empleado en ejecutar la primera tarea (n ciclos) y, luego
un ciclo de reloj por cada una de las tareas restantes (m – 1 ciclos). Por tanto:
t(n) = n + (m – 1)
Con estos datos, podemos deducir que la ganancia de velocidad de un
procesador segmentado, respecto a un procesador convencional es
𝑡(1) 𝑛𝑚
𝑆(𝑛)𝑖𝑑𝑒𝑎𝑙 = =
𝑡(𝑛) 𝑛 + 𝑚 − 1
Cuando el número de tareas ejecutadas, m, sea muy grande, es decir, cuando
haya pasado un poco de tiempo, tendremos que la ganancia estacionaria será:
𝑛𝑚 𝑛
𝑆(𝑛)∞ = lim 𝑆𝑖𝑑𝑒𝑎𝑙 = lim = lim =𝑛
𝑚→∞ 𝑚→∞𝑛 + 𝑚 − 1 𝑚→∞ 𝑛 𝑚−1
+
𝑚 𝑚
De esta forma podemos ver que la ganancia ideal estacionaria obtenida con un
procesador segmentado de n etapas es la misma que la que se consigue con un
sistema paralelo de n procesadores no segmentados.
Evidentemente, esta ganancia ideal no se consigue nunca por diversas razones:
 Las detenciones del cauce
 El desequilibrio entre los segmentos

9
 VI. SEGMENTACIÓN DE PROCESADORES

Este tipo de procesamiento se produce cuando el mismo flujo de datos es tratado

por una serie de procesadores, de forma que cada uno de ellos efectué una
subarea del proceso total. Cada procesador dejara sus resultados en una
memoria, que también es accesible desde el siguiente. Este tipo de
segmentación se emplea solamente en procesadores vectoriales de muy altas
prestaciones.
Por otra parte, los procesadores segmentados pueden ser tanto monofunción
como multi- función. Los primeros sólo pueden realizar una función fija; por el
contrario, los procesadores segmentados multifunción pueden efectuar
diferentes funciones, en instantes distintos, conectando de formas diferentes los
segmentos del cauce.
Los procesadores segmentados multifunción son estáticamente configurables si
no pueden cambiar su configuración mientras se está ejecutando una función;
esto implica que no pueden ejecutarse varias funciones diferentes al mismo
tiempo. Por el contrario, son dinámicamente configurables si pueden cambiar su
configuración en cualquier momento; por ello, los cauces de este tipo pueden
mantener varias configuraciones simultáneas y, por tanto, ejecutar varias
funciones diferentes a la vez.
Para que estos conceptos puedan apreciarse más claramente, pondremos como
ejemplo el procesador segmentado que se mostró en la figura 2.4. En este cauce
podrían ejecutarse diferentes clases de instrucciones, utilizando cada una de
ellas diferentes etapas: por ejemplo, una instrucción de bifurcación sólo
emplearía las etapas A, B y C; sin embargo, una instrucción de almacenamiento
de datos en memoria (STORE) emplearía las etapas A, B, C y D; por otra par-
te, una instrucción de carga (LOAD) emplearía las etapas A, B, C, D y escribiría
el resultado en uno de los registros del banco, por lo que volvería a emplear parte
de la etapa B; por último, una instrucción aritmética pasaría por las etapas A, B,
C y depositaria el resultado en un registro, por lo que tendría que emplear
nuevamente la etapa B.
Un cauce multifunción sería capaz de efectuar todas las operaciones anteriores
con los mismos segmentos, combinándolos de forma diferente en cada caso. Si
este cauce pudiera estar ejecutando al mismo tiempo diferentes clases de

10
instrucciones (evidentemente en diferentes etapas), sería un cauce
dinámicamente configurable.

VII. PROCESADORES CISC Y RISC

Los Microprocesadores o CPU administran juegos de instrucciones basadas en pilas, acumuladores y

registros. Las instrucciones basadas en registros han recibido la mayor atención por parte de los
programadores, hecho que a su vez ha propiciado que los fabricantes de semiconductores, diseñen
arquitecturas de microprocesadores SEGUN la forma en que se administran los registros. Partiendo
de esa base, han surgido dos grandes arquitecturas de microprocesadores para PCs: los diseñados
con instrucciones avanzadas o complejas llamados CISC (Complex Instruction Set Computer) y los
diseñados con instrucciones simples o reducidas llamados RISC (Reduced Instruction Set Computer).

 LA ARQUITECTURA CISC ( Complex Instruction Set Computer ).

La tecnología CISC (Complex Instruction Set Computer) nació de la mano de Intel, creador en 1971
del primer microchip que permitiría el nacimiento de la informática personal. Más concretamente, sería
en 1972 cuando aparecería el 8080, primer chip capaz de procesar 8 bits, suficiente para representar
números y letras. Con la posibilidad de colocar todos los circuitos en un solo chip y la capacidad de
manejar número y letras nacería la cuarta generación de ordenadores.

Los microprocesadores CISC tienen un conjunto de instrucciones que se caracteriza por ser muy
amplio y permitir operaciones complejas entre operandos situados en la memoria o en los registros
internos.

Este tipo de arquitectura dificulta el paralelismo entre instrucciones, por lo que en la actualidad la
mayoría de los sistemas CISC de alto rendimiento implementan un sistema que convierte dichas
instrucciones complejas en varias instrucciones simples, llamadas generalmente microinstrucciones.

La microprogramación es una característica importante y esencial de casi todas las arquitecturas CISC.
La microprogramación significa que cada instrucción de máquina es interpretada por un microprograma
localizado en una memoria en el circuito integrado del procesador. Las instrucciones compuestas son
decodificadas internamente y ejecutadas con una serie de microinstrucciones almacenadas en una
ROM interna. Para esto se requieren de varios ciclos de reloj, al menos uno por microinstrucción. Es

11
así entonces como los chips CISC utilizan comandos que incorporan una gran diversidad de pequeñas
instrucciones para realizar una única operación.

Cuando el sistema operativo o una aplicación requiere de una de estas acciones, envía al procesador
el nombre del comando para realizarla junto con el resto de información complementaria que se
necesite. Pero cada uno de estos comandos de la ROM del CISC varían de tamaño y, por lo tanto, el
chip debe en primer lugar verificar cuanto espacio requiere el comando para ejecutarse y poder así
reservárselo en la memoria interna. Además, el procesador debe determinar la forma correcta de
cargar y almacenar el comando, procesos ambos que ralentizan el rendimiento del sistema. El
procesador envía entonces el comando solicitado a una unidad que lo descodifica en instrucciones
más pequeñas que podrán ser ejecutadas por un nanoprocesador, una especie de procesador dentro
del procesador. Y al no ser las instrucciones independientes, pues son instrucciones menores
procedentes de la descodificación de una instrucción mayor, sólo puede realizarse una instrucción
cada vez.

A través de la compleja circuitería del chip, el nanoprocesador ejecuta cada una de las instrucciones
del comando. El desplazamiento por esta circuitería también ralentiza el proceso. Para realizar una
sola instrucción un chip CISC requiere de cuatro a diez ciclos de reloj.

- CARACTERISTICAS

 Instrucciones de longitud variable

La longitud de la instrucción depende del modo de direccionamiento usado en los operandos

 Las instrucciones requieren múltiples ciclos de reloj para ejecutar

Antes de que una instrucción pueda ser ejecutada los operandos deben ser buscados desde
diferentes ubicaciones en memoria

 Predominan las instrucciones con dos operandos

Los CISC soportan cero, uno o más operandos

 Variedad del direccionamiento de operandos

Registro a registro, registro a memoria y memoria a registro

 Múltiples modos de direccionamiento

Alguno de los direccionamientos soportados son el directo de memoria, indirecto de memoria
y el indexado a través de registros

12
VENTAJAS

 Facilidad de implementación del conjunto de instrucciones

 Compatibilidad hacia adelante y hacia atrás de nuevas CPU’s
 Facilidad de programación
 Puede ser menor la complejidad del compilador

DESVENTAJAS

 La complejidad del conjunto de instrucciones crece

 Las instrucciones de longitud variable reducen el rendimiento del sistema
 Inclusión de instrucciones que raramente se usan

 LA ARQUITECTURA RISC (RISC = Reduced Instruction Set Computer).

Buscando aumentar la velocidad del procesamiento se descubrió en base a experimentos que, con
una determinada arquitectura de base, la ejecución de programas compilados directamente con
microinstrucciones y residentes en memoria externa al circuito integrado resultaban ser más eficientes,
gracias a que el tiempo de acceso de las memorias se fue decrementando conforme se mejoraba su
tecnología de encapsulado.

La idea estuvo inspirada también por el hecho de que muchas de las características que eran incluidas
en los diseños tradicionales de CPU para aumentar la velocidad estaban siendo ignoradas por los
programas que eran ejecutados en ellas. Además, la velocidad del procesador en relación con la
memoria de la computadora que accedía era cada vez más alta.

Debido a que se tiene un conjunto de instrucciones simplificado, éstas se pueden implantar por
hardware directamente en la CPU, lo cual elimina el microcódigo y la necesidad de decodificar
instrucciones complejas.

La arquitectura RISC funciona de modo muy diferente a la CISC, su objetivo no es ahorrar esfuerzos
externos por parte del software con sus accesos a la RAM, sino facilitar que las instrucciones sean
ejecutadas lo más rápidamente posible. La forma de conseguirlo es simplificando el tipo de
instrucciones que ejecuta el procesador. Así, las instrucciones más breves y sencillas de un procesador

13
RISC son capaces de ejecutarse mucho más aprisa que las instrucciones más largas y complejas de
un chip CISC. Sin embargo, este diseño requiere de mucha más RAM y de una tecnología de
compilador más avanzada.

La relativa sencillez de la arquitectura de los procesadores RISC conduce a ciclos de diseño más cortos
cuando se desarrollan nuevas versiones, lo que posibilita siempre la aplicación de las más recientes
tecnologías de semiconductores. Por ello, los procesadores RISC no solo tienden a ofrecer una
capacidad de procesamiento del sistema de 2 a 4 veces mayor, sino que los saltos de capacidad que
se producen de generación en generación son mucho mayores que en los CISC.

Los comandos que incorpora el chip RISC en su ROM constan de varias instrucciones pequeñas que
realizan una sola tarea. Las aplicaciones son aquí las encargadas de indicar al procesador qué
combinación de estas instrucciones debe ejecutar para completar una operación mayor.

Además, los comandos de RISC son todos del mismo tamaño y se cargan y almacenan del mismo
modo. Al ser estas instrucciones pequeñas y sencillas, no necesitan ser descodificadas en
instrucciones menores como en el caso de los chips CISC, pues ya constituyen en sí unidades
descodificadas. Por ello, el procesador RISC no gasta tiempo verificando el tamaño del comando, en
descodificarlo ni en averiguar cómo cargarlo y guardarlo.

El procesador RISC puede además ejecutar hasta 10 comandos a la vez pues el compilador del
software es el que determina qué comandos son independientes y por ello es posible ejecutar varios a
la vez. Y al ser los comandos del RISC más sencillos, la circuitería por la que pasan también es más
sencilla. Estos comandos pasan por menos transistores, de forma que se ejecutan con más rapidez.
Para ejecutar una sola instrucción normalmente les basta con un ciclo de reloj.

CARACTERISTICAS

 Pequeño conjunto de instrucciones

Poseen un número significativamente menor de instrucciones
 Instrucciones simples
 Instrucciones de longitud fija
La mayoría de las instrucciones son de la misma longitud, lo que permite que una instrucción
se busque con una operación individual
 Predominan las instrucciones que se ejecutan en un ciclo de máquina
La mayoría de las instrucciones se ejecutan en un solo ciclo, esto permite la implementación
de la segmentación (Pipelining)

14
  Procesamiento de segmentación
Los procesadores RISC tienen la capacidad de manejar varias instrucciones al mismo tiempo,
por medio de la técnica de segmentación o línea de trabajo
 Causas de la Latencia
Instrucciones requieren más de un ciclo de máquina
Instrucciones de longitud variable
Instrucciones de punto flotante
Acceder a operandos desde memoria en vez que desde registros Acceder
a un recurso compartido
 El problema de la Dependencia Mutua
La dependencia mutua entre instrucciones impone un orden secuencial en la ejecución

VENTAJAS

 Cada instrucción puede ser ejecutada en un solo ciclo del CPU

 Hardware más simple debido a instrucciones más sencillas que requieren menos espacio en
el chip

 Utiliza un sistema de direcciones no destructivas en RAM. Eso significa que, a diferencia de

CISC, RISC conserva después de realizar sus operaciones en memoria los dos operandos y
su resultado, reduciendo la ejecución de nuevas operaciones. La CPU trabaja más rápido al
utilizar menos ciclos de reloj para ejecutar instrucciones.

DESVENTAJAS

 Excesiva dependencia en la efectividad del compilador

 La depuración de los programas se hace difícil por la programación de instrucciones

 Se incrementa el tamaño del código de lenguaje máquina

 Necesidad de memoria rápida

15
DIFERENCIAS RISC VS CISC

DIFERENCIAS CIS RISC

Programación Fácil Compleja

Código Corto Largo

Velocidad Lento Rápido

Compilar Largo Corto

16
 VIII. PROCESADORES SEGMENTADOS

La velocidad de ejecución de los programas depende de diversos factores. Una forma de

aumentar esta velocidad es hacer más rápidos los circuitos con los que se construyen los
procesadores y la memoria principal. No obstante, se debe considerar el coste que supone
una mejora y que el límite a esta velocidad lo impone el estado del arte actual de la
tecnología.
Otra posibilidad es organizar el hardware para poder ejecutar más de una instrucción
simultáneamente: concurrencia. La concurrencia se puede obtener en dos niveles: al nivel
del procesador y al nivel de la instrucción. La concurrencia al nivel de la CPU se obtiene
disponiendo de múltiples procesadores ejecutando simultáneamente varias instrucciones.
Obtener concurrencia a nivel de la instrucción significa poder ejecutar varias instrucciones
simultáneamente con una única CPU. Este último tipo de paralelismo se denomina
segmentación o encadenamiento, aunque suele ser más conocido por su denominación en
inglés: pipelining.
Las arquitecturas con múltiples procesadores suelen utilizarse en máquinas de muy altas
prestaciones (y muy alto precio). Sin embargo, con arquitecturas segmentadas se consigue
una muy buena mejora del rendimiento y a un coste asequible. Por esto, es normal que
todos los microprocesadores actuales de propósito general incorporen el pipelining.
Esta arquitectura es muy común en el desarrollo de programas para el intérprete de
comandos, ya que se pueden concatenar comandos fácilmente con tuberías (pipe).
También es una arquitectura muy natural en el paradigma de programación funcional, ya que
equivale a la composición de funciones matemáticas.
La segmentación (en inglés pipelining, literalmente tuberia o cañeria) es un método por el
cual se consigue aumentar el rendimiento de algunos sistemas electrónicos digitales. Es
aplicado, sobre todo, en microprocesadores. El nombre viene de que para impulsar el gas en
un oleoducto a la máxima velocidad es necesario dividir el oleoducto en tramos y colocar
una bomba que dé un nuevo impulse al gas. El símil con la programación existe en que los
cálculos deben ser registrados o sincronizados con el reloj cada cierto tiempo para que la
ruta crítica (tramo con más carga o retardo computacional entre dos registros de reloj) se
reduzca.
La ruta crítica es en realidad la frecuencia máxima de trabajo alcanzada por el conjunto. A
mayor ruta crítica (tiempo o retraso entre registros) menor es la frecuencia máxima de
trabajo y a menor ruta crítica mayor frecuencia de trabajo. La una es la inversa de la otra.
Repartir o segmentar equitativamente el cálculo hace que esa frecuencia sea la óptima a
costa de más área para el almacenamiento o registro de los datos intervinientes y de un
retraso o latencia (en ciclos de reloj/tiempo) en la salida del resultado equivalente al número
de segmentaciones o registros realizados. La ventaja primordial de este sistema es que, tal y
como se muestra en la imagen, una vez el pipe está lleno, es decir, después de una latencia

17
de cuatro en la imagen, los resultados de cada comando vienen uno tras otro cada flanco de
reloj y sin latencia extra por estar encadenados dentro del mismo pipe. Todo esto habiendo
maximizado la frecuencia máxima de trabajo.

- Detalle de la segmentación de instrucciones

El alto rendimiento y la velocidad elevada de los modernos procesadores, se debe,
principalmente a la conjunción de tres técnicas:
La segmentación consiste en descomponer la ejecución de cada instrucción en varias
etapas para poder empezar a procesar una instrucción diferente en cada una de ellas y
trabajar con varias a la vez.
En el caso del procesador DLX podemos encontrar las siguientes etapas en una instrucción:

IF: Lectura de instrucción

ID: Decodificación de instrucción/Ciclo de búsqueda de
registros
- Decodificar instrucción
- Transferencia de operandos del bancode registros
a los registros de entradade la ALULectura

EX: Ejecución / ciclo de dirección efectiva

- El resultado de una operación aritmético-lógica en
instrucciones registro-registro
- Una dirección efectiva de memoria, en
instrucciones de referencia a memoria
- Dirección de salto/rama en instrucciones de
transferencia de control

MEM: Acceso a memoria / ciclo de finalización de rama

- Se escribe en la memoria el resultado de la
operación o se revisa la condición de rama para
decidir si se toma o no

WB: Ciclo de Retroescritura (write-back)

- el resultado de la ejecución de una instrucción
registro-registro o de carga se almacena en el
banco de registros

18
19
 IX. TIPOS DE PROCESAMIENTO SEGMENTADO
Puede establecerse una clasificación de los procesadores segmentados
atendiendo al uso que se da a la segmentación. Esta clasificación fue
propuesta por Händler (1977):
SEGMENTACION ARITMETICA:
ALU de un computador puede segmentarse para la ejecución de algoritmos
aritméticos complejos. La segmentación aritmética es muy útil para procesar
instrucciones vectoriales, es decir, operaciones que deben repetirse de la
misma forma sobre todas las componentes de un vector; esto se consigue
provocando que un segmento de la unidad aritmética trabaje sobre una de las
componentes, mientras los demás trabajan sobre las componentes siguientes,
realizándose así las diferentes sub-funciones necesarias para la ejecución de la
operación aritmética. En la actualidad, este tipo de segmentación se emplea en
muchos procesadores para ejecutar operaciones aritméticas con números
representados en punto flotante. Un ejemplo clásico de este tipo de
procesadores es el multiplicador segmentado basado en un árbol de Wallace,
tal como se muestra en la figura 2.3. En esta figura, los bloques CSA
representan a sumadores con salvaguarda de llevadas y los bloques CLA, a
sumadores con generación anticipada de llevadas. Las líneas inclinadas hacia
la izquierda indican que los vectores de llevadas deben desplazarse a la
izquierda un lugar antes de entrar en la etapa siguiente (véase, por ejemplo,
(Bastida, 1995)). Por otra parte, es necesario señalar que las sumas deben
efectuarse con extensión de signo y que es necesario dejar bits de guarda para
tener en cuenta las posibles llevadas salientes.
Las cajas sombreadas representan registros cerrojos (latchs) que, en este
caso, se llaman

20
Fig. 2.3. Multiplicador segmentado basado en un árbol de Wallace.
registros de segmentación. Estos registros retienen las informaciones
salientes de cada etapa durante un ciclo de reloj para que se mantengan en la
entrada de la siguiente etapa.
Se ha supuesto que el retardo del sumador con anticipación es doble que el del
sumador con salvaguarda de llevadas.

21
SEGMENTACION DE INSTRUCCIONES:
La ejecución de un flujo de instrucciones puede adoptar una estructura
segmentada que permita el solapamiento de la ejecución de una instrucción
con la lectura, decodificación, búsqueda de operandos, etc. de las instrucciones
siguientes. Esta técnica también se denomina anticipación de instrucciones
(instruction lookahead).
En la figura 2.4 se muestra un ejemplo de segmentación de instrucciones. La
citada figura corresponde a un computador de tipo registro-registro, es decir, un
computador en que los accesos a memoria están restringidos a instrucciones
específicas (LOAD y STORE), y en que el modo de direccionamiento empleado
para estos accesos a memoria y para las bifurcaciones, es el relativo al
contador de programa. Se supone que el computador dispone de arquitectura
Harvard, es decir, que posee memorias caché separadas para código

22
Fig. 2.4. Ejemplo de segmentación de instrucciones.
y datos. En el ejemplo, se ha dividido la ejecución completa de cada instrucción
en cuatro segmentos:
A. Lectura.
B. Decodificación y lectura de operandos.
C. Ejecución.
D. Acceso a la memoria de datos (si es necesario).
Prácticamente, todos los computadores actuales disponen de segmentación de
instrucciones.

SEGMENTACION DE PROCESADORES:
Este tipo de procesamiento se produce cuando el mismo flujo de datos es
tratado por una serie de procesadores, de forma que cada uno de ellos efectúe
una subtarea del proceso total. Cada procesador dejará sus resultados en una
memoria, que también será accesible desde el siguiente, para que éste
procese esos resultados para ejecutar la siguiente subtarea sobre el flujo de
datos. Este tipo de segmentación se emplea solamente en procesadores
vectoriales de muy altas prestaciones.
Por otra parte, los procesadores segmentados pueden ser tanto monofunción
como multifunción. Los primeros sólo pueden realizar una función fija; por el
contrario, los procesadores segmentados multifunción pueden efectuar
diferentes funciones, en instantes distintos, conectando de formas diferentes
los segmentos del cauce.
Los procesadores segmentados multifunción son estáticamente configurables
si no pueden cambiar su configuración mientras se está ejecutando una
función; esto implica que no pueden ejecutarse varias funciones diferentes al
mismo tiempo. Por el contrario, son dinámicamente configurables si pueden
cambiar su configuración en cualquier momento; por ello, los cauces de este
tipo pueden mantener varias configuraciones simultáneas y, por tanto, ejecutar
varias funciones diferentes a la vez.
Para que estos conceptos puedan apreciarse más claramente, pondremos
como ejemplo el procesador segmentado que se mostró en la figura 2.4. En
este cauce podrían ejecutarse diferentes clases de instrucciones, utilizando

23
cada una de ellas diferentes etapas: por ejemplo, una instrucción de bifurcación
sólo emplearía las etapas A, B y C; sin embargo, una instrucción de
almacenamiento de datos en memoria (STORE) emplearía las etapas A, B, C y
D; por otra parte, una instrucción de carga (LOAD) emplearía las etapas A, B,
C, D y escribiría el resultado en uno de los registros del banco, por lo que
volvería a emplear parte de la etapa B; por último, una instrucción aritmética
pasaría por las etapas A, B, C y depositaría el resultado en un registro, por lo
que tendría que emplear nuevamente la etapa B.
Un cauce multifunción sería capaz de efectuar todas las operaciones anteriores
con los mismos segmentos, combinándolos de forma diferente en cada caso. Si
este cauce pudiera estar ejecutando al mismo tiempo diferentes clases de
instrucciones (evidentemente en diferentes etapas), sería un cauce
dinámicamente configurable.

X. CONFLICTOS DE SEGMENTACION
Hay circunstancias que pueden disminuir el rendimiento de un procesador
segmentado debido a que provocan la detención del cauce. Estas
circunstancias se denominan riesgos o conflictos.

Existen tres clases de conflictos (Hennessy & Patterson, 2003):

Conflictos estructurales:
Los conflictos estructurales, en los cauces monofunción, se resuelven, si ello
fuera posible, aumentando las posibilidades del hardware duplicando todos los
recursos que sea necesario.Uno de los conflictos estructurales más frecuentes
en los cauces monofunción son los relacionados con los accesos a memoria;
por ejemplo, se producirá un conflicto cuando una etapa trate de acceder a
memoria para leer una instrucción y otra lo haga para acceder a un dato. Estos
conflictos se resuelven, en primer lugar, mediante la arquitectura Harvard en
que existen memorias caché diferenciadas para código y datos. Aún así, podría
mantenerse algún conflicto, por accesos simultáneos a datos por parte de
varios segmentos. Esto se puede evitar agregando nuevos puertos a la caché
de datos o, también, limitando los accesos a datos a determinadas
instrucciones para que sea difícil que se superpongan (arquitecturas registro-
registro o de carga-almacenamiento). También existe la posibilidad de que el

24
compilador tenga en cuenta la estructura del procesador, detecte este tipo de
conflictos y, cuando ello ocurra, intente modificar el orden de ejecución de las
instrucciones, siempre que sea posible, para intentar evitarlos.

En los cauces no lineales, el control de estos conflictos adquiere una nueva

dimensión. El problema todavía se agrava más en los cauces multifunción
dinámicamente configurables. En estos cauces existe la posibilidad del uso
simultáneo de varios segmentos por parte de ejecuciones distintas de la misma
función o por varias de las funciones. Este tipo de conflictos estructurales se
denominan colisiones. El control de colisiones se hace más complejo si el
grafo de precedencia de las tareas no es lineal. Las técnicas de prevención de
colisiones se basan en las tablas de reservas (Davidson, 1971).

Una tabla de reservas contiene la información sobre la ocupación de cada

segmento en cada uno de los ciclos máquina hasta que termine de ejecutarse
cierta tarea. Las filas de la tabla representan a cada uno de los segmentos y las
columnas representan los ciclos necesarios para la ejecución de la tarea. Para
un cauce monofunción y lineal, la tabla de reservas sólo tendrá marcadas las
casillas de la diagonal, sin embargo, en los cauces no lineales, la construcción
de la tabla no será tan simple. Un ejemplo de este tipo de tablas puede verse
en la figura 2.5 para las instrucciones aritméticas y de carga en el procesador
segmentado de la figura 2.4.

Para simplificar el estudio del control de las colisiones consideraremos

inicialmente un procesador segmentado monofunción. Tomaremos como
ejemplo la función cuya tabla de reservas

25
se muestra en la figura 2.6(a). El problema que se nos plantea es: si
quisiéramos efectuar dos veces sucesivas la misma tarea, ¿Cuántos ciclos
máquina tendríamos que esperar para arrancar dicha tarea por segunda vez?
La solución es sencilla: basta superponer a la tabla de reservas original, la
misma tabla desplazada un lugar a la derecha. Si alguna de las etapas está
ocupada en el mismo ciclo por la tabla original y por la desplazada, significa
que no podrá ejecutarse la tarea la segunda vez, arrancada sólo un ciclo más
tarde, por existir una colisión. Se debe intentar superponer la tabla
desplazándola más lugares hacia la derecha hasta que no haya ningún ciclo
que esté ocupado en ambas tablas al mismo tiempo. El número de
desplazamientos entre ambas tablas nos dará el número de ciclos que habrá
que esperar (también denominado latencia) para arrancar la tarea por segunda
vez sin que haya colisiones. A las latencias en que ocurre colisión se les
denomina latencias prohibidas. Precisamente a partir de esta idea, se
construye el vector de colisiones que es un vector binario cuya componente i
es 1 si, y sólo si, se produce una colisión cuando se arranca la tarea la
segunda vez i ciclos después de haberse iniciado la primera.

En el caso de la tabla de reservas anterior, el vector de colisiones se muestra

en la figura 2.6(b).
Como fácilmente puede comprenderse, el número de componentes del vector
de colisiones

26
estará acotado superiormente por el número de ciclos necesarios para
completar la ejecución de la tarea menos uno, ya que no se contempla la
colisión de la ejecución de una tarea consigo misma; en cualquier caso, es
posible omitir las últimas componentes nulas del vector. Ahora estudiaremos la
forma en que puede ayudarnos en la práctica el vector de colisiones para
prevenir éstas. Hay que tener en cuenta que los cálculos necesarios para esa
prevención deben hacerse de forma simultánea y en el mismo tiempo del ciclo
máquina; por ello, los circuitos necesarios deben ser muy sencillos y rápidos.
En la figura 2.7 se muestra el esquema de principio de un circuito para la
prevención de las colisiones. Como puede observarse, este circuito basa su
funcionamiento en un registro de desplazamiento hacia la izquierda con
posibilidad de carga paralela. El funcionamiento comprende los siguientes
pasos (Davidson, 1971):

1. Al principio de cada ciclo, se provoca un desplazamiento del

registro hacia la izquierda.
2. Una petición de acceso al cauce debe concederse si el bit saliente
del registro de desplazamiento es 0; por el contrario, debe
denegarse si el bit saliente es 1.
3. Ahora actuaremos de forma diferente en función de la concesión o
no del acceso al cauce:
 Si una petición ha sido concedida, se efectúa una operación
OR entre el contenido del registro de desplazamiento y el
vector de colisiones, el resultado de esta operación se carga
en el registro.
 Si, por el contrario, la petición no ha sido concedida, no se
hará ninguna operación sobre el registro de desplazamiento y
sólo se retendrá la petición para repetirla en el ciclo siguiente.

27
 4. Se vuelve al primer paso del proceso.

El número de ciclos que habrá que esperar, en caso de denegarse la solicitud

de acceso, no podrá ser mayor que la longitud del vector de colisiones, ya que
en ese número de ciclos el registro de desplazamiento se habrá vaciado

La estrategia de control que se ha expuesto se basa en comenzar una nueva

tarea en el primer ciclo de reloj en que no haya conflicto con las tareas ya
comenzadas. A este tipo de estrategia se le denomina estrategia avara
(greedy strategy) debido a que se trata de arrancar una nueva tarea tan
pronto como sea posible. Esta estrategia es fácil de implementar, como se
acaba de ver, pero no es necesariamente la que proporciona un mejor
rendimiento. Si la estrategia avara fuera la mejor, y muchas veces lo es, se
dará el caso de que podremos implementar una estrategia con buen
rendimiento por procedimientos sencillos. Para explicar por qué la estrategia
avara no es siempre la mejor, recurriremos al llamado diagrama de estados
que mostrará el estado del registro de desplazamiento del circuito de la figura
2.7 cuando se ejecuta dos veces la misma tarea, retrasada la segunda
respecto a la primera el número de ciclos señalado en cada arco del grafo. Sólo
se representarán en el diagrama los estados correspondientes a las latencias
que no producen colisión. Para generar el diagrama de estados se deben
seguir los siguientes pasos:

1. Se parte del vector de colisiones como estado inicial del diagrama.

2. De cada estado deben salir tantos arcos como número de ceros haya en
él. Cada uno de estos arcos nos llevará al estado del registro de
desplazamiento cuando cada uno de los ceros salga por la izquierda, y se
etiquetará con el número de la componente que ocupe ese cero en el
vector. Hay que tener en cuenta que, para llegar al nuevo estado, es
necesario efectuar la operación OR con el vector de colisiones, como se
indicó antes. Si el estado al que se llega con esta operación no está aún
en el diagrama, debe agregarse a la lista de estados con los que
repetiremos la operación.
3. Cuando se haya terminado de efectuar la operación anterior con todos los
estados existentes, se añadirá, a cada estado, un arco que le una con el
estado inicial. A este arco se le asignará una etiqueta que sea igual al
número de componentes del vector de colisiones más 1 y el superíndice
+. El signo + sobre una etiqueta de arco indica que ese arco se refiere a
la latencia indicada y a todas las mayores que ella, por esto, puede

28
 cambiarse la etiqueta de alguno de estos arcos a un valor inferior al
número de componentes del vector de colisiones si, para las latencias
mayores a ese valor, corresponde el mismo arco del diagrama.

Los arcos etiquetados con el superíndice + provienen del hecho de que el

registro de desplazamiento se vacía después de cierto número de operaciones.
A partir de ese momento, el circuito vuelve a su estado inicial.

En la figura 2.8 se muestra el diagrama de estados correspondiente al vector

de colisiones de la figura 2.6(b). En el citado diagrama puede observarse que si
aplicamos la estrategia avara, no se alcanzará el mejor rendimiento, porque el
arco con latencia menor (2) nos llevará al estado 11111, y éste nos obliga a
salir por un arco de latencia 6. Si se arrancan sucesivas tareas siguiendo ese
ciclo del grafo, el rendimiento final será peor que si hubiéramos salido por el
arco de latencia 3.

Al diseñar un cauce, debe construirse el diagrama de estados para ver cuál es

el recorrido cíclico en el grafo con mejor rendimiento. Éste se medirá por el
número medio de tareas iniciadas por ciclo de reloj a lo largo de todo el ciclo (r)
o, también, por la latencia media que es el número medio de ciclos de reloj
que hay que esperar entre dos iniciaciones consecutivas de la tarea (esta
medida será la inversa de la anterior). El recorrido cíclico del grafo que
consigue la

mínima latencia media (minimal average latency,MAL) será el de mayor

rendimiento. En el ejemplo anterior la estrategia avara tiene una latencia media
de 4, mientras que su MAL es 3. Como veremos a continuación, la MAL está
acotada inferiormente por el número máximo de ciclos reservados (marcas)
para una etapa (fila) en la tabla de reservas (Shar, 1972). Para demostrar esto,

29
llamaremos Ni al número de ciclos reservados en la fila i de la tabla de
reservas.
El índice de utilización de la etapa i vendrá dada por rNi. Este índice valdrá,
como máximo, 1 (cuando todas las casillas de esa fila de la tabla de reservas
estén marcadas, aunque no por una sola iniciación de la tarea), es decir

donde n es el número de segmentos del cauce. Como se explicó antes, r es el

inverso de la latencia media. Por tanto, el inverso del máximo valor de r será la
MAL. Tomando los valores inversos de la última inecuación, tendremos que

que es lo que pretendíamos demostrar.

La conclusión final de todo esto es que, si llegamos a conseguir que la latencia

entre dos iniciaciones consecutivas de la misma tarea, sea el número máximo
de marcas en una fila de la tabla de reservas, se obtendrá el máximo
rendimiento del cauce. Esto puede conseguirse, como se mostrará en el
siguiente algoritmo debido a Patel y Davidson (1976), introduciendo retardos
entre los segmentos del cauce. Para explicar el funcionamiento del algoritmo, lo
aplicaremos sobre la tabla de reservas ya mostrada en la figura 2.6 y a la que
corresponde el diagrama de estados de la figura 2.8. En este diagrama puede
apreciarse que la mínima latencia media (MAL) se produce en el ciclo que sólo
pasa por el estado 11011, y su valor es 3. Como se acaba de demostrar, la
cota inferior del MAL, para este caso, es 2, que es el número máximo de
marcas en una fila de la tabla de reservas.

El algoritmo propuesto puede seguirse en la figura 2.9. Para ilustrarlo mejor, se

muestran las tablas de reservas para más tiempo que el necesario para una
sola iniciación de la tarea. El algoritmo toma cada marca de la tabla de
reservas, en orden temporal, y copia dicha marca con una periodicidad igual a
la latencia deseada, en el caso de nuestro ejemplo, esta latencia es 2, como ya
se mencionó antes. Señalaremos estas copias con una P (prohibida) indicando
que esas

30
31
casillas estarán ocupadas en las siguientes iniciaciones de la tarea. Puede
ocurrir (figura 2.9(g)) que debamos poner una marca en una casilla ya ocupada
(y, por tanto, señalada con una P); en este caso, introduciremos un retardo en
esa etapa (señalado en la tabla con una R) para conseguir que ocupe un lugar
libre. Cuando nos veamos obligados a ello, deberemos tener en cuenta que las
etapas siguientes en el tiempo deberán ser retardadas en la misma medida.
Como resultado de la aplicación de este proceso, llegaremos a una tabla de
reservas con algunas etapas retardadas; para nuestro ejemplo concreto, esta
tabla se muestra en la figura 2.10(a), su vector de colisiones se muestra en (b)
y el diagrama de estados correspondiente puede verse en (c). Con esta tabla
se conseguirá la latencia mínima posible para nuestro cauce, que es 2,
pasando por los estados 100010 y 101010, quedando cíclicamente en éste
último. Muchos de los conceptos anteriores son también aplicables cuando se
ejecutan varias tareas distintas en un cauce multifunción. En este caso, será
necesario calcular los vectores de colisiones de cada función ejecutada
después de cada una de las demás. Para ilustrar esta idea, analicemos lo que
ocurriría en el cauce al que corresponde la tabla de la figura 2.6, si además de
esa función (llamémosla X), pudiera ejecutar otra función Y , con la tabla de
reservas y vector de colisiones que se muestran en la figura 2.11. Para saber
en qué momento podremos arrancar la función Y cuando ya se está ejecutando
la función X, superpondremos las tablas de reservas de ambas operaciones y
desplazaremos la correspondiente a la función Y hacia la derecha hasta que no

32
haya superposiciones (colisiones); de esta forma, podremos construir el vector
de

colisiones de Y después de X (vector de colisiones cruzadas), que será:

Análogamente podríamos proceder al cálculo del vector de colisiones cruzadas

de X después de Y , con lo que se obtendría:

Con estos vectores, y los vectores de colisiones de las propias funciones (vxx y
vyy), construiremos la llamada matriz de colisiones para una función (MX),
que es una matriz cuyas filas son los vectores de colisiones correspondientes a
esa función cuando después se ejecuta cada una de las demás. Si los vectores
tuvieran diferentes números de componentes, la matriz toma tantas columnas
como corresponda a la longitud del vector más largo, completando los demás
con ceros por la derecha. Para las operaciones anteriores, las matrices de
colisiones serán:

33
Con estas matrices de colisiones, podremos determinar si, en un determinado
ciclo de reloj, se podría admitir el comienzo de una nueva tarea en el
procesador segmentado. Para hacerlo, ampliaremos el circuito mostrado en la
figura 2.7 para tener en cuenta todos los casos posibles en el orden de
ejecución de las funciones. Este circuito ampliado se muestra en la figura 2.12,
y su funcionamiento es completamente análogo al anterior. En general, un
procesador segmentado, en que se puedan ejecutar p funciones diferentes, se
podrá controlar con p registros de desplazamiento.

También puede construirse para este caso el diagrama de estados. Este

diagrama, que es análogo al correspondiente a los cauces monofuncionales,
difiere sin embargo de éstos en los siguientes aspectos:

34
  Los nodos, en vez de estar identificados por un vector, están
identificados por una matriz.
 El estado inicial no es único, sino que hay tantos estados iniciales
como funciones pueda efectuar el procesador segmentado.
 En los arcos que conectan los nodos debe indicarse, además de la
latencia, la operación que se ejecuta.

Como muestra de diagrama de estados, en la figura 2.13 puede verse el

correspondiente al ejemplo anterior.

Conflictos por dependencias de datos

Como ya se explicó anteriormente, este tipo de conflictos surgen cuando varias

tareas acceden a los mismos datos. Normalmente estos conflictos se producen
en procesadores segmentados de instrucciones, sobre todo si están
profundamente segmentados, pero también podrían producirse en cauces
aritméticos.

Supongamos dos instrucciones A y B que se ejecutan en ese mismo orden en

un procesador segmentado de instrucciones. Las dependencias de datos que
se pueden presentar pueden ser de tres clases:

RAW (read after write, lectura después de escritura): la instrucción B trata

de leer un operando antes de que la instrucción A lo haya escrito; de esta
forma, B puede tomar un valor incorrecto de ese operando. Éste es el tipo de
dependencia más común. Trataremos de exponer ahora una condición más
formalizada para la existencia de estos riesgos (Keller, 1975): Si denotamos
por OA al conjunto de salida o rango de la instrucción A, y por IB al conjunto de

35
entrada o dominio de la instrucción B (recordar el apartado 1.3.4), habrá
posibilidad de riesgo RAW si:

Esto, que corresponde con la dependencia de flujo definida en la apartado

1.3.4, es una condición necesaria pero no suficiente. La existencia o no de
riesgo depende de la separación temporal de las instrucciones A y B, así como
de la profundidad de la segmentación.

WAR (write after read, escritura después de lectura): la instrucción B trata

de escribir en un registro antes de que sea leído por la A; por ello, A tomaría un
valor incorrecto, ya que debería tomar el valor antes de modificarse. Este
riesgo es poco frecuente, debido a que la escritura de los resultados se efectúa
en los últimos segmentos y es difícil que esa escritura se adelante al segmento
de lectura de una instrucción anterior. El riesgo WAR se podría presentar,
sobre todo, en procesadores con autoindexación, en los que la fase de lectura
de operando, que es una de las primeras, puede modificar un registro antes de
que una instrucción anterior lo haya leído. Aun en este tipo de procesadores
este riesgo es difícil que se produzca. No obstante, como veremos más
adelante, esta clase de riesgos se pueden producir si se alterara el orden de la
ejecución de las instrucciones. Existirá peligro de producirse este riesgo si

es decir, si existe antidependencia entre las instrucciones A y B, aunque, igual

que en el caso anterior, esta condición es necesaria pero no suficiente.

WAW (write after write, escritura después de escritura): la instrucción B

intenta escribir un operando antes de que sea escrito por la A. Dado que las
escrituras se están realizando en orden incorrecto, el resultado final depositado
es el correspondiente a la instrucción A cuando debería ser el depositado por la
B. Este conflicto sólo se produce en procesadores segmentados que escriben
en más de una etapa y esto no es muy frecuente. Este riesgo, igual que el
anterior, se podría producir en máquinas que permiten direccionamientos
autoindexados. Al igual que el riesgoWAR, los riesgosWAWtambién podrían
aparecer si se cambiara el orden de ejecución de las instrucciones. Podrá
existir un riesgoWAWentre las instrucciones A y B si existe dependencia de
salida entre las citadas instrucciones, es decir, si se verifica que:

36
Aunque, como en los casos anteriores, esta condición no es suficiente para la
existencia del riesgo.

Debe observarse que RAR (lectura después de lectura) no constituye ningún

riesgo puesto que ninguna de las dos instrucciones cambia el valor del dato.

Existen técnicas para detectar los conflictos por dependencias de datos. Estas
técnicas precisan algo de hardware adicional: unos buffers, que guarden los
números de los registros implicados en las últimas instrucciones, junto con
unos comparadores. Los buffers tendrán una estructura de registro de
desplazamiento, de forma que la posición del número de registro dentro del
desplazador nos dirá en qué segmento se encuentra y la clase de operación
que se efectúa sobre él (lectura o escritura). Los comparadores analizarán si
coinciden los operandos de la instrucción que va a ejecutarse, con los de
alguna de las anteriores con las que pueda entrar en conflicto. Si existe
conflicto, como primera solución, se detendrá la ejecución de la instrucción
hasta que las anteriores hayan avanzado y la dependencia desaparezca (esto
es lo que se llama insertar una burbuja). Frecuentemente, en este caso, se
dice que se impide la emisión de la instrucción, ya que se llama así al paso
de la instrucción de la etapa de decodificación a la siguiente, donde comienza
la ejecución efectiva de la instrucción (localización de operandos). Una solución
para reducir la duración de estas detenciones es hacer uso del resultado, en
cuanto se disponga de él, aunque no se haya escrito en el registro afectado;
este método se llama anticipación

Existen también técnicas para evitar las posibles detenciones que podría
producir un conflicto. Estos métodos pueden clasificarse en dos grupos:

Planificación estática: las técnicas de este tipo consisten en habilitar los

medios software para que el compilador detecte los riesgos y cambie el orden
de las instrucciones que los producen en la medida de lo posible. Si el
compilador no encuentra ninguna instrucción que pueda evitar la detención,
insertará una instrucción NOP (no operación) para dejar un lugar libre en la
cadena de procesamiento sin tener que efectuar una detención.

Para ver los efectos de la planificación estática, tomaremos como ejemplo el

siguiente fragmento de código (se supone que el destino es el último
operando):

37
En esta porción de código, y representan dos direcciones de memoria. En el
ejemplo, la instrucción, tiene una dependencia de datos respecto de las
instrucciones que acceden a memoria y hasta que éstas no tengan los datos,
no podrá leer los operandos. En este fragmento de código se puede observar
que las instrucciones son independientes de las siguientes por lo que pueden
ejecutarse en cualquier orden respecto a ellas. Según esto, un compilador que
lleve a cabo planificación estática puede adoptar la solución de reordenar estas
instrucciones de la forma siguiente:

Esta reordenación de las instrucciones evitará la dependencia de datos, ya que

mientras se ejecutan y, dará tiempo a que las instrucciones tengan disponibles
los datos.

La mayoría de los computadores segmentados actuales utilizan planificación

estática, bien efectuada por el propio compilador, o bien, por parte de algún
post-procesador que optimice el código generado por el compilador.

Planificación dinámica: con esta clase de métodos es el propio procesador,

durante la ejecución de las instrucciones, el que cambia el orden de emisión de
las mismas para mantener los segmentos del cauce tan ocupados como sea
posible. Esto puede hacerse incluyendo la detección y evitación de conflictos
en el código del microprograma, en los procesadores microprogramados, o
bien añadiendo el hardware oportuno en los procesadores cableados.

Existen dos métodos clásicos para implementar la planificación dinámica:

38
 El marcaje (scoreboarding): un marcador (scoreboard) es un sistema de
tablas (mantenidas a nivel hardware) que tiene información sobre la
ocupación de los recursos de la máquina. Mediante el marcador podemos
saber cuándo una instrucción tiene o no dependencias pendientes. Si
tuviera alguna dependencia, aplazamos su emisión intentándola con otra
instrucción posterior en que esas dependencias no se produzcan. El
emitir las instrucciones fuera de orden puede tener el inconveniente de
que se pueden producir nuevos riesgos que también deberán ser
considerados por el marcador. Cada instrucción pasa por el marcador (en
una de las primeras fases de la segmentación) donde se mantiene una
tabla con las dependencias de datos. En esta tabla está la información
suficiente para saber cuándo la instrucción puede emitirse o no. Si la
instrucción no se pudiera emitir en ese momento, intenta emitir otra y
controla los cambios producidos para saber cuándo la dependencia de
datos está resuelta. El marcador contiene las siguientes informaciones:

1. Estado de las instrucciones, es decir, el segmento en el que se

encuentra cada instrucción.
2. Estado de las unidades funcionales: indica la ocupación de cada
unidad funcional además de los operandos con los que está
trabajando
3. Estado de los registros de resultado: nos informara sobre las
escrituras en los registros para saber cuándo están actualizados.

 El algoritmo de Tomasulo (1967): este algoritmo es similar a los

sistemas de marcadores, con la diferencia de que la información sobre la
ocupación de recursos está distribuida en las llamadas estaciones de
reserva. Cada unidad funcional tiene una estación de reserva que
controla cuándo puede comenzar una nueva operación en esa unidad
funcional, es decir cuándo sus operandos están listos. Cada estación de
reserva tiene las siguientes informaciones:

1. La operación a efectuar.
2. Los numero de estaciones de reserva que corresponden a las
unidades funcionales que producirán los operandos de la
instrucción. Debe existir un valor (normalmente 0) para indicar que
alguno de los operandos ya está disponible; para este caso se
activa el campo descrito a continuación.
3. Los valores de los operandos fuentes si es que ya están
disponibles.

39
El algoritmo de Tomasulo utiliza anticipación, es decir, si un operando está
disponible, no se espera a que sea almacenado en el registro de destino, sino
que se lleva a las estaciones de reserva que lo estén esperando; de esa forma,
éstas lo podrán utilizar para sus respectivas operaciones. Otra característica
importante es que todas las estaciones de reserva tienen acceso a un bus,
denominado bus común de resultados, en que las unidades funcionales
dejan los resultados de las operaciones.

La ventaja que tiene el disponer de este bus es que, si hubiera varias

estaciones de reserva esperando por el mismo dato, cuando ese dato aparezca
en el bus común, podrá ser capturado por todas y continuar la ejecución.

Para este algoritmo también se precisa mucho hardware, con la diferencia

respecto a los marcadores, de que ese hardware está distribuido entre todas
las estaciones de reserva.

El algoritmo de Tomasulo se utilizó en el IBM-360/91 también en los años 60.

Las técnicas de planificación dinámica pueden ser algo más eficaces que las
estáticas, pero también son bastante más complicadas. Una de las misiones
del diseñador de un procesador segmentado será decidir el tipo de planificación
más adecuado, sopesando las ventajas e inconvenientes de cada uno.

40
Conflictos de control

Este tipo de conflictos se producen en los procesadores de instrucciones

segmentados. Como se mencionó anteriormente, los conflictos de control se
deben a las instrucciones de control del flujo, que no permiten que se lea la
instrucción siguiente hasta que no se conozca su dirección (que precisamente
es calculada por la propia instrucción de control de flujo). Parece claro que una
instrucción de control de flujo provocará una detención del procesador, ya que
el cálculo de la dirección de destino, al menos en principio, se efectúa en la
fase de escritura de resultado (de la instrucción de control) y esta fase suele
ser la última. Esto es especialmente válido en las instrucciones de bifurcación
condicional. Una imagen gráfica de un conflicto de control puede verse en la
figura 2.14. Conflictos de esta misma índole se producen también debido a los
desvíos e interrupciones. En estos casos, los conflictos son más graves porque
no están previstos en el programa y, por tanto, son mucho más difíciles de
controlar.

Calcularemos la pérdida de rendimiento debida a los saltos si no se toma

ninguna medida correctora. Supongamos que, en cuanto se detecte una
instrucción de control de flujo, se detiene inmediatamente el procesador hasta
que la dirección de la instrucción siguiente se haya calculado. Evidentemente,
cuanto mayor sea el porcentaje de instrucciones de control de flujo, mayor será
la influencia de los conflictos de control en el rendimiento del cauce.

Sea Ps la probabilidad de aparición de una instrucción de control, y b el numero

de ciclos perdidos por la detención (penalización del salto). En estas
condiciones, el tiempo de ejecución de m tareas será:

Podemos mejorar un poco este tiempo si dejamos que se continúen leyendo

instrucciones. De esta forma, si la instrucción de control no es efectiva (es decir
si la condición no se cumple), habremos adelantado algo. Para los cálculos
siguientes vamos a suponer que, cuando la condición de bifurcación se haya
evaluado, todavía no se ha emitido la instrucción siguiente, es decir, que dicha
instrucción no ha efectuado ninguna acción difícilmente reversible (modificación
de registros, flags, etc.). Estas suposiciones pueden servir para hacernos una

41
idea de la incidencia de los conflictos de control en el rendimiento de un
procesador segmentado:

Sea Pt la probabilidad de que una instrucción de control sea efectiva, entonces,

y con los anteriores supuestos, el tiempo de ejecución de m tareas será:

La productividad del procesador vendrá dada por:

donde f es la frecuencia del reloj. Esta productividad, en el estado estacionario,

es decir, para valores grandes de m, tenderá a:

Si suponemos que las bifurcaciones se resuelven en el último segmento,

tendremos que el número de ciclos perdidos, b, será n−1, con lo que la
productividad estacionaria se podrá escribir como:

Otra forma de medir las pérdidas por riesgos de control sería calcular el CPI
teniendo en cuenta estos riesgos (pero prescindiendo de los demás), es decir:

Como se ve las pérdidas debidas a los conflictos de control son bastante

importantes, ya que, en condiciones ideales, el CPI estacionario debe ser 1.
Esto significa que la eficiencia se calculará dividiendo este CPI ideal por el
obtenido en 2.9, por tanto:

42
Una de las soluciones para evitar estas pérdidas de rendimiento es hacer que
el compilador encuentre algo útil para hacer mientras calcula la dirección del
destino del salto. Esto se conseguirá reordenando las instrucciones de la
misma forma que se hacía en la planificación estática de los riesgos por
dependencias de datos. Si el compilador no pudiera encontrar ninguna
instrucción para ocupar los huecos libres dejados por la instrucción de salto,
rellenaría con instrucciones NOP. Para llevar a cabo este método, denominado
bifurcación retardada, tienen que ponerse de acuerdo en la forma de operar
el hardware y el compilador. En la figura 2.15 se muestra la

forma de operar de la bifurcación retardada: el hardware de la máquina debe

garantizar que la instrucción de bifurcación cambie el contador de programa
siempre en la misma etapa, tanto si el salto es efectivo como si no es; en la
citada figura se ha supuesto que esa etapa es la última, aunque no
necesariamente eso es siempre así.

Existen otros métodos más sofisticados para mejorar las bifurcaciones. Estos
métodos se basan en la predicción del destino de los saltos para las
instrucciones de bifurcación condicional. Esta predicción puede hacerse a nivel
estático (compilador) o a nivel dinámico (en ejecución). El problema de todos
los métodos de predicción es que, si ésta es incorrecta, hay que descartar las

43
instrucciones que hayan entrado en el cauce equivocadamente, y eso puede
acarrear una pérdida de rendimiento muy grande:

 La predicción estática se basa en los diferentes comportamientos de los

distintos tipos de instrucciones de bifurcación condicional. Concretamente
las bifurcaciones debidas a iteraciones se cumplen casi siempre y el
comportamiento de las bifurcaciones condicionales puede preverse por el
contexto (aunque no siempre). Basándose en estas consideraciones, el
diseñador de la máquina puede suministrar dos códigos de operación
para las bifurcaciones condicionales: uno para el salto probable y otro
para el salto no probable. Se puede mejorar este enfoque con la
predicción denominada semiestática, que consiste en pasar el programa,
compilado con predicción estática, por un simulador de la máquina para
que se estudie si el comportamiento de los saltos es el previsto o no; si
las predicciones fueran incorrectas, se podrían corregir los fallos de la
predicción estática.
 La predicción dinámica (Sussenguth, 1971) consiste en llevar una tabla
con la historia de cada salto. Esta tabla tendría la forma mostrada en la
figura 2.16. La información estadística de la tabla se iría actualizando
continuamente con cada ejecución de una instrucción de bifurcación
condicional, esto significa que al comienzo de la ejecución del programa
la estimación de la probabilidad de efectividad del salto no será muy
correcta; sin embargo, esa probabilidad se irá corrigiendo
automáticamente con el tiempo.

El problema de la predicción dinámica radica en que su gran complejidad,

en cuanto al hardware, no está justificada por su fiabilidad en la
predicción.

44
 XI. TAXONOMÍA DE FLYNN

En 1966 Michael Flynn propuso un mecanismo de clasificación de las

computadoras. El método de Flynn se basa en el número de instrucciones y de
la secuencia de datos que la computadora utiliza para procesar información.
Puede haber secuencias de instrucciones sencillas o múltiples y secuencias de
datos sencillas o múltiples. Esto da lugar a 4 tipos de computadoras, de las
cuales solamente dos son aplicables a las computadoras paralelas.

 Computadores SISD (Single Instruction Single Data): Un único flujo de

instrucciones procesa operandos y genera resultados definiendo un único
flujo de datos. Computadores monoprocesador.

Características:

 La CPU procesa únicamente una instrucción por cada ciclo de reloj

 Únicamente un dato es procesado en cada ciclo de reloj
 Es el modelo más antiguo de computadora y el más extendido

45
 Computadores SIMD (Single Instruction Multiple Data): Un único flujo de
instrucciones procesa operandos y genera resultados definiendo varios
flujos de datos. Computadores matriciales y vectoriales. Es una técnica
empleada para conseguir paralelismo a nivel de datos.

Los repertorios SIMD consisten en instrucciones que aplican una misma

operación sobre un conjunto más o menos grande de datos. Es una
organización en donde una única unidad de control común despacha las
instrucciones a diferentes unidades de procesamiento. Todas éstas
reciben la misma instrucción, pero operan sobre diferentes conjuntos de
datos. Es decir, la misma instrucción es ejecutada de manera sincronizada
por todas las unidades de procesamiento.

Características del modelo SIMD:

 Todas las unidades ejecutan la misma instrucción

 Cada unidad procesa un dato distinto
 Todas las unidades operan simultáneamente

46
 Computadores MIMD (Multiple Instruction Multiple Data): El computador
ejecuta varias secuencias o flujos distintos de instrucciones y cada uno de
ellos procesa operandos y genera resultados de forma que existen también
varios flujos, uno por cada flujo de instrucciones. Computadores
multiprocesadores y multicomputadores.

Es una técnica empleada para lograr paralelismo. Las máquinas que usan
MIMD tienen un número de procesadores que funcionan de manera
asíncrona e independiente. En cualquier momento, cualquier procesador
puede ejecutar diferentes instrucciones sobre distintos datos. La
arquitectura MIMD pueden utilizarse en una amplia gama de aplicaciones
como el diseño asistido, simulación, modelado y en interruptores. Las
computadoras MIMD pueden categorizarse por tener memoria compartida
o distribuida, clasificación que se basa en cómo el procesador MIMD
accede a la memoria. La memoria compartida de las máquinas puede estar
basada en buses, extensiones, o de tipo jerárquico. Las máquinas con
memoria distribuida pueden tener esquemas de interconexión en
hipercubo o malla.

Características del modelo MIMD:

 Cada unidad ejecuta una instrucción distinta

 Cada unidad procesa un dato distinto
 Todas las unidades operan simultáneamente

47
 Computadores MISD (Multiple Instruction Single Data): Se ejecutan varios
flujos de instrucciones, aunque todos actúan sobre el mismo flujo de datos.
Es un tipo de arquitectura computacional (particularmente de computación
paralela) donde muchas unidades funcionales realizan diferentes
operaciones en los mismos datos. Las arquitecturas segmentadas
pertenecen a este tipo, aunque en un extremo se podría llegar a decir que
los datos son diferentes después de ser procesados por cada etapa en el
pipeline, con lo cual no entraría en esta categoría.

Las máquinas tolerantes a fallos ejecutan la misma instrucción

redundantemente para detectar y corregir errores, utilizando task
replication, son consideradas de este tipo. No existen muchos ejemplos de
esta arquitectura dado que las técnicas más comunes de procesamiento
de datos en paralelo suelen ser más apropiadas para MIMD y SIMD.
Específicamente, facilitan el escalamiento y el uso de recursos
computacionales mejor que MISD.

Características del modelo MISD:

 Cada unidad ejecuta una instrucción distinta
 Cada unidad procesa el mismo dato
 Aplicación muy limitada en la vida real

48
 XII. TIPOS DE PROCESAMIENTO PARALELISMO SEGÚN LA TAXONOMÍA
DE FLYNN
Paralelismo de datos
Se utiliza cuando una misma función, instrucción, etc… se ejecuta repetidas
veces en paralelo sobre datos diferentes. Se utiliza en máquinas de la clase
MIMD.
Paralelismo funcional.
Se aprovecha cuando las funciones, bloques, instrucciones, etc… que
intervienen se ejecutan en paralelo. Existen distintos niveles de paralelismo
funcional.
 Nivel de instrucciones u operaciones. (ILP), las instrucciones de un
programa se ejecutan en paralelo, es de bajo nivel, se explota por el
hardware de forma transparente o por el compilador. Es el nivel de
granularidad más fina en la arquitectura de computadores la granularidad
es la cantidad de trabajo asociado a cada tipo de tarea candidata a la
paralelización.

49
 Nivel de bucle. Se ejecutan en paralelo distintas iteraciones de un bucle o
secuencias de instrucciones de un programa, la granularidad es fina-
media.
 Nivel de funciones. Los distintos procedimientos que constituyen un
programa se ejecutan simultáneamente, la granularidad es media.
 Nivel de programas. Se ejecutan en paralelo programas diferentes que
pueden ser o no de una misma aplicación, la granularidad es gruesa.

50