Уменьшение времени построение дерева решений для задач линейного программирования с помощью параллельных вычислений

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

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 23.10.2016
Размер файла 171,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

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

Уменьшение времени построение дерева решений для задач линейного программирования с помощью параллельных вычислений

Кокуев Александр Александрович

тьютор

Аннотация

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

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

параллельный вычисление программирование

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

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

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

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

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

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

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

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

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

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

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

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

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

Итогом работы процедуры является набор пар (таблица, набор предположении?).

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

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

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

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

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

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

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

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

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

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

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

Для реализации описанного процесса вычислении? использовался входящий в стандартную поставку комплекта для разработки на языке программирования Python модуль «multiprocessing». При этом использовалась возможность распараллеливания вычислении? между процессами, а не потоками операционной системы. Это вызвано особенностями реализации языка программирования Python: она не предусматривает одновременное выполнение нескольких потоков и использует для синхронизации глобальную блокировку «GlobalInterpreterLock». Блокировкой сопровождается любое обращение к переменным текущего процесса интерпретатора, что приводит к тому, что даже при наличии нескольких вычислительных потоков, вычисления могут происходить только в одном из них. Использование процессов для распараллеливания вычислении? приводит к значительным накладным расходам на передачу данных, в то время как потоки могут разделять данные между собой, т.к. находятся в одном адресном пространстве. Припередачи данных между процессами используется модуль «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

Библиографический список

Немнюгин С. А., Стесик О. Л. Параллельное программирование для многопроцессорных вычислительных систем. - СПб. : БХВ-Петербург, 2002. - 400 с.

Кокуев А.А., Ктитров С.В. Построение дерева решении? в задачах линейного программирования // Вестник Национального исследовательского ядерного университета «МИФИ». - 2014. - Т. 3, №1.

Кокуев А. А., Ктитров С. В. Построение дерева решении? в задачах линейного программирования // Тезисы докладов XX международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации». - М. : Изд-во ПГУ, 2011.

AmdahlGene M. ValidityoftheSingleProcessorApproachtoAchievingLargeScaleComputingCapabilities // ProceedingsoftheApril 18-20, 1967, SpringJointComputerConference. - AFIPS '67 (Spring). - NewYork, NY, USA: ACM, 1967. - URL: http://doi.acm.org/10.1145/1465482.1465560.

GustafsonJohn L. ReevaluatingAmdahl'sLaw // Communicationsofthe ACM. - 1988. - Vol. 31.

BrownRobert G. MaximizingBeowulfPerformance. - 2000. - URL: http://www.phy. duke.edu/~rgb/brahma/brahma_old/als.pdf (online; accessed: 10.04.2015).

AnderssonKarl-Johan, AronssonDaniel, KarlssonPatrick. Anevaluationofthesystemperformanceof a beowulfcluster. - 2001. - URL: http://www.it.uu.se/edu/course/homepage/projektF/vt01/rapporter/grupp2/grendel.pdf (online; accessed: 10.04.2014).

Размещено на Allbest.ru


Подобные документы

  • Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.

    курсовая работа [1,1 M], добавлен 15.12.2010

  • Методы определения оптимального плана производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида. Технология поиска оптимального решения задач линейного программирования (ЗЛП) с помощью итоговой симплекс-таблицы.

    лабораторная работа [42,8 K], добавлен 11.03.2011

  • Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.

    курсовая работа [663,9 K], добавлен 10.06.2014

  • Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.

    дипломная работа [1,3 M], добавлен 27.03.2013

  • Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

    дипломная работа [2,4 M], добавлен 20.11.2010

  • Основные понятия математического линейного программирования. Постановка и методы решения заданий целочисленного и параметрического составления программ. Примеры вычисления задач с параметрами в целевой функции и в свободных членах системных ограничений.

    дипломная работа [432,0 K], добавлен 25.10.2010

  • Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.

    курсовая работа [132,0 K], добавлен 09.12.2008

  • Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.

    контрольная работа [199,8 K], добавлен 15.06.2009

  • Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

    курсовая работа [1,1 M], добавлен 21.03.2012

  • Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.

    курсовая работа [88,9 K], добавлен 11.02.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.