УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ СИГНАЛА ПЕРЕПОЛНЕНИЯ Российский патент 1994 года по МПК G06F7/38 

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

Известно устройство [1] для формирования сигнала переполнения, содержащее узел инвертирования, блок дешифраторов нуля, дешифратор нуля, блок коммутации, первую и вторую схемы сравнения, элемент ИЛИ. Указанное устройство характеризуется низким быстродействием (максимальная задержка распространения сигнала равна 9 τ_э при N = 64, где τ_э - время задержки сигнала одним логическим элементом; N - разрядность информационного входа устройства).

Необходимость поиска структуры рассматриваемых устройств, обеспечивающей более высокое быстродействие, обусловлена тем, что при организации конвейерной обработки двоичных кодов (операндов) устройство для формирования сигнала переполнения должно работать синхронно с устройством для сдвига двоичных кодов (операндов). Для этого устройство для формирования сигнала переполнения должно иметь такое же или большее быстродействие, что и устройство для сдвига операнда. Максимальное быстродействие устройства для сдвига операндов достигает 8 τ_э (см. авт.св. СССР N 1633391) и на уровне логической структуры может быть увеличено на 6 τ_э при технологических ограничениях - использовании для построения устройств логических элементов с количеством входов не больше четырех или пяти.

Наиболее близким по технической сущности к заявляемому является устройство для формирования сигнала переполнения [2] , содержащее элемент И, преобразователь кода, модулей формирования сигнала переполнения, где N - количество разрядов информационного входа устройства; К - количество разрядов в группе (байта), причем информационные входы модулей соединены с соответствующими группам из К соседних разрядов информационного входа устройства, выход (сигнала переполнения) которого соединен с выходом элемента И, каждый i-й i = 1 - вход которого соединен с выходом сигнала переполнения одного i-го модуля, вход блокировки которого, кроме крайнего левого модуля, соединен с i-м разрядом выхода блокировки преобразователя кода, а в преобразователе кода через дешифратор границы нулей и второй вход дешифратора границы нулей (не упомянутый в указанном источнике) с (i-1)-м разрядом формирователя маски (необходимость которого подразумевается), вход которого должен быть соединен с вторым входом задания величины сдвига (старшими разрядами кода величины сдвига) устройства, вход знака которого соединен с входом знака всех модулей, вход блокировки крайнего левого модуля соединен с выходом источника логической "1".

Описанное устройство характеризуется низким быстродействием (максимальная задержка распространения сигнала при N = 64 равна 11 τ_э с учетом того, что задержка элемента ПЗУ в модуле равна 4 τ_э).

Основным техническим результатом заявляемого устройства является более высокое быстродействие.

Указанный технический результат достигается благодаря тому, что устройство для формирования сигнала переполнения, содержащее элемент И, первый формирователь маски, модулей формирования сигнала переполнения, где N - количество разрядов информационного входа устройства; К - количество разрядов в группе разрядов, причем информационные входы модулей соединены с соответствующими группами разрядов из К соседних разрядов информационного входа устройства, выход которого соединен с выходом элемента И, каждый i-й i = 1 - вход которого соединен с выходом одного i-го модуля, первый вход блокировки которого, кроме крайнего левого (первого) модуля, соединен с (i-2)-м разрядом выхода первого формирователя маски, вход которого соединен с первым входом задания величины сдвига устройства, вход знака которого соединен с входом знака всех модулей, первый вход блокировки крайнего левого модуля соединен с выходом источника логической "1", дополнительно содержит второй формирователь маски, дешифратор нуля, причем второй вход задания величины сдвига устройства соединен с входом второго формирователя маски, выход которого соединен с входом маски всех модулей, второй вход блокировки которых соединен с выходом дешифратора нуля, вход которого соединен с третьим входом задания величины сдвига устройства, третий вход блокировки каждого i-го i = 1 - -1 модуля соединен с (i-1)-м разрядом выхода первого формирователя маски, третий вход блокировки -го модуля соединен с выходом источника нуля.

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

Технический результат - высокое быстродействие в заявляемом устройстве достигается благодаря обеспечению параллельности дешифрации нуля требуемого количества групп разрядов информационного входа устройства (в узле дешифрации нуля выбранных маской, формируемой на выходе первого формирователя маски модулей) и анализа переполнения в одной требуемой группе из К разрядов информационного входа устройства (с помощью второго формирователя маски и узла анализа переполнения в требуемом (выбранном) модуле).

На фиг.1 изображена структурная схема устройства; на фиг.2 - структурная схема модуля; на фиг.3 - функциональная схема узла дешифрации нуля; на фиг. 4 - функциональная схема узла дешифрации нуля; на фиг.4 - функциональная схема узла анализа переполнения.

На фиг.1-4 1 - модуль формирования сигнала переполнения, 2 - элемент И, 3 - второй формирователь маски, 4 - дешифратор нуля, 5 - первый формирователь маски, 6 - второй вход задания величины сдвига, вход формирователя 3, 7 - первый вход задания величины сдвига, вход формирователя5, 8 - вход знака устройства и модуля 1, 9 - информационный вход устройства, 10 - вход маски модуля 1, выход формирователя 3, 11 - информационный вход модуля 1, 12 - первый вход блокировки модуля 1, выход источника единицы, 13 - третий вход блокировки модуля 1, 14 - второй вход блокировки модуля 1, выход дешифратора 4, 15 - выход модуля 1, 16 - третий вход блокировки -го = = 4 модуля, соединенный с выходом источника нуля, 17 - третий вход задания величины сдвига устройства, 18 - выход устройства и элементы И 2, 19 - элемент НЕ с парафазным выходом, 20 - узел дешифрации нуля в модуле 1, 21 - группа элементов И-НЕ в модуле 1, 22 - узел анализа переполнения, 23 - парафазный выход элемента НЕ 19, вход знака узлов 20 и 22, 24 - информационный вход узла 20, 25 - второй вход группы элементов И-НЕ 21, соединенный с соответствующими разрядами [0/6] входа 11 (при K = 8, N = 31 в частном случае). 26 - выход узла 20, третий информационный вход узла 22, 27 - выход группы 21, второй информационный вход узла 22, 28 - элементы ИЛИ-НЕ в узле 20, 29 - элементы И в узле 20, 30 - элементы ИЛИ в узле 20, 31 - элементы И-НЕ в узле 20, 32 - элемент И в узле 20, 33 - инверсный выход элемента НЕ 19 (инверсный разряд входа 23), 34 - прямой выход элемента НЕ 19 (прямой разряд входа 23), 35 - элемент 3И-НЕ в узле 22, 36 - элемент 4И-ИЛИ в узле 22, 37 - элемент И в узле 22, 38 - элемент И в узле 22, 39, 40, 41 - элементы И-НЕ в узле 22, 42 - элемент НЕ в узле 22.

Модуль 1 предназначен для формирования на выходе 15 сигнала (логического "0") переполнения в одной требуемой группе из К разрядов информационного входа устройства или сигнала (логического "0") неравенства нулю кода на соответствующих группах из К разрядов информационного входа устройства (с учетом кода знака на входе 8 знака устройства), или "нейтрального" сигнала (логической "1") в зависимости от значений сигналов на входах 12, 13, 14 блокировки и значений кодов на информационных входах 8, 10, 11. Модуль 1 (фиг.2) содержит элемент НЕ 19, узел 20 дешифрации нуля, группу 21 элементов НЕ, узел 22 анализа переполнения. При логическом "0" на входе 12 на выходе 15 модуля 1 устанавливается логическая "1" независимо от значений сигналов на входах 8, 10, 11, 14, 13. При логическом "0" на входе 14 и при логической "1" на входе 12 действие сигналов на входах 11, 10 на выход 15 блокируется и на выход 15 передается инвертированное значение сигнала с выхода 26. При этом при логическом "0" на входе 13 выход 26 узла 20 блокируется и на нем постоянно устанавливается логический "0", а на выходе 15 - логическая "1". При логической "1" на входе 13 в рассматриваемом случае на выходе 26 узла 20 (фиг.2) устанавливается логический "0" при нулевом коде на входе 11 (24) с учетом кода знака на входе 8, а на выходе 15 - логическая "1". При неравенстве кода на входе 11 нулю (с учетом кода знака на входе 8) на выходе 26 узла 20 устанавливается логическая "1", а на выходе 15 - логический "0". При логической "1" на входе 13 действие сигналов на входах 8, 10, 11 на выход 15 блокируется и, как и в предыдущем случае, на выход 15 передается инвертированное значение сигнала с выхода 26. При этом независимо от значения сигнала на входе 14 на выходе 26 узла 20 (фиг.3) устанавливается логический "0" при нулевом коде на входе 11 (24) с учетом кода знака на входе 8, а на выходе 15 - логическая "1". При неравенстве кода на входе 11 нулю (с учетом кода знака на входе 8) на выходе 26 узла 20 устанавливается логическая "1", а на выходе 15 - логический "0". Дешифрация нуля на входе 24 (11) осуществляется в описанных случаях с помощью узла 20. При этом "отрицательный" ноль (физически единичный код на входах 8 и 11) фиксируется с помощью элементов И 29 и элемента И-НЕ 31, один из входов которого соединен с прямым выходом 34 элемента НЕ 19 (с прямым разрядом 34 входа 23- фиг.3). "Положительный" ноль (физический нулевой код на входах 8 и 11) фиксируется с помощью элементов ИЛИ-НЕ 28 и элемента И-НЕ, один из входов которого соединен с инверсным выходом 33 элемента НЕ 19 (с инверсным разрядом 33 входа 23). Работа узла 20 блокируется, и на его выходе 26 устанавливает логический "0" только при логическом "0" на входах 13, 14 благодаря установке на выходе элемента ИЛИ 30 логического "0" и блокировке элемента И 32.

При установке на входе 14 логической "1", а на входе 13 - логического "0" работа узла 20 блокируется с установкой на выходе 26 логической "1", так как на входах элемента И 32 устанавливаются единицы. В остальных случаях обеспечивается формирование на выходе 26 логического "0" (при нулевом (логическом) коде на входе 24) или логической "1" (при ненулевом коде на входе 24).

При установке на входах 12, 14 логической "1", а на входе 13 - логического "0" осуществляется блокировка (как указывалось) узла 20 с установкой на выходе 26 логической "1", которая не блокирует работу узла 22. В этом случае осуществляется анализ переполнения на группе разрядов кода, установленного на входе 11 с учетом кода маски на входе 10. При К = 8 на разрядах [0/6] входа 10 формируется код маски, в котором логические "1" устанавливаются в таком количестве (l) разрядов слева (на выходе 10 формирователя 3), которое равно значению двоичного кода, установленного на входе 6 устройства. В остальных разрядах справа кода маски устанавливаются логические "0". В результате на выход 27 группы элементов И-НЕ 21 переданы инвертированные значения только l левых разрядов входа 11, а на остальных разрядах справа выхода устанавливаются логические "1".

В узле 22 с помощью элементов И 37, 38, И-НЕ 40 осуществляется фиксация единичного кода на входе 27 при логическом "0" на входе 8 (т.е. при положительном знаке) с формированием на выходе 15 логической "1" при установке на входе 27 единичного кода и логического "0" при установке на входе 27 любого другого кода. С помощью элементов 3И-ИЛИ 35, 4И-ИЛИ 36, И-НЕ 39 осуществляется фиксация на входе 27 нулевого кода при логической "1" на входе 8. Для этого через вход 10 осуществляется повторное маскирование, т.е. маскирование кода с входа 27, так как при единичном коде на входах 8, 2, 5 на выходе 27 формируется код, в котором в l старших (слева) разрядах установлены логические "0", и в остальных (справа) разрядах устанавливаются логические "1". Повторным маскированием осуществляется "подавление" логических "1". В результате обеспечивается с помощью элементов 3И-ИЛИ 35, 4И-ИЛИ 36 фиксация на входе 25 физического единичного кода с формированием на выходе 15 логической "1". В противном случае на выходе 15 устанавливается логический "0".

Узел 20 дешифрации нуля может быть построен на элементах ИЛИ-НЕ 28, И 29, 32, И-НЕ 31, ИЛИ 30. Узел 22 анализа переполнения может быть построен (фиг. 4) на элементах 3И-ИЛИ 35, 4И-ИЛИ 36, И 37, 38, И-НЕ 39, 40, 41, НЕ 42. Возможны другие схемы построения узлов 20, 22.

Структура модуля 1 является оптимальной в отношении аппаратных затрат. Формирователи 3 и 5 масок предназначены для преобразования кодов величины сдвига, устанавливаемых на входах 6 и 7 соответственно, в соответствующий код маски. Они могут быть построены на элементах постоянных запоминающих устройств (ПЗУ), закодированных в соответствии с табл.1 и 2 (для случая N = 64, K = 8).

Дешифратор 4 нуля предназначен для фиксации нулевого кода на входе 6 с формированием логического "0" на выходе 14. При этом в зависимости от особенностей внешней системы на входе 17 может устанавливаться тот же код, что и на входе 6, или инверсное значение кода, устанавливаемого на входе 6. В первом случае в качестве дешифратора 4 используется элемент ИЛИ, а во втором случае - элемент И-НЕ. Кроме этого, в библиотеке базовых элементов базового матричного кристалла чаще всего отсутствуют элементы ИЛИ, а для формирования соответствующего кода на входе 17 можно использовать дополнительный выход формирователя 3. Чтобы учесть все возможные случаи построения устройства (не влияющие на достигаемый технический результат) вход дешифратора 4 соединен с отдельным входом 17 устройства.

Устройство функционирует следующим образом.

В исходном состоянии на входе 9 устанавливается сдвигаемый двоичный код. На входе 8 устанавливается код знака сдвигаемого двоичного числа. На входе 6 устанавливается код младших разрядов кода величины сдвига. На входе 17 устанавливается инверсный код от кода, установленного на входе 6, или такой же код, что и код на входе 6 (в зависимости от особенностей внешней системы). На входе 7 устанавливается код старших разрядов кода величины сдвига. При отсутствии переполнения на выходе 18 устройства устанавливается логическая "1". При наличии переполнения на выходе 18 устройства устанавливается логический "0".

Рассмотрим для определенности пример (при N = 32, К = 8) сдвига двоичного числа М= = 1111000011110000111100001111000 на величину Ll = 23, т.е. L = 2 = (10) ^дв, l =3= =(011)^дв. Код М устанавливается на входе 9. Код знака, равный значению кода крайнего левого разряда кода М, т.е. равный единице, устанавливается на входе 8.

На входе 6 устанавливается код 011, на входе 17 - код =100, на входе 7 - код L = 10. В соответствии с табл.1 на выходе 10 формируется код маски 1110000. На выходе формирователя 5 на разряда [0/2] в соответствии с табл.2 формируется код 111. На выходе 14 устанавливается логическая "1", так как на входе 17 код не равен единичному. В соответствии с алгоритмом функционирования модулей 1 на выходах первого, второго, третьего, четвертого модулей (при отсчете слева направо) формируется код 0001 и на выходе 18 устанавливается нулевой код, означающий, что имеет место переполнение. При этом на информационном входе каждого модуля устанавливается код 11110000 (т.е. К = 8 разрядов кода М). На выходе 27 всех модулей формируется код 00011111. На выходах элементов И-НЕ 39, 40 всех модулей 1, кроме четвертого, устанавливаются логические "1", так как они заблокированы вследствие логической "1" на входе 13. На выходе 26 всех модулей, кроме четвертого, устанавливается логическая "1", так как на информационном входе каждого из них отсутствует единичный код, а установлен код 11110000. В результате на всех входах элементы И-НЕ 41 всех модулей, кроме четвертого, устанавливаются логические "1", а на выходе 15 - логические "0". В четвертом модуле узел 20 заблокирован вследствие логического "0" на входе 13 (16). На выходах элементов И-НЕ 39, 40 четвертого модуля устанавливают соответственно "0", "1", а на выходе 15 устанавливается логическая "1".

Таким образом обеспечивается фиксация переполнения так же, как и в прототипе и аналогах. При этом при N = 64, К = 8 с учетом того, что элементы 3И-ИЛИ 35, 4И-ИЛИ 36 и элемент И 2 имеют задержку распространения сигналов, равную 2 τ_э, где τ_э - задержка распространения сигналов элементов типа И-НЕ с количеством входов не больше пяти, быстродействие заявляемого устройства равно
Т_э = 1 τ_э+2 τ_э+1 τ_э+1 τ_э+2 τ_э = 7 τ_э.

Так как в прототипе быстродействие Т_п = =14 τ_э, а в аналоге [1] Т_ан= 9 τ_э, то технический результат - более высокое быстродействие заявляемого устройства - обеспечивается как по отношению к прототипу, так и по отношению ко всем известным к настоящему времени аналогам.

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

1. УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ СИГНАЛА ПЕРЕПОЛНЕНИЯ, содержащее элемент И, первый формирователь маски, N / K модулей формирования сигнала переполнения, где N - количество разрядов информационного входа устройства, K - количество разрядов информационного входа модуля, причем информационные входы модулей соединены с соответствующими группами разрядов из K соседних разрядов информационного входа устройства, выход которого соединен с выходом элемента И, каждый i-й (где i = 1, N / K) вход которого соединен с выходом одного i-го модуля, первый вход блокировки которого, кроме первого модуля, соединен с (i - 2)-м разрядом выхода первого формирователя маски, вход которого соединен с первым входом задания величины сдвига устройства, вход знака которого соединен с входом знака всех модулей, первый вход блокировки первого модуля соединен с выходом источника логической единицы, отличающееся тем, что он дополнительно содержит второй формирователь маски, дешифратор нуля, причем второй вход задания величины сдвига устройства соединен с входом второго формирователя маски, выход которого соединен с входом маски всех модулей, второй вход блокировки которых соединен с выходом дешифратора нуля, вход которого соединен с третьим входом задания величины сдвига устройства, третий вход блокировки каждого i-го (где i = 1, ... N / K - 1) модуля соединен с (i - 1)-м разрядом выхода первого формирователя маски, третий вход блокировки N / K-го модуля соединен с выходом источника нуля. 2. Устройство по п.1, отличающееся тем, что модуль формирования сигнала переполнения содержит элемент НЕ, узел дешифрации нуля, группу элементов И - НЕ, узел анализа переполнения, причем информационный вход модуля соединен с информационным входом узла дешифрации нуля, вход знака которого соединен с входом знака узла анализа переполнения и с парафазным выходом элемента НЕ, вход которого соединен с входом знака модуля, вход маски которого соединен с первым информационным входом узла анализа переполнения и с первым входом группы элементов НЕ, выход которой соединен с вторым информационным входом узла анализа переполнения, третий информационный вход которого соединен с выходом узла дешифрации нуля, первый вход блокировки которого соединен с третьим входом блокировки узла анализа переполнения и модуля, выход которого соединен в выходом узла анализа переполнения, второй вход блокировки которого соединен с вторым входом блокировки узла дешифрации нуля.