Алгоритмы синтеза схем-заплаток для решения ресурсо-ориентированной функциональной коррекции схем из функциональных элементов

Л. И. Высоцкий; Жуков В. В.; Шуплецов М. С.

doi:10.31114/2078-7707-2018-1-30-37

Публикации

?

Алгоритмы синтеза схем-заплаток для решения ресурсо-ориентированной функциональной коррекции схем из функциональных элементов

С. 30–37.

Высоцкий Л. И., Жуков В. В., Шуплецов М. С.

При обнаружении ошибок или изменении
спецификации
проектируемой
сверхбольшой
интегральной схемы (СБИС) на поздних этапах
маршрута проектирования откат на более ранние этапы
проектирования и их повторное выполнение очень часто
становится непрактичным в силу существенных
временных затрат. Для целей сокращения времени
проектирования
в
современные
маршруты
проектирования интегрируют специальные этапы
функциональной коррекции схемы (англ. Engineering
Change Order, ECO). В основе указанного подхода лежит
анализ уже спроектированной схемы и построение
небольшой подсхемы-заплатки, внедрение которой в уже
синтезированную схему позволяет исправить все
обнаруженные логические несоответствия. Таким
образом, не требуется заново полностью повторять уже
пройденные этапы логического и физического синтеза
интегральной схемы.

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

Язык: русский

Полный текст

DOI

Текст на другом сайте

Ключевые слова: Boolean circuits equivalence checking схемы из функциональных элементов автоматическая коррекция logic synthesis логический синтез

В книге

Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018)

Вып. 1. , М.: ИППМ РАН, 2018.

The Exact Circuit Complexity of Boolean Functions in an Infinite Basis

V. V. Kochergin, A. V. Mikhailovich, Mathematical notes 2025 Vol. 117 No. 4 P. 579–594

Добавлено: 28 февраля 2026 г.

Точное значение схемной сложности булевых функций в одном бесконечном базисе

Кочергин В. В., Михайлович А. В., Математические заметки 2025 Т. 117 № 4 С. 523–542

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

Добавлено: 8 апреля 2025 г.

О немонотонной сложности функций k-значной логики

Кочергин В. В., Михайлович А. В., В кн.: Проблемы теоретической кибернетики. Материалы заочного семинара XIX международной конференции.: Издательство Казанского (Приволжского) федерального университета, 2021. С. 75–78.

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

Добавлено: 6 декабря 2021 г.

О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов

Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2014 Т. 3 № 31 С. 78–100

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

Добавлено: 2 декабря 2019 г.

Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами

Данилов Б. Р., Известия высших учебных заведений. Поволжский регион. Физико-математические науки 2015 Т. 4 № 36 С. 58–77

Добавлено: 2 декабря 2019 г.

Асимптотические оценки функции Шеннона в одной модели глубины схем из функциональных элементов с емкостными параметрами выходов элементов

Данилов Б. Р., Ложкин С. А., Прикладная математика и информатика 2018 № 59 С. 40–49

В работе предлагается метод синтеза усилительных схем из функциональных элементов (УСФЭ), позволяющий установить асимптотику функции Шеннона для обобщённой глубины УСФЭ – то есть глубины самой «плохой» функции алгебры логики, зависящей от заданных переменных – в специальном базисе (модели глубины), где глубина элемента определяется как его типом, так и степенью ветвления выхода в схеме. Асимптотическое поведение ...

Добавлено: 2 декабря 2019 г.

Synthesis of asymptotically size-optimal Boolean circuits protected from functionality inference

Lozhkin S. A., Shupletsov M. S., Danilov B.R., Математические вопросы криптографии 2017 Vol. 8 No. 2 P. 87–96

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

Добавлено: 1 декабря 2019 г.

О проблеме эквивалентности недетерминированных автоматов-преобразователей над однобуквенным выходным алфавитом

Захаров В. А., Жайлауова Ш. Р., В кн.: Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019).: М.: Изд-во механико-математического факультета МГУ, 2019. С. 272–274.

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

Добавлено: 17 октября 2019 г.

Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019)

М.: Изд-во механико-математического факультета МГУ, 2019.

Сборник содержит материалы XII Международного семинара «Дискретная математика и ее приложения» имени академика О.Б. Лупанова, проходившего на механико-математическом факультете МГУ имени М. В. Ломоносова с 17 по 22 июня 2019 г. при поддержке Российского фонда фундаментальных исследований (проект 16–01–20345). Семинар охватывает следующие направления в области дискретной математики: теория функциональных систем, синтез, сложность и надежность управляющих ...

Добавлено: 17 октября 2019 г.

Exact Value of the Nonmonotone Complexity of Boolean Functions

V.V. Kochergin, A.V. Mikhailovich, Mathematical notes 2019 Vol. 105 No. 1 P. 28–35

Добавлено: 22 апреля 2019 г.

Automatic Spelling Correction for Russian Social Media Texts

Сорокин А. А., Шаврина Т. О., , in: Computational Linguistics and Intellectual Technologies: Proceedings of the Annual International Conference “Dialogue” (2016).: М.: Изд-во РГГУ, 2016. P. 688–701.

Добавлено: 30 ноября 2018 г.

The minimum number of negations in circuits for systems of multi-valued functions

Kochergin Vadim V., Mikhailovich Anna V., Discrete Mathematics and Applications 2017 Vol. 27 No. 5 P. 295–302

The paper is concerned with the complexity of realization of 𝑘-valued logic functions by logic circuits over an infinite complete bases containing all monotone functions; the weight of monotone functions (the cost of use) is assumed to be 0. The complexity problem of realizations of Boolean functions over a basis having negation as the only ...

Добавлено: 14 марта 2018 г.

On complexity of multi-valued logic functions over one infinite basis

Kochergin V.V., Mikhailovich A.V., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2018 Vol. 12 No. 1 P. 40–58

Добавлено: 11 марта 2018 г.

Hardware and Software: Verification and Testing. HVC 2017. Lecture Notes in Computer Science

Cham: Springer, 2017.

This book constitutes the refereed proceedings of the 13th International Haifa Verification Conference, HVC 2017, held in Haifa, Israel in November 2017. The 13 revised full papers presented together with 4 poster and 5 tool demo papers were carefully reviewed and selected from 45 submissions. They are dedicated to advance the state of the art and state of the ...

Добавлено: 24 января 2018 г.

On the Minimization Problem for Sequential Programs

Захаров В. А., Jaylauova S., Automatic Control and Computer Sciences 2017 Vol. 51 No. 7 P. 689–700

Добавлено: 19 декабря 2017 г.

О минимизации схем программ относительно логико-термальной эквивалентности

Захаров В. А., Жайлауова Ш. Р., В кн.: Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.).: М.: МГУ, МАКС Пресс, 2017. С. 84–87.

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

Добавлено: 22 октября 2017 г.

Точное значение немонотонной сложности булевых функций

Михайлович А. В., Кочергин В. В., Математические заметки 2019 Т. 105 № 1 С. 32–41

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

Добавлено: 28 сентября 2017 г.

Asymptotics of growth for non-monotone complexity of multi-valued logic function systems

Mikhailovich A.V., Kochergin V.V., Siberian Electronic Mathematical Reports 2017 Vol. 14 P. 1100–1107

Добавлено: 28 сентября 2017 г.

Немонотонная сложность как обобщение инверсионной сложности

Михайлович А. В., Кочергин В. В., XXI век: итоги прошлого и проблемы настоящего плюс 2017 № 4(38) С. 98–105

Рассматривается задача об экономной реализации булевых функций и функций многозначной логики схемами из функциональных элементов в бесконечном базисе, состоящем из всех монотонных и конечного числа немонотонных функций, причем мерой качества реализации является немонотонная сложность — число использований немонотонных элементов (монотонные функции «бесплатны»). Для случая реализации систем булевых функций в базисе, содержащем помимо монотонных функций только ...

Добавлено: 28 сентября 2017 г.