Варианты структурной организации систем проектирования РЭА

Е.И. Артамонов, Зав.лаб. ИПУ РАН,
д.т.н., проф.,г.Москва

В.А.Высоких, аспирант ИПУ РАН

Формализованные методы структурного проектирования позволяют ускорить процесс разработки систем, улучшить их эксплуатационные характеристики и обеспечить передачу знаний по принципам структурной организации. На примере выбора лучшей структурной организации систем проектирования РЭА показана возможность использования формализованного метода синтеза структур [1,2]. Метод основан на предварительных операциях со структурами алгоритмов  и последующего выбора оптимального, по наперед заданным критериям,  покрытия полученных структур алгоритмов соответствующими программными реализациями. Метод структурного проектирования может использоваться для систем различной размерности, начиная от систем со сравнительно простыми алгоритмами функционирования и до программных комплексов, включающих набор систем для сопровождения всех этапов жизненного цикла создаваемого промышленного продукта.

 

Операции со структурами алгоритмов.

 

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

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

 В литературе часто встречается понятие «модуль», как реализация минимально неделимых частей алгоритма.  В [3], например, под программным модулем понимается набор связанных процедур вместе с данными, которые они обрабатывают.  Для решения задач формализованного синтеза структур систем важным является более точное определение  понятия минимально неделимой части алгоритма. 

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

,                                                             (1)

где - множество способов кодирования объектов информации;

       - множество форм внешнего представления объектов информации;

 - множество точностей представления объектов информации.

 

            Из выражения (1) видно, что недостаточно проводить декомпозицию структур алгоритмов только по связности, как это указано в  [7], необходимо еще учитывать и параметры операндов.  Тогда минимально неделимая часть алгоритма и ее реализация формально могут быть определены следующим образом:

Определение 1. Связанную часть алгоритма  последовательного выполнения операций над данными с  и  назовем   «локальным алгоритмом» (ЛА).

Определение 2.  Реализацию ЛА назовем локальной структурой (ЛС).

Покажем далее, что минимальной неделимой частью алгоритма является ЛА, а его реализацией – множество ЛС.

Пусть в алгоритме содержится  = операций, где  – число операций i-го типа, - число типов операций.

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

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

                                                              (2)

где       - стоимость реализации одного разряда операции i-го типа;

- сложность кодирования операндов в j-ом операционном блоке i-го типа.

       Определение 3. Сложностью кодирования  операнда  в коде   с точностью  назовем полное количество двоичных разрядов, требуемое для представления   на технических средствах системы.

       Для позиционной системы счисления с основанием имеем

 

                       ,                                             (3)

 

где   йХщ - означает ближайшее целое число к  Х.

          Стоимость реализации алгоритма в ПО типа б):

                                             (4)

где       - стоимость реализации одного элемента памяти,

 для .

Определим, при каких условиях лучшей реализацией будет ПО типа а), т.е.  разделение на ЛА будет целесообразно, если Q1< Q2 :

 

                           (5)

Для выполнения условия достаточно, чтобы имело место:

 для 

                                                   (6)

Таким образом, действительно, соотношение (6), учитывая (3), выполняется только при  и/или  для, что дает возможность сформулировать первое правило в операциях со структурами алгоритмов – правило первоначального разделения структуры алгоритма на локальные (ЛА).  

Правило 1. Первоначальное разделение алгоритма  на локальные алгоритмы (ЛА) выполняется при наличии несвязанных операций,  и/или , . 

Дополнительно следует отметить, что правая часть соотношения (6)  оказывается меньше при постоянных значениях  и , поскольку стоимость разряда памяти меньше стоимости разряда операционного блока . При таких условиях следует стремиться к объединению однотипных операционных блоков. Наличие множеств значений  и  характерно в большей степени для интерактивных систем [5], в которых информация по входу и выходу связана с датчиками технологических процессов, исполнительными механизмами,  средствами интерактивного взаимодействия и другими системами.

Операция разделения структуры алгоритма на ЛА иногда приводит к ситуации, когда возникает неопределенность по выбору способа кодирования  и форм    внешнего представления объектов информации между ЛА. В первом случае следует применять правило 2. Во втором – правило 3.

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

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

                                   (7)

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

 

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

       Операции объединения проводятся по следующим правилам.

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

Правило 5. При объединении двух и более ЛА с различными точностями представления информации точность представления данных в обобщенном алгоритме выбирается как,, где - число ЛА.           

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

где  -время выполнения одной операции преобразованного алгоритма,

 -максимально допустимое время выполнения заданного алгоритма,

 - число последовательно выполняемых операций.

       Для последовательных  форм представления информации возможен частный случай объединения  параллельных ЛА без увеличения общего времени вычислений, в том случае, если выполняется соотношение:

где  - время обработки одного разряда информации.

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

       Таким образом, за счет операций с алгоритмами производится упорядоченный перебор вариантов структур. Количество вариантов структур не превосходит общего числа сочетаний ЛА, полученных при начальном разделении.

 

Построение сетевых моделей вариантов реализации структур систем

 

       Традиционно решение задач автоматизированного проектирования и управления складывается из следующих основных наборов множеств связанных операций (ЛА):

 

 ,                                       (8)

где  - проблемно ориентированные задачи обработки информации;      

       - запись и чтение информации из блоков памяти;

       - межоперационные и межсистемные преобразования информации; 

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

       - вывод и преобразования информации для внешних устройств, исполнительных механизмов и станков с ЧПУ;          

       - управление процессом работы системы.

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

      (9)

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

Из выражения (4) следует:

1.      При объединении двух операционных блоков (сокращении числа )  возрастает стоимость  за счет увеличения ячеек памяти в операционных блоках и необходимости выбора  из двух возможных. Тогда стоимость вычисляется по выражению:

       (10)

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

3.      Стоимости  не зависят от взаимосвязей операционных блоков. 

 

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

Фрагмент структуры обобщенной модели, например, для двух способов кодирования  a1 и a2  показан на рис.1.  Левая сторона пространственного графа является входом, правая – выходом.        Множества локальных структур ЛС11-ЛС31 и ЛС12-ЛС32 реализуют локальные алгоритмы для способов кодирования a1 и  a2 соответственно.

Из рисунка видно, что преобразования данных в обобщенной модели занимают значительное место. Так ЛС1212, ЛС1221, ЛС2312, ЛС2321 реализуют ЛА преобразований способов кодирования, вертикальные плоскости в пространственных графах представляют преобразования форматов файлов и типов данных. ЛС1212 и ЛС2312, ЛС1221 и ЛС2321 являются эквивалентными; ЛС1211, ЛС2311, ЛС1222, ЛС2322 отображают связи между вершинами предыдущих и последующих графов (значения их дуг равны 0). Качество проектируемой системы в существенной мере зависит от количества преобразователей, используемых не только внутри комплекса, но и для согласовании с другими, внешними по отношению к проектируемой, системами. Сокращение общего количества преобразователей возможно за счет использования стандартных структур данных. 

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

 

Рис.1

Разработанный метод синтеза структур эффективно использовался при создании программно-технических комплексов CAD/CAM систем, системы управления процессами смешения нефтепродуктов, устройств измерения параметров технологических процессов.   

 Варианты структурной организации ПО САПР РЭА 

 

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

Основными операциями алгоритма функционирования САПР РЭА являются: 

1.       Разработка схемы электрической принципиальной (СхПР).

1.1.  Создание базы данных элементов СхПР.

1.2.  Размещение элементов СхПР.

1.3.  Трассировка  соединений между элементами на СхПР.

1.4.  Выпуск таблицы перечня элементов на СхПР.

1.5.  Разработка электронной документации и вывод чертежей на СхПР.

2.       Автоматическая трассировка соединений между элементами на печатной плате (ПП).

2.1. Создание база данных элементов ПП.

2.2. Размещение элементов ПП. Подготовка модели трассируемого поля ПП.

2.3. Трассировка  соединений между элементами на ПП.

2.4. Выпуск фотошаблонов.

3.       Разработка электронной документации на монтажные схемы (СхМ).

4.       Проектирование конструктивов.

 

 

 

Рис.2

 

На рис. 2 показаны основные этапы проектирования, соответствующие указанному алгоритму. Реализация каждого этапа покрывается множеством имеющимся на рынке систем (на рис. показаны синим цветом некоторые представители этого множества). Взаимодействие между системами в том числе между отдельными этапами производится через преобразования структур данных. Возможные структуры данных показаны красным цветом.  Лучшая реализация выбирается по наперед заданным критериям. На рис.  3,4,5,6,7     приведены некоторые из возможных вариантов реализаций.

Рис.3

Рис.4

 

Рис.5

Рис.6

 

Рис.7

 

Литература

1.        Artamonov E.I. Automation of digital device structure design. B-215, ACTA IMEKO, 1973, p. 561-570.

2.       Артамонов Е.И., Хачумов В.М. Синтез структур специализированных средств машинной графики. МЦНТИ. Москва,1991 г. 145 стр.

3.        Бьерн Страуструп. Язык программирования С++. Третье издание. AT&T Labs. Мюррей-Хилл, Нью-Джерси. Перевод с английского. М.-СПб. 2000 г.