РАЗДЕЛ 2
МЕТОДЫ СТРУКТУРНОГО СИНТЕЗА БЫСТРОДЕЙСТВУЮЩИХ СУММИРУЮЩИХ УСТРОЙСТВ
Известно, что наиболее часто применяемыми операциями в вычислительных системах
являются сложение и умножение как целых чисел, так и чисел с плавающей запятой.
Причем умножение базируется на ряде операций сложения целых чисел. Отсюда
следует, что повышение быстродействия комбинационных сумматоров является
ключевым моментом при решении задачи увеличения производительности
вычислительной системы в целом.
При синтезе многоразрядных многооперандных сумматоров целых чисел используется
алгебра симметрических булевых функций.
Критерием эффективности спроектированных в диссертации арифметических устройств
считается их высокое быстродействие при приемлемых аппаратных затратах.
2.1. Табличные методы проектирования быстродействующих сумматоров целых чисел
Табличные методы широко применяют для реализации схем, где удобно использовать,
например, постоянные запоминающие устройства или программируемые логические
матрицы (ПЛМ). В соответствии с методом таблицы составляют для наиболее
употребляемых функций, и затем заносят их в ПЗУ (ПЛМ). Особенность табличного
метода в том, что таблицы создают для каждой элементарной функции, но
устройства строят для реализации всего списка функций на одной алгоритмической
структуре. Кроме того, устройства, созданные на основе данного метода, в общем
случае жестко специализированы [14].
Табличные методы характеризуются:
а) правилами составления таблиц;
б) способами хранения и использования таблиц.
Значительного повышения быстродействия средств вычислительной техники можно
достичь при организации вычислений с большими массивами данных. В [61]
предложено повышать быстродействие путем организации вычислений на операционных
элементах, построенных на многооперандных структурах. Многооперандный подход
заключается в реализации операции над блоком данных в едином операционном
цикле.
а =1 =1 S
в
с
і2
P
Рис. 2.1. Структура одноразрядного полного сумматора
В качестве примера многооперандной структуры может быть рассмотрено устройство
для суммирования M N-разрядных двоичных чисел [81]. Данное устройство отличает
регулярность структуры, а также то, что оно спроектировано на базе
одноразрядных полных сумматоров (ОПС). Вариант реализации ОПС показан на рис.
2.1, где а, в ѕ слагаемые, с ѕ входной перенос, S ѕ сумма, Р ѕ выходной
перенос. Данный ОПС содержит два элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и один МАЖОРИТАРНЫЙ
элемент.
Число рядов (рангов) r ОПС дерева сумматоров в блоке i-го разряда данного
устройства для суммирования определяется из формулы r = 2(log2(M/4) + 1). То
есть, число рангов в данном устройстве, и, следовательно, и его быстродействие,
непосредственно зависят от количества суммируемых устройством чисел, что
является его недостатком.
Ниже предлагаются табличные методы проектирования быстродействующих M-словных
сумматоров целых N-разрядных чисел (обозначаются MеN) с параллельным переносом
и со сквозным переносом Глассера. Сумматоры типа MеN представляют собой
дальнейшее развитие идей и структур сумматоров двух n-разрядных целых чисел
(см. рис. 1.2) [53].
2.1.1. Табличный метод проектирования сумматора типа MеN с параллельным
переносом на основе таблиц значений разрядных индексов. В соответствии с
методом [37], при синтезе сумматора типа MеN оригинальная таблица значений
разрядных индексов для переносов Рi (i ѕ номер разряда, 2 Ј i Ј N + K; К ѕ
количество дополнительных переносов, К определяется формулой М = 2К+1 - К - 1)
составляется следующим образом [27]. Последовательно перебираются значения
индексов от 0 до М + 1 (до М для i > K) в столбце первого разряда при
фиксированных значениях индексов в старших разрядах. Затем увеличивается на
единицу значение индекса во втором разряде при фиксированных значениях индексов
старших разрядов и снова производится перебор всех возможных значений индексов
в первом разряде, и т.д. до тех пор, пока во втором разряде не будут перебраны
все возможные значения индексов; затем увеличивается на единицу значение
индекса в третьем разряде и производится перебор значений индексов в первом и
втором разрядах в последовательности, описанной ранее. Описанная процедура
выполняется вплоть до заполнения в последнем столбце таблицы для Pi (количество
столбцов равно i - 1, если i Ј N, и равно N в остальных случаях) последнего
значения индекса, равного М. В каждой строке должны быть такие значения
разрядных индексов, что их двоично-взвешенная сумма дает число, в двоичном
эквиваленте которого появляется “1” в i-ом (иногда, кроме того, в (i + 1)-ом)
разряде.
Полученные таблицы обладают некоторой избыточностью и допускают минимизацию
описания схемы сумматора за счет объединения строк, в которых индексы
отличаются только в одном столбце; при этом для СФ с соседними значениями
индексов по данному столбцу возможно склеивание исходных переменных.
Примером таблицы значений разрядных индексов, например, для функции переноса Р4
при М = N = 4 служит таблица 2.1. Здесь 2 - 5; 0 - 5 и т.п. обозначают
перечисления индексов 2, 3, 4, 5; 0, 1, 2, 3, 4, 5; ... В столбцах данной
таблицы помещены индексы СФ, сумма которых по некоторой строке с учетом веса
разряда дает перенос в 4-й разряд. Например, для переноса в четвертый разряд по
первой строке имеем: 2 Ч 21 + 4 Ч 20 = 8 либо 2 Ч 21 + 5 Ч 20 = 9. Аналогично
составлены и остальные строки данной и всех остальных подобных таблиц.
Обозначим Вi = Fi для М + 1 переменных i-го разряда и Di = Fi д
- Киев+380960830922