Параллельный поиск в ширину - Parallel breadth-first search - Wikipedia

В алгоритм поиска в ширину это способ исследовать вершины графа слой за слоем. Это базовый алгоритм теории графов, который может использоваться как часть других алгоритмов графов. Например, BFS используется Алгоритм диника найти максимальный поток на графике. Более того, BFS также является одним из алгоритмов ядра в График500 эталонный тест, который является эталоном для задач суперкомпьютерных вычислений с интенсивным использованием данных.^[1] В этой статье обсуждается возможность ускорения BFS за счет использования параллельные вычисления.

Последовательный поиск в ширину

В обычном последовательном алгоритме BFS создаются две структуры данных для хранения границы и следующей границы. Граница содержит вершины, которые находятся на одинаковом расстоянии (его также называют «уровнем») от исходной вершины, эти вершины необходимо исследовать в BFS. Каждый сосед этих вершин будет проверен, некоторые из этих соседей, которые еще не исследованы, будут обнаружены и помещены в следующую границу. В начале алгоритма BFS данная исходная вершина s - единственная вершина на границе. Все прямые соседи s посещаются на первом этапе, которые образуют следующий рубеж. После каждого обхода слоя «следующая граница» переключается на границу, и новые вершины будут сохранены в новой следующей границе. Следующий псевдокод обрисовывает его идею, в которой структуры данных для границы и следующей границы называются FS и NS соответственно.

1    определять bfs_sequential (график (V, E), исходники): 2 за все v в V делать3 d [v] = -1; 4 d [s] = 0; level = 0; FS = {}; NS = {}; 5 нажатий (s, FS); 6 пока ПС! Пусто делать7            за ты в ФС делать 8                за каждый сосед v из вас делать 9                    если d [v] = -1 тогда10 push (v, NS); 11 d [v] = уровень; 12 FS = NS, NS = {}, level = level + 1;

Первый шаг распараллеливания

В качестве простого и интуитивно понятного решения классический Параллельная машина произвольного доступа (PRAM) подход - это просто расширение последовательного алгоритма, показанного выше. Два за-loops (строка 7 и строка 8) могут выполняться параллельно. Обновление следующей границы (строка 10) и увеличение расстояния (строка 11) должны быть атомарными. Атомарные операции - это программные операции, которые могут выполняться только полностью без прерывания и пауз.

Модель PRAM.

Однако в этом простом распараллеливании есть две проблемы. Во-первых, операции проверки расстояния (строка 9) и обновления расстояния (строка 11) представляют две благоприятные расы. Причина гонки заключается в том, что сосед одной вершины может также быть соседом другой вершины на границе. В результате расстояние до этого соседа может проверяться и обновляться более одного раза. Хотя эти гонки тратят ресурсы и приводят к ненужным накладным расходам, с помощью синхронизации они не влияют на корректность BFS, так что эти гонки являются безобидными. Во-вторых, несмотря на ускорение прохождения каждого слоя за счет параллельной обработки, барьер синхронизация необходима после каждого слоя, чтобы полностью обнаружить все соседние вершины на границе. Эта послойная синхронизация указывает на то, что этапы необходимого взаимодействия равны самым длительным расстояние между двумя вершинами, O (d), куда О это нотация большой O и d - это диаметр графика.

Это простое распараллеливание асимптотическая сложность в худшем случае аналогичен последовательному алгоритму, но можно сделать некоторые оптимизации для достижения лучшего распараллеливания BFS, например:

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

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

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

Параллельная BFS с общей памятью

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

Модель с общей памятью.

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

Многие параллельные алгоритмы BFS для общей памяти можно разделить на два типа: подходы, ориентированные на контейнер, и подходы, ориентированные на вершины.^[3] При контейнерно-ориентированном подходе создаются две структуры данных для хранения текущей границы и следующей границы вершины. Граница следующей вершины переключается на текущую границу в конце каждого шага. Существует компромисс между стоимостью синхронизации и локализацией данных в зависимости от места хранения данных. Эти две структуры данных могут храниться в каждом обрабатывающем объекте (например, потоке), который поддерживает локальность данных, но требует дополнительных механизмов балансировки нагрузки. В качестве альтернативы они могут быть глобальными для обеспечения неявной балансировки нагрузки, когда специальные структуры данных используются для одновременного доступа от обрабатывающих объектов. Но тогда эти обрабатывающие объекты будут работать одновременно, и для синхронизации потребуется больше усилий.

Кроме того, можно оптимизировать организацию данных контейнеров. Типичная структура данных в последовательной BFS и некоторых параллельных BFS: Очередь FIFO, поскольку это просто и быстро, когда операция вставки и удаления требует только постоянного времени.

Другой альтернативой является конструкция мешка.^[4]. Операция помещения в сумку занимает O (войти) время в худшем случае, тогда как это занимает только постоянное амортизированное время который работает так же быстро, как FIFO. Кроме того, объединение двух сумок занимает Θ (lgn) time, где n - количество элементов в меньшей сумке. Операция разделения пакетов также требует Θ (lgn) время. С помощью bag-структуры определенное количество вершин (в соответствии с параметром гранулярности) хранится в одном мешке, и bag-структура становится базовой параллельной сущностью. Более того, редуктор может быть объединен со структурой bag для параллельной записи вершин и эффективного обхода их.

Вершинно-ориентированный подход рассматривает вершину как параллельный объект ，, что позволяет выполнять параллельные итерации. Каждой вершине назначается параллельный объект. Этот подход, ориентированный на вершины, может работать хорошо, только если глубина графа очень мала. Глубина графа в BFS определяется как максимальное расстояние от любой вершины графа до исходной вершины. Следовательно, вертексцентрический подход хорошо подходит для GPU если каждый поток отображается ровно на одну вершину.^[3]

Параллельная BFS с распределенной памятью

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

Модель распределенной памяти.

1-D разбиение

1D-разделение - это самый простой способ объединить параллельную BFS с распределенной памятью. Он основан на разбиении вершин. Балансировка нагрузки по-прежнему является важной проблемой для разделения данных, которая определяет, какие преимущества мы можем получить от распараллеливания. Другими словами, каждый процессор с распределенной памятью (например, процессор) должен отвечать примерно за одинаковое количество вершин и их исходящих ребер. Для реализации хранения данных каждый процессор может хранить матрица смежности его локальных вершин, в которых каждая строка для каждой вершины представляет собой ряд исходящих ребер, представленных индексами вершин назначения.

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

Следующий псевдокод одномерной распределенной памяти BFS показывает более подробную информацию, взятую из статьи.^[5]. Этот алгоритм изначально разработан для IBM BlueGene / L системы, которая имеет 3D тор сетевая архитектура. Поскольку синхронизация - это основная дополнительная плата за распараллеливание BFS, авторы этой статьи также разработали масштабируемую всеобщее общение на основе связь точка-точка. После этого они также сократили количество двухточечных соединений, воспользовавшись преимуществами высокопроизводительной торовой сети.

Основные этапы обхода BFS в следующем алгоритме:

1. представление процессора (строка 8): построить границу FS с вершинами из локального хранилища
2. глобальное представление (строка 10-11): завершить обход, если ФС всех процессоров пуста
3. представление процессора (строка 13): построить следующую границу на основе вершины соседей его FS, хотя некоторые из их соседей могут храниться в других процессорах
4. глобальное представление (строка 15-18): запустите всеобщую коммуникацию, чтобы каждый процессор знал, какие локальные вершины должны быть помещены в его локальную следующую границу NS
5. представление процессора (строки 20-22): получать сообщения от всех других процессоров, обновлять значение расстояния до их локальных вершин на текущей границе, изменять его NS на FS

1    определять 1_D_distributed_memory_BFS (график (V, E), источники): 2 // нормальная инициализация3        за все v в V делать4 d [v] = -1; 5 d [s] = 0; level = 0; FS = {}; NS = {}; 6 // начинаем обход BFS7        пока Истинный делать: 8 FS = {множество локальных вершин с уровнем} 9 // пройдены все вершины10           если FS = {} для всех процессоров тогда: 11 завершить цикл while12 // строим NS на основе локальных вершин на текущей границе13 NS = {соседи вершин в FS, как локальные, так и нелокальные вершины} 14 // синхронизация: общение всех со всеми15           за 0 <= j 
делать: 16 N_j = {вершины в NS принадлежат процессору j} 17 Отправить N_j к процессору j18 получить N_j_rcv от процессора j19 // объединяем полученное сообщение, чтобы сформировать локальную границу следующей вершины, а затем обновить для них уровень20 NS_rcv = Союз (N_j_rcv) 21 за v в NS_rcv и d [v] == -1 делать22 d [v] = уровень + 1

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

Благодаря многопоточности локальные вершины в пограничной FS могут быть разделены и назначены разным потокам внутри одного процессора, что в дальнейшем параллельно проходит обход BFS. Однако, в отличие от методов, описанных выше, нам нужно больше структуры данных для каждого отдельного потока. Например, стек потока, который подготовлен для сохранения соседних вершин из вершин этого потока. Каждый поток имеет локальное хранилище p-1, где p - количество процессоров. Потому что каждый поток должен разделять сообщения для всех остальных процессоров. Например, они будут помещать свои соседние вершины в свой j-й стек для формирования сообщения, отправляемого j-му процессору, если j-й процессор является владельцем этих вершин. Кроме того, для синхронизации необходим Thread барьер. В результате, хотя распределенная память с многопоточностью может выиграть от улучшения распараллеливания, она также приводит к дополнительной стоимости синхронизации для потоков.

Основные этапы обхода BFS в следующем алгоритме:

1. представление потока (строки 19-22): на основе присвоенных себе вершин найти процессор-владелец соседних вершин, поместить их в базу стека потоков по их владельцам.
2. представление процессора (строка 23): запустите барьер потока, дождитесь, пока все потоки (одного процессора) завершат свою работу.
3. представление процессора (строки 25-26): объединить все стеки потоков всех потоков, у которых есть один и тот же владелец (они имеют место назначения для следующего шага).
4. глобальное представление (строки 28-30): запустите всеобщую связь с главным потоком, чтобы каждый процессор знал, какие локальные вершины следует поместить в следующую границу.
5. вид процессора (строка 31): запустить барьер потока, дождаться завершения связи (главного потока).
6. представление процессора (строка 33): назначьте вершины со следующей границы каждому потоку.
7. представление потока (строки 34-36): если вершина не посещена, обновите значение расстояния для их вершин и поместите его в стек потока для следующей границы NS.
8. представление процессора (строка 37): запустите барьер потока, дождитесь, пока все потоки (одного процессора) завершат свою работу.
9. представление процессора (строка 39): совокупные стеки потоков для следующей границы из каждого потока
10. представление процессора (строка 40): запустить барьер потока, дождаться, пока все потоки отправят все свои вершины в своем стеке.

1    определять 1_D_distributed_memory_BFS_with_threads (график (V, E), источники): 2 // нормальная инициализация3        за все v в V делать4 d [v] = -1; 5 уровень = 1; FS = {}; NS = {}; 6 // находим индекс процессора-владельца исходной вершины s7 pu_s = find_owner (s); 8 если pu_s = index_pu тогда9 нажатий (с, FS); 10 дней [с] = 0; 11 // инициализация сообщения12       за 0 <= j 
делать13 sendBuffer_j = {} // p общих буферов сообщений 14 recvBuffer_j = {} // для связи MPI 15 thrdBuffer_i_j = {} // стек локального потока для потока i16 // начинаем обход BFS17       пока ПС! = {} делать18           // проходим вершины и находим владельцев соседних вершин19           за каждый u в FS в параллельно делать20               за каждый сосед v из вас делать21 pu_v = find_owner (v) 22 push (v, thrdBuffer_i_ ​​(pu_v)) 23 Нитевой барьер24           // объединяем стек потока для формирования sendBuffer25           за 0 <= j 
делать26 объединить thrdBuffer_i_j параллельно 27 // общение со всеми 28 Полный коллективный шаг с главным потоком: 29 1. отправка данных в sendBuffer30 2. получение и агрегирование вновь посещенных вершин в recvBuffer31 Нитевой барьер32           // обновить уровень для новых посещенных вершин 33           за каждый u в recvBuffer в параллельно делать34               если d [u] == -1 тогда35 d [u] = level36 push (u, NS_i) 37 Нитевой барьер38           // агрегировать NS и формировать новую FS 39 FS = Союз (NS_i) 40 Нитевой барьер41 уровень = уровень + 1f

2-мерное разбиение

Поскольку алгоритм BFS всегда использует матрица смежности как представление графа. Также можно рассмотреть естественное двухмерное разложение матрицы. При двумерном разбиении каждый процессор имеет двумерный индекс (i, j). Ребра и вершины назначаются всем процессорам с двухмерной блочной декомпозицией, в которых хранится матрица субсмежности.

Если всего процессоров P = R · C, то матрица смежности будет разделена, как показано ниже:

2D-разбиение матрицы смежности.

После этого деления идут столбцы C и строки блока R · C. Для каждого процессора они отвечают за C блоков, а именно процессор (i, j) хранит A_{я, j}⁽¹⁾ к А_{я, j}^(С) блоки. Обычное одномерное разбиение эквивалентно двумерному разбиению с R = 1 или C = 1.

В общем, параллельная обработка краев на основе двумерного разбиения может быть организована в 2 фазы связи, а именно фазу «развертывания» и фазу «свертывания».^[6]

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

На этапе «сворачивания» вершины, образующие следующую границу, отправляются процессорам-владельцам для локального формирования новой границы. При двухмерном разбиении эти процессоры находятся в одном ряду процессоров.^[5]

Основными этапами обхода BFS в этом алгоритме двухмерного разбиения являются (для каждого процессора):

1. фаза расширения (строки 13-15): на основе локальных вершин отправлять сообщения процессорам в столбце процессора только для того, чтобы сообщить им, что эти вершины находятся на границе, получать сообщения от этих процессоров.
2. (строка 17-18): объединить все полученные сообщения и сформировать границу сети N. Обратите внимание, что не все вершины из полученных сообщений должны быть помещены в следующую границу, некоторые из них уже могут быть посещены. Следующая граница содержит только вершины со значением расстояния -1.
3. Фаза свертки (строки 20-23): на основе локальных вершин в следующей границе, отправлять сообщения процессорам-владельцам этих вершин в строке процессора.
4. (строки 25-28): объединить все получаемые сообщения и обновить значение расстояния до вершин на следующей границе.

Псевдокод ниже описывает более подробную информацию о алгоритме 2D BFS, который взят из статьи:^[5]

1    определять 2_D_distributed_memory_BFS (график (V, E), источники): 2 // нормальная инициализация3        за все v в V делать4 d [v] = -1; 5 d [s] = 0; 6 // начинаем обход BFS7        за l = 0 до бесконечности делать: 8 F = {множество локальных вершин уровня l} 9 // пройдены все вершины10           если F = {} для всех процессоров тогда: 11 завершить цикл while12 // проходим вершины, отправляя сообщение выбранному процессору13           за весь процессор q в этом столбце процессора делать:14               послать F к процессору q15 Получить Fqр с q16 // обрабатываем полученную информацию после прохождения границы17 Fр = Союз {Fqр} для всех q18 N = {соседи вершин в Fр с использованием списков ребер на этом процессоре} 19 // транслируем соседние вершины, отправляя сообщение их процессору-владельцу20           за весь процессор q в этой строке процессора делать: 21 с.ш.q = {вершины в N принадлежат процессору q} 22 послать Nq к процессору q23 Получить Nqр с q24 // формируем следующую границу, используемую для обхода следующего слоя25 с.ш.р = Союз {Nqр} для всех q26 // обновление расстояния между слоями27           за v в Nр и d (v) = - 1 делать: 28 уровень = l + 1

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

Стратегии оптимизации внедрения

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

Оптимизация направления

В оригинальной нисходящей BFS каждая вершина должна проверять всех соседей вершины на границе. Иногда это неэффективно, когда на графике низкая диаметр.^[7] но некоторые вершины внутри имеют гораздо более высокие степени, чем в среднем, например, граф малого мира^[8]. Как упоминалось ранее, одна благоприятная гонка в параллельной BFS заключается в том, что если более одной вершины на границе имеют общие соседние вершины, расстояние до соседних вершин будет проверяться много раз. Хотя обновление расстояния по-прежнему корректно с помощью синхронизации, ресурс тратится впустую. Фактически, чтобы найти вершины для следующей границы, каждой непосещенной вершине нужно только проверить, находится ли какая-либо ее соседняя вершина на границе. Это также основная идея для оптимизации направления. Еще лучше то, что каждая вершина быстро найдет родительский элемент, проверив входящие ребра, если значительное количество ее соседей находится на границе.

В газете^[8]авторы вводят восходящую BFS, где каждой вершине нужно только проверить, находится ли кто-либо из их родителей на границе. Это можно определить эффективно, если граница представлена битовая карта. По сравнению с нисходящей BFS, восходящая BFS сокращает количество проверок сбоев за счет самоанализа родителя для предотвращения конфликтов.

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

Баланс нагрузки

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

Рандомизация - один из простых и полезных способов балансировки нагрузки. Например, в бумаге^[6], граф обходится путем случайного перемешивания идентификаторов всех вершин перед разделением.

Структура данных

Пример CSR-представления ориентированного графа.

Структура данных вымпела для k = 0 до k = 3.

Пример конструкции сумки из 23 элементов.

Существуют некоторые специальные структуры данных, от которых может выиграть параллельный BFS, например CSR (сжатая разреженная строка), bag-structure, битовая карта и так далее.

В CSR все смежности вершины сортируются и компактно хранятся в непрерывном блоке памяти, при этом смежность вершины i + 1 находится рядом со смежностью i. В примере слева есть два массива, C и R. В массиве C хранятся списки смежности всех узлов. В массиве R хранится индекс в C, запись R [i] указывает на начальный индекс списков смежности вершины i в массиве C. CSR выполняется чрезвычайно быстро, поскольку для доступа к смежности вершин требуется только постоянное время. Но это только для одномерного разбиения.^[6]. Более подробную информацию о КСО можно найти в^[9]. Для двумерного разбиения больше подходит DCSC (дважды сжатые разреженные столбцы) для гиперразреженных матриц, дополнительную информацию о DCSC можно найти в статье.^[10]

В газете^[4], авторы разрабатывают новую структуру данных, называемую bag-structure. Структура мешка построена на основе структуры данных вымпела. Вымпел - дерево из двух^k nodex, где k - неотрицательное целое число. Каждый корень x в этом дереве содержит два указателя x.left и x. right своим детям. У корня дерева есть только левый дочерний элемент, который является полным двоичное дерево оставшихся элементов^[4].

Структура мешка представляет собой набор вымпелов с опорным массивом S. Каждая запись S [i] в ​​S является либо нулевым указателем, либо указателем на вымпел размером s^я. Операция помещения в сумку занимает О (1) амортизированное время и объединение двух сумок занимает Θ (lgn) время. Разделение пакетов также требует Θ (lgn) время. С этой пакетной структурой параллельному BFS разрешено записывать вершины уровня в единую структуру данных параллельно, а затем эффективно проходить их параллельно.^[4]

Более того, битовая карта также очень полезная структура данных для запоминания того, какие вершины уже посещены, независимо от восходящей BFS.^[11] или просто чтобы проверить, посещаются ли вершины в нисходящей BFS^[9]

Контрольные точки

График500 это первый тест для решения проблем суперкомпьютеров с интенсивным использованием данных^[1]. Этот тест сначала генерирует реберный кортеж с двумя конечными точками. Затем ядро ​​1 построит неориентированный граф, в котором вес ребра не будет назначен, если после этого будет работать только ядро ​​2. Пользователи могут выбрать запуск BFS в ядре 2 и / или Single-Source-Shortest-Path в ядре 3 на построенном графе. Результат этих ядер будет проверен, и время работы будет измерено.

График500 также предоставляет две эталонные реализации для ядра 2 и 3. В упомянутой BFS исследование вершин просто отправляет сообщения целевым процессорам, чтобы информировать их о посещенных соседях. Дополнительного метода балансировки нагрузки нет. Для синхронизации используется AML (библиотека активных сообщений, СПМД коммуникационная библиотека, построенная поверх MPI3, предназначенные для использования в приложениях с мелким зерном, таких как Graph500), барьер обеспечивает постоянный проход после каждого слоя. Указанный BFS используется только для проверки правильности результатов. Таким образом, пользователи должны реализовать собственный алгоритм BFS на основе своего оборудования. Выбор BFS не ограничен, если выходное дерево BFS является правильным.

Правильность результата основывается на сравнении с результатом упомянутого BFS. Поскольку для запуска ядра 2 и / или ядра 3 выбираются только 64 ключа поиска, результат также считается правильным, если этот результат отличается от результата, на который ссылаются, только потому, что ключ поиска отсутствует в выборках. Эти 64 ключа поиска также последовательно запускают ядро ​​для вычисления среднего значения и дисперсии, с помощью которых измеряется производительность одного поиска.

Отличается от TOP500, показатель производительности в График500 является Пройденных краев в секунду (TEPS).

Смотрите также

• Параллельный алгоритм
• Распределенный алгоритм

Ссылка

1. График500
2. «Разработка многопоточных алгоритмов для поиска в ширину и возможности st-подключения на Cray MTA-2»., Бадер, Дэвид А., и Камеш Маддури. 2006 Международная конференция по параллельной обработке (ICPP'06). IEEE, 2006 г.
3. «Синхронные по уровню параллельные алгоритмы поиска в ширину для многоядерных и многопроцессорных систем»., Рудольф и Матиас Макулла.FC 14 (2014): 26-31.]
4. «Эффективный алгоритм параллельного поиска в ширину (или как справиться с недетерминизмом редукторов)»., Лейзерсон, Чарльз Э., и Тао Б. Шардл. Материалы двадцать второго ежегодного симпозиума ACM по параллелизму в алгоритмах и архитектурах. ACM, 2010.
5. «Масштабируемый распределенный параллельный алгоритм поиска в ширину на BlueGene / L»., Ю, Энди и др. Материалы конференции ACM / IEEE 2005 г. по суперкомпьютерам. Компьютерное общество IEEE, 2005.
6. «Параллельный поиск в ширину в системах с распределенной памятью»., Булуч, Айдын и Камеш Маддури. Труды Международной конференции 2011 года по высокопроизводительным вычислениям, сетям, хранению данных и анализу. ACM, 2011.
7. «Коллективная динамика сетей« маленького мира »»., Уоттс, Дункан Дж., и Стивен Х. Строгац. природа 393.6684 (1998): 440.
8. «Поиск в ширину с оптимизацией направления»., Бимер, Скотт, Крсте Асанович, и Дэвид Паттерсон. Научное программирование 21.3-4 (2013): 137-148.
9. «Масштабируемый обход графа графического процессора», Меррилл, Дуэйн, Майкл Гарланд и Эндрю Гримшоу. Уведомления Acm Sigplan. Vol. 47. № 8. АКМ, 2012.
10. «О представлении и умножении гипер разреженных матриц». Булук, Айдын и Джон Р. Гилберт. Международный симпозиум IEEE по параллельной и распределенной обработке, 2008 г. IEEE, 2008 г.
11. «Поиск в ширину с распределенной памятью на массивных графах». Buluc, Aydin, et al. Препринт arXiv arXiv: 1705.04590 (2017).