![]() |
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
В заявке на грант были сформулированы следующие цели. Будут развиты созданные ранее и предложены новые эффективные методы синтеза схем для "типичных" и самых "сложных" функций алгебры логики в ряде "традиционных" моделей дискретных управляющих систем с определенными ограничениями на структуру и параметры схем. С помощью этих методов для сложности указанных функций в некоторых классах схем (контактных схем с различными ограничениями на смежные контакты, предикатных схем в ряде базисов и др.) будут получены асимптотические оценки, имеющие, как правило, высокую степень точности. Кроме того, будет установлена возможность реализации указанных функций схемами из некоторых классов, оптимальными как по сложности, так и по задержке на уровне оценок высокой или близкой к ней степени точности. Будет исследована сложность и структура оптимальных схем для ряда функций, встречающихся в приложениях. Будут получены, в частности, оценки высокой степени точности для сложности реализации мультиплексорной функции в некоторых классах схем, описана структура оптимальных и близких к ним контактных схем и схем из функциональных элементов для некоторых симметрических функций и др. Будет разработан ряд новых методов "вложения" схем в различные регулярные структуры (в плоские прямоугольные решетки - топологическую модель СБИС, в единичные кубы и др.). Будет продолжена, в частности, разработка методов реализации функций алгебры логики клеточными схемами различных типов, а также схемами, вложенными в гиперкуб. Будут найдены новые примеры полных схемных базисов, допускающих константные верхние оценки функций Шеннона длины проверяющих тестов при различных типах неисправностей функциональных элементов. Будут получены новые оценки функций Шеннона длины теста при неисправностях на входах схем. Будут созданы модифицированные варианты разработанных методов, ориентированные на решение задач логического и топологического синтеза СБИС.
Разработаны методы эффективной реализации функций алгебры логики (ФАЛ) схемами из некоторых классов, связанных, как правило, с введением определенных ограничений на структуру и параметры схем одного из основных типов. В каждом из этих классов получены новые более точные асимптотические оценки функции Шеннона, которая равна сложности реализации самой сложной ФАЛ от n булевых переменных (БП), n=1,2, …, схемами данного класса. Полученные оценки являются, как правило, либо асимптотическими оценками высокой степени точности (АОВСТ), которые устанавливают поведение функции Шеннона с точностью до асимптотики первого остаточного члена ее «стандартного» асимптотического разложения, либо близкими к ним оценками. Так, получены близкие к АОВСТ оценки функции Шеннона для сложности обобщенных BDD, где выбор одной из двух дуг, исходящих из любой вершины схемы, не являющейся ее стоком, определяется значением приписанной ей базисной ФАЛ, зависящей от входных БП схемы, а число указанных вершин определяет ее сложность. Установлены АОВСТ функции Шеннона для сложности предикатных схем в некоторых новых базисах и АОВСТ функции Шеннона для сложности формул с глубиной альтернирования 3, реализующих ФАЛ из некоторых классов, связанных с грамматиками, имеющими конечное число состояний. Получены АОВСТ функции Шеннона для сложности формул в базисах из функциональных элементов с прямыми и итеративными входами, являющихся итеративными модификациями стандартного базиса. Установлен ряд фактов, показывающих, что получение аналогичных результатов для произвольного базиса является сложной задачей. Разработаны новые более эффективные методы синтеза схем из функциональных элементов (СФЭ) в стандартном базисе с ограничениями на ветвление выходов элементов. Для произвольной квазимультиплексорной ФАЛ получены нетривиальные нижние оценки сложности ее реализации в классах формул и СФЭ стандартного базиса. При этом в некоторых случаях доказаны верхние оценки, близкие к нижним. В модели задержки СФЭ, где задержка базисного элемента положительна и задается произвольно для каждого входа, каждого возможного варианта подключения других элементов к этому входу, а также каждого набора значений остальных входов данного элемента, получены близкие к АОВСТ оценки соответствующей функции Шеннона для задержки ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с их оптимизацией как по динамической мощности, так и по сложности. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, сложность которой близка к АОВСТ соответствующей функции Шеннона, а динамическая мощность растет линейно по числу переменных исходной ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с оптимизацией получаемой схемы как по глубине, так и по размерности единичного куба, допускающего ее изоморфное вложение. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, размерность которой отличается от значения соответствующей функции Шеннона не более чем на константу, а глубина растет линейно по числу переменных исходной ФАЛ. Доказано существование некоторых конечных полных базисов, в которых функция Шеннона длины полного проверяющего теста относительно инверсных неисправностей на выходах элементов не превосходит константы, а также установлено, что во всяком конечном полном базисе функция Шеннона длины единичного проверяющего теста относительно константных и инверсных неисправностей на выходах элементов не превосходит константы. Доказано, что для произвольной отличной от константы булевой функции существуют тестопригодные контактные схемы либо с одной дополнительной существенной переменной, либо с одним дополнительным полюсом, которые допускают единичные проверяющие тесты линейной по числу переменных длины. Установлено, что для почти всех булевых функций n переменных существуют двухполюсные контактные схемы с линейной по числу переменных длиной полного проверяющего теста размыкания (замыкания). Получены новые оценки (в ряде случаев асимптотически точные или точные по порядку роста) функций Шеннона длин полного проверяющего и полного диагностического теста относительно различных типов слипаний переменных булевой функции (в частности, линейных, симметрических, монотонных симметрических слипаний), относительно примитивных сдвигов влево входов схем, а также относительно вытесняющих неисправностей входов схем.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 17 мая 2012 г.-31 декабря 2012 г. | Этап 2012 года |
Результаты этапа: Разработаны методы эффективной реализации функций алгебры логики (ФАЛ) схемами из некоторых классов, связанных, как правило, с введением определенных ограничений на структуру и параметры схем одного из основных типов. В каждом из этих классов получены новые более точные асимптотические оценки функции Шеннона, которая равна сложности реализации самой сложной ФАЛ от n булевых переменных (БП), n=1,2,… , схемами данного класса и имеет, обычно, порядок роста $\frac{2^n}{n}$ (первый тип), либо $\frac{2^n}{\log n}$ (второй тип). Полученные оценки являются, как правило, либо асимптотическими оценками высокой степени точности (АОВСТ), которые устанавливают значение функции Шеннона от n БП с относительной погрешностью (ОП) вида $O(\frac{1}{n})$ и $O(\frac{1}{\log n})$ для 1-го и 2-го типа функций соответственно, либо близкими к АОВСТ 1-го типа оценками, имеющими ОП $O(\frac{\log \log n}{n})$. Так, получены близкие к АОВСТ оценки функции Шеннона 1-го типа для сложности обобщенных BDD, где выбор одной из двух дуг, исходящих из любой вершины схемы, не являющейся ее стоком, определяется значением приписанной ей базисной ФАЛ, зависящей от входных БП схемы, а число указанных вершин определяет ее сложность. Установлены АОВСТ функции Шеннона 1-го типа для сложности предикатных схем в некоторых новых базисах и АОВСТ функции Шеннона 2-го типа для сложности формул с глубиной альтернирования 3, реализующих ФАЛ из некоторых классов, связанных с автоматными языками. Получены новые оценки функции Шеннона 1-го типа для сложности таких схем из функциональных элементов (СФЭ) в стандартном базисе, в которых из любой вершины исходит не более двух дуг, устанавливающие ее значение (от n БП) с ОП $O(\frac{\log^2 n}{n})$. Получена новая более высокая нижняя оценка сложности реализации мультиплексорной ФАЛ в классе СФЭ в стандартном базисе. Предложены некоторые новые содержательные модели задержки и динамической мощности СФЭ, в рамках которых установлен линейный относительно числа БП реализуемых ФАЛ порядок роста соответствующих функций Шеннона, причем для первой из них доказано существование асимптотики и выявлен характер зависимости от базиса константы, определяющей эту асимптотику. Установлено асимптотическое поведение функции Шеннона для площади клеточных схем ограниченной высоты с кратными входами, реализующих ФАЛ из некоторых нулевых инвариантных классов. Доказано, что функция Шеннона длины полного проверяющего теста относительно произвольных инверсных неисправностей на выходах элементов для СФЭ в одном специальном конечном полном базисе и функция Шеннона длины единичного проверяющего теста относительно произвольных константных и инверсных неисправностей на выходах элементов для СФЭ в произвольном конечном полном базисе принимают значения от 2 до 4. Установлено точное значение 2 функции Шеннона длины полного проверяющего теста и порядок роста $2^{n/2}$ функции Шеннона длины полного диагностического теста относительно примитивных циклических сдвигов влево переменных в ФАЛ от n БП. | ||
2 | 5 марта 2013 г.-31 декабря 2013 г. | Этап 2013 года |
Результаты этапа: Разработаны методы синтеза и с их помощью получены асимптотические оценки высокой степени точности (АОВСТ) функции Шеннона для сложности формул в базисах из функциональных элементов с прямыми и итеративными входами, являющихся итеративными модификациями стандартного базиса. Расширены классы тех "итеративных" базисов, в которых поведение данной функции Шеннона установлено с точностью до порядка. Разработаны новые более эффективные методы синтеза схем из функциональных элементов (СФЭ) в стандартном базисе с ограничениями на ветвление выходов элементов. Для произвольной квазимультиплексорной функции алгебры логики (ФАЛ) получены нетривиальные нижние оценки сложности ее реализации в классе параллельно-последовательных контактных схем и классе формул стандартного базиса. При этом в некоторых случаях доказаны верхние оценки, близкие к нижним. В модели задержки СФЭ, где задержки базисных элементов определяются емкостными параметрами входов и выходов и задаются произвольно для каждого входа и каждого возможного варианта подключения других элементов к этому входу, получены асимптотически точные оценки соответствующей функции Шеннона для задержки ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с их оптимизацией как по динамической мощности, так и по сложности. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, сложность которой близка к АОВСТ соответствующей функции Шеннона, а динамическая мощность растет линейно по числу переменных исходной ФАЛ. При некоторых ограничениях на глубину СФЭ и при фиксированной высоте 3 и более для клеточных схем с кратными входами установлена асимптотика функции Шеннона для площади этих схем. Разработан метод синтеза СФЭ в стандартном базисе с оптимизацией получаемой схемы как по глубине, так и по размерности единичного куба, допускающего ее изоморфное вложение. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, размерность которой отличается от значения соответствующей функции Шеннона не более чем на константу, а глубина растет линейно по числу переменных исходной ФАЛ. Найдены новые примеры полных схемных базисов, в которых функция Шеннона длины полного проверяющего теста относительно произвольных константных неисправностей на выходах элементов не превосходит константы. Доказано, что в любом конечном полном базисе функция Шеннона длины единичного проверяющего теста относительно произвольных константных и инверсных неисправностей на выходах элементов не меньше 3 (и, значит, лежит в пределах от 3 до 4). Доказано, что для произвольной отличной от константы ФАЛ возможны тестопригодные реализации контактными схемами как системы функций, состоящей из этой ФАЛ и ее отрицания, так и некоторой надфункции этой ФАЛ. Указанные тестопригодные реализации допускают такие единичные проверяющие тесты и полные проверяющие тесты замыкания (размыкания), которые имеют линейную по числу переменных длину. Установлено точное значение функции Шеннона длины полного диагностического теста относительно множественных линейных слипаний входов схем. Уточнено поведение функций Шеннона длины диагностического и проверяющего тестов относительно вытесняющих неисправностей входов схем. Получены нетривиальные оценки различных функций Шеннона длины диагностического теста относительно некоторых слипаний входов схем. | ||
3 | 3 апреля 2014 г.-31 декабря 2014 г. | Этап 2014 года |
Результаты этапа: За все время выполнения проекта получены следующие основные результаты. Разработаны методы эффективной реализации функций алгебры логики (ФАЛ) схемами из некоторых классов, связанных, как правило, с введением определенных ограничений на структуру и параметры схем одного из основных типов. В каждом из этих классов получены новые более точные асимптотические оценки функции Шеннона, которая равна сложности реализации самой сложной ФАЛ от n булевых переменных (БП), n=1,2, …, схемами данного класса. Полученные оценки являются, как правило, либо асимптотическими оценками высокой степени точности (АОВСТ), которые устанавливают поведение функции Шеннона с точностью до асимптотики первого остаточного члена ее «стандартного» асимптотического разложения, либо близкими к ним оценками. Так, получены близкие к АОВСТ оценки функции Шеннона для сложности обобщенных BDD, где выбор одной из двух дуг, исходящих из любой вершины схемы, не являющейся ее стоком, определяется значением приписанной ей базисной ФАЛ, зависящей от входных БП схемы, а число указанных вершин определяет ее сложность. Установлены АОВСТ функции Шеннона для сложности предикатных схем в некоторых новых базисах и АОВСТ функции Шеннона для сложности формул с глубиной альтернирования 3, реализующих ФАЛ из некоторых классов, связанных с грамматиками, имеющими конечное число состояний. Получены АОВСТ функции Шеннона для сложности формул в базисах из функциональных элементов с прямыми и итеративными входами, являющихся итеративными модификациями стандартного базиса. Установлен ряд фактов, показывающих, что получение аналогичных результатов для произвольного базиса является сложной задачей. Разработаны новые более эффективные методы синтеза схем из функциональных элементов (СФЭ) в стандартном базисе с ограничениями на ветвление выходов элементов. Для произвольной квазимультиплексорной ФАЛ получены нетривиальные нижние оценки сложности ее реализации в классах формул и СФЭ стандартного базиса. При этом в некоторых случаях доказаны верхние оценки, близкие к нижним. В модели задержки СФЭ, где задержка базисного элемента положительна и задается произвольно для каждого входа, каждого возможного варианта подключения других элементов к этому входу, а также каждого набора значений остальных входов данного элемента, получены близкие к АОВСТ оценки соответствующей функции Шеннона для задержки ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с их оптимизацией как по динамической мощности, так и по сложности. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, сложность которой близка к АОВСТ соответствующей функции Шеннона, а динамическая мощность растет линейно по числу переменных исходной ФАЛ. Разработан метод синтеза СФЭ в стандартном базисе с оптимизацией получаемой схемы как по глубине, так и по размерности единичного куба, допускающего ее изоморфное вложение. Он позволяет для произвольной ФАЛ строить такую реализующую ее СФЭ, размерность которой отличается от значения соответствующей функции Шеннона не более чем на константу, а глубина растет линейно по числу переменных исходной ФАЛ. Доказано существование некоторых конечных полных базисов, в которых функция Шеннона длины полного проверяющего теста относительно инверсных неисправностей на выходах элементов не превосходит константы, а также установлено, что во всяком конечном полном базисе функция Шеннона длины единичного проверяющего теста относительно константных и инверсных неисправностей на выходах элементов не превосходит константы. Доказано, что для произвольной отличной от константы булевой функции существуют тестопригодные контактные схемы либо с одной дополнительной существенной переменной, либо с одним дополнительным полюсом, которые допускают единичные проверяющие тесты линейной по числу переменных длины. Установлено, что для почти всех булевых функций n переменных существуют двухполюсные контактные схемы с линейной по числу переменных длиной полного проверяющего теста размыкания (замыкания). Получены новые оценки (в ряде случаев асимптотически точные или точные по порядку роста) функций Шеннона длин полного проверяющего и полного диагностического теста относительно различных типов слипаний переменных булевой функции (в частности, линейных, симметрических, монотонных симметрических слипаний), относительно примитивных сдвигов влево входов схем, а также относительно вытесняющих неисправностей входов схем. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".