![]() |
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
В рамках проекта будет проведена разработка оригинальных эффективных методов реализации «типичных» и «самых сложных» функций алгебры логики (ФАЛ) в ряде классов комбинационных дискретных управляющих систем при определѐнных ограничениях на структуру и параметры схем. С помощью этих методов будут получены оценки, являющиеся, как правило, асимптотическими оценками высокой степени точности (АОВСТ), для сложности «типичных» функций и сложности «самой сложной» функции, то есть функции Шеннона, в указанных классах схем. Будет выполнена разработка методов синтеза и будут установлены асимптотические оценки различной степени точности для задержки (глубины) схем из функциональных элементов (СФЭ) в некоторых моделях, учитывающих особенности процесса распространения сигналов в современных СБИС, а также для динамической активности СФЭ в различных базисах, моделирующей энергопотребление СБИС. При этом во втором случае будет исследована возможность построения схем, оптимальных как по динамической активности, так и по сложности. На уровне АОВСТ или близких к ним оценок будет исследовано поведение функции Шеннона для сложности ФАЛ из ряда специальных классов, а также сложности некоторых ФАЛ, встречающихся в приложениях, и, в частности, ФАЛ мультиплексорного типа. Асимптотические оценки различной степени точности будут получены для сложности реализации ФАЛ схемами, допускающими вложение в некоторые «регулярные» геометрические структуры (единичные кубы, плоские прямоугольные решетки и др.), причем будет исследована возможность построения схем, оптимальных как по «объемным», так и по «временным» параметрам. Будут разработаны новые методы синтеза оптимальных или близких к ним схем от малого числа переменных, основанные на алгоритмах переборного типа. Будут получены новые нетривиальные оценки функций Шеннона длин тестов различных типов при неисправностях элементов в схемах (в частности, в итеративных контактных схемах и в СФЭ) и при неисправностях на входах схем (в частности, при условных замещениях входов схем). При этом будет осуществлено описание достаточно широких классов легкотестируемых схем с оценками длин тестов для них. Будут установлены новые нетривиальные верхние и нижние оценки длины полного условного диагностического теста для минимальной контактной схемы счетчика четности, построенной по методу каскадов.
Результаты этапа 2015 года. 1. Доказано, что для стремящегося к бесконечности натурального n почти все булевы функции от n переменных допускают реализацию их такими схемами из функциональных элементов в стандартном базисе, у которых размерность булева куба, допускающего изоморфное вложение схемы, и глубина схемы отличаются от минимально возможных значений не более чем на константу и асимптотически не более чем в три раза соответственно. 2. Получены асимптотические оценки высокой степени точности для контактной сложности дизъюнктивных дешифраторов с одним входом. Установлены точные значения 13 и 34 указанной сложности для дешифраторов порядка 3 и 4 соответственно. 3. Получен порядок динамической активности для схем из функциональных элементов в стандартном базисе, реализующих мультиплексорную функцию. Показана возможность одновременной оптимизации схем, реализующих указанную функцию, как по сложности, так и по динамической активности. 4. Разработаны новые методы синтеза асимптотически наилучших по задержке СФЭ в модели, где положительная задержка на входе элемента произвольным образом зависит как от номера этого входа, так и от типа подключенного сверху элемента. В модели описанного типа для обширного класса базисов получены АОВСТ задержки мультиплексорной ФАЛ и функции Шеннона для задержки ФАЛ. Также разработаны применимые к обширному классу базисов методы синтеза асимптотически наилучших по задержке СФЭ в другой модели, где задержка дополнительно зависит от наборов, поступающих на входы элемента в содержащей его схеме. 5. Исследовалась задача синтеза схем из функциональных элементов с ограничениями на способы соединения элементов в схеме. Входы элементов схем делятся на два типа – прямые и итеративные. Итеративные входы служат для присоединения к ним выходов других элементов, а прямые входы являются входами схем. Задача синтеза в этой модели рассмотрена для случая формул, т.е. схем без ветвлений выходов элементов. Получена асимптотика функции Шеннона для сложности формул алгебры логики в полных базисах с прямыми и итеративными переменными, итеративное замыкание которых содержит класс монотонных функций. Указан способ нахождения константы в этой асимптотике. Установленные результаты позволяют сделать вывод о существовании асимптотики функции Шеннона для формул в отдельных классах базисов с прямыми и итеративными переменными, где порядок этой функции «стандартный» и совпадает с порядком роста соответствующей функции для класса булевых формул в обычных полных базисах – . Кроме того, впервые в классе формул в базисах с прямыми и итеративными входами выделен достаточно широкий подкласс, в котором получены оценки высокой степени точности функции Шеннона для их сложности. 6. Разработаны методы синтеза легкотестируемых двухполюсных итеративных контактных схем, реализующих произвольную булеву функцию (возможно, с константной входной избыточностью) и допускающих проверяющий тест (относительно размыканий и замыканий контактов) константной длины. При этом установлено, что для произвольной отличной от константы булевой функции f, зависящей от n переменных, существуют неизбыточные реализующие функцию, равную f, обобщенные итеративные контактные схемы, допускающие: а) единичный проверяющий тест размыкания длины не более 7, б) единичный проверяющий тест замыкания длины не более 4, а также имеется тестопригодная моделирующая функцию f (т.е. реализующая такую функцию, для которой f является подфункцией) обобщенная итеративная контактная схема, допускающая единичный проверяющий тест длины 11. Указанные оценки являются и верхними оценками функции Шеннона длины единичного проверяющего теста соответствующего типа. 7. Разработан метод синтеза схем из функциональных элементов в базисе Жегалкина, гарантирующий существование для каждой булевой функции f неизбыточной схемы, допускающей единичный диагностический тест длины 1 при инверсных неисправностях на выходах элементов. 8. Установлено, что длина минимального условного полного диагностического теста для схемы Кардо от 4 переменных равна 14.
МГУ | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2015 г.-31 декабря 2015 г. | Модели и методы теории синтеза и контроля комбинационных дискретных управляющих систем |
Результаты этапа: 1. Доказано, что для стремящегося к бесконечности натурального n почти все булевы функции от n переменных допускают реализацию их такими схемами из функциональных элементов в стандартном базисе, у которых размерность булева куба, допускающего изоморфное вложение схемы, и глубина схемы отличаются от минимально возможных значений не более чем на константу и асимптотически не более чем в три раза соответственно. 2. Получены асимптотические оценки высокой степени точности для контактной сложности дизъюнктивных дешифраторов с одним входом. Установлены точные значения 13 и 34 указанной сложности для дешифраторов порядка 3 и 4 соответственно. 3. Получен порядок динамической активности для схем из функциональных элементов в стандартном базисе, реализующих мультиплексорную функцию. Показана возможность одновременной оптимизации схем, реализующих указанную функцию, как по сложности, так и по динамической активности. 4. Разработаны новые методы синтеза асимптотически наилучших по задержке СФЭ в модели, где положительная задержка на входе элемента произвольным образом зависит как от номера этого входа, так и от типа подключенного сверху элемента. В модели описанного типа для обширного класса базисов получены АОВСТ задержки мультиплексорной ФАЛ и функции Шеннона для задержки ФАЛ. Также разработаны применимые к обширному классу базисов методы синтеза асимптотически наилучших по задержке СФЭ в другой модели, где задержка дополнительно зависит от наборов, поступающих на входы элемента в содержащей его схеме. 5. Исследовалась задача синтеза схем из функциональных элементов с ограничениями на способы соединения элементов в схеме. Входы элементов схем делятся на два типа – прямые и итеративные. Итеративные входы служат для присоединения к ним выходов других элементов, а прямые входы являются входами схем. Задача синтеза в этой модели рассмотрена для случая формул, т.е. схем без ветвлений выходов элементов. Получена асимптотика функции Шеннона для сложности формул алгебры логики в полных базисах с прямыми и итеративными переменными, итеративное замыкание которых содержит класс монотонных функций. Указан способ нахождения константы в этой асимптотике. Установленные результаты позволяют сделать вывод о существовании асимптотики функции Шеннона для формул в отдельных классах базисов с прямыми и итеративными переменными, где порядок этой функции «стандартный» и совпадает с порядком роста соответствующей функции для класса булевых формул в обычных полных базисах – . Кроме того, впервые в классе формул в базисах с прямыми и итеративными входами выделен достаточно широкий подкласс, в котором получены оценки высокой степени точности функции Шеннона для их сложности. 6. Разработаны методы синтеза легкотестируемых двухполюсных итеративных контактных схем, реализующих произвольную булеву функцию (возможно, с константной входной избыточностью) и допускающих проверяющий тест (относительно размыканий и замыканий контактов) константной длины. При этом установлено, что для произвольной отличной от константы булевой функции f, зависящей от n переменных, существуют неизбыточные реализующие функцию, равную f, обобщенные итеративные контактные схемы, допускающие: а) единичный проверяющий тест размыкания длины не более 7, б) единичный проверяющий тест замыкания длины не более 4, а также имеется тестопригодная моделирующая функцию f (т.е. реализующая такую функцию, для которой f является подфункцией) обобщенная итеративная контактная схема, допускающая единичный проверяющий тест длины 11. Указанные оценки являются и верхними оценками функции Шеннона длины единичного проверяющего теста соответствующего типа. 7. Разработан метод синтеза схем из функциональных элементов в базисе Жегалкина, гарантирующий существование для каждой булевой функции f неизбыточной схемы, допускающей единичный диагностический тест длины 1 при инверсных неисправностях на выходах элементов. 8. Установлено, что длина минимального условного полного диагностического теста для схемы Кардо от 4 переменных равна 14. | ||
2 | 1 января 2016 г.-31 декабря 2016 г. | Модели и методы теории синтеза и контроля комбинационных дискретных управляющих систем, этап 2016 года |
Результаты этапа: В первом направлении проекта получены следующие результаты. 1. Установлено, что точное значение глубины в унимодальном базисе мультиплексорной функции алгебры логики (ФАЛ) от $n$ адресных переменных равно $n+2$, если $n \geq 2$ и $n \neq 9$. 2. Расширен класс тех базисов из элементов с прямыми и итеративными входами, в которых имеет место «стандартное» асимптотическое поведение с порядком роста $2^n/(\log n)$ функции Шеннона для сложности формул, установленное на уровне асимптотических оценок высокой степени точности (АОВСТ). Кроме того, впервые в классе усилительных схем из функциональных элементов (СФЭ) в некоторых базисах из элементов с прямыми и итеративными входами получены АОВСТ функции Шеннона для их сложности. 3. Разработаны методы синтеза одновременно асимптотически наилучших по сложности и по задержке СФЭ в модели, где положительная задержка на входе элемента произвольным образом зависит как от номера входа, так и от типа подключаемого сверху элемента, а также от наборов значений, подаваемых на остальные входы. Доказано, что в модели задержки описанного типа для представительного класса базисов указанная одновременная оптимизация возможна также и на уровне асимптотических оценок сложности и задержки близких к АОВСТ. 4. Получен порядок роста динамической активности СФЭ в произвольном базисе, реализующих мультиплексорную функцию. В ряде базисов показана возможность реализации указанной функции схемой, которая имеет асимптотически минимальную сложность и оптимальную по порядку динамическую активность. 5. Существенно обновлена версия базы данных о сложности и структуре контактных схем (КС), реализующих ФАЛ от 5 переменных. Установлена новая верхняя оценка 19 значения функции Шеннона для сложности КС от пяти переменных, которая совпала с установленной ранее (в 1981 г.) нижней оценкой указанной функции Шеннона и определила ее точное значение. 6. Доказано, что для стремящегося к бесконечности натурального аргумента $n$ почти все ФАЛ от $n$ переменных реализуемы такими СФЭ в стандартном базисе, у которых размерность булева куба, допускающего изоморфное вложение данной схемы, и ее глубина отличаются от минимально возможных значений не более чем на константу и асимптотически не более чем в два раза соответственно. 7. Создан метод (с экспериментальным подтверждением эффективности) оптимизации решения задачи размещения элементов интегральной схемы за счет анализа ряда структурных характеристик графа интегральной схемы. Разработан прототип системы предварительного выбора алгоритма размещения элементов интегральной схемы и подбора его параметров на основе исследуемых характеристик графа схемы. Во втором направлении проекта получены следующие результаты. 1. Доказано, что в базисе из двухвходовых конъюнкции, суммы по модулю 2 и эквивалентности и в базисе Жегалкина для любой отличной от константы булевой функции существует неизбыточная реализующая ее СФЭ, допускающая диагностический тест длины не более 22 относительно произвольных константных неисправностей на выходах элементов. 2. Доказано, что в базисе $\{ x\bar{y}, \bar{x}\}$ для любой булевой функции существует неизбыточная реализующая ее СФЭ, допускающая единичный диагностический тест длины не более 13 относительно инверсных неисправностей на выходах элементов. 3. Доказано, что в базисе Жегалкина для любой отличной от константы булевой функции существует неизбыточная реализующая ее СФЭ, допускающая единичный проверяющий тест длины 2 относительно неисправностей «объединение двух смежных элементов в элемент отрицания конъюнкции или в элемент отрицания дизъюнкции». 4. Установлена линейность по числу входных переменных порядка роста функции Шеннона длины диагностического теста относительно порожденных фиксированным (но произвольным) набором примитивных сдвигов влево входов схем. 5. Под условными $k$-кратными локальными замещениями входов схем понимаются такие неисправности входов схем, при которых какой-то один набор длины $k$ значений неисправных подряд идущих входов замещается каким-то другим набором длины $k$. Установлено, что функции Шеннона длины полного проверяющего теста относительно локальных условных $k$-кратных замещений входов схем от n переменных не превосходит $2^{2k}(n-k+1)$. | ||
3 | 1 января 2017 г.-31 декабря 2017 г. | Модели и методы теории синтеза и контроля комбинационных дискретных управляющих систем |
Результаты этапа: В первом направлении проекта, которое было посвящено разработке эффективных методов синтеза и оценке сложности схем из некоторых классов как для «типичных» или «самых сложных» функций алгебры логики (ФАЛ), так и для ряда специальных ФАЛ, встречающихся в приложениях, были получены следующие основные результаты. Установлена асимптотика функции Шеннона для формульной сложности ФАЛ в полных базисах с прямыми и итеративными переменными, итеративное замыкание которых содержит класс монотонных функций, предложен способ нахождения по базису константы в этой асимптотике. Выявлен, а затем существенно расширен класс тех из указанных базисов, в которых «стандартное» асимптотическое поведение функции Шеннона для сложности формул установлено на уровне асимптотических оценок высокой степени точности (АОВСТ). Существенно обновлена версия базы данных о сложности и структуре контактных схем (КС), реализующих ФАЛ от 5 переменных, установлено точное значение функции Шеннона для сложности КС от пяти переменных, которое равно 19. Предложены асимптотически оптимальные методы гомеоморфного вложения деревьев подобных формул в прямоугольные решетки с расположением листьев дерева на нижней стороне решетки и с оптимизацией как высоты решетки, так и глубины дерева. Разработан метод синтеза таких усилительных схем из функциональных элементов (СФЭ) в стандартном базисе, сложность которых совпадает с соответствующей функцией Шеннона на уровне ее АОВСТ, а логарифм числа попарно не эквивалентных схем, получающихся из построенной для «типичной» ФАЛ схемы в результате переключений входов ее элементов внутри подсхем глубины 2, имеет такой же порядок роста, как и указанная функция Шеннона. В рамках исследования временных параметров СФЭ продолжено углубление результатов, связанных с задержками распространения сигналов в схеме зависящими, в частности, от значений самих распространяемых сигналов. Установлена возможность одновременной асимтотической оптимизации схем по задержке указанного типа и традиционной сложности. Получены асимптотические оценки различной степени точности для новых функционалов задержки мультиплексорной ФАЛ и соответствующей функции Шеннона. В рамках одной моделей динамического энергопотребления схем установлена связь между глубиной и динамической активностью ФАЛ в классе СФЭ над произвольным унимодальным базисом, установлен линейный относительно числа адресных переменных порядок роста динамической активности мультиплексорной ФАЛ в классе СФЭ в произвольном базисе и разработаны методы синтеза реализующих её асимптотически оптимальных по сложности СФЭ в некоторых базисах, которые имеют оптимальную по порядку роста динамическую активность. Для ориентированных КС (ОКС) был введен функционал динамической активности, для которого была установлена точная линейная оценка соответствующей функции Шеннона и разработан метод синтеза асимптотически оптимальных по сложности и порядку роста динамической активности ОКС для типичных функций. Разработан алгоритм разбиения СФЭ на эквивалентные подсхемы, который показывает хорошие результаты локализации не эквивалентной части двух произвольных СФЭ. Во втором направлении проекта, связанном с разработкой методов контроля схем и построением на их основе оптимальных или близких к оптимальным тестов, в следующих задачах контроля получены новые оценки функций Шеннона L(n) (n - число переменных ФАЛ) длин соответствующих тестов. В модели СФЭ над полным базисом Б относительно константных неисправностей для единичных проверяющих тестов доказано, что L(n) ≤ 3 в случае неисправностей на выходах элементов квазинеизбыточных схем над произвольным базисом Б и L(n) ≤ 16 в случае неисправностей на входах и выходах элементов СФЭ над базисами Б’={xy (mod 2), x+y (mod 2), 1} и Б’’={xy (mod 2), x+y (mod 2), x+y+1 (mod 2)}. Доказано также, что L(n) ≤ const для диагностического теста относительно константных неисправностей кратности не более 2 на выходах элементов СФЭ над базисом Б’’, L(n) =1 и L(n) =2 для единичных диагностических тестов относительно инверсий элементов СФЭ над базисами Б’ и {x(y+1) (mod 2), x+1 (mod 2)} соответственно, и что L(n) ≤ 2 для аналогичных тестов относительно константных неисправностей на выходах элементов СФЭ над базисами Б’ и Б’’. Далее, в модели обобщенных итеративных контактных схем для единичных проверяющих тестов установлено, что L(n) ≤ 11 относительно замыкания и размыкания контакта при моделировании ФАЛ, что L(n) ≤ 7 относительно размыкания контакта, и что L(n) ≤ 4 относительно замыкания контакта. Кроме того, относительно локальных условных замещений входов схем установлено, что при всяком n, начиная с некоторого, для минимального полного проверяющего теста некоторой функции n переменных требуются все наборы, и что для полных проверяющих тестов относительно k-местных замещений log L(n) = 2k (1+o(1)) при log (n-k) = o(k). |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".