Спецпроцессор для задачи выполнимости булевых формул

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

Уваров Сергей Иванович (RU)

G06F17/00 - Устройства или методы цифровых вычислений или обработки данных, специально предназначенные для специфических функций

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

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук (RU)

Изобретение относится к вычислительной технике, в частности к специализированным процессорам с высокой степенью параллелизма. Технический результат заключается в снижении сложности спецпроцессора и повышении скорости решения задачи о выполнимости булевых функций за счет упрощения структуры спецпроцессора, основой которого является сумматор-аккумулятор, приоритетная цепочка и матрица, содержащая N×M однотипных ячеек (CELL). Технический результат достигается тем, что спецпроцессор для задачи выполнимости булевых формул содержит N-разрядный сумматор-аккумулятор, вход сброса которого является входом сброса спецпроцессора, вход синхронизации является входом синхронизации спецпроцессора, вход разрешения записи является первым управляющим входом спецпроцессора; первый и второй дешифраторы, m-разрядный и k-разрядный информационные входы которых являются соответственно первым и вторым информационными входами спецпроцессора, а управляющий вход второго дешифратора является вторым управляющим входом спецпроцессора. 8 ил.

Изобретение относится к вычислительной технике, в частности к специализированным процессорам с высокой степенью параллелизма. Спецпроцессор предназначен для решения задачи о выполнимости булевых функций, заданных в конъюнктивной нормальной форме (CNF), имеющих N=2^k переменных и до М=2^m дизъюнкций (CLAUSE).

Известен параллельный спецпроцессор для решения задач о выполнимости булевых формул, реализуемый на реконфигурируемой аппаратуре. Спецпроцессор решает задачу выполнимости, используя параллельные аппаратурно-реализованные обратные связи (parallel backtrace). Спецпроцессор содержит блок управления и синхронизации, а также блоки логики переменных, литералов и дизъюнкций (US 6292916 B1, 18.09.2001).

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

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

Известен высокопараллельный спецпроцессор для решения задач о выполнимости булевых формул, наиболее близкий по своей технической сущности к предлагаемому изобретению и выбранный в качестве прототипа. Данный спецпроцессор содержит интерфейсный блок, устройство управления и процессорный блок, выполненный в виде матрицы. Процессорный блок является устройством параллельной записи и считывания с многоразрядным адресным входом, входом сброса и одним выходом. Для перебора возможных значений переменных в спецпроцессоре используется счетчик (RU 2074415 С1, 27.02.1997).

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

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

Технический результат изобретения - снижение сложности спецпроцессора, и повышение скорости решения задачи о выполнимости булевых функций. Технический результат достигается упрощением структуры спецпроцессора, основой которого является сумматор-аккумулятор, приоритетная цепочка и матрица, содержащая N×M однотипных ячеек (CELL). После записи информации об анализируемой булевой формуле в триггеры ячеек матрицы спецпроцессор функционирует как сумматор-аккумулятор, имеющий обратную связь выхода с входом, т.е. как конечный автомат с простейшей структурой. Время решения задачи сокращается благодаря приоритетной цепочке, позволяющей (когда это возможно) в каждом такте работы спецпроцессора отбрасывать значительное число неперспективных наборов переменных.

Технический результат достигается тем, что предлагаемый спецпроцессор содержит N-разрядный сумматор-аккумулятор, вход сброса которого является входом сброса спецпроцессора, вход синхронизации является входом синхронизации спецпроцессора, вход разрешения записи является первым управляющим входом спецпроцессора, а информационный вход подключен к выходу приоритетной цепочки; первый и второй дешифраторы, m-разрядный и k-разрядный информационные входы которых являются соответственно первым и вторым информационными входами спецпроцессора, а управляющий вход второго дешифратора является вторым управляющим входом спецпроцессора; М последовательно пронумерованных блоков дизъюнкции (CLAUSE), каждый из которых содержит первый элемент «ИЛИ» и N последовательно пронумерованных ячеек (CELL), каждая из которых содержит первый RS-триггер, D-триггер, элемент суммирования по модулю два, первый, второй и третий элементы «И», второй и третий элементы «ИЛИ»; причем в каждой ячейке выход первого элемента «И» соединен с входом разрешения D-триггера и установочным входом первого RS-триггера, выход которого соединен с первыми входами второго элемента «И» и второго элемента «ИЛИ», выход которого соединен с первым входом третьего элемента «И», выход которого, в свою очередь, соединен с первым входом третьего элемента «ИЛИ», второй вход второго элемента «И» подключен к выходу элемента суммирования по модулю два, первый вход которого подключен к выходу D-триггера; в каждом блоке дизъюнкции вторые входы третьих элементов «И» подключены к инверсному выходу первого элемента «ИЛИ», второй вход второго элемента «ИЛИ» и инверсный вход третьего элемента «И» младшей ячейки блока обнулены, а соответствующие входы второго элемента «ИЛИ» и третьего элемента «И» каждой из остальных ячеек блока подключены к выходу второго элемента «ИЛИ» предшествующей ячейки; вторые входы элементов суммирования по модулю два ячеек, имеющих в блоках дизъюнкции одинаковый номер, подключены к разряду с соответствующим номером N-разрядного информационного выхода сумматора-аккумулятора, одновременно являющегося первым выходом спецпроцессора; вторые входы третьих элементов «ИЛИ» ячеек блока дизъюнкции, имеющего младший номер обнулены, а вторые входы третьих элементов «ИЛИ» ячеек остальных блоков дизъюнкции подключены к выходам третьих элементов «ИЛИ» соответствующих по номеру ячеек предшествующего блока дизъюнкции, при этом выход третьего элемента «ИЛИ» каждой из ячеек старшего блока дизъюнкции соединен с соответствующим разрядом входа приоритетной цепочки и с одним из входов четвертого элемента «ИЛИ», инверсный вход которого подключен к первому управляющему входу спецпроцессора, а инверсный выход является вторым выходом спецпроцессора; информационные входы всех D-триггеров соединены и являются третьим информационным входом спецпроцессора; первые входы первых элементов «И» одноименных ячеек всех блоков дизъюнкции подключены к соответствующему разряду N-разрядного выхода второго дешифратора, а все вторые входы первых элементов «И» ячеек блока дизъюнкции объединены и подключены к разряду, соответственно номеру блока дизъюнкции, M-разрядного выхода первого дешифратора; выход переноса сумматора-аккумулятора подключен к установочному входу второго RS-триггера, выход которого является третьим выходом спецпроцессора; кроме того, входы сброса и синхронизации всех триггеров подключены к входу сброса и к входу синхронизации спецпроцессора.

На фиг.1 представлена схема спецпроцессора, содержащего М блоков однотипных блоков дизъюнкции (CLAUSE).

На фиг.2 приведена схема блока дизъюнкции, содержащего N однотипных ячеек (CELL).

На фиг.3 приведена схема ячейки (CELL) предлагаемого спецпроцессора.

На фиг.4 приведена временная диаграмма, иллюстрирующая функционирование спецпроцессора при обработке формулы, не имеющей выполняющего набора переменных.

На фиг.5 приведена временная диаграмма, иллюстрирующая функционирование спецпроцессора при обработке формулы, имеющей выполняющий набор переменных.

На фиг.6 представлена таблица 1, содержащая 18 дизъюнкций, из которых скомпонованы формулы в примерах, использованных при описании функционирования спецпроцессора.

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

На фиг.8 представлен вариант схемы управления спецпроцессором.

Предлагаемый спецпроцессор для задачи выполнимости булевых формул содержит N-разрядный сумматор-аккумулятор 1, вход сброса которого является входом 2 сброса спецпроцессора, вход синхронизации является входом 3 синхронизации спецпроцессора, вход разрешения записи является первым управляющим входом 4 спецпроцессора, а информационный вход подключен к выходу приоритетной цепочки 5; первый 6 и второй 7 дешифраторы, m-разрядный и k-разрядный информационные входы которых являются соответственно первым 8 и вторым 9 информационными входами спецпроцессора, а управляющий вход второго дешифратора 7 является вторым управляющим входом 10 спецпроцессора; М последовательно пронумерованных блоков дизъюнкции (CLAUSE), каждый из которых содержит первый элемент «ИЛИ» 11 и N последовательно пронумерованных ячеек (CELL) каждая из которых содержит первый RS-триггер 12, D-триггер 13, элемент суммирования по модулю два 14, первый 15, второй 16 и третий 17 элементы «И», второй 18 и третий 19 элементы «ИЛИ»; причем в каждой ячейке выход первого элемента «И» 15 соединен с входом разрешения D-триггера 13 и установочным входом первого RS-триггера 12, выход которого соединен с первыми входами второго элемента «И» 16 и второго элемента «ИЛИ» 18, выход которого соединен с первым входом третьего элемента «И» 17, выход которого, в свою очередь, соединен с первым входом третьего элемента «ИЛИ» 19, второй вход второго элемента «И» 16 подключен к выходу элемента суммирования по модулю два 14, первый вход которого подключен к выходу D-триггера 13; в каждом блоке дизъюнкции вторые входы третьих элементов «И» 17 подключены к инверсному выходу первого элемента «ИЛИ» 11, второй вход второго элемента «ИЛИ» 18 и инверсный вход третьего элемента «И» 17 младшей ячейки блока обнулены, а соответствующие входы второго элемента «ИЛИ» 18 и третьего элемента «И» 17 каждой из остальных ячеек блока подключены к выходу второго элемента «ИЛИ» 18 предшествующей ячейки; вторые входы элементов суммирования по модулю два 14 ячеек, имеющих в блоках дизъюнкции одинаковый номер, подключены к разряду с соответствующим номером N-разрядного информационного выхода сумматора-аккумулятора 1, одновременно являющегося первым выходом 20 спецпроцессора; вторые входы третьих элементов «ИЛИ» 19 ячеек блока дизъюнкции, имеющего младший номер, обнулены, а вторые входы третьих элементов «ИЛИ» 19 ячеек остальных блоков дизъюнкции подключены к выходам третьих элементов «ИЛИ» 19 соответствующих по номеру ячеек предшествующего блока дизъюнкции, при этом выход третьего элемента «ИЛИ» 19 каждой из ячеек старшего блока дизъюнкции соединен с соответствующим разрядом входа приоритетной цепочки 5 и с одним из входов четвертого элемента «ИЛИ» 21, инверсный вход которого подключен к первому управляющему входу 4 спецпроцессора, а инверсный выход является вторым выходом 22 спецпроцессора; информационные входы всех D-триггеров соединены и являются третьим информационным входом 23 спецпроцессора; первые входы первых элементов «И» 15 одноименных ячеек всех блоков дизъюнкции подключены к соответствующему разряду N-разрядного выхода второго дешифратора 7, а все вторые входы первых элементов «И» 15 ячеек блока дизъюнкции объединены и подключены к разряду, соответственно номеру блока дизъюнкции, M-разрядного выхода первого дешифратора 6; выход переноса сумматора-аккумулятора 1 подключен к установочному входу второго RS-триггера 24, выход которого является третьим выходом 25 спецпроцессора; кроме того, входы сброса и синхронизации всех триггеров подключены к входу 2 сброса и к входу 3 синхронизации спецпроцессора.

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

В процессе работы предлагаемого спецпроцессора используется естественная кодировка булевой формулы, представленной в конъюнктивной нормальной форме. Запись формулы начинается с маркера, в качестве которого использован восклицательный знака «!». За маркером начала следуют записанные через запятую «,» литералы - номера переменных без знака или со знаком «-», входящих в одну дизъюнкцию. Использование знака «-» означает, что в дизъюнкции используется инверсное значение переменной. Запись переменных, принадлежащих дизъюнкции, заканчивается маркером точка с запятой «;» в случае, если дизъюнкция не является последней, и маркером точка «.», если дизъюнкция является последней в записи функции.

Например, функция

F=(¬Х₀+¬Х₂+¬Х₁+Х₃+Х₄+¬Х₅+Х₇)(Х₀+Х₁+Х₂)(Х₆+¬Х₄+Х₅+¬Х₃+¬Х₇),

записывается в эквивалентном виде

Y!-0,-2,-1,3,4,-5,7;0,1,2;6,-4,5,-3,-7.

Для рассматриваемой булевой функции N=8 (k=3), М=3.

Спецпроцессор и его устройство управления оперируют со следующей последовательностью k+3-разрядных информационных слов в буферном ОЗУ:

/Y!/-0,/-2,/-1,/3,/4,/-5,/7;/0,/1,/2;/6,/-4,/5,/-3/-7./

Информационные слова, имеющие последовательные адреса, разделены маркером «/».

Используемые при записи формулы знаки препинания кодируются следующим образом «!»=>00, «,»=>01, «;»=>10, «.»=>11. Для кодирования знаков препинания используются разряды k+3, k+2. Разряд k+1 используется для кодирования инверсии переменной. При работе представленного на фиг.8 варианта устройства управления k-разрядный код Y не используется.

После снятия сигнала сброса устройство управления на основании информации, записанной в ОЗУ, осуществляет установку D-триггеров и первых RS-триггеров ячеек блоков дизъюнкции. При этом текущий номер блока дизъюнкции определяется кодом, поступающим с выхода счетчика дизъюнкций на первый информационный вход 8 спецпроцессора, а номер ячейки в блоке дизъюнкции определяется младшими k-разрядами слова ОЗУ, поступающими на второй информационный вход 9 спецпроцессора. Единичное значение на выходе первого RS-триггера свидетельствует о том, что соответствующая переменная включена в составе соответствующей дизъюнкции.

На третий информационный вход 23 спецпроцессора подается несущий информацию об инверсии переменной разряд k+1 слова ОЗУ. Этот разряд поступает на информационные входы всех D-триггеров и записывается в триггер выбранной ячейки. Единичное значение на выходе D-триггера свидетельствует о том, что соответствующая переменная в составе соответствующей дизъюнкции инвертирована.

Код «.» устанавливает RS-триггер устройства управления, при этом процесс записи информации в триггеры ячеек блоков дизъюнкции прекращается, одновременно разрешается работа сумматора-аккумулятора 1.

Состояние инверсного выхода элемента «ИЛИ» 11 каждого блока дизъюнкции определяет, является ли соответствующая дизъюнкции действующей. Действующей называется дизъюнкция, все литералы которой равны нулю при наборе значений булевых переменных заданным состоянием выхода сумматора-аккумулятора 1. Вторые элементы «ИЛИ» 18 и третьи элементы «И» 17 в каждом из блоков дизъюнкции образуют приоритетную цепочку так, что в блоке действующей дизъюнкции единичное значение принимает выход третьего элемента «И» 17 ячейки, соответствующей младшей переменной.

Выходы третьих элементов «И» 17 ячеек блоков дизъюнкции собраны поразрядно по «ИЛИ», реализованному на двухвходовых третьих элементах «ИЛИ» 19, при этом выход элемента «ИЛИ» 19 старшего блока дизъюнкции соединен с соответствующим разрядом входа приоритетной цепочки 5. Приоритетная цепочка 5 выбирает действующую дизъюнкцию, младшая переменная которой является старшей по сравнению с младшими переменными других действующих дизъюнкций. Приоритетный выбор дизъюнкции направлен на исключение максимального числа неперспективных наборов переменных. Если в разряде j выхода приоритетной цепочки 5 присутствует единица, код в сумматоре-аккумуляторе 1 увеличивается на 2^j, что соответствует отбраковке 2^j наборов переменных в одном такте работы спецпроцессора.

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

Ситуация, когда все разряды выхода (BACK) приоритетной цепочки 5 обнулены, соответствует нахождению выполняющего набора булевой формулы, поскольку набор на выходе сумматора-аккумулятора 1 не порождает ни одной действующей дизъюнкции. В таком случае на инверсном выходе четвертого элемента «ИЛИ» 21, являющегося вторым выходом 22 (SAT) спецпроцессора, устанавливается единичное значение.

Загруженная в спецпроцессор булева формула невыполнима, если единица появляется на выходе переноса (N_SAT) сумматора-аккумулятора 1. Единица, появившаяся на выходе переноса сумматора-аккумулятора 1, запоминается во втором RS-триггере 24, выход которого является третьим выходом 25 спецпроцессора.

Графа (СТ) на временных диаграммах, представленных на фиг.4 и фиг.5, представляет в шестнадцатиричной системе число тактов (CLK) работы спецпроцессора в режиме конечного автомата (SJOB=1).

Работа спецпроцессора проиллюстрирована на примере булевых формул, составленных из конъюнкций, представленных в таблице 1 на фиг.6.

Временная диаграмма на фиг.4 иллюстрирует работу спецпроцессора на примере невыполнимой формулы F_N, являющейся конъюнкцией всех восемнадцати дизъюнкций, представленных в таблице 1 (фиг.6).

F_N=C₀·C₁·C₂·C₃·C₄·C₅·C₆·C₇·C₈·C₉·C₁₀·C₁₁·C₁₂·C₁₃·C₁₄·C₁₅·C₁₆·C₁₇.

В таблице 2 (фиг.7) приведены восемнадцать выполнимых формул, каждая их которых получена удалением из невыполнимой формулы F_N одной из дизъюнкций. Для каждой из таких формул приведен выполняющий набор, начиная со старших переменных (Х₇, Х₆, X₅, Х₄, Х₃, Х₂, Х₁, Х₀), и число тактов работы спецпроцессора.

Временная диаграмма, иллюстрирующая обработку формулы F₁, представлена на фиг.5.

Спецпроцессор для задачи выполнимости булевых формул характеризуется тем, что содержит N-разрядный сумматор-аккумулятор 1, вход сброса которого является входом 2 сброса спецпроцессора, вход синхронизации является входом 3 синхронизации спецпроцессора, вход разрешения записи является первым управляющим входом 4 спецпроцессора, а информационный вход подключен к выходу приоритетной цепочки 5; первый 6 и второй 7 дешифраторы, m-разрядный и k-разрядный информационные входы которых являются соответственно первым 8 и вторым 9 информационными входами спецпроцессора, а управляющий вход второго дешифратора 7 является вторым управляющим входом 10 спецпроцессора; М последовательно пронумерованных блоков дизъюнкции (CLAUSE), каждый из которых содержит первый элемент «ИЛИ» 11 и N последовательно пронумерованных ячеек (CELL), каждая из которых содержит первый RS-триггер 12, D-триггер 13, элемент суммирования по модулю два 14, первый 15, второй 16 и третий 17 элементы «И», второй 18 и третий 19 элементы «ИЛИ»; причем в каждой ячейке выход первого элемента «И» 15 соединен с входом разрешения D-триггера 13 и установочным входом первого D-триггера 12, выход которого соединен с первыми входами второго элемента «И» 16 и второго элемента «ИЛИ» 18, выход которого соединен с первым входом третьего элемента «И» 17, выход которого в свою очередь соединен с первым входом третьего элемента «ИЛИ» 19, второй вход второго элемента «И» 16 подключен к выходу элемента суммирования по модулю два 14, первый вход которого подключен к выходу D-триггера 13; в каждом блоке дизъюнкции вторые входы третьих элементов «И» 17 подключены к инверсному выходу первого элемента «ИЛИ» 11, второй вход второго элемента «ИЛИ» 18 и инверсный вход третьего элемента «И» 17 младшей ячейки блока обнулены, а соответствующие входы второго элемента «ИЛИ» 18 и третьего элемента «И» 17 каждой из остальных ячеек блока подключены к выходу второго элемента «ИЛИ» 18 предшествующей ячейки; вторые входы элементов суммирования по модулю два 14 ячеек, имеющих в блоках дизъюнкции одинаковый номер, подключены к разряду с соответствующим номером N-разрядного информационного выхода сумматора-аккумулятора 1, одновременно являющегося первым выходом 20 спецпроцессора; вторые входы третьих элементов «ИЛИ» 19 ячеек блока дизъюнкции, имеющего младший номер, обнулены, а вторые входы третьих элементов «ИЛИ» 19 ячеек остальных блоков дизъюнкции подключены к выходам третьих элементов «ИЛИ» 19 соответствующих по номеру ячеек предшествующего блока дизъюнкции, при этом выход третьего элемента «ИЛИ» 19 каждой из ячеек старшего блока дизъюнкции соединен с соответствующим разрядом входа приоритетной цепочки 5 и с одним из входов четвертого элемента «ИЛИ» 21, инверсный вход которого подключен к первому управляющему входу 4 спецпроцессора, а инверсный выход является вторым выходом 22 спецпроцессора; информационные входы всех D-триггеров соединены и являются третьим информационным входом 23 спецпроцессора; первые входы первых элементов «И» 15 одноименных ячеек всех блоков дизъюнкции подключены к соответствующему разряду N-разрядного выхода второго дешифратора 7, а все вторые входы первых элементов «И» 15 ячеек блока дизъюнкции объединены и подключены к разряду, соответственно номеру блока дизъюнкции, M-разрядного выхода первого дешифратора 6; выход переноса сумматора-аккумулятора 1 подключен к установочному входу второго RS-триггера 24, выход которого является третьим выходом 25 спецпроцессора; кроме того, входы сброса и синхронизации всех триггеров подключены к входу 2 сброса и к входу 3 синхронизации спецпроцессора.

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

Соединение визуальных свойств диаграмм с ячейками в таблицах // 2514102

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

Информационно-измерительная система контроля параметров условий труда // 2514100

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

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

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

Технологическая платформа интеграции ресурсов сети интернет для проведения федеральных выборов и референдумов // 2513721

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

Отслеживание потока фона веществ в окружающей среде // 2512113

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

Устройство для решения задачи о назначениях // 2511412

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

Способ проектирования первичной структуры белка с заданной вторичной структурой // 2511002

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

Сервер для предоставления контента, устройство воспроизведения контента, способ предоставления контента, способ воспроизведения контента, программа и система для предоставления контента // 2506635

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

Устройство для контроля качества канала передачи данных // 2504830

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

Спецпроцессор для поиска гамильтоновых циклов в графах // 2515211

Изобретение относится к вычислительной технике и направлено на построение эффективного спецпроцессора, осуществляющего поиск Гамильтонова цикла в графе, заданном матрицей смежностей, хранящейся в памяти. Техническим результатом является увеличение скорости решения задачи отыскания Гамильтонова цикла в графе за счет параллельной работы процессорных элементов и уменьшение используемого объема памяти до величины, необходимой для хранения матрицы смежностей вершин обрабатываемого графа, за счет обращения в память только за информацией о смежности обрабатываемой пары вершин графа. Спецпроцессор для поиска Гамильтоновых циклов в графах содержит N идентичных процессорных элементов, каждый из которых состоит из регистра, 3-х мультиплексоров, вычитающего счетчика, 9 элементов «ИЛИ», 8 элементов «И», 2-х групп элементов «И», RS триггера и D триггера, 6 элементов «ИЛИ», две группы элементов «ИЛИ», 5 элементов «И», RS триггер и два D триггера. 5 ил.

Способ и система поиска нарушений авторских прав на изображения // 2515706

Изобретение относится к вычислительной технике и может быть использовано в компьютерных системах для поиска и выявления изображений, авторские права на которые нарушены. Техническим результатом является повышение точности, качества и скорости поиска идентичных или сходных до степени смешения изображений. В способе поиска нарушений авторских прав на изображения, выполняемом на компьютерной системе, производят расчет дескриптора для изображения №1, располагающегося в блоке памяти №1. Выполняют расчет дескриптора для изображения №2, располагающегося в блоке памяти №2. Сравнивают значения дескрипторов изображений №1 и №2. Если значения дескрипторов изображений №1 и №2 равны, то выполняют сравнение изображений №1 и №2. После чего отображают результаты сравнения на устройстве для отображения информации. 6 н. и 7 з.п. ф-лы, 5 ил.

Устройство и способ для определения информации о парковках // 2516575

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

Способ оценки эффективности управления и устройство для его осуществления // 2517409

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

Способ формирования квазиструктурированных моделей фактографического информационного наполнения документов // 2517428

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

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

Изобретение относится к способам и устройствам для предоставления контента через сеть. Техническим результатом является обеспечение удобства доступа к модифицированному контенту, а также возможность модифицирования атрибутов контента, который предоставляется, чтобы он соответствовал характеристикам устройства, принимающего контент. Способ содержит: сохранение исходного контента в предопределенном устройстве хранения; модифицирование атрибутов исходного контента, чтобы генерировать модифицированный контент; генерацию метаданных, включающих в себя информацию местоположения устройства хранения, в котором сохранен исходный контент; и предоставление модифицированного контента и метаданных к устройству, взаимосвязанному через сеть, при этом метаданные дополнительно включают в себя метаданные устройства, которые относятся к информации о деталях истории передачи, когда модифицированный контент передается между разными устройствами, и истории редактирования, которая относится к информации об отредактированных деталях модифицированного контента. 4 н. и 11 з.п. ф-лы, 26 ил.

Устройство для решения задач целочисленного линейного программирования // 2518998

Изобретение относится к автоматике и вычислительной технике. Техническим результатом является увеличение быстродействия и надежности устройства, уменьшение аппаратных затрат, расширение функциональных возможностей в части возможности задания допустимого количества исходных заготовок в каждом каскаде. Устройство для решения задач целочисленного линейного программирования содержит генератор тактовых импульсов 1, триггеры разрешения 2, готовности результата 3, группы из n счетчиков 41, 42, …, 4n (n - число возможных вариантов разрезания заготовок длиной L), n третьих регистров 51, 52, …, 5n, n третьих схем сравнения 61, 62, …, 6n, k шестых регистров 71, 72, …, 7k, k третьих сумматоров 81, 82, …, 8k, k четвертых схем сравнения 91, 92, …, 9k, k каскадов 101, 102, …, 10k (k - количество типов различных исходных заготовок), элемент И 11, группы из m*n первых регистров 1211, …, 12mn (m - общее число типов требуемых различных типов заготовок), m*n четвертых сумматоров 1311, …, 13mn, m*n седьмых регистров 1411, …, 14mn, m первых сумматоров 151, 152, …, 15m, m первых схем сравнения 161, 162, …, 16m, m вторых регистров 171, 172, …, 17m, m восьмых регистров 181, 182, …, 18m, n четвертых регистров 191, 192, …, 19n, n пятых сумматоров 201, 202, …, 20n, n девятых регистров 211, 212, …, 21n, второй сумматор 22, пятый регистр 23, вторую схему сравнения 24, входы пуска 25 и сброса 26 устройства, первый 27, вторые 281, 282, …, 28n, третьи 291, 292, …, 29n и четвертые 30 выходы устройства. 1 ил., 3 табл.

Устройство для оценки предпочтительного уровня унификации технических систем // 2519049

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

Создание маски для кардиосубстракции // 2519353

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

Способ обмена информацией между информационными системами // 2519447

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