Кэш Забывчивые алгоритмы для параллельного программирования?

Question

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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