Лучшие практики для локальности кэша в многоядерном параллелизме в F #

Question

Я изучаю многоядерный параллелизм в F #.Я должен признать, что неизменность действительно помогает написать правильную параллельную реализацию.Однако при увеличении числа ядер трудно добиться хорошего ускорения и масштабируемости.Например, мой опыт работы с алгоритмом быстрой сортировки состоит в том, что многие попытки реализовать параллельную быструю сортировку чисто функциональным способом и с использованием List или Array в качестве представления не удаются.Профилирование этих реализаций показывает, что количество пропусков кеша значительно увеличивается по сравнению с последовательными версиями.Однако, если реализовать параллельную быструю сортировку с использованием мутаций внутри массивов, можно добиться хорошего ускорения.Поэтому я думаю, что мутация может быть хорошей практикой для оптимизации многоядерного параллелизма.

Я считаю, что локальность кэша является большим препятствием для многоядерного параллелизма в функциональном языке.Функциональное программирование включает в себя создание множества недолговечных объектов;уничтожение этих объектов может разрушить свойство когерентности кэшей ЦП.Я видел много предложений, как улучшить локальность кэша в императивных языках, например, здесь и здесь .Но мне не ясно, как они будут реализованы в функциональном программировании, особенно с рекурсивными структурами данных, такими как деревья и т. Д., Которые появляются довольно часто.

Существуют ли какие-либо методы для улучшения локальности кэша внечистый функциональный язык (в частности, F #) ?Любые советы или примеры кода приветствуются.

Answer 1

Насколько я могу судить, ключ к локальности кэша (многопоточный или другой) -

• Храните рабочие блоки в непрерывном блоке оперативной памяти, который помещается в кэш

С этой целью;

• Избегайте объектов, где это возможно
  • Объекты размещаются в куче и могут распыляться повсюду, в зависимости от фрагментации кучи и т. Д.
  • Вы практически не контролируете размещение объектов в памяти до такой степени, что ГХ может перемещать их в любое время.
• Использовать массивы. Массивы интерпретируются большинством компиляторов как непрерывный блок памяти.
  • Другие типы данных коллекций могут распределять объекты повсеместно - связанные списки, например, состоят из указателей.
• Использовать массивы примитивных типов. Типы объектов распределяются в куче, поэтому массив объектов - это просто массив указателей на объекты, которые могут быть распределены по всей куче.
• Используйте массивы структур, если вы не можете использовать примитивы. Структуры имеют свои поля, расположенные последовательно в памяти, и обрабатываются компиляторами .NET как примитивы.
• Определите размер кэша на машине, на которой вы будете его выполнять
  • ЦП имеют кэш L2 разного размера
  • Возможно, было бы целесообразно спроектировать ваш код для масштабирования с различными размерами кэша
  • Или, проще, напишите код, который будет соответствовать наименьшему общему размеру кэша, на котором будет выполняться код
• Выясните, что нужно сидеть рядом с каждым датумом
  • На практике вы не собираетесь помещать весь свой рабочий набор в кэш L2
  • Изучите (или перепроектируйте) ваши алгоритмы, чтобы используемые вами структуры данных содержали данные, которые требовались «рядом» с данными, которые ранее были необходимы.

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

Хорошая академическая статья по этому вопросу: Кэш-эффективная сортировка строк с использованием копирования.

Answer 2

Отличным подходом является разделение работы на более мелкие разделы и перебор каждого раздела в каждом ядре.

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

Вот отличный пример этого: Cache Locality For Performance

В книге Томаса Петричака было несколько замечательных разделов Функциональное программирование в реальной работе , ознакомьтесь с главой 14 Написание параллельных функциональных программ, вы можете найти параллельную обработку двоичного дерева, представляющего особый интерес.

Answer 3

Я не эксперт по параллелизму, но в любом случае вот мой совет.

1. Я бы ожидал, что локально изменяемый подход, в котором каждому ядру выделяется область памяти, которая как для чтения, так и для записи, всегда превзойдет чистый подход.
2. Попробуйте сформулировать свой алгоритм так, чтобы он работал последовательно в непрерывной области памяти. Это означает, что если вы работаете с графиками, возможно, стоит сгладить узлы в массивы и заменить ссылки на индексы перед обработкой. Независимо от проблем с локальностью кэша, это всегда хороший метод оптимизации в .NET, поскольку он помогает убрать сборщик мусора.

Answer 4

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

Вот что вернул быстрый поиск: Parallel Quicksort в Haskell .Давайте продолжим обсуждение производительности, сфокусированной на производительности.Выберите процессор, затем сравните его с конкретным алгоритмом.

Чтобы ответить на ваш вопрос без каких-либо подробностей, я бы сказал, что Clojure подход к реализации STM можетУрок в общем случае о том, как разделить пути выполнения на многоядерных процессорах и улучшить локальность кэша.Но он эффективен только тогда, когда количество операций чтения превышает количество записей.

Answer 5

Создание масштабируемого локального кэша приложений имеет первостепенное значение для скорости вашего приложения. Принципы хорошо объясняются Скоттом Мейерсом . Неизменность не очень хорошо работает с локальностью кэша, поскольку вы создаете новые объекты в памяти, что заставляет ЦП снова загружать данные из нового объекта. Как отмечается в докладе, даже на современных процессорах кэш-память L1 имеет размер всего 32 КБ, который распределяется для кода и данных между всеми ядрами. Если вы используете многопоточность, вы должны стараться использовать как можно меньше памяти (до свидания, всегда), чтобы оставаться в самом быстром кеше. Кэш-память второго уровня составляет около 4–8 МБ, что намного больше, но все же крошечно по сравнению с данными, которые вы пытаетесь отсортировать.

Если вам удастся написать приложение, которое потребляет как можно меньше памяти (локальность кэша данных), вы можете получить ускорение 20 или более. Но если вы справитесь с этим для 1 ядра, вполне возможно, что масштабирование на большее количество ядер снизит производительность, поскольку все ядра конкурируют за один и тот же кэш L2.

Чтобы получить максимальную отдачу от этого, ребята из C ++ используют PGA (Profile Guided Optimizations), которая позволяет им профилировать свое приложение, которое используется в качестве входных данных для компилятора, чтобы испускать более оптимизированный код для конкретного случая использования.

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

Answer 6

Вы можете получить некоторые идеи из них:

Cache-Oblivious http://supertech.csail.mit.edu/cacheObliviousBTree.html Проект деревьев поиска с кэшированием

DSapce @ MIT Когерентные стратегии кэша в многоядерном процессоре http://dspace.mit.edu/handle/1721.1/61276

описывает революционную идею алгоритмов, не обращающих внимания на кэш, благодаря элегантной и эффективной реализации умножения матриц в F #.