|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Горизонтальные, вертикальные и блочные размещения массивов данных.
Будем предполагать, что рассматриваемая многопроцессорная вычислительная система (МВС) содержит p процессорных элементов (ПЭ), каждый из которых представляет собой процессор со своей локальной памятью. Доступ к локальной памяти другого процессора возможен через коммуникационное устройство, соединяющее все ПЭ. Получение машинного слова из локальной памяти другого ПЭ и будем называть межпроцессорной пересылкой. В данной работе рассматриваются такие коммуникационные устройства, как полнодоступный коммутатор, кольцевая сеть, m-мерная решетка, гиперкуб [ 138 ]. Размещением m-мерного массива X[1..N1; 1..N2;...; 1..Nm] будем называть функцию, которая каждому набору индексов I=(I1, I2,..., Im), (1≤ I1≤ N1,..., 1≤ Im≤ Nm) ставит в соответствие номер модуля памяти, в котором должен находиться элемент массива X(I1,..., Im). Размещение данных в отличие от распределения данных не указывает, в какую именно ячейку модуля памяти попадает данный элемент массива. Размещение массива A[1..N1; 1..N2;...; 1..Nm] будем называть вертикальным тогда и только тогда, когда для любого I=(I1, I2,..Im), (1≤ I1≤ N1,..., 1≤ Im≤ Nm) элемент массива A[I1, I2,..Im] находится в модуле памяти с номером ]I1/]N/p[[.
Пример 6. Возьмем массив X из предыдущего определения со следующими значениями параметров: p=4, m=2, N1=10, N2=2. Тогда вертикальное размещение элементов этого массива имеет вид:
Размещение массива A[1..N1; 1..N2;...; 1..Nm] будем называть горизонтальным, если для любого I=(I1, I2,..Im), (1≤ I1≤ N1,..., 1≤ Im≤ Nm) элемент A[I1, I2,..Im] находится в модуле памяти с номером I1 mod p.
Пример 7. Возьмем массив X из предыдущего примера. Тогда горизонтальное размещение элементов этого массива имеет вид:
Размещение массива A[1..N1; 1..N2;...; 1..Nm] будем называть блочным с блоком d, если для любого I=(I1, I2, …, Im), (1≤ I1≤ N1,..., 1≤ Im≤ Nm) элемент массива A[I1, I2, …, Im] находится в модуле памяти с номером ]I1/d[ mod p. Блочное размещение является обобщением и горизонтального и вертикального размещений. Полагая d=1, получим горизонтальное размещение. Полагая d=]N/p[, получаем вертикальное размещение.
Пример 8. Рассмотрим фрагмент программы DO 99 I = 1, N DO 99 J = 1, N (11) 99 Y(I) = AI*X(2*I-1, J) + BI*X(2*I, J) + HI
Возьмем массив X из предыдущего примера со значениями параметров: p=4, m=2, N1=10, N2=2 и добавим параметр d =2. Тогда блочное размещение элементов этого массива будет иметь следующий вид:
Следует отметить, что для рассматриваемого гнезда циклов такое размещение массива может оказаться эффективнее, чем горизонтальное или вертикальное. Блочное размещение данных можно свести к горизонтальному. Пусть задан m-мерный массив X[1..N1; 1..N2;...; 1..Nm] и пусть этот массив размещен блочно с размером блока d. Пусть N11 = N1/d. Рассмотрим новый массив XX[1..N11; 1..N2;...; 1..Nm], элементы которого представляют собой векторы из элементов массива X.
XX(I1,..., Im) = (X((I1-1)*d+1,..., Im), X((I1-1)*d+2,..., Im), …, X(I1*d,..., Im))
Тогда блочное размещение массива X сводится к горизонтальному размещению массива XX. Таким образом, достаточно получить алгоритмы оптимального размещения горизонтальных массивов. Горизонтальные и вертикальные размещения рассматривались в работах автора и в [140, стр. 38] (по-другому названные).
Более общие типы размещения массивов.
Никто не запрещает размещать элементы массива в параллельной памяти как угодно случайным образом. Проблема в том, чтобы к этим элементам массива удобно было обращаться. Выбор способа размещения данных должен зависеть от исполняемой программы. Широкое множество способов размещения данных описано в [75], но без связи с исполняемым кодом. Для размещения данных в параллельной памяти существует принципиальное различие между распределенной памятью и общей распределенной (разделяемой) памятью. В случае распределенной памяти аргументы одной бинарной операции должны быть в одном модуле памяти, а в случае общей распределенной памяти, аргументы одной операции могут (должны) быть в разных модулях памяти. Но типы размещения массивов одинаковы. Будем предполагать, что имеется p модулей памяти. Пусть X – некоторый m-мерный массив.
Будем рассматривать аффинные по модулю p размещения данных, т.е. такие размещения, при которых элемент массива X(i1, i2,..., im) находится в модуле памяти с номером u = (s1*i1+s2*i2+...+sm*im+s0) mod p, где s0, s1, s2,...sm - константы, зависящие только от массива X. Число s0 будем называть сдвигом массива X. Это число показывает номер модуля памяти, в котором размещается нулевой элемент X(0, 0, …, 0).
Следующие способы размещения данных являются частными случаями аффинного по модулю p размещения.
{-1, 0, +1}-размещения. Это аффинные по модулю p размещения, в которых константы s1, s2,...sm принадлежат множеству {-1, 0, +1}. К таким размещениям, в частности, относятся размещение матрицы по строкам или по столбцам или по диагоналям или скошенная форма хранения матрицы.
{0, +1}-размещения. Это аффинные по модулю p размещения, в которых константы s1, s2,...sm принадлежат множеству {0, +1}. К такому типу размещений относятся размещения матриц по строкам, по столбцам и в скошенном виде. Размещение по диагоналям к такому типу не относится.
Покоординатные размещения со сдвигами. Это такие {0, +1}-размещения, в которых лишь одна константа s1, s2,...sm может быть равна 1.
Покоординатные размещения. Это такие {0, +1}-размещения, в которых лишь одна константа s1, s2,...sm может быть равна 1 и сдвиг равен нулю s0=0. Размещения матрицы по строкам или по столбцам являются покоординатными.
Блочно-аффинные по модулю p размещения данных. Пусть натуральные числа p, d1, d2, …, dm и целые константы s0, s1, s2,..., sm зависят только от m-мерного массива X. Блочно-аффинное по модулю p размещение m-мерного массива X – это такое размещение, при котором элемент X(i1, i2,..., im) находится в модуле памяти с номером
u = (]i1/d1[ * s1 + ]i2/d2[ * s2 +... + ]im/dm[ * sm + s0) mod p.
Число s0 будем называть сдвигом массива X. Это число показывает номер модуля памяти, в котором размещается нулевой элемент X(0, 0, …, 0). При описанном блочно-аффинном способе размещения m-мерный массив представляется как массив блоков размерности d1 * d2 *…* dm, который размещается так, что у каждого блока все элементы оказываются в одном модуле памяти. В работе [140, стр. 38] приводятся горизонтальные размещения одномерных массивов не во всех процессорах подряд, а с некоторым периодом – но это, очевидно, частный случай аффинного размещения (например, при размещении массива только в четных процессорных элементах s1=2). Естественным образом можно определить подтипы блочно-аффинного размещения: блочное по модулю p {-1, 0, +1}-размещение, блочное по модулю p покоординатное размещение и др. Горизонтальные и вертикальные размещения, как частный случай блочных размещений, также войдут в класс блочно-аффинных размещений. При поиске оптимального размещения данных рассматриваются размещения из определенного класса. Чем шире рассматриваемый класс размещений, тем, с одной стороны, больше шансов подобрать оптимальное размещение, но, с другой стороны, на поиск оптимального размещения потребуется больше времени. Иногда может быть целесообразным один массив данных разместить в одном множестве модулей памяти, а другой массив – в другом множестве. Но в рамках своего множества модулей памяти каждый массив может быть размещен одним из описанных способов.
Элементарные параллельные переразмещения массивов.
Рассылка.
Во многих параллельных алгоритмах возникает потребность одно данное разослать сразу во много вычислительных устройств. Такая операция рассылки обычно в языках программирования называется broadcast. Иногда рассылка поддерживается аппаратно (если, например, вычислительные устройства соединены коммуникационной сетью «звезда»).
Кольцевой сдвиг.
Кольцевая сеть позволяет одновременно выполнять пересылки, соответствующие только циклическим сдвигам, т. е. таким подстановкам s, что для любых i, jÎ {1,.., p} (si-i) mod p = (sj - j) mod p. Например,
S =
Время на пересылку данных в соответствии с такой подстановкой s на полнодоступном коммутаторе есть величина T0, не зависящая от p и от того, какое данное в каком ПЭ расположено (лишь бы не требовалось в один момент времени считывать (или записывать) несколько данных из памяти одного ПЭ). С другой стороны, время для пересылки данных на кольцевой сети равно T1+T2*|si - i|, где i – номер ПЭ, из которого данное считывается, si – номер ПЭ, в который данное записывается, T1, T2 - константы, не зависящие от p и размещения данных. Здесь, конечно, предполагается, что для всех i=1,..., p пересылки могут быть выполнены одновременно, если (si -i) mod p не зависит от i. Константа T1 означает время загрузки данных из процессорного элемента, пересылающего данные, в коммуникационную сеть, плюс время считывания из коммуникационной сети в процессорный элемент, получающий данные. Константа T2 означает время движения данных по коммуникационной сети между двумя соседними процессорными элементами (исключая время загрузки-выгрузки данных).
Транспонирование.
Есть разные стандарты представления двумерной матрицы в одномерной памяти компьютера. Трансляторы языка ФОРТРАН размещают матрицы «по столбцам», а трансляторы языка Си – «по строкам». От способа размещения матрицы может зависеть время работы программы. Если при обращении к матрице считываются ее столбцы, то удобнее, чтобы элементы этих столбцов находились в памяти рядом – в этом случае и происходит лучшее попадание в кэш-линейку и быстрее вычисление адреса следующего элемента массива (прибавление единицы). Если в программе обращение к матрице по строкам – то и размещать матрицу лучше, соответственно, по строкам. Но может так случиться, что в одном месте программы есть обращение к матрице по строкам, а в другом месте – по столбцам, причем и тех и других обращений много. Тогда бывает эффективным переразмещение матрицы – транспонирование. Транспонирование матрицы представляет собой такое переразмещение массива в памяти компьютера, при котором строки размещаются, как столбцы, а столбцы – как строки. Если компилятор все массивы размещает одинаково либо по строкам, либо по столбцам, то транспонирование может быть описано простой программой
DO 1 I1 = 0, N-1 DO 1 I2 = 0, N-1 1 Y(I1, I2) = X(I2, I1)
В данном случае в памяти компьютера кроме исходной матрицы X будет существовать и транспонированная к ней матрица Y. Несложно записать программу, в которой транспонированная матрица займет место исходной
DO 1 I1 = 0, N-1 DO 1 I2 = 0, I1 T = X(I2, I1) X(I2, I1) = X(I1, I2) 1 X(I1, I2) = T
Транспонирование матриц использовалось в традиционных последовательных компьютерах для более быстрого обращения к памяти. Общий параллельный алгоритм переразмещения массивов и, в частности, транспонирования будет описан далее.
Скашивание.
Матрица-клетка – это матрица, размерность которой равна количеству модулей памяти. Во многих эффективных параллельных алгоритмах (для архитектуры SIMD [81]) произвольные матрицы могут быть представлены как блочные матрицы, блоки которых – матрицы-клетки. Скошенная форма хранения матрицы-клетки – это такое размещение матрицы, при котором в каждом модуле памяти хранится некоторая косая диагональ матрицы.
a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44
Рис. 51. Косые диагонали матрицы.
P1 P2 P3 P4 a14 a11 a12 a13 a23 a24 a21 a22 a32 a33 a34 a31 a41 a42 a43 a44
Рис. 52. Скошенное размещение матрицы в параллельной памяти. Над столбцами обозначены номера процессоров, в которых эти столбцы размещены.
Скошенная форма хранения позволяет обращаться одновременно как к элементам любой строки матрицы-клетки, так и к элементам любого столбца. Алгоритм приведения матрицы к скошенной форме может выглядеть следующим образом.
DO 1 I1 = 0, p DO 1 I2 = 0, p 1 Y(I1, I2) = X( (I2 + I1) mod p, I1)
Задачи. Задача 1. Как разместить матрицу N*N в распределенной памяти так, чтобы ее транспонирование занимало малое время, если в качестве коммуникационной сети используется кольцо:
Задача 2. В параллельной вычислительной системе в качестве коммуникационной сети используется двумерная квадратная решетка (тор). Узлы пронумерованы от 0 до (p-1) сверху-вниз, слева-направо. Как разместить матрицу N*N в распределенной памяти так, чтобы ее транспонирование занимало малое время:
Задача 3. В параллельной вычислительной системе в качестве коммуникационной сети используется n-мерный куб. Узлы имеют стандартную для гиперкуба двоичную кодировку, которая может быть переведена в десятичную с нумерацией от 0 до (p-1), p=2n. Как разместить матрицу N*N в распределенной памяти так, чтобы ее транспонирование занимало малое время:
|
Последнее изменение этой страницы: 2019-05-17; Просмотров: 684; Нарушение авторского права страницы
