Ответы к экзамену (2), страница 6

Значение «истина» для pi(x) совпадает со значением.В качестве примера приведем программу вычисления факториала.Functional Program FactorialScheme Factorial{Factorial = (id*<0>).eq -> <1> +(id*<0>).ne -> (id * (id*<1>).minus.Factorial) .

mult;}Application%factorial(6)В этом примере функция вычисления факториала определена с помощью одногофункционального уравнения, содержащего только встроенные в язык функции (id – тождественнаяфункция, eq – функция равенства и т.д.). Программа также содержит задание на вычислениефункции (от аргумента 6).9. Структурный анализ FPTL программ10. Анализ вычислительной сложности FPTL программ24Язык FPTL строится на множестве базисных функций, операций (композиции функций, ·, *, →, +),системы рекурсивных уравнений.Операции языка FPTL:1.

суперпозиция (· ) – ассоциативна, некоммутативна, последовательнаf(m, n) = f1(m, k) · f2(k, n)Вызов всех функций производится по значению (именованию).f1 · (f2 · f3) = (f1 · f2) · f3F(x, y) = if x=0 then 1 else F (x-1, F(x, y))1. конкатенация (*) – ассоциативна, некоммутативна, параллельнаf(m, n1+n2) = f1(m, n1) * f2(m, n2)f(m, 0) = {(α, β) | Ǝ j ((α, j) Є f1 Λ (j, β) Є f2f (g1(x), g2(x), …, gk(x)) = (g1 * g2 * … * gk) · f1. условие (→)f(m, n) = f1(m, k) → f2(m, n)1.

объединение ортогональных функций () – коммутативна, ассоциативнаf1(m, n) и f2(m, n) ортогональны, если пересечение их графиков (т.е. для любогоопределённого , определена только одна из них, но могут быть неопределены обе).Проблема ортогональности алгоритмически неразрешима.f(m, n) = f1(m, n) f2(m, n)f(x) = if P (g(x)) then r (v(x),t(x)) else S (x-1)f1 (x) = x-1f(1, 1) = ((g · p) → (v * t) · r)) ((g · p) → (f1 · S))1. системы функциональных уравненийXi = ti, i = 1, 2, … ,n; F = {fi | i = 1, 2, …, k} – множество всех входящих в термы ti, i = 1, 2, …,n, базисных функций.Приоритет операций: ·, *, →, .Терм:1. любая базисная функция и любая функциональная переменная – терм2.

если t’ и t” – термы, то t’ · t”, t’ * t”, t’ → t”, t’ t” – термы.Термы ti в задании ФС могут быть представлены в эквивалентной форме ti = ti1 Å ti2 Å … Å tik, i =1, 2, …, n, где каждый терм tij не содержит операции ортогонального объединения Å.Пусть C(R) – функция, определяющая сложность параллельного вычисления значения любойфункции R.Для любой базисной функции fi предполагается, что C(fi) задано и представляет собой некоедействительное число.

Также предполагается, что на области определения DR интересующейфункции R для каждого терма tij задана вероятность qij того, что именно его значение будетопределено при вычислении любого значения ti(d) для dÎDR. Эта вероятность напрямую связана вобщем случае с условием, определяющим выполнение этого события.Таким образом, .При этих условиях сложность параллельного вычисления значения функций Xi в задании ФСможет быть определена следующим образом.По заданию ФС последовательно вычисляются «приближения» фиксированной точки для Xiсогласно следующей формуле:Xi(0) = f (нигде не определено),25Xi(k+1) = [Xj(k)/Xj | j = 1, 2, …, n]ti, i = 1, 2, …, n.Очевидно, термы в правых частях приближения Xj(k) не содержат функциональной переменной Xi,и после их приведения к указанной выше эквивалентной форме их вычислительная сложностьюопределяется индукцией по построению:C(fi) = ti (время вычисления значения базисной функции fi)C(t¢®t²) = max{C(t¢) , C(t²)}C(t¢*t²) = max{C(t¢) , C(t²)}C(t¢·t²) = C(t¢) + C(t²)Зная в представлении Xi(k) = ti1(k)Åti2(k)Å .

..Åtivi(k) вероятности qij, i, j = 1, 2, …, vi, того, что привычислении значения Xi(k)(d) будет определено tij(k)(d) = d¢ (остальные значения tit(k)(d), it ¹ ij,будут не определены в силу того, что функции tij(k), i = 1, 2, …, vi попарно ортогональны) можносчитать, что среднее время вычисления Xi(k)(d) для любого d из области определения Ximin(минимальной фиксированной точки для Xi) равно.Более точно, эта формула есть промежуточный шаг в определении среднего времени вычисленияXimin при применении Ximin к любому элементу из области ее определения.Среднее время параллельного вычисления значений функции Ximin определяется как Ci(Xi (kmin))для минимального значения k = kmin такого, что|Ci(Xi(k)) - Ci(Xi(k+1))| £ e,где заданная e – точность вычисления среднего значения.Описанная итеративная процедура вычисления среднего времени параллельного вычислениязначений функций сходится.

Вместо нее можно применять другой, точный метод вычислениясреднего значения, который сводится к решению множества систем линейных уравнений,построенных по ФС, в которых в качестве неизвестных выступают средние времена сложностиC(Xi) параллельных вычислений значений функций Xi в задании ФС.Например, для ФСX1 = (f1*f2)·X1 Å f3®f4·X2 Å f5X2 = f6®f7*f8·X2 Å f9имеем следующую систему уравнений:С(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)) + q3×C(f5)C(X2) = q4×max{C(f6), C(f8)+C(X2)} + q5×C(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).26Продолжая этот процесс, мы построим все искомые линейные системы уравнений сограничениями, разрешая которые мы получим однозначную оценку для среднего временивычисления C(X1) и C(X2) функций X1 и X2.11. Распараллеливание последовательных программ путем трансляциив FPTL программы12.

Средства параллельного программирования MULTITHREADING.Модель параллельного выполнения программ, реализация намногоядерных компьютерах.Потоки27OpenMPOpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master)поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается,что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров необязательно должно быть больше или равно количеству потоков).Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этихзадач, описываются с помощью специальных директив препроцессора соответствующего языка — прагм.Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждыйиз которых имеет свою копию переменной N, предваряется следующей директивой: !$OMP PARALLELPRIVATE(N)Количество создаваемых потоков может регулироваться как самой программой при помощи вызовабиблиотечных процедур, так и извне, при помощи переменных окружения.Ключевыми элементами OpenMP являются● конструкции для создания потоков (директива parallel),● конструкции распределения работы между потоками (директивы DO/for и section),● конструкции для управления работой с данными (выражения shared и private для определениякласса памяти переменных),● конструкции для синхронизации потоков (директивы critical, atomic и barrier),● процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num),● переменные окружения (например, OMP_NUM_THREADS).Pthreadsстандарт POSIX реализации потоков (нитей) выполнения, определяющий API для создания и управленияими.Библиотеки, реализующие этот стандарт (и функции этого стандарта), обычно называются Pthreads(функции имеют приставку «pthread_»).

Хотя наиболее известны варианты для Unix-подобныхоперационных систем, таких как Linux или Solaris, но существует и реализация для Microsoft Windows(Pthreads-w32)○○○○pthread_create(): создание потокаpthread_exit(): завершение потока (должна вызываться функцией потока при завершении)pthread_cancel(): отмена потокаpthread_join(): подключиться к другому потоку и ожидать его завершения; поток, ккоторому необходимо подключиться, должен быть создан с возможностью подключения(PTHREAD_CREATE_JOINABLE)28○●pthread_detach(): отключиться от потока, сделав его при этом отдельным(PTHREAD_CREATE_DETACHED)○ pthread_attr_init(): инициализировать структуру атрибутов потока○ pthread_attr_setdetachstate(): указывает параметр "отделимости" потока (detach state),который говорит о возможности подключения к нему (при помощи pthread_join) другихпотоков (значение PTHREAD_CREATE_JOINABLE) для ожидания окончания или о запретеподключения (значение PTHREAD_CREATE_DETACHED); ресурсы отдельного потока(PTHREAD_CREATE_DETACHED) при завершении автоматически освобождаются ивозвращаются системе○ pthread_attr_destroy(): освободить память от структуры атрибутов потока (уничтожитьдескриптор)Функции синхронизации потоков:○ pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(),pthread_mutex_unlock(): с помощью мьютексов○ pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait(): с помощью условныхпеременных13.

Технологии проектирования параллельных программ, сравнение стехнологиями проектирования последовательных программ.14. Сетевое представление FPTL программ. Приведение их кмаксимальной параллельной форме.15. Управление параллельными процессами в компьютерах икомпьютерных системах. Организация управления..