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

Посмотреть архив целиком

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


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

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

Первый предполагает существование языка или определённого набора примитивов, средствами которых программист описывает в программе интересующие его параллельно выполняемые действия. Примитивы par begin par end, forkjoin, средства задания параллельных процессов в 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, предполагающий контроль его завершения после окончания выполнения входящего в него оператора с максимальным временем выполнения (или всех таких операторов, если их несколько).


Случайные файлы

Файл
104094.rtf
91837.rtf
94278.rtf
CBRR1032.DOC
C_TOTAL.DOC




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.