УДК 519.85

УМЕНЬШЕНИЕ ВРЕМЕНИ ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЙ ДЛЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Кокуев Александр Александрович
Национальный исследовательский ядерный университет «МИФИ»
тьютор

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

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


REDUCING COMPUTATION TIME OF THE DECISION TREE BUILDING FOR LINEAR PARAMETRIC PROGRAMMING PROBLEMS USING PARALLEL COMPUTATION

Kokuev Alexander Alexandrovich
National Research Nuclear University MEPhI
tutor

Abstract
This article discusses two ways to reduce the computation time of the decision tree building for linear parametric programming problems using parallel computing. The main difference between first and second way is that in latter whole problem divided into much smaller subtasks. Results of applying both methods shows that the second way gives better results. So the article concludes that decreasing subtask size is direction of future research.

Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Кокуев А.А. Уменьшение времени построение дерева решений для задач линейного программирования с помощью параллельных вычислений // Современные научные исследования и инновации. 2015. № 4. Ч. 2 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/04/52303 (дата обращения: 03.10.2017).

Построение дерева решений в задачах линейного параметрического программирования, при большой размерности задачи или при большом количестве параметров, нередко занимает значительное время. Ввиду комбинаторной природы задачи и используемого переборного алгоритма, а также текущего направления развития вычислительной техники, наиболее актуальным способом сократить общее время построения дерева решений является использование параллельных вычислений [1, с. 99].

Рассмотрим подробнее один из этапов алгоритма построения дерева решений [2, с. 119; 3, с. 321], заключающийся в генерации таблиц. В основу алгоритма генерации таблиц заложена процедура симплекс-метода. Основная задача алгоритма генерации таблиц, заключается в получении всех пар: (возможная таблица, набор предположений). При этом набор предположений, в общем случае, состоит из сложной системы предположений, которая тем не менее приводится к конъюнктивной нормальной форме. На входе алгоритма дана симплекс-таблица для задачи линейного параметрического программирования. Параметры задачи выраженные символами записываются в ячейки симплекс-таблицы так, как будто они являются численными.

Изложение алгоритма будет приводится поэтапно «сверху-вниз», сначала будет рассмотрен основной алгоритм, а затем отдельно будет рассмотрен один из его этапов.

Алгоритм перебора всех возможных коэффициентов критерия оптимизации (алгоритм I):

  1. Из всех коэффициентов критерия оптимизации необходимо выделить набор таких коэффициентов, которые могут быть неположительными. Если полученный набор непустой, то это фиксируется в виде истинного значения специального флага, в противном случае, в этот флаг помещается значения «ложь».
  2. Для каждого коэффициента полученного на предыдущем шаге создается набор предположений, необходимых для того, чтобы столбец соответствующий этому коэффициенту вошел в новый базис.
  3. Для каждой пары (коэффициент критерия оптимизации, набор предположений) вызывается процедура генерации таблиц для каждой из оптимизируемых переменных, которые являются кандидатами на исключения из базиса. Результатом это процедуры может стать нуль или более пар (таблица, набор предположений). Каждая таблица в таких парах является возможной таблицей для перехода.
  4. Если значение специального флага, заданного на этапе 1 является «ложь», то рассматривается случай, когда все коэффициенты критерия оптимизации больше нуля. Это равносильно тому, что текущая таблица не предполагает дальнейших переходов и представляет оптимальное решение. В этом случае текущая таблица с набором предположений, что все коэффициенты критерия оптимизации больше нуля добавляется к результату полученному на предыдущем шаге.

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

Рассмотрим подробнее алгоритм генерации всех таблиц для некоторой оптимизируемой переменной c учетом того, что для этой переменой у нас имеется набор предположений, необходимый для ее рассмотрения (алгоритм II):

  1. Выбор коэффициента критерия оптимизации сужает выбор разрешающего элемента до коэффициентов матрицы ограничений, находящихся в одном столбце. На первом этапе из всего таких коэффициентов отбрасываются заведомо неположительные.
  2. Для каждого коэффициента из оставшихся на предыдущем шаге, составляется набор предположений, необходимых, чтобы этот коэффициент был разрешающим элементом. Чтобы составить набор предположений для некоторого текущего коэффициента, необходимо для всех остальных коэффициентов получить два типа предположений. Первый тип предположений заключается в том, что другой коэффициент является отрицательным, поэтому разрешающим быть не может. Второй тип предположений заключается в том, что другой коэффициент положительный, но его выбор приводит к менее выигрышному переходу. Поскольку обычно оба типа предположений являются допустимыми, необходимо рассмотреть их все.
  3. После формирования набора предположений для каждого коэффициента из предыдущего этапа, согласно правилам симплекс-метода формируется новая таблица. Получаемая в итоге таблица и набор предположений формируют результат процедуры.
  4. Итогом работы процедуры является набор пар (таблица, набор предположений).

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

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

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

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

Испытание приведенного выше алгоритма (в дальнейшем он будет обозначаться как «версия 1») привело к следующим результатам: увеличение количества рабочих процессов сверх 4 не приводит к уменьшению времени работы. Анализ ситуации показал, основное время рабочие процессы затрачивают на генерацию всех дочерних таблиц и проверку непротиворечивости каждой из них, по мере готовности отправляя готовые для дальнейшей обработки задачи диспетчеру. При этом время обработки полностью одной таблицы либо достаточно велико, либо очень мало. Что приводит к тому, что все работа разбивается на сравнительно небольшое число крупных задач, которые выполняются последовательно каждым вычислительным процессом.

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

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

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

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

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

При этом теоретически оценить возможный прирост производительности согласно закону Амдала [4, c. 483] или закону Густавсона—Барсиса [5, c.532] не представляется возможным, ввиду того, что прирост для приведенного способа распараллеливания зависит от распределения нагрузки на процессы-вычислители, а не от доли параллельных и последовательных этапов алгоритма.

Для реализации описанного процесса вычислений использовался входящий в стандартную поставку комплекта для разработки на языке программирования Python модуль «multiprocessing». При этом использовалась возможность распараллеливания вычислений между процессами, а не потоками операционной системы. Это вызвано особенностями реализации языка программирования Python: она не предусматривает одновременное выполнение нескольких потоков и использует для синхронизации глобальную блокировку «Global Interpreter Lock». Блокировкой сопровождается любое обращение к переменным текущего процесса интерпретатора, что приводит к тому, что даже при наличии нескольких вычислительных потоков, вычисления могут происходить только в одном из них. Использование процессов для распараллеливания вычислений приводит к значительным накладным расходам на передачу данных, в то время как потоки могут разделять данные между собой, т.к. находятся в одном адресном пространстве. При передачи данных между процессами используется модуль «pickle».

Для исследования быстродействия варианта программы использующей параллельные вычисления использовался следующий подход. Поскольку время, необходимое для построения дерева, достаточно большое, для измерения времени построения дерева использовался измеритель времени доступный в среде Python. После считывания задачи и перед началом построения запоминалось время полученное с помощью метода time.time(). Аналогично, после построения дерева, до его записи в файл, проводилось считывания текущего значения времени. Разница между двумя значениями составляла время построения дерева. Для каждого испытания построение дерева проводилось не менее 10 раз, после чего вычислялось среднее и погрешность измерения по методу Стьюдента.

В таблицах 1 и 2 приведены результаты испытания для соответственно «версии 1» и «версии 2» вариантов распараллеливания.

Таблица 1 — Результаты испытания распараллеленного варианта (версия 1)

Количество вычислителей

Время построения дерева, c

Время относительно №1

Прирост  производительности относительно №1

1

(200 ± 2) ⋅ 10

1.000

2

(104 ± 3) ⋅ 10

0.52

1.92

3

852 ± 12

0.427

2.35

4

652 ± 17

0.327

3.07

5

641 ± 19

0.321

3.12

6

632 ± 14

0.317

3.16

Таблица 2 — Результаты испытания распараллеленного варианта (версия 2)

Количество вычислителей

Время построения дерева, c

Время относительно №1

Прирост  производительности относительно №1

1

(203 ± 5) ⋅ 10

1.000

2

1046 ± 19

0.52

1.94

3

747 ± 5

0.367

2.72

4

644 ± 6

0.317

3.16

5

576 ± 12

0.284

3.53

6

533 ± 6

0.262

3.82

Согласно полученным данным были построены два графика. Первый график иллюстрирует зависимость времени построения дерева от количества процессов- вычислителей (см. рис. 1). На нем представлено убывание времени построения дерева в зависимости от количества процессов-вычислителей для «версии 1» и «версии 2», а также для идеального случая помеченного «линейное», когда время убывает пропорционально количеству процессов. На графике видно, что разница между временем построения для количества процессов-вычислителей 4, 5 и 6 практически отсутствует для «версии 1» в отличие от «версии 2».

График на рис. 2 иллюстрирует зависимость прироста производительности от количества процессов-вычислителей. На графике представлено прирост производительности в зависимости от количества процессов-вычислителей для «версии 1» и «версии 2», а также для идеального случая помеченного «линейный», когда прирост производительности зависит от количества процессов линейно.

Рисунок 1 — График зависимости времени построения от количества процессов- вычислителей.

Рисунок 2 — График зависимости прироста производительности от количества процессов-вычислителей.

График на рис. 1 имеет характерное сходство с графиками, построенными для аналогичных систем при исследовании влияния количества процессов-вычислителей на прирост производительности [6; 7]. Однако, если в случае «версии 1» максимальное значение прироста производительности практически достигнуто, то в случае «версии 2» максимальное значение еще не достигнуто и для его нахождения необходимо увеличить количество процессов-вычислителей.

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта No 13-07-00465 


Библиографический список
  1. Немнюгин С. А., Стесик О. Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб. : БХВ-Петербург, 2002. – 400 с.
  2. Кокуев А.А., Ктитров С.В. Построение дерева решений в задачах линейного программирования // Вестник Национального исследовательского ядерного университета «МИФИ». – 2014. – Т. 3, №1.
  3. Кокуев А. А., Ктитров С. В. Построение дерева решений в задачах линейного программирования // Тезисы докладов XX международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации». – М. : Изд-во ПГУ, 2011.
  4. Amdahl Gene M. Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities // Proceedings of the April 18-20, 1967, Spring Joint Computer Conference. – AFIPS ’67 (Spring). – New York, NY, USA: ACM, 1967. – URL: http://doi.acm.org/10.1145/1465482.1465560.
  5. Gustafson John L. Reevaluating Amdahl’s Law // Communications of the ACM. – 1988. – Vol. 31.
  6. Brown Robert G. Maximizing Beowulf Performance. – 2000. – URL: http://www.phy. duke.edu/~rgb/brahma/brahma_old/als.pdf (online; accessed: 10.04.2015).
  7. Andersson Karl-Johan, Aronsson Daniel, Karlsson Patrick. An evaluation of the system performance of a beowulf cluster. – 2001. – URL: http://www.it.uu.se/edu/ course/homepage/projektF/vt01/rapporter/grupp2/grendel.pdf (online; accessed: 10.04.2014).


Все статьи автора «Кокуев Александр Александрович»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

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

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: