Воронов Е. М. Методы оптимизации управления ММС на основе стабильно-эффективных игровых решений (2001) (1264203), страница 73
Текст из файла (страница 73)
В работе [54] детально описаны процедуры в рамках каждого блока и их связи.Глава 9. Программно-технические системы3971⇐Ввод данных о цели и параметрах динамики ЛАr, r, ϕ , χ , ε1 , ε 2H ,V1 , α, β, γ, υ, ψt ∈ t ϕ −1 ; T 2Предварительная обработка информации3Прогноз времени до встречи ЛА с цельюДействияна такте4Ф ормирование области достижимости цели,множества потребных управлений перехватчикоми оптимизация5Ограничение и коррекциявектора управления6Вычисление и выдача команд рулевым приводам⇒ n, γ ( υυδв , δэ )Переход к новому тактуt ∈ [t ,T ]Рис. 9.9.
Схема программного такта субоптимального ПКЗУ9.3.3.Транспьютерная реализация алгоритмаПарето–Шепли-оптимизации (СТЭК-6)Анализ, проведенный в пунктах 9.3.3, 9.3.4, носит качественный характер. В основном он связан с оценкой работоспособности параллельных алгоритмов. Но, в то же время, полученные параллельные реализации на малых транспьютерных сетях имеют и определенную практическую ценность. Разработанные параллельные алгоритмы могут быть значительноускорены в нейросетях и нейрокомпьютерах.Результаты временных замеров работы двухэтапного алгоритмапараметрической оптимизации управления ММС на основе вектораШепли.
Базовым вариантом для анализа является пример главы 5.398 Элементы проектирования и реализации управления ММС. Часть IIIНачальные условия задачи:1) P 31 = 0,8; P 32 = 0,8; P 13 = 0,8; P 14 = 0,8; P ij − эффективность воздействия одного объекта i-го вида одной системы на один объект j-го типадругой системы, 0 ≤ Pij ≤ 1 ;2) α 11 = 0,7; α 12 = 0,3; α 21 = 0,3; α 22 = 0,7; α ij – весовые коэффициенты,определяющие целевой приоритет каждой стороны в поражении активных или пассивных средств противоположной стороны. 0 ≤ α ij ≤ 1; α i1+ + α i2 =1; i = {1,2}, j = {1,2};3) x 1 = 10; x 2 = 10; x 3 = 10, x 4 = 10, x i – начальное количество объектов iго типа, x i ≥ 0, i = {1, 2, 3, 4};4) квадратичный критерийJ A = α11 ⋅ x32 ( T ) − x12 ( T ) + α12 ⋅ x42 ( T ) − x22 ( T ) → min, J з = α21 ⋅ x12 ( T ) − x32 ( T ) + α22 ⋅ x22 ( T ) − x42 ( T ) → min.
Оценка времени работы данного алгоритма производилась на маломощном вычислителе, поэтому имеет характер гарантированных оценок«сверху», но сравнительные временные замеры этапов алгоритма даютточный результат.Рис. 9.10. Зависимость времени работы двухэтапного алгоритма от количества точекКак видно из табл. 9.3. и рис. 9.10, с увеличением количества сетевыхточек время работы двухэтапного алгоритма параметрической оптимизации управления ММС на основе вектора дележа Шепли растет. Причем90–99% времени приходится на алгоритм Парето-оптимизации (ЛП-поиск,вычисление показателей и Парето-оптимизация). Этот факт объясняетсяциклической структурой, содержащей вложенные циклы алгоритма Парето-оптимизации.
Следовательно, необходима разработка параллельногоалгоритма Парето-оптимизации.Следует отметить, что эффективное параллельное ускорение Паретооптимизации может быть дополнено ускорением Нэш-оптимизации, кото-Глава 9. Программно-технические системы399рое применяется при вычислении точки Шепли и обладает геометрическим параллелизмом (см. п.
2.4.3).Параллельный алгоритм Парето-оптимизации. Для разработки параллельного варианта алгоритма Парето-оптимизации использован тотфакт, что для получения очередной точки ЛП-последовательности необходимо знать только ее номер. Это говорит о том, что вычисление следующей точки ЛП-последовательности не зависит от предыдущей. Следовательно, мы можем распределить задачу ЛП-поиска N точек последовательности между р транспьютерами, назначив для вычисления каждому транспьютеру р/N точек.Количество точекТа блица 9 .3Вре ме нные з ам ер ы д в ухэ та пно го алгор итм а1-й этап алгоритмаЛП-поиски вычислениепоказателейТ, сР, %ПаретооптимизацияВычислениеточки ШеплиТ, сТ, сР, %Общеевремяработыалгоритма2-й этапалгоритмаР, %Минимизация отклоненияот точкиШеплиР,Т, с%Множество ПаретоР,%N1000,6174,390,1113,410,056,1 0,056,1660,822001,4374,870,3819,930,052,6 0,052,6841,914003,6271,111,3726,930,050,98 0,05 0,9811 2,755,095004,7367,862,1430,70,050,72 0,05 0,72132,66,97100011,0455,398,7944,110,050,25 0,05 0,2520219,93Здесь Т – время работы, с; Р – процент общего времени; N – количествоточек.Далее необходимо получить значения показателей в этих точках.
Этотэтап проводится также параллельно на каждом транспьютере, посколькукаждой точке ЛП-последовательности однозначно соответствуют значенияпоказателей. Теперь необходимо проанализировать полученное пространство показателей с целью получения Парето-границы.Сначала проведем оптимизацию полученного локального пространствапоказателей на каждом транспьютере в параллельном режиме. Оптимизация будет иметь смысл отсева заведомо худших вариантов. Затем, переслав полученные локальные Парето-множества со всех транспьютеров сети на Host-транспьютер, осуществим окончательную Парето-оптимизациюполученного множества.400 Элементы проектирования и реализации управления ММС. Часть IIIточки11TRAMI1II1I2II2III1N/p(N/p)+12TRAMIII2IV2N/p1+(p – 1)/pNpTRAMIpIIIpIIpNРис.
9.11. Блок-схема параллельного алгоритма Парето-оптимизацииЭтапы параллельного алгоритма Парето-оптимизации на рис. 9.11:1 − распределение задачи по транспьютерам; параллельные ЛП-поиски;параллельные вычисления показателей;2 − параллельные Парето-оптимизации; получение локальных Паретограниц;3 − пересылка полученных локальных Парето-границ на Hostтранспьютер;4 − окончательная Парето-оптимизация локальных Парето-границ; получение полной Парето-границы.Возможные конфигурации транспьютерной сети. Рассмотрим несколько видов конфигураций транспьютерной сети, исходя из имеющейсятранспьютерной сети, состоящей из пяти транспьютеров (имеется в видутранспьютерная сеть кафедры ИУ-1 МГТУ им. Н.Э.
Баумана).fs30tsHostserverT01Т212321T103321T20212T30КонтроллерРис. 9.12. Конфигурация 5PIPE (конвейерная)31 2T40Глава 9. Программно-технические системыfs30tsHostserverT01Т212321T10401321T2033212T301T402КонтроллерРис. 9.13. Конфигурация 5TREE (древовидная)Исходя из анализа возможных конфигураций транспьютерной сети,можно заранее оценить, при какой из конфигураций время работы параллельного алгоритма Парето-оптимизации будет наименьшим.На рис. 9.12 и 9.13 даны конфигурации 5PIPE и 5TREE.Та блица 9 .4Сра в н ит ел ьна я э ффе ктив но ст ь кон ф и гур а ц ийУменьшениевремениработыалгоритма1TRAM (1 транспьютер)3PIPE (Host-транспьютер + 2 транспьютера;конвейерная передача данных)3TREE (Host-транспьютер +2 транспьютера;древовидная передача данных)5TREE (Промежуточный транспьютер + Hostтранспьютер + 3 транспьютера; древовиднаяпередача данных)5PIPE (Host-транспьютер + 4 транспьютера;конвейерная передача данных)Описание конфигурации транспьютерной сети 5PIPE.
Описание состоит из следующих компонентов: описание процедур WORK4, WORK3,WORK2, WORK1; описание процедуры WORK0; описание констант;определение отображения каналов на линии связи.Процедура WORK4 выполняется транспьютером Т 4 :3NЛП-поиск: (точки (+ 1, , N )); вычисление показателей; Парето4оптимизация, получение локальной Парето-границы; пересылка полученной локальной Парето-границы транспьютеру Т 3 ;402 Элементы проектирования и реализации управления ММС.
Часть IIIПроцедура WORK1 выполняется транспьютером Т 1 : ЛП-поиск (точкиN( 1 , , )); вычисление показателей; Парето-оптимизация, получение ло4кальной Парето-границы; прием локальных Парето-границ от транспьютеров Т 2 , Т 3 , Т 4 ; пересылка локальных Парето-границ транспьютеров Т 1 , Т 2 ,Т 3 , Т 4 транспьютеру Т 0 ;Процедура WORK0 выполняется транспьютером Т 0 : прием локальныхПарето-границ транспьютеров Т 1 , Т 2 , Т 3 , Т 4 ; окончательная оптимизациялокальных Парето-границ; получение полной Парето-границы; пересылкаданных на Host-сервер; запись результатов в файл.Константы, используемые транспьютерами Т 0 , Т 1 , Т 2 , Т 3 , Т 4 для выполнения процедур WORK0, WORK1, WORK2, WORK3, WORK4, записаны в файле lab.inc.
При отображении каналов на линии связи, для описания конфигурации необходимо определить каналы, соединяющие все процессы друг с другом; программное описание конфигурации представлено вфайле main.pmg.Тексты процедур WORK0, WORK1, WORK2, WORK3, WORK4, текстыфайлов lab.inc и main.pmg представлены в [54]. В [54] также приведенытексты файлов lab.inc, main.pmg, WORK0 для конфигурации транспьютерной сети 1TRAM (программа 1TRAM).Таким образом, параллельный алгоритм реализован на транспьютернойсети, состоящей из пяти транспьютеров. Реализация алгоритма выполнялась на алгоритмическом языке параллельного программированияОССАМ.Параллельная программа, написанная на языке ОССАМ, представляетсобой совокупность отдельных процессов, которые выполняются параллельно и взаимодействуют между собой. В результате взаимодействияпроцессов решаются две задачи: 1 – синхронизация процессов, 2 – обменинформацией.Процессы синхронизируются путем передачи сообщений друг другу.Конфликты при обращении исключаются благодаря тому, что в любоймомент времени каждый процесс может взаимодействовать только с одним другим процессом.Результаты временных замеров работы параллельного алгоритмаПарето-оптимизации.
Исследования времени выполнения параллельногоалгоритма Парето-оптимизации проводились с транспьютерной сетью изпяти транспьютеров Т800. Транспьютеры Т800 эквивалентны IBM AT-386.Исследовался базовый вариант примера главы 5, описание которого дано вначале пункта 9.3.3. Результаты сведены в табл. 9.5.Глава 9. Программно-технические системы403Та блица 9 .5Вре ме н н ые з ам ер ы д ля ко нфигур ац и й 1T RAM, 5PIP EВремя работыВремя работыпрограммы.программы.Конфигурация 1TRAM, с Конфигурация 5PIPE, с1,4440,3843,8771,10310,2492,91813,7483,71535,8899,08094,17621,894253,05053,584Кол-воточек100200400500100020004000Множество Парето451216222841Оценка временных характеристик производилась исходя из того, чтоB− A1 секунда равна 64 «тикам» процессора транспьютера. Отсюда t =,15625где B − конечный тик, A − начальный тик.Из табл.
9.5 следует, что с увеличением количества точек время работыпрограммы резко возрастает. Этот факт объясняется наличием циклической структуры алгоритма, содержащего вложенные циклы.По результатам таблицы временных замеров видно, что, увеличиваяколичество транспьютеров от одного (конфигурация 1TRAM) до пяти(конфигурация 5PIPE), время работы программы значительно уменьшается, причем с увеличением количества точек ускорение растет (см. табл.
9.6,рис. 9.14, рис. 9.15).Увеличение времени работы программы в конфигурации 1TRAM посравнению с последовательным (см. табл. 9.3) связано со свойствами конфигурации (1TRAM), которая является менее быстродействующей для последовательного вычисления.T, c1001TRAM505PIPE1002004008001000Количество точекРис. 9.14. Зависимость времени работы программы от количества точекдля конфигураций 1TRAM и 5PIPE404 Элементы проектирования и реализации управления ММС.
Часть IIIS5432120004008001000Количество точекРис. 9.15. Зависимость ускорения времени работы программы конфигурации 5PIPEпо сравнению с конфигурацией 1TRAM от количества точекТа блица 9 .6Ус кор ен и я вр ем е ни в ыпо л не ния про гр амм ы ко н фи гур а ци е й5P IPE по сра в не нию с к онф и гур а цие й 1T RA MКоличество точекУскорение S = (T1TRAM ,c) (T5 PIPE ,c)1003,7602003,5144003,5125003,70010003,95220004,30040004,722Сравнение временных характеристик в зависимости от количества точек и конфигурации транспьютерной сети дано в табл. 9.7 и на рис. 9.16.Та блица 9 .7Сра в н ит ел ьны й а на л из врем е нных х ар ак тер и ст и кЧисло точек1TRAM3PIPE3TREE5TREE5PIPE100035,88914,89214,01511,9479,080200094,17639,22336,91330,36821,894Глава 9. Программно-технические системы405T, c100502000 точек1000 точек100135КоличествотранспьютеровРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
