Hispanopedia Wiki
Articulo de referencia

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 ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 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 se definen implícitamente mediante los patrones del esqueleto. Los programadores no tienen que especificar las sincronizaciones entre las partes secuenciales de la aplicación. Esto conlleva dos implicaciones. Primero, como los patrones de comunicación/acceso a datos se conocen de antemano, se pueden aplicar modelos de costos para programar los programas de esqueletos. [ 1 ] Segundo, que la programación de esqueletos algorítmicos reduce el número de errores en comparación con los modelos de programación paralela tradicionales de bajo nivel (hilos, 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 del algoritmo QuickSort basada en un esqueleto algorítmico , utilizando el patrón Divide y vencerás. Cabe destacar que este enfoque de alto nivel oculta la gestión de hilos al programador.

import java.util.concurrent.* ; import cl.niclabs.skandium.* ;// 1. Definir el programa esqueleto Skeleton < Range , Range > sort = new DaC <> ( new ShouldSplit ( threshold , 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 completa el patrón ( ShouldSplit, SplitList, Sort, MergeList). El código funcional lo escribe el programador sin preocuparse por el paralelismo.
  2. El segundo paso consiste en la introducción de datos, lo que activa el cálculo. En este caso, `Range` es una clase que contiene un array y dos índices que permiten representar un sub-array. Por cada dato introducido en el framework, se crea un nuevo objeto `Future`. Se pueden introducir varios objetos `Future` simultáneamente en un esqueleto.
  3. El futuro permite la computación asíncrona, ya que se pueden realizar otras tareas mientras se calculan los resultados.
  4. Podemos recuperar el resultado del cálculo, bloqueando la operación si es necesario (es decir, si los resultados aún no están disponibles).

Los códigos funcionales de este ejemplo corresponden a cuatro tipos: Condición, División, Ejecución y Combinación.

importar java.util.concurrent.* ;public class ShouldSplit implements Condition < Range > { private int threshold ; private int maxTimes ; private int times ; public ShouldSplit ( int threshold , int maxTimes ) { this . threshold = threshold ; this . maxTimes = maxTimes ; this . times = 0 ; } @Override public synchronized boolean condition ( Range r ) { return ( r . right - r . left ) > threshold && times ++ < maxTimes ; } }

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

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

importar java.util.concurrent.* ;public class SplitList implements Split < Range , Range > { @Override public Range [] split ( Range r ) { int i = partition ( r . array , r . left , r . right ); Range [] intervals = { new Range ( r . array , r . left , i - 1 ), new Range ( r . array , i + 1 , r . right ) }; return intervals ; } }

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

import java.util.Arrays ; import java.util.concurrent.* ;public class Sort implements Execute < Range , Range > { @Override public Range execute ( Range r ) { if ( r . right <= r . left ) { return r ; } Arrays . sort ( r . array , r . left , r . right + 1 ); return r ; } }

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

importar java.util.concurrent.* ;publicclassMergeListimplementsMerge<Range,Range>{@OverridepublicRangemerge(Range[]r){returnnewRange(r[0].array,r[0].left,r[1].right);}}

Frameworks and libraries

ASSIST

ASSIST[2][3] is a programming environment which provides programmers with a structured coordination language. The coordination language can express parallel programs as an arbitrary graph of software modules. The module graph describes how a set of modules interact with each other using a set of typed data streams. The modules can be sequential or parallel. Sequential modules can be written in C, C++, or Fortran; and parallel modules are programmed with a special ASSIST parallel module (parmod).

AdHoc,[4][5] a hierarchical and fault-tolerant Distributed Shared Memory (DSM) system is used to interconnect streams of data between processing elements by providing a repository with: get/put/remove/execute operations. Research around AdHoc has focused on transparency, scalability, and fault-tolerance of the data repository.

While not a classical skeleton framework, in the sense that no skeletons are provided, ASSIST's generic parmod can be specialized into classical skeletons such as: farm, map, etc. ASSIST also supports autonomic control of parmods, and can be subject to a performance contract by dynamically adapting the number of resources used.

CO2P3S

CO2P3S (Correct Object-Oriented Pattern-based Parallel Programming System), is a pattern oriented development environment,[6] which achieves parallelism using threads in Java.

CO2P3S is concerned with the complete development process of a parallel application. Programmers interact through a programming GUI to choose a pattern and its configuration options. Then, programmers fill the hooks required for the pattern, and new code is generated as a framework in Java for the parallel execution of the application. The generated framework uses three levels, in descending order of abstraction: patterns layer, intermediate code layer, and native code layer. Thus, advanced programmers may intervene the generated code at multiple levels to tune the performance of their applications. The generated code is mostly type safe, using the types provided by the programmer which do not require extension of superclass, but fails to be completely type safe such as in the reduce(..., Object reducer) method in the mesh pattern.

The set of patterns supported in CO2P3S corresponds to method-sequence, distributor, mesh, and wavefront. Complex applications can be built by composing frameworks with their object references. Nevertheless, if no pattern is suitable, the MetaCO2P3S graphical tool addresses extensibility by allowing programmers to modify the pattern designs and introduce new patterns into CO2P3S.

Support for distributed memory architectures in CO2P3S was introduced in later.[7] To use a distributed memory pattern, programmers must change the pattern's memory option from shared to distributed, and generate the new code. From the usage perspective, the distributed memory version of the code requires the management of remote exceptions.

Calcium & Skandium

Calcium is greatly inspired by Lithium and Muskel. As such, it provides algorithmic skeleton programming as a Java library. Both task and data parallel skeletons are fully nestable; and are instantiated via parametric skeleton objects, not inheritance.

Calcium supports the execution of skeleton applications on top of the ProActive environment for distributed cluster like infrastructure. Additionally, Calcium has three distinctive features for algorithmic skeleton programming. First, a performance tuning model which helps programmers identify code responsible for performance bugs.[8] Second, a type system for nestable skeletons which is proven to guarantee subject reduction properties and is implemented using Java Generics.[9] Third, a transparent algorithmic skeleton file access model, which enables skeletons for data intensive applications.[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 la programación paralela, mientras que sus comunicaciones permanecen implícitas. Los procesos se comunican a través de canales unidireccionales, que conectan un escritor con un único lector. Los programadores solo necesitan especificar de qué datos depende un proceso. El modelo de procesos 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 bajo nivel de Eden, lo que permite el paralelismo tanto de tareas como de datos . Por lo tanto, a diferencia de la mayoría de los demás enfoques, Eden permite que los esqueletos se definan en el mismo lenguaje y al mismo nivel en que se escribe la instanciación del esqueleto: el propio Eden. Dado 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 ( eSkel ) está escrita 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 los esqueletos. El modo de anidamiento 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 el persistente significa que el esqueleto se instancia una vez y la misma instancia de esqueleto se invocará durante 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 la explícita significa que los datos pueden generarse o eliminarse 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.

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 rendimiento para cada mapeo, basado en á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ía. [ 21 ] [ 22 ]

Flujo rápido

FastFlow es un marco de programación paralela esquelético específicamente dirigido al desarrollo de aplicaciones de transmisión y procesamiento paralelo de datos. Desarrollado inicialmente para plataformas multinúcleo , se ha extendido sucesivamente para abarcar plataformas heterogéneas compuestas por clústeres de plataformas de memoria compartida, [ 23 ] [ 24 ] posiblemente equipadas con aceleradores de computación como NVidia GPGPU, Xeon Phi , Tilera TILE64. La filosofía de diseño principal 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, que incluyen, entre otros: paralelismo de grano fino en plataformas de memoria compartida con coherencia de caché; aplicaciones de transmisión; uso acoplado de multinúcleo y aceleradores. En otros casos, FastFlow suele ser comparable a (y en algunos casos es ligeramente más rápido que) marcos de programación paralela de última generación como Intel TBB, OpenMP, Cilk, etc. [ 26 ]

HDC

El enfoque de 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 a C/MPI y enlazarse con implementaciones de esqueleto. El lenguaje se centra en el paradigma de divide y vencerás, y a partir de un esqueleto general 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 a 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 base, 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 puede resultar en un número excesivo de subproblemas o en un paralelismo insuficiente para aprovechar 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 ( HOC ) tienen como objetivo simplificar el desarrollo de aplicaciones Grid. El objetivo de HOC-SA es proporcionar a los usuarios de Globus, que no desean conocer todos los detalles del middleware de Globus (documentos GRAM RSL, servicios web y configuración de recursos, etc.), HOC que ofrecen una interfaz de nivel superior a la del Globus Toolkit principal. Los HOC son esqueletos habilitados para Grid, implementados como componentes sobre el Globus Toolkit, accesibles remotamente a través de servicios web. [ 29 ]

JaSkel

JaSkel [ 30 ] es un framework de esqueletos basado en Java que proporciona esqueletos como farm, pipe y heartbeat. Los esqueletos se especializan mediante 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, el esqueleto concurrente farm se puede usar en entornos de memoria compartida (hilos), pero no en entornos distribuidos (clústeres), donde se debe usar el esqueleto distribuido. Para cambiar de una versión a otra, los programadores deben cambiar la firma de sus clases para que hereden de un esqueleto diferente. El anidamiento de esqueletos utiliza la clase básica Java Object, por lo que no se impone ningún sistema de tipos durante la composición del esqueleto.

En JaSkel, los aspectos de distribución del cálculo se gestionan mediante AOP, específicamente con la implementación de AspectJ. Por lo tanto, JaSkel puede implementarse tanto en clústeres como en infraestructuras tipo Grid. [ 31 ] Sin embargo, una desventaja del enfoque de JaSkel es que el anidamiento del esqueleto está estrictamente relacionado con la infraestructura de implementación. Así, un doble anidamiento de granjas produce un mejor rendimiento que una granja simple en infraestructuras jerárquicas. Esto contradice el propósito de usar AOP para separar las preocupaciones de distribución y funcionalidad del programa esqueleto.

Litio y almizcle

Lithium [ 32 ] [ 33 ] [ 34 ] y su sucesor Muskel son marcos de trabajo de esqueleto desarrollados en la Universidad de Pisa, Italia. Ambos proporcionan esqueletos anidables al programador como bibliotecas Java. La evaluación de una aplicación de 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 el comportamiento funcional y paralelo del lenguaje de esqueleto utilizando un sistema de transición etiquetado. Además, se aplican varias optimizaciones de rendimiento, tales como: técnicas de reescritura de esqueleto [18, 10], anticipación de tareas y enlace perezoso 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 base se procesa para obtener un grafo de flujo de macrodatos. Los nodos del grafo son instrucciones de flujo de macrodatos (MDFi), que representan las secuencias 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. Una vez finalizado el cálculo del grafo, el resultado se coloca en el flujo de salida y se entrega 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 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 no estructurada [ 44 ] y la investigación reciente ha abordado la extensibilidad. [ 45 ]

Mallba

Mallba [ 46 ] es una biblioteca para optimizaciones combinatorias que admite estrategias de búsqueda exactas, heurísticas e híbridas. [ 47 ] Cada estrategia se implementa en Mallba como un esqueleto genérico que se puede usar proporcionando el código necesario. En los algoritmos de búsqueda exacta, Mallba proporciona esqueletos de ramificación y acotación y optimización dinámica. Para las heurísticas de búsqueda local, Mallba admite: ascenso de colina , 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 evolutiva 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 C++ y no son anidables, pero sí de tipos seguros. Se utiliza una capa de abstracción MPI personalizada, NetStream, que se encarga de la serialización de tipos de datos primitivos, la sincronización, etc. Un esqueleto puede tener múltiples implementaciones paralelas de bajo nivel 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 almacenan 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 usar para almacenar la mejor solución encontrada hasta el momento, o los valores α y β para la poda de ramificación y acotación. [ 48 ]

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

Médula

Marrow [ 49 ] [ 50 ] es un marco de trabajo de esqueleto algorítmico en C++ para la orquestación de cálculos OpenCL en entornos multi- GPU , posiblemente heterogéneos . Proporciona un conjunto de esqueletos tanto de tareas como de datos paralelos 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 de cálculo de la 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, incluyendo 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 distintivas 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 anidamiento de esqueletos, una característica también novedosa en este contexto. Además, el framework 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 mediante múltiples 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. Salvo especificar qué parámetros del kernel pueden descomponerse y, cuando sea necesario, definir cómo deben combinarse los resultados parciales, el programador está completamente abstraído de la arquitectura multi-GPU subyacente.

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

Muesli

La biblioteca de plantillas Muenster Skeleton Library 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.. Está construido 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. El anidamiento 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 anidamiento paralelo de tareas. [ 53 ] Se utilizan plantillas de C++ para hacer que los esqueletos sean polimórficos, pero no se impone 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 admitidos [ 55 ] son ​​Branch & Bound, [ 56 ] Divide & Conquer, [ 57 ] [ 58 ] Farm, [ 59 ] [ 60 ] y Pipe, los esqueletos auxiliares son Filter, Final e Initial. Los esqueletos de paralelismo 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 de paralelismo 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 compila y se ejecuta en una computadora de clúster de múltiples nodos de un solo núcleo sin cambios en el código fuente, es decir, se garantiza la compatibilidad con versiones anteriores. Esto se asegura proporcionando una capa de abstracción OpenMP muy delgada de modo que el soporte para arquitecturas de múltiples núcleos se puede activar/desactivar simplemente proporcionando/omitiendo el indicador del compilador OpenMP al compilar el programa. Al hacer esto, prácticamente no se introduce sobrecarga en tiempo de ejecución.

P3L, SkiIE, SKElib

P3L [ 64 ] (Pisa Parallel Programming Language) es un lenguaje de coordinación basado en esqueletos. P3L proporciona construcciones de esqueleto que se utilizan para coordinar la ejecución paralela o secuencial del código C. Se proporciona un compilador llamado Anacleto [ 65 ] para el lenguaje. Anacleto utiliza plantillas de implementación para compilar el código P3L en una arquitectura de destino. De este modo, 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 grafo 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 una estructura básica definida con flujos de entrada y salida, y otros submódulos o código C secuencial. Los módulos pueden anidarse mediante un modelo de dos niveles, donde el nivel externo se compone de estructuras paralelas de tareas, mientras que en el nivel interno se pueden utilizar estructuras paralelas de datos [64]. La verificación de tipos se realiza a nivel de flujo de datos, cuando el programador especifica explícitamente el tipo de los flujos de entrada y salida, y al especificar el flujo de datos entre submódulos.

SkIE [ 67 ] (Entorno Integrado Basado en Esqueletos) es bastante similar a P3L , ya que también se basa en un lenguaje de coordinación, pero ofrece funciones avanzadas como herramientas de depuración, análisis de rendimiento, visualización e interfaz gráfica de usuario. En lugar de usar 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 otras cosas, 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 trabajo de esqueletos 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 utilizan una extensión de C++ para escribir sus aplicaciones de esqueleto1 . El código luego 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 que se encarga de coordinar la ejecución del esqueleto. Los esqueletos pueden anidarse jerárquicamente mediante los objetos Rep. Además de la ejecución del esqueleto, el 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 padre y los subesqueletos.

Una extensión de PAS denominada SuperPas [ 71 ] y posteriormente EPAS [ 72 ] aborda las preocupaciones sobre la extensibilidad de los esqueletos. Con la herramienta EPAS , se pueden agregar nuevos esqueletos a PAS . Se utiliza un lenguaje de descripción de esqueletos (SDL) para describir el patrón del esqueleto especificando la topología con respecto a una cuadrícula de procesadores virtuales. El SDL se puede compilar a código C++ nativo, que puede utilizarse 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 busca 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 la disposición del procesador. La estructura interna de un componente se puede definir utilizando tres esqueletos: granja, tubería y multibloque.

SBASCO aborda las aplicaciones descomponibles por dominio mediante su esqueleto multibloque. Los dominios se especifican mediante matrices (principalmente bidimensionales), que se descomponen en submatrices con posibles límites superpuestos. El cálculo se realiza de forma iterativa, similar al BSP. La primera etapa consiste en cálculos locales, mientras que la segunda 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: Componentes Científicos (SC), que proporcionan el código funcional; y 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 se conectan a un componente CAC, que puede actuar como gestor en tiempo de ejecución reasignando dinámicamente los procesadores asignados a un SC. En [ 76 ] se muestra un caso de uso que demuestra un rendimiento mejorado al utilizar componentes CAC.

SCL

El lenguaje de coordinación estructurada ( SCL ) [ 77 ] fue uno de los primeros lenguajes de programación de esqueletos. Proporciona un enfoque de lenguaje de coordinación para la programación de esqueletos 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: de configuración , elementales y de 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 de paralelismo de datos como map, scan y fold. Los esqueletos de computación abstraen el flujo de control y corresponden principalmente a esqueletos de paralelismo de tareas como farm, SPMD e iterateUntil. El enfoque de 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 esqueletos para CPU multinúcleo y sistemas multi-GPU. Es una biblioteca de plantillas de C++ con seis esqueletos de paralelismo de datos y uno de paralelismo de tareas, dos tipos de contenedores y soporte para ejecución en sistemas multi-GPU tanto con CUDA como con OpenCL. Recientemente, se ha desarrollado en SkePU soporte para ejecución híbrida, planificación dinámica con conciencia del rendimiento y equilibrio de carga mediante la implementación de un backend para el sistema de tiempo de ejecución StarPU. SkePU se está extendiendo para clústeres de GPU.

SKiPPER & QUAFF

SKiPPER es una biblioteca de esqueletos específica 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 operacional. Los esqueletos declarativos son utilizados directamente por los programadores, mientras que sus versiones operacionales proporcionan una implementación de destino específica para 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 características 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 operacionales: grafos de flujo de datos estáticos, redes de procesos paramétricos, grafos de tareas jerárquicas y grafos de flujo de datos de tokens etiquetados. [ 81 ]

QUAFF [ 82 ] es una biblioteca de esqueletos más reciente escrita en C++ y MPI. QUAFF se basa en técnicas de metaprogramación basadas en plantillas para reducir la sobrecarga en tiempo de ejecución y realizar expansiones y optimizaciones de esqueletos en tiempo de compilación. Los esqueletos pueden anidarse y las funciones secuenciales son con 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 ]

Escanea

El proyecto SkeTo [ 84 ] es una biblioteca de C++ que logra la paralelización mediante MPI. SkeTo se diferencia de otras bibliotecas de esqueletos porque, en lugar de proporcionar patrones de paralelismo anidables, proporciona esqueletos paralelos para estructuras de datos paralelas como listas, árboles [ 85 ] [ 86 ] y matrices [ 87 ] . Las estructuras de datos se tipifican mediante 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.

La investigación adicional sobre SkeTo también se ha centrado en estrategias de optimización mediante 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 combina dos invocaciones de funciones sucesivas en una sola, lo que reduce la sobrecarga de las llamadas a funciones y evita la creación de estructuras de datos intermedias que se pasan entre funciones.

Habilidad

Skil [ 90 ] es un lenguaje imperativo para la programación de esqueletos. 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 propias de los lenguajes funcionales, como funciones de orden superior, curring y tipos polimórficos. Al compilar Skil , estas características se eliminan y se genera código C estándar. De este modo, Skil transforma funciones polimórficas de orden superior en funciones monomórficas de primer orden de C. Skil no admite la composición anidada de esqueletos. El paralelismo de datos se logra mediante estructuras específicas de paralelismo de datos, por ejemplo, para distribuir matrices entre los procesadores disponibles. Se pueden utilizar esqueletos de filtro.

Marco de trabajo básico de STAPL

En STAPL Skeleton Framework [ 91 ] [ 92 ] , los esqueletos se definen como grafos de flujo de datos paramétricos, lo que les permite escalar más allá de 100 000 núcleos. Además, este marco aborda la composición de esqueletos como una composición punto a punto de sus grafos de flujo de datos correspondientes a través del concepto de puertos, lo que permite agregar nuevos esqueletos fácilmente 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 alternar entre ejecución paralela y secuencial en cada nivel de anidamiento. Este marco se beneficia de la implementación escalable de los 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 se basaba en gran medida en las propiedades de la programación funcional, y se definieron cinco esqueletos como funciones de orden superior: Divide y vencerás, Granja, Mapa, Tubería y RaMP. Un programa podía tener más de una implementación, cada una utilizando una combinación de diferentes esqueletos. Además, cada esqueleto podía tener diferentes implementaciones paralelas. Se utilizó una metodología basada en transformaciones de programas funcionales guiadas por modelos de rendimiento de los esqueletos para seleccionar el esqueleto más apropiado para el programa, así como la implementación más apropiada del esqueleto. [ 95 ]

Comparación de marcos de trabajo

  • El período de actividad conocido corresponde a las fechas indicadas en esta columna. Estas fechas corresponden a la primera y última publicación de un artículo relacionado en una revista científica o actas de congreso. Cabe destacar que un proyecto puede seguir activo más allá de este período, y que no hemos encontrado ninguna publicación posterior a 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 y abarcan 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, las estructuras básicas se han proporcionado como construcciones del lenguaje o como bibliotecas. Proporcionar estructuras básicas como construcciones del lenguaje implica el desarrollo de un lenguaje específico de dominio personalizado y su compilador. Esta fue, sin duda, la tendencia predominante al inicio de la investigación sobre estructuras básicas. La tendencia más reciente es proporcionar estructuras básicas como bibliotecas, en particular con lenguajes orientados a objetos como C++ y Java.
  • El lenguaje de ejecución es aquel en el que se ejecutan o compilan las aplicaciones base. Desde muy pronto se reconoció que los lenguajes de programación (especialmente en el caso funcional) no eran lo suficientemente eficientes para ejecutar los programas base. Por lo tanto, los lenguajes de programación base se simplificaron ejecutando las aplicaciones base en otros lenguajes. Se introdujeron procesos de transformación para convertir las aplicaciones base (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 bajo nivel (a veces llamados esqueletos operacionales) 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 la arquitectura de destino, optimizado para el rendimiento, en la aplicación transformada. La Tabla 1 muestra que el lenguaje C ha sido uno de los lenguajes de ejecución preferidos.
  • La biblioteca de distribución proporciona la funcionalidad para realizar cálculos paralelos/distribuidos. La más popular en este sentido ha sido MPI, lo cual no sorprende, 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úster. Los peligros de programar directamente con la biblioteca de distribución, por supuesto, se ocultan a los programadores que nunca interactúan con ella. Recientemente, la tendencia ha sido desarrollar frameworks base capaces de interactuar con más de una biblioteca de distribución. Por ejemplo, CO2 P3 S puede usar Threads, RMI o Sockets; Mallba puede usar Netstream o MPI; o JaSkel, que usa AspectJ para ejecutar las aplicaciones base en diferentes frameworks base.
  • La seguridad de tipos se refiere a la capacidad de detectar errores de incompatibilidad de tipos en un programa esqueleto. Dado que los primeros frameworks esqueleto se basaban en lenguajes funcionales como Haskell, la seguridad de tipos se heredaba directamente del lenguaje anfitrión. Sin embargo, a medida que se desarrollaron lenguajes personalizados para la programación esqueleto, fue necesario escribir compiladores que tuvieran en cuenta la verificación de tipos; lo cual no fue tan difícil, ya que el anidamiento de esqueletos no era totalmente compatible. Recientemente, sin embargo, al comenzar a implementar frameworks esqueleto en lenguajes orientados a objetos con anidamiento completo, el problema de la seguridad de tipos ha resurgido. Desafortunadamente, la verificación de tipos se ha pasado por alto en gran medida (con la excepción de QUAFF), especialmente en los frameworks esqueleto basados ​​en Java.
  • El anidamiento de esqueletos es la capacidad de composición jerárquica de patrones de esqueleto. Desde sus inicios, el anidamiento de esqueletos se identificó como una característica importante en la programación basada en esqueletos, ya que permite la composición de patrones más complejos a partir de un conjunto básico de patrones más simples. Sin embargo, la comunidad tardó mucho tiempo en ofrecer soporte completo para el anidamiento arbitrario de esqueletos, principalmente debido a las dificultades de planificación y verificación de tipos. La tendencia actual es clara: los frameworks de esqueletos recientes ofrecen soporte completo para el anidamiento de esqueletos.
  • El acceso a archivos es la capacidad de acceder a ellos y manipularlos desde una aplicación. Anteriormente, la programación esquelética ha demostrado ser útil principalmente para aplicaciones computacionalmente intensivas, donde pequeñas cantidades de datos requieren mucho tiempo de procesamiento. Sin embargo, muchas aplicaciones distribuidas requieren o generan grandes cantidades de datos durante su procesamiento. Este es el caso de la astrofísica, la física de partículas, la bioinformática, etc. Por lo tanto, brindar soporte para la transferencia de archivos que se integre con la programación esquelética es una cuestión clave que, en general, se ha pasado por alto.
  • Un conjunto de esqueletos es la lista de patrones de esqueletos compatibles. Los conjuntos de esqueletos varían mucho de un framework a otro, y lo que es aún más sorprendente, algunos esqueletos con el mismo nombre tienen semánticas diferentes en distintos frameworks. Los patrones de esqueletos más comunes en la literatura son probablemente farm, pipe y map.

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 alto nivel en redes 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 Actas del 10.º Congreso Internacional Euro-Par 2004 sobre Procesamiento Paralelo, volumen 3149 de LNCS, páginas 596-605. Springer, 2004.
  5. ↑ Aldinucci, M.; Danelutto, M.; Antoniu, G.; Jan, M. (2008). "Compartición 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ág. 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 13.ª Conferencia Internacional Euro-Par: Procesamiento Paralelo, 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 con tipado seguro». En Actas de la 16.ª Conferencia Euromicro sobre Procesamiento Paralelo, Distribuido y Basado en Redes, 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 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. "Sacando 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 esquelética». En V. Sunderam, D. van Albada, P. Sloot y J. Dongarra (eds.), The International Conference on Computational Science (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 (eds.), Conferencia Internacional sobre Ciencias Computacionales (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 con estructura de pipeline mediante 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 cuadrícula basadas en esqueletos utilizando pepa y nws". The Computer Journal, número especial sobre modelado y medición del rendimiento de la cuadrícula, 48(3):369–378, 2005.
  19. ↑ A. Benoit y Y. Robert. «Mapeo de esqueletos de pipelines en plataformas heterogéneas». En ICCS 2007, 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 pipeline totalmente adaptativo para entornos distribuidos heterogéneos». En Procesamiento paralelo y distribuido y aplicaciones, 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). "Targeting Distributed Systems in FastFlow" (PDF) . Euro-Par 2012: Talleres de Procesamiento Paralelo . Euro-Par 2012: Talleres de Procesamiento Paralelo. Lecture Notes in Computer Science. Vol. 7640. pp. 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 paralelo de preservación de bordes para la eliminación de ruido en imágenes de sal y pimienta". 3.ª Conferencia Internacional sobre Teoría, Herramientas y Aplicaciones del Procesamiento de Imágenes (IPTA) de 2012. 3.ª Conferencia Internacional sobre Teoría, Herramientas y Aplicaciones del Procesamiento de Imágenes (IPTA). pp. 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 bloqueo ilimitada y eficiente para sistemas multinúcleo". Procesamiento paralelo Euro-Par 2012. Notas de clase en informática. Vol. 7484. pp. 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. 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 la estrategia de divide y vencerás." 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 la programación en cuadrícula. Haciendo 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 esqueletos de Java para computación en clúster y en malla estructurada». En CCGRID '06: Actas del Sexto Simposio Internacional IEEE sobre Computación en Clúster y en Malla, páginas 301–304, Washington, DC, EE. UU., 2006. IEEE Computer Society.
  31. ↑ J. Sobral y A. Proenca. "Habilitando esqueletos jaskel para clústeres y redes computacionales". En IEEE Cluster. IEEE Press, 9 2007.
  32. ↑ M. Aldinucci y M. Danelutto. "Optimización de esqueletos paralelos de flujo". En Actas de PDCS: Conferencia Internacional sobre Computación y Sistemas Paralelos y Distribuidos, 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 admite 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. «Lithium: Un entorno de programación paralela estructurada en Java». En Actas de ICCS: Conferencia Internacional sobre Ciencias Computacionales, 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, Computación paralela: tecnología de software, algoritmos, arquitecturas y aplicaciones, PARCO 2003, volumen 13 de Avances en computación paralela, páginas 63-70, Dresde, Alemania, 2004. Elsevier.
  36. ↑ Aldinucci, M.; Danelutto, M. (2007). "Programación paralela basada en esqueletos: semántica funcional y paralela en una sola toma☆". Computer Languages, Systems & Structures . 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 la implementación de esqueletos paralelos en entornos de cuadrícula». En S. Gorlatch, editor, Actas del CMPP: Taller Internacional sobre Métodos Constructivos para la Programación Paralela, páginas 35-47, Stirling, Escocia, Reino Unido, julio de 2004. Universidad de Münster, 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 dinámico en tiempo de ejecución para esqueletos". Informe técnico, 1999.
  40. ↑ M. Danelutto. "QoS en programación paralela mediante gestores de aplicaciones". En PDP '05: Actas de la 13.ª Conferencia Euromicro sobre Procesamiento Paralelo, Distribuido y Basado en Redes (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, Actas de Intl. Euromicro PDP 2007: Procesamiento paralelo distribuido y basado en redes, páginas 213–220, Nápoles, Italia, febrero de 2007. IEEE.
  42. ↑ M. Aldinucci y M. Danelutto. "Garantizando la seguridad de sistemas esqueléticos con una penalización 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 del paralelismo estructurado/no estructurado mediante el flujo de datos». En V. Alexandrov, D. van Albada, P. Sloot y J. Dongarra (editores), Actas 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.
  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. Garcia-Nieto, G. Ordonez y G. Leguizamon. «Mallba, una biblioteca de software para diseñar algoritmos de optimización eficientes». International Journal of Innovative Computing and Applications, 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 paralelos para tareas en 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 esqueletos 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 visión general exhaustiva». 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 aplicación de patrones de diseño". Addison-Wesley, 2001.
  55. ↑ Michael Poldner. "Esqueletos algorítmicos paralelos para tareas". Tesis doctoral, Universidad de Münster, 2008.
  56. ↑ Michael Poldner y Herbert Kuchen. "Esqueletos algorítmicos para ramificación 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 flujos de datos esqueléticos para la estrategia de divide y vencerás". 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 conquistar". Actas de la Conferencia Internacional IASTED sobre Computación y Redes Paralelas y Distribuidas (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 de Farm." 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 y Sistemas Paralelos y Distribuidos (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 LM OSEM en clústeres multinúcleo». Computación paralela: de multinúcleos y GPU a petaescala, 19: 169–176, 2010.
  63. ↑ Philipp Ciechanowicz y Herbert Kuchen. «Mejora de los esqueletos de paralelismo de datos de Muesli para arquitecturas informáticas multinúcleo». Conferencia Internacional sobre Computación 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 de alto nivel estructurado y su soporte estructurado". Concurrency: Practice and Experience . 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 compensación entre procesamiento paralelo de datos y procesamiento paralelo de flujos. En S. Gorlatch, editor, Actas del CMPP: Taller Internacional sobre Métodos Constructivos para la Programación Paralela, páginas 44-58. Universidad de 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 patrones de diseño a 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 extensibilidad y composición de esqueletos». En Procesamiento paralelo y distribuido y aplicaciones, Segundo Simposio Internacional, ISPA, Lecture Notes in Computer Science, páginas 985–996. Springer-Verlag, 2004.
  72. ↑ 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.
  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 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.
  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 Redes, 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 (eds.), 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 la 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. ↑ "SkePU" .
  80. ↑ J. Serot, D. Ginhac y J. Derutin. «SKiPPER: un entorno de programación paralela basado en esqueletos 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-10 de septiembre de 1999.
  81. ↑ J. Serot y D. Ginhac. "Esqueletos para el procesamiento paralelo de imágenes : una visió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 esqueletos". En GR Joubert, C. Bischof, FJ Peters, T. Lippert, M. Bcker, P. Gibbon y B. Mohr, editores, Computación paralela: arquitecturas, algoritmos y aplicaciones (Actas de PARCO 2007, Jülich, Alemania), volumen 38 de NIC, páginas 243-252, Alemania, septiembre de 2007. Instituto John von Neumann de Computación.
  84. ↑ K. Matsuzaki, H. Iwasaki, K. Emoto y Z. Hu. "Una biblioteca de esqueletos constructivos para programación paralela de estilo secuencial". 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 árbol». 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 la manipulación de árboles generales". Computación paralela, 32(7):590–603, 2006.
  87. ↑ K. Emoto, Z. Hu, K. Kakehi y M. Takeichi. «Un marco compositivo para el desarrollo de 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 del 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 de alto nivel eficiente". 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 ACM sobre Supercomputación . págs. 415–424 . doi : 10.1145/2751205.2751241 . ISBN  9781450335591. S2CID 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 . Lecture Notes in Computer Science. 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 del 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 mediante funciones 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 
Lecturas relacionadas
6 articulos
Simulación por computadoraComputaciónLa informática es cualquier actividad orientada a objetivos que requiera, se beneficie o cree maquinaria informática . [1] Incluye el estudio y la ...Modelo de programación paralelaModelo de programación paralelaEn informática , un modelo de programación paralela es una abstracción de la arquitectura de computadoras paralelas , con la que es conveniente exp...Computación distribuidaComputación distribuidaLa computación distribuida es un campo de la informática que estudia los sistemas distribuidos , definidos como sistemas informáticos cuyos compone...Ordenación rápidaOrdenación rápidaQuicksort es un algoritmo de ordenamiento eficiente y de uso general . Quicksort fue desarrollado por el informático británico Tony Hoare en 1959 [...Memoria compartida distribuidaMemoria compartida distribuidaEn informática , la memoria compartida distribuida ( DSM ) es una forma de arquitectura de memoria donde las memorias separadas físicamente pueden ...{\displaystyle t}Seguridad de tipoEn informática , la seguridad de tipos es el grado en que un lenguaje de programación desalienta o previene los errores de tipo . Los lenguajes con...