Разрешение неоднозначности памяти

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

Фон

Зависимости

При попытке выполнить инструкции не по порядку микропроцессор должен учитывать истинные зависимости между инструкциями . Например, рассмотрим простую истинную зависимость:

1: add $1, $2, $3      # R1 <= R2 + R3
2: add $5, $1, $4      # R5 <= R1 + R4 (dependent on 1)

В этом примере add Инструкция в строке 2 зависит от add инструкции в строке 1, поскольку регистр R1 является исходным операндом операции сложения в строке 2. add в строке 2 не может выполняться до тех пор, пока не будет add в строке 1 завершается. В этом случае зависимость статична и легко определяется микропроцессором, поскольку источниками и приемниками являются регистры. Регистр назначения add инструкция в строке 1 ( R1) является частью кодирования инструкций и поэтому может быть определен микропроцессором на ранней стадии, на этапе декодирования конвейера. Аналогично, исходные регистры add инструкция в строке 2 ( R1 и R4) также закодированы в самой инструкции и определяются при декодировании. Чтобы учесть эту истинную зависимость, логика планировщика микропроцессора будет выдавать эти инструкции в правильном порядке (сначала инструкция 1, затем инструкция 2), так что результаты операции 1 будут доступны, когда они потребуются инструкции 2.

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

1: store $1, 2($2)      # Mem[R2+2] <= R1
2: load  $3, 4($4)      # R3 <= Mem[R4+4] (possibly dependent on 1, possible same address as above)

Здесь инструкция сохранения записывает значение в ячейку памяти, указанную значением в адресе (R2+2), а инструкция загрузки считывает значение в ячейке памяти, указанной значением в адресе (R4+4). Микропроцессор не может статически определить до выполнения, являются ли ячейки памяти, указанные в этих двух инструкциях, разными или являются одним и тем же местом, поскольку эти местоположения зависят от значений в R2 и R4. Если местоположения разные, инструкции независимы и могут успешно выполняться вне очереди. Однако, если местоположения одинаковы, то инструкция загрузки зависит от хранилища для создания своего значения. Это известно как неоднозначная зависимость .

Операции внеочередного выполнения и доступа к памяти

Выполнение операций загрузки и сохранения не по порядку может привести к неверным результатам, если зависимая пара загрузки/сохранения была выполнена не по порядку. Рассмотрим следующий фрагмент кода, представленный в MIPS сборке :

1: div $27, $20
2: sw  $27, 0($30)
3: lw  $08, 0($31)
4: sw  $26, 0($30)
5: lw  $09, 0($31)

Предположим, что логика планирования выдаст инструкцию исполнительному устройству, когда все его операнды-регистры будут готовы. Далее предположим, что регистры $30 и $31 готовы: значения в $30 и $31 были рассчитаны давно и не изменились. Однако предположим $27 не готов: его значение все еще находится в процессе вычисления div (целочисленное деление). Наконец, предположим, что регистры $30 и $31 содержат одно и то же значение, и, таким образом, все загрузки и сохранения во фрагменте получают доступ к одному и тому же слову памяти.

В этой ситуации sw $27, 0($30) инструкция в строке 2 не готова к выполнению, но lw $08, 0($31) инструкция в строке 3 готова. Если процессор позволяет lw инструкция, выполняемая перед sw, загрузка прочитает старое значение из системы памяти; однако он должен был прочитать значение, которое только что было записано там пользователем sw. Загрузка и сохранение выполнялись вне программного порядка, но между ними была нарушена зависимость от памяти.

Аналогично предположим, что регистр $26 готов . sw $26, 0($30) Инструкция в строке 4 также готова к выполнению и может выполняться раньше предыдущей. lw $08, 0($31) в строке 3. Если это произойдет, lw $08, 0($31) Инструкция прочитает неправильное значение из системы памяти, поскольку более поздняя инструкция сохранения записала туда свое значение до выполнения загрузки.

Характеристика зависимостей памяти

Зависимости памяти бывают трех видов:

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

Три зависимости показаны в предыдущем сегменте кода (воспроизведено для ясности):

1: div $27, $20
2: sw  $27, 0($30)
3: lw  $08, 0($31)
4: sw  $26, 0($30)
5: lw  $09, 0($31)

The lw $08, 0($31) инструкция в строке 3 имеет RAW-зависимость от sw $27, 0($30) инструкция в строке 2, а lw $09, 0($31) инструкция в строке 5 имеет RAW-зависимость от sw $26, 0($30) инструкция в строке 4. Обе инструкции загрузки считывают адрес памяти, записанный предыдущими хранилищами. Хранилища были последними производителями этого адреса памяти, и нагрузки считывают значение этого адреса памяти.
The sw $26, 0($30) инструкция в строке 4 имеет зависимость WAR от lw $08, 0($31) в строке 3, поскольку она записывает адрес памяти, из которого считывается предыдущая загрузка.
The sw $26, 0($30) инструкция в строке 4 имеет WAW-зависимость от sw $27, 0($30) инструкцию в строке 2, поскольку оба хранилища записывают по одному и тому же адресу памяти.

Механизмы устранения неоднозначности памяти

Современные микропроцессоры используют следующие механизмы, реализованные аппаратно , для разрешения неоднозначных зависимостей и восстановления в случае нарушения зависимости.

Как избежать зависимостей WAR и WAW

Значения из инструкций сохранения не сохраняются в системе памяти (в современных микропроцессорах — в кэше ЦП ) при их выполнении. Вместо этого инструкции сохранения, включая адрес памяти и данные сохранения, буферизуются в сохранения очереди до тех пор, пока не достигнут точки вывода из эксплуатации. Когда хранилище удаляется, оно записывает свое значение в систему памяти. Это позволяет избежать проблем с зависимостью WAR и WAW, показанных в приведенном выше фрагменте кода, когда более ранняя загрузка получает неправильное значение из системы памяти, поскольку более позднему сохранению было разрешено выполнение до более ранней загрузки.

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

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

Магазин для загрузки переадресации

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

Чтобы решить эту проблему, процессоры используют метод, называемый пересылкой от хранилища к загрузке с использованием очереди хранилища. Помимо буферизации хранилищ до выхода из эксплуатации, очередь хранилища служит второй цели: пересылка данных из завершенных, но еще не выведенных из эксплуатации («находящихся») хранилищ для последующих загрузок. Вместо простой очереди FIFO очередь хранилища на самом деле представляет собой память с адресацией по содержимому (CAM), поиск в которой осуществляется по адресу памяти. Когда выполняется загрузка, она ищет в очереди хранилища текущие хранилища по тому же адресу, который логически находится раньше в программном порядке. Если соответствующее хранилище существует, загрузка получает значение данных из этого хранилища, а не из системы памяти. Если подходящего хранилища нет, загрузка обращается к системе памяти как обычно; все предыдущие соответствующие хранилища должны уже выйти из эксплуатации и зафиксировать свои значения. Этот метод позволяет нагрузкам получать правильные данные, если их хранилище-производитель завершено, но еще не удалено.

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

Нарушения зависимости от RAW

Обнаружение нарушений зависимости RAW

Современные вышедшие из строя процессоры могут использовать ряд методов для обнаружения нарушения зависимости RAW, но все методы требуют отслеживания текущих нагрузок от выполнения до вывода из эксплуатации. Когда выполняется загрузка, она обращается к системе памяти и/или очереди сохранения для получения значения своих данных, а затем ее адрес и данные буферизуются в очереди загрузки до выхода из эксплуатации. Очередь загрузки по структуре и функциям аналогична очереди сохранения, и фактически в некоторых процессорах может быть объединена с очередью сохранения в единую структуру, называемую очередью загрузки-сохранения , или LSQ . Для обнаружения нарушений зависимости RAW используются или были предложены следующие методы:

Загрузить очередь поиска CAM

При использовании этого метода очередь загрузки, как и очередь сохранения, представляет собой CAM, поиск которого осуществляется по адресу доступа к памяти, и отслеживает все текущие загрузки. Когда хранилище выполняется, оно ищет в очереди загрузки завершенные загрузки с того же адреса, которые логически расположены позже в программном порядке. Если такая соответствующая загрузка существует, она должна была быть выполнена до сохранения и, таким образом, прочитать неправильное старое значение из очереди системы памяти/хранилища. Любые инструкции, в которых использовалось значение нагрузки, также использовали неверные данные. Для восстановления в случае обнаружения такого нарушения нагрузка помечается как «нарушенная» в буфере выбытия. Хранилище остается в очереди сохранения и буфере удаления и удаляется обычным образом, фиксируя свое значение в системе памяти при выходе из эксплуатации. Однако когда нарушенная загрузка достигает точки вывода из эксплуатации, процессор очищает конвейер и возобновляет выполнение инструкции загрузки. На этом этапе все предыдущие хранилища зафиксировали свои значения в системе памяти. Инструкция загрузки теперь будет считывать правильное значение из системы памяти, и все зависимые инструкции будут выполняться повторно с использованием правильного значения.

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

Неопределенность на пенсии

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

Этот метод концептуально проще, чем поиск в очереди загрузки, и исключает использование второго CAM и его энергоемкого поиска (очередь загрузки теперь может быть простой очередью FIFO). Поскольку нагрузка должна повторно получить доступ к системе памяти непосредственно перед выходом из строя, доступ должен быть очень быстрым, поэтому эта схема опирается на быстрый кэш. Однако независимо от того, насколько быстр кэш, второй доступ к системе памяти для каждой инструкции загрузки, находящейся вне порядка, увеличивает задержку вывода инструкций и увеличивает общее количество обращений к кэшу, которые должен выполнить процессор. Дополнительный доступ к кэшу во время вывода из эксплуатации может быть обеспечен путем повторного использования существующего порта кэша; однако это создает конкуренцию за ресурсы порта с другими загрузками и хранилищами в процессоре, пытающимися выполниться, и, таким образом, может привести к снижению производительности. В качестве альтернативы можно добавить дополнительный порт кэша только для устранения неоднозначности нагрузки, но это увеличивает сложность, мощность и площадь кэша. Некоторые недавние работы (Roth 2005) показали способы предотвращения повторного выполнения многих загрузок, если известно, что никакого нарушения зависимости RAW не могло произойти; такой метод поможет или устранит такие задержки и конфликты за ресурсы.

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

Как избежать нарушений зависимости от RAW

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

Первый вариант, обеспечивающий порядок загрузки и хранения, позволяет избежать зависимостей RAW, поскольку нет возможности выполнения загрузки до хранилища ее производителя и получения неверных данных. Другая возможность — эффективно разбить загрузку и сохранение на две операции: генерацию адреса и доступ к кэшу. С помощью этих двух отдельных, но связанных операций ЦП может разрешить загрузкам и сохранениям доступ к системе памяти только после того, как адреса всех предыдущих загрузок и сохранений были сгенерированы и буферизованы в LSQ. После генерации адреса больше не существует неоднозначных зависимостей, поскольку все адреса известны, и поэтому зависимые загрузки не будут выполняться до тех пор, пока не будут завершены соответствующие сохранения. Эта схема по-прежнему допускает некоторую «неупорядоченность» — операции генерации адресов для любых текущих загрузок и сохранений могут выполняться вне очереди, и как только адреса были сгенерированы, доступ к кешу для каждой загрузки или сохранения может быть выполнен вне очереди. происходить в любом порядке, который соответствует (теперь известным) истинным зависимостям.

Дополнительные проблемы

Прогнозирование зависимости памяти

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

См. также