Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.))

Силаева Т,А. Методы решения задач оптимального проектирования вычислительных систем", Учебное пособие к лабораторным работам. — М,: Изд-во МАИ, 2000, — 92 сл ил. Лабораторные работы, выполняемые в дисплейном классе, позволяют студентам изучить и практически овладеть методами решения задач оптимального проектвровавия, в том числе методами решения задач безусловной оптимизации, условной оптимизации н линейного программирования.

Предназначены для студентов специальностей «Вычислительные машины, комплексы, системы и сети» в «Программное Обеспечение вычислительная техники и автоматизированных систем», а также могут быть полезны аспирантам, научным сотрудникам и внженерам, спецяалнзирующимся в области вычислительной техники. Рецензенты: В.И. Попов, В.Ю. Рутковский, В.М. Суханов 15В5> 5-7035-2374-5 Е> Москозскяй зявацяовный настятут, 2000 Работа 1. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ Цель работы: изучить и практически овладеть основными методамн решения задач безусловной оптимизации. ОБЩИЕ СВЕДЕНИЯ Постановка задачи оптимального проектирования ЭВМ, систем н сетей Задача оптимального проектировании на любом иерархическом уровне заключается в определении оптимальной структуры проектируемого объекта на этом уровне и/илн его оптимальных параметров.

Под оптимальным будем понимать такой вариант структуры я/иля параметров объекта, при котором критервй оптимальности, описывающий качество илн эффективность объекта, принимает оптимальное (ванлучп>ее) значение, а управляемые параметры удовлетворяют ограничениям, описывающим требования технического задания (ТЗ) на проектирование объекта. Критерий оптимальности называют также целевой функцией, а оптимальное значение функции — экстремумом (им может быть минимум вли максимум). Пример задачи оптимального проектирования: определение структуры ЭВМ максимальной производительности при заданных массогабаритных ограничениях, надежности н потребляеМой МОЩНОСТИ. В формализованном виде задача оптимального проектирования записывается следующим образом: ехзг /(Х); (1.1) Хе Хл> ХП = ( Х ! ф (Х ) = 0; Ч (Х) < 0 1, (1. 2) Задача (1.1) — (1.2) нахожденяя экстремума /(Х) состоит е определения оптимального значения Х (илн значений, если нх несколько) вектора Х = ( а >, ..., х „) управляемых параметров, прн 3 котором скалярная целевая функция !"(Х) принимает оптимальное значение (или значения) прк условии, что Х принадлежит обла- сти допустимых значений Х)), задаваемой ограничениями (1.2) тяпа неравенств Ч'(Х) < О и/нлн равенств Ф(Х) = О.

Данные ог- раничения записаны в векторной форме н их можно переписать з скалярной форме, например, вместо Ф(Х) = О будет ср (х!,...,х„)= О (!= 1,т, я!< и). В общей постановке задача оптимального проектирования представляет собой задачу математического программирования. Из постановки задачи оптимального проектирования следует, что для ее формулировки и решения вначале необходимо: 1) выделить некоторую совокупность управляемых парамет- р о в ориентирования — вектор независимых переменных Х= ~ з !, ..., х ~, фиксация значений которых определяет один з нз вариантов структуры объекта, его параметры и количественные характеристики, в том числе значения целевой функции я функ- ций ограннченкй; 2) сформировать скалярную целевую функцию )'(Х); 3) из ТЗ сформировать функции ограничений х (Х) и Ф(Х), если таковые имеются.

Существуют следующие способы построения целевой функции: 1. Если имеется один частный критерий эффективности нля качества проектируемого объекта, то его и принимаем за целевую функцию 1'(Х) . 2. Если существует набор частных критериев эффективности У! (Х) Уз(Х) .—,,г,(Х), то возникает многокритериальная зада- ча. Она сводится к однокрнтериальной путем формирования обоб- щенного критерия оптимальности, который и используем в каче- стве целевой функции: У(Х) = ф! (Х),Гз (Х), ...,У, (Х) ), Обобщенный критерий формируется одним из следующих спо- собов: 2.1.

Из частных критериев выделяем наиболее важный (" (Х), а остальные не рассматриваем, тогда г(Х) = ! (Х) . 2.2. Как аддитивный (в виде суммы) критерий ('(Х) .= ~ч, !х ь )'а (Х), где аз — весовые коэффициенты, и они могут быть как больше нуля, если !(Х) увеличивается при росте Уь(Х), так н меньше нуля в противном случае. 2.3. Как мультипликативный (в виде произведения) критерий У(Х) = П У„'з(Х) . =1 2.4. Как мияимаксный критерий ш!в ~ шах Уь(Х) ~, т,е.

хек з У(Х)= шах Уь(Х). 2.5. В виде максиминного критерия шах ~ шш У„(Х) ~, т.е. хе хп ь г (Х ) = пйп г", (Х ) . ь В общей постановке задача (1.1) — (1.2) оптимального проектирования представляет собой задачу математического врограммировання.

Существуют следующие виды данной задачи: 1, Если отсутствуют ограничения на значения управляемых параметров, то имеем задачу безусловной оптимизации (илн задачу на безусловнын экстремум). 2. Если ограничения существуют, то это задача условнои оптимизации. 3. Если у(Х) и все функции ограничений линейны, то имеем задачу линейного программирования. 4, Если хотя бы одна функция среди ('(Х) н функций ограничений (1,2) нелинейна, то приходим к задаче нелинейного программирования.

5. Если некоторые ияи все управляемые параметры могут принимать лишь определенные дискретные значения, то имеем задачу дискретного программирования. 6. Если управляемые параметры могут принимать только целочисленные значения, то приходим к задаче целочисленного программирования. Экотремум может быть глобальным и локальным, и соответственно имеем задачи нахождения глобального или локального экстремума.

Глобальным минимумом функции ((Х) на множестве Х1)~ Е (Е" — и-мерное эвклидово пространство) называется та- кая точка Х*я ХР, для которой при любом Хн ХР выполняется ~ (Х" ) > г(Х) . Для глобального максимума выполняется у (Х" ) < у'(Х) . Точке в Е" соответствует п-мерный вектор. Точка Х я ХР называется локальным минимумом функции /(Х) на множестве ХРш Е", еслв существует е> О, при котором для всех Хя ХР, и таких, что ~ Х- Х ~ < е (т.е, для Х из еокрестности точки Х ), справедливо ~ (Х*) ь у(Х) . Для локального максимума.' )" (Х ) > У(Х). Локальных минимумов и максимумов может быть несколько, а глобальный — только один.

Задача нахождения шах т' (Х) сводится к нахождению х ппп(- у(Х) ), т.е, достаточно изучить методы решения задачи по- Х иска минимума. Типовые задачи оптимального проектирования ЭВМ, сястем, сетей в БИС Перечислвм несколько групп типовых задач оптимального проектирования: Многие задачи выбора состава оборудования в вычислительных системах и сетях сводятся к задачам дискретного и целочислеяного программирования: ехьг ) (Х), Хе Хтз ХР= (Х! У(Х)~ У, Х Р1, где х= (х1, ...,х ), У= (У1, ...,У ), Уг= (Угт, ...,У~ ). Вектор Х управляемых параметров определен на дискретном множестве .0 или на множестве целых чисел.

Значение Х может характеризовать количество элементов каждого типа в системе или сети, указывать на наличие илн отсутствие каждого элемента и соединения е структуре системы илк сети. В качестве целевой функции /(Х), а также каждой из функций ограничений у.(Х) ~'= 1, т) может выступать одна из выходных характеристик системы или сети, например среднее время решения задачи в системе, вероятность отказа в решение, производительность системы, надежность свстемы илв сети, коэффициент загрузки оборудова- ння, пропускная способность сети передачи данных, Требуемые значения Уг задаются в ТЗ.

Кроме того, при необходимости У(Х) может быть сформирована как функция нескольквх выходных характеристик системы, не нспользуемых в У(Х), в соответствии с уже рассмотренными способами нахожденяя обобщенного критерия оптимальности. Примеры задач первой группы: 1.1. Задача выбора количества х,.

(т'= 1, л ) устройств каждого типа (процессоров, модулей памяти, устройств ввода-вывода и т.д.) в вычислительной системе. При этом х, я 1 О, 1, 2, ..., и,), где и, — максимально возможное число устройств т-го типа в системе. 1.2. Задача выбора каналов связи х„между пунктами г н ~ з сети передачи данных, где х„я ) О, 1) в О будет означать отсутствие в структуре сети соответствующего устройства или соединения, а 1 — наличие. Задачи 1.1 и 1.2 сводятся к задачам целочисленного линейного программирования, если в качестве у(Х) и у (Х) выбираются аддитивные функции числа устройств (стовмость, производительность, энергопотребление, габариты, масса).

Если исходная функция мультипликативная, то ее можно свести к аддитивной путем логарифмирования. 2. Задачи оптимнзации вычислительной системы, рассматриваемой как система массового обслужвваявя. Часть этвх задач формулируются в виде задач нелинейного программирования, другие сводятся к задачам дискретного и частично-дискретного программирования, Примером задачи атой группы служат синтез структуры памяти специализврованной ЭВМ.