Методы синтеза функциональных модулей управляющих вычислительных систем

АННОТАЦИЯ

Задача синтеза макроструктуры специализированных вычислительных систем (ВC) заключается в разработке формальной процедуры установления соответствия между автоматами (функциональными модулями), поиска области допустимых структур ВС и выбора из нее оптимальной структуры схемы с постоянными связями, а также, разработки метода композиции функциональных модулей (ФМ). В работе показана раскраска ФМ, а также рассмотрена раскраска модулей с помощью классов толерантности. На построенной области допустимых структур ВС найден вариант, который позволяет решить задачи с минимальными затратами времени и оборудования.  Получив структуры вычислительных систем, развернутую в пространстве, и уточнив состав ФМ с точки зрения минимизации времени можно приступить к композиции ФМ, ведущий к синтезу структуру ВС с многократным использованием модулей.

ABSTRACT

The task of the synthesis of the macrostructure of specialized computing systems is to develop a formal procedure for establishing a correspondence between automata (functional modules), search for the area of permissible structures of computing systems and select from it the optimal structure of the scheme with constant connections, as well as the development of the method of composition of functional modules. The paper shows the coloring of the functional modules, and also considered the coloring of the modules using the classes of tolerance. On the constructed area of permissible structures of the aircraft found an option that allows you to solve the problem with minimal time and equipment.  Having received the structure of computer systems deployed in space, and specifying the composition of the functional modules in terms of minimizing the time you can proceed to the composition of the functional modules, leading to the synthesis of the structure of computer systems with multiple modules.

Ключевые слова: синтез макроструктуры, раскраска функциональных модулей, композиция функциональных модулей, отношения порядка, кортеж, понятие упорядоченности.

Keywords: synthesis of macrostructure, coloring of functional modules, composition of functional modules, order relations, tuple, the concept of orderliness.

Постановка задачи. В работе задача синтеза ФМ управляющих вычислительных систем (УВС) рассматривается как акт установления отношения порядка на множестве элементов ФМ, ведущей к синтезу ВС и заданию упорядоченности, порожденных порядком на блоках алгоритмов и раскрывающих конкретный вид упорядоченности между элементами структуры ВС. Структура отражает устойчивую упорядоченность. Понятие упорядоченности в системно-структурных исследованиях выступает как определенный вид этой композиции, которая в знаковой математической форме описывается с помощью формул, уравнений, таблиц, графиков и других средств. С учетом изложенного в работе [1] понимания ФМ ВС и отношения порядка на них дадим определение понятия структуры ВС, ориентированной на классы применения.

ОПРЕДЕЛЕНИЕ 1. Структура ВС, настроенная на структуру алгоритмов решаемых задач, есть вид композиции (упорядоченности) множества ФМ, который устойчив (инвариантен) относительно заданного класса решаемых задач.

Для установления отношения порядка на множестве элементов ВС, при котором наиболее полно учитывается характер взаимосвязи операторов и блоков, составляющих алгоритмы решаемых задач, предлагается один из возможных подходов к композиции, названный методом проекционного отображения. Он основан на установлении соответствия между компонентами схемы алгоритма и ФМ с последующим отображением блок-схем алгоритмов на набор ФМ, что позволяет построить структурный граф требуемой ВС.

ОПРЕДЕЛЕНИЕ 2. Проекция набора М  модулей на блок-схему G алгоритма есть выбор одного (или более) элемента М_s  некоторого множества М  и перевод его в элемент подмножества  данного множества G.  При этом обычно элементы множества М представляют собой кортеж, полученный в результате декартова произведения множества  ,  элементом подмножества является элемент из множества    или из произведения части этих множеств, но не из всего М.

Считаем, что проекция задана, если установлены правила перевода элементов из М в элементы . Задача синтеза макроструктуры, специализированной ВС заключается в разработке этих правил. Ее решение распадается на несколько взаимосвязанных задач. В статье рассмотрена задача, названная методом проекционного отображения.  Остальные задачи показаны в работе автора [1].

Решение задачи. РАСКРАСКА БЛОКОВ АЛГОРИТМА. Пусть задана модель алгоритма, состоящего из n  блоков , на схемах  каждого из которых определена базисная система маршрутов  ,   пусть также на множестве блоков  определены классы толерантности  по правилам, изложенным в [2],  упорядочены все  блоки ,  по классам толерантности. В результате упорядочения получим ряд из S подсистем блоков, образующих некоторые К – классы толерантности,  . Эти  подсистемы блоков зададим с помощью матрицы инциденций

  – двоичная переменная, определяемая следующим образом

Из свойства матрицы инцидентности и определения класса толерантности следует, что вектор-строка     перечисляет упорядоченные блоки , находящихся, в отношении вложения каждого предыдущего со всеми последующими, и задает подсистему  блоков, образующих   К-класс толерантности, который запишем в виде

Для каждого К – класса толерантности определим (построим) его представитель – вектор – такой, что все остальные вектора данного К – класса находится с ним в отношении е вложения. Обозначим этот вектор через .  Из определения отношения вложения следует, что он содержит максимальное (для данного К- класса) число     компонент-единиц ((маршрутов   на схеме алгоритма)  и согласно принятому правилу построения  (упорядочения)  им выступает вектор . Обозначим  через т.е.  = .

Тогда векторы – представители К-классов можно записать в виде

Рассмотрим все блоки   определим, в состав каких построенных подсистем   КТ_к, к = 1,…,s   (классов толерантности) они входят, тем самым найдем расцветку каждого блока  , т.е. все его к- цвета. Эта информация содержится в  j- м вектор- столбце матрицы (1), перечисляющем  все инцидентные с блоком    подсистемы .  Об этом свидетельствуют единичные компоненты  у_kj , вектора  

Выписав только номера мест единичных компонент вектора ,  представим его в компактной форме 

Здесь   количество классов толерантности (признаков цветов), в состав которых  входит блок  ,  - номер цвета – класса толерантности. В который окрашен блок   алгоритма.

ГРУППИРОВАНИЕ БЛОКОВ АЛГОРИТМА. РАСКРАСКА ГРУПП. Поскольку классы толерантности пересекаются, что вытекает из формального свойства отношения толерантности [2], то один и тот же блок алгоритма может войти в состав разных классов. По этой причине не существует однозначного – единственного распределения блоков по таксонам. Однако при синтезе макроструктуры ВС каждый блок должен быть включен в состав только одного таксона. Поэтому – возникает задача такого распределения блоков, при котором каждый из них входил бы в состав только одного из классов, если блоки из этих классов толерантности входят в разные таксоны, а, значит, и только одного таксона. Рассматривая таксон как инцидентную систему, состоящую из К- классов толерантности, k = 1,…,s,  каждый из которых сам в свою очередь выступает инцидентной подсистемой, содержащей блоки  в качестве своих элементов, зададим его матрицей,

где    – двоичная переменная, определяемая следующим образом

Вектор-строка этой матрицы задает все К – классы толерантности, входящие в l- таксон поэтому ее можно считать и вектором раскраски    –таксона.

У некоторых блоков и таксонов все цвета могут оказаться разными. Такие блоки и таксоны не сравнимы по расцветке. На сравнимых же по расцветке блоках и таксонах возможные ситуации описываются условием

S_l> <S_j,                                                                                    (2)

(S_l, S_j –  число цветов у l = таксона j - блока соответственно).

Если число цветов в разных таксонах одинаково по отношению к одноименному блоку, то выбирается таксон с меньшим номером.

РАСКРАСКА ФУНКЦИОНАЛЬНЫХ МОДУЛЕЙ.  Пусть задан набор ФМ {M_s,  s = 1,…,r}  с базисными системами – маршрутов     N_s,  s = 1,…,r. Вне зависимости от метода оптимизации набора М⁰ модулей M_s, M_s Î М⁰ суть их раскраски одна и тяже и заключается  в  определении векторов представителей классов толерантности  или векторов – представителей классов толерантности. Поэтому в работе рассмотрена раскраска модулей с помощью классов толерантности.

Построим пространственную структурную схему G_* ВС следующим образом. Каждому l- таксону ставим в соответствие подсистему модулей, с которыми вектор-таксон    следовательно, и всякий блок из l- таксона находится в отношении вложения. Соответствие  установлением сравниваем раскрасок  X_l  каждого отдельного таксона  Т_l(ξ)  из  ξ- яруса с раскрасками  ФМ М_s  и последующего выбора для каждого таксона тех модулей, в расцветке которых встречаются все  цвета l – таксона, т.е. номера тех классов толерантности, образующие l – таксон. 

Выполнив описанную процедуру сюръективного отображения для всех ξ- ярусов (ξ= 1,…, р), определим исходный, структурный граф  G_*(M^*,U^*₁), т.е. найдем  подмножества M^*(ξ),  ξ = 1,…, р ,  модулей  М_lυ(ξ), образующие множество М^*, и установим порядок  на нем  , т.е. связи между модулями, изоморфные связям  U₁ на множестве G блоков  G_j(ξ) алгоритма. Полученный исходный, структурный граф G_*(M^*,U^*₁) c описанными свойствами  задает область допустимых структур ВС, развернутых в пространство. Граница этой области определяются следующим образом.

На заданной схеме алгоритма G с блоками G₁,…,G_n множество классов толерантности строится единственным образом.  По этой причине раскраска модулей, блоков и таксонов на ярусах при выбранном радиусе сферы таксономизации также единственная. Сами цвета на ярусах и таксонах распределяются случайным образом.  Тогда, чтобы определить множество всех вариантов структурного построения ВС, необходимо вычислить число способов, которыми могут быть реализованы блоки алгоритмов. т. е. входящие в состав одного таксона Т₁(ξ) цветов  распределены между подмножеством  М_l (ξ) модулей,  если отображение  φ_l    l- таксонов на множестве М_l (ξ) взаимно- однозначно   φ_l :  Т₁(ξ)® М_l (ξ).

В таком случае задача формализуется как задача на перестановки с повторениями. Опустив все промежуточные выкладки, приведем окончательно выражение для вычисления перестановок

Р(,) = 

а, значит, и числа способов реализации блоков, входящих в таксон T_l(ξ) подмножеством модулей   М_l(ξ).  Для ξ- яруса число возможных вариантов равно   а для всего графа  G алгоритма

Выводы. На построенной области допустимых структур ВС необходимо найти вариант, который позволяет решать задачи и минимальными затратами времени и оборудования. Будем считать время решения задач главным фактором, влияющим на выбор структуры ВС, а затраты оборудования подчиненным фактором, и они не должны лишь превосходить некоторых заданных (разумных) пределов.  Это значит, что оптимизация затрат на оборудование (и вопрос его многократного использования) может решаться лишь в тех случаях, когда имеется запас по времени решения проблемных задач.  Поэтому на первом этапе оптимизации целевая функция сводится к критерию затрат времени. На втором этапе оптимизируется оборудование ВС. При таком подходе значительно упрощается поиск оптимальной структуры ВС.

Список литературы:
1. Мусаев М.У., Ручка Е.И. Формальный аппарат устанавления сходства и различия алгоритмов и автоматов/ Ташк.политех.ин-т.-1988.-16 с. ---Деп. В УзНИИНТИ.27.12.88.№912.
2. Бекмуратов Т.Ф.,.Мусаев М.У Методы построения классов толерантности на множестве алгоритмов. Доклады АН РУз № 7. 1997г. с. 24-27.