КОНВЕЙЕРНЫЙ АРИФМЕТИЧЕСКИЙ УМНОЖИТЕЛЬ
CONVEYOR ARITHMETIC MULTIPLIER

Изобретение относится к вычислительной технике и может быть применено в быстродействующих арифметических устройствах для выполнения операций умножения чисел.
Известно устройство для умножения [Cell-Structured Digital Multiplier of Semi-Systolic Construction, US 4748583, опубл. 31.05.1988], образующее полусисталическую конструкцию с линиями сумм и переносов, которые подключают определенные ячейки, и в конце линий образуются выходные сигналы.
Устройство содержит прямоугольную матрицу из 16-ти логических умножителей, на первый вход которой подается четырехразрядный сигнал множимого, а на второй вход матрицы подается четырехразрядный сигнал множителя через поразрядный сдвиговый регистр и драйвер. Причем сквозные выходы прямоугольной матрицы (4-4-4-4) подключены к треугольной матрице (4-3-2-1), а диагональные выходы этих двух матриц подаются через поразрядные сдвиговые регистры к восьмиразрядному выходу произведения.
Функционально устройство содержит ячейки, делящие матрицу на ряды и колонки, где ряды выдают порции частичных произведений в соответствии с конвейерным процессом. За счет элемента суммирующего логическое произведение формируется частичное произведение, сигнал суммы и сигнал переноса. При этом получается наименьшая задержка загрузки всеми битами, чтобы получить короткий интервал времени в передаче сигнала между двумя рядами.
В результате задержка подачи битов в умножителе не влияет на переходное время между ступенями матрицы, благодаря чему повышается быстродействие работы цифрового умножителя.
Из числа аналогов наиболее близким по технической сущности является конвейерный умножитель из патента [Pipeline Arithmetic Adder and Multiplier, US 4887233, опубл. 12.12.1989], который и выбран в качестве прототипа.
Прототип является более быстродействующим устройством, поскольку в данном устройстве отсутствует задержка сквозного распространения сигнала переноса, а также проблема размещения больших и нерегулярных впередсмотрящих сумматоров. Вместо этого введена конвейерная обработка. В такой конструкции каждая ячейка является полным сумматором, на вход которого поступают 3 бита: бит суммы с предыдущего ряда, бит частичного произведения и бит переноса из предыдущего ряда. Между соседними рядами включены защелки, и эти защелки позволяют осуществлять операции умножения конвейерным способом. Это означает, что пока в каком-либо ряду формируется частичная сумма одной операции умножения на основании информации, сохраненной в защелках предыдущего ряда, этот предыдущий ряд может вычислять частичную сумму для следующей операции умножения. Техника помещения защелок между соседними рядами ячеек увеличивает время между началом и концом операции умножения (задержку), но сильно увеличивает скорость, с которой последовательные произведения появляются на выходе (быстродействие).
Прототип содержит конвейерный умножающий блок и конвейерный суммирующий блок, которые имеют ячеистую структуру и разбиты на колонки и ряды, причем умножающий блок является входным с числом колонок, равным сумме разрядов множимого и множителя и с числом рядов на один больше числа разрядов множителя, а у суммирующего блока число колонок и число рядов равны числу разрядов соответственно множимого и множителя, где колонка старшего разряда начинается со второго ряда одноразрядным регистром, выход которого подключен к последовательно соединенным ячейкам первого типа, каждая из которых состоит из элемента ИЛИ и следующего за ним одноразрядного регистра, при этом остальные колонки суммирующего блока начинаются с первого ряда ячейками второго типа, каждая из которых состоит из полусумматора и следующего за ним одноразрядного регистра, причем эти ячейки содержатся во всех рядах кроме последнего, а число этих ячеек второго типа уменьшается в каждом ряду суммирующего блока на одну от ряда к ряду со стороны младших разрядов, причем первый ряд умножающего блока со стороны младших разрядов содержит ячейки третьего типа, каждая из которых состоит из элемента И и следующего за ним одноразрядного регистра и число которых соответствует числу разрядов множителя, образуя вместе составной элемент, а в остальных колонках этого первого ряда содержатся одноразрядные регистры, при этом второй ряд умножающего блока со стороны старших разрядов также содержит одноразрядные регистры, а в колонке, где в первом ряду был последний со стороны старших разрядов регистр, находится второй составной элемент, в следующем - третьем, ряду составной элемент находится в колонке, которая на один разряд ближе к старшему разряду, а в остальных колонках со стороны старших разрядов содержатся одноразрядные регистры, причем и со стороны младших разрядов в колонке сразу после составного элемента находится одноразрядный регистр, а в остальных колонках, кроме первой, располагаются ячейки второго типа, далее в следующем четвертом ряду четвертый составной элемент находится в колонке, которая еще на один разряд ближе к старшему разряду, чем в предыдущем ряду, и со стороны младших разрядов в колонке сразу после четвертого составного элемента находится одноразрядный регистр, а в остальных колонках, кроме первой и второй, располагаются ячейки четвертого типа, каждая из которых состоит из сумматора и следующего за ним одноразрядного регистра, далее в каждом последующем ряду умножающего блока составной элемент располагается в колонке, которая соответственно ближе поразрядно к старшему разряду и со стороны старших разрядов находятся одноразрядные регистры, а со стороны младших разрядов повторяются элементы из четвертого ряда, не доходя до первых трех, затем четырех и так далее колонок, при этом, если составной элемент размещается во второй со стороны старших разрядов колонке, то в этом ряду этот элемент - первый, а следующий ряд - последний ряд умножающего блока, у которого первый элемент - одноразрядный регистр, размещенный во второй со стороны старших разрядов колонке, в следующих колонках располагаются ячейки четвертого типа в том же количестве, что и в предпоследнем ряду, причем вход множимого умножающего блока объединен с входом одноразрядного регистра в колонке старшего разряда первого ряда и с первыми входами ячеек третьего типа этого ряда составного элемента, подключенных вторыми входами к входу последнего младшего разряда множителя, входы остальных разрядов которого от старшего до предпоследнего соединены соответственно с входами одноразрядных регистров первого ряда от второй колонки со стороны старшего разряда, а в каждой из этих колонок все ячейки последовательно соединены, в колонке старшего разряда от первого ряда до третьего от конца, кроме того, выходы всех одноразрядных регистров этой колонки каждого ряда соединены со вторыми входами составных элементов следующего ряда соответственно, а выходы этих составных элементов объединены со вторыми входами ячеек четвертого типа следующего ряда соответственно, кроме выхода составного элемента во втором ряду, объединенного со вторыми входами ячеек второго типа третьего ряда, а выходы переноса всех ячеек второго и четвертого типа подаются на третьи входы ячеек четвертого типа следующего ряда со сдвигом на один разряд в сторону старших разрядов, а в оставшихся со стороны младших разрядов столбцах, кроме первого и второго, все ячейки с использованием первого входа последовательно соединены и выходы ячеек третьего типа первого ряда объединены с первыми входами соответствующих по колонкам ячеек второго типа третьего ряда, а выход ячейки старшего разряда нижнего ряда суммирующего блока является выходом старшего разряда всего устройства, причем все ряды начиная с третьего со стороны младших разрядов содержит одноразрядные регистры, которые по колонкам соединены последовательно и выходы регистров последнего ряда являются выходами устройства от младшего до предпоследнего разряда, а одноразрядный регистр третьего ряда первой колонки объединен с выходом ячейки третьего типа первого ряда этой колонки.
Устройство работает следующим образом.
0
1
2
3
Пусть множимое X равно 0101 (5) и множитель Y равен 1011 (11). На вход первого ряда умножающего блока поступает множимое 0101 и заводится младший разряд множителя y (1), результат (0101) поступает во второй ряд, на который заводится произведение второго разряда множителя y (1) и X (что равно 01010). Дальше результат (01111) и перенос (00000) поступают в третий ряд, на который заводится произведение y и X (000000). Полученный результат (001111) и перенос (000000) поступают в четвертый ряд, на который заводится произведение y на X (0101000), следующий результат (0100111) и перенос (0010000) поступают в первый ряд суммирующего блока, далее результат (0110111) и перенос (0000000) поступают во второй ряд суммирующего блока т.д.. Перенос (0000000) поступает на третий и четвертый ряды без изменений, а итоговым результатом становится код 0110111. Данный результат соответствует результату умножения 5 на 11, равному 55 (0110111).
Недостатком прототипа является ограниченное быстродействие, связанное с последовательным функционированием синхронизирующего блока из регистров и невозможностью оперативной работы с отдельными битами результата.
Техническим результатом является создание устройства, имеющего более высокое быстродействие и позволяющее работать с отдельными битами по ходу их формирования.
Решение поставленной задачи состоит в том, что в конвейерный арифметический умножитель, содержащий конвейерный умножающий блок и конвейерный суммирующий блок, которые имеют ячеистую структуру и разбиты на колонки и ряды, причем умножающий блок является входным с числом колонок, равным сумме разрядов множимого и множителя и с числом рядов на один больше числа разрядов множителя, а у суммирующего блока число колонок и число рядов равны числу разрядов соответственно множимого и множителя, где колонка старшего разряда начинается со второго ряда одноразрядным регистром, выход которого подключен к последовательно соединенным ячейкам первого типа, каждая из которых состоит из элемента ИЛИ и следующего за ним одноразрядного регистра, при этом остальные колонки суммирующего блока начинаются с первого ряда ячейками второго типа, каждая из которых состоит из полусумматора и следующего за ним одноразрядного регистра, причем эти ячейки содержатся во всех рядах кроме последнего, а число этих ячеек второго типа уменьшается в каждом ряду суммирующего блока на одну от ряда к ряду со стороны младших разрядов, причем первый ряд умножающего блока со стороны младших разрядов содержит ячейки третьего типа, каждая из которых состоит из элемента И и следующего за ним одноразрядного регистра и число которых соответствует числу разрядов множителя, образуя вместе составной элемент, а в остальных колонках этого первого ряда содержатся одноразрядные регистры, при этом второй ряд умножающего блока со стороны старших разрядов также содержит одноразрядные регистры, а в колонке, где в первом ряду был последний со стороны старших разрядов регистр, находится второй составной элемент, в следующем - третьем, ряду составной элемент находится в колонке, которая на один разряд ближе к старшему разряду, а в остальных колонках со стороны старших разрядов содержатся одноразрядные регистры, причем и со стороны младших разрядов в колонке сразу после составного элемента находится одноразрядный регистр, а в остальных колонках, кроме первой, располагаются ячейки второго типа, далее в следующем четвертом ряду четвертый составной элемент находится в колонке, которая еще на один разряд ближе к старшему разряду, чем в предыдущем ряду, и со стороны младших разрядов в колонке сразу после четвертого составного элемента находится одноразрядный регистр, а в остальных колонках, кроме первой и второй, располагаются ячейки четвертого типа, каждая из которых состоит из сумматора и следующего за ним одноразрядного регистра, далее в каждом последующем ряду умножающего блока составной элемент располагается в колонке, которая соответственно ближе поразрядно к старшему разряду и со стороны старших разрядов находятся одноразрядные регистры, а со стороны младших разрядов повторяются элементы из четвертого ряда, не доходя до первых трех, затем четырех и так далее колонок, при этом, если составной элемент размещается во второй со стороны старших разрядов колонке, то в этом ряду этот элемент - первый, а следующий ряд - последний ряд умножающего блока, у которого первый элемент - одноразрядный регистр, размещенный во второй со стороны старших разрядов колонке, в следующих колонках располагаются ячейки четвертого типа в том же количестве, что и в предпоследнем ряду, причем вход множимого умножающего блока объединен с входом одноразрядного регистра в колонке старшего разряда первого ряда и с первыми входами ячеек третьего типа этого ряда составного элемента, подключенных вторыми входами к входу последнего младшего разряда множителя, входы остальных разрядов которого от старшего до предпоследнего соединены соответственно с входами одноразрядных регистров первого ряда от второй колонки со стороны старшего разряда, а в каждой из этих колонок все ячейки последовательно соединены, в колонке старшего разряда от первого ряда до третьего от конца, кроме того, выходы всех одноразрядных регистров этой колонки каждого ряда соединены со вторыми входами составных элементов следующего ряда соответственно, а выходы этих составных элементов объединены со вторыми входами ячеек четвертого типа следующего ряда соответственно, кроме выхода составного элемента во втором ряду, объединенного со вторыми входами ячеек второго типа третьего ряда, а выходы переноса всех ячеек второго и четвертого типа подаются на третьи входы ячеек четвертого типа следующего ряда со сдвигом на один разряд в сторону старших разрядов, а в оставшихся со стороны младших разрядов столбцах, кроме первого и второго, все ячейки с использованием первого входа последовательно соединены и выходы ячеек третьего типа первого ряда объединены с первыми входами соответствующих по колонкам ячеек второго типа третьего ряда, а выход ячейки старшего разряда нижнего ряда суммирующего блока является выходом старшего разряда всего устройства, введены элемент памяти и элементы управления записью информации в память и чтением информации из памяти, причем выход ячейки третьего типа первого ряда первой со стороны младших разрядов колонки соединен с первым входом ввода данных элемента памяти, а остальные входы ввода данных соединены соответственно с основными выходами ячеек крайних со стороны младших разрядов столбцов начиная от третьего ряда и заканчивая предпоследним, при этом выходы элементов управления записью и чтением объединены с соответствующими входами элемента памяти, а выходы элемента памяти вместе с выходом старшего разряда устройства объединены в выходную шину устройства.
Сущность изобретения состоит в организации синхронизации выходных бит и сигналов переноса конвейерного умножения с помощью элемента памяти, благодаря чему увеличивается скорость, с которой последовательные произведения по битам появляются на выходе, и появляется возможность оперативной работы с отдельными битами.
Сущность предлагаемого изобретения поясняется чертежами, где на фиг.1 изображена функциональная схема предлагаемого конвейерного арифметического умножителя с ячеистой структурой, где выделены штрихпунктирными линиями конвейерные умножающий и суммирующий блоки, линиями из точек - колонки и пунктирными линиями - составные элементы, на фиг.2 представлен пример организации управления записью информации CWR в память по условным номерам ячеек, на фиг.3 обобщено управление чтением информации элементом CRD и формирование выходной шины BUS D с учетом старшего разряда для рассматриваемого примера.
0
M-1
1
Конвейерный арифметический умножитель (фиг.1), содержащий конвейерный умножающий блок 1 и конвейерный суммирующий блок 2, которые имеют ячеистую структуру и разбиты на колонки 1.1.k, 1.2.k, 1.3.k, …, 2.1.k, 2.2.k, … и ряды 1.p.1, 1.p.2, 1.p.3, …, 2.p.1, 2.p.2, … (позиционно обозначены: № блока, № колонки, № ряда), причем умножающий блок является входным с числом колонок, равным сумме разрядов множимого N и множителя M и с числом рядов на один больше числа разрядов множителя (M+1), а у суммирующего блока число колонок и число рядов равны числу разрядов соответственно множимого N и множителя M, где колонка старшего разряда начинается со второго ряда одноразрядным регистром 2.M.2, выход которого подключен к последовательно соединенным ячейкам первого типа …, 2.M.(N-1), 2.M.N, каждая из которых состоит из элемента ИЛИ и следующего за ним одноразрядного регистра, при этом остальные колонки суммирующего блока начинаются с первого ряда ячейками второго типа 2.(M-1).1, …, 2.2.1, 2.1.1, каждая из которых состоит из полусумматора и следующего за ним одноразрядного регистра, причем эти ячейки содержатся во всех рядах кроме последнего, а число этих ячеек второго типа уменьшается в каждом ряду суммирующего блока (от 2.p.1 до 2.p.N) на одну от ряда 2.(M-1).2, …, 2.2.2 к ряду 2.(M-1).(N-1) со стороны младших разрядов, причем первый ряд умножающего блока со стороны младших разрядов содержит ячейки третьего типа, каждая из которых состоит из элемента И и следующего за ним одноразрядного регистра и число которых соответствует числу разрядов множителя N 1.1.1, 1.2.1, 1.3.1, …, 1.N.1, образуя вместе составной элемент 3.1, а в остальных колонках этого первого ряда 1.(N+1).1, 1.(N+2).1, …, 1.(M+N-1).1, 1.(M+N).1 содержатся одноразрядные регистры, при этом второй ряд умножающего блока со стороны старших разрядов также содержит одноразрядные регистры 1.(M+N).2, 1.(M+N-1).2, …, 1.(N+2).2, а в колонке, где в первом ряду был последний со стороны старших разрядов регистр, находится второй составной элемент 3.2 (1.(N+1).2), в следующем - третьем, ряду составной элемент 3.3 находится в колонке, которая на один разряд ближе к старшему разряду (1.(N+2).3), а в остальных колонках со стороны старших разрядов содержатся одноразрядные регистры 1.(M+N).3, 1.(M+N-1).3, …, причем и со стороны младших разрядов в колонке сразу после составного элемента 1.(N+2).3 находится одноразрядный регистр 1.(N+1).3, а в остальных колонках, кроме первой, располагаются ячейки второго типа 1.2.3, 1.3.3, …, 1.N.3, далее в следующем четвертом ряду четвертый составной элемент 1.(M+N-1).4 находится в колонке, которая еще на один разряд ближе к старшему разряду, чем в предыдущем ряду, и со стороны младших разрядов в колонке сразу после четвертого составного элемента находится одноразрядный регистр 1.(N+2).4, а в остальных колонках, кроме первой и второй, располагаются ячейки четвертого типа 1.(N+1).4, 1.N.4, …, 1.3.4, каждая из которых состоит из сумматора и следующего за ним одноразрядного регистра, далее в каждом последующем ряду умножающего блока (от 1.p.4 до 1.p.(M-1)) составной элемент располагается в колонке, которая соответственно ближе поразрядно к старшему разряду (от (N+3) до (M+N-1)) и со стороны старших разрядов находятся одноразрядные регистры (M+N-1).(M+1), а со стороны младших разрядов повторяются элементы из четвертого ряда (…, 1.(N+2).(M+1), 1.(N+1).(M+1), 1.N.(M+1)), не доходя до первых трех, затем четырех и так далее колонок, при этом, если составной элемент размещается во второй со стороны старших разрядов колонке 1.(M+N-1).k, то в этом ряду этот элемент - первый 1.(M+N-1).4, а следующий ряд - последний ряд умножающего блока, у которого первый элемент - одноразрядный регистр 1.(M+N-1).(M+1), размещенный во второй со стороны старших разрядов колонке, в следующих колонках располагаются ячейки четвертого типа в том же количестве, что и в предпоследнем ряду, причем вход множимого умножающего блока объединен с входом одноразрядного регистра в колонке старшего разряда первого ряда 1.(M+N).1 и с первыми входами ячеек третьего типа этого ряда 1.N.1, 1.3.1, 1.2.1, 1.1.1 составного элемента 3.1, подключенных вторыми входами к входу последнего младшего разряда множителя y, входы остальных разрядов которого от старшего y до предпоследнего y соединены соответственно с входами одноразрядных регистров первого ряда от второй колонки со стороны старшего разряда, а в каждой из этих колонок все ячейки последовательно соединены 1.(M+N-1).1, 1.(M+N-1).2, 1.(M+N-1).3, 1.(M+N-1).4, …, 1.(M+N-1).(M+1), 2.(M-1).1, 2.(M-1).2, …, 2.(M-1).(N-1); …; 1.(N+2).1, 1.(N+2).2, 1.(N+2).3, 1.(N+2).4, …, 1.(N+2).(M+1), 2.2.1, 2.2.2; 1.(N+1).1, 1.(N+1).2, 1.(N+1).3, 1.(N+1).4, …, 1.(N+1).(M+1), 2.1.1, в колонке старшего разряда от первого ряда до третьего от конца 1.(M+N).1, 1.(M+N).2, 1.(M+N).3, …, кроме того, выходы всех одноразрядных регистров этой колонки (M+N) каждого ряда соединены со вторыми входами составных элементов следующего ряда соответственно 1.(N+2).3, …, 1.(M+N-1).4, а выходы этих составных элементов объединены со вторыми входами ячеек четвертого типа следующего ряда соответственно 1.(N+1).4, 1.N.4, …, 1.3.4; …, 1.(N+2).(M+1), 1.(N+1).(M+1), 1.N.(M+1), кроме выхода составного элемента во втором ряду 1.(N+1).2, объединенного со вторыми входами ячеек второго типа третьего ряда 1.N.3, …, 1.3.3, 1.2.3, а выходы переноса всех ячеек второго и четвертого типа подаются на третьи входы ячеек четвертого типа следующего ряда со сдвигом на один разряд в сторону старших разрядов 2.(M-1).1, …, 2.2.1, 2.1.1; 2.M.2, 2.(M-1).2, …, 2.2.2; 2.M.(N-1), 2.(M-1).(N-1); 2.M.N, а в оставшихся со стороны младших разрядов столбцах, кроме первого и второго, все ячейки с использованием первого входа последовательно соединены и выходы ячеек третьего типа первого ряда 1.N.1, …, 1.3.1, 1.2.1, 1.1.1 объединены с первыми входами соответствующих по колонкам ячеек второго типа третьего ряда 1.N.3, …, 1.3.3, 1.2.3, а выход ячейки старшего разряда нижнего ряда суммирующего блока 2.M.N является выходом старшего разряда всего устройства.
Кроме того, устройство содержит элемент памяти 4 и элементы управления записью информации 5 в память и чтением информации 6 из памяти, причем выход ячейки третьего типа первого ряда первой со стороны младших разрядов колонки 1.1.1 соединен с первым входом ввода данных элемента памяти 4, а остальные входы ввода данных соединены соответственно с основными выходами ячеек крайних со стороны младших разрядов столбцов начиная от третьего ряда и заканчивая предпоследним 1.2.3, 1.3.4, …, 1.N.(M+1), 2.1.1, 2.2.2, …, 2.(M-1).(N-1), при этом выходы элементов управления записью 5 и чтением 6 объединены с соответствующими входами элемента памяти 4, а выходы элемента памяти 4 вместе с выходом старшего разряда устройства 2.M.N объединены в выходную шину устройства.
Устройство работает следующим образом.
N-1
1
0
0
1
0
0
1
N-1
1
Пусть в начальный момент времени на вход ячеек третьего типа A/R первого ряда 1.1.1, 1.2.1, 1.3.1, …, 1.N.1 блока 1 подается множимое X=x, …, x, x и младший значимый бит множителя y. Множимое X задерживается и затем подается вместе со следующим битом множителя y. Ячейки A/R первого ряда отвечают за младший значимый бит множителя y. Каждая из этих ячеек также отвечает за различные биты множимого X: ячейка A/R 1.1.1 отвечает за младший значащий бит множимого x, ячейка A/R 1.2.1 отвечает за следующий значащий бит множимого x и т.д. до ячейки A/R 1.N.1, которая взаимодействует со старшим значащим битом множимого x. С выхода первой ячейки первого ряда A/R 1.1.1 сигнал поступает на первый вход ввода данных элемента памяти 4. Остальные ячейки A/R 1.2.1, 1.3.1, …, 1.N.1 первого ряда распространяют свои выходные сигналы соответственно на входы ячеек второго типа H/R третьего ряда 1.2.3, 1.3.3, …, 1.N.3. Наиболее старший бит содержится в ячейке R1.(N+1).3. Ячейки от 1.2.3 до 1.(N+1).3 отвечают за копирование элемента множимого X составного элемента 3.2, который проходит через второй значащий бит множителя y. Этот бит множителя задерживается ячейкой R1.(N+1).1. Задержки X и у синхронизованы: выход составного элемента 3.2 с выходом ячеек A/R от 1.1.1 до 1.N.1. Выходы ячеек от 1.2.3 до 1.N.3 выдают частичную сумму, поступающую на следующий ряд.
0
2
2
Первые три ряда блока 1 имеют отличную структуру от последующих рядов, потому что вначале нет частичной суммы. Два входа отвечают за множимое, которое комбинируется в третьем ряду. Все последующие ряды, кроме предпоследнего, имеют в старшем конце ряда ячейки R. Ячейки F/R располагаются со стороны младших позиций ряда. Каждая из ячеек F/R соединена с битом множимого, для каждого из которых введена соответствующая задержка посредством ячеек R. Каждая ячейка F/R впоследствии принимает сумму соответствующего сумматора в ячейку из предыдущего ряда и также принимает сигнал переноса из сумматора предыдущего ряда, который на один бит ниже значимого. Например, ячейка F/R 1.3.4 принимает сигнал суммы ячейки H/R 1.3.3, сигнал переноса ячейки H/R 1.2.3 и результат произведения x*y из четвертой ячейки составного элемента A/R 3.3. Вход в этот элемент получается после задержки соответствующего бита множителя y через ячейки 1.(N+2).1 и 1.(N+2).2 и задержкой множимого X на аналогичный размер (ячейки 1.(M+N).1 и 1.(M+N).2).
Каждая ячейка из младших позиций ряда начиная с третьего соединена с очередным входом ввода данных элемента памяти 4. Его работа согласована с помощью элементов управления записью 5 информации в память и чтением информации 6 из памяти.
Блок 2 - это суммирующее устройство, использующее конвейерный принцип работы. Блок 2 разбит на M рядов и M столбцов. Первый ряд модуля 2 содержит M-1 ячеек H/R. Младшая ячейка H/R 2.1.1 соединена с переносом, поступающим из младшей ячейки F/R в последнем ряду блока 1 (ячейка 1.N.(M+1)), и с результатом суммы, поступающим из предыдущей ячейки F/R того же ряда (ячейка 1.(N+1).(M+1)). Старшая значащая ячейка H/R в первом ряду блока 2 соответственно соединена со старшей значащей ячейкой последнего ряда блока 1. В первом ряду блока 2 расположено только N-1 ячеек, потому что последняя ячейка последнего ряда блока 1 (ячейка R1.(M+N-1).(M+1)) не распространяет сигнала переноса.
Второй ряд блока 2 имеет ячейку R 2.M.2 в своей старшей значащей позиции и ячейки H/R от следующей позиции 2.(M-1).2 до последней, заканчивающейся за одну позицию 2.2.2 от младшей. Ячейка R 2.M.2 распространяет сигнал переноса старшей ячейки первого ряда блока 2 H/R 2.(M-1).1. Каждая ячейка H/R соединена с выходом суммы соответствующей ячейки H/R предыдущего ряда и с выходом переноса ячейки H/R предыдущего ряда, но на один знак более младшей позиции. В каждом последующем ряду блока 2 количество ячеек H/R уменьшается на одну, а старшей ячейкой является ячейка O/R а не R.
Каждая ячейка H/R 2.1.1, 2.2.2, …, 2.(M-1).(N-1) из младших позиций рядов блока 2 распространяет сигнал суммы на очередной вход ввода данных элемента памяти 4. Сигнал суммы старшего разряда n поступает с выхода ячейки R 2.M.N на выходную шину всего устройства. Остальные сигналы суммы поступают на выходную шину с выходов элемента памяти 4 в порядке следования разрядов от 1 до n-1.
Пусть, например, множимое X равно 0101 (5 в десятичном коде), а множитель Y равен 1011 (11 в десятичном коде). Множимое 0101 заводится на элементы составного элемента A/R 3.1; это означает, что на вход ячейки A/R 1.1.1 будет поступать «1», на вход ячейки A/R 1.2.1 - «0», на вход ячейки A/R 1.3.1 - «1» и на вход ячейки A/R 1.4.1 - «0» (в общем случае - это ячейка A/R 1.N.1).
0
Со входа множителя y младший разряд подается на другой вход составного элемента A/R 3.1; это означает, что на другие входы ячеек A/R 1.1.1, A/R 1.2.1, A/R 1.3.1, A/R 1.4.1 (в общем случае - это ячейка A/R 1.N.1) будет поступать «1». В результате логического умножения на выходе указанных ячеек будет выработан код 0101, и «1» с выхода младшего разряда, а именно с выхода A/R 1.1.1, поступит на первый вход ввода данных элемента памяти 4. Информация с выходов остальных разрядов ячеек A/R 1.2.1, A/R 1.3.1, A/R 1.4.1 подается на ячейки второго типа H/R, а это значит, что на вход ячейки H/R 1.2.3 поступает «0», на вход ячейки H/R 1.3.3 поступает «1» и на вход ячейки H/R 1.4.3 (в общем случае - это ячейка H/R 1.N.3) поступает «0».
1
На составной элемент A/R 3.2 через регистр R1.(N+1).1 поступает бит множителя y, который в данном случае имеет значение «1», а также через регистр R1.(M+N).1 поступает множимое X равное 0101. В результате на выходе составного элемента A/R 3.2 появляется такой же код, как и на выходе элемента третьего типа A/R 3.1, то есть 0101. А это значит, что на вход ячейки H/R 1.2.3 поступает «1», на вход ячейки H/R 1.3.3 поступает «0» и на вход ячейки H/R 1.4.1 (в общем случае - это ячейка H/R 1.N.3) поступает «1», а старший разряд «О» подается на вход регистра R 1.(N+1).3. В результате на выходах ячеек второго типа H/R формируется код, представленный битами сумм. Эти суммы получаются при обработке сигналов ячеек соответственно: A/R 1.2.1 и младшей ячейки элемента третьего A/R3.2-(«0»+«1»=«1»); A/R 1.3.1 и следующей ячейки элемента третьего A/R3.2-(«1»+«0»=«1»); A/R 1.4.1 (в общем случае - это ячейка A/R 1.N.1) и следующей ячейки элемента третьего A/R 3.2-(«0»+«1»=«1»). Таким образом, биты суммы будут представлены числом 111. Младшая из единиц с выхода первой в ряду ячейки H/R 1.2.3 поступает на второй вход ввода данных элемента памяти 4. Следующие две единицы подаются на входы ячеек четвертого типа F/R следующего ряда соответствующих колонок. Старший разряд с составного элемента A/R 3.2 подается на вход ячейки четвертого типа F/R в своей колонке, как отмечалось, через регистр R 1.(N+1).3, поэтому значение его не меняется, то есть на ячейку F/R 1.(N+1).4 поступает «0».
В ячейках второго типа H/R кроме основного результата формируются также биты переноса, которые передаются на ячейки четвертого типа F/R, находящиеся в следующих по номеру колонках следующего ряда. В рассматриваемом примере при формировании сумм биты переноса представлены нулями 000: для младшей ячейки H/R 1.2.3 - («0»+«1»=«1» и перенос «0»), для следующей ячейки H/R 1.3.3 - («1»+«0»=«1» и перенос «0»), и наконец, для последней H/R ячейки в этом ряду 1.4.3 (в общем случае - это ячейка H/R 1.N.3) - («0»+«1»=«1» и перенос «0»).
2
На составной элемент A/R 3.3 через регистры R 1.(N+2).1 и R 1.(N+2).2 поступает бит множителя y, который в данном случае имеет значение «0», а также через регистры R 1.(M+N).1 и R 1.(M+N).2 поступает множимое X равное 0101. В результате на выходе составного элемента A/R 3.3 появляется нулевой код, то есть 0000. А это значит, что на входы всех ячеек F/R четвертого ряда F/R 1.3.4, F/R 1.4.4 (в общем случае - это ячейка F/R 1.N.4), F/R 1.5.4 (в общем случае - это ячейка F/R 1.(N+1).4), а также на вход регистра R 1.(N+2).4 поступают нули, то есть 0000.
В результате на выходах ячеек четвертого типа F/R формируются биты сумм и переноса: для ячейки F/R 1.3.4-(«0»+«1»+«0»=«1» и перенос «0»), для ячейки F/R 1.4.4 (в общем случае - это ячейка F/R 1.N.4) - («0»+«1»+«0»=«1» и перенос «0»), для ячейки F/R 1.5.4 (в общем случае -это ячейка F/R 1.(N+1).4) - («0»+«0»+«0»=«0» и перенос «0»). Таким образом, биты суммы будут представлены числом 011. Младшая единица с выхода первой в ряду ячейки F/R 1.3.4 поступает на третий вход ввода данных элемента памяти 4. Старшие биты подаются на входы ячеек четвертого типа F/R следующего ряда соответствующих колонок. Старший разряд с составного элемента A/R 3.3 подается на вход ячейки четвертого типа F/R в своей колонке, как отмечалось, через регистр R 1.(N+2).4, поэтому значение его не меняется, то есть на ячейку F/R 1.(N+2).(M+1) поступает «0».
В ячейках четвертого типа F/R сформированные биты переноса, передаются на ячейки четвертого типа F/R, находящиеся в следующих по номеру колонках следующего ряда. В рассматриваемом примере при формировании сумм биты переноса представлены нулями 000.
3
M-1
На составной элемент A/R 3.4 через регистры R 1.(M+N-1).1, R 1.(M+N-1).2 и R 1.(M+N-1).3 поступает бит множителя y (в общем случае вход y), который в данном случае имеет значение «1», а также через регистры R 1.(M+N).1, R 1.(M+N).2 и R 1.(M+N).3 поступает множимое X равное 0101. В результате на выходе составного элемента A/R 3.4 появляется такой же код, как и на выходе элемента третьего типа A/R 3.1, то есть 0101. А это значит, что на вход ячейки F/R 1.N.(M+1) поступает «1», на вход ячейки F/R 1.(N+1).(M+1) поступает «0» и на вход ячейки F/R 1.(N+2).(M+1) поступает «1», а старший разряд «0» подается на вход регистра R 1.(M+N-1).(M+1).
В результате на выходах ячеек четвертого типа F/R формируются биты сумм и переноса: для ячейки F/R 1.N.(M+1) - («1»+«1»+«0»=«0» и перенос «1»), для ячейки F/R 1.(N+1).(M+1) - («0»+«0»+«0»=«0» и перенос «0»), для ячейки F/R 1.(N+2).(M+1) - («1»+«0»+«0»=«1» и перенос «0»). Таким образом, биты суммы будут представлены числом 100. Младший нуль с выхода первой в ряду ячейки F/R 1.N.(M+1) поступает на i-й вход ввода данных элемента памяти 4. Старшие биты подаются на входы ячеек второго типа H/R следующего ряда соответствующих колонок блока 2. Старший разряд подается на вход ячейки второго типа H/R в своей колонке блока 2 с выхода регистра R 1.(M+N-1).(M+1), поэтому значение его не меняется, то есть на ячейку H/R 1.(M-1).1 поступает «0».
В ячейках четвертого типа F/R последнего ряда блока 1 сформированные биты переноса передаются на ячейки второго типа H/R, находящиеся в следующих по номеру колонках следующего ряда, который является первым в блоке 2. В рассматриваемом примере при формировании сумм биты переноса представлены кодом 001.
В результате на выходах ячеек второго типа H/R первого ряда блока 2 формируются биты сумм и переноса: для ячейки H/R 2.1.1 - («1»+«0»=«1» и перенос «0»), для ячейки H/R 2.2.1 - («0»+«1»=«1» и перенос «0»), для ячейки H/R 2.(M-1).1 - («0»+«0»=«0» и перенос «0»). Таким образом, биты суммы будут представлены числом 011. Младшая единица с выхода первой в ряду ячейки H/R 2.1.1 блока 2 поступает на i+1 вход ввода данных элемента памяти 4. Старшие биты подаются на входы ячеек второго типа H/R следующего ряда соответствующих колонок блока 2.
В ячейках второго типа H/R первого ряда блока 2 сформированные биты переноса, передаются на ячейки, находящиеся в следующих по номеру колонках следующего ряда, который является вторым в блоке 2. В старшей колонке сигнал переноса принимает регистр R 2.M.2, а в остальных - ячейки второго типа H/R. В рассматриваемом примере при формировании сумм биты переноса представлены нулями 000.
В результате на выходах ячеек второго типа H/R второго ряда блока 2 формируются биты сумм и переноса: для ячейки H/R 2.2.2 - («0»+«1»=«1» и перенос «0»), для ячейки H/R 2.(M-1).2 - («0»+«0»=«0» и перенос «0»). Таким образом, биты суммы будут представлены числом 01. Младшая единица с выхода первой в ряду ячейки H/R 2.2.2 блока 2 поступает на i+2 вход ввода данных элемента памяти 4. Старший бит подается на вход ячейки второго типа H/R следующего ряда соответствующей колонки блока 2. В этом ряду в старшей колонке находится регистр R 2.M.2, с которого на следующий ряд передается принятая информация, то есть нуль.
В ячейках второго типа H/R второго ряда блока 2 сформированные биты переноса, передаются на ячейки, находящиеся в следующих по номеру колонках следующего ряда. В старшей колонке сигнал переноса принимает ячейка первого типа O/R 2.M.(N-1), а в следующей - ячейка второго типа H/R 2.(M-1).(N-1). В рассматриваемом примере при формировании сумм биты переноса представлены нулями 00.
В результате на выходе ячейки второго типа H/R 2.(M-1).(N-1) предпоследнего ряда блока 2 формируются биты суммы и переноса: («0»++«0»=«0» и перенос «0»). Таким образом, бит суммы будет представлен числом 0, и поступает на n-1 вход ввода данных элемента памяти 4. В этом ряду в старшей колонке находится ячейка первого типа O/R 2.M.(N-1), которая выполняет функцию ИЛИ: («0» ИЛИ «0»=«0»), то есть на следующий последний ряд будет передан нуль.
Сформированный в ячейке второго типа H/R 2.(M-1).(N-1) предпоследнего ряда блока 2 бит переноса нуль, передается на ячейку O/R 2.M.N, находящуюся в следующей по номеру колонке следующего ряда. Таким образом, на выходе этой ячейки O/R 2.M.N будет получен результат по функции ИЛИ: («0» ИЛИ «0»=«0»), то есть на n выход блока 2 в шину BUS D будет передан нуль.
Остальные разряды шины BUS D от n-1 до 1 снимаются с выхода элемента памяти 4 под управлением элемента чтения информации 6 из памяти. Для данного примера на шине сформируется код 00110111 (55 в десятичном коде). Таким образом, в десятичном коде множимое 5 умножается на множитель 11 и получается 55.
Принцип работы устройства состоит в конвейерном формировании результата умножения по рядам с соответствующей управляемой последовательной записью результата по каждому биту и организацией считывания как параллельно, так и в других режимах.
3
2
1
0
3
2
1
0
8
7
6
5
4
3
2
1,
В начале работы осуществляется прием информации в первый ряд. Для используемого примера x x x x равно 0101, а y y y y равно 1011. Результаты работы подаются на соответствующие входы ввода данных элемента памяти 4, что для данного примера отражено на временной диаграмме фиг.2 в виде поочередного представления результата a a a a a a a a равного 00110111. При этом показано управление записью информации CWR в память по условным номерам ячеек.
1
1
2
2
3
3
4
5
6
7
4
5
6
7
Результат первого разряда a=«1» запишется в ячейку 1.1 памяти на втором такте под управлением CWR. Результат второго разряда a=«1» запишется в ячейку 2.1 памяти на третьем такте под управлением CWR. Результат третьего разряда a=«1» запишется в ячейку 3.1 памяти на четвертом такте под управлением CWR. Далее аналогично результаты четвертого (a=«0»), пятого (a=«1»), шестого (a=«1») и седьмого (a=«0») разрядов будут записаны в ячейки памяти 4.1, 5.1, 6.1, 7.1 под управлением CWR, CWR, CWR, CWR соответственно.
Управление чтением информации CRD может выполняться по отдельным битам уже в следующем такте после записи этих битов, что дает возможность оперативной работы с результатом по мере его формирования. При этом сохраняется возможность параллельного съема информации с выходной шины BUS D по готовности старшего разряда и с его учетом, что для данного примера отражено на временной диаграмме фиг.3, где показано управление чтением информации CRD из памяти по условным номерам ячеек.
1
7
8
8
На восьмом такте под управлением CRD÷CRD производится чтение всего результата, к которому при организации выходной шины BUS D добавляется результат a старшего разряда (для данного примера a=«0»).
1
n
Функциональная характеристика конвейерного арифметического умножителя определяется по рядам с формированием результата по битам a÷a.
0
В начале работы множимое и множитель поступают на вход умножителя. В первом ряду составным элементом A/R 3.1 реализуется функция И для множимого X с множителем y:
A/R 1.1
0
0
A/R 2.1
1
0
A/R 3.1
2
0
A/RN.1
N-1
0
S=(x&y); S=(x&y); S=(x&y); …; S=(x&y).
В результате определяется значение младшего разряда произведения
1
A/R1.1
0
0
a=S=x&y, которое подается на запись в ячейку памяти RAM 1.1.
1
На следующем этапе работы составным элементом A/R 3.2 реализуется функция И для множимого X с множителем y:
A/R(N+1)/1.2
0
1
A/R(N+1)2.2
1
1
A/R(N+1)/3.2
2
1
A/R(N+1)/(N-1).2
N-2
1
A/R(N+1)/N.2
N-1
1
S=(x&y); S=(x&y); S=(x&y); …; S=(x&y); S=(x&y).
Выходы ячеек составных элементов A/R 3.1 и 3.2 синхронизованы при поступлении на следующий третий ряд, где ячейки второго типа H/R 1.2.3, 1.3.3, …, 1.N.3 реализуют функции суммирования с выработкой переносов:
H/R2.3
A/R2.1
A/R(N+1)/1.2
H/R2.3
H/R3.3
A/R3.1
A/R(N+1)/2.2
S=(S+S) и C; S=(S+S)
и
H/R3.3
H/RN.3
A/RN.1
A/R(N+1)/(N-1).2
H/RN.3
C; …; S=(S+S) и C.
В результате на выходе ячейки второго типа H/R 1.2.3 определяется значение второго разряда произведения
2
H/R 2.3
A/R 2.1
A/R (N+1)/1.2
a=S=(S+S),
2
которое подается на запись в ячейку памяти RAM 2.1. Кроме того, на этом этапе составным элементом A/R 3.3 реализуется функция И для множимого X с множителем y:
A/R(N+2)/1.3
0
2
A/R(N+2)/2.3
1
2
A/R(N+2)/3.3
2
2
A/R(N+2)/N.3
(N-1)
2
S=(x&y); S=(x&y); S=(x&y); …; S=(x &y).
В четвертом ряду ячейки четвертого типа F/R реализуют полное суммирование с учетом переносов:
F/R3.4
H/R2.3
H/R3.3
A/R(N+2)/1.3
F/RN.4
H/R(N-1).3
H/R N.3
A/R(N+2)/(N-2).3
F/R(N+1).4
H/R N.3
A/R(N+2)/(N-1).3
S=C+S+S; …; S=C+S+S; S=C+S.
При этом на выходе ячейки четвертого типа F/R 1.3.4 формируется значение третьего разряда произведения
3
F/R3.4
H/R2.3
H/R3.3
A/R(N+2)/1.3
a=S=C+S+S,
которое подается на запись в ячейку памяти RAM 3.1. Ячейки F/R при реализации суммирования вырабатывают переносы для следующего уровня обработки информации:
F/R3.4
F/RN.4
F/R(N+1).4
C, …, C, C.
3
Кроме того, здесь, как и на предыдущем этапе, реализуется функция И элементом третьего типа A/R 3.4 для множимого X с множителем y.
1
(M-1)
Далее процесс повторяется для множимого X со всеми множителями y вплоть до y. Для представленной четырехразрядной структуры умножителя реализация функции И в этом случае будет иметь вид:
A/R(M+N-1)/1.4
0
(M-1)
A/R(M+N-1)/2.4
1
(M-1)
A/R(M+N-1)/1.3
2
(M-1)
A/R(M+N-1)/N.4
(N-1)
(M-1)
S=(x&y); S=(x&y); S=(x&y); …; S=(x&y).
В последнем ряду блока 1 с помощью ячеек четвертого типа F/R завершается полное трехбитовое суммирование с учетом переносов:
F/RN.(M+1)
F/R(N-1).M
F/RN.M
A/R(M+N-1)/1.M
F/R(N+1).(M+1)
F/R.M
F/R(N+1).M
A/R(M+N-1)/2.M
F/R(N+2).(M+1)
F/R(N+1).M
F/R(N+2).M
A/R(M+N-1)/3.M
S=C+S+S; S=C+S+S; S=C+S+S; ….
В общем случае i-й разряд произведения для ячейки памяти RAM i.1 вырабатывается ячейкой четвертого типа F/R 1.N.(M+1)
i
F/RN.(M+1)
F/R(N-1).M
F/RN.M
A/R(M+N-1)/1.M
a=S=C+S+S,
а остальные выходы элементов последнего ряда умножающего блока подаются на суммирующий блок, в том числе переносы:
F/RN.(M+1)
F/R(N+1).(M+1)
F/R(N+2).(M+1)
C; C; C; ….
Первый ряд бока 2 содержит ячейки второго типа H/R 2.1.1, 2.2.1, …, 2.(M-1).1, которые реализуют функции суммирования двух битов с выработкой переносов:
H/R2.1.1
F/RN.(M+1)
F/R(N+1).(M+1)
H/R2.1.1
H/R2.2.1
F/R(N+1).(M+1)
F/R(N+2).(M+1)
H/R2.2.1
H/R2.(M-1).1
F/R(M+N-2).(M+1)
A/R(M+N-1).M
H/R2.(M-1).1
S=C+S и C; S=C+S и C; …; S=C+S и C. С выхода суммы первой ячейки H/R 2.1.1 в первом ряду блока 2 снимается i+1 разряд произведения в ячейку памяти RAM (i+1).1
i+1
H/R2.1.1
F/RN.(M+1)
F/R(N+1).(M+1)
a=S=C+S.
Во втором ряду блока 2 реализуется та же функция суммирования, что и в первом ряду:
H/R2.2.2
H/R2.1.1
H/R2.2.1
H/R2.2.2
H/R2.(M-1).2
H/R2.(M-2).1
H/R2.(M-1).1
H/R2.(M-1).2
S=C+S и C; …; S=C+S и C.
Аналогично с первой ячейки второго ряда H/R 2.2.2 в ячейку памяти RAM (i+2).1 подается i+2 разряд произведения.
В предпоследнем ряду находятся ячейка первого типа O/R 2.M.(N-1) и ячейка второго типа H/R 2.(M-1).(N-1). При этом ячейка первого типа находится в последнем столбце и реализует функцию ИЛИ для сигнала переноса с ячейки второго типа предпоследнего столбца предыдущего ряда H/R 2.(M-1).(N-2) и для сигнала результата с ячейки первого типа последнего столбца предыдущего ряда O/R 2.M.(N-2)
O/R2.M.(N-1)
H/R2.(M-1).(N-2)
O/R2.M.(N-2)
S=C v S,
а в предпоследнем столбце находится ячейка второго типа H/R, которая формирует сумму двух битов и перенос
H/R2.(M-1).(N-1)
H/R2.(M-2).(N-2)
H/R2.(M-1).(N-1)
H/R2.(M-1).(N-1)
S=C+S и C.
Выход суммы ячейки H/R 2.(M-1).(N-1) является выходом предпоследнего разряда произведения и подается в ячейку памяти RAM (n-1).1
n-1
H/R2.(M-1).(N-1)
H/R2.(M-2).(N-2)
H/R.(M-1).(N-2)
a=S=C+S.
В последней колонке последнего ряда находится ячейка первого типа O/R 2.M.N, которая реализует функцию ИЛИ для получения последнего старшего разряда произведения, который подается непосредственно в выходную шину BUS D
n
O/R2M.N
H/R2.(M-1).(N-1)
O/R2.M.(N-1)
a=S=C v S.
Таким образом, формирование старшего разряда позволяет перейти к чтению всего результата. При этом информация с предыдущих разрядов может использоваться по мере их получения, что повышает быстродействие работы устройства и позволяет работать с отдельными битами по ходу их формирования.