Software & Systems

Одним из путей достижения высокой производительности современных вычислительных систем является совершенствование методов организации вычислительного процесса в многопроцессорных вычислительных системах (МВС). Большинство современных высокоорганизованных вычислительных систем содержат в своем составе несколько процессоров.

МВС являются системами со сложными структурной организацией и управлением ходом вычислений в процессе их функционирования в режиме обработки М-задач на N-процес-сорах системы, причем М> >N. Возникает необходимость решения задачи оптимального последовательно! о распределения поступающих на обработку готовых для реализации задач на свободные подструктуры, синхронизации работы процессоров, коммутации процессоров в процессе функционирования МВС и т.д. При этом следует учитывать, что рабочая нагрузка МВС постоянно изменяется, т.е. на вход поступают задачи с различными характеристиками (приоритетом обрабатываемых задач, разрядности и обрабатываемой информации, времени их реализации и т.д.). Состояние самой многопроцессорной системы также изменяется в каждый момент времени (т.е. изменяется количество свободных подсистем МВС и время их занятости). Поэтому организация динамического управления многопроцессорной потоковой вычислительной машиной является сложной проблемой, и одной из важнейших ее составляющих является задача оптимального распределения ресурсов МВС при множественности входных наборов задач и различных критериальных требованиях к функционированию системы (например показателей качества).

В настоящее время разработаны различные эвристические методы решения задачи распределения ресурсов- МВС для частных случаев поступления входных наборов задач, например для случая обработки задач одинаковой разрядности, равноприоритетных задач, задач с приблизительно одинаковым временем реализации и других. Однако ввиду множественности входной нагрузки у ВС широкого назначения, изменяющегося состояния оборудования МВС и при различных целевых функциях ее работы для каждого набора задач может быть более эффективна своя стратегия распределения сегментов на свободные процессоры МВС, например с целью максимальной загрузки оборудования системы или обработки приоритетных задач. Поэтому следует, обобшая накопленные знания по решению задачи назначения, определить средство аккумуляции знаний экспертов в данной проблемной области в единую целостную систему для использования их наилучшим образом при решении задачи, распределения изменяющейся входной рабочей нагрузки на свободные подсистемы МВС, достигая при этом оптимума целевого критерия функционирования системы.

Достижению оптимума показателя качества работы многопроцессорной системы препятствуют многие факторы, в том числе и неэффективность стратегий распределения ресурсов системы, не учитывающих характер поступающих на обработку задач. Снизить влияние отрицательных факторов возможно, если представить процесс динамического управления МВС как процесс приведения системы к равновесию с максимальным значением показания качества с помощью механизма гомеостазиса, в роли которого в данной работе выступает экспертная система (ЭС) распределения изменяющейся входной рабочей нагрузки на свободные процессоры МВС ПОТОК.

Вследствие разнообразного характера множества задач, поступающих на вход системы, изменяющегося в каждый момент времени состояния аппаратуры МВС и г.ри различных критериальных требованиях к ее работе необходимо абстрагироваться от конкретных, частных характеристик решаемых задач и структур многопроцессорных систем и перейти на уровень их модельного представления. Следует учитывать, что сама по себе обрабатываемая задача имеет сложную структуру, т.е. состоит из совокупности взаимосвязанных блоков задачи (сегментов). Модельное представление обрабатываемых задач характеризуется паспортом задачи, отражающим основные ее параметры. Паспорт является математической моделью внешней среды функционирования многопроцессорной системы. Использование паспортов готовых к реализации задач (сегментов) позволяет усовершенствовать процесс автоматизации распараллеливания вычислений на процессоры МВС и тем самым минимизировать время решения совокупности задач при максимальной загрузке оборудования системы.

Способами решения поставленной задачи распределения ресурсов многопроцессорной системы с учетом множественности входных наборов задач, изменяющегося состояния аппаратуры МВС и различных целевых функций ее работы являются:

1)       представление вешаемых задач крупно структурированными едоками данных (сегмен тами);

2)       использование потокового принципа ор ганизации вычислений;

3)       создание информативных моделей внеш ней среды функционирования МВС и состояния аппаратуры для решения задачи назначения рабочей нагрузки;

4)       разработка стратегий эффективной орга низации распределения ресурсов МВС на осно ве модельного подхода;

5)       создание базы знаний принятия решения задачи назначения.

На этапе исследований при создании ЭС ПОТОК предполагалось, что методикой крупноблочного распараллеливания поступающие на обработку задачи разбиваются на сегменты, причем степень связанности сегментов задачи может быть различной. На вход системы могут поступать несвязанные задачи, задачи, состоящие из слабосвязанных сегментов, и задачи, граф связи сегментов которых приближается к полному графу. Использование потокового принципа организации вычислений в МВС предполагает, что для назначения на свободную подсистему выбирается подходящий готовый сегмент, т.е. сегмент, получивший от сегментов-предшественников все необходимые данные для его обработки.

Исследование задачи распределения ресурсов МВС показало, что для назначения в систему целесообразнее выбирать подходящие сегменты, принадлежащие различным задачам. Такой способ решения совокупности задач приводит к тому, что в каждый момент времени в системе будет находиться большое число готовых к выполнению сегментов, которыми всегда можно дозагрузить свободные процессоры системы. В ходе создания ЭС ПОТОК был разработан алгоритм эффективной дозагрузки свободных подструктур МВС задачами различной разрядности. Задача считается подходящей для дозагрузки, если ее ранг R не больше числа свободных процессоров системы. Рангом задачи называют количество требуемых для обработки задачи процессоров.

Ввиду множественности входных наборов задач с различными характеристиками, множественности состояний аппаратуры многопроцессорной системы и при различных показателях качества ее работы оптимальное решение задачи распределения методами теории расписаний в большинстве случаев предполагает полный перебор вариантов решения поставленной задачи. Создание ЭС ПОТОК, обобщающей накопленные знания в данной проблемной области, позволяет на основе определения однозначного соответствия математической модели внешней среды функционирования МВС, математической модели состояния аппаратуры системы и требуемого показателя качества ее работы сакратить пространстрз анализируемых представительных параметров решаемых задач. Это приводит к сокращению времени принятия решения задачи назначения и следовательно к сокращению времени, затрачиваемому на выбор наилучшей для данной входной нагрузки стратегии распределения задач (уже на первоначальном этапе сужается класс рассматриваемых стратегий распределения). Например, при необходимости минимизации времени решения приоритетных задач после определенной предварительной обработки набора задач выбирается класс стратегий обработки приоритетных задач. Затем выбор готовой подходящей задачи {сегмента сложной задачи) и ее распределение по процессорам МВС осуществляется исходя из среднестатистических данных рассматриваемой совокупности задач с целью сужения подпространства анализируемых параметров задач и вариантов решения задачи распределения для данной входной нагрузки.

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

Во всякой ЭС, как системе искусственного интеллекта (ИИ), в выработке решения должна присутствовать идея аргументации принятия решения. В связи с тем, что накопленный опыт для обобщения в системе требует глубинных представлений знаний о предметной области, что требует дополнительных серьезных исследований, в данной работе принято некоторое упрощение, связанное с тем, что модель принятия решения определяется в некоторой степени статистическими методами, которые в значительной мере отражают семантику принятия решения задачи назначения. Учитывая недостатки изученности глубинных знаний, на данном этапе управления МВС можно ограничиться предложенным подходом.

В качестве инструментального средства создания интеллектуальной системы назначения входной рабочей нагрузки на свободные процессоры МВС на .этапе исследований использовалась гибридная инструментальная среда GURU - оболочка экспертной системы. Среда GURU применялась в качестве исследовательского прототипа для доказательства целесообразности применения элементов ИИ при реше-

нии задачи распределения ресурсов МВС. На исследовательском этапе создания экспертной системы ПОТОК в качестве модели представления знаний использовались правила продукций, например:

IF: quality = "миннаб" and aver(4) = 0 andpr=false\

and r = true and aver(3) < 50 . THEN: run "maxrt.exe"

В заключительной части правила может стоять вызов процедуры распределения ресурсов из разработанной библиотеки процедур. Разнообразие и сложность представления задачи управления приводит к выводу о необходимости применения смешанных методов представления знаний на этапе совершенствования ЭС распределения ресурсов МВС ПОТОК, например смешанной фреймово-продукционной системы представления знаний.

В ходе разработки системы ПОТОК было создано две базы данных, характеризующие математическую модель функционирования МВС и математическую модель состояния аппаратуры МВС.

Используя модельный подход к решению задачи оптимизации динамического управления многопроцессорной потоковой вычислительной машиной, можно анализировать модель динамики функционирования универсальной МВС. При этом по желанию пользователя ЭС ПОТОК можно моделировать работу N-процессор-ной системы, где N варьируется.

Апробация работы исследовательской ЭС распределения ресурсов МВС показала, что применение элементов ИИ при решении поставленной задачи дает выигрыш в загрузке оборудования МВС, составляющий приблизительно 15-20%. Совершенствование разработанной ЭС возможно в случае использования в качестве инструментального средства языков инженерии знаний и языков программирования, ориентированных на создание ЭС и систем ИИ. Эти средства обеспечивают более высокую эффективность разработанных ЭС в плане уменьшения времени реакции системы на решение поставленной задачи распределения ресурсов МВС.

ЭС ПОТОК физически может быть реализована в составе операционной системы (ОС) управляющего процессора ' при относительно небольшом количестве процессоров многопроцессорной системы либо в составе ОС процессора, управляющего кластерами МВС при большом количестве процессоров системы. Распределение во втором случае осуществляется как на микроуровне (распределение задач между процессорами одной кластерной группы), так и на макроуровне (распределение наборов задач между различными кластерами). Это приводит к возможности параллельной обработки различных наборов задач, решению задачи автоматического распараллеливания сегментов сложных задач и синхронизации работы процессоров системы и т.п.

Все вышеизложенные соображения в сочетании с эффективной организацией распределения задач на свободные подструктуры МВС приводит к увеличению загрузки процессоров системы и к увеличению производительности МВС в целом.

Список литературы

1. Шигин Л.Г. Мультипрограммная многопроцессорная потоковая ВС, динамически настраиваемая с помощью элементов искусственного интеллекта. // Тезисы докладов секции "Информационные средства и технологии в науке, технике и обучении" Международного форума информати зации. -М.: МЭИ, 1992.

2.      Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. - М.: Радио н связь, 1983.

3.      1) л реки и А.Б- Планиронанне параллельных вычисли тельных процессов. - М.: Машиностроение, 1988. - 192 с.