УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Заявка на конкурс исследовательских проектов в области автоматизации проектирования интегральных схем, проводимый компанией "Intel" и Московским физико-техническим институтом (техническим университетом)

Газета "Поиск", 2003, №7

1. Название проекта - "Декомпозиция и логический синтез булевых функций в базисе произвольных логических элементов"

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

   Возможны два подхода к построению комбинационных схем: от входов к выходу и от выхода к входам.

   Среди методов, основанных на первом подходе, отметим метод названный "формульным" (Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих логических устройств. Л.: Энергоиздат, 1981. 168 с.).

   При использовании этого метода, реализуемая булева функция и функция, описывающая элемент (порождающая функция элемента), задаются нормальными булевыми формулами, которые могут содержать скобки произвольной глубины, а их двухместные операции подчиняются сочетательному закону. Этот метод строит одновыходную схему, число элементов в которой, линейно зависит от числа букв в заданной формуле (Артюхов В.Л., Копейкин Г.А., Шалыто А.А. Об оценках сложности реализации булевых формул древовидными схемами из настраиваемых модулей //Автоматика и телемеханика. 1981. N11, 124-130).

   Среди методов, основанных на втором подходе, отметим метод названный "мультиплексорным" (Шалыто А.А. Логическое управление методы аппаратной и программной реализации алгоритмов. СПб.: Наука, 2000. 780 с.).

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

   В ходе разработки мультиплексорного метода:

   • выполнен обзор методов синтеза булевых функций схемами из произвольных логических элементов и показано, что несмотря на почти 50-летнюю историю эта задача не была решена;
   • введено понятие "мультиплексорная декомпозиция". Эта декомпозиция выполняется по образу мультиплексорной функции и является разделительной;
   • предложена стандартная схема, состоящая из мультиплексора и двух постоянных запоминающих устройств, реализующая мультиплексорную декомпозицию;
   • предложен метод построения мультиплексорных декомпозиций на основе нового эффективного подхода к решению логических уравнений, которые "красиво" не удавалось решать почти в течение 100 лет (Lowenheim L. Uber die Auflosung von Gleichungen in Logishen gebietkalkul. //Math. Annal. 1910. Bd.68);
   • предложены параметрическая и явная мультиплексорные формы для решения логических уравнений. По уравнению, записанному одной из таких форм, достаточно просто определяется число решений и для каждой из этих форм существует конструктивный и наглядный подход к построению каждого из решений. При этом выбор конкретного решения на каждом шаге в настоящее время выполняется эвристически;
   • предложен мультиплексорный метод реализации произвольных булевых функций на произвольных, априори заданных логических элементах, основанный на исследовании функциональных возможностей указанных элементов, составлении и решении в мультиплексорной форме для каждого шага декомпозиции логического уравнения. Предлагаемый метод является обобщением наиболее широко применяемого в настоящее время метода синтеза схем из мультиплексоров;
   • на примерах из литературы выполнено сравнение универсального (по виду функций, описывающих применяемые при синтезе элементы) предлагаемого метода с известными методами синтеза схем, использующими элементы определенного вида (например, мажоритарные). Показано, что и в этих случаях предлагаемый метод строит схемы, сложность которых обычно не выше, чем при использовании специализированных методов.

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

   Дальнейшее совершенствование этих методов связано с эффективным (по числу элементов) построением многовыходных комбинационных схем.

3. Руководитель проекта - Шалыто Анатолий Абрамович, доктор технических наук, профессор, заведующий кафедрой "Информационные системы" Санкт-Петербургского института точной механики и оптики (технического университета) СПбГИТМО (ТУ).

4. Состав группы - студенты и аспиранты кафедры "Компьютерные технологии" СПбГИТМО (ТУ), участники и призеры финалов студенческого командного чемпионата мира по программированию АСМ (Association for Computing Machinery), а также международного студенческого командного чемпионата по кибернетике ISA:
   • Штучкин Александр - студент 3-го курса, чемпион России по программированию (2001), участник финалов чемпионата ACM (2003, 2002);
   • Станкевич Андрей - студент 5-го курса, обладатель золотой и серебряной медалей чемпионата ACM (2001, 2000);
   • Корнеев Георгий - студент 5-го курса, обладатель золотой и серебряной медалей чемпионата ACM (2001,2000);
   • Казаков Матвей - аспирант первого года, третье место на чемпионате ACM (1999);
   • Левкин Владимир - аспирант первого года, третье место на чемпионате ACM (1999);
   • Шамгунов Никита - аспирант второго года, трехкратный чемпион Урала по программированию (2000, 1999, 1998), участник финалов чемпионата ACM (2000, 1999).
   • Туккель Никита - аспирант четвертого года, первое место на чемпионате Европы (ISA) по кибернетике (1999), второе место на чемпионате мира (ISA) по кибернетике (1999).
   • Наумов Лев - студент 4-го курса, трижды Соросовский студент.

5. Основные научные работы авторов проекта, выполненных в течение последнего года.

   Непосредственно по теме проекта:

   1. Шалыто А.А. Мультиплексорный метод реализации булевых функций схемами из произвольных логических элементов //Раздел 3.5 в книге "Управление в условиях неопределенности". СПб.: СПбГТУ, 2002, с.186-194.
   2. Шалыто А.А. Мультиплексорный метод реализации булевых функций схемами из произвольных логических элементов //Известия РАН. Теория и системы управления. 2003. N1. (Shalyto A.A. Multiplexor Method for Realization of Boolean Functions by Circuits Composed of Arbitrary Logical Elements //Journal of Computer and Systems Sciences International. 2003. Vol.42. N1, p.101-105).

   Близко к теме проекта:

   3. Шалыто А.А. Реализация булевых формул и булевых функций однородными структурами //Известия РАН. Теория и системы управления. 2002. N2. (Shalyto A.A. Realization of Boolean Formulas and Boolean Functions by Homogeneous Structures //Journal of Computer and Systems Sciences International. 2002. Vol.41. N2, p.264-273. Программирование с использованием автоматов - автоматное программирование:
   4. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. N2. С.144-149. Статья размещена на сайте is.ifmo.ru.
   5. Шалыто А.А., Туккель Н.И. Реализация автоматов при программировании событийных систем //Программист. 2002. N4, с.74-80. Статья размещена на сайте is.ifmo.ru.
   6. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы //Программист. 2002. N8, с.82-90. Статья размещена на сайте is.ifmo.ru.
   7. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные //Программирование. 2002. N5, с.12-26. Статья размещена на сайте is.ifmo.ru (Shalyto A.A., Tukkel N.I. Translating Iterative Algorithms into Automation Ones //Programming and Computer Software. 2002. 28(5).
   8. Шалыто А.А., Туккель Н.И. Алгоритмизация и программирование логических и событийных систем на основе конечных автоматов //Раздел 3.4 в книге "Управление в условиях неопределенности". СПб.: СПбГТУ, 2002, с.141-186.
   9. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Реализация рекурсивных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2002. N5, с.72-99.
   10. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Задача о ходе коня //Мир ПК. 2003. N1, с.152-155. Статья размещена на сайте is.ifmo.ru.
   11. Шалыто А.А., Туккель Н.И. Танки и автоматы //BYTE/Россия. 2003. N2, с.69-73.

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

   Названия работ руководителя проекта, выполненных в предыдущие годы, приведены на сайте http://is.ifmo.ru в разделе "Персоналии".