НЕБОЛЬШОЕ ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
Погрузитесь в мир мелкомасштабного параллельного программирования, изучая производительность OpenMP и CUDA при обработке разреженного умножения матрицы на вектор, раскрывая сложную взаимосвязь между моделями программирования и характеристиками матриц.
- Литературный обзор
- Методология
- Полученные результаты
- Заключение
Умножение разреженной матрицы на вектор (SpMV), важнейшая операция в научных вычислениях, представляет собой сложную и динамичную область со множеством проблем, которые необходимо решить для достижения оптимальной производительности.
В этом исследовании мы изучили производительность OpenMP и CUDA для SpMV на гибридной платформе ЦП и ГП. Мы реализовали обе модели программирования на наборе разреженных матриц разного размера и плотности.
Наши результаты выявили связь между выбором модели программирования и характеристиками используемой разреженной матрицы. В частности, OpenMP превосходил CUDA на меньших матрицах с меньшим количеством ненулевых элементов, тогда как CUDA был более эффективным на больших матрицах с более высокой плотностью ненулевых элементов.
Литературный обзор
Разреженные матрицы
Умножение разреженной матрицы на вектор (SpMV) — это фундаментальная операция, которая широко используется в научных и инженерных областях, таких как численное моделирование, машинное обучение и анализ данных. Эта операция включает в себя умножение матрицы, состоящей из нулевых элементов, на вектор, в результате чего получается линейная комбинация столбцов матрицы, взвешенная по соответствующим элементам вектора. Основная проблема при умножении разреженной матрицы на вектор заключается в том, что матрица преимущественно разреженная, что указывает на то, что она содержит большое количество нулевых элементов.
На самом деле разреженная матрица определяется Джеймсом Уилкинсоном [1] следующим образом:
"Любая матрица с достаточным количеством нулей, чтобы выгодно ими воспользоваться".
Численно это переводится как количество ненулевых элементов (NZ) намного меньше, чем количество строк по столбцам: [2]
NZ ≪ M × N
Хотя эту разреженность можно использовать для снижения вычислительных затрат, она также усложняет распараллеливание операции, поскольку рабочая нагрузка распределяется по элементам матрицы неравномерно.
В последние годы исследования были посвящены изучению и разработке алгоритмов разреженного умножения матрицы на вектор, при этом ядро SpMV стало выдающимся и широко используемым подходом. Однако растущий масштаб наборов данных в последних областях, управляемых данными, требует изучения более эффективных и масштабируемых методов. Чтобы решить эту проблему, были исследованы среды параллельного программирования, в частности OpenMP и CUDA, как средства достижения превосходной производительности в SpMV.
Вычисления разреженных матриц сложны, а производительность компьютерного кластера часто низка. Фактически, разреженные матрицы требуют явного представления координат ненулевых элементов, что увеличивает пропускную способность памяти, необходимую для манипулирования ими во время вычислений. Более того, вычисления разреженных матриц требуют меньше повторного использования значений, чем плотные матрицы, что затрудняет эффективное использование регистров и кэшей. Кроме того, циклическая структура вычисления разреженного произведения матрицы-вектора менее регулярна, чем структура цикла вычисления произведения плотной матрицы-вектора, что приводит к менее эффективному коду, сгенерированному компилятором. [4]
Для решения этих проблем были изучены методы, в том числе разработка различных представлений разреженных матриц, переупорядочивание матриц, совместное использование нескольких представлений, блокировка кэша и регистров, а также комбинации этих подходов. Используя эти методы, можно повысить производительность вычислений с разреженными матрицами, тем самым делая возможным их применение в широком диапазоне научных и инженерных областей.
CUDA и OpenMP
Среды параллельного программирования, такие как OpenMP и CUDA, продемонстрировали значительный потенциал в повышении производительности умножения разреженной матрицы на вектор. OpenMP — это модель параллельного программирования с общей памятью, которая предоставляет эффективные средства использования многоядерных процессоров в среде с общей памятью, что делает ее пригодной для параллелизма, включая разреженное умножение матрицы на вектор.
В отличие от этого, CUDA — это среда параллельного программирования, разработанная NVIDIA, которая специально разработана для использования с графическими процессорами, обеспечивая огромную мощь параллелизма современных графических процессоров, содержащих тысячи потоков обработки, которые можно эффективно использовать параллельно. Как отмечают Натан Белл и Майкл Гарланд [3], модель программирования CUDA может обеспечить высокую производительность и масштабируемость для SpMV, особенно для матриц значительного размера.
Предыдущие исследования сравнивали производительность OpenMP и CUDA для умножения разреженной матрицы на вектор и пришли к выводу, что CUDA предпочтительнее для более масштабных задач, тогда как OpenMP больше подходит для небольших задач и для систем с относительно небольшим количеством ядер.
Использование сред параллельного программирования OpenMP и CUDA оказалось эффективным для повышения производительности умножения разреженной матрицы на вектор. Выбор оптимальной платформы может зависеть от конкретных требований приложения, и всестороннее понимание сильных и слабых сторон каждой платформы имеет решающее значение для достижения высокой производительности и масштабируемости.
Цели
Цели следующих отчетов заключаются в следующем:
- Разработайте и протестируйте параллельное ядро продукта SpMV, способное вычислять y ← Ax, где A — разреженная матрица, хранящаяся либо в формате CSR, либо в формате ELLPACK.
- Распараллеливайте ядро, чтобы использовать доступные вычислительные возможности с использованием версий OpenMP и CUDA.
- Разработайте вспомогательные функции для предварительной обработки матричных данных и представления их в нужном формате.
- Протестируйте производительность ядра на указанном наборе матриц, полученных из набора разреженных матриц Suite.
Методология
Форматы матриц
В ходе проекта использовались несколько методов форматирования разреженной матрицы, в частности, для хранения информации о файле, о структуре данных и проведения экспериментов. Обратите внимание, что теперь каждое индексирование будет основано на C/C++, что означает, что первый элемент будет проиндексирован как 0 в массиве.
главный операционный директор
Формат списка координат (COO) является широко используемым представлением разреженных матриц. Этот формат хранит ненулевые элементы в виде кортежа индекса строки, индекса столбца и значения, как показано на рисунке 1. Формат COO очень гибок и эффективен для построения и преобразования в другие форматы разреженных матриц, поэтому используемые матрицы в следующем проекте хранятся в формате COO в файлах. При обработке матриц формат COO будет преобразован в CSR или ELLPACK, которые будут храниться в различных структурах данных внутри компьютерного кластера. Память, используемая для хранения разреженной матрицы в формате COO, представляет собой три массива элементов NZ.
КСО
Формат Compressed Storage by Row (CSR) используется для представления разреженных матриц и улучшает вычислительные возможности. Он использует три одномерных массива для хранения ненулевых значений матриц, индексов столбцов и указателей строк, как показано на рис. 2. Этот формат оптимизирован для параллельных вычислений с помощью сред OpenMP и CUDA, что делает его одним из предпочтительных методов для разреженных вычислений. умножение матрицы на вектор.
Несмотря на свои преимущества, важно отметить, что формат CSR не всегда может быть наиболее эффективным представлением для всех типов разреженных матриц. Нерегулярные шаблоны разреженности могут быть проблематичными.
Произведение матрицы на вектор в формате CSR вычисляется следующим образом, где AS, JA и IRP представляют разреженную матрицу, M — количество строк, x — входной вектор, y — выходной вектор:
Рисунок 3: Псевдокод SpMV в формате CSR:
function MatrixMultiply(AS: array of double, JA: array of int, IRP: array of int, M: int, x: array of double, y: array of double):
for i from 0 to M-1 do
t = 0
for j from IRP[i] to IRP[i+1]-1 do
t = t + x[JA[j]] * AS[j]
end for
y[i] = t
end for
end function
ЭЛЛПАК
Представление разреженной матрицы ELLPACK получило широкое распространение благодаря своей эффективности хранения и вычислений. В формате ELLPACK матрица хранится в массивах, имеющих два измерения. Каждая строка массива содержит заданное количество ненулевых элементов, при этом ненулевые значения хранятся в массиве значений, а соответствующие индексы столбцов хранятся в массиве индексов столбцов, как показано на рисунке 4. Пустые записи в матрица заполнена нулями в AS и -1 в JA. Этот формат оптимизирован для параллельных вычислений, особенно для матриц с одинаковыми шаблонами разреженности, и хорошо подходит для использования с платформами CUDA.
По сравнению с форматом CRS формат ELLPACK обеспечивает представление фиксированной длины для каждой строки, что может значительно повысить эффективность вычислений за счет использования кэшей и регистров. Более того, формат ELLPACK более эффективно использует память по сравнению с форматом CSR, особенно для матриц с одинаковыми шаблонами разреженности.
Однако важно отметить, что формат ELLPACK может быть не самым эффективным представлением матриц с нерегулярными шаблонами разреженности. Это может привести к значительным издержкам хранения и неэффективному доступу к памяти. Кроме того, представление фиксированной длины для каждой строки может быть не оптимальным для матриц с шаблонами переменной разреженности, где будет храниться много ненужных данных.
Произведение матрицы на вектор в формате ELLPACK вычисляется следующим образом: AS и JA представляют разреженную матрицу, M — количество строк, max_nz — максимальное количество ненулевых элементов в строке, x — входной вектор, y — выходной вектор:
Рисунок 5: Псевдокод SpMV в формате ELLPACK
function MatrixMultiply(JA: array of int, AS: array of double, M: int, max_nz: int, x: array of double, y: array of double):
for i from 0 to M-1 do
t0 = 0.0
for j from 0 to max_nz-1 do
if JA[i][j] == -1 then
break
end if
t0 = t0 + AS[i][j] * x[JA[i][j]]
end for
y[i] = t0
end for
end function
Развертывание цикла
Развертывание цикла — это метод, используемый компиляторами или непосредственно внутри исходного кода, который направлен на сокращение времени выполнения программ за счет уменьшения количества выполнений цикла. Копируя тело цикла и увеличивая счетчик цикла на большее значение, он позволяет выполнять несколько итераций цикла в одном цикле, уменьшая накладные расходы на инструкции управления циклом. Развертывание цикла может быть особенно полезным для компьютерных архитектур, в которых отсутствует параллелизм, таких как процессоры с ограниченным числом потоков.
Преимущества развертывания цикла многочисленны. Увеличивая объем работы, выполняемой за итерацию, и уменьшая количество итераций, развертывание цикла может улучшить использование кэша инструкций программы, что способствует более быстрому времени выполнения.
Однако, хотя развертывание цикла может быть очень эффективным методом оптимизации последовательного кода на процессорах с ограниченным параллелизмом, это не оптимальный выбор для параллельного кода, работающего на графических процессорах. В этих ситуациях такие стратегии, как объединение памяти, блокировка потоков и общая память, используются для повышения производительности графических процессоров за счет использования параллелизма в большем масштабе. Стоит отметить, что развертывание цикла увеличивает использование регистров в архитектуре, что, вероятно, создаст крышу максимального развертывания, которое стоит кодировать на конкретном оборудовании.
CUDA
Парадигма распараллеливания CUDA основана на использовании большой архитектуры потоков, которую предлагает GPU. Это достигается запуском нескольких потоков, работающих одновременно на GPU. Каждый поток выполняет определенные вычисления на небольшом подмножестве данных, которое обычно состоит из единственного элемента или уменьшительного блока элементов, полученных из входных данных. Парадигма распараллеливания CUDA относится к распараллеливанию задачи на максимальном количестве потоков.
Парадигма программирования CUDA предоставляет метод организации потоков в двухуровневую иерархию, состоящую из блоков потоков и сеток. Блок относится к группе потоков, которые могут взаимодействовать и синхронизироваться за счет использования быстрой общей памяти. Сетка — это совокупность блоков, которые работают независимо и могут обмениваться данными только через глобальную память. Наиболее распространенным подходом к распараллеливанию является распараллеливание одномерных блоков и сеток, при котором данные делятся на одномерные массивы, а одномерная структура блоков и сеток используется для распараллеливания вычислений, как показано на рисунке 6.
В определенных обстоятельствах может быть более эффективным использование двумерной блочной и сеточной структуры, которая может оптимизировать шаблоны доступа к памяти и уменьшить расхождение потоков. Двухмерное распараллеливание блоков и сеток особенно полезно в области обработки изображений и других приложений, работающих с двумерными структурами данных, как показано на рисунке 7.
CUDA использует не только блоки и сетки, но и варпы для параллельного выполнения потоков на одном процессоре. Деформация состоит из потоков, которые выполняются в унисон, и количество потоков, присутствующих в варпе, обычно составляет 32, в зависимости от архитектуры графического процессора, это наименьшая единица работы в CUDA. Для обеспечения оптимальной производительности крайне важно свести к минимуму расхождение деформации. Это явление имеет место, когда потоки внутри деформации следуют по разным путям в потоке программы, что приводит к тому, что некоторые потоки простаивают, а другие все еще выполняются. В результате время выполнения имеет тенденцию увеличиваться, тем самым снижая общую производительность.
Экспериментальная оценка
Эксперименты будут проводиться на нескольких матрицах коллекции SuiteSparse Matrix Collection Университета Флориды (https://sparse.tamu.edu/). Набор анализируемых матриц следующий:
Table 1: Matrix analysis
Matrix Name M NZ Avg_NZ Max_NZ Symmetric
--------------------- --------- ----------- -------- -------- -----------
cavity10.mtx 2597 76367 29.4 62 False
PR02R.mtx 161070 8185136 50.8 92 False
nlpkkt80.mtx 1062400 28704672 27.0 28 True
Cube_Coup_dt0.mtx 2164760 127206144 58.8 68 True
roadNet-PA.mtx 1090920 3083796 2.8 9 True
ML_Laplace.mtx 377002 27689972 73.4 74 False
bcsstk17.mtx 10974 428650 39.1 150 True
mhda416.mtx 416 8562 20.6 33 False
af_1_k101.mtx 503625 17550675 34.8 35 True
thermal1.mtx 82654 574458 7.0 11 True
thermomech_TK.mtx 102158 711558 7.0 10 True
rma10.mtx 46835 2374001 50.7 145 False
cage4.mtx 9 49 5.4 6 False
cant.mtx 62451 4007383 64.2 78 True
dc1.mtx 116835 766396 6.6 114190 False
raefsky2.mtx 3242 294276 90.8 108 False
lpi_itest6.mtx 11 29 2.6 3 False
rdist2.mtx 3198 56934 17.8 61 False
mcfe.mtx 765 24382 31.9 81 False
olm1000.mtx 1000 3996 4.0 6 False
lung2.mtx 109460 492564 4.5 8 False
webbase-1M.mtx 1000005 3105536 3.1 4700 False
mhd4800a.mtx 4800 102252 21.3 33 False
west2021.mtx 2021 7353 3.6 12 False
thermal2.mtx 1228045 8580313 7.0 11 True
adder_dcop_32.mtx 1813 11246 6.2 100 False
mac_econ_fwd500.mtx 206500 1273389 6.2 44 False
FEM_3D_thermal1.mtx 17880 430740 24.1 27 False
amazon0302.mtx 262111 1234877 4.7 5 False
cop20k_A.mtx 121192 2624331 21.7 81 True
olafu.mtx 16146 1015156 62.9 89 True
can_24.mtx 24 160 6.7 9 True
af23560.mtx 23560 484256 20.6 21 False
В матрице много разнообразия и разреженности, что будет полезно для сравнения и понимания поведения и преимуществ каждой формы хранения в CUDA и OpenMP. Коллекция матриц также включает некоторые большие матрицы, такие как Cube_Coup_dt0.mtx, которая содержит более 127 миллионов ненулевых элементов и более миллиона строк. В результирующей части для наглядности выделено несколько матриц результата, которые будут представлены в качестве результата; выбор был сделан, чтобы иметь разнообразие шаблонов разреженности.
Чтобы понять разницу в разреженности и специфику каждой матрицы, мы можем визуализировать некоторые из них.
Описание оборудования
Используемая структура HPC — это Crescent, исследовательское учреждение, расположенное в Крэнфилдском университете. Наше исследование будет опираться на Tesla K40m в качестве основного устройства. Устройство состоит из 15 мультипроцессоров, каждый из которых имеет 192 ядра CUDA, всего 2880 ядер CUDA. Устройство имеет ширину шины памяти 384 бита, что делает доступным в общей сложности 12 207 МБ глобальной памяти и 32 регистра. Для обработки больших наборов данных Tesla K40m может работать с различными размерами BlockSize. Кроме того, устройство может поддерживать максимальное количество потоков на блок 1024 и имеет размер деформации 32.
Эксперименты
Многочисленные конфигурации, методы развертывания циклов и методы распараллеливания будут выполнены в следующей части результатов, чтобы проанализировать эффект и понять влияние на память, кеш и эффективность каждого из них. Форматы CSR и ELLPACK будут сравниваться во время выполнения. Скорость вычислений будет вычисляться с использованием GFlops, который является показателем производительности с точки зрения операций с плавающей запятой. GFlops рассчитываются следующим образом:
На ЦП SpMV будет вычисляться с использованием OpenMP на 1, 2, 4, 8 и 16 потоках для нескольких методов развертывания: горизонтальное развертывание — когда одна строка обрабатывается за раз путем доступа к нескольким последовательным элементам одновременно — и вертикальное развертывание — где несколько строк обрабатываются одновременно параллельно. Каждый метод развертывания будет протестирован с разными уровнями параллелизма: 2, 4, 8 и 16.
На графических процессорах SpMV будет вычисляться с использованием CUDA на одном графическом процессоре для нескольких методов распараллеливания: 1D-блок и 1D-сетка, 2D-блок и 1D-сетка, где каждая строка блока вычисляет одну строку параллельно. Для формата ELLPACK будет проведен дополнительный анализ, в котором двухмерные массивы JA и AS транспонируются, и каждая строка вычисляется с использованием одного потока с использованием одномерного блока и одномерной сетки. Транспонированный массив позволит провести распараллеливание без каких-либо конфликтов доступа к памяти между потоками, потому что языки C являются основными языками доступа к строкам.
Полученные результаты
OpenMP
Алгоритмы и форматы хранения
Как было описано в предыдущей части, было реализовано несколько способов развертывания — горизонтальное и вертикальное развертывание — с использованием разных уровней распараллеливания — уровней 2, 4, 8 и 16. На графиках рис. 13–15 и тепловой карте рис. 14 показан результат реализации. с помощью OpenMP.
Эти результаты ясно показывают нам, что формат CSR более эффективен, а матрицы имеют более высокие GFlops с использованием CSR, чем ELLPACK. Более того, нет существенного улучшения при увеличении уровня раскатки. Наилучший найденный алгоритм — с развертыванием уровня 2. Это можно объяснить ограничением регистров внутри ЦП, чем больше развертывания мы хотим реализовать, тем больше регистров мы будем использовать для хранения временной переменной для выполнения вычислений. Если достигнут предел регистра, то не будет никакого существенного улучшения во времени, и это может даже привести к снижению эффективности ядра из-за использования менее эффективного выделения памяти и доступа.
Во-вторых, горизонтальная развертка дает лучшие результаты, чем вертикальная развертка, когда доступ к нескольким строкам осуществляется за одну итерацию. Это можно объяснить поведением кэша внутри железа и доступом к элементам на языках Си.
Одним интересным замечанием является тот факт, что для некоторых матриц существует значительная разница между форматами ELLPACK и CSR. Например, для dc1.mtx средний CSR GFlops составляет 6,01, а для ELLPACK — 0,83. Эти существенные различия произошли из-за разреженности этой матрицы с NZ_max, равным 114 190, и Avg-N, равным 6,6, как описано в таблице 1, что делает хранение в формате ELLPACK менее эффективным, поскольку в нем необходимо хранить несущественные элементы.
Резьбы и элементы НЗ
Влияние элементов NZ и количество потоков, используемых с OpenMP, были проанализированы во второй раз, что представлено результатом, показанным на рис. 16. Результат, как и ожидалось, показывает нам, что GFlops растет по мере роста количества потоков. Вычисление дает более эффективные результаты с большим количеством потоков. Существует также легкая корреляция между GFlops и количеством элементов NZ независимо от разреженности матрицы.
Наконец, наилучший алгоритм развертывания — это горизонтальное развертывание уровня 2, за которым следует вертикальное развертывание второго уровня, как показано в таблице 2. Обратите внимание, что весь исходный код был скомпилирован с использованием флага -O3, который указывает компилятору максимально оптимизировать код. насколько это возможно. Затем компилятор может выполнять дополнительные методы развертывания при компиляции исходного кода, это также может объяснить производительность кода без развертывания или однородный результат с различными методами развертывания, поскольку компилятор перестраивает исходный код во время компиляции для его оптимизации.
Table 2: OpenMP, Best unrolling method per number of threads Nbr Thread 1 2 4 8 16 ------------ ---- ---- ---- --- ---- C_2H 12 11 11 8 7 C_2V 2 4 3 3 2 C_4H 2 2 3 2 2 C_4V 1 3 0 0 2
Наконец, такие матрицы, как Cube_Coup_dt0, полости10, ML_Laplace и af_1_k101, достигли примерно 5 ускорений для 16 потоков с использованием OpenMP и горизонтальной развертки уровня 2, как показано на рис. 17.
CUDA
Алгоритмы и форматы хранения
Для CUDA были протестированы несколько методов распараллеливания, во-первых, матрицы вычислялись с использованием 1D и 2D Block внутри 1D Grid, где каждый поток в строке блока вычисляет одну и ту же строку в матрице, а затем сводит результат к окончательному вектор. Каждый метод был протестирован с различными методами развертывания и использования формата CSR и ELLPACK. Результат следующих тестов показан на рисунках 18 и 20, а также на тепловой карте на рисунке 19.
Эти результаты ясно показывают нам эффективность использования 2D-блока по сравнению с 1D-блоком для всех типов разреженности матриц, симметричных или нет. Как объясняется в части методологии, развертывание неэффективно в CUDA, и мы не достигли лучшего результата, используя методологию развертывания. Одним из интересных отличий является то, что формат ELLPACK более эффективен, чем формат CSR, чего нельзя сказать о OpenMP.
BlockSize и элементы NZ
Эффект элементов NZ такой же, как и в OpenMP, существует корреляция между элементами NZ и GFlops, как показано на рисунке 21. Мы также можем наблюдать разницу между несколькими размерами блока. Самый эффективный BlockSize — 16, а худший — 64, что изначально не является первым, что нужно иметь в виду, потому что, естественно, мы можем подумать, что с большим количеством потоков мы сможем распределить работу более равномерно и быть более эффективными. Но реальность здесь такова, что нам нужно свести результат к одному вектору, поэтому для сокращения требуется синхронизация между потоками, что может привести к менее эффективному алгоритму для слишком большого количества потоков. Еще одна вещь, которую следует иметь в виду, это тот факт, что чем больше потоков, тем больше общая память между потоками.
ELLPACK Транспонированный
Наконец, последний эксперимент состоял в том, чтобы переставить массивы JA и AS формата ELLPACK и попробовать другую методологию распараллеливания с использованием CUDA, где только один поток будет вычислять каждую строку матрицы. Таким образом, мы можем воспользоваться основным доступом к строкам C++.
Table 3: CUDA, Comparison between ELLPACK transposed or not
| Not Transposed | Transposed |
------------------- ------------ --------- --------- ----------- -----------
Matrix 1Thread Best 1D Best 2D 1Thread T Best
------------------- ------------ --------- --------- ----------- -----------
rdist2.mtx 0.76 2.65 4.95 1.39 Best 2D
cavity10.mtx 0.71 4.02 6.36 1.84 Best 2D
raefsky2.mtx 0.91 9.34 14.01 4.33 Best 2D
bcsstk17.mtx 1.52 5.79 12.80 4.96 Best 2D
lung2.mtx 4.19 1.17 7.64 11.87 1Thread T
thermal1.mtx 3.10 1.69 8.09 11.61 1Thread T
thermomech_TK.mtx 3.23 1.68 6.44 7.95 1Thread T
rma10.mtx 1.56 7.51 17.33 13.41 Best 2D
roadNet-PA.mtx 3.72 0.71 4.17 12.69 1Thread T
cant.mtx 1.51 8.74 18.90 18.38 Best 2D
PR02R.mtx 1.54 7.32 17.85 18.44 1Thread T
af_1_k101.mtx 1.78 6.65 20.40 25.34 1Thread T
ML_Laplace.mtx 1.59 10.17 23.08 24.82 1Thread T
nlpkkt80.mtx 2.01 5.96 16.81 30.97 1Thread T
Cube_Coup_dt0.mtx 1.59 9.84 21.24 26.59 1Thread T
Результаты, показанные в таблице 3 и на рисунке 22, интересны тем, что они показывают, что использование только одного потока на строку вообще неэффективно, но когда массивы переставлены, этот метод внезапно стал одним из самых эффективных. Разница в эффективном использовании одного и того же количества нити впечатляет. При перестановке массивов в большинстве случаев эффективнее использовать только 1 поток за строкой, чем несколько.
Эта резкая разница в эффективности при использовании одного и того же количества потоков связана с тем, что когда матрица хранится в формате ELLPACK, коэффициенты в одном и том же столбце хранятся в памяти рядом друг с другом. Следовательно, чтобы последовательные потоки могли обращаться к последовательным записям, матрица должна быть перенесена в память. Путем перестановки массивов оптимизируется шаблон доступа к памяти, что приводит к лучшему использованию кэша и объединению памяти. В результате в большинстве случаев эффективнее использовать только один поток на строку при транспонировании матрицы.
В C++ выделение памяти для двумерных массивов обычно организовано в порядке возрастания строк, так что каждая строка массива хранится в смежных ячейках памяти. Однако при выполнении умножения матрицы на вектор в CUDA, где каждый блок потока обычно назначается набору строк в матрице, могут возникнуть конфликты, если несколько потоков попытаются получить доступ к ячейкам памяти, расположенным близко друг к другу. Такие конфликты могут возникнуть, если ненулевые элементы в строке разбросаны по всему массиву, а не расположены в непрерывном блоке.
Чтобы решить эту проблему, транспонирование матрицы может быть полезным. Путем транспонирования матрицы ненулевые элементы в каждом столбце объединяются в непрерывный блок. Это снижает вероятность конфликтов потоков, тем самым позволяя потокам получать доступ к данным с большей эффективностью и сводя к минимуму риск зависания из-за доступа к памяти. Уменьшение конкуренции за доступ к памяти может привести к повышению производительности в CUDA, поскольку конфликты потоков могут привести к задержкам, которые могут замедлить общие вычисления.
CUDA против OpenMP
В завершение этой части результатов была проанализирована разница между CUDA и OpenMP, как показано в таблице 4 и на рисунках 24 и 23. Результат в таблице и графиках отсортирован по элементам NZ, поскольку результат показывает, что OpenMP более эффективен для меньших матриц и CUDA. для больших матриц с большим количеством NZ как Cube_Coup_dt0.
Эту разницу между CUDA и OpenMP можно объяснить ограниченным количеством потоков внутри ЦП, поэтому OpenMP ограничен в своей методологии масштабирования. Однако ЦП внутри ЦП более мощный и эффективный. Парадигма в CUDA противоположна той, что в ЦП, где цель состоит в том, чтобы распараллелить огромное количество потоков, менее мощных, чем ЦП. Кроме того, разница между CUDA и OpenMP, по-видимому, составляет около 2 500 000 элементов NZ, что меньше, чем OpenMP, тем лучше, иначе это CUDA.
Table 4: CUDA vs OpenMP
Matrix NZ CUDA OpenMP Best
------------------- ----------- ------- -------- --------
rdist2.mtx 56934 4.95 11.37 OpenMP
cavity10.mtx 76367 6.36 13.93 OpenMP
raefsky2.mtx 294276 14.01 16.79 OpenMP
bcsstk17.mtx 428650 12.80 21.40 OpenMP
lung2.mtx 492564 11.87 20.56 OpenMP
thermal1.mtx 574458 11.61 16.91 OpenMP
thermomech_TK.mtx 711558 7.95 11.57 OpenMP
rma10.mtx 2374001 17.33 27.93 OpenMP
roadNet-PA.mtx 3083796 12.69 2.09 CUDA
cant.mtx 4007383 18.90 8.16 CUDA
PR02R.mtx 8185136 18.44 10.03 CUDA
af_1_k101.mtx 17550675 25.34 9.72 CUDA
ML_Laplace.mtx 27689972 24.82 9.11 CUDA
nlpkkt80.mtx 28704672 30.97 6.93 CUDA
Cube_Coup_dt0.mtx 127206144 26.59 9.40 CUDA
И последнее наблюдение — логарифмическая линейная регрессия, которую можно наблюдать с результатом CUDA между элементами GFlops и NZ на рис. 25. Это соотношение показывает нам способность CUDA эффективно масштабироваться для больших матриц.
Заключение
В заключение следует отметить, что результаты реализации OpenMP показывают, что формат Compressed Sparse Row (CSR) превосходит формат ELLPACK и что горизонтальное развертывание более эффективно, чем вертикальное. Однако увеличение уровня развертывания, по-видимому, не оказывает существенного влияния на эффективность ядра, поскольку может привести к неоптимальному распределению памяти и доступу к ней. GFlops демонстрируют положительную корреляцию с количеством потоков, используемых с OpenMP, также очевидно влияние ненулевых элементов (NZ). Оптимальным алгоритмом развертывания является горизонтальное развертывание второго уровня, за которым следует вертикальное развертывание второго уровня, при этом некоторые матрицы достигают примерно 5 ускорений для 16 потоков с использованием OpenMP и горизонтального развертывания второго уровня.
С другой стороны, реализация CUDA показывает, что двумерный (2D) блок более эффективен, чем одномерный (1D), и что формат ELLPACK более эффективен, чем формат CSR. Однако развертывание неэффективно в CUDA, и наиболее эффективный размер блока равен 16, а худший — 64. Существует корреляция между GFlops и количеством ненулевых (NZ) элементов, и сокращение требует синхронизации между потоками. что может привести к неэффективному алгоритму для слишком большого количества потоков. Наконец, путем перестановки массивов JA и AS формата ELLPACK и использования отдельной методологии распараллеливания с использованием CUDA можно добиться более эффективного алгоритма.
Найдите больше кода здесь.
Рекомендации
[1] Т. Дэвис. Определение разреженной матрицы Уилкинсона (2007 г.)
[2] Сальваторе Филиппоне, Валерия Карделлини, Давиде Барбьери, Алессандро Фанфарилло (2017), Умножение разреженной матрицы на вектор на GPGPU
[3] Натан Белл, Майкл Гарланд (2008), Эффективное разреженное матрично-векторное умножение на CUDA.
[4] Джон Меллор-Крамми, Джон Гарвин (2003), Оптимизация вычислений разреженных матрично-векторных продуктов с использованием раскрутки и замятия.
[5] Сальваторе Филиппоне (2023), Маломасштабное параллельное программирование, Крэнфилдский университет.
Узнать больше
Решение задачи коммивояжёра с помощью параллельных вычислений
Множественная линейная регрессия, градиентный спуск/с Python
© Все права защищены, апрель 2023 г., Симеон ФЕРЕС
