ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Fortran - сопрограммы Средства представления параллельных вычислений доступны, начиная с первых языков высокого уровня. Языки Fortran II и Fortran IV были достаточно универсальны для представления программ организации параллельных процессов. Механизм сопрограмм, допускающий многовходовые (Entry) процедуры, позволял представлять программы взаимодействующих процессов и декомпозировать программу на управляющую и вычисляющую части, выглядящие как независимые компоненты программы, но это не привело к практике параллельного программирования и постепенно сопрограммы превратились модули, обеспечивающие представление иерархии функций подобно иерархии классов в ООП. Синтаксически средства параллельного программирования выглядят в современных Fortran-программах как разметка текста ключевыми словами и вызовы библиотечных функций. Lisp – отложенные вычисления Унификация представления данных и программ позволила пополнить передачу параметров по заранее вычисленному значению или указателю возможностью организовывать передачу представления выражений, вычисление которых можно выполнять по мере необходимости. Такая возможность привела к концепции «ленивых» вычислений и развитию методов динамической оптимизации процессов в отличие от статической оптимизации программ. APL – векторные операции Более удачной оказалась идея поэлементной обработки однородных структур данных в языке APL, особенно с появлением векторных архитектур Cray. В 1962 году был предложен интересный механизм реализации многомерных векторов, приспособленный к расширению и распараллеливанию обработки данных. Сложные данные представляются как пара из последовательности скаляров и паспорта, согласно которому эта последовательность структурируется. Такое решение позволяет любое определение функции над скалярами автоматически распространять на 177 произвольные структуры данных из однотипных скаляров. В настоящее время для большинства специализированных языков параллельного программирования типично, что сложные построения факторизуются с учетом особенностей структуры данных так, что выделяются несложные отображающие функции, "просачиваемые" по структуре данных с помощью функций более высокого порядка – функционалов. В результате можно независимо варьировать структуры данных, функционалы, методы сборки полного результата и набор отображаемых множеств. Целенаправленно выделяются конвейерные процессы, приспособленные к минимизации хранения промежуточных результатов. С 1980-ых годов эта идея наследуется многими языками, поддерживающими параллелизм и в наше время фактически является стандартной. Algol-68 – критические участки и семафоры К концу 1960-х годов сложилось значительное разнообразие теоретических моделей параллелизма, при исследовании которых проявилась проблема надежности параллельных вычислений, выразившаяся в неожиданном различии поведения императивной последовательности действий в зависимости от включаемых в нее фрагментов «независимых» процессов, нарушающих императивность. Для профилактики таких эффектов в семантику языка Algol-68 включается идея непрерывно исполняемых критических участков и представления их защиты в терминах семафоров. Unix и JCL – управление процессами Независимо идеи явного порождения процессов и организации их взаимодействия через каналы возникают в языках управления заданиями и процессами в операционных системах. Setl – множества и кванторы Другой подход к надежности программирования предложен в языке теоретико-множественного программирования Setl, ориентированном на активизацию интуиции грамотных математиков при разработке спецификаций программ в терминах преобразования множеств, естественно подразумевающих возможность параллельной обработки элементов множества, причем в реализационно независимом стиле. Наследование решений из универсальных языков сверх высокого уровня, таких как Setl, абстрагирование данных и процессов в которых приспособлено к гибкому и строгому структурированию, удобно для культивирования доказательных 178 построений в практике параллельного программирования. В этом плане представляет особый интерес эксперимент по развитию теоретико- множественной семантики языка Setl, в котором весьма общее построение формул с кванторами над множествами погружено в обычную схему последовательного управления процессами. Реализация языка Setl характеризуется богатым полиморфизмом. Для представления множеств используется около двадцати разных структур данных, выбор которых осуществляется системой программирования в зависимости от динамики операций над множествами. В результате программируемые функции слабо зависят от реализационной структуры данных. В практике управления процессами используется понимание команд как позиций независимого порождения процессов. Такое понимание естественно согласуется с идеями теории множеств о независимости элементов множеств и может служить основой архитектуро независимой семантики языка программирования. SQL – транзакционная память и нормальные формы Много более заметная проблема параллельной обработки данных независимыми операторами обнаружилась в практике применения общих баз данных, приведшей к выделению языка запросов (SQL) и концепции транзакционной памяти, теперь рассматриваемой как перспективная основа семантики языков параллельного программирования. Occam – взаимодействие «процесс-канал» Середина 1970-х годов характеризуется кризисом технологии программирования, выход из которого тогда виделся в массовом переходе к параллельному программированию. Активные исследования разрешимых классов параллельных схем программ показали ряд неудобных, снижающих эффективность распараллеливания, конструкций, таких как ветвления. Э. Дейкстра опубликовал решение этой проблемы в форме защищенных команд, которая нашла свое место в определении языка Occam,предоставляющем для транспьютерного программирования модель взаимодействия CSP процесс-канал. В эти же годы популяризируются идеи структурного программирования, нацеленные на снижение сложности отладки программ, близкие идеям функционального программирования, которое теперь рассматривается как один из универсальных методов представления удобно распараллеливаемых программ. Ada – «рандеву» В проект языка Ada предпочли включить механизм «рандеву», сводящий представление взаимодействия процессов к рассредоточенному обмену 179 сообщениями, подобному сигналам в оборудовании и модели CCS, что можно рассматривать как приаппаратное низкоуровневое средство, несколько диссонирующее с высоким уровнем языка. БАРС – сетевое управление В нашей стране разработаны языки БАРС и Поляр с разными концепциями сетевого управления процессами и представления дисциплины доступа к памяти. Программирование на уникальном по уровню средств управления процессами языке БАРС нацелено на обеспечение высокопроизводительных вычислений и организацию асинхронных параллельных процессов. При создании языка БАРС в качестве базового ЯВУ был привлечен популярный язык Pascal, в 1970-е годы перераставший из учебного в производственный язык системного программирования. При сохранении основных принципов семантики вычислений были существенно обобщены средства структуризации данных на основе понятия «мультимножество», приспособленного к именованию элементов структур данных и учета кратности их использования. Работа с именованной памятью (Name-oriented) дополнена возможностью задавать дисциплину доступа к элементам памяти. Идеи более ранних языков параллельного программирования были развиты и обогащены в языке БАРС в трех направлениях: – в качестве базовой структуры данных были выбраны мультимножества (размеченные множества с кратностью элементов); – описание элементов памяти сопровождается предписанием дисциплины доступа к памяти; – средства управления асинхронными процессами включали механизм сетей Петри, координирующих работу независимо созданных функциональных фрагментов. Процедуры в таком языке приспособлены к варьированию дисциплины доступа к данным и схемы управления процессами обработки данных. Сети Петри позволяют независимые описания процессов связывать в терминах разметки. Узлы с одинаковой разметкой срабатывают одновременно. Процесс обработки данных рассматривается как распределенная система, находящаяся под сетевым управлением. Узлы такой системы могут сработать в зависимости от условий готовности разной природы: доступность ресурсов, сигналы монитора, внутри сетевые отношения, иерархия сетей, правила функционирования разносортных подсетей. Вычисления, как и в языках APL и Sisal, распространяются со скаляров на сложные структуры. Радикальное продвижение в повышении уровня 180 программирования, предложенное в языке БАРС, заключается в переносе механизма типизации данных на проблему типизации схем управления. Sisal – однократные присваивания и пространства итерирования Авторы строго типизированного функционального языка параллельного программирования Sisal создали интересный прецедент по расширению и уточнению системы понятий программирования для нужд представления и реализации масштабируемых параллельных вычислений. Программа в этом языке строится из участков с однократными присваиваниями, удобными для оптимизирующих преобразований, включая распараллеливание. В структуре цикла выделены позиции для формирования пространства параллельных итераций, фильтрации или сборки параллельно полученных результатов и обработки потоков данных при развитой системе работы с векторами, включая методику распространения скалярных операций на структуры данных. Произошедшее в конце 1970-х годов отвлечение внимания от кризиса технологии программирования на задачу освоения микропроцессоров не остановило поиск языковых решений для представления программ, обладающих параллелизмом. Появился функциональный язык параллельного программирования Sisal, позволяющий формировать пространства итераций для эффективного распараллеливания циклов компилятором. Название языка функционального программирования Sisal расшифровывается как «Streams and Iterations in a Single Assignment Language». Система вычислений в языке Sisal использует понятие «мультизначение», позволяющее подобно языку APL распространять скалярные действия на данные любой структуры, а их обработку осуществлять на многопроцессорных конфигурациях. Отображение мультизначения рассматривается как обработка его элементов на независимых процессорах. Результаты отображения могут повергнуться свертке или фильтрации. Sisal-программа представляет собой набор функций, допускающих частичное применение, т.е. вычисление при неполном наборе аргументов. В таком случае по исходному определению функции строятся его проекции, зависящие от остальных аргументов, что позволяет оперативно использовать эффекты смешанных вычислений и определять специальные оптимизации программ, связанные с разнообразием используемых конструкций и реализационных вариантов параллельных вычислений. Основное продвижение по технике программирования в языке Sisal – развитие структуры циклов для их реализации на параллельных процессорах. Введено понятие «пространство итераций» и предложена 181 специальная конструкция для фильтрации мультизначений, получаемых при совмещенном исполнении итераций и участков повторяемости. Формирование мультизначения управляется представлением пространства итераций и учетом зависимостей между одноуровневыми итерациями. Работа с именованной памятью (Name-oriented) освобождена от проблемы побочных эффектов методом локализации участков с однократными присваиваниями – SSA-форм, что делает программы удобными для преобразований, оптимизации и компиляции, включая распараллеливание и масштабирование. Oberon – обучение управлению процессами 1980-е годы знаменует переход к сетевой обработке данных и признанию потенциала ООП при организации информационных бизнес-процессов. Появляются Oberon, Eiffel, SmallTalk-80, C++, Erlang, Perl и другие языки, отчасти компенсирующие недостаток базовых средств и методов реализации массово используемых императивных языков программирования в новых условиях. В наши дни Вирт позиционирует язык Oberon как кандидат на включение в школьную программу информатики вместо языка Паскаль. Python и Ruby – разработка распределѐнных систем Общий прогресс в эксплуатационных характеристиках оборудования с 1990-х годов резко расширил возможности сборки информационных систем из готовых компонентов и сделал доступными свободно распространяемые программные инструменты конструирования систем программирования, как правило, поддерживающие организацию параллельных процессов, если не собственно на уровне языка, то на уровне библиотечных компонент. Мультипарадигматические языки Python и Ruby показывают хорошие результаты в программировании сетевых процессов для многопроцессорных комплексов и привлекают большое число сторонников. Язык Python зарекомендовал себя как удобное средство разработки распределенных систем и сетевого программирования. Haskell – «ленивые» вычисления и мемоизация Кроме того, существуют сотни функциональных языков программирования, ориентированных на разные классы задач параллельного программирования. Языки функционального программирования обогатились типовыми средствами практически всех известных подходов к представлению программ и организации вычислительного эксперимента и информационных процессов. Обеспечена организация параллельных процессов. Возможна визуализация данных и программ. Имеются средства 182 стандартного и объектно-ориентированного программирования. Поддержано управление компиляцией и конструирование компиляторов. Методы функционального проектирования и программирования обеспечивают технику представления и отладки функциональных моделей, спецификации и верификации программ, исследования их свойств и экспериментального сравнения моделируемых параллельных процессов с моделями и прототипами. Функциональный подход исторически является основой для исследования средств и методов программирования, прототипирования и декомпозиции программируемых систем и развития современных методов параллельного и многоязыкового программирования. Разработан чисто функциональный язык Haskell, предлагающий эффективную модель «ленивых» вычислений с мемоизацией промежуточных результатов по принципу полузабытых методов «математического динамического программирования». Норма – параллельные вычисления Система поддержки параллельного программирования для решения задач вычислительной математики. MPI и Open MP – средства распараллеливания программ Появляются популярные системы MPI и Open MP, обеспечивающие эффективность параллельного программирования в рамках языков Fortran и C. В MPI взаимодействие процессов обеспечивается через посылку сообщений между процессорами. Open MP предоставляет процессам возможность использовать разные виды памяти, включая быструю общую память, что при удачном ее распределении позволяет достигать высокой эффективности. mpC – синхронизация семейств процессоров В мире параллелизма все базовые понятия программирования претерпели изменение или расширение (программа, ветвление, цикл, событие, память, результат). Появился ряд специфических для параллельного программирования понятий (процессор, поток, ожидание, длительность, фильтр, барьер). Программы стали многопоточными, циклы – параллельными, память обретает копии и реплики, события происходят одновременно в разных синхронизуемых процессах, вычисление результата может не означать завершение процесса. Такая ревизия понятий влияет не только на стиль программирования, но и изменяет характер компиляции на этапе генерации кода программы. Возрастает роль техники использования многократно используемых компонент схемного уровня, соответствующего 183 средствам типизации управления процессами. Так, например, язык mpC предлагает более детальный учет механизмов взаимодействия параллельных процессов в терминах барьеров и специальных категорий переменных, обладающих особым, аппаратно реализуемым поведением. Java, C#, Scala, F# – библиотеки управления синхронизацией В новых системах программирования для языков Java, C#, Scala, F# и т.д. существенно повысилась результативность системных решений в области работы с памятью, компиляции, манипулирования комплектами функций и классами объектов, выделение которых по существу обусловлено результатами теоретических работ в области системного статического анализа, основу которых все в большей мере составляет функциональный подход. Получили значительное развитие методы декомпозиции программ в рамках объектно-, субъектно- и аспектно- ориентированных подходов к определению систем программирования на базе многократно используемых компонент. Для современных областей программирования и проектирования характерна интеграция средств и методов из разных парадигм, что может привести к профессиональной консолидации программистского корпуса. Изучаются средства организации параллельных процессов средствами языка функционального программирования F# с библиотеками .Net. На этом языке рассматривается возможность реорганизация программ, что поддержано в языке специальными средствами типа Quotation – доступ к внутреннему представлению программ в виде структуры данных. Анализируется вклад типизации данных в построение эффективных программ. Использование модифицируемой и защищенной памяти. Прикладные аспекты работы с информацией, отражающей специфику области приложения программ (measure). C# дает возможность встраивать функциональные построения в контекст привычных императивных программ. Рассматривается стыковка программ на новых языках с производственными системами, разрабатываемыми на базе библиотек .Net. Возможность оперирования деревом разбора программы и ее исполнимым кодом. Вопросы защиты программ и данных. Управление дисциплиной доступа к памяти и представление запросов к базам данных. CUDA – многопроцессорные видеоплаты Появление технологии CUDA, объединившей в графических ускорителях достоинства этих ранее сложившихся подходов, выводит параллельное программирование в ранг массово доступных методов 184 создания программных систем благодаря преодолению стоимостного барьера. Следует ожидать, что развитие парадигмы параллельного программирования приведет к улучшению средств поддержки полного жизненного цикла программ, включая активное использование методов верификации взаимодействия процессов, автоматизацию приведения обычных программ к эффективно распараллеливаемой форме, обеспечение мобильности параллельных программ относительно параллельных архитектур, а следовательно и к повышению эффективности и надежности программ, приспособленных к многократному использованию типизированных решений особо важных наукоемких задач. На повестке дня – разработка методов архитектурно независимой кодогенерации масштабируемых параллельных программ, легко настраиваемых на особенности используемых вычислительных комплексов. Так, например, новый язык программирования OpenCL обеспечивает параллелизм на уровне инструкций и на уровне данных для различных графических и центральных процессоров. 8.5. Языки сверхвысокого уровня Подготовка программ на базе языков сверхвысокого уровня (ЯСВУ) нацелена на длительный срок жизни запрограммированных решений особо важных и сложных задач. Удлинение жизненного цикла достигается представлением обобщенных решений с определенной степенью свободы по отношению к полным пространствам допустимых смежных компонент, реализованных ранее или планируемых на будущее. Реализационное сужение семейства процессов, допускаемых семантикой ЯСВУ, противоречит его целям или концепциям по следующим прагматическим мотивам: – высокий уровень абстрагирования программируемых решений; – решаются задачи, зависящие от непредсказуемых внешних факторов; – базовые средства и/или алгоритмы вычислений используют параллелизм; – актуальны прагматические требования к темпу и производительности вычислений; – эксплуатируются динамически реконфигурируемые многопроцессорные комплексы. Обычно создатели нового ЯСВУ используют в качестве исходного материала один или несколько базовых ЯВУ и встраивают в них 185 изобретаемые средства и методы. От базовых ЯВУ наследуются парадигмы удовлетворительного решения сопутствующих задач. В таких случаях парадигматическая характеристика ЯСВУ может формулироваться относительно базовых ЯВУ, хотя внешнее синтаксическое сходство языковых конструкций иногда скрывает совсем другую семантику. Для ЯСВУ характерно применение регулярных, математически ясных и корректных, абстрактных структур, при обработке которых возможны преобразования данных и программ, использование подобий и доказательных построений. Все это призвано гарантировать высокую производительность вычислений, надежность процесса разработки программ и длительность их жизненного цикла. Типичны алгебраические спецификации, теоретико-множественные построения, параллелизм, модели процессов разработки программ. Изобретаются специальные системные средства, повышающие емкость представлений, их общность и масштабируемость. Естественный резерв производительности компьютеров – параллельные процессы. Их организация требует контроля и детального учета временных отношений и неимперативного стиля управления действиями. Суперкомпьютеры, поддерживающие высокопроизводительные вычисления, нуждаются в особой технике системного программирования, которая еще не сложилась, хотя уже имеется опыт эффективного решения особо важных задач. Таким образом можно как бы «просачивать» определения функций над простыми данными, распределять их по структурам данных и тем самым распространять простые функции на сложные данные подобно матричной арифметике. Похожие построения предлагаются Бэкусом в его программной статье о функциональном стиле программирования и в языке APL, ориентированном на обработку матриц. Как правило, языки параллельного программирования включают в себя средства, характерные для разных парадигм. Это определяет целесообразность трансформационного подхода к накоплению правильности программных решений при разработке и модернизации параллельных программ на разных языках в рамках общей системы программирования. Развитие ЯСП в настоящее время ориентировано на решение задач на основе общих библиотечных модулей, обеспечивающих эффективную организацию процессов, или подъязыков, допускающих многопоточное программирование. Это не исключает реальную практику ручного распараллеливания ранее отлаженных обычных программ, приведения их к виду, удобному для применения производственных систем поддержки параллельных вычислений. Значительная часть таких работ носит технический характер и заключается в систематической 186 реорганизации структур данных, изменении статуса переменных и включении в программу аннотаций, сообщающих компилятору об информационно-логических взаимосвязях. Существенным ограничением результата ручного распараллеливания является не только опасность повторной отладки алгоритма, но и его избыточная зависимость от характеристик целевой архитектуры. 8.6. Высокопроизводительное программирование. Рассмотрим один из известных ЯП – функциональный язык параллельного программирования SISAL |