автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач

На правах рукописи

МИЛЕХИНА ТАТЬЯНА ВИКТОРОВНА

Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач (на примере задачи составления расписания

занятий)

Специальность 05.13.01. Системный анализ, управление и обработка информации (в приборостроении)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 8 ИЮЛ 2011

Москва 2011

4851881

Работа выполнена на кафедре Вычислительной техники при Московском государственном институте электронной техники (техническом университете).

Научный руководитель

кандидат технических наук, профессор Лупин Сергей Андреевич.

Официальные оппоненты

доктор технических наук,

Щагин Анатолий Васильевич

кандидат, физико-математических наук Шебеко Юрий Александрович

Ведущее предприятие - Институт системного анализа РАН

Защита состоится 2011 года на заседании

диссертационного совета Д212.134.02 при Московском государственном институте электронной техники (техническом университете). 124498, Москва, Зеленоград, проезд 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан " ¿/ьсиЯ 2011 года.

" >го совета

д.т.н., Гуреев А.В.

Общая характеристика работы

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

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

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

Цель работы и задачи исследования. Работа посвящена исследованию методов повышения эффективности кластерных систем при решении оптимизационных задач за счет адаптации алгоритмов к особенностям их архитектуры.

Для достижения поставленной цели в работе решаются следующие основные задачи:

1. Анализ переносимости методов решения задач многокритериальной оптимизации на параллельную платформу.

2. Постановка и формализация задачи составления расписания занятий в ВУЗе.

3. Разработка критериальных оценок качества решения задачи составления расписания.

4. Разработка алгоритма решения задачи составления расписания занятий.

5. Анализ методов распределения нагрузки для многопроцессорных систем с распределенной памятью.

6. Разработка метода распределения нагрузки для алгоритма оптимизации, повышающего эффективность кластерных вычислителей с распределенной памятью.

7. Разработка параллельной программы, адаптированной для кластерных вычислителей с распределенной памятью.

8. Экспериментальное исследование эффективности предложенного алгоритма.

Объект и предмет исследования. Объектом исследования являются методы и алгоритмы решения оптимизационных задач.

Предметом исследования являются параллельные алгоритмы многокритериальной оптимизации, повышающие эффективность кластерных вычислителей с распределенной памятью.

Методы исследования. При решении указанных задач были использованы положения теории принятия решений, теории множеств, методы многокритериальной оптимизации и языки параллельного программирования.

Научная новизна. Основной результат диссертационной работы состоит в теоретической разработке и практической реализации нового

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

Положения, выносимые на защиту,

1. Результаты анализа переносимости алгоритмов решения задачи составления расписания занятий на параллельную платформу.

2. Итерационный алгоритм решения задачи составления расписания.

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

4. Параллельная программа автоматического решения задачи составления расписания для многопроцессорных вычислительных систем с распределенной памятью.

5. Результаты практического исследования эффективности алгоритма и программы.

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика - 2007, 2008», «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007», IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» - 2009, Международной

научно-практической конференции ГПШ8'2010 «Информационные технологии. Электронные приборы и системы».

Публикации. По материалам диссертации опубликовано пять тезисов докладов и две статьи, одна из которых в журнале, рекомендуемом ВАК. Получены два свидетельства РФ на программу для ЭВМ.

Структура и объём диссертационной работы. Рукопись диссертационной работы состоит из введения, четырех глав, заключения, списка литературы и приложения. Общий объем работы 136 листов и приложения.

Содержание работы

Во введении обоснована актуальность, цель работы, ее научная новизна и практическая значимость; представлены применяемые методы исследования, внедрение результатов, апробации и обзор содержания диссертации.

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

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

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

раскраски графа, имитационное программирование, линейное целочисленное программирование, генетические алгоритмы.

Большинство предлагаемых методов основываются на некотором «нулевом», начальном варианте расписания занятий, и нацелены на его оптимизацию. При этом итоговый вариант может существенно отличаться от начального. Но «нулевое» расписание необходимо сначала как-то получить. Если в таком качестве использовать решение, полученное быстрыми алгоритмами случайного поиска, то его модификация будет длительным процессом с непредсказуемым результатом. Это вытекает из методов итерационной оптимизации, в которых решение, получаемое на к-ом шаге алгоритма, зависит от к-1 шага. Кроме того, в силу размерности задачи, речь может идти только о поиске локально-оптимальных решений. Не удается использовать в качестве начального приближения и уже разработанное в прошлом ручное расписание, т.к. учебный процесс весьма динамичен и может изменяться от семестра к семестру, и тем более, от курса к курсу: возможно изменение числа факультетов, числа групп студентов, преподавателей и дисциплин.

Таким образом, программный комплекс составления расписания должен качественно генерировать в автоматическом режиме не только окончательное, но и начальное решение задачи.

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

Во второй главе рассмотрены вопросы формализации задачи составления расписания, выбора критериальных функций, представлена математическая модель.

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

В задаче составления расписания можно выделить следующие объекты:

студенческие группы ((Э), имеющие уникальный идентификатор;

преподаватели (Р) или группы преподавателей, проводящие

занятие;

учебные дисциплины (5) с видами и объемом занятий;

аудитории (К) .

Единицей расписания является занятие, представляющее собой совокупность всех перечисленных объектов (каждый тип объекта может иметь не единичное вхождение, например, при потоковом занятии, занятие будет содержать некоторое количество объектов «группа», соответствующее количеству групп в данном потоке).

Так как учебный план формируется заранее, то набор дисциплин для каждой группы уже определен, так же как и объем нагрузки по каждому предмету. В работе использован принцип равномерного распределения всех дисциплин в течение семестра. Таким образом, при известном количестве часов, отведенных для данной дисциплины, известна и периодичность проведения занятия Р - еще один атрибут расписания. Зачастую нагрузка преподавателей планируется заранее, и для ряда групп уже назначен преподаватель каждой дисциплины.

В общем виде задачу составления расписания занятий в ВУЗе можно сформулировать в следующем виде - необходимо найти временной интервал Т, место проведения занятия Я, т.е. соответствующую аудиторию, и преподавателя Р. В сформированном расписании у каждого занятия будут определены все атрибуты (Сг, Р,3,Я, Т, Р).

Результат решения задачи синтеза расписания обычно представляется в виде таблицы, это наиболее удобная и понятная форма представления такого рода информации.

Расписание (Тше-ТаЫе) будем рассматривать как 3-х мерный массив, элемент которого это кортеж:

ТТик =(Р,5,Л) , где: / = (1,48) порядковый номер занятия (атрибут Т), } - (1, Л7) идентификатор группы (атрибут С), к = (1,4) порядковый номер недели в месяце (атрибут Р).

При этом элементы таблицы ТТ1/к могут быть как различными, так и

одинаковыми (если несколько групп объединены в поток).

. Это представление расписания для группы, аналогично, ТТф =(0,5,Л) - для преподавателей, и ТТт = для аудиторий.

Для задачи составления расписания занятий можно выделить «жесткие» ограничения, выполнение которых обязательно для получения корректного расписания, и «мягкие», желательные критерии, которые влияют на качество получаемого расписания.

Любое найденное решение должно удовлетворять ограничениям или пространственным и временным условиям не конфликтности расписания:

в одной аудитории не может проходить одновременно несколько занятий;

одно занятие не должно проходить одновременно в разных аудиториях (исключая специальные лабораторные работы, когда может потребоваться несколько аудиторий для проведения занятия); у группы не может проходить одновременно несколько разных занятий (исключая дисциплины по выбору);

преподаватель не может проводить одновременно несколько занятий.

К критериям можно отнести следующие:

количество «окон» в расписании групп;

количество «окон» в расписании преподавателей;

превышение оптимального количества занятий в день у групп;

превышение оптимального количества занятий в день у

преподавателей;

неэффективная загруженность дня у групп; неэффективная загруженность дня у преподавателей; пожелания преподавателей;

ограничение на количество рабочих дней у преподавателей; оптимальное количество рабочих дней у преподавателей; оптимальное количество дней обучения у групп. Преподаватели могут предъявлять к расписанию различные пожелания: проведение занятий только в определенные дни или в определенное время, скомпоновать занятия в несколько дней и т.п. Так же могут быть различные пожелания и для занятий: определенная аудитория, в которой его необходимо проводить (характерно для лабораторных работ), проводить лекции до семинаров, временные пожелания.

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

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

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

т in

Sched(х) = £ aj¡(х) min;а, =1.

1=1 1 ¡=1 Таким образом, лучшим решением будет то решение, значение Sched(x) которого будет минимально. Дополнительные параметры так же учитываются в данной свёртке и включаются в общую сумму наравне с основными критериями.

Для определения коэффициентов важности в работе использовались два подхода: наборы ненормированных и нормированных критериев.

Определение коэффициентов важности OCi плохо формализованный

процесс потому, что сложно выразить все критерии в численном виде и определить отношения предпочтения между ними.

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

С некоторым упрощением алгоритм составления расписания можно представить следующим образом:

1. Получение всей необходимой исходной информации: данные о занятиях, о преподавателях, о группах, аудиториях, задание коэффициентов важности cc¡.

2. Подсчет штрафной функции для каждого занятия в каждый момент времени.

3. Выбор на основе полученных значений целевой функции Sched(x) наиболее подходящего занятия, закрепление которого, приводит к минимизации штрафной функции.

4. Блокирование ресурсов выбранного занятия в выбранный временной интервал.

5. Выполнять шаги 2-5 пока все занятия из списка не будут расставлены, или пока дальнейшая расстановка не стала невозможной.

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

Для определения весовых коэффициентов в работе использовался преобразованный метод Саати с использованием так называемой «транзитивной» шкалы. Суть метода заключается в получении цепочки предпочтений ЛПР а[2, а2з, ...Оп,.,^. При таком подходе достигается непротиворечивость информации и значительно упрощается диалог с ЛПР. Далее пользуясь соотношением

ац - а, / ау

условием нормированное™ вектора а, решается уравнение.

В процессе работы было отмечено, что при определении степеней превосходства все же возникают некоторые противоречия. Избежать этого момента можно путем «двойного диалога» с ЛПР. На первом этапе выстраивается список критериев, убывающий по степени важности. Т.е. ЛПР отвечает на вопрос: «Важнее ли ¡-й критерий .¡-го?». На второй стадии уже определяется степень важности критериев, т.е. «Какое превосходство имеет ¡-й критерий над ¡-м?» (слабое, сильное, очень сильное, абсолютное).

Для того чтобы оценить качество полученного расписания, меру его удовлетворения заданным требованиям, были введены следующие критерии:

1. Неравномерность расписания для студентов;

2. Неравномерность расписания для преподавателей;

3. Превышение максимально допустимого числа занятий в день у студентов;

4. Превышение максимально допустимого числа занятий в день у преподавателей;

5. Одно занятие в день у студентов;

6. Одно занятие в день у преподавателей;

7. Совпадение расписания занятий с пожеланиями преподавателей;

8. Доля автоматически расставленных занятий;

9. Число преподавателей, у которых не выполнены требования по количеству рабочих дней;

10. Превышение оптимального количества дней занятий у студентов;

11. Превышение оптимального количества занятых дней у преподавателей.

Выразим эти критерии через операции с элементами 3-х мерной таблицы расписания, число учебных групп обозначим , а число

преподавателей Nрг:

Л^г 4 5 7

1) .л=ЕЕЕЕ^

н'*1 с/=0 1>=2

Цти.»*0' и 3/6(1,^-1) и ]е(р +1,8) такие, что

Ирг 4 5 7

2) /2 = ЕЕЕЕ™%,

/>г=1 ^=1 ¿=0 р=2

^^■(.^/»■при ПРИ

такое, что ТТы.щ)л,Л'Р>^ Рг и Э^еОлГ) при ]е{р +1,8)

такое, что ТТ(11.иЛяг ,„(,Р,) = ;

3) /з гда +

/сО /А»]

где ТТ'(1,ити1Г = 1 в том случае, если * 0; тахОг -

максимально допустимое число занятий у группы в день, критерий учитывает только превышение допустимого числа занятий, поэтому суммируются только положительные значения

4) Л = Е Е Е'и - т = (Е ТГ*8 * »'>■ ") ~ тах Рг,

М' = 1 рг = \ »яО /?»=1

где если Э^еОЛ^) такое, что

7Т(1.,8+т) г ,„ (,Р,) = рг, шахРг - максимально допустимое число

занятий у преподавателя в день, критерий учитывает только превышение допустимого числа занятий поэтому суммируются только положительные значения тРгКрг^,\

5) А = S S S oGru, где oGriiitI, = 1, если (£ TT'o • s*,). -О = 1,

£ = ] >-0 II 1 = 1

где TT\i4tll,Ui„ = 1 в том случае, если TT(i4+m) sM * 0.

6) Л=S Е Z0 рv,- ■ гда оРги».» =1 »если Œ ""с *8 * <">■ <"• »•)=1.

ii/=l pr-1 /=0 m=l

где TT\l4„„lprw = 1, если 3gs(l,Ngr) такое, что .

7) Этот критерий разделён на два усредненных подкритерия: доля выполненных пожеланий f7] и доля невыполненных пожеланий

/73.

Npr 4 5 8

^wPr , если

pr*) )f=l î/=û ^=1

TT(j-s+p).s,» (>P>) = Pr ПРИ некотором l<g<Ngr, и преподаватель

заявлял о желании работать в это время, то vva«/ Pr(<J,8+;j) = 1.

WantAmount - это общее количество ((положительных» пожеланий для этого преподавателя. AmPr - это общее количество преподавателей, изъявлявших «положительные» желания. Однако этот критерий не совсем точно отражает степень выполнения данного критерия, так как количество пожеланий может превышать общую занятость преподавателя. Например, занятость преподавателя - одна пара в неделю, и преподаватель изъявил желание работать, допустим, в понедельник, таким образом, количество «желаемых» занятий будет равно б временным отрезкам, а количество реальных - одному. Поэтому в случае, если количество выполненных пожеланий равно общей занятости преподавателя, то считается, что для него этот критерий равен 1.

Npr 4 S !

/v=&ŒlLZNwantPh^PiPrJ'KwantAmaunt)/Am Pr, если

pr*1 »'=1 rf=() P=l

= Pr ПРИ некотором 1 <g<Ngr, a преподаватель

просил не ставить в это время занятий, то Nwant Pr(rf., } =1.

NwantAmount - количество заявлении о не желании преподавать в какое-либо время для данного преподавателя, AmPr - общее количество преподавателей, высказавших «отрицательные» пожелания.

8) f¡¡ = {Ngool/_par / Npar), где Npar - общее количество занятий, . Ng0lldjar - количество расставленных занятий.

Npr 5

9) Л = (Z (must-dayw ~YuKo1-daypr,é)), где Kol_dayprJ = 1 в

/»•=1 </=0

том случае, если 3ge(l,Ngr) такое, что TT(d.^m)g n{,P,) = ргпри т 6 и w € , учитывается только факт превышения количества дней над must_daypr.

Ngr 5

1 L=CLW_day%r -J^Kol_daygr¡<¡)), где Kol_daygrd =1 в том

gr=l Í/=0

случае, если 3/е(1,р-1) и 3w e(l,4), что TT[d.¡+n sr lK * 0 ; a

opt__daygr = AllStudgr /opt_stud , где AllStudg, - это общее

количество занятий для данной группы в неделю, opt_stud -оптимальное количество занятий в день, принятое равным 4.

Л»и- 5

И) fu=C£(opt_daypr-YjKol_daylir!t)),rRZ Kol _dayprí/ =1 в том

;jr-I í/=0

случае, если Зяе(1,Л^) такое, что TT(dti+m)g„(,P,) = рг при и w б (l,4); a opt _ cfoy^. = AllStudpr / opt _ stud, где

AllStudpr - это общее количество занятий для данного преподавателя в неделю, opt_stud - оптимальное количество занятий в день, принятое равным 4.

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

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

Кластеры СоЭД^ позволяют получить производительность порядка единиц ТБЬрз, что вполне достаточно для многих практических приложений, но обладают слабой системой коммуникации. Это накладывает существенные ограничения на методы построения параллельных приложений и приводит к необходимости использовать средства явной передачи сообщений через коммуникационную среду при межузловом взаимодействии.

Чтобы из последовательной реализации программы сделать код, способный работать на параллельной платформе, необходимо решить три основные задачи:

выделить в программе ветви вычислений, которые можно исполнять параллельно;

распределить данные или код по модулям локальной памяти процессоров;

согласовать распределение данных с параллелизмом вычислений.

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

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

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

Предложенный метод основан на разделении данных между узлами, т.е. на фрагментации, а полученный код соответствует SPMD {Single Program Multiple Data) технологии.

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

Информационное взаимодействие между узлами осуществляется с помощью передачи сообщений (MPI). Алгоритм предполагает полную осведомленность всех узлов на каждом шаге о результатах всех предыдущих шагов каждого узла. Это значит, что обмен сообщениями должен также производиться на каждой итерации, следовательно, необходимо стремиться уменьшить количество пересылок и объем передаваемых данных. Для этого предложено реплицировать исходные данные на каждом узле. Таким образом, узлу достаточно знать лишь порядковый номер занятия, чтобы узнать все его атрибуты. Это позволяет каждому узлу решать задачу поиска локального оптимума в выделенном пространстве опираясь на полную информацию о состоянии всех остальных узлов.

Рассылки осуществляются:

при выборе наилучшего варианта для установки на данном шаге, узлы обмениваются только данными о штрафной функции;

при передаче параметров устанавливаемого занятия на данном этапе: порядковый номер занятия, номер аудитории, порядковый номер пары, номер недели месяца.

Обладая полной информацией о занятии, узел может заблокировать необходимые ресурсы, исходя из полученных данных.

Рис. 1. Параллельный алгоритм решения задачи составления расписания.

На рис. 1 представлен параллельный алгоритм задачи составления расписания. Жирными линиями выделены этапы алгоритма, которые исполняются параллельно.

Для практических исследований эффективности предложенного подхода была разработана параллельная MPI программа.

В четвертой главе приведены результаты экспериментальных исследований и испытаний, а также анализ эффективности предложенного алгоритма.

Параллельная программа для решения задачи составления расписания занятий в ВУЗе использует библиотеку MPI. В качестве аппаратной платформы для экспериментов был использован CoWS кластер МИЭТ-2008 с коммуникационной средой на основе Gigabit Ethernet. Пиковая производительность кластера составляет 1,6 TFlops. Он состоит из 25 узлов, в каждом из которых установлено по два 4-х ядерных процессора Intel Xeon.

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

Некоторые результаты исследований для различного числа занятий приведены на рисунках 2-4.

1800 1 t? 1600 £ 140 0

1 1200 ч 1000

и

| 800

м 60 О

1 400

И 200

о

1 2 4 8 16 32 64 96 128 136 Число ядер

\

Рис. 2. Оценка масштабируемости алгоритма

1600 -а-2200

-^-2524

16 32 64 96 128 136 Число ядер

Рис 3. Оценка ускорения параллельного алгоритма

1600 2200 2524

16 32 64 Число ядер

96 128 136

Рис. 4. Эффективность параллельного алгоритма.

Эксперименты проводились для 1600, 2200, 2524 занятий. Результаты показывают, что время вычислений обратно пропорционально

числу вычислительных ядер. Это позволяет сделать вывод о приемлемой масштабируемости алгоритма. При запуске последовательного приложения на 8-ми ядерной машине загруженность процессора составляла величину порядка 12%. Запуск параллельного приложения позволяет повысить эффективность использования ресурсов системы и достичь 90-96% загрузки процессоров узлов кластера, что близко к практическому максимуму и говорит о правильно выбранной стратегии распределения нагрузки.

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

Таблица 1. Оценка качества составленного расписания

Критерий Количество занятий

1600 2200 2524

Л 15 32 29

Л 30 65 188

Л 45 78 182

Л 0 2 34

Л 933 1042 1091

и 1533 2203 2512

Лп 0,68 0,78 0,68

/?2 0,02 0,04 0,04

Л 1 1 1

Л 0 1 2

Ло 193 234 262

Ли 230 316 362

Отметим, что во всех случаях алгоритм полностью решил задачу, значение критерия /$ для всех примеров равно 1. Полученные результаты практически подтверждают возможность эффективного использования вычислительных систем с распределенной памятью для решения оптимизационных задач.

В заключении приведены основные результаты работы.

Основные результаты работы

1. Проведен анализ существующих методов решения задач многокритериальной оптимизации и обоснована необходимость их переноса на параллельную платформу.

2. Формализована задача составления расписания занятий в ВУЗе, как задача многокритериальной оптимизации.

3. Разработан последовательный алгоритм составления расписания занятий в ВУЗе, основанный на минимизации целевой функции, вычисленной по методу линейной свертки.

4. Разработан параллельный алгоритм решения задачи составления расписания занятий, учитывающий архитектурные особенности кластерных систем обработки информации, обеспечивающий 90% загрузку узлов кластера и ее динамическую балансировку.

5. На языке С++ с использованием библиотеки MPI разработан программный модуль автоматического составления расписания занятий в ВУЗе, адаптированный для кластерных вычислительных систем с распределенной памятью и обеспечивающий 100% расстановку занятий в автоматическом режиме. На указанный программный модуль получено свидетельство об официальной регистрации.

6. Исследования предложенного алгоритма и разработанной на его основе программы, проведенные на вычислительном кластере МИЭТ-2008, подтвердили, что эффективность использования узлов кластера в процессе решения оптимизационной задачи достигает величины 90-96%.

Основные результаты диссертации изложены в работах:

1. Милехина Т.В. Формализация задачи составления расписания занятий.// Микроэлектроника и информатика. 14-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, апрель 2007г, с. 157.

2. Лупин С.А., Милехина Т.В. Программа автоматического составления расписания занятий В ВУЗе - «1п518Ьес1и1е». //Свидетельство РФ об официальной регистрации программы для ЭВМ №2007613815

3. Лупин С.А., Милехина Т.В. Метод решения задачи составления расписания, ориентированный на кластерные вычислительные системы.// Научно-технический журнал "Известия высших учебных заведений. Электроника" - М.: МИЭТ №6 , с. 63 - 69, 2007г.

4. Милехина Т.В. Распараллеливание задачи составления расписания занятий в ВУЗе. // «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем». Всероссийская межвузовская научно-практическая конференция. - М.: МИЭТ, ноябрь 2007 г., с. 127.

5. Милехина Т.В. Организация межузловых обменов при решении задачи составления расписания. // Микроэлектроника и информатика. 15-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. - М.: МИЭТ, апрель 2008 г., с. 202.

6. Милехина Т.В. Распределение нагрузки и межузловой обмен данными при решении задачи составления расписания занятий на параллельных системах. // «Техника и технология» №5 2008г., стр.41-43.

7. Лупин С.А., Милехина Т.В., Ней Мин Тун. Параллельная программа автоматического построения кратчайших связывающих деревьев - "РагТгасе". //Свидетельство об официальной регистрации программы для ЭВМ № 2008610703

8. Милехина Т.В., Лупин С.А., Киселев Д. В. К вопросу об алгоритмизации задачи составления расписания занятий в распределенной среде. // Материалы IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» - МГУ, Москва, декабрь 2009г.

9. Милехина Т.В., Лупин С.А., Киселев Д. В. Алгоритмизация задачи составления расписания занятий в распределенной среде. // "Материалы Международной научно-практической конференции "Информационные технологии, электронные приборы и системы, 1ТЕБ5'2010" 6-7 апреля 2010 г. Минск, Беларусь: БГУ. - стр.73-77.

Подписано в печать:

Заказ№ /У^Тираж90экз.Уч.-изд.л.1,35. Формат60x84 1/16. Отпечатано в типографии МИЭТ (ТУ). 124498, Москва, МИЭТ (ТУ).

Введение.

Глава 1. Методы решения задач многокритериальной оптимизации.

1.1 Метод моделирования отжига (Simulated Annealing).

1.2 Генетические алгоритмы (Genetic Algorithms).

1.3 Табуированный поиск (Tabu Search).

1.4 Метод роящихся частиц (Particle Swann).

1.5 Алгоритм раскраски графа (Graph Coloring Algorithm).

1.6 Метод муравьиных колоний (Ant Colony Algorithm).

1.7 Метод пчелиной колонии (Bees Colony Algorithm).

1.8 Линейная свертка. Линейное целочисленное программирование. (Linear convolution. Linear integer programming).

1.9 Существующие подходы к решению задачи составления расписания.

1.10 Выводы.

Глава 2. Формализация задачи составления расписания занятий.

2.1. Составление расписания, как задача многокритериальной оптимизации.

2.1.1 Объекты расписания.

2.1.2 Множество критериев.

2.1.3 Влияние критериев на качество расписания.

2.1.4 Дополнительные параметры.

2.2. Метод решения задачи составления расписания.

2.3 Автоматическое назначение преподавателя.

2.4. Многокритериальная оптимизация в задаче составления расписания.

2.5. Выбор альтернатив в задаче составления расписания.

2.6 Коэффициенты важности критериев и параметров.

2.7 Вычисление критериальных функционалов.

2.7.1 Критерий «окна».

2.7.2 Эффективная загруженность дня.

2.7.3 Эффективная загруженность недели.

2.7.4 Пожелания преподавателей.

2.8 Алгоритм выбора аудитории для занятия.

2.9 Особенности составления расписания в МИЭТ.

2.10 Оценка качества полученного решения.

2.11 Выводы.

Глава 3. Особенности реализации параллельных программ на кластерных системах.

3.1 Основные типы и архитектуры многопроцессорных систем.

3.2 Основные характеристики производительности.

3.3 Основные проблемы разработки параллельного алгоритма.

3.4 Основные этапы разработки параллельных алгоритмов.

3.5 Выделение подзадач в задаче составления расписания занятий. Информационные зависимости.

3.6 Масштабирование задачи составления расписания.

3.7 Взаимодействие между подзадачами составления расписания.

3.8 Распределение подзадач между процессорами кластерной системы.

3.9 Параллельный алгоритм для кластерных систем решения задачи составления расписания.

3.10 Формирование подсписков. Динамическая балансировка загрузки узлов.

3.11 Обмен данными между узлами кластерной системы.

3.12 Выводы.

Глава 4. Исследование эффективности кластера для параллельного алгоритма составления расписания занятий.

4.1 Структура входных данных.

4.2 Оценка качества получаемых решений.

4.3 Вычислительный эксперимент.

4.4. Выводы.

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

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

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

Цель работы и задачи исследования. Работа посвящена исследованию методов повышения эффективности кластерных систем при решении оптимизационных задач за счет адаптации алгоритмов к особенностям их архитектуры.

Для достижения поставленной цели в работе решаются следующие основные задачи:

1. Анализ переносимости методов решения задач многокритериальной оптимизации на параллельную платформу.

2. Постановка и формализация задачи составления расписания занятий в ВУЗе.

3. Разработка критериальных оценок качества решения задачи составления расписания.

4. Разработка алгоритма решения задачи составления расписания занятий.

5. Анализ методов распределения нагрузки для многопроцессорных систем с распределенной памятью.

6. Разработка метода распределения нагрузки для алгоритма оптимизации, повышающего эффективность кластерных вычислителей с распределенной памятью.

7. Разработка параллельной программы, адаптированной для кластерных вычислителей с распределенной памятью.

8. Экспериментальное исследование эффективности предложенного алгоритма.

Объект и предмет исследования. Объектом исследования являются методы и алгоритмы решения оптимизационных задач.

Предметом исследования являются параллельные алгоритмы многокритериальной оптимизации, повышающие эффективность кластерных вычислителей с распределенной памятью.

Методы исследования. При решении указанных задач были использованы положения теории принятия решений, теории множеств, методы многокритериальной оптимизации и языки параллельного программирования.

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

1. Результаты анализа переносимости алгоритмов решения задачи составления расписания занятий на параллельную платформу.

2. Итерационный алгоритм решения задачи составления расписания. 1

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

4. Параллельная программа автоматического решения задачи составления расписания для многопроцессорных вычислительных систем с распределенной памятью.

5. Результаты практического исследования эффективности алгоритма и программы.

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика - 2007, 2008», «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007», IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» - 2009, Международной научно-практической конференции ГГЕ08'2010 «Информационные технологии. Электронные приборы и системы».

Публикации. По материалам диссертации опубликовано пять тезисов докладов и две статьи, одна из которых в журнале, рекомендуемом ВАК. Получены два свидетельства РФ на программу для ЭВМ.

4.4. Выводы.

1. Проведенные эксперименты подтвердили, что параллельная программа позволяет решать оптимизационную задачу составления расписания занятий в автоматическом режиме. Разработанные алгоритмы и найденные коэффициенты важности критериев и параметров позволяют получить полностью корректное расписание со 100% расстановкой занятий в автоматическом режиме.

2. Использование параллельных алгоритмов дает возможность варьировать коэффициенты важности в уравнении свертки и генерировать различные решения, отвечающие предпочтениям Л ПР.

3. Эффективность кластера при решении оптимизационной задачи зависит от числа используемых узлов и находится в интервале от 0,94 — 0,23. Ее снижение при увеличении числа узлов определяется латентностью системы коммутации.

4. Загруженность каждого ядра при выполнении счетных операций составляет 96%, что говорит об эффективном использовании вычислительной мощности узла и правильной стратегии балансировки.

Заключение.

Краткая характеристика выполненных исследований:

1. Проведен анализ существующих методов решения задач многокритериальной оптимизации и обоснована необходимость их переноса на параллельную платформу.

2. Формализована задача составления расписания занятий в ВУЗе, как задача многокритериальной оптимизации.

3. Разработан последовательный алгоритм составления расписания занятий в ВУЗе, основанный на минимизации целевой функции, вычисленной по методу линейной свертки.

4. Разработан параллельный алгоритм решения задачи составления расписания занятий, учитывающий архитектурные особенности кластерных систем обработки информации, обеспечивающий 90% загрузку узлов кластера и ее динамическую балансировку.

5. На языке С++ с использованием библиотеки MPI разработан программный модуль автоматического составления расписания занятий в ВУЗе, адаптированный для кластерных вычислительных систем с распределенной памятью и обеспечивающий 100% расстановку занятий в автоматическом режиме. На указанный программный модуль получено свидетельство об официальной регистрации.

6. Исследования предложенного алгоритма и разработанной на его основе программы, проведенные на вычислительном кластере МИЭТ-2008, подтвердили, что эффективность использования узлов кластера в процессе решения оптимизационной задачи достигает величины 90-96%.

1. Подиновский В. В. Парето-Оптимальные решения многокритериальных задач / В. В. Подиновский, В.Д. Ногин. М.: Наука, 1982. - 254 с.

2. Блюмин C.JI. Введение в математические методы принятия решений / C.JI Блюмин, И.А. Шуйкова. Липецкий Государственный Педагогический Институт, Липецк 1999, 100стр.

3. William Н. Press, Saul A. Teukolsky, William Т. Vetterling, Brian P. Flannery "Numerical recipes in C: the art of scientific computing", Second Edition, Cambridge University Press, 1992, 994 стр

4. Dimitris Bertsimas, John Tsitsiklis "Simulated Annealing", Statistical Science, Vol.8,No l,p. 10-15, 1993.

5. Безгинов A.H Обзор существующих методов составления расписаний / А.Н. Безгинов, С.Ю. Трегубов // Информационные технологии и программирование выпуск 2(14), 2005г, с 5 — 19.

6. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / под редакцией Ю.Ю. Тарасевича. Астрахань: Издательский дом «Астраханский университет», 2007г, 87 стр.

7. Michel Gendreau "An Introduction to Tabu Search", 2002

8. Available: http://www.ifi.uio.no/infheur/Bakffrunn/Intro to TS Gendreau.htm

9. Маляренко Илья Планирование и оптимизация: от Вергилия до. APS-системы // PC WEEK. 2006г. Электронный ресурс] - Режим доступа: http://www.pcweek.m/idea/article/detail.php?ID=72912

10. Дискретная математика. Электронный ресурс] — Режим доступа: http://pgap.chat.ru/zap/zap251 .htm

11. Rong Qu, Edmund Burke, Barry McCollum, Liam T.G. Merlot and Sau Y. Lee "A Survey of Search Methodologies and Automated Approaches for Examination Timetabling" // Computer Science Technical Report No. NOTTCS-TR-2006-4

12. Ахо Альфред, Хопкрофт Джон, Ульман Джефри Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Издательский дом «Вильяме». — 2007. -400с. ISBN 5-8459-0122-7

13. Scheuermann, Bemd Ant Colony Optimization on Runtime Reconfigurable Architectures. : Dissertation . 20.12.2005.

14. Available: http://digbib.ubka.uni-karlsruhe.de/volltexte/1000003803

15. Муравьиный алгоритм. Электронный ресурс]http://ru.wikipedia.org/wiki/%D0%9C%D 1 %83%D 1 %80%D0%B0%D0%B2%D 1 %8C%D0%B8%D0%BD%D 1 %8B%D0%B9 %D0%B0%D0%BB%D0%B3%D0 %BE%D 1 %80%D0%B8%D 1 %82%D0%BC

16. Субботин C.A. Часть III. Интеллектуальные мультиагентные методы (Swarm Intelligence) / C.A. Субботин , Ан. А. Олейник., Ал. А. Олейник 2006.

17. Chin Soon Chong A Bee Colony Optimization Algorithm to Job Shop Scheduling / Chin Soon Chong, Malcolm Yoke Hean Low, Appa Iyer Sivakumar, Kheng Leng Gay. // Simulation Conference, 2006. WSC 06. Proceedings of the Winter, pages 1954-1961.

18. Ногин В.Д. Проблема сужения множества Парето: подходы к решению. // Искусственный интеллект и принятие решений № 15 2008, стр. 98-112.

19. В. Н. Шевченко, Н. Ю. Золотых. Линейное и целочисленное программирование. // Учебное пособие. Изд. Нижегородского Государственного Университета.- Нижний Новгород.- 2002.

20. Яндыбаева Н.В. Генетический алгоритм в задаче оптимизации учебного расписания. // Современные наукоемкие технологии — Изд. ООО Издательский дом «Академия Естествознания», №11, 2009, стр. 97-98.

21. Любченко A.B. Автоматизация процесса составления расписания занятий для кафедры ВУЗа. // Системи обробки інформації. Харків: ХВУ. -2007-№3 (61),-С. 150-152.

22. Береговых Ю. В., Васильєв Б. А., Володин Н. А. Алгоритм составления расписания занятий. // Искусственный интеллект. — №2. — 2009. С. 50-56.

23. Шаповалов Т.С., Пересветов В.В. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем. // Вычислительные методы и программирование. — Т. 10 — 2009. — С. 13-29.

24. Ерунов В. П., Морковин И. И. Формирование оптимального расписания учебных занятий в ВУЗе. // Вестник ОГУ. 3. - 2001. - С. 55-63.

25. Каргапольцев С. К., Лашук Н. В. Применение искусственных нейронных сетей в задаче составления расписания учебных занятий. // Электронный источник, http://www.iumal.org/articles/2008/inf73.html

26. Веревкин В. И., Исмагилова О. М., Атавин Т. А. Автоматизированное составление расписания учебных занятий вуза с учетом трудности дисциплин и утомляемости студентов. // Журнал «Доклады Томского Государственного

27. Университета систем управления и радиоэлектроники». №1 (19) — часть 1. — 2009.-С. 221-225.

28. Расписание занятий. Описания программ и закачка пробных версий. Электронный ресурс]

29. Режим доступа: http://soft.israelmfo.ru/programs/education/223

30. Басыров P. AVTORcKoe составление расписаний. Электронный ресурс] Режим доступа: http://www.softkev.info/reviews/review647.php

31. Расписание занятий Серия компьютерных программ. Электронный ресурс]

32. Режим доступа: http://www.raspisanie.com/

33. Университет 3.2.0.711. Электронный ресурс] Режим доступа: http://allsoft.ru/programpage.php7grp~l 1148

34. Scheduling Software for School and University Timetables Режим доступа: http://www.mimosasoftware.com/

35. Ректор-Программа Расписание: Продукты. Электронный ресурс] Режим доступа: http://www.rector.spb.ru/

36. Найханова JI. В. Методы и алгоритмы принятия решений в управлении учебным процессом в условиях неопределенности: Монография. / Л. В. Найханова, С. В. Дамбаева; Улан-Удэ: Изд-во ВСГТУ, 2004. - 164 с.

37. Жилина Г.А. «Методическое пособие и инструкции по составлению расписаний на ЦВМ» / Г.А. Жилина, М. В. Медведский, Л.С. Писаренко; Минское высшее инженерное зенитное ракетное училище противовоздушной обороны, 1976. 92с.

38. Давыдов С. В. Система автоматического построения расписания учебных занятий. / С. В. Давыдов Электронный ресурс]

39. Режим доступа: http://davidovsv.narod.ru/schedule/index.html

40. Черноруцкий И.Г. Методы принятия решений / И.Г. Черноруцкий. -СПб.: БХВ-Петербург. 2005. -416с. ISBN 5-94157-481-9

41. Богачёв К. Ю. Основы параллельного программирования. / К. Ю. Богачёв. М.: БИНОМ. Лаборатория знаний, 2003. - 342 С. ISBN 5-94774037-0

42. Гергель В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие / В. П. Гергель, Р. Г. Стронгин, Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 С.

43. Multiprocessing. Available: http://en.wikipedia.org/wiki/Multiprocessing

44. SISD. Available: http://en.wikipedia.org/wiki/SISD

45. MISD. Available: http://en.wikipedia.org/wiki/MISD

46. SIMD. Available: http://en.wikipedia.org/wiki/SIMD

47. MIMD. Available: http://en.wikipedia.org/wiki/MIMD

48. Классификации архитектур вычислительных систем. Электронный ресурс]

49. Режим доступа: http://www.parallel.ru/computers/taxonomy/

50. Ananth Grama Introduction to Parallel Computing, Second Edition. / Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, Addison Wesley, 2003. -856 C.

51. Воеводин Вл. В. Параллельная обработка данных / Вл. В. Воеводин. Электронный ресурс] Режим доступа: http://www.parallel.ru/parallel/vvv/

52. Duncan A. Grove Performance Modelling of Message-Passing Parallel Programs. PhD Thesis, University of Adelaide, 2003. 313p.

53. Посыпкин M.A. Основы параллельного программирования / M.A. Посыпкин. Электронный ресурс] Режим доступа: http://posmik.narod.ru/curs/Vvedenie.2006.10.23 .ppt

54. Карпов А. Введение в проблематику разработки параллельных программ. / А. Карпов. Электронный ресурс] Режим доступа: http://www.viva64.eom/ru/a/0016/

55. Гергель В.П. Теория и практика параллельных вычислений / В.П. Гергель. Электронный ресурс]

56. Режим доступа: http://www.intuit.rii/departtTient/calculate/paralltp/4/l.html