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

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

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

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

26
задан pad 3 October 2012 в 08:45
поделиться