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

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

Материал опубликован в еженедельнике PC WEEK/RE. 2005. № 7, с.37-39.

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

Это горение не проходило долгие годы. Оно вдохновляло и другие группы ученых нашей страны, работавших в этой области, на получение результатов, совокупность которых позволила мне назвать это время Великой эпохой (Шалыто А.А. "У нас была Великая эпоха!"). А каким юмором обладали эти люди! (Розенблюм Л.Я. Воспоминания, раздел "Беллетристика").

"Взяться за перо" меня заставили два события.

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

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

Меня не покидала эта мысль, но в конце года я все никак не мог сосредоточиться, и отложил написание текста на новогодние каникулы. Однако третьего января 2005 года случилось второе, на этот раз трагическое, событие - скончался Виктор Ильич Варшавский. Наступил шок. Единственное, что удалось сделать, - страницу о Викторе Ильиче на сайте выпускников Санкт-Петербургского государственного университета информационных технологий, механики и оптики (СПбГУ ИТМО), который многим известен в стране и в мире, как ЛИТМО.

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

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

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

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

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

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

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

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

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

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

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

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

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

В начале 70-х годов Варшавский, имевший за плечами богатый опыт теоретических и прикладных исследований в таких областях, как пороговая и мажоритарная логики [Варшавский В.И. Некоторые вопросы теории логических сетей, построенных из пороговых элементов. В кн. "Вопросы теории математических машин" под ред. Ю.Я. Базилевского. М., Физматгиз,1962], коллективное поведение автоматов [Варшавский В.И. Коллективное поведение автоматов. М., Наука, 1973, 408 с.], однородные структуры [Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Однородные структуры. Анализ. Синтез. Поведение. М., Энергия, 1973, 152 с.], а также в смежных областях кибернетики, по стечению обстоятельств пытался вместе с одним из своих аспирантов разобраться в, казалось бы, тривиальном вопросе - как формально синтезировать схему асинхронного триггера, известного как Гарвардский триггер. Странно, но тогда они сделать этого не смогли. (Это было сделано несколько позже). В то время Варшавский, его коллеги и ученики не имели абсолютно никакого представления о работах, инициированных Маллером. Единственным выходом из затруднения для Варшавского была идея перехода из формальной стадии назад, в наивную фазу (что, как нам кажется, послужило одновременно началом критической стадии асинхронной науки). Виктор Ильич занялся изобретательством, что часто помогало ему в жизни. Его неимоверно развитая инженерная интуиция была тем волшебным паровозиком, который толкал Варшавского к теоретическому осмыслению решаемых задач.

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

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

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

Дальнейшие исследования в области управления асинхронными процессами в нашей команде нашли отражение во второй книге [Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. Под редакцией В.И. Варшавского. М., Наука, 1986, 308 с.], законченной в 1984 году и изданной в 1986 году под несколько скучным названием, навязанным редакцией. В 1990 году ее перевод на английский [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.] стал доступен асинхронному сообществу и она явилась предметом детального изучения в научных группах двух ведущих в области вычислительной техники университетов мира - в Беркли и Стэнфорде.

В 1987 году в Хельсинском технологическом университете был опубликован цикл лекций Варшавского [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], прочитанных им в 1982-83 годах. К сожалению, это издание малодоступно. Изданная в 1994 году последняя книга с участием Варшавского [Kishinevsky M., Kondratyev A., Taubin A., Varshavsky V. Concurrent Hardware. The Theory and Practice of Self-timed Design. J.Wiley, 1994, p.368] ориентирована на формальные модели описания, проверки и синтеза управляющих асинхронных устройств. Разработанные авторами идеи нашли применение в системе FORCAGE, предназначенной для автоматизированного проектирования (анализа и синтеза) самосинхронных схем.

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

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

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

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

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

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

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

• в пороговой логике и искусственных нейронах, которыми Виктор Ильич занимался в начале своей научной карьеры и вернулся в последние годы [например, Avedillo M.J. VLSI implementation of threshold logic: a comprehensive survey. IEEE Trans. Neural Networks, 14(5), Sept. 2003];
• в коллективном поведении автоматов, ставшей темой докторской диссертации Варшавского. При этом заметим, что в последнее время значительно вырос интерес к поведению стохастических автоматов с переменной структурой [например, 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].

Популярное изложение принципов децентрализованного управления сложными системами содержится в еще одной книге Виктора Ильича [Варшавский В. И., Поспелов Д.А. Оркестр играет без дирижера. М., Наука, 1984].

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

На всех этапах своей жизни Варшавский не переставал учиться и учить. Во многом его мировоззрение сформировалось на зимних школах под Ленинградом, которые он сам создал и которые уже были упомянуты Ему удалось привлечь таких выдающихся ученых и мыслителей, работающих в разных областях науки, как М.Л.Цетлин, М.М.Бонгард, Л.И.Розоноер, В.С.Гурфинкель, С.М.Осовец, Д.А.Поспелов, Я.А.Альтман и др. Школы питали мыслями и идеями всех ее участников более 10 лет. Варшавский принимал активное участие в работе школ М.А.Гаврилова, общепризнанного пионера в области теории автоматов в СССР, который всегда активно поддерживал работы команды Варшавского.

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

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

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

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

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

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

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

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

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

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

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

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

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

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