Как работает оперативная память? Почему это постоянный случайный доступ?

Ответ 1

Поскольку программному обеспечению нравится O (1) "рабочая" память, и, таким образом, аппаратное обеспечение должно вести себя таким образом

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

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

Теперь для "обычной" ОЗУ это свойство (по крайней мере, AFAIK) истинно - когда процессор/материнская плата/контроллер памяти запрашивает чип RAM для получения некоторых данных, он делает это в постоянное время; детали не очень актуальны для разработки программного обеспечения, а внутренняя часть чипов памяти многократно менялась в прошлом и снова изменится в будущем. Если вас интересует обзор деталей текущих ОЗУ, вы можете посмотреть здесь о DRAM.

Общая концепция заключается в том, что чипы ОЗУ не содержат ленты, которую необходимо переместить, или дискового плеча, который должен быть расположен; когда вы запрашиваете у них байт в определенном месте, работа (в основном изменение настроек некоторых аппаратных мультиплексоров, которые соединяют вывод с ячейками, где хранится статус байта) одинаково для любого места, которое вы могли бы просить; таким образом, вы получаете производительность O (1)

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

Итак:

массивы массивов по адресному пространству, которое отображается по ОЗУ, которое имеет O (1) случайный доступ; все карты (более или менее) O (1), массивы сохраняют оперативную производительность О (1) оперативной памяти.

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

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

Ответ 2

Расчет, полученный от начала массива до любого заданного элемента, принимает только две операции, умножение (times sizeof (element)) и добавление. Обе эти операции являются постоянными. Часто с сегодняшними процессорами это можно сделать практически без времени, поскольку процессор оптимизирован для такого доступа.

Ответ 3

Когда я говорю массив [4] = 12 в программе, я действительно просто храню бит представление адреса памяти в регистр. Это физическое Регистрация в аппаратном обеспечении включит соответствующие электрические сигналы в соответствии с представлением бит, которое я ему подал. Эти электрические сигналы каким-то образом волшебным образом (надеюсь, кто-то может объяснить магия) доступа к правильному адресу памяти в физической/основной памяти.

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

array[4] = 12;

Итак, из комментариев кажется, что вам нужно получить базовый адрес массива, а затем умножить на размер элемента массива (или сдвиг, если такая оптимизация возможна), чтобы получить адрес (из ваших программ перспектива) расположения памяти. Справа от летучей мыши у нас есть проблема. Являются ли эти элементы уже в реестре или нам нужно их получить? Базовый адрес для массива может быть или не быть в регистре в зависимости от кода, который окружает эту строку кода, в частности предшествующий ему код. Этот адрес может находиться в стеке или в другом месте в зависимости от того, где вы его объявили и как. И это может быть или не иметь значения, сколько времени это займет. Оптимизирующий компилятор может (часто) заходить так далеко, чтобы предварительно вычислить адрес массива [4] и поместить его где-нибудь, чтобы он мог войти в регистр, а умножение никогда не происходит во время выполнения, поэтому абсолютно неверно, что вычисление массива [4] для случайного доступа является фиксированным количеством времени по сравнению с другими случайными доступом. В зависимости от процессора некоторые немедленные шаблоны являются одной инструкцией, которую другие принимают больше, что также имеет значение для того, читается ли этот адрес из .text или stack или т.д. И т.д.... Чтобы не курить и яйцо, что проблема до смерти, предположим, что у нас есть вычислен адрес массива [4].

Это операция записи, с точки зрения программистов. Начиная с простого процессора, без кеша, без буфера записи, без mmu и т.д. В конце концов простой процессор поместит адрес на край ядра процессора, с строкой записи и данными, каждая шина процессоров отличается от других семейств процессоров, но это примерно то же самое, что адрес и данные могут выходить в одном цикле или в отдельных циклах. Тип команды (чтение, запись) может происходить одновременно или различно. но команда выходит. Край ядра процессора подключен к контроллеру памяти, который декодирует этот адрес. Результатом является пункт назначения, является ли это периферийным, если это так, и в какой шине это память, если это так, на какой шине памяти и так далее. Предположим, что ram, предположим, что этот простой процессор имеет sram не драм. Sram дороже и быстрее в сравнении яблок с яблоками. У sram есть адрес и строки записи/чтения и другие элементы управления. В конце концов вы будете иметь тип транзакции, чтение/запись, адрес и данные. Однако sram, однако, его геометрия будет направлять и сохранять отдельные биты в их отдельных парах/группах транзисторов.

Цикл записи может быть огнем и забыть. Вся информация, необходимая для завершения транзакции, это запись, это адрес, это данные, которые известны сразу и там. Контроллер памяти может, если он захочет сообщить процессору, что транзакция записи завершена, даже если данные нигде не находятся рядом с памятью. Эта пара адресов/данных займет время, чтобы добраться до памяти, и процессор может продолжать работать. Некоторые системы, хотя конструкция такова, что процессоры пишут транзакцию, ждут, пока сигнал не вернется, чтобы указать, что запись полностью переместилась в плунжер. При настройке типа "огонь" и "забыть" этот адрес/данные будут помещены в очередь где-то и прокладываются к оЗУ. Очередь не может быть бесконечно глубокой, иначе это будет сам баран, поэтому он конечен, и вполне возможно, что многие записи в строке могут заполнить эту очередь быстрее, чем другой конец может записать в ram. В этот момент текущая и следующая запись должны ждать очереди, чтобы указать, что есть место для еще одного. Таким образом, в ситуациях, подобных этому, насколько быстро происходит ваша запись, независимо от того, связан ли ваш простой процессор с вводом-выводом или нет, с предыдущими транзакциями, которые могут или не могут быть инструкциями по написанию, которые предшествовали данной инструкции.

Теперь добавьте некоторую сложность. ECC или другое имя, которое вы хотите назвать (EDAC, другое). Способ работы ECC-памяти заключается в том, что записи являются фиксированными, даже если ваша реализация состоит из четырех разделов памяти объемом 8 бит, которые дают вам 32 бита данных для записи, вы должны иметь фиксированный код, который охватывает ECC, и вы должны одновременно записывайте биты данных плюс ecc-бит (необходимо вычислить ecc по всей ширине). Так что если это 8-битная запись, например, в 32-битную защищенную ECC-памятью, тогда для цикла записи требуется цикл чтения. Прочитайте 32 бита (проверьте ecc на это чтение) измените новые 8 бит в этом 32-битном шаблоне, вычислите новый шаблон ecc, напишите 32 бита плюс ecc-бит. Естественно, что часть чтения цикла записи может закончиться ошибкой ecc, которая просто делает жизнь еще более увлекательной. Ошибки с единичным битом могут быть исправлены обычно (что хорошо для ECC/EDAC, если оно не может), многобитовых ошибок нет. То, как аппаратное обеспечение предназначено для устранения этих ошибок, влияет на то, что происходит дальше, ошибка чтения может просто просачиваться обратно на процессор, сбой в транзакции записи, или он может вернуться в качестве прерывания и т.д. Но вот другое место, где один случайный доступ не то же самое, что и другое, в зависимости от доступной памяти, а размер доступа для чтения-модификации-записи определенно занимает больше времени, чем простая запись.

Драма также может попасть в эту категорию с фиксированной шириной, даже без ECC. Фактически вся память попадает в эту категорию в какой-то момент. Массив памяти оптимизирован на кремнии для определенной высоты и ширины в единицах бит. Вы не можете нарушать эту память, ее можно читать и записывать только в единицах этой ширины на этом уровне. Силиконовые библиотеки будут включать в себя множество геометрий ram, и дизайнеры будут выбирать эти геометрии для своих частей, а части будут иметь фиксированные пределы, и часто вы можете использовать несколько частей для получения целочисленной ширины такого размера, и иногда дизайн будет позволяют записывать только одну из этих частей, если меняются только некоторые из битов, или некоторые конструкции заставляют все детали загораться. Обратите внимание, как следующее семейство модулей ddr, которые вы подключаете к домашнему компьютеру или ноутбуку, первая волна - это много частей с обеих сторон платы. Затем, когда эта технология станет старше и станет более скучной, она может измениться до меньшего количества частей с обеих сторон платы, и в конечном итоге становится меньше частей на одной стороне платы до того, как эта технология устареет, и мы уже входим в следующий.

Эта категория фиксированной ширины также несет в себе штрафные санкции. К сожалению, большинство людей учатся на машинах x86, которые не ограничивают вас выравниванием доступа, как и многие другие платформы. Существует определенный штраф производительности на x86 или других за неприглашенные обращения, если это разрешено. Обычно, когда люди переходят к мипсам или обычно к одному из устройств с батарейным питанием, когда они сначала учатся программистам о выровненных доступах. И, к сожалению, найти их скорее болезненными, чем благословением (из-за простоты как в программировании, так и в плане преимуществ оборудования, которые приходят от него). В двух словах, если ваша память имеет ширину в 32 бита и доступна только для чтения, чтения или записи, 32 бита за раз, что означает, что она ограничена только выравниванием доступа. Шина памяти в 32-битной памяти обычно не имеет младших битов адреса a [1: 0], потому что для них нет необходимости. эти младшие биты с точки зрения программистов являются нулями. если бы наша запись была 32 бит против одной из этих 32-битных памяти, а адрес был 0x1002. Затем кто-то по линии должен прочитать память по адресу 0x1000 и взять два наших байта и изменить это 32-битное значение, а затем записать его обратно. Затем возьмите 32 бита по адресу 0x1004 и измените два байта и запишите их обратно. четыре цикла шины для одной записи. Если бы мы писали 32 бита для адреса 0x1008, хотя это была бы простая 32-разрядная запись, без чтения.

sram против драма. драм болезненно медленный, но супер дешевый. от половины до четверти - количество транзисторов на бит. (4 для sram, например, 1 для драм). Sram запоминает бит до тех пор, пока включена мощность. Драма должна быть обновлена, как аккумуляторная батарея. Даже если питание остается на одном бите, оно будет запоминаться только в течение очень короткого периода времени. Поэтому некоторые аппаратные средства (ddr-контроллер и т.д.) Должны регулярно выполнять циклы шины, говорящие, что RAM запоминает определенный фрагмент памяти. Эти циклы крадут время от вашего процессора, желая получить доступ к этой памяти. драма очень медленная, он может сказать 2133 МГц (2.133ghz) на коробке. Но это больше похоже на барабан 133 МГц, правый 0,133 ГГц. Первый чит - ддр. Обычно вещи в цифровом мире происходят один раз за такт. Часы идут к утверждённому состоянию, затем переходит в состояние дезактивированного (единицы и нули), один цикл - один такт. DDR означает, что он может что-то делать как на высоком полупериоде, так и на нижнем полупериоде. так что память 2133 ГГц действительно использует 1066 МГц часов. Затем происходит конвейер, как параллелизмы, вы можете вставлять команды в пакетах с такой высокой скоростью, но в конечном итоге к тому, что на барабане нужно получить доступ. Общий драм не является детерминированным и очень медленным. Sram, с другой стороны, никаких обновлений не требует, чтобы он помнил, пока власть включена. Может быть в несколько раз быстрее (133mhz * N) и так далее. Он может быть детерминированным.

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

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

Несколько уровней кешей. l1, l2, l3... L1, как правило, самый быстрый либо по своей технологии, либо по близости, и, как правило, самый маленький, и он идет вверх от скорости и размера, а некоторые из них связаны со стоимостью памяти. Мы делаем запись, но когда вы читаете кеш, прочитайте, что если l1 имеет пропущенность, он переходит на l2, который, если у него есть промах, переходит на l3, который, если он пропустит пропущен, переходит в основную память, тогда l3, l2 и l1 все сохранит копию. Таким образом, промах на всех 3, конечно, самый болезненный и медленнее, чем если бы у вас не было кеша вообще, но последовательные чтения дадут вам кешированные элементы, которые теперь находятся в l1 и очень быстрые, так как кеш будет полезным последовательным чтением по линии кэша требуется меньше времени, чем чтение этой большой памяти непосредственно из медленного драм. Система не должна иметь 3 слоя кешей, она может варьироваться. Аналогично, некоторые системы могут отделять выборки команд от чтения данных и могут иметь отдельные кэши, которые не выселяют друг друга, а некоторые кэши не являются отдельными, а выборки команд могут вытеснять данные из чтения данных.

кэширует помощь при выравнивании. Но, конечно же, существует еще более суровое наказание за неудовлетворенный доступ к кеш-линиям. Кэши имеют тенденцию работать, используя куски памяти, называемые линиями кэша. Это часто несколько целочисленных по размеру памяти на другой стороне. 32-битная память, например, кэш-строка может составлять 128 бит или 256 бит, например. Поэтому, если и когда строка кеша находится в кеше, тогда чтение-изменение-запись из-за негласной записи происходит против более быстрой памяти, но еще более болезненной, чем выровненной, но не такой болезненной. Если это было негласное чтение, и адрес был таким, что часть этих данных находится на одной стороне границы строки кэша, а другая на другой, тогда две строки кэша должны быть прочитаны. Например, 16-битное чтение может стоить вам много байтов, считанных с самой медленной памятью, очевидно, в несколько раз медленнее, чем если бы у вас не было кэшей вообще. В зависимости от того, как создаются кэши и система памяти в целом, если вы выполняете запись через границу строки кэша, это может быть аналогичным образом больно или, может быть, не так сильно, чтобы фракция записывала в кеш, а другая фракция выходила с другой стороны, как на меньшую величину.

Следующий уровень сложности - mmu. Предоставление процессору и программисту иллюзии плоских пространств памяти и/или контроль за тем, что кэшируется или нет, и/или защита памяти, и/или иллюзия, что все программы работают в одном и том же адресном пространстве (поэтому ваша инструментальная цепочка всегда может компилироваться /link для адреса 0x8000, например). Mmu принимает часть виртуального адреса на стороне ядра процессора. выглядит так, что в таблице или в серии таблиц эти поисковые запросы часто находятся в системном адресном пространстве, поэтому каждый из этих запросов может быть одним или несколькими из вышеперечисленного, поскольку каждый из них представляет собой цикл памяти в системной памяти. Эти поисковые запросы могут привести к ошибкам ecc, даже если вы пытаетесь сделать запись. В конце концов, после одного или двух или трех или более чтений, mmu определил, что адрес находится на другой стороне mmu, и свойства (кэшируемые или нет и т.д.) И которые передаются следующей вещи (l1, и т.д.) и все вышеизложенное. У некоторых mmus есть немного кеша в них из некоторого количества предыдущих транзакций, помните, что программы являются последовательными, трюки, используемые для увеличения иллюзии производительности памяти, основаны на последовательном доступе, а не на случайном доступе. Таким образом, некоторое количество поисковых запросов может быть сохранено в mmu, поэтому сразу не нужно выходить в основную память...

Таким образом, в современном компьютере с mmus, кешами, драм, последовательными чтениями, в частности, но также и записи, скорее всего, будет быстрее, чем произвольный доступ. Разница может быть драматичной. Первая транзакция в последовательном чтении или записи в данный момент представляет собой произвольный доступ, поскольку он не был замечен ни когда-либо, ни какое-то время. Как только последовательность продолжается, хотя оптимизация падает в порядке, а следующие несколько/некоторые заметно быстрее. Размер и выравнивание вашей транзакции также играют важную роль в производительности. Несмотря на то, что происходит так много не детерминированных действий, как программист с этими знаниями вы изменяете свои программы, чтобы работать намного быстрее, или, если не повезло или специально, вы можете изменить свои программы, чтобы они работали намного медленнее. Последовательный будет, как правило, быстрее на одной из этих систем. случайный доступ будет очень недетерминированным. Массив [4] = 12; за которым следует массив [37] = 12; Эти две операции высокого уровня могут занимать значительно разные промежутки времени, как при вычислении адреса записи, так и фактической записи. Но, например, discarded_variable = array [3]; Массив [3] = 11; Массив [4] = 12; Может довольно часто выполнять значительно быстрее, чем массив [3] = 11; Массив [4] = 12;

Ответ 4

Массивы на C и С++ имеют произвольный доступ, поскольку они хранятся в ОЗУ - Random Access Memory в конечном, предсказуемом порядке. В результате для определения местоположения данной записи требуется простая линейная операция (a [i] = a + sizeof (a [0]) * i). Этот расчет имеет постоянное время. С точки зрения процессора не требуется операция "искать" или "перематывать", она просто сообщает памяти "загрузить значение по адресу X".

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

Тем не менее - общий принцип заключается в том, что время получения заданного набора из 4 или 8 байтов из ОЗУ одинаково независимо от адреса. Например. если с чистого листа вы получите доступ к ОЗУ [0] и ОЗУ [4294967292], процессор получит ответ в пределах того же количества циклов.

#include <iostream>
#include <cstring>
#include <chrono>

// 8Kb of space.
char smallSpace[8 * 1024];

// 64Mb of space (larger than cache)
char bigSpace[64 * 1024 * 1024];

void populateSpaces()
{
    memset(smallSpace, 0, sizeof(smallSpace));
    memset(bigSpace, 0, sizeof(bigSpace));
    std::cout << "Populated spaces" << std::endl;
}

unsigned int doWork(char* ptr, size_t size)
{
    unsigned int total = 0;
    const char* end = ptr + size;
    while (ptr < end) {
        total += *(ptr++);
    }
    return total;
}

using namespace std;
using namespace chrono;

void doTiming(const char* label, char* ptr, size_t size)
{
    cout << label << ": ";
    const high_resolution_clock::time_point start = high_resolution_clock::now();
    auto result = doWork(ptr, size);
    const high_resolution_clock::time_point stop = high_resolution_clock::now();
    auto delta = duration_cast<nanoseconds>(stop - start).count();
    cout << "took " << delta << "ns (result is " << result << ")" << endl;
}

int main()
{
    cout << "Timer resultion is " << 
        duration_cast<nanoseconds>(high_resolution_clock::duration(1)).count()
        << "ns" << endl;

    populateSpaces();

    doTiming("first small", smallSpace, sizeof(smallSpace));
    doTiming("second small", smallSpace, sizeof(smallSpace));
    doTiming("third small", smallSpace, sizeof(smallSpace));
    doTiming("bigSpace", bigSpace, sizeof(bigSpace));
    doTiming("bigSpace redo", bigSpace, sizeof(bigSpace));
    doTiming("smallSpace again", smallSpace, sizeof(smallSpace));
    doTiming("smallSpace once more", smallSpace, sizeof(smallSpace));
    doTiming("smallSpace last", smallSpace, sizeof(smallSpace));
}

Live demo: http://ideone.com/9zOW5q

Выход (от идеона, который может быть не идеальным)

Success  time: 0.33 memory: 68864 signal:0
Timer resultion is 1ns
Populated spaces
doWork/small: took 8384ns (result is 8192)
doWork/small: took 7702ns (result is 8192)
doWork/small: took 7686ns (result is 8192)
doWork/big: took 64921206ns (result is 67108864)
doWork/big: took 65120677ns (result is 67108864)
doWork/small: took 8237ns (result is 8192)
doWork/small: took 7678ns (result is 8192)
doWork/small: took 7677ns (result is 8192)
Populated spaces
strideWork/small: took 10112ns (result is 16384)
strideWork/small: took 9570ns (result is 16384)
strideWork/small: took 9559ns (result is 16384)
strideWork/big: took 65512138ns (result is 134217728)
strideWork/big: took 65005505ns (result is 134217728)

Что мы видим здесь, это влияние кеша на производительность доступа к памяти. В первый раз, когда мы нажимаем smallSpace, требуется ~ 8100ns для доступа ко всем 8kb небольшого пространства. Но когда мы называем это снова сразу после, дважды, он принимает ~ 600ns меньше при ~ 7400ns.

Теперь мы уходим и делаем bigspace, что больше, чем текущий кеш процессора, поэтому мы знаем, что мы сбрасывали кеши L1 и L2.

Возвращаясь к маленькому, мы уверены, что сейчас не кэшируется, мы снова видим ~ 8100ns в первый раз и ~ 7400 для вторых двух.

Мы удаляем кеш, и теперь мы вводим другое поведение. Мы используем версию с чередованием. Это усиливает эффект "промахивания кеша" и значительно снижает время, хотя "небольшое пространство" вписывается в кэш L2, поэтому мы по-прежнему видим сокращение между проходом 1 и двумя проходами.