Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005).pdf), страница 6

Затем генерируются новые n частиц. Процесс продолжается.На наш взгляд, второй способ легко реализуем и требует меньшей переработки исходной программы.Третий способ заключается в распараллеливании процедур, выполняющих вычисление координат движущейся частицы в моментпредполагаемой смены одного элемента траектории спуска другим.При этом перебираются все осевшие частицы. Предлагается разбитьмассив осевших частиц (пусть их будет k) на n (число процессоров)массивов размера k/n. Возьмем k/n в качестве k. Вычисления поручимсвоему процессору. Получим n-кратное ускорение работы этих процедур.25ИНТЕГРИРОВАННАЯ СРЕДА АНАЛИЗА СТРУКТУРНОЙИ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ ФУНКЦИОНАЛЬНЫХПРОГРАММ И ИХ ЦЕЛЕНАПРАВЛЕННЫХЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙС.Е.

Бажанов, М.М. Воронцов, В.П. Кутепов, Д.А. ШестаковМосковский Энергетический Институт (ТУ), МоскваВведениеВ научной группе д.т.н. проф. В.П. Кутепова в настоящее времяреализуется система функционального параллельного программирования для кластеров [1, 3, 8].

Система включает в себя высокоуровневыйязык функционального параллельного программирования, инструментальную среду поддержки разработки функциональных программ наэтом языке и инструментальные средства выполнения функциональных программ на кластерных системах.В рамках этого проекта создана инструментальная среда разработки функциональных параллельных программ, которая позволяет выполнять следующие функции:– структурный анализ функциональных программ по их схемам сцелью выявления циклических, рекурсивных, взаимно рекурсивных идругих определений;– анализа вычислительной сложности параллельных программ спозиций их параллельного выполнения;– проведение эквивалентных преобразований, позволяющих приводить схему функциональной программы в некотором смысле к оптимальной параллельной форме;Методы и алгоритмы структурного анализа подробно рассмотренынами в [1, 9]. В частности результаты этого анализа позволяют строитьэффективные стратегии планирования процессов параллельного выполнения функциональных программ на кластерах [1].Поэтому ниже мы подробно рассмотрим алгоритмы анализа вычислительной сложности и целенаправленных эквивалентных преобразований функциональных программ, используемые в разрабатываемойинтегрированной среде, предназначающиеся для повышения эффективности процесса разработки функциональных программ и улучшения их качественных характеристик.261.

Анализ вычислительной сложностифункциональных программПрактический интерес представляет возможность получения точных оценок времени параллельного выполнения функциональных программ (ФП) при достаточно общих предположениях: известных данных о времени выполнения элементарных функций в ФП и вероятности осуществления (неосуществления) условных переходов в ней. Подобная задача оценивания временной сложности для последовательныхпрограмм решалась в различных работах [4, 5].В [6] разработана формальная система, позволяющая оцениватьвремя параллельного вычисления значений функций по заданным характеристикам временной сложности элементарных функций, входящих в представление функции, и вероятностям осуществления условных переходов.Пусть задана функциональная схема (ФС) Xi = τi, i = 1, 2, …, n;F = {fi | i = 1, 2, …, k} – множество всех входящих в термы τi, i = 1, 2,…, n, базисных функций.В [6] показано, что термы τi в задании ФС могут быть представлены в эквивалентной форме τi = τi1 ⊕ τi2 ⊕ … ⊕ τik, i = 1, 2, …, n, гдекаждый терм τij не содержит операции ортогонального объединения ⊕.Пусть C(R) – функция, определяющая сложность параллельноговычисления значения любой функции R.Для любой базисной функции fi предполагается, что C(fi) задано ипредставляет собой некое действительное число.

Также предполагается, что на области определения DR интересующей функции R для каждого терма τij задана вероятность qij того, что именно его значение будет определено при вычислении любого значения τi(d) для d ∈ DR. Этавероятность напрямую связана в общем случае с условием, определяющим выполнение этого события.kiТаким образом,∑ qij = 1.j =1При этих условиях сложность параллельного вычисления значенияфункций Xi в задании ФС может быть определена следующим образом[6].По заданию ФС последовательно вычисляются «приближения»фиксированной точки для Xi согласно известной формуле [6]:Xi(0) = φ (нигде не определено),27Xi(k+1) = [Xj(k)/Xj | j = 1, 2, …, n]τi, i = 1, 2, …, n.Очевидно, термы в правых частях приближения Xj(k) не содержатфункциональной переменной Xi, и после их приведения к указаннойвыше эквивалентной форме, согласно [6], их вычислительная сложность определяется индукцией по построению:C(fi) = ti (время вычисления значения базисной функции fi ),C(τ′→τ″) = max{C(τ′), C(τ″)},C(τ′∗τ″) = max{C(τ′), C(τ″)},C(τ′•τ″) = C(τ′) + C(τ″).Зная в представлении Xi(k) = τi1(k) ⊕ τi2(k) ⊕ ...

⊕ τivi(k) вероятностиqij, i, j = 1, 2, …, vi, того, что при вычислении значения Xi(k)(d) будетопределено τij(k)(d) = d′ (остальные значения τit(k)(d), it ≠ ij, будут неопределены в силу того, что функции τij(k), i = 1, 2, …, vi попарно ортогональны) можно считать, что среднее время вычисления Xi(k)(d) длялюбого d из области определения Ximin (минимальной фиксированнойточки для Xi ) равноnC ( X i( k ) ) = ∑ qij C ( τij ).j −1Более точно, эта формула есть промежуточный шаг в определениисреднего времени вычисления Ximin при применении Ximin к любомуэлементу из области ее определения.Среднее время параллельного вычисления значений функции Ximinопределяется как Ci(Xi (kmin)) для минимального значения k = kmin такого, что|Ci(Xi(k)) − Ci(Xi(k+1))| ≤ ε,где заданная ε – точность вычисления среднего значения.Описанная итеративная процедура вычисления среднего временипараллельного вычисления значений функций сходится [6].

Вместо нееможно применять другой, точный метод вычисления среднего значения, который сводится к решению множества систем линейных уравнений, построенных по ФС, в которых в качестве неизвестных выступают средние времена сложности C(Xi) параллельных вычислений значений функций Xi в задании ФС.Например, для ФСX1 = (f1∗f2)•X1 ⊕ f3 → f4•X2 ⊕ f5,X2 = f6 → f7∗f8•X2 ⊕ f928имеем следующую систему уравнений:С(X1) = q1⋅(max{C(f1), C(f2)} + C(X1)) ++ q2⋅max{C(f3), C(f4) + C(X2)} + q3⋅C(f5),C(X2) = q4⋅max{C(f6), max{C(f7), C(f8) + C(X2)}} + q5⋅C(f9).Здесь q1, q2, q3, q4, q5 – вероятности для соответствующих термов в ФС;q1 + q2 + q3 = 1; q4 + q5 = 1.Из нее, вводя соответствующие условия – ограничения для всевозможных предположений о сложности C(Xi) функциональных переменных, можно построить множество систем линейных уравнений, решаякоторые и проверяя выполнение введенных условий, можно получитьоднозначную оценку средней сложности параллельных вычисленийлюбой определяемой в ФС функции Xi, i = 1, 2, …, n.Для рассматриваемого примера имеем следующие системы линейных уравнений с условиями – ограничениями:1.

С(X1) = q1⋅(max{C(f1), C(f2)} + C(X1)) + q2⋅C(f3) + q3⋅C(f5),C(X2) = q4⋅C(f6) + q5⋅C(f9),если C(f4) + C(X2) ≤ C(f3) и max{C(f7), C(f8) + C(X2)} ≤ C(f6).2. С(X1) = q1(max{C(f1), C(f2)} + C(X1)) + q2(C(f4) + C(X2)) +q3C(f5),C(X2) = q4 max{C(f6), C(f8) + C(X2)} + q5C(f9),если C(f3) < C(f4) + C(X2) и C(f6) < max{C(f7), C(f8) + C(X2)}.Эта система уравнений сводится к двум системам линейных уравнений с рассмотрением ограничений для каждой из них:C(f7) ≤ C(f8) + C(X2) и C(f8) + C(X2) < C(f7).Продолжая этот процесс, мы построим все искомые линейные системы уравнений с ограничениями, разрешая которые мы получим однозначную оценку для среднего времени вычисления C(X1) и C(X2)функций X1 и X2.В интегрированной среде поддержки проектирования функциональных программ реализован описанный выше метод итерационноговычисления среднего значения параллельного вычисления значенийфункций.2.

Эквивалентные преобразования функциональных программНа функциональном языке, как и на любом другом языке программирования, для реализации каждого алгоритма может быть написано29бесконечно большое число программ. Все эти программы будут функционально тождественны, однако они будут иметь различные характеристики. Так как во многих случаях основной задачей является улучшение программной реализации, то из всех имеющихся выбираютсяпрограммы, имеющие оптимальные сложностные характеристики.Кроме того, встает вопрос, как, преобразовывая программу при сохранении ее функционального значения, улучшить характеристики.В [7] предложено исчисление преобразований для рассматриваемого языка функционального параллельного программирования.

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