![]() |
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
С увеличением производительности микропроцессоров за последние годы произошло и увеличение их энергопотребления (в тысячи раз): некоторые схемы рассеивают более 100 Вт тепла и требуют вентиляторов, теплоотводов и даже жидкостных систем охлаждения. Согласно анализу ITRS-2001, при переходе к 22-нм технологии интенсивность выделение тепла процессором составит 5-10 млн Вт/кв.см, даже при использовании самых современных материалов. При таких объёмах тепловыделения традиционные методы отвода тепла становятся малоэффективными. Выходом в данной ситуации может послужить переход к вычислительным устройствам, реализующим обратимые вычисления. На сегодняшний день обратимые вычисления являются важнейшим направлением теоретических исследований не только в силу указанной причины, но и потому, что в рамках данного направления можно решать фундаментальные вопросы об организации компьютерных вычислений. Здесь имеется в виду исследование базового понятия однонаправленности, лежащего в основе всей современной криптографии. Проект предполагает создать фундамент для глубоких исследований данных вопросов.
With the increase in microprocessor performance in recent years has occurred and an increase in their energy consumption (thousands of times): some circuits dissipate more than 100 watts of heat and require fans, heat sinks, and even liquid cooling systems. According to the analysis ITRS-2001, the transition to 22-nm technology intensity of heat generation processor will be 5-10 million watts / cm², even using the most modern materials. With such volumes of the traditional methods of heat dissipation of heat are ineffective. The solution in this situation can serve as a transition to a computing device that implements reversible computing. Today reversible computing is the most important area of theoretical research not only because of this reason, but also because in the framework of this direction can solve fundamental questions about the organization of computing. This refers to the study of the basic concepts of one-pointedness, which is the basis of all modern cryptography. The project plans to create a foundation for in-depth studies of these issues.
В результате изучения свойств схем из обратимых логических элементов предполагается получение новых подходов к синтезу схем из обратимых логических элементов. Данные предварительных исследований и научного задела коллектива позволяют с достаточной уверенностью предполагать выполнение данного пункта плана. Следующим научным результатом первого года работы над проектом будут теоретические исследования однонаправленных логических схем и систематизация таких схем, а также проработка вопросов их реализации, в результате чего будет заложена основа для дальнейших исследований по теме проекта. Далее, на основе разработанных подходов будут созданы методы и алгоритмы синтеза схем из обратимых логических элементов с их предварительной программной реализацией и апробацией. Все полученные результаты будут оригинальными и изложены в статьях и докладах на научных конференциях.
1. Проведены предварительные исследования обратимых схем, реализующих заданное булево отображение с использованием и без использования дополнительной памяти (дополнительных входов). Доказаны некоторые теоретические результаты, связанные с их свойствами. 2. Исследованы различные существующие алгоритмы синтеза обратимых схем: переборные алгоритмы (непереборные быстрые алгоритмы и алгоритмы снижения сложности обратимой схемы). 3. Исследованы различные способы снижения сложности обратимых схем. Доказаны необходимое и достаточное условие коммутируемости двух обратимых логических элементов и предложены различные эквивалентные замены композиций обратимых логических элементов с доказательством корректности таких замен при помощи операций на множествах. Также рассмотрены вопросы асимптотической сложности и глубины обратимых схем. 4. Теоретически рассмотрено применение обратимых схем для решения задачи схемной реализации некоторых вычислительно асимметричных преобразований. 5. Предложен метод синтеза схем, основанный на разложение Э. Гильберта.
1. Разработан новый алгоритм синтеза обратимых схем, , имеющий асимптотически оптимальную сложность и позволяющий (в некоторых случаях) получать обратимые схемы с лучшими характеристиками. 2. Предложены новые подходы к синтезу схем, использующие спектры Рида-Маллера и разложение Гильберта. 3. Получены оценки сложности обратимых схем некоторых специальных типов. 4. Разработан инкрементальный метод оптимизации 2-го порядка. 5. Разработаны модели данных для представления функций алгебры логики и схем логических элементов.
МГУ имени М.В.Ломоносова | Координатор |
МГТУ им. Н.Э. Баумана, каф. ИУ-8 | Соисполнитель |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2016 г.-31 декабря 2016 г. | Разработка теоретических основ проектирования алгоритмического и аппаратного обеспечения на основе схем обратимых логических элементов |
Результаты этапа: 1. Разработан новый алгоритм синтеза обратимых схем, , имеющий асимптотически оптимальную сложность и позволяющий (в некоторых случаях) получать обратимые схемы с лучшими характеристиками. 2. Предложены новые подходы к синтезу схем, использующие спектры Рида-Маллера и разложение Гильберта. 3. Получены оценки сложности обратимых схем некоторых специальных типов. 4. Разработан инкрементальный метод оптимизации 2-го порядка. 5. Разработаны модели данных для представления функций алгебры логики и схем логических элементов. | ||
2 | 1 января 2017 г.-31 декабря 2017 г. | Разработка методов синтеза схем обратимых логических элементов |
Результаты этапа: Проведено исследование обратимых логических схем, построенных из элементов NOT, CNOT, CСNOT. Рассматривались схемы, реализующие подстановки _2^n→_2^n с использованием q дополнительных линий (дополнительной памяти). Для этого случая вводятся функции, аналогичные классическим функциям Шеннона: сложность схемы L (n, q), как функция от числа входов n и числа дополнительных входов q, и глубина схемы D (n, q), как функция тех же параметров. Для этих функций доказаны общие нижние границы. Кроме того, предложен новый, основанный на теоретико-групповом подходе, алгоритм синтеза схем из обратимых логических элементов, без использования дополнительных входов. Получена верхняя оценка сложности алгоритма. Использовались методы дискретной математики и комбинаторики. Исследование является полностью оригинальным и находится на мировом уровне, что подтверждается отзывами зарубежных специалистов и высокой оценкой докладов (с изложением промежуточных результатов) на международных и российских конференциях. Подготовлен обзор современного состояния теории схем из обратимых логических элементов, включающий как общие вопросы, так и математические вопросы обратимых вычислений, обратимых языков программирования, синтез сбоеустойчивых обратимых схем и реализации обратимых элементов. Обзор оригинален и, в силу широты охватываемых вопросов, востребован как материал введения в проблему и постановки задач (МГУ им. М. В. Ломоносова, МГТУ им. Н. Э. Баумана). Изучался вопрос сложности и глубины обратимых схем, в условиях ограничения на количество используемых дополнительных входов: функции Шеннонa сложности и глубины обратимой схемы при некоторых ограничениях на количество дополнительных входов. Получены верхние асимптотические границы для функций Шеннонa для синтеза обратимых схем с дополнительной памятью (разработан аналог метода Лупанова). Все полученные результаты являются новыми. Исследования находятся на переднем крае развития математической кибернетики и теории синтеза управляющих схем. Исследовались различные модели обратимых вычислений, в частности, обратимые клеточные автоматы и связь обратимости с поведением обратимых клеточных автоматов при их применении в блочных шифрах. Изучается влияния наличия дополнительной памяти (дополнительных, «мусорных» линий) на сложность реализации обратимой схемы, использование спектральных свойств булевых функций, описывающих обратимые преобразования, в алгоритмах синтеза схем из обратимых элементов (в частности, для поиска декомпозиции обратимых преобразований с целью уменьшения сложности соответствующих схем), построение асимметричных криптографических алгоритмов на базе преобразований, реализуемых обратимыми логическими элементами. Построен новый алгоритм для нахождения числа нулей булевых полиномов, заданных матрицей своих мономов. Получена формула для числа нулей булева полинома с разделяющимися переменными обобщающая известную лемму о рандомизации, найдены новые соотношения для спектров линейных кодов служащих основанием для оценок их корректирующих способностей. Методы исследования традиционны для дискретной математики и теории синтеза схем, а все результаты оригинальны. Начаты исследования обратимых вычислений как важнейшего случая алгебраических и их альтернативы численному параллелизму (следуя подходу Н. Н. Непейводы). Исследования находятся на переднем крае математической кибернетики и современной теории программирования. Также изучалась проблема синтеза сбоеустойчивых ИС на базе подходов, основанных на использовании помехозащищенного кодирования, использовании обратимой логики и самопроверяемых обратимых схем. Выявлены особенности данной задачи, отличающие ее от известной задачи кодирования сообщений. В частности, выяснено, что обычные характеристики кода для рассматриваемой задачи не являются определяющими и описан блоковый линейный нециклический R-код с проверкой на четность с произвольным числом информационных символов, важным свойством которого является возможность обеспечивать технологической защитой только часть основной схемы (ОС). Код относится к классу SEC/SED, хотя и имеет кодовое расстояние, равное 2, как следствие безошибочности вычисления бита четности выходного вектора ОС. Полученные результаты востребованы (ИППМ РАН). | ||
3 | 1 января 2018 г.-31 декабря 2018 г. | Разработка теоретических основ проектирования алгоритмического и аппаратного обеспечения на основе схем обратимых логических элементов |
Результаты этапа: |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".
№ | Имя | Описание | Имя файла | Размер | Добавлен |
---|---|---|---|---|---|
1. | Заключительный отчёт | OTChYoT_2018-12-19.docx | 50,7 КБ | 17 июня 2019 [sgur] |