О параллелизме с разных сторон (547927), страница 2
Текст из файла (страница 2)
Фукнции и данные в FPTL определяются в общем случае ввиде систем функциональных и реляционных уравнений, а поскольку рекурсия являетсяболее мощным средством задания параллелизма по сравнению с определением функцийпосредством циклических конструкций, это придает языку большую выразительную силу[11].Уникальной является среда проектирования функциональных программ на FPTL, вкоторой помимо традиционных инструментов отладки программ созданы не имеющиеаналогов подсистемы эквивалентных преобразований программы, позволяющиеавтоматически приводить ее к максимально параллельной форме, а также подсистемыанализа структурной и вычислительной сложности и верификации [10,11].Реализация языка на многопроцессорных КС [10,11], созданные средства дляэффективного планирования порождаемых при выполнении функциональной программыпроцессов и распределения ресурсов полностью избавляют программиста от необходимостиэтой работы, как это делается при использовании MPI, Multithreading и других средствпараллельного программирования.ПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW45Отметим здесь также, что стремление приблизить языковые средства к проблемнойсреде явилось результатом создания целого ряда проблемно-ориентированных языковпараллельного программирования: параллельный FORTRAN, DVM, MPC (ориентация нарешение задач линейной алгебры), PARLOG (параллельный логический вывод), OCCAM(взаимодействие параллельно выполняемых процессов) и других.Ниже мы рассмотрим те наиболее важные особенности паралелизма, которыесущественны для построения языков параллельного программирования и для разработкипараллельных программ.1) Явный и неявный параллелизм.В последовательных программах, функциональных языках и других системахпараллелизм представлен неявно, и необходимы соответствующие решения для еговыявления на стадии трансляции или интерпретации.
PVM, MPI, Multithreading, примитивызадания векторного и нитевого (fork и join) параллелизма – примеры явного заданияпараллелизма на процессном уровне.2) Коммутативный и некоммутативный параллелизм.Первое предполагает, что возможен произвольный порядок выполнения фрагментовпрограммы, как, например, для векторных команд. В условном операторе if P(x) then f1(x) elsef2(x), начав вычисление с f1(x) или f2(x) , мы не всегда можем по лучить существующийрезультат (пусть вычисление f1(x) длится неограниченно, а P(x) ложно и результат f2(x)определен).Результативность достигается, если по крайней мере вычисление P(x) не откладыветсядо получения результата f1(x) и f2(x).3) Упреждающий и наследственный параллелизм.В условном операторе мы можем вычислить с упреждением значение функций f1(x) иf2(x), стремясь добиться большего ускорения (в лучшем случае при равенстве временвычисления значений P(x), f1(x), f2(x) оно равно двум).
Однако, какой результат f1(x) или f2(x)потребуется, станет ясно только после вычисления P(x). Ясно, что выполнение условногооператора легко сводится к последовательной форме.Однако, существует огромное множество так называемых параллельных функций(функций с наследственным параллелизмом [12]), которые нельзя корректно вычислитьпростым сведением вычислений их составляющих к последовательной форме. Приведемхорошо известный в телефонии пример функции голосования f(x1, x2, x3), такой, что еезначение определено, если определены любые два ее аргумента (положим, что вместо нихподставлены другие функции), при этом значения функции является значением одного изпары равных аргументов; в противном случае значение функции не определено. Очевидно,при строго последовательной форме вычисления значений этой функции алгоритм долженбыть устроен так, что вычисление значений любых функций, стоящих на месте аргументовх1, х2 и х3, не должно откладываться на неограниченное время.
Это хороший пример дляПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW46того, чтобы еще раз напомнить о нетривиальной реальности во «взаимоотношениях»последовательной и параллельной парадигм программирования.4) Потоковый параллелизм.Этот вид параллелизма возникает при параллельной обработке данных, типичным ипростым примером которого является конвейерная обработка (обработка потоков данных,производство деталей и т.п.).Программа, как правило, применяется к множеству данных и у нас есть возможностьорганизовать ее копии, применяя их одновременно к различным данным, или построитьпроцесс таким образом, чтобы данные (обычно тегированные) продвигались от одногофрагмента к другому, зависящему от данного фрагмента, и инициализация выполнениялюбого фрагмента осуществлялась по готовности поступающих данных.
Так устроены графсхемные программы [8,9], модули которых одновременно могут применяться ко всемпоступившим данным путем копирования их подпрограмм и применения каждой из них ксоответствующему кортежу поступивших тегированных данных. Теория систем массовогообслуживания создавалась с целью описания процессов функционирования и исследованияэффективности огромного многообразия реальных производственных и обслуживающихсистем, с которыми мы сталкиваемся почти на каждом шагу. Граф-схемный язык позволяетестественно описывать такие системы и возникающий в них параллелизм.5) Нужно отметить и другие такие важные особенности параллелизма, как напримерасинхронный и синхронный параллелизм.Первое предполагает реализацию без задержек всех возникающих в процессевыполнения программы возможностей одновременного выполнения ее фрагментовнезависимо от их длительности. Второй вид параллелизма, как правило, обусловлен либологическими причинами (процесс может начаться только после завершения несколькихдругих процессов) или используется с целью упрощения описания и выполненияпараллельных фрагментов (векторные команды – типичный пример).Проблемная среда, обычно характеризуемая используемыми средствами для описанияприсущих ей задач (функциональное, логическое, процессное и др.
описание), диктует своиспособы выявления и представления параллелизма.Перейдем к характеристикам параллелизма, играющим определенную роль в егореализации на многомашинных и многопроцессорных компьютерных системах.6) Ограниченный и неограниченный параллелизм.Мы говорим, что параллелизм в программе (в методе решения задачи) ограничен, еслипри любом ее выполнении на множестве ее входных значений количество могущиходновременно выполняться фрагментов ограниченно.
В противном случае мы говорим, чтопараллелизм в программе не ограничен. Приведем пример параллельной функциивычисления n!:ПЛЕНАРНЫЕ ДОКЛАДЫ ПЯТОЙ МЕЖДУНАРОДНОЙ КОНФЕРЕНЦИИ«ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ И ЗАДАЧИ УПРАВЛЕНИЯ», МОСКВАPACO ‘2010PLENARY PAPERS OF THE FIFTH INTERNATIONAL CONFERENCE“PARALLEL COMPUTING AND CONTROL PROBLEMS”, MOSCOW47где ⌉a⌈ – ближайшее целое к a.Очевидно, F(1, n) = n!, и фрагментыможно вычислять,одновременно. Модель подобного параллельного вычисления значений рекурсивныхфункций детально описана в [10,11].
Для данного примера параллельное вычисление можнопредставить в виде динамческого развертывания и свертывания двоичного дерева, вупрощенном виде сводящего вычисление к форме, изображенной на рис. 1.×××××12n-1nРис. 1. Параллельное вычисление n!Очевидно, что количество шагов последовательного вычисления n! имеет порядок n, апараллельного log2(n).Ускорение n / log2(n) при неограниченном увеличении n растет неограниченно. Этоозначает, что при неограниченном количестве компьютерных ресурсов можно сколь угодноускорять вычисление n! с увеличением n.Хотя теоретики в поисках NP-полных проблем придумывают замысловатые примерыплохо распареллеливаемых задач, реальная практика показывает, что почти любая сложнаязадачалегко декомпозируется и, как правило, хорошо распараллеливается.7) Глубина или степень распараллеливания задачи – следующая важная характеристикапараллелизма, которая позволяет, с одной стороны, охарактеризовать предельное ускорение,которое может быть получено.
С другой стороны, варьируя этот параметр, программист (илисистема управления выполнением программы) достигает минимизации времени выполненияпрограммы и используемых при этом ресурсов на конкретной системе.В вычислении n!, если глубина распараллеливания, определяемая как усредненнаясложность фрагментов программы, выбрана с точностью сложности выполнения операцииумножения, то нельзя надеяться, что будет получен хороший эффект при такомраспараллеливании.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
