Содержание к диссертации
Введение
Глава 1. Основные понятия и формальная постановка задачи 11
1.1. Модель
1.2. Оценка погреишости и времени составления расписания 12
1.3. Задачи большой размерности 14
Глава 2, Характеристика задачи я существующие методы ее решения 15
2.1. Результаты для задач минимизации длины расписания 15
2.2. Характеристик алгоритмов составления расписаний 16
2.3. Анализ существующих точных и приближенных алгоритмов 18
2.4. Анализ существующих параллельных стратегий 29
Глава 3. Алгоритмы составления расписания без прерываний 38
31- Алгоритм «Прщессор с ранним окончанием первым» 38
3.2. Вероятностный алгоритм 39
3.3. Лсевдополиномиальные алгоритмы 42
3.3.1. Различные интерпретации псевдополиномиальных алгоритмов 42
3.3.2. Псевдопопиномиальный алгоритме поиском в ширину 44
3.3.3. Псевдополиномиальный алгоритм с поиском в глубину 46
3.4. Метод агрегирования 41
3.4.1. Формальное описание 48
3.4.2. Задача составления расписания п работ на m идентичных процессорах 50
3.4.3. Вспомогательные алгоритмы 52
3.4.4. Агрегирующие алгоритмы 54
3.5. Анализ возможности совместного использования методики агрегирования с другими алгоритмами 55
Глава 4. Алгоритмы с гарантированной точностью 59
4. L Псевдополиномиальный алгоритм с поиском в глубину 59
4.2. Вероятностный алгоритм 62
4.3. Алгоритм «Процессор с ранним окончанием первым» „ 63
4.4. Алгоритм «Самая длинная работа первой» 65
Глава 5. Результаты для некоторых частных случаев 66
5.1 Длительности работ, заданные арифметической прогрессией 66
5.2. Длительности работ, близкие к арифметической прогрессии 68
53. Фиксированное число процессоров 68
Глава 6. Параллельное выполнение вычислений 70
6.1. Комбинированный псевдополиномиальныи алгоритм 70
6.2. Параллельное построение дерет решения 71
Глава 7. Результаты экспериментов 78
7. /. Экспериментальная система 78
7.2. Таблиг(ы и графики 79
Заключение 95
Список использованных источников
- Оценка погреишости и времени составления расписания
- Анализ существующих точных и приближенных алгоритмов
- Различные интерпретации псевдополиномиальных алгоритмов
- Комбинированный псевдополиномиальныи алгоритм
Введение к работе
Актуальность и характеристики задачи
Задачи составления расписания возникают при проектировании и эксплуатации автоматизированных систем обработки информации и управления. Такие автоматизированные системы функционируют при непосредственном взаимодействии с внешней средой, и должны за кратчайшее время вернуть среде результаты обработки в виде корректирующих воздействий или в виде сообщений пользователю. Необходимость в корректных и полных математических моделях и быстрых точных алгоритмах, составляющих многопроцессорные расписания, часто возникает в задачах распределенных вычислений в реальном времени и задачах оперативного управления на основе обработки поступающих в реальном времени данных.
Для иллюстрации большой практической значимости рассматриваемых задач и важности эффективных алгоритмов их решения можно привести следующие примеры: системы противоракетной обороны; системы управления ядерными реакторами на АЭС; бортовые системы при испытаниях и управлении летательными аппаратами и космическими кораблями; организация расписаний в современных аэропортах и многие другие.
В наиболее общей формулировке задача составления расписания состоит в следующем, С помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочения заданий, оптимизирующий желаемую меру эффективности. В качестве мер эффективности обычно рассматриваются длина расписания и среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том смысле,
что вся информация, на основе которой принимаются решения об упорядочении, известна заранее.
Исторически появлению дискретных методов оптимизации предшествовало развитие методов линейного программирования. Высокая вычислительная производительность этих методов позволила предполагать, что на их основе могут быть разработаны эффективные методы решения дискретных задач оптимизации. Однако вычислительные эксперименты не подтвердили это предположение. Принципиальные трудности решения дискретных задач показала и теория вычислительной сложности алгоритмов [1, 2, 3, 4]. В соответствии с этой теорией оценка эффективности производится по наихудшему случаю. Так как для большинства дискретных задач оптимизации в наихудшем случае не известен точный алгоритм кроме перебора всех или почти всех вариантов, то полученные оценки являются неудовлетворительными с точки зрения практического использования.
При построении расписания работы детерминированной системы обслуживания актуальна задача понижения размерности, состоящая в преобразовании исходной системы путем группирования требований и назначения укрупненным требованиям всех тех характеристик, которые содержала исходная система обслуживания. Такое преобразование системы называется агрегирование.
Помимо того, что понижение размерности системы обслуживания ускоряет в дальнейшем процедуру построения допустимого расписания ее работы, оно необходимо и для решения других проблем. В современных вычислительных системах со стороны операционной системы (ОС) нередко выдвигаются количественные ограничения, которые необходимо учитывать при подготовке пакета прикладных программ.
Ограничениями ОС являются: количество приоритетных уровней доступных диспетчеру ОС, уровень мультипрограммирования, объемы оперативной памяти, выделяемые программной единице и т.п. Агрегирование детерминированной системы обслуживания позволяет
снизить количество управляемых программных единиц, тем самым выполнить соответствующие требования ОС,
Понижение размерности системы приводит также к уменьшению накладных расходов на организацию обслуживания, которые, например, согласно некоторым исследованиям [5] в вычислительных системах реального времени достигают 70% (в отдельных случаях и выше) времени работы центрального процессора.
Кроме методов агрегирования, в последнее время все большую популярность стали получать методы параллельного составления расписаний, когда одни параллельные вычислительные системы используются для составления расписания заданий для других параллельных систем. На данный момент существует достаточно большое количество различных архитектур параллельных вычислительных систем, и каждая из них требует специально адаптированных алгоритмов для эффективного использования. В данной работе разработан новый алгоритм для одной из параллельных архитектур - параллельный вычислительный кластер.
При исследовании задачи мы полагаем, что на процесс составления расписания влияют ограничивающие факторы возможностей вычислительной системы, на которой осуществляется упорядочение. Основными ограничивающими факторами являются время выполнения процесса составления расписания и объем используемой вычислительной памяти. Будем называть задачами большой размерности те, решение которых нарушает хотя бы одно из ограничений используемой вычислительной системы.
В работе используются многие сходные термины без их формального уточнения. Например, такие слова, как «работы», «задания», «программы» (в вычислительной машине) и «заявки», могут считаться эквивалентными. Понятие «ресурсы» может быть отнесено к машинам, накопителям и, наиболее часто, к процессорам. По отношению к соответствующим ресурсам работы могут быть совершены, просчитаны, выполнены, записаны в память
или обслужены. Вместо слова «алгоритм» могут использоваться такие слова, как «правило», «процедура». Такие слова и выражения, как «составление», «упорядочение», «распределение» и «назначение», используются как синонимы или аналоги, в зависимости от контекста.
Цели и новизна работы
Целями настоящей диссертационной работы являются:
построение математических моделей многопроцессорных систем без дополнительных ограничений по ресурсам, выполнение заданий в которых осуществляется без прерываний;
разработка и анализ точных и эвристических алгоритмов решения задачи поиска оптимального расписания в этих системах;
разработка нового подхода к решению задачи составления расписания путем агрегирования заданий системы и решения полученной таким образом задачи меньшей размерности;
разработка параллельных алгоритмов решения задачи составления расписания большой размерности с высоким коэффициентом эффективности и линейной функцией изоэффективности;
получение аналитических ограничений на точность расписания, получаемого эвристическими алгоритмами, и на время выполнения алгоритмов, разработанных в рамках данной работы;
подтверждение полученных результатов экспериментальными данными и создание банка вычислительных результатов, которые могут быть в дальнейшем использованы другими исследователями для сравнения практической эффективности новых алгоритмов.
Оценки алгоритмической сложности для многих задач рассматриваемого класса (см. Приложение 1) известны уже давно, однако, в литературе встречается сравнительно мало специализированных алгоритмов решения этих задач и экспериментальных результатов их работы. В связи с
этим, наравне с созданием новых алгоритмов, в рамках работы проведено большое число вычислительных экспериментов и, для сравнения, приведены результаты переборного алгоритма и широко используемых для других классов задач жадных методик и алгоритма имитации отжига.
Методы исследований
В данной диссертационной работе используются методы теории расписаний, теории графов, оптимизации, дискретной математики, теории алгоритмов и теории сложности, а также математического моделирования.
В основу работы легли аналитические исследования, для каждого из утверждений было получено полное и достоверное доказательство. Также, для подтверждения выводов, были разработаны комплексы вычислительных программ, было проведено большое количество экспериментов, результаты усреднялись для получения статистически достоверных данных.
Практическая ценность работы
Разработанные в диссертации алгоритмы построения оптимальных и ^-приближенных расписаний могут быть рекомендованы к использованию при проектировании, анализе и эксплуатации аппаратно-программных комплексов систем реального времени, применяемых при разработке, испытаниях и эксплуатации сложных технических объектов, а также в системах оперативного мониторинга.
Апробация работы
Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на:
- XLV, XLVII и IL научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2002,2004,2006);
X, XI и XII международных конференциях "Проблемы управления безопасностью сложных систем'* (Москва, 2002, 2003,2004);
IV международной конференции по исследованию операций (Москва, 2004);
II Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005);
научных семинарах кафедры математических основ управления Московского физико-технического института (государственного университета);
научных семинарах сектора проектирования систем реального времени Вычислительного центра им. АЛ. Дородницына Российской Академии Наук,
По материалам диссертации опубликовано 12 печатных работ.
Структура работы
Работа состоит из данного введения, семи глав и заключения.
В главе 1 вводится формальная постановка и описание задачи. Формализуются термины, которые используются далее в работе. В главе 2 приводится анализ исследований рассматриваемого и смежных классов задач, проведенные другими учеными. Проводится исследование описанных в литературе алгоритмов, которые могут использоваться для рассматриваемого класса задач, приводятся их сильные и слабые стороны. Выделен ряд наиболее перспективных алгоритмов и методик, которые были использованы для сравнения с разработанными в рамках данной работы алгоритмами. Глава 3 посвящена алгоритмам, разработанным в рамках данной работы: их формальному описанию, определению алгоритмической сложности, В главе 4 для разработанных ^-приближенных алгоритмов определяется и доказывается их гарантированная точность. Глава 5 посвящена некоторым интересным математическим фактам, относящимся к
разработанным алгоритмам, которые были определены в процессе этой диссертационной работы. В главе 6 исследуется параллельный процесс построения расписания. В главе 7 собраны и структурированы все полученные вычислительные результаты, приводится описание системы, которая использовалась для проведения экспериментов.
Оценка погреишости и времени составления расписания
Рассматривая различные алгоритмы решения одной и той же задачи, полезно проанализировать, сколько вычислительных ресурсов они требуют (время работы и память), и выбрать наиболее эффективный.
Время составления расписания зависит от количества работ и процессоров: чем их больше, тем больше может понадобиться времени. Будем изучать зависимость времени работы от размера входа (впрочем, для некоторых рассматриваемых алгоритмов важен не только размер входа, но и последовательность работ: например, если набор работ упорядочен по длительности, то время работы алгоритма СДРП из раздела 3-43 будет меньше).
Важно отметить тот факт, что время работы в худшем и лучшем случае могут сильно различаться. В рамках данной диссертации будет изучаться время работы в худшем случае которое определяется как максимальное время работы алгоритма для входов данного размера. Это связано с тем, что, зная время работы в худшем случае, мы можем гарантировать, что выполнение алгоритма закончится за некоторое время, даже не зная, какой именно вход (данного размера) подается, В некоторых случаях нас будет интересовать также среднее время работы алгоритма на входах данной длины. Конечно, эта величина может зависеть от выбранного распределения длительностей работ, и на практике реальное распределение может отличаться от предполагаемого. При проведении экспериментов, рассматривалось случайное равномерное распределение длительностей работ на некотором промежутке, который варьировался. Кроме того, дополнительно, проводились эксперименты на некоторых выделенных распределениях.
Для эвристических алгоритмов наравне со временем работы также важна величина погрешности - отклонение значения показателя эффективности расписания от оптимального значения, К сожалению, далеко не для всех задач возможно вычислить оптимальное решение, поэтому и точное определение погрешности зачастую бывает затруднено- В таких случаях, обычно, определяют отклонение от некоторой нижней оценки показателя эффективности расписания. Однако получаемая таким образом погрешность является показателем не только алгоритма, но и точности использованной нижней оценки, и не всегда хорошо характеризует работу алгоритма.
В рамках данной работы для задач, оптимальное решение для которых не известно, использовалась аналитическая нижняя оценка длительности расписания: В [6] вводится следующее понятие задач большой размерности, которое применяется и в этой работе.
Пусть - множество параметров конкретной задачи (число работ, процессоров, длительности работ). Обозначим через T\S) время решения этой задачи на конкретной вычислительной системе, V(S) - память, необходимая для решения, 7Q И VQ - соответственно время и память, выделенные для решения задачи.
Будем говорить, что рассматриваемая задача является задачей большой размерности, если не выполнено хотя бы одно из неравенств. Г(5) Г0) V(S) Vr
Такое определение обладает, однако, той особенностью, что определить, является ли задача задачей большой размерности можно только в процессе решения задачи. При этом нет простых способов определить принадлежность задачи к этому классу. Так, например, большое значение количество работ и процессоров в задаче не всегда означает задачу большой размерности, Так, например, если длительности работ задаются арифметической прогрессией, и число работ кратно 2т (где т - число процессоров), то точное решение задачи может быть найдено за время 0(1) при любых 5, удовлетворяющих этим условиям. Доказательства этого факта и определение погрешности и алгоритмической сложности алгоритма СДРП при длительностях работ, задаваемых арифметической прогрессией или близких к ней приведены в разделе 5.1.
В работе [7] также проводится анализ необходимых вычислительных ресурсов (время, память) при решении задач большой размерности на последовательных вычислительных машинах. В работах [8, 9, 10] проведено большое исследование, посвященное выявлению задач большой размерности и их параметризации.
В общем случае термин «сложность» алгоритма решения какой-либо задачи связывают только со временем получения решения, выраженного в виде функции от длины входа, т. е. количества битов, необходимых для задания конкретного набора параметров задачи. Мы будем определять сложность в виде функции от основных параметров задачи, в первую очередь от количества заданий и, В ряде ситуаций это является существенным упрощением, которое, однако, вполне допустимо для наших целей. (Мы попросту полагаем, что время считывания и преобразования чисел всегда постоянно и не зависит от их длины, что оправдано с точки зрения практики.)
Детальное описание функций, определяющих сложность, зависит от особенностей алгоритма и структуры данных и не входит в сферу нашего рассмотрения. Поэтому мы будем пользоваться символом 0(-% обозначающим зависимость по порядку величины, ограничиваясь тем самым описанием свойств, определяющих поведение функции на бесконечности. Так, если мы говорим, что алгоритм имеет сложность 0(п), то это просто означает, что существует постоянная с, такая, что функция сп2 ограничивает сверху время выполнения алгоритма как функции от п.
Алгоритм, сложность которого ограничена полиномом от и, называется полиномиальным алгоритмом или алгоритмом, работающим полиномиальное время. Соответствующая задача называется полиномиально разрешимой. В дальнейшем мы будем называть алгоритм эффективным, если он полиномиален. Для такого определения имеются веские основания с практической точки зрения, особенно при больших значениях я. В этой связи необходимо отметить, что задачи упорядочения, которые будут рассмотрены, относятся или могут быть сведены к конечным задачам в том смысле, что множество их решений конечно
Анализ существующих точных и приближенных алгоритмов
Случайный и исчерпывающий поиск. Быстродействие алгоритмов случайного поиска обычно является функцией отношения количества решений к количеству так называемых хороших решений. Чаще это отношение мало, потому что большинство задач имеют очень жесткие ограничения на качество решения. Поэтому случайный поиск хорошего расписания подобен поиску иголки в стоге сена. Классические эвристические поисковые методы работают достаточно эффективно для задач малой размерности, однако, при увеличении пространства поиска время работы таких алгоритмов сушественно увеличивается. Классический эвристический поиск часто сравнивают с работой экспертов-людей. По той же причине можно ожидать, что будет сравнительно быстро найден локальный минимум, В книгах [11, 12, 13] демонстрируется применение достаточно эффективных алгоритмов исчерпывающего поиска к задаче составления расписаний, однако эти алгоритмы перестают быть применимыми при увеличении размерности задачи. Математической основой методов случайного поиска служит итерационный процесс: Хк+1=Х +а Л , = 0Л»м где ак - величина шага, = (,...,&) некоторая реализация гс-мерного случайного вектора
Ненаправленный случайный поиск (метод Монте-Карло) заключается в многократном случайном выборе допустимых вариантов решений и запоминании наилучшего из них.
Все алгоритмы направленного случайного поиска без самообучения делают шаг от текущего значения А оптимизируемых параметров. Известны следующие алгоритмы направленного случайного поиска без самообучения [14]: алгоритм с парной пробой, алгоритм с возвратом при неудачном шаге, алгоритм с пересчетом при неудачном шаге, алгоритм с линейной экстраполяцией, алгоритм наилучшей пробы, алгоритм статистического градиента.
Алгоритмы случайного направленного поиска с самообучением заключаются в перестройке вероятностных характеристик поиска, т.е. в определенном целенаправленном воздействии на случайный вектор Он уже перестает быть равновероятным и в результате самообучения приобретает определенное преимущество в направлениях наилучших шагов. Это достигается введением вектора памяти Р -(рк,рк1іш.Гірк), где рк вероятность выбора положительного направления поу-ой координате на &-ом шаге. Алгоритм рекуррентно корректирует значение компонентов этого вектора на каждой итерации в зависимости от того, насколько удачным/неудачным (изменилось значение целевой функции) был сделанный шаг. Описание и анализ различных способов коррекции вектора г приведены в [14],
Дня алгоритмов случайного поиска можно выделить следующие особенности: слабая адаптация (или ее отсутствие) к поведению оптимизируемой функции для алгоритмов ненаправленного и направленного случайного поиска без самообучения; низкая скорость сходимости, уменьшающаяся с возрастанием количества оптимизируемых параметров. Обзор известных на данный момент методов поиска, а также результаты некоторых новых алгоритмов приведены в работах [15, 16, 17].
Математическое программирование. Математическое программирование - это семейство методов оптимизации функций с независимыми ограничениями. Однако этот метод применим только для задач малой размерности. Примеры таких подходов, существующих для задач составления расписаний, можно найти в [18] (линейное целочисленное программирование) и [19].
Динамическое программирование. Основная идея этого метода заключается в замене одновременного выбора большого количества параметров системы поочередным их выбором. Многомерная задача оптимизации сводится к многошаговой задаче меньшей размерности, В основу метода положены принципы оптимальности и инвариантного погружения [20]. Для этого метода также показана его неэффективность для случая задач большой размерности [21
Различные интерпретации псевдополиномиальных алгоритмов
Дадим следующую интерпретацию рассматриваемой задачи. Необходимо решить оптимизационную задачу вида " —» Ід t=\ - min , где
Для произвольного пектора a (altCl2 ..,apt)t = max Ctk - величина максимальной компоненты. pf -(0,-., .,,0) - шхерный вектор, В теории оптимизаций задача а подобной формулировке называется «задачей об упаковке». Однако несложна заметить» что «задача об упаковке» имеет однозначное еоотнетстаие с рассматриваемой задачей: достаточно провести соответствие вектора р: =(0r r, ,.,,G) о работой Т где &-шжер процессора, ш который назначиш ЖЕ работа. Суть йсе&дополиномиалыюго алгоритма состоит в поеледомтмьном построении и переборе вариантов с дополнительным условней отсева, при котором да рассмотрения выбрасываются варианты, в процесс ! їіоо фоеиия которых сумма векторов превысила по &шш#Ми6о из компонент оїфедсленньш заранее директашый интервал
Друїшз интерпретация алгоритми связана 0 построением дерева расписаний. Вершены доревзі и такай щ рпретшри еоотщтстру от работам, a pefipa дерева — наїжачений работы на процессу При зпш в су каждого ребра дерма ставится н ШОГВЙТСТЙИР длительность выполнения определенной работы на соотвегствушщем процессоре. Так, например, в щ чж? рассматриваемом па рисунке 3, вершина с порядковым номером генерирования 1 соответствует назначению первой работы на первый процессор, а вершины с порядковым номером 2 соответствует расписанию, при котором первая вершина назначена на второй процессор. Веса ре бер равны соответственно тп и г12. При генерадии новой вершины проверяется условие, согласно которому сумма весов «со-направленных» ребер по полученной ветви дерева не должна превышать директивного интервала. Если это условие нарушается, то соответствующая вершина не создается.
Работу алгоритма, решающего поставленную задачу, опишем следующим образом- Вычислим величину В, которую будем называть директивным сроком. Число В можно получить, например, с помощью описанных выше алгоритмов ГТРОП или ВА. Затем будем рассматривать т-мерный куб со стороной В (в векторной интерпретации). Необходимо выбрать вектора pf так, чтобы каждая компонента вектора J] Д не - превосходила В. Под выбором вектора pt будем понимать выбор процессора, на который назначена работа 7}, что однозначно задает вектор. Выбор осуществляем путем построения множества точек m-мерного пространства, для каждой из которых на 1-м уровне проверяем, принадлежит ли точка т-мерному кубу со стороной В (рис, 2). Если условие не выполнено, то точка исключается из дальнейшего рассмотрения. Формализуем алгоритм по шагам.
1. Строим первые т точек w-мерной решетки: ( ,0,.,.,0),(0, 2,...,0),...,(0,0,..., ). Полагаем / = 1, а все указанные точки активными.
2. Исключаем из списка активных точек те, которые не принадлежат т-мерному кубу со стороной 5. Если / - щ то переходим к п. 4. В противном случае переходим к п. 3.
3. Полагаем / = / + 7, Каждую активную точку (дь &2, ..., яД полученную на шаге /- 1, исключаем из списка активных точек и строим новые активные точки (а}+т1иа2, ...,ат\(аиа2+тп, ---, ), ...,(аиаъ .,., am+r!m). Переходим к п. 2.
4. Множество решений найдено. Из числа активных точек находим точку, соответствующую оптимальному решению. Завершаем работу алгоритма.
Таким образом, в результате выполнения алгоритма определяются все расписания с длиной, не превосходящей В, и из них выбирается оптимальное. Отметим, что для шага 2 важно, чтобы множество активных точек не было пусто, что верно, т.к. существует хотя бы одно решение, найденное с помощью алгоритма ПРОП.
Из описания алгоритма видно, что на первом шаге выполняется OQn) действий с точками m-мерного пространства (всего 0(т ) операций), затем на этапах 2 и 3 алгоритма для каждой из активных точек т-мерного пространства выполняется по 0(т) операций. Поскольку в худшем случае число вершин ветвления совпадает с числом узлов целочисленной решетки в /«-мерном кубе со стороной В (т.е. с числом (В+1)т в силу целочисленности задачи), то вычислительная сложность пунктов 1-3 алгоритма составляет 0(т (В±1)т).
Комбинированный псевдополиномиальныи алгоритм
Для решения задачи составления расписаний большой размерности предлагается следующий алгоритм, С помощью эвристического алгоритма строится расписание, длина которого So берется за оценку сверху длины итогового расписания. На следующем шаге проводится декомпозиция задачи на подзадачи в соответствии с полученным расписанием. Для этого проводится разбиение процессоров на группы с некоторым задаваемым параметром М(М равно количеству групп, на которое разбивается множество процессоров) таким образом, что в первую группу попадает [т/2М\ наиболее загруженных процессоров (суммарное время выполнения работ, на которых наибольшее), и столько же наименее загруженных. Аналогично строятся остальные группы из оставшихся процессоров. Затем производится декомпозиция множества работ. Оно также разбивается на М групп, и в каждую группу попадают те работы, которые были назначены эвристическим алгоритмом на процессоры из соответствующей группы. Каждая из полученных таким образом подзадач решается с помощью описанного выше псевдополиномиального алгоритма.
На рис, 6 схематически изображено распределение 8 работ по 4 процессорам, полученное с помощью алгоритма ПРОП Если рассмотреть случай декомпозиции исходной задачи на две подзадачи, то первая подзадача будет «распределить работы t\, t%, t4, t$ по процессорам 1 и 4»5 а вторая подзадача - «распределить работы Хъ h, t h по процессорам 2 и 3». Каждая из полученных подзадач будет затем решена с помощью псевдополиномиального алгоритма.
Если в исходной задаче требуется получить расписание с заданной точностью, то на первом шаге для построения первоначального решения вместо эвристического алгоритма можно использовать псевдополиномиальный алгоритм с требуемой точностью.
Определение эффективности параллельной реализации алгоритмов Для определения эффективности алгоритмов, основанных на параллельном построении дерева решений, рассматривают (например, в исследованиях, проведенных в [49]) следующие величины.
1. Размерность задачи W (для рассматриваемого класса задач построения дерева решений это количество вершин в дереве).
2. Коэффициент ветвления Ъ (среднее число потомков у вершин дерева решений).
3. Размер параллельной вычислительной системы q (число процессоров, используемых для проведения параллельной работы алгоритма),
4. Времена параллельной и последовательной работы алгоритма: Tq (время выполнения алгоритма на q процессорах) и Т\ (время последовательного выполнения алгоритма). Будем предполагать, что Т\ пропорционально W,
5. Время проведения вычислений Гвыч (сумма времен, затраченных всеми процессорами для проведения вычислений). Будем предполагать, что количество вычислений при параллельном и последовательном выполнении в среднем одинаково. Поэтому значения величины Т ыч Для Ч процессоров и для одного процессора совпадают и равны Т\.
6. Время взаимодействия Тю (сумма времен, затраченных всеми процессорами на взаимодействие с другими процессорами с целью получения работы (сюда также включается простой в случае, если работы больше нет). Поскольку каждый процессор в любой момент времени либо проводит вычисление, либо ожидает новую работу, то Тві + ГВЬ1Ч = qxTr
7 1, Прирост в скорости iS = — (отношение, показывающее уменьшение времени работы алгоритма при использовании параллельной вычислительной системы).
8. Эффективность Е (прирост в скорости, отнесенный к числу параллельных процессоров; демонстрирует эффективность использования параллельной вычислительной системы): EJ= т, = тшч = 1 т выч
9. Единица вычислительного времени /выч (среднее время, затрачиваемое на ветвление одной вершины дерева решений).
10. Единица времени взаимодействия UB1 (среднее время взаимодействия между процессорами вычислительной системы для получения новой работы).
Эффективность и прирост по скорости, достигаемые параллельными вычислительными алгоритмами, определяются архитектурой параллельной вычислительной системы, алгоритмом распределения работ, количеством процессоров и размерностью системы. При заданной размерности системы W увеличение числа процессоров q приводит к уменьшению эффективности в силу того, что Гвэ увеличивается, а Тш остается прежней. При заданном q увеличение W улучшает эффективность (в качестве примера см. кривую прироста скорости для архитектуры Intel Hypercube в [48]).
