Download Arquitecturas paralelas…

CURSO DE TITULACIÓN 2003
COMPUTACION PARALELA;
ARQUITECTURAS Y
ALGORITMOS PARALELOS
I.S.C. Heberto Ferreira Medina (TECMOR 88-92)
Maestría en Ciencias Sección Computación (CINVESTAV, 94-96)
Especialidad Sistemas Distribuidos
COMPUTACION PARALELA; ARQUITECTURAS Y
ALGORITMOS PARALELOS
CONTENIDO DEL CURSO:
UNIDAD I. PROGRAMACION PARALELA.
1.1 INTRODUCCION.
1.2 TAXONOMIA DE FLYNN.
1.3 PROGRAMACION EN SISTEMAS PARALELOS.
UNIDAD II. ARQUITECTURAS PARALELAS.
2.1 MODELOS DE MÁQUINAS PARALELAS.
2.2 TECNOLOGIAS DE HARDWARE.
2.3 ARQUITECTURAS ESCALABLES.
UNIDAD III. SOFTWARE PARA LA PROGRAMACION PARALELA.
3.1 LENGUAJES Y COMPILADORES.
3.2 AMBIENTES DE DESARROLLO.
3.3 SOFTWARE PARA UNIX Y OTROS SISTEMAS OPERATIVOS.
UNIDAD IV. IMPLEMENTACION DE ALGORITMOS PARALELOS (PVM Y MPI).
4.1 ORDENAMIEMTO PARALELO.
4.2 BUSQUEDAS EN PARALELO.
4.3 PVM Y MPI.
Bibliografía







ADVANCED COMPUTER ARQUITECTURE; Paralelism, Scalability, Programmability.
Kai Hwang.
McGraw-Hill Series in Computer Science.
ARQUITECTURA DE COMPUTADORAS Y PROCESAMIENTO PARALELO.
Kai Hwang.
McGraw-Hill.
PARALELL COMPUTING; Theory and practice.
Michael J. Quinn.
McGraw-Hill.
PARALELL PROGRAMMING.
Sussan Ragsdale.
McGraw-Hill.
Análisis y diseño de algoritmos paralelos de ordenamiento y teoría de grafos con
arquitectura Hipercubo.
TESIS; Carlos Alberto Hernández Hernández.
CINVESTAV MEXICO.
PVM 3.4, USERS GUIDE AND REFERENCE MANUAL
Oak Ridge National Laboratory, Univeristy of Tennessee, Carnegie Mellon University,
Pittsburgh Supercomputing Center and Emory University. September, 1994.
MPI 2, USERS GUIDE AND REFERENCE MANUAL.
http://www.mpi-forum.org
http://www-unix.mcs.anl.gov/mpi
Evaluación del Curso …



Trabajos de Investigación (15 %)
Examen(s) teórico(s) (20 %)
Proyecto de programación:
Programa ejemplo de PVM en Linux/Windows (35 %)
 Programa ejemplo de MPI en un Cluster Linux (30 %)


Mínima aprobatoria 70
UNIDAD I. PROGRAMACION
PARALELA
1.1 INTRODUCCION
1.2 TAXONOMIA DE FLYNN
1.3 PROGRAMACION EN SISTEMAS
PARALELOS
1.1 Introducción
Historia
 CISC
 RISC
 RISC VS CISC
 Arquitecturas paralelas
 Clasificaciones
 Nuevas tecnologías

Historia ..

La capacidad de cómputo se doblara aproximadamente cada 18 meses.
Esta progresión de crecimiento exponencial: doblar la capacidad de los
microprocesadores cada año y medio a mitad de precio.
Gordon Moore
Cofundador de Intel

La consecuencia directa de esta Moore es que los precios bajan al
mismo tiempo que las prestaciones suben: la computadora que hoy vale
3.000 dólares costará la mitad al año siguiente y estará obsoleta en dos
años. En 26 años el número de transistores en un chip se ha
incrementado 3.200 veces.
Historia …

Desde los inicios de las arquitecturas de computadoras, un tema de mucho estudio es
como interconectar más de un procesador y que estos permitan aprovechar al máximo
su capacidad en paralelo.
[Michael J. Quinn, parallel computing]

En los 60´s la ILLIAC IV fue una de las primeras computadoras que intentó conectar
dos computadoras paralelas.
La universidad de Carnegie-Mellon en los 70´s desarrolló la C.mmp y Cm*.
En los 80´s la mayoría de las computadoras paralelas de la actualidad inician su carrera
hacia el paralelismo anhelado; nCube, Intel, Amtek, Cray, CM, IBM, NEC, MP, entre
otros …
En los 90´s nace PVM, una máquina virtual que pretende se usada en la mayoría de las
redes actuales, MPI es la utilización eficiente de las redes utilizando cluster´s.
En el desarrollo del paralelismo se fijaron objetivos a alcanzar:










Control del paralelismo
Escalabilidad
Procesamiento paralelo de datos
Desempeño en paralelo
Máxima aceleración (speedup)
Acceso a dispositivos de I/O en paralelo
Historia ...

Tendencia -> SD:
No es la panacea para resolver todos los problemas de interconexión en Red

Necesidad de Interconexión -> Evolución del Hardware

Aplicaciones GUI -> Evolución del Software
Inteligencia Artificial -> Evolución Hardware y Software
Evolución de los SO hacia Interfaces + Multimedia
El hardware móvil sin enchufes
El software( Inteligencia Artificial )= Inteligente + Toma
de decisiones
Herramientas CASE + Matemáticas aplicadas al diseño ->
Técnicas de Descripción Formal
Tecnología = Industria $$$






Evolución Procesador Intel
Processor Type
Year
N. Transistors
Package Type
Speeds
Other Details
4004
1971
2,300
4-bit word size and data bus; used in calculators.
8080
1974
6,000
8-bit word size and data bus; used in the first PC (the Altair) and in traffic
signal controllers.
8086
1978
29,000
16-bit word size and data bus; used in IBM PCs and XTs.
8088
1979
29,000
40-pin DIP
5 MHz to 8 MHz
(turbo)
80286
1982
134,000
square 68-pin grid array (PGA)
12 MHz to 20 MHz
Used in IBM ATs starting 1984. 16-bit word size and data bus. 16 MB of
addressable RAM.
80386 (DX, SX
Versions)
1985
275,000
132 pin PGA
16 MHz to 40 MHz
32-bit word size/data bus (DX). 32-bit word size, 16-bit data bus (SX). 4
GB of addressable RAM. Supports multitasking.
80486 DX
1989
1.6 million
168 pin PGA
25 MHz to 50 MHz
32-bit word size and data bus. 8 KB cache. 4GB of addressable RAM.
80486 DX2
1992
50 MHz to 80 MHz
Upgrade to the 486DX. Has a clock doubler to process data and
instructions at twice the clock speed.
80486 DX4
1994
75 MHz to 120 MHz
Uses clock tripler technology that enables the processor to operate at
three times clock speed.
Pentium
1993
3.3 million
273 pin PGA or 296 pin
staggered PGA
60 MHz to 200 MHz
and up
Uses superscaler processing. Includes SMM (System Management
Mode). 64-bit data bus, 32-bit address bus. Requires a cooling fan.
4 GB of addressable RAM.
Pentium Pro
1995
5.5 million
387-pin staggered PGA
(SPGA)
150 MHz to 200 MHz
and up
Scaleable (up to 4 processors) Uses Dynamic Execution to improve
processor efficiency. 64-bit word size/32-bit data bus size/36-bit
address bus.
Pentium MMX
1997
4.5 million
Pentium II
1997
7.5 million
16-bit word size; 8-bit data bus; also used in IBM PCs and XTs. 1 MB
addressable RAM.
Optimized for multimedia. 64-bit data bus/32-bit address bus.
242-pin SEC (single edge
contact)
233 MHz to 400 MHz
and up.
Scaleable (up to 2 processors). 64 GB of addressable RAM. 64-bit system
bus and cache bus, both with ECC (error correction code). 64-bit
word size/32-bit data bus/36-bit address bus.
Arquitectura CISC ...













La arquitectura CISC, se caracteriza por la complejidad en su
arquitectura y sus instrucciones, surge desde los 50`s
Modos de operación
Modos de direccionamiento
Ambiente de ejecución
Organización de la memoria
Registros de propósito general
Registros de segmentos
Registros de datos
Banderas
Llamado a procedimientos
Interrupciones
Conjunto de instrucciones
Manejo de I/O
Arquitectura RISC ...






La arquitectura RISC surge de un proyecto de la universidad de Berkeley
e IBM a finales de los 70`s
Poco después la universidad de Stanford desarrolla la arquitectura MIPS
a principios de los 80´s (Mayor énfasis en el Pipeline para acelerar
instrucciones)
Sus principales características son:
 Un solo ciclo de ejecución por instrucción, optimización de
instrucciones por ciclo de reloj
 Pipeline, ejecución de las instrucciones en pseudo-paralelismo
 Un gran número de registros, que permitan el Pipeline en la mayoría
de las instrucciones
Una de las grandes ventajas de estas arquitecturas son la sencillez de sus
instrucciones, donde existen pocos modos de direccionamiento
Las técnicas de Pipeline son muy estudiadas, de tal forma que en la
actualidad son muy eficientes y veloces.
El Pipeline opera por estados y cuya finalidad es desarrollar el mayor
número de estados por ciclo de instrucción , es decir más de una
instrucción a la vez.
Arquitectura RISC ...

El Pipeline se realiza en general en 5 pasos:









Carga de instrucciones desde la memoria
Lectura de registros y decodificación de instrucción
Ejecución de la instrucción y cálculo de la dirección
Escritura de resultados en un registro
Debido a la necesidad del Pipeline, los procesadores RISC operan más
de una instrucción por ciclo de reloj, esto ocasiona problemas de
dependencia de instrucciones, esto ocurre cuando el resultado de una
instrucción es utilizado por la siguiente.
Los procesadores MIPS tienen implementados algoritmos que permiten
el reordenamiento de instrucciones para evitar la dependencia de
instrucciones.
Una de las técnicas es la predicción de resultados y su reordenamiento.
Aún con todo y estas técnicas existen algunas instrucciones que tienen
una dependencia tal que no es posible reordenarlas y existen ciclos de
reloj en los cuales no se puede ejecutar el Pipeline.
Los métodos que utilizan los procesadores MIPS pueden ejecutar hasta
el 90 % de las dependencias y resolverlas correctamente.
RISC vs. CISC

En realidad es difícil de comparar ambas arquitecturas puesto que tienen objetivos
diferentes, una apuesta por la sencillez del hardware (RISC) y la otra por la
aceleración en instrucciones (CISC).:
CISC
RISC
Énfasis en el Hardware (Velocidad)
Énfasis en el Software (Sencillez y rapidez
en el Pipeline)
Incluye instrucciones complejas multi-reloj
Instrucciones con reloj simple
Instrucciones complejas (Más de 1000)
Instrucciones sencillas (Menos de 100)
Instrucciones que trabajan de memoria a
memoria
Instrucciones que trabajan de registro a
registro
Carga y almacenamiento incorporados en
la misma instrucción
La carga y el almacenamiento son
instrucciones independientes
El tamaño del código es pequeño
El tamaño del código es muy grande
Muchos ciclos de reloj por segundo
Pocos ciclos de reloj por segundo
Pocos registros para almacenar los
resultados
Muchos registros para almacenar
resultados
Alto costo de producción
Bajo costo de producción
RISC vs. CISC ...

La forma de medir el desempeño de una computadora sin importar su arquitectura
es:

En la actualidad se han visto las ventajas de ambas arquitecturas y por tal motivo la
convergencia RISC-CISC es cada vez más vista en los nuevos procesadores, los
CISC incluyen nuevas técnicas de Pipeline para acelerar el numero de instrucciones
por segundo y RISC incluye cada vez más instrucciones para acelerar aún mas los
programas en hardware.
Ventas de procesadores RISC al 2001
Características
1994
1995
1996
1997
1998
1999
2000
2001
ARM/Strong
ARM
32 bits, 75% del mercado, utilizado en
automóviles, Dispositivos I/O, Palm, etc
2,170
2,100
4,200
9,800
50,400
152,000
414,000
402,000
MIPS Rxx00
32 y 64 bits, consolas, cable modem, etc
3,254
5,500
19,200
48,000
53,200
57,000
62,800
62,000
Hitachi SH
32 bits, bluetooth, Dispositivos I/O, etc
2,800
14,000
18,300
23,800
26,000
33,000
50,000
45,000
POWER/Po
werPC
Motorola, 32 y 64 bits, utilizado en PC´s,
workstation, telecomunicaciones, etc --
2,090
3,300
4,300
3,800
6,800
8,300
18,800
23,000
30,49
9
33,830
58,480
98,220
149,08
0
262,820
556,800
538,860
Total
Arquitecturas paralelas




Un tema complicado era el como conectar los componentes de la arquitectura de tal
forma que permitiera al máximo la ejecución de instrucciones en paralelo.
El modelo PRAM, fue uno de las primeras arquitecturas que fueron probadas con éxito
y permite el paralelismo, esta consiste de una unidad de control, memoria global y un
conjunto ilimitado de procesadores.
Uno de los problemas clásicos es la forma de acceder a la memoria:
Existen varios modelos para controlar la concurrencia:
 EREW (Exclusive Read Exclusive Write) no hay conflictos.
 CREW (Concurrent Read Exclusive Write).
 CRCW(Concurrent Read Concurrent Write), existen 3 modelos:
 Común; todos los procesadores escriben concurrentemente en la misma
dirección global pero el mismo valor.
 Arbitrario; si hay varios que desean acceder uno es declarado ganador
 Prioridad; el procesador con mayor prioridad es que accesa
Arquitectura ...
TOP 500 DEL SUPERCOMPUTO:
Rank
Manufacturer
Computer/Procs
Rmax
Rpea
Installation Site
Country/Year
k
1
NEC
Earth-Simulator/ 5120
35860.00
409
60.
00
Earth Simulator Center
Japan/2002
2
Hewlett-Packard
ASCI Q - AlphaServer SC ES45/1.25 GHz/ 4096
7727.00
102
40.
00
Los Alamos National Laboratory
USA/2002
3
Hewlett-Packard
ASCI Q - AlphaServer SC ES45/1.25 GHz/ 4096
7727.00
102
40.
00
Los Alamos National Laboratory
USA/2002
4
IBM
7226.00
122
88.
00
Lawrence Livermore National Laboratory
USA/2000
ASCI White, SP Power3 375 MHz/ 8192
5
Linux NetworX
MCR Linux Cluster Xeon 2.4 GHz - Quadrics/ 2304
5694.00
110
60.
00
Lawrence Livermore National Laboratory
USA/2002
6
Hewlett-Packard
AlphaServer SC ES45/1 GHz/ 3016
4463.00
603
2.0
0
Pittsburgh Supercomputing Center
USA/2001
7
Hewlett-Packard
AlphaServer
SC ES45/1 GHz/ 2560
169
IBM
Netfinity Cluster PIII 1.4 GHz - Eth/ 1024
3980.00
512
0.0
0
Commissariat a l'Energie Atomique (CEA)
France/2001
366.00
Pemex Gas
3337.00
675
Forecast Systems Laboratory - NOAA
USA/2002
8
HPTi
Aspen Systems, Dual Xeon 2.2 GHz - Myrinet2000/ 1536
1433.00
Mexico/2002
Arquitecturas paralelas…

En general la mayoría de las arquitecturas siguen tres importantes modelos de la computación
paralela:




Los criterios para medir la eficiencia y la implementación de los algoritmos en una arquitectura
paralela son:





Arreglo de procesadores. Modelo PRAM clásico.
Multiprocesadores. Diferente modelos de interconexión.
Multicomputadoras. Cluster e interconexión utilizando dispositivos I/O
Diámetro (D): El diámetro es la distancia más grande entre 2 nodos. El diámetro más bajo es menor, es
simplifica los requerimientos de comunicación entre procesadores.
Ancho de bisección de una red (AB): Es el mínimo número de bordes que pueden ser eliminados en
orden para dividir un arreglo de procesadores en dos mitades. Una bisección alta es mejor porque los
algoritmos requieren un gran movimiento de datos y este puede dividirse entre el número de conexiones
posible (1a. instancia).
Número de bordes por nodo (NB). Es mejor si el número es constante independientemente del tamaño
de la red.
Máxima longitud de borde (MLB). Por razones de escalabilidad es mejor si el número de nodos y
bordes pueden ser representados en un espacio tridimensional independientemente del tamaño.
Los tipos clásicos de organización son:







Interconexión en malla (mesh network).
Árbol binario.
Hiper-árbol.
Pirámide,
Mariposa.
Hiper-cubo.
Otras
Clasificación de Arquitecturas ...

Kai Hwang, presenta tres esquemas de clasificación:

Taxonomía de Flynn(1966)
- Se basa en la multiplicidad de los flujos de instrucciones y datos
en un sistema.

Taxonomía de Feng (1972)
- Se basa en la confrontación del procesamiento serie frente al
procesamiento paralelo

Taxonomía de Händler (1977)
- Se determina por el grado de paralelismo y encauzamiento en
diferentes niveles y subsistemas
 Otras
taxonomias o clasificaciones: Shore´s, Hockney &
Jessophe´s y Towards
Taxonomía de Flynn ...


Simple flujo de Instrucciones – Simple Flujo de datos (SISD).
Máquinas secuénciales; CISC y RISC, 1 procesador.
Simple flujo de Instrucciones – Múltiple Flujo de Datos (SIMD).
Multiprocesadores, CISC o RISC.
Taxonomía de Flynn ...

Múltiple flujo de Instrucciones – Simple Flujo de Datos (MISD). No
aplicado.

Múltiple flujo de Instrucciones – Múltiple Flujo de Datos (MIMD).
Multiprocesadores, Clusters, Transputer.
Taxonomía de Feng …

Tse-yun-Feng, sugiere el grado de paralelismo como criterio de
clasificación.
Maximo grado de paralelismo ( P ) = número máximo de dígitos binarios que
pueden ser procesados en una unidad de
tiempo

Grado medio de paralelismo ( Pm ) y tasa de utilización ( µ ) de un
sistema en T ciclos:
Donde Pi es el No. de bits que
puede ser procesados en el i-esimo
ciclo del procesador, para T ciclos.

Tasa de utilización
en T ciclos
Se puede clasificar a la computadoras actuales de acuerdo a este
criterio como:




Palabra-serie y bit-serie (PSBS). n=m=1, primera generación de computadoras.
Palabra-paralelo y bit-serie (PPBS). n=1, m>1, procesamiento por sección de
bits (procesa una sección de m bits cada vez), no usado.
Palabra-serie y bit-paralelo (PSBP).n>1, m=1, procesamiento por sección de
palabra (procesa una palabra de n bits a la vez), computadoras actuales.
Palabra-paralelo y bit-paralelo (PPBP). n>1, m>1, procesamiento totalmente
paralelo (se procesa una matriz de n*m bits a la vez), multiprocesadores y
multicomputadoras (cluster´s).
Taxonomía de Feng …

Si la potencia de
computación esta
totalmente utilizada
(paralelismo máximo),
tenemos que Pi = P para
todo i y µ = 1 con
utilización al 100%.

Una sección de bits es una
cadena de bits, uno por cada
una de las palabras sobre las
que se opera en paralelo.
Clasificación de Händler

Wolfgang Händler ha propuesto un esquema donde se considera el
procesamiento paralelo encauzado en tres niveles de subsistemas:




UCP (Unidad Central de procesamiento)
UAL (Unidad Aritmética Lógica)
El circuito a nivel Bit (CNB), utilizado para realizar operaciones a nivel bit en la
UAL.
Un sistema computador (C )puede caracterizarse por una triada:
C = < K x K’, D x D’, W x W’ > donde:
K = Es el número procesadores
K’ = Número de procesadores que puede encauzarse (pipelined)
D = Es el número de ALU bajo el control de un CPU
D’ = Número de ALU´s que pueden ser encauzadas (pipelined)
W = Longitud de palabra de una UAL o un Elemento de Proceso (EP)
W’ = El número de segmentos en pipeline en todas las ALU´s o EP´s
Clasificación de Händler y Otras …

Por ejemplo para la Cray-1: Es un procesador de 64-bit simple con 12
ALU, 8 de las cuales pueden trabajar en pipeline. Diferentes unidades
funcionales tienen de 1 a 14 segmentos los cuales pueden trabajas en
pipeline.
CRAY-1 = < 1, 12 x 8, 64 x ( 1~14) >

Otras clasificaciones que se pueden encontrar en la literatura son:
Taxonomía de Shore´s (1973). Basada en la estructura y el número de
unidades funcionales en la computadora. Se divide en 6 categorías.
Taxonomía estructural de Hockney y Jesshope´s. Se basa en la notación
llamada “Estilo de Notación Estructural Algebraica (ASN)”, es muy
compleja.


C(Cray-1) = Iv12 [ 12Ep12 - 16M50 ] r; 12Ep = {3Fp64,9B}

Existe una nomenclatura que pretende ser más descriptiva y se basa en:
multiplicidad del procesador, tamaño de grano, topología y control de
multiplicidad. Computadora
Nueva Clasificación Flynn
IBMPC
ZL
SISD
Nuevas Tecnologías ..


Revisar nuevas tecnologías de arquitectura de
computadoras en Internet
Revisar PVM y MPI implementación y programación
en Linux.