3.2 Тест 2

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

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

Данная задача была выбрана в рамках работ, проводимых в ФИЦ ИУ РАН в отделе «Прикладных проблем оптимизации». В процессе изучения возможных способов получения решения задачи, было проведено исследование возможности использования графических ускорителей, а также комбинирования алгоритмов, реализованных на гибридных системах - совместном использовании центрального процессора и графической карты.

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

Решения задачи о ранце в рамках комбинаторной оптимизации начали появляться во второй половине 20 века. Большинство методов решения данной задачи было сформулировано и реализовано в 1970-х годах. Реализации этих решений основывались на достаточно старых вычислительных технологиях. С развитием компьютерных систем, на сегодняшний день имеется множество различных технологий, языков и стандартов, для современных реализаций алгоритмов решения задачи. В 2006 году в рамках проекта GPGPU -( General-purpose computing for graphics processing units) - проекта, посвящённому использованию графических карт не только для обработки графической информации в приложениях, но и для обычных расчётов, которыми обычно занимается центральный процессор. Данный проект изменил представления о вычислениях, открыв новую эру вычислений на графических картах. Благодаря особой архитектуре, видеокарты обладают огромным вычислительным потенциалом, благодаря высокому параллелизму операций. Современные суперкомпьютеры, обладающие производительностью, оцениваемой в петафлопсах, по большей части строятся на основе графических ускорителей.

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

Для реализации параллельных алгоритмов, вычисляемых на видеокарте, была выбрана технология CUDA от Nvidia. Первый выпуск датируется 23 июня 2007 года. С того момента архитектура графических процессоров существенно улучшилась. Если первые видеокарты обладали порядком сотни независимых вычислительных ядер, то на сегодняшний день лучшие графические ускорители обладают более чем 5000 ядер.

Вычисления на видеокартах строятся по принципу SIMD - Single Instruction, Multiple Data - что означает выполнение одного набора команд на большом объёме различных входных данных. Архитектура видеокарты (Рис. 1) устроена следующим образом: существует некоторое число потоковых мультипроцессоров, работающих с вычислительными потоками. Вычисления на каждом потоке делаются независимо от других потоков на мультипроцессоре и от работы других мультипроцессоров.

Рис. 1. Архитектура видеокарты

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

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

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

· Имеется “n” элементов.

· Каждый элемент обладает свойствами: вес - , стоимость - .

· Задано ограничение вместимости W.

· Необходимо максимизировать функцию суммы стоимостей , при заданном ограничении суммарного веса (вместимости) W, ? W

· Вектор представляет собой набор из 0 и 1, т.е. - коэффициент наличия элемента.

В данной постановке, задача о ранце «Рюкзак 0-1», поскольку каждый предмет существует в единственном экземпляре, а конечное решение представляет собой вектор длины «n», состоящий из 0 и 1. Данный вид задачи является одним из самых распространённых и простых для реализации.

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

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

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

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

Описание последовательного алгоритма:

1) Вычисляется общее число операций ;

2) В цикле от 0 до каждое число переводится из десятичной системы в двоичную, то есть превращается в бинарный набор длины n;

3) Каждый коэффициент стоимости и веса умножается на соответствующий его индексу 0 или 1 из бинарного набора, производится сложение полученных значений для данного набора.

4) Если сумма веса не превосходит вместимость W, то сумма стоимостей сравнивается с максимально достигнутым на данном шаге (если есть, иначе записывается вместо максимального);

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

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

1) Вычисляется общее число операций ;

2) Исходя из этого числа, определяется количество используемых в вычислениях блоков потоков;

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

4) Каждый коэффициент стоимости и веса умножается на соответствующий его индексу 0 или 1 из бинарного набора, производится сложение полученных значений для данного набора.

5) Если сумма веса, полученная на потоке не превосходит вместимость W, то сумма стоимостей записывается в память видеокарты;

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

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

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

Рис. 2. Редукция.

Вычисления на видеокарте производятся каждым потоком независимо, однако за 1 раз 1 потоковый мультипроцессор может обработать «warp» - небольшой блок, состоящий из 32 потоков. Таким образом, за выполнение одного warp'a будет получено 32 значения суммарный весов и стоимостей на 1 мультипроцессоре, следовательно, при наличии только 1 мультипроцессора, количество операций сокращается с до . При наличии «k» процессоров на графическом ускорителе, данное число сокращается до операций.

Подробное описание алгоритма полного перебора на GPU

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

cudaDeviceProp deviceProp;

cudaGetDeviceProperties(&deviceProp, 0);

int threads_per_block = deviceProp.maxThreadsDim[0];

int max_blocks = deviceProp.maxGridSize[0]/2 + 1;

«threads_per_block» - максимальное количество потоков в блоке;

«max_blocks» - максимальное количество блоков на 1 мультипроцессор.

Используемые данные - коэффициенты веса, стоимости и вместимость, вводятся вручную либо перенаправлением потока ввода из файла. В первоначальной реализации коэффициенты копировались в глобальную память видеокарты, однако в ходе исследований и тестирования было получено, что копирование данных коэффициентов в «constant memory» видеокарты, даёт прирост производительности около 10%, поскольку скорость обращения к константной памяти на видеокарте является самой быстрой. Также на копирование коэффициентов в константную память повлияло тот факт, что коэффициенты не изменяются в ходе работы программы.

Далее выполняется функция, отвечающая за выполнение 1 блока потоков. Запускается блок из максимального (обычно 1024) числа потоков. В разделяемой памяти видеокарты создаётся 2 массива - один для значений сумм стоимостей потока, второй для записи номера потока.

extern __shared__ float sh_array[];

float* sh_maxs = (float*)sh_array;

long int* indices = (long int*)&sh_maxs[threads_per_block];

indices[threadIdx.x] = threadIdx.x;

«extern» - означает, что количество выделяемой памяти задаётся в вызове функции.

«sh_maxs» - суммы стоимостей каждого потока, записываемые в разделяемую память видеокарты.

«indices» - индексы потоков в блоке; используются в процессе редукции для поиска оптимального набора - вектора

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

#pragma unroll

for (uint i = 0; i < arraySize; i++)

{

th_bin[i] = ((num_to_bin) >> i) % 2;

th_w_sum += th_bin[i] * coefs[i];

th_v_sum += th_bin[i] * coefs[i+arraySize];

}

«#pragma unroll» - выражение, которое после прочтения компилятором, «разворачивает» цикл, т.е. все операции будут произведены одновременно, а на в цикле.

«th_bin[i]» - массив размерности n (число предметов), вектор

«th_w_sum» - сумма весов на наборе потока.

«th_v_sum» - сумма стоимостей на наборе потока.

«coefs» - коэффициенты веса или стоимости, в зависимости от индекса. Находятся в константной памяти GPU.

Далее идёт отсев «лишних» значений:

sh_maxs[threadIdx.x] = (th_w_sum > coefs[arraySize*2]) ? 0:th_v_sum;

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

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

for (uint offset = blockDim.x >> 1; offset >= 1; offset >>= 1)

{

if (threadIdx.x < offset)

{

if (sh_maxs[threadIdx.x] < sh_maxs[threadIdx.x + offset])

{

sh_maxs[threadIdx.x] = sh_maxs[threadIdx.x + offset];

indices[threadIdx.x] = indices[threadIdx.x + offset];

}

}

__syncthreads ();

}

«blockDim» - размер блока - количество потоков в блоке.

«offset» - сдвиг для сравнения элементов; равен половине размера рассматриваемого блока.

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

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

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

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

Фиксированная часть. Нефиксированная часть.

Решение методом полного перебора. Решение методом Горовица-Сахни. ветвь граница видеокарта данный

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

В рамках ВКР, мной был рассмотрен и реализован комбинированный (гибридный) алгоритм, использующий для вычислений возможности GPU.

Реализация метода Горовица-Сахни на одном потоке GPU не отличается от её реализации на CPU, поэтому параметры решения данной задачи на GPU зависят только от количества элементов, обрабатываемых методом полного перебора.

Описание алгоритма:

1) Определяется номер элемента «k» для деления набора;

2) Каждый поток видеокарты создаёт часть бинарного набора от 0 до k;

2.1) В разделяемую память блока записывается индекс потока;

3) Производятся операции перемножения коэффициентов веса и стоимости на первых k элементов;

4) Каждый поток вычисляет свою «остаточную» вместимость - разность общей вместимости, и полученной суммы веса на шаге 3;

5) Начиная с «k + 1»-го до «n»-го элемента выполняется алгоритм метода ветвей и границ Горовица-Сахни для остаточной вместимости;

6) Полученные значения потоков записываются в разделяемую память;

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

7.1) При поиске максимального значения в блоке, записывается номер потока, получившего максимальное значение;

7.2) Полученный оптимальный бинарный набор на потоке с максимумом, записывается в глобальную память видеокарты.

8) Проводится последняя редукция для определения максимальной суммы стоимостей и определения искомого набора элементов - вектора

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

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

Первая конфигурация ЭВМ:

GPU - Nvidia GeForce 610m, 1 SM, 48 cores, 1024 threads, Architecture - Fermi

CPU - Intel Core I3, 2.3GHZ, single thread

Compiler - gcc 5.4

Cuda compute capability 2.0, Toolkit v7.5

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

Среднее время работы составило около 600 секунд, то есть порядка 10 минут.

Второй тест - параллельный полный перебор на GPU. Этот алгоритм также не зависит от коэффициентов и выдаёт стабильное время работы. Оно составило в среднем 28,9 c. Отклонение от среднего времени составило не более 0,015с.

Ускорение относительно последовательной версии составляет около 21,5 раз.

Третий тест - реализация метода ветвей и границ Горовица-Сахни на CPU:

А) Данные не коррелируют:

3,45с

0,443с

Б) Данные обладают слабой корреляцией:

2,293с

0,4с

В) Данные сильно коррелируют:

0,37с

1,17с

Г) Условия Финкельштейна:

Около 1600с - около 26 минут.

Четвёртый тест - гибридный алгоритм.

А) Данные не коррелируют:

2,73с

0,93с

Б) Слабая корреляция:

0,73с

0,51с

В) Сильная корреляция

1,75с

0,97с

Г) Условия Финкельштейна:

81,26с

3.2 Тест 2

1 Лекции по комбинаторной оптимизации М.А. Посыпкин, Москва, 2017г, ВЦ ФИЦ ИУ РАН

2 Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. Изд. 2-е, исп. И доп. М.: ФИЗМАТЛИТ, 2007.

3 Keller H., Pfershy U., Pisinger D. Knapsack Problems. Springer Verlag, 2004

4 Официальное руководство по программированию на CUDA, вер. 1.1 // CUDA Programming Guide. Chapter 1. Introduction to CUDA > 1.2 CUDA: A New Architecture for Computing on the GPU

5 Параллельные вычисления на GPU. Архитектура и программная модель CUDA: Учебное пособие. А. В. Боресков и др. Предисл.: В. А. Садовничий Издательство Московского университета, 2012

6 Левитин А. В. Алгоритмы. Введение в разработку и анализ -- М.: Вильямс, 2006.

7 Роберт Седжвик. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск = Algorithms in C++. Parts 1-4. Fundamentals. Data Structures. Sorting. Searching. -- 3-е. -- Россия, Санкт-Петербург: «ДиаСофт», 2002

8 Martello S., Toth P. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, 1990.

9]Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976.

10 Посыпкин М. А., Сигал И.Х. Исследование алгоритмов параллельных вычислений а задачах дискретной оптимизации ранцевого типа // ЖВМиМФ. 2005. Т. 45, No 10. С. 1801-1809.

11 Kellerer H., Pferschy U., Pisinger D. Knapsack Problems. Berlin, Germany: pringer, 2004.

Аннотация

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

In this paper, we consider methods for solving global optimization problems with the use of graphic accelerator...