Устранение неоднозначности памяти — это набор методов, используемых высокопроизводительными микропроцессорами с внеочередным выполнением, которые выполняют инструкции доступа к памяти (загружают и сохраняют) вне программного порядка. Механизмы устранения неоднозначности памяти, реализованные с использованием цифровой логики внутри ядра микропроцессора, обнаруживают истинные зависимости между операциями памяти во время выполнения и позволяют процессору восстановиться, когда зависимость была нарушена. Они также устраняют ложные зависимости памяти и обеспечивают больший параллелизм на уровне команд , обеспечивая безопасное выполнение операций загрузки и сохранения вне очереди.
При попытке выполнить инструкции не по порядку микропроцессор должен учитывать истинные зависимости между инструкциями . Например, рассмотрим простую истинную зависимость:
1: добавить $1, $2, $3 # R1 <= R2 + R32: добавить $5, $1, $4 # R5 <= R1 + R4 (в зависимости от 1)
В этом примере addинструкция в строке 2 зависит от addинструкции в строке 1, поскольку регистр R1 является исходным операндом операции сложения в строке 2. Операция addв строке 2 не может выполняться до тех пор, пока addне завершится операция в строке 1. В этом случае зависимость статична и легко определяется микропроцессором, поскольку источниками и приемниками являются регистры. Регистр назначения инструкции addв строке 1 ( R1) является частью кодирования инструкции и поэтому может быть определен микропроцессором на ранней стадии, на этапе декодирования конвейера. Аналогично, исходные регистры инструкции addв строке 2 ( R1и R4) также кодируются в самой инструкции и определяются при декодировании. Чтобы учесть эту истинную зависимость, логика планировщика микропроцессора будет выдавать эти инструкции в правильном порядке (сначала инструкция 1, затем инструкция 2), так что результаты операции 1 будут доступны, когда они потребуются инструкции 2.
Сложности возникают, когда зависимость не является статически определимой. Такие нестатические зависимости возникают с инструкциями памяти (загрузка и сохранение), поскольку расположение операнда может быть косвенно указано как операнд регистра, а не указано непосредственно в самой кодировке инструкции.
1: сохранить $1, 2($2) # Mem[R2+2] <= R12: загрузить $3, 4($4) # R3 <= Mem[R4+4] (возможно, зависит от 1, возможно, тот же адрес, что и выше)
Здесь инструкция сохранения записывает значение в ячейку памяти, указанную значением в адресе (R2+2), а инструкция загрузки считывает значение в ячейке памяти, указанной значением в адресе (R4+4). Микропроцессор не может статически определить до выполнения, являются ли ячейки памяти, указанные в этих двух инструкциях, разными или являются одним и тем же местом, поскольку эти местоположения зависят от значений в R2 и R4. Если местоположения разные, инструкции независимы и могут успешно выполняться вне очереди. Однако если местоположения одинаковы, то инструкция загрузки зависит от хранилища для создания своего значения. Это известно как неоднозначная зависимость .
Выполнение операций загрузки и сохранения не по порядку может привести к неверным результатам, если зависимая пара загрузки/сохранения была выполнена не по порядку. Рассмотрим следующий фрагмент кода, представленный в сборке MIPS :
1: деление $27, $202: SW 27 долларов, 0 (30 долларов США)3: lw $08, 0($31)4: 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)инструкция прочитает неправильное значение из системы памяти, поскольку более поздняя инструкция сохранения записала туда свое значение до загрузки. казнен.
Зависимости памяти бывают трех видов:
Три зависимости показаны в предыдущем сегменте кода (воспроизведено для ясности):
1: деление $27, $202: SW 27 долларов, 0 (30 долларов США)3: lw $08, 0($31)4: 26 долл. США, 0 (30 долл. США)5: lw $09, 0($31)
lw $08, 0($31)в строке 3 имеет зависимость RAW от sw $27, 0($30)инструкции в строке 2, а lw $09, 0($31)инструкция в строке 5 имеет зависимость RAW от sw $26, 0($30)инструкции в строке 4. Обе инструкции загрузки считывают адрес памяти, записанный предыдущими хранилищами. Хранилища были последними производителями этого адреса памяти, и нагрузки считывают значение этого адреса памяти.sw $26, 0($30)в строке 4 имеет WAR-зависимость от lw $08, 0($31)инструкции в строке 3, поскольку она записывает адрес памяти, из которого считывается предыдущая загрузка.sw $26, 0($30)в строке 4 имеет WAW-зависимость от sw $27, 0($30)инструкции в строке 2, поскольку оба хранилища записывают данные в один и тот же адрес памяти.Современные микропроцессоры используют следующие механизмы, реализованные аппаратно , для разрешения неоднозначных зависимостей и восстановления в случае нарушения зависимости.
Значения из инструкций сохранения не сохраняются в системе памяти (в современных микропроцессорах — в кэше ЦП ) при их выполнении. Вместо этого инструкции сохранения, включая адрес памяти и данные сохранения, буферизуются в очереди сохранения до тех пор, пока не достигнут точки вывода из эксплуатации. Когда хранилище удаляется, оно записывает свое значение в систему памяти. Это позволяет избежать проблем с зависимостью WAR и WAW, показанных в приведенном выше фрагменте кода, когда более ранняя загрузка получает неправильное значение из системы памяти, поскольку более позднему сохранению было разрешено выполнение до более ранней загрузки.
Кроме того, буферизация сохранения до выхода из эксплуатации позволяет процессорам спекулятивно выполнять инструкции сохранения, которые следуют за инструкцией, которая может вызвать исключение ( например, загрузка неправильного адреса, деление на ноль и т. д.) или инструкцию условного перехода , направление которой (принято или нет) взято) пока неизвестно. Если инструкция, создающая исключение, не была выполнена или направление ветвления было предсказано неправильно, процессор выберет и выполнит инструкции по «неправильному пути». Эти инструкции вообще не должны были выполняться; условие исключения должно было возникнуть до выполнения любой из спекулятивных инструкций, или ветвь должна была пойти в другом направлении и вызвать выборку и выполнение других инструкций. Процессор должен «отбросить» любые результаты неправильного пути, спекулятивно выполненных инструкций, когда он обнаруживает исключение или неверное предсказание перехода. Сложность для хранилищ заключается в том, что любые хранилища на неправильном или неверно предсказанном пути не должны были зафиксировать свои значения в системе памяти; если бы хранилища зафиксировали свои значения, было бы невозможно «выбросить» фиксацию, а состояние памяти машины было бы повреждено данными из инструкции сохранения, которая не должна была выполняться.
Таким образом, без буферизации хранилища хранилища не могут выполняться до тех пор, пока не будут выполнены все предыдущие инструкции, которые могли вызвать исключение (и не вызвали исключение), и пока не станут известны все предыдущие направления ветвления. Принуждение магазинов ждать, пока не станут известны направления ветвей и исключения, значительно снижает агрессивность нарушений порядка и ограничивает ILP ( параллелизм на уровне инструкций ) и производительность. Благодаря буферизации хранилища хранилища могут выполняться раньше инструкций ветвления, вызывающих исключения или неразрешенные, буферизуя свои данные в очереди хранилища, но не фиксируя их значения до выхода из эксплуатации. Это предотвращает передачу значений хранилищами по неверно предсказанным или неверным путям в систему памяти, в то же время обеспечивая повышенную ILP и производительность при полном выполнении хранилищ вне порядка.
Буферизация хранилищ до выхода из эксплуатации позволяет избежать зависимостей WAW и WAR, но создает новую проблему. Рассмотрим следующий сценарий: хранилище выполняет и буферизует свой адрес и данные в очереди хранилища. Через несколько инструкций выполняется загрузка, считывающая из того же адреса памяти, в который только что записывалось хранилище. Если загрузка считывает свои данные из системы памяти, она считывает старое значение, которое было бы перезаписано предыдущим хранилищем. Данные, полученные при загрузке, будут неверными.
Чтобы решить эту проблему, процессоры используют метод, называемый пересылкой от хранилища к загрузке с использованием очереди хранилища. Помимо буферизации хранилищ до выхода из эксплуатации, очередь хранилища служит второй цели: пересылка данных из завершенных, но еще не выведенных из эксплуатации («находящихся») хранилищ для последующих загрузок. Вместо простой очереди FIFO очередь хранилища на самом деле представляет собой память с адресацией по содержимому (CAM), поиск в которой осуществляется по адресу памяти. При выполнении загрузки она ищет в очереди хранилища текущие хранилища по тому же адресу, который логически находится раньше в программном порядке. Если соответствующее хранилище существует, загрузка получает значение данных из этого хранилища, а не из системы памяти. Если подходящего хранилища нет, загрузка обращается к системе памяти как обычно; все предыдущие соответствующие хранилища должны уже выйти из эксплуатации и зафиксировать свои значения. Этот метод позволяет нагрузкам получать правильные данные, если их хранилище-производитель завершено, но еще не удалено.
В очереди сохранения может присутствовать несколько сохранений по адресу памяти загрузки. Чтобы справиться с этим случаем, очередь сохранения приоритетно кодируется для выбора последнего хранилища, которое логически предшествует загрузке в программном порядке. Определение того, какое хранилище является «последним», может быть достигнуто путем прикрепления какой-либо временной метки к инструкциям по мере их выборки и декодирования или, альтернативно, путем знания относительного положения (слота) загрузки по отношению к самым старым и новейшим хранилищам в пределах очередь в магазине.
Современные вышедшие из строя процессоры могут использовать ряд методов для обнаружения нарушения зависимости RAW, но все методы требуют отслеживания текущих нагрузок от выполнения до вывода из эксплуатации. Когда выполняется загрузка, она обращается к системе памяти и/или очереди сохранения для получения значения своих данных, а затем ее адрес и данные буферизуются в очереди загрузки до выхода из эксплуатации. Очередь загрузки по структуре и функциям аналогична очереди сохранения, и фактически в некоторых процессорах может быть объединена с очередью сохранения в единую структуру, называемую очередью загрузки-сохранения , или LSQ . Для обнаружения нарушений зависимости RAW используются или были предложены следующие методы:
При использовании этого метода очередь загрузки, как и очередь сохранения, представляет собой CAM, поиск которого осуществляется по адресу доступа к памяти, и отслеживает все текущие загрузки. Когда хранилище выполняется, оно ищет в очереди загрузки завершенные загрузки с того же адреса, которые логически расположены позже в программном порядке. Если такая соответствующая загрузка существует, она должна была быть выполнена до сохранения и, таким образом, прочитать неправильное старое значение из очереди системы памяти/хранилища. Любые инструкции, в которых использовалось значение нагрузки, также использовали неверные данные. Для восстановления в случае обнаружения такого нарушения нагрузка помечается как «нарушенная» в буфере выбытия. Хранилище остается в очереди сохранения и буфере удаления и удаляется обычным образом, фиксируя свое значение в системе памяти при выходе из эксплуатации. Однако когда нарушенная загрузка достигает точки вывода из эксплуатации, процессор очищает конвейер и возобновляет выполнение инструкции загрузки. На этом этапе все предыдущие хранилища зафиксировали свои значения в системе памяти. Инструкция загрузки теперь будет считывать правильное значение из системы памяти, и все зависимые инструкции будут выполняться повторно с использованием правильного значения.
Этот метод требует ассоциативного поиска очереди загрузки при каждом выполнении хранилища, что потребляет мощность схемы и может оказаться трудным путем синхронизации для больших очередей загрузки. Однако он не требует каких-либо дополнительных портов памяти ( кэша ) и не создает конфликтов ресурсов с другими выполняемыми загрузками или хранилищами.
При использовании этого метода инструкции загрузки, которые были выполнены вне очереди, выполняются повторно (они обращаются к системе памяти и второй раз считывают значение со своего адреса), когда достигают точки выхода из эксплуатации. Поскольку загрузка теперь является удаляемой инструкцией, она не зависит ни от одной инструкции, которая все еще находится в процессе выполнения; все хранилища перед ним зафиксировали свои значения в системе памяти, поэтому любое значение, прочитанное из системы памяти, гарантированно будет правильным. Значение, считанное из памяти во время повторного выполнения, сравнивается со значением, полученным при первом выполнении загрузки. Если значения совпадают, исходное значение было правильным и нарушений не произошло. Если значение повторного выполнения отличается от исходного значения, произошло нарушение RAW и конвейер необходимо очистить, поскольку инструкции, зависящие от нагрузки, использовали неправильное значение.
Этот метод концептуально проще, чем поиск в очереди загрузки, и исключает использование второго CAM и его энергоемкого поиска (очередь загрузки теперь может быть простой очередью FIFO). Поскольку нагрузка должна повторно получить доступ к системе памяти непосредственно перед выходом из строя, доступ должен быть очень быстрым, поэтому эта схема опирается на быстрый кэш. Однако независимо от того, насколько быстр кэш, второй доступ к системе памяти для каждой инструкции загрузки, находящейся вне порядка, увеличивает задержку вывода инструкций и увеличивает общее количество обращений к кэшу, которые должен выполнить процессор. Дополнительный доступ к кэшу во время вывода из эксплуатации может быть обеспечен путем повторного использования существующего порта кэша; однако это создает конкуренцию за ресурсы порта с другими загрузками и хранилищами в процессоре, пытающимися выполниться, и, таким образом, может привести к снижению производительности. В качестве альтернативы можно добавить дополнительный порт кэша только для устранения неоднозначности нагрузки, но это увеличивает сложность, мощность и площадь кэша. Некоторые недавние работы (Roth 2005) показали способы предотвращения повторного выполнения многих загрузок, если известно, что никакого нарушения зависимости RAW не могло произойти; такой метод поможет или устранит такие задержки и конфликты за ресурсы.
Незначительное преимущество этой схемы (по сравнению с поиском в очереди загрузки) заключается в том, что она не помечает нарушение зависимости RAW и не запускает очистку конвейера , если хранилище, которое могло бы вызвать нарушение зависимости RAW (адрес хранилища соответствует текущему адресу). адрес загрузки) имеет значение данных, которое соответствует значению данных, уже находящемуся в кэше. В схеме поиска в очереди загрузки необходимо добавить дополнительное сравнение данных в аппаратное обеспечение поиска в очереди загрузки, чтобы предотвратить такую очистку конвейера.
Процессоры, которые полностью поддерживают внеочередное выполнение операций загрузки и сохранения, должны иметь возможность обнаруживать нарушения зависимости RAW при их возникновении. Однако многие процессоры избегают этой проблемы, заставляя все загрузки и сохранения выполняться по порядку или поддерживая только ограниченную форму выполнения загрузки/сохранения вне порядка. Этот подход обеспечивает более низкую производительность по сравнению с поддержкой полной загрузки/сохранения вне очереди, но может значительно снизить сложность исполнительного ядра и кэшей.
Первый вариант, обеспечивающий порядок загрузки и хранения, позволяет избежать зависимостей RAW, поскольку нет возможности выполнения загрузки до хранилища ее производителя и получения неверных данных. Другая возможность — эффективно разбить загрузку и сохранение на две операции: генерацию адреса и доступ к кэшу. С помощью этих двух отдельных, но связанных операций ЦП может разрешить загрузкам и сохранениям доступ к системе памяти только после того, как все предыдущие загрузки и сохранения имеют свои адреса, сгенерированные и буферизованные в LSQ. После генерации адреса больше не существует неоднозначных зависимостей, поскольку все адреса известны, и поэтому зависимые загрузки не будут выполняться до тех пор, пока не будут завершены соответствующие сохранения. Эта схема по-прежнему допускает некоторую «неупорядоченность» — операции генерации адресов для любых текущих загрузок и сохранений могут выполняться вне очереди, а после того, как адреса сгенерированы, доступ к кешу для каждой загрузки или сохранения может выполняться вне порядка. происходить в любом порядке, который соответствует (теперь известным) истинным зависимостям.
Процессоры, которые полностью поддерживают выполнение загрузки/сохранения вне порядка, могут использовать дополнительный связанный метод, называемый предсказанием зависимости памяти , чтобы попытаться предсказать истинные зависимости между загрузкой и сохранением до того, как станут известны их адреса. Используя этот метод, процессор может предотвратить выполнение нагрузок, которые, по прогнозам, зависят от текущего хранилища, до завершения этого сохранения, избегая нарушения зависимости RAW и, таким образом, избегая очистки конвейера и связанного с этим снижения производительности. Дополнительные сведения см. в статье о прогнозировании зависимости памяти.