Содержание к диссертации
Введение
1. Методология принятия решений на этапе синтеза структуры встраиваемых микроконтроллерных систем 11
1.1. Технология проектирования ВМС 11
1.1.1. Особенности элементной базы ВМС 11
1.1.2. Средства проектирования ВМС 17
1.1.3. Этап структурного проектирования ВМС 28
1.2. Теория поддержки принятия решений при структурном проектировании ВМС 29
1.2.1. Общие положения 29
1.2.2. Критериальное структурирование множества альтернатив 30
1.2.3. Вербальный анализ решений 40
Выводы к главе 1 43
2. Оценка критериев альтернативных вариантов структур ВМС 45
2.1 Общий подход к выбору структуры ВМС 45
2.2 Количественные и качественные параметры векторных критериев вариантов структур ВМС 47
2.3 Методика и алгоритм вычисления обобщенного критерия качества структуры ВМС 50
Выводы к главе 2 59
3. Интеграция аппаратных и программных компнентов структур ВМС 60
3.1. Концептуальные положения подхода 60
3.1.1 .Формирование множества допустимых решений 60
3.1.2. Формирование множества критерий 60
3.1.3. Иерархия целей 62
3.1.4. Свойства критериев 65
3.1.5. Иерархия критериев 66
3.2 Методика оценки сочетаний аппаратных и программных средств по качественным и количественным критериям 69
Выводы к главе 3 73
4. Программа поддержки принятия решений для задач размещения программ по уровням памяти ВМС 75
4.1 Постановка задачи 75
4.2 Используемые методы поддержки решений 79
4.3 Методы прямой и обратной фильтрации 84
4.4 Механизм фильтрации 85
4.5 Метод первой точки вне окрестностей и стратегия удвоения 85
4.6 Начальные значения d и Дё 87
4.7 Метод ближайшей точки вне окрестностей 88
4.8 Метод наиболее удаленной точки окрестностей 89
4.9 Обратная фильтрация 89
4.10 Постановка задачи проектирования СППР 90
4.11 Технология размещения программ по уровням
памяти ВМС с использованием СППР 91
4.12 Принятие проектных решений 93
Выводы к главе 4 95
Заключение 96
Литература 98
- Теория поддержки принятия решений при структурном проектировании ВМС
- Количественные и качественные параметры векторных критериев вариантов структур ВМС
- Методика оценки сочетаний аппаратных и программных средств по качественным и количественным критериям
- Метод первой точки вне окрестностей и стратегия удвоения
Введение к работе
Диссертационная работа посвящена разработке математического и программного обеспечения поддержки принятия решений при выборе структур микроконтроллерных систем.
Для решения этой задачи в диссертации используются теория и методы принятия решений.
Актуальность работы. Проблемы оценки и выбора аппаратных и программных компонентов микропроцессорных устройств и систем остаются актуальными для разработчиков уже более четверти века. Это связано с одной стороны с постоянным ростом номенклатуры элементной базы, а с другой - расширением областей применения микрокомпьютерных систем.
Повсеместное использование микропроцессорной элементной базы породило новый класс устройств - встроенные микроконтроллерные системы (ВМС). Этот класс устройств возник благодаря резкому снижению стоимости микропроцессорной элементной базы. Использовать ВМС, например, в недорогом фотоаппарате теперь не вызывает никаких проблем связанных со стоимостью изделия. Однако это действительно так, если грамотно выбрана элементная база ВМС, а, следовательно, ее структура. Не последнюю роль при этом играют стоимость и сроки проектирования, объем выпуска изделия.
У разработчиков ВМС имеется возможность реализовывать управляющие алгоритмы различными способами, используя элементную базу разных фирм. Естественно, что при этом получаются разные варианты возможных структур ВМС. Из такого набора возможных вариантов разработчик на этапе структурного синтеза должен выбрать для последующей реализации наиболее рациональный вариант. Этап структурного синтеза очень ответственен, т.к. от правильности выбора варианта будут зависеть трудоемкость и сроки проектирования системы, ее стоимость при производстве.
Целью диссертационной работы являются разработка методики и алгоритмов средств поддержки принятия решений, позволяющих проектировщику упорядочить множество вариантов структур ВМС для последующего выбора по заданным критериям оптимального варианта. Варианты структур задаются перечислением альтернатив с присущими им параметрами или диапазонами их изменений.
Для достижения этой цели потребовалось
провести анализ этапов проектирования ВМС;
проанализировать функциональные, параметрические и конструктивные характеристики элементной базы, используемой для ВМС;
исследовать функциональные возможности инструментальных средств проектирования и их влияние на выбор вариантов структур ВМС и на ход проектирования;
разработать методику оценки количественных и качественных параметров компонентов и среды проектирования ВМС для построения многокритериальной функции ценности;
разработать систему предпочтений проектировщика на этапе структурного проектирования ВМС, применительно к функциональным особенностям и параметрам элементной базы и инструментальных систем проектирования;
провести анализ применимости известных методов принятия решений к задаче выбора оптимальной структуры ВМС.
На защиту выносятся следующие положения
метод построения многокритериальной функции ценности для характеристики ВМС и их среды проектирования;
метод оценки и выбора элементов программно-аппаратных структур ВМС;
метод формирования критерия полезности для задачи размещения программ по уровням памяти ВМС.
Методы исследования. При решении поставленных задач использовалась теория множеств, методы исследования операций, теория и методы принятия решений.
Научная новизна работы заключается в разработке теоретических и методологических основ решения задачи выбора оптимального варианта структуры ВМС на этапе структурного проектирования:
предложена методика принятия решений применительно к выбору элементной базы ВМС с совокупности с инструментальными средствами проектирования;
разработаны методы оптимизации и поддержки принятия решений при размещении программ по уровням памяти ВМС;
сформулирована аксиоматика системы предпочтений проектировщиков при принятии решений на этапе структурного проектирования.
Практическая ценность работы состоит в создании методики оценки выбора структур ВМС для последующего выбора оптимального варианта. В рамках работы разработана программа поддержки решений для размещения управляющих программ по уровням памяти ВМС, используемая разработчиками в интерактивном режиме на этапе структурного проектирования. Программа используется так же и в учебном процессе.
Реализация результатов работы. Основные результаты диссертационной работы внедрены в Московской Государственной Академии Приборостроения и Информатики на кафедре «Персональные ЭВМ, системы и сети».
Апробация работы. Результаты работы были доложены на Международной научно-практической конференции «Фундаментальные проблемы приборостроения, информатики, экономики и права (г. Сочи, 1999).
Публикации. Основные материалы диссертации опубликованы в 7 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, списка использованной литературы из 95 наименований. Основной текст диссертации изложен на 104 страницах машинописного текста.
В первой главе анализируются проблемы, решаемые разработчиками ВМС на стадии структурного проектирования. На основании проведенного обзора работ Авена О.И., Вентцель Е.С., Прангишвили И.В., Трахтенгерца Э.А., Ларичева О.И., Липаева В.В., Дж. фон Неймана, Моргенштерна О., Саати Т. и других сделан вывод о применимости теории принятия решений к задачам структурного проектирования ВМС [5, 31-37, 42, 48, 52].
В главе рассматривается методика проектирование устройств на базе ВМС, начиная с разработки технического задания ТЗ. Анализируется этап структурного проектирования ВМС на основе ТЗ и определяется необходимый для его реализации набор базовых функций, последовательно или параллельно выполняемых во времени.
Показано, что набор базовых функций, из которых складываются различные алгоритмы управляющих устройств, обозрим. Каждой базовой функции в соответствие могут быть поставлены одна или несколько ее физических реализаций (программных, аппаратных или программно-аппаратных) с соответствующими параметрами.
Целью этапа структурного проектирования является выбор
оптимальной структуры ВМС. Однако понятие оптимальности здесь нельзя рассматривать, как это принято в теории исследования операций, где существует единый критерий оптимальности.
Показано, что задача структурного синтеза ВМС по своей природе многокритериальна, причем критерии не всегда согласованы между собой и часто противоречивы. Кроме того, критерии носят как количественный, так и качественный характер, что затрудняет их оценку.
Поэтому для решения задачи выбора оптимальной структуры по заданным критериям в работе используются модели и методы принятия решений.
Далее в главе эта проблема анализируется с позиций теории и методов принятия решений. Анализируются трудности, связанные с получением информации от ЛПР относительно важности критериев в условиях многокритериальности. Сложность экспертных оценок оказывается одинаковой как для качественных, так и для количественных измерений ценности. В обоих случаях используются одни те же бинарные отношения.
Далее рассматривается методика анализа непротиворечивости экспертных оценок на основании свойств используемых бинарных отношений.
Показано, что на конечном множестве альтернатив существует функция ценности, которая ставит в соответствие более предпочтительной альтернативе большее числовое значение. Основой для построения решающих правил служит информация о предпочтении различных альтернатив для ЛПР. Ее математическая основа - система аксиом, в рамках которых существует некоторая мера ценности, позволяющая упорядочить результаты решений. Принятие решений в условиях определенности характеризуется детерминированной связью между выбранной альтернативой и ее исходом.
В работе показано, что при проектировании ВМС всегда присутствует достаточно много количественных показателей. При этом при минимуме качественных показателей (и к тому же весьма очевидных), модель структур ИМС можно считать объективной. Однако при появлении качественных трудноопределимых показателей модель становится субъективной. Показаны ситуации, в которых возникают такие проблемы.
Модель принятия решений выглядит следующим образом. Постановка задачи определяет множество допустимых решений, определяя понятие «вариант решения». В работе рассматривается задача полного упорядочения множества решений. Первоначально для экспертной оценки формируется иерархия целей, т.е. набор критериев. Показано, что набор критериев, соответствующих целям экспертизы, должен быть полным, не избыточным и конструктивным (действенным). Этот этап принятия решений носит эвристический характер, в работе разрабатываются общие принципы его проведения.
Во второй главе анализируются количественные и качественные параметры физических реализаций, которые формируют вектора критериев вариантов структур ВМС.
При решении задачи сравнительной оценки различных физических реализаций компонентов МВС желательно получить обобщенную скалярную величину оценки качества для каждого компонента и варианта структуры в целом. Основная проблема, возникающая при формировании такой оценки, заключается в неоднородности критериев (характеристик, параметров), используемых для сравнения, поскольку различные критерии имеют свои единицы измерения.
В известной процедуре вычисления обобщенной оценки производится суммирование критериев, умноженных на их весовые коэффициенты. Последние определяются экспертным путем. Эту процедуру, возможно, частично формализовать, конечно, не отказавшись полностью от экспертных оценок. Отметим, что рассматриваемый метод наиболее эффективно работает в случае большого числа критериев.
Пусть задано множество физических реализаций МВС, перечень параметров их характеризующих, по которым они сравниваются. На первом этапе множество критериев, учитывая их возможную зависимость друг от друга, представляется в виде дерева, самый нижний уровень которого образуют единичные параметры. Именно эти параметры получаются с помощью физических измерений или экспертных оценок, соответственно при качественных и количественных оценках.
На втором и последующих уровнях расположены комплексные критерии. Комплексные критерии формируются исходя из единичных параметров или комплексных критериев нижнего уровня. При этом единичные показатели должны быть нормированы - измеряться в относительных единицах, лежащих в интервале от нуля до единицы.
Переход от единичных критериев, измеряемых физическими величинами, к относительным осуществляется с помощью функций перевода, определяемых экспертами.
После того, как определены относительные значения исходных параметров, необходимо по их совокупности синтезировать соответствующий комплексный критерий. Этот процесс можно провести путем задания операторов агрегирования для каждого комплексного критерия.
Задача расчета обобщенного критерия распадается на множество подзадач расчета каждого комплексного критерия на основе порождающих его критериев. Соответственно, проблема агрегирования критериев для определения обобщенного критерия распадается на множество небольших по размерности задач, связанных с заданием и обоснованием операторов агрегирования для каждого комплексного критерия.
В главе проанализированы факторы, рассматриваемые при оценке ВМС.
В третьей главе рассматривается проблема интеграции аппаратных и программных компонентов как проблема синтеза структуры ВМС.
В главе предлагается подход к синтезу структуры ВМС в виде решения задачи интеграции аппаратных и программных средств, в основу, которой положен алгоритм выбора оптимального (квазиоптимального) соответствия их параметров, ориентированный на реализацию с помощью автоматизированной системы поддержки принятия решений (СППР) в диалоговом режиме работы пользователя. Для формирования на первоначальной стадии проектирования допустимых аппаратных и программных альтернатив используются критерии оценки как качественных, так и количественных их признаков и сочетаний.
Разработан набор критериев для отбора из множества компонентов только тех, количественные значения параметров которых удовлетворяют требованиям ТЗ и предпочтениям пользователя.
На основании предложенной методики разработаны алгоритмы СППР.
В четвертой главе рассматриваются методы оптимизации и поддержки принятия решений для задачи размещения программ по уровням памяти в ВМС. Такие задачи весьма актуальны, т.к. многие микроконтроллеры имеют в своем составе ограниченный объем памяти.
Отображение адресного пространства процессов на физическую память осуществляется либо с помощью страничной организации памяти, либо путем свопинга программ. Второй способ в настоящее время может быть эффективно реализован в ВМС благодаря наличию встроенных интерфейсов последовательной передачи данных, как в микросхемах флэш-памяти, так и микроконтроллерах. Поэтому во многих случаях имеется техническая возможность загрузки (свопинга) фрагментов программ в память микроконтроллера на время их выполнения. В главе дан обзор технических средств, позволяющих реализовывать этот процесс.
Временные параметры и объемы закачиваемых фрагментов программ могут быть самыми разнообразными: программы могут храниться как во флэш-памяти большего объема, эмулирующей работу жесткого диска, так и в памяти меньшего объема, подключенной через последовательный интерфейс к микроконтроллеру.
При распределении задач по уровням проектируемой системы учитывается число подзадач управления и ставится задача минимизировать общий объем загружаемых программ, объем памяти микроконтроллера при ограничениях на время транзакций в процессе свопинга.
На первом этапе многокритериальной оптимизации происходит выделение эффективных точек из множества допустимых решений. Такой процесс поиска оптимального решения является длительным, поэтому для сокращения перебора в работе автором был использован алгоритм Балаша, по которому рассматриваются только допустимые решения.
При этом создается файл эффективных решений. Аналогично создается файл слабоэффективных решений. При синтезе структуры устройства при таком подходе первоначально выделяется множество допустимых решений, а затем методом перебора выбирается наиболее подходящий (оптимальный) вариант.
При получении большого количества эффективных точек, их можно отфильтровать, запуская процедуры прямой и обратной фильтрации и получать множество подходящих точек.
На основе этого алгоритма была разработана программа поддержки решений. Результаты работы программы выводятся для ЛПР в графическом виде на экран.
Программа разработана на языке С + с использованием пакета RESOURCE WORKSHOP и представляет собой загрузочный модуль, который работает в среде WINDOWS.
Теория поддержки принятия решений при структурном проектировании ВМС
Основные идеи прикладной дисциплины под названием "Теория поддержки принятия решений" (английские эквиваленты - Decision Science, Decision Making) состоят в следующем [42, 31-37, 47, 48, 59]. Схема процесса принятия решения не зависит от той предметной области, в которой принимается решение. Принять решение - значит, выбрать конкретный вариант действий из некоторого множества вариантов. Принятие решений - процесс человеческой деятельности, направленный на выбор наилучшего варианта действий. Слово поддержка означает, что цель методов не собственно принятием решений, а подготовкой рекомендаций для лица, которому нужно решение принимать - ЛПР. Применительно к задаче, решаемой в диссертационной работе, под ЛПР будет пониматься ведущий разработчик проекта. Варианты действий называются альтернативами, показатель привлекательности альтернатив называют критериями. Различают три этапа принятия решений - изучение и систематизация информации, конструирование альтернатив, выбор лучшей (лучших) альтернатив. Первоначально у ЛПР может не быть даже множества альтернатив, из которых предстоит делать выбор. Формирование множества альтернатив есть предварительный этап решения проблемы выбора. Задачи принятия решений: упорядочение (структурирование) множества многокритериальных альтернатив, классификация многокритериальных альтернатив, выделение лучшей. Рассмотрим основные способы структурирования.
Первый из них является КЛАССИФИКАЦИЯ. Исходное множество неструктурированных альтернатив разбивается на НЕУПОРЯДОЧЕНЫЕ друг относительно друга классы. Можно считать, что каждый класс есть подмножество исходного множества альтернатив. Второй способ структурирования называется СТРАТИФИКАЦИЯ. Стратификация есть разбиение множества на ряд упорядоченных уровней. Страты выражают некоторые уровни "качества". Следующий способ структурирования называется РАНЖИРОВАНИЕ. Внешне он напоминает стратификацию, но в отличие от нее при упорядочивании (ранжировки) ранги (уровни) не выражают "качества", а трактуются просто как "номер в списке". Если один и тот же ранг присвоен нескольким объектам, ранжировка называется нестрогой. Структуризации множества альтернатив нужна не сама по себе, а с целью выполнить ВЫБОР. Классификация здесь стоит особняком, поскольку для нее выбор сводится по сути, к выбору определенного класса, к которому следует отнести альтернативу.
Стратификация и ранжировка предоставляют нам более широкие возможности выбора. Методы структуризации делятся на критериальные и некритериальные. Некритериальные методы структурирования основаны на сравнении пар альтернатив "в целом" (предполагается, что все альтернативы попарно сравнимы). Оно проводится, не используя в явном виде понятия "критерий". Один из распространенных простейших способов преобразования подобных структур в ранжировку является "метод строчных сумм". Для реализации метода, обычно строят квадратную таблицу парных некритериальных сравнений. На пересечении строки и столбца таблицы располагают индексы результатов парных сравнений - 1, если альтернатива с именем строки лучше альтернативы с именем столбца, - О, если альтернатива с именем строки хуже альтернативы с именем столбца, - 1/2, если альтернатива с именем строки равноценна альтернативе с именем столбца. Подсчитываются суммы строк, и альтернативе, имеющей максимальную строчную сумму, присваивается ранг 1. Альтернативе, имеющей следующую по величине сумму, присваивается ранг 2, и так далее, пока не будут отранжированы все альтернативы. При структурирование множества альтернатив с использованием критериев уровень привлекательности определяется обобщенной оценкой по критериям. Методы многокритериальных решений зависят от степени объективности рассматриваемых моделей. Для объективных моделей при единственном критерии, а также в случае перевода оставшихся критериев в ограничения, для получения оптимального решения используются методы исследования операций. Наличие многих критериев качества решений делает необходимым нахождения компромисса между ними на основе предпочтений ЛПР. Для проблем и их моделей имеющих объективный характер, и качество решений которых оценивается по многим критериям, типичен метод "стоимость-эффективность". Он включает в себя первый этап
Количественные и качественные параметры векторных критериев вариантов структур ВМС
При решении задачи сравнительной оценки различных физических реализаций компонентов МВС желательно получить обобщенную скалярную величину оценки качества для каждого компонента и варианта структуры в целом. Основная проблема, возникающая при формировании такой оценки, заключается в неоднородности критериев (характеристик, параметров), используемых для сравнения, поскольку различные критерии имеют свои единицы измерения.
Перечислим некоторые критерии аппаратных составляющих, определяющие алгоритмические и системные параметры ВМС: 1. Производительность. Экспертная оценка возможности реализации критических по времени фрагментов управляющего алгоритма выбираемой элементной базой. Процессор и вспомогательные аппаратные средства могут оцениваться по степени избыточности по производительности. Чем выше избыточность, тем более вероятно, что на основе выбранной элементной базы синтезируемый вариант структуры ВМС является допустимым. 2. Логические возможности. Экспертная оценка возможности реализации управляющего алгоритма заданного уровня логической сложности на выбираемой элементной базой. Процессор может оцениваться по степени избыточности по объему памяти, вспомогательные аппаратные элементы - по степени соответствия их алгоритмов функционирования фрагментам управляющих алгоритмов. 3. Функциональная избыточность. Степень избыточности (запас по производительности, памяти и, пока не используемых, функциональных элементов) - критерий, позволяющий оценить возможность дальнейшей модернизации ВМС. Естественно, наличие такой избыточности в качестве положительного фактора в будущем компенсируется повышением стоимости изделия в текущий момент. 4. Конструктивное исполнение. Этот параметр можно рассматривать как с классической точки зрения (размеры, типы корпусов и т.д.), так и применительно к особенностям современной элементной базы. Например, конструктивной совместимости по выводам микропроцессорных БИС, имеющих разные типы программной памяти.
Это позволяет производителю выпускать на первоначальном этапе довольно дорогие опытные изделия, например, с флэш-памятью, а затем перейти на выпуск дешевых изделий с масочной памятью. При таком переходе не потребуется производить никаких доработок. Параметр "конструктивное исполнение" может существенно влиять на стоимость изделия в зависимости от наличия технологического оборудования у изготовителя и объема производства. 5. Стоимость комплекта микросхем для альтернативного варианта, казалось бы, является безусловно, количественным параметром, однако это далеко не так. Стоимость претерпевает существенное изменение в зависимости от объема закупок микросхем, времени с начала их производства (стоимость вначале резко падает, потом может расти) и других экономических факторов. 6. Потребляемая мощность - это параметр, который можно отнести к количественным. Однако и здесь все далеко не так просто. Микросхема может иметь или не иметь режима пониженного энергопотребления, потребляемая мощность зависит от тактовой частоты и т.д. 7. Климатика и другие внешние факторы (температурный диапазон использования, влажность, радиационная стойкость и т.д.). 8. Надежность, в том числе структурная, встроенная аппаратная защита от несанкционированного копирования программ и другие особые условия применения. 9. Весо-габаритные характеристики ВМС. 10.Время проектирования и отладки аппаратных средств ВМС. 11.Стоимость проектирования и отладки аппаратных средств ВМС. Далее рассмотрим критерии программных составляющих, определяющие алгоритмические и системные параметры ВМС: 1. Наличие и возможность использования на заданной элементной базе ранее подготовленных фрагментов алгоритма управления. 2. Наличие библиотеки программ, для выбранной элементной базы и реализации заданного алгоритма управления и некоторых системных функций (системная надежность, защита от несанкционированного копирования и модификации управляющей программы и т.д.). В случаях проектирования сложных систем, работающих в режиме разделения времени и ресурсов, может потребоваться операционная система реального времени [54, 57]. 3. Степень избыточности по временным характеристикам и памяти при реализации фрагментов управляющего алгоритма. Этот критерий тесно связан с аналогичными критериями для аппаратных составляющих (см. выше). Однако при большой степени избыточности появляется возможность программирования на языках высокого уровня, что сокращает время и уменьшает стоимость разработки. 4. Степень сложности комплексирования с другими элементами структуры. Определяет трудности при отладке программы и ее модификации. 5. Время проектирования и отладки программных средств ВМС. 6. Стоимость проектирования и отладки программных средств ВМС. Стоимость и время проектирования ВМС в целом (включая комплексную отладку программно-аппаратных частей) тесно зависит также от внешних параметров. Выбор структуры ВМС зависит так же от множества внешних параметров, определяемых условиями проектирования и пожеланиями заказчика: 1. Наличие опыта применения выбираемой элементной базы. 2. Наличие инструментальной системы проектирования и отладки с необходимыми компиляторами. 3. Наличие достаточно полной технической документации.
Опыт использования выбираемых инструментальных средств. 4. Стоимость инструментальных средств. 5. Перспективность применения для последующих разработок выбираемой элементной базы и средств проектирования. Перечисленные параметры на этапе проектирования вариантов структур ВМС имеют как количественный, так и качественный (в основном) характер. Как было показано, что даже такой параметр как стоимость микросхем в условиях неопределенности, характерных для выбора структур ВМС, нельзя в полной мере отнести к количественному. Совершенно очевидно, что определять параметры, какой либо одной группы в отрыве от параметров другой группы невозможно. Это точно так же верно, как невозможно полностью отладить программные и аппаратные компоненты ВМС раздельно друг от друга.
Методика оценки сочетаний аппаратных и программных средств по качественным и количественным критериям
В случае достаточно большого числа критериев (большего 7±2), оценивание альтернатив по подмножествам критериев является наиболее приемлемым способом решения данной проблемы. Тогда при построении иерархии целей ЛПР должен придерживаться следующего правила: каждой цели любого уровня иерархии (кроме целей, являющихся листьями дерева целей) должно соответствовать не менее 2 и не более 7±2 целей предыдущего уровня иерархии. Критерии-заместители и прямые измерения предпочтения В рассмотренной нами выше модели ПР предполагалось, что критерии, которые эксперт сформировал для набора целей, носят объективный характер То есть, получены либо в результате измерений соответствующих свойств рассматриваемых альтернатив, либо вычислены с использованием известных функциональных зависимостей между характеристиками альтернатив и критериями. Однако, эксперт может оказаться в ситуации, когда получение объективных критериев либо невозможно, либо нецелесообразно Так. при оценке производительности процессоров используются результаты прогонки тестовых задач, по которым эксперт должен оценить возможности системы по решению требуемых ему задач Эксперт не имеет возможности в данном случае оценить производительность системы на требуемой ему нагрузке Адекватный подбор смеси тестовых воздействий (задач) для описания вычислительной нагрузки тоже является достаточно сложной задачей. В другом случае имеющиеся в распоряжении эксперта объективные критерии могут соответствовать таким характеристикам альтернатив, что делают эти критерии недейственными.
Так, для критерия «Производительность» можно использовать следующие паспортные характеристики: число тестовых щупов в эмуляторе, количество отображаемых каналов. Производительность при отладке зависит от этих характеристик, но не может быть определено ими полностью. Отсутствие объективных критериев у некоторых целей заставляет эксперта использовать другие способы измерения степени их достижения. К таким способам отнесем применение вместо объективных критериев [22]: критериев-заместителей; субъективных критериев. Воспользуемся определением, данным в [22]: «Критерий-заместитель - это такой критерий, который только косвенно характеризует степень достижения связанной с ним цели, но не является средством непосредственного измерения этой цели. Таким образом, критерии-заместители лишь косвенно измеряют достижение сформулированной цели. В сущности, все критерии являются «заместителями», так как ничто не поддается абсолютному измерению. Существуют только в той или иной степени приближенные способы прямого измерения цели». Применение критериев-заместителей означает, что эксперт использует в качестве исходных данных значения критериев-заместителей, а при принятии решений уже оперирует со значениями исходных (замещаемых) критериев, неформально их преобразуя на основании своего опыта и интуиции Набор критериев-заместителей может быть неединственным и. кроме того, критерии-заместители могут подходить в разной степени. Успех применения критерия-заместителя зависит от того, насколько хорошо эксперт представляет его связь с исходным критерием - насколько часто он использует этот критерий-заместитель при приеме решений. В случае субъективного критерия степень достижения цели определяется экспертом (субъектом). Субъективные критерии успешно используются при приеме решений. Так. каждой цели иерархии, кроме целей нижнего уровня, поставлен в соответствие субъективный критерий, шкалу которого эксперт формирует при формальном описании своих предпочтений. Принципиально возможны два различных подхода к построению шкалы субъективного критерия.
Суть первого подхода состоит в определении экспертом функциональной зависимости, связывающей некоторые объективные характеристики альтернатив со значениями на шкале субъективного критерия. Неизвестная функциональная зависимость между объективными характеристиками альтернатив и данным критерием определяется при проведении дополнительной экспертизы, целью которой является построение шкалы данного субъективного критерия. Предполагается, что эксперт в состоянии построить иерархию целей для решения этой задачи и сформировать набор объективных критериев (реальных характеристик альтернатив). Особое внимание следует уделить действенности набора и способности эксперта принимать решение при детализации субъективного критерия. Далее, эксперт определяет соответствие между изменениями значений характеристик альтернатив и изменениями на шкале субъективного критерия. Основное достоинство рассмотренного способа построения шкалы критерия состоит в том, что эксперту не требуется определять оценки по данному критерию для каждой рассматриваемой им альтернативы. Построенные в результате дополнительной экспертизы иерархия целей и набор объективных критериев способствуют пониманию сути оценок построенной экспертом шкалы субъективного критерия. Второй подход подразумевает непосредственное задание экспертом шкалы субъективного критерия: формирование множества шкальных значений и определение значений каждой альтернативы по данному критерию
Эксперт оперирует целостными образами при формировании шкалы критерия и определении значений альтернатив. В лучшем случае он может дать лишь словесное описание построенной шкалы. Как было уже отмечено в предыдущих главах, управляющий алгоритм реализуется в ВМС в основном программно, однако некоторые его фрагменты выполняются аппаратно. Это относится к тем фрагментам, на время выполнения которых наложены жесткие ограничения. Таким образом, структура ВМС может содержать процессорный элемент (или несколько элементов) и некоторые аппаратные блоки для реализации фрагментов с жесткими временными параметрами. У разработчика такой структуры имеется право выбора -применить высокопроизводительный, но дорогой процессор и реализовать управляющий алгоритм программно или использовать дешевый процессор относительно низкой производительности и аппаратные блоки для реализации критических по времени фрагментов алгоритма. Как было отмечено в работе ранее, желательно синтезировать несколько допустимых (в рамках ТЗ) структур ВМС с разными процессорами и дополнительными аппаратными блоками и затем выбрать по определенной методики лучшую из них. Таким образом предлагается подход к синтезу структуры ВМС в виде решения задачи интеграции аппаратных и программных средств, в основу которой положен алгоритм выбора оптимального (квазиоптимального) соответствия их параметров, ориентированный на реализацию с помощью автоматизированной системы поддержки принятия решений (СППР) в диалоговом режиме работы пользователя. Под аппаратными средствами ВМС будем понимать набор, состоящий из собственно микроконтроллера, внешней памяти, если таковая имеется, и периферийных специализированных устройств. Под программными средствами ВМС будем понимать некоторый набор программ (уже имеющийся у коллектива разработчиков или вновь разрабатываемый) с определенными параметрами.
Метод первой точки вне окрестностей и стратегия удвоения
Имеется три метода прямой фильтрации. Первый из методов называется методом первой точки вне окружностей. Это быстродействующий метод, дающий первую аппроксимацию. Второй - это метод ближайщей точки вне окрестностей. Третий метод - это метод наиболее удаленной точки вне окрестностей. Второй и третий методы являются более трудоемкими по объему вычислений, но дают при этом лучшие результаты. Во всех трех методах применяется отношение фильтрации, чтобы сравнивать взвешенные расстояния в Lp - метрике между точками, которые к настоящему моменту еще не « задержаны» фильтром, и точками, уже «задержанными». Отношение фильтрации задается в виде где t - верхний индекс для обозначения вектора, который еще незадержан фильтром; h - верхний индекс для задержанного фильтром вектора; d - параметр существенности расстояния.
Параметр существенности расстояния регулирует процесс прямой фильтрации следующим образом. Если расстояние между точками vl и v больше или равно d, то эти точки считаются существенно отличающимися. Если же v1 отстоит от vh меньше чем на d, то две точки считаются несущественно отличающимися.
Предположим, что при п векторов требуется построить рассеянное множество, состоящий из v точек, используя метод первой точки вне окрестностей. Процесс начинается с некоторого значения параметра существенности расстояния d. Затем все пвектора помещаются в список для чтения их фильтрующей процедурой. Вектор в начале списка называется начальной точкой прямой фильтрации. С этой точки начинает работать фильтр, и она является первой точкой, задержанной фильтром. Точки, задержанные фильтром в результате процедуры, и составляют рассеянное множество , вычисляемое с помощью фильтра.
Для определения второй точки, задержанной фильтром, по порядку обрабатываются остальные п-1 векторов. Так как начальная точка 86 единственная точка, пока задержанная фильтром, то каждый из векторов сравнивается с этой точкой с помощью отношения фильтрации. Предположим , что векторы с номером 2 и 3 несущественно отличаются от начальной точки с номером 1, а вектор с номером 4 - наоброт. Тогда останавливаемся на этом векторе, чтобы вектор 4 был задержан фильтром.
Далее мы возобновляем процесс с вектора 5. При этом следующий вектор, для того чтобы быть задержанным фильтром, должен существенно отличаться от обоих векторов - начальной точки вектора 4. Предположим, что векторы 5, 6, 7 и 8 не удовлетворяют этому условию , а вектор 9 - удовлетворяет. Тогда останавливаемся на нем , чтобы вектор 9 был задержан фильтром. Далее если продолжить процесс с вектора 10, то каждый следующий вектор будет задержан фильтром, если он существенно отличатся от каждого из векторов 1, 4 и 9. Процесс продолжается до конца обработки списка.
Предположим, что ни один из оставшихся векторов не удовлетворяет этому условию. Хотя обработка списка закончена, заметим, цель - оставить ровно v векторов из п - не достигнута. Причина того, что процесс окончен на меньшем, чем v количестве точек, заключается в слишком большом значении параметра d. Заметим, что при большом d существенное отличие векторов встречается реже, чем при малом. Следовательно, нужно уменьшить d в надежде на то, что число векторов, задерживаемых фильтром, возрастет.
К сожалению, для определения подходящего d нет другого пути, кроме экспериментального. Предположим, что проводимая дальше фильтрация с некоторым d показывает, что сокращенный список (после фильтрации) слишком длинен. Тогда d нужно увеличить и фильтровать векторы снова. Предположим, что новый сокращенный список оказывается слишком коротким. Тогда d надо вновь увеличить и отфильтровать векторы еще раз. Возможно, что этот процесс придется проводить многократно с различными значениями d пока не будет получено сокращенное множество требуемого объема.
Выполняя прямую фильтрацию, мы руководствуемся правилом: 1) сокращенное множество слишком мало : уменьшаем d; 2) сокращенное множество слишком велико : увеличиваем d. Заметим, что значение параметра d, который порождает сокращенное множество определенной размерности, выбирается из некоторого интервала. Для дискретного изменения параметра d так, чтобы процесс многократных запусков процедуры прямой фильтрации сходился к множеству желаемого числа точек, мы используем деление пополам и удвоение. Алгоритм прямой фильтрации с удвоением и делением пополам, используемый мною в разработанной системе СППР, приведен ниже.
