УСТРОЙСТВО ДЛЯ ВЫРАВНИВАНИЯ ПОРЯДКОВ m ДВОИЧНЫХ ЧИСЕЛ
DEVICE FOR MATCHING EXPONENTS OF m BINARY NUMBERS

Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих функцию выравнивания порядков двоичных чисел путем параллельно-конвейерного нахождения максимального порядка, а затем вычисления разностей между максимальным порядком и остальными порядками m двоичных чисел. Вычисленные разности указывают, на сколько разрядов необходимо сдвинуть мантиссы операндов для того, чтобы выровнять порядки.
Однородной вычислительной средой называется регулярная структура, состоящая из соединенных друг с другом одинаковых ячеек, выполняющая определенную функцию.
Ячейка однородной вычислительной среды - элемент регулярной структуры.
Разрядный срез - совокупность бит i-й позиции от m участвующих в операции операндов. Операндами в данном случае будут выступать порядки исходных двоичных чисел.
Известно устройство выравнивания порядков операндов, запатентованное в качестве изобретения - патент RU 2006910 С1 от 30.01.1994. Устройство содержит: четыре входных регистра, два регистра, формирователь кода сдвига целого числа, нормализатор целого числа, узел сдвига/обращения числа, блок формирования кодов сдвигов чисел, узел управления, два выходных регистра. Недостаток состоит в том, что в устройстве не реализован конвейерный принцип обработки информации, что существенно снижает быстродействие устройства.
Наиболее близким к заявляемому решению является техническое решение устройства, в котором итерационно находится максимальный порядок путем последовательного сравнения исходных порядков, а затем происходит последовательно m вычитаний исходных порядков из найденного наибольшего порядка с целью определения количества сдвигов мантисс исходных чисел. Устройство обладает значительными аппаратурными затратами, что приводит к снижению надежности, при этом не реализован параллельно-конвейерный принцип обработки информации, что значительно снижает его быстродействие.
Техническим результатом от использования заявляемого устройства для выравнивания порядков m двоичных чисел является повышение быстродействия за счет параллельно-конвейерного нахождения максимального порядка с помощью анализа разрядных срезов операндов, а затем вычисления разностей максимального порядка и остальных порядков m двоичных чисел. Также при увеличении количества участвующих операндов количество аппаратурных затрат возрастает линейно.
Заявляемое устройство имеет m-разрядный вход, вход синхронизации, вход сброса, m-разрядный выход и состоит из блока нахождения максимального порядка и блока вычитания.
Вход синхронизации устройства для выравнивания порядков m двоичных чисел соединен с входом синхронизации блока нахождения максимального порядка и блока вычитания, вход сброса устройства соединен с входом сброса блока нахождения максимального порядка и блока вычитания, m-разрядный вход устройства соединен со вторым m-разрядным информационным входом блока вычитания и m-разрядным информационным входом блока нахождения максимального порядка, выход которого соединен с первым информационным входом блока вычитания.
Блок нахождения максимального порядка состоит из m-входового элемента ИЛИ и из m ячеек блока нахождения максимального порядка, при этом блок нахождения максимального порядка имеет m-разрядный информационный вход, вход синхронизации, вход сброса, одноразрядный выход.
Ячейка блока нахождения максимального порядка состоит из двух двухвходовых элементов И, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, двух информационных триггеров и имеет вход синхронизации, вход сброса, два информационных входа, информационный выход.
Вход синхронизации ячейки соединен с входом синхронизации первого триггера и первым входом первого элемента И, выход которого соединен с входом синхронизации второго триггера. Вход сброса ячейки соединен с входом сброса второго триггера. Первый информационный вход ячейки подключен к информационному входу первого триггера, выход которого подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и информационному выходу ячейки. Второй информационный вход ячейки подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу второго триггера, инверсный выход которого подключен ко второму входу первого элемента И и второму входу второго элемента И.
На фиг.1 приведена функциональная схема ячейки блока нахождения максимального порядка, где 1, 3 - информационные входы; 2 - вход синхронизации; 4 - вход сброса; 5, 9 - двухвходовые элементы И; 6 - элемент ИСКЛЮЧАЮЩЕЕ ИЛИ; 7, 8 - информационные триггеры, 10 - информационный выход. Ячейка может быть реализована на любой элементной базе, имеющей возможность представления булевых функций, в том числе сверхбольшие интегральные схемы и программируемые логические интегральные схемы (ПЛИС). Вариант реализации на языке программирования аппаратуры VHDL приведен на фиг.2.
В заявляемом техническом решении блок нахождения максимального порядка представляет собой совокупность рассмотренных ячеек и m-входового элемента ИЛИ, m-разрядного информационного входа, входа синхронизации, входа сброса и выхода, которые соединены следующим образом.
Вход синхронизации блока нахождения максимального порядка соединен с входами синхронизации всех ячеек. Вход сброса блока нахождения максимального порядка соединен с входами сброса всех ячеек. Первый информационный вход ячеек блока нахождения максимального порядка соединен с соответствующими разрядами m-разрядного информационного входа блока. Выход каждой i-й ячейки подключен к i-му входу m-входового элемента ИЛИ, выход которого подключен ко второму информационному входу каждой ячейки, где i∈[1, m].
Количество ячеек в блоке нахождения максимального порядка равно m. Выход m-входового элемента ИЛИ соединен с выходом блока нахождения максимального порядка.
Блок вычитания состоит из m ячеек блока вычитания и имеет первый m-разрядный информационный вход, второй одноразрядный информационный вход, вход синхронизации, вход сброса, m-разрядный выход.
Ячейка блока вычитания состоит из трех двухвходовых элементов И, трех двухвходовых элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, одного двухвходового элемента ИЛИ, одного элемента НЕ, четырех информационных триггеров и имеет вход синхронизации, вход сброса, два информационных входа, информационный выход.
Вход синхронизации ячейки блока вычитания соединен с первым входом первого элемента И, выход которого соединен с входом синхронизации первого триггера. Вход синхронизации ячейки блока вычитания соединен с входами синхронизации второго, третьего триггера и элемента НЕ, выход которого соединен с входом синхронизации четвертого триггера.
Первый информационный вход ячейки блока вычитания подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента ИЛИ. Второй информационный вход ячейки блока вычитания подключен к первому входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен ко второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и второму входу второго элемента И. Второй информационный вход ячейки блока вычитания подключен к информационному входу первого триггера, выход которого подключен ко второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Вход сброса ячейки блока вычитания подключен к входу сброса первого триггера, инверсный выход которого подключен ко второму входу первого элемента И.
Первый информационный вход ячейки блока вычитания подключен к первому входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому входу третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и первому входу третьего элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера, выход которого подключен к второму входу третьего элемента И и второму входу третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу второго триггера, выход которого является информационным выходом ячейки блока вычитания.
На фиг.3 приведена функциональная схема ячейки первого типа однородной вычислительной среды, где 1, 2 - информационные входы; 3 - вход синхронизации; 4 -вход сброса; 7, 8, 10 - элементы ИСКЛЮЧАЮЩЕЕ ИЛИ; 5, 9, 11 - элементы И; 6, 13, 14, 12 - элемент ИЛИ; 15 - элемент НЕ; 17 - информационные триггеры, 16 - информационный выход. Примером построения ячейки может служить ее реализация на программируемых логических интегральных схемах (ПЛИС). Вариант реализации на языке программирования аппаратуры VHDL приведен на фиг.4.
В заявляемом техническом решении блок вычитания представляет собой совокупность рассмотренных ячеек, первого информационного входа, второго m-разрядного информационного входа, входа синхронизации, входа сброса и m-разрядного выхода, которые соединены следующим образом.
Вход синхронизации блока вычитания соединен с входами синхронизации всех ячеек. Вход сброса блока вычитания соединен с входами сброса всех ячеек. Первый информационный вход блока вычитания соединен с первыми информационными входами всех ячеек блока вычитания. Второй информационный вход ячеек блока вычитания соединен с соответствующими разрядами m-разрядного информационного входа блока вычитания. Выход ячеек блока вычитания соединен с соответствующими разрядами m-разрядного выхода блока вычитания. Количество ячеек в блоке вычитания равно m.
1
m
1
m
На фиг.5 представлена структурная схема устройства для выравнивания порядков m двоичных чисел в общем виде, где 1 - m-входовой элемент ИЛИ, 2 - блок нахождения максимального порядка, 3 - блок вычитания, CELL1 - ячейки блока нахождения максимального порядка, CELL2 - ячейки блока вычитания, X-X - m-разрядный информационный вход, Y-Y - m-разрядный выход. Устройство может быть реализовано на любой элементной базе, имеющей возможность представления булевых функций, в том числе сверхбольшие интегральные схемы и программируемые логические интегральные схемы (ПЛИС).
Описание работы устройства
Устройство обеспечивает выравнивание порядков двоичных чисел путем параллельно-конвейерного нахождения максимального порядка, а затем вычисления разностей между максимальным порядком и остальными порядками m двоичных чисел, где ячейка блока нахождения максимального порядка (фиг.1) реализует следующую логическую функцию:
Q(t)=a(t-1)&(~(b(t-1)⊕(Q(t-1)));
где a, b - соответственно состояние сигналов на входах 1 и 3 ячейки;
Q(t) - состояние сигнала на выходе 10 ячейки.
Ячейка блока вычитания (фиг.3) реализует следующую систему логических функций:
s(t)=a⊕(b⊕b(t-1))⊕p(t-1);
p(t)-(a&(b⊕b(t-1)))v(p(t-1)&(а⊕(b⊕b(t-1))));
где а, b - соответственно состояние сигналов на входах 1 и 2 ячейки;
s(t) - состояние сигнала на выходе 12 ячейки;
p(t) - обратная связь сигнала переноса внутри ячейки.
i
n
n-1
1
Каждый i-й двоичный позиционный порядок можно представить в виде последовательности бит A(a,a,…,a), где n - разрядность порядка, i∈[1,m]. Тогда m порядков исходных чисел можно представить в виде матрицы:
1,j
2,j
m,j
Столбцы матрицы с элементами (a, а,…,a) являются входными векторами - разрядными срезами, которые поступают на обработку в заявляемое устройство.
В каждом такте на входы синхронизации всех триггеров подается сигнал синхронизации.
Операция выравнивания порядков состоит из двух этапов.
На первом этапе находится максимальный остаток. Разряды порядков в виде разрядных срезов подаются на m-разрядный информационный вход устройства начиная со старших разрядов. Причем каждый следующий разрядный срез подается на следующий такт работы устройства. В каждом такте происходит анализ очередной позиции порядков. Если в текущем разрядном срезе присутствует хотя бы одна единица, то запись последующих разрядов в ячейки, содержащие в этом такте нули, блокируется. В случае когда в разрядном срезе присутствуют только нули, запись ни в одну из ячеек не блокируется. Таким образом, после прохождения всех разрядных срезов запись в соответствующие ячейки будет заблокирована для всех порядков, отличных от максимального.
На втором этапе происходит параллельно-конвейерное вычитание исходных порядков из максимального порядка. Разряды порядков в виде разрядных срезов подаются на m-разрядный информационный вход устройства начиная с младших разрядов. Причем каждый следующий разрядный срез подается на следующий такт работы устройства. В результате через один такт работы устройства формируется младший бит разности n-разрядных порядков. После этого биты результата доступны на выходе устройства каждый последующий такт работы. Таким образом, устройство реализует конвейерный принцип обработки информации. Так как в ячейке самая длинная цепочка распространения сигнала имеет четыре логических элемента, время задержки распространения сигнала составляет 4·t, где t - время задержки сигнала одним логическим элементом.
Если принять за время вычитания пары n-разрядных порядков чисел n тактов работы устройства, то время нахождения максимального порядка в конвейерном режиме равно n тактов и время параллельного вычисления разностей в конвейерном режиме равно n тактов, тогда полное время работы устройства составит 2·n тактов. При этом время нахождения максимального порядка известным итерационным способом равно m·n тактов, где m - количество исходных порядков, а время последовательного вычитания порядков из максимального также составит m·n тактов. Таким образом, быстродействие устройства на базе описанного способа в (2·m·n)/(2·n)=m раз выше по сравнению с быстродействием устройства на базе известного итерационного способа суммирования. Например, при количестве порядков m=64 быстродействие предлагаемого устройства больше в 64 раза.