Прогнозирование зависимости от памяти - Memory dependence prediction

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

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

В общем, прогнозирование зависимости от памяти предсказывает, являются ли две операции с памятью зависимыми, то есть взаимодействуют ли они, обращаясь к одной и той же области памяти. Помимо использования прогнозирования зависимости от памяти для загрузки (RAW или истинное) для неупорядоченного планирования загрузок и сохранений, были предложены другие приложения для прогнозирования зависимости от памяти. См. Например.^[1]

Прогнозирование зависимости от памяти - это оптимизация поверх предположение о зависимости от памяти. Семантика последовательного выполнения подразумевает, что операции сохранения и загрузки выполняются в порядке, заданном программой. Однако, как и в случае выполнения других инструкций вне очереди, может оказаться возможным выполнить две операции с памятью в порядке, отличном от того, который подразумевается программой. Это возможно, когда две операции независимы. В предположении зависимости от памяти загрузке можно разрешить выполнение до предшествующего ей хранилища. Спекуляция успешна, когда загрузка не зависит от хранилища, то есть когда две инструкции обращаются к разным ячейкам памяти. Спекуляция терпит неудачу, когда загрузка зависит от хранилища, то есть когда два доступа перекрываются в памяти. В первых, современных нестандартных конструкциях, спекуляция с памятью не использовалась, поскольку ее преимущества были ограничены. Если объем внепланового выполнения увеличился на несколько десятков инструкций, использовались наивные предположения о зависимости от памяти. В предположение о зависимости наивной памяти,^[2] загрузке разрешено обходить любой предыдущий магазин. Как и в случае с любой другой формой спекуляции, важно сопоставить преимущества правильных спекуляций с штрафом, уплаченным за неправильные спекуляции. По мере того как объем внепланового выполнения увеличивается до нескольких десятков инструкций, преимущества наивной спекуляции в производительности уменьшаются. Чтобы сохранить преимущества агрессивных предположений о зависимости от памяти, избегая при этом затрат на неправильные предположения, было предложено несколько предикторов.

Селективное предсказание зависимости от памяти^[2][3] останавливает определенные нагрузки до тех пор, пока не будет уверенности, что нарушения не произойдет. Он не предсказывает явно зависимости. Этот предсказатель может задерживать загрузки дольше, чем необходимо, и, следовательно, приводить к неоптимальной производительности. На самом деле, в некоторых случаях он работает хуже, чем наивно спекулировать всеми нагрузками как можно раньше. Это потому, что часто быстрее ошибиться и восстановить, чем ждать, пока все предыдущие хранилища выполнятся. Точное предсказание зависимости от памяти было разработано в Университете Висконсина-Мэдисона. Конкретно, Динамическое предположение и синхронизация^[2][3] задерживает загрузку только до тех пор, пока это необходимо, прогнозируя точное хранилище, которого должна ждать загрузка. Этот предсказатель предсказывает точные зависимости (пара накоплений и нагрузок). В предиктор синонимов^[1] группирует вместе все зависимости, которые имеют общую инструкцию загрузки или сохранения. В магазинные наборы^[4] predictor эффективно представляет несколько потенциальных зависимостей, группируя вместе все возможные хранилища, от которых может зависеть нагрузка. В барьер магазина^[5] predictor рассматривает определенные инструкции магазина как препятствия. То есть всем последующим операциям загрузки или сохранения не разрешается обходить конкретное хранилище. Предиктор барьера хранилища не предсказывает явно зависимости. Этот предсказатель может без необходимости задерживать последующие, но независимые загрузки. Прогнозирование зависимости от памяти имеет и другие приложения, помимо планирования загрузки и хранения. Например, спекулятивная маскировка памяти^[1] и умозрительный обход памяти^[1] используйте прогнозирование зависимости от памяти, чтобы упростить передачу значений через память.

Аналогия с предсказанием ветвления

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

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

Смотрите также

• Параллелизм на уровне памяти
• Устранение неоднозначности в памяти

Рекомендации

1. Moshovos, A .; Сохи, Г. С. (1997). «Оптимизация межоперационной связи с памятью через прогнозирование зависимости данных». Материалы 30-го ежегодного международного симпозиума по микроархитектуре. МИКРО '97. С. 235–245. Дои:10.1109 / MICRO.1997.645814.
2. Мошовос, Андреас; Breach, Scott E .; Виджайкумар, Т. Н .; Сохи, Гуриндар С. (1997). «Динамическое предположение и синхронизация зависимостей данных». Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре. ISCA '97. С. 181–193. Дои:10.1145/264107.264189. Также в виде технического отчета, Департамент компьютерных наук, Университет Висконсин-Мэдисон, март 1996 г.
3. Прогнозирование зависимости от памяти, Мошовос, доктор философии. Диссертация, факультет компьютерных наук, Университет Висконсин-Мэдисон, декабрь 1998 г.
4. Chrysos, G. Z .; Эмер, Дж. С. (1998). «Прогнозирование зависимости от памяти с использованием наборов магазинов». Материалы 25-го ежегодного международного симпозиума по компьютерной архитектуре. ISCA '98. С. 142–153. Дои:10.1109 / ISCA.1998.694770.
5. Устройство для динамического управления неупорядоченным выполнением инструкций загрузки-сохранения в процессоре, способном отправлять, выдавать и выполнять несколько инструкций за один цикл процессора, Hesson, LeBlanc and Ciavaglia, IBM, Патент США 5615350, март 1997 г.