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

Question

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

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

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

Answer 1

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

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

С этой целью;

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

Answer 6

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

Обнаружение кэша http://supertech.csail.mit.edu/cacheObliviousBTree.html Проект деревьев поиска, не обращающий внимания в кэш

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

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