    
Раздел: Документация
0 ... 29 30 31 32 33 34 35 ... 78 слоя, и, поскольку начальные значения линий данных - нулевые, этот случай трактуется так, как если бы матрица была дополнена первой нулевой строкой и было бы справедливо равенство q = l. Вращения в данном случае начинаются простой заменой нулевой строки на следующие строки и матрица проходит через структуру без изменения. Рассмотрим теперь случаи, когда матрица слишком широка для систолической структуры (w > vv). Как и ранее, обработка матрицы производится за несколько проходов подматриц. Конечно, потребуется некоторая аппаратная модификация, позволяющая зациклить обработку элементов, которые не прошли через всю строку. Так как подматрицы могут быть заполненными (ширина ленты « размерности), а систолическая структура спроектирована для разреженных матриц (ширина полосы <С размерности), можно ожидать некоторого ухудшения эффективности. Будем компенсировать его соответствующим усложнением аппаратных средств. Рассмотрим две схемы. Первая аналогична схеме из примера, приведенного в гл. 22: обнуление всех элементов, лежащих ниже главной диагонали группами из к столбцов, при использовании Г (п - 1) /ЛЛ проходов; к > \ определяется величинами w и q. В каждом прогоне необходимо принимать во внимание только большее окно, состоящее из г >q+k строк и п столбцов, где г должно быть определено. Большее окно содержит все элементы, которые должны быть обнулены, и движется вниз по матрице, начиная со строк 1, к+1, 2к+ 1 и т.д. в последующих прогонах; в последнем прогоне несуществующие строки полагаем нулевыми. Большее (основное) окно будет всегда содержать некоторое число ведущих и нулевых столбцов, последними можно пренебречь; максимальное число ненулевых столбцов может достигать г +р. Так как процессорная структура способна исключать за один прогон только q поддиагоналей, то при q>q для обработки г строк будет необходимо Vqjq~\ прогонов снизу вверх. С этой целью используем среднее окно, состоящее из гг =q+k строк и п столбцов и продвигающееся вверх внутри большого окна. При этом нужно определить разбиение гг строк на передний блок, состоящий из Sj столбцов, и на задний блок, состоящий из s2 столбцов. Наибольшее число ненулевых задних блоков равно т=Г (г +р --si)/s2~!. Выбираем k<Sx с целью, чтобы все необходимые повороты могли быть определены из первого блока. Для этого требуется, чтобы IIЭ каждого слоя структуры, который обычно начинал вращения, был включен для обработки принимаемой информации; значения самих углов поворота могут храниться вне структуры в сдвиговых регистрах - один регистр на один слой ПЭ в структуре. Блок размера г г Xs i, полученный из последних г t строк переднего блока размера г Xs i, имеет не больше ~q ненулевых поддиагоналей, и, таким образом, они обнуляются за один прогон через систолическую структуру, полученные повороты применяются к т задним блокам размера г xXs2, среднее окно перемещается вверх на q строк и весь этот процесс повторяется. Поэтому меньшие окна состоят из s,- строк и перемещаются вправо по k-t
Рис 112. Расположение окна и исключаемых элементов: / - начальное в конечное расположение первого среднего окна; 2 - начальное и конечное расположение второго среднего окна; 3 - другой способ начального расположения второго среднего окна. Элементы, исключенные на первом прогоне удалены (левый нижний угол) среднему окну. Размещение окон и последовательность исключений иллюстрируются на рис. 11.2. Эффективность использования процессора может быть улучшена, если дополнить систолическую (qXw)-структуру двумя треугольниками из 2q2 элементов задержек, как показано на рис. 11.1 для q=w = 3. Это позволяет вводить дополнительные данные в верхние уровни структуры согласно определенной закономерности. Пара элементов задержки эквивалентна обыкновенному ПЭ с фиксированным тождественным вращением. Исходя из рассмотрения числа ненулевых диагоналей и входных портов (одна диагональ на порт) требуем, чтобы: для переднего блока размера rrXsi выполнялось условие q+S\ w + q, для заднего блока размера г j Xs2 - условие г j +s2 1 <й> +q. Эти условия определяют все основные параметры и ограничения. Грубая оценка времени разложения дает следующую формулу: (п/к) (q/q) (передний блок + т-задний блок + «?-г0) Отсюда следует, что значение т будет минимально, если минимизируется г и максимизируется s{. Итак, выбираем соотношения
(1,0) {q,0).-4qrq+1) Загрузка данных:  Рис. 11.3. Пример фиксированного вращения н поступления данных для дополненной процессорной матрицы: элемент (I,/), 1 <i</+<jjl <]<$, поступает в ячейку (Д, w -q + +1 - / ) в момент времени i +/ - 1, покидает ячейку (1, W+I-/) в момент времени 2 (</ - 1) +1 +/ ; элемент (i,s+j), l<i<rx, 1< </ < w - 1, поступает в ячейку 07, I - (?) в момент времени vv+l +/ - 1, покидает ячейку (1, i), в момент времени 2 (<? - 1) + (1,Sj + w-1) (r,,Sj + VL>-1) Sj = W, s2 = w + q-rl + l= w - k+l, r = q + k, m = [(r + p- s,)/s2l = [w/s2~\ ~ 1 -При выборе таких соотношений время обработки переднего блока составит w + 3q +k - 2, заднего блока vv + 3q - 1. Остается выбрать значение к между значениями 1 и w с целью минимизации времени выполнения; очевидно, оно будет минимальным при к *&w/2. Однако из рис. 11.2 следует, что q w поворотов могут начинаться с передних блоков и зацикливаться перпендикулярно q+k строкам. Задержку между преобразованиями задних блоков можно исключить, взяв k=w и использовав метод фиксированного вращения вместо первоначального изменяемого вращения. Это показано на рис. 11.3. Поворот (/,/) начинается с обнуления элемента (/,/) в переднем блоке, где индексы относятся к среднему окну. Далее в отмеченных на рис. 11.3 процессорных элементах фиксируем поворот (/+/,/) в ПЭ с координатами (£,/), Кг <q, K/<w. Элементы задержки не требуют изменения. Загрузка значений углов поворота для второго прогона осуществляется довольно легко при введении дополнительного управляющего сигнала. В первом прогоне поворот начинается слева и перемещается вправо; когда 198 достигает нужного положения, создается копия; это положение может быть идентифицировано управляющим сигналом, который проходил бы налево и вверх и начинался бы в правом нижнем ПЭ, обозначенном {Д, 1), когда процесс поворота (д + 1,1) его достигнет. В конце первого прохода все элементы поворота оказываются на месте, и можно начать второй прогон без задержки (рис. 11.4). Время для вычисления среднего окна, таким образом, составляет w + 3(g+vv - 1),а общее время \(П - \)/w]\qlq\(yv + 3(q + w - 1) + i0). Это, по существу, оптимальная процедура. Преимущество структуры с изменяемыми-фиксированными вращениями по сравнению со структурой с фиксированными вращениями состоит в том, что для генерации вращений в первой необходимо иметь только q процессорных элементов вместо q - w. Наличие управляющего сигнала не вносит дополнительной сложности в проектирование ПЭ. Также нет необходимости хранения значений углов поворота вне структуры, по крайней мере для рассматриваемого метода разбиения. Недостатком является необходимость двух способов ввода данных: сначала диагоналей, а затем строк. Это можно достаточно легко осуществить путем передачи строк данных в порт через преобразующий фильтр, размер которого пропорционален величине q-w. Имеется еще одна последовательность исключений, по сути близкая к рассмотренной в [11, 12]: исключение q самых дальних от центра поддиагоналей и повторение операции с использованием rq/q~] прогонов. Теперь основное окно состоит из строк с номерами (q+ 1 - q) .. .и, где q - число оставшихся ненулевых поддиагоналей; верхняя строка передвигается вверх на q строк. Среднее окно состоит из rt строк, как и ранее, но продвигается вниз на к строк внутри основного окна, начиная с вершины (см. рис. 11.2). Подсчетом числа обнуленных элементов можно показать, что общее время будет таким же, как и в предыдущем случае. t в Рис. 11.4. Временная диаграмма для рис. 11.3 cq = w=3. Вращения и элементы матрицы показаны только своими индексами. Не указаны элементы, для которых х- у = =0 и вращение - I. Используемое у х Время вращение
Во всех рассмотренных методах разбиения матриц на блоки производилась попытка использовать матрицы с такими же размерами по горизонтали, как и в исходной матрице. Так как часто бывает легче разработать алгоритмы для обработки малых подматриц, рассмотрим два случая, где комбинируются два конкурирующих метода. Пусть С = АВ А, А2 А3 [В,В2 CjjCl2. C2iC22. где А, В - матрицы размеров пХг; г Хт соответственно. Эта формула содержит операцию умножения блоков, которая выполняется с помощью систолической структуры с накапливающей ячейкой для операции скалярного произведения. Предположим, что процессорная структура содержит пХт ортогонально связанных ПЭ, вычисляет матричное произведение (пХк)Х(кХ Xw) для произвольного к и хранит результат. Это соответствует встречно-поточному процессору, рассмотренному в работе [24]. Матрицы Аг- (размера пХг) и By (размера г Хт) дополняются нулевыми строками и столбцами, если это необходимо. В [18] описан метод, основанный на использовании управляющих сигналов и переплетении данных для считывания из блоков С во время вычислений последующих результатов А,-Ву. При и = 1, как показано в [20], разгрузка производится сразу же и не требуется специальных приемов. Основной недостаток алгоритма блочного умножения заключается в том, что А,- вводится построчно, в го время как В;- - по столбцам, что требует либо двойственного механизма памяти, либо большой, но простой систолической структуры для оперативного транспонирования. Исчерпывающий анализ других методов для векторных конвейерных машин дан в работе [51; он может быть распространен и на систолические структуры. LU-разложение блочных матриц часто рассматривается как технический прием для всех параллельных процессоров (например, [9,14-16]). Выбор главных элементов может быть осуществлен путем введения либо дополнительной аппаратуры [14], либо локальной памяти [16] при увеличении затрат времени на вычисления. Недостаток метода заключается в том, что поиск главного элемента только внутри диагонального блока недостаточен для численной устойчивости при отсутствии дополнительных сведений о матрице. Движение данных в систолической структуре можно улучшить, объединив разбиение К раута с ортогональной редукцией блочных строк и некоторыми друшми базовыми операциями. Предположим, что имеются аппаратурные средства фиксированного вращения для приведения матрицы размера рХп к верхней трапецеидальной форме. Разобьем матрицу А размера for / =1 torn-1 do привести ... А,и) = (А,-,- . . - А,„) - (L„ • • - Ч,- l) Ui числить
-и! • Ln,l-1 U, Ц--и Ur.1 и Последний шаг может быть выполнен транспонированием блоков и решением нижних треугольных систем. По практическим соображениям матрицу Lj-j- лучше не вычислять непосредственно на последнем шаге, поскольку она наверняка не будет ортогональной из-за погрешностей округления. Обычный алгоритм Краута дает LU-разложение матрицы Ац, а в остальном совпадает с описанным. 11.5. РАЗРЕЖЕННЫЕ МАТРИЦЫ Интересной открытой проблемой является обработка разреженных матриц на систолических структурах. В [6] отмечено, что, поскольку разбиение разреженной матрицы А дает заполненную матрицу, может оказаться полезным изменение представления в течение разбиения. Таким образом, исходя из того, что А хранится как разреженная матрица (индекс, значение и компоненты), заканчиваем получением -~1 L
где LUu Unl U12 должны храниться как разреженные матрицы, a L22, U22 - как заполненные.исПОПЬЗОвана в систолических структурах, Аналогичная идея может быть испол знеструктурных спосо- бе действительно может быть необходимо избежал.несРУ yV бон обращения к памяти. Например, аддитивные разбиения 0 ... 29 30 31 32 33 34 35 ... 78 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
