En informática , los esqueletos algorítmicos o patrones de paralelismo son un modelo de programación paralela de alto nivel para la informática paralela y distribuida.
Los esqueletos algorítmicos aprovechan los patrones de programación comunes para ocultar la complejidad de las aplicaciones paralelas y distribuidas. Partiendo 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á implícitamente definida por los patrones del esqueleto. Los programadores no tienen que especificar las sincronizaciones entre las partes secuenciales de la aplicación. Esto tiene dos implicaciones. Primero, como los patrones de comunicación / acceso a datos se conocen de antemano, los modelos de costos se pueden aplicar para programar programas de esqueletos. [1] En segundo lugar, la programación de esqueleto algorítmico reduce el número de errores en comparación con los modelos tradicionales de programación paralela de bajo nivel (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 esqueleto algorítmico del algoritmo QuickSort utilizando el patrón Divide and Conquer. Observe que el enfoque de alto nivel oculta la administración de subprocesos al programador.
// 1. Defina el programa esqueleto Skeleton < Range , Range > sort = new DaC < Range , Range > ( new ShouldSplit ( umbral , maxTimes ), new SplitList (), new Sort (), new MergeList ());// 2. Parámetros de entrada Future < Range > future = sort . input ( new Range ( generate (...)));// 3. Haz algo más aquí. // ...// 4. Bloque para los resultados Rango resultado = futuro . obtener ();
- Lo primero es definir una nueva instancia del esqueleto con el código funcional que llena el patrón (ShouldSplit, SplitList, Sort, MergeList). El programador escribe el código funcional sin preocupaciones de paralelismo.
- El segundo paso es la entrada de datos que desencadena 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 introducido en el marco, se crea un nuevo objeto Future. Se puede ingresar más de un Futuro en un esqueleto simultáneamente.
- El futuro permite el cálculo asincrónico, ya que se pueden realizar otras tareas mientras se calculan los resultados.
- Podemos recuperar el resultado del cálculo, bloqueando si es necesario (es decir, resultados aún no disponibles).
Los códigos funcionales de este ejemplo corresponden a cuatro tipos de Condición, Dividir, Ejecutar y Combinar.
La clase pública ShouldSplit implementa Condición < Rango > { int umbral , maxTimes , veces ; public ShouldSplit ( int umbral , int maxTimes ) { esto . umbral = umbral ; esto . maxTimes = maxTimes ; esto . veces = 0 ; } @ Anular la condición booleana sincronizada pública ( rango r ) { return r . derecha - r . izquierda > umbral && tiempos ++ < esto . 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, esto decidirá si una submatriz debe subdividirse nuevamente o no.
La clase SplitList implementa la interfaz dividida, 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 cambio y pivote 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 ); Rango [] intervalos = { nuevo rango ( r . Matriz , r . Izquierda , i - 1 ), nuevo rango ( r . Matriz , i + 1 , r . Derecha )}; intervalos de retorno ; } }
La clase Sort implementa la 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.
Clasificar implementos de clase pública Ejecutar < Rango , Rango > { @Override public Range ejecutar ( Range r ) { si ( r . derecha <= r . izquierda ) return r ; Matrices . ordenar ( r . matriz , r . izquierda , r . derecha + 1 ); return r ; } }
Finalmente, una vez que se ordena un conjunto de subarreglos, fusionamos las partes del subarreglo en un arreglo más grande con la clase MergeList que implementa una interfaz Merge.
público de clase MergeList implementos Combinar < Rango , Rango > { @ Anular fusión de rango público ( Rango [] r ) { Resultado de rango = nuevo Rango ( r [ 0 ] . Matriz , r [ 0 ] . Izquierda , r [ 1 ] . Derecha ); devolver resultado ; } }
Marcos y bibliotecas
AYUDAR
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 del módulo describe cómo un conjunto de módulos interactúa entre sí mediante un conjunto de flujos de datos escritos. 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 ASSIST especial ( parmod ).
AdHoc, [4] [5] un sistema de memoria compartida distribuida (DSM) jerárquico y tolerante a fallas se utiliza para interconectar flujos de datos entre elementos de procesamiento proporcionando un repositorio con operaciones: obtener / poner / eliminar / ejecutar. 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 esqueleto clásico, en el sentido de que no se proporcionan esqueletos, el parmod genérico de ASSIST puede especializarse en esqueletos clásicos como: granja , mapa , etc. ASSIST también admite el control autónomo de parmods y puede estar sujeto a un contrato de desempeño adaptando dinámicamente el número de recursos utilizados.
CO2P3S
CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System), es un entorno de desarrollo orientado a patrones, [6] que logra el paralelismo utilizando subprocesos en Java.
CO2P3S se ocupa del proceso de desarrollo completo de una aplicación paralela. Los programadores interactúan a través de una GUI de programación para elegir un patrón y sus opciones de configuración. Luego, los programadores llenan los ganchos necesarios para el patrón y se genera 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 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 de tipos, utilizando los tipos proporcionados por el programador que no requieren extensión de superclase, pero no es completamente seguro de 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étodo, distribuidor, malla y frente de onda. Se pueden construir aplicaciones complejas componiendo marcos con sus referencias a objetos. Sin embargo, si ningún patrón es adecuado, la herramienta gráfica MetaCO2P3S aborda la extensibilidad permitiendo a los programadores modificar los diseños de patrones e introducir 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 del uso, la versión de memoria distribuida del código requiere la gestión de excepciones remotas.
Calcio y Skandio
El calcio se inspira en gran medida en el litio y el muskel. Como tal, proporciona programación de esqueleto algorítmico como una biblioteca de Java. Tanto los esqueletos paralelos de tareas como de datos son completamente encajables; y se crean instancias a través de objetos esqueléticos paramétricos, no por herencia.
Calcium admite la ejecución de aplicaciones esqueléticas sobre el entorno ProActive para una infraestructura distribuida similar a un clúster. Además, el calcio tiene tres características distintivas para la programación del esqueleto algorítmico. Primero, un modelo de ajuste de 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 encajables que se ha demostrado que garantiza las propiedades de reducción de sujetos y se implementa utilizando Java Generics. [9] En tercer lugar, un modelo de acceso a archivos de esqueleto algorítmico transparente, que habilita esqueletos para aplicaciones intensivas en datos. [10]
Skandium es una reimplementación completa de Calcium para computación de múltiples núcleos. Los programas escritos en Skandium pueden aprovechar la memoria compartida para simplificar la programación en paralelo. [11]
Edén
Eden [12] es un lenguaje de programación paralelo para entornos de memoria distribuida, que amplía Haskell. Los procesos se definen explícitamente para lograr la programación en paralelo, mientras que sus comunicaciones permanecen implícitas. Los procesos se comunican a través de canales unidireccionales, que conectan 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 esquelético 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 respalda el paralelismo de tareas y datos . Entonces, contrariamente a la mayoría de los otros enfoques, Eden permite que los esqueletos se definan en el mismo idioma y al mismo nivel, se escribe la instanciación del esqueleto: el propio Eden. 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 de esqueletos de Edimburgo ( 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 anidamiento y el modo de interacción para esqueletos. El modo de anidamiento puede ser transitorio o persistente, mientras que el modo de interacción puede ser implícito o explícito. La anidación transitoria significa que se crea una instancia del esqueleto anidado para cada invocación y se destruye posteriormente, mientras que persistente significa que se crea una instancia del esqueleto una vez y se invoca 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ícito 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 una interacción explícita.
La predicción del rendimiento para la programación y el mapeo de recursos, principalmente para tuberías, ha sido explorada por Benoit et al. [16] [17] [18] [19] Proporcionaron un modelo de desempeño para cada mapeo, basado en el álgebra de procesos, y determinaron la mejor estrategia de programación basada en 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 la tubería. [21] [22]
Flujo rápido
FastFlow es un marco de programación esquelético paralelo específicamente dirigido al desarrollo de aplicaciones de transmisión y de datos en paralelo. Inicialmente desarrollado para apuntar a plataformas multinúcleo , se ha extendido sucesivamente para apuntar a plataformas heterogéneas compuestas por grupos de plataformas de memoria compartida, [23] [24] posiblemente equipadas con aceleradores informáticos como NVidia GPGPU, 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 paralelas 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, que incluyen, entre otros: paralelismo de grano fino en plataformas de memoria compartida coherentes con caché; aplicaciones de transmisión; uso combinado de multinúcleo y aceleradores. En otros casos, FastFlow es típicamente comparable (y en algunos casos es ligeramente más rápido que) marcos de programación paralelos de última generación como Intel TBB, OpenMP, Cilk, etc. [26]
HDC
Divide y vencerás de orden superior ( HDC ) [27] es un subconjunto del lenguaje funcional Haskell . Los programas funcionales se presentan como funciones polimórficas de orden superior, que pueden compilarse en C / MPI y vincularse con implementaciones de esqueleto. El lenguaje se centra en el paradigma de divide y vencerás, y partiendo 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 recursividad constante, recursividad de bloques múltiples, operaciones por elementos 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 se esfuerza por estimar una asignación adecuada de procesadores para cada parte del programa. Por lo tanto, el rendimiento de la aplicación está estrechamente relacionado con el número estimado de procesadores, lo que genera un número excesivo de subproblemas o un paralelismo insuficiente para explotar los procesadores disponibles.
HOC-SA
HOC-SA es un proyecto de incubadora Globus .
HOC-SA significa Arquitectura de servicio de componentes de orden superior. Los componentes de orden superior ( HOC ) tienen el objetivo de 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 proporcionan una interfaz de nivel superior para Grid que el conjunto de herramientas principal de Globus.
Los HOC son esqueletos habilitados para Grid, implementados como componentes en la parte superior de Globus Toolkit, de forma remota a través de servicios web. [29]
JaSkel
JaSkel [30] es un marco esqueleto basado en Java que proporciona esqueletos como farm, pipe y heartbeat. Los esqueletos se especializan mediante la herencia. Los programadores implementan los métodos abstractos para cada esqueleto para proporcionar el código específico de su aplicación. Los esqueletos en JaSkel se proporcionan en versiones secuenciales, concurrentes y dinámicas. Por ejemplo, la granja simultánea se puede usar en entornos de memoria compartida (subprocesos), pero no en entornos distribuidos (clústeres) donde se debe usar 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. El anidamiento de esqueletos utiliza la clase de objeto Java 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álculo se manejan en JaSkel usando AOP, más específicamente la implementación de AspectJ. Por lo tanto, JaSkel se puede implementar tanto en clústeres como en infraestructuras similares a Grid. [31] Sin embargo, un inconveniente del enfoque de JaSkel es que el anidamiento del esqueleto se relaciona estrictamente con la infraestructura de implementación. Por lo tanto, un doble anidamiento de la granja 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 Muskel
Lithium [32] [33] [34] y su sucesor Muskel son esqueletos desarrollados en la Universidad de Pisa, Italia. Ambos proporcionan esqueletos anidables al programador como bibliotecas Java. La evaluación de una aplicación esqueleto sigue una definición formal de semántica operativa introducida por Aldinucci y Danelutto, [35] [36] que puede manejar tanto el paralelismo de tareas como de datos. La semántica describe el comportamiento tanto funcional como paralelo del lenguaje esquelético utilizando un sistema de transición etiquetado. Además, se aplican varias optimizaciones del rendimiento, tales como: técnicas de reescritura de esqueleto [18, 10], búsqueda anticipada de tareas y enlace diferido de servidor a servidor. [37]
A nivel de implementación, Lithium aprovecha el flujo de macrodatos [38] [39] para lograr el paralelismo. Cuando el flujo de entrada recibe un nuevo parámetro, el programa esquelético 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 varios MDFi y son consumidas por elementos de procesamiento inactivos de un grupo de tareas. Cuando se concluye 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 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 fallas cuando se interactúa con Java / Jini Parallel Framework (JJPF), [43] un marco de ejecución distribuido. Muskel también proporciona soporte para combinar programación estructurada con no estructurada [44] y una investigación reciente ha abordado la extensibilidad. [45]
Mallba
Mallba [46] es una biblioteca para optimizaciones combinatorias que soportan estrategias de búsqueda exactas, heurísticas e híbridas. [47] Cada estrategia se implementa en Mallba como un esqueleto genérico que puede usarse proporcionando el código requerido. En los algoritmos de búsqueda exactos, Mallba proporciona esqueletos de optimización dinámica y ramificados. Para la heurística de búsqueda local, Mallba admite: escalada , metrópolis, recocido simulado y búsqueda tabú ; y también heurísticas basadas en poblaciones derivadas de algoritmos evolutivos como algoritmos genéticos , estrategia de evolución y otros (CHC). Los esqueletos híbridos combinan estrategias, tales 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 de C ++ y no se pueden anidar, pero son seguros para los tipos. Se utiliza una capa de abstracción MPI personalizada, NetStream, que se encarga de la clasificación, sincronización, etc. de tipos de datos primitivos. 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 puede usarse para almacenar la mejor solución encontrada hasta ahora, o valores α, β para la poda de ramas y límites. [48]
En comparación con otros marcos, el uso que hace Mallba 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 una estructura de esqueleto algorítmico de C ++ para la orquestación de cálculos OpenCL en entornos de múltiples GPU , posiblemente heterogéneos . Proporciona un conjunto de esqueletos paralelos de datos y tareas que se pueden componer, mediante anidamiento, para construir cálculos compuestos. Los nodos hoja de los árboles de composición resultantes representan los núcleos computacionales de la GPU, mientras que los nodos restantes denotan el esqueleto aplicado al subárbol anidado. El marco asume toda la orquestación del lado del host requerida para ejecutar correctamente estos árboles en entornos heterogéneos de múltiples GPU, incluida la ordenación adecuada 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 distinguibles 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 anidación de esqueletos, una característica también nueva en este contexto. Además, el marco introduce optimizaciones que se superponen a 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 varias GPU sigue una estrategia de descomposición paralela de datos, 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 kernel se pueden descomponer y, cuando sea necesario, definir cómo se deben fusionar los resultados parciales, el programador se abstrae completamente de la arquitectura subyacente de múltiples GPU.
Puede encontrar más información, así como el código fuente, en el sitio web de Marrow.
Muesli
La biblioteca de esqueletos de Muenster Muesli [51] [52] es una biblioteca de plantillas de C ++ que vuelve a implementar muchas de las ideas y conceptos introducidos en Skil , por ejemplo, funciones de orden superior, curry y tipos polimórficos [1] . Está construido sobre MPI 1.2 y OpenMP 2.5 y admite, a diferencia de muchas otras bibliotecas de esqueletos, esqueletos paralelos de datos y tareas. El anidamiento de esqueletos (composición) es similar al enfoque de dos niveles de P3L , es decir, los esqueletos paralelos de tareas pueden anidarse arbitrariamente mientras que los esqueletos paralelos de datos no pueden, pero pueden usarse en las hojas de un árbol de anidación paralela de tareas. [53] Las plantillas de C ++ se utilizan para representar esqueletos 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 plegar (reducir), mapear, permutar, comprimir 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 matrices, matrices y matrices dispersas. [61]
Como característica única, los esqueletos paralelos de datos de Muesli escalan automáticamente tanto en arquitecturas de clúster de un solo núcleo como de múltiples núcleos y 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 se ejecuta en una computadora en 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 al proporcionar una capa de abstracción OpenMP muy delgada, de modo que el soporte de arquitecturas de múltiples núcleos se puede activar / desactivar simplemente proporcionando / omitiendo el indicador del compilador OpenMP al compilar el programa. Al hacerlo, prácticamente no se introducen gastos generales en tiempo de ejecución.
P3L, SkIE, SKElib
P3L [64] (Pisa Parallel Programming Language) es un lenguaje de coordinación basado en esqueleto. P3L proporciona construcciones 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 usa plantillas de implementación para compilar el código P3 L 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 las transformaciones del programa que pueden conducir a optimizaciones del rendimiento. [66]
Un módulo P3L corresponde a una estructura de estructura correctamente definida con flujos de entrada y salida, y otros submódulos o código C secuencial. Los módulos se pueden anidar usando el modelo de dos niveles, donde el nivel externo está compuesto por esqueletos paralelos de tareas, mientras que los esqueletos paralelos de datos pueden usarse en el nivel interno [64]. La verificación de tipo se realiza a nivel de flujo de datos, cuando el programador especifica explícitamente el tipo de flujos de entrada y salida, y especificando el flujo de datos entre submódulos.
SkIE [67] (entorno integrado basado en esqueleto) es bastante similar a P3L , ya que también se basa en un lenguaje de coordinación, pero proporciona funciones 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 heredando, entre otros, el sistema de plantillas. Se diferencia de ellos porque ya no se usa un lenguaje de coordinación, sino que los esqueletos se proporcionan como una biblioteca en C, con un rendimiento similar al logrado en P3L . A diferencia de Skil , otro marco esqueleto similar a C, la seguridad de tipos no se aborda en SKELib .
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 usan una extensión de C ++ para escribir sus aplicaciones básicas1. Luego, el código se pasa a través de un script 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 representante 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 los esqueletos padre y secundario.
Una extensión de PAS etiquetada como SuperPas [71] y más tarde como EPAS [72] aborda los problemas 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 usar 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 bloque múltiple.
SBASCO se ocupa de las aplicaciones descomponibles de dominio a través de su esqueleto de bloques múltiples. Los dominios se especifican a través de matrices (principalmente bidimensionales), que se descomponen en submatrices con posibles límites superpuestos. A continuación, el cálculo tiene lugar de forma iterativa similar a 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] Componentes científicos (SC) se presentan dos tipos de componentes que proporcionan el código funcional; y Componentes de aspectos de comunicación (CAC) que encapsulan el comportamiento no funcional, como la comunicación, el diseño del procesador de distribución 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 al reasignar dinámicamente los procesadores asignados a un SC. En [76] se muestra un caso de uso que muestra un rendimiento mejorado cuando se utilizan componentes CAC. [76]
SCL
El Lenguaje de Coordinación Estructurado ( SCL ) [77] fue uno de los primeros lenguajes de programación esqueleto. Proporciona un enfoque de lenguaje de coordinación para la programación esquelética sobre componentes de software. SCL se considera un lenguaje base y fue diseñado para integrarse con un lenguaje host, 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 . Esqueletos de configuración patrones abstractos para estructuras de datos de uso común, como matrices distribuidas (ParArray). Los esqueletos elementales corresponden a esqueletos paralelos de datos como mapa, escaneo y plegado. Esqueletos de computación que abstraen el flujo de control y 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 esqueleto para CPU multinúcleo y sistemas multi-GPU. Es una biblioteca de plantillas C ++ con seis esqueletos en paralelo de datos y uno en paralelo de tareas, dos tipos de contenedores y soporte para ejecución en sistemas multi-GPU tanto con CUDA como OpenCL. Recientemente, el soporte para la ejecución híbrida, la programación dinámica consciente del rendimiento y el equilibrio de carga se desarrolló en SkePU 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.
SKiPPER Y QUAFF
SKiPPER es una biblioteca de esqueletos de dominio específico 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 formas: declarativa y operativa. Los programadores utilizan directamente los esqueletos declarativos, mientras que sus versiones operativas proporcionan una implementación de destino específica de la arquitectura. Desde el 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.
Se han explorado diferentes enfoques en SKiPPER 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 de tokens etiquetados. [81]
QUAFF [82] es una biblioteca esqueleto más reciente escrita en C ++ y MPI. QUAFF se basa en técnicas de metaprogramación basadas en plantillas para reducir los gastos generales del tiempo de ejecución y realizar ampliaciones y optimizaciones del esqueleto en el momento de la 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 C ++ para generar, en el momento de la compilación, nuevo código C / MPI. QUAFF se basa en el modelo CSP, donde el programa esqueleto se describe como una red de proceso y reglas de producción (único, en serie, par, ensamblado). [83]
SkeTo
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 encajables, SkeTo proporciona esqueletos paralelos para estructuras de datos paralelas como: listas, árboles, [85] [86] y matrices. [87] Las estructuras de datos se escriben utilizando plantillas y se pueden invocar varias operaciones paralelas en ellas. Por ejemplo, la estructura de la lista proporciona operaciones paralelas como: mapear, reducir, escanear, comprimir, desplazar, etc.
La investigación adicional en torno a SkeTo también se ha centrado en las estrategias de optimización por transformación y, más recientemente, en optimizaciones específicas de dominio. [88] Por ejemplo, SkeTo proporciona una transformación de fusión [89] que fusiona dos invocaciones de función sucesivas en una sola, disminuyendo así la sobrecarga de llamadas de función y evitando la creación de estructuras de datos intermedias pasadas entre funciones.
Skil
Skil [90] es un lenguaje imperativo para la programación esquelética. Los esqueletos no forman parte directamente del lenguaje, sino que se implementan con él. Skil utiliza un subconjunto del lenguaje C que proporciona características similares al lenguaje funcional, como funciones de orden superior, tipos curring y polimórficos. Cuando se compila Skil , estas características se eliminan y se produce un código C normal. Por lo tanto, Skil transforma funciones polimórficas de alto orden en funciones C monomórficas de primer orden. Skil no admite la composición encajable 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.
Marco 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 correspondientes gráficos de flujo de datos a través de la noción de puertos, lo que permite agregar 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 anidación. 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 esquelética. [94] El sistema se basó en gran medida en las propiedades de programación funcional, y cinco esqueletos se definieron como funciones de orden superior: Divide-and-Conquer, Farm, Map, Pipe y RaMP. Un programa puede tener más de una implementación, cada una con una combinación de esqueletos diferentes. Además, cada esqueleto podría tener diferentes implementaciones paralelas. Se utilizó una metodología basada en transformaciones funcionales del programa guiadas por modelos de desempeño de los esqueletos para seleccionar el esqueleto más apropiado para ser utilizado para el programa, así como la implementación más adecuada del esqueleto. [95]
Comparación de marcos
- Los años de actividad son los años de actividad conocidos. Las fechas representadas en esta columna corresponden a la primera y última fecha de publicación de un artículo relacionado en una revista científica o acta de congreso. Tenga en cuenta que un proyecto puede seguir activo más allá del período de actividad y que no hemos podido encontrar una publicación para él más allá de la fecha indicada.
- El lenguaje de programación es la interfaz con la que los programadores interactúan para codificar sus aplicaciones básicas. Estos lenguajes son diversos, abarcando paradigmas como: lenguajes funcionales, lenguajes de coordinación, lenguajes de marcado, lenguajes imperativos, lenguajes orientados a objetos e incluso interfaces gráficas de usuario. Dentro del lenguaje de programación, se han proporcionado esqueletos como construcciones de lenguaje o bibliotecas. Proporcionar esqueletos como construcción de lenguaje implica el desarrollo de un lenguaje específico de dominio personalizado y su compilador. Esta fue claramente la tendencia más fuerte al comienzo de la investigación del esqueleto. La tendencia más reciente es proporcionar esqueletos como bibliotecas, en particular con lenguajes orientados a objetos como C ++ y Java.
- El lenguaje de ejecución es el lenguaje en el que se ejecutan o compilan las aplicaciones básicas. Se reconoció muy pronto que los lenguajes de programación (especialmente en los casos funcionales), no eran lo suficientemente eficientes para ejecutar los programas esqueléticos. Por lo tanto, los lenguajes de programación esqueleto se simplificaron al ejecutar la aplicación esqueleto en otros lenguajes. Se introdujeron procesos de transformación para convertir las aplicaciones esqueléticas (definidas en el lenguaje de programación) en una aplicación equivalente en el lenguaje de ejecución de destino. Se introdujeron diferentes procesos de transformación, como la generación de código o la instanciación de esqueletos de nivel inferior (a veces llamados esqueletos operativos) que eran capaces de interactuar con una biblioteca en el lenguaje de ejecución. La aplicación transformada también brindó la oportunidad de introducir código de arquitectura de destino, personalizado para el rendimiento, en la aplicación transformada. La Tabla 1 muestra que uno de los favoritos para el lenguaje de ejecución ha sido el lenguaje C.
- La biblioteca de distribución proporciona la funcionalidad para lograr cálculos en paralelo / distribuidos. El gran favorito en este sentido ha sido MPI, que no es de extrañar ya que se integra bien con el lenguaje C, y es probablemente la herramienta más utilizada para el paralelismo en la computación en clústeres. Los peligros de programar directamente con la biblioteca de distribución están, por supuesto, ocultos de forma segura lejos de los programadores que nunca interactúan con la biblioteca de distribución. Recientemente, la tendencia ha sido desarrollar marcos esqueléticos capaces de interactuar con más de una biblioteca de distribución. Por ejemplo, CO2 P3 S puede utilizar Threads, RMI o Sockets; Mallba puede utilizar Netstream o MPI; o JaSkel que usa AspectJ para ejecutar las aplicaciones de esqueleto en diferentes marcos de esqueleto.
- La seguridad de tipos se refiere a la capacidad de detectar errores de incompatibilidad de tipos en el programa esqueleto. Dado que los primeros frameworks de esqueleto se construyeron en lenguajes funcionales como Haskell, la seguridad de tipos simplemente se heredó del lenguaje anfitrión. Sin embargo, como se desarrollaron lenguajes personalizados para la programación esquelética, los compiladores tuvieron que escribirse para tener en cuenta la verificación de tipos; lo cual no fue tan difícil como el anidamiento de esqueletos no fue completamente compatible. Sin embargo, recientemente, cuando comenzamos a alojar esqueletos de frameworks en lenguajes orientados a objetos con anidamiento completo, el problema de seguridad de tipos ha resurgido. Desafortunadamente, la verificación de tipos se ha pasado por alto en su mayoría (con la excepción de QUAFF), y especialmente en los marcos de esqueleto basados en Java.
- El anidamiento de esqueletos es la capacidad de composición jerárquica de patrones de esqueletos. Skeleton Nesting se identificó como una característica importante en la programación de esqueletos desde el principio, porque permite la composición de patrones más complejos a partir de un conjunto básico de patrones más simples. Sin embargo, a la comunidad le ha llevado mucho tiempo apoyar por completo el anidamiento arbitrario de esqueletos, principalmente debido a las dificultades de programación y verificación de tipo. La tendencia es clara de que los marcos de esqueletos recientes admiten el anidamiento completo de esqueletos.
- El acceso a archivos es la capacidad de acceder y manipular archivos desde una aplicación. En el pasado, la programación esquelética ha demostrado ser útil principalmente para aplicaciones computacionales intensivas, donde pequeñas cantidades de datos requieren grandes cantidades de tiempo de cálculo. Sin embargo, muchas aplicaciones distribuidas requieren o producen grandes cantidades de datos durante su cálculo. Este es el caso de la astrofísica, la física de partículas, la bioinformática, etc. Por lo tanto, proporcionar soporte de transferencia de archivos que se integre con la programación básica es una preocupación clave que se ha pasado por alto en la mayoría de los casos.
- El conjunto de esqueleto es la lista de patrones de esqueleto admitidos. Los conjuntos de esqueletos varían mucho de un marco a otro y, lo que es más sorprendente, algunos esqueletos con el mismo nombre tienen semánticas diferentes en diferentes marcos. Los patrones de esqueleto más comunes en la literatura son probablemente farm, pipe y map.
Años de actividad | Lenguaje de programación | Lenguaje de ejecución | Biblioteca de distribución | Escriba seguro | Anidación de esqueletos | Acceso a archivos | Conjunto de esqueleto | |
---|---|---|---|---|---|---|---|---|
AYUDAR | 2004-2007 | Lenguaje de control personalizado | C ++ | TCP / IP + ssh / scp | sí | No | explícito | seq, parmod |
SBSACO | 2004-2006 | Lenguaje de composición personalizado | C ++ | MPI | sí | sí | No | agrícola, de tuberías, multibloques |
eSkel | 2004-2005 | C | C | MPI | No | ? | No | tubería, granja, trato, mariposa, santificar |
HDC | 2004-2005 | Subconjunto de Haskell | C | MPI | sí | ? | No | dcA, dcB, dcD, dcE, dcF, mapa, rojo, escaneo, filtro |
SKELib | 2000-2000 | C | C | MPI | No | No | No | granja, tubería |
Patrón | 1999-2002 | CAML | C | SynDex | sí | limitado | No | scm, df, tf, intermem |
SkIE | 1999-1999 | GUI / lenguaje de control personalizado | C ++ | MPI | sí | limitado | No | tubería, granja, mapa, reducir, bucle |
Edén | 1997-2011 | Extensión de Haskell | Haskell | PVM / MPI | sí | sí | No | mapa, granja, grupo de trabajo, nr, corriente continua, tubería, iterUntil, toro, anillo |
P3L | 1995–1998 | Lenguaje de control personalizado | C | MPI | sí | limitado | No | mapa, reducir, escanear, composición, tubería, granja, seq, bucle |
Skil | 1995–1998 | Subconjunto C | C | ? | sí | No | No | pardata, mapa, pliegue |
SCL | 1994-1999 | Lenguaje de control personalizado | Fortran / C | MPI | sí | limitado | No | mapa, escanear, plegar, granja, SPMD, iterar |
T4P | 1990-1994 | Esperanza + | Esperanza + | CSTools | sí | limitado | No | D&C (divide y vencerás), mapa, tubería, ramp |
Años de actividad | Lenguaje de programación | Lenguaje de ejecución | Biblioteca de distribución | Escriba seguro | Anidación de esqueletos | Acceso a archivos | Conjunto de esqueleto | |
---|---|---|---|---|---|---|---|---|
Skandium | 2009-2012 | Java | Java | Hilos | sí | sí | No | seq, pipe, farm, for, while, map, d & c, fork |
Flujo rápido | 2009– | C ++ | C ++ 11 / CUDA / OpenCL | Hilos C ++ 11 / Hilos Posix / TCP-IP / OFED-IB / CUDA / OpenCL | sí | sí | sí | Pipeline, Farm, ParallelFor, ParallelForReduce, MapReduce, StencilReduce, PoolEvolution, MacroDataFlow |
Calcio | 2006-2008 | Java | Java | Proactivo | sí | sí | sí | seq, pipe, farm, for, while, map, d & c, fork |
BEBER A GRANDES TRAGOS | 2006-2007 | C ++ | C | MPI | sí | sí | No | seq, tubería, granja, scm, pardo |
JaSkel | 2006-2007 | Java | Java / AspectJ | MPP / RMI | No | sí | No | granja, tubería, latido del corazón |
Muskel | 2005-2008 | Java | Java | RMI | No | sí | No | farm, pipe, seq, + gráficos MDF personalizados |
HOC-SA | 2004-2008 | Java | Java | Globus, KOALA | No | No | No | granja, oleoducto, frente de onda |
SkeTo | 2003-2013 | C ++ | C ++ | MPI | sí | No | No | lista, matriz, árbol |
Mallba | 2002-2007 | C ++ | C ++ | NetStream / MPI | sí | No | No | exacto, heurístico, híbrido |
Médula | 2013– | C ++ | C ++ más OpenCL | (ninguno) | No | sí | No | paralelo de datos: mapa, mapa-reducir. tarea paralela: tubería, bucle, para |
Muesli | 2002-2013 | C ++ | C ++ | MPI / OpenMP | sí | sí | No | datos en paralelo: plegar, mapear, permutar, escanear, comprimir y variantes. Tarea paralela: bifurcar y unir, dividir y conquistar, cultivar, tubería. auxiliar: filtro, final, inicial |
Alt | 2002-2003 | Java / GworkflowDL | Java | RMI de Java | sí | No | No | mapa, zip, reducción, escanear, dh, replicar, aplicar, ordenar |
(E) PAS | 1999-2005 | Extensión C ++ | C ++ | MPI | No | sí | No | singleton, replicación, composicional, pipeline, divideconquer, dataparallel |
Litio | 1999-2004 | Java | Java | RMI | No | sí | No | tubería, mapa, granja, reducir |
CO2P3S | 1999-2003 | GUI / Java | Java (generado) | Hilos / RMI / Enchufes | Parcial | No | No | secuencia de método, distribuidor, malla, frente de onda |
GRAPAS | 2010– | C ++ | C ++ 11 | Biblioteca en tiempo de ejecución STAPL (MPI, OpenMP, PThreads) | sí | sí | sí | map, zip Operadores: redactar, repetir, hacer mientras, hacer todo, cruzar |
Ver también
- Halide (lenguaje de programación)
- Cuneiforme (lenguaje de programación)
- Modelo de programación paralela
Referencias
- ^ K. Hammond y G. Michelson, editores. "Direcciones de investigación en programación funcional paralela". Springer-Verlag, Londres, Reino Unido, 1999.
- ^ 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 .
- ^ M. Aldinucci, M. Coppola, M. Danelutto, N. Tonellotto, M. Vanneschi y C. Zoccolo. "Programación de red de alto nivel con ASSIST". Métodos computacionales en ciencia y tecnología, 12 (1): 21–32, 2006.
- ^ M. Aldinucci y M. Torquati. Acelerar las granjas de apache a través de un repositorio de objetos escalable distribuido ad hoc. En Proc. del décimo Intl. Euro-Par 2004 Parallel Processing, volumen 3149 de LNCS, páginas 596–605. Springer, 2004.
- ^ Aldinucci, M .; Danelutto, M .; Antoniu, G .; Jan, M. (2008). "Intercambio de datos tolerante a fallas para la red de alto nivel: una arquitectura de almacenamiento jerárquica". Logros en la investigación europea sobre sistemas de red . pag. 67. doi : 10.1007 / 978-0-387-72812-4_6 . ISBN 978-0-387-72811-7.
- ^ 'S. MacDonald, J. Anvik, S. Bromling, J. Schaeffer, D. Szafron y K. Tan. ». "De patrones a marcos y programas paralelos". Computación paralela., 28 (12): 1663–1683, 2002.
- ^ K. Tan, D. Szafron, J. Schaeffer, J. Anvik y S. MacDonald. "Uso de patrones de diseño generativo 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.
- ^ 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.
- ^ D. Caromel, L. Henrio y M. Leyton. "Escriba esqueletos algorítmicos seguros". 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.
- ^ D. Caromel y M. Leyton. "Un modelo de datos de archivo transparente no invasivo para esqueletos algorítmicos". En el 22º Simposio internacional de procesamiento paralelo y distribuido (IPDPS), páginas 1 a 8, Miami, EE. UU., Marzo de 2008. IEEE Computer Society.
- ↑ Mario Leyton, Jose M. Piquer. "Skandium: Programación multinúcleo con esqueletos algorítmicos", IEEE Euro-micro PDP 2010.
- ^ Rita Loogen y Yolanda Ortega-Mallén y Ricardo Peña-Marí. "Programación funcional paralela en el Edén", Journal of Functional Programming, No. 15 (2005), 3, páginas 431–475
- ^ Murray Cole. "Sacar esqueletos del armario: un manifiesto pragmático para la programación esquelética paralela". Computación paralela, 30 (3): 389–406, 2004.
- ^ 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.
- ^ A. Benoit y M. Cole. "Dos conceptos fundamentales en la programación paralela esquelética". En V. Sunderam, D. van Albada, P. Sloot y J. Dongarra, editores, La Conferencia Internacional sobre Ciencias Computacionales (ICCS 2005), Parte II, LNCS 3515, páginas 764–771. Springer Verlag, 2005.
- ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. Evaluar el desempeño 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.
- ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. "Evaluación del desempeño de programas paralelos estructurados en tubería con esqueletos y álgebra de procesos". Computación escalable: práctica y experiencia, 6 (4): 1–16, diciembre de 2005.
- ^ A. Benoit, M. Cole, S. Gilmore y J. Hillston. "Programación de aplicaciones de cuadrícula basadas en esqueletos usando pepa y nws". The Computer Journal, Número especial sobre modelado y medición de la performabilidad de cuadrícula, 48 (3): 369–378, 2005.
- ^ A. Benoit y Y. Robert. "Mapeo de esqueletos de oleoductos en plataformas heterogéneas". En ICCS 2007, la 7ma Conferencia Internacional sobre Ciencias Computacionales, LNCS 4487, páginas 591–598. Springer Verlag, 2007.
- ^ G. Yaikhom, M. Cole, S. Gilmore y J. Hillston. "Un enfoque estructural para modelar el rendimiento de sistemas utilizando esqueletos". Electr. Notas Theor. Computación. Sci., 190 (3): 167-183,2007.
- ^ H. Gonzalez-Velez y M. Cole . "Hacia un paralelismo de canalización totalmente adaptable para entornos distribuidos heterogéneos". En Procesamiento y aplicaciones paralelos y distribuidos, 4º Simposio Internacional (ISPA), Notas de clase en Ciencias de la Computación, páginas 916–926. Springer-Verlag, 2006.
- ^ H. Gonzalez-Velez y M. Cole. "Paralelismo estructurado adaptativo para cuadrículas 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.
- ^ Aldinucci, M .; Campa, S .; Danelutto, M .; Kilpatrick, P .; Torquati, M. (2013). Orientación a sistemas distribuidos en FastFlow (PDF) . Euro-Par 2012: Talleres de procesamiento paralelo. Apuntes de conferencias en Ciencias de la Computación. 7640 . pag. 47. doi : 10.1007 / 978-3-642-36949-0_7 . ISBN 978-3-642-36948-3.
- ^ Aldinucci, M .; Spampinato, C .; Drocco, M .; Torquati, M .; Palazzo, S. (2012). Un algoritmo de conservación de bordes paralelos para la eliminación de ruido de imágenes de sal y pimienta . III Congreso Internacional sobre Teoría, Herramientas y Aplicaciones del Procesamiento de Imágenes (IPTA). pag. 97. doi : 10.1109 / IPTA.2012.6469567 . hdl : 2318/154520 .
- ^ Aldinucci, M .; Danelutto, M .; Kilpatrick, P .; Meneghin, M .; Torquati, M. (2012). Una cola libre de bloqueos ilimitada y eficiente para sistemas multinúcleo . Procesamiento paralelo Euro-Par 2012. Apuntes de conferencias en Ciencias de la Computación. 7484 . pag. 662. doi : 10.1007 / 978-3-642-32820-6_65 . ISBN 978-3-642-32819-0.
- ^ Aldinucci, M .; Meneghin, M .; Torquati, M. (2010). "Smith-Waterman eficiente en Multi-core con Fast Flow ". 2010 18ª Conferencia Euromicro sobre procesamiento en paralelo, distribuido y basado en red . IEEE. pag. 195. CiteSeerX 10.1.1.163.9092 . doi : 10.1109 / PDP.2010.93 . ISBN 978-1-4244-5672-7.
- ^ CA Herrmann y C. Lengauer. "HDC: un lenguaje de orden superior para dividir y conquistar". Cartas de procesamiento paralelo, 10 (2–3): 239–250, 2000.
- ^ CA Herrmann. La paralelización basada en esqueletos de las recurrencias de divide y vencerás. Tesis doctoral, 2000. ISBN 3-89722-556-5 . ".
- ^ J. Dünnweber, S. Gorlatch. "Componentes de orden superior para la programación de redes. Haciendo las redes más utilizables". Springer-Verlag, 2009. ISBN 978-3-642-00840-5
- ^ JF Ferreira, JL Sobral y AJ Proenca. "Jaskel: un marco basado en esqueleto de Java para la computación en cuadrícula y clúster estructurado". En CCGRID '06: Actas del Sexto Simposio Internacional IEEE sobre Computación en Clústeres y Grid, páginas 301–304, Washington, DC, EE. UU., 2006. IEEE Computer Society.
- ^ J. Sobral y A. Proenca. "Habilitación de esqueletos de jaskel para clústeres y cuadrículas computacionales". En IEEE Cluster. IEEE Press, 9 de 2007.
- ^ M. Aldinucci y M. Danelutto. "Optimización de esqueletos paralelos". En Proc. de PDCS: Intl. Conference on Parallel and Distributed Computing and Systems, páginas 955–962, Cambridge, Massachusetts, EE.UU., noviembre de 1999. IASTED, ACTA press.
- ^ Aldinucci, M .; Danelutto, M .; Teti, P. (2003). "Un entorno avanzado que soporta la programación paralela estructurada en Java". Sistemas informáticos de futura generación . 19 (5): 611. CiteSeerX 10.1.1.59.3748 . doi : 10.1016 / S0167-739X (02) 00172-3 .
- ^ M. Danelutto y P. Teti. "Lithium: un entorno estructurado de programación paralela en Java". En Proc. de ICCS: Conferencia Internacional sobre Ciencias Computacionales, volumen 2330 de LNCS, páginas 844–853. Springer Verlag, abril de 2002.
- ^ M. Aldinucci y M. Danelutto. "Una semántica operativa 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, Dresden, Alemania, 2004. Elsevier.
- ^ Aldinucci, M .; Danelutto, M. (2007). "Programación paralela basada en esqueleto: Semántica funcional y paralela en un solo disparo ☆". Lenguajes, sistemas y estructuras informáticas . 33 (3–4): 179. CiteSeerX 10.1.1.164.368 . doi : 10.1016 / j.cl.2006.07.004 .
- ^ M. Aldinucci, M. Danelutto y J. Dünnweber. "Técnicas de optimización para la implementación de esqueletos paralelos en entornos grid". En S. Gorlatch, editor, Proc. de CMPP: Intl. Taller sobre métodos constructivos para la programación paralela, páginas 35–47, Stirling, Escocia, Reino Unido, julio de 2004. Universität Munster, Alemania.
- ^ M. Danelutto . Soporte eficiente para esqueletos en clústeres de estaciones de trabajo. Cartas de procesamiento paralelo, 11 (1): 41–56, 2001.
- ^ M. Danelutto. "Soporte de tiempo de ejecución dinámico para esqueletos". Informe técnico, 1999.
- ^ M. Danelutto. "Qos en programación paralela a través de administradores 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.
- ^ M. Aldinucci y M. Danelutto. "El costo de la seguridad en los sistemas esqueléticos". En P. D'Ambra y MR Guarracino, editores, Proc. de Intl. Euromicro PDP 2007: Procesamiento distribuido en paralelo y basado en red, páginas 213–220, Napoli, Italia, febrero de 2007. IEEE.
- ^ M. Aldinucci y M. Danelutto. "Asegurar los sistemas esqueléticos con una penalización de rendimiento limitada: la experiencia muskel". Revista de Arquitectura de Sistemas, 2008.
- ^ M. Danelutto y P. Dazzi. "Un marco Java / Jini que admite cálculos en paralelo de secuencias". En Proc. de Intl. PARCO 2005: Parallel Computing, septiembre de 2005.
- ^ M. Danelutto y P. Dazzi. "Explotación conjunta del paralelismo estructurado / no estructurado a través del flujo de datos". En V. Alexandrov, D. van Albada, P. Sloot y J. Dongarra, editores, Proc. de ICCS: Conferencia Internacional sobre Ciencias Computacionales, Taller sobre aspectos prácticos de la programación paralela de alto nivel, LNCS, Reading, Reino Unido, mayo de 2006. Springer Verlag.
- ^ M. Aldinucci, M. Danelutto y P. Dazzi. "Muskel: un entorno esquelético expandible". Computación escalable: práctica y experiencia, 8 (4): 325–341, diciembre de 2007.
- ^ 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 la optimización combinatoria (nota de investigación) ". En Euro-Par '02: Actas de la 8ª Conferencia Internacional Euro-Par sobre procesamiento paralelo, páginas 927–932, Londres, Reino Unido, 2002. Springer-Verlag.
- ^ E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Díaz, I. Dorta, J. Gabarro, C. Leon, G. Luque, J. Petit, C. Rodríguez, A. Rojas y F. Xhafa. Algoritmos lan / wan paralelos eficientes para la optimización: el proyecto mallba. Computación paralela, 32 (5): 415–440, 2006.
- ^ E. Alba, G. Luque, J. García-Nieto, G. Ordóñez y G. Leguizamon. "Mallba una biblioteca de software para diseñar algoritmos de optimización eficientes". Revista Internacional de Computación y Aplicaciones Innovadoras, 1 (1): 74–85, 2007.
- ^ "Ricardo Marques, Hervé Paulino, Fernando Alexandre, Pedro D. Medeiros". "Framework de esqueleto algorítmico para la orquestación de cálculos de GPU". Euro-Par 2013: 874–885
- ^ "Fernando Alexandre, Ricardo Marques, Hervé Paulino". "Sobre el soporte de esqueletos algorítmicos en paralelo de tareas para computación con múltiples GPU". ACM SAC 2014: 880–885
- ^ H. Kuchen y J. Striegnitz. "Características de la programación funcional para una biblioteca de esqueleto C ++". Simultaneidad: práctica y experiencia, 17 (7–8): 739–756, 2005.
- ^ Philipp Ciechanowicz, Michael Poldner y Herbert Kuchen. "El Muesli de la biblioteca de esqueletos de Muenster: una descripción general completa". Documento de trabajo de ERCIS No. 7, 2009
- ^ H. Kuchen y M. Cole . "La integración de esqueletos paralelos de tareas y datos". Cartas de procesamiento paralelo, 12 (2): 141-155, 2002.
- ^ A. Alexandrescu. "Diseño C ++ moderno: programación genérica y patrones de diseño aplicados". Addison-Wesley, 2001.
- ^ Michael Poldner. "Esqueletos algorítmicos paralelos de tareas". Tesis doctoral, Universidad de Münster, 2008.
- ^ Michael Poldner y Herbert Kuchen. "Esqueletos algorítmicos para rama y límite". Actas de la 1ª Conferencia Internacional sobre Software y Tecnología de Datos (ICSOFT), 1: 291–300, 2006.
- ^ Michael Poldner y Herbert Kuchen. "Optimización del procesamiento de flujo esquelético para dividir y conquistar". Actas de la 3ª Conferencia Internacional sobre Tecnologías de Software y Datos (ICSOFT), 181–189, 2008.
- ^ Michael Poldner y Herbert Kuchen. "Esqueletos para dividir y conquistar". Actas de la Conferencia internacional IASTED sobre redes y computación distribuida y paralela (PDCN), 181–188, 2008.
- ^ Michael Poldner y Herbert Kuchen. "Granjas escalables". Actas de la Conferencia Internacional sobre Procesamiento Paralelo (ParCo) 33: 795–802, 2006.
- ^ Michael Poldner y Herbert Kuchen. "Sobre la implementación del esqueleto de la granja". Cartas de procesamiento paralelo, 18 (1): 117-131, 2008.
- ^ Philipp Ciechanowicz. "Esqueletos algorítmicos para matrices dispersas generales". Actas de la 20ª Conferencia Internacional IASTED sobre Sistemas y Computación Paralelos y Distribuidos (PDCS), 188-197, 2008.
- ^ Philipp Ciechanowicz, Philipp Kegel, Maraike Schellmann, Sergei Gorlatch y Herbert Kuchen. "Paralelizar la reconstrucción de imágenes LM OSEM en clústeres de varios núcleos". Computación paralela: de multinúcleos y GPU a Petascale, 19: 169–176, 2010.
- ^ Philipp Ciechanowicz y Herbert Kuchen. "Mejora de esqueletos paralelos de datos de Muesli para arquitecturas informáticas multinúcleo". Conferencia Internacional sobre Computación y Comunicaciones de Alto Rendimiento (HPCC), 108-113, 2010.
- ^ Bacci, B .; Danelutto, M .; Orlando, S .; Pelagatti, S .; Vanneschi, M. (1995). "P3L: Un lenguaje paralelo estructurado de alto nivel y su soporte estructurado". Simultaneidad: práctica y experiencia . 7 (3): 225. CiteSeerX 10.1.1.215.6425 . doi : 10.1002 / cpe.4330070305 .
- ↑ 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 de Australia, Canberra, agosto de 1997.
- ^ M. Aldinucci, M. Coppola y M. Danelutto. Reescritura de programas esqueléticos: cómo evaluar el intercambio de datos, flujo paralelo y paralelo. En S. Gorlatch, editor, Proc de CMPP: Intl. Taller sobre métodos constructivos para la programación paralela, páginas 44–58. Uni. Passau, Alemania, mayo de 1998.
- ^ B. Bacci, M. Danelutto, S. Pelagatti y M. Vanneschi. "Skie: un entorno heterogéneo para aplicaciones HPC". Computación paralela., 25 (13-14): 1827-1852, 1999.
- ^ 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.
- ^ D. Goswami, A. Singh y BR Preiss. "Desde patrones de diseño hasta esqueletos arquitectónicos paralelos". J. Parallel Distrib. Comput., 62 (4): 669–695, 2002.
- ^ D. Goswami, A. Singh y BR Preiss. "Uso de técnicas orientadas a objetos para realizar esqueletos arquitectónicos paralelos". En ISCOPE '99: Actas del Tercer Simposio Internacional sobre Computación en Ambientes Paralelos Orientados a Objetos, Lecture Notes in Computer Science, páginas 130-141, Londres, Reino Unido, 1999. Springer-Verlag.
- ^ 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 Procesamiento y aplicaciones paralelos y distribuidos, segundo simposio internacional, ISPA, Lecture Notes in Computer Science, páginas 985–996. Springer-Verlag, 2004.
- ^ MM Akon, A. Singh, D. Goswami y HF Li. "Esqueletos arquitectónicos paralelos extensibles". En High Performance Computing HiPC 2005, 12ª Conferencia Internacional, volumen 3769 de Lecture Notes in Computer Science, páginas 290–301, Goa, India, diciembre de 2005. Springer-Verlag.
- ^ M. Díaz, B. Rubio, E. Soler y JM Troya. "SBASCO: Componentes científicos basados en esqueletos". En PDP, páginas 318–. Sociedad de Informática IEEE, 2004.
- ^ M. Díaz, 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 Aspectos prácticos de la programación paralela de alto nivel (PAPP), afiliado a la Conferencia Internacional sobre Ciencias Computacionales (ICCS), volumen 3992 de Lecture Notes in Computer Science, páginas 912–919. Springer, 2006.
- ^ M. Díaz, 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.
- ^ M. Díaz, S. Romero, B. Rubio, E. Soler y JM Troya. "Reconfiguración dinámica de componentes científicos utilizando 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.
- ^ 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 la programación paralela, páginas 19–28, Nueva York, NY, EE. UU., 1995. ACM.
- ^ 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
- ^ http://www.ida.liu.se/~chrke/skepu
- ^ 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, 5ª Conferencia Internacional sobre Tecnologías de Computación Paralela (PaCT-99), volumen 1662 de LNCS, páginas 296–305. Springer, 6 a 10 de septiembre de 1999.
- ^ J. Serot y D. Ginhac. "Esqueletos para el procesamiento de imágenes en paralelo: una descripción general del proyecto SKiPPER". Computación paralela, 28 (12): 1785–1808, diciembre de 2002.
- ^ J. Falcou, J. Serot, T. Chateau y JT Lapreste. "Quaff: diseño eficiente en C ++ para esqueletos paralelos". Computación paralela, 32 (7): 604–615, 2006.
- ^ J. Falcou y J. Serot. "Semántica formal aplicada a la implementación de una biblioteca de programación paralela basada en esqueletos". En GR Joubert, C. Bischof, FJ Peters, T. Lippert, M. Bcker, P. Gibbon y B. Mohr, editores, Parallel Computing: Architectures, Algorithms and Applications (Proc. De PARCO 2007, Julich, Alemania), volumen 38 de NIC, páginas 243–252, Alemania, septiembre de 2007. Instituto de Computación John von Neumann.
- ^ 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.
- ^ 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.
- ^ K. Matsuzaki, Z. Hu y M. Takeichi. "Esqueletos paralelos para manipular árboles generales". Computación paralela, 32 (7): 590–603, 2006.
- ^ K. Emoto, Z. Hu, K. Kakehi y M. Takeichi. "Un marco de composición para el desarrollo de programas paralelos en matrices bidimensionales". Informe técnico, Departamento de Informática Matemática, Universidad de Tokio, 2005.
- ^ K. Emoto, K. Matsuzaki, Z. Hu y M. Takeichi. "Estrategia de optimización de dominios específicos para programas esqueléticos". En Euro-Par, volumen 4641 de Lecture Notes in Computer Science, páginas 705–714. Springer, 2007.
- ^ K. Matsuzaki, K. Kakehi, H. Iwasaki, Z. Hu y Y. Akashi. "Una biblioteca de esqueletos incrustados por 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.
- ^ GH Botorog y H. Kuchen. "Programación paralela eficiente de alto nivel". Theor. Computación. Sci., 196 (1-2): 71-107, 1998.
- ^ 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ª ACM sobre Conferencia Internacional sobre Supercomputación . págs. 415–424. doi : 10.1145 / 2751205.2751241 . ISBN 9781450335591.
- ^ 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 . Apuntes de conferencias en Ciencias de la Computación. Springer International Publishing. págs. 176–190. doi : 10.1007 / 978-3-319-17473-0_12 . ISBN 9783319174723.
- ^ "G. Tanase, et.al." "STAPL Parallel Container Framework" Actas de PPoPP '11 Actas del 16º simposio de ACM sobre Principios y práctica de la programación paralela Páginas 235–246
- ^ J. Darlington, AJ Field, PG Harrison, PHJ Kelly, DWN Sharp y Q. Wu. "Programación paralela usando funciones esqueléticas". En PARLE '93: Actas de la 5ª Conferencia Internacional PARLE sobre arquitecturas paralelas y lenguas europeas, páginas 146–160, Londres, Reino Unido, 1993. Springer-Verlag.
- ^ 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