Comments 15
А почему вы не ставите ( R ) после слова Xeon?
Старался учесть все правила Интел, после слова Xeon символ ( R ) не нужен.
Вот читаю статью, а перед глазами вижу свою работу полуторалетней давности. Тот же Штрассен, тот же Xeon Phi… Сравнение с тем же DGEMM… И даже результат тот же: я тоже так и не смог догнать DGEMM. У меня, правда, все было совсем плохо: моя реализация была быстрее DGEMM на обычном процессоре при, но вот на Xeon Phi оказывалась во много раз медленнее. Уж не знаю, как так вышло. А вообще, если кому интересно, вот.
Интел регулярно поднимает тему алгоритма Штрассена, похоже видят какие-то перспективы на этот счет. Помимо вашей работы, например, проводился Intel Threading Challenge 2009, где также была эта задача. Судя по нашему обзору открытых источников наши результаты оказались лучше результатов наших предшественников.
Так в чем в итоге проблема отставания, в рекурсии и синхронизации?
Я бы выделил несколько основных причин отставания. Во-первых, синхронизация, которая вызывается на каждом уровне рекурсии по 3 раза. Затем, древовидная структура распараллеливания (на верхнем уровне создается 7 потоков, на каждом они делятся еще на 7 и т.д.), здесь возникает как минимум 3 проблемы: неравномерная загрузка потоков, не кратное степени 2 число потоков (а значит не оптимальное отображение на архитектуру Xeon Phi), а также вопрос ограничения максимального количества потоков. Мы пробовали создавать различное число потоков на каждом уровне рекурсии, оставить распараллеливание только на 2-3 верхних уровнях, по-разному группировать вычислительные операции по потокам, разный binding, но все равно, результаты распараллеливания нельзя назвать очень хорошими. Отдельно стоит выделить проблему с вложенным параллелизмом, который достаточно сложен в использовании и сам по себе, а эффективно использовать свой параллелизм поверх параллелизма MKL вообще очень сложно, т.к. MKL предоставляет ограниченный API для управления параллелизмом. Также стоит отметить, что в однопоточном варианте наша реализация оказалась существенно быстрее MKL DGEMM (около 1.5-2 раз), то есть мы проиграли именно в распараллеливании.
Ну я вот и спрашиваю про параллельный вариант. На одном то юните алгоритм сам по себе быстрее, чем больше юнитов, тем больше разница в абсолютных значениях. Я так понял, что проблема, которая, видимо, общая для всех алгоритмов, которые распараллеливают рекурсию: неравномерность вычислений, которая затормаживает быстрые потоки на моменте синхронизации и несоответствие количества вычислений количеству юнитов. А не пробовали другие методы использовать, что нибудь а ля thread pool для этих задач?
Мы пробовали преобразовывать рекурсию в цикл (алгоритм нашли в одной из статей). Но это потребовало определенного препроцессинга и постпроцессинга, которые занимали слишком много времени (эффективность непосредственно умножения подматриц ожидаемо увеличилась). Насчет реализации собственной очереди задач (если вы это имели в виду) мы думали, но решили, что это не даст никакого положительного эффекта.
UFO just landed and posted this here
На максимальном количестве потоков не дал. При однопоточном выполнении ускорение было получено, примерно такое, как Вы посчитали, правда формула расчета количества операций для алгоритма Штрассена будет сложнее, т.к. мы использовали комбинированный алгоритм (начиная с определенного значения размера подматриц вызывается стандартный алгоритм). По поводу причин отсутствия ускорения смотрите в комментарии выше.
Вопрос автору, при использонии алгоритма Штрассена, чем/как перемножались малые матрицы?
MKL тем и хорош, что исбользует правильные алгоритм кеш-блокинга/рекурсивное деление матриц, что бы запихнуть правильные плитки (tiles) матриц в разные уровни кешей. Без этого мы говорим не о compute-bound имплементации, а намного замедленном коде, т.к. в нем будет слишком много кеш промохов.
А еще для Xeon Phi 1.2 TFLOP/s — это только максимально возможная производительность на double precision, для FMA инструкций при использовании 512-битных векторных инструкций на всех ядрах. Только одна нить из 4-х на ядро смоежет использовать VPU за цикл. Но это я отвлекся. Т.е нужно еще думать как векторизовать весь код, если он не bandwidth-bound.
Если есть желание побеседовать по этой теме — прошу в личку.
MKL тем и хорош, что исбользует правильные алгоритм кеш-блокинга/рекурсивное деление матриц, что бы запихнуть правильные плитки (tiles) матриц в разные уровни кешей. Без этого мы говорим не о compute-bound имплементации, а намного замедленном коде, т.к. в нем будет слишком много кеш промохов.
А еще для Xeon Phi 1.2 TFLOP/s — это только максимально возможная производительность на double precision, для FMA инструкций при использовании 512-битных векторных инструкций на всех ядрах. Только одна нить из 4-х на ядро смоежет использовать VPU за цикл. Но это я отвлекся. Т.е нужно еще думать как векторизовать весь код, если он не bandwidth-bound.
Если есть желание побеседовать по этой теме — прошу в личку.
По первому вопросу:
(в качестве стандартного алгоритма мы использовали Intel MKL DGEMM)Т.е. в вопросе векторизации умножения подматриц мы как раз на MKL и полагались. Насчет производительности Вы правильно заметили, что это теоретический предел, в статье также про это написано.
OShapovalov, «векторизация» вот это я подразумевал выше под «попробовать другие способы». Это правильней с терминологической и практической точки зрения. У меня еще возник вопрос по ходу чтения этого комментария с упоминанием про fma-инструкции и кеша. Зачем там x86 архитектура, если устройство предназначено для плавающей точки. Ведь на OpenCL и CUDA можно самому регулировать что в какую память пойдет и на какие вычислительные единицы. Получается, что теряется гибкость и контроль. Есть ли у этого какие-то плюсы, кроме того, что там Линукс?
Основное преимущество x86 заключается в более простом программировании (для нативного режима часто достаточно перекомпиляции программы без изменений в исходном коде). А гибкость… я не думаю, что она часто требуется. Вообще у нас не стояла задача выбирать вычислительное устройство. Кстати OpenCL на Xeon Phi поддерживается.
У Интела сейчас задача заставить программистов переписать старый legacy код, который разрабатывался в 80х-90х без учета векторных операций и мульти- и много-ядерности под новые архитектуры. И мы говорим о коде в сотни тысяч строк или даже нескольких миллионов строк. Переписывать все это богатство с нуля отвыжится только сумасшедший. Поэтому стратегически было принято решение поддерживать х86 инструкции и устоявшуюся инфроструктуру, векторизацию спихнуть на компилятор, а параллелизм нитей реализовать с помощью OpenMP стандарта — прагмы проще вставлять, чем переписывать сам код. Это далеко не идеальное решение, но уж какое Интел придумал. MIC первого покаления — это первый шаг в направлении такое системы, где без векторизации и нитей нифига летать не будет. Со вторым поколением (KNL) схожая ситуация, хотя и чуть ускорился одно-поточный код. И плюс в KNL с memkind библиотекой специальными аллокаторами можно будет управлять где выделяется памить: в MCDRAM или DDR4, если чип во flat mode памяти находится.
Sign up to leave a comment.
Распараллеливание алгоритма Штрассена на Intel® Xeon Phi(TM)