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

АННОТАЦИЯ

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

ABSTRACT

The task of synthesis of the macrostructure of specialized VS is to develop a formal procedure for establishing correspondence between automata ( functional modules), search for the optimal structure of the scheme with constant connections and develop a method of composition of functional modules. On the constructed area of admissible structures of VS the variant which allows to solve problems with the minimum expenses of time and the equipment is found. Having received the structure of the aircraft deployed in space, the composition of functional modules from the point of view of minimizing time, you can proceed to the composition of functional modules, leading to the synthesis of aircraft with multiple use of modules.

Ключевые слова: задача синтеза макроструктуры, функциональные модулы, метода композиции, структура ВС, биективное отображение, сюръективное отображение, раскраска, класса толерантности.

Keywords: problem of synthesis of macrostructure, functional modules, composition method, structure of VS, objective mapping, subjective mapping, coloring, tolerance class.

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

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

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

Получив структуру ВС, развернутую в пространстве, и уточнив состав ФМ с точки зрения минимизации времени и реализации алгоритма t(G), можно приступить к композиции ФМ, ведущий к синтезу структуры ВС с многократным использованием модулей.  Для этого построим правило композиции, в основе которого лежит метод проекционного отображения множества М элементов М_σ, М_σ,∈ М  на подмножестводанного множества М с установлением на нем (на подмножестве) соответствующих связей  

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

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

Пусть известны следующие исходные характеристики графов G и . Ширина  ξ- яруса (ξ = 1,….,р) равна  n(ξ) , т.е. на каждом ярусе может быть n(ξ) , блоков  (ξ)  ξ = 1,….,n(ξ)  r(ξ) модулей М_υ (ξ), υ = 1,…, r(ξ). Блоки распределены по таксонам Т_l(ξ), которых на ξ- ярусе - q(ξ). В каждом l- таксоне содержится n₁(ξ), блоков где , j= 1,…,n(ξ). Таксоны Т_l(ξ) l =1,…,q(ξ) на ξ- ярусе в общем случае могут быть образованы блоками, принадлежащими σ_l( ξ) классам толерантности и окрашенными поэтому в S_l(ξ) цветов, причем S_l( ξ)≤S( ξ) ≤S.

Совокупность модулей первого яруса графа G_*, которую обозначим через М^*(I), М^*(I)⊆M^*, выбираем в качестве первоначального набор ФМ, образующих структуру ВС с многократным использованием модулей. Затем расширяем его до набора M^*_∑(ξ) такого, чтобы существовали, во-первых, биективное отображение между блоками любого максимального - таксона и ξ – яруса , ξ`=2,…,ξ и модулями из одноименных подсистем M^*_l(ξ)⊆M^*_∑(ξ) и, во-вторых, инъективное отображение остальных - таксонов из ξ – яруса на те же одноименные подсистемы модулей. Следовательно, расширение- процесс установления соответствия между модулями М_j(ξ ) графа G_*, расположенными на одном ξ – ярусе, ξ=1,…,р, и модулями из набора M^*_∑(ξ). Это соответствие устанавливается таким образом, чтобы для всякого М_j(ξ ), j ← l_γβ, а, следовательно, и для блока G_j(ξ) из графа G алгоритма , существовал соотнесенный, только ему модель M^*_lυ(ξ)⊆M^*_l(ξ)⊆M^*_∑(ξ) расцветка {σ_x} которого включает расцветку {k_β} блока  из - таксона : {σ_x} ⊃ {k_β}, т.е. для каждого маршрута на схеме блока  найдется такой же маршрут на модуле М _lυ(ξ ).

Чтобы упростить процедуру расширения первоначального набора ФМ М^*(1) для каждого ξ`- яруса ξ` =2,…,р и определения из схемы структурного графа G_* структуры ВС с многократным использованием модулей, воспользуемся матрицей Т(ξ) распределения таксонов из ξ–ярусов, содержащей всю информацию о раскраске ярусов графа алгоритма. В этом случае процедура расширения подсистемы M^*_l(ξ) к- цветных модулей М _lυ(1),

υ = 1,…,r_l(ξ) из набора M^*_l(ξ) до биективного соответствия с k-цветными блоками G_j(ξ) алгоритма сводится поиску максимальных наборов модулей, поставленных в соответствие одноименным таксонам. А для этого необходимо для всех однотипных таксонов Т_l(ξ), расположенных на разных ярусах алгоритма, найти такой, который содержит наибольшее число блоков. Следовательно, зафиксированный номер  из L таксона

( –conσt) и изменив номера ярусов ξ = var, переберем все однотипные группы. Сравним число блоков в них и выберем большие по числу блоков из таксонов, а, значит. Максимальные наборы модулей

                                                  (1)

(, - результирующее число ФМ  – типа, раскрашенных в_γ– цвет).

При решении уравнений (4.9) находим такие, чтобы обязательно были справедливы условия , ≥ n_l( ξ) , {σ_x} ⊃ {k_β}, т.е. в результате расширения набора М^*(1) число , всех _γ– цветных модулей M_lυ(ξ) ⊆M^*_l(ξ) ⊆M^*_∑(ξ) будет больше или равно числу n_l(ξ) _γ– цветных блоков G_j(ξ) на любом из ξ- ярусов ξ = 1,…,р.

С учетом максимальных наборов модулей  – типов дальнейшее построение структуры ВС по структурному мультиграфу G_* графу G алгоритма заключается во-первых, в последовательном установлении соответствия, выполняемого за Р- циклов ( по числу ярусов), между элементами- блоками G_lγ(ξ) каждого ξ- яруса блочного графа G({G_ξj}, U₁) и модулями М_lυ из с одновременной пометкой слева направо пар (G_lγ(ξ), М_lυ) , уже участвовавших в сопоставлении в ξ- цикле, где υ – номер последнего (слева) из помеченных _γ– цветных модулей - типа; во-вторых, в установлении связей между модулями М_lυ∈M^*_∑.

Изложенное построение максимальных наборов модулей M^*_∑ выполняется таким образом, чтобы существовало сюръективное отображение φ: G→T множество G = {G_j(ξ)} блоков G_j(ξ) на некоторое множество таксонов Т_l(×), где Т_l(×) будет

Т_l(×) =  

и биективное отображение между подмножествами

где Т_l(ξ) ⊆T_l(×) и .

Чтобы завершить построение правило композиции, рассмотрим на множестве G отношение «иметь один и тот же образ» и обозначим это отношение через t. Оно выполняется G_lγtG_{lγ`</sub>, если φ (G<sub>lγ</sub> ) = φ (G<sub>lγ`} ). Обозначим через Т_l(×) множество всех блоков G_lγ∈G , имеющих один и тот же образ W∈T [34], т.е. таких что G_lγ= . Ясно, что так как, любой блок из G имеет образ. Кроме того, при равных  и ` T<sub>l</sub>(×) T<sub>l`</sub>= ǿ, так как иначе блок, попавший в область пересечения T_l(×) T_{l`</sub>, имел бы два разных образа W<sub>l</sub> и W<sub>l`} . Поскольку φ - сюрьективно,

T_l(×) = ǿ для любого W_lÎT. Итак, множества T_l(×) , образуют разбиение множества G = {G_j(ξ)}, а отношение t есть эквивалентность, соответствующая этому разбиению. Последнее следует из того, что G_lγtG_{lγ`</sub> тогда и только тогда, когда G<sub>lγ</sub> и G<sub>lγ`}, принадлежат общему множеству T_l(×).

Если L – непустое подмножество индексов всех классов – таксонов множества индексов I всех блоков в G, то в силу биективного отображения между множествами T_l(×) и , являющегося следствием принятого максимальных наборов модулей , можем утверждать, что определена проекция

p_L: 

сопоставляющая каждому блоку  из G_l его классов однотипных модулей и устанавливающая связи между модулями , если помимо правил перевода элементов ÎG в их классы эквивалентности ( разработаны автором [94]) установлены правила связи элементов М_lυиз М_l(×)ÌM^*_∑. Друг с другом, индуцированные связями на множестве G. Эти связи вытекают из отношения функциональной зависимости и задаются с помощью соответствующей матрицы смежности Мσ_G отношения функциональной зависимости или информационных связей блоков алгоритма.

Сформулируем правила установления связи между модулями, а, значит, и правила построения матрицы смежности Мσ_M модулей воспользовавшись матрицей смежности М σ_G отношения функциональной зависимости.

1⁰. Если в вектор строке  компоненты {( ξ, l, β; ξ+χ, β-υ), (ξ, l , β;ξ+ χ, β-υ+1) ,…..,(ξ, l , β; ξ+χ, l, β+υ)} равны единицы , то это значит, что блок  соединен с блоками  дугами (l_γβ, l_γβ+υ),….,(l_γβ, l_γβ) ,….,(l_γβ, l_γβ-υ) такими, что для всех 1≤ ξ ≤ р ; и χ≥ 1, 1≤β≤ П_l (ξ) и υ ≥ 1 выполняется условия:

 ξ +χ≤ р ; 1 ≤β+υ ≤n_l( ξ). Поэтому модуль М_lβсоединяется с модулями {M_lβ+υ}. А это значит, что в вектор- строке с номером

( l,β) из матрицы Мσ_Mсмежности компонентам с номерами (l, β-υ), (l, β- υ +1),…,(l, β+υ) присваиваются значения, равные единице;

2⁰. Если в вектор –строке компоненты {(ξ, l, β, ξ+χ, l-d, β), (ξ, l , β, ξ+ χ, l+d+1, β) ,…..,(ξ, l , β, ξ+χ, l+d, β)} равны единицы , то это значит, что на некотором ξ- ярусе , ξ= 1,…,р существует β- блок G_lγβ(ξ) , соединенный β- блоками G_(l±d)γβ(ξ+χ) из (ξ+χ) – ярусов дугами (l_γβ, (1+d)γβ), ….,(l_γβ, l_γβ) ,( (l_γβ,(l-d)γβ) такими , что для всех 1≤ ξ ≤ р ; и χ> 1, 1≤l≤q и d≥ 1 выполняется условия: ξ +χ≤ 1 , a 0 ≤l+d≤p. Поэтому модуль М_lβ соединяется с модулями {M_lβ+υ}. А это значит, что в вектор- строке с номером (,β) из матрицы Мσ_Mсмежности компонентам с номерами (-d, β), (-d+, β),…,(l+d,β) присваиваются значения, равные единице.

3⁰. Модуль М_lβ соединяется с модулями {M_{l±d, β±υ}} если одновременно выполняются условия из 1⁰ и 2⁰.

Итак, по рассмотренным правилам. Однозначно строится матрица смежности Мσ_M элементов М_lβиз множества M^*_∑., М_lβ∈M^*_∑. Представляющая собой клеточную матрицу соединений друг с другом.

На последнем цикле установления соответствия окончательно находится множество Мσ_M⊆M^*_∑.х M^*_∑., задающее закон композиции, согласно которому устанавливаются связи между модулями М_lβрасширенного набора M^*_∑., т.е. перечисляются все пары (М_lβ, M_dυ) элементов множества M^*_∑ модулей, включая и однотипные. Эти пары и образуют сеть связи между ФМ ВС.

Таким образом, задан закон композиции модулей и определены структуры ВС, реализующей алгоритмы задач из данного класса за минимально возможное время.

ВЫВОДЫ:

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

Список литературы:
1. Бекмуратов Т.Ф. Мусаев М.У. Методы построения классов толерантности на множестве алгоритмов. // Доклады АН РУз.-1997 -№7 с 24-27.
2. Мусаев М.У. Ручка. Е.И. Формальный аппарат установления сходства и различия алгоритмов и автоматов./ Ташк. Политех-ин-т-!988 . 16 стр. –ДЕП. УЗНИИНТИ 27.12.88.№912.
3. Мусаев М.У. Методы синтеза макроструктур функционально-ориентированных управляющих ВС. Доклады Республиканской научно-технической конференции. «Современное состояние и перспективы применения информационных технологии в управлении». Джиззак 5-6 сентября 2016 год. Стр. 81-85 .