В вычислительной технике алгоритмические скелеты или шаблоны параллелизма представляют собой высокоуровневую модель параллельного программирования для параллельных и распределенных вычислений.
Алгоритмические скелеты используют общие шаблоны программирования, чтобы скрыть сложность параллельных и распределенных приложений. Начиная с базового набора паттернов (скелетонов), можно строить более сложные паттерны, комбинируя базовые.
Самая выдающаяся особенность алгоритмических скелетов, которая отличает их от других высокоуровневых моделей параллельного программирования, заключается в том, что оркестровка и синхронизация параллельных действий неявно определяются шаблонами каркаса. Программистам не нужно указывать синхронизацию между последовательными частями приложения. Отсюда два следствия. Во-первых, поскольку шаблоны связи/доступа к данным известны заранее, модели затрат могут применяться для составления расписания программ. [1] Во-вторых, алгоритмическое скелетное программирование снижает количество ошибок по сравнению с традиционными моделями параллельного программирования более низкого уровня (Threads, MPI).
Цель состоит в том, чтобы реализовать основанную на алгоритмическом скелете параллельную версию алгоритма быстрой сортировки с использованием шаблона «разделяй и властвуй». Обратите внимание, что высокоуровневый подход скрывает управление потоками от программиста.
Класс ShouldSplit реализует интерфейс Condition. Функция получает входные данные, в данном случае Range r, и возвращает значение true или false. В контексте «Разделяй и властвуй», где будет использоваться эта функция, она будет решать, следует ли снова разделить подмассив или нет.
Класс SplitList реализует интерфейс разделения, который в данном случае делит (под)массив на более мелкие подмассивы. Класс использует вспомогательную функцию partition(...), которая реализует известную схему поворота и подкачки QuickSort.