Декодер с суммарной адресацией

В конструкции ЦП использование декодера с суммарной адресацией (SAD) или декодера с суммарной адресацией памяти (SAM) является методом уменьшения задержки доступа к кэшу ЦП и расчета адреса (база + смещение). Это достигается за счет объединения операции суммирования адреса с операцией декодирования в кэше SRAM .

Обзор

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

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

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

Остальная часть этой страницы предполагает архитектуру набора команд (ISA) с одним режимом адресации (регистр+смещение), виртуально индексированным кэшем данных и загрузкой расширения знака, которая может иметь переменную ширину. Большинство RISC ISA соответствуют этому описанию. В ISA, таких как Intel x86 , три или четыре входа суммируются для генерации виртуального адреса. Сложение с несколькими входами можно свести к сложению с двумя входами с помощью сумматоров с сохранением переноса, а оставшаяся проблема описана ниже. Таким образом, критическим повторением является сумматор , декодер , линия слов SRAM, битовая линия SRAM, усилитель(и) считывания, мультиплексоры управления байтами и обходные мультиплексоры.

В этом примере с прямым отображением размером 16 КБ предполагается кэш данных , который возвращает значения, выровненные по двойному слову (8 байт). Каждая строка SRAM имеет размер 8 байт, всего 2048 строк, адресуемых Addr[13:3]. Идея SRAM с суммарной адресацией одинаково хорошо применима и для установки ассоциативных кэшей.

суммы: свернуть сумматор и

Декодер SRAM для этого примера имеет 11-битный вход Addr[13:3] и 2048 выходов — строки декодированных слов. В одной строке слов устанавливается высокий уровень в ответ на каждое уникальное значение Addr[13:3].

В простейшей форме декодера каждая из 2048 строк логически представляет собой логический И. элемент 11 бит (назовем их A[13:3] и их дополнения (назовем их B[13:3]) подаются в декодер. Для каждой строки 11 бит или дополнений подаются на логический элемент И с 11 входами. Например, десятичное число 1026 равно 10000000010 двоичному. Функция для строки 1026 будет такой:

wordline[1026] = A[13] & B[12] & B[11] & B[10] & B[9] & B[8] & B[7] & B[6] & B[5] & A[4] & B[3]

И цепочка переноса сумматора, и декодера объединяют информацию со всей ширины индексной части адреса. Объединение информации по всей ширине дважды избыточно. SRAM с суммарной адресацией объединяет информацию только один раз, реализуя сумматор и декодер в одной структуре.

Напомним, что SRAM индексируется по результату сложения. Вызовите слагаемые R (для регистра) и O (для смещения этого регистра). Декодер с суммарной адресацией будет декодировать R+O. Для каждой линии декодера вызовите номер строки L.

Предположим, что наш декодер управлял как R, так и O по каждой линии декодера, и каждая строка декодера реализована:

wordline[L] = (R+O)==L

(R+O)==L <=> R+O-L==0
         <=> R+O+~L+1==0
         <=> R+O+~L==-1==11..1.

Для преобразования R+O+~L в S+C можно использовать набор полных сумматоров (это сложение с сохранением переноса). S+C==11..1 <=> S==~C. В финальном дополнении не будет керри. Обратите внимание: поскольку C представляет собой строку переносов, она сдвигается на один бит вверх, так что R[13:3]+O[13:3]+~L[13:3] == {0,S[13:3] } + {C[14:4],0}

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

Игнорирование младших разрядов: поздний выбор при переносе

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

Если R[13:3] и O[13:3] складываются для получения некоторого индекса I[13:3], то фактический адрес Addr[13:3] равен либо I[13:3], либо I [13:3] + 1, в зависимости от того, генерирует ли R[2:0]+O[2:0] перенос. И I, и I+1 можно получить, если имеется два банка SRAM: один с четными адресами, а другой с нечетными. В четном банке хранятся адреса 000xxx, 010xxx, 100xxx, 110xxx и т. д., а в нечетном банке — адреса 001xxx, 011xxx, 101xxx, 111xxx и т. д. Вынос из R[2:0]+O[2:0] затем может быть использован для выбора четного или нечетного двойного слова, полученного позже.

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

Генерация совпадений

Я[13:3]	даже банк извлекает строку	странный банк извлекает строку
100	100	101
101	110	101
110	110	111

Ссылаясь на соседнюю диаграмму, четный банк получит строку 110, когда I[13:3]==101 или I[13:3]==110. Нечетный банк получит строку 101, когда I[13:3]==100 или I[13:3]==101.

В общем, нечетный банк SRAM должен выбирать строку Lo==2N+1, когда либо I[13:3]==2N, либо I[13:3]==2N+1. Оба условия можно записать так:

I[13:3] = Lo-1 =>  R[13:3] + O[13:3] + ~Lo+1 = 11..11
               =>  R[13:3] + O[13:3] + ~Lo   = 11..10
I[13:3] = Lo   =>  R[13:3] + O[13:3] + ~Lo   = 11..11

Игнорируйте последнюю цифру сравнения: (S+C)[13:4]==11..1

Аналогично, четный банк SRAM извлекает строку Le==2N, когда либо I[13:3]==2N, либо I[13:3]==2N-1. Условия записываются следующим образом и снова игнорируют последнюю цифру сравнения.

I[13:3] = Le-1 =>  R[13:3] + O[13:3] + ~Le = 11..10
I[13:3] = Le   =>  R[13:3] + O[13:3] + ~Le = 11..11

Реализация на уровне ворот

    R13 ... R6  R5  R4  R3
    O13 ... O6  O5  O4  O3
    L13 ... L6  L5  L4  L3
--------------------------
    S13 ... S6  S5  S4  S3
C14 C13 ... C6  C5  C4

Прежде чем свернуть избыточность между строками, просмотрите:

Каждая строка каждого декодера для каждого из двух банков реализует набор полных сумматоров, которые сводят три добавляемых числа (R[13:3], O[13:3] и L) к двум числам (S[14: 4] и С[13:3]). LSB (==S[3]) отбрасывается. Выполнение (==C[14]) также отбрасывается. Строка соответствует, если S[13:4] == ~C[13:4], что равно &( xor(S[13:4], C[13:4])).

Можно частично специализировать полные сумматоры на 2-входовые И, ИЛИ, исключающее ИЛИ и исключающее ИЛИ, поскольку вход L является постоянным. Полученные выражения являются общими для всех строк декодера и могут быть собраны внизу.

S0;i   = S(Ri, Oi, 0) = Ri xor Oi
S1;i   = S(Ri, Oi, 1) = Ri xnor Oi
C0;i+1 = C(Ri, Oi, 0) = Ri and Oi
C1;i+1 = C(Ri, Oi, 1) = Ri or Oi.

В каждой позиции цифры есть только два возможных S _i , два возможных C _i и четыре возможных XOR между ними:

Li=0 and Li-1=0: X0;0;i = S0;i xor C0;i = Ri xor Oi xor (Ri-1 and Oi-1)
Li=0 and Li-1=1: X0;1;i = S0;i xor C1;i = Ri xor Oi xor (Ri-1 or Oi-1)
Li=1 and Li-1=0: X1;0;i = S1;i xor C0;i = Ri xnor Oi xor (Ri-1 and Oi-1) = !X0;0;i
Li=1 and Li-1=1: X1;1;i = S1;i xor C1;i = Ri xnor Oi xor (Ri-1 or Oi-1)  = !X0;1;i

Один из возможных декодеров для примера может вычислить эти четыре выражения для каждого из битов 4..13 и подать на декодер все 40 проводов. Каждая линия декодера будет выбирать один из четырех проводов для каждого бита и состоять из 10-входового И.

Что удалось сохранить?

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

В конструкции с адресацией суммы последний логический элемент И в декодере остается, хотя его ширина составляет 10 бит вместо 11. Сумматор был заменен логическим выражением с четырьмя входами в каждом бите. Экономия задержки достигается за счет разницы в скорости между сумматором и выражением с четырьмя входами, что позволяет сэкономить, возможно, три простых КМОП- вентиля.

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

Дальнейшие оптимизации: предварительное декодирование

Многие конструкции декодеров позволяют избежать использования логических элементов И с большим входом в самой линии декодирования за счет использования этапа предварительного декодирования. Например, 11-битный декодер может быть предварительно декодирован на три группы по 4, 4 и 3 бита в каждой. Каждая 3-битная группа будет управлять 8 проводами основного массива декодирования, каждая 4-битная группа будет управлять 16 проводами. Линия декодера тогда становится логическим элементом И с 3 входами. Такая реорганизация может сэкономить значительную площадь реализации и некоторую власть.

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

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

Ссылки

• У Пола Демоуна есть объяснение кэшей с суммарной адресацией в статье о реальных технологиях .
• Хилд и др. В ISSCC 1998 есть статья, в которой объясняется, что может быть исходным кэшем с суммарной адресацией в Ultrasparc III.
• Память с суммарной адресацией описана в

Патент США 5,754,819 , 19 мая 1998 г., Метод и структура индексации памяти с малой задержкой . Изобретатели: Линч; Уильям Л. (Пало-Альто, Калифорния), Лаутербах; Гэри Р. (Лос-Альтос, Калифорния); Правопреемник: Sun Microsystems, Inc. (Маунтин-Вью, Калифорния), подано: 28 июля 1994 г.

• По крайней мере, один из изобретателей, упомянутых в патенте, касающемся декодирования адресов без переноса, доверяет следующей публикации:

Оценка условий A + B = K без распространения переноса (1992) Хорди Кортаделла, Хосе М. Ллаберия Транзакции IEEE на компьютерах , [1] [2]

• Следующий патент расширяет эту работу, чтобы использовать избыточную арифметику форм во всем процессоре и таким образом избежать накладных расходов на распространение переноса даже в операциях ALU или когда операция ALU пропускается по адресу памяти:

Патент США 5,619,664, Процессор с архитектурой для улучшенной конвейерной обработки арифметических инструкций путем пересылки избыточных промежуточных форм данных . награжден 18 апреля 1997 г., Изобретатель: Глю; Эндрю Ф. (Хиллсборо, Орегон); Правопреемник: корпорация Intel (Санта-Клара, Калифорния), Прил. №: 08/402,322, Подано: 10 марта 1995 г.