УСТРОЙСТВО ДЛЯ ВЫРАВНИВАНИЯ ПОРЯДКОВ m ДВОИЧНЫХ ЧИСЕЛ Российский патент 2014 года по МПК G06F5/01 G06F7/38 

Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих функцию выравнивания порядков двоичных чисел путем параллельно-конвейерного нахождения максимального порядка, а затем вычисления разностей между максимальным порядком и остальными порядками 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.

На фиг.5 представлена структурная схема устройства для выравнивания порядков m двоичных чисел в общем виде, где 1 - m-входовой элемент ИЛИ, 2 - блок нахождения максимального порядка, 3 - блок вычитания, CELL1 - ячейки блока нахождения максимального порядка, CELL2 - ячейки блока вычитания, X₁-X_m - m-разрядный информационный вход, Y₁-Y_m - 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-й двоичный позиционный порядок можно представить в виде последовательности бит A_i(a_n,a_n-1,…,a₁), где n - разрядность порядка, i∈[1,m]. Тогда m порядков исходных чисел можно представить в виде матрицы:

Столбцы матрицы с элементами (a_1,j, а_2,j,…,a_m,j) являются входными векторами - разрядными срезами, которые поступают на обработку в заявляемое устройство.

В каждом такте на входы синхронизации всех триггеров подается сигнал синхронизации.

Операция выравнивания порядков состоит из двух этапов.

На первом этапе находится максимальный остаток. Разряды порядков в виде разрядных срезов подаются на 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 раза.

Изобретение относится к вычислительной технике и предназначено для построения однородных вычислительных сред, выполняющих функцию выравнивания порядков двоичных чисел. Техническим результатом является повышение быстродействия за счет параллельно-конвейерного нахождения максимального порядка с помощью анализа разрядных срезов операндов, а затем вычисления разностей максимального порядка и остальных порядков m двоичных чисел. Устройство содержит блок нахождения максимального порядка, состоящий из m-входового элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и m ячеек, каждая из которых включает элементы И, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, информационные триггеры, и блок вычитания, состоящий из m ячеек, каждая из которых включает элементы И, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИЛИ, элемент НЕ, информационные триггеры. 5 ил.

Устройство для выравнивания порядков m двоичных чисел, имеющее m-разрядный вход, вход синхронизации, вход сброса, m-разрядный выход и состоящее из блока нахождения максимального порядка и блока вычитания, где
вход синхронизации устройства для выравнивания порядков m двоичных чисел соединен с входом синхронизации блока нахождения максимального порядка и блока вычитания, вход сброса устройства соединен с входом сброса блока нахождения максимального порядка и блока вычитания,
m-разрядный вход устройства соединен со вторым m-разрядным информационным входом блока вычитания и m-разрядным информационным входом блока нахождения максимального порядка, выход которого соединен с первым информационным входом блока вычитания,
блок нахождения максимального порядка состоит из m-входового элемента ИЛИ и из m ячеек блока нахождения максимального порядка, при этом блок нахождения максимального порядка имеет m-разрядный информационный вход, вход синхронизации, вход сброса, одноразрядный выход,
ячейка блока нахождения максимального порядка состоит из двух двухвходовых элементов И, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, двух информационных триггеров и имеет вход синхронизации, вход сброса, два информационных входа, информационный выход,
вход синхронизации ячейки соединен с входом синхронизации первого триггера и первым входом первого элемента И, выход которого соединен с входом синхронизации второго триггера,
вход сброса ячейки соединен с входом сброса второго триггера,
первый информационный вход ячейки подключен к информационному входу первого триггера, выход которого подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и информационному выходу ячейки,
второй информационный вход ячейки подключен к первому входу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу второго триггера, инверсный выход которого подключен ко второму входу первого элемента И и второму входу второго элемента И,
при этом вход синхронизации блока нахождения максимального порядка соединен с входами синхронизации всех ячеек, вход сброса блока нахождения максимального порядка соединен с входами сброса всех ячеек,
первый информационный вход ячеек блока соединен с соответствующими разрядами m-разрядного информационного входа блока нахождения максимального порядка,
выход каждой i-й ячейки подключен к i-му входу m-входового элемента ИЛИ, выход которого подключен ко второму информационному входу каждой ячейки, где i∈[1, m], причем количество ячеек в блоке нахождения максимального порядка равно m,
выход m-входового элемента ИЛИ соединен с выходом блока нахождения максимального порядка,
блок вычитания состоит из m ячеек блока вычитания и имеет первый m-разрядный информационный вход, второй одноразрядный информационный вход, вход синхронизации, вход сброса, m-разрядный выход,
ячейка блока вычитания состоит из трех двухвходовых элементов И, трех двухвходовых элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, одного двухвходового элемента ИЛИ, одного элемента НЕ, четырех информационных триггеров и имеет вход синхронизации, вход сброса, два информационных входа, информационный выход,
вход синхронизации ячейки блока вычитания соединен с первым входом первого элемента И, выход которого соединен с входом синхронизации первого триггера, вход синхронизации ячейки блока вычитания соединен с входами синхронизации второго, третьего триггера и элемента НЕ, выход которого соединен с входом синхронизации четвертого триггера,
первый информационный вход ячейки блока вычитания подключен к первому входу второго элемента И, выход которого подключен к второму входу элемента ИЛИ,
второй информационный вход ячейки блока вычитания подключен к первому входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен ко второму входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и ко второму входу второго элемента И,
второй информационный вход ячейки блока вычитания подключен к информационному входу первого триггера, выход которого подключен ко второму входу первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,
вход сброса ячейки блока вычитания подключен к входу сброса первого триггера, инверсный выход которого подключен ко второму входу первого элемента И,
первый информационный вход ячейки блока вычитания подключен к первому входу второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к первому входу третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и к первому входу третьего элемента И, выход которого подключен к первому входу элемента ИЛИ, выход которого подключен к информационному входу третьего триггера, выход которого подключен к информационному входу четвертого триггера, выход которого подключен к второму входу третьего элемента И и ко второму входу третьего элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого подключен к информационному входу второго триггера, выход которого является информационным выходом ячейки блока вычитания,
при этом вход синхронизации блока вычитания соединен с входами синхронизации всех ячеек, вход сброса блока вычитания соединен с входами сброса всех ячеек, первый информационный вход блока вычитания соединен с первыми информационными входами всех ячеек блока вычитания, второй информационный вход ячеек блока вычитания соединен с соответствующими разрядами m-разрядного информационного входа блока вычитания, выход ячеек блока вычитания соединен с соответствующими разрядами m-разрядного выхода блока вычитания,
причем количество ячеек в блоке вычитания равно m.