Н-БФТ

Новый простой, быстрый и распараллеливаемый алгоритм обхода в ширину (BFT) для больших разреженных графов с несколькими входами и несколькими выходами.

Эту реализацию можно использовать для любого типа графов, но здесь мы реализовали это для графов схемы EDA. Согласно закону Мура, с удвоением количества транзисторов в электронных схемах каждые два года сложность цифровых электронных схем также увеличивается день ото дня. Это одна из самых больших проблем, с которыми сталкивается индустрия EDA (автоматизация электронного проектирования).

Здесь мы реализовали однопоточную реализацию H-BFT и ее многопоточную реализацию. Хотя существует много способов повысить производительность многопоточного BFT, мы используем графический процессор (GPU), чтобы получить значительное ускорение.

Как правило, для разреженных графов обход в ширину выполняется с использованием реализации разреженного матричного векторного произведения (SMVP). Но если мы используем алгоритм SMVP на графическом процессоре, он становится дорогостоящим методом вычислений BFT. Но наш новый алгоритм проходит через граф уровень за уровнем без каких-либо дорогостоящих вычислений.

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

• Данные графика, которые вводятся в H-BFS, переносятся в «GraphList». Первоначально массив «уровень» заполняется значениями -1, чтобы указать, что эти вершины не посещаются. Поскольку мы знаем входные вершины, мы делаем уровни этих вершин равными нулю, чтобы указать, что эти вершины являются входами в схему.
• Наша версия ЦП представляет собой однопоточную реализацию. Мы просматриваем GraphList (массив структур Edge) одну за другой и проверяем значение уровня вершины «От» и вершины «до». Если значение уровня
  вершины «От» является неотрицательным значением, а значение уровня вершины «до» является отрицательным значением, то значение уровня вершины «до» обновляется. Продолжаем этот процесс, пока массив уровней не заполнится неотрицательными значениями.
• Для реализации GPU используются те же структуры данных. Кроме того, мы используем динамический параллелизм с использованием потоков графического процессора. Из ЦП parentKernel вызывается с использованием одного потока в одном блоке. Это родительское ядро ​​отвечает за обход в ширину в параллельном алгоритме H-BFT. Это ядро ​​будет запускать дочерние ядра BreadthFirstSearch и isLevelFilled повторно
  до тех пор, пока весь массив уровней не заполнится неотрицательными значениями.

__global__ void parentKernel(struct Edge *adjacencyList, int * vertices, int * level,int * lev, int * edges){
         *lev=1;
         int kb=0;
          while(*lev){
                 kb = kb+1;
                 BreadthFirstSearch<<<ceil(*edges/256.0),256>>>(adjacencyList,vertices,level,lev,edges);
                 cudaDeviceSynchronize();
                 isLevelFilled<<<ceil(*vertices/256.0),256>>>(level,vertices,lev);
                 cudaDeviceSynchronize();
           }
}

• Реализация процессора была протестирована на сервере с процессором Intel i7 6-го поколения (6700K) и 32 ГБ ОЗУ. Реализации этого графического процессора были протестированы на видеокарте NVIDIA Kepler K40 с 2880 ядрами CUDA и
  12 ГБ выделенной оперативной памяти. Сгенерированные нами графы состоят из постоянного количества вершин (n), равного 10⁶, и разного количества ребер (nnz) от 10⁷ до 10⁸.

Согласно результатам, для графа с 10⁶ узлами и 10⁸ ребрами мы достигли 10-кратной производительности GPU по сравнению с CPU. Наконец, в качестве заключения мы можем показать результаты следующим образом. Кроме того, наша версия ЦП H-BFT в 75 раз быстрее, чем версия ЦП SMVP-BFT, которая обычно используется в инструментах EDA.

Дополнительные сведения см. в моей статье H-BFT: алгоритм быстрого обхода в ширину для разреженных графов и его реализация на графическом процессоре.

Найдите коды реализованного алгоритма H-BFT на GitHub.

Соответствующий исследовательский документ, который мы опубликовали в материалах 6-й Международной конференции IEEE по информации и автоматизации для устойчивого развития (ICIAfS), декабрь 2016 г., Галле, Шри-Ланка, теперь доступен по адресу https://ieeexplore.ieee.org/document/ 7946532/