Кэш Забывчивые алгоритмы для параллельного программирования?
Я много читал о алгоритмах кэширования и потоковых деревьях и т. Д. Я понимаю основы, которые до сих пор не могу понять, почему они хороши для параллельного программирования? Я думаю, что видел, как Джон Харроп заявил, что они революционны для этого.
3 ответа
В статье http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms
Они указывают на то, что
Идея алгоритмов, не учитывающих кэш, заключается в эффективном использовании кэшей процессора и снижении требований к пропускной способности памяти. Обе вещи одинаково важны для однопоточных алгоритмов, но особенно важны для параллельных алгоритмов, потому что доступная пропускная способность памяти обычно распределяется между аппаратными потоками и часто становится узким местом для масштабируемости.
Доступ к памяти может быть узким местом в параллельных алгоритмах, поэтому использование алгоритмов, которые пытаются использовать кэшированную память, может быть более эффективным.
В той же статье они описывают, как алгоритмы, не обращающие внимания на кеш, используют доступный кеш:
Не обращающие внимания на кэш алгоритмы работают, рекурсивно разделяя набор данных задачи на более мелкие части, а затем выполняя как можно больше вычислений для каждой части. В конечном итоге набор данных подзадачи помещается в кэш, и мы можем выполнять на нем значительное количество вычислений, не обращаясь к памяти
Я просто хочу отметить, что ваш вопрос особенно важен в многоядерной архитектуре, где у нескольких процессоров есть свои собственные частные кэши и общие кэши между несколькими ядрами. Чтобы достичь высокой эффективности и масштабируемости, параллельный алгоритм должен демонстрировать хорошую пространственную и временную локальность в кэшах данных.
До магистерской диссертации Харальда Прокопа алгоритмы и структуры данных разрабатывались с учетом кэш-памяти (кэш-памяти), чтобы уменьшить количество пропусков кеша, например, B-дерево является хорошо известным примером структур данных с поддержкой кеша в параметр B настраивается с использованием размера кэша ЦП. В модели, не обращающей внимания на кэш, из-за рекурсивной природы алгоритмов, подзадачи в конечном итоге помещаются в кеши, а манипулирование такими подзадачами приводит к небольшому количеству пропусков кеша.
Некоторые приятные свойства не обращающих внимания на кэш алгоритмов не зависят от размеров кэша ЦП, хорошо работают с любой иерархией памяти и оказались оптимальными по сложности кеша. С ростом многоядерного параллелизма алгоритмы, не обращающие внимания на кеш, могут играть важную роль в создании производительных параллельных программ. Я также вижу интересную дискуссию о рекурсивных структурах данных и алгоритмах кеширования в следующей статье http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx,
Многоядерные процессоры имеют меньше кэша на ядро. Кеш в выделенном одноядерном процессоре занимает огромное место на кремнии. Вы можете убедиться сами, просто выполнив поиск в Google. вы обнаружите, что размеры кэша огромны, например, http://www.bit-tech.net/hardware/memory/2007/11/15/the_secrets_of_pc_memory_part_1/2
Таким образом, если у вас есть 20 ядер, и каждое из них имеет 1/20 кеша обычного процессора, вам лучше надеяться, что ваши алгоритмы будут работать без гигантского кеша. знак равно