В вычислениях , то Kogge-камень сумматор ( KSA или КС ) является параллельным формой префикса переносов вперед сумматором . Другие сумматоры параллельного префикса (PPA) включают Брент-кунг сумматор (BKA), [1] Хан-Карлсон сумматор (ГЛК), [2] [3] , и самые быстрые из известных вариации, то Линч-Swartzlander связующего дерева сумматора (СТО ). [4] [5]
Kogge-камень сумматор занимает больше площади для реализации , чем сумматор Брент-Kung, но имеет более низкий вентилятор-аут на каждой стадии, что повышает производительность для типичных КМОП обработки узлов. Однако перегрузка проводки часто является проблемой для сумматоров Когге – Стоуна. Конструкция Lynch-Swartzlander меньше, имеет более низкую веерной из , и не страдает от электрической перегрузки; однако, чтобы его можно было использовать, узел процесса должен поддерживать реализации манчестерской цепи переноса . Общая проблема оптимизации параллельных сумматоров префиксов идентична задаче оптимизации многоуровневого сумматора с переменным размером блока и пропуску переноса , решение которой найдено в диссертации Томаса Линча 1996 года [5].
Пример 4-битного сумматора Когге – Стоуна показан на схеме. Каждая вертикальная ступень производит биты «распространения» и «генерации», как показано. Кульминационные биты генерации ( переносы ) производятся на последнем этапе (по вертикали), и эти биты являются XOR 'd с начальным распространением после ввода (красные прямоугольники) для создания битов суммы. Например, первый (наименее значимый) бит суммы вычисляется путем XOR распространения в крайнем правом красном поле («1») с переносом («0»), получая «1». Второй бит вычисляется путем XOR распространения во втором прямоугольнике справа («0») с C0 («0»), создавая «0».
Концепция сумматора Когге – Стоуна была разработана Питером М. Когге и Гарольдом С. Стоуном , которые опубликовали ее в основополагающей статье 1973 года под названием «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений» . [6]
Улучшения
Усовершенствования исходной реализации включают увеличение числа оснований системы счисления и разреженности сумматора. Radix сумматора относится к тому, как много результатов по сравнению с предыдущим уровнем вычисления используются для генерации следующего. В исходной реализации используется основание radix-2, хотя возможно создание radix-4 и выше. Это увеличивает мощность и задержку каждой ступени, но уменьшает количество требуемых ступеней. В так называемом редком сумматоре Когге – Стоуна ( SKA ) разреженность сумматора указывает на то, сколько битов переноса генерируется деревом переноса. Генерация каждого бита переноса называется разреженным-1, тогда как генерация каждого другого - разреженным-2, а каждый четвертый - разреженным-4. Полученные в результате переносы затем используются в качестве вводов переноса для гораздо более коротких сумматоров переноса пульсаций или какой-либо другой конструкции сумматора, которая генерирует биты окончательной суммы. Увеличение разреженности снижает общее количество необходимых вычислений и может уменьшить перегрузку маршрутизации.
Выше приведен пример сумматора Когге – Стоуна с разреженностью-4. Элементы, удаленные из-за разреженности, показаны отмеченными прозрачностью. Как показано, мощность и площадь генерации переноса значительно улучшаются, а перегрузка маршрутизации существенно снижается. Каждый сгенерированный перенос подается на мультиплексор для сумматора выбора переноса или переноса сумматора с пульсационным переносом.
Расширение
Этот пример является перспективным - в 4-битном сумматоре, подобном показанному на вводном изображении этой статьи, есть 5 выходов. Ниже расширение:
S0 = (A0 XOR B0) XOR CinS1 = (A1 XOR B1) ИСКЛЮЧАЮЩЕЕ ИЛИ ((A0 И B0) ИЛИ ((A0 XOR B0) AND Cin))S2 = (A2, исключающее ИЛИ B2) ИСКЛЮЧАЮЩЕЕ ИЛИ ((A1 И B1) ИЛИ ((A1 XOR B1) AND (A0 AND B0)) ИЛИ ((A1 XOR B1) AND (A0 XOR B0) AND Cin))S3 = (A3 XOR B3) ИСКЛЮЧАЮЩЕЕ ИЛИ ((A2 И B2) ИЛИ ((A2 XOR B2) AND (A1 AND B1)) ИЛИ ((A2 XOR B2) AND (A1 XOR B1) AND (A0 AND B0)) ИЛИ ((A2 XOR B2) AND (A1 XOR B1) AND (A0 XOR B0) AND Cin))Cout = (A3 И B3) ИЛИ ((A3 XOR B3) AND (A2 AND B2)) ИЛИ ((A3 XOR B3) AND (A2 XOR B2) AND (A1 AND B1)) ИЛИ ((A3 XOR B3) AND (A2 XOR B2) AND (A1 XOR B1) AND (A0 AND B0)) ИЛИ ((A3 XOR B3) AND (A2 XOR B2) AND (A1 XOR B1) AND (A0 XOR B0) AND Cin)
Рекомендации
- ^ Брент, Ричард Пирс ; Кунг, Сян Дэ (март 1982 г.). «Обычный макет для параллельных сумматоров» . Транзакции IEEE на компьютерах . С-31 (3): 260–264. DOI : 10.1109 / TC.1982.1675982 . ISSN 0018-9340 .
- ^ Хан, Такдон; Карлсон, Дэвид А .; Левитан, Стивен П. (октябрь 1982 г.). «Проектирование СБИС высокоскоростной схемы сложения малой площади» . Труды 1981 Международная конференция IEEE по компьютерному дизайну: СБИС в компьютерах и процессорах . IEEE : 418–422. ISBN 0-81860802-1.
- ^ Хан, Такдон; Карлсон, Дэвид А. (октябрь 1987 г.). "Быстрые СБИС-сумматоры с эффективностью по площади" Материалы 8-го симпозиума по компьютерной арифметике . IEEE : 49–56.
- ^ Линч, Томас Уокер; Шварцлендер-младший, Эрл Э. (август 1992 г.). «Остовное дерево переносит сумматор вперед». Транзакции IEEE на компьютерах . 41 (8): 931–939. DOI : 10.1109 / 12.156535 .
- ^ а б Линч, Томас Уокер (май 1996). «Бинарные сумматоры» (дипломная работа). Техасский университет . Архивировано (PDF) из оригинала на 2018-04-14 . Проверено 14 апреля 2018 .
- ^ Когге, Питер Майкл ; Стоун, Гарольд С. (август 1973 г.). «Параллельный алгоритм эффективного решения общего класса рекуррентных уравнений». Транзакции IEEE на компьютерах . С-22 (8): 786–793. DOI : 10.1109 / TC.1973.5009159 .
дальнейшее чтение
- Зейдел, Барт Р. (2006). «Энергетические характеристики КМОП сумматоров». In Oklobdzija, Vojin G .; Кришнамурт, Рам К. (ред.). Высокопроизводительный энергоэффективный микропроцессор . Серия по интегральным схемам и системам. Дордрехт, Нидерланды: Springer . С. 147–169. DOI : 10.1007 / 978-0-387-34047-0_6 . ISBN 0-387-28594-6.