ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ТЕХНИЧЕСКИЕ ВЫЧИСЛЕНИЯ С MPI

В этом техническом отчете основное внимание уделяется внедрению высокопроизводительных технических вычислений в кластере высокопроизводительных вычислений с использованием MPI для распараллеливания решения задачи коммивояжера.

  • Литературный обзор
  • Методология
  • Полученные результаты
  • Заключение

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

Литературный обзор

HPC

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

Для достижения параллельной вычислительной мощности HPC использует специализированное аппаратное и программное обеспечение. Эти системы обычно строятся с использованием кластеров высокопроизводительных компьютеров, соединенных в единое целое. Аппаратные компоненты этих систем разработаны для обеспечения максимальной производительности благодаря многочисленным взаимосвязанным процессорам, высокоскоростным соединениям, достаточному объему памяти и устройству хранения данных. Кроме того, специально разработанное программное обеспечение, такое как интерфейс передачи сообщений (MPI), используется для координации процессоров и обеспечения их совместной работы и совместного решения сложных вычислительных задач.

Проблема бродячего продавца и NP HARD

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

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

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

филиал и связаны

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

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

Цели

Задача 1. Разработайте последовательный алгоритм для решения алгоритма ветвей и границ.

Задача 2. Разработайте параллельный алгоритм для решения задачи странствующего продавца с использованием MPI.

Задача 3:Протестируйте параллельную программу в 17 городах с различными методами связи и оптимизации.

Задание 4. Измерьте производительность последовательного и параллельного кодов и обсудите.

Методология

Кластер Crescent HPC

Инфраструктура HPC, используемая для этого проекта, — это Crescent, исследовательский центр Университета Крэнфилда, который предлагает 1488 доступных ядер, распределенных по разным типам узлов, включая шасси 2U, отдельные узлы 1U и 2U. Эти узлы оснащены процессорами Intel Sandy Bridge и Haswell, обеспечивающими в общей сложности от 16 до 32 ядер на узел и диапазоном общей памяти от 64 ГБ до 256 ГБ. Средство подходит для запуска приложений на основе MPI, предоставляя достаточные вычислительные ресурсы для проекта. [3]

ИМБ

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

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

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

Слабая и сильная раздача

На протяжении всего проекта мы будем тщательно управлять и оптимизировать распределение задач, чтобы избежать слабого распределения. Слабое распределение имеет место, когда распределение работы не приводит к сокращению времени вычислений, часто из-за того, что время, затрачиваемое на связь между экземплярами, превышает время, затрачиваемое на фактическое вычисление задачи. Чтобы смягчить это, мы будем стремиться минимизировать время общения, насколько это возможно, при этом обеспечивая эффективное и действенное распределение задач. [6]

Алгоритмы

В этом проекте мы будем оценивать два алгоритма — алгоритм грубой силы и алгоритм ветвей и границ. Алгоритм Brute Force будет работать, исследуя каждый путь дерева, тогда как алгоритм Branch and Bound будет более эффективным, делая выборочный выбор пути для исследования и обрезая дерево как можно скорее в процессе.

ДФС

В этом проекте оба алгоритма будут использовать алгоритм поиска в глубину (DFS) для изучения дерева потенциальных путей. Алгоритм DFS будет работать рекурсивно и выполнять глубокий поиск в дереве, исследуя его сверху вниз и слева направо.

Ветвь и границы

Алгоритм ветвей и границ вызывается рекурсивно и попытается посетить все непосещенные города, начиная с заданного предварительного пути. Алгоритм будет каждый раз проверять, не ниже ли стоимость пути путем добавления непосещенного города ниже наилучшей найденной стоимости. Если это так, алгоритм продолжает DFS, если нет, он обрезает дерево, начиная с этого города, уменьшая количество возможностей для дальнейшего исследования. Как представлено псевдокодом на рисунке 1.

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

Примечание: для исследования грубой силы мы будем следовать тому же принципу, используя алгоритм DFS, разница в том, что мы никогда не будем отслеживать, если current_cost ниже найденного на данный момент best_cost, и по-прежнему исследовать все возможности дерева.

Рис. 1. Алгоритм ветвей и границ в псевдокоде.

function branch_and_bound(current_path, current_cost, best_cost):
    if length of current_path = num_cities:
        # Base case: if current cost < best cost update it
        best_cost = min(best_cost, current_cost)
    else:
        for each unvisited city in cities:
            # Calculate cost of adding the city to current path
            cost = calculate_cost(last_city, city)
            if current_cost + cost < best_cost:
                # Add the city to the current path
                new_path = current_path + [city]
                # Recursively call branch_and_bound with updated path and cost
                new_cost = branch_and_bound(new_path, current_cost + cost, best_cost)
                
# Initial call to branch_and_bound with an starting from city 0
branch_and_bound([0], 0, INT_MAX)

Параллельная реализация

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

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

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

После завершения поиска по предварительным путям процессы будут участвовать в межпроцессном взаимодействии для обмена рассчитанными значениями минимальной стоимости (min_cost). Используя функцию MPI «ReduceAll», процессы совместно определяют глобальную минимальную стоимость (min_global cost), которая будет использоваться для более эффективной обрезки дерева в последующих итерациях. Частота общения будет проанализирована в разделе результатов, чтобы оптимизировать баланс между чрезмерным и недостаточным общением. Псевдокод параллельной реализации представлен на рисунке 3.

Рисунок 3. Псевдокод параллельного алгоритма

ALGORITHM parallel_wsp_branch_and_bounds:

1. Initialize variables and data structures

2. Read the input file and create the distance matrix 

3. Create all possible pre-paths:
   a. Generate all possible pre-paths for X cities deep
   b. Shuffle the pre-paths
   c. Distribute the pre-path shuffled amoung all processes

4. Loop through all pre-paths assigned:
   a. Initialize the curr-distance depending of the current pre-path
   b. Initialized the visited city for each city in the current pre-path
   c. Call the function `dfs` starting from the current pre-path
   d. Reduce the min_cost from all the processes

5. Print the final results

Коммуникация

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

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

Нет трансляции

При параллельном подходе выбор был сделан так, что все процессы будут читать входной файл и создавать свою матрицу расстояний. Другим решением могло бы быть то, что ранг 0 считывает и создает матрицу расстояний, а затем передает ее всем процессам. Кроме того, матрица расстояний будет храниться в одномерном массиве, где индексация для доступа к правильной переменной будет выполняться вручную. Массив 1D был выбран вместо сохранения расстояния в массиве 2D после выполнения некоторых тестов, которые показали большую эффективность для 1D.

Полученные результаты

В следующей части отчета мы сосредоточим все наши тесты и результаты на примере 17 городов. Кроме того, для соответствия нашему сравнению и результату мы проведем тест, начав поиск с города 1 - результаты, начиная с каждого города, можно найти в приложении - тем не менее, в окончательном программном обеспечении выбор первого города будет быть случайным. Мы можем визуализировать города на карте, как показано на рисунке 4, и мы будем использовать это представление позже, чтобы нарисовать лучший найденный путь и визуально проверить наш результат. Каждый город связан с другим городом матрицей расстояний, как показано на рисунке 5.

Лучший путь, найденный для 17 городов, — это 1, 10, 4, 14, 15, 9, 6, 11, 13, 5, 8, 3, 16, 2, 17, 7 и 12 со стоимостью 278. Путь представлен на рисунке 6. Это представление помогает нам провести первую глобальную проверку нашего результата, поскольку представленный путь имеет смысл и визуально выглядит кратчайшим из возможных, начиная с города 1.

Эффект перетасовки предварительных путей

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

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

Блокировка/неблокировка связи

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

Сравнение общего времени вычислений представлено на рисунке 9. Мы видим, что неблокирующая связь не уменьшила общее время вычислений нашей реализации. Одна из причин может заключаться в том, что я не реализовал неблокирующую коммуникацию должным образом, чтобы правильно ею воспользоваться. Другая причина заключается в том, что даже если отправка не является блокирующей для IreduceAll, процессу все равно придется ждать результата связи. Если один процесс застрял в длинном цикле изучения различных возможностей, даже если другой процесс тем временем выполнял другие вычисления, ему все равно нужно было бы дождаться завершения IreduceAll другого процесса, прежде чем продолжить. Таким образом, в приложении это только задержит задержку и, в конце концов, не повлияет на скорость вычислений.

Эффект общения

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

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

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

Как показано на рис. 11, как и ожидалось, недостаточное или слишком интенсивное общение приведет к увеличению времени общения. Важно протестировать параллельную реализацию, чтобы найти оптимальное количество коммуникаций для работы в оптимальных условиях. В нашем случае с предварительными путями, сгенерированными для 5 городов в глубину, что приводит к 43 680 предварительным путям для изучения, оптимальной стратегией является сообщение каждых 60 исследованных предварительных путей. Это соотношение идеально подходит для компенсации накладных расходов на связь между процессами и времени, полученного за счет более раннего сокращения дерева.

Эффект генерации предварительного пути

Одной из важных оптимизаций является количество сгенерированных предварительных путей и то, насколько глубоко вы изучаете дерево путей перед его распространением. Количество сгенерированных предварительных путей влияет на распределение рабочей нагрузки между процессами и возникновение связи между процессами. Для тестирования различных конфигураций 5, 6 и 7 городов были проведены глубокие предварительные маршруты и проведено их сравнение друг с другом. Чтобы сравнение было последовательным и чтобы на результат влияло только количество предварительных путей, количество соединений осталось одинаковым для каждой конфигурации.

Как показано на рисунках 12 и 13, время вычислений и время простоя зависят от конфигурации. Из проведенного теста я обнаружил, что оптимальной конфигурацией была генерация 6 городов с глубокими предварительными путями. Даже если среднее время простоя ниже при конфигурации с 7 городами, количество сгенерированных предварительных путей — 5 765 760 — слишком велико и делает программу медленнее в общем времени работы. Идеальный промежуточный вариант можно найти с глубокой конфигурацией предварительных путей 6 городов. При более глубоком создании предварительного пути вероятность исследования заданного предварительного пути ниже, и каждый процесс будет исследовать более узкую часть дерева, избегая того, чтобы один процесс застревал на сложных путях и создавал узкое место в программном обеспечении.

Заключительная программа «Ветви и границы»

Наконец, со всеми оптимизациями, найденными ранее, окончательное программное обеспечение было протестировано и сравнено с серийной реализацией, чтобы получить окончательное ускорение и сравнить их с теорией. Результат окончательной реализации представлен на рисунке 14.

Мы можем наблюдать, что ускорения следуют теоретической линии почти до 16 процессоров, затем ускорение снижается. Это можно объяснить архитектурой нашего кластера HPC. На самом деле процессоров в узле 16, и если мы хотим иметь больше 16 процессоров, то будем использовать несколько узлов внутри HPC. Как видно из документации и лекций, связь между узлами медленнее, чем внутри одного узла. Поскольку наша программная реализация много общается, это может объяснить падение ускорения, начиная с 16 процессоров. [3]

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

Финальная программа грубой силы

Мы можем сравнить наше программное обеспечение Branch and Bounds с реализацией Brute Force. Первое, на что следует обратить внимание, это то, что наша программа Brute Force более эффективна при ускорении и почти соответствует теоретической линии, как показано на рис. 15. Реализация Brute Force не включает связь между процессами, поэтому для вычислений не добавляются накладные расходы. Это означает, что масштабирование программного обеспечения эффективно и стоит того.

Обсуждение

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

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

Как видно из всей части результатов, проведение теста для поиска идеальной конфигурации на конкретном оборудовании чрезвычайно важно, один небольшой параметр может значительно улучшить общее время вычислений программного обеспечения — разница между генерацией 5 и 6 городов в глубоком предварительном режиме. путь от 29s до 14s.

Замечу, что на обеих кривых ускорений для брутфорса и ветвления и связей мы не наблюдали снижения ускорений, мы видели только фазу роста. Обычно параллельное программное обеспечение имеет фазу увеличения, вершины, а затем фазу убывания ускорения. Это может означать, что наше программное обеспечение может иметь большее ускорение при тестировании, потому что мы были ограничены 64 процессорами в кластере Crescent HPC. Было бы интересно посмотреть, где может быть вершина, и будет ли наша реализация также иметь фазу убывания в будущем.

Возможны улучшения

Я заметил несколько улучшений, которые можно внести в реализацию. Один из основных на мой взгляд — использовать более эффективные структуры данных и отказаться от перераспределения памяти для каждой итерации. В поиске DFS массив посещений и массив путей управляются динамически, когда текущий добавленный город вызывается push_back(), а затем pop_back() в конце массива. Это может означать, что каждый раз массив необходимо копировать в другое место памяти, что в таком случае приведет к большим накладным расходам.

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

Заключение

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

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

Как видно из части обсуждения, поиск эффективного алгоритма, который упростит исходную задачу и уменьшит объем необходимых вычислений, еще более важен, прежде чем начинать распараллеливать нашу работу. Мы могли бы распараллелить с максимально возможным ускорением алгоритм Brute Force, но я мог бы за неделю на 64 процессорах выполнить работу алгоритма ветвей и границ на одном процессоре за 5 минут.

Найдите больше кода здесь.

Рекомендации

[1] Питер Пачеко (1997), Параллельное программирование с MPI, Морган Кауфм, анн.

[2] Питер Пачеко (2011), Введение в параллельное программирование, Elsevier.

[3] Д-р Ирен Моулицас (2022 г.), Высокопроизводительные технические вычисления, Крэнфилдский университет.

[4] Амей Гохил, Манан Тайал, Тезан Саху и Вьянкатеш Савалпуркар (2021), Задача коммивояжера: параллельные реализации и анализ

[5] Джонсон, Д. Б., и МакГеоч, Л. А. (1997). Задача коммивояжера: пример локальной оптимизации.

Узнать больше

Облачные вычисления AWS с Python

Множественная линейная регрессия, градиентный спуск на Python

© Все права защищены, март 2023 г., Симеон ФЕРЕС