ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
. Название языка расшифровывается как «Streams and Iterations in a Single Assignment Language», сам он представляет собой дальнейшее развития языка VAL, известного в середине 70-х годов. Среди целей разработки языка SISAL следует отметить наиболее характерные, связанные с функциональным стилем программирования: – создание универсального функционального языка; – разработка техники оптимизации для высокоэффективных параллельных программ; – достижение эффективности исполнения, сравнимой с императивными языками типа Fortran и C; – внедрение функционального стиля программирования для больших научных программ. Эти цели создателей языка SISAL подтверждают, что функциональные языки способствуют разработке корректных параллельных программ. Одна из причин заключается в том, что функциональные программы свободны от побочных эффектов и ошибок, зависящих от реального времени. Это существенно снижает сложность отладки. Результаты переносимы на разные архитектуры, операционные системы или инструментальное окружение. В отличие от императивных языков, функциональные языки уменьшают нагрузку на кодирование, в них проще анализировать информационные потоки и схемы управления. Легко создать функциональную программу, которая безусловно является параллельной, если ее можно писать, освободившись от большинства сложностей параллельного программирования, связанных с выражением частичных отношений порядка между отдельными операциями уровня аппаратуры. Пользователь языка SISAL получает возможность сконцентрироваться на конструировании алгоритмов и раз работке программ в терминах крупноблочных и регулярно организованных 187 построений, опираясь на естественный параллелизм уровня постановки задачи. Параллельное программирование на языке Sisal опирается на парадигму функционального программирования. Но замысел языка нацелен на создание конкуренции вечно живому языку Fortran и, кроме того, в качестве базового языка был использован язык VAL, в свою очередь многое унаследовавший от языка Pascal. От языка Fortran унаследован ряд идей по обработке и представлению векторов. Система вычислений в языке Sisal использует понятие «мультизначение», позволяющее подобно языку APL распространять скалярные действия на данные любой структуры, а их обработку осуществлять на многопроцессорных конфигурациях. Работа с именованной памятью (Name-oriented) освобождена от проблем с побочными эффектами с помощью локализации участков с однократными присваиваниями – SSA-форм, что делает программы удобными для преобразований, оптимизации и компиляции, включая распараллеливание и масштабирование. Отображение значений при информационной обработке рассматривается как исполняемое на многопроцессорных конфигурациях. Результаты отображения могут повергнуться свертке или фильтрации. Формирование конфигурации управляется представлением пространства итераций и учетом зависимостей между одноуровневыми итерациями. Программа строится из участков с однократными присваиваниями, что упрощает технику оптимизационных и распараллеливающих оптимизаций. Основное продвижение по технике программирования – развитие структуры циклов для их реализации на параллельных архитектурах. Введено понятие «пространство итераций» и предложена специальная конструкция для фильтрации мультизначений, получаемых при совмещенном исполнении итераций и участков повторяемости. Основные виды команд: – обработка потоков (очередь =стек= список); – контроль однократности присваиваний (SSA-формы); – дополнение цикла участком «returns» для оформления значения распараллеленного цикла; – формирование пространство итераций; – канальный обмен между итерациями; – операции по упаковке, свѐртке или фильтрации серийных значений. 188 Фрагмент Пояснение 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 % инициирование цикла % предусловие завершения цикла % однократные % присваивания % образуют % тело цикла % выбор и вычисление результата цикла Пример 57. Вычисление числа π (пи) Фрагмент Пояснение 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 исполняется независимо % выбор и свертка результатов всех итераций цикла % вычисление результата выражения Пример 58. Это выражение также вычисляет число π (пи). Это выражение вычисляет сумму всех вычисленных значений 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 Пример 59. В for-выражениях операции dot и cross могут порождать пары индексов при формировании пространства итерирования Фрагмент Пояснение for i in [1..2] cross j in [3..4] do % для пар [1,3], [1,4], [2,3] и [2,4] 189 returns product (i+j) end for % произведение сумм % = 600 Пример 60. В 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 % значение из предыдущей итерации Пример 61. Итеративное for-выражение с обменом данными между итерациями Как это свойственно языкам функционального программирования, SISAL язык математически правильный – функции отображают аргументы в результаты без побочных эффектов, и программа строится как выражение, вырабатывающее значение. Наиболее интересна форма параллельного цикла. Она выделяет три части: for - генератор пространства итераций, do - тело цикла и returns - формирователь возвращаемых значений. SISAL-программа представляет собой набор функций, допускающих частичное применение, т. е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений. Фрагмент Пояснение function Sum (N); result (+ ( sqw (1 .. N))); % Сумма квадратов Пример 62. Сумма квадратов 190 Для ЯСВУ характерна яркая специфика, связанная с поиском новых средств и методов программирования. Такая специфика может стать основой новой парадигмы. Ряд ЯВУ, такие как Fortran, Lisp, Algol, Apl, Pascal, используются как базовые при создании новых ЯВУ и ЯСВУ, что позволяет формулировать относительные парадигматические характеристики в лаконичной и легко воспринимаемой форме. 8.7.Трансформационная семантика Трансформационная семантика обеспечивает сведение конструкций языка программирования к его базовым средствам, что позволяет упростить операционную семантику, а также выбрать реализационное ядро системы программирования при его экспериментальной раскрутке. Задача трансформационной семантики – сведение программы к нормализованной форме, удобной для интерпретации программ или генерации масштабируемого исполнимого кода. В случае многопоточных программ преобразование сети потоков может быть нацелено на сведение к однородной системе потоков, однозначно отображаемых на заданный комплекс процессоров – размещение потоков по процессам или назначение процессоров для выполнения потоков. В такой «причесанной» форме все потоки начинаются с барьеров, и общая шкала событий упорядочена так, что последовательность событий потока ей не противоречит. Можно считать, что процессоры включаются сами. Шкала событий содержит списки ожидающих потоков. Действия, выполняемые процессорами, соотнесены с их исходными потоками. Обратимость преобразований и чувствительность их результата к информационным связям между фрагментами программы требуют формализации критериев применимости трансформаций и выбора подходящего варианта. При отладке формируется ряд контекстов, на которых демонстрируются отдельные свойства фрагментов, из которых собирается полная программа. Это контексты для отдельных потоков, для пар синхронизованных потоков, для интегрированной из потоков программы, а кроме того контексты для удостоверения наличия-отсутствия информационных связей между фрагментами. Возможны пользовательские преобразования схем управления процессами, что позволит не только минимизировать «ручную» оранжировку распараллеливаемых программ, но и даст основу для формирования библиотек преобразования схем программ. Теоретически 191 такие преобразования следует сопровождать доказательствами частичной эквивалентности для понимания границ их применимости. На этом фоне задача трансформационной семантики языка параллельного программирования – сведение программы к нормализованной форме, удобной для интерпретации программ, их распараллеливания и генерации настраиваемого объектного кода. Похожая техника применяется при сведении грамматик языка к удобной для автоматизации построения анализатора форме и при оптимизации программ. Направление преобразований программ обычно связано с определенными критериями применимости и оптимальности, учитывающими результаты анализа логических и информационных связей. При организации параллельных процессов такие критерии обладают спецификой, отражающей особенности эксплуатации многоядерных архитектур. В частности, возрастает роль учета времени доступа к разнородной памяти и статического планирования загрузки процессоров наряду с обеспечением обратимости обработки данных и динамического управления производительностью вычислений. Поддержка такой семантики вычислений выходит за границы традиционных решений по реализации языков высокого уровня. При декомпозиции трансформационной семантики языка параллельного программирования возникает коллекция нормализованных функциональных моделей отдельных аспектов управления процессами. Нормализация моделей направлена на ограничение сложности их анализа, приспособленность к интеграции с другими моделями, поддержку быстрого прототипирования многопоточных программ, верификацию различных свойств программных систем и их факторизацию в процессе разработки и усовершенствования. Такие механизмы могут быть включены в систему параллельного программирования. Необходимость согласования большого числа разноплановых факторов приводит к многослойному описанию семантики языков параллельного программирования (ЯПП), в котором разделены уровни абстрактных схем управления вычислениями и наполнения схем конкретными вычислениями. Чтобы избежать повторной компиляции при согласовании выбора схемы управления с целевой архитектурой, при формировании внутреннего представления многопоточных программ обычно используются методы смешанных вычислений и техника макрогенерации. Практичность таких методов обуславливается вполне конкретными, не редко диктуемыми аппаратурой, требованиями к фрагментам наполнения, связанными с целесообразностью достижения конечности отладки фрагментов 192 (целостность действий, однократность присваиваний, одномерные вектора, функции без рекурсии, циклы со статически определенной кратностью, потоки действий, выполняемых по готовности данных – как при вычислении арифметических выражений). 8.8. Абстрактный комплекс Операционная семантика языка программирования обычно базируется на определении абстрактной машины, которая в случае многопроцессорных конфигураций естественно становится конструкцией из абстрактных процессоров – абстрактным комплексом (АК). В основном определение команд абстрактной машины наследует решения SECD- машины, предложенные Лэндиным и описанные в книге Хэндерсона. Для языка параллельного программирования такой комплекс можно определить следующим образом: АМ = <Регистры, [АП-1, … АП-n], СК> АП-i = <Пам-i, СК-i> Регистры = < стек результатов, структура общего контекста, синхросеть потоков/процессоров (активных и пассивных), очередь барьеров> СК – система команд, включающая в себя универсальные для всех процессоров команды, типичные для языков управления заданиями. Появляется пересмотр ряда понятий, а именно переход от АМ к абстрактному комплексу (АК): АК = , где P – вектор процессоров, R – список внешних результатов вычислений, B – таблица синхронизованных потоков, ждущих достижения барьера другими потоками, D – набор пассивных потоков. Элементы P – вектора процессоров содержат номер активного потока, текущий результат его выполнения и собственно список его предстоящих действий (фрагментов): P = 193 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' Естественно, на уровне абстрактной машины поддержаны обычные бинарные операции над данными и дополнительные операции локального управления процессами, возникающие при реализации системы программирования. Определение синхронизации циклов и рекурсий может 194 быть представлено в терминах индексируемых барьеров. Динамическая синхронизация в стиле ООП несложно выражается с помощью дополнительного регистра для реализации канала обмена сообщениями. Наполнение многопоточной программы может развиваться независимо от схем управления вычислениями в отдельных потоках, а схемы можно реорганизовывать без дополнительной отладки наполнения. Они играют роль макетов или моделей программ и работают подобно макросам (открытая подстановка), но с контролем соответствия параметров объявленным синтаксическим типам фрагментов. В новых языках программирования, поддерживающих параллелизм, таких как императивный C# и функциональный F#, имеется возможность манипулировать структурами данных, представляющими внутренний код программы. Выделение схемного уровня упрощает включение в схему разработки программ механизмов верификации (подобие модели или соответствие аксиомам), а на их основе возможна проверка программ на правдоподобие, логический вывод свойств, выполнение индуктивных и дедуктивных построений. Кроме того, техника отладки программ обогащается возможностью привлечения протоколов ранее выполненных вычислений и приведения программ к нормальным формам, удобным для сведения к базовым/стандартным моделям параллельных вычислений. 8.9. Память На уровне первичного элементарного программирования мало заметна принципиальная разница между хранением данных в оперативной и внешней памяти. Особенности работы с внешней памятью много детальнее изучены в практике организации реляционных баз данных (БД) и применения языка запросов к базам данных SQL. Характерной особенностью хранимых в БД данных является их соответствие некоторым физическим параметрам реальных объектов. Такие параметры относительно одного объекта можно представлять в виде строки таблицы. Существуют системы управления базами данных (СУБД), обеспечивающие создание, долговременной хранение, использование и уточнение таких таблиц. В использовании конкретных таблиц может быть заинтересовано множество пользователей для разных сфер применения. Хранение таблиц может быть организовано на базе различных устройств и файловых систем и доступ к ним может реализовываться с помощью различных дисциплин коммуникации. Для обеспечения эффективности использования 195 аппаратуры и необходимого для практичности пользовательского интерфейса разработаны определѐнные системные решения, что суммарно приводит к трѐм уровням проектирования архитектуры БД. Уровни архитектуры: – внутренний (организация хранения); – внешний (логика использования); – промежуточный (концепции системы). Важным достижением реализационного похода в этом направлении является понятие нормальных форм (НФ), дающее разработчику БД чѐткое руководство по прогнозу эффективности принятых им решений. Число таких форм немного превышает десяток. Соответствие нормальной форме определяет выбор схемы реализации БД, компактность и структуру хранения данных во внешней памяти и скорость доступа к хранимым данным. Причѐм во многих случаях повышение компактности хранения сопровождается повышением скорости доступа, опровергая расхожее утверждение, что выигрыш в памяти влечѐт потери в скорости и наоборот. Нормальные формы образуют упорядоченную последовательность – очередная последовательность наследует свойства предыдущей. Полноценное решение проблем параллельного программирования требует создания более специализированного инструментария, некоторые механизмы реализации которого могут быть изучены в форме экспериментальной разработки учебного языка параллельного программирования. 196 ЗАКЛЮЧЕНИЕ Выбор парадигмы программирования – это выбор концептуальной схемы постановки проблем и методов их решения, инструмент «грамотного» описания фактов, событий, явлений и процессов, выделения частных и общих понятий. Альтернативные подходы к обработке информации, накопленные и сложившиеся в форме языков и систем программирования, принято называть парадигмами программирования. Изучение и чѐткая классификация уже сложившихся и новых компьютерных парадигм призваны помочь обоснованному выбору компьютерных языков при формировании новых программных проектов и создании новых информационных технологий. Естественная классификация по ѐмкости абстрагирования конструкций, выделяющая ЯП низкого, высокого и сверхвысокого уровня, дополняется определением парадигм, поддерживаемых ЯСП. В настоящее время число по существу различимо более двух десятков парадигм. Многие языки программирования относят к пяти - восьми парадигмам. Часть упоминаемых в разных источниках ПП можно характеризовать как стили или методики, отражающие поиск путей снижения трудоѐмкости программирования и повышения надѐжности программ на базе доступных СП. Например, аспектно-ориентированное программирование поддерживается как макро-расширение ООП. Структурное программирование фактически сводится к ряду рекомендаций по стилю представления императивно-процедурных программ. Мета- программирование представляет собой технику компиляции программ в комплекте с типовыми элементами данных. Недетерминированное программирование не более чем частный случай параллелизма. При определении ПП обычно поляризуются следующие характеристики ЯП: – программируемые решения представляются в императивной или в декларативной форме; – обрабатываемые элементы данных позиционируются как адресуемые блоки памяти или независимо размещаемые значения; – программа может быть защищена от изменений в процессе еѐ выполнения или допускать программируемые модификации по ходу получения результатов вычисления; 197 – программа может быть целостной или собираться из типовых компонент и шаблонов; – представленные в программе функции могут быть частичными, типизированными, обрабатывающими значения заданного домена или универсальными, дающими разумную реакцию на любой элемент данных; – управления вычислениями выполняется последовательно или параллельно; – порядок действий может быть определѐнным или недетерминированным; – вычисления могут быть энергичными или ленивыми; – области видимости имѐн могут быть глобальными или локализованными по иерархии конструкций с возможностью восстановления контекста; – распределение и повторное использование памяти может быть действием в программе или выполняться автоматически СП; – инициирование памяти первоначально размещаемыми значениями может требовать программируемых действий или выполняться в СП по умолчанию; – домены значений могут быть независимыми или допускать пересечения; – результат выполнения программы может быть рассредоточен по ряду переменных или сконцентрирован в специальном регистре; – контроль правильности может выполняться статически – при анализе текста программы или динамически – при выполнении кода программы. Выбор между так противопоставленными характеристиками в представлении программы выражается синтаксически или с помощью спецификаторов. В практике программирования признаны основными парадигмы императивно-процедурного, функционального, логического и объектно-ориентированного программирований, поддерживающие механизмы снижения трудоѐмкости полного жизненного цикла программ с тенденцией продвижений к параллельному программированию. При оценке образовательного значения ПП выделяют в качестве базовых функциональное, параллельное и императивно-процедурное программиро- вания, а логическое и ООП рассматривают как дополнение, изучаемое в виде расширения базовых парадигм. Мультипарадигматичность долго живущих ЯП и тенденция создания новых мультипарадигматических ЯП |