МКО представляет собой совокупность подходов позволяющих спроектировать параллельное вычислительные структуры: SIMD, MIMD процессоры. Как и любая методология, методология КО носит алгоритмический, а не алгебраический характер, т.е. для одной и той же задачи может быть получено несколько решений.
Успешность того или иного решения определяется опытом или искусством проектировщика. Методология имеет рекомендательный характер, т.е. алгебраической процедуры, которая бы позволила однозначно вычислить структуру системы для поставленной задачи, не существует. Отличительными чертами методологии КО является: - применимость лишь в случаях однородных графовых зависимостей, т.е. инвариантных по отношению к операции сдвига;- использование только линейных проекций и планов; - регулярность структуры результирующего матричного процессора.
Методология КО включает в себя три основных этапа:
1)разработка однородного графа зависимостей, инвариантного относительно операции сдвигаются.
2)разработка графа потока сигналов путем проецирования графа зависимостей на матричную структуру.
3)разработка самого матричного процессора для физической реализации графа, потока, сигнала.
Можно выделить также нулевой предварительный этап, на котором для построения задачи потребуется промежуточная форма в виде программ с однократным присваиванием, а затем на основе этой программы строится первый граф зависимости, возможно еще не локализованный.
Разработка графа зависимостей является задачей, для которой, как правило, нет однозначных решений, т.е. может быть построено несколько вариантов графа зависимостей.
В свою очередь на основе одного и того же графа зависимостей путем применения различных планов и направлений проецирования можно получить множество графов потоков сигналов.
Наряду с методологией канонического отображения существует методология обобщенного отображения. Данная методология более сложна и представляет собой набор методологии меньшего уровня. Методология обобщенного отображения применяется в случаях неоднородности исходного графа зависимостей при нелинейном планировании и при мульти проекциях.
Графы зависимостей и графы потоков сигналов. Процедура отображения графа зависимостей в граф потока сигналов. Критерий допустимости линейного плана.
Граф зависимостей представляет собой графическую форму описания процесса вычисления, выполняемых в программе с однократными присваиваниями, узлы графа соответствуют вычислительным операциям, а дуги отображают зависимости между данными (исходными к результатам промежуточных вычислений).
Алгоритм является вычисленным лишь тогда, когда его граф зависимостей не содержит ни петель, ни циклов.
Сущность операций, производимых в узлах графа, может не учитываться. Если сущность операций учитывается, то такой граф зависимостей называется полным.
Первая содержит дуги, которые обеспечивают распространение значений элементов вектора bj во все точки индексного пространства, содержащих одинаковое значение j. Дуги такого типа соответствуют данным названным распределенными.
Вторая не содержит распространенных данных. Речь идет не о распространение данных, а об их последовательной передачи от узла к узлу без изменений. Их называют передаваемыми.
С точки зрения простоты проектирования сети, связывающей элементы желательно чтобы все связи между элементами были локальные. Наличие только локальных связей означает необходимость замены всех распространенных данных.
Графы потоков сигналов:
ГПС – это промежуточная форма, которая находится для представления алгоритма, представленного своим графом зависимости. Проектирование матричного процессора можно произвести и без использования промежуточной формы представления в виде ГПС, однако, такой подход является нерациональным, поскольку результирующая матричная структура будет включать в себя процессорные элементы, которые будут участвовать в вычислениях один или два раза, а большую часть времени простаивать. ГЗ включает в себя две части: функциональную и структурную.
Функциональная часть описывает поведение в отдельных узлах, а структурная взаимосвязи между ними. Со структурной точки зрения ГПС может быть описан как :
A=<v,e,d(e)>, где v – множество вершин,e – множество ребер, d(e) – это функция, которая каждому ребру из множества Е ставит в соответствие его вес, модулирующий временную задержку.
ГПС может иметь петли, но не циклы. ГПС может быть получен на основе ГЗ путем отображения, состоящего из двух этапов:1)составляет назначение на процессоры, при этом множеству вершин и ребер множество ГЗ представляется во множество вершин и ребер ГПС. При этом в соответствии с основным принципом методологии канонического отображения допустимы только линейные проекции. 2)соответствует планированию вычислений на данном этапе определяется порядок вычислений на основании линейного плана. В методологии канонического отображения допускаются только линейные планы.
Допустимые линейные планы:
Целью этапа проецирования является отображение ГЗ, как правило, расширенной структуры на решетку меньшей размерности. Математически проекция ГЗ описывается вектором проекции а. В самом простом варианте направление выбирается вдоль одной из параллельных осей:
Планирование представляет собой отображение линейного пространства ГЗ на одномерном множестве планов или расписаний.
Линейный план строится на основе множества параллельных и равномерно распределенных гипер плоскостей. Узлы ГЗ, лежащие на одной гипер плоскости, соответствуют вычислениям, которые могут быть выражены одномерно.
Математически линейный план описывается векторным столбцом плана S, который является нормалью по отношению к гипер плоскостям.
Для выбора проекции не все планы являются допустимыми, т.к. некоторые из них противоречат порядку вычислений задаваемому графу зависимостей, поэтому можно говорить о классе допустимых планов, направление гипер плоскостей которых не нарушают порядка вычислений.
Допустимость плана и вектора плана S при соблюдении двух условий является необходимым и достаточным: 1)STe≥0,Ve€E, т.е. не нарушается порядок вычислений заданный графом зависимостей и тем более не изменяется на противоположный. 2)STα>0, что направление нормали к гипер плоскостям не должно быть ортогональным вектору проекции, т.к. в этом случае множество вершин принадлежащей одной гипер плоскости будет назначен один процессорный элемент, т.е. на один процессорный элемент будут назначены вычисления, которые могут быть выполнены параллельно.
Наиболее распространенными типами линейных планов являются план по умножению рекурсивных и систалических планов.
В случае плана по умолчанию направление вектора в проекции d является параллельным направлению вектора нормали S.
Этот план при котором вектор S параллелен одной из индексных осей исходного графа зависимостей, как правило это ось времени, соответствующий рекурсивному вычислению.
Систалический план – применяется для разработки систалических массивов при этом каждому ребру результирующего графа потока сигналов должна быть поставлена в соответствие не нулевая задержка.
Выделяют еще один тип планов – оптимизированный план. С учетом соблюдения требований и ограничений по использованию ресурсов. Такой план может быть получен с использованием средств САПР.
