Я посмотрел, что происходит с векторизацией. В общем, GCC с флагом -O3 пытается векторизовать цикл скалярного умножения строки матрицы на вектор с использованием SSE-инструкций, но получается это у него не очень эффективно (godbolt). Основная проблема - после перемножения каждой пары векторов он сразу выполняет горизонтальное суммирование элементов результирующего вектора вместо того, чтобы выполнить это один раз в конце (я так понимаю, что он это делает для сохранения исходного порядка операций). Впрочем, эта проблема решилась добавлением #pragma omp simd reduction(+:res) перед циклом.
Эта доработка позволила ускорить вычисления практически до двух с половиной раз, но общая картина осталась прежней. Из интересного - пришлось увеличивать размер блока итераций в версии Dynamic, чтобы получить максимальное ускорение.
Я почитал комментарии и сейчас уже не уверен в своем ответе. Возможно стоит порассуждать со стороны того, что включение-выключение есть умножение на прямоугольную функцию, что является сверткой в частотной области с sinc. Можно ли считать процесс включения-выключения за кашу?
Нет, не излучаются. С точки физики процесса, на мой взгляд, тоже никак, дело только в математике. То что вы наблюдаете называется спектральная утечка, происходит из-за того, что преобразование Фурье предполагает бесконечный сигнал (ну по крайней мере периодический, если вы его задаете фрагментом), а у вас это совсем не так во входных данных.
Ни в коем случае не претендую данной статьей на анализ многообразия вариантов применения. Но тем не менее считаю, что выбранная задача похожа на типичную нагрузку в задачах моделирования и обработки данных, где OpenMP как раз широко и используется. С этой же точки зрения считаю, что любая изоляция вычислительного аспекта только бы снизила практическую пользу от исследования.
Но в целом я вас понял. Буду только "За", если вы выполните собственное исследования, исходя уже из типичной нагрузки в вашей области. На этом же предлагаю закончить дискуссию.
Смотрите, нет вопроса "8 производительных или 8 энергоэффективных?". Энергоэффективные ядра все-таки слишком слабы (в этой задаче 1 к 4 примерно).
Вопрос ставится следующим образом: только производительные или производительные совместно с энергоэффективными? Характеристики стенда я указал — то есть тесты приведены для 8P против 8P+16E. Будет какой‑то другой процессор с двумя P‑ядрами и 128 E‑ядрами — картина будет конечно другая, но софт делается здесь и сейчас под существующие процессоры.
Про память - из графиков видно, что упор в память происходит только начиная с определенного размера задачи, так что я не знаю, чему здесь можно удивляться.
Тут скорее вопрос к реализации openFOAM — есть ли там балансировка? MPI — же просто интерфейс обмена сообщениями, если декомпозиция задачи была выполнена без учета дисбаланса, то уже реализация MPI не поможет.
Смысл статьи все-таки в другом. Если у вас уже есть реализация BLAS, возможно вам следует её адаптировать для достижения максимальной производительности.
Быстрее получается, если только вы при этом используете динамическое распределение потоков. Мы же по прежнему MKL обсуждаем? Насколько я понимаю, далеко не все процедуры в нём так реализованы.
А то, что по дефолту грузит все ядра - в этом как раз и есть главная проблема, которая и побудила меня на статью. Поведение по умолчанию может сильно проигрывать. По ссылке Intel как раз рекомендует менять значение переменно окружения KMP_HW_SUBSET, чтобы явно указывать, где исполнять вычисления.
Спасибо за статьи! С интересом прочитал обе. Особенно понравился стиль изложения с постепенным усложнением решения и пояснениями, в каких случаях это будет оправдано.
Отличное решение! Действительно, из моего поля зрения совсем ускользнуло наличие альтернативных реализаций для строк. Ваши решения проходят все тесты с большим запасом.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Заголовок спойлера
import Data.Char (isSpace, isDigit, digitToInt)
import Data.List (foldl')
import Control.Monad
import System.IO
import Data.Array.Unboxed
getInt :: IO Int
getInt = hGetIntegral stdin
hGetIntegral :: Handle -> IO Int
hGetIntegral h = do
digits <- hGetDigits h
return $ read digits
hGetDigits :: Handle -> IO [Char]
hGetDigits h = g =<< hIsEOF h
where
g eof
| eof == True = return []
| otherwise = do
char <- hGetChar h
if isDigit char
then fmap (char:) (hGetDigits h)
else return []
foldM' :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM' _ z [] = return z
foldM' f z (x:xs) = do
z' <- f z x
z' `seq` foldM' f z' xs
addToArray :: UArray Int Int -> Int -> UArray Int Int
addToArray arr number = accum (+) arr [(number, 1)]
fillArray :: UArray Int Int -> IO (UArray Int Int)
fillArray a = do
numb <- getInt
foldM' (\arr num -> addToArray arr <$> num) a (replicate numb getInt)
printPair (a, b) = replicateM_ b $ print a
main :: IO ()
main = do
t <- read <$> getLine :: IO Int
let a = array (0,100) [(i, 0) | i <- [0..100]]
res <- foldl' (>=>) return (replicate t fillArray) a
mapM_ printPair $ assocs res
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.
Я посмотрел, что происходит с векторизацией. В общем, GCC с флагом -O3 пытается векторизовать цикл скалярного умножения строки матрицы на вектор с использованием SSE-инструкций, но получается это у него не очень эффективно (godbolt). Основная проблема - после перемножения каждой пары векторов он сразу выполняет горизонтальное суммирование элементов результирующего вектора вместо того, чтобы выполнить это один раз в конце (я так понимаю, что он это делает для сохранения исходного порядка операций). Впрочем, эта проблема решилась добавлением
#pragma omp simd reduction(+:res)перед циклом.Эта доработка позволила ускорить вычисления практически до двух с половиной раз, но общая картина осталась прежней. Из интересного - пришлось увеличивать размер блока итераций в версии Dynamic, чтобы получить максимальное ускорение.
Я почитал комментарии и сейчас уже не уверен в своем ответе. Возможно стоит порассуждать со стороны того, что включение-выключение есть умножение на прямоугольную функцию, что является сверткой в частотной области с sinc. Можно ли считать процесс включения-выключения за кашу?
Нет, не излучаются. С точки физики процесса, на мой взгляд, тоже никак, дело только в математике. То что вы наблюдаете называется спектральная утечка, происходит из-за того, что преобразование Фурье предполагает бесконечный сигнал (ну по крайней мере периодический, если вы его задаете фрагментом), а у вас это совсем не так во входных данных.
Ни в коем случае не претендую данной статьей на анализ многообразия вариантов применения. Но тем не менее считаю, что выбранная задача похожа на типичную нагрузку в задачах моделирования и обработки данных, где OpenMP как раз широко и используется. С этой же точки зрения считаю, что любая изоляция вычислительного аспекта только бы снизила практическую пользу от исследования.
Но в целом я вас понял. Буду только "За", если вы выполните собственное исследования, исходя уже из типичной нагрузки в вашей области. На этом же предлагаю закончить дискуссию.
Я правильно понимаю, что суть вашей претензии сводится к тому, что "о, ужас" все программы разные? Одни compute bound, другие memory?
Допустим, но вывод то какой? Не писать программы, которые активно используют кэш? Не запускать их?
Спасибо! Да, я думаю, что это хорошая идея. Надеюсь, что смогу заняться ею
Смотрите, нет вопроса "8 производительных или 8 энергоэффективных?". Энергоэффективные ядра все-таки слишком слабы (в этой задаче 1 к 4 примерно).
Вопрос ставится следующим образом: только производительные или производительные совместно с энергоэффективными? Характеристики стенда я указал — то есть тесты приведены для 8P против 8P+16E. Будет какой‑то другой процессор с двумя P‑ядрами и 128 E‑ядрами — картина будет конечно другая, но софт делается здесь и сейчас под существующие процессоры.
Про память - из графиков видно, что упор в память происходит только начиная с определенного размера задачи, так что я не знаю, чему здесь можно удивляться.
Тут скорее вопрос к реализации openFOAM — есть ли там балансировка? MPI — же просто интерфейс обмена сообщениями, если декомпозиция задачи была выполнена без учета дисбаланса, то уже реализация MPI не поможет.
Смысл статьи все-таки в другом. Если у вас уже есть реализация BLAS, возможно вам следует её адаптировать для достижения максимальной производительности.
Быстрее получается, если только вы при этом используете динамическое распределение потоков. Мы же по прежнему MKL обсуждаем? Насколько я понимаю, далеко не все процедуры в нём так реализованы.
А то, что по дефолту грузит все ядра - в этом как раз и есть главная проблема, которая и побудила меня на статью. Поведение по умолчанию может сильно проигрывать. По ссылке Intel как раз рекомендует менять значение переменно окружения KMP_HW_SUBSET, чтобы явно указывать, где исполнять вычисления.
Буквально в этом же абзаце
Я не знаю, что это, если не рекомендация :)
Спасибо за статьи! С интересом прочитал обе. Особенно понравился стиль изложения с постепенным усложнением решения и пояснениями, в каких случаях это будет оправдано.
Единственное — во второй версии пришлось заменить <> на `mappend`, в противном случае компиляция заканчивалась с ошибкой. Предполагаю, что в GHC 7.10.2, который используется в системе тестирования, ещё не было этого оператора в ByteString.Builder.
Не подскажите, что за приложение вы использовали для визуализации результатов профилирования?
Спасибо за комментарий! Да, я реализовывал подобный подход с посимвольным чтением входных данных. К сожалению, это не дало какого-либо прироста производительности. Единственное, чего удалось добиться с его помощью — еще большего уменьшения используемой памяти: для сортировки подсчётом и boxed-массивов на 19 тесте получаем 8.61Mb вместо 10.25Mb, а для unboxed 984.00Kb.
Конечно можно предположить, что мы таким образом хоть и выиграли на чтении, но получили просадку в производительности на существенном большем количестве вызовов функции accum, но считаю это маловероятным. Тоже самое я пробовал с IOArray, который такой функции не имеет, и при его использовании приходится в обоих случаях оперировать с отдельными элементами — результат получился аналогичным.
Остаётся ещё оптимизация вывода результата, но я пока ничего не придумал в этом направлении.
По-хорошему, мне необходимо разобраться с профилированием программ на Haskell, чтобы выяснить какая именно часть кода работает большую часть времени. Надеюсь, что смогу этим заняться в обозримом будущем.