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

Изобретение относится к области обработки информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является упрощение устройства при сохранении высокой скорости выполнения операции. Устройство содержит n=2k бинарных входов битов строки данных, где k-целое положительное число, n выходов значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки Мij, содержащие сумматоры и образующие пирамидальную структуру с k уровнями обработки, где индекс j меняется от 1 до k=log2n и указывает номер уровня обработки, а индекс i меняется от 1 до 2j-1 и указывает номер блока на уровне. 6 з.п. ф-лы, 7 ил.

 

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

Известен многовходовый одноразрядный сумматор (пат. №2047216 Россия, G06F 7/50. Многовходовый одноразрядный сумматор). Многовходовый одноразрядный сумматор содержит К элементов сложения по модулю два (К [log2n] n разрядность входного двоичного слова), выход r-го из которых соединен с r-м выходом сумматора, отличающийся тем, что содержит p мажоритарных элементов (p [n/2]), s-й которых имеет порог, равный 2s, i-й вход сумматора соединен с i-м входом первого элемента сложения по модулю два и 1-м входом s-го мажоритарного элемента, t-й вход j-го элемента сложения по модулю два , , соединен с выходом мажоритарного элемента с порогом t∙2j-1, (k+1)-й выход сумматора соединен с выходом мажоритарного элемента с порогом 2k.

Данный многовходовый одноразрядный сумматор можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n многовходовых одноразрядных сумматоров, при этом общее число используемых в устройстве сумматоров составляет O(n2).

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

Известен метод и устройство для подсчета количества бит с высоким логическим уровнем (пат. №5541865 США, G06F 7/60, 007/50. Method and apparatus for performing a population count operation). Устройство, предназначенное для вычисления числа бит с высоким логическим уровнем элемента данных, включает: первый набор сумматоров с сохранением переноса, состоящий из первого, второго, третьего и четвертого сумматоров, входы которых соединены с входами устройства так, чтобы получить первую, вторую, третью и четвертую битовые части первого элемента данных соответственно, первый и второй сумматоры с сохранением переноса формируют на своих выходах первый многобитовый блок данных, а третий и четвертый сумматоры с сохранением переноса формируют на своих выходах второй многобитовый блок данных; второй набор сумматоров, состоящий из пятого и шестого сумматоров с сохранением переноса, входы которых соединены так, чтобы получить первый и второй многобитовые блоки данных соответственно, пятый и шестой сумматоры с сохранением переноса формируют на своих выходах третий многобитовый блок данных; седьмой сумматор с сохранением переноса, входы которого соединены так, чтобы получить третий многобитовый блок выходных данных, который формирует на своих выходах четвертый многобитовый блок данных; полный сумматор, входы которого соединены так, чтобы получить четвертый многобитовый блок данных, который формирует на своих выходах количество бит с высоким логическим уровнем. Каждый сумматор с сохранением переноса представляет собой 4-2 сумматор с сохранением переноса. Полный сумматор представляет собой четырехбитовый полный сумматор.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом общее число используемых сумматоров составляет O(n2).

Недостатком такого решения является существенное усложнение схемы с параллельной обработкой. При использовании последовательной обработки существенно возрастает время расчета порядковых номеров битов с высоким логическим уровнем.

Известно устройство для расчета количества бит с высоким логическим уровнем (пат. №6754685 США, G06F 5/01, 7/60, 007/00. Dynamic popcount/shift circuit). Устройство выполняет функцию расчета количества бит с высоким логическим уровнем входной строки данных и функцию сдвига данных. Метод, положенный в основу работы устройства, обеспечивает баланс между нагрузкой счетчиков числа бит с высоким логическим уровнем и схем сдвига данных. Это приводит к увеличению скорости выполнения операции. Устройство имеет входы для битов первого вектора, второго вектора, средства для вычисления числа бит с высоким логическим уровнем первого вектора, средства для осуществления операции сдвига множества бит второго вектора на основе результатов расчета числа бит с высоким логическим уровнем первого вектора, средств для формирования третьего вектора, получающегося на основе операции сдвига. Устройство состоит из множества динамических уровней, за которыми следуют статические уровни. На динамических уровнях используются динамические узлы, которые вычисляют величины, зависящие от отдельных бит указателя и разреженного вектора. Устройство расширяется путем повторения базовой схемы, поэтому оно может быть изменено в соответствии с размером указателя и разреженного вектора.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом аппаратурная сложность устройства составляет O(n2).

Недостатком такого решения является существенное усложнение схемы с параллельной обработкой. При использовании последовательной обработки существенно возрастает время расчета порядковых номеров битов с высоким логическим уровнем.

Известно устройство и метод для расчета количества бит с высоким логическим уровнем (пат. №5717616 США, G06F 7/60, 017/00 Computer hardware instruction and method for computing population counts). Устройство предназначено для вычисления числа бит с высоким логическим уровнем в строках большой длины. При этом вся строка разделяется на более мелкие части и для каждой из частей рассчитывается число бит с высоким логическим уровнем. Для ускорения выполнения операции используются сумматоры с сохранением переноса. Устройство состоит из регистра данных, содержащего строку битов, в которой рассчитывается число битов с высоким логическим уровнем, множества полных сумматоров, каждый из которых имеет выход, и суммирует биты с высоким логическим уровнем из уникального набора битов из регистра данных, множества сумматоров с сохранением переноса, каждый из которых имеет выход, и суммирует биты с высоким логическим уровнем из уникального набора битов из аккумулирующего регистра. Каждый из сумматоров с сохранением переноса формирует уникальный набор выходных данных в регистре назначения, где регистр назначения хранит количество бит с высоким логическим уровнем из подмножества бит регистра данных и группу бит из аккумулирующего регистра в формате суммы с сохранением переноса. Множество полных сумматоров образуют иерархическую структуру так, что первый уровень сумматоров рассчитывает число бит с высоким логическим уровнем, хранящихся в регистре данных. Входы полных сумматоров второго уровня соединены с выходами сумматоров первого уровня так, что каждый из сумматоров второго уровня складывает результаты на выходах двух сумматоров первого уровня, причем каждый из выходов сумматора первого уровня соединен с одним входом сумматора второго уровня. Число полных сумматоров первого уровня составляет половину от числа бит в регистре данных, число полных сумматоров на втором уровне составляет четверть от числа бит в регистре данных. Сумматоры с сохранением переноса суммируют одинаковое количество бит. Роль регистра назначения и аккумулирующего регистра выполняет один и тот же регистр.

Данное устройство можно использовать для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n. Но для параллельной обработки необходимо использовать n устройств подсчета количества бит с высоким логическим уровнем, при этом общее число используемых сумматоров составляет O(n2).

Недостатком такого решения является существенное усложнение схемы с параллельной обработкой. При использовании последовательной обработки существенно возрастает время расчета порядковых номеров битов с высоким логическим уровнем.

Задачей настоящего решения является разработка простого устройства с количеством используемых сумматоров не более O(n) для расчета значений порядковых номеров битов и общего числа бит с высоким логическим уровнем в строке данных длиной n бит, обеспечивающего высокое быстродействие за счет параллельной обработки данных.

Техническим результатом является сокращение числа используемых в устройстве сумматоров до 5/2n-2log2(n)-2 при сохранении высокой скорости выполнения операции.

Поставленная задача достигается тем, что устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, согласно решению содержит n=2k бинарных входов битов строки данных Db1, Db2,.…, Dbn, где k - целое положительное число, n выходов Q1, Q2,.…, Qn значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И1, И2…, Иn, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки Mij, образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log2n и указывает номер уровня обработки, а индекс i меняется от 1 до 2l-1 и указывает номер блока на уровне j, каждый блок Mij имеет вход I_NUM1 результатов суммирования с нижнего уровня и выход O_NUM2 результатов суммирования, каждый блок Mij, где j=2,.…, k, i=1, 2, …, 2j-1 дополнительно имеет вход I_NUM2 результатов суммирования с нижнего уровня и выход O_NUM результатов суммирования, передаваемых на верхний уровень, каждый блок Mij, где j=2,.…, k, i=2, 3, …, 2j-1 дополнительно имеет вход I_NUM результатов суммирования с верхнего уровня и выход O_NUM1 результатов суммирования, блок Ml,k дополнительно имеет выход O_NUM1 результатов суммирования, блок Mn/2,k дополнительно имеет выход I_NUM2 результатов суммирования, при этом у блока Mij уровня j, где j=1, 2,.…, k-1, i=1, 2,.…, 2j-1, выход O_NUM1 соединен с входом I_NUM блока M2i-1, j+1 выход O_NUM2 соединен с входом I_NUM блока M2ij+1 вход I_NUM1 соединен с выходом O_NUM блока M2ij+1, вход I_NUM2 соединен с выходом O_NUM блока M2ij+1 у блоков Mi,k последнего уровня k, где k=log2n, i=1, 2,.…, 2k-1 выход O_NUM1 соединен с первым входом X1 логического элемента И2i-1 вход I_NUM1 соединен с входом Db2i-1 устройства и вторым бинарным входом Х2 логического элемента И2i-1, выход логического элемента И2i-1, соединен с выходом Q2i-1 устройства, выход O_NUM2 блока Мi,k соединен с первым входом X1 логического элемента И2i, вход I_NUM2 блока Мi,k соединен с входом Db2i устройства и вторым бинарным входом Х2 логического элемента И2i, выход логического элемента И2i соединен с выходом Q2i, устройства, выход O_NUM2 блока Mn/2,k дополнительно соединен с выходом POPCNT устройства. У блока М11 вход I_NUM1 соединен с выходом O_NUM2. Каждый блок промежуточного уровня Mi,j, где j=2,.…, k-1, i=2j-l, включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход блока I_NUM1 соединен с первым входом сумматора I1, вход I_NUM соединен со вторым входом сумматора I2 и с выходом O_NUM1, выход O_NUM2 соединен с выходом OU сумматора. Каждый блок Ml.j, где j=2,.…, k-1 включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход I_NUM1 соединен с первым входом сумматора I1 и с выходом O_NUM2, вход I_NUM2 соединен со вторым входом сумматора I2, выход O_NUM соединен с выходом OU сумматора. Блок М1,k включает в себя сумматор с первым I1 и вторым I2 входами, и выходом OU, причем вход I_NUM1 соединен с первым входом сумматора I1 и с выходом O_NUM1, вход I_NUM2 соединен со вторым входом сумматора I2, выход O_NUM соединен с выходом OU сумматора и с выходом O_NUM2. Каждый блок Мi,k последнего уровня k, где i=2,.…, n/2, состоит из трех сумматоров, каждый из которых имеет первый I1 и второй I2 входы, и выход OU, причем вход I_NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I_NUM2 соединен со вторым входом I2 первого сумматора, вход I_NUM соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора, выход OU первого сумматора соединен со вторым входом I2 третьего сумматора и с выходом O_NUM при его наличии, выход O_NUM1 соединен с выходом OU второго сумматора, выход O_NUM2 соединен с выходом OU третьего сумматора. Каждый блок промежуточного уровня Mi,j, где j=2,.…, k-1, i=2, 3,.…, 2j-1-1 состоит из двух сумматоров, имеющих первый I1 и второй I2 входы, и выход OU, причем вход I_NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I_NUM2 соединен со вторым входом I2 первого сумматора, вход I_NUM соединен с вторым входом I2 второго сумматора и с выходом O_NUM1, выход O_NUM соединен с выходом OU первого сумматора, выход O_NUM2 соединен с выходом OU второго сумматора.

Изобретение поясняется чертежами, где на фиг.1 приведена структурно-функциональная схема устройства для расчета порядковых номеров битов с высоким логическим уровнем в строке данных длиной n=8, на фиг.2 приведена схема блоков Мi,k последнего уровня преобразования k, где k=log2n, i=2, 3,.…, 2k-1, на фиг.3 приведена схема блоков промежуточного уровня Мs,t, где 1<t<k, a 1<s<2t-1, на фиг.4 приведена схема блоков М1,m, где 1<m<k, на фиг.5 приведена схема блоков Mpq, где q=2,.…, k-1, p=2q-1, на фиг.6 приведена схема блока М1,k, на фиг.7 приведена схема блока Mn/2,k, где

М11 - первый блок первого уровня;

М12, М22 - первый и второй блоки второго уровня;

M13, М23, M33, M43 - первый, второй, третий и четвертый блоки третьего уровня;

И1- И8 - логические элементы И;

X1 - первый вход логического элемента И;

Х2 - второй бинарный вход логического элемента И;

Y - выход логического элемента И;

O_NUM - выход результатов суммирования, передаваемых на верхний уровень;

O_NUM1, O_NUM2 - первый и второй выходы результатов суммирования, передаваемых на нижний уровень;

I_NUM - вход результатов суммирования с верхнего уровня;

I_NUM1, I_NUM2 - первый и второй входы результатов суммирования с нижнего уровня;

Q1, Q2, Q3, Q4, Q5, Q6, Q7, Q8 - выходы значений порядковых номеров битов с высоким логическим уровнем;

Db1, Db2, Db3, Db4, Db5, Db6, Db7, Db8 - бинарные входы битов входной строки данных;

POPCNT - выход суммы битов с высоким логическим уровнем;

ADD - сумматор;

I1, I2 - входы сумматора;

OU - выход сумматора.

В общем случае предлагаемое устройство имеет n бинарных входов для получения битов входной строки данных, n выходов результатов расчета порядковых номеров битов с высоким логическим уровнем, выход результатов расчета количества битов с высоким логическим уровнем. Предлагаемое устройство содержит вычислительные блоки Mi,j, образующие пирамидальную структуру с k=log2n уровнями обработки, причем индекс i меняется от 1 до 2j-1 и указывает номер блока на уровне, а индекс j меняется от 1 до k и указывает номер уровня обработки. Таким образом, на первом уровне (j=1) расположен единственный блок М11, на втором уровне расположено два блока, на третьем - четыре и так далее до последнего уровня (j=k), содержащего n/2 блоков. Устройство также содержит n элементов логического умножения И1, И2…, Иn, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, при этом число на выходе Y равно числу на входе Х1, если на входе Х2 высокий логический уровень, если на входе Х2 низкий логический уровень, то число на выходе Y равно нулю.

Блоки Mi,j разделяются на семь типов.

1. Блок М11 имеет вход I_NUM1 и выход J_NUM2, которые соединены между собой.

Остальные блоки состоят из сумматоров ADD, каждый из которых имеет первый I1 и второй I2 входы для подачи суммируемых чисел и выход OU, на котором формируется сумма чисел, подаваемых на входы I1 и I2.

2. Блоки Mi,k последнего уровня преобразования k, где k=log2n, i=2, 3,.…, 2k-l-1 состоят из трех сумматоров ADD. Схема блоков Mi,k приведена на фиг.2. Блоки Мi,k имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока Mi,k соединен с первым входом I1 первого сумматора и со вторым входом I2 второго сумматора. Вход I_NUM2 блока Mi,k соединен со вторым входом I2 первого сумматора. Вход I_NUM блока Mi,k соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора. Выход O_NUM блока Mi,k соединен с выходом OU первого сумматора и со вторым входом I2 третьего сумматора. Выход O_NUM1 блока Mi,k соединен с выходом OU второго сумматора. Выход O_NUM2 блока Mi,k соединен с выходом OU третьего сумматора. На фиг.1 блоки М23, М33 соответствуют описанию блока Mi,k, схема которого представлена на фиг.2.

3. Блоки Ms,t промежуточного уровня преобразования t, где 1<t<k, a 1<s<2t-1 состоят из двух сумматоров ADD. Схема блоков Ms,t приведена на фиг.3. Блоки Ms,t имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока Ms,t соединен с первым входом I1 первого сумматора и со первым входом I1 второго сумматора. Вход I_NUM2 блока Ms,t соединен со вторым входом I2 первого сумматора. Вход I_NUM блока Ms,t соединен со вторым входом I2 второго сумматора и с выходом O_NUM1 блока M Ms,t. Выход O_NUM блока Ms,t соединен с выходом OU первого сумматора. Выход O_NUM2 блока Ms,t соединен с выходом OU второго сумматора. На фиг.1 не изображены блоки, которые соответствуют описанию блоков Ms,t, схема которых представлена на фиг.3, так как эти блоки появляются при длине входной строки данных n более восьми бит.

4. Блоки М1m промежуточного уровня преобразования m, где 1<m<k состоят из одного сумматора ADD. Схема блоков М1m приведена на фиг.4. Блоки М1,m, имеют выход результатов суммирования, передаваемых на верхний уровень O_NUM, выход O_NUM2 результатов суммирования, передаваемых на нижний уровень, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока М1,m соединен с первым входом I1 сумматора и с выходом O_NUM2. Вход I_NUM2 блока М1,m соединен со вторым входом I2 сумматора. Выход O_NUM блока М1,m соединен с выходом OU сумматора. На фиг.1 блок MI2 соответствуют описанию блока М1m, схема которого представлена на фиг.4.

5. Блоки Mp,q промежуточного уровня преобразования q, где 1<q<k, p=2q-1 состоят из одного сумматора ADD. Схема блоков Mp,q приведена на фиг.5. Блоки Mp,q имеют первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход результатов суммирования с нижнего уровня I_NUM1, вход I_NUM результатов суммирования с верхнего уровня. Вход I_NUM1 блока Mp.q соединен с первым входом I1 сумматора. Вход I_NUM блока Mp,q соединен со вторым входом I2 сумматора и с выходом O_NUM1 блока Mp,q. Выход O_NUM2 блока Mp.q соединен с выходом OU сумматора. На фиг.1 блок М22 соответствуют описанию блока Mp,q, схема которого представлена на фиг.5.

6. Блок M1,k последнего уровня преобразования k, где k=log2n, состоит из одного сумматора ADD. Схема блока М1,k приведена на фиг.6. Блок M1,k имеет выход результатов суммирования, передаваемых на верхний уровень O_NUM, первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока M1,k соединен с первым входом I1 сумматора блока M1,k и с выходом O_NUM1 блока M1,k. Вход I_NUM2 блока M1,k соединен со вторым входом I2 сумматора блока M1,k. Выход O_NUM блока M1,k соединен с выходом OU сумматора блока M1,k и с выходом O_NUM2 блока Mi,k. На фиг.1 блок M13 соответствует описанию блока М1,k, схема которого представлена на фиг.6.

7. Блок Mn/2,k последнего уровня преобразования k, где k=log2n, состоит из трех сумматоров ADD. Схема блока Mn/2,k приведена на фиг.7. Блок Mn/2,k имеет первый O_NUM1 и второй O_NUM2 выходы результатов суммирования, передаваемых на нижний уровень, вход I_NUM результатов суммирования с верхнего уровня, первый I_NUM1 и второй I_NUM2 входы результатов суммирования с нижнего уровня. Вход I_NUM1 блока Mn/2,k соединен с первым входом I1 первого сумматора и с первым входом I1 второго сумматора. Вход I_NUM2 блока Mn/2,k соединен со вторым входом I2 первого сумматора. Вход I_NUM блока Mn/2,k соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора. Выход OU первого сумматора блока Mn/2,k соединен со вторым входом I2 третьего сумматора. Выход O_NUM1 блока Mn/2,k соединен с выходом OU второго сумматора. Выход O_NUM2 блока Mn/2,k соединен с выходом OU третьего сумматора. На фиг.1 блок М43 соответствует описанию блока Mn/2,k, схема которого представлена на фиг.7.

Соединения между блоками устройства следующие.

Если у блока Мр,m уровня m, где m=1, 2,.…, k-1; р=1, 2,.…, 2m-1 существует выход O_NUM1, то он соединен с входом I_NUM блока M2p-1, m+1 уровня m+1. Выход O_NUM2 блока Мр,m уровня m соединен с входом I_NUM блока М2р,m+1 уровня m+1. Вход I_NUM1 блока Мр,m уровня m соединен с выходом O_NUM блока M2p-1, m+1 уровня m+1, если у блока Мр,m уровня m существует вход I_NUM2, то он соединен с выходом O_NUM блока М2р,m+1 уровня m+1. Выход O_NUM1 каждого блока Mi,k последнего уровня k, где k=lоg2n, a i=1, 2,.…, 2k-1 соединен с первым входом X1 логического элемента И2i-1, вход I_NUM1 блока Мi,k соединен с входом Db2i-1 устройства и вторым бинарным входом Х2 логического элемента И2i-1, выход логического элемента И2p-1 соединен с выходом Q2p-1 устройства, выход O_NUM2 блока Мi,k последнего уровня k, где k=log2n, i=1, 2,.…, 2k-l, соединен с первым входом X1 логического элемента И2i, вход I_NUM2 блока Мi,k соединен с входом Db2i устройства и вторым бинарным входом Х2 логического элемента И2i, выход логического элемента И2i соединен с выходом Q2i устройства. Выход O_NUM2 блока Мn/2,k дополнительно соединен с выходом POPCNT суммы битов с высоким логическим уровнем во входной строке данного устройства.

Устройство работает следующим образом. На бинарные входы Db1, Db2,.…, Dbn устройства для расчета порядковых номеров битов с высоким логическим уровнем поступают биты входной строки данных. Через время задержки t3 на выходах Q1, Q2,.…, Qn, устройства появляются значения порядковых номеров битов с высоким логическим уровнем во входной строке данных. Скорость выполнения операции зависит от типа используемых сумматоров. Если задержка сумматора не зависит от числа суммируемых разрядов и равна τ, задержка t3 выполнения предлагаемым устройством расчета порядковых номеров битов с высоким логическим уровнем составляет tз=2τ(log2(n)-1). Задержка формирования результата на выходе POPCNT также равна tз.

В блоках Mi,j могут использоваться сумматоры с сохранением переноса, сумматоры со сквозным переносом, сумматоры с ускоренным переносом и другие сумматоры, описанные, например, в книге Жан М. Рабаи, Ананта Чандракасан, Боривож Николич. Цифровые интегральные схемы. Методология проектирования. М.: Вильямс, 2007, 912 с. При расчете порядковых номеров битов с высоким логическим уровнем в n разрядной строке данных используются схемы для суммирования входных данных с числом разрядов от 1 до lоg2n.

В блоках Mi,j могут использоваться сумматоры, суммирующие входные данные по модулю 2. В этом случае устройство определяет четность или нечетность порядкового номера бита с высоким логическим уровнем в строке данных. В общем случае, если в блоках Mi,j используются сумматоры, суммирующие входные данные по модулю d, порядковые номера битов с высоким логическим уровнем в строке данных также будут вычисляться по модулю d.

Число разрядов суммируемых величин в блоках различно. У блока Мр,m уровня m, где m=1, 3,.…, k; p=1, 2,.…, 2m-1 выход O_NUM1 имеет число двоичных разрядов, равное int(log2(p))+k-m+1, где функция int(log2(p)) вычисляет ближайшее целое число, большее чем log2(p), а выходы O_NUM2 и O_NUM имеют число двоичных разрядов, равное int(log2(p))+k-m+2. Таким образом, последний сумматор последнего уровня, формирующий результат на выходе O_NUM2, имеет k+1 разряд. У блока Мр,m уровня m, где m=1, 3,.…, k; р=1, 2,.…, 2m-1 входы I_NUM1, I_NUM2 имеют число двоичных разрядов, равное k-m+1. В блоках Мр,m можно использовать одинаковые сумматоры с числом разрядов суммируемых чисел, равным k, но при этом часть старших разрядов части сумматоров не будет использоваться.

Заметим, что устройство можно использовать при значениях длины входной строки данных n, отличной от степени числа 2. При этом используется только часть блоков, на которые поступают биты строки входных данных. Неиспользуемые блоки и логические элементы Иi можно исключить из устройства.

Таким образом, устройство выполняет расчет порядковых номеров битов с высоким логическим уровнем входной бинарной строки данных. Одновременно с расчетом порядковых номеров битов устройство осуществляет расчет количества битов с высоким логическим уровнем во входной строке данных. Устройство характеризуется небольшим числом используемых сумматоров. Аппаратурная сложность устройства, определяемая количеством используемых сумматоров, составляет 5/2n-2log2(n)-2, где n - число бит входной строки данных. Это значительно меньше количества сумматоров, необходимого для расчета порядковых номеров битов с высоким логическим уровнем с использованием n устройств расчета количества бит с высоким логическим уровнем. Обработка данных в предлагаемом устройстве выполняется параллельно, что обеспечивает высокую скорость выполнения операции.

1. Устройство для расчета порядковых номеров битов с высоким логическим уровнем в строке данных, характеризующееся тем, что оно содержит n=2k бинарных входов битов строки данных Db1, Db2, …, Dbn, где k - целое положительное число, n выходов Q1, Q2, …, Qn значений порядковых номеров битов с высоким логическим уровнем в строке данных, выход POPCNT числа битов с высоким логическим уровнем в строке данных, n элементов логического умножения И1, И2,…, Иn, каждый из которых имеет выход Y, первый вход X1 и второй бинарный вход Х2, и формирует на выходе Y результат умножения данных на входах X1 и Х2, вычислительные блоки Mq, образующие структуру с k уровнями обработки, где индекс j меняется от 1 до k=log2n и указывает номер уровня обработки, а индекс i меняется от 1 до 2j-1 и указывает номер блока на уровне j, каждый блок Мij имеет вход I-NUM1 результатов суммирования с нижнего уровня и выход 0-NUM2 результатов суммирования, каждый блок Mi,j, где j=2, …, k, i=1, 2, …, 2j-i-1 дополнительно имеет вход I-NUM2 результатов суммирования с нижнего уровня и выход O-NUM результатов суммирования, передаваемых на верхний уровень, каждый блок Mi,j, где j=2, …, k, i=2, 3, …, 2j-1 дополнительно имеет вход I-NUM результатов суммирования с верхнего уровня и выход O-NUM1 результатов суммирования, блок M1,k дополнительно имеет выход O-NUM1 результатов суммирования, блок Mn/2,k дополнительно имеет выход I-NUM2 результатов суммирования, при этом у блока Мij уровня j, где j=1, 2, …, k-1, i=1, 2, …, 2j-1, выход O-NUM1 соединен с входом I-NUM блока М2i+1, j+i, выход O-NUM2 соединен с входом I-NUM блока М2i, j+i, вход I-NUM1 соединен с выходом O-NUM блока M2i-1, j+i, вход I-NUM2 соединен с выходом O-NUM блока М2i,j+1, у блоков Мi,k последнего уровня k, где k=log2n, i=1, 2, …, 2k-1, выход O-NUM1 соединен с первым входом X1 логического элемента И2i-1, вход I-NUM1 соединен с входом Db2i-i устройства и вторым бинарным входом Х2 логического элемента И2i-1, выход логического элемента И2i-1 соединен с выходом Q2i-1 устройства, выход O-NUM2 блока Mi,k соединен с первым входом X1 логического элемента И2i, вход I-NUM2 блока Мi;k соединен с входом Db2i устройства и вторым бинарным входом Х2 логического элемента И2i, выход логического элемента И2i соединен с выходом Q2i устройства, выход O-NUM2 блока Mn/2,k дополнительно соединен с выходом POPCNT устройства.

2. Устройство по п.1, характеризующееся тем, что у блока М11 вход I-NUM1 соединен с выходом O-NUM2.

3. Устройство по п.1, характеризующееся тем, что каждый блок промежуточного уровня Mi,j, где j=2, …, k-1, i=2j-1, включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход блока I-NUM1 соединен с первым входом сумматора I1, вход I-NUM соединен со вторым входом сумматора I2 и с выходом O-NUM1, выход O-NUM2 соединен с выходом OU сумматора.

4. Устройство по п.1, характеризующееся тем, что каждый блок Мi,j, где j=2, …, k-1 включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход I-NUM1 соединен с первым входом сумматора I1 и с выходом O-NUM2, вход I-NUM2 соединен со вторым входом сумматора I2, выход O-NUM соединен с выходом OU сумматора.

5. Устройство по п.1, характеризующееся тем, что блок M1,k включает в себя сумматор с первым I1 и вторым I2 входами и выходом OU, причем вход I-NUM1 соединен с первым входом сумматора I1 и с выходом O-NUM1, вход INUM2 соединен со вторым входом сумматора I2, выход O-NUM соединен с выходом OU сумматора и с выходом O-NUM2.

6. Устройство по п.1, характеризующееся тем, что каждый блок Мi,k последнего уровня k, где i=2, …, n/2, состоит из трех сумматоров, каждый из которых имеет первый I1 и второй I2 входы, и выход OU, причем вход I-NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I-NUM2 соединен со вторым входом I2 первого сумматора, вход I-NUM соединен со вторым входом I2 второго сумматора и с первым входом I1 третьего сумматора, выход OU первого сумматора соединен со вторым входом I2 третьего сумматора и с выходом O-NUM при его наличии, выход O-NUM1 соединен с выходом OU второго сумматора, выход O-NUM2 соединен с выходом OU третьего сумматора.

7. Устройство по п.1, характеризующееся тем, что каждый блок промежуточного уровня Mi,j, где j=2, …, k-1, i=2, 3, …, 2j-1-1, состоит из двух сумматоров, имеющих первый I1 и второй I2 входы и выход OU, причем вход I-NUM1 соединен с первыми входами I1 первого и второго сумматоров, вход I-NUM2 соединен со вторым входом I2 первого сумматора, вход I-NUM соединен со вторым входом I2 второго сумматора и с выходом O-NUM1, выход O-NUM соединен с выходом OU первого сумматора, выход O-NUM2 соединен с выходом OU второго сумматора.



 

Похожие патенты:

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике и может быть ис . .

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов , проверочные матрицы которых содержат элементы конечных полей GF(2m).

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

Изобретение относится к вычислительной технике, Цель изобретения - упрощение устройства. .

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых [ni]f(2n) и [mi ]f(2n) с применением арифметических аксиом троичной системы счисления f(+1,0,-1).

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств для выполнения арифметических процедур суммирования позиционных аргументов [ni]f(2n) и [mi]f(2n ).

Изобретение относится к вычислительной технике и может быть использовано при построении надежных, портативных, многоразрядных, быстродействующих сумматоров и АЛУ.

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнения арифметических операций логического суммирования позиционных аргументов аналоговых сигналов [ni]f(2n ) и [mi]f(2n) с применением арифметических аксиом троичной системы счисления f(+1,0,-1).

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

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

Изобретение относится к вычислительной технике и может быть использовано при построении многоразрядных быстродействующих сумматоров и АЛУ. .

Изобретение относится к вычислительной технике и может быть использовано при построении арифметических устройств и выполнения арифметических процедур суммирования позиционных аргументов аналоговых сигналов слагаемых [ni]f(2n) и [mi ]f(2n) с применением арифметических аксиом троичной системы счисления f(+1,0,-1).

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

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

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