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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «ВЫСШАЯ ШКОЛА ЭКОНОМИКИ» Разработка методов дискретной оптимизации, ориентированных на графические ускорители и гибридные системыВ рамках выпускной квалификационной работы, рассмотрена задача об одномерном ранце, являющаяся классической задачей в области дискретной оптимизации. Комбинаторная оптимизация это область теории оптимизации, рассматривающая задачи о поиске оптимального элемента из конечного множества элементов. Исходя из гипотезы о неравенстве классов задач P и NP, исследования эффективности различных алгоритмов решения типовой задачи о ранце могут помочь в разрешении гипотезы. Выбранная в рамках работы задача о ранце имеет следующую постановку: из конечного множества элементов с параметрами «вес» и «стоимость», необходимо найти некоторое подмножество, обладающее наибольшей суммой стоимостей, при этом не превосходящее ограничение по суммарному весу. Реализация различных способов решения задачи о ранце является актуальной на сегодняшний день, поскольку решение данной задачи активно используется при решении более сложных прикладных проблем в различных сферах: планировании, управлении, инвестициях, логистике, моделировании экономических процессов, криптографии, и т.д.3) Каждый коэффициент стоимости и веса умножается на соответствующий его индексу 0 или 1 из бинарного набора, производится сложение полученных значений для данного набора. 3) Вызывается функция на GPU, которая, исходя из значения номера потока и блока потоков на видеокарте, вычисляет свой собственный уникальный бинарный набор; 5) Если сумма веса, полученная на потоке не превосходит вместимость W, то сумма стоимостей записывается в память видеокарты; Вычисления на видеокарте производятся каждым потоком независимо, однако за 1 раз 1 потоковый мультипроцессор может обработать «warp» - небольшой блок, состоящий из 32 потоков. Таким образом, за выполнение одного warp’a будет получено 32 значения суммарный весов и стоимостей на 1 мультипроцессоре, следовательно, при наличии только 1 мультипроцессора, количество операций сокращается с до .В отличие от алгоритма полного перебора, считается более оптимизированным, благодаря отсеву заранее неподходящих наборов элементов, однако заранее просчитать количество операций и время работы невозможно. Это происходит изза того, что данный алгоритм очень сильно зависит от коэффициентов элементов и вместимости ранца. 3) Когда суммарный вес превышает вместимость, делается «шаг назад» (backtrack) - выбрасывается последний положенный элемент, вершина помечается как 0, и проверяется, какие элементы после него могут поместиться в рюкзак, и улучшит ли это достигнутое максимальное значение суммы стоимостей. Если коэффициенты отношения стоимости к цене будут близки к друг-другу, алгоритм показывает меньшую эффективность. Таким образом, первоначальная постановка задачи о ранце превращается в следующую: В данном случае, когда все коэффициенты четные, а вместимость - нечетная, решение задачи релаксации будет вызываться на каждом «шаге назад», изза чего не происходит отсева заведомо неоптимальных наборов, совершается в несколько раз больше действий, а эффективность становится меньше, чем у алгоритма полного перебора.Данный алгоритм совмещает в себе алгоритм полного перебора и метод ветвей и границ Горовица-Сахни. Идея заключается в том, чтобы «зафиксировать» некоторый начальный набор элементов, после чего вычесть из общей вместимости полученную сумму веса, а на оставшихся предметах использовать метод Горовица-Сахни. Решение методом Горовица-Сахни. ветвь граница видеокарта данный Подобные идеи комбинированного алгоритма рассмотрены в главе 2.2, однако предложенный алгоритм подразумевал использование параллелизма на центральном процессоре, без применения технологий вычисления на графических картах. Реализация метода Горовица-Сахни на одном потоке GPU не отличается от ее реализации на CPU, поэтому параметры решения данной задачи на GPU зависят только от количества элементов, обрабатываемых методом полного перебора.Наборы коэффициентов генерировались по способу, предложенному в книге «Knapsack problems. Коэффициенты генерировались 3 способами с разными параметрами: Без корреляции: и - случайные числа в диапазоне . Ограничение вместимости вычислялось 2 способами: , , Для каждого способа генерации использовалось по 3 разных диапазона генерации случайных чисел, что должно дать большую чистоту проводимым исследованиям. Данное число стало переходным в решении задачи, поскольку индексы/количество операций перешли с int на long (с 4 байт на 8). Поскольку количество операций переборного алгоритма всегда известно заранее, исходя из размерности задачи, тестирование проводилось не на всех наборах, поскольку время работы не отличалось вне зависимости от коэффициентов.Для данного алгоритма время выполнения не зависит от коэффициентов, поэтому все время усреднено для каждого тестового ПК.

Оглавление

Глава 1. Постановка задачи

Глава 2. Алгоритмы

2.1 Метод полного перебора

2.2 Метод ветвей и границ Горовица-Сахни

2.3 Гибридный алгоритм

Глава 3. Тестирование

3.1 Тест 1

3.2 Тест 2

3.3 Тест 3

3.4 Сравнение эффективности

Выводы

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

Аннотация

Глава 1. Постановка задачи