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

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

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

Обзор

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

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

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

Цель состоит в том, чтобы реализовать параллельную версию алгоритма QuickSort на основе алгоритмического скелета с использованием шаблона «Разделяй и властвуй». Обратите внимание, что высокоуровневый подход скрывает управление потоками от программиста.

// 1. Определить скелет программы 
 Skeleton  <  Range  ,   Range  >   sort   =     new   DaC  <  Range  ,   Range  >  ( 
     new   MustSplit  (  порог  ,   maxTimes  ), 
     новый   SplitList  (), 
     новый   Sort  (), 
     новый   MergeList  ()); 
		
  // 2. Входные параметры 
 Future  <  Range  >   Future   =   sort  .   ввод  (  новый   диапазон  (  генерировать  (...))); 
	
  // 3. Сделайте здесь что-нибудь еще. 
  // ... 
	
 // 4. Блок результатов 
 Range   result   =   Future  .   получать  (); 

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

Функциональные коды в этом примере соответствуют четырем типам: «Условие», «Разделение», «Выполнение» и «Слияние».

публичный   класс   MustSplit   реализует   Condition  <  Range  >  { 

   int   порог  ,   maxTimes  ,   times  ; 
  
    public   MustSplit  (  int   порог  ,   int   maxTimes  ) { 
     this  .   порог   =   порог  ; 
      этот  .   МаксВремя    =   МаксВремя  ; 
      этот  .   раз       =   0  ; 
    } 
	
   @Override 
   публичное   синхронизированное   логическое   условие  (  диапазон   r  ) { 
     return   r  .   правильно   -   р  .   влево   >   порог   && 
    	    раз  ++   <   это  .   МаксВремя  ; 
    } 
 } 

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

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

публичный   класс   SplitList   реализует   Split  <  Range  ,   Range  >  { 

  @Override 
  public   Range  []   Split  (  Range   r  ) { 
        
     int   i   =   раздел  (  r  .  array  ,   r  .  left  ,   r  .  right  ); 
        
      Range  []   интервалы   =   {  новый   диапазон  (  r  .  array  ,   r  .  left  ,   i  -  1  ),  
                          новый   диапазон  (  r  .  array  ,   i  +  1  ,   r  .  right  )}; 
        
     возврата    интервалы  ; 
   } 
 } 

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

общественный   класс   Sort   реализует   Execute  <  Range  ,   Range  >   { 

   @Override 
   public   Range   выполнить  (  Range   r  ) { 
		
     if   (  r  .  right   <=   r  .  left  )   return   r  ; 
		
      Массивы  .   сортировка  (  р  .  массив  ,   р  .  влево  ,   р  .  вправо  +  1  ); 
		
      вернуть   р  ; 
    } 
 } 

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

общедоступный   класс   MergeList   реализует   Merge  <  Range  ,   Range  >  { 

   @Override 
   public   Range   merge  (  Range  []   r  ) { 
		
     диапазона   Результат   =   новый   диапазон  (   r  [  0  ]  .  массив  ,   r  [  0  ]  .  влево  ,   r  [  1  ]  .  вправо  ) ; 
		
      вернуть   результат  ; 
    } 
 } 

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

ПОМОЩЬ

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

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

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

CO2P3S

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

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

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

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

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

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

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

Skandium — это полная переработка Calcium для многоядерных вычислений. Программы, написанные на Skandium, могут использовать преимущества общей памяти для упрощения параллельного программирования.

Иден

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

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

эСкел

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

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

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

Более поздние работы посвящены проблеме адаптации структурного параллельного программирования. в частности для каркаса трубы.

ФастФлоу

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

HDC

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

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

-

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

Яскель

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

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

Литий и мускус

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

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

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

Мальба

Шаблон — это библиотека для комбинаторной оптимизации, поддерживающая точные, эвристические и гибридные стратегии поиска. Каждая стратегия реализована в Mallba как общий скелет, который можно использовать, предоставив необходимый код. Что касается точных алгоритмов поиска, Mallba предоставляет скелеты ветвей и границ и динамической оптимизации. Для эвристики локального поиска Mallba поддерживает: восхождение на холм , мегаполис, имитацию отжига и поиск с запретами ; а также популяционную эвристику, полученную на основе эволюционных алгоритмов, таких как генетические алгоритмы , стратегия эволюции и другие (CHC). Гибридные скелеты сочетают в себе стратегии, такие как: GASA, смесь генетического алгоритма и имитация отжига и CHCCES, сочетающий CHC и ES.

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

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

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

Костный мозг

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

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

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

Более подробную информацию, а также исходный код можно найти на веб-сайте Marrow.

Мюсли

Мюенстерская библиотека скелетов, мюсли — это библиотека шаблонов C++, которая повторно реализует многие идеи и концепции, представленные в Skil , например функции высшего порядка, каррирование и полиморфные типы [1] . Он построен на основе MPI 1.2 и OpenMP 2.5 и поддерживает, в отличие от многих других библиотек скелетов, параллельные скелеты как задач, так и данных. Вложенность скелетов (композиция) аналогична двухуровневому подходу P3L , т.е. скелеты параллельных задач могут быть вложены произвольно, тогда как скелеты параллельных данных не могут, но могут использоваться в листьях дерева параллельной вложенности задач. Шаблоны C++ используются для визуализации полиморфных скелетов, но никакая система типов не применяется. Однако библиотека реализует механизм автоматической сериализации, вдохновленный так что в дополнение к стандартным типам данных MPI в скелетах можно использовать произвольные определяемые пользователем типы данных. Поддерживаемые параллельные скелеты задач являются филиалами и границами, Разделяй и властвуй, Ферма, и Pipe, вспомогательными скелетами являются Filter, Final и Initial. Скелеты параллельных данных, такие как сгиб (сокращение), карта, перестановка, zip и их варианты, реализованы как функции-члены более высокого порядка распределенной структуры данных. В настоящее время Muesli поддерживает распределенные структуры данных для массивов, матриц и разреженных матриц.

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

P3L, SkIE, SKElib

P3L (Язык параллельного программирования Pisa) — это язык координации, основанный на скелете. P3L предоставляет скелетные конструкции, которые используются для координации параллельного или последовательного выполнения кода C. Компилятор по имени Анаклето предусмотрен для языка. Anacleto использует шаблоны реализации для компиляции кода P3 L в целевую архитектуру. Таким образом, скелет может иметь несколько шаблонов, каждый из которых оптимизирован под свою архитектуру. Шаблон реализует скелет конкретной архитектуры и предоставляет параметрический граф процесса с моделью производительности. Затем модель производительности можно использовать для принятия решений о преобразованиях программы, которые могут привести к оптимизации производительности.

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

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

СКЕЛиб основывается на достижениях P3L и SkiE, наследуя, среди прочего, систему шаблонов. Он отличается от них тем, что больше не используется язык координации, а вместо этого в виде библиотеки на C предоставляются скелеты с производительностью, аналогичной достигнутой в P3L . В отличие от Skil , еще одной C-подобной каркасной структуры, безопасность типов не рассматривается в SKELib .

PAS и EPAS

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

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

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

СБАСКО

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

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

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

СКЛ

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

СкеПУ

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

ШКИППЕР И КУАФФ

SKiPPER — это специализированная библиотека скелетов для приложений машинного зрения. который предоставляет скелеты в CAML и, таким образом, полагается на CAML для обеспечения безопасности типов. Скелеты представлены двумя способами: декларативным и операционным. Декларативные скелеты напрямую используются программистами, в то время как их рабочие версии обеспечивают целевую реализацию для конкретной архитектуры. На основе среды выполнения, спецификаций скелета CAML и конкретных функций приложения (предоставляемых программистом на языке C) генерируется и компилируется новый код C для запуска приложения на целевой архитектуре. Одна из интересных особенностей SKiPPER заключается в том, что программа-скелет может выполняться последовательно для отладки.

были исследованы различные подходы В SKiPPER к написанию операционных скелетов: статические графы потоков данных, параметрические сети процессов, иерархические графы задач и графы потоков данных с тегированными токенами.

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

СкеТо

СкеТо ​ Project — это библиотека C++, которая обеспечивает распараллеливание с использованием MPI. SkeTo отличается от других библиотек скелетов тем, что вместо предоставления вложенных шаблонов параллелизма SkeTo предоставляет параллельные скелеты для параллельных структур данных, таких как: списки, деревья, и матрицы. Структуры данных типизируются с использованием шаблонов, и над ними можно вызывать несколько параллельных операций. Например, структура списка обеспечивает параллельные операции, такие как: сопоставление, уменьшение, сканирование, сжатие, сдвиг и т. д.

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

Развод

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

Каркас STAPL

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

Т4П

T4P была одной из первых систем, представленных для скелетного программирования. Система в значительной степени опиралась на свойства функционального программирования, и пять скелетов были определены как функции более высокого порядка: «Разделяй и властвуй», «Ферма», «Карта», «Труба» и «RaMP». Программа может иметь более одной реализации, каждая из которых использует комбинацию различных скелетов. Более того, каждый скелет может иметь разные параллельные реализации. Для выбора наиболее подходящего скелета для программы, а также наиболее подходящей реализации скелета использовалась методология, основанная на функциональных преобразованиях программ, основанных на моделях производительности скелетов.

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

• Годы активности  — это известный интервал лет деятельности. Даты, представленные в этом столбце, соответствуют первой и последней дате публикации соответствующей статьи в научном журнале или материалах конференции. Обратите внимание, что проект может оставаться активным и после окончания периода активности, и что нам не удалось найти для него публикацию после указанной даты.
• Язык программирования — это интерфейс, с которым программисты взаимодействуют при написании своих скелетных приложений. Эти языки разнообразны и включают в себя такие парадигмы, как функциональные языки, языки координации, языки разметки, императивные языки, объектно-ориентированные языки и даже графические пользовательские интерфейсы. Внутри языка программирования скелеты предоставляются либо в виде языковых конструкций, либо в виде библиотек. Предоставление скелетов в качестве языковой конструкции подразумевает разработку специального предметно-ориентированного языка и его компилятора. Это была явно более сильная тенденция в начале исследования скелетов. Более поздней тенденцией является предоставление скелетов в виде библиотек, в частности, в объектно-ориентированных языках, таких как C++ и Java.
• Язык выполнения — это язык, на котором запускаются или компилируются скелетные приложения. Очень рано было признано, что языки программирования (особенно в функциональных случаях) недостаточно эффективны для выполнения скелетных программ. Поэтому скелетные языки программирования были упрощены за счет выполнения скелетных приложений на других языках. Были введены процессы преобразования для преобразования скелетных приложений (определенных на языке программирования) в эквивалентное приложение на целевом языке выполнения. Были введены различные процессы преобразования, такие как генерация кода или создание скелетов нижнего уровня (иногда называемых операционными скелетами), которые были способны взаимодействовать с библиотекой на языке выполнения. Преобразованное приложение также дало возможность внедрить в преобразованное приложение код целевой архитектуры, настроенный по производительности. Таблица 1 показывает, что фаворитом в качестве языка исполнения был язык C.
• Библиотека распределения предоставляет функциональные возможности для выполнения параллельных/распределенных вычислений. Большим фаворитом в этом смысле является MPI, что неудивительно, поскольку он хорошо интегрируется с языком C и, вероятно, является наиболее используемым инструментом параллелизма в кластерных вычислениях. Опасности прямого программирования с использованием дистрибутивной библиотеки, конечно, надежно скрыты от программистов, которые никогда не взаимодействуют с дистрибутивной библиотекой. В последнее время наблюдается тенденция к разработке каркасных фреймворков, способных взаимодействовать с более чем одной библиотекой дистрибутива. Например, CO2 P3 S может использовать резьбу, RMI или разъемы; Mallba может использовать Netstream или MPI; или JaSkel, который использует AspectJ для выполнения скелетных приложений в различных скелетных средах.
• Типовая безопасность относится к способности обнаруживать ошибки несовместимости типов в скелетной программе. Поскольку первые каркасные фреймворки были построены на функциональных языках, таких как Haskell, типобезопасность просто унаследована от основного языка. Тем не менее, поскольку для скелетного программирования были разработаны специальные языки, необходимо было написать компиляторы, учитывающие проверку типов; что было не так сложно, поскольку вложение скелетов не поддерживалось полностью. Однако недавно, когда мы начали размещать скелетные структуры на объектно-ориентированных языках с полной вложенностью, проблема безопасности типов вновь всплыла на поверхность. К сожалению, проверка типов по большей части игнорируется (за исключением QUAFF), особенно в каркасных фреймворках на основе Java.
• Вложенность скелетов — это возможность иерархической композиции шаблонов скелетов. Скелетная вложенность с самого начала была определена как важная функция скелетного программирования, поскольку она позволяет составлять более сложные шаблоны, начиная с базового набора более простых шаблонов. Тем не менее, сообществу потребовалось много времени, чтобы полностью поддержать произвольное вложение скелетов, главным образом из-за трудностей планирования и проверки типов. Тенденция очевидна: последние скелетные структуры поддерживают полную вложенность скелетов.
• Доступ к файлам — это возможность получать доступ к файлам и манипулировать ими из приложения. В прошлом скелетное программирование оказывалось полезным в основном для приложений с интенсивными вычислениями, где небольшие объемы данных требуют большого количества вычислительного времени. Тем не менее, многие распределенные приложения требуют или производят большие объемы данных во время своих вычислений. Это относится к астрофизике, физике элементарных частиц, биоинформатике и т. д. Таким образом, обеспечение поддержки передачи файлов, которая интегрируется со скелетным программированием, является ключевой проблемой, которая по большей части игнорируется.
• Набор скелетов — это список поддерживаемых шаблонов скелетов. Наборы скелетов сильно различаются от одного фреймворка к другому, и что еще более шокирует, некоторые скелеты с одинаковыми именами имеют разную семантику в разных фреймворках. Наиболее распространенными моделями скелетов в литературе, вероятно, являются «ферма», «труба» и «карта».

Необъектно-ориентированные алгоритмические скелетные структуры

	Годы деятельности	Язык программирования	Язык исполнения	Библиотека дистрибутива	Тип безопасный	Вложение скелета	Доступ к файлам	Набор скелетов
ПОМОЩЬ	2004–2007	Пользовательский язык управления	С++	TCP/IP + SSH/SCP	Да	Нет	явный	продолжение, пармод
SBSACO	2004–2006	Пользовательский язык композиции	С++	ИМБ	Да	Да	Нет	ферма, труба, многоблочная
eScale	2004–2005	С	С	ИМБ	Нет	?	Нет	трубопровод, ферма, сделка, бабочка, hallowSwap
HDC	2004–2005	Подмножество Haskell	С	ИМБ	Да	?	Нет	dcA, dcB, dcD, dcE, dcF, карта, красный, сканирование, фильтр
СКЕЛиб	2000-2000	С	С	ИМБ	Нет	Нет	Нет	ферма, труба
СкИППЕР	1999–2002	КАМЛ	С	СинДекс	Да	ограниченное	Нет	СКМ, ДФ, ТФ, промежуточный
SkIE	1999-1999	Графический интерфейс/пользовательский язык управления	С++	ИМБ	Да	ограниченное	Нет	труба, ферма, карта, сокращение, петля
Эдем	1997–2011	Расширение Хаскелла	Хаскелл	ПВМ/MPI	Да	Да	Нет	карта, ферма, рабочий пул, номер, округ Колумбия, труба, iterUntil, тор, кольцо
P3L	1995–1998	Пользовательский язык управления	С	ИМБ	Да	ограниченное	Нет	карта, уменьшение, сканирование, комп, конвейер, ферма, последовательность, цикл
Понимать	1995–1998	Подмножество C	С	?	Да	Нет	Нет	пардата, карта, сгиб
СКЛ	1994–1999	Пользовательский язык управления	Фортран/С	ИМБ	Да	ограниченное	Нет	карта, сканирование, сгиб, ферма, СПМД, итерацияПока
Т4П	1990–1994	Надежда+	Надежда+	CSИнструменты	Да	ограниченное	Нет	D&C (разделяй и властвуй), Карта, Труба, RaMP

Объектно-ориентированные алгоритмические скелетные структуры

	Годы деятельности	Язык программирования	Язык исполнения	Библиотека дистрибутива	Тип безопасный	Вложение скелета	Доступ к файлам	Набор скелетов
Скандий	2009–2012	Джава	Джава	Потоки	Да	Да	Нет	seq, труба, ферма, для, пока, карта, d&c, вилка
ФастФлоу	2009–	С++	С++11/CUDA/OpenCL	Потоки C++11/потоки Posix/TCP-IP/OFED-IB/CUDA/OpenCL	Да	Да	Да	Конвейер, Ферма, ParallelFor, ParallelForReduce, MapReduce, StencilReduce, PoolEvolution, MacroDataFlow
Кальций	2006–2008	Джава	Джава	Проактив	Да	Да	Да	seq, труба, ферма, для, пока, карта, d&c, вилка
КУАФ	2006–2007	С++	С	ИМБ	Да	Да	Нет	seq, труба, ферма, scm, пардо
Яскель	2006–2007	Джава	Java/AspectJ	МПП / РМИ	Нет	Да	Нет	ферма, трубопровод, сердцебиение
Мышцы	2005–2008	Джава	Джава	РМИ	Нет	Да	Нет	ферма, труба, секвенсор, + пользовательские графики MDF
HOC-SA	2004–2008	Джава	Джава	Глобус, КОАЛА	Нет	Нет	Нет	ферма, трубопровод, фронт волны
СкеТо	2003–2013	С++	С++	ИМБ	Да	Нет	Нет	список, матрица, дерево
Шаблон	2002–2007	С++	С++	НетСтрим / МПИ	Да	Нет	Нет	точный, эвристический, гибридный
Костный мозг	2013–	С++	С++ плюс OpenCL	(никто)	Нет	Да	Нет	параллельные данные: карта, карта-сокращение. параллельная задача: конвейер, цикл, для
мюсли	2002–2013	С++	С++	MPI/ОпенМП	Да	Да	Нет	параллельные данные: сгиб, сопоставление, перестановка, сканирование, сжатие и варианты. параллельные задачи: «ветвь и граница», «разделяй и властвуй», «ферма», «труба». вспомогательные: фильтр, окончательный, начальный
Все	2002–2003	Java/GworkflowDL	Джава	Ява РМИ	Да	Нет	Нет	карта, zip, уменьшение, сканирование, dh, репликация, применение, сортировка
(Д) ПОСЛЕ	1999–2005	Расширение C++	С++	ИМБ	Нет	Да	Нет	синглтон, репликация, композиционный, конвейер, разделение-покорение, параллельные данные
Литий	1999–2004	Джава	Джава	РМИ	Нет	Да	Нет	труба, карта, ферма, уменьшить
CO2P3S	1999–2003	Графический интерфейс/Java	Java (сгенерировано)	Резьба/RMI/Гнезда	Частичный	Нет	Нет	метод-последовательность, распределитель, сетка, волновой фронт
СКОБКА	2010–	С++	С++11	Библиотека времени выполнения STAPL (MPI, OpenMP, PThreads)	Да	Да	Да	карта, zip<arity>, уменьшение, сканирование, ферма, (обратная) бабочка, (обратное) дерево<k-ary>, рекурсивное удвоение, серийный, транспонирование, трафарет<n-dim>, wavefront<n-dim >, allreduce, allgather, собрать, разбросать, транслировать Операторы: составить, повторить, сделать пока, сделать все, сделать через

См. также

• Галид (язык программирования)
• Клинопись (язык программирования)
• Модель параллельного программирования