Асинхронные программы, показывающие местность ссылки?

Question

Я читал эту замечательную статью, которая дает введение в асинхронное программирование здесь http://krondo.com/blog/?p=1209, и я наткнулся на следующую строку, которую мне трудно понять.

Поскольку фактический параллелизм (в asnyc) отсутствует, на наших диаграммах видно, что асинхронная программа займет столько же времени, сколько и синхронно, возможно, дольше, поскольку асинхронная программа может иметь более низкую локальность ссылки.

Может ли кто-нибудь объяснить, как здесь упоминается местность ссылок?

Answer 1

Местность ссылки, как упоминается в статье в Википедии, является наблюдением, что при доступе к некоторым данным (на диске, в памяти, независимо от того) также доступны другие данные рядом с этим местоположением. Это наблюдение имеет смысл, поскольку разработчики склонны группировать подобные данные вместе. Поскольку данные связаны, они часто обрабатываются вместе. В частности, это называется пространственной локальностью.

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

Архитектура компьютера учитывает местность справки. В операционных системах есть понятие «страницы», которые представляют собой (примерно) 4 Кбайта фрагменты данных, которые можно выгружать и выгружать отдельно (перемещается между физической памятью и диском). Когда вы касаетесь некоторой памяти, которая не является резидентной (не физически в ОЗУ), ОС выведет всю страницу данных с диска и в память. Причиной этого является локальность: вы, вероятно, будете касаться других данных вокруг того, что вы только что коснулись.

Кроме того, у процессоров есть концепция кешей. Например, у ЦП может быть кеш L1 (уровень 1), который на самом деле является просто большим блоком данных на процессоре, который процессор может получить быстрее, чем оперативная память. Если значение находится в кеше L1, CPU будет использовать это вместо выхода в ОЗУ. Следуя принципу локальности ссылки, когда ЦП обращается к некоторому значению в основной памяти, он приведет это значение и все значения рядом с ним в кеш L1. Этот набор значений известен как строка кэша. Кэш-линии различаются по размеру, но дело в том, что когда вы получаете доступ к первому значению массива, CPU может потребоваться получить его из ОЗУ, но последующие обращения (близкие по близости) будут быстрее, поскольку ЦП привел весь пакет значения в кеш L1 при первом доступе.

Итак, чтобы ответить на ваш вопрос: если вы представляете себе синхронный процесс, вычисляющий сумму очень большого массива, он будет прикасаться к ячейкам памяти по порядку один за другим. В этом случае ваша местность хороша. Однако в асинхронном случае у вас могут быть потоки n, каждый из которых принимает срез массива (размером 1/n) и вычисляет сумму. Каждый поток касается потенциально очень другого места в памяти (поскольку массив большой), и поскольку каждый поток может быть включен и не исполнен, фактический шаблон доступа к данным с точки зрения ОС или ЦП является плохим. Кэш L1 на процессоре является конечным, поэтому, если в Thread 1 содержится строка кэша (из-за доступа), это может вывести строку кэша Thread 2. Затем, когда Thread 2 переходит к его значению массива, он должен перейдите в ОЗУ, которое снова приведет к своей строке кэша и потенциально выйдет из строя строки кэша Thread 1 и так далее. В зависимости от системных ресурсов и использования в целом этот шаблон может происходить и на уровне ОС/страницы.

Answer 2

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

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