1. Introducción

¿Cómo podemos alcanzar el máximo rendimiento de una máquina? El desafío de crear un algoritmo que se pueda implementar en una máquina paralela utilizando su arquitectura de tal manera que produzca un tiempo de reloj más rápido es la pregunta que impulsa la computación paralela. A pesar del avance y la complejidad de la arquitectura moderna de la computadora, todavía es una máquina finita y hay limitaciones que deben tenerse en cuenta al implementar un algoritmo. Por ejemplo, ¿el código de computadora traducido funciona con la máxima eficiencia sin exceder los límites de memoria? Esto no significa que el código deba tener pocas operaciones. De hecho, al usar dos algoritmos diferentes, el que tiene más operaciones puede ser más eficiente si las operaciones se ejecutan al mismo tiempo (en paralelo), en comparación con el algoritmo con menos operaciones que se ejecutan en serie.

Entonces, ¿cómo podemos utilizar una máquina paralela para ejecutar un número óptimo de operaciones dentro de un algoritmo dado? Hay muchos problemas que deben abordarse para responder esta pregunta, como la partición de tareas, el mapeo de tareas independientes en múltiples procesadores o la programación de tareas, y la asignación simultánea de tareas a uno o más procesadores. Sincronización de tareas, determinando un orden de ejecución para que la información intercambiada entre tareas mantenga el progreso deseado de iteraciones necesarias para el algoritmo; También debe ser tomado en consideración. Otra cuestión a tener en cuenta es la implementación de un algoritmo que depende de las características específicas de la arquitectura de computadora paralela. Además de proporcionar una aplicabilidad limitada, este enfoque haría que el algoritmo se vuelva obsoleto una vez que la arquitectura cambie en uno de los campos que cambian más rápidamente en todo el mundo.

Hay muchos elementos a considerar cuando se trata de optimización paralela y es necesario saber qué modelo o modelos le ayudarán a lograr una eficiencia óptima. Dos modelos importantes son el paralelismo de control, que pertenece a la partición de conjuntos de instrucciones que son independientes y se ejecutan simultáneamente, así como el paralelismo de datos, relacionado con la ejecución simultánea de instrucciones en muchos elementos de datos por parte de muchos procesadores. Después de leer esta publicación técnica, debería comprender mejor los principios detrás del control y el paralelismo de datos. Además, obtenga una comprensión básica de varias técnicas para ejecutar un número óptimo de operaciones al mismo tiempo que utiliza una máquina paralela; y posee una mayor comprensión general sobre los problemas, técnicas y aplicaciones de la computación paralela.

2.1 Peligros y convenciones de la programación a una arquitectura paralela específica

Cuando se diseña un algoritmo paralelo que utiliza el rendimiento máximo de una máquina, a menudo se logra solo a través de la implementación de un algoritmo que explota esa arquitectura específica. Sin embargo, al adoptar un enfoque más general, uno puede diseñar un algoritmo que no dependa de una arquitectura específica, pero que aún así se encuentre cerca de la eficiencia de rendimiento máxima. Este enfoque es muy deseado y debe usarse sobre un diseño de algoritmo que depende de una arquitectura específica. Esto asegurará que el algoritmo no se vuelva obsoleto una vez que cambie la arquitectura y también mejorará la aplicabilidad. Existen tantas arquitecturas paralelas diversas y un algoritmo debería tener la flexibilidad suficiente para permitir su implementación en un rango de arquitecturas sin un alto grado de dificultad.

2.2 Control y paralelismo de datos

Hay dos modelos que ayudan a facilitar la implementación de algoritmos paralelos en una amplia gama de arquitecturas paralelas, control de paralelismo y paralelismo de datos. El paralelismo de control divide las instrucciones de un programa en conjuntos de instrucciones que pueden ejecutarse simultáneamente debido a que los conjuntos son independientes entre sí. La canalización es un tipo popular de paralelismo de control. El paralelismo de datos implementa simultáneamente instrucciones en muchos elementos de datos utilizando muchos procesadores creando tareas a partir de la partición de los datos de problemas y luego distribuyéndolos a múltiples procesadores. Se pueden programar múltiples tareas en el mismo procesador para su ejecución, por lo que la cantidad real de procesadores en la máquina de destino no es crítica. El paralelismo de datos generalmente se favorece sobre el paralelismo de control porque los problemas se convierten en una mayor complejidad del algoritmo y el código permanece sin cambios, solo aumenta la cantidad de datos. Debido a esto, el paralelismo de datos permite que se utilicen más procesadores para problemas a gran escala.

2.3 Particionamiento de tareas, programación y sincronización

Un algoritmo paralelo que requiere una gran cantidad de operaciones para alcanzar una solución puede ser más eficiente que un algoritmo secuencial con menos operaciones. Entonces, la pregunta es, ¿de qué manera afecta el paralelismo a los cálculos? Hay problemas específicos que deben abordarse al diseñar un algoritmo adecuado para una implementación paralela y son la partición de tareas, la programación de tareas y la sincronización de tareas.

2.3.1 Particionamiento de tareas

La partición de tareas se ocupa del problema de las operaciones de partición o los datos en tareas independientes que se asignarán en varios procesadores. Las operaciones de un algoritmo se dividen en conjuntos que son independientes entre sí y se superponen en la duración de su ejecución. Los datos del problema se dividen en bloques sin interdependencias y están disponibles antes para procesar múltiples bloques en paralelo. Una Tarea es el nombre dado a las particiones de operaciones o bloques de datos independientes. La partición de tareas se vuelve más fácil de resolver en algoritmos diseñados con operaciones independientes o algoritmos que mantienen pequeños subconjuntos de los datos del problema en cada paso. Por lo tanto, al abordar el problema de la partición de tareas a través del diseño de algoritmos adecuados, el diseñador de algoritmos puede ayudar al programador de aplicaciones ayudando a eliminar un problema grave en la programación paralela.

2.3.2 Programación de tareas

La programación de tareas aborda el problema de determinar cómo asignar tareas a uno o más procesadores para la ejecución simultánea. Este problema no se puede dejar solo al programador debido a la gran variedad de arquitecturas; el diseñador de algoritmos debe diseñar un algoritmo que se pueda estructurar para utilizar el número de procesadores disponibles en una variedad de arquitecturas diferentes. Sin embargo, se puede obtener una solución satisfactoria en la programación de tareas a los procesadores para una variedad de arquitecturas si el algoritmo teórico de suscripción es flexible. Por lo tanto, siempre que las operaciones del algoritmo se puedan estructurar para tener tantas tareas independientes como la cantidad de procesadores disponibles, el programador debería poder resolver cualquier problema de programación.

2.3.3 Sincronización de tareas

La sincronización de tareas es la cuestión de determinar un orden para la ejecución de las tareas y las instancias en las que se debe llevar a cabo la información para garantizar el correcto progreso de las iteraciones según el algoritmo a través de su ejecución. Esto puede parecer un problema que se resuelve estrictamente por la implementación del programador; sin embargo, un diseño de algoritmo cuya convergencia esté garantizada para garantizar que los requisitos de sincronización no sean excesivos probablemente sea más eficiente cuando se implementa en una arquitectura paralela.

2.4 Modelos de profundidad de trabajo

Un modelo de profundidad de trabajo quita el foco a cualquier máquina en particular y lo enfoca en el algoritmo al examinar el número total de operaciones realizadas por ese algoritmo y las dependencias entre esas operaciones. El trabajo W del algoritmo es el número total de operaciones realizadas; La profundidad D es la cadena de dependencias más larga a través de sus operaciones. La relación P = W / D se llama el paralelismo del algoritmo. La ventaja de utilizar un modelo de profundidad de trabajo es la falta de detalles dependientes de la máquina que se utilizan en otros modelos que solo sirven para complicar el diseño y análisis de algoritmos. La siguiente figura muestra un circuito para sumar 16 números. Todos los arcos o aristas se dirigen hacia la parte inferior, los arcos de entrada están en la parte superior, cada nodo + agrega los valores de cada arco entrante y coloca el resultado en su arco saliente. La suma de todas las entradas se devuelve en la salida única en la parte inferior.

Dejar respuesta

Please enter your comment!
Please enter your name here