capI-Introduccion

Vista previa del material en texto

2 I. Introducción 
I.1. EL PROCESAMIENTO PARALELO 
 
El procesamiento paralelo ha provocado un tremendo impacto en muchas áreas donde las 
aplicaciones computacionales tienen cabida. Un gran número de aplicaciones 
computacionales en la ciencia, ingeniería, comercio o medicina requieren de una alta 
velocidad de cálculo para resolver problemas de visualización, bases de datos distribuidas, 
simulaciones, predicciones científicas, etc. 
 
 Estas aplicaciones envuelven procesamiento de datos o ejecución de un largo número de 
iteraciones de cálculo. El procesamiento paralelo es uno de los enfoques computacionales 
que hoy en día puede ayudarnos ha procesar éstos cálculos de una manera más viable. 
Este incluye el estudio de arquitecturas paralelas y algoritmos paralelos. 
 
Las tecnologías del procesamiento paralelo son actualmente explotadas de forma 
comercial, principalmente para el trabajo en el desarrollo de herramientas y ambientes. El 
desarrollo de esta área en las redes de computadoras ha dado lugar a la llamada 
Computación Heterogénea [Bacci et al.99] (que proporciona un ambiente donde la 
aplicación paralela es ejecutada utilizando diferentes computadoras secuenciales y 
paralelas en las cuales la comunicación se lleva a cabo a través de una red inteligente. Este 
enfoque proporciona alto rendimiento). 
 
Existen muchos factores que contribuyen al rendimiento de un sistema paralelo, entre ellos 
están la integración entre procesos, es decir, el tener múltiples procesos activos 
simultáneos resolviendo un problema dado; la arquitectura del hardware (arquitectura 
superescalar, de vector o pipelinizada, etc.), y enfoques de programación paralela; 
propuestas de programación paralela para comunicar y sincronizar los procesos. 
 
 
 
I.2. ARQUITECTURA DE COMPUTADORAS 
 
La arquitectura de computadoras es el estudio de la organización e interconexión de los 
componentes que integran un sistema computacional. La computadora puede ser 
constituida a partir de la construcción de bloques tales como memorias, unidades 
aritméticas, elementos de procesamiento y buses. Con estos elementos se pueden 
conformar un número indeterminado de diferentes tipos de máquinas computacionales, 
desde las más pequeñas o básicas hasta las llamadas supercomputadoras. El 
comportamiento funcional de los componentes de las diferentes computadoras son 
similares unos con otros. Por ejemplo, el sistema de memoria realiza funciones de 
almacenamiento, la unidad de procesamiento central lleva a cabo operaciones, y las 
interfaces de entrada y salida transfieren datos desde un procesador a los dispositivos 
apropiados. 
Las mayores diferencias sobre los distintos tipos de computadoras estriban en la forma en 
que sus módulos son conectados entre sí, las características de rendimiento de dichos 
módulos, y el método mediante el cual un sistema computacional es controlado por sus 
operaciones. Los dos elementos principales de un sistema computacional convencional son 
el procesador y la memoria. 
 I. Introducción 3
Un procesador manipula datos almacenados en la memoria mediante instrucciones. Las 
instrucciones son colocadas en los módulos de memoria y el flujo siempre va de la 
memoria al procesador. El movimiento de datos en un sistema es bidireccional; pues estos 
pueden ser leídos desde, o escritos hacia los módulos de memoria. La figura I.1 representa 
la interconexión memoria-procesador conocida como el modelo de computación Von 
Newmann. 
 
 
 
 
 
 
 
 
 
Figura I.1. Interconexión Memoria-Procesador 
 
Una extensión natural del modelo Von Neumann es la llamada Red de Computadoras. En 
este esquema, cada nodo en la red es una computadora en sí misma, la cual puede ser 
considerablemente compleja y operar completamente de forma autónoma respecto a las 
otras computadoras que integran la red. Además, una red de computadoras puede ser 
geográficamente distribuida. 
 
En adición a esta extensión natural del modelo Von Neumann, es posible tomar un 
enfoque más fundamental y diseñar nuevos modelos computacionales exclusivamente 
para el procesamiento paralelo. El número de instrucciones leídas y datos manipulados 
simultáneamente por el procesador forman la base para la clasificación de arquitecturas 
que a continuación de detalla. 
 
 
I.2.1. Clasificación de las arquitecturas de computadoras 
 
Michael Flynn ha clasificado las arquitecturas de computadoras mediante una variedad de 
características que incluyen el número de procesadores, número de programas que 
pueden ser ejecutados por dichos procesadores y la estructura de memoria. La 
clasificación de Flynn es un buen método para definir la taxonomía de las arquitecturas de 
computadoras aunque existen algunas otras taxonomías propuestas; tales como las de 
Dasgupta, Hockney , Skillicorn y Bell. Treleaven, Brownbridge y Hopking [Roosta99], 
sugieren que las computadoras convencionales pueden ser analizadas bajo dos puntos de 
vista: 
 
 
• El mecanismo de control, el cual define el orden de ejecución 
• El mecanismo de datos, que define la forma en que los operandos son utilizados 
 
 
Procesador
 
Memoria
 
Instrucción 
Datos 
 4 I. Introducción 
La clasificación de Flynn incluye las siguientes categorías: 
 
1. SISD - Convencional. 
 
2. SIMD - datos paralelos, vector computing. 
 
3. MISD - arrays sistólicos. 
 
4. MIMD – Muy general, múltiples enfoques. 
 
 
1. SISD (Single Instruction Stream, Single Data Stream) 
Las computadoras SISD tienen un CPU que ejecutan una instrucción a la vez (single, 
instruction stream) e instancía un item de datos a la vez (single data stream). La figura I.2.2 
muestra la estructura general de la arquitectura SISD. 
 
 
Figura I.2. Modelo de una Arquitectura SISD 
 
Todas las computadoras SISD utilizan un registro simple llamado el contador del programa, 
el cual lleva el conteo de la ejecución serial de las instrucciones. Como cada instrucción es 
fetch-eada desde la memoria, el contador del programa es actualizado para direccionar a 
la siguiente instrucción ha ser fetch-eada y ejecutada; lo que resulta ser una orden serial de 
ejecución. 
 
2 Las figuras I.2 ha I.7 de esta sección han sido tomadas de http://www.dgs.monash.edu.au/~rajkumar y 
traducidas al español. 
 
 
 
La Arquitectura SISD 
Procesador Datos de 
Entrada 
Datos de 
Salida 
In
str
uc
ci
on
es
 I. Introducción 5
2. SIMD (Single Instruction Stream, Multiple Data Stream) 
Las máquinas SIMD tienen una unidad de control que ejecutan un flujo de instrucción 
simple, pero tienen más de un elemento procesando. La unidad de control genera las 
señales de control para todos los elementos que se están procesando, la cual ejecuta la 
misma operación en diferentes ítems de datos (esto es, multiple data stream). En otras 
palabras, muchos elementos de procesamiento separados son invocados mediante una 
simple unidad de control. Estas computadoras son utilizadas frecuentemente para 
problemas que tienen un alto grado de paralelismo de grano pequeño (small-grain). 
Algunas computadoras SIMD popularmente comerciales son la ILLIAC IV, la DAP o la 
CM-2 [Roosta99]. Las computadoras SIMD pueden soportar vectores de procesamiento, 
los cuales pueden ser acompañados por vectores de elementos para procesado individual 
de elementos dentro de cálculos concurrentes. La figura I.3. representa una vista general 
de una arquitectura SIMD. 
 
 
Figura I.3. Modelo de una Arquitectura SIMD 
 
 
3. MISD (Multiple Instruction Stream, Single Data Stream) 
Las máquinas de esta categoría pueden ejecutar varios programas distintos con el mismo 
item de datos. Esto implica que algunas instrucciones son operadas con una sola pieza de 
datos. La arquitectura puede ser ilustrada en dos categorías: 
 
a) Una clase de máquinas que requieren de distintas unidades de procesamiento que 
pueden recibir distintas instrucciones para ser ejecutadas con los mismos datos. Sin 
embargo, este tipo de arquitecturases más un ejercicio intelectual que una 
configuración práctica. 
La arquitectura SIMD 
Flujo de 
Instrucción 
Procesador 
A 
Flujo de 
Entrada de 
Datos A 
Flujo de 
Salida de 
Datos A
Flujo de 
Entrada de 
Datos B 
Flujo de 
Entrada de 
Datos C 
Procesador 
B 
Procesador 
C 
Flujo de 
Salida de 
Datos B
Flujo de 
Salida de 
Datos C
 6 I. Introducción 
 
b) Una clase de máquinas tales que el flujo de datos circula sobre una serie de 
elementos de procesamiento. Las arquitecturas pipeline tales como los arrays 
sistólicos entran dentro de este grupo de máquinas. Las arquitecturas pipeline 
realizan un vector de procesamiento sobre una serie de etapas, cada una de las 
cuales lleva a cabo una función particular y produce un resultado inmediato. La 
razón por la que estas arquitecturas son agrupadas dentro de las máquinas MISD 
es que los elementos de un vector pueden tener el mismo grupo de datos, y todas 
las etapas del pipeline representen múltiples instrucciones que estén siendo 
aplicadas al vector. La figura I.4 representa la estructura general de una 
arquitectura MISD. 
 
 
Figura I.4. Modelo de una Arquitectura MISD 
 
4. MIMD (Multiple Instruction Stream, Multiple Data Stream) 
Las máquinas MIMD son llamadas multiprocesadores. Estas tienen más de un procesador y 
cada uno puede ejecutar un programa diferente (multiple instruction stream) con 
múltiples flujos de datos. En muchos sistemas MIMD, cada procesador tiene acceso a una 
memoria global, la cual puede reducir el tiempo de comunicación de los procesadores, tal 
como se ilustra en la figura I.5. 
 
La Arquitectura MISD 
Flujo de 
Entrada 
de Datos 
Procesador 
A 
Flujo de 
Instrucciones A 
Flujo de 
Salida de 
Datos 
Flujo de 
Instrucciones B 
Flujo de 
Instrucciones C 
Procesador 
B 
Procesador 
C 
 I. Introducción 7
 
Figura I.5. Modelo de memoria compartida en la arquitectura MIMD 
 
Además cada procesador posee una memoria privada (ver figura I.6). Muchas de las 
arquitecturas MIMD son utilizadas para paralelismo de grano-medio y grano-largo. 
 
 
Figura I.6. Modelo de memoria distribuida en la arquitectura MIMD 
 
 
Memoria Compartida en máquinas MIMD
 
 
 
 
Sistema de Memoria Global
Procesador 
A 
Procesador
B 
Procesador
C 
 
 
B 
U 
S 
 
D 
E 
M
E
M
O
R 
 I 
A 
B 
U 
S 
 
D 
E 
B 
U 
S 
 
D 
E 
M
E
M
O
R 
 I 
A 
M
E
M
O
R 
 I 
A 
Memoria Distribuida en máquinas MIMD 
Procesador 
A 
Procesador
B 
Procesador
C 
Memoria 
del 
Sistema 
A 
Memoria 
del 
Sistema 
B 
Memoria 
del 
Sistema 
C 
 
 
B 
U 
S 
 
D 
E 
M
E
M
O
R 
 I 
A 
 
 
B 
U 
S 
 
D 
E 
M
E
M
O
R 
 I 
A 
 
 
B 
U 
S 
 
D 
E 
M
E
M
O
R 
 I 
A 
 8 I. Introducción 
En las arquitecturas paralelas MIMD actuales, el número de procesadores es más pequeño 
que en los sistemas SIMD. Las computadoras MIMD son las más complejas, pero ofrecen 
grandes promesas para obtener eficiencia acompañada del procesamiento concurrente. 
Algunas computadoras MIMD comerciales son, la BBN Butterfly, la serie Alliant FX, la 
serie iPSC de Intel, y la Ultracomputadora de la universidad de New Cork [Roosta99]. La 
figura I.7 representa la estructura general de una arquitectura MIMD. 
 
 
Figura I.7. Modelo de una arquitectura MIMD 
 
I.2.2. ARQUITECTURAS PARALELAS 
 
En la sección anterior, la clasificación de Flynn divide a las arquitecturas paralelas en dos 
familias importantes: la familia de las computadoras SIMD y la familia de las 
computadoras MIMD. La figura I.8 muestra una taxonomía que representa algunas de las 
características de las arquitecturas paralelas. En esta sección se hablará entonces de las 
arquitecturas paralelas SIMD y MIMD. 
 
 
 
 
 
 
 
 
 
 
 
 
 
La Arquitectura MIMD 
Procesador
A 
Procesador
B 
Procesador
C 
Flujo de 
Entrada de 
Datos A 
Flujo de 
Instrucciones
A 
Flujo de 
Instrucciones
B 
Flujo de 
Instrucciones
C 
Flujo de 
Entrada de 
Datos B 
Flujo de 
Entrada de 
Datos C 
Flujo de 
Salida de 
Datos A 
Flujo de 
Salida de 
Datos B 
Flujo de 
Salida de 
Datos C 
 I. Introducción 9
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura I.8. Taxonomía de las arquitecturas de procesamiento paralelo 
 
 
I.2.2.1. Arquitecturas SIMD 
 
En una máquina SIMD, varios elementos procesados se supervisan por una unidad de 
control. Todas las unidades de procesamiento reciben la misma instrucción desde la 
unidad de control, pero operan con diferentes conjuntos de datos, los cuales provienen de 
distintos flujos de datos (ver figura I.3). Las características principales de este tipo de 
máquinas paralelas son: 
 
• Distribuyen el procesamiento sobre un larga cantidad de hardware 
• Operan concurrentemente con muchos elementos de datos diferentes 
• Realizan el mismo cálculo en todos los elementos de datos 
 
Así, cada unidad de procesamiento ejecuta la misma instrucción al mismo tiempo, y los 
procesadores operan de manera síncrona. El potencial de speedup o aceleración de las 
máquinas SIMD es proporcional a la cantidad de hardware disponible. El paralelismo hace 
que las máquinas SIMD desarrollen altas velocidades. 
 
El procesamiento de Arrays fue la primera forma de procesamiento paralelo estudiada e 
implementada. De aquí se derivan dos tipos diferentes de máquinas: 
 
• Aquellas que realizan operaciones por bits, tales como las máquinas MPP y CM-1 
• Aquellas que realizan operaciones por palabras, tales como la ILLIAC IV. 
 
 
MIMD 
 
SIMD 
 
Mybrid 
MISD 
 
Multiprocesadores
Multicomputadores 
Máquinas de Flujo de Datos 
Procesadores de Arrays 
 
Procesadores de Vector Pipeline 
Procesadores de Vector Pipeline 
 
Arrays Sistólicos 
Máquinas SIMD-MIMD
 
Máquinas MIMD-SIMD 
 10 I. Introducción 
Algunas características generales de las computadoras SIMD comparándolas con las 
computadoras MIMD son las siguientes: 
 
• Menos Hardware que las MIMD, debido a que utilizan sólo una unidad global de 
control. 
• Menos memoria que las MIMD, ya que sólo se necesita una copia de las 
instrucciones colocada en la memoria del sistema. 
• Flujo de instrucciones simples y sincronización implícita del procesamiento de 
elementos, lo que hace que una aplicación SIMD sea entendible, fácil de programar 
y fácil de trazar. 
• Instrucciones de control de flujo y operaciones escalares que son comunes a todos 
los elementos procesados que pueden ser ejecutados en la unidad de control, 
mientras los procesadores están ejecutando otras instrucciones. 
• Necesidad de mecanismos de sincronización sobre los procesadores, después de 
cada ciclo de ejecución de una instrucción. En contraste con las primitivas de 
sincronización explícitas que se requieren en la arquitectura MIMD. 
• Menos costo ya que sólo se necesita un decodificador de instrucción simple en la 
unidad de control, en contra de un decodificador en cada elemento que esta siendo 
procesado en una arquitectura MIMD. 
 
Ejemplos de computadoras SIMD incluyen la ILLIAC IV, MPP, DAP, CM-2, MasPar MP-1 
y MasPar MP-2 [Roosta99]. 
 
 
I.2.2.2. Arquitecturas MISD 
 
Un procesador Pipeline es un procesador MISD que trabaja acorde al principio del 
funcionamiento de un Pipe. La arquitectura pipeline es la forma fundamental de ejecución 
paralela de un proceso y es una idea poderosa que puede probar de manera significativa el 
rendimiento de una computadora SIMD. El principio Pipeline implica la segmentación o 
partición de un proceso computacional. Un proceso puede ser dividido en varios 
segmentos o etapas (stages). El procesamiento serial es concerniente con la ejecución de 
todos los stages de un proceso antes de iniciar la ejecución del primer stage del siguiente 
proceso. Sin embargo en el procesamiento serial, un proceso finaliza completamente antes 
de iniciar el siguiente proceso. Un procesador puede aumentar su velocidad de ejecución 
utilizando un pipeline. En un pipeline, mientras un stage esta siendo ejecutado, otro stage 
esta siendo cargado y la entrada deun stage se corresponde con la salida del stage previo. 
La figura I.9 muestra los principios básicos de un pipeline para un proceso que se 
constituye de cuatro stages, en una ejecución serial y paralela. Un resultado del pipeline es 
que el procesador realiza diferentes cálculos concurrentemente, pero en cualquier instante 
de tiempo cada cálculo es llevado a cabo en un stage de ejecución distinto. 
 
 
 
 
 
 
 I. Introducción 11
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura I.9. Ejecución serial y pipelinizada de un proceso formado por 4 stages 
 
Los principios del pipeline pueden ser usados en dos niveles diferentes: unidades 
aritméticas pipelines y unidades de control pipelines; lo cual nos da dos enfoques de 
diseño distintos. 
 
Stage 1 Stage 2 Stage 3 Stage 4 
Un proceso con 4 stages: 
Stage 
1 
Stage 
2 
Stage 
3 
Stage 
4 
Stage 
1 
Stage 
2 
Stage 
3 
Stage 
4 
Ejecución serial de 2 procesos formados por 8 stages: 
Stage 
1 
Stage 
2 
Stage 
3 
Stage 
4 
Stage 
1 
Stage 
2 
Stage 
3 
Stage 
4 
Ejecución pipelinizada de los mismos 2 procesos formados 
por 8 stages: 
Tiempo de Ejecución Total del procesamiento Serial: 2 * ∑i=1,4 Si 
Ejecución Total del procesamiento Pipelinizado: 1 * ∑i=1,4 Si+ S4 
Donde Sies el tiempo de ejecución del stage i 
 12 I. Introducción 
En general, los principios del pipeline, como la capacidad de ejecutar operaciones de 
forma simultanea, pueden ser explotados dentro de una arquitectura de computadora en 
tres niveles: 
 
1. A nivel de instrucción: Es utilizado en el diseño de unidades de procesamiento de 
instrucciones. Una instrucción pasa sobre un segmento durante cada ciclo, de 
manera que después las entradas de instrucciones dentro del pipeline, son emitidas 
en cualquier ciclo. 
 
2. A nivel de Subsistema: Las unidades aritméticas pipeline son un ejemplo de este 
nivel. Las operaciones pipelinizadas ADD, MUL, DIV y SORT se encuentran en 
muchas arquitecturas de computadoras. 
 
3. A nivel de Sistema: El segmento pipeline no necesita estar a nivel de hardware, 
sino que el pipeline puede formar una estructura de software. Esto incluye redes 
de computadoras especializadas. 
 
Consecuentemente, el pipeline es en principio un concepto para procesamiento de 
vectores y puede ser hallado en muchas computadoras diseñadas para tales propósitos. 
Arquitecturas como la CDC STAR 100, Texas Instruments ASC y Cray I [Roosta99], son 
ejemplos fieles. 
 
I.2.2.3. Arquitecturas MIMD 
 
Un sistema MIMD es un sistema multiprocesador o una multicomputadora en donde cada 
procesador individual tiene su unidad de control y ejecuta su propio programa. Las 
computadoras MIMD tienen las siguientes características: 
 
• Distribuyen el procesamiento sobre un número independiente de procesadores. 
• Comparten fuentes, incluyendo el sistema de memoria principal, sobre los 
procesadores. 
• Cada procesador opera independientemente y concurrentemente. 
• Cada procesador corre su propio programa. 
 
Esto indica que los sistemas MIMD ejecutan operaciones en paralelo de manera asíncrona; 
los nodos activos cooperan pero operan independientemente. Las arquitecturas MIMD 
difieren con la interconexión de redes, procesadores, técnicas de direccionamiento de 
memoria, sincronización y estructuras de control. La interconexión de redes hace que los 
procesadores se comuniquen e interactúen unos con otros. Ejemplos de computadoras 
MIMD incluyen la Cosmic Cube, nCUBE2, iPSC, Symmetry, FX-8, FX-2800, TC-2000, CM-
5, KSR-1 y la Paragon XP/s [Roosta99]. 
 
Las computadoras MIMD se pueden categorizar en sistemas fuertemente acoplados y 
sistemas débilmente acoplados; dependiendo de cómo los procesadores accedan a la 
memoria. 
 
 I. Introducción 13
Los procesadores en un sistema multiprocesador fuertemente acoplado generalmente 
comparten un sistema de memoria global; estos sistemas son conocidos como sistemas de 
memoria compartida. Aquellos sistemas MIMD débilmente acoplados pueden compartir 
un sistema de memoria, pero cada procesador tiene su propia memoria local. A estos 
sistemas se les conoce como sistemas de paso de mensajes. Las computadoras fuertemente 
acopladas y débilmente acopladas corresponden a los sistemas MIMD de Memoria Global 
(GM-MIMD) y MIMD de Memoria Local (LM-MIMD) respectivamente. 
 
Las computadoras MIMD de paso de mensajes se refieren a multicomputadoras en 
donde cada procesador tiene su propia memoria, llamada memoria local o privada, y es 
accesible sólo por su propio procesador. Las arquitecturas MIMD de paso de mensajes 
están referidas tanto a arquitecturas de memoria distribuida como a arquitecturas de 
memoria privada. 
 
Un sistema MIMD de memoria compartida es llamado Sistema de Acceso Uniforme a 
Memoria (UMA, Uniform Memory Access), ya que el tiempo de acceso a memoria es el 
mismo para todos los procesadores que la comparten. En este modelo, los procesadores 
pueden comunicarse sin restricciones y de una manera simple compartiendo datos 
utilizando un mismo espacio de direccionamiento. Los datos que se comparten pueden 
protegerse mediante el uso de métodos de ocultamiento de datos que los modernos 
lenguajes de programación ofrecen. Debido a esta capacidad de soportar una gran 
variedad de modelos de programación eficientes, un sistema multiprocesador de memoria 
compartida es siempre la primera elección de los usuarios de programación paralela. 
Esto entra en contraste con los sistemas de paso de mensajes que son más fáciles de 
diseñar pero más difíciles de implementar o programar. En general, los sistemas MIMD 
fuertemente acoplados proporcionan mayor rapidez en el intercambio de datos entre los 
procesadores que los sistemas MIMD débilmente acoplados. 
 
Ejemplos de computadoras GM-MIMD son la serie CDC 6600 y la Cray XM-P. Ejemplos de 
computadoras LM-MIMD son la Carnegie-Mellon Cm* y la Tandom/16 [Roosta99]. 
 
I.3. ALGORITMOS PARALELOS 
 
Uno de los ingredientes más importantes para el procesamiento paralelo son sin duda los 
algoritmos paralelos que tienen un considerable interés en su desarrollo. Dado un 
problema a resolver en paralelo, el algoritmo paralelo describe como puede resolverse el 
problema pensando en una determinada arquitectura paralela, mediante la división del 
problema en subproblemas, comunicando los procesadores y posteriormente uniendo las 
soluciones parciales para obtener la solución final. Por ejemplo, los algoritmos basados en 
la estrategia de divide y vencerás usualmente tienen una naturaleza inherentemente 
paralela. 
Existen dos enfoques en el diseño de algoritmos paralelos con respecto al número de 
procesadores disponibles. El primero es el diseño de un algoritmo en el cual el número de 
procesadores utilizados por el algoritmo es un parámetro de entrada, lo que hace que el 
número de procesadores no dependa del tamaño de entrada del problema. 
 
 14 I. Introducción 
El segundo enfoque permite que el número de procesadores utilizados por el algoritmo 
paralelo crezca con el tamaño de la entrada, de tal forma que el número de procesadores 
no es un parámetro de entrada, pero si una función del tamaño de entrada del problema. 
Utilizando el esquema “división de labor”, un algoritmo diseñado con el segundo enfoque 
puede siempre ser convertido a un algoritmo del primer enfoque. 
 
Gran importancia dentro de los algoritmos paralelos toma la forma en que los distintos 
procesadores pueden llevar a cabo su propia comunicación. Los patrones de comunicación 
en los procesadores son rara vez arbitrarios y no estructurados. En cambio, las 
aplicaciones paralelas tienden a emplear patrones de comunicación predeterminados entre 
sus componentes. Si los patrones de comunicación más comúnmente utilizados son 
identificados en términos de sus componentes y de sus comunicaciones, es posible 
entonces crear un entorno o ambiente que este disponible mediante abstracciones de alto 
nivel para utilizarseen la escritura de aplicaciones. Esto proporciona un enfoque 
estructurado que puede ser acomodado dentro de un lenguaje orientado a objetos 
utilizado como lenguaje de programación paralela. 
 
 
I.4. LENGUAJES DE PROGRAMACION PARALELA 
 
Los lenguajes de programación paralela se basan en dos categorías, en abstracciones de 
programación paralela basadas en exclusión mutua de accesos a una memoria individual; 
y en abstracciones de procesos que se comunican mediante el envío de mensajes unos con 
otros. El envío de mensajes es una acción de alto nivel que puede ser implementada 
físicamente mediante procesadores distribuidos. 
 
Cada enfoque de programación paralela sugiere una configuración de hardware 
particular. La mejor será aquella que empate con las primitivas del lenguaje utilizado en la 
programación paralela. Actualmente existen muchos lenguajes de programación que ya 
tienen diseñadas primitivas para el manejo de procesos de manera asíncrona o síncrona. 
La programación asíncrona se utiliza para la programación de multiprocesadores o 
sistemas distribuidos; mientras que las soluciones paralelas síncronas son propias del uso 
de arrays o vectores de procesadores. 
 
En el caso de la programación orientada a objetos, ésta puede ser utilizada como un buen 
enfoque de programación paralela ya que puede encapsular y abstraer patrones comunes 
de comunicación paralela y llevar dicha abstracción hacia un estilo estructurado de 
programación paralela. 
 
El lenguaje de programación C++ es un ejemplo de un excelente lenguaje de programación 
orientado a objetos con el que se pueden implementar aplicaciones paralelas mediante el 
uso de threads para el manejo de procesos ligeros o hilos en un ambiente de memoria 
compartida. 
 
 
 
 
 
 I. Introducción 15
I.5. CONCURRENCIA 
 
La programación concurrente tiene sus raíces en los sistemas operativos y en la programación 
de sistemas. En los años 60’s se introdujeron en las computadoras dispositivos 
controladores independientes de entrada-salida llamados canales. Estos canales eran 
programables en sí mismos. Los sistemas operativos fueron organizados como una 
colección de procesos ejecutándose concurrentemente, algunos en los canales y otros 
ejecutándose en el procesador principal o CPU. Varios de estos procesos comparten 
memoria en su ejecución. Esta cmpartición de memoria provoca el problema de la 
sincronización de procesos. 
 
La escritura de programas que consisten de múltiples procesos que comparten memoria es 
una forma de programación concurrente. La sincronización de tales procesos en la 
compartición de memoria es de vital importancia para el buen funcionamiento del 
programa concurrente que se implementa. Existen varias alternativas tanto de hardware 
como de software (que fueron desarrolladas por diseñadores de S.O. e ingenieros de 
computación) que dan solución a los problemas de sincronización existentes. Científicos y 
matemáticos han tratado el problema de la sincronización de procesos como un problema 
abstracto. Dijkstra, por ejemplo, ha diseñado el concepto de semáforo para resolver este 
problema. Los semáforos ya han sido añadidos hoy en día a muchos lenguajes de 
programación. Por su parte Hoare propone el concepto de monitor para enfatizar el poder 
expresivo de la sincronización en los lenguajes de programación. Los Semáforos y los 
monitores han sido entonces diseñados para ser utilizados por procesos que comparten 
memoria. 
 
Por otro lado, para aquellos procesos que quieren intercambiar información sin compartir 
memoria, se utiliza el esquema de paso de mensajes. Problemas que se resuelven bajo el 
modelo cliente-servidor pueden comunicarse y sincronizarse utilizando el paso de 
mensajes, que es otra forma de programación concurrente. 
 
Los desarrollos más recientes del hardware y las arquitecturas de computadoras (ya 
mencionadas) tienen una gran influencia en la programación concurrente. Hoy en día 
existen muchas computadoras equipadas con varios procesadores, todos ellos 
compartiendo una memoria principal global en una arquitectura paralela llamada 
arquitectura de multiprocesador de memoria compartida. Si se quieren utilizar todos los CPU’s 
disponibles para ejecutar un programa, el programador tendrá que escribir el programa 
como una colección de procesos que se comunican sobre las variables globales 
compartidas o bien mediante el paso de mensajes. Los procesos son distribuidos sobre los 
CPU’s de tal forma que cada CPU tiene uno o más procesos. Sin embargo la creación de un 
nuevo proceso por el sistema operativo resulta ser caro ya que el sistema consume muchos 
recursos. Cuando se crea un proceso se debe crear un nuevo espacio de direcciones y 
mapearlo físicamente en memoria, es decir, el código del proceso y los datos iniciales son 
copiados allí y el sistema operativo actualiza sus tablas. El cambio de contexto entre los 
procesos asignados al CPU es caro ya que todos los registros deben ser salvados y 
restaurados y el mapeo del espacio de direcciones de los procesos es cambiado físicamente 
en memoria. 
 
 16 I. Introducción 
No obstante estos costos bajan considerablemente al diseñar procesos ligeros o threads. 
Bajo este modelo, todos los threads que se crean comparten el mismo espacio de 
direcciones. Crear un nuevo thread en un proceso resulta ser por tanto mucho menos caro 
que crear un nuevo proceso y hacer el cambio de contexto en un CPU desde un hilo a otro 
que entre procesos. El uso de múltiples threads (multi-threading) es otra forma de 
programación concurrente. El programador puede llevar a cabo las mismas fases de 
sincronización en un programa multi-threaded para comunicar procesos mediante 
memoria compartida o por paso de mensajes, con la fortuna de que las mismas 
herramientas que se utilizan para los procesos pesados pueden ser utilizadas aquí. 
 
1.5.1. Procesos 
 
Un proceso es un código de programa que se encuentra en algún estado de ejecución. Un proceso 
tiene su propio espacio de direcciones y algunos procesos sino es que todos están 
mapeados por el sistema operativo en una memoria física principal. Un proceso tiene un 
simple thread o flujo de control. El registro del contador de programa o (CP) en el CPU 
contiene la dirección de la siguiente instrucción a ser ejecutada. En un sistema 
multiprogramable tal como una mainframe o una Workstation, muchos procesos son 
localizados dentro de memoria física y pueden ejecutarse concurrentemente, 
compartiendo el CPU y los dispositivos periféricos. 
Un proceso tiene un estado corriente o actual: ejecutándose (running), listo (ready o 
runnable), bloqueado (blocked), o suspendido (suspended). 
 
Un proceso ejecutándose (running): esta actualmente utilizando el CPU. 
Un proceso listo (ready o runnable) esta esperando a ser planificado para entonces utilizar el 
CPU. 
Un proceso bloqueado (blocked) esta esperando para algún servicio que sea requisitado por el 
sistema operativo. 
Un proceso suspendido (suspended) le ha sido enviada una señal de “suspendido” hasta que 
no sea notificado o despertado no podrá pasar a otro estado. 
 
 
 
 I. Introducción 17
1.5.2. Hilos o Hebras (Threads) 
 
Dos procesos pueden compartir datos mediante una petición del sistema operativo para 
mapear los datos compartidos en ambos espacios de direccionamiento. Alternativamente, 
un proceso puede preguntar al sistema operativo por más de un hilo o flujo de control en 
su espacio de direcciones. Los sistemas operativos que soportan esto último son llamados 
multithreaded. Todos los threads de un proceso comparten el mismo espacio de direcciones 
y variables globales, sin embargo, cada thread tiene su propio contador de programa, 
valores de registros de CPU y un snack para llamados a procedimientos. 
 
Las mismas herramientas, semáforos y monitores que son utilizados para la sincronización 
de procesos que comparten memoria son utilizados por múltiples threads en un proceso 
que sincroniza sus accesos a su espaciode direcciones. Un thread también se encuentra en 
algún posible estado actual como lo muestra la siguiente figura: