Несколько уровней параллелизма с использованием OpenMP - возможно? Умный? Практическая?

Question

В настоящее время я работаю над библиотекой разреженных матриц / математиков и итераторов C ++ для инструмента моделирования, которым я управляю. Я бы предпочел использовать существующий пакет, однако после тщательного изучения не было найдено ни одного, подходящего для нашего симулятора (мы рассмотрели flens, it ++, PetSC, eigen и некоторые другие). Хорошая новость - мои решатели, и разреженные матричные структуры теперь очень эффективны и надежны. Плохая новость в том, что сейчас я изучаю распараллеливание с использованием OpenMP, и кривая обучения немного крутая.

Домен, который мы решаем, можно разбить на субдомены, которые объединяются в блочно-диагональном формате. Таким образом, наша схема хранения выглядит как массив меньших квадратных матриц (блоков []), каждая из которых имеет формат, соответствующий субдомену (например, хранилище сжатых строк: CRS, хранилище сжатых диагоналей: CDS, плотное и т. и фоновая матрица (в настоящее время использующая CRS), которая учитывает связь между поддоменами.

«Горячая точка» в большинстве (всех?) Итерационных решателей - это операция умножения Matrix Vector, и это верно для моей библиотеки. Таким образом, я сосредоточил свои усилия на оптимизации моих подпрограмм MxV. Для блочной диагональной структуры псевдокод для M * x = b будет выглядеть следующим образом:

b=background_matrix*x
start_index = 1;
end_index = 0;
for(i=1:number of blocks) {
    end_index=start_index+blocks[i].numRows();
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index);
    start_index = end_index+1;
}

где background_matrix - матрица фона (CRS), block - массив матриц субдомена, а .range возвращает часть вектора от начального индекса до конечного индекса.

Очевидно, что цикл может быть (и был) распараллелен, поскольку операции не зависят от других итераций цикла (диапазоны не перекрываются). Поскольку в типичной системе у нас 10-15 блоков, потоки 4+ на самом деле имеют существенное значение.

Другое место, где распараллеливание считается хорошим вариантом, - это операция MxV для каждой схемы хранения в субдомене (вызовы в строках 1 и 6 в приведенном выше коде). Существует множество способов распараллеливания операций CRS, CDS и MxV с плотной матрицей. Как правило, хорошее увеличение наблюдается с 2 потоками, с очень уменьшающимся возвратом по мере добавления новых потоков.

Я предполагаю схему, где 4 цикла будут использоваться в цикле блоков для приведенного выше кода, и каждый из этих потоков будет использовать 2 потока для решений субдоменов. Однако я не уверен, как с помощью OpenMP можно управлять пулом потоков - возможно ли ограничить количество потоков в цикле openmp for? Является ли этот многоуровневый параллелизм чем-то, что на практике имеет смысл? Буду признателен за любые другие мысли о том, что я здесь предложил (и спасибо, что дочитали до конца!)

Answer 1

Обратите внимание, что все, что я описываю, зависит от реализации.

Можно ли ограничить количество потоков в цикле openmp for?

Да.Есть разные способы сделать это.Установите omp_set_nested(1); и используйте что-то вроде #pragma omp parallel for num_threads(4) или аналогичное во внешнем цикле и директиву #pragma omp parallel for num_threads(2) во внутреннем цикле.Это должно дать вам 8 потоков (в зависимости от реализации вам, возможно, также придется установить OMP_THREAD_LIMIT, если у вас менее 8 ядер)

В качестве альтернативы, вы можете вручную развернуть свои циклы, например, используя что-то вроде

#pragma omp parallel sections {
     #pragma omp section 
     do your stuff for the first part, nest parallel region again
     #pragma omp section 
     and so on for the other parts
}

Вы можете сделать то же самое иногда более эффективно в OpenMP 3.0 с помощью #pragma omp task.

Или вы запускаете 8 потоков и получаете номер текущего потока в параллельном разделе и планируете вручную на основеномер потока.

Наконец, если у вас есть идеально вложенный цикл (цикл идеально вложен, если фактическое назначение происходит только в самом внутреннем цикле), вы можете переписать все в один цикл.В основном, упакуйте два итератора i и j в один большой итератор (i, j).Обратите внимание, что это может уменьшить локальность и, следовательно, снизить производительность

Является ли этот многоуровневый параллелизм чем-то, что на практике имеет смысл?

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

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

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

Любые другие мысли

Хотели ли вы сделать MxV с SIMD?В зависимости от архитектуры, это может дать ускорение 2-4.Я быстро прогуглил для вас эту презентацию .

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

Answer 2

Почему бы не спросить экспертов на OpenMP.org

Зарегистрируйтесь и войдите на: http://openmp.org/forum/viewforum.php?f=3