Содержание к диссертации
Введение
ГЛАВА 1 Модели оценки эффективности многопроцессорных систем обработки информации и управления 11
1.1 Модель оценки производительности МСОИУ 11
1.2 Модель расчета оценки надежности МСОИУ 25
1.3 Методы решения СЛАУ 32
1.4 Сравнительный анализ методов решения СЛАУ 38
Выводы 47
ГЛАВА 2 Постановка задачи и алгоритмы выбора эффективной конфигурации МСОИУ 49
2.1 Постановка задачи выбора эффективной конфигурации МСОИУ 49
2.2 Стандартный генетический алгоритм 57
2.3 Алгоритмы многокритериальной оптимизации 65
2.4 Разработка модифицированного генетического алгоритма для решения задачи выбора эффективной конфигурации МСОИУ 76
2.5 Настройка параметров генетического алгоритма 83
2.6 Метод случайного поиска для решения задачи глобальной оптимизации 86
Выводы 89
ГЛАВА 3 Практическая реализация моделей и алгоритмов 91
3.1 Система поддержки принятия решений для выбора эффективной конфигурации МСОИУ 91
3.2 Проверка работоспособности СППР на задаче выбора эффективного быстродействия процессоров МСОИУ ПС-2000 96
3.3 Проверка работоспособности СППР на задаче выбора эффективного быстродействия процессоров МВК «Эльбрус-2» 108
Выводы 111
Заключение 112
Список литературы 113
- Модель оценки производительности МСОИУ
- Постановка задачи выбора эффективной конфигурации МСОИУ
- Разработка модифицированного генетического алгоритма для решения задачи выбора эффективной конфигурации МСОИУ
- Система поддержки принятия решений для выбора эффективной конфигурации МСОИУ
Введение к работе
Актуальность темы.
За последние десятилетия рост производительности компьютеров, объемов их оперативной и внешней памятей, пропускной способности внешних устройств и каналов связи качественно изменил ситуацию в области систем обработки информации и сферах их применения. Несмотря на это, существует немало задач обработки информации, решение которых невозможно получить стандартными средствами за приемлемое время или обеспечить управление сложным объектом в режиме реального времени. Один из путей повышения производительности систем обработки информации состоит в переходе от однопроцессорных к многопроцессорным системам, в распараллеливании процессов вычислений и обработки информации, как на уровне процессоров многопроцессорных систем, так и на уровне выполнения элементарных операций внутри процессоров. Этот путь является наиболее перспективным и не содержит принципиальных ограничений в повышении скорости и точности работы систем обработки информации.
На базе многопроцессорных систем обработки информации и управления (МСОИУ) реализуются системы управления для многих отраслей: космической отрасли, авиации, для систем противовоздушной и противоракетной обороны и многих других. Однако производство МСОИУ затруднено высокой стоимостью работ на всех его стадиях. В результате общая стоимость системы часто делает ее недоступным инструментом. Использование современных оптимизационных методов и алгоритмов на этапе разработки МСОИУ позволило бы снизить затраты на ее производство и при этом система соответствовала бы предъявляемым к ней требованиям. В связи с этим разработка методов автоматизированного выбора оптимальной конфигурации МСОИУ является актуальной научной задачей.
Целью работы является повышение обоснованности принятия решений при формировании эффективной конфигурации многопроцессорных систем обработки информации и управления.
Поставленная цель определила следующие основные задачи исследования:
Провести анализ существующих математических моделей функционирования многопроцессорных систем и возможных подходов к их созданию.
Программно реализовать и провести сравнительный анализ способов получения оценок качества работы и стоимости многопроцессорных систем.
Разработать процедуру одновременного выбора как оптимальной структуры многопроцессорных систем, так и эффективного быстродействия специализированных процессоров.
Разработать и программно реализовать алгоритм, позволяющий осуществлять поиск решения в большом поисковом пространстве.
Разработать и программно реализовать алгоритм решения задачи многокритериальной оптимизации многопроцессорных систем по критериям производительности и стоимости.
Разработать, программно реализовать и оценить эффективность процедуры совместного использования предложенных алгоритмов для автоматического генерирования и оптимизации конфигураций многопроцессорных систем обработки информации и управления.
Разработать и апробировать систему поддержки принятия решений при формировании конфигурации многопроцессорных систем.
Методы исследования. Для решения поставленных задач использовались методы системного анализа, линейной алгебры, исследования операций, теории массового обслуживания, теории вероятности, математической статистики, дискретной оптимизации и эволюционных алгоритмов.
Научная новизна диссертационной работы состоит в следующем:
1. Предложена и реализована новая модель оценки быстродействия
многопроцессорной системы обработки информации, требующая зна
чительно меньшего количества вычислений и отличающаяся от из
вестных возможностью определения эффективного быстродействия
специализированных процессоров.
Предложен новый генетический алгоритм, отличающийся от известных способом генерирования решений и позволяющий находить оптимальные решения на дискретных структурах переменной размерности.
Предложен модифицированный генетический алгоритм многокритериальной оптимизации, эффективно сочетающий положительные стороны известных методов многокритериальной эволюционной оптимизации и позволяющий генерировать репрезентативную аппроксимацию множества Парето.
Практическая значимость. На основе предложенных моделей и алгоритмов разработаны современные программные системы, которые позволяют широкому кругу специалистов проектировать эффективную многопроцессорную вычислительную систему произвольной конфигурации для решения задач управления и обработки информации в режиме реального времени, а так же других сложных задач, к которым предъявляются соответствующие требования по надежности и производительности. Система поддержки принятия решений для выбора эффективной конфигурации многопроцессорных вычислительных систем зарегистрирована в отраслевом фонде алгоритмов и программ (№ ЕСПД .03524577.01437-01 99 01). Материалы исследования и разработанные программные системы были использованы при оценке существующих и разработке перспективных средств вычислительной техники в ФГУП ЦКБ «Геофизика» (г. Красноярск). Результаты проведенного анализа были включены в комплекс предложений по совершенствованию средств вычислительной техники для обработки геофизической информации с измерительных устройств в режиме реального времени.
Основные защищаемые положения:
Предложенная модель оценки быстродействия МСОИУ совместно с алгоритмом прямого вычисления производительности представляет собой эффективную процедуру оценки производительности многопроцессорных систем обработки информации и управления, требующую меньшего количества вычислений и обеспечивающую достаточную точность получаемых решений.
Генетический алгоритм с переменной длиной хромосом способен находить эффективные варианты МСОИУ произвольной конфигурации с оптимальным быстродействием спецпроцессоров, значительно сокращая при этом объем вычислений.
Модифицированный генетический алгоритм многокритериальной оптимизации позволяет генерировать эффективные конфигурации МСОИУ по критерию производительность/стоимость.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: X юбилейная Международная научно-практическая конференция «Современные техника и технологии», Томск, 2004; Международная научно-практическая конференция «Актуальные проблемы информатики и информационных технологий», Тамбов, 2004; VIII Всероссийская научная конференция с международным участием «Решетневские чтения», Красноярск 2004; 1-й Международный форум (6-я Международная конференция) «Актуальные проблемы современной науки», Самара, 2005; VIII Всероссийская конференция с участием иностранных ученых "Современные методы математического моделирования природных и антропогенных катастроф", Кемерово, 2005; IX Международная научная конференция посвященная 45-летию Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева, Красноярск, 2005; VI Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), Кемерово, 2005; Международная школа-конференция по приоритетным направлениям развития науки и техники, Москва, 2006.
Публикации. По результатам диссертационной работы опубликовано 13 печатных научных работ, среди которых 5 статей. Список публикаций приведен в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка использованных источников.
Модель оценки производительности МСОИУ
В этом параграфе рассматривается разработка метода оценки производительности МСОИУ, состоящей из произвольного количества типов процессоров, произвольного числа процессоров каждого типа и многошинной организацией связи процессоров с общей оперативной памятью.
Процесс функционирования МСОИУ рассматривается как последовательная смена состояний в некотором интервале времени At. Этот процесс может быть описан с помощью аппарата теории массового обслуживания.
Рассмотрим МСОИУ, состоящую из N различных типов процессоров по mi (i=l,N) процессоров каждого типа и общей оперативной памяти. Объединение процессоров с общей оперативной памятью по данным осуществляется посредством п шин (рисунок 1).
При разработке математической модели функционирования для суммарного потока запросов на обслуживание, поступающего в случайные моменты времени от процессоров і-го типа в оперативную память, предполагается, что интервал времени между двумя любыми смежными заявками подчиняется пуассоновскому закону распределению с параметром Vj. Причем, параметр Vj уменьшается с увеличением числа запросов, ожидающих обслуживания в оперативной памяти, вследствие замкнутости системы [75, 84].
Кроме того, при оценке производительности МСОИУ наиболее часто полагают, что интервал времени между двумя смежными обслуживаниями подчиняется экспоненциальному закону распределения с параметром щ [30, 31].
Представим процесс функционирования МСОИУ замкнутой системой массового обслуживания (СМО) с ожиданием и случайным распределением запросов всех типов по всем шинам без взаимодействия между собой [56, 58].
Пусть имеется N типов процессоров, причем количество процессоров каждого типа произвольное (mh Ш2, ..., т ). Каждый процессор в некоторые случайные моменты времени нуждается в обслуживании. Обслуживание осуществляется в памяти посредством п шин. Поток запросов от процессоров каждого типа — пуассоновский с параметром Vj, где i = \,N. Интенсивность обслуживания каждого запроса в оперативной памяти подчиняется экспоненциальному закону распределения с параметром о.,-. Вновь поступивший на обслуживание запрос направляется с равной вероятностью в любую из свободных шин и принимается на обслуживание. Если все шины заняты, то поступивший на обслуживание запрос становится в очередь и ждет своего обслуживания. Дисциплина обслуживания - случайный равновероятный выбор из очереди.
Постановка задачи выбора эффективной конфигурации МСОИУ
Построенный комплекс моделей позволяет перейти к формализации задач выбора эффективных конфигураций разнородных МСОИУ. Выполним такую формализацию. Нетрудно видеть, что формализация задач выбора эффективных вариантов МСОИУ должна привести к оптимизационным постановкам. При этом очевидны, как минимум, три группы критериев [15]: - критерии производительности, которые должны быть максимизированы, - критерии надежности, которые должны быть максимизированы (коэффициенты готовности, время наработки на отказ, живучесть и т.п.) или минимизированы (вероятности отказов, время пребывания в неработоспособном состоянии), - критерии стоимости, которые должны быть минимизированы (стоимость системы, стоимость разработки системы, стоимость эксплуатации, стоимость ремонта и т.д.).
При этом на переменные задачи будут наложены ограничения, например, по энергопотреблению, скорости и т.д. Становится очевидным, что речь идет о многокритериальной задаче условной оптимизации. Таким образом, проблема выбора эффективного варианта МСОИУ формализуется в виде многокритериальной задачи оптимизации с тремя противоречивыми группами критериями. При выделении ведущего критерия в каждой из групп получим задачу с тремя критериями и группой ограничений, в которые превратятся остальные критерии каждой из групп. Поэтому необходимо выполнить анализ степени противоречивости критериев.
Первое, что необходимо отметить, это - согласованность критериев внутри каждой из трех групп. Так суммарное количество операций в секунду многопроцессорного комплекса будет возрастать с ростом числа непростаи-вающих процессоров и наоборот. Аналогичная картина наблюдается и в группе критериев надежности - чем ниже (т.е. лучше) вероятность отказа, тем больше (т.е. лучше) время наработки на отказ. Различные стоимостные показатели также будут практически одновременно возрастать с ростом сложности системы. Из этого следует, что множественность критериев в каждой из групп может быть преодолена достаточно простым способом - достаточно выделить один (ведущий) критерий в группе, а остальные перевести в ограничения. Недостатки метода ведущего критерия, свойственные многокритериальным задачам, в данном случае не существенны, т.к. внутри группы критерии согласованы. Совсем отказаться от других критериев группы (исключая ведущий) все же нельзя, т.к. возможны случаи, когда при значительном улучшении ведущего критерия, остальные могут принять недопустимые значения. Так, например, в исключительном случае при значительном снижении стоимости разработки системы может возрасти стоимость ремонта и эксплуатации, а это значит, что надо все-таки предусмотреть предельно допустимые значения, т.е. ввести ограничения.
Второе, что следует отметить, это противоречие стоимостных критериев по отношению к критериям производительности и надежности, т.к. увеличение (т.е. улучшение) последних обычно достигается увеличением числа процессоров и шин, а значит - приводит к увеличению (т.е. ухудшению) первых.
Отношения критериев производительности и надежности не так очевидны. Расчеты по аналитическим и имитационным моделям, проведенные в [22], показали, что производительность растет нелинейно с ростом числа процессоров - сначала возрастает, а затем перестает расти. В тот момент, ко гда производительность перестает расти с ростом числа процессоров, данный критерий вступает в противоречие с критериями надежности, которые, естественно, в этом случае продолжают расти. Однако, такая ситуация возможна только в случае чрезмерного насыщения МСОИУ процессорами какого-либо типа, что является неэффективным не только с позиции увеличения производительности, но и в первую очередь, с позиции уменьшения стоимости системы. Кроме того, "насыщение" производительности за счет увеличения числа процессоров обычно наступает уже при том количестве процессоров, когда показатели надежности достигают достаточно высокого уровня. Таким образом, критерии надежности и производительности оказываются вполне согласованными. Поэтому можно перевести критерий надежности в ограничения и проводить оптимизацию по двум критериям: производительности и стоимости, при соблюдении некоторых условий на надежность и производительность. Например, условия включения в состав МСОИУ, для обеспечения надежности, как минимум двух процессоров каждого типа. В то же время увеличение количества шин значительно увеличивает стоимость.
Таким образом, проблема выбора эффективного варианта МСОИУ формализуется в виде многокритериальной задачи оптимизации с двумя противоречивыми группами критериями. При выделении ведущего критерия в каждой из групп получим задачу с двумя критериями и группой существенных ограничений, в которые превратятся остальные критерии каждой из групп.
Существенную проблему для решения получаемой задачи оптимизации создает также способ вычисления целевых функций (критериев). В [29, 60] были предложены как аналитические, так и имитационные модели. Однако, с точки зрения создаваемых для оптимизационных алгоритмов проблем оба класса моделей чрезвычайно неудобны. Даже аналитические модели не могут быть исследованы методами математического анализа из-за их чрезвычайной сложности, а значит - их аналитический вид не дает им никаких преимуществ перед имитационными моделями. Таким образом, целевые функции нашей задачи оптимизации можно считать заданными алгоритмически, а это означает, что для ее решения могут быть задействованы только методы прямого поиска, причем те из них, которые могут работать со многими критериями и с переменными того типа, которые имеют место при выборе структуры МСОИУ.
Рассмотрим тип переменных нашей оптимизационной задачи. При этом будем полагать заданным максимальное количество типов процессоров N и шин (л), а также максимально и минимально возможное количество процессоров и шин каждого типа (для процессоров т,+ и ті соответственно, / = 1, ..., N, а для шин и/и п/ соответственно,у = 1, ..., п). Обозначим через mt количество процессоров /-го типа, включаемых в структуру МСОИУ (/ = 1, ..., N), а через rij - количество шину-го типа, включаемых в МСОИУ. Не трудно видеть, что переменные нашей оптимизационной задачи (т{ и nj) являются целочисленными, т.е. мы имеем задачу дискретной оптимизации, а точнее - задачу оптимизации на целочисленной решетке. В случае использования аналитических моделей оценки показателей эффективности, список переменных этим и исчерпывается. Однако переменные данной задачи на самом деле зависят от параметров процессоров и шин (v„ jx,-), которые должны быть известны заранее.
Разработка модифицированного генетического алгоритма для решения задачи выбора эффективной конфигурации МСОИУ
В качестве приемлемого средства решения задачи выбора эффективной конфигурации МСОИУ был выбран генетический алгоритм. Однако, для работы генетического алгоритма необходимо закодировать каждое решение в бинарную строку конечной длины — хромосому. Здесь решение — это набор параметров, однозначно определяющий структуру МСОИУ и быстродействие спецпроцессоров. Наш же алгоритм должен работать с вариантами МСОИУ произвольной конфигурации. То есть, нам заранее не известно не только значение параметров МСОИУ, но и их количество. Действительно, если в качестве одного из параметров, который должен настроить генетический алгоритм, выступает N — количество типов процессоров, то среди вариантов МСОИУ, которые рассматривает алгоритм, могут оказаться такие, которые отличаются количеством типов процессоров, а значит и количеством наборов данных. Поэтому для решения задачи выбора эффективной конфигурации МСОИУ генетический алгоритм должен быть существенно модифицирован. Поэтому в диссертации разработан модифицированный генетический алгоритм с переменной длиной хромосомы.
На этапе инициализации генетического алгоритма каждому решению случайным образом присваивается значение, определяющее количество типов процессоров в данной МСОИУ. Этот параметр определяет длину хромосомы и не принимает участия в работе генетических операторов. Следующие четыре бита хромосомы содержат информацию о количестве шин в МСОИУ, таким образом, количество шин для каждой МСОИУ подбирается от 1 до 16. Далее в хромосоме следуют наборы бит, характеризующие каждый тип процессоров. Количество таких наборов будет зависеть от заданного для данной хромосомы количества типов процессоров. Первые пять бит из набора определяют быстродействие процессоров данного типа. Как упоминалось выше, быстродействие измеряется в микросекундах и может выражаться нецелым числом. Однако, абсолютные значения быстродействий процессоров могут значительно отличаться. В таблице 5 приведены значения быстродействий процессоров многопроцессорного вычислительного комплекса "Эльбрус-2".
Как видно из значений, приведенных в таблице, быстродействие процессоров может различаться в сотни раз. Поэтому в хромосому кодировалось значение быстродействия в логарифмической шкале. Это позволило охватить весь интересующих нас интервал с необходимым разбросом значений. На рисунке 12 показан случайный выбор значения быстродействия на логарифмической шкале.
Следующие четыре бита из набора определяют количество процессоров данного типа, благодаря этому, число процессоров каждого типа вариру-ется от 1 до 16. На рисунке 13 показана хромосома с процессорами двух типов, двумя шинами, семью процессорами с быстродействием 52.33 и шестнадцатью процессорами с быстродействием 3.16
Система поддержки принятия решений для выбора эффективной конфигурации МСОИУ
На основе предложенных алгоритмов и методов была разработана система поддержки принятия решения для выбора эффективной конфигурации МСОУИ. Данная программная система зарегистрирована в отраслевом фонде алгоритмов и программ (№ ЕСПД .03524577.01437-01 99 01).
Программная система «СППР выбора эффективной конфигурации МВС» предназначена для создания вариантов многопроцессорных вычислительных систем с оптимальной структурой и быстродействием специализированных процессоров. Расчет основных характеристик качества работы МСОИУ - относительной производительности и стоимости системы, осуществляется по оригинальной аналитической формуле. При поиске оптимальной конфигурации МСОИУ происходит настройка не только структуры МСОИУ, то есть количества компонентов входящих в ее состав, но и настройка параметров быстродействия спецпроцессоров, также напрямую влияющих на производительность системы и формирование стоимости МСОИУ. Поиск эффективного варианта МСОИУ осуществляется с помощью модификации генетического алгоритма, разработанного специально для поиска разнородных по составу вариантов МСОИУ. Пользователь контролирует работу генетического алгоритма, а так же осуществляет настройку всех параметров МСОИУ. Кроме того, пользователь может предлагать системе свои варианты МСОИУ, для их оптимизации.
Программная система разработана под Windows ХР [66] средствами Borland C++, версии 6.0 [3, 65, 68]. Для работы с данной программной системой необходимо иметь персональный компьютер типа Pentium II с операционной системой Windows 95 и выше и оперативной памятью 196 Мб. Общий объем электронного продукта 1 Мб.
Предлагаемая программная система состоит из трех блоков (рисунок 19): блок пользовательского интерфейса, блок, реализующий алгоритм прямого вычисления производительности МСОИУ, и блок отвечающий за работу модернизированного генетического алгоритма. Пользователь производит настройку параметров генетического алгоритма и указывает некоторые характеристики интересующей его МСОИУ. Генетический алгоритм постоянно обращается к блоку алгоритма прямого вычисления производительности, для получения оценок производительности МСОИУ найденных им в ходе работы. Рабочее окно программы имеет три рабочих области. Первая область: «Настройка запуска» (рисунок 20). Пользователь может ввести свои параметры работы генетического алгоритма (правая часть области настройки запуска). Пользователь может выбрать тип скрещивания (одноточечный и двухточечный), механизм многокритериального отбора ГА (VEGA, FFGA или гибридную схему), а так же задать кажущиеся ему более разумные параметры: количество поколений, размер популяции и вероятность мутации. По умолчанию генетический алгоритм может быть запущен с двухточечным скрещиванием, гибридной схемой многокритериального отбора, размером популяции 40 индивидов, вероятностью мутации 0.01 и с количеством поколений 10. В левой части области настройки запуска происходит настройка некоторых параметров МСОИУ, которые будут неизменны в ходе работы алгоритма. Это - коэффициент связанности алгоритмов по памяти, максимальное число типов процессоров и параметр, определяющий быстродействие шин МСОИУ. По умолчанию коэффициент связанности по памяти равен 0.35, быстродействие шин принимается равным 1.2, а максимальное количество типов процессоров равно 6. Кроме того, в области настройки запуска находятся кнопки запуска генетического алгоритма и кнопка выхода из программы. Вторая область: «Своя МСОИУ» (рисунок 21). Здесь пользователь может в качестве одного из индивидов начальной популяции генетического алгоритма ввести свой вариант МСОИУ. Для этого необходимо поставить флажок «Включить свою МВС в начальную популяцию», а затем задать количество типов процессоров, количество шин, количество и быстродействие процессоров каждого типа своей МСОИУ. При этом вводимые параметры не должны противоречить параметрам МСОИУ введенным в области «Настройки запуска». В случае отключенного флажка «Включить свою МСОИУ в начальную популяцию», МСОИУ пользователя не будет включена в стартовую популяцию.
