Это сложная проблема, тесно связанная с архитектурными особенностями современных процессоров, и ваша интуиция в том, что случайное чтение медленнее, чем случайные записи, поскольку ЦП должен ждать, пока прочитанные данные не проверены (большая частьвремя).Я объясню несколько причин.
Современные процессоры очень эффективно скрывают задержку чтения
, тогда как запись в память обходится дороже, чемчтение памяти
особенно в многоядерной среде
Причина № 1 Современные процессоры эффективно скрывают задержку чтения.
Современный суперскалярный может выполнять несколько инструкций одновременно и изменять порядок выполнения инструкций ( вне порядка исполнения ).Хотя первая причина этих функций заключается в увеличении производительности команд, одним из наиболее интересных последствий является способность процессоров скрывать задержки записи в память (или сложных операторов, ветвей и т. Д.).
Чтобы объяснить это,давайте рассмотрим простой код, который копирует массив в другой.
for i in a:
c[i] = b[i]
Один скомпилированный код, выполняемый процессором, будет как-то так
#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc
(это очень упрощенно ифактический код более сложен и должен иметь дело с управлением циклами, вычислением адресов и т. д., но в настоящее время этой упрощенной модели достаточно).
Как сказано в вопросе, для операций чтения требуется, чтобы процессор ожидалфактические данные.Действительно, 1b нужны данные, извлеченные 1a, и они не могут выполняться, пока 1a не завершена.Такое ограничение называется зависимость , и мы можем сказать, что 1b зависит от 1a.Зависимости является основным понятием в современных процессорах.Зависимости выражают алгоритм (например, я пишу от b до c) и должны обязательно соблюдаться.Но, если между инструкциями нет зависимости, процессоры попытаются выполнить другие ожидающие инструкции, чтобы всегда поддерживать активный конвейер.Это может привести к нарушению порядка выполнения, если соблюдаются зависимости (аналогично правилу «как если бы»).
Для рассматриваемого кода существует нет зависимость между высоким уровнеминструкция 2. и 1. (или между инструкциями asm 2a и 2b и предыдущими инструкциями).На самом деле, конечный результат даже будет идентичен: 2. выполняется перед 1., и процессор попытается выполнить 2a и 2b, до завершения 1a и 1b.Между 2a и 2b все еще существует зависимость, но обе могут быть выданы.И аналогично для 3а.и 3б. и тд.Это мощное средство для скрытия задержки памяти .Если по какой-либо причине 2., 3. и 4. могут завершиться до того, как 1. загрузит свои данные, вы можете даже не заметить никакого замедления.
Этот параллелизм на уровне команд управляется набором «очередей»в процессоре.
очередь ожидающих выполнения инструкций в станциях резервирования RS (введите 128 µинструкций в последних пенсиях).Как только ресурсы, требуемые инструкцией, становятся доступными (например, значение регистра c1 для инструкции 1b), инструкция может выполнить.
очередь ожидающих обращений к памяти в буфере порядка памяти MOBдо кэша L1.Это необходимо для работы с псевдонимами памяти и для обеспечения последовательности при записи в память или при загрузке по одному и тому же адресу (тип. 64 загрузки, 32 хранилища)
очередь для обеспечения последовательности при обратной записиприводит к регистрам (буфер переупорядочения или ROB из 168 записей) по аналогичным причинам.
и некоторые другие очереди при получении инструкций для генерации мопов, записи и пропуска буферов в кэш и т. д.
В какой-то момент выполнения предыдущей программы будет много ожидающих сохраняющихся инструкций в RS, несколько загрузок в MOB и инструкций, ожидающих выхода в ROB.
Как только данные становятся доступными (например, чтение прекращается), могут выполняться различные инструкции, что освобождает позиции в очередях.Но если завершение не происходит и одна из этих очередей заполнена, функциональный блок, связанный с этой очередью, останавливается (это также может произойти при выдаче команды, если в процессоре отсутствуют имена регистров).Задержки - это то, что создает потерю производительности, и чтобы избежать этого, заполнение очереди должно быть ограничено.
Это объясняет разницу между линейным и случайным доступом к памяти.
В линейном доступе 1 / количество пропусков будетменьше из-за лучшей пространственной локализации и из-за того, что кэши могут предварительно выбирать доступ с регулярным шаблоном, чтобы еще больше уменьшить его и 2 / всякий раз, когда чтение завершается, это будет касаться всей строки кэша и может освободить несколько ожидающих инструкций загрузки, ограничивающих заполнение очередей команд.Это приводит к тому, что процессор постоянно занят, а задержка памяти скрыта.
Для произвольного доступа число пропусков будет выше, и при поступлении данных будет обслуживаться только одна загрузка.Следовательно, очереди инструкций будут быстро насыщаться, задержки процессора и задержки памяти больше не будут скрыты при выполнении других инструкций.
Архитектура процессора должна быть сбалансирована с точки зрения пропускной способности, чтобы избежать насыщения очереди и остановок.Действительно, на каком-то этапе выполнения в процессоре обычно присутствуют десятки инструкций, и глобальная пропускная способность (т. Е. Способность обслуживать запросы инструкций памятью (или функциональными единицами)) является основным фактором, определяющим производительность.Тот факт, что некоторые из этих ожидающих инструкций ожидают значения памяти, имеет незначительный эффект ...
... за исключением случаев, когда у вас длинные цепочки зависимостей.
Существует зависимость, когдаИнструкция должна ждать завершения предыдущего.Использование результата чтения является зависимостью.И зависимости могут быть проблемой, когда участвуют в цепочке зависимостей.
Например, рассмотрим код for i in range(1,100000): s += a[i].Все чтения из памяти являются независимыми, но для накопления в s существует цепочка зависимостей.Никакое дополнение не может произойти, пока предыдущий не закончилсяЭти зависимости быстро заполняют станции резервирования и создают задержки в конвейере.
Но операции чтения редко включаются в цепочки зависимостей.По-прежнему возможно представить патологический код, в котором все чтения зависят от предыдущего (например, for i in range(1,100000): s = a[s]), но в реальном коде они редки.И проблема возникает из цепочки зависимостей, а не из-за того, что это чтение;Ситуация была бы аналогичной (и даже, вероятно, еще хуже) с зависимым от вычислений кодом, подобным for i in range(1,100000): x = 1.0/x+1.0.
Следовательно, за исключением некоторых ситуаций, время вычислений больше связано с пропускной способностью, чем с зависимостью чтения, благодаря тому факту, чтоЭто суперскалярное выполнение или выполнение заказа скрывает задержку.А что касается пропускной способности, записи хуже, чем чтения.
Причина № 2: Операции записи в память (особенно случайные) дороже чтения в памяти
Это связано кэши ведут себя.Кэш-память - это быстрая память, которая хранит часть памяти (называемую line ) процессором.Строки кэша в настоящее время занимают 64 байта и позволяют использовать пространственную локальность ссылок на память: после сохранения строки все данные в строке становятся немедленно доступными.Важным аспектом здесь является то, что все передачи между кешем и памятью являются строками .
Когда процессор выполняет чтение данных, кеш проверяет, принадлежит ли строка, к которой принадлежат данныенаходится в кеше.Если нет, то строка извлекается из памяти, сохраняется в кеше, и нужные данные отправляются обратно в процессор.
Когда процессор записывает данные в память, кеш также проверяет наличие строки.Если строка отсутствует, кэш не может отправить свои данные в память (поскольку все передачи основаны на строке) и выполняет следующие шаги:
- кэш извлекает строку из памятии записывает его в строку кэша.
- данные записываются в кэш, а полная строка помечается как измененная (грязная)
- , когда строка подавляется из кэша, она проверяет наличиеизмененный флаг, и если строка была изменена, она записывает ее обратно в память (кэш обратной записи)
Следовательно, каждой записи в память должна предшествовать запись в память вполучить строку в кеше.Это добавляет дополнительную операцию, но не очень дорого для линейных записей.При первом записанном слове произойдет пропуск кеша и чтение памяти, но последовательные записи будут касаться только кеша и будут попаданиями.
Но ситуация для случайных записей очень разная.Если важно число пропусков, каждая пропущенная кэш-память подразумевает чтение, за которым следует только небольшое количество записей, прежде чем строка будет извлечена из кеша, что значительно увеличивает стоимость записи.Если строка извлекается после одной записи, мы можем даже считать, что запись вдвое превышает временную стоимость чтения.
Важно отметить, что увеличение количества обращений к памяти (при чтении или записи)имеет тенденцию насыщать путь доступа к памяти и глобально замедлять все передачи между процессором и памятью.
В любом случае запись всегда дороже чтения.И многоядерные расширения дополняют этот аспект.
Причина № 3: Случайные записи создают ошибки кэша в многоядерных системах
Не уверен, что это действительно относится к ситуации вопроса.Хотя подпрограммы BLAS являются многопоточными, я не думаю, что базовая копия массива есть.Но это тесно связано и является еще одной причиной, почему записи стоят дороже.
Проблема многоядерности заключается в обеспечении правильной когерентности кэша таким образом, чтобы данные, совместно используемые несколькими процессорами, корректно обновлялись в кэше каждого ядра.Это делается с помощью протокола, такого как MESI , который обновляет строку кеша перед ее записью и делает недействительными другие копии кеша (прочитано для владельца).
Хотя на самом деле ни одна из данных не является действительнойразделить между ядрами в вопросе (или его параллельной версии), обратите внимание, что протокол применяется к строкам кэша .Всякий раз, когда необходимо изменить строку кэша, она копируется из кэша, содержащего самую последнюю копию, локально обновляется, а все остальные копии становятся недействительными.Даже если ядра обращаются к разным частям строки кэша.Такая ситуация называется ложное совместное использование , и это важная проблема для многоядерного программирования.
Что касается проблемы случайной записи, строки кэша имеют размер 64 байта и могут содержать 8 int64, и есликомпьютер имеет 8 ядер, каждое ядро будет обрабатывать в среднем 2 значения.Следовательно, существует важный ложный обмен, который замедляет запись.
Мы провели некоторые оценки производительности.Это было выполнено в C для того, чтобы включить оценку влияния распараллеливания.Мы сравнили 5 функций, которые обрабатывают массивы int64 размера N.
Просто копия b в c (c[i] = b[i]) (реализовано компилятором с memcpy())
Копирование с линейным индексом c[i] = b[d[i]], где d[i]==i (read_linear)
Копирование со случайным индексом c[i] = b[a[i]], где a -случайная перестановка 0..N-1 (read_random эквивалентно fwd в исходном вопросе)
Запись линейная c[d[i]] = b[i], где d[i]==i (write_linear)
Запись случайного числа c[a[i]] = b[i] с a случайной перестановкой 0..N-1 (write_random эквивалентно inv в вопросе)
Код был скомпилирован с gcc -O3 -funroll-loops -march=native -malign-double на процессоре Skylake.Производительность измеряется с _rdtsc() идано в циклах на итерацию.Функция выполняется несколько раз (1000-20000 в зависимости от размера массива), выполняется 10 экспериментов и сохраняется наименьшее время.
Диапазон размеров массива от 4000 до 1200000. Весь код был измерен с последовательным ипараллельная версия с openmp.
Вот график результатов.Функции имеют разные цвета, с последовательной версией в толстых линиях и параллельной версией в тонких.
Прямая копия (очевидно) самая быстраяи реализуется gcc с высокооптимизированным memcpy().Это способ получить оценку пропускной способности данных с помощью памяти.Он варьируется от 0,8 цикла на итерацию (ИПЦ) для маленьких матриц до 2,0 ИПЦ для больших.
Показатели линейного чтения примерно в два раза длиннее, чем memcpy, но есть 2 чтения и запись, против 1 чтение и запись для прямого копирования.Более индекс добавляет некоторую зависимость.Минимальное значение составляет 1,56 ИПЦ, а максимальное значение 3,8 ИПЦ.Линейная запись немного длиннее (5-10%).
Чтение и запись со случайным индексом являются целью исходного вопроса и заслуживают более длинных комментариев.Вот результаты.
size 4000 6000 9000 13496 20240 30360 45536 68304 102456 153680 230520 345776 518664 777992 1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785
небольшие значения (<10k): кэш-память L1 имеет размер 32 КБ и может содержать массив из 4 КБ uint64.Обратите внимание, что из-за случайности индекса после ~ 1/8 итераций кэш L1 будет полностью заполнен значениями массива случайных индексов (поскольку строки кэша имеют размер 64 байта и могут содержать 8 элементов массива).При доступе к другим линейным массивам мы быстро сгенерируем много пропусков L1, и нам придется использовать кэш L2.Доступ к кэш-памяти L1 составляет 5 циклов, но он конвейерный и может обслуживать пару значений за цикл.Доступ L2 длиннее и требует 12 циклов.Количество пропусков одинаково для случайного чтения и записи, но мы видим, что мы полностью оплачиваем двойной доступ, необходимый для записи, когда размер массива небольшой. </p>
средние значения (10k-100k): Кэш-память L2 имеет размер 256 КБ и может содержать массив размером 32 КБ Int64.После этого нам нужно перейти в кэш L3 (12Mo).По мере увеличения размера увеличивается число пропусков в L1 и L2 и соответственно увеличивается время вычисления.Оба алгоритма имеют одинаковое количество пропусков, в основном из-за случайного чтения или записи (другие обращения являются линейными и могут быть очень эффективно предварительно извлечены кэшем).Мы извлекаем фактор два между случайным чтением и записью, уже отмеченными в ответе BM.Это может быть частично объяснено двойной стоимостью записи.
большие значения (> 100k): разница между методами постепенно уменьшается.Для этих размеров большая часть информации хранится в кеше L3.Размер L3 достаточен для хранения всего массива 1,5 М, и линии с меньшей вероятностью будут извлечены.Следовательно, для записей, после начального чтения, большее количество записей может быть выполнено без извлечения строки, и относительная стоимость операций записи по сравнению с чтением снижается.Для этих больших размеров есть также много других факторов, которые необходимо учитывать.Например, кеши могут обслуживать только ограниченное число пропусков (тип 16), а когда количество пропусков велико, это может быть ограничивающим фактором.
Одно слово на параллельном ompверсия случайного чтения и записи.За исключением небольших размеров, где наличие массива случайных индексов, распределенного по нескольким кэшам, может не быть преимуществом, они систематически ~ в два раза быстрее.Для больших размеров мы ясно видим, что разрыв между случайным чтением и записью увеличивается из-за ложного совместного использования.
Почти невозможно делать количественные прогнозы со сложностью современных компьютерных архитектур, даже для простого кода и дажеКачественные объяснения поведения сложны и должны учитывать множество факторов.Как упоминалось в других ответах, программные аспекты, связанные с питоном, также могут оказывать влияние.Но, хотя это может происходить в некоторых ситуациях, в большинстве случаев нельзя считать, что чтение обходится дороже из-за зависимости от данных.