Чапуров Д.В., аспирант Московского государственного института электронной техники
К ВОПРОСУ РАЦИОНАЛЬНОГО ПОДХОДА ПРИ СТРУКТУРНОМ
ПРОЕКТИРОВАНИИ СОВРЕМЕННЫХ РАДИОЭЛЕКТРОННЫХ УСТРОЙСТВ
Введение
Окружающий нас мир меняется очень быстро. То, что в прошлом занимало несколько лет сейчас сжато в рамках месяцев и недель. Областью техники, в которой наиболее ярко проявляется все новое, является современная электроника. Развитие рынка электроники приводит к увеличению функциональности и усложнению выпускаемых приборов. Появляются новые задачи, технологии их решения, а конкуренция между производителями оборудования растет. Идет специализация ресурсов по разработке и оптимизация их использования.
В статье делается попытка проанализировать процесс проектирования — процесс творческий, невозможный без участия в нем человека-творца. Среди методик проектирования и формальных процедур в последовательности: научно-исследовательская работа (НИР) — опытно-конструкторская работа (ОКР) — технологический процесс (ТП) — производственный процесс (ПП) обязательно есть этапы, которые требуют участия человека. Несомненно, важным является оснащение этой последовательности процессов множеством вспомогательных средств, позволяющих быстро и без чрезмерного напряжения просматривать многие варианты структурных решений для достаточно сложных ситуаций, оценивать общую сложность решений, планировать содержание и общий ход процесса проектирования, проходящего в коллективе соавторов. Рассмотрению аппарата комбинаторного поиска рациональных решений, особенностям применимости тех или иных математических алгоритмов и методов и посвящена данная статья.
Технология проектирования
Процесс проектирования требует затрат самых разнообразных ресурсов со стороны заинтересованных лиц. Проектирование изделий в производственном процессе — это процесс, состоящий из нескольких этапов разработки и оформления документов на изделие, блок-схема которого представлена ниже:
Рисунок 2
К сожалению, многое в этом, по сути своей, творческом процессе может быть отнесено к различным формам рутинного нетворческого труда. Существует два подхода к решению этой проблемы: первый основывается на расширении самой области проектирования, усложнении объектов проектирования; второй подход связан с применением ЭВМ в процессе проектирования, использования разного рода САПР для моделирования и автоматизации рутинных операций. Однако, большие надежды, возлагаемые на использование вычислительных средств, оправдываются далеко не в полной мере. С позиций формальных методов, имеющих хорошо проработанный математический аппарат, задача проектирования сводится к выбору числовых параметров данной структуры — параметрическому синтезу. Совершенной иной является задача структурного синтеза, которая не может быть решена формально. Именно решение этой задачи составляет содержание творческой деятельности инженера, его личного опыта, фантазии и интуиции.
При проектировании достаточно сложных объектов, характеризующихся большим объемом исходных данных и размерами исходного описания проектируемого объекта необходима декомпозиция объекта проектирования на некоторое число однородных подобъектов. Проектирование любого объекта начинается с анализа исходного задания, при этом приходится прибегать к использованию разработок в области искусственного интеллекта [5]. Естественным шагом со стороны проектировщика является поиск аналогов. Если удается получить достаточно близкий аналог, то в качестве исходного отправного варианта проектного решения берется решение, структура которого или идентична или достаточно близка к структуре аналога. Эта структура может подвергнуться значительному изменению, однако в качестве начальной берется именно она. Тем самым процесс декомпозиции уже является выполненным.
Результатом выполнения приема начальной декомпозиции независимо от конкретного типа объекта проектирования является составление формального задания на структурный поиск в форме, абстрагированной от конкретных физических признаков объекта. Выбор структуры проектируемого объекта может быть осуществлен на основе какой-либо формы конечного перебора. И задача поиска структуры, изначально представляемая как творческая неформальная, превращается в задачу, вполне определенную и решаемую методами комбинаторики.
Комбинаторная задача принятия решений при синтезе структуры
Алгоритмический объект проектирования Q, как и объект проектирования других классов, характеризуется набором некоторых потребительских свойств Б, которые должны допускать свое функциональное представление в зависимости от ряда внутренних А и внешних В по отношению к объекту параметров, а также переменных (входных X и выходных У).
1 А, Б г
X Б(Х,Л,Б,У) У
X — множество независимых входных переменных — аргументов функции Б, заданных по спецификации на объект Q и являющихся предметом обработки или преобразования в Q;
А — множество варьируемых параметров, доступных проектировщику при выполнении параметрического синтеза;
В — множество независимых параметров, представляющих внешние условия или такие параметры объекта, которые недоступны проектировщику;
У — множество выходных переменных, являющихся результатом обработки или преобразования в Q.
Функция объекта Q может быть представлена набором его частных функций / (X {; А; В; у ), где X {; А/; В {;У имеют тот же смысл, что и в общей функции Г, но / определяет
конкретную принадлежность перечисленных множеств именно /-му компоненту структуры.
Процесс декомпозиции основывается на выявлении информационных и установлении управляющих связей между компонентами структуры, выбранных из используемого структурного базиса. В результате формируются информационные и управляющие структуры объекта проектирования Q.
Х1
У1 X
У Х„
У„
Рисунок 3
Установление информационными связями заключается в определении соответствия между выходными переменными одного компонента структуры и входными переменными других компонентов, т. е. соответствий типа Xki = У ., где Xki - к-ая входная переменная /-го
компонента структуры, У. - р-ая выходная переменная .-го компонента.
Рисунок 4
Установление управляющих связей основывается на определении возможности функционирования (передачи управления) /-го компонента структуры. Оформление наличия и взаимоотношений связей в структуре объекта происходит в виде матрицы порядка (МП) столбец-список входов строка-список выходов пересечение строки и столбца с одинаковым номером — определение ^.
МП, в которой отражаются связи входных и выходных переменных различной структуры, определят совокупность информационных связей. В дальнейшем удобнее будет оперировать с редуцированными матрицами порядка (РМП), в которых удалены излишние, транзитивные замыкания.
Матрицу порядка можно видоизменить в граф порядка — ориентированный граф, в котором символы базисного множества
/1
/2
/3 |
- /4
/5
/б
имеют форму вершин графа, а сами отношения порядка имеют форму направленных дуг.
При исследовании и конструировании сложных структурных функций вводится понятие комбинаторного пространства, позволяющее использовать наглядные образы при проведении различных форм исследования.
При определении структурной функции в комбинаторном пространстве речь идет не о выявлении действительной аналитической модели, представляющей влияние структуры на значения целевой или критериальной функций, а о поиске той аналитической формы, которая позволит аппроксимировать сложную связь между структурой объекта проектирования и структурными функциями, значения которых определялись после выполнения цепочки сложных действий. В число таких действий входят, в частности, и алгоритмы параметрической оптимизации. Форма построения зависимости структурной функции от сконструированного комбинаторного пространства позволяет вести упорядоченный поиск экстремумов этих функций, когда функция меняет свои значения регулярно с изменением своего аргумента по некоторому пути в комбинаторном пространстве. Справедливо определение структурной функции — однозначного соответствия между значениями аргумента (точками в комбинаторном пространстве) и численным значением функции.
Задачи, связанные с нахождением экстремальных значений структурной функции, имеют особенности и решаются при помощи методов дискретной оптимизации. К сожалению, для дискретных задач не всегда пригодны критерии оценки эффективности алгоритмов оптимизации, используемые для непрерывных задач, отсутствует компактный математический аппарат. Практически единственным решающим приемом, обеспечивающим получение гарантированного результата в комбинаторике, является перебор, объем которого стремительно растет по мере увеличения размерности задачи. Еще С.В. Яблонским [3] была высказана гипотеза о том, что для экстремальных задач комбинаторного типа, к которому относится данная задача, не могут быть разработаны алгоритмы существенно менее трудоемкие, чем алгоритмы полного перебора.
В общем случае задачи комбинаторного типа являются задачами экспоненциальной сложности. Для многих практически важных и теоретически интересных постановок задач до сих пор известны лишь алгоритмы, требующие экспоненциальных затрат. Поэтому целочисленные задачи линейной оптимизации могут быть решены точно только до определенного предела.
Таблица 3
Сложность алгоритма Максимальный размер задачи, разрешимой за единицу времени
R на современных ЭВМ на ЭВМ с 10ти кратной скоростью на ЭВМ с 1000 кратной скоростью
п K ^ 1000K
П п L почти 10L 1000L
п2 M 31^
п N 2.^ ^
2п P P+3.3 P+9.97
Точная оценка сложности комбинаторной задачи, как правило, сама представляет задачу столь же сложную. Эта задача перечисления всех точек области определения структурной функции, описывающей потребительские свойства объекта проектирования, требует применения особых приемов в силу своей труднорешаемости. Регулярные методы получения точных оценок (методы расширения) пригодны для задач небольшой размерности, классический метод включения и исключения имеет ограниченные возможности в практическом применении.
При определении мощност
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.