Содержание к диссертации
Введение
1. Введение 4
1.1. Цели и задачи 4
1.2. Постановки задачи Штейнера 5
1.3. Применение 6
1.3.1. VLSI-проектирование 6
1.3.2. Восстановление филогенетических деревьев 8
1.3.3. Интерактивная телекоммуникация 9
1.4. Описание работы по главам 10
1.5. Основные определения и обозначения 13
2. Состояние дел 15
2.1. Точные алгоритмы 15
2.1.1. Алгоритм динамического программирования 16
2.1.2. Сведение к задаче линейного программирования 18
2.2. Приближенные алгоритмы 21
2.2.1. Алгоритм Такахаши-Мацуямы 22
2.2.2. Приближенные алгоритмы основанные на линейном программировании 23
2.2.3. Жадные алгоритмы 28
3. Алгоритм /с-кластерной оптимизации 33
3.1. Определение кластеров в графе 34
3.1.1. Построение опорного дерева 34
3.1.2. Разбиение на кластеры 35
3.2. Построение деревьев Штейнера на кластерах 37
3.3. Улучшение деревьев Штейнера на кластерах 38 3.4. Нахождение промежуточного полного дерева Штейнера 38
3.5. Улучшение промежуточного дерева Штейнера 39
3.6. Теорема о вычислительной сложности 40
4. Приближенный метод 3 для задачи Штейнера на евклидовых графах 47
4.1. Алгоритм А поиска кратчайшего пути 47
4.2. Задача Штейнера на концентрических окружностях 50
4.3. Алгоритм S на евклидовых графах 53
4.3.1. Построение приближенного решения 53
4.3.2. Построение множества терминальных подмножеств. Наивный метод 54
4.3.3. Построение множества терминальных подмножеств. Метод «концентрических окружностей» 56
4.3.4. Построение множества терминальных подмножеств. Обобщенный метод 58
4.3.5. Теоретические результаты 59
5. Вычислительные оптимизации 62
5.1. Общий обзор 62
5.2. Особенности реализации однопоточных алгоритмов 63
5.2.1. Алгоритм динамического программирования 63
5.2.2. /с-кластерный приближенный алгоритм 73
5.2.3. Приближенный метод S на евклидовых графах 76
5.3. Параллелизация алгоритмов 81
5.3.1. Параллелизация точного алгоритма решения 5.3.2. Параллелизация алгоритма / -кластерной оптимизации 89
5.3.3. Параллелизация алгоритма аппроксимации S 91
6. Вычислительные результаты 93
6.1. Сравнение эффективности структур, реализующих приоритетную очередь 93
6.2. Сравнение эффективности -кластерного метода с другими известными 95
6.3. Сравнение эффективности метода S с другими известными 97
6.4. Сравнение быстродействия однопоточных и параллельных реализаций методов 102
6.4.1. Метод динамического программирования 102
6.5. Метод к-кластерной оптимизации 104
6.6. Метод 5 105
7. Результаты и выводы 108
- VLSI-проектирование
- Сведение к задаче линейного программирования
- Улучшение деревьев Штейнера на кластерах 38 3.4. Нахождение промежуточного полного дерева Штейнера
- Алгоритм динамического программирования
Введение к работе
Данная работа ПОСВЯ1Ц6Н cL разработке приближенных методов решеНИЯ 3 CLrZI^ cL"ЧИ Штейнера на ориентированных графах, а также некоторых ее частных постановок, их теоретическому исследованию и обоснованию, программной реализации, оптимизации быстродействия с учетом текущего развития вычислительной техники, а также эмпирическому подтверждению их применимости.
Задача Штейнера на ориентированных графах определяется следующим образом:
Пусть G(M, N) — ориентированный граф с заданной на дугах функцией d : N ^ R+ .В M выделена начальная вершина b и множество терминальных вершин E. Требуется найти дерево минимальной длины с корнем в заданной вершине b, содержащее пути от b до любого терминала из E.
Актуальность темы
Задача Штейнера в различных вариациях широко используется в таких передовых областях промышленности, как проектирование и производство интегральных микросхем, в т. ч. и микропроцессоров, телекоммуникации, в особенности при реализации современных технологических систем, таких как выборочное ТбЛбВбЩсШIdf«і ЙНТбр9iKTИВHІзКЗ телеконференции, а также в некоторых областях биологии (филогенетике).
Как известно, задача Штейнера в графовой форме является NP- трудной [6]. Большинство исследований данной задачи ставят целью найти приемлемые с точки зрения быстродействия и точности решения приближенные алгоритмы, эвристики и аппроксимации, с применением широкого спектра подходов: жадных алгоритмов, методов динамического программирования, генетических методов, а также различных аппроксимаций, основанных на линеаризации задачи и релаксации полученных условий. Большой вклад в исследование различных постановок задачи Штейнера внесли А. Зеликов- ский, А. Иванов, А. Тужи, і и и. М. Zachariasen, S. Arora, М. Hwang.
В то же время, вопрос о существовании более эффективных методов для решения данной задачи как с точки зрения быстродействия, так и точности, остается открытым. Кроме того, во многих практических задачах имеется дополнительная информация о структуре графа, что влечет интерес к разработке методов с большей ТОЧНОСТЬЮ ДЛЯ TQjKHX. более узких, классов задач. Наконец, современное развитие вычислительной техники вызывает интерес к методам, обладающим большей способности к распараллеливанию, т. е. к декомпозиции на отдельные подзадачи, которые могут решаться одновременно, независимо друг от друга.
Цель работы
Целью данной работы является исследование ориентированной задачи Штейнера на графах и некоторых ее специальных постановок, разработка новых приближенных методов и подходов к ее решению и их программная оптимизация.
Методы исследования
При экспериментальных исследованиях точности разработанных алгоритмов и сравнения их с другими распространенными методами были использованы программные реализации их на языке C^ 4.0. В качестве тестовой базы использовались задачи из базы задач SteinLib [8], а также сгенерированные автором наборы задач.
Для разработки параллельных реализации методов была использована библиотека Microsoft Task Parallel Library.
Основные положения, выносимые на защиту
Среди полученных в ходе исследования результатов можно выделить следующие
-
Разработан и реализован метод ^-кластерной оптимизации для задачи Штейнера на ориентированных графах.
-
Разработан и реализован приближенный метод S* ДЛЯ рбШбНИЯ 3cLсі/Чїї Штейнера на евклидовых ориентированных графах.
-
Теоретически доказана полиномиальная вычислительная сложность обоих алгоритмов.
-
Проведены экспериментальные исследования данных методов и показана их практическая ценность.
-
Разработаны и реализованы параллельные версии метода динамического программирования и обоих представленных приближенных методов, проведены экспериментальные сравнения быстродействия параллельных и последовательных версий алгоритмов.
Научная новизна
Все результаты, выносимые на защиту, являются новыми.
Практическая значимость
В результате исследований было показано, что данные приближенные методы могут быть эффективно использованы для решения практических задач, а параллельная реализация наилучшим образом использует получающую все большее распространение в настоящее время многоядерную архитектуру центральных процессоров.
Кроме того, предложенные подходы, использованные в приведенных методах, являются новыми и могут быть И С С Л 6ДОВ QjH Ы ДйЛбб для разработки новых приближенных методов.
Апробация работы
Основные результаты работы докладывались на российской конференции по проблемам дискретной оптимизации и исследования операций DOOR- 2010, на межвузовской научной конференции по проблемам информатики СПИСОК-2011, международной конференции «Математика, экономика, менеджмент: 100 лет со дня рождения Jl. В. Канторовича», а также на семинарах кафедры исследования операций математико-механического факультета СПбГУ.
Публикации по теме работы
Материалы ^ДИССбрТЭ)! ЩИ опубликованы в пяти работах [1,2,3,4,5]. Из них работы [2,3] — в списке журналов, рекомендованных ВАК. Работа [2] выполнена в соавторстве: соискателю принадлежат доработка и реализация ограниченного метода динамического программирования, доказательство точности, проведение вычислительных экспериментов.
Объем и структура работы
VLSI-проектирование
Классический формат телевещания и видеоконференций подразумевает, что все пользователи получают одну и ту же информацию из источника вещания, не имея возможности повлиять на ее выбор и передачу. Однако в последнее время, в связи с развитием волоконных технологий на смену старым форматам приходят новые форматы вещания, такие как интерактивное телевидение и интерактивные видеоконференции, в которых ползователь может выбирать информацию, которую он хочет получать. Такие форматы характеризуются выборочной многоточечной коммуникацией [12].
Примером интерактивной услуги является уже получившая большое распространение услуга Video-on-Demand (видео по требованию). Ее смысл заключен в том, что абонент кабельной телекомпании может в любое время заказать любое доступное видео из каталога, и оно будет ретранслировашю на его телевизионную приставку. Другим примером является возможность выбора абонентом желательного качества передаваемого изображения одной и той же транслируемой в данный момент передачи.
Таким образом, перед поставщиком такой услуги ставится задача по установлению оптимальных путей до абонентов для выборочной мультивещательной трансляции. Особенно она актуальна для сетей, использующих виртуальную цепь путей, таких как ATM и Frame Relay [67]. Данная задача часто моделируется как графовая задача Штейнера в той или иной форме, в зависимости от предоставляемой услуги.
Кроме того, специфика данной области применения часто накладывает на задачу Штейнера дополнительные ограничения и ставит новые вопросы -— например, необходимость строить или перестраивать дерево Штейнера оптимальным образом «на лету» при добавлении и удалении того или иного приемника.
Таким образом, нельзя не отметить, что задача Штейнера широко востребована в современных технологичных процессах, как уже давно использующихся и развитых, так и только начинающих развиваться, а значит исследование и построение новых, отвечающих современным требованиям алгоритмов решения по-прежнему необходимо.
Во главе «Состояние дел» описываются, классифицируются и анализируются основные направления развития в исследовании ориентированной задачи Штейнера на графах. Внимание уделяется как методам точного, так и приближенного решения, в том числе методам динамического программирования и линейной релаксации, жадным алгоритмам, алгоритмам локальных улучшений, и. т. д. Представлены наиболее известные алгоритмы в каждом из направлений, вместе с их оценками точности и(или) быстродействия.
В главе «Алгоритм -кластерной оптимизации» представлен раз работанный автором эвристический алгоритм для решения этой задачи.
Общая идея данного алгоритма заключается в том, что исходный граф разбивается на не более чем к непересекающихся подграфов, на каждом из которых ставится отдельная задача Штейнера, индуцированная исходной. Задачи Штейнера не более чем с к терминалами решаются с помощью точного метода. Подзадачи с более чем к терминалами в свою очередь вновь разбиваются на более мелкие подзадачи.
После преобразования исходной задачи с учетом найденных частичных решений, с помощью точного метода находится промежуточное дерево Штейнера, которое затем оптимизируется с помощью алгоритма локальных улучшений.
Также в этой главе доказывается теорема о вычислительной сложности этого алгоритма, составляющей 0(2ktnlogm).
В главе «Приближенный метод S на евклидовых графах» представлен разработанный автором эвристический алгоритм для решения ориентированной задачи Штейнера на евклидовых графах, то есть таких, чьим вершинам соответствуют координаты двумерного евклидового пространства.
Данный метод основан на идее алгоритма поиска кратчайшего пути А [34], который использует некоторую дополнительную эвристическую функцию (например, евклидово расстояние между двумя точками), чтобы оценить расстояние от текущей точки пути до конечной. Представленный алгоритм адаптирует данное соображение к задаче Штейнера, позволяя значительно уменьшить число рассматриваемых подмножеств терминалов в методе динамического про граммирования, в том числе сделать их число полиномиальным в приближенном методе.
Кроме того, в главе находится теоретическая оценка вычислительной сложности и доказывается полиномиальность полученного алгоритма решения.
В главе «Вычислительные оптимизации» рассматриваются технологические особенности реализации представленных в работе алгоритмов на языке С#, позволяющие уменьшить время решения и объем занимаемой памяти. Кроме того, представлены параллельные версии всех алгоритмов, которые дают возможность значительно уменьшить время решения задач на компьютерах с многоядерными центральными процессорами.
В главе «Вычислительные результаты» проводятся экспериментальные исследования представленных методов, производится их сравнение с другими известными приближенными методами решения задачи Штейнера, а также и друг с другом, на известных наборах задач из библиотеки SteinLib [68], а также на собственноручно стенериро-ваных наборах задач.
Сведение к задаче линейного программирования
Другой алгоритм, основанный на этом подходе, предложил Вонг в [59]. Он отличается от описанного выше тем, что на каждом шаге итерации выбирает и увеличивает двойственное значение только одного, некоторым образом выбранного множества, не удовлетворяющего ограничениям разреза (6).
Согласно ему, каждая дуга в графе имеет, кроме обычной стоимости сп, также сокращенную стоимость сп, которая в алгоритме первоначально инициализируется исходной стоимостью. Сокращенные стоимости дуг могут только уменьшаться. Дуга с нулевой сокращенной стоимостью называется насыщенной. Эти дуги индуцируют насыщенный граф Gs = (M,N(c)), где N(c) = {а Є А : сп(а) = 0}. Поскольку стоимости всех дуг положительны, то этот граф в начале работы алгоритма не содержит ни одной дуги, и состоит из \М\ компонент связности.
Все операции в алгоритме определены по отношению к текущему насыщенному графу. Пусть R — множество вершин некоторой компоненты сильной связности графа Gs. Напомним, что компонентой сильной связности ориентированного графа называется любое мак еималыюе подмножество вершин, такое, что существует ориентированный путь между любыми двумя вершина графа. Это множество будем называть корневой компонентой если:
Если R — корневая компонента, то обозначим через W(R) D R множество вершин, из которых имеются пути до R по дугам из Gs. Тогда алгоритм выглядит следующим образом: Алгоритм двойственного подъема Вонга Инициализация: сп -f- сп для всех п Є N, LB 4— 0; пока существует корневая компонента в Gs делать Полученный в результате работы алгоритма граф Gs содержит хотя бы одно решение задачи Штейнера, однако в нем также могут содержаться ненужные дуги. От них можно избавиться следующим образом: а) Пусть Q — множество вершин, достижимых из Ъ по дугам из Gs- Найдем минимальное ориентированное остовное дерево на подграфе Gs, индуцированном Q. б) Будем удалять из остовного дерева все листья, не являющиеся терминалами, пока существует хотя бы один лист, не являю щийся терминалом. Заметим, что LB, полученное в результате работы алгоритма — это нижняя граница решения, дающая гарантию качества решения.
Будем без ограничения общности предполагать, что граф G(M,N) является транзитивным, т. е. для любого пути т\ -л т , т\,т і Є М существует дуга {т\,т і) Є N. Кроме того, будем предполагать, что длина любой дуги в графе равна длине наименьшего пути между ее началом и концом. Обозначим через GE подграф G, индуцированный множеством Е U Ъ. Через Mst(E) обозначим наименьшее ориентированное остовное дерево GE, a Mo = MQ(E) — его стоимость. Полное дерево Штейнера Т — это ориентированное дерево, такое, что:
Сокращение дерева Т означает уменьшение до нуля стоимости дуг Mst(E), заканчивающихся в терминалах Т. Результат сокращения обозначим Е\Т. Таким образом, сокращение уменьшает значение MQ(E). Многие приближенные алгоритмы укладываются в следующую структуру [63]:
Обобщенный алгоритм жадного сокращения Инициализация: L = 0 список деревьев пока М0(Е) О Найти полное дерево Штейнера Т в некотором классе К, которое минимизирует некоторую оценочную функцию f(T): Т - агдтгпт к}\Т). вставить Т в список L : L = L U {Т } сократить Т , Е - Е\Т конец пока Восстановить дерево Штейнера из деревьев, находящихся в списке L, и выдать его. Многие известные приближенные алгоритмы для решения как ориентированной задачи Штейнера, так и других ее постановок могут быть уложены в данную схему, с помощью использования разных классов рассматриваемых поддеревьев К и оценочных функции алгоритм Такахаши и Мацуямы [55], уже рассматривавшийся в данной работе: К содержит всевозможные пути, а /CO = с(Т); эвристический алгоритм Рейварда-Смита [48]: К содержит всевозможные звезды, а /(Т) = с(Т)/(г— 1), где г — число листьев Т; обобщенная жадная эвристика [64]: К состоит из деревьев с тремя терминалами и f(T) = с(Т) - (М0(Е) -М0(Е\ Т)); относительная жадная эвристика с ограничением размера [65]: К содержит все деревья с максимум г терминалами, M0(S)-M0(S\Ty
Еще один эвристический алгоритм для решения ориентированной задачи Штейнера, который может быть уложен в данную схему, предложили Чарикар и др. [14]. Суть его заключается в следующем:
Задача Штейнера здесь решается как частный случай более общей задачи D-STEINER(/C, b, Е), где Ьи Е опеределяются аналогично оригинальной задаче, а/с — некоторое целое число, удовлетворяющее условию к \Е\. Задача заключается в том, чтобы построить ориентированное дерево с корнем в Ь, содержащим пути до любых к терминалов из Е, имеющее минимальную длину. Очевидно, что D-STEINER( , 6, Е) — это обычная ориентированная задача Штейнера.
Будем обозначать через d(T) плотность дерева Т — отношение стоимости дерева Т к числу терминалов Т. Будем называть частичной приближенной процедурой f(k) для D-STEINER(/C, 6, Е) процедуру, которая строит дерево V с корнем в Ь, связывающее 1 к к терминалов из Е, такое что d(T ) f(k) f21, где СОРТ — это стоимость оптимального решения D-STEINER(/C, 6, Е).
Предположим имееется А(к, b, Е) — частичная приближенная процедура для D-STEINER(/c, 6, Е). Тогда, чтобы получить приближенный алгоритм В[к b, Е) можно применить А несколько раз следующим образом.
Вначале В(к,Ь,Е) вызывает процедуру А{к)Ь1Е), которая возвращает дерево Ті, связывающее к\ терминалов. Если к\ = /с, то возвращается Ті, и алгоритм завершает работу. В ином случае Б(к,Ь,Е) возвращает объединение Ті и дерева, возвращенного рекурсивным вызовом процедуры В (к — к\, 6, Е \ Е\), где Е\ — множество терминалов в Ті.
Зеликовским в [63] была доказана следующая лемма: Лемма. Для всех I 1 существует l-уровневое дерево, которое представляет кт приближенное решение для D-STEINER(A;, b, Е).
Основная суть алгоритма Чарикара заключена в следующем: рассматриваются деревья, состоящие из пути от Ъ до некоторой промежуточной вершины т, в свою очередь соединенной с некоторым множеством терминалов с помощью кратчайших путей. Деревья такого типа будем называть гроздьями. Из них выбираются деревья с наилучшей плотностью и добавляются в искомое дерево жадным образом. Приведем формальный алгоритм: Алгоритм Ai(k, b, Е) если не существует к терминалов в Е, достижимых из Ь, вернуть 0. Т - 0 пока к О TBEST - 0 для всех вершин т Є М, и каждого к , 1 к к T -Ai (k ,b,E)u{{b)m)} если d{TBEST) d{T) то 7WT - Г T Tu TWT; fc - fc - n M(TBE5T); Я - Я \ M{TBEST) конец для всех конец пока Вернуть Т. Доказана теорема о коэффициенте аппроксимации и вычислительной сложности алгоритма:
Улучшение деревьев Штейнера на кластерах 38 3.4. Нахождение промежуточного полного дерева Штейнера
Данный алгоритм является примером использования данных о координатах вершин в евклидовом графе для решения задачи о маршрутизации.
Алгоритм А является развитием алгоритма Дейкстры для решения задачи о кратчайшем пути [22], и имеет большую, в сравнении с ним, производительность. Данный алгоритм является эвристическим и использует дополнительные знания о графе. Основная его идея базируется на существовании некоторой допустимой эвристической функции Напомним, что эвристическая функция называется допустимой, если ее значение априори не превышает значение кратчайшего пути к цели (в случае задачи о маршрутизации, где граф индуцирован реальной сетью в евклидовом пространстве, в качестве такой функции может выступать евклидово расстояние до конечной вершины).
Алгоритм использует эвристическую функцию / : М — Ш+1 определяющую порядок, в котором алгоритм обходит вершины. Функция / представляет собой сумму двух функций / = g + функция стоимости пути от начальной вершины до рас сматриваемой вершины; введенная выше допустимая эвристическая функция.
Используя её, алгоритм рассматривает в первую очередь пути, которые, скорее всего (согласно эвристической функции /г), могут привести к цели, однако при этом принимает во внимание и уже пройденное расстояние. Пример определения данной функции представлен на рисунке Рисунок 7 - Функция f(x)
Формально алгоритм А приведен ниже. Алгоритм А инициализация: Q - приоритетная очередь частичных путей, R - список рассмотренных вершин для b вычислим f(b) и добавим путь Ъ — b в Q пока Q ф 0 делать Авторами [34] было доказано, что данный алгоритм является полным и оптимальным, т. е. всегда находит наилучшее решение, если оно существует. Кроме того, показано, что если функция h(x) является монотонной, т. е. удовлетворяет условию
h(hegn) d(n) + h(endn) Vn Є N, (15)
то алгоритм А можно реализовать еще эффективнее - рассматривать каждую вершину только один раз. В этом случае А по сути является алгоритмом Дейкстры на графе с уменьшенной функцией стоимости d (n) — d(n) — h(begn) + /i(endn).
Прежде чем перейти к описанию алгоритма в общем случае, рассмотрим одну специфическую задачу и предложим возможный способ ее решения. 4.2. Задача Штейнера на концентрических окружностях
Пусть на евклидовой плоскости имеется множество концентрических окружностей, на каждой из которых также задано произвольное множество точек. Рассмотрим граф, множество вершин которого состоит из выбранных точек, а также центральной точки системы окружностей. Любые две точки соседних (и только соседних) окруж Рисунок 8 - Пример задачи ностей соединены попарно дугами, ведущим от внутренней окружности к внешней. Длина дуги определяется евклидовым расстоянием между ее вершинами на плоскости. Начальная точка задачи Штейнера — центральная точка системы, множество терминалов — некоторое подмножество множества вершин внешней окружности (см. рисунок 8).
Покажем, что для такой задачи можно сделать алгоритм динамического программирования более быстрым, ограничив множество рассматриваемых подмножеств терминалов. А именно, будем рассматривать только такие подмножества, все элементы которых следуют одна за другой на окружности. Т. е. не существует терминала, не вошедшего во множество, разделяющего два терминала из множества. В то же время, нетерминальных вершин между терминалами из такого множества может быть любое число (см. рисунок 9). В
Множество, удовлетворяющее условию множестве из к терминалов содержится лишь к (к — 1) + 2 к2 подмножеств, состоящих из вершин, идущих подряд. Это к одноэлементных, к двухэлементных, и. т. д., к — (к — 1)-элементных, а также пустое подмножество и множество всех терминалов. Это значит, что алгоритм динамического программирования с таким ограничением будет иметь не экспоненциальную, а полиномиальную сложность.
Однако нам необходимо удостовериться, что алгоритм динамического программирования с такими ограничениями для этой задачи по-прежнему будет выдавать точное решение. Для этого достаточно показать, что в любом состоянии (i, ST) процесса (і — текущая начальная вершина, ST — некоторое подмножество терминалов), для любого разбиения {SA,ST\A}I не удовлетворяющего ограничениям, существует разбиение, удовлетворяющее ограничениям, которое дает не худший результат.
То что разбиение не удовлетворяет ограничениям, означает, что существуют вершины а,Ь Є SA, c,d Є ST\A, расположенные через одну: a,c,b, d. Рассмотрим решение, полученное из такого разбие ния (см. рисунок 10). Существуют две соседние окружности, между Рисунок 10 - Разбиение, не удовлетворяющее ограничениям которыми пути г — с и і — Ь пересекаются. Пусть пересечение происходит на дугах (хі, у2), [х2, У\). Тогда, если выбросить из путей эти дуги, и вставить вместо них дуги (х і, уі) и (х2,у2), получим некоторое решение для разбиения, когда а, с Є SA,b,d Є ST\A- Очевидно, что а значит оптимальное решение для такого разбиения не больше, чем для исходного. Меняя таким образом местами все «перекрещивающиеся» вершины, придем к разбиению, удовлетворяющему наложенным ограничениям, и при этом получаемое с помощью данного разбиения решение будет не больше, чем для разбиения {SAJST\A}. 4.3. Алгоритм S на евклидовых графах
Далее будем считать, что ориентированный граф G(M,N), на котором поставлена задача Штейнера является евклидовым, т. е. индуцированным некоторым набором точек в двумерном евклидовом пространстве Е2, а функция стоимости с(п) задается евклидовым расстоянием между концами дуги п. Таким образом, каждой вершине т Є М сопоставлены ее евклидовы координаты (хт:ут), а функция стоимости:
Основная идея разработанного алгоритма заключается в том, чтобы ограничить множество рассматриваемых в методе динамического программирования подмножеств терминалов. Мощность этого множества изначально равна 2 1 Будем добиваться того, чтобы она зависела от мощности множества терминалов полиномиально. Для этого воспользуемся информацией о взаимном расположении вершин, которая доступна в евклидовом графе
Алгоритм динамического программирования
Параллельные вычисления — это форма вычислений, при которой несколько вычислений производятся одновременно, основывающаяся на принципе, что большие задачи могут быть зачастую разделены на меньшие подзадачи, которые могут решаться одновременно. Параллельные вычисления применяются уже много лет, особенно в области высокопроизводительных вычислений, однако интерес к ним вырос значительно в последнее время, в связи с тем, что физические ограничения не позволяют более наращивать тактовую частоту процессоров с той же скоростью, как раньше.
Параллельные компьютеры могут быть разделены на несколько классов, в зависимости от уровня, на котором технически поддерживает параллелизм: мультиядерные и мультипроцессорные компьютеры имеют несколько процессорных элементов внутри одной машины, в то время как кластеры, массово-параллельные архитектуры и гри-ды используют несколько компьютеров, работающих над одной и той же задачей. Рассмотрим основные виды параллелизации подробнее:
а) Распределенные вычисления. Так называется способ реше ния трудоемких задач с использованием нескольких компьюте ров, чаще всего объединенных в параллельную вычислитель ную систему. Однако каждый из компьютеров при этом име ет собственную локальную память. Особенностью таких систем является возможность неограниченного наращивания произво дительности за счет масштабирования. Коммуникация между элементами распределенных систем производится при помощи посылки сообщений. Первые широко распространенные рас пределенные системы появились в 70-х годах прошлого века [9]. Существует несколько технологий и стандартов, упрощаю щих создание распределенных программ (посылка и обработка сообщений). Наиболее известны из них стандарты ОрепМР и MPI [10]. б) Конкурентные вычисления. Конкурентные вычисления от личаются от распределенных тем, что выполняются внутри среды с общей разделяемой памятью.
В последнее время все основные производители микропроцессоров, начиная от Intel и AMD, и заканчивая Sparc и PowerPC отказываются от традиционных ПОДХОДЕ К увеличению производительности центральных процессоров. Вместо увеличения тактовой частоты и пропускной способности последовательных инструкций, они обращаются к технологиям мультиядерности и гипертрединга (несколько виртуальных потоков на одном ядре). Обе эти возможности уже широко используются на совре менных процессорах [54].
Число ядер в компьютерах в настоящее время растет, на рынке широко представлены модели процессоров с двумя, четырьмя и даже восемью ядрами, процессоры Intel Core І5 и і 7 обладают четырьмя ядрами и поддержкой гипертрединга, т. е. восемью параллельными потоками выполнения. Intel уже анонсировал возможный выпуск в ближайшее время процессоров, имеющих до 80 ядер [38], а по исследованиям InStat уже к 2013 году число мультиядерных процессоров на мобильных устройствах достигнет 88% [40].
Все это ведет к фундаментальной смене точки зрения на разработку программного обеспечения, и к резкому росту популярности технологии распараллеливания с разделяемой памятью.
Существуют также подход, при котором распределенные вычисления и параллельные вычисления разделяют, отождествляя параллельные вычисления только с конкурентным программированием, т. е. с программированием с разделяемой памятью.
Далее будут представлены конкурентные версии алгоритмов, представленных в работе, позволяющие использовать сильные стороны многоядерной архитектуры.
В .NET Framework 4.0 включена библиотека Task Parallel Library, позволяющая писать параллельные версии программ в декларативном стиле. Она основана на подходе, при котором выполнение программы разбивается на отдельные подзадачи, каждая из которых определяется некоторой функцией (зачастую А-функцией). Они создаются и автоматически распределяются по ядрам, когда наступает их очередь выполняться.
Для того, чтобы сделать эффективную параллельную версию алгоритма с использованием TPL, необходимо прежде всего определить разбиение алгоритма на задачи, которые будут выполняться параллельно, и время, когда разрешать запуск каждой последующей задачи, а также разработать механизм блокировок для корректной работы с разделяемыми данными.
Напомним, в однопоточном варианте алгоритм выглядит следующим образом: таблица Т задается двумерным массивом. Итеративный ПрОЦеСС ИСПОЛНЯеТСЯ В ЦИКЛе, Определенном В МеТОДе Iteration .
На каждой итерации цикла выполняются последовательно методы Dijkstrification (алгоритм Дейкстры), и UseRow (использование получен-ного ряда для пересчета длин деревьев для подмножеств, содержащих данное).
Определим отдельной задачей каждое выполнение метода iteration. Таким образом всего алгоритм решения будет состоять из 2і задач. Однако, очевидно, что даже при гипотетическом наличии в вычислительной машине 2і ядер процессора мы не можем запустить все задачи одновременно, поскольку, прежде чем применять метод Дейкстры к некоторому подмножеству, необходимо проверить всевозможные разбиения данного множества на дизъюнктные подмножества и найти оптимальные разбиения для каждой вершины.
