Предотвращение конфликтов между командами при конвейеризации команд

Аппаратная оптимизация использования регистров в RISC-процессорах ориентирована на две проблемы.

Регистры в RISC-процессорах

Отличительная черта RISC-архитектуры - большое число регистров общего назначения, что объясняется стремлением свести все пересылки к типу «регистр-регистр». Но увеличение числа РОН способно дать эффект лишь при разумном их использовании. Оптимизация использования регистров в RISC-процессорах обеспечивается как программными, так и аппаратными средствами.

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

Задача оптимизации состоит в определении того, каким переменным в данной точке программы выгоднее всего выделить физические регистры. Наиболее распространенный метод, применяемый для этой цели, известен как раскраска графа.

В общем случае метод формулируется следующим образом. Имеется граф, состоящий из узлов и ребер. Необходимо раскрасить узлы так, чтобы соседние узлы имели разный цвет и чтобы при этом общее количество привлеченных цветов было минимальным. В нашем случае роль узлов выполняют виртуальные регистры. Если два виртуальных регистра одновременно присутствуют в одном и том же фрагменте программы, они соединяются ребром. Делается попытка раскрасить граф в n цветов, где n — число физических регистров. Если такая попытка не увенчалась успехом, то узлам, которые не удалось раскрасить, вместо физических регистров выделяются ячейки в памяти.

Для этого некоторым регистрам придают специальные качества: такие регистры в состоянии принимать на себя имя любого РОН. Набор регистров, обладающих подобным свойством, называют буфером переименования. Прием оказывается очень удобным при конвейеризации команд и позволяет предотвратить конфликты, когда одна команда хочет воспользоваться регистром, в данный момент занятым другой командой.