Асинхронные процессы и параллелизм
Полное представление об асинхронных процессах, их эффективности и проблемах организации дают работы по сетям Петри.
Заметное место среди языков функционального программирования занимают языки организации распределенных и параллельных вычислений. Практики с большой похвалой отзываются о языке функционального программирования Erlang фирмы Ericsson. Здесь мы рассмотрим один из довольно известных — язык функционального программирования SISAL [11].
- создание универсального функционального языка;
- разработка техники оптимизации для высокоэффективных параллельных программ;
- достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C;
- внедрение функционального стиля программирования для больших научных программ.
Название языка расшифровывется как "Streams and Iterations in a Single Assignment Language", сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функциональным стилем программирования:
Эти цели содателей языка SISAL подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочних эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальное окружение. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления. Легко создать функциональную программу, которая является безусловно параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь Sisal-а получает возможность сконцентрироваться на конструировании алгоритмов и раз работке программ в терминах крупноблочных и регулярно организованных построений, опираясь на естественный параллелизм уровня постановки задачи.
Начнем с примера программы:
1. Вычисление числа ? (пи).
For % инициирование цикла Approx := 1.0; Sign := 1.0; Denom := 1.0; i := 1
while i <= Cycles do % предусловие завершения цикла Sign := -Sign; % однократные Denom := Denom + 2.0; % присваивания Approx := Approx + Sign / Denom; % образуют i := i + 1 % тело цикла
returns Approx * 4.0 % выбор и вычисление результата цикла end for
2. Это выражение также вычисляет число ? (пи).
for i in [1..Cycles/2] do % пространство параллельно % исполнимых итераций
val := 1.0/real(4*i-3) — 1.0/real(4*i-1); % тело цикла, для каждого i % исполняемое независимо
returns sum( val ) % выбор и свертка результатов % всех итераций цикла
end for * 4.0 % вычисление результата % выражения
Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0.
3, 4. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования:
for i in [1..2] dot j in [3..4] do % для пар индексов [1,3] и % [2,4] returns product (i+j) % произведение сумм end for % = 24 for i in [1..2] cross j in [3..4] do % для пар [1,3], [1,4], [2,3] % и [2,4] returns product (i+j) % произведение сумм end for % = 600
5. Итеративное for-выражение с обменом данными между итерациями:
for I := 1 while I < S do K := I; I := old I + 2; % значение из предыдущей итерации J := K + I; returns product(I+J) end for
Как это свойственно языкам фукнционального программирования, Sisal язык математически правильный — функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она включает в себя три части: генератор пространства итераций, тело цикла и формирователь возвращаемых значений.
SISAL-программа представляет собой набор функций, допускающих частичное применение, т.е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений.
function Sum (N); % Сумма квадратов result (+ ( sqw (1 .. N)));
Обычно рассматривают оптимизации, обеспечивающие устранение неиспользуемого кода, чистку циклов, слияние общих подвыражений, перенос участков повторяемости для обеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла, втягивание константных вычислений, уменьшение силы операций, удаление копий агрегатных конструкций и др.
