Se caracterizaba por guardar las instrucciones de los procesos y los datos en una memoria electronica, a diferencia de como se modelaban los computadores de la epoca a través de una conexion de cables

Componentes principales

• Memoria
• Unidad de control
• Unidad Aritmetica Logica
• Entradas/Salidas

Memoria de acceso aleatorio

En la memoria de acceso aleatorio se almacenaban los datos y los programas que estaban siendo ejecutados

• Las instrucciones del programa son datos codificados que le dicen al computador que es lo que tiene que hacer
• Los datos son simplemente informacion que sera usada por el programa

Taxonomia de Flynn

Single Instruction, Single Data (SISD)

Hay un elemento de procesamiento, que tiene acceso a un único programa y a un almacenamiento de datos. En cada paso, el elemento de procesamiento carga una instrucción y la información correspondiente y ejecuta esta instrucción. El resultado es guardado de vuelta en el almacenamiento de datos. Luego SISD es el computador secuencial convencional, de acuerdo al modelo de von Neumann.

Multiple Instruction, Single Data (MISD)

Hay múltiples elementos de procesamiento, en el que cada cual tiene memoria privada del programa, pero se tiene acceso común a una memoria global de información. En cada paso, cada elemento de procesamiento de obtiene la misma información de la memoria y carga una instrucción de la memoria privada del programa. Luego, las instrucciones posiblemente diferentes de cada unidad, son ejecutadas en paralelo, usando la información (idéntica) recibida anteriormente. Este modelo es muy restrictivo y no se ha usado en ningún computador de tipo comercial.

Single Instruction, Multiple Data (SIMD):

Hay múltiples elementos de procesamiento, en el que cada cual tiene acceso privado a la memoria de información (compartida o distribuida). Sin embargo, hay una sola memoria de programa, desde la cual una unidad de procesamiento especial obtiene y despacha instrucciones. En cada paso, cada unidad de procesamiento obtiene la misma instrucción y carga desde su memoria privada un elemento de información y ejecuta esta instrucción en dicho elemento. Entonces, la instrucción es síncronamente aplicada en paralelo por todos los elementos de proceso a diferentes elementos de información. Para aplicaciones con un grado significante de paralelismo de información, este acercamiento puede ser muy eficiente. Ejemplos pueden ser aplicaciones multimedia y algoritmos de gráficos de computadora.

Multiple Instruction, Multiple Data (MIMD):

Hay múltiples unidades de procesamiento, en la cual cada una tiene tanto instrucciones como información separada. Cada elemento ejecuta una instrucción distinta en un elemento de información distinto. Los elementos de proceso trabajan asíncronamente. Los clusters son ejemplo son ejemplos del modelo MIMD.

Patrones de diseño paralelo

Los patrones se han establecido como buenas practicas a la hora de realizar ingeniería de software.

Los patrones de control en el caso de la programación paralela son maneras de combinar la distribución de los procesos y el acceso a los datos para la solucion de un problema.

Fork-Join

En este patrón de diseño se generan dos ejecuciones concurrentes, que empieza inmediatamente después de que el fork es llamado en código, después, se usa join para combinar estas dos ejecuciones concurrentes en una. Cada join puede unirse entonces a su fork correspondiente y lo hace antes de las otras terminen.

Map

Map es un patrón que replica una función sobre todos los elementos de un conjunto de entrada. La función que está siendo replicada se llama función elemental, dada que la misma se aplica a una coleccion real de datos.

Stencil

Stencil es un generalización del patron de Map, en el cual una función elemental tiene acceso no solo a un elemento del conjunto de entrada sino también a un conjunto de "vecinos"

Como la estructura de datos no es infinita se deben tener en cuenta el manejo de excepciones para los bordes de la misma.

Reducción

Una reducción combina cada elemento de una colección en uno solo utilizado una función asociativa conocida como función combinatoria. Como es asociativa las tareas se pueden distribuir de muchas maneras y si la función resultara ser también conmutativa el número de posibilidides aumentaría aún más.

Scan

Scan realiza las reducciones de cada elemento perteneciente a una estructura. En otras palabras cada elemento de salida es la reduccion de un elemento de entrada. A traves de una función sucesora se avanza de un estado al otro haciendo folds en el proceso asociativo.

ParBegin - ParEnd

Parbegin y Parend originalmente propuesto por Dijsktra es un patrón para lenguajes estructurados en bloque como Pascal y permiten una especificación explicita del paralelismo, todo lo que esté contenido entre ambos será ejecutado en hilos separados en tanto se necesite y se genera un grafo de precedencia como el que se ve en la imagen, donde se muestra simplemente el orden de las instrucciones a ejecutar.

Maestro / Esclavo

Es usada cuando se tienen dos o más procesos que necesitan ejecutarse simultanea y continuamente pero a diferentes velocidades. Si estos procesos corren en un único ciclo, pueden suceder problemas de temporización graves. Estos problemas de temporización ocurren cuando una parte del ciclo tarda más en ejecutarse de lo esperado. Si esto sucede, la sección restante del ciclo se atrasa. El patrón Maestro/Esclavo consiste en múltiples ciclos en paralelo. Un ciclo actúa como el maestro y los otros como esclavos. El ciclo maestro controla a todos los demás.

SPMD - SIMD

Esto viene de la taxonomia Flynn SPMD (Single Program, Multiple Data), múltiples procesadores autónomos ejecutan simultáneamente el mismo programa en puntos independientes, SIMD (Single instructon, multiple data) está basado en organizar los datos relevantes al problema en estructuras de datos iterativas como arreglos y en definir la computación en términos de una secuencia de actualizaciones paralelas en paralelo con estas estructuras de datos.

Creación de hilos y procesos

Los hilos se distinguen de los tradicionales procesos en que los procesos son generalmente independientes, llevan bastante información de estados, e interactúan sólo a través de mecanismos de comunicación dados por el sistema. Por otra parte, muchos hilos generalmente comparten otros recursos directamente. En muchos de los sistemas operativos que proveen facilidades para los hilos, es más rápido cambiar de un hilo a otro dentro del mismo proceso, que cambiar de un proceso a otro.

Arquitecturas de memoria de computación paralela

Memoria compartida

• Los procesos comparten un espacio de memoria común
• Escriben y leen de manera asíncrona
• No es necesario especificar cómo se comunican los datos entre las tareas
• Se usan semáforos o locks para controlar el acceso a la memoria compartida

• Lo más comúnmente representado hoy por las máquinas Symmetric Multiprocessor (SMP)
• Procesadores idénticos
• Igual acceso y tiempos de acceso a la memoria
• Si un procesador actualiza una ubicación en memoria compartida, todos los demás procesadores saben sobre la actualización, esto es llamado coherencia del caché

• Hecho mediante la vinculación física de dos o más SMP
• Un SMP puede acceder directamente a la memoria de otro SMP
• No todos los procesadores tienen igual tiempo de acceso a toda la memoria
• El acceso a la memoria es más lento
• Si se mantiene la coherencia del caché

Memoria distribuida

Esta arquitectura se basa en múltiples procesadores con su propia memoria física privada, las tareas pueden operar solo con información local y se necesita de la comunicación para obtener información remota, a través también de procesadores remotos Hay cuatro implementaciones que pueden servir como ejemplo conocidas para esta arquitectura tales como: múltiples sistemas operativos, Middlewares, clusters y grids. Las razones por las que se prefiere esta arquitectura en ciertos escenarios es porque en principio se pueden añadir tantas unidades de procesamiento como la red pueda soportar, pero las limitaciones recaen directamente en ella.

• También llamado modelo de paso de mensajes
• requieren una red de comunicación para conectar la memoria entre procesadores
• Las tareas intercambian datos por medio del paso y recepción de mensajes
• Los procesadores tienen su propia memoria local. Las direcciones de memoria en un procesador no se asignan a otro procesador, por lo que no hay concepto de espacio de direcciones global en todos los procesadores.
• Debido a que cada procesador tiene su propia memoria local, funciona independientemente. Los cambios que hace en su memoria local no tienen ningún efecto en la memoria de otros procesadores. Por lo tanto, el concepto de coherencia de caché no se aplica.
• Cuando un procesador necesita acceso a los datos de otro procesador, suele ser la tarea del programador definir explícitamente cómo y cuándo se comunican los datos. La sincronización entre tareas también es responsabilidad del programador.

Ejemplos de memoria distribuida

• Clusters: Colección de computadores que se encuentran interconectados mediante redes de alta velocidad (Ethernet, SCI, Myrinet, Infiniband) Existe una categorización hecha por la organización TOP500 que lleva cuenta de los clusteres más poderosos de la tierra con capacidad de procesamiento del órden de gigaflops. Estos generalmente están basados en una arquitectura MIMD.
• Grids: Computadores de múltiples dominios administrativos conectados para solucionar una tarea determinada.

Hibrido memoria distribuida-comopartida

• Es la combinación entre memoria compartida y memoria distribuida, con sus ventajas en común.
• Su principal ventaja es su escalabilidad.
• Su principal desventaja es que la complejidad de programación aumenta.

Hilos

• Un proceso pesado puede convertirse en varios procesos livianos ejecutados de manera concurrente.
• Se pueden describir como una subrutina dentro del programa principal.
• Se comunican entre ellos a través de la memoria global.

Datos en paralelo

• También conocido como PGAS (Partitioned Global Address Space)
• Una serie de tareas trabajan de manera colectiva en la misma estructura de datos
• Las tareas realizan la misma operación, pero cada una en su partición pero cada tarea trabaja en una partición diferente de ésta

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están distribuidos uniformemente entre las tareas

• Cuando la cantidad de trabajo que realiza cada tarea es variable o no se puede predecir, puede ser útil usar un planificador - task pool approach. Cuando cada tarea termina su trabajo, espera en una cola para obtener una nueva pieza de trabajo.
• Puede ser necesario diseñar un algoritmo que detecte y maneje desequilibrios de carga como ocurren dinámicamente dentro del código.

Medidas de rendimiento

Tiempo de respuesta

Es el tiempo que tarda en ejecucion el programa A.

MIPS - MFLOPS

MIPS - Millones de operaciones por segundo. MFLOPS - Millones de operaciones de punto flotante por segundo.

Eficiencia

La eficiencia del programa se mide en el costo de ejecucion.

Aplicaciones

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están distribuidos uniformemente entre las tareas

Aproximación y cálculo de constantes y/o funciones numéricas.

Worldwide LHC Computing Grid (WLCG) es una colaboración global de centros de computación. Fue lanzado en 2002 para proporcionar un recurso para almacenar, distribuir y analizar los 15 petabytes (15 millones de gigabytes) de datos generados cada año por el Large Hadron Collider (LHC).

Predicción del clima y cambio climático

Uno de los primeros usos exitosos de la computación paralela fue la predicción del tiempo. La información, como la temperatura, la humedad y las precipitaciones, se ha recolectado y utilizado para predecir el clima durante más de 500 años. En 1904, el físico y meteorólogo noruego Vilhelm Bjerknes propuso un modelo de ecuaciones diferenciales para la predicción meteorológica que incluía siete variables, incluyendo temperatura, lluvia y humedad.

Análisis de imágenes multiespectro

Las imágenes satelitales consisten en grandes cantidades de datos. Por ejemplo, las imágenes Landsat 7 consta de siete tablas de datos, donde cada entrada en una tabla representa una longitud de onda magnética diferente (azul, verde, rojo o infrarrojo térmico) para un píxel de 30 metros cuadrados de la superficie de la Tierra.

Astronomía

Hay muchas aplicaciones de los supercomputadores a la astronomía, incluyendo el uso de un supercomputador para simular eventos en el futuro, o pasado, para probar teorías astronómicas. La Universidad de Minnesota Supercomputer Center simuló lo que una explosión de supernova que se origina en el borde de una gigantesca nube de gas molecular interestelar parecería 650 años después de la explosión.

Renderizado de imagenes y animación

Diagnóstico de enfermedades mentales

El proyecto RePhrase incluido en el programa Horizonte 2020 de la UE tuvo como objetivo trabajar en la mejora del desarrollo de software para arquitecturas paralelas y heterogéneas. Los resultados de esta investigación encontraron aplicación en diversos campos, como en la mejora de procesos industriales de fabricación, la monitorización del tráfico ferroviario y la optimización de aplicaciones para el diagnóstico de enfermedades mentales. Este último consistía en el procesamiento por computador de imágenes capturadas mediante resonancia magnética del cerebro, con el objetivo de conseguir diagnósticos más rápidos en el caso de enfermedades como la la esquizofrenia, el trastorno bipolar o la depresión.

• Reducción en los tiempos de comunicaciones en las arquitecturas
• Software de desarrollo más sencillo para clústeres
• Sistema híbridos en múltiples plataformas
• Confiabilidad y tolerancia a fallos
• Computación en la nube
• Unificación o integración de APIs
• Producción de software que haga transparente la programación en sistemas híbridos

Hilos POSIX

Para empezar, POSIX significa Portable Operating System Interface. Está compuesto por una serie de estándares especificados por IEEE para promover la interoperabilidad de los sistemas operativos. Además, POSIX establece reglas para la portabilidad de programas.

Los Hilos POSIX, generalmente denominados pthreads, es un modelo de ejecución independiente del lenguaje, así como un modelo de ejecución paralelo. Permite que un programa controle múltiples flujos de trabajo diferentes que se superponen en el tiempo. Cada flujo de trabajo se denomina subproceso, y la creación y el control de estos flujos se logra haciendo llamadas a la API de subprocesos POSIX. Los Hilos POSIX son una API definida por el estándar POSIX.1c, extensiones de Threads ( IEEE Std 1003.1c-1995). [25]

OpenMP

Es una interfaz de programa de aplicación (API) que se puede utilizar para dirigir explícitamente paralelismo de memoria compartida multi-procesos. Está compuesto por:

• Directivas de compilación
• Runtime Library Routines
• Variables de entorno

Ejemplo región paralela

						
#include <omp.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
	/* Cada thread tiene una variable id privada (tid) */
	int nthreads, tid;

	#pragma omp parallel private(tid)
	{
	/* Se asigna y se imprime el id de cada thread  */
	tid = omp_get_thread_num();
	printf("Hello World desde el thread = %d\n", tid);
	/* Solo el thread master ejecuta lo siguiente */
	if (tid == 0)
	{
		nthreads = omp_get_num_threads();
		printf("El numero de threads es = %d\n", nthreads);
	}
	}
}
						
					

Parallel For

						
#include <omp.h>
#include <stdio.h>

#define N       1000
#define CHUNKSIZE   100

int main(int argc, char *argv[])
{

	int i, chunk;
	float a[N], b[N], c[N];

	for (i=0; i < N; i++)
	a[i] = b[i] = i * 1.0;
	chunk = CHUNKSIZE;

	#pragma omp parallel for \
	shared(a,b,c,chunk) private(i) \
	schedule(static,chunk)

	for (i=0; i < N; i++)
	c[i] = a[i] + b[i];
}
						
					

Sincronización en OpenMP

						
#include <omp.h>
int main(int argc, char *argv[])
{
	int x;
	x = 0;

	#pragma omp parallel shared(x)
	{
	#pragma omp critical
	x = x + 1;
	}
	/* Final de la región paralela */
}
						
					

CUDA

CUDA son las siglas de Compute Unified Device Architecture (Arquitectura Unificada de Dispositivos de Cómputo) que hace referencia a una plataforma de computación en paralelo incluyendo un compilador y un conjunto de herramientas de desarrollo creadas por nVidia que permiten a los programadores usar una variación del lenguaje de programación C para codificar algoritmos en GPU de nVidia.[27]

Ejemplo de Programación Paralela en Java

						
public class CajeraThread extends Thread {
	private String nombre;
	private Cliente cliente;
	private long initialTime;
	// Constructor, getter & setter

	@Override
	public void run() {
		System.out.println("La cajera " + this.nombre + " COMIENZA A PROCESAR LA COMPRA DEL CLIENTE "
					+ this.cliente.getNombre() + " EN EL TIEMPO: "
					+ (System.currentTimeMillis() - this.initialTime) / 1000
					+ "seg");
		for (int i = 0; i < this.cliente.getCarroCompra().length; i++) {
			this.esperarXsegundos(cliente.getCarroCompra()[i]);
			System.out.println("Procesado el producto " + (i + 1)
			+ " del cliente " + this.cliente.getNombre() + "->Tiempo: "
			+ (System.currentTimeMillis() - this.initialTime) / 1000
			+ "seg");
		}
		System.out.println("La cajera " + this.nombre + " HA TERMINADO DE PROCESAR "
						+ this.cliente.getNombre() + " EN EL TIEMPO: "
						+ (System.currentTimeMillis() - this.initialTime) / 1000
						+ "seg");
	}

	private void esperarXsegundos(int segundos) {
		try {
			Thread.sleep(segundos * 1000);
		} catch (InterruptedException ex) {
			Thread.currentThread().interrupt();
		}
	}
}
						
					

Ejemplo de Programación Paralela en Java

						
public class MainThread {

	public static void main(String[] args) {

		Cliente cliente1 = new Cliente("Cliente 1", new int[] { 2, 2, 1, 5, 2, 3 });
		Cliente cliente2 = new Cliente("Cliente 2", new int[] { 1, 3, 5, 1, 1 });

		// Tiempo inicial de referencia
		long initialTime = System.currentTimeMillis();
		CajeraThread cajera1 = new CajeraThread("Cajera 1", cliente1, initialTime);
		CajeraThread cajera2 = new CajeraThread("Cajera 2", cliente2, initialTime);

		cajera1.start();
		cajera2.start();
	}
}
						
					

Ejemplo de Programación Paralela en Java

						
La cajera Cajera 1 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente 1 EN EL TIEMPO: 0seg
La cajera Cajera 2 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente 2 EN EL TIEMPO: 0seg
Procesado el producto 1 del cliente Cliente 2->Tiempo: 1seg
Procesado el producto 1 del cliente Cliente 1->Tiempo: 2seg
Procesado el producto 2 del cliente Cliente 2->Tiempo: 4seg
Procesado el producto 2 del cliente Cliente 1->Tiempo: 4seg
Procesado el producto 3 del cliente Cliente 1->Tiempo: 5seg
Procesado el producto 3 del cliente Cliente 2->Tiempo: 9seg
Procesado el producto 4 del cliente Cliente 2->Tiempo: 10seg
Procesado el producto 4 del cliente Cliente 1->Tiempo: 10seg
Procesado el producto 5 del cliente Cliente 2->Tiempo: 11seg
La cajera Cajera 2 HA TERMINADO DE PROCESAR Cliente 2 EN EL TIEMPO: 11seg
Procesado el producto 5 del cliente Cliente 1->Tiempo: 12seg
Procesado el producto 6 del cliente Cliente 1->Tiempo: 15seg
La cajera Cajera 1 HA TERMINADO DE PROCESAR Cliente 1 EN EL TIEMPO: 15seg