✖


Jump to content

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

Edit links

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

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

Обзор

[ редактировать ]

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

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

[ редактировать ]

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

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

// 1. Define the skeleton program
Skeleton<Range, Range> sort =   new DaC<Range, Range>(
    new ShouldSplit(threshold, maxTimes),
    new SplitList(),
    new Sort(),
    new MergeList());
		
// 2. Input parameters
Future<Range> future = sort.input(new Range(generate(...)));
	
// 3. Do something else here.
// ...
	
// 4. Block for the results
Range result = future.get();
  1. Первым делом необходимо определить новый экземпляр скелета с функциональным кодом, заполняющим шаблон (ShouldSplit, SplitList, Sort, MergeList). Функциональный код пишется программистом без учета параллелизма.
  2. Второй шаг — это ввод данных, которые запускают вычисления. В данном случае Range — это класс, содержащий массив и два индекса, которые позволяют представлять подмассив. Для каждых данных, введенных в структуру, создается новый объект Future. В скелет одновременно можно ввести более одного Future.
  3. Будущее допускает асинхронные вычисления, поскольку во время вычисления результатов можно выполнять другие задачи.
  4. Мы можем получить результат вычисления, заблокировав его при необходимости (т. е. результаты еще не доступны).

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

public class ShouldSplit implements Condition<Range>{

  int threshold, maxTimes, times;
  
  public ShouldSplit(int threshold, int maxTimes){
    this.threshold = threshold;
    this.maxTimes  = maxTimes;
    this.times     = 0;
  }
	
  @Override
  public synchronized boolean condition(Range r){
    return r.right - r.left > threshold &&
    	   times++ < this.maxTimes;
  }
}

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

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

public class SplitList implements Split<Range, Range>{

 @Override
 public Range[] split(Range r){
        
    int i = partition(r.array, r.left, r.right);
        
    Range[] intervals = {new Range(r.array, r.left, i-1), 
                         new Range(r.array, i+1, r.right)};
        
    return intervals;
 }
}

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

public class Sort implements Execute<Range, Range> {

  @Override
  public Range execute(Range r){
		
    if (r.right <= r.left) return r;
		
    Arrays.sort(r.array, r.left, r.right+1);
		
    return r;
  }
}

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

public class MergeList implements Merge<Range, Range>{

  @Override
  public Range merge(Range[] r){
		
    Range result = new Range( r[0].array, r[0].left, r[1].right);
		
    return result;
  }
}

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

[ редактировать ]

ПОМОЩЬ

[ редактировать ]

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

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

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

CO2P3S

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

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

Эдем

[ редактировать ]

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

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

eScale

[ редактировать ]

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

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

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

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

ФастФлоу

[ редактировать ]

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 ) имеют целью упростить Разработка грид-приложений.
Целью HOC-SA является предоставление пользователям Globus, которые не хотят знать обо всех деталях промежуточного программного обеспечения Globus (документы GRAM RSL, веб-сервисы, конфигурация ресурсов и т. д.), HOC, которые предоставляют интерфейс более высокого уровня для Grid, чем основной Globus Toolkit.
HOC — это скелеты с поддержкой Grid, реализованные как компоненты поверх Globus Toolkit, доступные удаленно через веб-службы. [29]

Яскель

[ редактировать ]

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

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

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

[ редактировать ]

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

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

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

Шаблон

[ редактировать ]

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

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

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

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

костный мозг

[ редактировать ]

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

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

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

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

Мюсли

[ редактировать ]

Мюенстерская библиотека скелетов, мюсли [51] [52] — это библиотека шаблонов C++, которая повторно реализует многие идеи и концепции, представленные в Skil , например функции высшего порядка, каррирование и полиморфные типы [1] . Он построен на основе MPI 1.2 и OpenMP 2.5 и поддерживает, в отличие от многих других библиотек скелетов, параллельные скелеты как задач, так и данных. Вложенность скелетов (композиция) аналогична двухуровневому подходу P3L , т.е. скелеты параллельных задач могут быть вложены произвольно, тогда как скелеты параллельных данных не могут, но могут использоваться на концах дерева параллельной вложенности задач. [53] Шаблоны C++ используются для визуализации полиморфных скелетов, но никакая система типов не применяется. Однако библиотека реализует механизм автоматической сериализации, вдохновленный [54] так что в дополнение к стандартным типам данных MPI в скелетах можно использовать произвольные определяемые пользователем типы данных. Поддерживаемые параллельные скелеты задач [55] являются филиалами и границами, [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) — это язык координации, основанный на скелете. P3L предоставляет скелетные конструкции, которые используются для координации параллельного или последовательного выполнения кода C. Компилятор по имени Анаклето [65] предусмотрен для языка. Anacleto использует шаблоны реализации для компиляции кода P3 L в целевую архитектуру. Таким образом, скелет может иметь несколько шаблонов, каждый из которых оптимизирован под свою архитектуру. Шаблон реализует скелет конкретной архитектуры и предоставляет параметрический граф процесса с моделью производительности. Затем модель производительности можно использовать для принятия решений о преобразованиях программы, которые могут привести к оптимизации производительности. [66]

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

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

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

ПАС и ЭПАС

[ редактировать ]

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

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

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

СБАСКО

[ редактировать ]

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

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

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

СКЛ

[ редактировать ]

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

СкеПУ

[ редактировать ]

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

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

[ редактировать ]

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

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

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

СкеТо

[ редактировать ]

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

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

Возвращаться

[ редактировать ]

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

Каркас STAPL

[ редактировать ]

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

Т4П

[ редактировать ]

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

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

[ редактировать ]
  • Годы активности  — это известный интервал лет деятельности. Даты, представленные в этом столбце, соответствуют первой и последней дате публикации соответствующей статьи в научном журнале или материалах конференции. Обратите внимание, что проект может оставаться активным и после окончания периода активности, и что нам не удалось найти для него публикацию после указанной даты.
  • Язык программирования — это интерфейс, с которым программисты взаимодействуют при написании своих скелетных приложений. Эти языки разнообразны и включают в себя такие парадигмы, как функциональные языки, языки координации, языки разметки, императивные языки, объектно-ориентированные языки и даже графические пользовательские интерфейсы. Внутри языка программирования скелеты предоставляются либо в виде языковых конструкций, либо в виде библиотек. Предоставление скелетов в качестве языковой конструкции подразумевает разработку специального предметно-ориентированного языка и его компилятора. Это была явно более сильная тенденция в начале исследования скелетов. Более поздней тенденцией является предоставление скелетов в виде библиотек, в частности, в объектно-ориентированных языках, таких как 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 С++ С++ МПИ/ОпенМП Да Да Нет параллельные данные: сгиб, сопоставление, перестановка, сканирование, сжатие и варианты. параллельные задачи: «ветвь и граница», «разделяй и властвуй», «ферма», «труба». вспомогательные: фильтр, окончательный, начальный
Все 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, собрать, разбросать, транслировать

Операторы: составить, повторить, сделать пока, сделать все, сделать через

См. также

[ редактировать ]

Ссылки

[ редактировать ]
  1. ^ К. Хаммонд и Г. Майкельсон, редакторы. «Направления исследований в области параллельного функционального программирования». Спрингер-Верлаг, Лондон, Великобритания, 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. ^ Альдинуччи, М.; Данелутто, М.; Антониу, Г.; Ян, М. (2008). «Отказоустойчивое совместное использование данных для высокоуровневой сети: иерархическая архитектура хранения». Достижения европейских исследований грид-систем . п. 67. дои : 10.1007/978-0-387-72812-4_6 . ISBN  978-0-387-72811-7 .
  6. ^ 'С. Макдональд, Дж. Анвик, С. Бромлинг, Дж. Шеффер, Д. Шафрон и К. Тан». «Из узоров от фреймворков к параллельным программам». Parallel Comput., 28(12):1663–1683, 2002.
  7. ^ К. Тан, Д. Шафрон, Дж. Шеффер, Дж. Анвик и С. Макдональд. «Использование шаблонов генеративного проектирования для создания параллельного кода для среды с распределенной памятью». В PPoPP '03: Материалы девятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, страницы 203–215, Нью-Йорк, Нью-Йорк, США, 2003. ACM.
  8. ^ Д. Каромель и М. Лейтон. «Точная настройка алгоритмических скелетов». На 13-й Международной конференции Euro-Par: Параллельная обработка, том 4641 конспектов лекций по информатике, страницы 72–81. Спрингер-Верлаг, 2007.
  9. ^ Д. Каромель, Л. Анрио и М. Лейтон. «Введите безопасные алгоритмические скелеты». В материалах 16-й конференции Euromicro по параллельной, распределенной и сетевой обработке, стр. 45–53, Тулуза, Франция, февраль 2008 г. IEEE CS Press.
  10. ^ Д. Каромель и М. Лейтон. «Прозрачная неинвазивная модель файловых данных для алгоритмических скелетов». На 22-м Международном симпозиуме по параллельной и распределенной обработке (IPDPS), страницы 1–8, Майами, США, март 2008 г. Компьютерное общество IEEE.
  11. ^ Марио Лейтон, Хосе М. Пикер. «Скандиум: многоядерное программирование с алгоритмическими скелетами», IEEE Euro-micro PDP 2010.
  12. ^ Рита Лооген, Иоланда Ортега-Маллен и Рикардо Пенья-Мари. «Параллельное функциональное программирование в Эдеме», Журнал функционального программирования, № 15 (2005), 3, страницы 431–475.
  13. ^ Мюррей Коул. «Вытаскивание скелетов из чулана: прагматический манифест скелетного параллельного программирования». Параллельные вычисления, 30(3):389–406, 2004.
  14. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Гибкое скелетное программирование с помощью eskel». В JC Cunha и PD Medeiros, редакторах Euro-Par, том 3648 конспектов лекций по информатике, страницы 761–770. Спрингер, 2005.
  15. ^ А. Бенуа и М. Коул. «Две фундаментальные концепции скелетного параллельного программирования». В. Сундерам, Д. ван Альбада, П. Слоот и Дж. Донгарра, редакторы, Международная конференция по вычислительной науке (ICCS 2005), Часть II, LNCS 3515, страницы 764–771. Спрингер Верлаг, 2005.
  16. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. Оценка производительности параллельных программ высокого уровня на основе скелета. В М. Бубаке, Д. ван Альбаде, П. Слооте и Дж. Донгарре, редакторах, Международная конференция по вычислительной науке (ICCS 2004), Часть III, LNCS 3038, страницы 289–296. Спрингер Верлаг, 2004.
  17. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Оценка производительности конвейерных структурированных параллельных программ с использованием скелетов и алгебры процессов». Масштабируемые вычисления: практика и опыт, 6 (4): 1–16, декабрь 2005 г.
  18. ^ А. Бенуа, М. Коул, С. Гилмор и Дж. Хиллстон. «Планирование грид-приложений на основе скелета с использованием pepa и nws». Компьютерный журнал, специальный выпуск по моделированию и измерению производительности энергосистем, 48(3):369–378, 2005 г.
  19. ^ А. Бенуа и Ю. Роберт. «Сопоставление скелетов трубопроводов на гетерогенных платформах». В ICCS 2007, 7-я Международная конференция по вычислительной науке, LNCS 4487, страницы 591–598. Спрингер Верлаг, 2007.
  20. ^ Г. Яйхом, М. Коул, С. Гилмор и Дж. Хиллстон. «Структурный подход к моделированию производительности систем с использованием скелетов». Электр. Примечания Теор. Вычислить. Sci., 190(3):167–183, 2007.
  21. ^ Х. Гонсалес-Велес и М. Коул . «На пути к полностью адаптивному конвейерному параллелизму для гетерогенных распределенных сред». В книге «Параллельная и распределенная обработка и приложения», 4-й международный симпозиум (ISPA), конспекты лекций по информатике, страницы 916–926. Спрингер-Верлаг, 2006.
  22. ^ Х. Гонсалес-Велес и М. Коул. «Адаптивный структурированный параллелизм для вычислительных сеток». В PPoPP '07: Материалы 12-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, страницы 140–141, Нью-Йорк, США, 2007. ACM.
  23. ^ Альдинуччи, М.; Кампа, С.; Данелутто, М.; Килпатрик, П.; Торквати, М. (2013). «Нацеливание на распределенные системы в FastFlow» (PDF) . Euro-Par 2012: Семинары по параллельной обработке . Euro-Par 2012: Семинары по параллельной обработке. Конспекты лекций по информатике. Том. 7640. стр. 47–56. дои : 10.1007/978-3-642-36949-0_7 . ISBN  978-3-642-36948-3 .
  24. ^ Альдинуччи, М.; Спампинато, К.; Дрокко, М.; Торквати, М.; Палаццо, С. (2012). «Параллельный алгоритм сохранения краев для шумоподавления изображений с солью и перцем». 2012 3-я Международная конференция по теории, инструментам и приложениям обработки изображений (IPTA) . 3-я Международная конференция по теории, инструментам и приложениям обработки изображений (IPTA). стр. 97–104. дои : 10.1109/IPTA.2012.6469567 . hdl : 2318/154520 .
  25. ^ Альдинуччи, М.; Данелутто, М.; Килпатрик, П.; Менегин, М.; Торквати, М. (2012). «Эффективная неограниченная очередь без блокировок для многоядерных систем». Параллельная обработка Euro-Par 2012 . Euro-Par 2012 Параллельная обработка. Конспекты лекций по информатике. Том. 7484. стр. 662–673. дои : 10.1007/978-3-642-32820-6_65 . hdl : 2318/121343 . ISBN  978-3-642-32819-0 .
  26. ^ Альдинуччи, М.; Менегин, М.; Торквати, М. (2010). «Эффективный метод Смита-Уотермана на многоядерных процессорах с быстрым потоком ». 2010 18-я конференция Euromicro по параллельной, распределенной и сетевой обработке . IEEE. п. 195. CiteSeerX   10.1.1.163.9092 . дои : 10.1109/PDP.2010.93 . ISBN  978-1-4244-5672-7 . S2CID   1925361 .
  27. ^ CA Херрманн и К. Ленгауэр. «HDC: язык высшего порядка для принципа «разделяй и властвуй». Письма о параллельной обработке, 10 (2–3): 239–250, 2000.
  28. ^ CA Херрманн. Скелетная параллелизация рекурсий «разделяй и властвуй». Кандидатская диссертация, 2000. ISBN   3-89722-556-5 ».
  29. ^ Дж. Даннвебер, С. Горлач. «Компоненты высшего порядка для Grid-программирования. Делаем сетки более удобными. ". Шпрингер-Верлаг, 2009. ISBN   978-3-642-00840-5
  30. ^ Дж. Ф. Феррейра, Дж. Л. Собрал и А. Дж. Проенка. «Jaskel: фреймворк на основе скелета Java для структурированных кластерных и грид-вычислений». В CCGRID '06: Труды шестого международного симпозиума IEEE по кластерным вычислениям и сетям, страницы 301–304, Вашингтон, округ Колумбия, США, 2006. Компьютерное общество IEEE.
  31. ^ Дж. Собрал и А. Проэнка. «Включение скелетов Jaskel для кластеров и вычислительных сеток». В кластере IEEE. IEEE Press, 9 2007.
  32. ^ М. Альдинуччи и М. Данелутто. «Оптимизация скелета параллельного потока». В Proc. ПДКС: Международный Конференция по параллельным и распределенным вычислениям и системам, страницы 955–962, Кембридж, Массачусетс, США, ноябрь 1999 г. IASTED, ACTA press.
  33. ^ Альдинуччи, М.; Данелутто, М.; Тети, П. (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. ^ М. Альдинуччи и М. Данелутто. «Операционная семантика скелетов». Г. Р. Жубер, В. Е. Нагель, Ф. Дж. Петерс и В. В. Уолтер, редакторы, «Параллельные вычисления: программные технологии, алгоритмы, архитектуры и приложения», PARCO 2003, том 13 журнала «Достижения в области технологий». Параллельные вычисления, страницы 63–70, Дрезден, Германия, 2004. Elsevier.
  36. ^ Альдинуччи, М.; Данелутто, М. (2007). «Скелетное параллельное программирование: функциональная и параллельная семантика в одном кадре☆». Компьютерные языки, системы и структуры . 33 (3–4): 179. CiteSeerX   10.1.1.164.368 . дои : 10.1016/j.cl.2006.07.004 .
  37. ^ М. Альдинуччи, М. Данелутто и Дж. Даннвебер. «Методы оптимизации реализации параллельных скелетов в сеточных средах». В С. Горлач, редактор Proc. CMPP: Международный. Семинар по конструктивным методам параллельного программирования, страницы 35–47, Стерлинг, Шотландия, Великобритания, июль 2004 г. Университет Мюнстера, Германия.
  38. ^ М. Данелутто . Эффективная поддержка скелетов в кластерах рабочих станций. Письма о параллельной обработке, 11(1):41–56, 2001 г.
  39. ^ М. Данелутто. «Динамическая поддержка скелетов во время выполнения». Технический отчет, 1999 г.
  40. ^ М. Данелутто. «QOS в параллельном программировании через менеджеры приложений». В PDP '05: Материалы 13-й конференции Euromicro по параллельной, распределенной и сетевой обработке (PDP'05), страницы 282–289, Вашингтон, округ Колумбия, США, 2005. Компьютерное общество IEEE.
  41. ^ М. Альдинуччи и М. Данелутто. «Цена безопасности скелетных систем». У П. Д'Амбры и М. Р. Гуаррачино, редакторов Proc. международного Euromicro PDP 2007: Параллельная распределенная и сетевая обработка, страницы 213–220, Неаполь, Италия, февраль 2007 г. IEEE.
  42. ^ М. Альдинуччи и М. Данелутто. «Защита скелетных систем с ограниченным снижением производительности: опыт мускулов». Журнал системной архитектуры, 2008.
  43. ^ М. Данелутто и П. Дацци. «Среда Java/Jini, поддерживающая потоковые параллельные вычисления». В Proc. международного PARCO 2005: Параллельные вычисления, сентябрь 2005 г.
  44. ^ М. Данелутто и П. Дацци. «Совместное использование структурированного/неструктурированного параллелизма посредством потока данных». В. Александров, Д. ван Альбада, П. Слоот и Дж. Донгарра, редакторы Proc. ICCS: Международная конференция по вычислительной технике, семинар по практическим аспектам параллельного программирования высокого уровня, LNCS, Ридинг, Великобритания, май 2006 г. Springer Verlag.
  45. ^ М. Альдинуччи, М. Данелутто и П. Дацци. «Маскель: расширяемая скелетная среда». Масштабируемые вычисления: практика и опыт, 8(4):325–341, декабрь 2007 г.
  46. ^ Э. Альба, Ф. Алмейда, М. Дж. Блеса, Х. Кабеса, К. Котта, М. Диас, И. Дорта, Х. Габарро, К. Леон, Х. Луна, Л. М. Морено, К. Паблос, Х. Пети , А. Рохас и Ф. Джафа. « Мальба: библиотека скелетов для комбинаторной оптимизации (исследовательская записка) ». В Euro-Par '02: Материалы 8-й Международной конференции Euro-Par по параллельной обработке, страницы 927–932, Лондон, Великобритания, 2002. Springer Verlag.
  47. ^ Э. Альба, Ф. Алмейда, М. Блеса, К. Котта, М. Диас, И. Дорта, Х. Габарро, К. Леон, Г. Люке, Ж. Пети, К. Родригес, А. Рохас и Ф. Джафа. Эффективные параллельные алгоритмы Land/One для оптимизации: проект mallba. Параллельные вычисления, 32(5):415–440, 2006.
  48. ^ Э. Альба, Г. Луке, Х. Гарсиа-Ньето, Г. Ордонес и Г. Легуисамон. «Mallba — библиотека программного обеспечения для разработки эффективных алгоритмов оптимизации». Международный журнал инновационных вычислений и приложений, 1 (1): 74–85, 2007.
  49. ^ «Рикардо Маркес, Эрве Паулино, Фернандо Александре, Педро Д. Медейрос». «Алгоритмическая скелетная структура для оркестровки вычислений на графическом процессоре». Европар 2013: 874–885.
  50. ^ «Фернандо Александре, Рикардо Маркес, Эрве Паулино». «О поддержке алгоритмических скелетов с параллельным выполнением задач для вычислений с несколькими графическими процессорами». 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. ^ Баччи, Б.; Данелутто, М.; Орландо, С.; Пелагатти, С.; Ваннески, М. (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. Университет. Пассау, Германия, май 1998 г.
  67. ^ Б. Баччи, М. Данелутто, С. Пелагатти и М. Ваннески. «Skie: гетерогенная среда для приложений HPC». Параллельные вычисления, 25 (13–14): 1827–1852, 1999.
  68. ^ М. Данелутто и М. Стильяни. «Skelib: Параллельное программирование со скелетами на C». В Euro-Par '00: Материалы 6-й Международной конференции Euro-Par по параллельной обработке, страницы 1175–1184, Лондон, Великобритания, 2000. Springer-Verlag.
  69. ^ Д. Госвами, А. Сингх и Б. Р. Прейсс. «От шаблонов проектирования к параллельным архитектурным скелетам». Дж. Параллельное распределение. Comput., 62(4):669–695, 2002. doi:10.1006/jpdc.2001.1809.
  70. ^ Д. Госвами, А. Сингх и Б. Р. Прейсс. «Использование объектно-ориентированных методов для реализации параллельных архитектурных скелетов». В ISCOPE '99: Материалы третьего международного симпозиума по вычислениям в объектно-ориентированных параллельных средах, конспекты лекций по информатике, страницы 130–141, Лондон, Великобритания, 1999. Springer-Verlag.
  71. ^ М. М. Акон, Д. Госвами и Х. Ф. Ли. «Superpas: параллельная модель архитектурного скелета, поддерживающая расширяемость и композицию скелета». В книге «Параллельная и распределенная обработка и приложения», Второй международный симпозиум, ISPA, конспекты лекций по информатике, страницы 985–996. Спрингер-Верлаг, 2004.
  72. ^ М. М. Акон, А. Сингх, Д. Госвами и Х. Ф. Ли. «Расширяемые параллельные архитектурные скелеты». В журнале High Performance Computing HiPC 2005, 12-я Международная конференция, том 3769 конспектов лекций по информатике, страницы 290–301, Гоа, Индия, декабрь 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. Спрингер-Верлаг, 2006.
  77. ^ Дж. Дарлингтон, Ю. Кэ Го, Х.В. То и Дж. Ян. «Параллельные скелетоны для структурированной композиции». В PPOPP '95: Материалы пятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, страницы 19–28, Нью-Йорк, Нью-Йорк, США, 1995. ACM.
  78. ^ Джон Дарлинтон; Мустафа Ганем; Йике Го; Хинг Винг То (1996), «Управляемая организация ресурсов в гетерогенных параллельных вычислениях», Журнал высокопроизводительных вычислений , 4 (1): 13–23, CiteSeerX   10.1.1.37.4309
  79. ^ «СкеПУ» .
  80. ^ Дж. Серо, Д. Жинак и Дж. Дерутин. «SKiPPER: скелетонизированная среда параллельного программирования для приложений обработки изображений в реальном времени». В. Малышкин, редактор, 5-я Международная конференция по параллельным вычислительным технологиям (PaCT-99), том 1662 LNCS, страницы 296–305. Спрингер, 6–10 сентября 1999 г.
  81. ^ Дж. Серот и Д. Жинак. «Скелеты для параллельной обработки изображений: обзор проекта SKiPPER». Параллельные вычисления, 28(12):1785–1808, декабрь 2002 г.
  82. ^ Ж. Фальку, Ж. Серо, Т. Шато и Ж. Т. Лапрест. «Quaff: эффективный проект C++ для параллельных скелетов». Параллельные вычисления, 32(7):604–615, 2006.
  83. ^ Ж. Фальку и Ж. Серо. «Формальная семантика, применяемая к реализации библиотеки параллельного программирования на основе скелета». Г. Р. Жубер, К. Бишоф, Ф. Дж. Петерс, Т. Липперт, М. Бкер, П. Гиббон ​​и Б. Мор, редакторы, «Параллельные вычисления: архитектуры, алгоритмы и приложения» (Proc. of PARCO 2007, Юлих, Германия), том 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. ^ К. Мацузаки, К. Какехи, Х. Ивасаки, З. Ху и Ю. Акаши. «Библиотека скелетов, встроенная в Fusion». В М. Данелутто, М. Ваннески и Д. Лафоренце, редакторах, Euro-Par, том 3149 конспектов лекций по информатике, страницы 644–653. Спрингер, 2004.
  90. ^ Г. Х. Боторог и Х. Кучен. «Эффективное параллельное программирование высокого уровня». Теор. Вычислить. Sci., 196(1–2):71–107, 1998.
  91. ^ Зандифар, Мани; Абдулджаббар, Мустафа; Маджиди, Алиреза; Киз, Дэвид; Амато, Нэнси; Раухвергер, Лоуренс (2015). «Составление алгоритмических скелетов для реализации высокопроизводительных научных приложений». Материалы 29-й Международной конференции ACM по суперкомпьютерам . стр. 415–424. дои : 10.1145/2751205.2751241 . ISBN  9781450335591 . S2CID   13764901 .
  92. ^ Зандифар, Мани; Томас, Натан; Амато, Нэнси М.; Раухвергер, Лоуренс (15 сентября 2014 г.). Бродман, Джеймс; Ту, Пэн (ред.). Языки и компиляторы для параллельных вычислений . Конспекты лекций по информатике. Международное издательство Спрингер. стр. 176–190. дои : 10.1007/978-3-319-17473-0_12 . ISBN  9783319174723 .
  93. ^ "Г. Танасе и др." Продолжается работа «STAPL Parallel Container Framework» PPoPP '11 Материалы 16-го симпозиума ACM по принципам и практике параллельного программирования Страницы 235–246.
  94. ^ Дж. Дарлингтон, Эй Джей Филд, П.Г. Харрисон, П.Х.Дж. Келли, ДУН Шарп и К. Ву. «Параллельное программирование с использованием скелетных функций». В PARLE '93: Материалы 5-й Международной конференции PARLE по параллельным архитектурам и языкам в Европе, страницы 146–160, Лондон, Великобритания, 1993. Springer-Verlag.
  95. ^ Дж. Дарлинтон; М. Ганем; HW To (1993), «Структурированное параллельное программирование», В моделях программирования для компьютеров с массовым параллелизмом. Издательство Компьютерного общества IEEE. 1993 : 160–169, CiteSeerX   10.1.1.37.4610 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithmic_skeleton&oldid=1190792141"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 65e2fd40b69134e5144917fc436de2d8__1703012100
URL1:https://arc.ask3.ru/arc/aa/65/d8/65e2fd40b69134e5144917fc436de2d8.html
Заголовок, (Title) документа по адресу, URL1:
Algorithmic skeleton - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)