• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Актуальность и цели

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

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

Материалы и методы

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

Результаты

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

Выводы

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