Введение в теорию анализа и структуры программ и алгоритмов. Воеводин (2009) (1186032)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Рабочие материалы по курсуПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ДАННЫХРазделВВЕДЕНИЕ В ТЕОРИЮ АНАЛИЗА СТРУКТУРЫПРОГРАММ И АЛГОРИТМОВВл.В.Воеводинзаместительзаместитель директорадиректора НИВЦНИВЦ МГУ,МГУ,член-корреспондентчлен-корреспондент РАН,РАН,voevodin@parallel.ruvoevodin@parallel.ruПользователь: почему?Aijk = Ai-1jk + Bjk + Bjk,i=1,40; j=1,40; k=1,1000Cray C90, пиковая производительность 960 Mflop/sdo k = 1, 1000do j = 1, 40do i = 1, 40A(i,j,k) = A(i-1,j,k)+B(j,k)+B(j,k)Производительность:20 Mflop/s на Cray C90Пользователь: почему?Aijk = Ai-1jk + Bjk + Bjk,i=1,40; j=1,40; k=1,1000Cray C90, пиковая производительность 960 Mflop/sdo i = 1, 40, 2do j = 1, 40do k = 1, 1000A(i,j,k) = A(i-1,j,k)+2*B(j,k)A(i+1,j,k) = A(i,j,k)+2*B(j,k)Производительность:700 Mflop/s на Cray C90Умножение матриц: все ли просто?Фрагмент исходного текста:Возможен ли порядок:( i, k, j) - ?ДА( k, i, j) - ?ДА( k, j, i) - ?ДА( j, i, k) - ?ДАA[i][j] = A[i][j] + B[i][k]*C[k][j] ( j, k, i) - ?ДАfor( i = 0; i < n; ++i)for( j = 0; j < n; ++j)for( k = 0; k < n; ++k)Порядок циклов: ( i, j, k)Почему возможендругой порядок?А зачем нужендругой порядок?Умножение матриц: все ли просто?(сравнение с порядком ( i, j, k) )7Tijk/Txyz65i,j,ki,k,j4j,i,kj,k,i3k,i,jk,j,i21dempsey1pentiumd1woodcrest2woodcrest4woodcrest6woodcrest7clover town1clover town3xeon1opteron2opteron40Решение задачи на компьютереПредметная сторонаЗадачаКомпьютерная сторонаКомпьютерМетодКомпиляторТехнологиипрограммированияАлгоритмПрограммаГрафовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Вершины: процедуры, циклы, линейные участки,операторы, итерации циклов, срабатыванияоператоров…Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Вершины: итерации циклов.for( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}…nКаждая вершина соответствуетдвум операторам (телу цикла),выполненным на одной и той жеитерации цикла.Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Вершины: срабатывания операторов.for( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}……nКаждая вершина соответствуетодному из двух операторов теладанного цикла, выполненному нанекоторой итерации.Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Вершины: процедуры, циклы, линейные участки,операторы, итерации циклов, срабатыванияоператоров…Дуги: отражают связь (отношение) междувершинами.Выделяют два типа отношений:- операционное отношение,отношение- информационное отношение.Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Дуги: операционное отношение:ABДве вершины A и B соединяются направленной дугойтогда и только тогда, когда вершина B может бытьвыполнена сразу после вершины A.Операционное отношение = отношение по передаче управления.Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Дуги: операционное отношение:x(i) = a + b(i)y(i) = 2*x(i) – 3t1 = y(i)*y(i) + 1t2 = b(i) – y(i)*a(1)(2)(3)(4)1234Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Дуги: информационное отношение:ABДве вершины A и B соединяются направленной дугойтогда и только тогда, когда вершина B использует вкачестве аргумента некоторое значение, полученноев вершине A.Информационное отношение = отношение по передаче данных.Графовые модели программБудем представлять программы с помощью графов:набор вершин и множество соединяющих ихнаправленных дуг.Дуги: информационное отношение:x(i) = a + b(i)y(i) = 2*x(i) – 3t1 = y(i)*y(i) + 1t2 = b(i) – y(i)*a(1)12(2)343(3)(4)124Четыре основные модели программГраф управления программы.Вершины: операторыДуги: операционное отношениеfor( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}(1)1(2)2Четыре основные модели программИнформационный граф программы.Вершины: операторыДуги: информационное отношениеfor( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}(1)1(2)2Четыре основные модели программОперационная история программы.Вершины: срабатывания операторовДуги: операционное отношениеfor( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}……(1)(2)n12Четыре основные модели программИнформационная история программы.Вершины: срабатывания операторовДуги: информационное отношениеfor( i = 0; i < n; ++i) {A[i] = A[i – 1] + 2;B[i] = B[i] + A[i];}……(1)(2)n12Несколько вопросов…Может ли информационная история некоторогофрагмента программы иметь 100 вершин и ни однойдуги?ДА.for( i = 0; i < 100; ++i)A[i] = B[i] + C[i]*x;…100Несколько вопросов…Может ли информационная история некоторогофрагмента программы иметь 67 вершин и 3 дуги?ДА.63for( i = 0; i < 63; ++i)A[i] = B[i] + C[i]*x;x1 = 10;x2 = x1+1;x3 = x2+2;x4 = x3+3;…Несколько вопросов…Может ли информационная история некоторогофрагмента программы иметь 20 вершин и 200 дуг?НЕТ.Несколько вопросов…Модель некоторого фрагмента программы вкачестве подграфа содержит следующий граф:Какой моделью могла бы быть исходная модель?ГУИГОИИИМножество графовых моделей программИнформационныемоделиОперационныемодели(опорные точки)Компактные моделиИсторииГраф управления12…Операционная история……12nИнформационный граф Информационная история…1……2n12Какое отношение выбрать для описаниясвойств программ?Операционное отношение?x(i) = a + b(i)y(i) = 2*x(i) – 3t1 = y(i)*y(i) + 1t2 = b(i) – y(i)*a(1)(2)(3)(4)1234Какое отношение выбрать для описаниясвойств программ?Информационная структура – это основа анализасвойств программ и алгоритмов.x(i) = a + b(i)y(i) = 2*x(i) – 3t1 = y(i)*y(i) + 1t2 = b(i) – y(i)*a(1)(2)(3)(4)3y(i)Исполнять толькопоследовательно !x(i)12y(i)4Можно исполнятьпараллельно !Какое отношение выбрать для описаниясвойств программ?Информационная структура – это основа анализасвойств программ и алгоритмов.3y(i)Исполнять толькопоследовательно !x(i)12y(i)4Можно исполнятьпараллельно !Информационная зависимость определяет критерийэквивалентности преобразований программ.Информационная независимость определяет ресурспараллелизма программы.От компактных до историй: что выбратьдля описания свойств программ?Аргументы для выбора степени компактностимодели:• компактность описания,• информативность,• сложность построения.От компактных до историй: что выбратьдля описания свойств программ?Аргументы для выбора степени компактностимодели:• компактность описания,• информативность,12• сложность построения.…………1212От компактных до историй: что выбратьдля описания свойств программ?Аргументы для выбора степени компактностимодели:• компактность описания,(компактные +)• информативность,(истории +)• сложность построения.(компактные +)Граф алгоритма – это параметризованнаяинформационная история:• компактность описания за счет параметризации,• имеет информативность истории,• разработана методика построения графаалгоритма по исходному тексту программ.Схема анализа и преобразованияструктуры программИсходная программаПостроениеграфа алгоритмаПреобразованная программаИсследованиеграфа алгоритмаПреобразованиеграфа алгоритмаТеорема о построении графа алгоритмаТеорема.

Если фрагмент принадлежит к линейномуклассу программ, то на основе статического анализаможно построить компактное описание его графаалгоритма в следующем виде:для каждого входа каждого оператора фрагментабудет указано конечное множество троек вида( N, ∆(N), F(∆, N) )k ,где:N – линейный выпуклый многогранник в пространствевнешних переменных фрагмента,∆(N) – линейный выпуклый многогранник впространстве итераций фрагмента,F(∆, N) – линейная векторная функция, описывающаявходящие дуги оператора.Программы и их графы алгоритмаj…Do i = 1, nDo j = 1, ms = s + A(i, j)…1……Для входа s:n ≥1N1 =  m ≥ 2n≥2N 2 =  m ≥ 12i1≤ i ≤ ni′ = iI1 =  2 ≤ j ≤ m F1 =  ′ j = j −12≤i≤ni′ = i − 1F2 =  ′I2 =  j = 1j =mПрограммы и их графы алгоритмаs=0Do i = 1, ns=s+1Do i = 1, ms=s+1s=s+1m ≥ 1 j1 = m из 3(1)1(2)2…3n(3)m(4)m < 1n ≥ 1 j1 = n из 2…m < 1n < 1 из 14Программы и их графы алгоритма(умножение матриц)Do i = 1, nDo j = 1, n1A(i,j) = 0Do k = 1, nA(i,j) = A(i,j) + B(i,k)*C(k,j)21 ≤ i ≤ n1 ≤ j ≤ nk =1  i1 = i  j1 = j из (1)1 ≤ i ≤ n1 ≤ j ≤ n2 ≤ k ≤ n i = i 1  j1 = j k1 = k − 1 из (2)2k1jiЯрусно-параллельная формаграфа алгоритма7591124163810Как определить и сделать понятным ресурспараллелизма в графе алгоритма (в программе, валгоритме) ?Ярусно-параллельная формаграфа алгоритма75911241638105214381067911Ярусно-параллельная формаграфа алгоритма5214367911810123456789ярусы- начальная вершина каждой дуги расположена на ярусес номером меньшим, чем номер яруса конечнойвершины,- между вершинами, расположенными на одном ярусе, неможет быть дуг.Ярусно-параллельная формаграфа алгоритма5214367911810123456789Высота ЯПФ – это число ярусов,Ширина яруса – число вершин, расположенных на ярусе,Ширина ЯПФ – это максимальная ширина ярусов в ЯПФ.Высота ЯПФ = сложность параллельной реализацииалгоритма/программы.Ярусно-параллельная формаграфа алгоритма521476119831012345678952143128367911671045Каноническая ярусно-параллельная формаграфа алгоритма52143128367911671045Высота канонической ЯПФ = длине критического пути + 1.Каноническая ярусно-параллельная формаграфа алгоритмаfor( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i][j–1] + C[i][j]*x;Чему, согласно закону Амдала, равно максимальноеускорение, которое можно получить при исполненииданного фрагмента на параллельной вычислительнойсистеме?Закон Амдала:S≤α1(1 – α)+ pгде:α – доля последовательных операций,p – число процессоров в системе.Каноническая ярусно-параллельная формаграфа алгоритмаfor( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i][j–1] + C[i][j]*x;m…αЧисло последовательныхоперацийОбщее числоопераций=mn*m=1n…11S≈…1S≈α=jnniВиды параллелизмав алгоритмах и программахпараллелизмконечныймассовыйКонечный параллелизм определяетсяинформационной независимостью некоторыхфрагментов в тексте программы.Массовый параллелизм определяетсяинформационной независимостью итераций цикловпрограммы.Виды параллелизмав алгоритмах и программахКонечный параллелизм.cout << "N=" << N << endl;cycleTestWithUnroll_KJI("k");cycleTestWithUnroll_KJI("j");cycleTestWithUnroll_KJI("i");cycleTestWithUnroll_KJI_3("k");cycleTestWithUnroll_KJI_3("j");cycleTestWithUnroll_KJI_3("i");cycleTest("j,i,k");cycleTest("i,k,j");cycleTest("k,j,i");cycleTest("i,j,k");cycleTest("k,i,j");cycleTest("j,k,i");float ***a12=new float**[N];for (i=0;i<N;i++) {a12[i]=new float*[N];for (j=0;j<N;j++) {a12[i][j]=new float[N];for (k=0;k<N;k++) {a12[i][j][k]=(float)1/(i+j+k+1);}}}for (i=1;i<N;i++)for (j=1;j<N;j++)for (k=1;k<N;k++) {testee[i][k] = testee[i][k] + S[k]*A[k][j][i] + P[i][j]*A[k][j][i-1] +P[i][k]*A[k][j-1][i] + P[j][k]*A[k-1][j][i];}……12312…3Виды параллелизмав алгоритмах и программахМассовый параллелизм.for( i = 0; i < n; ++i)A[i] = B[i] + C[i]*x;…nВиды параллелизмав алгоритмах и программахпараллелизмконечныймассовыйкоординатныйскошенныйВиды параллелизмав алгоритмах и программахКоординатный параллелизм.jm……#pragma omp parallel forfor( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i][j–1] + C[i][j]*x;…11niВиды параллелизмав алгоритмах и программахКоординатный параллелизм.Утверждение: для того чтобы цикл был параллельнымнеобходимо и достаточно, чтобы для любой тройкиграфа алгоритма данного цикла включение ∆ i ⊂ Giбыло верным, где∆ i — это многогранник из тройки,Gi = {f1 = i1,i1 — это параметр анализируемого цикла,f1 — это первая компонента векторной функции Fi изтройки.Виды параллелизмав алгоритмах и программахСкошенный параллелизм.jm……n+m-1for( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i][j–1] + A[i-1][j]*x;n+m-2…11123…niЭквивалентные преобразования программИсходная программаПостроениеграфа алгоритмаПреобразованная программаИсследованиеграфа алгоритмаПреобразованиеграфа алгоритмаЭквивалентные преобразования программ(суммирование элементов массива)s = 0.0;for ( i = 0; i < n; ++i )s = s + A[ i ];Эквивалентные преобразования программ(суммирование элементов массива)1234Эквивалентные преобразования программ3y(i)Исполнять толькопоследовательно !x(i)12y(i)4Информационная зависимость определяет критерийэквивалентности преобразований программ.Информационная независимость определяет ресурспараллелизма программы.Элементарные преобразования цикловПерестановка циклов.jm……for( i = 0; i < n; ++i)for( j = omp0; j <parallelm; ++j) for#pragmaA[i][j] = A[i-1][j] + C[i][j]*x;…11niЭлементарные преобразования цикловПерестановка циклов.jimn……#pragma omp parallel forfor( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i–1][j] + C[i][j]*x;…11mnjiЭлементарные преобразования цикловВсегда ли перестановка цикловявляется эквивалентнымпреобразованием?for( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i+c1][j+c2] + C[i][j]*x;for( i = 0; i < n; ++i)for( j = 0; j < m; ++j)A[i][j] = A[i–1][j+1] + C[i][j]*x;jm11n iЭлементарные преобразования цикловРаспределение циклов.123for( i = 1; i < n; ++i) {A[i] = A[i–1]*p + q;C[i] = (A[i] + B[i–1])*s;B[i] = (A[i] – B[i])*t;}Элементарные преобразования цикловРаспределение циклов.123for( i = 1; i < n; ++i) {A[i] = A[i–1]*p + q;C[i] = (A[i] + B[i–1])*s;B[i] = (A[i] – B[i])*t;}n–1………123Элементарные преобразования цикловРаспределение циклов.123for( i = 1; i < n; ++i) {A[i] = A[i–1]*p + q;C[i] = (A[i] + B[i–1])*s;B[i] = (A[i] – B[i])*t;}112332Утверждение: для того чтобы можно было выполнить распределение цикланеобходимо и достаточно, чтобы распределяемые части находились в разныхкомпонентах сильной связности информационного графа тела данного цикла.Элементарные преобразования цикловРаспределение циклов.for( i = 1; i < n; ++i) {A[i] = A[i–1]*p + q;C[i] = (A[i] + B[i–1])*s;B[i] = (A[i] – B[i])*t;}for( i = 1; i < n; ++i)A[i] = A[i–1]*p + q;#pragma omp parallel forfor( i = 1; i < n; ++i)B[i] = (A[i] – B[i])*t;#pragma omp parallel forfor( i = 1; i < n; ++i)C[i] = (A[i] + B[i–1])*s;Элементарные преобразования цикловРасщепление циклов.for( i = 501; i <= 2000; ++i)A[i] = A[i] + A[i–500];Элементарные преобразования цикловРасщепление циклов.for( i = 501; i <= 2000; ++i)A[i] = A[i] + A[i–500];…501…10011501Элементарные преобразования цикловРасщепление циклов.for( i = 501; i <= 2000; ++i)A[i] = A[i] + A[i–500];500#pragma omp parallel forfor( i = 501; i <= 1000; ++i)A[i] = A[i] + A[i–500];#pragma omp parallel forfor( i = 1001; i <= 1500; ++i)A[i] = A[i] + A[i–500];#pragma omp parallel forfor( i = 1501; i <= 2000; ++i)A[i] = A[i] + A[i–500];…Эквивалентные преобразования программЭквивалентно ли преобразование?for( i = 0; i < n; ++i)D[i] = D[i] * F[i];if( m == 3 )for( i = 0; i < n; ++i)R[i] = P[i] + D[i];elsefor( i = 0; i < n; ++i)R[i] = Q[i] – D[i];if( m == 3 )for( i = 0; i < n; ++i)R[i] = P[i] + D[i] * F[i];elsefor( i = 0; i < n; ++i)R[i] = Q[i] – D[i] * F[i];Простой пример…(последовательный вариант)DO i = 1, nDO j = 1, nU( i + j ) = U( 2*n – i – j + 1)*q + pEndDOEndDOiСовсем не простой пример…(параллельный вариант)DO i = 1, nDO j = 1, n – iПараллельный цикл !U( i + j ) = U( 2*n – i – j + 1)*q + pEnd DODO j = n – i + 1, nПараллельный цикл !U( i + j ) = U( 2*n – i – j + 1)*q + pEnd DOEnd DOРешение задачи на компьютереПредметная сторонаЗадачаКомпьютерная сторонаКомпьютерМетодКомпиляторТехнологиипрограммированияАлгоритмПрограммаРешение СЛАУ: от метода к алгоритму(информационная структура, последовательный вариант)do i = n, 1, -1s=0do j = i+1, ns = s + A(i,j)*x(j)end dox(i) = (b(i) - s)/A(i,i)end doРешение СЛАУ: от метода к алгоритму(информационная структура, параллельный вариант)do i = n, 1, -1s=0do j = n, i+1, -1s = s + A(i,j)*x(j)end dox(i) = (b(i) - s)/A(i,i)end doГде узнать больше?.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги