Алгоритмы на кристалле. Глава 1 (продолжение). Схемы простейших устройств02.06.2022 05:16

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

Предыдущие черновики:
… Примерное оглавление.
… Вычислительная модель.
… Быстродействие логических схем.

Возможно, в вашем браузере с первого раза не будут правильно отображаться формулы. Если так, попробуйте перезагрузит страницу — на моем компьютере этот фокус работает.
Желаю приятного чтения.

Простой способ представить себе работу элементарной логической схемы

Логическая схема и ее компоненты

Логические схемы состоят всего из трех типов компонент: портов (входных и выходных), шин и логических блоков (функциональных и регистров). При графическом изображении логическим блокам соответствуют скругленные прямоугольники, портам — маленькие полукруги, а шинам — тонике, иногда разветвленные линии. Границы самой схемы обозначены прямоугольной рамкой.

(Схема »=»)
Логическая схема способны производить вычисления, при этом они оперирует двоичными словами: «данными». Выходные порты (заполненные полукруги) нужны, чтобы отправлять данные, входные порты (белые полукруги) — чтобы их принимать, шины — чтобы передавать данные от выходных портов к входным. Функциональные логические блоки нужны, чтобы данные неким образом преобразовывать, а блоки-регистры — чтобы их временно запоминать.

Пути распространения данных в схеме неизменны: порты статично прикреплены к логическим блокам (внутренние порты) или внешней рамке (внешние порты), шины статично прикреплены к портам. Каждая шина и каждый порт способны работать с двоичными словами строго определённой длины, которая называется их размерностью. Размерности шины и всех прикрепленных к ней портов должны поэтому совпадать. Чтобы избежать неоднозначности в пересылаемых данных, к каждой шине разрешено прикреплять в точности один выходной порт. Места разветвления шин изображаются жирными точками, там, где точек нет — шины всего лишь пересекаются, не оказывая влияния на работу друг друга.

Такт, как эпоха

Процесс вычислений, производимых схемой, состоит из последовательности тактов. Неформально каждый такт удобно представлять себе как продолжительную временную эпоху. Логические схемы проектируются таким образом, чтобы в продолжение каждой эпохи каждый выходной порт смог отправить в прикрепленную к нему шину ровно одно двоичное слово, а каждый входной порт — ровно одно двоичное слово из прикрепленной к нему шины смог принять. Слово, которое на данном такте выходной порт отправит в шину, входной порт примет из шины, а сама шина передаст — будем также называть соответственно значением выходного порта, значением входного порта и значением шины в данный такт времени.

Процесс вычислений в схеме без регистров

По определению значение, которые функциональный блок на данном такте выставит на том или ином своем порту выхода, полностью определяется именем порта выхода, типом блока и значениями, которые на этом такте примут его входные порты. Например, функциональные блоки элементарного типа »+» реализуют сложение двух однобитных чисел: порту » $c$ » блок этого типа выставит значение »1» тогда и только тогда, когда оба его входных порта » $arg1$ » и » $arg2$ » на этом тате приняли значения »1», а значение порта » $r$ » окажется равным »1» лишь в том случае, когда среди значений » $arg1$ » и » $arg2$ » единица в точности одна. У блоков-констант нет портов входа, на каждом такте своим портам выхода они выставляют одно и тоже значение: блок «ноль» выставляет »0», блок «единица» выставляет »1». Спецификация функциональных блоков всех элементарных типов описана в аксиомах E1-E7 статьи «Вычислительная модель».

(рисунок однобитного +)

И так, пусть все логические блоки в схеме являются функциональными. Опишем работу такой схемы в один из тактов.

(Cхема равенства с аппендиксом из константы в продолжение одного такта. Начало).

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

(Продолжение: рассылка конвертов 1 этап).

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

(Продолжение: рассылка конвертов 2 этап).

Если в логической схеме нельзя совершить круг, переходя от одного функционального блока к другому функциональному блоку так, чтобы всякий раз при этом один из портов входа второго блока был бы соединен с одним из портов выхода первого, то такая схема называется функционально ациклической (есть в ней регистры, или нет — не важно). Из результатов статьи «Вычислительная модель» следует, что в функционально ациклических схемах (только такие мы и будем рассматриваться в оставшейся части книги) описанный выше процесс рассылки конвертов обязательно приведет к тому, что в итоге каждый входной порт схемы ровно один раз получит свой конверт, а для каждого внутреннего выходного порта, логический блок к которому тот прикреплен, ровно один раз вычислит его значение. Как только это произойдет, очередной такт можно считать завершенным.

(Рассылка конвертов. Конец: все порты получили значения).

Особенности поведения регистров

Элементарные регистры способны хранить в себе однобитные слова — значения регистра. Значения регистров меняются только при смене тактов. Слово, которое появится на единственном выходном порте » $out$ » регистра в текущий такт, является копией значения, которое имеет регистр в этот такт времени. То, какое значение будет хранить регистр в следующем такте, полностью определяется настоящим значением регистра и значениями его входных портов, принятыим ими на текущем такте. Все регистры имеют входной порт » $in$ », некоторые типы — входные поры » $reset$ » и » $enable$ » в любых сочетаниях. В зависимости от наличия тех или иных портов и значений, принятых этими портами на текущем такте, значение регистра в следующий такт времени либо сохраняется прежним, либо копирует значение, принятое на текущем такте портом » $in$ », либо обнуляется.

Для регистра с одним единственным входным портом » $in$ » значение, которое этот регистр будет иметь в следующий такт времени в точности равно значению, которое принял порт » $in$ » на текущем такте. Если регистр имеет порт » $reset$ » и значение, принятое этим портом на текущем такте есть »1», то на следующем такте значение регистра станет »0» вне зависимости от других условий.

Чтобы значение регистра можно было сохранять несколько тактов подряд, в некоторые типы регистров добавлен порт » $enable$ »: без учета влияния порта reset, если на текущем такте порт »» принял »0», то значение регистра на следующий такт останется прежним, если »1», то оно с копирует значение, принятое на этом такте портом » $in$ ».

Значение любого элементарного регистра в нулевой такт случайно.

(рисунок, поясняющий работу регистров)

Спецификация всех регистров, принятых в этой книге за элементарные, описаны в аксиомах E8-E11 статьи «Вычислительная модель».

Смена тактов в элементарной схеме

Если в схеме есть регистры, то в начале каждого такта в качестве еще одного первоисточника данных к уже упоминавшимся внешним выходным портам и выходным портам блоков-констант добавляются выходные порты регистров. В остальном процесс вычислений, происходящий на схеме в течение такта почти такой же, что и описанный выше процесс вычислений на схеме без регистров. Единственным отличие будет то, что каждый раз между концом текущего такта и началом следующего все регистры определяют свое новое значение. Ниже приведен пример работы за несколько последовательных тактов простенькой схемы с регистром «пульсар».

(рисунок, поясняющий работу пульсара в продолжение одного такта)

Замечание по поводу именования портов

Все внешние порты схемы наделяются собственными именами и никакой путаницы в их назывании не будет. В то же время мы неоднократно будем встречать схемы, в которых присутствуют сразу несколько блоков одного и того типа и у каждого из этих блоков есть порт с одним и тем же именем » $A \_port$ ». Пусть » $X \_block$ » и » $Y \_block$ » — собственные имена блоков, обладающих портом с именем » $A \_port$ ». Чтобы точно указать о каком именно порте идет речь к имени порта справа через точку будем приписывать собственное имя логического блока, к которому он принадлежит:» $X \_block.A \_port$ » — » $A \_port$ » блока » $X \_block$ »,» $Y \_block.A \_port$ » — » $A \_port$ » блока » $Y \_block$ ».

На этом наше короткое знакомство с основами теории логических схем закончено. Его объема, в принципе, должно быть достаточно для понимания всего излагаемого ниже материала. Более подробное и формализованное изложение общей теории читатель найдет в двух предыдущих статьях. По мере углубления в предмет их содержание станет полезным. Сейчас мы переходим к конкретным почти промышленным схемам.

Схема каскадного компаратора

Определение старшинства между двоичными словами

Для сравнения двоичных слов мы будем использовать лексикографический порядок. В лексикографическом порядке расставлены слова в словарях и справочниках. Применительно к двоичным словам он определяется следующим образом:

Пусть даны два m-битных слова: $x = x_0, …, x_m-1$ и $y = y_0, …, y_m-1$ .
Какое-то число начальных членов этих слов могут быть одинаковыми, то есть: $x_1 = y_1, …, x_i = y_i$ . Если эти слова совпадают не во всех позициях и $k$ — наименьшая из позиций, где они отличны, то меньшим считается то слово, у которого на $k$ -той позиции стоит »0». Например из двух 7 битных слов »0101000» и »0100111» в лексикографическом порядке второе меньше первого.

В следующем пераграфе мы докажем, что если каждое из слов $x$ и $y$ интерпретировать как запись натурального числа в двоичной системе исчисления: то есть $n(x) = x_0 * 2^{m-1} + …+ x_{m-1} *2^0$ , $n(y) = y_0 * 2^{m-1} + …+ y_{m-1} *2^0$ , то слово $x$ тогда и только тогда меньше слова $y$ в лексикографическом порядке, кода натурально число $n(x)$ , выраженное словом x, меньше натурального числа $n(y)$ , выраженного словом $y$ (это утверждение кажется очевидным, но все-таки попробуйте доказать его точно).

Абстрактное описание алгоритма сравнения

Само определение лексикографического порядка содержит в себе алгоритм его вычисления. Действительно, все что мы должны делать — это синхронно перебирать последовательности символов обоих слов до тех пор, пока не обнаружим позицию $k$ , на которой символы $x_k$ и $y_k$ различны. То слово, у которого в позиции $k$ стоит 0 и будет меньшим.

В пошаговом виде, описанный алгоритм выглядит так:

Ввести два булевых слова-состояния: первое — «просмотрев символы слов до позиции 0 включительно, установлено, что » или коротко — , и второе: «просмотрев символы слов до позиции 0 включительно, установлено, что », коротко — . Обоим словам-состояниям присвоить значение «ложь», перейти к 2)
Проверить одинаковы ли символы и . Если они различны и »0»- присвоить значение истина состоянию , если они различны и »0» — присвоить значение истина состоянию . Перейти к циклическому повторению 3)-5)
Если рассматриваемая позиция в словах и — последняя, перейти к 7). Иначе в обоих словах перейти к позиции , а в алгоритме к шагу 4)
Ввести слова-состояния: слово $(x<y)_{i+1}$ — «просмотрев слова вплоть до позиции , установлено, что », и слово $(y<x)_{i+1}$ — «просмотрев слова вплоть до позиции , установлено, что ». Обоим только что введенным словам-состояниям присвоить значения «ложь». Если хотя бы одно из слов-состояний предыдущей позиции или имеет значение «истина» (уже установлено какое из слов меньше), никаких действий над символами $x_{i+1}$ и $y_{i+1}$ не требуется. Просто копируем в $(x<y)_{i+1}$ , в $(y<x)_{i+1}$ . Снова переходим к 3). Иначе переходим к 5).
Если мы здесь, значит анализ ранее просмотренных позиций слов и не смог дать ответ, какое из слов меньше. Сравним текущие позиции $x_{i+1}$ и $y_{i+1}$ . Если они различны и $x_{i+1} =$ »0»- присвоить значение истина слову-состоянию $(x<y)_{i+1}$ , если они различны и $y_{i+1} =$ »0» — присвоить значение истина состоянию $(y<x)_{i+1}$ . Вернуться к циклическому повторению шага 3).
Конец алгоритма. Мы просмотрели все m позиций. Логика алгоритма такова, что только одно из слов-состояний: $(x<y)_{m-1}$ , или $(y<x)_{m-1}$ , может в итоге иметь значение «истина», тем самым отвечая на вопрос, какое из слов меньше. Если оба этих слова-состояния остались ложными, то слова и в точности совпадают.

Интерфейс схемы компаратора

Прежде чем строить схему какого-либо алгоритма, нужно определиться, в каком виде мы собираемся подавать исходные данные, а в каком виде — снимать результат. Компаратор, который мы построим ниже будет способен сравнивать два m-битных слова за один такт. Передаваться эти слова будут в качестве значений внешних выходных $m$ -битных портов » $x$ » и » $y$ ». Результат сравнения будет выводится как значения внешних входных 1-битных портов » $(x<y)?$ » и » $(y<x)?$ », при этом значение »1» будет интерпретироваться как истина, а значение »0» — как ложь. Если оба порта »» и »» на этом кате имеют значение ложь, значит поступившие на порты $x$ и $y$ в начале этого такта слова идентичны.

(интерфейс компаратора)

С интерфейсом схемы мы определились, пора теперь разобраться со знаком вопроса.

Операционная ячейка схемы компаратора

Алгоритм сравнения, который был описан выше, так или иначе синхронно просматривает все позиций слов $x$ и $y$ , совершая при этом некоторые действия. Если бы алгоритм был реализован как программа для обычного компьютера, то обработка символов каждой позиции слов $x$ и $y$ выполнялась бы последовательно одним единственным центральным процессором. Реализуя алгоритм в виде логической схемы, мы можем поручить обработку символов каждой позиций отдельной плеяде соединенных между собой логических блоков, которые мы будем называть ячейками (cell). В следующих статьях вы увидите, что такой подход может значительно увеличить производительность вычислительного устройства в сравнении со строго последовательным выполнением алгоритма одним единственным процессором.

В своей логической конструкции описанный выше алгоритм сравнения сводится к следующему:

Находясь над позицией $i$ и наблюдая пару символов $(x_i, y_i)$ , мы получаем результат обработки всех предыдущих пар $(x_0, y_0), …, (x_{i-1}, y_{i-1})$ закодированное в значениях однобитных слов-состояний $(x<y)_{i-1}$ и $(y<x)_{i-1}$ .

Если одно из этих состояний уже имеет значение «истина», или же $x_i = y_i$ , то все, что надо сделать — это передать без изменений значения обоих этих слов обработчику символов следующей позиции, но уже под видом $(x<y)_i$ и .

Если же оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ имеют значение «ложь», то значения слов-состояний $(x<y)_i$ и $(y<x)_i$ определяется тем, каковы символы $x_i$ , или $y_i$ . Если эти символы одинаковы, то обеим словам и следует приписать ложь. Если же символы различны, то одному из них нужно приписать «истина», а другому — ложь.

Давайте теперь подробно разберем схемы ячейек-обработчиков.

На рисунке… изображен обработчик пары первых символов слов $x$ и $y$ .

(Головная ячейка компаратора)

Плеяда блоков » $dif \_and_in$ » (тип » $and$ »),» $dif \_not$ » (тип » $not$ »),» $dif \_or$ » (тип » $or$ ») и » $dif\_and_r$ » (обведена сиреневым пунктирным прямоугольником) имеет назначение выяснить, различны ли $x_0$ и $y_0$ . Только в том случае, если первые символы слов $x$ и $y$ различны выходной порт » $r$ » блока » $dif \_and_r$ » посылает в голубую шину значение »1». Действительно, если значение выходного порта блока » $dif\_and_r$ » равно единице, значит и оба его входных порта также на текущем такте приняли значение единица. Порт » $dif \_and_r.arg1$ » примет значение «единица», только если оба символа $x_0$ и $y_0$ одновременно не являются единицей. Далее, порт «dif\_and_r.arg2» будет единицей в точности тогда, когда хотя бы один из символов $x_0$ или $y_0$ является единицей. Вместе два последних предложения доказывают, что » $dif \_and_r.r$ » на текущем такте будет иметь значение »1», только если первые символы поданных в этот такт слов $x$ и $y$ различны.

После того как порт » $dif \_and_r.r$ » выдал свое значение, вступают в игру прямые мультиплексоры » $mux_1$ » и » $mux_2$ ». Если первые символы сравниваемых слов одинаковы, то на порты » $comm$ » обоих мультиплексоров поступит »0», соответственно они оба на свой выход скопируют значения своих портов » $arg1$ », то есть »0». Если же символы $x_0$ и $y_0$ различны, значением выходов мультиплексоров станут копии значений их вторых портов входа » $arg2$ ». В этом случае значением слова $(x<y)_0$ станет копия $y_0$ , а значением слова $(y<x)_0$ — копия $x_0$ .

Не трудно проверить, что такой способ придавать значения словам $(x<y)_0$ и $(y<x)_0$ , когда $x_0$ и $y_0$ не одинаковы, действительно правильно устанавливает какое из слов: $x$ или $y$ меньше в лексикографическом сравнении. Если $x_0 = $ »1», то $y_0 = $ »0» и слово $(x<y)_0$ копирует $y_0$ , то есть получает, как и должно, значение «ложь», а $(y<x)_0$ копирует $x_0$ , то есть получает, как и должно, значение «истина». Если же $x_0 = $ »0», то тогда $y_0 = $ »1», соответственно $(x<y)_0$ получает значение «истина», а — значение «ложь».

И так, мы доказали, что приведенная схема обработчика двух самых первых символов слов $x$ и $y$ правильно вычисляет слова-состояния $(x<y)_0$ и $(y<x)_0$ . Рассмотри теперь обработчик, применимый для всех последующих позиций.

(Регулярная ячейка компаратора)

По сравнению с предыдущим рисунком здесь добавилась плеяда блоков в кирпичном прямоугольнике и блок типа » $and$ » » $con \_and$ ». Одновременно с этим исчез блок-константа и немного поменялись маршруты потоков данных. Самым главным же изменением, которое повлекло все остальные, стало добавление шин, по которым поступают слова-состояния $(x<y)_{i-1}$ и $(y<x)_{i-1}$ от обработчика позиции $i-1$ .

При обработке всех позиций, кроме первой, для того, чтобы значения слов $(x<y)_i$ и $(y<x)_i$ не стали простыми копиями $(x<y)_{i-1}$ и $(y<x)_{i-1}$ , должны выполняться сразу два условия:

оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ должны иметь значение «ложь»;
значения , и должны быть разными.

Второе условие, как и на предыдущем рисунке выполняет плеяда блоков с префиксом » $dif \_$ » — она заключена в сиреневый пунктирный прямоугольник. Первое условие проверятся плеядой блоков с префиксом » $s \_$ »: блоком типа » $or$ » » $s \_or$ » и блоком типа » $not$ » » $s \_not$ ». Значение выхода блока » $s \_not$ » тогда и только тогда равно »1», когда значение выхода блока » $s \_or$ » равно »0». Последнее будет наблюдаться в том и только в том случае, кода оба слова $(x<y)_{i-1}$ и $(y<x)_{i-1}$ имеют значение »0».

Блок » $con \_and$ » посылает на мультиплексоры »1» только в том случае, если выполнены оба условия. Сценарий, при котором на порты » $com$ » мультиплексоров подана »1» ничем не отличается от аналогичного сценария для обработчика головной части: если символы $x_i$ и $y_i$ различны, то значения $(x<y)_i$ и $(y<x)_i$ будут содержать в себе ответ, какое из слов: $x$ или $y$ в лексикографическом порядке меньше другого. Если же на порты » $com$ » поданы »0»-ли, то значением выходного порта каждого мультиплексора будет копия значения его входного порта » $arg1$ », а слова $(x<y)_i$ и $(y<x)_i$ , как и требует алгоритм, будут копиями слов $(x<y)_{i-1}$ и $(y<x)_{i-1}$ .

Схема целиком

Давайте теперь объединим все наши наработки в одну схему. Чтобы результат занимал не очень много места перерисуем схемы ячеек в более компактное представление и ограничимся сравнением 3-битных слов. Проверьте самостоятельно, что это все те же самые ячейки-обработчики, которые мы рисовали выше.

(компактное представление головного об