Логические схемы на примере двоичного сумматора

64-битный сумматор реализуется как два 32-битных - один для младшей 32-битной секции числа, а другой - для старшей. Младшая секция, представляющая собой обычный 32-битный сумматор, складывает биты $a\_0,\; a\_1,\; \backslash dots,\; a\_\{31\}+b\_0,\; b\_1,\; \backslash dots,\; b\_\{31\}$ и выдаёт биты суммы $s\_0,\; s\_1,\; \backslash dots,\; s\_\{31\}$, а также бит переноса $c\_\{31\; \backslash to\; 32\}$. Старшая секция складывает с учётом переноса $c\_\{31\; \backslash to\; 32\}$ старшие биты $a\_\{32\},a\_\{33\},\backslash dots,\; a\_\{63\}+b\_\{32\},\; b\_\{33\},\; \backslash dots,\; b\_\{63\}$. Но чтобы не ждать переноса из младшей секции, старшая организована следующим образом: она состоит из двух 32-битных сумматоров, получающих на вход одни и те же слагаемые $a\_\{32\},a\_\{33\},\backslash dots,\; a\_\{63\}$ и $b\_\{32,\; b\_\{33\},\backslash dots,b\_\{63\}$, и при этом один из сумматоров всегда получает бит переноса $c\_\{31\; \backslash to\; 32\}=0$, а другой - $c\_\{31\; \backslash to\; 32\}=1$. Сумматоры старшей секции "запускаются" одновременно друг с другом и с сумматором младшей, и одновременно с ней заканчивают работу. К моменту окончания работы этих трёх 32-битных сумматоров (одного "младшего" и двух "старших") становится известно действительное значение переноса $c\_\{31\; \backslash to\; 32\}$, и в итоговую сумму попадают результирующие биты лишь одного из "старших" сумматоров - того, который работал в условиях верного предположения значения входящего переноса $c\_\{31\; \backslash to\; 32\}$.

Описанный подход можно описать словами: "Сделай всё, что можешь, как можно скорее, часть из этого пригодится, остальное выбросим". Такая стратегия вычислений называется спекулятивной. Спекулятивность усложняет сумматор в нашем примере: она приводит к тому, что, фактически, результаты 1/3 вычислений (одного из трёх 32-разрядный сумматоров) выполняются впустую. Тем не менее она популярна, так как позволяет ускорить работу сумматора почти вдвое. Иногда сумматоры делят и на бо?льшее число секций.

Арифметикло-логическое устройство

Сумматор, мультипликатор (логическая схема для умножения двоичных чисел), а также модули для выполнения логических операций и некоторые другие логические схемы составляют арифметико-логическое устройство (АЛУ), которое является одним из основных блоков процессора.

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

В зависимости от значения на управляющем входе (4) ко входам и выходам (1-3) подключается та или иная логическая схема, входящая в состав АЛУ:

Сделаем небольшой обзор реализаций упомянуты арифметико-логических операций.

Сложение выполняется при помощи сумматора. Вычитание выполняется также сумматором, поскольку очевидным образом выражается через сложение, как мы обсуждали в предыдущих лекциях.

Побитовые логические операции - это операции, которые выполняются побитово, например, побитовое отрицание двоичного числа выполняет отрицание каждого его бита, побитовая операция "и" двух чисел выполняет "и" для каждой пары соответствующих битов и т.д. Таким образом, для побитовое отрицание, получая на вход 32-битовое двоичное число $a\_0,\; a\_1,\; \backslash dots,\; a\_\{31\}$, выдает следующий результат: $\backslash neg\; a\_0,\; \backslash neg\; a\_1,\; \backslash dots,\; \backslash neg\; a\_\{31\}$. Побитовое "и" (операция & в языке С), получая на вход два 32-битовых числа получая на вход 32-битовое двоичное число $a\_0,\; a\_1,\; \backslash dots,\; a\_\{31\}$ и $b\_0,\; b\_1,\; \backslash dots,\; b\_\{31\}$, выдаёт число $a\_0\; \backslash wedge\; b\_0,\; a\_1\; \backslash wedge\; b\_1,\; \backslash dots,\; a\_\{31\}\; \backslash wedge\; b\_\{31\}$. Аналогично действуют и другие побитовые операции - "или", "исключающее или" и т.д. Поскольку, в отличие от сумматора, все биты обрабатываются независимо, проблем с задержкой переноса не возникает, и побитовые операции всегда выполняются за один такт.

Сдвиг двоичного числа - это операция, смещающая разряды (биты) числа от младшего к старшему, дописывая справа нуль и теряя старший бит (левый сдвиг, обозначается "<<" в языке C) или от старшего к младшему, дописывая слева ноль и теряя младший бит (правый сдвиг, ">>" в языке C). Для того, чтобы сдвинуть аргумент a на 1 бит влево АЛУ присоединяет выходные биты к соответствующим входным. Сдвиг числа влево на 1 бит эквивалентен умножению на 2, но выполняется намного быстрее. Аналогично работает сдвиг вправо, и он эквивалентен делению на 2 нацело. Поскольку при сдвигах АЛУ всего лишь соединяет выходы с соответствующими входами, сдвиги, так же, как и побитовые операции, выполняются за один такт. Отметим, что современные AЛУ за один такт умеют сдвигать числа и на произвольное количество битов, а также выполнять некоторые другие разновидности сдвигающих биты операций.

Умножение выполняется мультипликатором. Если мы вспомним алгоритм умножения "в столбик", то увидим, что он состоит из сдвигов, сложений и умножений на одноразрядное число. В случае двоичной системы умножение на одноразрядное число реализуется тривиально: поскольку одноразрядное число может быть либо 0, либо 1, то и произведение будет равно или другому множителю, или нулю. Таким образом, мультипликатор также можно изготовить в виде логической схемы. Но она получится весьма громоздкой: в ней будет уже очень много вентилей и связей между ними. Поэтому в некоторых АЛУ операция умножения выполняется не единой логической схемой, а как последовательность микроопераций (про микрооперации мы расскажем в следующих разделах) с запоминанием промежуточных результатов в специальных внутренних регистрах, используемых только в АЛУ. Чтобы лучше представить себе работу такого АЛУ, попробуйте написать программу на любом языке программирования, которая умножает два числа, пользуясь для этого лишь операциями сдвига и сложения. По аналогии с умножением, деление также можно реализовать при помощи логической схемы, но она получится ещё сложнее, поэтому деление также часто реализуется в виде последовательности микроопераций.

Отметим, что программная реализация умножения, которую мы предлагаем выполнить читателям - отнюдь не просто "учебное" упражнение. АЛУ некоторых простых процессоров, например, Intel 8080, позволяло выполнять лишь сложение, вычитание, сдвиг и побитовые операции, а умножение для этих процессоров действительно приходилось реализовывать уже программистам.

Вопросы

Литература