Cache Обильные алгоритмы для параллельного программирования?

Ответ 1

В статье http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms

Они указывают, что

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

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

В той же статье они продолжают описывать, как кэширующие забытые алгоритмы используют доступный кэш:

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

Ответ 2

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

Прежде чем Харальд Прокоп, магистерская диссертация, алгоритмы и структуры данных были разработаны в режиме кэширования (кэширования), чтобы уменьшить отношение кеш-промахов, например, B-tree - это хорошо известный пример структур данных с поддержкой кэша, в которых параметр B настраивается с использованием размера кэша ЦП. В неприглядной кэш-модели, из-за рекурсивного характера алгоритмов, подзадачи в конечном итоге вписываются в кеши и манипулируют такими подзадачами, которые несут небольшое количество промахов в кэше.

Некоторые приятные свойства алгоритмов, не учитывающих кеш, не зависят от размеров кэша процессора, хорошо работают с любой иерархией памяти и оказались оптимальными в сложности кэша. При увеличении многоядерных parallelism алгоритмы, игнорирующие кеш, могут сыграть важную роль в получении исполняемых параллельных программ. Я также вижу интересное обсуждение рекурсивных структур данных и алгоритмов, не учитывающих кэша, в следующей статье http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx.

Ответ 3

У многоядерных процессоров меньше кэша на ядро. Кэш в выделенном одноядерном процессоре занимает огромное количество места на кремнии. Вы можете сами убедиться, что это просто поиск изображений в Google; вы обнаружите, что размеры кеша огромны, например. http://www.bit-tech.net/hardware/memory/2007/11/15/the_secrets_of_pc_memory_part_1/2

Таким образом, если у вас есть 20 ядер, и каждый из них имеет 1/20 кэш обычного процессора, вам лучше надеяться, что ваши алгоритмы будут хорошо работать без гигантского кеша. =)