stringtranslate.com

Esqueleto algorítmico

En informática , los esqueletos algorítmicos , o patrones de paralelismo , son un modelo de programación paralela de alto nivel para la computación paralela y distribuida.

Los esqueletos algorítmicos aprovechan los patrones de programación comunes para ocultar la complejidad de las aplicaciones paralelas y distribuidas. A partir de un conjunto básico de patrones (esqueletos), se pueden construir patrones más complejos combinando los básicos.

Descripción general

La característica más destacada de los esqueletos algorítmicos, que los diferencia de otros modelos de programación paralela de alto nivel, es que la orquestación y sincronización de las actividades paralelas está definida implícitamente por los patrones de esqueleto. Los programadores no tienen que especificar las sincronizaciones entre las partes secuenciales de la aplicación. Esto produce dos implicaciones. En primer lugar, como los patrones de comunicación/acceso a datos se conocen de antemano, los modelos de costos se pueden aplicar para programar programas esqueleto. [1] En segundo lugar, que la programación de esqueletos algorítmicos reduce el número de errores en comparación con los modelos tradicionales de programación paralela de nivel inferior (Threads, MPI).

Programa de ejemplo

El siguiente ejemplo se basa en la biblioteca Java Skandium para programación paralela.

El objetivo es implementar una versión paralela basada en el esqueleto algorítmico del algoritmo QuickSort utilizando el patrón Divide and Conquer. Observe que el enfoque de alto nivel oculta la gestión de subprocesos al programador.

// 1. Definir el programa esqueleto Skeleton < Range , Range > sort = new DaC < Range , Range > ( new ShouldSplit ( thunder , maxTimes ), new SplitList (), new Sort (), new MergeList ()); // 2. Parámetros de entrada Future < Range > future = sort . input ( new Range ( generate (...))); // 3. Hacer algo más aquí. // ... // 4. Bloque para los resultados Range result = future . get ();
  1. Lo primero es definir una nueva instancia del esqueleto con el código funcional que rellena el patrón (ShouldSplit, SplitList, Sort, MergeList). El código funcional lo escribe el programador sin preocupaciones de paralelismo.
  2. El segundo paso es la entrada de datos que activa el cálculo. En este caso, Range es una clase que contiene una matriz y dos índices que permiten la representación de una submatriz. Por cada dato ingresado en el marco, se crea un nuevo objeto Future. Se puede ingresar más de un Future en un esqueleto simultáneamente.
  3. El futuro permite el cálculo asincrónico, ya que se pueden realizar otras tareas mientras se calculan los resultados.
  4. Podemos recuperar el resultado del cálculo, bloqueándolo si es necesario (es decir, resultados aún no disponibles).

Los códigos funcionales en este ejemplo corresponden a cuatro tipos: Condición, Dividir, Ejecutar y Fusionar.

La clase pública ShouldSplit implementa Condición < Rango > {     int umbral , maxTimes , veces ; público ShouldSplit ( int umbral , int maxTimes ) { este.umbral = umbral ; este.maxTimes = maxTimes ; este.times = 0 ; } @Override público sincronizado condición booleana ( Rango r ) { devolver r.derecha - r.izquierda > umbral && veces ++ < este.maxTimes ; } }​​​​​​​​​​

La clase ShouldSplit implementa la interfaz Condition. La función recibe una entrada, Range r en este caso, y devuelve verdadero o falso. En el contexto de Divide and Conquer donde se usará esta función, decidirá si una submatriz debe subdividirse nuevamente o no.

La clase SplitList implementa la interfaz split, que en este caso divide una (sub)matriz en submatrices más pequeñas. La clase utiliza una función auxiliar partition(...)que implementa el conocido esquema de pivotación e intercambio QuickSort.

La clase pública SplitList implementa Split < Range , Range > {      @Override public Range [] split ( Range r ){ int i = partición ( r . matriz , r . izquierda , r . derecha ); Range [] intervalos = { nuevo Range ( r . matriz , r . izquierda , i - 1 ), nuevo Range ( r . matriz , i + 1 , r . derecha )}; devolver intervalos ; } }

La clase Sort implementa una interfaz Execute y se encarga de ordenar la submatriz especificada por Range r. En este caso, simplemente invocamos el método predeterminado de Java (Arrays.sort) para la submatriz dada.

La clase pública Sort implementa Execute < Range , Range > {       @Override public Range ejecutar ( Range r ){ si ( r . derecha <= r . izquierda ) devolver r ; Matrices . sort ( r . matriz , r . izquierda , r . derecha + 1 ); devolver r ; } }

Finalmente, una vez que se ordena un conjunto de submatrices, fusionamos las partes de la submatriz en una matriz más grande con la clase MergeList que implementa una interfaz Merge.

La clase pública MergeList implementa Merge < Range , Range > {      @Override public Range merge ( Range [] r ){ Resultado del rango = nuevo Rango ( r [ 0 ] . array , r [ 0 ] . left , r [ 1 ] . right ); devolver resultado ; } }

Marcos y bibliotecas

ASISTIR

ASSIST [2] [3] es un entorno de programación que proporciona a los programadores un lenguaje de coordinación estructurado. El lenguaje de coordinación puede expresar programas paralelos como un gráfico arbitrario de módulos de software. El gráfico de módulos describe cómo un conjunto de módulos interactúa entre sí utilizando un conjunto de flujos de datos tipificados. Los módulos pueden ser secuenciales o paralelos. Los módulos secuenciales se pueden escribir en C, C++ o Fortran; y los módulos paralelos se programan con un módulo paralelo especial de ASSIST ( parmod ).

AdHoc, [4] [5] un sistema de memoria compartida distribuida (DSM) jerárquico y tolerante a fallos se utiliza para interconectar flujos de datos entre elementos de procesamiento proporcionando un repositorio con operaciones de obtención/colocación/eliminación/ejecución. La investigación en torno a AdHoc se ha centrado en la transparencia, la escalabilidad y la tolerancia a fallos del repositorio de datos.

Si bien no es un marco de esqueleto clásico, en el sentido de que no se proporcionan esqueletos, el parmod genérico de ASSIST se puede especializar en esqueletos clásicos como: farm , map , etc. ASSIST también admite el control autónomo de parmods y puede estar sujeto a un contrato de rendimiento adaptando dinámicamente la cantidad de recursos utilizados.

CO2P3S

CO2P3S (Sistema de programación paralela basado en patrones orientados a objetos correctos), es un entorno de desarrollo orientado a patrones, [6] que logra paralelismo utilizando subprocesos en Java.

CO2P3S se ocupa del proceso completo de desarrollo de una aplicación paralela. Los programadores interactúan a través de una interfaz gráfica de programación para elegir un patrón y sus opciones de configuración. Luego, los programadores completan los ganchos necesarios para el patrón y se genera un nuevo código como marco en Java para la ejecución paralela de la aplicación. El marco generado utiliza tres niveles, en orden descendente de abstracción: capa de patrones, capa de código intermedio y capa de código nativo. Por lo tanto, los programadores avanzados pueden intervenir en el código generado en múltiples niveles para ajustar el rendimiento de sus aplicaciones. El código generado es en su mayoría seguro en cuanto a tipos , ya que utiliza los tipos proporcionados por el programador que no requieren la extensión de la superclase, pero no es completamente seguro en cuanto a tipos, como en el método reduce(..., Object reducer) en el patrón de malla.

El conjunto de patrones admitidos en CO2P3S corresponde a secuencia de métodos, distribuidor, malla y frente de onda. Se pueden crear aplicaciones complejas componiendo marcos con sus referencias de objetos. Sin embargo, si ningún patrón es adecuado, la herramienta gráfica MetaCO2P3S aborda la extensibilidad al permitir que los programadores modifiquen los diseños de patrones e introduzcan nuevos patrones en CO2P3S.

El soporte para arquitecturas de memoria distribuida en CO2P3S se introdujo más adelante. [7] Para utilizar un patrón de memoria distribuida, los programadores deben cambiar la opción de memoria del patrón de compartida a distribuida y generar el nuevo código. Desde la perspectiva de uso, la versión de memoria distribuida del código requiere la gestión de excepciones remotas.

Calcio y escandio

Calcium está inspirado en gran medida en Lithium y Muskel. Como tal, proporciona programación de esqueleto algorítmico como una biblioteca Java. Tanto los esqueletos paralelos de tareas como de datos son completamente anidados y se instancian a través de objetos de esqueleto paramétricos, no de herencia.

Calcium admite la ejecución de aplicaciones de esqueleto sobre el entorno ProActive para infraestructuras distribuidas de tipo clúster. Además, Calcium tiene tres características distintivas para la programación de esqueletos algorítmicos. En primer lugar, un modelo de ajuste del rendimiento que ayuda a los programadores a identificar el código responsable de los errores de rendimiento. [8] En segundo lugar, un sistema de tipos para esqueletos anidados que ha demostrado garantizar propiedades de reducción de sujetos y se implementa utilizando Java Generics. [9] En tercer lugar, un modelo de acceso a archivos de esqueletos algorítmicos transparente, que habilita esqueletos para aplicaciones con uso intensivo de datos. [10]

Skandium es una reimplementación completa de Calcium para computación multinúcleo. Los programas escritos en Skandium pueden aprovechar la memoria compartida para simplificar la programación paralela. [11]

Edén

Eden [12] es un lenguaje de programación paralela para entornos de memoria distribuida, que extiende Haskell. Los procesos se definen explícitamente para lograr una programación paralela, mientras que sus comunicaciones permanecen implícitas. Los procesos se comunican a través de canales unidireccionales, que conectan a un escritor con exactamente un lector. Los programadores solo necesitan especificar de qué datos depende un proceso. El modelo de proceso de Eden proporciona control directo sobre la granularidad del proceso, la distribución de datos y la topología de comunicación.

Eden no es un lenguaje esqueleto en el sentido de que los esqueletos no se proporcionan como construcciones del lenguaje. En cambio, los esqueletos se definen sobre la abstracción de procesos de nivel inferior de Eden, lo que admite el paralelismo de tareas y datos . Por lo tanto, a diferencia de la mayoría de los otros enfoques, Eden permite que los esqueletos se definan en el mismo lenguaje y en el mismo nivel en el que se escribe la instanciación del esqueleto: Eden mismo. Debido a que Eden es una extensión de un lenguaje funcional, los esqueletos de Eden son funciones de orden superior . Eden introduce el concepto de esqueleto de implementación, que es un esquema independiente de la arquitectura que describe una implementación paralela de un esqueleto algorítmico.

eSkel

La biblioteca Edinburgh Skeleton Library ( eSkel ) se proporciona en C y se ejecuta sobre MPI. La primera versión de eSkel se describió en [13] , mientras que una versión posterior se presenta en [14] .

En [15] se definen el modo de anidación y el modo de interacción para los esqueletos. El modo de anidación puede ser transitorio o persistente, mientras que el modo de interacción puede ser implícito o explícito. El anidamiento transitorio significa que el esqueleto anidado se instancia para cada invocación y se destruye después, mientras que persistente significa que el esqueleto se instancia una vez y se invocará la misma instancia de esqueleto en toda la aplicación. La interacción implícita significa que el flujo de datos entre esqueletos está completamente definido por la composición del esqueleto, mientras que explícita significa que los datos se pueden generar o eliminar del flujo de una manera no especificada por la composición del esqueleto. Por ejemplo, un esqueleto que produce una salida sin recibir nunca una entrada tiene interacción explícita.

Benoit et al. [16] [17] [18] [19] exploraron la predicción del rendimiento para la programación y el mapeo de recursos, principalmente para tuberías. Proporcionaron un modelo de rendimiento para cada mapeo, basado en el álgebra de procesos, y determinaron la mejor estrategia de programación en función de los resultados del modelo.

Trabajos más recientes han abordado el problema de la adaptación en la programación paralela estructurada, [20] en particular para el esqueleto de tuberías. [21] [22]

Flujo rápido

FastFlow es un marco de programación paralela esquelético específicamente orientado al desarrollo de aplicaciones de transmisión y datos en paralelo. Inicialmente desarrollado para plataformas multinúcleo , se ha ampliado sucesivamente para apuntar a plataformas heterogéneas compuestas por clústeres de plataformas de memoria compartida, [23] [24] posiblemente equipadas con aceleradores de computación como NVidia GPGPUs, Xeon Phi, Tilera TILE64. La principal filosofía de diseño de FastFlow es proporcionar a los diseñadores de aplicaciones características clave para la programación paralela (por ejemplo, tiempo de comercialización, portabilidad, eficiencia y portabilidad del rendimiento) a través de abstracciones de programación paralela adecuadas y un soporte de tiempo de ejecución cuidadosamente diseñado. [25] FastFlow es un marco de programación C++ de propósito general para plataformas paralelas heterogéneas. Al igual que otros marcos de programación de alto nivel, como Intel TBB y OpenMP, simplifica el diseño y la ingeniería de aplicaciones paralelas portátiles. Sin embargo, tiene una clara ventaja en términos de expresividad y rendimiento con respecto a otros marcos de programación paralela en escenarios de aplicación específicos, incluidos, entre otros: paralelismo de grano fino en plataformas de memoria compartida coherentes con caché; aplicaciones de streaming; uso acoplado de múltiples núcleos y aceleradores. En otros casos, FastFlow es típicamente comparable a (y en algunos casos es ligeramente más rápido que) los marcos de programación paralela de última generación como Intel TBB, OpenMP, Cilk, etc. [26]

HDC

Higher-order Divide and Conquer ( HDC ) [27] es un subconjunto del lenguaje funcional Haskell . Los programas funcionales se presentan como funciones polimórficas de orden superior, que se pueden compilar en C/MPI y vincular con implementaciones de esqueleto. El lenguaje se centra en el paradigma de divide y vencerás y, a partir de un tipo general de esqueleto de divide y vencerás, se derivan casos más específicos con implementaciones eficientes. Los casos específicos corresponden a: profundidad de recursión fija, grado de recursión constante, recursión de múltiples bloques, operaciones elemento por elemento y comunicaciones correspondientes [28].

HDC presta especial atención a la granularidad del subproblema y su relación con el número de procesadores disponibles. El número total de procesadores es un parámetro clave para el rendimiento del programa esqueleto, ya que HDC intenta estimar una asignación adecuada de procesadores para cada parte del programa. Por lo tanto, el rendimiento de la aplicación está fuertemente relacionado con el número estimado de procesadores, lo que lleva a que se exceda el número de subproblemas o a que no haya suficiente paralelismo para explotar los procesadores disponibles.

HOC-SA

HOC-SA es un proyecto de la Incubadora Globus.
HOC-SA significa Arquitectura de Servicios de Componentes de Orden Superior. Los Componentes de Orden Superior (HOCs) tienen como objetivo simplificar el desarrollo de aplicaciones Grid.
El objetivo de HOC-SA es proporcionar a los usuarios de Globus, que no quieren conocer todos los detalles del middleware de Globus (documentos GRAM RSL, servicios web y configuración de recursos, etc.), HOCs que proporcionen una interfaz de nivel superior a Grid que el kit de herramientas principal de Globus.
Los HOCs son esqueletos habilitados para Grid, implementados como componentes sobre el kit de herramientas de Globus, a los que se puede acceder de forma remota a través de servicios web. [29]

JaSkel

JaSkel [30] es un marco de trabajo basado en Java que proporciona esqueletos como granja, tubería y latido. Los esqueletos se especializan mediante herencia. Los programadores implementan los métodos abstractos para cada esqueleto para proporcionar su código específico de aplicación. Los esqueletos en JaSkel se proporcionan en versiones secuenciales, concurrentes y dinámicas. Por ejemplo, la granja concurrente se puede utilizar en entornos de memoria compartida (subprocesos), pero no en entornos distribuidos (clústeres) donde se debería utilizar la granja distribuida. Para cambiar de una versión a otra, los programadores deben cambiar la firma de sus clases para heredar de un esqueleto diferente. La anidación de esqueletos utiliza la clase Java Object básica y, por lo tanto, no se aplica ningún sistema de tipos durante la composición del esqueleto.

Los aspectos de distribución del cómputo se manejan en JaSkel usando AOP, más específicamente la implementación de AspectJ. Por lo tanto, JaSkel se puede implementar tanto en infraestructuras de tipo clúster como de tipo Grid. [31] Sin embargo, una desventaja del enfoque de JaSkel es que la anidación del esqueleto se relaciona estrictamente con la infraestructura de implementación. Por lo tanto, una anidación doble de granjas produce un mejor rendimiento que una sola granja en infraestructuras jerárquicas. Esto frustra el propósito de usar AOP para separar las preocupaciones funcionales y de distribución del programa esqueleto.

Litio y almizcle

Lithium [32] [33] [34] y su sucesor Muskel son marcos de trabajo esqueleto desarrollados en la Universidad de Pisa, Italia. Ambos proporcionan esqueletos anidados al programador como bibliotecas Java. La evaluación de una aplicación esqueleto sigue una definición formal de semántica operacional introducida por Aldinucci y Danelutto, [35] [36] que puede manejar tanto el paralelismo de tareas como el de datos. La semántica describe tanto el comportamiento funcional como el paralelo del lenguaje esqueleto utilizando un sistema de transición etiquetado. Además, se aplican varias optimizaciones de rendimiento como: técnicas de reescritura de esqueleto [18, 10], anticipación de tareas y enlace diferido de servidor a servidor. [37]

A nivel de implementación, Lithium explota el flujo de macrodatos [38] [39] para lograr paralelismo. Cuando el flujo de entrada recibe un nuevo parámetro, el programa esqueleto se procesa para obtener un gráfico de flujo de macrodatos. Los nodos del gráfico son instrucciones de flujo de macrodatos (MDFi) que representan las piezas secuenciales de código proporcionadas por el programador. Las tareas se utilizan para agrupar varias MDFi y son consumidas por elementos de procesamiento inactivos de un grupo de tareas. Cuando finaliza el cálculo del gráfico, el resultado se coloca en el flujo de salida y, por lo tanto, se devuelve al usuario.

Muskel también proporciona características no funcionales como la calidad de servicio (QoS); [40] seguridad entre el grupo de tareas y los intérpretes; [41] [42] y descubrimiento de recursos, equilibrio de carga y tolerancia a fallos cuando se interconecta con Java / Jini Parallel Framework (JJPF), [43] un marco de ejecución distribuida. Muskel también proporciona soporte para combinar programación estructurada con programación no estructurada [44] y las investigaciones recientes han abordado la extensibilidad. [45]

Centro comercial

Mallba [46] es una biblioteca para optimizaciones combinatorias que admiten estrategias de búsqueda exacta, heurística e híbrida. [47] Cada estrategia se implementa en Mallba como un esqueleto genérico que se puede utilizar proporcionando el código requerido. En los algoritmos de búsqueda exacta, Mallba proporciona esqueletos de optimización dinámica y de ramificación y acotación. Para las heurísticas de búsqueda local, Mallba admite: escalada de colinas , metrópolis, recocido simulado y búsqueda tabú ; y también heurísticas basadas en la población derivadas de algoritmos evolutivos como algoritmos genéticos , estrategia de evolución y otros (CHC). Los esqueletos híbridos combinan estrategias, como: GASA, una mezcla de algoritmo genético y recocido simulado, y CHCCES que combina CHC y ES.

Los esqueletos se proporcionan como una biblioteca C++ y no se pueden anidar, pero son de tipo seguro. Se utiliza una capa de abstracción MPI personalizada, NetStream, que se encarga de la ordenación de tipos de datos primitivos, la sincronización, etc. Un esqueleto puede tener múltiples implementaciones paralelas de nivel inferior según las arquitecturas de destino: secuencial, LAN y WAN. Por ejemplo: maestro-esclavo centralizado, maestro-esclavo distribuido, etc.

Mallba también proporciona variables de estado que contienen el estado del esqueleto de búsqueda. El estado vincula la búsqueda con el entorno y se puede acceder a él para inspeccionar la evolución de la búsqueda y decidir acciones futuras. Por ejemplo, el estado se puede utilizar para almacenar la mejor solución encontrada hasta el momento, o los valores α, β para la poda de ramas y límites. [48]

En comparación con otros marcos, el uso que Mallba hace de los conceptos de esqueletos es único. Los esqueletos se proporcionan como estrategias de búsqueda paramétrica en lugar de patrones de paralelización paramétrica.

Médula

Marrow [49] [50] es un marco de trabajo de esqueleto algorítmico de C++ para la orquestación de cálculos OpenCL en entornos multi- GPU posiblemente heterogéneos . Proporciona un conjunto de esqueletos de tareas y datos paralelos que se pueden componer, mediante anidamiento, para construir cálculos compuestos. Los nodos de hoja de los árboles de composición resultantes representan los núcleos computacionales de GPU, mientras que los nodos restantes denotan el esqueleto aplicado al subárbol anidado. El marco de trabajo se encarga de toda la orquestación del lado del host necesaria para ejecutar correctamente estos árboles en entornos multi-GPU heterogéneos, incluido el orden adecuado de la transferencia de datos y de las solicitudes de ejecución, y la comunicación requerida entre los nodos del árbol.

Entre las características más destacadas de Marrow se encuentran un conjunto de esqueletos que antes no estaban disponibles en el contexto de la GPU, como Pipeline y Loop, y la capacidad de anidar esqueletos, una característica también nueva en este contexto. Además, el marco introduce optimizaciones que superponen la comunicación y el cálculo, enmascarando así la latencia impuesta por el bus PCIe .

La ejecución paralela de un árbol de composición de Marrow por parte de varias GPU sigue una estrategia de descomposición de datos en paralelo, que aplica simultáneamente todo el árbol computacional a diferentes particiones del conjunto de datos de entrada. Además de expresar qué parámetros del núcleo se pueden descomponer y, cuando es necesario, definir cómo se deben fusionar los resultados parciales, el programador está completamente abstraído de la arquitectura multi-GPU subyacente.

Puede encontrar más información, así como el código fuente, en el sitio web de Marrow

Muesli

La biblioteca de esqueletos Muenster Muesli [51] [52] es una biblioteca de plantillas de C++ que reimplementa muchas de las ideas y conceptos introducidos en Skil, por ejemplo, funciones de orden superior, currificación y tipos polimórficos [1]. Está construida sobre MPI 1.2 y OpenMP 2.5 y admite, a diferencia de muchas otras bibliotecas de esqueletos, tanto esqueletos paralelos de tareas como de datos. La anidación de esqueletos (composición) es similar al enfoque de dos niveles de P3L, es decir, los esqueletos paralelos de tareas se pueden anidar arbitrariamente mientras que los esqueletos paralelos de datos no, pero se pueden usar en las hojas de un árbol de anidación paralela de tareas. [53] Las plantillas de C++ se usan para hacer que los esqueletos sean polimórficos, pero no se aplica ningún sistema de tipos. Sin embargo, la biblioteca implementa un mecanismo de serialización automatizado inspirado en [54] de modo que, además de los tipos de datos MPI estándar, se pueden usar tipos de datos arbitrarios definidos por el usuario dentro de los esqueletos. Los esqueletos paralelos de tareas compatibles [55] son ​​Branch & Bound, [56] Divide & Conquer, [57] [58] Farm, [59] [60] y Pipe, los esqueletos auxiliares son Filter, Final e Initial. Los esqueletos paralelos de datos, como fold (reduce), map, permute, zip y sus variantes se implementan como funciones miembro de orden superior de una estructura de datos distribuida. Actualmente, Muesli admite estructuras de datos distribuidas para arreglos, matrices y matrices dispersas. [61]

Como característica única, los esqueletos paralelos de datos de Muesli se escalan automáticamente tanto en arquitecturas de clúster de un solo núcleo como de múltiples nodos. [62] [63] Aquí, la escalabilidad entre nodos y núcleos se garantiza mediante el uso simultáneo de MPI y OpenMP, respectivamente. Sin embargo, esta característica es opcional en el sentido de que un programa escrito con Muesli aún se compila y ejecuta en una computadora de clúster de un solo núcleo y múltiples nodos sin cambios en el código fuente, es decir, se garantiza la compatibilidad con versiones anteriores. Esto se garantiza proporcionando una capa de abstracción OpenMP muy delgada de modo que el soporte de arquitecturas de múltiples núcleos se puede activar o desactivar simplemente proporcionando u omitiendo el indicador del compilador OpenMP al compilar el programa. Al hacerlo, prácticamente no se introduce ninguna sobrecarga en el tiempo de ejecución.

P3L, SkIE, SKElib

P3L [64] (Pisa Parallel Programming Language) es un lenguaje de coordinación basado en esqueleto. P3L proporciona estructuras de esqueleto que se utilizan para coordinar la ejecución paralela o secuencial de código C. Se proporciona un compilador llamado Anacleto [65] para el lenguaje. Anacleto utiliza plantillas de implementación para compilar código P3L en una arquitectura de destino. Por lo tanto, un esqueleto puede tener varias plantillas, cada una optimizada para una arquitectura diferente. Una plantilla implementa un esqueleto en una arquitectura específica y proporciona un gráfico de proceso paramétrico con un modelo de rendimiento. El modelo de rendimiento se puede utilizar para decidir transformaciones del programa que pueden conducir a optimizaciones del rendimiento. [66]

Un módulo P3L corresponde a un esqueleto de construcción correctamente definido con flujos de entrada y salida, y otros submódulos o código C secuencial. Los módulos se pueden anidar utilizando el modelo de dos niveles, donde el nivel externo está compuesto por esqueletos paralelos de tareas, mientras que los esqueletos paralelos de datos se pueden utilizar en el nivel interno [64]. La verificación de tipo se realiza en el nivel de flujo de datos, cuando el programador especifica explícitamente el tipo de los flujos de entrada y salida, y especificando el flujo de datos entre submódulos.

SkIE [67] (Skeleton-based Integrated Environment) es bastante similar a P3L , ya que también se basa en un lenguaje de coordinación, pero proporciona características avanzadas como herramientas de depuración, análisis de rendimiento, visualización e interfaz gráfica de usuario. En lugar de utilizar directamente el lenguaje de coordinación, los programadores interactúan con una herramienta gráfica, donde se pueden componer módulos paralelos basados ​​en esqueletos.

SKELib [68] se basa en las contribuciones de P3L y SkIE al heredar, entre otros, el sistema de plantillas. Se diferencia de ellos porque ya no se utiliza un lenguaje de coordinación, sino que se proporcionan esqueletos como una biblioteca en C, con un rendimiento similar al logrado en P3L . A diferencia de Skil , otro marco de esqueletos similar a C, en SKELib no se aborda la seguridad de tipos .

PAS y EPAS

PAS (Parallel Architectural Skeletons) es un marco para la programación de esqueletos desarrollado en C++ y MPI. [69] [70] Los programadores utilizan una extensión de C++ para escribir sus aplicaciones de esqueleto1. Luego, el código se pasa a través de un script de Perl que expande el código a C++ puro, donde los esqueletos se especializan a través de la herencia.

En PAS , cada esqueleto tiene un objeto Representante (Rep) que debe ser proporcionado por el programador y se encarga de coordinar la ejecución del esqueleto. Los esqueletos se pueden anidar de forma jerárquica a través de los objetos Rep. Además de la ejecución del esqueleto, el objeto Rep también gestiona explícitamente la recepción de datos del esqueleto de nivel superior y el envío de datos a los subesqueletos. Se utiliza un protocolo de comunicación/sincronización parametrizado para enviar y recibir datos entre el esqueleto principal y los subesqueletos.

Una extensión de PAS denominada SuperPas [71] y posteriormente EPAS [72] aborda las cuestiones de extensibilidad del esqueleto. Con la herramienta EPAS , se pueden agregar nuevos esqueletos a PAS . Se utiliza un lenguaje de descripción de esqueleto (SDL) para describir el patrón de esqueleto especificando la topología con respecto a una cuadrícula de procesador virtual. Luego, el SDL se puede compilar en código C++ nativo, que se puede utilizar como cualquier otro esqueleto.

SBASCO

SBASCO ( Skeleton-BAsed Scientific COmponents ) es un entorno de programación orientado al desarrollo eficiente de aplicaciones numéricas paralelas y distribuidas. [73] SBASCO tiene como objetivo integrar dos modelos de programación: esqueletos y componentes con un lenguaje de composición personalizado. Una vista de aplicación de un componente proporciona una descripción de sus interfaces (tipo de entrada y salida); mientras que una vista de configuración proporciona, además, una descripción de la estructura interna del componente y el diseño del procesador. La estructura interna de un componente se puede definir utilizando tres esqueletos: granja, tubería y multibloque.

El sistema SBASCO se dirige a aplicaciones descomponibles en dominios a través de su esqueleto multibloque. Los dominios se especifican a través de matrices (principalmente bidimensionales), que se descomponen en submatrices con posibles límites superpuestos. El cálculo se lleva a cabo de manera iterativa, como en el BSP. La primera etapa consiste en cálculos locales, mientras que la segunda etapa realiza intercambios de límites. Se presenta un caso de uso para un problema de reacción-difusión en [74] .

En [75] se presentan dos tipos de componentes: los componentes científicos (SC), que proporcionan el código funcional; y los componentes de aspecto de comunicación (CAC), que encapsulan el comportamiento no funcional, como la comunicación, la distribución del procesador y la replicación. Por ejemplo, los componentes SC están conectados a un componente CAC, que puede actuar como administrador en tiempo de ejecución reasignando dinámicamente los procesadores asignados a un SC. En [76] se muestra un caso de uso que muestra un rendimiento mejorado al utilizar componentes CAC.

LCC

El lenguaje de coordinación estructurado ( SCL ) [77] fue uno de los primeros lenguajes de programación de esqueleto. Proporciona un enfoque de lenguaje de coordinación para la programación de esqueleto sobre componentes de software. SCL se considera un lenguaje base y fue diseñado para integrarse con un lenguaje anfitrión, por ejemplo Fortran o C, utilizado para desarrollar componentes de software secuenciales. En SCL , los esqueletos se clasifican en tres tipos: configuración , elemental y computación . Los esqueletos de configuración abstraen patrones para estructuras de datos de uso común, como matrices distribuidas (ParArray). Los esqueletos elementales corresponden a esqueletos paralelos de datos, como map, scan y fold. Los esqueletos de computación, que abstraen el flujo de control, corresponden principalmente a esqueletos paralelos de tareas, como farm, SPMD e iterateUntil. El enfoque del lenguaje de coordinación se utilizó junto con modelos de rendimiento para programar máquinas paralelas tradicionales, así como máquinas paralelas heterogéneas que tienen diferentes núcleos múltiples en cada nodo de procesamiento. [78]

SkePU

SkePU [79] SkePU es un marco de programación de esqueleto para CPU multinúcleo y sistemas multi-GPU. Es una biblioteca de plantillas C++ con seis esqueletos de datos paralelos y uno de tareas paralelas, dos tipos de contenedores y soporte para ejecución en sistemas multi-GPU tanto con CUDA como con OpenCL. Recientemente, se desarrolló en SkePU soporte para ejecución híbrida, programación dinámica consciente del rendimiento y balanceo de carga mediante la implementación de un backend para el sistema de tiempo de ejecución StarPU. SkePU se está ampliando para clústeres de GPU.

PATRÓN Y QUAFF

SKiPPER es una biblioteca de esqueletos específica de dominio para aplicaciones de visión [80] que proporciona esqueletos en CAML y, por lo tanto, se basa en CAML para la seguridad de tipos. Los esqueletos se presentan de dos maneras: declarativa y operativa. Los esqueletos declarativos son utilizados directamente por los programadores, mientras que sus versiones operativas proporcionan una implementación de destino específica de la arquitectura. A partir del entorno de ejecución, las especificaciones del esqueleto CAML y las funciones específicas de la aplicación (proporcionadas en C por el programador), se genera y compila nuevo código C para ejecutar la aplicación en la arquitectura de destino. Una de las cosas interesantes de SKiPPER es que el programa esqueleto se puede ejecutar secuencialmente para la depuración.

En SKiPPER se han explorado diferentes enfoques para escribir esqueletos operativos: gráficos de flujo de datos estáticos, redes de procesos paramétricos, gráficos de tareas jerárquicas y gráficos de flujo de datos con tokens etiquetados. [81]

QUAFF [82] es una biblioteca de esqueleto más reciente escrita en C++ y MPI. QUAFF se basa en técnicas de metaprogramación basadas en plantillas para reducir los tiempos de ejecución y realizar expansiones y optimizaciones de esqueleto en tiempo de compilación. Los esqueletos se pueden anidar y las funciones secuenciales tienen estado. Además de la verificación de tipos, QUAFF aprovecha las plantillas de C++ para generar, en tiempo de compilación, nuevo código C/MPI. QUAFF se basa en el modelo CSP, donde el programa esqueleto se describe como una red de procesos y reglas de producción (single, serial, par, join). [83]

Esqueleto

El proyecto SkeTo [84] es una biblioteca C++ que logra la paralelización usando MPI. SkeTo es diferente de otras bibliotecas de esqueletos porque en lugar de proporcionar patrones de paralelismo anidados, SkeTo proporciona esqueletos paralelos para estructuras de datos paralelas como: listas, árboles [85] [86] y matrices. [87] Las estructuras de datos se tipifican usando plantillas, y se pueden invocar varias operaciones paralelas sobre ellas. Por ejemplo, la estructura de lista proporciona operaciones paralelas como: map, reduce, scan, zip, shift, etc.

Investigaciones adicionales en torno a SkeTo también se han centrado en estrategias de optimización por transformación y, más recientemente, en optimizaciones específicas del dominio. [88] Por ejemplo, SkeTo proporciona una transformación de fusión [89] que fusiona dos invocaciones de funciones sucesivas en una sola, disminuyendo así los costos de llamadas de función y evitando la creación de estructuras de datos intermedias pasadas entre funciones.

Habilidad

Skil [90] es un lenguaje imperativo para la programación de esqueletos. Los esqueletos no son parte directa del lenguaje, pero se implementan con él. Skil utiliza un subconjunto del lenguaje C que proporciona características similares a las del lenguaje funcional, como funciones de orden superior, tipos polimórficos y de curring. Cuando se compila Skil , se eliminan dichas características y se produce un código C regular. De este modo, Skil transforma funciones polimórficas de orden superior en funciones C monomórficas de primer orden. Skil no admite la composición anidable de esqueletos. El paralelismo de datos se logra utilizando estructuras paralelas de datos específicas, por ejemplo, para distribuir matrices entre los procesadores disponibles. Se pueden utilizar esqueletos de filtro.

Estructura del esqueleto STAPL

En STAPL Skeleton Framework [91] [92] los esqueletos se definen como gráficos de flujo de datos paramétricos, lo que les permite escalar más allá de los 100.000 núcleos. Además, este marco aborda la composición de esqueletos como una composición punto a punto de sus gráficos de flujo de datos correspondientes a través de la noción de puertos, lo que permite que se agreguen fácilmente nuevos esqueletos al marco. Como resultado, este marco elimina la necesidad de reimplementación y sincronizaciones globales en esqueletos compuestos. STAPL Skeleton Framework admite la composición anidada y puede cambiar entre ejecución paralela y secuencial en cada nivel de anidamiento. Este marco se beneficia de la implementación escalable de contenedores paralelos STAPL [93] y puede ejecutar esqueletos en varios contenedores, incluidos vectores, matrices multidimensionales y listas.

T4P

T4P fue uno de los primeros sistemas introducidos para la programación de esqueletos. [94] El sistema dependía en gran medida de las propiedades de la programación funcional y se definieron cinco esqueletos como funciones de orden superior: Divide-and-Conquer, Farm, Map, Pipe y RaMP. Un programa podía tener más de una implementación, cada una de las cuales utilizaba una combinación de diferentes esqueletos. Además, cada esqueleto podía tener diferentes implementaciones paralelas. Se utilizó una metodología basada en transformaciones funcionales de programas guiadas por modelos de rendimiento de los esqueletos para seleccionar el esqueleto más apropiado para ser utilizado en el programa, así como la implementación más apropiada del esqueleto. [95]

Comparación de marcos

Véase también

Referencias

  1. ^ K. Hammond y G. Michelson, editores. "Direcciones de investigación en programación funcional paralela". Springer-Verlag, Londres, Reino Unido, 1999.
  2. ^ Vanneschi, M. (2002). "El modelo de programación de ASSIST, un entorno para aplicaciones portátiles paralelas y distribuidas". Computación paralela . 28 (12): 1709–1732. CiteSeerX  10.1.1.59.5543 . doi :10.1016/S0167-8191(02)00188-6.
  3. ^ M. Aldinucci, M. Coppola, M. Danelutto, N. Tonellotto, M. Vanneschi y C. Zoccolo. "Programación de cuadrícula de alto nivel con ASSIST". Métodos computacionales en ciencia y tecnología, 12(1):21–32, 2006.
  4. ^ M. Aldinucci y M. Torquati. Aceleración de granjas de Apache mediante un repositorio de objetos escalable distribuido ad hoc. En Proc. of 10th Intl. Euro-Par 2004 Parallel Processing, volumen 3149 de LNCS, páginas 596–605. Springer, 2004.
  5. ^ Aldinucci, M.; Danelutto, M.; Antoniu, G.; Jan, M. (2008). "Intercambio de datos tolerante a fallos para redes de alto nivel: una arquitectura de almacenamiento jerárquica". Logros en la investigación europea sobre sistemas de redes . p. 67. doi :10.1007/978-0-387-72812-4_6. ISBN 978-0-387-72811-7.
  6. ^ 'S. MacDonald, J. Anvik, S. Bromling, J. Schaeffer, D. Szafron y K. Tan.' "De patrones a marcos de trabajo y programas paralelos". Parallel Comput., 28(12):1663–1683, 2002.
  7. ^ K. Tan, D. Szafron, J. Schaeffer, J. Anvik y S. MacDonald. "Uso de patrones de diseño generativos para generar código paralelo para un entorno de memoria distribuida". En PPoPP '03: Actas del noveno simposio ACM SIGPLAN sobre Principios y práctica de la programación paralela, páginas 203-215, Nueva York, NY, EE. UU., 2003. ACM.
  8. ^ D. Caromel y M. Leyton. "Ajuste fino de esqueletos algorítmicos". En 13th International Euro-Par Conference: Parallel Processing, volumen 4641 de Lecture Notes in Computer Science, páginas 72-81. Springer-Verlag, 2007.
  9. ^ D. Caromel, L. Henrio y M. Leyton. "Esqueletos algorítmicos de tipo seguro". En Actas de la 16.ª Conferencia Euromicro sobre procesamiento paralelo, distribuido y basado en red, páginas 45-53, Toulouse, Francia, febrero de 2008. IEEE CS Press.
  10. ^ D. Caromel y M. Leyton. "Un modelo de datos de archivo transparente y no invasivo para esqueletos algorítmicos". En el 22.º Simposio Internacional de Procesamiento Paralelo y Distribuido (IPDPS), páginas 1–8, Miami, EE. UU., marzo de 2008. IEEE Computer Society.
  11. ^ Mario Leyton, Jose M. Piquer. "Skandium: Programación multinúcleo con esqueletos algorítmicos", IEEE Euro-micro PDP 2010.
  12. ^ Rita Loogen y Yolanda Ortega-Mallén y Ricardo Peña-Marí. "Programación funcional paralela en Eden", Journal of Functional Programming, No. 15 (2005), 3, páginas 431–475
  13. ^ Murray Cole. "Sacar los esqueletos del armario: un manifiesto pragmático para la programación paralela esquelética". Parallel Computing, 30(3):389–406, 2004.
  14. ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. "Programación esquelética flexible con eskel". En JC Cunha y PD Medeiros, editores, Euro-Par, volumen 3648 de Lecture Notes in Computer Science, páginas 761–770. Springer, 2005.
  15. ^ A. Benoit y M. Cole. "Dos conceptos fundamentales en la programación paralela esqueletal". En V. Sunderam, D. van Albada, P. Sloot y J. Dongarra, editores, Conferencia Internacional sobre Ciencias Computacionales (ICCS 2005), Parte II, LNCS 3515, páginas 764–771. Springer Verlag, 2005.
  16. ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. Evaluación del rendimiento de programas paralelos de alto nivel basados ​​en esqueletos. En M. Bubak, D. van Albada, P. Sloot y J. Dongarra, editores, The International Conference on Computational Science (ICCS 2004), Parte III, LNCS 3038, páginas 289–296. Springer Verlag, 2004.
  17. ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. "Evaluación del rendimiento de programas paralelos estructurados en pipeline con esqueletos y álgebra de procesos". Scalable Computing: Practice and Experience, 6(4):1–16, diciembre de 2005.
  18. ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. "Programación de aplicaciones de red basadas en esqueletos utilizando pepa y nws". The Computer Journal, número especial sobre modelado y medición de la capacidad de ejecución de la red, 48(3):369–378, 2005.
  19. ^ A. Benoit y Y. Robert. "Mapeo de esqueletos de tuberías en plataformas heterogéneas". En ICCS 2007, la 7.ª Conferencia Internacional sobre Ciencias Computacionales, LNCS 4487, páginas 591–598. Springer Verlag, 2007.
  20. ^ G. Yaikhom, M. Cole, S. Gilmore y J. Hillston. "Un enfoque estructural para modelar el rendimiento de sistemas utilizando esqueletos". Electr. Notes Theor. Comput. Sci., 190(3):167–183, 2007.
  21. ^ H. Gonzalez-Velez y M. Cole . "Hacia un paralelismo de tuberías totalmente adaptativo para entornos distribuidos heterogéneos". En Procesamiento y aplicaciones paralelas y distribuidas, 4.º Simposio internacional (ISPA), Lecture Notes in Computer Science, páginas 916–926. Springer-Verlag, 2006.
  22. ^ H. Gonzalez-Velez y M. Cole. "Paralelismo estructurado adaptativo para redes computacionales". En PPoPP '07: Actas del 12º simposio ACM SIGPLAN sobre Principios y práctica de la programación paralela, páginas 140-141, Nueva York, NY, EE. UU., 2007. ACM.
  23. ^ Aldinucci, M.; Campa, S.; Danelutto, M.; Kilpatrick, P.; Torquati, M. (2013). "Apuntando a sistemas distribuidos en FastFlow" (PDF) . Euro-Par 2012: Talleres de procesamiento paralelo . Euro-Par 2012: Talleres de procesamiento paralelo. Apuntes de clase en informática. Vol. 7640. págs. 47–56. doi : 10.1007/978-3-642-36949-0_7 . ISBN 978-3-642-36948-3.
  24. ^ Aldinucci, M.; Spampinato, C.; Drocco, M.; Torquati, M.; Palazzo, S. (2012). "Un algoritmo de preservación de bordes paralelos para la eliminación de ruido de imágenes con efecto sal y pimienta". 2012 3.ª Conferencia internacional sobre teoría, herramientas y aplicaciones de procesamiento de imágenes (IPTA) . 3.ª Conferencia internacional sobre teoría, herramientas y aplicaciones de procesamiento de imágenes (IPTA). págs. 97–104. doi :10.1109/IPTA.2012.6469567. hdl : 2318/154520 .
  25. ^ Aldinucci, M.; Danelutto, M.; Kilpatrick, P.; Meneghin, M.; Torquati, M. (2012). "Una cola sin bloqueos ilimitada y eficiente para sistemas multinúcleo". Euro-Par 2012 Procesamiento paralelo . Euro-Par 2012 Procesamiento paralelo. Apuntes de clase en informática. Vol. 7484. págs. 662–673. doi : 10.1007/978-3-642-32820-6_65 . hdl : 2318/121343 . ISBN 978-3-642-32819-0.
  26. ^ Aldinucci, M.; Meneghin, M.; Torquati, M. (2010). "Efficient Smith-Waterman on Multi-core with Fast Flow ". 2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing . IEEE. pág. 195. CiteSeerX 10.1.1.163.9092 . doi :10.1109/PDP.2010.93. ISBN.  978-1-4244-5672-7.S2CID 1925361  .
  27. ^ CA Herrmann y C. Lengauer. "HDC: un lenguaje de orden superior para dividir y vencer". Parallel Processing Letters, 10(2–3):239–250, 2000.
  28. ^ CA Herrmann. La paralelización basada en esqueletos de las recursiones de divide y vencerás. Tesis doctoral, 2000. ISBN 3-89722-556-5 ". 
  29. ^ J. Dünnweber, S. Gorlatch. "Componentes de orden superior para programación en cuadrícula. Cómo hacer que las cuadrículas sean más utilizables". Springer-Verlag, 2009. ISBN 978-3-642-00840-5 
  30. ^ JF Ferreira, JL Sobral y AJ Proenca. "Jaskel: Un marco basado en esqueleto de Java para computación en clúster y en red estructurada". En CCGRID '06: Actas del Sexto Simposio Internacional IEEE sobre Computación en Clúster y Red, páginas 301–304, Washington, DC, EE. UU., 2006. IEEE Computer Society.
  31. ^ J. Sobral y A. Proenca. "Habilitación de esqueletos jaskel para clústeres y redes computacionales". En IEEE Cluster. IEEE Press, 9 de 2007.
  32. ^ M. Aldinucci y M. Danelutto. "Optimización de esqueletos de flujo paralelo". En Proc. of PDCS: Intl. Conference on Parallel and Distributed Computing and Systems, páginas 955–962, Cambridge, Massachusetts, EE. UU., noviembre de 1999. IASTED, ACTA press.
  33. ^ Aldinucci, M.; Danelutto, M.; Teti, P. (2003). "Un entorno avanzado que soporta la programación paralela estructurada en Java". Future Generation Computer Systems . 19 (5): 611. CiteSeerX 10.1.1.59.3748 . doi :10.1016/S0167-739X(02)00172-3. 
  34. ^ M. Danelutto y P. Teti. "Litio: un entorno de programación paralela estructurada en Java". En Proc. of ICCS: International Conference on Computational Science, volumen 2330 de LNCS, páginas 844–853. Springer Verlag, abril de 2002.
  35. ^ M. Aldinucci y M. Danelutto. "Una semántica operacional para esqueletos". En GR Joubert, WE Nagel, FJ Peters y WV Walter, editores, Parallel Computing: Software Technology, Algorithms, Architectures and Applications, PARCO 2003, volumen 13 de Advances in Parallel Computing, páginas 63–70, Dresde, Alemania, 2004. Elsevier.
  36. ^ Aldinucci, M.; Danelutto, M. (2007). "Programación paralela basada en esqueleto: Semántica funcional y paralela en una sola toma☆". Lenguajes, sistemas y estructuras informáticas . 33 (3–4): 179. CiteSeerX 10.1.1.164.368 . doi :10.1016/j.cl.2006.07.004. 
  37. ^ M. Aldinucci, M. Danelutto y J. Dünnweber. "Técnicas de optimización para implementar esqueletos paralelos en entornos de red". En S. Gorlatch, editor, Proc. of CMPP: Intl. Workshop on Constructive Methods for Parallel Programming, páginas 35–47, Stirling, Escocia, Reino Unido, julio de 2004. Universität Munster, Alemania.
  38. ^ M. Danelutto . Soporte eficiente para esqueletos en clústeres de estaciones de trabajo. Parallel Processing Letters, 11(1):41–56, 2001.
  39. ^ M. Danelutto. "Soporte de tiempo de ejecución dinámico para esqueletos". Informe técnico, 1999.
  40. ^ M. Danelutto. "Calidad de servicio en programación paralela mediante gestores de aplicaciones". En PDP '05: Actas de la 13.ª Conferencia Euromicro sobre procesamiento paralelo, distribuido y basado en red (PDP'05), páginas 282-289, Washington, DC, EE. UU., 2005. IEEE Computer Society.
  41. ^ M. Aldinucci y M. Danelutto. "El costo de la seguridad en sistemas esqueléticos". En P. D'Ambra y MR Guarracino, editores, Proc. of Intl. Euromicro PDP 2007: Procesamiento distribuido en paralelo y basado en red, páginas 213-220, Nápoles, Italia, febrero de 2007. IEEE.
  42. ^ M. Aldinucci y M. Danelutto. "Cómo asegurar sistemas esqueléticos con una pérdida de rendimiento limitada: la experiencia de Muskel". Journal of Systems Architecture, 2008.
  43. ^ M. Danelutto y P. Dazzi. "Un marco Java/Jini que admite cálculos paralelos de flujo". En Proc. de Internacional PARCO 2005: Computación paralela, septiembre de 2005.
  44. ^ M. Danelutto y P. Dazzi. "Explotación conjunta de paralelismo estructurado/no estructurado a través del flujo de datos". En V. Alexandrov, D. van Albada, P. Sloot y J. Dongarra, editores, Proc. of ICCS: International Conference on Computational Science, Workshop on Practical Aspects of High-level Parallel Programming, LNCS, Reading, Reino Unido, mayo de 2006. Springer Verlag.
  45. ^ M. Aldinucci, M. Danelutto y P. Dazzi. "Muskel: un entorno de esqueleto expandible". Scalable Computing: Practice and Experience, 8(4):325–341, diciembre de 2007.
  46. ^ E. Alba, F. Almeida, MJ Blesa, J. Cabeza, C. Cotta, M. Díaz, I. Dorta, J. Gabarro, C. León, J. Luna, LM Moreno, C. Pablos, J. Petit , A. Rojas y F. Xhafa. "Mallba: una biblioteca de esqueletos para optimización combinatoria (nota de investigación)". En Euro-Par '02: Actas de la octava conferencia internacional Euro-Par sobre procesamiento paralelo, páginas 927–932, Londres, Reino Unido, 2002. Springer-Verlag.
  47. ^ E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Díaz, I. Dorta, J. Gabarro, C. León, G. Luque, J. Petit, C. Rodríguez, A. Rojas y F. Xhafa. Algoritmos eficientes de lan/wan paralelos para la optimización: el proyecto mallba. Computación paralela, 32(5):415–440, 2006.
  48. ^ E. Alba, G. Luque, J. García-Nieto, G. Ordóñez y G. Leguizamón. "Mallba: una biblioteca de software para diseñar algoritmos de optimización eficientes". Revista Internacional de Informática y Aplicaciones Innovadoras, 1(1):74–85, 2007.
  49. ^ "Ricardo Marques, Hervé Paulino, Fernando Alexandre, Pedro D. Medeiros". "Marco de trabajo algorítmico para la orquestación de cálculos en GPU". Euro-Par 2013: 874–885
  50. ^ "Fernando Alexandre, Ricardo Marques, Hervé Paulino". "Sobre el soporte de esqueletos algorítmicos de tareas paralelas para computación multi-GPU". ACM SAC 2014: 880–885
  51. ^ H. Kuchen y J. Striegnitz. "Características de la programación funcional para una biblioteca de esqueleto de C++". Concurrency – Practice and Experience, 17(7–8):739–756, 2005.
  52. ^ Philipp Ciechanowicz, Michael Poldner y Herbert Kuchen. "El muesli de la biblioteca de esqueletos de Münster: una descripción completa". Documento de trabajo ERCIS n.° 7, 2009
  53. ^ H. Kuchen y M. Cole . "La integración de esqueletos paralelos de tareas y datos". Parallel Processing Letters, 12(2):141–155, 2002.
  54. ^ A. Alexandrescu. "Diseño moderno en C++: programación genérica y patrones de diseño aplicados". Addison-Wesley, 2001.
  55. ^ Michael Poldner. "Esqueletos algorítmicos de tareas paralelas". Tesis doctoral, Universidad de Münster, 2008.
  56. ^ Michael Poldner y Herbert Kuchen. "Esqueletos algorítmicos para ramificaciones y acotación". Actas de la 1.ª Conferencia internacional sobre software y tecnología de datos (ICSOFT), 1:291–300, 2006.
  57. ^ Michael Poldner y Herbert Kuchen. "Optimización del procesamiento de flujo esqueletal para dividir y vencer". Actas de la 3.ª Conferencia internacional sobre tecnologías de software y datos (ICSOFT), 181–189, 2008.
  58. ^ Michael Poldner y Herbert Kuchen. "Esqueletos para dividir y vencer". Actas de la Conferencia internacional IASTED sobre computación paralela y distribuida y redes (PDCN), 181–188, 2008.
  59. ^ Michael Poldner y Herbert Kuchen. "Granjas escalables". Actas de la Conferencia internacional sobre procesamiento paralelo (ParCo) 33:795–802, 2006.
  60. ^ Michael Poldner y Herbert Kuchen. "Sobre la implementación del esqueleto agrícola". Parallel Processing Letters, 18(1):117–131, 2008.
  61. ^ Philipp Ciechanowicz. "Esqueletos algorítmicos para matrices dispersas generales". Actas de la 20.ª Conferencia internacional IASTED sobre computación paralela y distribuida y sistemas (PDCS), 188-197, 2008.
  62. ^ Philipp Ciechanowicz, Philipp Kegel, Maraike Schellmann, Sergei Gorlatch y Herbert Kuchen. "Paralelización de la reconstrucción de imágenes OSEM de LM en clústeres multinúcleo". Computación paralela: de núcleos múltiples y GPU a petaescala, 19: 169-176, 2010.
  63. ^ Philipp Ciechanowicz y Herbert Kuchen. "Mejora de los esqueletos paralelos de datos de Muesli para arquitecturas informáticas multinúcleo". Conferencia internacional sobre informática y comunicaciones de alto rendimiento (HPCC), 108–113, 2010.
  64. ^ Bacci, B.; Danelutto, M.; Orlando, S.; Pelagatti, S.; Vanneschi, M. (1995). "P3L: Un lenguaje paralelo estructurado de alto nivel y su soporte estructurado". Concurrencia: práctica y experiencia . 7 (3): 225. CiteSeerX 10.1.1.215.6425 . doi :10.1002/cpe.4330070305. 
  65. ^ S. Ciarpaglini, M. Danelutto, L. Folchi, C. Manconi y S. Pelagatti. "ANACLETO: un compilador p3l basado en plantillas". En Actas del Séptimo Taller de Computación Paralela (PCW '97), Universidad Nacional Australiana, Canberra, agosto de 1997.
  66. ^ M. Aldinucci, M. Coppola y M. Danelutto. Reescritura de programas esqueleto: cómo evaluar la disyuntiva entre datos y flujo paralelo. En S. Gorlatch, editor, Proc of CMPP: Intl. Workshop on Constructive Methods for Parallel Programming, páginas 44–58. Uni. Passau, Alemania, mayo de 1998.
  67. ^ B. Bacci, M. Danelutto, S. Pelagatti y M. Vanneschi. "Skie: un entorno heterogéneo para aplicaciones HPC". Parallel Comput., 25(13–14):1827–1852, 1999.
  68. ^ M. Danelutto y M. Stigliani. "Skelib: Programación paralela con esqueletos en C". En Euro-Par '00: Actas de la 6.ª Conferencia Internacional Euro-Par sobre Procesamiento Paralelo, páginas 1175-1184, Londres, Reino Unido, 2000. Springer-Verlag.
  69. ^ D. Goswami, A. Singh y BR Preiss. "De los patrones de diseño a los esqueletos arquitectónicos paralelos". J. Parallel Distrib. Comput., 62(4):669–695, 2002. doi:10.1006/jpdc.2001.1809
  70. ^ D. Goswami, A. Singh y BR Preiss. "Uso de técnicas orientadas a objetos para la realización de esqueletos arquitectónicos paralelos". En ISCOPE '99: Actas del Tercer Simposio Internacional sobre Computación en Entornos Paralelos Orientados a Objetos, Lecture Notes in Computer Science, páginas 130-141, Londres, Reino Unido, 1999. Springer-Verlag.
  71. ^ MM Akon, D. Goswami y HF Li. "Superpas: Un modelo de esqueleto arquitectónico paralelo que admite la extensibilidad y la composición del esqueleto". En el Segundo Simposio Internacional de Procesamiento y Aplicaciones Distribuidas y Paralelas, ISPA, Notas de clase en Ciencias de la Computación, páginas 985-996. Springer-Verlag, 2004.
  72. ^ MM Akon, A. Singh, D. Goswami y HF Li. "Extensible parallel architectural skeletons" (Esqueletos arquitectónicos paralelos extensibles). En High Performance Computing HiPC 2005, 12th International Conference, volumen 3769 de Lecture Notes in Computer Science, páginas 290–301, Goa, India, diciembre de 2005. Springer-Verlag.
  73. ^ M. Diaz, B. Rubio, E. Soler y JM Troya. "SBASCO: componentes científicos basados ​​en esqueletos". En PDP, páginas 318–. IEEE Computer Society, 2004.
  74. ^ M. Diaz, S. Romero, B. Rubio, E. Soler y JM Troya. "Uso de SBASCO para resolver ecuaciones de reacción-difusión en dominios irregulares bidimensionales". En Practical Aspects of High-Level Parallel Programming (PAPP), afiliado a la International Conference on Computational Science (ICCS), volumen 3992 de Lecture Notes in Computer Science, páginas 912–919. Springer, 2006.
  75. ^ M. Diaz, S. Romero, B. Rubio, E. Soler y JM Troya. "Un marco orientado a aspectos para el desarrollo de componentes científicos". En PDP '05: Actas de la 13.ª Conferencia Euromicro sobre procesamiento paralelo, distribuido y basado en red, páginas 290-296, Washington, DC, EE. UU., 2005. IEEE Computer Society.
  76. ^ M. Diaz, S. Romero, B. Rubio, E. Soler y JM Troya. "Reconfiguración dinámica de componentes científicos mediante programación orientada a aspectos: un estudio de caso". En R. Meersman y Z. Tari, editores, On the Move to Meaningful Internet Systems 2006: CoopIS, DOA, GADA y ODBASE, volumen 4276 de Lecture Notes in Computer Science, páginas 1351–1360. Springer-Verlag, 2006.
  77. ^ J. Darlington, Y. ke Guo, HW To y J. Yang. "Esqueletos paralelos para composición estructurada". En PPOPP '95: Actas del quinto simposio ACM SIGPLAN sobre Principios y práctica de programación paralela, páginas 19-28, Nueva York, NY, EE. UU., 1995. ACM.
  78. ^ John Darlinton; Moustafa Ghanem; Yike Guo; Hing Wing To (1996), "Organización guiada de recursos en computación paralela heterogénea", Journal of High Performance Computing , 4 (1): 13–23, CiteSeerX 10.1.1.37.4309 
  79. ^ "Escudo".
  80. ^ J. Serot, D. Ginhac y J. Derutin. "SKiPPER: un entorno de programación paralela basado en esqueleto para aplicaciones de procesamiento de imágenes en tiempo real". En V. Malyshkin, editor, 5th International Conference on Parallel Computing Technologies (PaCT-99), volumen 1662 de LNCS, páginas 296-305. Springer, 6-10 de septiembre de 1999.
  81. ^ J. Serot y D. Ginhac. "Esqueletos para el procesamiento paralelo de imágenes: una descripción general del proyecto SKiPPER". Computación paralela, 28(12):1785–1808, diciembre de 2002.
  82. ^ J. Falcou, J. Serot, T. Chateau y JT Lapreste. "Quaff: diseño eficiente en C++ para esqueletos paralelos". Parallel Computing, 32(7):604–615, 2006.
  83. ^ J. Falcou y J. Serot. "Semántica formal aplicada a la implementación de una biblioteca de programación paralela basada en esqueleto". En GR Joubert, C. Bischof, FJ Peters, T. Lippert, M. Bcker, P. Gibbon y B. Mohr, editores, Parallel Computing: Architectures, Algorithms and Applications (Proc. of PARCO 2007, Julich, Alemania), volumen 38 de NIC, páginas 243–252, Alemania, septiembre de 2007. John von Neumann Institute for Computing.
  84. ^ K. Matsuzaki, H. Iwasaki, K. Emoto y Z. Hu. "Una biblioteca de esqueletos constructivos para el estilo secuencial de programación paralela". En InfoScale '06: Actas de la 1.ª conferencia internacional sobre sistemas de información escalables, página 13, Nueva York, NY, EE. UU., 2006. ACM.
  85. ^ K. Matsuzaki, Z. Hu y M. Takeichi. "Paralelización con esqueletos de árboles". En Euro-Par, volumen 2790 de Lecture Notes in Computer Science, páginas 789–798. Springer, 2003.
  86. ^ K. Matsuzaki, Z. Hu y M. Takeichi. "Esqueletos paralelos para manipular árboles generales". Parallel Computation, 32(7):590–603, 2006.
  87. ^ K. Emoto, Z. Hu, K. Kakehi y M. Takeichi. "Un marco compositivo para desarrollar programas paralelos en matrices bidimensionales". Informe técnico, Departamento de Informática Matemática, Universidad de Tokio, 2005.
  88. ^ K. Emoto, K. Matsuzaki, Z. Hu y M. Takeichi. "Estrategia de optimización específica de dominio para programas esqueleto". En Euro-Par, volumen 4641 de Lecture Notes in Computer Science, páginas 705–714. Springer, 2007.
  89. ^ K. Matsuzaki, K. Kakehi, H. Iwasaki, Z. Hu e Y. Akashi. "Una biblioteca de esqueletos integrada en fusión". En M. Danelutto, M. Vanneschi y D. Laforenza, editores, Euro-Par, volumen 3149 de Lecture Notes in Computer Science, páginas 644–653. Springer, 2004.
  90. ^ GH Botorog y H. Kuchen. "Programación paralela eficiente de alto nivel". Theor. Comput. Sci., 196(1–2):71–107, 1998.
  91. ^ Zandifar, Mani; Abduljabbar, Mustafa; Majidi, Alireza; Keyes, David; Amato, Nancy; Rauchwerger, Lawrence (2015). "Composición de esqueletos algorítmicos para expresar aplicaciones científicas de alto rendimiento". Actas de la 29.ª Conferencia Internacional sobre Supercomputación de la ACM . págs. 415–424. doi :10.1145/2751205.2751241. ISBN . 9781450335591. Número de identificación del sujeto  13764901.
  92. ^ Zandifar, Mani; Thomas, Nathan; Amato, Nancy M.; Rauchwerger, Lawrence (15 de septiembre de 2014). Brodman, James; Tu, Peng (eds.). Lenguajes y compiladores para computación paralela . Notas de clase en informática. Springer International Publishing. págs. 176–190. doi :10.1007/978-3-319-17473-0_12. ISBN . 9783319174723.
  93. ^ "G. Tanase, et.al." "STAPL Parallel Container Framework" Actas PPoPP '11 Actas del 16.º simposio de la ACM sobre principios y práctica de la programación paralela Páginas 235–246
  94. ^ J. Darlington, AJ Field, PG Harrison, PHJ Kelly, DWN Sharp y Q. Wu. "Programación paralela utilizando funciones de esqueleto". En PARLE '93: Actas de la 5.ª Conferencia Internacional PARLE sobre Arquitecturas y Lenguajes Paralelos en Europa, páginas 146-160, Londres, Reino Unido, 1993. Springer-Verlag.
  95. ^ J. Darlinton; M. Ghanem; HW To (1993), "Programación paralela estructurada", en Modelos de programación para computadoras masivamente paralelas. IEEE Computer Society Press. 1993 : 160–169, CiteSeerX 10.1.1.37.4610