HPC

La computación de alto rendimiento implica usar la potencia de cálculo para resolver problemas complejos en ciencia, intengiería y gestión. Para lograr este objetivo, la computación de alto rendimiento se apoya en tecnologías computacionales como los clusters, los supercomputadores o la computación paralela.

Primero veamos las diferencias entre la computación serial y paralela:

Ejemplo de problema paralelo: los partidos de la copa del mundo.

En cada etapa (octavos, cuartos, semi y final) los partidos pueden ser ejecutados en forma paralela, mientras que la ejecución de etapas debe ser en forma serial. Es decir este problema es serial en el sentido horizontal, y paralelo en el sentido vertical.

Por qué es importante aprender HPC?

Ley de Moore: El número de transistores en un circuito integrado se duplica cada 2 años.

Entre 1968 a 2003 la performance de los microprocesadores aumentaron en promedio más del 50% por año. Gran parte de este incremento se debe al aumento de la densidad de transistores en los sistemas integrados. A medida que disminuye el tamaño de los transistores también aumenta su velocidad pero junto a esto el consumo de energía aumenta también. Mucho de la energía consumida se disipa como calor y cuando un circuito se calienta mucho puede empezar a tener fallos. Los circuitos refrigerados por aire ya ha llegado a su limite físico de discipación de calor. Es por esto que el número de ciclos que una CPU puede ejecutar por segundo (clock-speed) no aumenta desde el año 2000 (Intel Pentum 4).

Por lo tanto, desde el 2005 los productores de microprocesadores han decidido mejorar la performance a base de sistemas multi-core. En vez de desarrollar procesadores monolíticos más rápdidos han empezado a poner múltiple procesadores completos en los sistemas integrados.

Límites y costos de la computación paralela

Ley de Amdahl

Establece que la velocidad de un programa paralelo viene dada por:

v= (1 - p)-1

donde p: fracción de código paralelizable.

Considerando el número de procesadores:

v = (p/n + s)-1

donde n: nuemero de procesadores, s:fración serial.

Esto muestra que por más que nos forcemos en paralelizar al máximo un programa, este siempre tendrá un asíntota con respecto al numero de procesadores que usemos. Por ejemplo para un código que se puede paralelizar al 95\% nunca vamos a alcanzar una velocidad mayor a 20 veces la velocidad en serial.

Paralelismo automatico

Muchos compiladores cuando analizan el código identifican oportunidades para paralelizar, particularmente en loops. En tal caso uno podría analizar el código e identificar inhibidores e intentar eliminarlos de forma tal que el compilador pueda identificarlo y paralelizar.

De todas formas aún no existen implementaciones de compiladores que paralelizen automáticamente de forma eficiente y lo más común es que la paralelización se realice manualmente en base a directivas realizadas por el programador.

Diseño de programas paralelos

Sin duda, el primer paso a desarrollar un programa paralelo es entender en primer lugar el problema que se quiere resolver en paralelo. Y analizar antes si el problema es realmente paralelizable.

En caso que que sea paralelizable, es importante identificar:

En caso de que no sea un algoritmo paralelizable se puede buscar otros algoritmos posibles (si existen).

Ejemplo: Un ejemplo interesante para ilustrar esto es la serie de Fibonacci, esta seríe se construye algorítmicamente según:

fn+1 = fn + fn-1

donde los primeros dos elementos (f0 f1) son igual a 1. Este problema no es paralelizable por la dependencia del calculo de los elementos previos para la construcción de un nuevo elemento. Sin embargo existe un resultado matemático que podemos utilizar conocido como Fórmula de Binet:

fn= [ φn - (-φ-n) ] / √5

donde φ= (1 + √5) / 2 = 1.6180339887…

este resultado es altamente paralelizable ya que no hay dependencia alguna entre elementos de la serie. Cada procesador puede computar uno distinto, solo sería necesario sincronizar y ordenar los numeros computados al final.

Partición

El primer paso en todo programa paralelo es descomponer el problema en pedazos discretos de trabajo (particionar).

Hay dos formas básicas de particionar un problema:

Ejemplo: Imaginemos que tenemos 5 profesores para corregir los examenes de una clase de 100 estudiantes. La corrección se puede organizar de dos formas: Cada profesor corrige un ejercicio de los 100 examenes (paralelización de tareas); la otra alternativa es que todos los profesores corrijan la totalidad del examen pero cada uno corrige 20 examenes (paralelización de datos). Acá las unidades de procesamientos serían los 5 profesores, los “datos” serían los estudiantes y las tareas (ó tasks) serian los ejercicios a corregir.

Hay varios elementos involucrados en la coordinación de un problema paralelo:

Comunicación

La comunicación sólo es necesaria cuando los tasks comparten datos. Si el problema a tratar se puede descomponer en muchos pedazos autónomos, entonces no es necesario hacer eso de ella. Algunos factores a considerar:

Sincronización

Tipos de sincronización:

Balance de carga

El balance de carga (load balancing) se refiera a la forma en que se distribuye la cantidad de trabajo entre tasks de forma tal de reducir la capacidad osciosa. Las estrategias posibles son:

Granularidad

Como ya se dijo, la granularidad hace referencia a la relación entre computación y comunicación.

Inhibidores de paralelismo

Dependencia

Decimos que hay dependencia entre instrucciones cuando el orden de ejecución de estos afecta el resultado del programa. También existe la dependencia de datos, esta resulta del uso múltiple de la misma locación de datos por distintos tasks. La dependencia es importante ya que es el principal inhibidor de paralelismo.

Input/Output

Las operaciones I/O son generalmente inhibidores de paralelismo. sin embargo existen sistemas de archivos adaptados a paralelización, por ejemplo: GPFS, Lustre, HDF

Nociones del hardware

Arquitectura de Von Neuman

Para entender la computación paralela es necesario tener algunos conocimientos básicos de cuales son los componentes de una computadora y como funciona. La mayoría de las computadoras electrónicas siguen la arquitectura de John Von Neuman también conocida como computadora de almacenamiento de programas, en ella tanto los programas, las instrucciones y los datos se guardan en una memoria electronica.

Los componentes de estas computadoras son:

  1. Memoria
    • Cada espacio en la memoria tiene una dirección identificador llamado memory address.
    • RAM (Random Access Memory) Es una memoria en la que el accesso a cualquier porción de información en ella demora el mismo tiempo (es una idealización).
    • cache es la parte de la memoria de accesso más inmediato para un procesador.
  2. Unidad de Control (CU): se encarga de buscar instrucciones y datos de la memoria, decodificarlos y coordinar operaciones (secuencialmente) para resolver alguna tarea.
  3. Unidad Lógica/Aritmética (ALU). ejecuta operaciones lógicas y aritméticas.
  4. Dispositivo de Input/Output: hace referencia a la interfaz entre el humano (operador) y la computadora.

Comunmente denominámos Unidad de Procesamiento Central (CPU) al conjunto de la CU, ALU y una pequeña porción de memoria muy rápida llamada registro. La CU tiene un registro especial llamado contador que guarda la dirección de la próxima instrucción a ejecutar.

Las instrucciones y los datos son transferidos entre CPU y Memoria a travez de una red interconectada. Esto tradicionalmente se hacia a travez de un bus que consiste en una colección de cables y un hardware que controlaba el acceso a estos. Hoy en día se usa otro sistema.

La separación entre CPU y Memoria genera un importante cuello de botella ya que la velocidad a la que la CPU ejecuta instrucciones es mucho mayor a la velocidad en la que puede tomar datos de la memoria para ejecutarlos.

Procesos, multitasking y threads

El sistema operativo (SO) es el software que maneja el hardware y los recursos en la computadora. Determina que programas ejecutar, cuando y que memoria asignarle. Cuando uno ejecuta un programa el SO crea un proceso, que consise en:

Los SO modernos son multitasking es decis que sportan la ejecución conjunta de varios programas en “simultaneo”. En estos SO si un proceso necesita esperar algún recurso (por ejemplo leer un dato en una memoria externa, este se bloquea, es decir deja de ejecutarse así el SO puede seguir con otros procesos. Sin embargo parte del programa podría continuar ejecutandose aunque parte del programa esté esperando el recurso. La creación de threads proveen de un mecanismo para los progrmadores de dividir sus programas en task independientes con la propiedad que cuando un thread está bloqueado otro puede seguir ejecutandose. Es más rápido switchar entre threads que entre procesos ya que son más “livianos”. Los threads están contenidos dentro de un proceso, de forma que comparten ejecutable, memoria y otros recursos.

Modificaciones al modelo de Von Neumann

Caching

El cache es una colección de ubicaciones de memoria de más rapido acceso que otras ubicaciones de memoria. En particular el cache de la CPU pude estar ubicada en el mismo chip que la CPU o en un chip separado pero de acceso más rapido. En general lo que se guarda en el cache sigue la idea de que los programas tienden a usar datos e instrucciones que están físicamente cerca entre ellos (por ejemplo recorrer un array), esta idea se conoce como cercanía ó locality.

Para explotar este principio de locality los sistemas usan un sistema interconectado más ancho para acceder a datos e instrucciones. Es decir el acceso a memoria se hace en bloques. Estos bloques se conocen como cache blocks ó cache lines, estos almacenan entre 8/16 veces más información que una ubicación individual de memoria. Si bien solemos pensar al cache como un bloque homogeneo, suele tener niveles con distinta velocidad de acceso.

Mapeo del cache

Otro aspecto en el diseño del cache es donde se guardan las cache lines tomadas desde la memoria. Hay distintas formas de asignar a cada ubicación en memoria su correspondiente cache line:

Memoria virtual

Los caches hacen posible que la CPU acceda rapidamente a instrucciones y datos que estan en la memoria principal. Pero cuando ejecutamos programas muy grandes es posible que los datos no entren en la memoria principal. La memoria virtual fue desarrollada para que la memoria principal pueda funcionar como un cache de almacenamiento secundario. Explota el principio de localidad espacial/temporal guardando solo las partes activas del ó los programas siendo ejecutados en un bloque conocido como swap space. Al igual que la CPU la memoria virtual opera sobre instrucciones y bloques de datos, estos son comunmente llamados pages, y dado a que el accesso es cientas de veces más lento suelen tener un tamaño grande (~4-16 kb)

Las memorias virtuales resuelven tres problemas:

  1. Falta de memoria RAM
  2. Fragmentación de memoria. Cuando no hay espacio contiguo para guardar datos usados por un programa (aunque si en total haya suficiente espacio en la RAM).
  3. Problemas de seguridad (address corruption)

Paralelismo de bajo nivel

Instruction-level parallelism, o ILP, intenta mejorar la performance del procesador teniendo multiples componentes del procesador o unidades funcionales ejecutando instrucciones simultaneamente. Hay dos formas de lo lograr ILP:

Hardware multi-threading

ILP can be very difficult to exploit: a program with a long sequence of dependent statements offers few opportunities. For example, in a direct calculation of the Fi- bonacci numbers

f[0]=f[1]=1
for (i=2;i<=n;i++)
   f[i] = f[i-1] + f[i-2]

there’s essentially no opportunity for simultaneous execution of instructions. Thread-level parallelism, or TLP, attempts to provide parallelism through the simultaneous execution of different threads, so it provides a coarser-grained paral- lelism than ILP, that is, the program units that are being simultaneously executed— threads—are larger or coarser than the finer-grained units—individual instructions. Hardware multithreading provides a means for systems to continue doing use- ful work when the task being currently executed has stalled—for example, if the current task has to wait for data to be loaded from memory. Instead of looking for parallelism in the currently executing thread, it may make sense to simply run an- other thread. Of course, for this to be useful, the system must support very rapid switching between threads. For example, in some older systems, threads were sim- ply implemented as processes, and in the time it took to switch between processes, thousands of instructions could be executed. In fine-grained multithreading, the processor switches between threads after each instruction, skipping threads that are stalled. While this approach has the potential to avoid wasted machine time due to stalls, it has the drawback that a thread that’s ready to execute a long sequence of instructions may have to wait to execute every instruction. Coarse-grained multithreading attempts to avoid this problem by only switching threads that are stalled waiting for a time-consuming operation to complete (e.g., a load from main memory). This has the virtue that switching threads doesn’t need to be nearly instantaneous. However, the processor can be idled on shorter stalls, and thread switching will also cause delays.

Simultaneous multithreading, or SMT, is a variation on fine-grained multi- threading. It attempts to exploit superscalar processors by allowing multiple threads to make use of the multiple functional units. If we designate “preferred” threads— threads that have many instructions ready to execute—we can somewhat reduce the problem of thread slowdown.

Computadoras paralelas (clusters)

Las computadoras paralelas no son más que un conjunto de Memorias y CPUs conectadas en una red de forma inteligente. Basado en como es el acceso a la memoria de las unidades de procesamiento podemos clasificar a las computadores (clusters) en:

  1. Memoria distribuida (shared memory).
  2. Memoria compartida (distributed memory).

Shared Memory

En teoría estas arquitecturas permiten que los procesadores accedan a cualquier porción de la memoria libremente. Aunque los procesadores operen independientemente todos comparten los mismos recursos de memoria. Dentro de las arquitecturas de memoria compartida existen dos tipos básicos:

Ventajas:

Desventajas:

Distributed Memory

En estas los procesadores tienen su propia memoria local. En ellas no existe el concepto de global address space a lo largo de todos los procesadores. Como cada procesador tiene su propia memoria local, opera de forma independiente. Por lo tanto tampoco aplica el concepto de cache cherency.

Ventajas:

Desventajas:

Hibridas

Las grandes supercomputadoras del mundo hoy en día adoptan una arquitectura míxta.

Tipos de paralelismo y taxonomía de Flynn

Flynn clasificó las computadoras en base a dos características: el paralelismo de procesos y paralelismo de datos.

Modelos de programación paralela

Los modelos de programación paralela son abstracciones por encima del hardware, y por lo tanto es importante resaltar que si bien algunos modelos se usan principalmente en determinadas arquitecturas, cualquiera de ellos puede ser usada en teoría en cualquier computadora independientemente de su arqutectura.

Existen varios modelos de programación paralela en uso:

Diseño de programas paralelos

Ian Foster’s methodology:

  1. Partitioning. Divide the computation to be performed and the data operated on by the computation into small tasks. The focus here should be on identifying tasks that can be executed in parallel.
  2. Communication. Determine what communication needs to be carried out among the tasks identified in the previous step.
  3. Agglomeration or aggregation. Combine tasks and communications identified in the first step into larger tasks. For example, if task A must be executed before task B can be executed, it may make sense to aggregate them into a single composite task.
  4. Mapping. Assign the composite tasks identified in the previous step to processes/threads. This should be done so that communication is minimized, and each process/thread gets roughly the same amount of work.

Definiciones y conceptos:

Edit this page.

Licensed MIT.