Суммарный декодер - Sum-addressed decoder

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: «Суммарный декодер»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июнь 2019) (Узнайте, как и когда удалить этот шаблон сообщения)

В Дизайн процессора, использование суммированный декодер (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 по каждой строке декодера, и каждая строка декодера реализована:

строка слов [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 будет рассеивать больше энергии, чем выборка из одного полноразмерного банка, так как это вызывает больше переключений в усилителях считывания и логике управления данными.

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

Ссылаясь на соседнюю диаграмму, четный банк получит строку 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    L13 ... L6  L5  L4  L3-------------------------- S13 ... S6  S5  S4  S3C14 C13 ... С6  C5  C4

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

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

Можно частично специализировать полные сумматоры на 2 входа И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ и ИСКЛЮЧИТЕЛЬНОЕ ИЛИ, поскольку вход L постоянен. Полученные выражения являются общими для всех строк декодера и могут быть собраны внизу.

S0; я  = S (Rя, Oя, 0) = Rя xor OяS1; я  = S (Rя, Oя, 1) = Rя xnor OяC0; я + 1 = C (Rя, Oя, 0) = Rя и OяC1; я + 1 = C (Rя, Oя, 1) = Rя или Oя.

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

Lя= 0 и Lя-1= 0: X0; 0; я = S0; я xor C0; я = Rя xor Oя xor (Rя-1 и Oя-1) Lя= 0 и Lя-1= 1: X0; 1; я = S0; я xor C1; я = Rя xor Oя xor (Rя-1 или Oя-1) Lя= 1 и Lя-1= 0: X1; 0; я = S1; я xor C0; я = Rя xnor Oя xor (Rя-1 и Oя-1) =! X0; 0; яLя= 1 и Lя-1= 1: X1; 1; я = S1; я xor C1; я = Rя xnor Oя xor (Rя-1 или Oя-1) =! X0; 1; я

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

Что было спасено?

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

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

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

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

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

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

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

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

• У Пола Демона есть объяснение кешей с адресной суммой в реальных технологиях статья.
• Heald et al.^[1] есть статья в ISSCC 1998, в которой объясняется, что может быть исходным кешем с адресной суммой в Ultrasparc III.
• Суммарно-адресная память описана в

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

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

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

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

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