общий вопрос о решении задач с распараллеливанием

Question

У меня есть общий вопрос о программировании параллельных алгоритмов на C. Предположим, что наша задача - реализовать некоторые матричные алгоритмы с MPI и / или OpenMP. Есть некоторые ситуации, например, ложное совместное использование в OpenMP или в MPI, где связь возникает в зависимости от размера матрицы (столбцы циклически распределяются между процессами), что вызывает некоторые проблемы. Будет ли хорошей и распространенной попыткой разрешить эту ситуацию, например, путем транспонирования матрицы, потому что это уменьшит необходимые коммуникации или даже позволит избежать проблемы ложного обмена? После этого вы бы отменили транспонирование. Конечно, предполагая, что это приведет к гораздо лучшему ускорению. Я не думаю, что это было бы очень хитрым и более ленивым способом сделать это. Но мне любопытно прочитать некоторые мнения об этом.

Answer 1

Давайте начнем с первого вопроса: имеет ли смысл транспонировать?Ответ, это зависит, и вы можете оценить, улучшит ли это вещи или нет.

Транспонирование / ретранспозиция с наложением единовременной стоимости пропускной способности памяти 2 * (быстрый просмотр памяти) +2 * (медленный путь через память), где эти операции с памятью являются буквально операциями с памятью в многоядерном случае или сетевыми связями в случае распределенной памяти.Вы будете читать матрицу быстрым способом и медленно помещать ее в память.(Вы можете сделать это, по сути, 4 * (проходя через память быстрым способом), читая матрицу в одном блоке размера кэша за раз, транспонируя в кэш и выполняя запись в порядке).

Является ли это выигрышем или нет, зависит от того, сколько раз вы будете обращаться к массиву.Если бы вы ударили 4 раза по всему нетранспонированному массиву с доступом к памяти в «неправильном» направлении, то вы явно выиграете, выполнив две транспонирования.Если вы будете проходить через неперемещенный массив только один раз в неправильном направлении, то вы почти наверняка не выиграете, выполнив транспозицию.

Что касается более крупного вопроса, @AlexandreC абсолютно прав здесь- пытаться реализовать свои собственные процедуры линейной алгебры - это безумие.Посмотрите, например, Как написать быстрый числовой код , рисунок 3;между наивными и хорошо настроенными (скажем, GEMM) операциями может быть коэффициент 40.Эти вещи сильно ограничены в пропускной способности памяти, а параллельно это означает ограниченную сеть.Безусловно, лучше всего использовать существующие инструменты.

Для многоядерной линейной алгебры, существующие библиотеки включают в себя

• Атлас
• Плазма
• Flame

Для реализаций MPI существует

• BLACS
• Scalapack

или полная решающая среда, такая как

• PETSc
• Трилинос

Answer 2

Я не думаю, что это было бы очень хитрым и более ленивым способом сделать это.

Ленивые решения обычно лучше, чем «хитрые», потому что они, как правило, более просты и понятны. Поэтому их легче внедрять, документировать, понимать и поддерживать. Действительно, лень, возможно, является одним из величайших достоинств, которые может иметь программист. Пока программа дает правильные результаты на приемлемых скоростях, никого не должно волновать, насколько элегантно вы решили проблему (включая вас).

Answer 3

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

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