Еще раз об асинхронных процессорах

Памяти Виктора Ильича Варшавского

В начале 70-х, когда я только начал заниматься наукой, мой приятель Г. А. Копейкин однажды спросил меня, не хочу ли я познакомиться с группой ученых, которые так увлечены исследованиями, что могли бы заниматься наукой даже… в тюрьме.

Естественно, что это предложение меня сильно заинтересовало, и через несколько дней мы оказались в лаборатории Виктора Ильича Варшавского, где занимались теорией переключательных схем и конечных автоматов. Эта встреча повлияла на всю мою дальнейшую жизнь как в научном, так и человеческом плане – там я впервые увидел талантливых и увлеченных наукой людей, у которых горели глаза, что не часто было тогда и крайне редко теперь. И горение это не проходило долгие годы. Оно вдохновляло и другие группы ученых нашей страны, работавших в этой области, на получение результатов, совокупность которых позволила мне назвать это время Великой эпохой[1]. А каким юмором обладали эти люди! (Розенблюм Л. Я. Воспоминания. http://is.ifmo.ru, раздел "Беллетристика").

Взяться за перо меня заставили два события. Сначала о первом. 7 декабря 2004 г. PC Week/RE опубликовал статью Э. М. Пройдакова "Асинхронные процессоры", в которой речь шла о появлении на Западе нового класса процессоров, но ни слова не было сказано о роли советских ученых в становлении этого направления.

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

Меня не покидала эта мысль, но в конце года я все никак не мог сосредоточиться, и отложил написание текста на новогодние каникулы. Однако 3 января 2005 г. случилось второе, на сей раз трагическое событие – скончался Виктор Ильич Варшавский. Я испытал настоящий шок. Единственное, что удалось сделать, так это страницу (http://club.ifmo.ru/index.php?mode=3&index=15340) о Викторе Ильиче на сайте выпускников Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУ ИТМО), который многим известен в стране и в мире как ЛИТМО.

Теперь ученики в память о Викторе Ильиче написали статью, публикуемую ниже, в которой, в частности, показана роль Варшавского и его школы в создании "асинхроники".

В заключение хочется отметить, что кроме авторов указанной статьи существенный вклад в развитие этого раздела науки внесли также и такие ученики и соавторы В. И. Варшавского, как В. А. Песчанский, А. Г. Астановский, Р. Л. Финкельштейн и Б. С. Цирлин.

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

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

Наука потеряла одного из выдающихся своих представителей. 3 января после тяжелой болезни на 72-м году жизни скончался доктор технических наук, профессор Виктор Ильич Варшавский.

Поэт Лонгфелло как-то заметил: "Мы оцениваем самих себя по ощущениям того, на что мы способны, тогда как другие судят о нас по тому, что мы сделали".

Виктора Ильича нет больше с нами, поэтому нам (его коллегам, ученикам, друзьям и всему научному сообществу) необходимо осознать, что им было сделано, каково его наследие.

В. И. Варшавский

В. И. Варшавский сыграл большую роль в становлении кибернетики и искусственного интеллекта в нашей стране. В начале 1960-х годов он вместе с М. Л. Цетлиным начал проводить зимние школы под Ленинградом, привлекшие представительную группу ученых, специализирующихся в области математики, биологии, теории автоматов, коллективного поведения, распознавания образов, вычислительной техники, передачи информации и смежных областях. Тесную связь между этими проблемами В. И. Варшавский и М. Л. Цетлин, несомненно, почувствовали раньше других.

Позднее интересы Варшавского переключились на новую малоисследованную тогда область – создание асинхронных электронных устройств и систем, в которых не используются "часы". Такие системы обладают рядом полезных свойств, а методы их построения были неизвестны. Виктор Ильич явился пионером этого направления, что безоговорочно признано в "асинхронном сообществе" за рубежом.

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

По-видимому, асинхроника проистекает из основополагающей работы Д. Хаффмена (1954), который предложил модель асинхронного конечного автомата. Его труд знаменовал начало формальной стадии асинхроники, которая стартовала после скрытой от нас наивной фазы, и вызвал к жизни тысячи работ, посвященных противогоночному кодированию автоматов и расширениям модели. Между тем все известные модели асинхронных автоматов базируются на допущении, что инициатором перехода автомата в следующее состояние является изменение входного символа, а новый входной символ может быть подан лишь после завершения переходных процессов предыдущего такта. В противном случае будут иметь место сбои. Другим существенным ограничением моделей хаффменовского типа являются жесткая дисциплина смены входных сигналов, ужесточающая механизм взаимодействия автомата с внешней средой (обычно – соседние переходы). Это ограничение ставило под вопрос возможность композиции асинхронных автоматов и в конце концов стало тормозом на пути широкого практического использования подхода. Неясным оставался также вопрос, как избежать последствий нестабильности элементов, реализующих автоматы (равным образом не решенный и для синхронных реализаций).

Знаменательным для формальной фазы асинхронной науки надо признать 1959 год, когда Д. Е. Маллер и У. С. Бартки опубликовали отчет, в котором впервые предложили подход, связанный со схемами, не зависящими в своем поведении от задержек элементов. Сейчас такие схемы чаще называют асинхронными или самосинхронными (speed-independent, quasi delay insensitive, or self-timed). Р. Е. Миллер во втором томе своей книги[2] пытался привлечь внимание к маллеровскому подходу, но особого успеха не добился. Чрезмерное увлечение формалистикой в этом подходе оттолкнуло практиков, не увидевших изящных схемных решений. Неудачей окончилась и попытка Маллера воплотить свои идеи в рамках проекта Illiac II, по-видимому, из-за недостаточно высокого уровня технологической базы того времени и слабой проработки схемотехники базовых узлов.

В начале 1970-х годов Варшавский, имевший за плечами богатый опыт теоретических и прикладных исследований в таких областях, как пороговая и мажоритарная логика[3], коллективное поведение автоматов[4], однородные структуры[5], а также в смежных областях кибернетики, по стечению обстоятельств пытался вместе с одним из своих аспирантов разобраться, казалось бы, в тривиальном вопросе: как формально синтезировать схему асинхронного триггера, известного как гарвардский триггер. Странно, но тогда они сделать этого не смогли (это произошло несколько позже). В то время Варшавский, его коллеги и ученики не имели абсолютно никакого представления о работах, инициированных Маллером. Единственным выходом из затруднения для Варшавского была идея перехода из формальной стадии назад, в наивную фазу (что, как нам кажется, послужило одновременно началом критической стадии асинхронной науки). Виктор Ильич занялся изобретательством, что часто помогало ему в жизни. Его неимоверно развитая инженерная интуиция была тем волшебным паровозиком, который толкал Варшавского к теоретическому осмыслению решаемых задач.

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

Варшавский продолжал развивать свою идею и инициировал тотальный поиск литературы по асинхронике, в который погрузились все члены его команды. К 1975 г. был сделан не только скрупулезный анализ результатов западных ученых, но и развит общий подход к построению самосинхронных схем и устройств, интегрирующий все известные результаты. Практически были созданы основы общей теории самосинхронизации, интегрирующей известные фрагментарные подходы. В 1976 г. под редакцией Виктора Ильича на русском языке вышла в свет книга[6], в которой систематически изложены проблемы и решения в области самосинхронизации. Это издание в то время на Западе не было замечено, да этого и трудно было бы ожидать, поскольку еще не существовало ни асинхронного сообщества как такового, ни перевода книги на английский язык.

На фоне некоторого застоя в теории автоматов в 1960-е годы появилась и стала интенсивно развиваться новая научная дисциплина – теория сетей Петри. Развитие этой теории было относительно самостоятельным, но фактически не было автономным. Скорее всего она должна рассматриваться как ветвь общей теории автоматов, которая занимает ранее неисследованную нишу между конечными автоматами и машинами Тьюринга. Подавляющая часть работ по сетям Петри "обслуживает" проблематику общей теории систем и параллельного программирования. Тем не менее идейная сторона вопросов, связанных с выделением подкласса живых и безопасных сетей Петри и их исследованием, весьма близка к проблемам самосинхронизации. В книгe 1976 г. была продемонстрирована возможность прямой трансляции сети Петри из указанного подкласса в асинхронную схему в обход процедуры противогоночного кодирования состояний автомата.

Дальнейшие исследования нашей команды в области управления асинхронными процессами нашли отражение во второй книге[7], законченной в 1984 году и изданной в 1986 году под несколько скучным названием, навязанным редакцией. В 1990 г. ее перевод на английский[8] стал доступен асинхронному сообществу и она явилась предметом детального изучения в научных группах двух ведущих в области вычислительной техники университетов мира – в Беркли и Стэнфорде.

В 1987 г. в Хельсинском технологическом университете был опубликован цикл лекций Варшавского[9], прочитанных им в 1982-1983 гг. К сожалению, это издание малодоступно. Увидевшая свет в 1994 г. последняя книга с участием Варшавского[10] ориентирована на формальные модели описания, проверки и синтеза управляющих асинхронных устройств. Разработанные авторами идеи нашли применение в системе FORCAGE, предназначенной для автоматизированного проектирования (анализа и синтеза) самосинхронных схем.

Варшавский был несомненно абсолютно экстраординарным схемотехником и изобретателем. Он имеет более 150 авторских свидетельств СССР, патентов Японии и США, заявок на патенты.

Как ему удавалось синтезировать изящные основные, типовые схемы в стандартном базисе – такие, как триггеры, полусумматоры, автомат повторного вхождения, счетчики, буферные устройства и т. п., – загадка. Применение формальных методов в подавляющем большинстве случаев не позволяло воспроизвести оригинал даже при одинаковой начальной спецификации. Варшавского не интересовали "некрасивые" схемы – он оттачивал их до блеска. Асинхронный фольклор донес до нас историю создания С-элемента Маллера (в нашем окружении он назывался гистерезисным триггером или Г-триггером). Оказывается, первые две попытки Маллера (А и В) были неудачными, и только на букве С он остановился. Если пользоваться таким же подходом, то Варшавскому определенно не хватило бы множества больших и малых букв латинского алфавита и кириллицы. Во время посещения Советского Союза Нобелевский лауреат Поль Дирак прочел лекцию по философии физики, в ходе которой подошел к доске и написал: "Физические законы должны быть математически красивыми и простыми". Ту же мысль он высказал ранее в одной из своих лекций в Принстоне: "Вся моя жизнь – это написание красивых формул". Это же можно отнести и к схемам, предложенным Варшавским. Эта сторона деятельности Виктора Ильича, наверное, являлась главной в его творчестве. Если внимательно проанализировать многие асинхронные блоки, нашедшие сейчас практическое применение, то в них при желании можно увидеть прототипы схем, изобретенных Варшавским.

Одного перечисления схемотехнических новшеств, внесенных Варшавским в асинхронику, было бы достаточно, чтобы причислить его к элите ученых, занимающихся этой областью знаний. Но нельзя забыть и его вклад в теоретические аспекты этой науки. Он автор, соавтор и редактор восьми книг, пять из которых посвящены асинхронике (три из них – на английском), более 200 статей и отчетов (в последних он выступал в роли научного руководителя).

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

Перечислим важнейшие результаты деятельности Варшавского в асинхронике:

• самосинхронная реализация комбинационных логических схем и конечных автоматов (парафазная и четырехфазная с встроенными индикаторами), 1976;
• прямая трансляция управляющих спецификаций (типа параллельных асинхронных блок-схем алгоритмов и сетей Петри) в асинхронные схемы управления, 1976;
• работы по самосихронным кодам и реализации кодов в изменениях, 1981;
• самосинхронные интерфейсы, использующие двух- и трехстабильные линии с избыточным кодированием или временную избыточность, 1981–1988;
• надежные самотестируемые и саморемонтируемые архитектуры, 1982–1986;
• конструктивное доказательство функциональной полноты двухвходовых элементов в классе полумодулярных схем, 1981–1986;
• десинхронизация синхронных реализаций посредством замены синхронных часов асинхронным управляющим автоматом для улучшения временных свойств схем, 1994–1998;
• асинхронные реализации FIFO-структур и схем памяти, 1988–1993;
• проектирование асинхронных схем на основе квантовых устройств (квантовых точек, одноэлектронных транзисторов), 1995–1996;
• инициация работ по программной поддержке методов проектирования (синтеза и верификации) асинхронных схем, 1988;
• схемы, нечувствительные к задержкам в транзисторах и проводах, 1987;
• проектирование конвейерного управления и конвейерных схем с разной плотностью заполнения информацией (неплотных, полуплотных и плотных), 1979–1986;
• мостиковые транзисторные реализации (в том числе двух- и трехвходовых С-элементов), 1988.

Вне асинхроники достаточно упомянуть ставшие классическими результаты работы Варшавского в таких областях, как:

• пороговая логика и искусственные нейроны, которыми Виктор Ильич занимался в начале своей научной карьеры и к которым вернулся в последние годы[11];
• коллективное поведение автоматов, ставшее темой докторской диссертации Виктора Ильича. При этом заметим, что в последнее время заметно вырос интерес к поведению стохастических автоматов с переменной структурой[12].

Популярное изложение принципов децентрализованного управления сложными системами содержится в еще одной книге Виктора Ильича[13].

Удивительной была способность Варшавского создавать команду единомышленников. Его окружение работало как хорошо отлаженный механизм, который никогда не давал катастрофических сбоев, хотя отдельные зависания и тупики, конечно, случались. Варшавский никого не отпускал в автономное плаванье – он выдавал задания, обсуждал возможные пути их решения и постоянно был в курсе их выполнения. Такой контроль не вызывал обычно отрицательных эмоций, так как осуществлялся он по-дружески. Матерые сотрудники, правда, иногда втихомолку роптали – у них были собственные идеи, но прессинг они считали нормальным, поскольку репутация босса была хорошей защитой от неприятных внешних воздействий.

На всех этапах своей жизни Варшавский не переставал учиться и учить. Во многом его мировоззрение сформировалось на зимних школах под Ленинградом, которые он сам создал и которые уже были упомянуты Ему удалось привлечь таких выдающихся ученых и мыслителей, работающих в разных областях науки, как М. Л. Цетлин, М. М. Бонгард, Л. И. Розоноер, В. С. Гурфинкель, С. М. Осовец, Д. А. Поспелов, Я. А. Альтман и др. Эти школы питала мыслями и идеями всех своих участников более 10 лет. Варшавский принимал активное участие в работе школ М. А. Гаврилова (http://www.computer-museum.ru/galglory/gavrilov.htm, is.ifmo.ru/belletristic/sh), общепризнанного пионера в области теории автоматов в СССР, который всегда активно поддерживал работы команды Виктора Ильича.

Возможность побывать и поработать за границей в условиях жизни за железным занавесом Варшавскому представлялась редко. Но иногда это все-таки удавалось. Иностранные гости АН СССР, работающие в области теории автоматов, обязательно включали в программы своих поездок посещение лаборатории Варшавского. Ему принадлежит и инициатива объединения "могучей кучки" эстонских ученых. Ежегодные зимние совместные семинары с участием ленинградской команды были названы "встречами на Эльби" по имени местечка под Пярну, где они проводились. Варшавский был ключевой фигурой и в подготовке ядра эстонских национальных кадров высшей квалификации в области теории автоматов и ее приложений. Можно упомянуть также множество постоянно действующих семинаров, которыми он руководил.

Виктор Ильич был экстраординарной фигурой и в общечеловеческом плане. У него было громадное количество друзей и знакомых, которые любили и глубоко уважали его. Профессор охотно поддерживал контакты и всегда был готов помочь советом или делом.

Никто и не пытался сосчитать число его аспирантов, защит, на которых он с блеском выступал в качестве оппонента, или статей и книг, которые он отрецензировал (часто – с сарказмом и сногшибательной критикой).

Варшавский обладал неистребимым чувством юмора. Маленький пример. Получив почетный знак "Изобретатель СССР", он моментально отреагировал на это событие, произнеся фразу: "Оказывается, я изобрел СССР!". Анекдоты хлестали из него, как из пожарного брандспойта. Его розыгрыши, мгновенная реакция на происходящее, острые ремарки, убийственно меткие характеристики людей и событий вошли в научный фольклор. Он был незаменимым тамадой на банкетах, и многие его друзья, которые сами по себе были замечательными спичмейкерами, в его присутствии слегка сникали.

О покойном говорят только хорошее или ничего. Но Варшавский – это исключение из общих правил. Но мы все-таки хотим отметить три его недостатка.

Первый – Виктор Ильич всегда дымил как паровоз и в короткие промежутки времени, когда он под прессингом свой жены Натальи пытался "завязать" с курением, постоянно сосал сигарету, засунутую в рот "нештатным" концом. Наверное, эта пагубная привычка сыграла не последнюю роль в том, что оборвалась его яркая жизнь, но работать без сигарет он вряд ли бы смог.

Второй – его чересчур спортивная натура. В институтские годы Виктор Ильич занимался классической борьбой и достиг значительных успехов. Но начав работать, забросил спорт, но сохранил неистребимое желание выигрывать. Любил шахматы, хотя и не занимался ими серьезно, но обожал блиц и часто доводил коллег до отчаяния, потому что любой разговор начинался и кончался десятком партий.

Третий – любовь к групповому пению и соло при полном отсутствии музыкального слуха. Как человек самобытный, он предлагал свои собственные интерпретации, основанные не на мелодике, а скорее на рваном ритме (может быть, именно поэтому Виктор Ильич пришел в асинхронику). Интересно, что его участие в хоровом исполнении всегда вызывало "катастрофические отказы" – соисполнители сначала начинали ошибаться, а потом и вовсе прекращали петь. Правда, Варшавского это не смущало.

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

Вот такой это был человек.

В. И. Варшавский оставил множество последователей, которые развили его идеи и обогатили науку и практику новыми идеями и разработками. Если ранее они работали только в СССР и социалистических странах Восточной Европы, то к настоящему времени многие из них мигрировали в более дальние края и с честью влились в асинхронное сообщество, которое, по нашему общему мнению, в основном продолжает пребывать в формальной фазе своего развития. Критическая фаза по-прежнему только начинается. В чем она проявится и чем завершится – остается только ждать. Возможно, Варшавский наметил некоторые пути развития критической стадии асинхроники, как любимого своего детища; это нашло отражение в идеях, связанных с построением схем, нечувствительных к задержкам как в транзисторах, так и проводах, а особенно в десинхронизации. 20–25 лет тому назад казалось, что асинхроника должна вот-вот победить синхронный подход. Этого не произошло, наверное, потому, что рутинная компьютерная технология развивалась куда более быстрыми темпами, чем асинхроника. Комбинация обоих подходов, возможно, станет в будущем реально продуктивной.

Заканчивая, имеет смысл возвратиться к цитатам. Французский геометр Гаспар Монж сказал когда-то, что "очарование, сопровождающее науку, может победить свойственное людям отвращение к напряжению ума". Варшавский, можно с уверенностью утверждать, всей своей жизнью продемонстрировал, что он был триумфатором в этом отношении.

Мы будем помнить его всегда.

Л. Розенблюм, М. Кишиневский, А. Кондратьев, О. Маевский, Ю. Мамруков, В. Мараховский, Н. Стародубцев, А. Таубин, А. Яковлев

Статья опубликована в PC Week/RE #7 от 01.03.2005 г., стр. 37.

Примечания

1. Шалыто А. А. У нас была Великая эпоха! http://www.computer-museum.ru/histsoft/epoch.htm

2. Миллер Р. Теория переключательных схем. Т. 2. М., Наука, 1971, 304 с.

3. Варшавский В. И. Некоторые вопросы теории логических сетей, построенных из пороговых элементов. В кн. “Вопросы теории математических машин” под ред. Ю. Я. Базилевского. М., Физматгиз, 1962.

4. Варшавский В. И. Коллективное поведение автоматов. М., Наука, 1973, 408 с.

5. Варшавский В. И., Мараховский В. Б., Песчанский В. А., Розенблюм Л. Я. Однородные структуры. Анализ. Синтез. Поведение. М., Энергия, 1973, 152 с.

6. Апериодические автоматы. Под редакцией В. И. Варшавского. М., Наука, 1976, 424 с.

7. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. Под редакцией В. И. Варшавского. М., Наука, 1986, 308 с.

8. Self-Timed Control of Concurrent Processes: The Design of Aperiodic Logical Circuits in Computers and Discrete Systems. V. I. Varshavsky, Ed. Kluwer Academic Publishers, 1990, p. 408.

9. Varshavsky V. I. Hardware Support of Parallel Asynchronous Processes. Helsinki, Finland: Digital Systems Laboratory. University of Technology. Series A: Research Report #2, 1987, p. 236.

10. Kishinevsky M., Kondratyev A., Taubin A., Varshavsky V. Concurrent Hardware. The Theory and Practice of Self-timed Design. J. Wiley, 1994, p.368.

11. Avedillo M. J. VLSI implementation of threshold logic: a comprehensive survey. IEEE Trans. Neural Networks, 14 (5), Sept. 2003.

12. Economides A., Kehagias A. The STAR automaton: expediency and optimality properties, IEEE Transactions on Systems, Man and Cybernetics, Part B, vol. 32, № 6, pp. 723-737, Dec. 2002.

13. Варшавский В. И., Поспелов Д. А. Оркестр играет без дирижера. М., Наука, 1984.