ывап. Курс лекций новосибирск 2015
 Скачать 1.73 Mb.
|
|
Парадигматическая характеристика парадигмы ООП Параметр Конкретика Эксплуатационная прагматика ЯП Практичное программирование, нацеленное на разумный компромисс в пространстве противоречивых критериев с приоритетом критериям сферы приложения программ. Регистры абстрактной машины S E C D M S – стек промежуточных результатов E – стек локальных переменных C – текущая программа D – дамп для восстановления контекста при рекурсии. M – общая память хранимых объектов. Результат рассредоточен по именованным состояниям памяти. Категории команд абстрактной машины Загрузка в стек. Сохранение значений. Манипулирование стеком. Арифметические и логические операции. Передачи управления. Выбор определения метода, функции, операции. Вызов метода. Возврат из метода. Обработка исключений. Работа под монитором (параллелизм). Реализационная прагматика Сочетание статического представления методов с динамикой размещения объектов, включая автоматизацию повторного использования памяти. Представление сигнатуры для динамического выбора конкретного метода обработки объект. Парадигматическая специфика Процесс программирования сводится к последовательности расширяемых по мере целесообразности программ. Использование предметной типизации классов объектов как ведущего параметра выбора конкретной техники обработки данных. 157 7.6. Мультипарадигмальные языки программирования Достаточно чѐтко границы между областями практичного проявления разных парадигм программирования можно выразить типичными формами постановок задач на программирование. Стандартное императивно-процедурное программирование: «Существует алгоритм решения актуальной задачи. Необходимо подготовить программу реализации алгоритма с практичными пространственно-временными характеристиками на доступном оборудовании». Функциональное программирование: «Известна предметная область. Следует выбрать символьное представление данных для этой области и отладить систему универсальных функций, пригодных для использования в разных программах обработки данных при решении актуальных задач из этой области». Логическое программирование: «Дана коллекция фактов и отношений, показывающая актуальную задачу. Надо привести эту коллекцию к форме, достаточной для получения ответов на практичные запросы относительно данной задачи». Объектно-ориентированное программирование: «Доступна иерархия классов объектов, поддерживающая работоспособные методы решения ряда задач некоторой предметной области. Нужно без лишних трудозатрат уточнить эту иерархию, чтобы приспособить еѐ к решению новых востребованных задач этой области, еѐ расширения или ей подобной». Практические задачи нередко включают такие формулировки в качестве подзадач, что приводит при создании ЯП и разработке СП к поддержке разных парадигм одновременно. Так, например, при целенаправленной разработке монопарадигматического языка Haskell, позиционируемого как чисто функциональный язык, авторы пришли к концепции монад, позволяющей привлекать механизмы других парадигм. Потребность в поддержке парадигм, отсутствующих в реализуемом ЯП, может встраиваться в СП в виде библиотечных процедур, ассемблерных вставок, макрогенераторов или организации выхода на уровень операционной системы. 158 Таб л иц а 3 9 Сравнение прагматических особенностей ПП ПП Иерархическая декомпозиция программы Укрупнение конструкций Память и результат Реализационная прагматика ИП Структуры данных. Динамика вызовов процедур. Области видимости идентификаторов Структуры и типы данных. Функции над значениями и указателями. Процедуры изменения состояний памяти S E C M Стеки промежуточных результатов и локальных переменных. Вектор общей памяти. Результат рассредоточен по именованным блокам памяти M Раздельное хранение программы и данных. «Забывание» идентификаторов и типов данных на период исполнения. Распределение памяти по принципу соседства ФП Структуры данных. Динамика вызовов функций. Статика и динамика определений. Сохраняемые состояния системы программировани я Функции, отображающие аргументы в результаты произвольной сложности. Символьные выражения S E C D Стеки для операндов и результатов, локальных определений, программы и восстановления состояний памяти. Результат в стеке S Тегированные указатели. Динамическое распределение памяти с автоматизацией повторного использования. Программа имеет представление в виде данных ЛП Структуры данных. Динамика вызовов процедур Шаблоны как лаконичная форма представления предикатов. Клаузы частичного определения логики вывода цели S E C D R Стеки как для ФП с добавлением регистра R для хранения вариантов. Результат – оценка выводимости цели Разностные списки. Перебор вариантов в порядке представления. Минимальность приоритета тупиковых вариантов. 159 ООП Распределение методов обработки объектов по иерархии классов. Наследование дисциплины доступа к полям объекта. Области видимости методов Классы объектов. Методы обработки объектов определѐнного класса. Структуры данных. Полиморфные определения S E C D M Стеки как для ФП с добавлением вектора M для хранения полиморфных определений методов Представление сигнатуры методов и их вызовов на период исполнения. Выбор метода по числу аргументов и типам данных Заметные различия ПП видны и на уровне базовых семантических систем ЯП. Таб л иц а 4 0 Специфика базовых семантических систем в разных парадигмах программирования на ЯВУ ПП Вычисления Память Управление Структуры ИП Скаляры = слова СД-ТД предвычислени я Статическое распределение := Области видимости - динамика вызовов - статика вложенности текста - глобалы: Описания Категории имен Составные имена exprt-import Goto If Call Case Select Switch For While Until Do Trap Catch Ситуации ОС Array Record Union Pointer ФП Длинные скаляры Списки Программы Пред и пост lazy GC – FS Без описаний До исчерпания Динамика вызовов – БД (атомы) Списки свойств Let Quote-eval Lazy Cond Lambda Defun Evalquote Ловушки Списки Файлы Строки Потоки Модели массивов, таблиц, 160 Declare Мультизначения Параллелизм Необязательные параметры вариантов ЛП Варианты с возвратами Шаблоны в строке Подстановка Накопление рецептов Обход лабиринта Параллелизм – обход графа в ширину Иерархия принятия решений ООП Обработка полей записи Разметка доступа Дружественный доступ Выбор метода по ТД или по ситуации Привязка к интерфейсу Иерархия классов Следует обратить внимание, что наиболее успешные, долго живущие языки и системы программирования являются мультипарадигматическими. ЯП Fortran включает в себя: – средства представления выражений с функциями; – арифметические функции; – неявные циклы форматного ввода-вывода векторов и массивов; – вычисляемые передачи управления; – сопрограммы – многовходовые подпрограммы. – Lisp 1.5 поддерживает работу : – с таблицей свойств атомов, фактически поддерживающей статическую память с побочным эффектом; – императивно-процедурное программирование в форме Prog. – глобальные определения атомов в терминах свойств атомов. – псевдо-атомы для работы со скалярами разных типов и форматов. – мультиоперации над числами и строками. – псевдо-функции для взаимодействия с операционной системой. – расширение системы программирования определениями на входном языке и средствами ассемблера. – статически типизированные ЯП Pascal, C и др. поддерживают вариантные структуры данных, позволяющие в динамике обойти контроль ТД. Такие комментарии можно привести для всех ЯП, подтвердивших длительностью своего существования разумность предложенных в них обобщенных решений. В рамках проекта .Net появились новые ЯП F# и C#. 161 Изначально императивно-процедурный C и язык ООП С++ при переходе к С# обогащаются рядом новых возможностей: – выражения могут содержать безымянные функции, представленные как структуры данных; – поддержаны динамические типы данных – стеки, очереди, списки, деревья; – доступны библиотеки классов, библиотеки элементов управления и библиотеки Web-элементов управления; – формируется код программы, способный учитывать особенности текущей платформы; – задача сборки мусора в памяти снята не только с программистов, но и с разработчиков трансляторов; она решается в нужное время и в нужном месте – исполнительной средой, ответственной за выполнение вычислений; – каждый тип, помимо полей, методов и свойств, может содержать и события; – при компиляции программы создаѐтся манифест, полностью описывающий еѐ сборку. ЯП F#, наследующий идеи функциональных ЯП ML, CAML, OCAML, поддерживает механизмы ЛП и ООП: – полный свод обычных механизмов функционального программирования, включая функции высших порядков; каррирование и сопоставление с образцом; – динамическое связывание; – ленивые и энергичные вычисления; – замыкания функций и мемоизация; – квотирование выражений; – конструирование выражений, частичное применение функции и мета- компиляция; – разреженные матрицы; – хеш-таблицы; – mutable-переменные (изменяемые); – монада недетерминированных вычислений; – асинхронные выражения и параллельное программирование; – интероперабельность с .NET. Язык Scala объединяет механизмы ФП и ООП с резким акцентом на контроль ТД, удобный для разработки компиляторов, обеспечивающих надѐжность программ: 162 – объекты и их поведение определяется классами с возможностью множественного наследования; – функции являются значениями и могут быть высших порядков; – статическая типизация поддерживает обобщѐнные классы, встроенные классы и абстрактные типы, составные типы, полиморфные методы и др.; – допускает включение новых языковых конструкций; – взаимодействует с Java и .Net; – допускает анонимные функции; – автоматическое конструирование типозависимых замыканий функций; – использует механизм сопоставления с образцом. Объединение разных ПП в рамках одного ЯП или их поддержка при реализации СП повышает их сферу применения и способствует производительности труда программистов, смягчая избыточное разнообразие теорий и моделей, сложившихся на разных фазах и этапах ЖЦП. Новые и долгоживущие ЯП как правило имеют мультипарадигматический характер. Следует обратить внимание на появление учебных языков программирования (A++, Oz), поддерживающих все основные парадигмы программирования, что показывает их взаимную дополнительность и образовательное значение. Приведенные функциональные модели основных ПП показывают, что функциональный стиль и традиция реализации функциональных систем программирования могут дать систему мер для сравнения языков программирования. 163 ЛЕКЦИЯ 8. ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ Прогресс производства аппаратуры намного опередил развитие технологий программирования. Параллельные архитектуры теперь позволяют принципиально повышать производительность программ решения многих задач. Методы автоматического распараллеливания программ способны обеспечить значительное ускорение вычислений, явно сводимых к комплексу независимых процессов обработки элементов векторов, но отступают перед программами более широкого класса. Перспектива выражения языковыми средствами параллелизма на уровне постановки новой задачи приторможена проблемами оптимизирующей верифицирующей компиляции, обеспечивающей аккуратный выбор эффективной и надежной схемы параллелизма. Кроме того, трудоѐмкость повторного программирования и отладки параллельных алгоритмов обуславливает рассмотрение готовых последовательных программ в качестве эталонов при оценке результатов параллельных вычислений, что сдерживает развитие языков параллельного программирования и методов их реализации. В настоящее время осознана актуальность формирования парадигмы параллельного программирования, вызванная расширением и развитием системы базовых понятий, необходимых для рациональной разработки систем управления процессами на современной аппаратуре. Парадигмы в программировании характеризуются стилем мышления при решении задачи, системой используемых понятий и особенностями их реализации. Можно констатировать, что стиль мышления и система понятий для параллельного программирования уже сложились в процессе эволюции языков программирования, но типовая их поддержка в системах программирования ещѐ не сформировалась «Ничем не скроешь фундаментальную трудность параллелизма» – так прозвучало заявление Мартина Одерски (Martin Odersky) в его приглашенном докладе на 20-й Международной конференции «Конструирование компиляторов», состоявшейся в марте 2011 года в Германии под председательством Дженса Кнопа (Jens Knoop) [21]. Несмотря на многочисленные призывы и конкурсы, пока не появилось общих идей по новому поколению языков и систем программирования (ЯСП), в которых параллелизм имел бы самостоятельное значение, а не рассматривался бы (по понятным причинам) как пристройка к традиционному программированию. 164 8.1. Пространство решений Рост интереса к параллельному программированию в наши дни связан с переходом к массовому производству многоядерных архитектур. Ознакомление с понятиями и явлениями параллельного программирования в данном материале нацелено на профилактику прочного привыкания к принципам традиционного последовательного программирования. Такая профилактика необходима для специализации в области разработки распределенных информационных систем, а также приложений для суперкомпьютеров, многопроцессорных конфигураций и графических процессоров. Современное развитие ЯСП на практике ориентировано на решение задач параллельного программирования. Как правило, новые ЯСП включают в себя библиотечные модули, обеспечивающие организацию процессов, или подъязыки, допускающие многопоточное программирование. Это не исключает реальную практику ручного распараллеливания ранее отлаженных обычных программ, приведения их к виду, удобному для применения производственных систем поддержки параллельных вычислений. Значительная часть таких работ носит технический характер и заключается в систематической реорганизации структур данных, изменении статуса переменных и включении в программу аннотаций, сообщающих компилятору об информационно- логических взаимосвязях. Существенным ограничением результата ручного распараллеливания является не только опасность повторной отладки алгоритма, но и его жесткая зависимость от характеристик целевой архитектуры. Разнообразие моделей параллельных вычислений и расширение спектра доступной архитектуры следует рассматривать как вызов разработчикам ЯСП, способных решать проблему создания методов компиляции многопоточных программ для многопроцессорных конфигураций. Язык должен допускать представление любых моделей параллелизма, проявляемого на уровне решаемой задачи или реализуемого с помощью реальной архитектуры, причем такое представление требует лаконичных форм и конструктивных построений, гарантирующих сохранение свойств программ при их реорганизации. Не менее важна расширяемость языка по мере развития средств и методов параллельных вычислений, темп которого превышает скорость осознания специалистами их возможностей. Рассматривая задачу формализации языков параллельного программирования как путь к решению проблемы адаптации программ к различным особенностям используемых многопроцессорных комплексов и 165 многоядерных процессоров, мы видим, что решение этой проблемы требует разработки новых методов компиляции программ, особенно масштабируемой кодогенерации, и развития средств и методов ясного описания семантики языков параллельного программирования. 8.2. Параллельные алгоритмы Обзор решений, встречающихся при организации параллельных процессов для реализации параллельных алгоритмов, даѐт некоторое представление о разнообразии многопроцессорных архитектур и систем: – процессоров может быть много, и они могут обладать разными системами команд; – процессоры могут работать автономно или сообща выполнять общую работу; – отдельные процессоры могут функционировать вхолостую, не выполняя полезной работы; – процессоры имеют свою локальную память и могут работать в общей памяти; – распределение действий по процессорам может быть предписано программой, а может осуществляться супервизором, поддерживающим определенную модель вычислений. Такое пространство допускает естественное развитие в направлении моделирования асинхронных процессов, а также помогает уяснить, что существуют контексты исполнения программ, от которых зависит выполнимость команд. При анализе результатов программ обнаруживаются разные категории ошибок управления и выделяются невыполнимые действия, несмотря на то, что все образующие их команды выполнимы. Проявляется роль частичного упорядочения действий в обеспечении работоспособности программ средствами управления вычислениями, отражающего неимперативность последовательного исполнения действий при организации параллельных процессов. Оптимизирующие компиляторы любую программу нередко рассматривают как мультипрограмму. Переход к параллельным алгоритмам влечѐт пересмотр содержания многих понятий и введение новых терминов, отражающих разного рода явления и эффекты, не имевшие особого значения для обычных последовательных алгоритмов. Прошли времена, когда параллельное программирование называли неалгоритмическим. Теперь термин «параллельный алгоритм» связан с пониманием того, что алгоритм может выполняться как одним, так и группой исполнителей. Такое понимание 166 резко расширяет пространство решений задач, меняет подходы к реализации решений, использующих параллелизм, и в некоторой мере сказывается собственно на постановке задач и планировании жизненного цикла программ решения задач, ориентированных на использование параллелизма. Прежде всего, следует прояснить следующие вопросы, связанные с формулировкой постановки задачи: 1. Насколько изменится трудоѐмкость жизненного цикла программы решения задачи с помощью параллельного алгоритма? 2. В какой мере при постановке задачи следует учитывать модель параллелизма? 3. Как обосновать и измерить выигрыш от разработки параллельного алгоритма? 4. Насколько изменяется постановка задачи при переходе к параллельным алгоритмам? 5. Что даѐт парадигма параллельного программирования на уровне разработки параллельного алгоритма? 6. Какими средствами представляются разрабатываемые параллельные алгоритмы решения задачи на этапе, предшествующем разработке программы? За полвека традиционного последовательного программирования отлажено колоссальное количество программ, аккумулированных в системы программирования и стандартные библиотеки. Изменение постановок задач, уже имеющих готовые отлаженные программные решения, ради учѐта допустимого параллелизма чревато повторным программированием и, что гораздо более трудоѐмко, повторной отладкой. Основной аргумент – целесообразность учета естественного параллелизма на уровне постановки задачи, утрачиваемого при решении задачи посредством обычных алгоритмов. Число языков параллельного программирования, удобных для реализации параллельных алгоритмов год от года растѐт, хотя и их применение решает не все проблемы организации параллельных вычислений. Итак, параллельный алгоритм может быть реализован по частям на множестве различных устройств с последующим объединением полученных результатов и получением целевого результата. Возникают практические вопросы: – Каким образом в определении алгоритма выделены части, выполняемые отдельными устройствами? – Обязана ли реализация алгоритма использовать в точности представленный в его определении набор устройств? 167 – Можно ли последовательный алгоритм рассматривать как параллельный, исполняемый на одном устройстве? Следующая обойма вопросов касается категории «время» и связана с проблемами синхронизации: – Могут ли части параллельного алгоритма обладать своим независимым или централизованным отсчетом времени? – Может ли синхронизация частей алгоритма противоречить его информационным связям и логике управления? – Можно ли синхронизацию частей алгоритма рассматривать как частный случай асинхронности? Особые сложности параллелизма вызывают вопросы доступа к памяти: – Каким образом взаимодействующие части параллельного алгоритма обмениваются данными? – Могут ли части параллельного алгоритма изменять состояние общей памяти и памяти других частей? – Может ли часть параллельного алгоритма воспрепятствовать использованию своей памяти другими частями? Кроме того, части алгоритма могут быть определены в разных моделях вычислений и над разными структурами данных. Оценка результата разработки параллельного алгоритма, кроме оценки сложности вычислений и объѐма данных, осложнена целесообразностью оценивать выполнение разного рода трудно формализуемых критериев, часть которых, однако, поддаѐтся современным средствам верификации на моделях. И всѐ же, сколь ни сложен мир параллелизма, программистам предстоит его понять и освоить! Интересно отметить появление новых архитектур, обладающих полным набором команд с условным исполнением. Исследования в области информатики в настоящее время претерпевают изменение системы понятий, используемой в практических ИТ. В этом процессе расширяется пространство решений сложных задач, модернизируются методы развития информационных систем (ИС) на основе компьютерных сетей и многопроцессорных комплексов. Интересно рассмотреть перспективы развития парадигм программирования, обусловленных изменением условий эксплуатации современных информационных систем, особенно связанных с повсеместным распространением сетевых технологий, меняющих критерии 168 оценки качества программ и методы обеспечения надежности и производительности программирования. Две основные линии такого развития – разработка распределенных информационных систем (РИС) и компонентное программирование (КП). При практичном решении проблемы разработки языков параллельного программирования и подходов к их реализации в центре внимания вопросы выбора лаконичных форм представления программ, обеспечения конструктивных построений, гарантирующих сохранение правильности программ при их реорганизации, и поддержки расширяемости языка по мере развития средств и методов параллельного программирования. Описание парадигмы параллельного программирования отражает прагматические различия в условиях реализации и применения изобразительных средств, используемых в жизненном цикле программ. Парадигмы параллельного программирования занимают нишу, связанную с реализацией программ выполнения вычислений на многопроцессорных системах для организации высокопроизводительных вычислений. Эта ниша обременена резким повышением трудоемкости отладки программ, вызванной комбинаторикой выполнения фрагментов асинхронных процессов. Варьирование правил функционирования сетей допускает как асинхронную, так и синхронную организацию срабатывания действий, включая дозирование нагрузки и специализацию процессоров и распределение действий по потокам выполнения. Использование иерархических, многоуровневых, структурированных и расширяемых сетей обеспечивает моделирование практически любых, накопленных в языках программирования, техник программирования и представления структур данных. 8.3. Практичные системы программирования При измерении производительности суперкомпьютеров и в экспериментах с распараллеливанием программ активно используются задачи научных расчѐтов, преимущественно реализующих алгоритмы векторной обработки данных, удобно распараллеливаемых с помощью MPI. Практические задачи современного параллельного программирования обычно выглядят как приведение больших отлаженных ранее программ на C или Fortran-е к форме, дающей выигрыш от распараллеливания с помощью штатных средств, включаемых в доступные системы программирования. В целом такая работа сводится к следующим видам работы: 169 – разметка участков программы, допускающих автоматическое распараллеливание; – анализ участков и причин, препятствующих распараллеливанию программы; – выбор участков программы, допускающих их техническое приведение к форме, пригодной для распараллеливания; – изобретение рецептов полуручного преобразования текста программы с целью расширения возможностей распараллеливания; – приведение текста программы к предельно распараллеливаемой форме; – прогон распараллеленной версии программы для оценки выигрыша от параллелизма; – частичное перепрограммирование и отладка фрагментов программы для исключения или смягчения эффектов, препятствующих достижению нужных характеристик производительности; – установление частичной функциональной эквивалентности исходной программы и результирующей еѐ версии. Обычно компилятор поддерживает оптимизации, обеспечивающие устранение неиспользуемого кода, чистку циклов, слияние общих подвыражений, перенос участков повторяемости для обеспечения однородности распараллеливаемых ветвей, раскрутку или разбиение цикла, втягивание константных вычислений, уменьшение силы операций, удаление копий агрегатных конструкций и др. Рассматривается зависимость ускорения вычислений от числа процессоров и объема общей и распределенной памяти. Выполняется систематическая замена рекурсии на циклы. Предпочитается однородное пространство процессоров, общая память, быстрые обмены, соседство, гарантирующие улучшение производительности систем для высокопроизводительных вычислений. Заметно влияние дисциплины работы с памятью на характеристики параллельных процессов. Используется защищенная и размазанная память. Различны решения, принятые в разных языках программирования, по работе с многоуровневой и разнородной памятью (доступ, побочный эффект, реплики, дубли и копии). Обработка транзакций становится одной из типовых семантик работы с памятью в языках программирования. Предлагаются средства и методы типизации управления процессами, удобными для подготовки программ, ориентированных на исполнение с помощью Open MP или MPI. Идеи языков программирования по сетевому представлению типов управления и дисциплины работы с памятью ещѐ не получили удобной системной поддержки. 170 Компонентно-ориентированная разработка ПО может следовать единому сетевому определению семантики языков программирования и процесса разработки программ. Некоторую поддержку работ по подготовке программ, использующих параллельные процессы, обеспечивает созданная фирмой Microsoft технология .NET, позволяющая применять общие системные библиотеки в программах на разных языках программирования. Лидирующие в области поддержки параллелизма фирмы Intel и Microsoft предлагают разработчикам высокопроизводительных вычислений новые решения, направленные на преобразования программ в процессе их создания и распараллеливания: – помощник по параллельному программированию (Parallel Advisor XE); – компиляторы-отладчики и библиотеки (Parallel Composer XE2011); – анализатор потоков и памяти (Parallel Inspector XE); – профилировщик производительности (Parallel Amplifier XE). Помощник по параллельному программированию анализирует исходный текст программы на языках Fortran или C до ее компиляции и отмечает узкие места, препятствующие распараллеливанию. Анализатор потоков и памяти исследует полученный в результате компиляции объектный код и выявляет неудачное распределение ресурсов, снижающее производительность программы. Профилировщик производительности позволяет наблюдать экспериментальную проверку достигнутой производительности программы. Технология применения всех этих инструментов предполагает, что программист по ходу дела многократно принимает решения об изменении исходного кода программы и вручную включает в него необходимые прагмы, указывающие компилятору допустимость оптимизирующих преобразований, что делает работу компилятора по распараллеливанию программы проще и надежнее. Возникает проблема автоматизации преобразования программ с целью приведения их к виду, удобному для распараллеливания компилятором и настройки объектного кода на конкретную многопроцессорную конфигурацию. Часть проблем решает схема подготовки параллельных программ с использованием библиотек преобразований исходного и объектного кода. При демонстрации новых средств поддержки параллельного программирования представители фирм-разработчиков компиляторов показывают, насколько просто выполняется каждое такое преобразование в отдельной позиции программы. Проблемой является то, что таких позиций 171 в нужной программе может быть не десятки и сотни, а тысячи и десятки тысяч. Отыскать их все без специальных инструментов проблематично. Кроме того, при выполнении таких работ возникает необходимость повторной разработки структур данных и схем управления вычислениями, а также обоснованного выбора средств реализации программного конструктива. Так, например, возникает необходимость устранения или преобразования ряда механизмов работы с глобальными переменными, общими блоками данных, глубокой вложенности процедур, перехода от рекурсивных вызовов к итерациям со статическим управлением циклом и другое. Кроме того, возникает целый спектр аналитических выкладок по установлению фактических областей видимости имѐн, выбор между общей памятью и памятью конкретного потока. Выполнение таких работ вручную связано с риском порождения типичных для параллельных программ ошибок, таких как гонки памяти, конфликт доступа, взаимоблокировка и т. п. Реорганизация векторов для нужд эффективного распараллеливания может идти разными путями: разделение на чѐтные-нечѐтные элементы, разбиение на половины или четверти, распределение по частям, требующим разной интенсивности вычислений и т. п. Иногда такие проблемы можно решить на уровне макропреобразований текста программы, выполняемых препроцессорами, – необходимо лишь разработать систему подходящих конкретной программе макроопределений. Такие системы обычно не обладают универсальностью: они отражают индивидуальный стиль программирования, учитывают особенности мнемоники и неявные границы схем управления вычисления. В результате создаѐтся многопоточная версия программы, строго говоря, не являющаяся эквивалентом исходной программы, а лишь эквивалентно строящая еѐ основные результаты. Особый круг проблем связан с навыками учѐта особенностей многоуровневой памяти в многопроцессорных системах. Обычное последовательное программирование такие проблемы может не замечать, полагаясь на решения компилятора, располагающего статической информацией о типах используемых данных и способного при необходимости выполнить оптимизирующие преобразования программы. Следует отметить, что использование языков параллельного программирования в качестве языка представления исходной программы не гарантирует еѐ приспособленность к удачному распараллеливанию. При анализе пригодности программы к распараллеливанию анализируются следующие потенциальные зоны риска: 172 – объявление и использование глобальных переменных; – области видимости переменных и констант; – определения распараллеливаемых процедур, содержащие внутренние вызовы других процедур; – рекурсивные определения; – заголовки циклов, управляющие кратностью выполнения распараллеливаемого тела цикла; – ветвления и переключатели, дающие развилки потоков; – обработчики исключений; – реакции на события и сообщения; – позиции возможного обмена данными между потоками; – тиражирование данных в общей памяти и в файлах; – списки параметров функций, возможно преобразуемые в данные в общей памяти; – декомпозиция управления циклом и реорганизация соответствующих структур данных; – границы участков изменения значений переменных; – переменные для значений промежуточных вычислений; – многократно выполняемые идентичные вычисления – избыточные; – инкрементные переменные, динамику изменения которых желательно сохранять для пост-анализа; – позиции диагностической аранжировки для пост-анализа; – фактически не задействованные переменные и константные или не используемые вычисления; – параметризация зависимостей частей многопоточной программы от номера потока. Вытекающие из такого анализа преобразования программы могут быть выполнены в стиле символьной обработки данных с помощью техники лексического и синтаксического анализа, регулярных выражений и макропреобразований. Чисто технические трудности связаны с разнообразием типов преобразований. Практики придерживаются традиционной методики отладки, т. е. разделяют процесс преобразований на шаги, на каждом из которых выполняется ровно один тип преобразований, после которого выполняется прогон программы на имеющихся тестовых данных с целью удостоверения сохранения частичной функциональной эквивалентности. Таким образом, техника приведения программ к распараллеливаемой форме меняет стиль применения систем программирования, требует программистской работы на уровне грани между разбором программы и 173 кодогенерацией, а также обустройства библиотек преобразований программы и еѐ оптимизирующих преобразований. Важно учесть изменение критериев применимости оптимизирующих преобразований. Если устранение избыточных вычислений в последовательной программе обычно оценивается как улучшение, то в параллельной программе оно может оказаться пессимизацией из-за появления лишних взаимосвязей между потоками и доступа к общей памяти. Следует принять во внимание, что, хотя основная трудоѐмкость жизненного цикла программ связана с тестированием и отладкой программ, именно это направление за полвека профессионального программирования практически не получило должного прогресса. Если первый барьер к успеху в параллельном программировании обусловлен последовательным стилем мышления, то второй очевидно зависит от до сих пор не преодолѐнной трудоѐмкости отладки. Основные результаты здесь получены в форме парадигм функционального, структурного и объектно-ориентированного программирования и технологий поддержки непрерывной работоспособности разрабатываемой программы, смягчающих сложность тестирования, развития и версифицирования программного продукта. Отладочные средства современных визуальных оболочек систем программирования, как и в ранние времена последовательного программирования, предоставляют для отладки параллельных программ средства выполнения в пошаговом режиме, отслеживания значений переменных и установления точек приостановок, для работы с которыми программист должен заранее подготовить комплекты тестов для всех участков программы и контроля корректности значений внутренних переменных. Возможно указание условий, при которых отладчик произведѐт приостановку программы и обеспечит воспроизводимость повторного прогона программы. Специфику параллельного программирования отражает лишь возможность переключения потоков, обнаружения тупиков и потерянных сигналов, совместно используемых (разделяемых) данных, реентерабельных процедур, вызываемых повторно из другого потока до их завершения. Для целей отладки выполняется компиляция специальной отладочной версии программы, что говорит о необходимости дополнительной отладки программы уже без отладочного сервиса. Впрочем, известны средства фоновой отладки, обеспечивающее слежение за отлаживаемой программой из независимого смежного процесса уровня ОС. Лишь в последние годы в работах ИСП РАН наметилось более серьѐзное отношение к проблемам отладки параллельных программ, что представлено 174 в форме появления теорий для обработки информации, подверженной искажениям, и методики сравнительной отладки программ, в которой задействовано понятие эталонной программы и схемы распределѐнного отладчика. 8.4. Модели параллелизма в языках программирования История языков программирования накопила целый ряд примеров лаконичных форм представления программ, начиная с умолчаний, неявных циклов и операторов ввода-вывода в языке Fortran. С точностью до реализационной прагматики, при разработке языков параллельного программирования можно унаследовать языковые конструкции и механизмы из привычных парадигм программирования и зарекомендовавших себя языков параллельного программирования. Прежде всего, это алгебраические механизмы распространения функций и операций относительно структур данных, предложенные в первом языке параллельного программирования APL. Дальнейшее упрощение изобразительных средств управления параллелизмом дает предложенный в языке Sisal подход к неявному распараллеливанию циклов на основе построения пространства итераций по пространству обрабатываемых данных. Ещѐ острее становятся проблемы разработки, отладки, тестирования и верификации параллельных программ по сложности весьма превосходящие обычное программирование. Именно здесь сосредоточена исследовательская активность современного языкотворчества и системного программирования, поиск средств и методов интеграции удачного опыта параллельного программирования и успешного обучения методам параллельных вычислений. Акцент на анализ подходящих решений в области разработки переносимых программ, средств визуализации процессов, типизации управления и дисциплины доступа к памяти. Практически в мире параллелизма все базовые понятия программирования претерпевают изменение или расширение (программа, ветвление, цикл, событие, память, результат). Появляется ряд специфических для параллельного программирования понятий (процессор, поток, ожидание, длительность, фильтр, барьер). Программы становятся многопоточными, циклы – параллельными, память обретает копии и реплики, события происходят одновременно в разных синхронизуемых процессах, вычисление результата может не означать завершение процесса. Такая ревизия понятий влияет не только на стиль программирования, но и 175 изменяет характер компиляции на этапе генерации кода программы. Возрастает роль техники использования многократно используемых компонент схемного уровня, соответствующего средствам типизации управления процессами. Существуют версии ряда стандартных языков императивного программирования, приспособленные к выражению взаимодействия последовательных процессов в предположении, что в каждый момент времени существует лишь один процесс. При таком подходе в программе выделяются критические интервалы, учет которых полезен при распараллеливании программ. Многие традиционные языки программирования приспособлены к выражению локального параллелизма с помощью специальных расширений или библиотечных функций, обеспечивающих выделение участков с независимыми действиями, пригодными для распараллеливания компилятором. Большие надежды связаны со строго функциональным подходом к спецификации параллельных программ и типов данных в языке с предпочтением так называемой «ленивой» схемы вычислений. Противопоставление достоинств и недостатков «ленивых» и «энергичных» методов вычислений отчасти смягчается концепцией «монад» в строго функциональном языке программирования Haskell. Особенности определения семантики языковых конструкций по-прежнему не отражают решение проблем обеспечения удобочитаемости программ и их отладки. Табулирование сложных вычислений, называемое «мемоизация», становится популярным практичным инструментом снижения сложности вычислений. В настоящее время существуют сотни функциональных языков программирования, ориентированных на разные классы задач параллельного программирования. Языки функционального программирования обогатились типовыми средствами практически всех известных подходов к представлению программ и организации вычислительного эксперимента и информационных процессов. Обеспечена организация параллельных процессов. Возможна визуализация данных и программ. Имеются средства стандартного и объектно-ориентированного программирования. Поддержано управление компиляцией и конструирование компиляторов. На сегодняшний день утратили актуальность опасения относительно ресурсно-эксплуатационных трудностей функционального программирования. Функциональное программирования вносит свой вклад техникой рекурсивных определений и отображений, параллелизмом обработки аргументов функций, ленивых 176 вычислений, а также сведением понятия «условия» в ветвлениях к понятиям «страж» или «образец». В семействе практичных языков функционального программирования заметное место занимают языки организации распределенных и параллельных вычислений. Практики с большой похвалой отзываются о языке функционального программирования Erlang фирмы Ericsson. |