В проектировании ЦП использование декодера с суммарной адресацией (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 будет следующей:
строка слова[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 по каждой линии декодера, и каждая линия декодера реализовала:
строка слов[L] = (R+O)==L
(Р+О)==Л <=> Р+ОЛ==0 <=> Р+О+~Л+1==0 <=> Р+О+~Л==-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 будет рассеиваться больше мощности, чем при выборке из одного полноразмерного банка, поскольку это приводит к большему количеству переключений в усилителях считывания и логике управления данными.
Ссылаясь на соседнюю диаграмму, четный банк выберет строку 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..10I[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..10I[13:3] = Le => R[13:3] + O[13:3] + ~Le = 11..11
Р 13 ... Р 6 Р 5 Р 4 Р 3 О 13 ... О 6 О 5 О 4 О 3 Л 13 ... Л 6 Л 5 Л 4 Л 3-------------------------- С 13 ... С 6 С 5 С 4 С 3 С 14 С 13 ... С 6 С 5 С 4
Прежде чем устранять избыточность между строками, просмотрите:
Каждая строка каждого декодера для каждого из двух банков реализует набор полных сумматоров, которые сокращают три числа для сложения (R[13:3], O[13:3] и L) до двух чисел (S[14:4] и C[13:3]). LSB (==S[3]) отбрасывается. Вынос (==C[14]) также отбрасывается. Строка совпадает, если S[13:4] == ~C[13:4], что равно &( xor(S[13:4], C[13:4])).
Можно частично специализировать полные сумматоры для 2-входовых AND, OR, XOR и XNOR, поскольку вход L является постоянным. Результирующие выражения являются общими для всех линий декодера и могут быть собраны внизу.
S 0;i = S(R i , O i , 0) = R i xor O i S 1;i = S(R i , O i , 1) = R i xnor O i C 0;i+1 = C(R i , O i , 0) = R i и O i C 1;i+1 = C(R i , O i , 1) = R i или O i .
В каждой позиции цифры существует только два возможных S i , два возможных C i и четыре возможных XOR между ними:
L i =0 и L i-1 =0: X 0;0;i = S 0;i xor C 0;i = R i xor O i xor (R i-1 и O i-1 )L i =0 и L i-1 =1: X 0;1;i = S 0;i xor C 1;i = R i xor O i xor (R i-1 или O i-1 )L i =1 и L i-1 =0: X 1;0;i = S 1;i xor C 0;i = R i xnor O i xor (R i-1 и O i-1 ) = !X 0;0;i L i =1 и L i-1 =1: X 1;1;i = S 1;i xor C 1;i = R i xnor O i xor (R i-1 или O i-1 ) = !X 0;1;i
Один возможный декодер для примера мог бы вычислить эти четыре выражения для каждого из битов 4..13 и направить все 40 проводов вверх по декодеру. Каждая линия декодера выбирала бы один из четырех проводов для каждого бита и состояла бы из 10-входового И.
Более простой путь кэширования данных будет иметь сумматор, за которым следует традиционный декодер. Для нашего примера подсистемы кэширования критическим путем будет 14-битный сумматор, производящий истинные и дополнительные значения, за которым следует 11-битный вентиль И для каждой строки декодера.
В конструкции с суммарной адресацией последний вентиль И в декодере остается, хотя и имеет ширину 10 бит вместо 11. Сумматор был заменен на логическое выражение с четырьмя входами на каждом бите. Экономия задержки достигается за счет разницы в скорости между сумматором и этим выражением с четырьмя входами, экономия, возможно, трех простых вентилей КМОП .
Если читатель считает, что это был непомерный объем головоломной работы для улучшения трех вентилей в многоцикловом критическом пути, то он лучше оценит уровень оптимизации современных процессоров.
Многие конструкции декодеров избегают высоко -входных вентилей И в самой линии декодирования, используя стадию предварительного декодирования. Например, 11-битный декодер может быть предварительно декодирован в три группы по 4, 4 и 3 бита каждая. Каждая 3-битная группа будет управлять 8 проводами вверх по основному массиву декодирования, каждая 4-битная группа будет управлять 16 проводами. Затем линия декодирования становится 3-входным вентилем И. Такая реорганизация может сэкономить значительную площадь реализации и некоторую мощность.
Эту же реорганизацию можно применить к декодеру с адресацией суммы. Каждый бит в непреддекодированной формулировке выше можно рассматривать как локальное двухбитное сложение. С преддекодированием каждая преддекодированная группа является локальным трех-, четырех- или даже пятибитным сложением, причем преддекодированные группы перекрываются на один бит.
Предварительное декодирование обычно увеличивает количество проводов, проходящих через декодер, а декодеры с суммарной адресацией обычно имеют примерно в два раза больше проводов, чем эквивалентный простой декодер. Эти провода могут быть ограничивающим фактором для количества возможного предварительного декодирования.
Патент США 5,754,819 , 19 мая 1998 г., Метод и структура индексации памяти с малой задержкой . Изобретатели: Линч; Уильям Л. (Пало-Альто, Калифорния), Лаутербах; Гари Р. (Лос-Альтос, Калифорния); Правообладатель: Sun Microsystems, Inc. (Маунтин-Вью, Калифорния), Подано: 28 июля 1994 г.
Оценка условий A + B = K без распространения переноса (1992) Хорди Кортаделла, Хосе М. Льяберия IEEE Transactions on Computers , [1] [2]
Патент США 5,619,664, Процессор с архитектурой для улучшенной конвейеризации арифметических инструкций путем пересылки избыточных промежуточных форм данных , выдан 18 апреля 1997 г., Изобретатель: Glew; Andrew F. (Хиллсборо, Орегон); Правообладатель: Intel Corporation (Санта-Клара, Калифорния), Заявка №: 08/402,322, Подан: 10 марта 1995 г.