Многопоточный GEMM медленнее однопоточного?

Я написал немного кода Naiive GEMM, и мне интересно, почему он намного медленнее, чем эквивалентный однопоточный код GEMM.

С матрицей 200x200, однопотоковая: 7 мс, многопоточная: 108 мс, ЦП: 3930k, 12 потоков в пуле потоков.

    template <unsigned M, unsigned N, unsigned P, typename T>
    static Matrix<M, P, T> multiply( const Matrix<M, N, T> &lhs, const Matrix<N, P, T> &rhs, ThreadPool & pool )
    {
        Matrix<M, P, T> result = {0};

        Task<void> task(pool);
        for (auto i=0u; i<M; ++i)
            for (auto j=0u; j<P; j++)
                task.async([&result, &lhs, &rhs, i, j](){
                    T sum = 0;
                    for (auto k=0u; k < N; ++k)
                        sum += lhs[i * N + k] * rhs[k * P + j];
                    result[i * M + j] = sum;
            });

        task.wait();

        return std::move(result);
    }
Источник

3 ответа

Решение

У меня нет опыта работы с GEMM, но, похоже, ваша проблема связана с проблемами, возникающими во всех видах многопоточных сценариев.

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

  1. создание / очистка начальных / конечных потоков
  2. контекст переключается когда (количество потоков) > (количество ядер ЦП)
  3. блокировка ресурсов, ожидающих получения блокировки
  4. проблемы синхронизации кеша

Пункты 2. и 3., вероятно, не играют роли в вашем примере: вы используете 12 потоков на 12 (гиперпоточных) ядрах, и ваш алгоритм не предусматривает блокировок.

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

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

"Зачем?" вы можете подумать, потому что вы пишете в разные места в памяти. Это связано с тем, что типичный кэш процессора организован в виде строк кэша, длина которых в современных моделях процессоров Intel и AMD составляет 64 байта. Это наименьший размер, который можно использовать для передачи из и в кэш, когда что-то изменяется. Теперь, когда все ядра ЦП читают и записывают в смежные слова памяти, это приводит к синхронизации 64 байтов между всеми ядрами всякий раз, когда вы пишете только 4 байта (или 8, в зависимости от размера используемого вами типа данных).

Если память не является проблемой, вы можете просто "дополнить" каждый элемент выходного массива "фиктивными" данными, чтобы в каждой строке кэша был только один выходной элемент. Если вы используете 4-байтовые типы данных, это будет означать пропуск 15 элементов массива для каждого 1 реального элемента данных. Проблемы с кешем также улучшатся, когда вы сделаете ваши потоки менее детализированными, потому что каждый поток получит доступ к своей собственной непрерывной области в памяти практически без вмешательства в память других потоков.

Изменить: более подробное описание Херб Саттер (один из гуру C++) можно найти здесь: http://www.drdobbs.com/parallel/maximize-locality-minimize-contention/208200273

Edit2: Кстати, предлагается избегать std::move в операторе return, поскольку это может помешать правилам возврата-оптимизации и копирования-выбора, которые стандарт теперь требует, чтобы это происходило автоматически. См. Имеет ли смысл возврат с `std::move` в случае множественных операторов возврата?

Источник

Многопоточность означает всегда синхронизацию, переключение контекста, вызов функции. Все это складывается и стоит процессорных циклов, которые вы можете потратить на основную задачу.

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

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

Источник

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

Вы должны помнить, что создание потоков связано с большими затратами. Есть также некоторые (но значительно меньше) накладные расходы с синхронизацией.

Источник
Другие вопросы по тегам