Алгоритмический скелет - Algorithmic skeleton

В вычисление, алгоритмические скелеты, или же шаблоны параллелизма, находятся на высоком уровне модель параллельного программирования для параллельных и распределенных вычислений.

Алгоритмические скелеты используют общие шаблоны программирования, чтобы скрыть сложность параллельных и распределенных приложений. Начиная с базового набора шаблонов (скелетов), можно создавать более сложные шаблоны, комбинируя базовые.

Обзор

Самая выдающаяся особенность алгоритмических каркасов, которая отличает их от других высокоуровневых моделей параллельного программирования, заключается в том, что оркестровка и синхронизация параллельных действий неявно определяются шаблонами каркасов. Программистам не нужно указывать синхронизацию между последовательными частями приложения. Это дает два следствия. Во-первых, поскольку шаблоны связи / доступа к данным известны заранее, модели затрат могут применяться для планирования программ-скелетов.[1] Во-вторых, такое алгоритмическое программирование каркаса снижает количество ошибок по сравнению с традиционными моделями параллельного программирования нижнего уровня (потоки, MPI).

Пример программы

Следующий пример основан на Java Скандий библиотека для параллельного программирования.

Целью является реализация параллельной версии алгоритмического скелета. QuickSort алгоритм с использованием паттерна Divide and Conquer. Обратите внимание, что высокоуровневый подход скрывает управление потоками от программиста.

// 1. Определим скелет программыСкелет<Классифицировать, Классифицировать> Сортировать =   новый DaC<Классифицировать, Классифицировать>(    новый ShouldSplit(порог, maxTimes),    новый SplitList(),    новый Сортировать(),    новый MergeList());		// 2. Входные параметрыБудущее<Классифицировать> будущее = Сортировать.Вход(новый Классифицировать(генерировать(...)));	// 3. Сделайте здесь что-нибудь еще.// ...	// 4. Блок для результатовКлассифицировать результат = будущее.получать();
  1. Первым делом необходимо определить новый экземпляр скелета с функциональным кодом, заполняющим шаблон (ShouldSplit, SplitList, Sort, MergeList). Функциональный код написан программистом без заботы о параллелизме.
  2. Второй шаг - это ввод данных, которые запускают вычисление. В этом случае Range - это класс, содержащий массив и два индекса, которые позволяют представлять подмассив. Для каждой введенной в структуру данных создается новый объект Future. В каркас можно одновременно поместить более одного Будущего.
  3. Будущее допускает асинхронные вычисления, так как другие задачи могут выполняться во время вычисления результатов.
  4. Мы можем получить результат вычисления, заблокировав при необходимости (т.е. результаты еще не доступны).

Функциональные коды в этом примере соответствуют четырем типам Condition, Split, Execute и Merge.

общественный учебный класс ShouldSplit орудия Условие<Классифицировать>{  int порог, maxTimes, раз;    общественный ShouldSplit(int порог, int maxTimes){    это.порог = порог;    это.maxTimes  = maxTimes;    это.раз     = 0;  }	  @Override  общественный синхронизированный логический условие(Классифицировать р){    возвращаться р.верно - р.оставили > порог &&    	   раз++ < это.maxTimes;  }}

Класс ShouldSplit реализует интерфейс Condition. Функция получает вход, в данном случае Range r, и возвращает true или false. В контексте «Разделяй и властвуй», где будет использоваться эта функция, она будет определять, следует ли подразделить подмассив снова или нет.

Класс SplitList реализует интерфейс разделения, который в этом случае делит (под) массив на более мелкие подмассивы. Класс использует вспомогательную функцию раздел (...) который реализует хорошо известную схему поворота и обмена QuickSort.

общественный учебный класс SplitList орудия Расколоть<Классифицировать, Классифицировать>{ @Override общественный Классифицировать[] расколоть(Классифицировать р){            int я = раздел(р.множество, р.оставили, р.верно);            Классифицировать[] интервалы = {новый Классифицировать(р.множество, р.оставили, я-1),                          новый Классифицировать(р.множество, я+1, р.верно)};            возвращаться интервалы; }}

Класс Sort реализует интерфейс Execute и отвечает за сортировку подмассивов, указанных в Диапазон r. В этом случае мы просто вызываем метод Java по умолчанию (Arrays.sort) для данного подмассива.

общественный учебный класс Сортировать орудия Выполнять<Классифицировать, Классифицировать> {  @Override  общественный Классифицировать выполнять(Классифицировать р){		    если (р.верно <= р.оставили) возвращаться р;		    Массивы.Сортировать(р.множество, р.оставили, р.верно+1);		    возвращаться р;  }}

Наконец, как только набор подмассивов отсортирован, мы объединяем части подмассивов в более крупный массив с помощью класса MergeList, который реализует интерфейс слияния.

общественный учебный класс MergeList орудия Объединить<Классифицировать, Классифицировать>{  @Override  общественный Классифицировать слияние(Классифицировать[] р){		    Классифицировать результат = новый Классифицировать( р[0].множество, р[0].оставили, р[1].верно);		    возвращаться результат;  }}

Фреймворки и библиотеки

ПОМОЩЬ

ПОМОЩЬ[2][3] это среда программирования, которая предоставляет программистам структурированный координационный язык. Координационный язык может выражать параллельные программы в виде произвольного графа программных модулей. График модулей описывает, как набор модулей взаимодействует друг с другом с помощью набора типизированных потоков данных. Модули могут быть последовательными или параллельными. Последовательные модули могут быть написаны на C, C ++ или Fortran; а параллельные модули программируются с помощью специального параллельного модуля ASSIST (пармод).

Для этого случая,[4][5] Иерархическая и отказоустойчивая система распределенной общей памяти (DSM) используется для соединения потоков данных между обрабатывающими элементами путем предоставления репозитория с операциями получения / размещения / удаления / выполнения. Исследования AdHoc были сосредоточены на прозрачности, масштабируемости и отказоустойчивости репозитория данных.

Хотя это и не классический каркас каркаса, в том смысле, что каркасы не предусмотрены, общий модуль ASSIST пармод может быть преобразован в классические скелеты, такие как: ферма, картаи т.д. ASSIST также поддерживает автономное управление пармоды, и может быть предметом контракта на производительность путем динамической адаптации количества используемых ресурсов.

CO2P3S

CO2P3S (Правильная объектно-ориентированная система параллельного программирования на основе шаблонов) - это среда разработки, ориентированная на шаблоны,[6] который обеспечивает параллелизм с использованием потоков в Java.

CO2P3S занимается полным процессом разработки параллельного приложения. Программисты взаимодействуют через графический интерфейс программирования, чтобы выбрать шаблон и его параметры конфигурации. Затем программисты заполняют крючки, необходимые для шаблона, и новый код генерируется как каркас на Java для параллельного выполнения приложения. Сгенерированная структура использует три уровня в порядке убывания абстракции: уровень шаблонов, уровень промежуточного кода и уровень собственного кода. Таким образом, опытные программисты могут вмешиваться в сгенерированный код на нескольких уровнях, чтобы настроить производительность своих приложений. Сгенерированный код в основном безопасен по типу, используя типы, предоставленные программистом, которые не требуют расширения суперкласса, но не могут быть полностью типобезопасными, например, в методе reduce (..., Object reducer) в шаблоне сетки.

Набор шаблонов, поддерживаемых в CO2P3S, соответствует последовательности методов, распределителю, сетке и волновому фронту. Сложные приложения можно создавать, составляя фреймворки с их объектными ссылками. Тем не менее, если ни один шаблон не подходит, графический инструмент MetaCO2P3S решает проблему расширяемости, позволяя программистам изменять шаблоны шаблонов и вводить новые шаблоны в CO2P3S.

Поддержка архитектур с распределенной памятью в CO2P3S была представлена ​​позже.[7] Чтобы использовать шаблон распределенной памяти, программисты должны изменить опцию памяти шаблона с разделяемой на распределенную и сгенерировать новый код. С точки зрения использования версия кода с распределенной памятью требует управления удаленными исключениями.

Кальций и скандий

Кальций во многом вдохновлен литием и мускелем. Таким образом, он обеспечивает программирование алгоритмического скелета в виде библиотеки Java. Параллельные скелеты задач и данных являются полностью вложенными; и создаются с помощью параметрических скелетных объектов, а не наследования.

Кальций поддерживает выполнение скелетных приложений поверх ProActive среда для распределенного кластера как инфраструктура. Кроме того, у Calcium есть три отличительные особенности для алгоритмического программирования скелетов. Во-первых, модель настройки производительности, которая помогает программистам идентифицировать код, ответственный за ошибки производительности.[8] Во-вторых, система типов для вложенных скелетов, которая, как было доказано, гарантирует свойства редукции субъектов и реализована с использованием Java Generics.[9] В-третьих, прозрачная алгоритмическая скелетная модель доступа к файлам, которая позволяет создавать скелеты для приложений, интенсивно использующих данные.[10]

Скандий это полная переработка Кальций для многоядерных вычислений. Программы, написанные на Скандий может использовать разделяемую память для упрощения параллельного программирования.[11]

Eden

Eden[12] - это язык параллельного программирования для сред с распределенной памятью, расширяющий Haskell. Процессы определены явно для достижения параллельного программирования, а их взаимодействие остается неявным. Процессы обмениваются данными через однонаправленные каналы, которые соединяют одного писателя ровно с одним считывателем. Программистам нужно только указать, от каких данных зависит процесс. Модель процесса Eden обеспечивает прямой контроль над детализацией процесса, распределением данных и топологией связи.

Eden не является языком скелетов в том смысле, что скелеты не предоставляются как языковые конструкции. Вместо этого скелеты определяются поверх абстракции процессов нижнего уровня Eden, поддерживая параллелизм задач и данных. Таким образом, в отличие от большинства других подходов, Eden позволяет определять скелеты на том же языке и на том же уровне, создание экземпляра скелета записывается: сам Eden. Поскольку Eden является расширением функционального языка, скелеты Eden функции высшего порядка. Иден вводит концепцию каркаса реализации, который представляет собой архитектурно-независимую схему, описывающую параллельную реализацию алгоритмического каркаса.

eSkel

В Эдинбургская библиотека скелетов (eSkel) предоставляется на C и работает поверх MPI. Первая версия eSkel описывалась в[13] в то время как более поздняя версия представлена ​​в.[14]

В,[15] Для скелетов определены режимы вложения и взаимодействия. Режим вложения может быть временным или постоянным, а режим взаимодействия может быть неявным или явным. Временное вложение означает, что вложенный скелет создается для каждого вызова и впоследствии уничтожается, в то время как постоянный означает, что экземпляр создается один раз, и один и тот же экземпляр скелета будет вызываться во всем приложении. Неявное взаимодействие означает, что поток данных между скелетами полностью определяется композицией скелета, а явное означает, что данные могут быть сгенерированы или удалены из потока способом, не указанным композицией скелета. Например, скелет, который производит вывод, не получая ввода, имеет явное взаимодействие.

Прогнозирование производительности для планирования и отображения ресурсов, в основном для трубопроводов, было исследовано Benoit et al.[16][17][18][19] Они предоставили модель производительности для каждого сопоставления, основанную на алгебре процессов, и определили лучшую стратегию планирования на основе результатов модели.

Более поздние работы были посвящены проблеме адаптации к структурному параллельному программированию,[20] в частности, для каркаса трубы.[21][22]

FastFlow

FastFlow представляет собой базовую структуру параллельного программирования, специально предназначенную для разработки потоковых приложений и приложений для параллельных данных. Первоначально разрабатывается для многоядерный платформ, он был последовательно расширен на целевые гетерогенные платформы, состоящие из кластеров платформ с общей памятью,[23][24] возможно оснащенный ускорителями вычислений, такими как NVidia GPGPU, Xeon Phi, Tilera TILE64. Основная философия дизайна FastFlow заключается в том, чтобы предоставить разработчикам приложений ключевые функции для параллельного программирования (например, время выхода на рынок, переносимость, эффективность и производительность) с помощью подходящих абстракций параллельного программирования и тщательно разработанной поддержки во время выполнения.[25] FastFlow это универсальная среда программирования на C ++ для гетерогенных параллельных платформ. Как и другие среды программирования высокого уровня, такие как Intel TBB и OpenMP, он упрощает проектирование и разработку переносимых параллельных приложений. Однако он имеет явное преимущество с точки зрения выразительности и производительности по сравнению с другими средами параллельного программирования в конкретных сценариях приложений, включая, среди прочего: мелкозернистый параллелизм на платформах с общей памятью, согласованной с кешем; потоковые приложения; совместное использование многоядерных процессоров и ускорителей, в остальных случаях FastFlow обычно сопоставимо (а в некоторых случаях немного быстрее) с современными средами параллельного программирования, такими как Intel TBB, OpenMP, Cilk и т. д.[26]

HDC

Разделяй и властвуй высшего порядка (HDC)[27] это подмножество функционального языка Haskell. Функциональные программы представлены как полиморфные функции высшего порядка, которые могут быть скомпилированы в C / MPI и связаны с каркасными реализациями. Язык ориентирован на парадигму «разделяй и властвуй», и, исходя из общего каркаса «разделяй и властвуй», выводятся более конкретные случаи с эффективными реализациями. Конкретные случаи соответствуют: фиксированной глубине рекурсии, постоянной степени рекурсии, многоблочной рекурсии, поэлементным операциям и соответствующей связи.[28]

HDC уделяет особое внимание гранулярности подзадачи и ее связи с количеством доступных процессоров. Общее количество процессоров является ключевым параметром для производительности программы-скелета, поскольку HDC стремится оценить адекватное назначение процессоров для каждой части программы. Таким образом, производительность приложения сильно зависит от предполагаемого количества процессоров, что приводит либо к превышению количества подзадач, либо к недостаточному параллелизму для использования доступных процессоров.

HOC-SA

HOC-SA - это Проект Глобус Инкубатор.
HOC-SA расшифровывается как «Компоненты высшего порядка - Сервисная Архитектура».HOC ) имеют целью упростить разработку Grid-приложений.
Цель HOC-SA - предоставить пользователям Globus, которые не хотят знать обо всех деталях промежуточного программного обеспечения Globus (документы GRAM RSL, веб-службы, конфигурация ресурсов и т. Д.), HOC, которые обеспечивают интерфейс более высокого уровня для Грид, чем основной Globus Toolkit.
HOC - это скелеты с поддержкой Grid, реализованные в виде компонентов поверх Globus Toolkit с удаленным доступом через веб-службы.[29]

JaSkel

JaSkel[30] представляет собой каркасную структуру на основе Java, предоставляющую такие каркасы, как ферма, канал и сердцебиение. Скелеты специализируются на наследовании. Программисты реализуют абстрактные методы для каждого скелета, чтобы предоставить свой специфичный для приложения код. Скелеты в JaSkel доступны как в последовательной, так и в параллельной и динамической версиях. Например, параллельная ферма может использоваться в средах с общей памятью (потоках), но не в распределенных средах (кластерах), где должна использоваться распределенная ферма. Чтобы перейти от одной версии к другой, программисты должны изменить сигнатуру своих классов для наследования от другого скелета. Вложение скелетов использует базовый класс Java Object, и поэтому во время композиции скелета система типов не применяется.

Аспекты распределения вычислений обрабатываются в JaSkel с использованием АОП, а точнее реализации AspectJ. Таким образом, JaSkel могут быть развернуты как в кластерных, так и в грид-подобных инфраструктурах.[31] Тем не менее недостатком JaSkel подход состоит в том, что вложение каркаса строго связано с инфраструктурой развертывания. Таким образом, двойное вложение фермы дает лучшую производительность, чем одиночная ферма в иерархической инфраструктуре. Это лишает смысла использование АОП для разделения распределения и функциональных проблем скелетной программы.

Литий и мускель

Литий[32][33][34] и его преемник Маскель каркасы, разработанные в Пизанском университете, Италия. Оба они предоставляют программисту вложенные скелеты в виде библиотек Java. Оценка скелетного приложения следует формальному определению операционной семантики, введенному Алдинуччи и Данелутто,[35][36] который может обрабатывать как задачи, так и параллелизм данных. Семантика описывает как функциональное, так и параллельное поведение скелетного языка с использованием помеченной системы переходов. Кроме того, применяется несколько оптимизаций производительности, таких как: методы перезаписи скелета [18, 10], упреждающий просмотр задач и отложенное связывание между серверами.[37]

На уровне реализации Lithium использует поток макроданных.[38][39] для достижения параллелизма. Когда входной поток получает новый параметр, скелетная программа обрабатывается для получения графа потока макроданных. Узлы графа - это инструкции потока макроданных (MDFi), которые представляют собой последовательные фрагменты кода, предоставленные программистом. Задачи используются для группировки нескольких MDFi и потребляются простаивающими элементами обработки из пула задач. Когда вычисление графика завершено, результат помещается в выходной поток и, таким образом, доставляется обратно пользователю.

Маскель также предоставляет нефункциональные функции, такие как качество обслуживания (QoS);[40] безопасность между пулом задач и интерпретаторами;[41][42] обнаружение ресурсов, балансировка нагрузки и отказоустойчивость при взаимодействии с Java / Jini Parallel Framework (JJPF),[43] структура распределенного исполнения. Маскель также обеспечивает поддержку для сочетания структурированного и неструктурированного программирования[44] и недавние исследования касались расширяемости.[45]

Mallba

Mallba[46] - это библиотека комбинаторных оптимизаций, поддерживающая точные, эвристические и гибридные стратегии поиска.[47] Каждая стратегия реализована в Mallba как общий каркас, который можно использовать, предоставив необходимый код. По точным алгоритмам поиска Mallba предоставляет скелеты ветвей и границ и динамической оптимизации. Для эвристики локального поиска Mallba поддерживает: скалолазание, мегаполис, имитация отжига, и табу поиск; а также эвристика на основе популяции, полученная из эволюционные алгоритмы Такие как генетические алгоритмы, стратегия эволюции и другие (CHC). Гибридные скелеты сочетают в себе стратегии, такие как: GASA, смесь генетического алгоритма и моделируемого отжига, и CHCCES, который объединяет CHC и ES.

Скелеты предоставляются в виде библиотеки C ++ и не являются вложенными, но безопасны по типу. Используется настраиваемый уровень абстракции MPI, NetStream, который заботится о маршалинге примитивных типов данных, синхронизации и т. Д. Каркас может иметь несколько параллельных реализаций нижнего уровня в зависимости от целевой архитектуры: последовательная, LAN и WAN. Например: централизованный главный-подчиненный, распределенный главный-подчиненный и т. Д.

Mallba также предоставляет переменные состояния, которые содержат состояние каркаса поиска. Состояние связывает поиск с окружающей средой и может быть доступно для проверки эволюции поиска и принятия решения о дальнейших действиях. Например, состояние может использоваться для хранения лучшего решения, найденного на данный момент, или значений α, β для обрезки ветвей и границ.[48]

По сравнению с другими фреймворками, использование концепции скелетов Маллба уникально. Скелеты предоставляются как стратегии параметрического поиска, а не как шаблоны параметрического распараллеливания.

Костный мозг

Костный мозг[49][50] представляет собой структуру алгоритмического каркаса C ++ для оркестровки OpenCL вычислений в, возможно, неоднородных, многоцелевыхGPU среды. Он предоставляет набор как задач, так и параллельных данных каркасов, которые могут быть скомпонованы посредством вложенности для построения сложных вычислений. Листовые узлы результирующих композиционных деревьев представляют вычислительные ядра графического процессора, а остальные узлы обозначают каркас, применяемый к вложенному поддереву. Платформа берет на себя всю оркестровку на стороне хоста, необходимую для правильного выполнения этих деревьев в гетерогенных средах с несколькими графическими процессорами, включая надлежащий порядок передачи данных и запросов на выполнение, а также необходимую связь между узлами дерева.

Среди наиболее отличительных функций Marrow - набор скелетов, ранее недоступных в контексте графического процессора, таких как конвейер и цикл, и возможность вложения скелетов - функция, также новая в этом контексте. Более того, фреймворк вводит оптимизацию, которая перекрывает коммуникацию и вычисления, тем самым маскируя задержку, налагаемую PCIe автобус.

Параллельное выполнение дерева композиции Marrow несколькими графическими процессорами следует стратегии параллельной декомпозиции данных, которая одновременно применяет все вычислительное дерево к различным разделам входного набора данных. Помимо указания того, какие параметры ядра могут быть разложены, и, при необходимости, определения того, как должны быть объединены частичные результаты, программист полностью абстрагируется от базовой архитектуры с несколькими GPU.

Более подробную информацию, а также исходный код можно найти на сайте Сайт костного мозга

Мюсли

Библиотека скелетов Мюнстера Мюсли[51][52] - это библиотека шаблонов C ++, которая повторно реализует многие идеи и концепции, представленные в Skil, например функции высшего порядка, каррирование и полиморфные типы [1]. Он построен поверх MPI 1.2 и OpenMP 2.5 и поддерживает, в отличие от многих других скелетных библиотек, параллельные скелеты задач и данных. Вложение (композиция) скелета аналогично двухуровневому подходу P3L, т.е. параллельные скелеты задач могут быть вложены произвольно, в то время как параллельные скелеты данных не могут, но могут использоваться на листьях дерева параллельного вложения задач.[53] Шаблоны C ++ используются для визуализации полиморфных скелетов, но система типов не применяется. Однако в библиотеке реализован механизм автоматической сериализации, вдохновленный[54] таким образом, в дополнение к стандартным типам данных MPI в каркасах могут использоваться произвольные типы данных, определенные пользователем. Поддерживаемые параллельные скелеты задач[55] являются Branch & Bound,[56] Разделяй и властвуй,[57][58] Ферма[59][60] и Pipe, вспомогательными каркасами являются Filter, Final и Initial. Параллельные скелеты данных, такие как сворачивание (сокращение), отображение, перестановка, zip и их варианты, реализованы как функции-члены более высокого порядка в распределенной структуре данных. В настоящее время Muesli поддерживает распределенные структуры данных для массивов, матриц и разреженных матриц.[61]

В качестве уникальной особенности параллельные скелеты данных Muesli автоматически масштабируются как на одноядерных, так и на многоядерных многоузловых кластерных архитектурах.[62][63] Здесь масштабируемость между узлами и ядрами обеспечивается одновременным использованием MPI и OpenMP соответственно. Однако эта функция является необязательной в том смысле, что программа, написанная с помощью Muesli, по-прежнему компилируется и запускается на одноядерном многоузловом кластерном компьютере без изменений исходного кода, т.е. обратная совместимость гарантирована. Это обеспечивается за счет предоставления очень тонкого уровня абстракции OpenMP, так что поддержку многоядерных архитектур можно включать / выключать, просто предоставляя / опуская флаг компилятора OpenMP при компиляции программы. Таким образом, во время выполнения практически не возникают накладные расходы.

P3L, SkIE, SKElib

P3L[64] (Pisa Parallel Programming Language) - это скелетный координационный язык. P3L предоставляет скелетные конструкции, которые используются для координации параллельного или последовательного выполнения кода C. Компилятор с именем Anacleto[65] предоставляется для языка. Anacleto использует шаблоны реализации для компиляции кода P3 L в целевую архитектуру. Таким образом, у скелета может быть несколько шаблонов, каждый из которых оптимизирован для своей архитектуры. Шаблон реализует каркас конкретной архитектуры и предоставляет параметрический граф процесса с моделью производительности. Затем модель производительности можно использовать для принятия решения о преобразованиях программы, которые могут привести к оптимизации производительности.[66]

А P3L module соответствует правильно определенной конструкции скелета с входными и выходными потоками и другими субмодулями или последовательным кодом C. Модули могут быть вложены с использованием двухуровневой модели, где внешний уровень состоит из параллельных каркасов задач, а параллельные каркасы данных могут использоваться на внутреннем уровне [64]. Проверка типа выполняется на уровне потока данных, когда программист явно указывает тип входного и выходного потоков и путем указания потока данных между субмодулями.

SkIE[67] (Интегрированная среда на основе скелетов) очень похожа на P3L, поскольку он также основан на языке координации, но предоставляет расширенные функции, такие как инструменты отладки, анализ производительности, визуализацию и графический пользовательский интерфейс. Вместо прямого использования координационного языка программисты взаимодействуют с графическим инструментом, в котором можно составлять параллельные модули на основе скелетов.

SKELib[68] опирается на вклад P3L и SkIE наследуя, среди прочего, систему шаблонов. Он отличается от них, потому что язык координации больше не используется, а вместо этого скелеты предоставляются в виде библиотеки на C, с производительностью, аналогичной той, которая была достигнута в P3L. Вопреки Skil, другой C-подобный каркас, безопасность типов не рассматривается в SKELib.

PAS и EPAS

PAS (Parallel Architectural Skeletons) - это фреймворк для программирования скелетов, разработанный на C ++ и MPI.[69][70] Программисты используют расширение C ++ для написания своих скелетных приложений1. Затем код передается через сценарий Perl, который расширяет код до чистого C ++, где скелеты специализируются посредством наследования.

В PAS, у каждого скелета есть Представитель (Rep) объект, который должен быть предоставлен программистом и отвечает за координацию выполнения скелета. Скелеты могут быть вложены иерархически через объекты Rep. Помимо выполнения скелета, Rep также явно управляет приемом данных от скелета более высокого уровня и отправкой данных субскелетам. Параметризованный протокол связи / синхронизации используется для отправки и получения данных между родительскими и субскелетами.

Расширение PAS, обозначенное как SuperPas[71] а позже как EPAS[72] решает проблемы расширяемости скелета. С EPAS инструмент, можно добавить новые скелеты PAS. Язык описания каркаса (SDL) используется для описания шаблона каркаса путем определения топологии по отношению к сетке виртуального процессора. Затем SDL можно скомпилировать в собственный код C ++, который можно использовать как любой другой скелет.

SBASCO

SBASCO (Компоненты Skeleton-BAsed Scientific) - это среда программирования, ориентированная на эффективную разработку параллельных и распределенных числовых приложений.[73] SBASCO направлена ​​на интеграцию двух моделей программирования: скелетов и компонентов с настраиваемым языком композиции. Представление компонента в приложении предоставляет описание его интерфейсов (тип ввода и вывода); в то время как представление конфигурации предоставляет, кроме того, описание внутренней структуры компонента и схемы процессора. Внутреннюю структуру компонента можно определить с помощью трех каркасов: фермы, канала и мультиблока.

SBASCO 's обращается к разлагаемым приложениям домена через свой многоблочный каркас. Домены задаются посредством массивов (в основном двумерных), которые разбиваются на подмассивы с возможными перекрывающимися границами. Затем вычисление происходит итеративным способом, подобным BSP. Первый этап состоит из локальных вычислений, а второй этап выполняет обмен границами. Представлен вариант использования для задачи реакции-диффузии в.[74]

Представлены два типа компонентов.[75] Научные компоненты (SC), которые обеспечивают функциональный код; и Компоненты аспекта связи (CAC), которые инкапсулируют нефункциональное поведение, такое как связь, компоновка процессора распределения и репликация. Например, компоненты SC подключаются к компоненту CAC, который может действовать как менеджер во время выполнения, динамически переназначая процессоры, назначенные SC. Пример использования, демонстрирующий повышение производительности при использовании компонентов CAC, показан в.[76]

SCL

В Структурированный язык координации (SCL)[77] был одним из первых языков программирования-скелетов. Он обеспечивает подход на языке координации для программирования скелетов программных компонентов. SCL считается базовым языком и был разработан для интеграции с основным языком, например Fortran или C, используемым для разработки последовательных программных компонентов. В SCL, скелеты делятся на три типа: конфигурация, элементарный и вычисление. Скелеты конфигурации - абстрактные шаблоны для часто используемых структур данных, таких как распределенные массивы (ParArray). Элементарные скелеты соответствуют параллельным каркасам данных, таким как карта, сканирование и складывание. Каркасы вычислений, которые абстрагируют поток управления и соответствуют в основном параллельным каркасам задач, таким как farm, SPMD и iterateUntil. Подход на языке координации использовался в сочетании с моделями производительности для программирования традиционных параллельных машин, а также параллельных разнородных машин, которые имеют несколько ядер на каждом узле обработки.[78]

SkePU

SkePU[79] SkePU - это каркасная среда программирования для многоядерных процессоров и систем с несколькими графическими процессорами. Это библиотека шаблонов C ++ с шестью каркасами параллельных данных и одной параллельной задачам, двумя типами контейнеров и поддержкой выполнения в системах с несколькими графическими процессорами как с CUDA, так и с OpenCL. Недавно в SkePU была разработана поддержка гибридного выполнения, динамического планирования с учетом производительности и балансировки нагрузки за счет реализации бэкэнда для системы времени выполнения StarPU. SkePU расширяется для кластеров GPU.

ЛЫЖИ И КВАФФ

СКИППЕР это библиотека скелетов, специфичная для домена, для приложений машинного зрения[80] который предоставляет скелеты в CAML и, таким образом, полагается на CAML для обеспечения безопасности типов. Скелеты представлены двумя способами: декларативным и операционным. Декларативные скелеты используются программистами напрямую, а их операционные версии обеспечивают целевую реализацию для конкретной архитектуры. Из среды выполнения, спецификаций каркаса CAML и специфических функций приложения (предоставленных программистом на C) новый код C генерируется и компилируется для запуска приложения в целевой архитектуре. Одна из интересных вещей о СКИППЕР заключается в том, что скелетная программа может выполняться последовательно для отладки.

Различные подходы были исследованы в СКИППЕР для написания операционных скелетов: статических графов потоков данных, параметрических сетей процессов, иерархических графов задач и графов потоков данных с тегами.[81]

QUAFF[82] - это более поздняя скелетная библиотека, написанная на C ++ и MPI. QUAFF полагается на методы метапрограммирования на основе шаблонов для уменьшения накладных расходов времени выполнения и выполнения расширений и оптимизаций скелета во время компиляции. Скелеты могут быть вложенными, а последовательные функции сохраняют состояние. Помимо проверки типов, QUAFF использует шаблоны C ++ для генерации во время компиляции нового кода C / MPI. QUAFF основан на CSP-модели, где скелетная программа описывается как технологическая сеть и производственные правила (одиночные, последовательные, номинальные, объединенные).[83]

SkeTo

В SkeTo[84] project - это библиотека C ++, которая обеспечивает распараллеливание с использованием MPI. SkeTo отличается от других скелетных библиотек, потому что вместо обеспечения вложенных шаблонов параллелизма SkeTo предоставляет параллельные скелеты для параллельных структур данных, таких как: списки, деревья,[85][86] и матрицы.[87] Структуры данных набираются с использованием шаблонов, и с ними можно вызывать несколько параллельных операций. Например, структура списка обеспечивает параллельные операции, такие как: сопоставление, уменьшение, сканирование, архивирование, сдвиг и т. Д.

Дополнительные исследования по SkeTo также были сосредоточены на стратегиях оптимизации путем преобразования, а в последнее время - на оптимизации для конкретных областей.[88] Например, SkeTo обеспечивает трансформацию слияния[89] который объединяет два последовательных вызова функций в один, тем самым уменьшая накладные расходы на вызов функций и избегая создания промежуточных структур данных, передаваемых между функциями.

Skil

Skil[90] является императивным языком для программирования скелетов. Скелеты не являются непосредственно частью языка, но реализуются вместе с ним. Skil использует подмножество языка C, которое предоставляет такие функциональные возможности языка, как функции высшего порядка, curring и полиморфные типы. Когда Skil компилируется, такие возможности удаляются и создается обычный код C. Таким образом, Skil преобразует полиморфные функции высокого порядка в мономорфные C-функции первого порядка. Skil не поддерживает гнездовой состав скелетов. Параллелизм данных достигается за счет использования определенных параллельных структур данных, например, для распределения массивов между доступными процессорами. Можно использовать каркасы фильтров.

Каркас скелета STAPL

В Каркас скелета STAPL [91][92] скелеты определяются как параметрические графы потоков данных, что позволяет им масштабироваться за пределы 100 000 ядер. Кроме того, эта структура рассматривает композицию скелетов как двухточечную композицию соответствующих графов потока данных через понятие портов, что позволяет легко добавлять новые скелеты в структуру. В результате эта структура устраняет необходимость в повторной реализации и глобальной синхронизации в составных каркасах. Каркас скелета STAPL поддерживает вложенную композицию и может переключаться между параллельным и последовательным выполнением на каждом уровне вложенности. Эта структура выигрывает от масштабируемой реализации параллельных контейнеров STAPL.[93] и может запускать скелеты в различных контейнерах, включая векторы, многомерные массивы и списки.

T4P

T4P была одной из первых систем, представленных для программирования скелетов.[94] Система в значительной степени полагалась на свойства функционального программирования, и пять скелетов были определены как функции более высокого порядка: разделяй и властвуй, ферма, карта, труба и RaMP. Программа может иметь более одной реализации, каждая из которых использует комбинацию различных скелетов. Более того, каждый каркас может иметь разные параллельные реализации. Для выбора наиболее подходящего каркаса, который будет использоваться для программы, а также наиболее подходящей реализации каркаса, использовалась методология, основанная на функциональных преобразованиях программы, управляемая моделями производительности каркасов.[95]

Сравнение фреймворков

  • Годы деятельности - известный период деятельности в годах. Даты, представленные в этом столбце, соответствуют дате первой и последней публикации соответствующей статьи в научном журнале или материалах конференции. Обратите внимание, что проект может все еще быть активным за пределами периода активности, и что нам не удалось найти для него публикацию после указанной даты.
  • Язык программирования это интерфейс, с которым программисты взаимодействуют, чтобы кодировать свои скелетные приложения. Эти языки разнообразны и охватывают такие парадигмы, как: функциональные языки, языки координации, языки разметки, императивные языки, объектно-ориентированные языки и даже графические пользовательские интерфейсы. Внутри языка программирования скелеты представлены либо в виде языковых конструкций, либо в виде библиотек. Предоставление скелетов в качестве языковых конструкций подразумевает разработку языка, специфичного для пользовательской области, и его компилятора. Это была явно более сильная тенденция в начале исследования скелетов. В последнее время появилась тенденция предоставлять скелеты в виде библиотек, в частности, для объектно-ориентированных языков, таких как C ++ и Java.
  • Язык исполнения это язык, на котором скелетные приложения выполняются или компилируются. Очень рано было признано, что языки программирования (особенно в функциональных случаях) недостаточно эффективны для выполнения скелетных программ. Поэтому скелетные языки программирования были упрощены за счет выполнения скелетного приложения на других языках. Процессы преобразования были введены для преобразования скелетных приложений (определенных на языке программирования) в эквивалентное приложение на целевом языке выполнения. Были введены различные процессы преобразования, такие как генерация кода или создание экземпляров скелетов нижнего уровня (иногда называемых рабочими скелетами), которые были способны взаимодействовать с библиотекой на языке исполнения. Преобразованное приложение также дало возможность ввести код целевой архитектуры, настроенный для обеспечения производительности, в преобразованное приложение. Таблица 1 показывает, что фаворитом для языка исполнения был язык C.
  • Библиотека распространения предоставляет функциональные возможности для выполнения параллельных / распределенных вычислений. Большим фаворитом в этом смысле был MPI, что неудивительно, поскольку он хорошо интегрируется с языком C и, вероятно, является наиболее часто используемым инструментом для параллелизма в кластерных вычислениях. Опасности прямого программирования с помощью библиотеки распространения, конечно, надежно скрыты от программистов, которые никогда не взаимодействуют с библиотекой распространения. В последнее время появилась тенденция к разработке каркасных структур, способных взаимодействовать с более чем одной библиотекой распространения. Например, CO2 P3 S может использовать резьбу, RMI или сокеты; Маллба может использовать Netstream или MPI; или JaSkel, который использует AspectJ для выполнения скелетных приложений на различных скелетных платформах.
  • Безопасность типов относится к возможности обнаружения ошибок несовместимости типов в скелетной программе. Поскольку первые каркасные фреймворки были построены на таких функциональных языках, как Haskell, безопасность типов просто унаследовалась от основного языка. Тем не менее, поскольку для программирования скелетов разрабатывались собственные языки, пришлось писать компиляторы, учитывающие проверку типов; что было не так сложно, поскольку вложение скелетов не поддерживалось полностью. Однако недавно, когда мы начали размещать каркасные структуры на объектно-ориентированных языках с полной вложенностью, проблема безопасности типов снова возникла. К сожалению, проверка типов в основном игнорировалась (за исключением QUAFF), особенно в каркасных каркасах на основе Java.
  • Вложение скелетов возможность иерархической композиции скелетных узоров. Вложенность скелетов с самого начала была определена как важная функция в программировании скелетов, поскольку она позволяет создавать более сложные шаблоны, начиная с базового набора более простых шаблонов. Тем не менее, сообществу потребовалось много времени, чтобы полностью поддержать произвольное вложение скелетов, в основном из-за трудностей планирования и проверки типов. Тенденция очевидна, что последние каркасы скелетов поддерживают полное вложение скелетов.
  • Доступ к файлам это возможность доступа и управления файлами из приложения. В прошлом скелетное программирование оказалось полезным в основном для приложений с интенсивными вычислениями, где небольшие объемы данных требуют большого количества времени вычислений. Тем не менее, многие распределенные приложения требуют или производят большие объемы данных во время вычислений. Это касается астрофизики, физики элементарных частиц, биоинформатики и т. Д. Таким образом, обеспечение поддержки передачи файлов, которая интегрируется с программированием скелетов, является ключевой задачей, которой в большинстве случаев не уделялось должного внимания.
  • Набор скелетов это список поддерживаемых шаблонов скелета. Наборы скелетов сильно различаются от одного фреймворка к другому, и, что более шокирует, некоторые скелеты с одним и тем же именем имеют разную семантику в разных фреймворках. Наиболее распространенными образцами скелетов в литературе, вероятно, являются ферма, трубка и карта.
Необъектно-ориентированные алгоритмические каркасы
Годы деятельностиЯзык программированияЯзык исполненияБиблиотека распространенияТип безопасныйВложение скелетовДоступ к файламНабор скелетов
ПОМОЩЬ2004–2007Пользовательский язык управленияC ++TCP / IP + ssh / scpдаНетявныйseq, parmod
SBSACO2004–2006Пользовательский язык композицииC ++MPIдадаНетферма, труба, многоблочная
eSkel2004–2005CCMPIНет?Неттрубопровод, ферма, сделка, бабочка, hallowSwap
HDC2004–2005Подмножество HaskellCMPIда?НетdcA, dcB, dcD, dcE, dcF, карта, красный цвет, сканирование, фильтр
SKELib2000-2000CCMPIНетНетНетферма, труба
SkiPPER1999–2002CAMLCSynDexдаограниченоНетscm, df, tf, intermem
SkIE1999-1999GUI / пользовательский язык управленияC ++MPIдаограниченоНеттруба, ферма, карта, сокращение, петля
Eden1997–2011Расширение HaskellHaskellPVM / MPIдадаНеткарта, ферма, рабочий бассейн, номер, постоянный ток, труба, iterUntil, тор, кольцо
P3L1995–1998Пользовательский язык управленияCMPIдаограниченоНеткарта, сокращение, сканирование, комп, конвейер, ферма, последовательность, цикл
Skil1995–1998Подмножество CC?даНетНетпардата, карта, складка
SCL1994–1999Пользовательский язык управленияФортран / CMPIдаограниченоНеткарта, сканирование, складывание, ферма, SPMD, iterateUntil
T4P1990–1994Надежда +Надежда +CSToolsдаограниченоНетD&C (разделяй и властвуй), Map, Pipe, RaMP
Объектно-ориентированные алгоритмические каркасы
Годы деятельностиЯзык программированияЯзык исполненияБиблиотека распространенияТип безопасныйВложение скелетовДоступ к файламНабор скелетов
Скандий2009–2012ЯваЯваПотокидадаНетseq, pipe, farm, for, while, map, d & c, вилка
FastFlow2009–C ++С ++ 11 / CUDA / OpenCLПотоки C ++ 11 / потоки Posix / TCP-IP / OFED-IB / CUDA / OpenCLдададаКонвейер, Ферма, ParallelFor, ParallelForReduce, MapReduce, StencilReduce, PoolEvolution, MacroDataFlow
Кальций2006–2008ЯваЯваProActiveдададаseq, pipe, farm, for, while, map, d & c, вилка
QUAFF2006–2007C ++CMPIдадаНетseq, pipe, farm, scm, пардо
JaSkel2006–2007ЯваJava / AspectJMPP / RMIНетдаНетферма, трубопровод, сердцебиение
Маскель2005–2008ЯваЯваRMIНетдаНетферма, труба, последовательность, + пользовательские графики МДФ
HOC-SA2004–2008ЯваЯваГлобус, КОАЛАНетНетНетферма, трубопровод, волновой фронт
SkeTo2003–2013C ++C ++MPIдаНетНетсписок, матрица, дерево
Mallba2002–2007C ++C ++NetStream / MPIдаНетНетточный, эвристический, гибридный
Костный мозг2013–C ++C ++ плюс OpenCL(никто)НетдаНетпараллельные данные: карта, карта-сокращение. параллельная задача: конвейер, цикл, для
Мюсли2002–2013C ++C ++MPI / OpenMPдадаНетпараллельные данные: складывание, карта, перестановка, сканирование, zip и варианты. параллельная задача: ветвь и граница, разделяй и властвуй, фарм, труба. вспомогательные: фильтр, финал, начальный
Alt2002–2003Java / GworkflowDLЯваJava RMIдаНетНеткарта, zip, сокращение, сканирование, dh, репликация, применение, сортировка
(E) PAS1999–2005Расширение C ++C ++MPIНетдаНетсинглтон, репликация, композиционный, конвейер, разделение, параллельные данные
Литий1999–2004ЯваЯваRMIНетдаНеттруба, карта, ферма, уменьшить
CO2P3S1999–2003GUI / JavaJava (сгенерировано)Потоки / RMI / сокетыЧастичноеНетНетметод-последовательность, распределитель, сетка, волновой фронт
STAPL2010–C ++C ++ 11Библиотека времени выполнения STAPL (MPI, OpenMP, PThreads)дададакарта, zip , сокращение, сканирование, ферма, (обратная) бабочка, (обратное) дерево , рекурсивное удвоение, последовательный, транспонирование, трафарет , волновой фронт , allreduce, allgather, собирать, разбрасывать, транслировать

Операторы: compose, repeat, do-while, do-all, do-through

Смотрите также

Рекомендации

  1. ^ К. Хаммонд и Г. Майкельсон, редакторы. «Направления исследований в параллельном функциональном программировании». Springer-Verlag, Лондон, Великобритания, 1999.
  2. ^ Ваннески, М. (2002). «Модель программирования ASSIST, среды для параллельных и распределенных переносимых приложений». Параллельные вычисления. 28 (12): 1709–1732. CiteSeerX  10.1.1.59.5543. Дои:10.1016 / S0167-8191 (02) 00188-6.
  3. ^ М. Алдинуччи, М. Коппола, М. Данелутто, Н. Тонеллотто, М. Ваннески и К. Зокколо. «Программирование высокоуровневой сетки с помощью ASSIST». Вычислительные методы в науке и технике, 12 (1): 21–32, 2006.
  4. ^ М. Алдинуччи и М. Торквати. Ускорение работы ферм Apache с помощью специального распределенного масштабируемого репозитория объектов. В Proc. 10-го Междунар. Параллельная обработка документов Euro-Par 2004, том 3149 LNCS, страницы 596–605. Спрингер, 2004.
  5. ^ Aldinucci, M .; Данелутто, М .; Антониу, G .; Ян, М. (2008). "Отказоустойчивый обмен данными для высокоуровневой сети: иерархическая архитектура хранения". Достижения в европейских исследованиях сетевых систем. п. 67. Дои:10.1007/978-0-387-72812-4_6. ISBN  978-0-387-72811-7.
  6. ^ С. Макдональд, Дж. Анвик, С. Бромлинг, Дж. Шеффер, Д. Шафрон и К. Тан ». «От шаблонов до фреймворков и параллельных программ». Параллельные вычисления, 28 (12): 1663–1683, 2002.
  7. ^ К. Тан, Д. Шафрон, Дж. Шеффер, Дж. Анвик и С. Макдональд. «Использование генеративных шаблонов проектирования для генерации параллельного кода для среды с распределенной памятью». В PPoPP '03: Материалы девятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, страницы 203–215, Нью-Йорк, штат Нью-Йорк, США, 2003. ACM.
  8. ^ Д. Каромель и М. Лейтон. «Тонкая настройка алгоритмических скелетов». На 13-й Международной конференции Euro-Par: Parallel Processing, том 4641 из Lecture Notes in Computer Science, страницы 72–81. Springer-Verlag, 2007.
  9. ^ Д. Каромель, Л. Генрио и М. Лейтон. «Типобезопасные алгоритмические скелеты». В материалах 16-й конференции Euromicro по параллельной, распределенной и сетевой обработке, страницы 45–53, Тулуза, Франция, февраль 2008 г. IEEE CS Press.
  10. ^ Д. Каромель и М. Лейтон. «Прозрачная неинвазивная файловая модель данных для алгоритмических скелетов». На 22-м Международном симпозиуме по параллельной и распределенной обработке (IPDPS), страницы 1–8, Майами, США, март 2008 г. IEEE Computer Society.
  11. ^ Марио Лейтон, Хосе М. Пикер. «Skandium: многоядерное программирование с алгоритмическими каркасами», IEEE Euro-micro PDP 2010.
  12. ^ Рита Лооген и Иоланда Ортега-Маллен и Рикардо Пенья-Мари. «Параллельное функциональное программирование в Eden», Журнал функционального программирования, № 15 (2005), 3, страницы 431–475
  13. ^ Мюррей Коул. «Извлечение скелетов из шкафа: прагматический манифест скелетного параллельного программирования». Параллельные вычисления, 30 (3): 389–406, 2004.
  14. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Гибкое скелетное программирование с помощью eskel». В J. C. Cunha и P. D. Medeiros, редакторы, Euro-Par, том 3648 конспектов лекций по информатике, страницы 761–770. Спрингер, 2005.
  15. ^ А. Бенуа и М. Коул. «Две фундаментальные концепции в скелетном параллельном программировании». В В. Сундерам, Д. ван Альбада, П. Слоот и Дж. Донгарра, редакторах, Международная конференция по вычислительным наукам (ICCS 2005), часть II, LNCS 3515, страницы 764–771. Springer Verlag, 2005.
  16. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. Оценка производительности параллельных программ высокого уровня на основе скелетов. В: М. Бубак, Д. ван Альбада, П. Слот и Дж. Донгарра, редакторы, Международная конференция по вычислительной науке (ICCS 2004), часть III, LNCS 3038, страницы 289–296. Springer Verlag, 2004 г.
  17. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Оценка производительности конвейерных параллельных программ с помощью скелетов и алгебры процессов». Масштабируемые вычисления: практика и опыт, 6 (4): 1–16, декабрь 2005 г.
  18. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Планирование приложений сетки на основе скелета с использованием pepa и nws». Компьютерный журнал, специальный выпуск по моделированию и измерению производительности сети, 48 (3): 369–378, 2005.
  19. ^ А. Бенуа и Ю. Роберт. «Нанесение каркасов трубопроводов на разнородные платформы». В ICCS 2007, 7-я Международная конференция по вычислительным наукам, LNCS 4487, страницы 591–598. Springer Verlag, 2007.
  20. ^ Дж. Яикхом, М. Коул, С. Гилмор и Дж. Хиллстон. «Структурный подход к моделированию производительности систем с использованием каркасов». Электр. Примечания Теор. Comput. Sci., 190 (3): 167–183, 2007.
  21. ^ Х. Гонсалес-Велес и М. Коул. «К полностью адаптивному конвейерному параллелизму для гетерогенных распределенных сред». In Parallel and Distributed Processing and Applications, 4th International Symposium (ISPA), Lecture Notes in Computer Science, pages 916–926. Springer-Verlag, 2006.
  22. ^ Х. Гонсалес-Велес и М. Коул. «Адаптивный структурированный параллелизм для вычислительных сетей». В PPoPP '07: Материалы 12-го симпозиума ACM SIGPLAN по Принципам и практике параллельного программирования, страницы 140–141, Нью-Йорк, Нью-Йорк, США, 2007. ACM.
  23. ^ Aldinucci, M .; Campa, S .; Данелутто, М .; Килпатрик, П .; Торквати, М. (2013). Ориентация на распределенные системы в FastFlow (PDF). Euro-Par 2012: Семинары по параллельной обработке. Конспект лекций по информатике. 7640. п. 47. Дои:10.1007/978-3-642-36949-0_7. ISBN  978-3-642-36948-3.
  24. ^ Aldinucci, M .; Spampinato, C .; Drocco, M .; Torquati, M .; Палаццо, С. (2012). Алгоритм сохранения параллельных краев для шумоподавления изображения солью и перцем. 3-я Международная конференция по теории, инструментам и приложениям обработки изображений (IPTA). п. 97. Дои:10.1109 / IPTA.2012.6469567. HDL:2318/154520.
  25. ^ Aldinucci, M .; Данелутто, М .; Килпатрик, П .; Менегин, М .; Торквати, М. (2012). Эффективная неограниченная очередь без блокировок для многоядерных систем. Euro-Par 2012 Параллельная обработка. Конспект лекций по информатике. 7484. п. 662. Дои:10.1007/978-3-642-32820-6_65. ISBN  978-3-642-32819-0.
  26. ^ Aldinucci, M .; Менегин, М .; Торквати, М. (2010). "Эффективный Смит-Ватерман на многоядерном оборудовании с быстрым Поток". 2010 18-я конференция Euromicro по параллельной, распределенной и сетевой обработке. IEEE. п. 195. CiteSeerX  10.1.1.163.9092. Дои:10.1109 / PDP.2010.93. ISBN  978-1-4244-5672-7.
  27. ^ К. А. Херрманн и К. Ленгауэр. «HDC: язык высшего порядка для разделения и властвования». Письма о параллельной обработке, 10 (2–3): 239–250, 2000.
  28. ^ К. А. Херрманн. Распараллеливание рекурсий "разделяй и властвуй" на основе скелетов. Кандидатская диссертация, 2000 г. ISBN  3-89722-556-5.".
  29. ^ Дж. Дюннвебер, С. Горлач. «Компоненты высшего порядка для программирования грид. Делаем грид более удобным в использовании». Springer-Verlag, 2009. ISBN  978-3-642-00840-5
  30. ^ Дж. Ф. Феррейра, Дж. Л. Собрал и А. Дж. Проенка. «Jaskel: Java-каркас для структурированных кластерных и грид-вычислений». В CCGRID '06: Материалы шестого международного симпозиума IEEE по кластерным вычислениям и сетям, страницы 301–304, Вашингтон, округ Колумбия, США, 2006. IEEE Computer Society.
  31. ^ Дж. Собрал и А. Проенка. «Включение скелетов jaskel для кластеров и вычислительных сетей». В кластере IEEE. IEEE Press, 9 2007.
  32. ^ М. Алдинуччи и М. Данелутто. «Оптимизация параллельного каркаса потока». В Proc. PDCS: Intl. Конференция по параллельным и распределенным вычислениям и системам, страницы 955–962, Кембридж, Массачусетс, США, ноябрь 1999 г. IASTED, ACTA press.
  33. ^ Aldinucci, M .; Данелутто, М .; Тети, П. (2003). «Расширенная среда, поддерживающая структурированное параллельное программирование на Java». Компьютерные системы будущего поколения. 19 (5): 611. CiteSeerX  10.1.1.59.3748. Дои:10.1016 / S0167-739X (02) 00172-3.
  34. ^ М. Данелутто и П. Тети. «Литий: среда структурированного параллельного программирования на Java». В Proc. ICCS: Международная конференция по вычислительным наукам, том 2330 LNCS, страницы 844–853. Springer Verlag, апрель 2002 г.
  35. ^ М. Алдинуччи и М. Данелутто. «Операционная семантика для скелетов». В: GR Joubert, WE Nagel, FJ Peters и WV Walter, редакторы, Parallel Computing: Software Technology, Algorithms, Architectures and Applications, PARCO 2003, volume 13 of Advances inParallel Computing, страницы 63–70, Дрезден, Германия, 2004. Elsevier .
  36. ^ Aldinucci, M .; Данелутто, М. (2007). «Параллельное программирование на основе скелетов: функциональная и параллельная семантика в одном кадре ☆». Компьютерные языки, системы и структуры. 33 (3–4): 179. CiteSeerX  10.1.1.164.368. Дои:10.1016 / j.cl.2006.07.004.
  37. ^ М. Алдинуччи, М. Данелутто и Дж. Дюннвебер. «Методы оптимизации для реализации параллельных скелетов в сетке». В С. Горлаче, редакторе, Proc. компании CMPP: Intl. Семинар по конструктивным методам параллельного программирования, страницы 35–47, Стерлинг, Шотландия, Великобритания, июль 2004 г. Universität Munster, Германия.
  38. ^ М. Данелутто. Эффективная поддержка скелетов в кластерах рабочих станций. Письма о параллельной обработке, 11 (1): 41–56, 2001.
  39. ^ М. Данелутто. «Поддержка динамического времени выполнения для скелетов». Технический отчет, 1999 г.
  40. ^ М. Данелутто. «Qos при параллельном программировании через менеджеры приложений». В PDP '05: Материалы 13-й конференции Euromicro по параллельной, распределенной и сетевой обработке (PDP'05), страницы 282–289, Вашингтон, округ Колумбия, США, 2005. Компьютерное общество IEEE.
  41. ^ М. Алдинуччи и М. Данелутто. «Стоимость безопасности в скелетных системах». В P. D'Ambra и M.R. Guarracino, редакторах, Proc. Intl. Euromicro PDP 2007: Параллельная распределенная и сетевая обработка, страницы 213–220, Неаполь, Италия, февраль 2007 г. IEEE.
  42. ^ М. Алдинуччи и М. Данелутто. «Обеспечение безопасности скелетных систем с ограниченными потерями производительности: опыт мускуса». Журнал системной архитектуры, 2008.
  43. ^ М. Данелутто и П. Дацци. «Среда Java / Jini, поддерживающая потоковые параллельные вычисления». В Proc. Intl. PARCO 2005: Параллельные вычисления, сентябрь 2005 г.
  44. ^ М. Данелутто и П. Дацци. «Совместное использование структурированного / неструктурированного параллелизма через поток данных». В В. Александров, Д. ван Альбада, П. Слоот и Дж. Донгарра, редакторы, Proc. ICCS: Международная конференция по вычислительной науке, семинар по практическим аспектам параллельного программирования высокого уровня, LNCS, Рединг, Великобритания, май 2006 г. Springer Verlag.
  45. ^ М. Алдинуччи, М. Данелутто и П. Дацци. «Маскел: расширяемая среда скелета». Масштабируемые вычисления: практика и опыт, 8 (4): 325–341, декабрь 2007 г.
  46. ^ Э. Альба, Ф. Алмейда, М. Дж. Блеса, Дж. Кабеза, К. Котта, М. Диас, И. Дорта, Дж. Габарро, К. Леон, Дж. Луна, Л. М. Морено, К. Паблос, Дж. Пети, А. Рохас, Ф. Ксафа. "Mallba: библиотека скелетов для комбинаторной оптимизации (исследовательская заметка). »In Euro-Par '02: Proceedings of 8th International Euro-Par Conference on Parallel Processing, страницы 927–932, Лондон, Великобритания, 2002. Springer-Verlag.
  47. ^ Э. Альба, Ф. Алмейда, М. Блеса, К. Котта, М. Диас, И. Дорта, Х. Габарро, К. Леон, Г. Луке, Х. Пети, К. Родригес, А. Рохас и Ф. .Xhafa. Эффективные параллельные алгоритмы LAN / WAN для оптимизации: проект mallba. Параллельные вычисления, 32 (5): 415–440, 2006.
  48. ^ Э. Альба, Дж. Луке, Х. Гарсия-Ньето, Дж. Ордонез и Дж. Легуисамон. «Mallba - программная библиотека для разработки эффективных алгоритмов оптимизации». Международный журнал инновационных вычислений и приложений, 1 (1): 74–85, 2007.
  49. ^ «Рикардо Маркес, Эрве Паулино, Фернандо Александр, Педро Д. Медейрос». «Алгоритмический каркас для оркестровки вычислений на GPU». Euro-Par 2013: 874–885
  50. ^ «Фернандо Александр, Рикардо Маркес, Эрве Паулино». «О поддержке задач-параллельных алгоритмических скелетов для вычислений с несколькими GPU». ACM SAC 2014: 880–885
  51. ^ Х. Кучен и Й. Стригниц. «Возможности функционального программирования для скелетной библиотеки C ++». Параллелизм - практика и опыт, 17 (7–8): 739–756, 2005.
  52. ^ Филипп Цеханович, Майкл Полднер и Герберт Кучен. «Мюсли из библиотеки скелетов Мюнстера - всесторонний обзор». Рабочий документ ERCIS № 7, 2009 г.
  53. ^ Х. Кучен и М. Коул. «Интеграция параллельных скелетов задач и данных». Письма о параллельной обработке, 12 (2): 141–155, 2002.
  54. ^ А. Александреску. «Современный дизайн C ++: применение общих шаблонов программирования и дизайна». Аддисон-Уэсли, 2001.
  55. ^ Майкл Полднер. «Задача параллельных алгоритмических скелетов». Кандидатская диссертация, Мюнстерский университет, 2008 г.
  56. ^ Майкл Полднер и Герберт Кучен. «Алгоритмические скелеты для ветвей и границ». Труды 1-й Международной конференции по программному обеспечению и технологиям данных (ICSOFT), 1: 291–300, 2006.
  57. ^ Майкл Полднер и Герберт Кучен. «Оптимизация обработки скелетных потоков для« разделяй и властвуй »». Труды 3-й Международной конференции по программному обеспечению и технологиям данных (ICSOFT), 181–189, 2008 г.
  58. ^ Майкл Полднер и Герберт Кучен. «Скелеты для разделения и господства». Труды Международной конференции IASTED по параллельным и распределенным вычислениям и сетям (PDCN), 181–188, 2008.
  59. ^ Майкл Полднер и Герберт Кучен. «Масштабируемые фермы». Труды Международной конференции по параллельной обработке (ParCo) 33: 795–802, 2006.
  60. ^ Майкл Полднер и Герберт Кучен. «О реализации скелета фермы». Письма о параллельной обработке, 18 (1): 117–131, 2008.
  61. ^ Филипп Цеханович. «Алгоритмические скелеты для общих разреженных матриц». Труды 20-й Международной конференции IASTED по параллельным и распределенным вычислениям и системам (PDCS), 188–197, 2008.
  62. ^ Филипп Цеханович, Филипп Кегель, Мараике Шеллманн, Сергей Горлач и Герберт Кучен. «Распараллеливание реконструкции изображений LM OSEM на многоядерных кластерах». Параллельные вычисления: от многоядерных и графических процессоров до петаскейла, 19: 169–176, 2010.
  63. ^ Филипп Цеханович и Герберт Кучен. «Улучшение параллельных скелетов данных Muesli для многоядерных компьютерных архитектур». Международная конференция по высокопроизводительным вычислениям и коммуникациям (HPCC), 108–113, 2010 г.
  64. ^ Bacci, B .; Данелутто, М .; Орландо, S .; Pelagatti, S .; Ваннески, М. (1995). «P3L: структурированный параллельный язык высокого уровня и его структурированная поддержка». Параллелизм: практика и опыт. 7 (3): 225. CiteSeerX  10.1.1.215.6425. Дои:10.1002 / cpe.4330070305.
  65. ^ С. Чиарпаглини, М. Данелутто, Л. Фольчи, К. Манкони и С. Пелагатти. «ANACLETO: компилятор p3l на основе шаблонов». В материалах седьмого семинара по параллельным вычислениям (PCW '97), Австралийский национальный университет, Канберра, август 1997 г.
  66. ^ М. Алдинуччи, М. Коппола и М. Данелутто. Переписывание скелетных программ: как оценить компромисс между параллельными данными и потоками. В С. Горлаче, редакторе, Proc of CMPP: Intl. Практикум по конструктивным методам параллельного программирования, страницы 44–58. Uni. Пассау, Германия, май 1998 г.
  67. ^ Б. Баччи, М. Данелутто, С. Пелагатти и М. Ваннески. «Skie: гетерогенная среда для приложений HPC». Параллельные вычисления, 25 (13–14): 1827–1852, 1999.
  68. ^ М. Данелутто и М. Стиглиани. «Скелиб: Параллельное программирование со скелетами на C.» In Euro-Par '00: Proceedings from 6th International Euro-Par Conference on Parallel Processing, страницы 1175–1184, Лондон, Великобритания, 2000. Springer-Verlag.
  69. ^ Д. Госвами, А. Сингх и Б. Р. Прейсс. «От дизайнерских узоров до параллельных архитектурных каркасов». J. Parallel Distrib. Вычисл., 62 (4): 669–695, 2002.
  70. ^ Д. Госвами, А. Сингх и Б. Р. Прейсс. «Использование объектно-ориентированных методов для реализации параллельных архитектурных скелетов». В ISCOPE '99: Proceedings of the Third International Symposium on Computing in Object-Oriented Parallel Environment, Lecture Notes in Computer Science, pages 130–141, London, UK, 1999. Springer-Verlag.
  71. ^ М. М. Акон, Д. Госвами и Х. Ф. Ли. «Superpas: параллельная архитектурная каркасная модель, поддерживающая расширяемость и композицию каркаса». Второй международный симпозиум по параллельной и распределенной обработке и приложениям, ISPA, Lecture Notes in Computer Science, стр. 985–996. Springer-Verlag, 2004.
  72. ^ М. М. Эйкон, А. Сингх, Д. Госвами и Х. Ф. Ли. «Расширяемые параллельные архитектурные скелеты». In High Performance Computing HiPC 2005, 12th International Conference, volume 3769 of Lecture Notes in Computer Science, pages 290–301, Goa, India, December 2005. Springer-Verlag.
  73. ^ М. Диас, Б. Рубио, Э. Солер и Дж. М. Троя. «SBASCO: Научные компоненты на основе скелетов». В PDP, страницы 318–. Компьютерное общество IEEE, 2004 г.
  74. ^ М. Диас, С. Ромеро, Б. Рубио, Э. Солер и Дж. М. Троя. «Использование SBASCO для решения уравнений реакции-диффузии в двумерных нерегулярных областях». В практических аспектах параллельного программирования высокого уровня (PAPP), член Международной конференции по вычислительным наукам (ICCS), том 3992 конспектов лекций по информатике, страницы 912–919. Спрингер, 2006.
  75. ^ М. Диас, С. Ромеро, Б. Рубио, Э. Солер и Дж. М. Троя. «Аспектно-ориентированная структура для разработки научного компонента». В PDP '05: Материалы 13-й конференции Euromicro по параллельной, распределенной и сетевой обработке, страницы 290–296, Вашингтон, округ Колумбия, США, 2005. Компьютерное общество IEEE.
  76. ^ М. Диас, С. Ромеро, Б. Рубио, Э. Солер и Дж. М. Троя. «Динамическая реконфигурация научных компонентов с использованием аспектно-ориентированного программирования: тематическое исследование». В Р. Меерсман и З. Тари, редакторы, На пути к осмысленным интернет-системам 2006: CoopIS, DOA, GADA и ODBASE, том 4276 конспектов лекций по информатике, страницы 1351–1360. Springer-Verlag, 2006.
  77. ^ Дж. Дарлингтон, Ю. Кэ Го, Х. В. То и Дж. Ян. «Параллельные скелеты для структурированной композиции». В PPOPP '95: Материалы пятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, страницы 19–28, Нью-Йорк, Нью-Йорк, США, 1995. ACM.
  78. ^ Джон Дарлинтон; Мустафа Ганем; Йике Го; Хинг Винг То (1996), "Управляемая организация ресурсов в гетерогенных параллельных вычислениях", Журнал высокопроизводительных вычислений, 4 (1): 13–23, CiteSeerX  10.1.1.37.4309
  79. ^ http://www.ida.liu.se/~chrke/skepu
  80. ^ J. Serot, D. Ginhac и J. Derutin. «SKiPPER: среда параллельного программирования на основе скелетов для приложений обработки изображений в реальном времени». В В. Малышкине, редакторе 5-й Международной конференции по технологиям параллельных вычислений (PaCT-99), том 1662 LNCS, страницы 296–305. Springer, 6–10 сентября 1999 г.
  81. ^ J. Serot и D. Ginhac. «Скелеты для параллельной обработки изображений: обзор проекта SKiPPER». Параллельные вычисления, 28 (12): 1785–1808, декабрь 2002 г.
  82. ^ J. Falcou, J. Serot, T. Chateau и J. T. Lapreste. «Quaff: эффективный дизайн на C ++ для параллельных каркасов». Параллельные вычисления, 32 (7): 604–615, 2006.
  83. ^ J. Falcou и J. Serot. «Формальная семантика применима к реализации скелетной библиотеки параллельного программирования». В работе GR Joubert, C. Bischof, FJ Peters, T. Lippert, M. Bcker, P. Gibbon и B. Mohr, редакторы, Parallel Computing: Architectures, Algorithms and Applications (Proc. Of PARCO 2007, Julich, Germany), том 38 NIC, страницы 243–252, Германия, сентябрь 2007 г. Институт вычислительной техники им. Джона фон Неймана.
  84. ^ К. Мацудзаки, Х. Ивасаки, К. Эмото, З. Ху. «Библиотека конструктивных скелетов для последовательного стиля параллельного программирования». В InfoScale '06: Материалы 1-й международной конференции по масштабируемым информационным системам, стр. 13, Нью-Йорк, Нью-Йорк, США, 2006. ACM.
  85. ^ К. Мацудзаки, З. Ху и М. Такеичи. «Распараллеливание с каркасами деревьев». В Euro-Par, том 2790 конспектов лекций по информатике, страницы 789–798. Спрингер, 2003.
  86. ^ К. Мацудзаки, З. Ху и М. Такеичи. «Параллельные скелеты для управления обычными деревьями». Параллельные вычисления, 32 (7): 590–603, 2006.
  87. ^ К. Эмото, З. Ху, К. Какехи и М. Такеичи. «Композиционная структура для разработки параллельных программ на двумерных массивах». Технический отчет факультета математической информатики Токийского университета, 2005 г.
  88. ^ К. Эмото, К. Мацудзаки, З. Ху и М. Такеичи. «Стратегия оптимизации для скелетных программ для конкретных областей». В Euro-Par, том 4641 конспектов лекций по информатике, страницы 705–714. Спрингер, 2007.
  89. ^ К. Мацудзаки, К. Какехи, Х. Ивасаки, З. Ху и Ю. Акаси. "Скелетная библиотека, встроенная во фьюжн". В M. Danelutto, M. Vanneschi и D. Laforenza, редакторах, Euro-Par, том 3149 конспектов лекций по информатике, страницы 644–653. Спрингер, 2004.
  90. ^ Г. Х. Боторог и Х. Кучен. «Эффективное параллельное программирование высокого уровня». Теор. Comput. Наук, 196 (1–2): 71–107, 1998.
  91. ^ Зандифар, Мани; Абдулджаббар, Мустафа; Маджиди, Алиреза; Киз, Дэвид; Амато, Нэнси; Раухвергер, Лоуренс (2015). Составление алгоритмических скелетов для создания высокопроизводительных научных приложений. Материалы 29-й ACM Международной конференции по суперкомпьютерам. С. 415–424. Дои:10.1145/2751205.2751241. ISBN  9781450335591.
  92. ^ Зандифар, Мани; Томас, Натан; Амато, Нэнси М .; Раухвергер, Лоуренс (15 сентября 2014 г.). Бродман, Джеймс; Ту, Пэн (ред.). Языки и компиляторы для параллельных вычислений. Конспект лекций по информатике. Издательство Springer International. С. 176–190. Дои:10.1007/978-3-319-17473-0_12. ISBN  9783319174723.
  93. ^ "Г. Тэнасе и др." "STAPL Parallel Container Framework" ProceedingPPoPP '11 Материалы 16-го симпозиума ACM по Принципам и практике параллельного программирования Стр. 235–246
  94. ^ Дж. Дарлингтон, А. Дж. Филд, П. Г. Харрисон, П. Х. Дж. Келли, Д. В. Н. Шарп и К. Ву. «Параллельное программирование с использованием скелетных функций». В PARLE '93: Материалы 5-й Международной конференции PARLE по параллельным архитектурам и языкам в Европе, страницы 146–160, Лондон, Великобритания, 1993. Springer-Verlag.
  95. ^ Дж. Дарлинтон; М. Ганем; H. W. To (1993), "Структурированное параллельное программирование", В моделях программирования для массивно параллельных компьютеров. Издательство IEEE Computer Society Press. 1993 г.: 160–169, CiteSeerX  10.1.1.37.4610