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

АННОТАЦИЯ

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

ABSTRACT

The article is devoted to research and development of the tolerance of equipment for algorithms and automata designed to automate the solution of one of the main issues of the VS macro-synthesis problem — determining the optimal composition of functional modules (FM) developed by the VS, differing in the minimum number of FM types, but the combination best implements any algorithm from a given complex tasks.

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

Keywords: tolerance of algorithms, functional modules, system of information exchange, optimal set, investment relationship.

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

Решения задачи. Оптимизация набора функциональных модулей на классах толерантности. Предварительно на подмножестве В векторов  выполним вспомогательное преобразование.

Базисные системы маршрутов , [1] входящие в подмножество В могут иметь некоторые количество одинаковых маршрутов, т.е. координат – единиц в векторе . Например, маршрут из  маршрут  из  могут быть одинаковыми, т.е.. Однако любые два вектора  и  из В имеют минимум два различных маршрута. Поэтому выделим общую часть, если существует, у всех векторов, входящих в подмножество В, следующим образом. Перебирая координаты всех векторов по порядку возрастания номеров от 1 до m, отметим те компоненты-единицы, которые имеются в составе всех векторов. Тогда вектор , имеющий компоненты-единицы на этих местах, а остальные нули, будет общей частью векторов подмножества В. У каждого вектора , подмножества В заменим помеченные координаты-единицы нулями и перенумеруем их от 1 до s: .

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

Будем искать вектора – представители модулей находящиеся в отношении  с вектор – блоками  из подмножества В. При этом выполнять процедуру поиска необходимо с учетом того, что вспомогательное преобразование позволяет уменьшить время сравнения векторов друг с другом, если оно выполняется лишь на тех значениях компонентах каждого вектора и подмножества, которые получены после удаления компонент – единиц общей части. В результате получим следующие подмножества векторов, c которыми вектора находится в отношении [2] е- вложения:

                                            (1)

Используя (1), выпишем для каждого вектора- представителя модуля  те вектора , которые находится с ни в отношении 

Выберем теперь вектор, с которым находится в отношении максимальное количество векторов  

Исключим соответствующий ему модуль и реализуемые им блоки алгоритма из дальнейшего рассмотрения. Из оставшийся модулей выбираем аналогичным образом тот, который выполняет максимальное количество блоков алгоритмов из всех оставшийся. Перебор прекращается, когда все блоки алгоритма будет реализованы некоторым, а подмножеством ФМ , которое и будет минимальным по количеству типов модулей.

Оптимизация набора функциональных модулей на таксонах.

В соответствии с построением таксонов, в первый включено максимальное количество векторов, поэтому с него начнем выделение оптимального набора функциональных модулей.

Найдем в наборе ФМ такие, с которыми вектор таксон , находится в отношении е-вложения. Если среди модулей не окажется таких, которые находятся в отношении е-вложения с полученным таксоном, то установление отношения вложения можно продолжить двумя путями:

-уменьшением значения -радиуса сферы до тех пор, пока не найдутся модули, содержащие нужные комплексы маршрутов;

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

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

Для каждого вектор-таксона  получаем подмножество вектор- модулей, находящихся в отношении  с соответствующими вектор-модулями: первый вектор-таксон  находится в отношении вложения е с подмножеством вектор-модулей:

;

второй вектор таксон – с подмножеством вектор-модулей:

;

наконец, последний вектор-таксон - с подмножеством вектор-модулей:

;

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

На этом процесс оптимизации базисного набора ФМ заканчивается, а полученный из множества набор функциональных модулей  будет оптимальным [3].

Число таксонов является функцией от  геометрического расположения векторов в m-мерном пространстве. Для меньших величины  и будут большими числами, а для большихвеличины  и будут меньше. Перебрав различные значения , q и  можно, исходя из условий конкретной задачи, выбрать наиболее подходящие ,  и которые нужно сделать, очевидно, возможно меньшими.

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

Список литературы:
1. Мусаев М.У. Метод выбора функциональных модулей/ Ташк. Политех.ин-т.- Ташкент,1989-15 стр.-Деп. В Уз НИИНТИ 20.04.89. №989 Уз89.
2. Бекмуратов.Т.Ф, Мусаев М.У. Методы распознавания сходства и различия алгоритмов и автоматов. Узбекский журнал «Проблемы информатики и
энергетики». Ташкент 1994 г. №2*3; с.1-6.
3. Мусаев М.У. Функция сравнения маршрутов на моделях алгоритмов. Доклады АН РУз № 8. 1997г. С.21-23.