Рекомендации по локализации кеша в Multicore Parallelism в F #

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

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

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

Ответ 1

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

Храните рабочие единицы в непрерывном блоке ОЗУ, который будет вписываться в кеш

С этой целью

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

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

Хорошая академическая статья по этому вопросу Эффективная сортировка строк с помощью копирования

Ответ 2

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

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

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

Ответ 3

Я не эксперт parallelism, но вот мой совет.

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

Ответ 4

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

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

Вот отличный пример: Кэш-локация для производительности

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

Ответ 5

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

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

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

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

Ответ 6

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

Cache-Oblivious http://supertech.csail.mit.edu/cacheObliviousBTree.html Проект Cache-Oblivious Search Trees

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

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