В. В. РОСЛОВЦЕВ
Научный руководитель ─ М. И. АРШАВСКИЙ, к. т.н., доцент
Московский инженерно-физический институт (государственный университет)
ПОСТРОЕНИЕ МОДЕЛИ БЛОКА ПАМЯТИ
ДЛЯ ОПИСАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
Предлагается подход к построению модели блока памяти для лабораторного практикума по курсу параллельные алгоритмы.
Реализация и эффективность параллельного алгоритма существенно зависит от архитектуры системы, на которой он должен выполняться. При изучении и апробации параллельных алгоритмов используют упрощённую модель такой системы. В данной работе за основу взяты следующие архитектурные схемы: гиперкубическая структура, векторный процессор и систоллическая структура.
Предполагается, что оперативная память системы обладает возможностью одновременного выполнения операций над массивами данных и состоит из нескольких банков памяти (БП).
Для реализации операций над двумерными массивами необходимо решить задачу такого их размещения в памяти, при котором не возникает конфликтов. Известны следующие способы их размещения [1]
- скошенное хранение
- метод BSP
- метод ассоциативных таблиц
В этих методах необходимо осуществить отображение (i, j)→(l, k), где
i, j – индексы элемента исходной матрицы, l – адрес в БП, k – номер БП. Описание метода задаёт прямые функции l=f1(i, j), k=f2(i, j). Модель такой памяти содержит группу параллельных процессов, каждый из которых управляет соответствующим БП. Это управление заключается в адресации БП и в определении источника и преемника данных. Для описания процессов необходимо найти функции q=g(d, row/col, w/r),
u= g(d, row/col, w/r), где d, – номер строки или столбца, q – адрес в БП,
u – позиция во входном или выходном регистрах, row/col – задаёт режим работы со строкой или столбцом, а w/r – задаёт задает режим записи или чтения.
В первом и третьем методах функции f1(i, j) и f2(i, j) имеют симметричную форму и проблем с построением описания не возникает. Но в методе BSP используются функции l= div N и k=a mod M, где a – линейный адрес элемента (i, j) в исходной матрице, N – размер матрицы, а M – число БП, причём число M≥N и является простым. В левой части таблицы 1 показано размещение в памяти элементов матрицы размера 4×4, а в правой части – размещение матрицы методом BSP.
Таблица 1.
А41 | А42 | А43 | А44 | А44 | Х | А14 | А24 | А34 |
А31 | А32 | А33 | А34 | А33 | А43 | Х | А13 | А23 |
А21 | А22 | А23 | А24 | А22 | А32 | А42 | Х | А12 |
А11 | А12 | А13 | А14 | А11 | А21 | А31 | А41 | Х |
Банк 0 | Банк 1 | Банк 2 | Банк 3 | Банк 0 | Банк 1 | Банк 2 | Банк 3 | Банк 4 |
Предлагается решить проблему построения описания следующим образом. По приведённым таблицам строятся таблицы для описания работы процессов, обслуживающих БП. Рассмотрим в качестве примера режим записи строки и столбца. Адрес в БП совпадает с номером столбца. Содержимым полученной таблицы является код позиции во входном регистре. При записи строк коды позиций во входном регистре и адреса в БП совпадают. Построенные таблицы приведены ниже.
Для полученных таблиц легко найти аналитическое представление реализующих их функций. Например, функцию, записи столбца, можно описать выражением l = (d+k) mod 5.
ЗАПИСЬ СТОЛБЦА | ЗАПИСЬ СТРОКИ | ||||||||
номер банка | номер столбца | номер банка | номер строки | ||||||
1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | ||
0 | 1 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 | – | 1 | – | 1 | 2 | 3 |
2 | 3 | 4 | – | 1 | 2 | 4 | – | 1 | 2 |
3 | 4 | – | 1 | 2 | 3 | 3 | 4 | – | 1 |
4 | – | 1 | 2 | 3 | 4 | 2 | 3 | 4 | – |
Таким образом, удаётся построить модель блока памяти с возможностью выполнения параллельных операций над массивами данных
Список литературы
1. Джесхоуп Дж. Параллельные ЭВМ. Радио и связь. 1988.
