Nota generada a partir de liga
Para tener un alto performance en un programa de máquina, deben considerarse las siguientes preguntas:
La respuesta nos lleva a pensar en el número de instrucciones por ciclo y el número de ciclos que realiza el procesador. Entiéndase un ciclo por los pasos de leer una instrucción, determinar acciones a realizar por tal instrucción y ejecutar las acciones (ver liga).
Dependiendo de la respuesta podemos elegir una arquitectura de computadoras u otra y así también un algoritmo u otro.
La respuesta implica analizar el tráfico de datos entre las jerarquías de almacenamiento (o máquinas si estamos en un clúster de máquinas) y potenciales bottlenecks.
Vectorización que pueden realizar los procesadores.
Perfilamiento de código para lograr la eficiencia deseada. Ver 1.6.Perfilamiento.ipynb.
Programación en lenguajes compilados en lugar de intérpretes (o combinando intérpretes con lenguajes compilados, ver 1.7.Compilar_a_C_Cython y 1.7.Reescribir_funciones_a_C++_Rcpp ).
Conocimiento de los propósitos con los que fueron diseñados los procesadores para explotar su capacidad. Aquí decidimos si usamos código secuencial o código en paralelo.
...además necesitamos conocer las diferentes arquitecturas que pueden utilizarse para cómputo en paralelo.
¿Alguien ya resolvió mi bottleneck?
Experiencia en el lenguaje de programación seleccionado.
Las componentes fundamentales de un sistema en una computadora pueden simplificarse en:
Unidades computacionales. En éstas unidades nos interesa la pregunta ¿cuántos cálculos pueden realizar por segundo?
Unidades de memoria. En éstas unidades nos interesa la pregunta ¿cuántos datos pueden alojar y qué tan rápido puede leerse desde y escribirse hacia las distintas jerarquías?
Conexiones entre las unidades anteriores. Nos interesa ¿qué tan rápido pueden moverse datos de un lugar a otro?
Con esta simplificación tenemos como ejemplo a la CPU como unidad de cómputo conectada tanto a la RAM y a un disco duro como dos unidades de memoria y un bus que provee las conexiones entre estas partes. Otro ejemplo es considerar que la CPU tiene diferentes unidades de memoria en ella: los cachés tipo L1, L2, L3 y L4* conectadas a la CPU a través de otro bus. También la GPU es ejemplo de una unidad de cómputo conectada a una unidades de memoria como RAM y cachés.
*ver liga para información sobre cachés tipo L.
Un dibujo simplificado y basado en una arquitectura de computadoras con nombre Von Neumann que nos ayuda a visualizar lo anterior en la CPU es el siguiente:
La memoria principal es una colección de ubicaciones que almacenan datos e instrucciones. Cada ubicación consiste de una dirección (address) que se utiliza para accesar a la ubicación y a sus contenidos.
La CPU está dividida en la unidad de control y la unidad aritmética y lógica. Aquí encontramos registers que son áreas o ubicaciones de almacenamiento (de datos, direcciones de memoria e información del estado de ejecución de un programa) de rápido acceso.
La interconexión o bus ayuda a la transferencia de datos e instrucciones entre la CPU y la memoria.
Obs:
En el dibujo no se está presentando los dispositivos de input y output pero sí aparecen en la arquitectura de Von Neumann.
También no se presentan en el dibujo unidades de almacenamiento como los discos duros pero también aparecen en la arquitectura de Von Neumann. Los discos duros se consideran dentro de las unidades de memoria y la CPU se conecta a ellos mediante un bus.
Si los datos se transfieren de la memoria a la CPU se dice que los datos o instrucciones son leídas y si van de la CPU a la memoria decimos que son escritos a memoria.
La separación entre la memoria y la CPU genera lo que se conoce como Von Neumann bottleneck y tiene que ver con la lectura/escritura y almacenamiento de datos e instrucciones. La interconexión determina la tasa a la cual se accede a éstos.
Sea una CPU o una GPU, las unidades computacionales toman como input un conjunto de bits (que representan números por ejemplo) y producen otro conjunto de bits (por ejemplo la suma de los números). El performance de éstas unidades se mide en instrucciones por ciclo y en ciclos por segundo. Para referencias de instrucciones por ciclo (IPC) ver liga y número de ciclos por segundo (llamado clock rate o clock speed) ver liga.
Entre los rediseños que se han hecho del modelo clásico de Von Neumman para resolver los bottlenecks, mejorar la velocidad y el performance se encuentran:
Mientras que incrementar el clock speed en una unidad computacional hace más rápido a un programa, también es importante la medida de IPC. La IPC se puede incrementar vía la vectorización y es típico en procesadores que soportan las instrucciones llamadas Single Instruction Multiple Data (SIMD). La vectorización consiste en que dados múltiples datos, el procesador puede trabajar sobre ellos en un instante o tiempo (ejecución en paralelo):
Comentario: este tipo de procesadores vinieron a reemplazar al modelo de Von Neumann clásico Single Instruction Single Data (SISD) en el que un conjunto de datos se procesaban en un tiempo determinado y no de forma simultánea o en paralelo:
por lo que se decidió transitar de un diseño de hardware secuencial hacia un hardware paralelo: la industria entre los años $2003-2005$ en lugar de fabricar procesadores monolíticos (clásico Von Neumann) que fueran más rápidos y complejos, decidió fabricar múltiples, simples procesadores, cores, en un sólo chip para incrementar el poder de procesamiento, disminuir el Von Neumann bottleneck y aumentar el clock speed. El término core* hoy en día lo usamos como sinónimo de procesador.
*Esto fue motivado pues desde el año $2002$ el incremento del performance de los procesadores con un sólo CPU fue de un $20\%$ por año vs un $50\%$ por año entre $1986$ y $2002$. Lo anterior se debió a los problemas de la construcción de procesadores monolíticos o de un core relacionados con la disipación del calor por un mayor consumo de energía al hacer más pequeños los transistores.
Un dibujo de una CPU y una GPU que nos ayudan a visualizar máquinas multicore con capacidad de cómputo en paralelo son los siguientes:
GPU
Comentarios:
Un ejemplo de procesadores SIMD son los procesadores vectoriales o en arreglo, ver liga.
En la práctica se ha visto que simplemente añadir más CPU's o cores al sistema no siempre aumenta la velocidad de ejecución en un programa. Existe una ley que explica lo anterior, la ley de Amdahl, la cual indica que si un programa está diseñado para ejecutarse en múltiples cores y tiene algunas secciones de su código que pueden sólo ejecutarse en un core, entonces éste será el bottleneck del programa. Por ejemplo, si tuviéramos que realizar una encuesta que tarda $1$ min a $100$ personas y tenemos una sola persona, entonces nos tardaríamos $100$ minutos (proceso serial). Si tenemos a $100$ personas entonces nos tardaríamos $1$ minuto en completar todas las encuestas (proceso en paralelo). Pero si tenemos más de $100$ personas, entonces no nos tardaremos menos de $1$ minuto pues las personas "extras" no podrán participar en realizar la encuesta. En este punto la única forma de reducir el tiempo es reducir el tiempo que le toma a una persona encuestar a otra (esta es la parte secuencial del programa).
Los sistemas SISD, SIMD y Multiple Instruction Multiple Data (MIMD), presentado a continuación:
son parte de la taxonomía de Flynn* (ver liga) que clasifica a los sistemas dependiendo del número de stream de datos e instrucciones que puede procesar. Ejemplos de sistemas MIMD son máquinas multicore y clústers de máquinas.
*Hay una división más, la del sistema Simple Program Multiple Data (SPMD) en el que un mismo programa se ejecuta en múltiples datos, éste sistema lo encontramos en la GPU por ejemplo.
*La industria ha creado procesadores capaces de ejecutar instrucciones basadas en operaciones vectorizadas y continúa desarrollándolas. Ver por ejemplo Streaming SIMD Extensions 2: SSE2 y Advanced Vector Extensions: AVX.
Otra funcionalidad que se les añadió a los procesadores para incrementar la velocidad de ejecución de un proceso* y resolver el bottleneck de Von Neumann fue la capacidad de crear hilos, threads*, de ejecución en un programa contenidos en un proceso, el llamado threading o hyperthreading en una CPU o en un core. Básicamente el threading permite la ejecución de más de una instrucción en un mismo core "virtualizando" un procesador adicional (el sistema operativo "cree" que en lugar de haber un core hay dos).
*Un proceso es una instancia de un programa que se ejecuta en el procesador y está compuesto por elementos como por ejemplo los bloques de memoria que puede utilizar (los llamados stack y heap) e información de su estado, entre otros.
*Un thread, al igual que un proceso, es una instancia de un programa, se ejecuta en el procesador pero está contenido en el proceso del que salió. Al estar contenido en el proceso, comparte elementos de éste, tienen distinto stack de memoria (variables locales creadas en funciones) y en sistemas multicore es posible definir variables que sean accesadas por todos los threads (variables globales).
La creación de threads a partir de un proceso se le llama fork y su unión al proceso se le llama join:
Su objetivo es el almacenamiento de bits de información. Como ejemplos tenemos la memoria RAM, discos duros o el caché. La principal diferencia entre cada tipo de unidad de memoria es la velocidad a la que pueden leer/escribir datos. Ésta velocidad depende enormemente de la forma en que se leen los datos. Por ejemplo, la mayoría de las unidades de memoria tienen un mejor performance al leer un gran pedazo de información que al leer muchos pedacitos*.
*Desde el punto de vista de los lenguajes de programación como Python o R, un resultado del manejo automático de memoria en estos lenguajes, es la fragmentación de datos o data fragmentation que surge al no tener bloques contiguos de memoria. Esto causa que en lugar de mover todo un bloque contiguo de datos en una sola transferencia a través del bus se requieran mover pedazos de memoria de forma individual lo que causa un mayor tiempo de lectura.
Las unidades de memoria tienen latencia* que típicamente cambia dependiendo de una jerarquía de almacenamiento mostrada en el dibujo siguiente:
*Entiéndase por latencia el tiempo que le toma a la unidad o dispositivo para encontrar los datos que serán usados por el proceso.
En el dibujo anterior se representan típicos dispositivos de almacenamiento en una máquina. La capacidad de almacenamiento disminuye conforme nos movemos hacia arriba en el dibujo: mientras que en disco podemos almacenar terabytes de información, en los registers sólo podemos almacenar bytes o kilobytes. Por el contrario, la velocidad de lectura/escritura disminuye conforme nos movemos hacia abajo: la lectura y escritura en disco es órdenes de veces más tardado que en los registers (que físicamente están en el procesador).
Entre las técnicas que tenemos a nuestro alcance para que un algoritmo pueda aprovechar el data layout de la información se encuentra el caching: el eficiente uso del caché. El caché es una memoria que está físicamente localizada más cercana a los registers del procesador para almacenar datos e instrucciones por lo que pueden ser accesados en menor tiempo que en otras unidades de memoria (como la RAM).
El caché se diseñó para resolver el Von Neumann bottleneck al existir un límite de tasa de transferencia entre la memoria RAM y el procesador (CPU o GPU). Si pudiéramos mover datos de una forma infinitamente rápida, no necesitaríamos al caché pues el procesador podría obtener los datos en cualquier instante, en esta situación no existiría tal bottleneck.
Aunque no tenemos en nuestros lenguajes de programación instrucciones del tipo "carga los datos en el caché" podemos usar los principios de localidad y temporalidad para mejorar la eficiencia de nuestros algoritmos. Los principios de localidad y temporalidad consisten en que el sistema de memoria tiende a usar los datos e instrucciones que físicamente son cercanos (localidad) y los datos e instrucciones que recientemente fueron usados (temporalidad).
¿Cómo funciona el acceso a la memoria en un sistema de computadora? Si el procesador requiere un conjunto de datos para ejecutar instrucciones, el sistema de memoria carga un bloque de datos (aunque pueden ser también instrucciones), conocido como cache blocks o cache lines para que el procesador opere en ellos.
Ejemplo:
En C al declarar un arreglo con la línea: float z[20]; se le solicita al sistema de memoria que se alojen $20$ bloques contiguos de ubicaciones de memoria en la RAM, esto es: la ubicación para el almacenamiento de z[1] está inmediatamente después de la de z[0]. Si además tenemos un programa como el siguiente:
...
float z[20];
float sum=0;
int i=0;
for(i=0;i<20;i++)
sum+=z[i];
...y nuestro cache line permite almacenar $16$ floats, entonces el sistema de memoria leerá los datos z[0],...,z[15] de la RAM al caché y el procesador realizará la suma.
Posteriormente el procesador (que en este caso es la CPU) al accesar a los datos checa primero el caché, si las encontró se le conoce como cache hit, si no lo encontró sería un cache miss y el sistema de memoria tendría que leer nuevamente desde la RAM.
Ejemplo 2:
C almacena los arreglos de dos dimensiones en una forma row major, esto es, aunque en papel representamos tales arreglos como un bloque rectangular, en la implementación en este lenguaje se están almacenando como un arreglo de una dimensión: el renglón $0$ es almacenado primero, a continuación el renglón $1$ y así sucesivamente.
Observemos los siguientes códigos que realizan una multiplicación secuencial entre una matriz A y un vector x para obtener al vector y:
Algoritmo: multiplicación matriz vector secuencial
double A[MAX][MAX], x[MAX], y [MAX]; //MAX es un valor constante definido previamente
...
//bloque de código para inicializar A,x
//bloque de código para inicializar y con ceros
//Algoritmo 1:
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
y[i]+=A[i][j]*x[j];
//volver a asignar a y con ceros
//Algoritmo 2:
for(j=0;j<MAX;j++)
for(i=0;i<MAX;i++)
y[i]+=A[i][j]*x[j];Supongamos que MAX=4 y los elementos de A están almacenados en memoria como sigue:
para simplificar el siguiente análisis supóngase que:
Ninguno de los elementos de A están en el caché al iniciar el par de loops.
Un cache line consiste de $4$ elementos de A y A[0][0] es el primer elemento del cache line.
Cada cache line le corresponde una única úbicación en el caché al que será asignado.
El caché sólo puede almacenar $4$ elementos de A o un cache line.
Entonces para el algoritmo $1$ se tiene que la CPU y el sistema de memoria:
1) La CPU requiere A[0][0] que no se encuentra en el caché por lo que tenemos un cache miss y el sistema de memoria lee de RAM el cache line: A[0][0] A[0][1] A[0][2] A[0][3] y al estar en caché la CPU puede operar con A[0][0].
2) La CPU requiere A[0][1] que sí se encuentra en el caché por lo que tenemos un cache hit y la CPU opera con éste dato. Posteriormente la CPU requiere A[0][2], A[0][3] y A[0][4] que se encuentran en cache y se tienen otros tres cache hits.
3) La CPU requiere A[1][0] que resulta en un cache miss y el sistema de memoria lee de RAM el cache line: A[1][0] A[1][1] A[1][2] A[1][3] y al estar en caché la CPU puede operar con A[1][0].
...
Finalmente para el algoritmo $1$ tenemos $4$ cache misses, uno por cada renglón.
Ejercicio: calcular el número de cache misses para el algoritmo 2.
Mayor número de cache misses incrementa el tiempo de ejecución de las instrucciones por el procesador pues no solamente el procesador espera mientras se transfieren los datos de la RAM hacia el caché sino también se interrumpe el flujo de la ejecución del pipeline*. Por ello es importante que los algoritmos trabajen con un buen data layout de la información y utilicen el data reuse y data locality.
*El pipelining es un mecanismo utilizado por un procesador para la ejecución de instrucciones. Obstáculos al pipelining se encuentran los cache misses o el llamado mispredicted branching. El branch prediction, relacionado con el branching en un código (para el branching piénsese por ejemplo en una línea de código del tipo if...then), es otro mecanismo del procesador para tratar de predecir la siguiente instrucción a ejecutar y cargar las porciones relevantes de memoria en el caché mientras se trabaja en la instrucción actual. El procesador al toparse con un branching en el código trata de hacer una suposición de qué dirección se tomará en el branching y precargar las instrucciones relevantes, si falla tiene branch-misses. Aunque también son importantes estos aspectos al considerar la impelmentación de un algoritmo, la herramienta más rápida que tenemos para resolver los bottlenecks en este contexto, son trabajar en la localidad y temporalidad de los datos.
Comentarios:
En Python se tiene el paquete de numpy para almacenamiento de bloques de memoria contiguos de arreglos y uso de la capacidad de la CPU para operaciones en un modo vectorizado. Sin extensiones a Python con paquetes como numpy no sería posible en este lenguaje aprovechar la vectorización (capaz de realizar un procesador actual) ni alojar bloques de memoria contiguos. El no soporte para operaciones vectorizadas tiene que ver con que el bytecode de Python no está optimizado para vectorización. En el caso del alojamiento de bloques de memoria contiguos, Python es un garbage-collected language (memoria es automáticamente alojada y liberada) por lo que se tienen problemas del tipo data and memory fragmentation que afecta la transferencia de datos al caché.
Para monitoreo de número de instrucciones por ciclo, número de ciclos por segundo, branch misses, cache references (o hits) y misses se recomienda la herramienta de perf o valgrind, ver también: Valgrind.
Hay distintos bus que permiten la comunicación entre las unidades computacionales y las de memoria:
El backside bus que permite la conexión entre el caché y el procesador. Tiene la tasa de transferencia de datos más alta.
El frontside bus permite la conexión entre la RAM y los L's cachés. Mueve los datos para ser procesados por el procesador (CPU o GPU) y mueve los datos de salida (resultados).
El external bus cuya acción se realiza en los dispositivos de hardware como los discos duros y tarjetas de memoria hacia la CPU y el sistema de memoria. Este bus típicamente es más lento que el frontside bus.
Entonces los datos se mueven del disco hacia la RAM con el external bus, luego de la RAM hacia el caché vía el frontside bus y finalmente del caché hacia la CPU con el backside bus.
Comentarios:
Muchos de los drawbacks al usar la GPU viene del bus a la cual está conectada pues éste procesador al estar en un dispositivo periférico, se comunica através del PCI bus, (ver PCI) el cual es más lento que el frontside bus. Como resultado, la transferencia de datos hacia la GPU y fuera de ésta es una operación costosa. Un diseño que atiende este problema es tener tanto a la CPU como a la GPU en el frontside bus para reducción de costos de transferencia hacia la GPU para grandes cantidades de información.
Otra capa de comunicación en un sistema de computadora es la red o network. Un dispositivo de red puede conectarse a una unidad de memoria u a otra unidad de computación. Típicamente la comunicación por red es mucho más lenta que las comunicaciones descritas en esta sección.
La propiedad principal de un bus es su velocidad: ¿cuántos datos pueden moverse en un periodo de tiempo? Esta propiedad se obtiene combinando el bus width entendido como ¿cuántos datos se pueden mover en una transferencia? (físicamente se puede observar por el número de cables del bus) y el bus frequency ¿cuántas transferencias se pueden hacer por segundo? (físicamente se ve en la longitud de los cables que unen a las unidades de cómputo o memoria).
Es importante notar que el movimiento de los datos en una transferencia siempre es secuencial: un pedazo de datos es leído de memoria y es movido a otro lugar: no es posible leer un pedazo de datos y moverlo a distintos lugares o leer divisiones del pedazo de datos que estén en distintos lugares.
Un bus width grande ayuda a la vectorización pues en una sola transferencia se mueven los datos importantes. Un bus frequency alto puede ayudar al código a realizar una gran candidad de lecturas de diferentes lugares de la memoria. Depende qué operación es la que se desea realizar lo que en un caso u otro convendrá pues podríamos tener un bus frequency alto y un bus width pequeño y aún así resolver el bottleneck que tenemos, si el problema a resolver se relaciona con la cantidad de lecturas que se deben hacer, por ejemplo.
La distinción entre los términos de paralelo y distribuido es borrosa y díficil de distinguir pero el término paralelo típicamente se relaciona con programas cuya ejecución involucra cores o nodos que físicamente son cercanos y comparten memoria o están conectados por una red (network). Los programas distribuidos son ejecutados por nodos o máquinas separadas a distancia y una de sus características es que no necesariamente fueron iniciados por un nodo central o master por lo que su ejecución es independiente de los demás nodos.
El término de concurrencia se refiere a que las múltiples tareas que debe realizar un programa pueden estar en progreso en cualquier instante. Por ejemplo: cada vez que tu código lee un archivo o escribe a un dispositivo, debe pausar su ejecución para contactar al kernel* del sistema operativo, solicitar que se ejecute tal operación, y esperar a que se complete (otra operación que requiere contactar al kernel es alojamiento de memoria). Estas operaciones son órdenes de magnitud más lentas que las instrucciones u operaciones ejecutadas en la CPU y el tiempo que el programa espera a que se completen tales operaciones se le llama I/O wait. La concurrencia nos ayuda a utilizar este tiempo perdido al permitir ejecutar operaciones mientras que una operación I/O se complete. Un programa concurrente en lugar de ejecutarse de forma secuencial, esto es, pasar de una línea a otra línea, tiene código escrito para ejecutar distintas líneas conforme sucedan "eventos". Aquí se involucra una forma de programación llamada asíncrona, por ejemplo si una operación tipo I/O es solicitada, el programa ejecuta otras funciones mientras espera que se complete la operación I/O.
* Ver kernel operating system) para definición del kernel de una máquina.
Comentario: cambiar de función a función en un programa asíncrono también genera costo pues el kernel debe invertir tiempo en hacer todo el set up para ejecutar a la función. La concurrencia funciona bien en programas con alto I/O wait.
La decisión de reescribir tu programa secuencial en un programa en paralelo depende mucho de considerar cuatro situaciones:
Tener el hardware para ejecución en paralelo del programa.
Comunicarle al programa que está en un hardware para ejecución en paralelo de instrucciones.
Tener un método que aproveche el hardware paralelo de forma eficiente.
Tiempo invertido en la reescritura de un código secuencial a uno en paralelo vs ganancias en tiempo de ejecución.
Lo primero es fácilmente alcanzable pues hoy en día tenemos celulares con múltiples cores o procesadores. Lo segundo es más dependiente del lenguaje e implementación de éste lenguaje en el que se esté programando. El tercer punto es quizás el más complicado de lograr pues en ocasiones implica repensar el método, disminuir la comunicación lo más posible entre los procesadores, el balanceo de carga o load balancing debe evaluarse y el perfilamiento o el debugging es más difícil en la programación en paralelo que en la forma secuencial. El cuarto punto es esencial para la decisión.
¿Cuando es recomendable pensar en ejecutar en paralelo tu programa?
Si tus instrucciones a realizar pueden ser divididas en múltiples cores o nodos sin tanto esfuerzo de ingeniería (levantar un clúster de cero es difícil...) o no te lleva mucho tiempo el rediseño de tus métodos para decisiones prácticas (paralelizar el método de despomposición en valores singulares, SVD, es difícil de realizar...) entonces es una opción a considerar. Se recomienda mantener el nivel de paralelización lo más simple posible (aunque no se esté utilizando el 100\% de todos tus cores) de modo que el desarrollo de programas sea rápido.
Si tengo n procesadores ¿espero un speedup de $nx$?
Normalmente no se tiene un mejoramiento en la velocidad de $n$ veces ($nx$) (por ejemplo, si tienes una máquina de $8$ cores es poco probable que observes un $8x$ speedup). Las razones de esto tienen que ver con que al paralelizar instrucciones típicamente se incrementa el overhead de la comunicación entre los procesos o threads y decrece la memoria RAM disponible que puede ser usada por subprocesos o threads. También dentro de las razones se encuentran la ley de Amdahl que nos dice que si sólo una parte del código puede ser paralelizado, no importa cuántos cores tengas, en términos totales el código no se ejecutará más rápido en presencia de secciones secuenciales que dominarán el tiempo de ejecución.
¿A qué nos referimos al escribir overhead en un programa cuya ejecución es en paralelo?
A todo lo que implica ejecutar el programa en paralelo que no está presente en la ejecución en una forma secuencial. Por ejemplo, iniciar procesos implica comunicación con el kernel del sistema operativo y por tanto, tiempo.
¿Cuáles enfoques puedo utilizar para escribir programas en paralelo?
Hay $2$ enfoques muy utilizados para escribir programas en paralelo:
Paralelizar las tareas entre los cores. Su característica principal es la ejecución de instrucciones distintas en los cores. Por ejemplo: al llegar la persona invitada a casa, María le ofrecerá de tomar y Luis le abrirá la puerta.
Paralelización de los datos entre los cores. Su característica principal es la ejecución de mismas instrucciones en datos que fueron divididos por alguna metodología previa. Por ejemplo: tú repartes la mitad del pastel a las mesas 1,2 y 3, y yo la otra mitad a las mesas 4,5 y 6.
Comentarios:
No son enfoques excluyentes, esto es, podemos encontrar ambos en un mismo programa. La elección de alguno de éstos enfoques depende del problema y del software que será usado para tal enfoque.
Obsérvese que en el ejemplo de María y Luis necesitan coordinarse, comunicarse y sincronizarse para tener éxito en recibir a la invitada.
Obsérvese que en el ejemplo de repartir el pastel se requiere un buen load balancing pues no queremos que yo le reparta a $5$ mesas y tú le repartas a sólo una!.
¿A qué nos referimos con el término embarrassingly parallel problem?
A los problemas en los que la comunicación entre procesos o threads es cero. Por ejemplo sumar un array a con un array b.
Y en general si evitamos compartir el estado (pensando a la palabra "estado" como un término más general que sólo comunicación) en un sistema paralelo nos hará la vida más fácil (el speedup será bueno, el debugging será sencillo, el perfilamiento será más fácil de realizar...).
¿Cómo inicio en la programación en paralelo de mi código?
Ian Foster en su libro "Designing and Building Parallel Programs" da una serie de pasos que ayudan a la programación en paralelo:
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.
Communication. Determine what communication needs to be carried out among the tasks identified in the previous step.
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.
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.
Comentario: en ocasiones es mejor dejar las tareas simples y redundantes que complicarlas y no redundantes. Por ejemplo, si en el programa en paralelo varios procesadores o threads hacen tarea redundante pero me evitan la comunicación, prefiero este programa a uno en el que haga trabajo no redundate y muy específico a cada procesador o thread pero que la comunicación a realizar sea muy complicada o compleja.
Preguntas de comprehensión
1) ¿Qué factores han influido en que desde el 2002-2003 a la fecha, el performance de los procesadores se esté incrementando en un 20% por año vs el 50% de incremento por año que se tenía entre 1986 y 2002?
2) Menciona los componentes y realiza un esquema de una arquitectura von Neumann y descríbelas.
3) Menciona la ley de Amdahl.
4) ¿Qué es un proceso y de qué consta?
5) ¿Qué es un thread?
6) ¿Qué es el threading? ¿qué ventajas nos da para la programación en un sistema de memoria compartida?
7) ¿Qué es el caché?
8) Nosotros como programadores o programadoras, ¿cómo podemos obtener ventajas del cache?
9) ¿Qué es un cache hit? ¿un cache miss?
10) De acuerdo a la taxonomía de Flynn, ¿qué tipos de arquitecturas existen? Menciona sus características, ventajas /desventajas y ejemplos.
11) Menciona algunos ejemplos de:
a. sistemas de memoria distribuida.
b. sistemas de memoria compartida.
12) ¿Qué es el pipelining y el branch prediction?
13) Menciona los distintos bus o interconexiones en un sistema de computadora y su propiedad principal o lo que nos interesa medir en un bus.
14) ¿Qué significan los términos concurrencia, paralelo, distribuido?
15) ¿Cuáles son los enfoques que se utilizan para escribir programas en paralelo?
16) Define a cuál enfoque corresponde (de acuerdo a la pregunta 13) cada uno de los siguientes incisos:
a) Supón que tienes 2 cores y un arreglo de tamaño 100
if(rango_core módulo 2 == 0 )
operar en los elementos 50 a 99
else
operar en los elementos 0 a 49
Donde módulo es una operación que nos devuelve el residuo al dividir un número entre otro.
b) Tenemos tres trabajadores: Aurora, Pedro, Daniel
if(mi_nombre es Pedro)
lavo el baño
else
voy de compras
17) En el cómputo en paralelo debemos realizar coordinación entre procesos o threads y considerar el load balancing. Menciona tipos de coordinación que existen y ¿a qué se refiere el load balancing?
18) ¿Cuáles son los pasos a seguir, que de acuerdo a Ian Foster, un@ puede seguir para el diseño de programas en paralelo?
Referencias:
P. Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann, 2011.
M. Gorelick, I. Ozsvald, High Performance Python, O'Reilly Media, 2014.