INTRODUCCION : Computadores
paralelas, programación paralela
y prestaciones
1. ARQUITECTURA PARALELA Y NIVELES DE
PARALELISMO
2. MOTIVACIÓN AL ESTUDIO DE
COMPUTADORES PARALELOS
3. ESPACIO DE DISEÑO CLASIFICACIÓN Y
ESTRUCTURA GENERAL
4. PROGRAMACIÓN PARALELA
5. PRESTACIONES EN COMPUTADORES
PARALELOS
7.1. Arquitecturas paralelas y
niveles de paralelismo
7.1.1. Niveles y tipos de paralelismo.
implementados en la arquitectura.
7.1.2. Niveles y tipos de paralelismo implícito en
una aplicación.
7.1.3. Unidades de ejecución: instrucciones,
hebras , procesos.
7.1.4. Relación entre paralelismo implícito,
explicito y arquitecturas paralelas.
7.1.5. Detección, utilización, implementación y
extracción del paralelismo.
7.1.1. Niveles y tipos de
paralelismo.
El computador es un sistema complejo en su vertiente
hardware y software.
Los niveles de hardware podrían ser: componentes, circuito
electrónico, lógica digital, RT y sistema del computador.
Por encima estaría el nivel del S.O. que actúa como interfaz
entre el software y hardware.
Para incrementar las prestaciones de un sistema se
aprovecha el paralelismo en un sistema explicito o implícito
en las entradas.
Hay dos alternativas para implementar paralelismo en un
sistema y aprovechar así el paralelismo en las entradas
componentes del sistema o segmentar (componentes del
procesador) el uso de componentes.
7.1.2. Niveles y tipos de paralelismo
implícito en una aplicación.
Comercialmente disponemos de computadoras
que implementan paralelismo en varios niveles de
arquitectura.
En una aplicación se distingue distintos niveles de
paralelismo que se aprovechan en diferentes
niveles del computador.
Se puede clasificar los niveles de paralelismo de
una aplicación en función del nivel de abstracción
dentro del código secuencial en que el podemos
encontrar el paralelismo.
Con el código secuencial, nos referimos al código
escrito en lenguaje imperativo, que es mas próximo
a la arquitectura de flujo de control frente a la
arquitectura de datos , reducción , etc.
Se puede considerar que un programa esta compuesto por
diferentes funciones y a la vez pueden estar compuesta por
bucles y estos se basan por operaciones.
Por encima esta el nivel de programas en el que podemos
encontrar programas que forman parte de las mismas o distintas
aplicaciones, o que pueden o no tener los mismos usuarios.
En general el paralelismo esta implícito en mayor o menor
grado en la descripción de una aplicación(diagrama de flujo
de control, algún código de alto nivel, código ensamblador ,
etc.)
Una descripción de una aplicación facilita la identificación de
este paralelismo tanto a una herramienta automática o hacia
un programador.
Dentro del código secuencial se puede encontrar paralelismo
implícito en los siguientes niveles de abstracción.
Los diferentes programas que
intervienen en una aplicación o
en diferentes aplicaciones se
pueden ejecutar en paralelo es
probable que exista
dependencia entre ellos.
En un nivel de abstracción mas
bajo, puede que esta
constituido por funciones y se
pueden ejecutar en paralelo
siempre que no haya
dependencias. Inevitables
como dependencias de datos
verdaderos
Se extrae el paralelismo disponible entre
Puede estar basada en la ejecución de operaciones, las operaciones
uno o mas bucles y se puede ejecutar independientes se pueden ejecutar en
varias veces, en cada iteración se paralelo. Los procesadores de propósito
completa una tarea, se puede ejecutar especifico y general. Se encuentra
en paralelo siempre que se eliminen los
instrucciones con varias operaciones y se
problemas derivados de las
dependencias verdaderas para aplican en secuencia al mismo flujo de
detectar se analiza las entradas y entrada.
salidas de la iteración del bucle.
7.1.3. Unidades de ejecución:
instrucciones, hebras , procesos.
El hardware se encarga de gestionar la ejecución de
las instrucciones. En un nivel superior el sistema
operativo se encarga de gestionar la ejecución de
unidades de mayor granularidad, procesos y hebras.
Para cada proceso en ejecución tiene su propia
asignación de memoria. Los sistemas operativos
multihebra permite que cada proceso componga de
una o varias hebras.
En la siguiente figura se vera la diferencia entre hebras
y procesos.
Una hebra tiene su propia fila y
contenido de registros entre
ellos IP que almacena la
instrucción a ejecutar de la
hebra, pero comparte el
código las variables globales y
otros recursos con las hebras
del mismo proceso. Estas
características hacen que las
hebras se puedan crear y
destruir en un menor tiempo
que los procesos y que la
comunicación, sincronización y
comunicación entre hebras
sea mas rápidas que entre
procesos y permite que tengan
menor granularidad en
elproceso.
Paralelismo funcional se puede detectar en distintos
niveles de un código secuencial.
Paralelismo de tareas: Se encuentra extrayendo,
generalmente de la definición de la aplicación, en la
estructura lógica de funciones de la aplicación. En esta
estructura los bloques son funciones y las conexiones
entre ellas reflejan el flujo de datos, analizando se
puede encontrar paralelismo de funciones.
Paralelismo de datos: Por su parte, se encuentra
implícito en las operaciones con estructuras de datos.
Se puede extraer de una representación matemática,
las operaciones vectoriales y matriciales engloban
múltiples operaciones con datos escalares que se
realiza en paralelo, estas operaciones se implementan
mediante bucles. Por la tanto en el P. de datos esta
relacionado con el P. a nivel bucles. Se puede extraer
de bucles analizando las operaciones con la misma
estructura de datos en diferentes iteraciones de bucle.
En la década de los noventa se han incorporado
unidades funcionales que implementan el P. de datos
usando procesamiento SIMD.
Tanto los procesadores específicos como(TriMedia de
Philips,TMS320C6xxx) como procesadores a propósito
general(MMX,SSE y SSE2 de Intel, VIS de Sun,3Dnow de
AMD o Altivec para PowerPC),
Las instrucciones multimedia aceleran el procesamiento
vectorial aplicando la misma instrucción en paralelo a
múltiples datos dentro de un registro.
Los procesadores que incluyeron alguna instrucción
SIMD Fueron el i860 de Intel (1889), el 88110 de
Motorola(1993) y el PA-7100LCde HP(1994),etc.
El paralelismo puede clasificarse en función de la
granularidad o magnitud de tarea y es candidata a la
paralelizacion que suele corresponder a los diferentes
niveles de paralelismo.
El grano mas pequeño(grano fino) generalmente
asocia al paralelismo entre operaciones o
instrucciones y el grano grueso, al paralelismo entre
programas.
Entre ambos extremos tenemos al grano medio,
asociado a los bloques lógicos de la aplicación.
7.1.3. Unidades de ejecución:
Instrucciones, hebras y procesos
El hardware se encarga de gestionar la ejecución
de las instrucciones.
A nivel superior S.O. se encarga de gestionar las
unidades de mayor granulidad, procesos y las
hebras.
Cada proceso en ejecución tiene su propia
asignación de memoria.
Los S.O. multihebras permite que cada proceso se
componga de una o varias hebras.
En la siguiente figura ilustra las diferencias entre
hebras y procesos.
7.1.4. Relación entre paralelismo implícito,
explicito y arquitecturas paralelas.
Se relacionan los distintos niveles que se encuentra el P. implícito en el
código. El P. entre programas se utiliza a nivel de procesos.
En el momento que se ejecuta un programa se crea el proceso asociado al programa. El
P. entre funciones se puede extraer para utiliza a nivel de procesos o de hebras. El P.
dentro de bucle también se extrae
Se puede aumentar la granularidad asociado un mayor número de iteraciones del ciclo
a cada unidad a ejecutar en paralelo. El P. en un bucle también puede hacerse
explicito dentro una instrucción vectorial para que sea aprovechado por arquitecturas
SIMD o vectoriales
El P. entre operaciones se puede aprovechar en arquitecturas con
paralelismo a nivel de instrucción ejecutando en paralelo las instrucciones
asociadas a estas operaciones independientes.
7.1.5. Detección, utilización, implementación y
extracción del paralelismo.
Se relaciona el agente que extrae el P. implícito en los diferentes niveles de la aplicación, con los niveles que se
hacen explícitos y las arquitecturas que lo aprovechan.
Los procesadores ILP superescalares o segmentados la arquitectura extraer P. eliminan dependencias de datos
falsas entre instrucciones eliminan dependencias de datos, control y recursos, la arquitectura extrae paralelismo
implícito en las entradas de tiempo de ejecución (dinámicamente) el grado de P. de las instrucciones se puede
incrementar con ayuda de un compilador o de un programador.
Podemos definir como grado de P. de un conjunto de entradas a un sistema, como el máximo número de entradas
del conjunto que se puede ejecutar en P. Debido a las dependencias de entradas este grado máximo será inferior
al numero de entradas en conjunto.
Para los procesadores las entradas serán instrucciones . En la arquitectura ILPVLIW la arquitectura que se va
aprovechar esta ya en explicito en las entradas. L as instrucciones que se van a ejecutar en paralelo se captan
juntas de memoria
El compilador es el que extrae P. para arquitecturas VILW La ayuda del programador puede incrementar en
concurrencia entre instrucciones aprovechado por arquitectura.
Hay compiladores que extraen el paralelismo a nivel de
bucles o también lo hacen implícito a nivel de hebra esto
dentro de una instrucción para que se pueda aprovechar en
un arquitectura SIMD(Lacey,2003), [Intel OM] o vectoriales.
Aun es difícil para un compilador extraer(localizar)
paralelismo a nivel de la función sin ayuda del programador.
El usuario como el programador puede extraer el paralelismo
implícito en un bucle entre funciones debido a hebras o
procesos.
La distribución de las tareas independientes entre hebras o
procesos dependerán de la granularidad de las unidades del
código independiente.
De la posibilidad que ofrezca la herramienta para
programación paralela disponible de definir hebras o
proceso.
De la arquitectura disponible para aprovechar el paralelismo
multihebra, multiprocesador, multicomputador y del sistema
operativo
