Устройство управляемой перестановки информации, хранимой в эвм

Авторы патента:

G06F7/24 - сортировка, т.е. отбор данных с одного или нескольких носителей информации, перегруппировка этих данных в определенную числовую или иную последовательность и перезапись отсортированных данных на этих же или других носителях информации (G06F 7/36 имеет преимущество)

Владельцы патента RU 2405187:

Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)

Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков данных. Устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети. 2 ил.

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

Известен дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ (см. патент РФ №2320000, МПК G06F 7/76). Дешифратор содержит К уровней узлов дешифрации, каждый уровень дешифрации содержит 2ⁱ элементов , регистр управляющих кодов, сдвиговый регистр данных, двойной буферный регистр накопления и хранения форматированных данных, блок управления, генератор тактовых импульсов. Вход выборки дешифратора соединен с первыми входами первого и второго элементов первого уровня. Элемент первого уровня реализует логическую функцию , остальные элементы реализуют логическую функцию . Вход Х элемента первого уровня соединен с выходом первого бита регистра управляющих кодов, входы X₁ остальных элементов i-го уровня соединены с выходом i-ro бита регистра управляющих кодов, входы X₂ остальных элементов i-ro уровня соединены с выходами элементов i-1 уровня, причем вход двойного буферного регистра накопления и хранения форматированных данных соединен с выходом сдвигового регистра данных, а входы разрешения записи этого регистра соединены с выходами последнего уровня дешифрации. Генератор тактовых импульсов соединен с блоком управления, который своими входами и выходами соединен с буферным регистром накопления и хранения форматированных данных, входным сдвиговым регистром данных, регистром управляющих кодов.

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

Известны сортирующие сети Бетчера ("Sorting Networks and Their Applications", К.E.Batcher, Proceedings of 1968 Spring Joint Computer Conference, pp.307-314, 1968). Данные устройства осуществляют быструю сортировку 2^p элементов данных за 1/2р(1+р) шагов, но не обеспечивают перестановку данных, управляемую внешним кодом.

Известна модифицированная сеть Бетчера для сортировки несортированных входных сигналов за log₂N последовательных проходов. Сеть строится рекурсивно от размера 4 до произвольного размера. Модифицированная сеть Бетчера сортирует N элементов данных за log₂N последовательных проходов через сеть, где N - число элементов данных для каждого прохода. Сеть имеет задержку на log₂N компараторах (см. патент US №5319788, МПК G06F 7/36; G06F 7/22).

Однако данная сеть не обеспечивает управляемую внешним кодом перестановку входных данных.

Известно устройство для осуществления управляемых перестановок, которое состоит из двух сетей типа «Butterfly» одинакового размера, соединенных одна с другой (back-to-back). Управление осуществляется программно с помощью процессора.

Недостатком данного устройства является программное управление перестановками, которое осуществляется процессором и приводит к замедлению работы системы (см. патент US №6922472, МПК H04L 9/34).

Задачей настоящего решения является упрощение и ускорение процесса управления перестановками при минимизации элементов устройства.

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

Поставленная задача достигается тем, что устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.

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

где

1. устройство управляемой перестановки;

2. ячейки сортирующей сети;

Х1, Х2,…, Хn - n входов данных;

Y1, Y2,…, Yn - n выходов данных;

IC1, IC2,…, IСn - n входов управляющих кодов;

ОС1, ОС2,…, ОСn-n выходов управляющих кодов;

π(1,2,…, n) - перестановка управляющих кодов;

(1,2,…, n) - отсортированные управляющие коды;

(x₁, х₂,…, х_n) - входные данные;

π(х₁, х₂,…, х_n) - выходные данные;

X₁, X₂ - первый и второй входы данных транспозиционных элементов;

Y1, Y₂ - первый и второй выходы данных транспозиционных элементов;

IC₁, IC₂ - первый и второй входы компараторов;

OC₁, OC₂ - первый и второй выходы компараторов;

IC1, IC2, IC3, IC4 - входы управляющих кодов;

OC1, OC2, ОС3, ОС4 - выходы управляющих кодов;

X1, Х2, Х3, Х4 - входы данных;

Y1, Y2, Y3, Y4 - выходы данных.

Предлагаемое устройство включает в себя сортирующую сеть 1, в узлах которой находятся ячейки 2, состоящие из компаратора сортирующей сети и транспозиционного элемента управляемой перестановки данных. Компаратор сортирующей сети имеет управляющий выход (на чертежах не показан), два входа IC₁, IC₂ и два выхода OC₁, OC₂. Транспозиционный элемент имеет вход управления, входы X₁, Х₂ и выходы Y₁, Y₂. В каждой ячейке управляющий выход компаратора соединен с входом управления транспозиционного элемента.

Соединения выходов OC₁ и входов IC₁, выходов ОС₂ и входов IC₂ компараторов определяются топологией используемой сортирующей сети. Соединения IC1,IC2,…, ICn входов управляющих кодов с входами компараторов входных ячеек сортирующей сети определяются топологией используемой сортирующей сети. Соединения ОС1,ОС2,…, ОСn выходов управляющих кодов с выходами компараторов выходных ячеек сортирующей сети определяются топологией используемой сортирующей сети.

Если выход ОС₁ компаратора одной ячейки сортирующей сети соединен с входом IC₁ компаратора другой ячейки сортирующей сети, то вход X₁ транспозиционного элемента одной ячейки соединен с выходом Y₁ другой ячейки. Если выход ОС₂ компаратора одной ячейки сортирующей сети соединен с входом IC₂ компаратора другой ячейки сортирующей сети, то вход Х₂ транспозиционного элемента одной ячейки соединен с выходом Y₂ другой ячейки. Если выходы OC₁, OC₂ выходной ячейки сортирующей сети являются выходами управляющих кодов устройства, то входы X₁, Х₂ транспозиционного элемента этой ячейки являются входами данных. Если входы IC₁, IС₂ входной ячейки сортирующей сети являются входами управляющих кодов устройства, то выходы Y₁, Y₂ транспозиционного элемента этой ячейки являются выходами данных.

Устройство работает следующим образом. На n входов управляющих кодов IC1,IC2,…, ICn, образованных входами компараторов IС₁, IС₂ устройства, подаются входные управляющие коды, представляющие собой перестановку чисел натурального ряда π(1,2,…, n). На n входов данных Х1,Х2,…, Хn, образованных входами транспозиционных элементов Х₁, Х₂ устройства, подаются входные данные (x₁,x₂,…, x_n). Через время задержки τ, на n выходах данных Y1,Y2,…, Yn, образованных выходами транспозиционных элементов устройства, появляются выходные данные, представляющие собой перестановку π(х₁,х₂,…, х_n). Время задержки τ определяется количеством элементов на пути распространения сигналов управления и данных. Если значение кода на входе компаратора IC₁ больше или равно значения кода на входе компаратора IC₂, то значение кода поступает с входа IC₁ на выход OC₁, а значение кода на входе IC₂ поступает на выход ОС₂. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X₁ поступают на выход Y₁; а перестанавливаемые данные на входе Х₂ поступают на выход Y₂.

Если значение кода на входе компаратора IС₁ меньше значения кода на входе компаратора IC₂, то значение кода поступает с входа IC₁ на выход ОС₂, а значение кода на входе IC₂ поступает на выход OC₁. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X₁ поступают на выход Y₂; а перестанавливаемые данные на входе Х₂ поступают на выход Y₁.

Таким образом, перестановка входного вектора данных (х₁,х₂,…, х_n) в соответствии с входными управляющими кодами π(1,2,…, n) выполняется параллельно, что обеспечивает высокую скорость преобразования. Число ячеек устройства зависит от топологии используемой сортирующей сети и для сетей Бетчера составляет O(n·(log₂ n)²). Это число растет практически линейно с ростом n, что делает технически возможным управляемую перестановку больших блоков данных.

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

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

Устройство и способ редактирования // 2252448

Изобретение относится к устройству и способу редактирования. .

Устройство для выбора оптимальных решений методом наименьших расстояний // 2234732

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

Устройство обращения циклического сдвига и обращенного перемежения данных // 2189629

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

Многоканальное устройство для выбора минимального значения средней величины // 920740

Многоканальное устройство для выбора минимального значения средней величины // 744610

Устройство для упорядочивания объектов // 467346

Устройство для сдвига информации // 458824

Устройство для преобразования статистической информации, вводимой в запоминающее устройство // 398944

Преобразователь цифрового кода в единичный // 269602

Конвейер классификации данных, включающий в себя правила автоматической классификации // 2544752

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

Способ предоставления информационной поддержки разработчика программного обеспечения для микроконтроллеров и реализующая его система // 2553067

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

Способ и устройство для отображения прикладного программного обеспечения // 2636133

Изобретение относится к средствам для отображения прикладного программного обеспечения. Технический результат заключается в повышении точности ранжирования прикладного программного обеспечения. Получают по меньшей мере два параметрических коэффициента, указывающих информацию о прикладном программном обеспечении в течение установленного периода. Выводят индекс сортировки прикладного программного обеспечения в результате вычисления на основе по меньшей мере двух полученных параметрических коэффициентов. Сортируют прикладное программное обеспечение в соответствии с индексом сортировки и представление отсортированного прикладного программного обеспечения. При этом получение по меньшей мере двух параметрических коэффициентов, указывающих информацию о прикладном программном обеспечении в течение установленного периода, представляет собой: получение значения количества загрузок прикладного программного обеспечения в течение установленного периода и выполнение обработки значения количества загрузок путем умножения значения количества загрузок на (1/2)T, где Т - установленный период времени, с получением таким образом коэффициента количества загрузок, указывающего информацию о прикладном программном обеспечении в течение установленного периода. 2 н. и 14 з.п. ф-лы, 6 ил.