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



Заявка на конкурс исследовательских проектов в области автоматизации проектирования интегральных схем, проводимый компанией "Intel" и Московским физико-техническим институтом (техническим университетом)
Газета "Поиск", 2003, №7
  1. Название проекта - "Декомпозиция и логический синтез булевых функций в базисе произвольных логических элементов"

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

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

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

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

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

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

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

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

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

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

  4. Состав группы - студенты и аспиранты кафедры "Компьютерные технологии" СПбГИТМО (ТУ), участники и призеры финалов студенческого командного чемпионата мира по программированию АСМ (Association for Computing Machinery), а также международного студенческого командного чемпионата по кибернетике ISA:

  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).

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

    1. Шалыто А.А. Реализация булевых формул и булевых функций однородными структурами //Известия РАН. Теория и системы управления. 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. Программирование с использованием автоматов - автоматное программирование:
    2. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. N2. С.144-149. Статья размещена на сайте is.ifmo.ru.
    3. Шалыто А.А., Туккель Н.И. Реализация автоматов при программировании событийных систем //Программист. 2002. N4, с.74-80. Статья размещена на сайте is.ifmo.ru.
    4. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Ханойские башни и автоматы //Программист. 2002. N8, с.82-90. Статья размещена на сайте is.ifmo.ru.
    5. Шалыто А.А., Туккель Н.И. Преобразование итеративных алгоритмов в автоматные //Программирование. 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).
    6. Шалыто А.А., Туккель Н.И. Алгоритмизация и программирование логических и событийных систем на основе конечных автоматов //Раздел 3.4 в книге "Управление в условиях неопределенности". СПб.: СПбГТУ, 2002, с.141-186.
    7. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Реализация рекурсивных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2002. N5, с.72-99.
    8. Шалыто А.А., Туккель Н.И., Шамгунов Н.Н. Задача о ходе коня //Мир ПК. 2003. N1, с.152-155. Статья размещена на сайте is.ifmo.ru.
    9. Шалыто А.А., Туккель Н.И. Танки и автоматы //BYTE/Россия. 2003. N2, с.69-73.

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

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