Более общие типы размещения массивов
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

       Никто не запрещает размещать элементы массива в параллельной памяти как угодно случайным образом. Проблема в том, чтобы к этим элементам массива удобно было обращаться. Выбор способа размещения данных должен зависеть от исполняемой программы. Широкое множество способов размещения данных описано в [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 покоординатное размещение и др. Горизонтальные и вертикальные размещения, как частный случай блочных размещений, также войдут в класс блочно-аффинных размещений.

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

Иногда может быть целесообразным один массив данных разместить в одном множестве модулей памяти, а другой массив – в другом множестве. Но в рамках своего множества модулей памяти каждый массив может быть размещен одним из описанных способов.


 


Дата: 2018-12-21, просмотров: 413.