Микросхема АЛУ 74181, то есть арифметико-логическое устройство, использовалась во многих мини-компьютерах 1970-х годов: она обеспечивала быстрые 4-битные арифметические и логические операции, а несколько таких микросхем можно было объединять для работы со словами большей разрядности, поэтому она стала важной частью многих процессоров. Но если присмотреться к этой микросхеме внимательнее, возникают вопросы. 

Она реализует сложение, вычитание и те булевы функции, которых вы ожидаете, но почему в ней есть несколько странных функций вроде «A плюс (A И НЕ B)»? И если посмотреть на принципиальную схему ниже, почему она выглядит как беспорядочная куча логических элементов, а не как схема, собранная из стандартных полных сумматоров?

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

Микросхема 74181 важна из-за той роли, которую она сыграла в истории мини-компьютеров. До эпохи микропроцессоров процессоры мини-компьютеров собирали из плат с отдельными микросхемами. Одной из ключевых частей процессора было АЛУ, выполнявшее арифметические операции, например сложение и вычитание, а также логические операции: AND, OR, XOR. В ранних мини-компьютерах АЛУ строили из большого числа простых логических элементов.

Но в марте 1970 года Texas Instruments представила микросхему АЛУ 74181, которая поместила полноценное 4-битное АЛУ в одну быструю TTL-микросхему. Эта микросхема поддерживала 32 арифметические и логические функции, а также упреждающий перенос для высокой производительности. Использование 74181 упрощало проектирование процессора мини-компьютера и делало его компактнее, поэтому микросхема применялась во многих мини-компьютерах.

Среди компьютеров, где использовалась 74181, были популярные мини-компьютеры PDP-11 и Xerox Alto, а также мощный «супермини-компьютер» VAX-11/780. 74181 до сих пор используют в ретрокомпьютерных хакерских проектах.^{(примеч.1)}

74181 реализует 4-битное АЛУ с 16 логическими и 16 арифметическими функциями, как показано в техническом описании ниже. Помимо ожидаемых сложения, вычитания и булевых операций, там есть и довольно странные функции, например «(A + B) PLUS AB».

Так как же реализована 74181 и почему в ней есть такие необычные операции? Есть ли в операциях 74181 какая-то логика, или их просто набросали случайным образом? И почему логические и арифметические функции в одной и той же строке таблицы на первый взгляд никак не связаны? Я исследовал микросхему, чтобы разобраться в этих вопросах.

16 булевых логических функций

На самом деле за набором функций 74181 стоит определенная система: логические функции представляют собой все 16 возможных булевых функций f(A,B). Почему их именно 16? Если у вас есть булева функция f(A,B) с однобитными входами, то в ее таблице истинности будет 4 строки. Каждая строка может выдавать либо 0, либо 1. Следовательно, существует 2^4 = 16 возможных функций. Если распространить их на 4-битные значения, то получится ровно 16 логических функций 74181: от тривиальных 0 и 1 до ожидаемых операций вроде A AND B и более искусственных вариантов наподобие NOT A AND B. Эти 16 функций выбираются входами выбора S0-S3.

Арифметические функции

Арифметические операции 74181 представляют собой комбинацию сложения, вычитания, логических операций и странных конструкций вроде «A PLUS AB PLUS 1». Оказывается, за этим набором тоже стоит вполне рациональная система: это просто 16 логических функций, складываемых с A и входящим переносом.^{(примеч.2)} То есть арифметические функции имеют вид: A PLUS f(A,B) PLUS входящий перенос.

Например, если f(A,B)=B, получается обычное сложение: A PLUS B PLUS входящий перенос. Если же f(A,B) = NOT B, получается A PLUS NOT B PLUS входящий перенос, что в логике дополнительного кода превращается в вычитание: A MINUS B MINUS 1 PLUS входящий перенос.

Другие арифметические функции требуют чуть более внимательного разбора. Предположим, что f(A,B) = NOT (A OR B). Тогда каждый бит выражения A PLUS f(A,B) всегда будет равен 1, кроме случая, когда A равно 0, а B равно 1, поэтому результатом суммы станет A OR NOT B. Хотя формально выполняется сложение, результат оказывается логической функцией, поскольку перенос здесь возникнуть не может. Аналогично можно объяснить и остальные странные арифметические функции.^{(примеч.3)}

Таким образом, 16 арифметических функций 74181 появились как следствие объединения операции сложения с одной из 16 булевых функций. И хотя многие из этих функций выглядят странно и, вероятно, бесполезно, у них есть логическое обоснование. (Булевы функции для арифметических операций расположены в другом порядке, чем для логических операций, поэтому на первый взгляд между арифметическими и логическими функциями нет очевидной связи.)

Упреждающий перенос: как выполнять быстрое двоичное сложение

Самый простой, но медленный способ построить сумматор — использовать для каждого бита простой однобитный полный сумматор, где перенос с выхода одного сумматора передается на вход следующего. Это похоже на сложение «в столбик» вручную: например, в десятичной системе при сложении 9999 + 1 приходится последовательно переносить единицу из одного разряда в следующий, а это медленно. Такой «волновой перенос» превращает сложение из параллельной операции в последовательную, что ухудшает производительность процессора.

Чтобы избежать этой проблемы, 74181 сначала вычисляет переносы, а затем складывает все четыре бита параллельно, устраняя задержку, вызванную волновым переносом. На первый взгляд это кажется невозможным: как можно определить наличие переноса еще до выполнения сложения? Ответом является упреждающий перенос.

В механизме упреждающего переноса используются сигналы «Generate» и «Propagate», чтобы определить, будет ли конкретный разряд всегда генерировать перенос или потенциально способен его пропустить дальше. Например, если складываются 0+0+C, где C — входящий перенос, выходной перенос появиться не может независимо от значения C. С другой стороны, при сложении 1+1+C выходной перенос возникнет всегда, независимо от C. Это называется случаем Generate. Наконец, для 0+1+C или 1+0+C выходной перенос появится только при наличии входящего переноса. Это называется случаем Propagate, поскольку входящий перенос «проталкивается» дальше на выход.^{(примеч.4)}

Если объединить все это, то для каждого разряда формируется сигнал G (generate), когда оба бита равны 1, и сигнал P (propagate), если оба бита не равны 0.

Перенос из каждого разряда можно вычислить по сигналам P и G, определяя, какие комбинации способны породить перенос. Например, перенос из бита 0 в бит 1 возникнет, если установлен P₀, то есть перенос либо генерируется, либо распространяется, и при этом существует либо входящий перенос, либо сгенерированный перенос. Таким образом:

C1 = P0 AND (Cin OR G0)

Для переносов старших разрядов количество вариантов растет, и логика становится сложнее. Например, рассмотрим перенос в бит 2. Во-первых, должен быть установлен P₁, чтобы перенос мог выйти из бита 1. Кроме того, перенос либо генерируется самим битом 1, либо передается из бита 0. И наконец, исходный перенос тоже должен откуда-то взяться: либо из входящего переноса, либо он был сгенерирован битом 0 или битом 1. Если объединить все это вместе, получится функция, используемая в 74181:

C2 = P1 AND (G1 OR P0) AND (C0 OR G0 OR G1)

Как видно, логика переноса становится сложнее для старших разрядов, но ключевая идея в том, что каждый перенос можно вычислить по значениям G, P и входящего переноса. Благодаря этому все переносы вычисляются параллельно, еще до выполнения сложения.^{(примеч.5)}

Создание сигналов P и G для произвольной булевой функции

В предыдущем разделе было показано, как сигналы P (propagate) и G (generate) используются при сложении двух значений. Следующий шаг — разобраться, как формируются P и G при сложении с произвольной булевой функцией f(A, B), как это реализовано в 74181. В таблице ниже показаны значения P и G при вычислении «A PLUS f(A,B)». Например, когда A=0, сигнал Generate возникнуть не может, а Propagate зависит от значения f. А когда A=1, сигнал Propagate должен присутствовать обязательно, тогда как Generate снова зависит от значения f.

В 74181 четыре значения f задаются напрямую четырьмя входами Select (выводы S), что приводит к следующей таблице:^{(примеч.6)}

Для вычисления P и G каждого бита микросхема использует логический блок, показанный ниже и повторяющийся четыре раза. Нетрудно проверить, что он реализует приведенную выше таблицу. Например, G будет установлен, если A равно 1, B равно 1 и S3 равно 1, либо если A равно 1, B равно 0 и установлен S2.

Создание арифметических выходов

Результаты сложения формируются из внутренних переносов (от C0 до C3) в сочетании с сигналами P и G. Для каждого бита выражение A PLUS f эквивалентно P ⊕ G, поэтому добавление переноса дает полноценную 4-битную сумму. Таким образом:

F0 = C0 ⊕ P0 ⊕ G0

Аналогично вычисляются и остальные выходы F.^{(примеч.7)} На принципиальной схеме для этого у каждого выходного бита используются два элемента XOR.

Создание логических выходов

Для логических операций переносы отключаются принудительной установкой их всех в 1. Чтобы выбрать логическую операцию, вход M устанавливается в 1. Сигнал M подается на все элементы AND-NOR схемы вычисления переноса, принудительно устанавливая переносы в 1. Сумма выходного бита вычисляется так же, как описано выше, давая выражение A ⊕ f ⊕ 1 = A ⊕ f. Это выражение позволяет получить все 16 булевых функций, но в порядке, отличающемся от арифметических функций.^{(примеч.8)}

Интерактивный просмотрщик 74181

Чтобы увидеть, как схемы 74181 работают совместно, попробуйте интерактивную схему ниже.^{(примеч.9)} Входы микросхемы расположены сверху и справа; нажмите на любой из них, чтобы изменить значение. Сигналы A и B — это два 4-битных аргумента. Биты S справа выбирают операцию. C — входящий перенос (в инверсном виде). M — режим работы: 1 для логических операций и 0 для арифметических. Динамическая таблица под схемой показывает, какая операция выполняется в данный момент.

Сигналы P и G генерируются верхней частью схемы, как было описано выше. Ниже логика упреждающего переноса создает сигналы переноса (C), комбинируя сигналы P и G с входящим переносом (Cn). Наконец, сумма для каждого бита (Σ) формируется из сигналов P и G7, а затем объединяется с соответствующим переносом для параллельного формирования выходов F.^{(примеч.10)}

Результат и таблица истинности для введенных выше входных данных

Select 1001: F = A PLUS B PLUS C

Фотография кристалла микросхемы 74181

Я вскрыл 74181, сделал фотографии кристалла и выполнил реверс-инжиниринг ее TTL-схемы. В своей более ранней статье я рассмотрел схемотехнику подробно, но здесь я тоже приведу фотографию кристалла, потому что микросхема выглядит очень красиво. По краям видны тонкие соединительные проволоки, связывающие контактные площадки кристалла с внешними выводами. Блестящие золотистые области — это металлический слой, обеспечивающий внутренние соединения микросхемы.

Под металлическим слоем находится кремний фиолетового оттенка, легированный для формирования транзисторов и резисторов TTL-схем. Расположение элементов на кристалле очень близко соответствует схеме симулятора выше: входы находятся сверху, а выходы — снизу.

В заключение

На первый взгляд 74181 кажется просто набором логических элементов, случайно собранных вместе ради получения странных функций. Но более внимательное изучение показывает, что в наборе ее функций есть система: микросхема реализует все 16 булевых логических функций, а также операции сложения с этими функциями. Схема построена вокруг механизма упреждающего переноса, генерирующего сигналы G и P, благодаря чему результат может вычисляться параллельно, без ожидания распространения переноса.

Современные процессоры по-прежнему используют упреждающий перенос, хотя уже в более сложных формах, оптимизированных для большой разрядности и эффективной компоновки кристалла.^{(примеч.12)}

Примечания и ссылки

1. Ретропроекты, использующие 74181, включают APOLLO181 CPU, Fourbit CPU, 4 Bit TTL CPU, Magic-1 (на базе 74F381), TREX, Mark 1 FORTH and Big Mess o' Wires.

2. Вход входящего переноса и выход исходящего переноса позволяют объединять несколько микросхем 74181 в цепочку для работы со словами большей разрядности. Самое простое решение — передавать перенос от одной микросхемы к следующей, и именно такой подход использовался во многих мини-компьютерах. Более быстрый вариант — применять микросхему 74182 look-ahead carry generator, которая выполняет упреждающий перенос сразу между несколькими 74181, позволяя им работать параллельно. 

3. Стоит отметить, что операция A PLUS A фактически дает сдвиг влево, однако без дополнительной схемотехники 74181 не умеет выполнять сдвиг вправо. 

4. Для упрощения логики 74181 рассматривает выражение 1+1+C одновременно как случай Propagate и как случай Generate. (Некоторые схемы упреждающего переноса считают 1+1+C случаем Propagate, но не Generate.) Для выходов 74181 сигнал Propagate должен быть установлен, чтобы сигнал Generate имел смысл. 

5. Логика упреждающего переноса в 74181 почти идентична более ранней микросхеме сумматора 74LS83. Схему 74181 можно рассматривать как развитие 74LS83 с поддержкой 16 булевых функций и логических операций через отключение переноса. 

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

7. Бит суммы Σ легко получить из сигналов P и G. В одних технических описаниях каждый сигнал Σ формируется как P XOR G, а в других — как NOT P AND G. Поскольку комбинация P=0 и G=1 никогда не возникает, оба варианта дают одинаковый результат. На схеме я использую XOR, потому что так концептуально проще понять работу схемы, однако исследование кристалла показывает, что физически в микросхеме используются элементы NOT/AND. 

8. Логические функции определяются через входы Select следующим образом:

9. Поскольку первые два терма инвертированы, логическая функция для конкретного входа Select не совпадает с соответствующей арифметической функцией. 

10. Схема основана на диаграмме, созданной Poil для WikiMedia по лицензии CC BY-SA 3.0, с изменениями схемотехники и обозначений. 

У микросхемы 74181 есть несколько дополнительных выходов. Выход A=B используется совместно с операцией вычитания для проверки равенства двух входов. Выход Cn+4 представляет собой инверсный выход переноса и позволяет поддерживать слова большей разрядности. Выходы P и G — это сигналы распространения и генерации переноса, используемые для упреждающего переноса при работе с длинными словами.^{(примеч.11)} 

11. Выходы P и G на моей схеме поменяны местами по сравнению с техническим описанием, и причина этого довольно непростая. Я описываю 74181 с использованием логики активного высокого уровня, где высокий сигнал соответствует 1, как обычно и ожидается. Однако 74181 также может работать с логикой активного низкого уровня, где низкий сигнал обозначает 1. В режиме active-low микросхема 74181 работает корректно, но значения некоторых выводов меняются, а операции переставляются местами. Обозначения P и G в техническом описании относятся именно к active-low логике, поэтому при использовании active-high они оказываются инвертированы. 

12. Одним из примеров современного сумматора с упреждающим переносом является Kogge-Stone. Более подробную информацию о современных сумматорах можно найти в этой презентации или в этой диссертации. 

Другие выпуски от Ken Shirriff

• Исследование кремниевых кристаллов процессора Intel 386

• Невидимая оборона 386: как защищены входы и выходы процессора

• Реверс-инжиниринг π: как Pentium считал синусы быстрее всех

• Как сделать реверс-инжиниринг аналоговой микросхемы: FM-радиоприёмник TDA7000

• Схемотехника стека сопроцессора Intel 8087 для чисел с плавающей запятой: реверс-инжиниринг

• Два бита на транзистор: ПЗУ микрокода повышенной плотности в FPU-сопроцессоре Intel 8087

• Анализ кристалла 8087: быстрый битовый шифтер математического сопроцессора

• Внутри Intel 8086: как микрокод управляет АЛУ

• Как работает движок микрокода процессора 8086

• У Z-80 4-битное АЛУ. Вот как оно работает

• Внутри Intel 1405: фото кристалла памяти на регистре сдвига (1970)

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