Файлы для подготовки к экзамену / Особенности параллелизма

1.2.2. Особенности параллелизма.

В этом пункте, следуя [1], мы охарактеризуем различные особенности и типы параллелизма, существенные с позиций поиска адекватных языковых средств для его выражения. Естественно, что в конечном итоге понятие параллелизма связано с одновременностью действий или процессов, осуществляемых в дискретном времени. Широко известные понятия синхронности и асинхронности протекающих процессов отражают допустимые схемы и “границы” взаимодействия процессов. Поиск моделей абсолютно асинхронных, или абсолютно параллельных процессов хотя и является неразрешимой проблемой, тем не менее, ставит вполне естественную и важную для параллельных вычислений задачу сравнения по выразительной силе различных подходов, моделей и языков, связанных с параллельным программированием.

Одной из важных характеристик параллелизма является способ его задания: явный или неявный.

Первый предполагает существование языка или определённого набора примитивов, средствами которых программист описывает в программе интересующие его параллельно выполняемые действия. Примитивы par begin par end, fork – join, средства задания параллельных процессов в MPI, PVM, многих других подобных программных средствах для задания параллелизма, наконец, различные процессные модели (сети Петри, модели взаимодействия процессов Милнера и Хоара[34] и др.) и т.п. – примеры явного задания параллелизма.

Параллелизм неявно присутствует почти во всякой последовательной программе и его часто с успехом может обнаружить компилятор, параллелизм неявно отражён в арифметических или логических выражениях, благодаря свойствам операций (ассоциативности, коммутативности, дистрибутивности), используемых при их построении.

Неявно параллелизм присутствует в функциональных языках[5, 6], логике первого порядка, Прологе. Благодаря тому, что эти языки имеют строгую детонационную семантику и независимую параллельную операционную семантику (у функциональных языков – эта семантика осуществляется через процессы свёртывания и развертывания деревьев [5, 6], у логических формализмов и языков – посредством построения параллельных алгоритмов вывода[7]). Более того, всякая попытка явного указания, что должно выполняться параллельно в такого рода программах выглядит противоестественным и, кроме того, почти всегда будет приводить к тому, что многие возможности распараллеливания будут просто утрачены.

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

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

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

Каждый из названных видов параллелизма основан на определённой парадигме программирования и имеет свои особенности, проявляющиеся как в способах его выявления, так и в присущей ему процессной модели и реализации.

Говоря о процессном параллелизме, мы имеем ввиду различные процессные модели (сети Петри, модели Хоара и Милнера, акторные модели и др. [8]оворя о процессном параллелизме, мы имеем ввиду различные процессные модели()ммированияливания будут просто утрачены.оестествен), в которых уточняются основные понятия, связанные с порождением и взаимодействием процессов.

Именно на основе этих моделей реализованы многие языки процессов (например, OCCAM), средства ОС для организации “нитевых” процессов и др.

Ещё один важный в практическом смысле аспект в характеризации параллелизма – это ограничения на “зернистость”, для уточнения которой обычно используют понятия: крупно – зернистый, средне и мелко – зернистый параллелизм (возможна и более детальная шкала дифференциации).

Глубина распараллеливания, которая обсуждалась в п. (1.2.1), уточняет это понятие. Обычно крупон – зернистый параллелизм связывают с модульным программированием, с разработкой сложных программных комплексов с разнообразными приложениями, в том числе ориентированными на решение задач вычислительного характера. Мелко – зернистый параллелизм – способность функциональных и логических программ.

Мелко – зернистый параллелизм – особенность арифметических и логических функциональных программ, алгоритмов вывода в логике и др. Мы показали (см. п. 1.2.1), что глубина распараллеливания, которая формально определяет “зернистость” параллельного алгоритма, существенно влияет на коэффициент ускорения и эффективность реализации параллельных вычислений на ВС[1, 2].

Более того, решения задачи оптимального управления загруженностью компьютеров (процессоров) ВС требуется вводить механизмы динамического измерения глубины распараллеливания[1].

Например, в реализации языка функционального программирования FTPL[5] на кластерах введён механизм управления глубиной распараллеливания при выполнении программы путём отнесения рекурсивно определённых функций к более сложным с вычислительной точки зрения фрагментам программы по сравнению с базисными функциями.

Кроме того, чтобы программист мог также варьировать “зернистость” параллелизма в программе, в языках функционального и логического программирования вводят средства модульной организации программы, указатели, какие её фрагменты должны выполняться параллельно (см., например, Т систему параллельного программирования[9])

Ещё два важных свойства параллелизма – это его коммутативность или некоммутативность[1]. Коммутативность предполагает, что готовые для выполнения фрагментов параллельной программы могут назначаться для выполнения в произвольном порядке, не влияя на результат. Для некоммутативного параллелизма это не верно.

Например, при вычислении значений известной в телефонии функции голосования: , , если также определено одно из значений , и , в противном случае значение не определено.

Ясно, что аргументы (вместо которых могут быть подставлены другие функции) можно вычислять параллельно, контролируя получение результата каждого из них и сравнивая с результатами вычисления других аргументов.

Однако, произвольный порядок не гарантирует получения правильного результата. Например, если значения и определены и равны, а значение не определено и процесс его вычисления длится неограниченное время, то результат не будет получен. Такие функции ещё называются наследственно параллельными функциями. Корректное вычисление их значений требует параллельного или квазипараллельного вычисления значений всех аргументов.

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

Типичный пример – условный оператор: if then else . Ясно, что значение , и можно вычислять одновременно, однако, значение всегда необходимо, а необходимость значений или определяется результатом . Заметим, что параллелизм указанных фрагментов не является коммутативным. Реализация упреждающего параллелизма усложняется необходимостью прерывания вычислений, результаты которых не потребуются.

Все параллельные программы могут быть отнесены к двум классам: с ограниченным и неограниченным параллелизмом[1, 2] (см. п. 1.2.1). Для программ первого класса заранее можно указать количество (обычно наименьшее) компьютеров ВС, которое достаточно для реализации всех возможностей параллелизма в программе при её выполнении для заранее определённого множества исходных данных. Для параллельных программ, отнесённых к классу программ, с неограниченным параллелизмом это условие не выполняется. Рассмотренные в п. 1.2.1 примеры параллельного вычисления n!, параллельного перемножения матриц относятся к классу параллельных программ с неограниченным параллелизмом, если не накладывать никаких ограничений на n.

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

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

Анализ, затрагивающий организационную специфику параллелизма, как системы взаимодействующих процессов, выделяет синхронную и асинхронную его реализацию. Первая в отличие от второй предполагает строгую спецификацию моментов времени (или событий), в которые могут происходить те или иные действия при выполнении параллельной программы. Типичный пример, векторный оператор par begin par end, предполагающий контроль его завершения после окончания выполнения входящего в него оператора с максимальным временем выполнения (или всех таких операторов, если их несколько).

Другая процессная характеризация параллелизма – это та, которой определятся схема его реализации как распределённой в пространстве системы процессов (то, что обычно называют распределенной обработкой), либо путём организации потоковой обработки. В первом случае параллелизм в [1] также назван пространственным. Схема потоковой обработки имеет разные “оттенки”. Прежде всего, это перенесение в сферу организации процессов вычислений давно применяемой на производстве схеме конвейерной обработки Известно, что разбивая сложный процесс на отдельные последовательно выполняемые мелкие фазы и организуя конвейерную (потоковую) обработку путём создания для реализации каждой фазы самостоятельного узла (устройства, станка и т.п.) можно в предельном случае в k раз увеличить производительность такой схемы выполнения “работ”, где k – число ступеней конвейера. Более того, эта схема позволяет достигать показателя наилучшего показателя в использовании ресурсов конвейера. Подлинное свое воплощение на компьютерной почве конвейер получил в 60-х годах прошлого века в компьютерах СТРЕТЧ и БЭСМ-6, где одновременно обрабатывалось от 7 до 10 команд программы. Любой современный компьютер (персональный или супер – компьютер, например Крей), кроме командного, реализуют скалярный и/или векторный конвейеры для выполнения арифметических операций.

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

Реальные системы обработки информации в общем случае многопоточные, как правило, с очередями на входах их узлов и сложными связями, определяющими “направление” движения данных: один ко многим, многие к одному узлу и др.

Эта схема обработки данных всё шире используется в параллельном программировании, описании распределённых систем и процессов[10].

В реализуемом в работе языке граф – схемного потокового программирования[11] возможно построение любых схем потоковой обработки (многопоточных схем с очередями данных на входах модулей), причём в силу того, что модули взаимодействуют только по данным информационно – независимые модули легко обнаруживаются по отсутствию связей между ними.

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

В заключение параграфа отметим, что данная выше характеристика различных сторон проявления параллелизма особенно важна для практики при создании языков параллельного программирования и их реализации на ВС. С её учётом создавался язык граф – схемного параллельного потокового программирования и строились принципиальные решения, при его реализации на ВС.