Логико-комбинаторный подход к выбору оптимальных структур сложных технических систем

УДК 519.6

Н. А. Жиляк, аспирант

ЛОГИКО-КОМБИНАТОРНЫЙ ПОДХОД К ВЫБОРУ ОПТИМАЛЬНЫХ СТРУКТУР СЛОЖНЫХ ТЕХНИЧЕСКИХ СИСТЕМ

The paper considers the issue of unification of the basic algorithm of synthesis of real-time computation structures. The said algorithm suggests multiple execution of a significant number of its blocks because the optimum structure is selected according to this algorithm from an aggregate of viable options at the final stage of algorithm execution. The memory required for storage of data on alternative options depends upon the number of these options which is NP-exhaustion of all combinations of functional devices which satisfy the requirements of real-time computation processing.

Thus one of key tasks to be solved in designing complex technical objects, the real-time systems being a part of them, is the shooting for labor and time saving solutions. Suggested is the method based on the combinatory logic in selecting optimum structures out of an aggregate of correct options.

Введение. Широкий круг задач науки, производства и других отраслей хозяйственной деятельности требует оперативной обработки больших массивов данных. Это задачи из отраслей энергетики, гидро- и радиолокации, радионавигации, сейсмические, геологические, биомедицинские, биохимические, космические исследования, автоматизация научного эксперимента, управление технологическими процессами и объектами, моделирование сложных технических систем, исследования технических объектов в процессе их производства и эксплуатации и т. д. Решение проблемы требует специализированных вычислительных структур (устройств и систем) реального времени.

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

Возможности формализации процесса проектирования таких систем представляются с использованием теории синтеза вычислительных систем реального времени [1].

Данная теория позволяет синтезировать вычислительные структуры в условиях жестких требований к временным параметрам алгоритмов на основе практически любых математических моделей, заданных аналитическим выражением во временной области или алгоритмом ее реализации, обеспечить высокие технические показатели проектируемых вычислительных структур, в первую очередь, загруженности и ускорения за счет распараллеливания и конвейеризации его путей, автоматизировать процесс синтеза вычислительных систем реального времени. На основе теории синтеза вычислительных структур был разработан базовый алгоритм синтеза вычислительных структур реального времени (ВСРВ) [2].

Предложенный алгоритм предполагает многократное выполнение значительного числа его блоков, так как выбор оптимальной

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

Таким образом, одной из центральных задач, решаемых при проектировании сложных технических объектов, к которым относятся СВРВ, является поиск снижения трудоемкости проектирования. Для решения данной задачи предлагается метод, основанный на логико-комбинаторном подходе к выбору оптимальных структур из множества правильных вариантов.

Основная часть. В соответствии с теорией синтеза ВСРВ [2] множество альтернативных вариантов структуры проектируемого объекта может быть неявно представлено в виде множества векторов назначения R вида

[Я] = (гь Г2, ..., ги ..., гI),

где 1 = 1,., I, где I - количество вершин графа вычислительного алгоритма (ГВА) реализации математической модели проектируемого объекта; г^ = у - номер функционального устройства из множества X = 22, ..., 2и ..., г1} экземпляров классов 2„\п = типовых элементов, реализующих в совокупности все операции некоторого класса задач, т. е. элемента z¿(n) из подкласса Хп о фп о vi, т. е. класса элементов, реализующих функцию фп, отождествленную с вершиной V ГВА; N - мощность множества Хп.

При этом в общем случае может иметь место пересечение подмножеств (рис. 1):

= П .

Рис. 1. Иерархия технических средств, используемых при синтезе сложного технического объекта

На данном рисунке zk(и) - к-й элемент множества Хп.

Для гк(п) справедливо равенство

"П

=

к=1

Каждый объект z <е X характеризуется га-кортежами вида

<Тп, а пУ Р пУ ..., та п

где тп' - время реализации у-м ФУ п-й опера-

ции; а ^\ в „, та „ - атрибуты, соответствующие техническим характеристикам у-го ФУ (потребляемая энергия, стоимость, масса, габариты и т. п.), учитываемые выборочно в зависимости от постановки задачи проектирования.

Из вышесказанного следует, что назначение ФУ каждой конкретной вершине ГВА определяется неоднозначно из условия удовлетворения определенных требований, среди которых при проектировании ВСРВ первостепенным является значение требования реализации вычислительного процесса в реальном времени. Как показано в (1), этому требованию соответствуют ФУ, для которых выполняется неравенство

Т < А^зад,

где т - время реализации у-м ФУ операции, отождествленной с 7-й вершиной; А7зад - некоторый заданный интервал времени, определяемый требованиями реализации процесса в РВ.

Очевидно, что неоднозначность отношения

^(п):Т7(п) <АЭД ^

предполагает множественность вариантов назначения ФУ вершинам ГВА, которая может быть оценена множеством векторов назначения, формируемых из матрицы соответствия [1]:

м = [ К = П1 ,

7=1 г =1

где - мощность множества векторов назначения; - элемент матрицы соответствия.

В связи с вышесказанным трудоемкость алгоритма синтеза ВСРВ складывается из следующих компонент:

б=бд+ем,

где б - трудоемкость базового алгоритма; 0д - трудоемкость линейной ветви алгоритма; бг -трудоемкость обработки вектора временной развертки (ВВР); М - число повторений цикла обработки ВВР, определяемое оценкой множества (7).

В соответствии с одним из центральных положений теории синтеза вычислительных структур реального времени для каждого вектора из множества (1) должна выполняться процедура определения множеств свертываемых вершин. Предположим, что граф вычислительного алгоритма или нагруженный граф (так называемый граф базовой структуры) содержит дуги (7, к), (у', к), (I, п), (т, п), (5, 7), (д, 7) (рис. 2), при этом в соответствии с выбранным на одном из более ранних этапов синтеза вектором назначения гк = гп = , т. е.

V к О zу, V п О zу, V 7 О Zу.

Рис. 2. Фрагмент ГВА

Тогда возможны следующие варианты множества свертываемых вершин:

£о(1) = 0 - пустое множество (отсутствие свертки);

=

п=1

£з(1) = (7, п); = (к, п, 0.

В общем случае справедливо следующее утверждение.

Если существуют (I, к), (I, п), ..., (5, 7) и к, п, ..., 7^то возможно преобразование

(I, к) —(I, V), (V, к); (/, п) —^ (/, м>), (Щ п); .; (5, 7) —^ (5,р); (р, 7), (V, р) = 5>,

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

Задача формализации этого важнейшего этапа проектирования сложных технических объектов (выбор оптимального варианта структуры) может быть решена с помощью аппарата булевых логических функций [3].

Характеристической булевой функцией (ХБФ) множества альтернативных вариантов называется такая булева функция ..., гп), что простая импликанта этой функции равна единице тогда и только тогда, когда ее аргументы 2\ , ..., г 1п представляют собой правильный вариант структуры.

Установим взаимно однозначное соответствие между ФЭ и аргументами характеристической функции:

г О Ьг.

Тогда перечисление всех вариантов структуры проектируемого объекта можно представить в виде дизъюнкции всех простых импли-кант ХБФ, т. е. сокращенной дизъюнктивной нормальной формы:

Щ 1д1, ..., Ьпд) = (Ь1(1)лЬ2(1)л...л Ьnl(1))v v(Ьl(2)лЬ2(2)л. лЬг(1)л Ьу(1)Л... лЬn(2))v

v.vЬn

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

С ростом числа альтернативных вариантов целесообразно использовать особенные скобочные нормальные формы характеристической булевой функции. Для ее формирования достаточно выполнить операцию факторизации и использовать правила булевой алгебры, в частности: хлхл.лх = = х. Для приведенного примера (9) получим

F(b 1(q), ..., bNq(q)) =

= (Ьа(1)л... Abß (1)лЬг(1)лЬул_ лЬ/2)л

л... лЬ/^МЬ^л. .. лbß(1)лbг(1)лb;(1)лbyл. лЬг(1) л

лЬ;(1)л. лbг(2))v(b а(1)л. лbß (1)лbг(1)лb;(1)л. л лbг(2)лby...лbг(1)лb;(1)л.)v(baл.лbßлbг(1)лb;(1)л

лЬу...л. .. лЬ/^л^лЬ/^л. .. b/V.. лЬ;(1)) =

baЛbßЛ

л...лЬул[(Ь/1:1лЬ (2)лbг(3))v(bг(1)лb;(1)лbг (1)лЬ;(1)л

лbг

л

лЬ/^лЬ/'И^)] =

ba ^л...лЬул[(Ь/1^(2)лЬ/3У

лЬ^лЬ/^лЬ^МЬ/^лЬ/1^.

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

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

Pb ^ min, Azn < a,

где P = (P1, ..., P n) - вектор весов элементов Zi e Z; b - вектор булевых переменных, обозначающих отдельные элементы из множества Z; Azn < a - система ограничений для атрибутов проектируемого объекта.

Например, процедура построения варианта структуры с минимальным суммарным весом /-элементов, составляющих структуру, может быть осуществлена следующим образом:

1) замена в формуле ХБФ - bi ^ Fi;

2) замена логических функций на арифметические: конъюнкция ^ арифметическое сложение, дизъюнкция ^ функция взятия минимума.

Предположим особенная скобочная нормальная форма имеет вид

f(zi, ..., Z13) = Z1 z3[zI3(z7vz8vz 12Z6)v

vZ6Z 11 (z 7vz8vz10vz 12) vz 10 vz12)v

v

Пусть веса /-элементов, выражение в условных единицах равны: р1 = 0, р2 = 5 р3 = 4, р4 = 7, Р5 = 8, р6 = 3, р 7 = 6, р 8 = 4, р9 = 6, р 10 = 4, р 11 = 5, р12 = 3. Тогда, чтобы зафиксировать варианты подструктур, получающихся в процессе вычислений, значениям весов приписываются сложные индексы в виде подформул соответствующих подструктур. Ради краткости в этих подформу-

лах указываются только индексы переменных z5(I = 1, ..., n) вместо самих переменных. Тогда в соответствии с формулой (8) можно записать:

mrnpf = рз + min(p 13 + min(p 7, p8, Р12 + Рб), Рб + Р11 + min(p 7, ps, pío, Р12), min(p 4, p5 + p2,p 9) + min(p 7, ps, Р12 + Рб, Р10)) =

= 4з + min(313 + 48, 3б + 5n + 48vío, 69 + 48vío) =

= 43 + min(713-8, 12б11(8v10), 109(8v10)) =

= 43 + 713• 8 = 11 313 8 .

Таким образом, минимальный вес z = 11 имеет вариант z1z 3z13 z 8.

В процессе получения оптимального решения выполнено суммирование тринадцати величин и взятие минимума от семнадцати величин. Этот метод может быть применен после реализации процедуры базового алгоритма «Определение множества свертываемых вершин».

Эффективность использования рассмотренной методологии выбора оптимальной структуры оценивается таким образом:

QБ - QM Э = ^—100%,

QE

где в определена по выражению (8);

вМ=вл+вм,

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

Заключение. Использование данного метода выбора из множества альтернативных вариантов проектируемого объекта позволит на одной из ранних стадий проектирования ограничить число рассматриваемых вариантов структуры и тем самым снизить трудоемкость проектирования и объем памяти, требуемой для хранения информации о множестве альтернативных вариантов структуры проектируемого объекта.

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

чить в сочетании с лучшими мировыми образцами САПР автоматизацию всех стадий проектирования ВС и других технических систем. Предложенные методы представления и синтеза математических моделей для вычислительных структур, синтеза вычислительных структур реального времени и средств управления нашли применение при разработке программного обеспечения безбумажного самописца -регистратора РМ-2201. Данный прибор разработан в ОАО «МНИПИ» с использованием новых технологий в рамках государственной научно-технической программы «Радиоэлектроника, телекоммуникации, приборостроение».

Электронный самописец осуществляет сбор, обработку и архивирование результатов измерения.

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

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

Таким образом, предложенный метод позволяет повысить производительность вычислительных процессов, ориентированных на реализацию заданных функций прибора, что в свою очередь дает положительный экономический эффект при реализации регистратора РМ-2201, выпускаемого серийно ОАО «МНИПИ».

Литература

1. Жиляк, Н. А. Базовый алгор итм синтеза вычислительных структур реального времени / Н. А. Жиляк, А. С. Кобайло // Труды БГТУ. Сер. VI, Физ.-мат. науки и информ. - 2007. -Вып. XV. - С. 147-150.

2. Кобайло, А. С. Единичные функции для математических моделей вычислительных процессов / А. С. Кобайло. - Минск: БГУИР, 2001.

3. Анкудинов, Г. И. Синтез структуры сложных объектов. Логико-комбинаторный подход / Г. И. Анкудинов. - Л.: Изд-во Ленинград. ун-та, 1986.