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

UptoLike

ВУЗ: 

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

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

Рубрика: 

построенной системе G
∗
реализуются все программы базовой со-
вокупности P
G
.
Д о к а з а т е л ь с т в о. этого утверждения с учетом теоремы 3.1
состоит в том, чтобы убедиться, что моменты включения функци-
ональных устройств базовой системы разнесены во времени в до-
статочной степени, в данном случае это гарантируется тем, что эти
функциональные устройства находятся на одном пути и операции
на нем выполняются последовательно одна за другой.
Замечание. sl Разбиение множества вершин графа алгоритма
на подмножества вершин, лежащих на одном пути, дает конструк-
тивный способ конструирования математических моделей вычисли-
тельных систем. Таких систем может быть много, но все они лучше
по основным параметрам (кроме размера памяти). Они содержат
меньшее число функциональных устройств, загруженность каждо-
го функционального устройства больше, число линий связей мень-
ше, причем на них реализуются все программы базовой совокупно-
сти P
G
. Здесь опять можно ставить задачу оптимизации, пытаясь
разбить новое множество вершин на подмножества и уменьшить их
число путем слияния.
Теорема 3.4. Пусть вычислительная система строится
так, как указано в теореме 3.1. Предположим, что граф алгорит-
ма направленный и проекции сливаемых вершин на направляющий
вектор различны. Поставим в соответствие k-му срабатыванию
функционального устройства ту из сливаемых вершин графа, ко-
торая имеет k-ю по порядку проекцию на направляющий вектор.
Тогда соответствие гарантирует правильную выполняемость ал-
горитма.
Д о к а з а т е л ь с т в о представляется весьма очевидным.
Теорема 3.5. Пусть граф G алгоритма направленный. Спро-
ектируем (ортогонально) его на гиперплоскость, перпендикуляр-
но направляющему вектору. Если эту проекцию взять в качестве
графа вычислительной системы, то будут выполняться условия
теоремы 3.4.
Д о к а з а т е л ь с т в о. Сливаемые вершины находятся на пря-
мых, параллельных направляющему вектору, поэтому их проекции
на направляющий вектор очевидно различны; тем самым условия
теоремы 3.4 выполнены.
Замечание. При ортогональном проектировании удобно счи-
тать, что дуги исходного графа прямолинейны, ибо в противном
72

Страницы