сумматор Когге – Стоуна
В вычислительной технике сумматор Когге-Стоуна ( KSA или KS ) представляет собой параллельную префиксную форму переноса упреждающего сумматора . Другие сумматоры параллельных префиксов (PPA) включают сумматор Брента-Кунга (BKA), [1] сумматор Хана - Карлсона (HCA), [2] [3] и самый быстрый из известных вариантов, сумматор связующего дерева Линча-Шварцлендера (STA ). [4] [5]
Сумматор Когге-Стоуна требует больше места для реализации, чем сумматор Брента-Кунга, но имеет меньшее разветвление на каждом этапе, что повышает производительность для типичных технологических узлов CMOS. Однако перегруженность проводки часто является проблемой для сумматоров Когге-Стоуна. Конструкция Линча - Шварцландера меньше, имеет меньшее разветвление и не страдает от перегрузки проводки; однако для использования узел процесса должен поддерживать реализации цепочки переноса Manchester . Общая проблема оптимизации параллельных сумматоров префиксов идентична задаче оптимизации многоуровневого сумматора переменного размера блока с пропуском переноса , решение которой можно найти в диссертации Томаса Линча 1996 года [5] .
Пример 4-битного сумматора Когге-Стоуна показан на схеме. Каждый вертикальный этап создает биты «распространения» и «генерации», как показано. Кульминационные биты генерации ( переносы ) создаются на последнем этапе (по вертикали), и эти биты подвергаются операции XOR с начальным распространением после ввода (красные прямоугольники) для получения битов суммы. Например, первый (наименее значащий) бит суммы вычисляется путем XOR распространения в крайнем правом красном поле («1») с переносом («0»), в результате чего получается «1». Второй бит вычисляется путем XOR распространения во втором поле справа («0») с C0 («0»), в результате чего получается «0».
Концепция сумматора Когге-Стоуна была разработана Питером М. Когге и Гарольдом С. Стоуном , которые опубликовали ее в основополагающей статье 1973 года под названием «Параллельный алгоритм для эффективного решения общего класса рекуррентных уравнений» . [6]
Усовершенствования исходной реализации включают увеличение основания и разреженности сумматора. Основание сумматора относится к тому, сколько результатов предыдущего уровня вычислений используется для создания следующего. Первоначальная реализация использует основание-2, хотя можно создать основание-4 и выше. Это увеличивает мощность и задержку каждого каскада, но уменьшает количество требуемых каскадов. В так называемом разреженном сумматоре Когге–Стоуна ( СКА ) разреженностьсумматора относится к тому, сколько битов переноса генерируется деревом переносов. Генерация каждого бита переноса называется разреженностью-1, генерация каждого другого — разреженностью-2, а каждый четвертый — разреженностью-4. Полученные переносы затем используются в качестве входных сигналов переноса для гораздо более коротких сумматоров пульсаций переноса или какой-либо другой конструкции сумматора, которая генерирует окончательные биты суммы. Увеличение разреженности уменьшает общее количество необходимых вычислений и может уменьшить количество перегрузок маршрутизации.
Выше приведен пример сумматора Когге-Стоуна с разреженностью-4. Элементы, исключенные из-за разреженности, отмечены прозрачностью. Как показано, мощность и область генерации переноса значительно улучшаются, а перегрузка маршрутизации существенно снижается. Каждый сгенерированный перенос подается на мультиплексор для сумматора выбора переноса или переноса сумматора пульсирующего переноса.
