Алгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) в (1.1) определяются организацией работы памяти. Если используется ассоциативная память (АЗУ), в которой операцию логического сложения можно выполнить непосредственным слиянием содержимого ячейки \[ x_{ij}^{k-1} \] с результирующим операндом \[ х_{ij}^{k-1}* x_{kj}^{k-1} \] , то \[ T_{АЗУ}= 3(N)^3\tau_{АЗУ} \] . В противном случае \[ T_{ОЗУ}= 4(N)^3\tau_{ОЗУ} \] .

В однопроцессорных ЭВМ операционные временные затраты на (1.1) определяются соотношением \[ T_{ОУ}= 2(N)^3\tau_{ОУ} \] .

Из приведенных данных видно:

1. В алгоритме Уошэлла - Флойда временные затраты на пересылки данных в 1,5-2 раза превышают затраты на обработку. Это вывод справедлив и без учета издержек на перезагрузку кеш-памяти, которая используется не только программой пользователя, но и системными программами даже в однозадачном режиме работы ЭВМ. Затраты на пересылки превосходят все остальные как за счет количества операций, так и за счет "средней" длительности каждой из них. "Средняя" длительность одной пересылки учитывает издержки на паразитное обновление кеш-памяти, и поэтому \[ \tau_c(p) < \tau_{ОЗУ} \] , и только при полном совмещении цикла обработки одной страницы кеш-памяти с циклом обновления другой ее страницы \[ \tau_c(p) = \tau_{ОЗУ} \] , но даже RISC -процессорах \[ \tau_{ОЗУ}\ge 2\tau_c(p) \] .
2. Из всех видов временных затрат операционные затраты алгоритма Уошэлла - Флойда, которые, собственно, только и интересуют пользователя, оказались минимальными. Полученные данные говорят о том, что при решении задач типа транзитивного замыкания в принципе невозможно получить коэффициент использования физических возможностей процессора выше 10-15 %. Попытка минимизации операционных и жестко связанных с ними коммутационных затрат приводит к включению оператора \[ if \] во второй уровень вложенности цикла \[ for \] и при наличии оптимизирующего компилятора это выполняется автоматически: \[ For\,\, k\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ if\,\,(x_{ik}^{k-1})=0)\to x_{ij}^{k}:=x_{ij}^{k} \text{ и } i:=i+1,\\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ x_{ij}^k:= x_{ij}^{k-1} + x_{ik}^{k-1} * x_{kj}^{k-1}, \] \[ For\,\, k\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ if\,\,(x_{ij}^{k-1})=1)\to x_{ij}^{k}:=x_{ij}^{k} \text{ и } i:=i+1,\\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ x_{ij}^k:= x_{ij}^{k-1} + x_{ik}^{k-1} * x_{kj}^{k-1}, \]

В вычислительном алгоритме (1.2) экономия от включения цикла \[ if \] зависит от количества элементов матрицы смежности \[ ||А^{k}|| \] с "нулевыми" значениями, а в (1.3) - от количества элементов с "единичными" значениями, которое возрастает с ростом индекса \[ k \] . Поэтому по мере роста индекса \[ k \] в случае (1.2) экономия от включения цикла \[ if \] будет падать, а в случае (1.3) - возрастать, но в любом случае затраты на управление увеличатся на \[ \Delta T_u = (2N)^3\tau_c(p) \] .

Отсюда, в "пользовательском" варианте предпочтение следует отдавать вычислительному алгоритму по варианту (1.3), но в синтетические и испытательные программы для полноты эксперимента необходимо включать все три варианта, так как они моделируют различные условия (не) зависимости временных затрат от содержимого преобразуемых данных.

Алгоритм Уошэлла - Флойда допускает только ОКМД-режим распараллеливания вычислений как по векторной, так и по конвейерной составляющей с коэффициентами \[ \gamma_{v} =\overline{l,N^{2}} \] и \[ \gamma_{k} =\overline{l,N} \] соответственно. Приведенные данные говорят о том, что минимально возможное время \[ T_{АЗУ}= \tau_{АЗУ} \] решения задачи транзитивного замыкания по классическому алгоритму Уошэлла - Флойда можно получить в специализированной параллельной архитектуре с максимальным коэффициентом векторно-конвейерного распараллеливания \[ \gamma = \max{\gamma_{v}} * \max{\gamma_{k}} = N^{3} \] , который поддерживается полнодоступным ассоциативным ЗУ на \[ N^{3} \] портов и \[ N^{3} \] операционными устройствами, осуществляющими обмен данными с каждым портом ассоциативного ЗУ по двум входным и одной выходной однобитной шине данных. Во всех остальных архитектурах время решения за дачи лимитируется характеристиками ОЗУ, поддерживающими соответствующий коэффициент распараллеливания вычислений по потокам данных: \[ \tau_{АЗУ} < T \le 4(N)^3\tau_{ОЗУ} \] .

Задачи векторно-матричной алгебры перекрывают весь спектр размерностей задач табл. 1.1:

• \[ O(N^{3}) \] , если выполняется умножение матриц \[ ||А||*||В|| = ||С|| \] ;
• \[ O(N^{2}) \] , если выполняется умножение векторов \[ А*В = С \] ;
• \[ O(N) \] , если выполняется сложение двух векторов \[ А+В = С \] .

Поэтому эти задачи стараются включать во все испытательные и синтетические программы для оценки пропускной способности ВС по потокам команд и данных практически всех параллельных архитектур.

При всей кажущейся простоте исходного алгоритма умножения матриц, его можно реализовать тремя типами вычислительных алгоритмов, отличающимися порядком формирования результирующей матрицы.

1. Вычислительный алгоритм умножения матриц с поэлементным порядком формирования результирующей матрицы: \[ For\,\, k\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ c_{ik}=\sum\limits_{j=1}^{N}{a_{ij}*b_{ij}},\\ \text{где } a_{ij} \in||A||,\,b_{jk} \in||B||,\,c_{ik} \in||C||. \]
2. Вычислительный алгоритм умножения матриц с "построчным" порядком формирования результирующей матрицы: \[ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ \langle c_{ik}{\rangle}=\sum\limits_{j=1}^{N}{a_{ij}}\prod\limits_{k=1}^{N}{{\langle}b_{jk}{\rangle}}, \]

   где \[ {\langle}b_{jk}{\rangle} \] , \[ {\langle}с_{ik}{\rangle} \] - соответственно строки матриц \[ ||B|| \] и \[ ||C|| \]
3. Вычислительный алгоритм умножения матриц с порядком формиро вания результирующей матрицы "по столбцам": \[ For\,\, j\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ {\langle}c_{ik}{\rangle}=\sum\limits_{j=1}^{N}{b_{jk}}\prod\limits_{k=1}^{N}{{\langle}a_{ji}{\rangle}}, \]

   где \[ {\langle}a_{ij}{\rangle} \] , \[ {\langle}с_{ik}{\rangle} \] - соответственно строки матриц \[ ||A|| \] и \[ ||C|| \]

Изменение порядка формирования результирующей матрицы сопровождается изменением порядка вызова данных, который может либо совпадать, либо не совпадать с порядком их хранения в ОЗУ. В современных ЭВМ данные в ОЗУ чаще хранятся по строкам и реже по столбцам. Это значит, что при "чтении" данных по столбцам и больших размерах преобразуемых матриц, превышающих размеры доступной пользователю кеш-памяти, возрастают паразитные пересылки страниц между кеш-памятью и ОЗУ и, как следствие, увеличивается продолжительность "среднего" цикла обращения к памяти.

Поэтому с помощью такой представительной задачи можно исследовать издержки на организацию обмена с кеш-памятью, для чего достаточно:

• с помощью датчика псевдослучайных чисел построить матрицы \[ ||А|| \] и \[ ||В|| \] размером \[ N*N \] ;
• реализовать алгоритмы поэлементного, "построчного" и "постолбцового" порядков формирования результирующей матрицы \[ ||C|| \] , изменяя \[ N \] в широких пределах, зависящих от размеров кеш-памяти;
• выполнить транспонирование матрицы \[ ||C|| \] после поэлементного ее формирования и определить временные затраты;
• реализовать постолбцовое формирование матрицы \[ ||C|| \] с "построчным" порядком записи ее элементов;
• определить вытекающие из каждого вычислительного алгоритма затраты на управление, пересылки данных и операционные затраты и сравнить их с экспериментальными данными.

Временные затраты на управление в задачах векторно-матричной алгебры аналогичны затратам задачи о транзитивном замыкании и в зависимости от архитектуры устройства управления процессора могут составлять либо \[ T_{u} = (3N)^3\tau_c(p) \] , либо \[ T_{u}= (N+3)\tau_c(p) \] .

Операционные временные затраты в данном случае зависят от схемы распараллеливания и не зависят от вычислительного алгоритма. Поэтому имеет смысл говорить только об удельных операционных затратах на формирование одного элемента результирующей матрицы, так как общее время вычисления всех ее элементов определяется доступным пользователю коэффициентом распараллеливания.

В изделиях микроэлектроники наибольшее распространение получили две схемы векторно-конвейерного распараллеливания ОКМД-типа на основе коллективов "скаляторных" операционных устройств, каждое из которых представляет последовательно соединенные умножитель на два входа и сумматор (рис. 1.5).

Продолжительность \[ T_{ОУ}(c_{ik}) = 2N\tau_c(*) \] цикла формирования элемента \[ c_{ik} \] , результирующей матрицы схемы рис. 1.5-а более чем в 2 раза может превосходить продолжительность \[ T_{ОУ}( c_{ik}) = \tau_c (*)+N\tau_c (+) \] того же цикла схемы рис. 1.5-б. В первом случае темп работы двухступенчатого конвейера из умножителя и сумматора-накопителя регламентирует более медленный умножитель, а во втором случае фаза умножения выполняется по всем входным операндам одновременно и поэтому темп работы \[ N \] ступенчатого конвейера лимитирует только фаза суммирования. Но это справедливо для (полу)заказного исполнения "скаляторов", в рамках которого справедливо неравенство \[ \tau_c (*) > \tau_c (+) \] , где \[ \tau_c (*) \] и \[ \tau_{c}(+) \] - соответственно достижимое время цикла срабатывания аппаратно реализованного умножителя и сумматора. В RISC -архитектурах по определению \[ \tau_{c}(*) = \tau_{c}(+) \] и темп вычисления элемента результирующей матрицы по схеме рис. 1.5-б определяется соотношением \[ T_{ОУ}(c_{ik}) = (N+1) \tau_{c}(*) \] .

В любом случае такой выигрыш оплачивается практически TV -кратным увеличением аппаратных затрат на схему рис. 1.5-б. Поэтому на практике большее распространение получила схема рис. 1.5-а, на основе которой можно варьировать коэффициентом распараллеливания \[ \gamma \] в пределах \[ \gamma = \overline{1,N^2} \] , а не \[ \gamma = \overline{1,N^3} \] .

При вычислении одного элемента результирующей матрицы на одном "скаляторном" устройстве рис. 1.5-а удельные алгоритмические временные затраты на коммутацию (пересылки данных в одноадресной ЭВМ) для всех трех алгоритмов определяются соотношением \[ T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ} \] . Снизить эти затраты можно в схеме "скалятора" с \[ N \] аккумуляторами, образующими FIFO -регистровую цепочку. Для такой схемы \[ T_{ОЗУ}(c_{ik}) = (N+2)\tau_{ОЗУ} \] (рис. 1.6).

"Скалятор" с \[ N \] аккумуляторами наиболее эффективен при построчном формировании элементов результирующей матрицы, так как в этом случае:

• элемент \[ a_{i}j \] вызывается один раз и хранится в регистре умножителя в течение всего времени обработки строки \[ (b_{jk}) \] ;
• построчный порядок "чтения" элементов обеих матриц \[ ||А|| \] и \[ ||В|| \] совпадает с порядком их хранения в ОЗУ, что минимизирует количество паразитных перезагрузок кеш-памяти при "больших" размерах этих матриц.

Однако такой двукратный выигрыш во времени оплачивается \[ N \] -кратным ростом аппаратных затрат на FIFO -регистровую цепочку аккумуляторов.

Из приведенных данных видно, что эффективное совмещение обработки одной области кеш-памяти с обновлением другой ее области можно получить, если \[ T_{ОЗУ}(c_{ik}) = 2N\tau_c(*) \approx T_{ОЗУ}(c_{ik}) = (2N+1)\tau_{ОЗУ} \] , что осуществимо, если \[ \tau_{c}(*) \approx \tau_{ОЗУ} \] . Последние условие как раз и предполагает отсутствие паразитных обновлений кеш-памяти за период вычисления матрицы \[ ||C|| \] .

Таким образом, включив в состав синтетических и испытательных программ все три варианта вычислительных алгоритмов умножения матриц, можно с различной степенью интенсивности симулировать паразитные обновления кеш-памяти по ходу вычислений. Это позволяет при одних и тех же исходных данных в процессе испытаний и исследований (Б)ВС варьировать общим временем решения задач векторно-матричной алгебры в пределах 20-40 %.

Как показали эмпирические данные, в пользовательскую библиотеку вычислительных алгоритмов векторно-матричной алгебры, содержащую подпрограммы поэлементного умножения матриц и транспонирования, имеет смысл включить подпрограмму построчного умножения, что улучшает качество работы всего пакета на 20-30 %.

Задача сортировки данных методом "пузырька" относится к классу задач типа \[ O(N^{2}) \le; N(N-1)/2 \] , и при ее распараллеливании возникают достаточно типичные издержки управления коллективом вычислителей, которые связаны с информационной зависимостью параллельных процессов и которые кардинальным образом снижают фактический коэффициент распараллеливания.

Алгоритм сортировки методом "пузырька":

\[ For\,\, i\,\, from\,\, 1\,\, to\,\, N, \\ For\,\, j\,\, from\,\, i+1\,\, to\,\, N, \\ If\,\,x_{i}>x_j\Rigtharrow Tr(x_{i},x_j) \]

где \[ Tr(x_{i}, x_{j}) \] представляет собой транспозицию (перестановку) сравниваемых элементов \[ x_i \] и \[ x_j \] .

Чтобы исследовать издержки управления сортировкой данных методом "пузырька", связанные с ростом коэффициента распараллеливания вычислений, достаточно:

1. С помощью датчика псевдослучайных чисел построить последовательность чисел \[ \{x_{i}\} \] мощности \[ N \] .
2. Упорядочить по возрастанию последовательность \[ \{x_{i}\}\Rightarrow {\langle}x_{i}{\rangle} \] методом "пузырька" и подсчитать количество выполненных транспозиций \[ \eta(N) \] .
3. Разбить последовательность \[ \{x_{i}\} \] на две равные части: \[ \{x_{i} \} = \{x_i\}_1U\{x_i\}_2 \] и повторить шаг 2 для каждой последовательности \[ \{x_{i}\}_1 \] и \[ \{x_{i}\}_2 \] , подсчитав \[ \eta_1(N/2) \] и \[ \eta_2(N/2) \] . Выбрать и запомнить \[ \max[\eta_1(N/2), \eta_2(N/2)] \] .
4. Сравнить "старший" элемент упорядоченной последовательности \[ x_{i1}\in{\langle}\{x_{i}\}_{1}{\rangle} \] с младшим" элементом последовательности \[ x_{i2}\in{\langle}\{x_{i}\}_{2}{\rangle} \] и при необходимости выполнить транспозицию, переводящую элемент \[ x_{i2}\in{\langle}\{x_{i}\}_{1}{\rangle} \] и элемент \[ x_{i1}\in{\langle}\{x_{i}\}_{2}{\rangle} \] .
5. Упорядочить модифицированные последовательности \[ {\langle}\{x_{i}}_{12}{\rangle} \] и \[ {\langle}\{x_{i}}_{21}{\rangle} \] и определить \[ \max[\eta_1(N/2), \eta_2(N/2)] \] . Запомнить сумму \[ \eta(N_1,N_2)=\max[\eta_{1}(N/2), \eta_{2} (N/2)]+\max[\eta_{12} (N/2), \eta_{21} (N/2)] \] .
6. Шаги 4 и 5 повторять до тех пор, пока \[ x_{i1} \le x_{i2} \] .
7. Шаги 3-6 повторить для \[ k = (4-256) \] , где \[ k \] - коэффициент распараллеливания алгоритма сортировки данных.

Условие останова алгоритма сформулировано в шестом пункте, из чего следует, что его размерность нарастает по \[ k: x_{i1} \le x_{i2} ... \le x_{ik} \] . Это условие представляет простейший алгоритм управления многопроцессорной системой, в которой согласно условию четвертого шага запуск следующей итерации многопроцессорной сортировки осуществляется синхронно и синфазно по всем процессорам и после того, как завершил работу самый нагруженный из них. Возникающие при этом "простои" процессоров накапливаются в сумме \[ \eta(\{N_{k} \}) \] , которая вычисляется на пятом шаге. Поэтому отношение \[ \eta(N)/\eta(\{N_k\}) \] характеризует реально полученный "средний" коэффициент распараллеливания вычислений, так как "объем выполненной работы" (число транспозиций) и в однопроцессорном, и в многопроцессорном вариантах один и тот же.

Эмпирические данные говорят о том, что начиная с \[ k = 4-5 \] один и более процессоров гарантировано начинают работать "вхолостую" и их количество возрастает с ростом \[ k \] до такой степени, что делает бессмысленным наращивание аппаратной платформы уже при \[ k \ge 16 \] .

В таких условиях можно варьировать правилами останова, что позволяет симулировать тот или иной вариант управления многопроцессорной архитектурой: распределенной, централизованной, потоком данных и т. п., который призван минимизировать простои базового алгоритма управления.

Таким образом, "представительность" задач сортировки состоит в том, что они позволяют исследовать пропускную способность сильно связанных многопроцессорных систем, не усложняя при этом вычислительное ядро алгоритма.

Одним из главных ограничивающих коэффициент распараллеливания факторов связан с падением вычислительной устойчивости алгоритмов при их реализации на параллельных архитектурах (см. раздел 6.6 курса "Задачи и модели вычислительных наноструктур"). Поэтому одна из главных задач исследований и испытаний параллельных (Б)ВС состоит в том, чтобы определить вычислительную устойчивость всех решаемых задач.

В вычислительной технике алгоритм и реализующая его программа считаются вычислительно устойчивыми, если погрешность вычисления результата не превосходит погрешности представления исходных данных.

Методику исследования вычислительной устойчивости алгоритмов проще всего проиллюстрировать на примере программы суммирования членов псевдослучайной последовательности из \[ N \] элементов.