Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 119 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

3.4. Систолические массивы и регулярные графы
Возвращаясь к построению систолических массивов, теперь
можем размещать систолические элементы в клетках подразделе-
ния.
Теорема 3.2. Пусть имеется клеточное подразделение и
каждая клетка представляет собой многоугольник на плоскости.
Предположим, что систолические элементы заполняют некото-
рые из этих клеток и в полученном систолическом массиве реали-
зуется принцип близкодействия. Тогда граф систолического мас-
сива является плоским.
Д о к а з а т е л ь с т в о сводится к построению некоторого под-
графа, сопряженного к подразделению так, что такой граф также
плоский.
Замечание. Стремление к экономному использованию отво-
димого места и к более компактному размещению систолическо-
го массива приводит к покрытию данной области систолическими
элементами без пропусков, а это ведет к разработке таких (обыч-
но многоугольных) форм этих элементов, чтобы отводимая область
могла быть ими полностью покрыта. Это обычно шестиугольные,
прямоугольные или треугольные элементы. Требования их стан-
дартизации приводят к определенной правильности их формы и
периодичности в их расположении. Математическое исследование
возможных форм и плотного расположения фигур привело к раз-
витию теории покрытий и упаковок.
Систолические массивы как вычислительные системы имеют
следующие особенности:
— систолический массив состоит из однотипных функциональ-
ных устройств;
— каждое функциональное устройство связано только с сосед-
ними;
— за каждый такт каждое функциональное устройство прини-
мает данные, выполняет операцию и отсылает результаты;
— систолический массив принимает входные данные и выдает
результаты только через граничные систолические ячейки;
— передача любой информации происходит на фоне выполне-
ния операций.
Для более глубокой характеристики систолических массивов
обратимся к регулярным графам.
Определение 3.6. Решетчатый граф называется регуляр-
120

Страницы