Высокопроизводительное программирование

Рассмотрим один из известных ЯП – функциональный язык параллель- ного программирования SISAL.

Название языка расшифровывается как «Streams and Iterations in a Single Assignment Language», сам он представляет собой дальнейшее развития языка VAL, известного в середине 1970-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функцио- нальным стилем программирования:

– создание универсального функционального языка;

– разработка техники оптимизации для высокоэффективных параллель- ных программ;

– достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C;

– внедрение функционального стиля программирования для больших научных программ.

Эти цели создателей языка SISAL подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочных эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальное окружение. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления. Легко создать функциональную программу, которая безусловно является параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь языка SISAL получает возможность сконцентрироваться на конструировании

 

 

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

Параллельное программирование на языке Sisal опирается на парадигму функционального программирования. Но замысел языка нацелен на создание конкуренции вечно живому языку Fortran и, кроме того, в качестве базового языка был использован язык VAL, в свою очередь многое унаследовавший от языка Pascal. От языка Fortran унаследован ряд идей по обработке и пред- ставлению векторов.

Система вычислений в языке Sisal использует понятие «мультизначение», позволяющее подобно языку APL распространять скалярные действия на данные любой структуры, а их обработку осуществлять на многопроцессор- ных конфигурациях. Работа с именованной памятью (Name-oriented) осво- бождена от проблем с побочными эффектами с помощью локализации участ- ков с однократными присваиваниями – SSA-форм, что делает программы удобными для преобразований, оптимизации и компиляции, включая распа- раллеливание и масштабирование. Отображение значений при информаци- онной обработке рассматривается как исполняемое на многопроцессорных конфигурациях. Результаты отображения могут повергнуться свертке или фильтрации. Формирование конфигурации управляется представлением про- странства итераций и учетом зависимостей между одноуровневыми итераци- ями. Программа строится из участков с однократными присваиваниями, что упрощает технику оптимизационных и распараллеливающих оптимизаций.

Основное продвижение по технике программирования – развитие струк- туры циклов для их реализации на параллельных архитектурах. Введено по- нятие «пространство итераций» и предложена специальная конструкция для фильтрации мультизначений, получаемых при совмещенном исполнении итераций и участков повторяемости.

Основные виды команд:

– обработка потоков (очередь =стек= список);

– контроль однократности присваиваний (SSA-формы);

– дополнение цикла участком «returns» для оформления значения распа- раллеленного цикла;

– формирование пространство итераций;

– канальный обмен между итерациями;

– операции по упаковке, свертке или фильтрации серийных значений.

 

 

Фрагмент	Пояснение
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	% выбор и вычисление результата цикла

Пример 61. Вычисление числа π (пи)

 

Фрагмент	Пояснение
for i in [1..Cycles/2]   do val:= 1.0/real(4*i-3) – 1.0/real(4*i-1); returns sum(val) end for * 4.0	% пространство параллельно исполнимых итераций % тело цикла, для каждого i исполняется независимо % выбор и свертка результатов всех итераций цикла % вычисление результата выражения

Пример 62. Это выражение также вычисляет число π (пи). Это выражение вычисляет сумму всех вычисленных значений val и умножает результат на 4.0

 

Фрагмент	Пояснение
for i in [1..2] dot j in [3..4] do returns product (i+j) end for	% для пар индексов [1,3] и [2,4] % произведение сумм % = 24

Пример 63. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования

 

Фрагмент	Пояснение
for i in [1..2] cross j in [3..4] do returns product (i+j) end for	% для пар [1,3], [1,4], [2,3] и [2,4] % произведение сумм % = 600

Пример 64. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования

 

Фрагмент	Пояснение
for I:= 1 while I < S do K:= I; I:= old I + 2; J:= K + I; returns product(I+J) end for	% значение из предыдущей итерации

Пример 65. Итеративное for-выражение с обменом данными между итерациями

 

Как это свойственно языкам функционального программирования, SISAL язык математически правильный – функции отображают аргументы в резуль- таты без побочных эффектов, и программа строится как выражение, выраба- тывающее значение. Наиболее интересна форма параллельного цикла. Она выделяет три части: for – генератор пространства итераций, do – тело цикла и returns – формирователь возвращаемых значений.

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

 

Фрагмент	Пояснение
function Sum (N); result (+ (sqw (1.. N)));	% Сумма квадратов

 

Пример 66. Сумма квадратов

 

Для ЯСВУ характерна яркая специфика, связанная с поиском новых средств и методов программирования. Такая специфика может стать основой новой парадигмы.

Ряд ЯВУ, такие как Fortran, Lisp, Algol, Apl, Pascal, используются как ба- зовые при создании новых ЯВУ и ЯСВУ, что позволяет формулировать от- носительные парадигматические характеристики в лаконичной и легко вос- принимаемой форме.

 

 

Абстрактный комплекс

Операционная семантика языка программирования обычно базируется на определении абстрактной машины, которая в случае многопроцессорных кон- фигураций естественно становится конструкцией из абстрактных процессоров

– абстрактным комплексом (АК). В основном определение команд абстракт- ной машины наследует решения SECD-машины, предложенные Лэндиным и описанные в книге Хэндерсона. Для языка параллельного программирования такой комплекс можно определить следующим образом:

АМ = <Регистры, [АП-1, … АП-n], СК> АП-i = <Пам-i, СК-i>

Регистры = < стек результатов, структура общего контекста,

синхросеть потоков/процессоров (активных и пассивных), очередь барьеров>

СК – система команд, включающая в себя универсальные для всех про- цессоров команды, типичные для языков управления заданиями.

Появляется пересмотр ряда понятий, а именно переход от АМ к абстракт- ному комплексу (АК):

 

АК = <P, R, B, D>, где

P – вектор процессоров;

R – список внешних результатов вычислений;

B – таблица синхронизованных потоков, ждущих достижения барьера другими потоками;

D – набор пассивных потоков.

Элементы P – вектора процессоров содержат номер активного потока, те- кущий результат его выполнения и собственно список его предстоящих дей- ствий (фрагментов):

 

P = <i, s, c>, где

 

i – уникальный номер потока, выполняемого на процессоре P; s – стек текущих результатов i-го потока;

c – список действий i-го потока.

 

Определена частичная функция T(i), задающая ограничение времени вы- полнения потока P(i).

 

 

Общая система команд АК поддерживает выполнение следующих дей- ствий:

LOAD – загрузка произвольного пассивного потока; F-LOAD – загрузка заданного пассивного потока;

BAR – статическая синхронизация потоков по барьерам; IF – фильтр по заданному предикату;

WHEN – ожидание истинности предиката; FORK – развилка;

JOIN – слияние ветвей;

SEND – динамическая синхронизация активных потоков в стиле «ран- деву»;

WAIT – ожидание сообщения; MASSAGE – получение сообщения;

KILL – принудительное отключение потока с диагностическим сообще- нием;

STOP – плановое завершение работы потока с формированием внешнего результата.

Нормальное завершение многопоточной программы происходит при ис- черпании регистров B и D и плановом завершении всех активных потоков.

Кроме того, общее завершение работы происходит при невозможности завершить работу каких-либо потоков регистра B – взаимоблокировки.

Для простоты учебной модели здесь не рассматривается учет разнообразия категорий систем команд отдельных процессоров и видов используемой памяти с различной дисциплиной функционирования. Ради удобочитаемости общие ко- манды АК представлены в виде системы переходов:

 

[i s c,...] R B D → [i' s' c', …] R' B' D'

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

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

 

 

подстановка), но с контролем соответствия параметров объявленным син- таксическим типам фрагментов. В новых языках программирования, поддер- живающих параллелизм, таких как императивный C# и функциональный F#, имеется возможность манипулировать структурами данных, представляю- щими внутренний код программы.

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

 

Многоуровневая память

На уровне первичного элементарного программирования мало заметна принципиальная разница между хранением данных в оперативной и внешней памяти. Особенности работы с внешней памятью много детальнее изучены в практике организации реляционных баз данных (БД) и применения языка за- просов к базам данных SQL.

Характерной особенностью хранимой в БД информации является ее соот- ветствие некоторым физическим параметрам реальных объектов. Такие па- раметры относительно одного объекта можно представлять в виде строки таблицы. Существуют системы управления базами данных (СУБД), обеспе- чивающие создание, долговременной хранение, использование и уточнение таких таблиц.

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

Уровни архитектуры:

– внутренний (организация хранения);

– внешний (логика использования);

– промежуточный (концепции системы).

 

 

Важным достижением реализационного похода в этом направлении явля- ется понятие нормальных форм (НФ), дающее разработчику БД четкое руко- водство по прогнозу эффективности принятых им решений. Число таких форм немного превышает десяток. Соответствие нормальной форме опреде- ляет выбор схемы реализации БД, компактность и структуру хранения дан- ных во внешней памяти и скорость доступа к хранимым данным. Причем во многих случаях повышение компактности хранения сопровождается повы- шением скорости доступа, опровергая расхожее утверждение, что выигрыш в памяти влечет потери в скорости и наоборот. Нормальные формы образуют упорядоченную последовательность – очередная последовательность насле- дует свойства предыдущей. Такая методика может помочь упорядочению разнообразия моделей параллельных вычислений. Нормализованные формы могут отражать конкретные модели, гарантирующие определенные свойства процессов, порождаемых по программам.

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