В. М. ГЛУШКОВ — ПИОНЕР МАТЕМАТИЧЕСКОЙ ТЕОРИИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

Сергиенко И.В., Капитонова  Ю.В. г. Киев, Украина (Тезисы доклада)

Введение

В 1956-1982 гг. в Украинской Академии наук работал Виктор Михайлович Глушков, после защиты в Московском Государственном университете докторской диссертации по исследованию и решению обощенной пятой проблемы Гильберта, что составило ему славу одного из ведущих алгебраистов мира. Кроме математического образования В.М. Глушков имел техническое, поскольку прослушал полный курс на факультете теплофизики Новочеркасского политехнического института. Возглавив лабораторию вычислительной математики и техники Института математики АН УССР, известную своими работами по первым в СССР вычислительным машинам (МЭСМ, СЭСМ, Киев), В.М. Глушков сумел сформулировать программу научных исследований, в основе которой лежала фундаментальная идея интеграци кибернетики, математики и вычислительной техники.

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

Теория автоматов

Основные работы по теории цифровых автоматов, за которые В.М. Глушков получил Ленинскую премию в 1964 г., были написаны в период 1959-1961 гг. Они были связаны с построением математического аппарата проектирования устройств ЭВМ. В то время уже были известны некоторые алгоритмы синтеза комбинационных схем, сформулирован и исследован ряд важных математических задач, таких, как проблема полноты, оценка сложности реализации функций алгебры логики релейно-контактными схемами и др. Однако, процессы проектирования устройств ЭВМ основывались скорее на инженерной интуиции, искусстве и опыте разработчиков, чем на точном знании. В.М. Глушков одним из первых использовал прикладное значение понятия абстрактного автомата для построения практической методики формализованного проектирования схем устройств ЭВМ. Им были разработаны оригинальные методы анализа и синтеза абстрактных автоматов. В обзорной статье в журнале “Успехи математических наук” (1961 год) [1] абстрактная теория автоматов была впервые представлена как сформировавшаяся математическая теория с ясно определенным местом и связями с другими разделами компьютерных наук. В 1962 г. была издана монография “Синтез цифровых автоматов” [2], сыгравшая существенную роль в распространении формализованных методов проектирования устройств среди инженеров. Здесь впервые был рассмотрен весь комплекс задач построения устройств от описания алгоритма функционирования устройств до схемы, его реализующей.

На базе этих методов была реализована “Малая система синтеза цифровых автоматов” (на ЭВМ “Киев”), первый прототип будущих систем автоматизации проектирования ЭВМ.

Дискретные преобразователи

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

Композиция управляющего и операционного автоматов, рассмотренная в этих работах, представляет собой частный случай общего понятия дискретного преобразователя, которое исследовалось в дальнейшем в работах В.М. Глушкова и его учеников [3]. Эти исследования развивались в двух направлениях. Первое направление — исследование абстрактно-алгебраических задач, таких, как распознавание эквивалентности, оптимизации по времени работы дискретных преобразователей, изучение соотношений, систем образующих в полугруппах преобразований операционного автомата и др. 

Второе направление связано с разработкой прикладных систем автоматизации проектирования ЭВМ, языков для описания алгоритмов функционирования устройств, методов и алгоритмов проектирования устройств и их композиций.

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

Алгебра алгоритмов

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

На конкретных примерах микропрограммных алгебр, порожденных арифметическими микрооперациями и условиями на одномерных регистрах была продемонстрирована фундаментальная идея проектирования алгоритмов: для того чтобы получить требуемое представление алгоритма, его следует представить в подходящей алгебре и, изучив соотношения этой алгебры, преобразовать это представление, добиваясь улучшения тех или иных его характеристик — времени, памяти и т.п. Была доказана также фундаментальная теорема о регуляризации произвольных микропрограмм: преобразование, выполняемое любой микропрограммой, может быть представлено выражением в микропрограммной алгебре, порожденной теми же элементарными операторами и условиями, которые используются в данной микропрограмме [4]. Поскольку конструкции микропрограммной алгебры носят общий характер, а проектирование устройств ЭВМ представляет собой лишь одну из многих областей ее применения, впоследствии эту алгебру стали называть алгеброй алгоритмов или системой алгоритмических алгебр. Идея использования многоосновных алгебр для представления различных аспектов взаимодействия компонент ЭВМ является актуальной и по сей час, когда на первый план выдвигаются проблемы управления процессами в глобальных сетях (Internet и др.).

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

Значительный вклад в развитие алгебры алгоритмов был внесен Е.Л. Ющенко и Г.Е.Цейтлиным. Их монография “Алгебра, языки, программирование” [5], написанная совместно с В.М.Глушковым, переведена на многие языки и много лет служит базовой монографией по теории программирования.

Теория структур данных и параллельные вычисления

В середине 80-х годов стало ясно, что особую актуальность приобретают вопросы эффективности организации вычислений в ЭВМ.

С одной стороны, микроминиатюризация элементной базы, а с другой, явное выделение в компьютерах компоненты системного программного обеспечения, которая имела тенденцию к миграции в аппаратуру. Кроме того, модели и методы проектирования, получившие реализацию в различных средствах автоматизации проектирования (например, серия систем ПРОЕКТ, Чертеж, КАПР и др.), в перспективе должны были обеспечить проектирование архитектуры ЭВМ в целом. В виду этого были исследованы и получили развитие теория структур данных и методы блочного проектирования ЭВМ. Монография  В.М. Глушкова в соавторстве с Капитоновой Ю.В. и Летичевского А.А. “Автоматизация проектирования вычислительных машин” [6] явилась своеобразным продолжением представления моделей, методов и средств построения многомашинных и многопроцессорных ЭВМ с единой базой проектирования компонентов схемного и программного оборудования.

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

Внутренний интеллект ЭВМ

Когда появился язык АЛГОЛ-60, В.М. Глушков стал одним из первых его пропагандистов и сторонником широкого внедрения в практику программирования. В то же время он ясно осознавал пропасть, лежащую между структурой неймановской ЭВМ и языками высокого уровня. Наличие этой проблемы приводило к сложным процедурам трансляции и потере эффективности программ по сравнению с программированием в машинно-ориентированных языках. Тогда была сформулирована идея повышения уровня внутреннего языка ЭВМ, что можно рассматривать как развитие внутреннего, т.е. заложенного в аппаратуру, интеллекта ЭВМ. Эта идея не только требовала пересмотра множества машинных команд ЭВМ, но существенно изменяла технологию обработки программы в машине. Одной из возможных добавлений к этой обработке была многоуровневая интерпретация, а точнее, многоуровневая система трансляции с интерпретацией. Кроме теоретического обоснования этой идеи [7] был осуществлен ряд разработок ЭВМ под руководством В.М. Глушкова. Сначала был ПРОМІНЬ — машина с элементами интерпретации языка высокого уровня. Затем проект машины “Украина”, где планировалось в качестве внутреннего языка использовать АЛГОЛ. Проект этот не был реализован. Наиболее полно аппаратную реализацию языков высокого уровня удалось осуществить в малых ЭВМ серии МИР (МИР-1, МИР-2, МИР-3). Структурная интерпретация языков высокого уровня МИР и АНАЛИТИК позволила получить эффективную реализацию работы с вещественными числами произвольной разрядности, целыми числами неограниченной разрядности, точных операций над дробными рациональными числами и др. Система АНАЛИТИК была одной из первых систем компьютерной алгебры, а в языке АНАЛИТИК впервые была широко использована техника переписывания алгебраических выражений (применение соотношений), которая в настоящее время является основой технологии декларативнеого программирования. В машинах серии МИР можно было проводить аналитические преобразования, в том числе дифференцирование и интегрирование формул.Архитектура ЭВМ серии МИР была не традиционной для того времени. Поиски новых архитектурных решений продолжались на программных прототипах многих прикладных систем и программных комплексов разработок института того времени. Среди этих систем — средства вычислений, эффективной организации моделирования СЛЭНГ и НЕДИС, Пакеты прикладных программ для научно-технических и экономических расчетов [8].

Архитектура ЭВМ

В.М. Глушков внес значительный вклад в развитие новых концепций ненеймановских компьютеров. В его работах неоднократно встречается обсуждение идеи ЭВМ с мозгоподобной структурой.

В 1974 году на Конгресс ИФИП в Стокгольме он, совместно с группой ученых из Москвы и Ленинграда выступает с идеей рекурсивной ЭВМ [8]. Помимо конкретных предложений по структуре РВМ в докладе содержится глубокая критика принципов неймановской архитектуры, обосновывается необходимость отказа от этих принципов и предлагаются новые принципы организации работы ЭВМ. В.М. Глушкова в первую очередь интересует проблема неограниченного наращивания производительности и ресурсов ЭВМ.

Идея рекурсивной ЭВМ явно была навеяна идеями сложных алгебраических (математических) конструкций и математической техникой умозрительного манипулирования ими. Здесь — организация рекурсивных вычислений, снятие ограниченний на физические параметры ресурсов (память, процессоры, коммуникационное поле), максимальное приближение внутреннего языка машины к языку формулировки задач, использование разнообразных универсальных алгоритмов вычислений, отличающихся друг от друга способами представления данных и механизмами вычислений. Поскольку в полной мере иди РВМ не могли быть реализованы в то время в силу технологических ограничений, было найдено компромиссное решение в идее макроконвейера (1978 год). Суть идеи макроконвейерной организации вычислений состоит в специальном представлении выполняемой распределенно программы, состоящей в том, чтобы соблюдался некоторый баланс между величинами обменных и вычислительных операций для участвующих в выполнении программы процессоров. В.М. Глушков организовал коллектив разработчиков, специалистов по компьютерной технике, общесистемному математическому обеспечению и методам решения прикладных задач. К началу 80-х годов проект принципиально новой макроконвейерной ЭВМ, включавшей в архитектуру серии разнородных процессоров , коммуникационное поле, общесистемную (операционная система и система программирования) и прикладную компонентность, был разработан, установлены связи с промышленностью. После 1982 г. работы по макроконвейеру продолжались. Ученики и последователи В.М. Глушкова под руководством В.С. Михалевича довели проект до промышленной реализации (ЕС 2701 и ЕС 1766) и решили на макроконвейере ряд сложных научно-технических задач. Эти многопроцессорные супер ЭВМ показали высокую эффективность макроконвейерной организации вычислений. Решались задачи расчета конструкции самолета, распространения тепловой волны при ядерном взрыве, моделирования климата мирового океана. Достигался линейный рост производительности по мере увеличения количества процессоров, демонстрировалась живучесть системы по мере уменьшения количества процессоров. Реальная скорость вычислений на 48 рабочих процессорах составляла 0,5 млрд. оп/с. Следует заметить, что элементная база этих машин была III поколения. Заметим, что в процессе создания этих машин получили дальнейшее развитие средства моделирования и проектирования архитектуры, алгоритмов функционирования и структуры ЭВМ [9]. По своим идеям и структуре, архитектура макроконвейерной ЭВМ еще в середине 80-х опережала мировой уровень вычислительной техники и опередила реализованные позже многие идеи организации многопроцессорных ЭВМ с распределенной памятью. Однако работы по дальнейшему совершенствованию и выпуску макроконвейерных ЭВМ были остановлены в силу известных причин. Опыт технических разработок (МИР, Макроконвейер), осуществленных под руководством В.М. Глушкова, послужил источником создания общей математической теории проектирования вычислительных систем, которая продолжает развиваться и в настоящее время учениками и последователями В.М. Глушкова. Исследования в этой области ведутся Институтом кибернетики имени В.М. Глушкова при поддержке международных фондов (INTAS, CRDF) в соответствующих международных проектах.

Самоорганизующиеся системы и искусственный интеллект

Начало 60-х годов связано с формированием представлений о сущности кибернетической науки, поисками перспективных направлений ее развития, укреплением и расширением коллектива ученых-кибернетиков в Киеве, установлением связей с научными школами СССР, активной популяризаторской деятельностью, поисками путей решения важнейших народнохозяйственных задач с применением ЭВМ. Поскольку теория автоматов к этому времени была наиболее разработанным разделом теоретической кибернетики, естественно было искать другие области ее применения помимо задач проектирования дискретных устройств. Одной из таких областей стало моденлирование процессов самоорганизации и самосовершенствования. Этому посвящен ряд оригинальных работ. Эти работы нашли отражение в монографии “Введение в кибернетику” [10], которая переведена на многие языки, и по настоящее время остается одним из лучших введений в предмет кибернетической науки. Задачу исследования самоорганизующихся и самосовершенствующихся систем В.М. Глушков считал одной из наиболее важных и интересных задач кибернетики, поскольку на пути решения этой задачи возможна разгадка многих тайн процесса мышления.

В.М. Глушков поставил своей целью дать описание теории самоорганизующихся систем как некоторой математической теории.

Это ему удалось в монографиях “Введение в теорию самосовершенствующихся систем” (1961 г.) [11]. Его предложения по “мере самоорганизации”, “мере обучения” и “мере целесообразного поведения” остаются примером точных рассуждений относительно этих интуитивных понятий до сих пор.

Вопросам искусственного интеллекта, образом которого В.М. Глушков считал ЭВМ, он занимался практически все время, о чем свидетельствует и его последняя монография “Основы безбумажной информатики” [12].

Под руководством В.М. Глушкова в 60-х — 70-х годах в Институте кибернетики АН УССР широким фронтом велись работы по созданию систем искусственного интеллекта. Здесь и работы по распознаванию образов (зрительных, речевых, языковых и т.п.), исследования в области робототехники, математической лингвистики, информационных систем м многое другое. Однако самой близкой для него проблемой, которой он много занимался непосредственно сам на протяжении всей своей кибернетической деятельности, была проблема автоматизации поиска доказательств теорем. Еще в 1958 г., изучая в качестве оппонента докторскую диссертацию А.И. Ширшова, В.М. Глушков сделал попытку проверить найденные А.И. Ширшовым тождества в кольцах и алгебрах Ли с помощью программы на машине “Урал”. Он внимательно следил за работами по созданию алгоритмов вывода теорем в СССР и за рубежом, инициировал проведение соответствующих исследований в Институте кибернетики. Под его руководством в начале 60-х годов были проведены эксперименты по машинной реализации алгоритма Тарского и некоторых других алгоритмов поиска вывода в разрешимых теориях. С проблемой доказательств связывались работы по аналитическим выкладкам и их реализации в машинах серии МИР. К концу 60-х годов сформировалась новая точка зрения на проблему поиска доказательств. Суть ее сводится к следующему. Прежде всего, необходимо разработать практический формальный язык для записи математических предложений и их доказательств. Этот язык должен быть близким к естественному языку математики и фактически представлять собой формализацию той части естественного языка, на котором пишутся книги по математике. Реализацией языка математики является “алгоритм очевидности”, который проверяет правильность математических утверждений, написанных в языке, если доказательства достаточно подробны, или находит в них пробелы, требующие расшифровки. На базе этих средств строится “интеллектуальная” информационная система, которая позволяет накапливать знания и пользоваться ими в процессе выполнения математических исследорваний. Открытие новых математических фактов и поиск доказательств сложных теорем, должны выполняться в диалоговом режиме с математиком. При этом используются программируемые специализированные дедуктивные средства, которые создаются динамически на базе языка, алгоритмов очевидности и информационной системы.

Значительная часть этих идей была реализована в системе САД (конец 70-х годов). В настоящее время исследования продолжаются в рамках международного проекта “Техника переписывания и эффективное доказательство теорем”.

Виктор Михайлович Глушков — основатель института кибернетики в Украине. В 1956 г. В.М.Глушков возглавил лабораторию вычислительной математики и техники Института математики АН УССР, в которой насчитывалось 28 человек. На базе этой лаборатории в 1957 году организовался Вычислительный центр АН УССР с правом научно-исследовательского института, который просуществовал до 1962 г. В 1962 г. в нем было уже более 200 сотрудников и он был переименован в Институт кибернетики АН УССР. В 1982 г. в нем насчитывалось более 6 тыс. человек. При нем Специальное конструкторское бюро математических машин и Специальное конструкторско-технологическое бюро программного обеспечения.

В период с 1957 по 1982 гг. институт превратился в ведущий центр кибернетических исследований не только в Украине, но и в СССР, работы которого хорошо были известны мировой общественности. Организационная деятельность В.М. Глушкова весьма многогранна и плодотворна.

Литература

1. В.М.Глушков. Абстрактная теория автоматов// Успехи мат.наук,1961.-16, № 5.-С.3-62.
2. В.М.Глушков. Синтез цифровых автоматов. — М.-: Физматгиз, 1962. — 476 с.
3. В.М.Глушков, А.А. Летичевский. Теория дискретных преобразований// Изд-во ВЦ СО АН СССР. В кн.: Избранные труды по общей алгебре, посвященные памяти А.И. Мальцева. Новосибирск, 1970.
4. В.М.Глушков. Теория автоматов и формальные преобразования микропрограмм// Кибернетика, 1965.-№ 5.- С. 1-10.
5. В.М.Глушков, Г.Е. Цейтлин, Е.Л. Ющенко. Алгебра, Языки, Программирование.-Киев: Наук.думка, 1974.- 328 с. 
6. В.М.Глушков, Ю.В. Капитонова, А.А. Летичевский. Автоматизация проектирования вычислительных машин. -К.: Наук. думка, 1975.-232 с.
7. В.М.Глушков, З.Л. Рабинович и др.  Вычислительные машины с развитыми системами интерпретации. -Киев: Наук.думка, 1970.- 259 с.
8. И.В.Сергиенко. Об основных направлениях развития информатики// Кибернетика и системный анализ.- 1997.- № 6 .- С. 3-93.
9. В.М.Глушков, М.В. Игнатьев, В.А. Мясников, В.А. Торгашев. Рекурсивные машины и вычислительная техника, 1974.- Киев.-26 с.- (Препр./ ИК АН УССР).
10. Системное математическое обеспечение многопроцессорного вычислительного комплекса ЕС. В двух томах. (Под ред. Ю.В. Капитоновой).-Изд-во ВВИА имени проф. Н.Е. Жуковского.-Москва, 1986.
11. В.М.Глушков. Введение в кибернетику. - Киев.: Изд-во АН УССР, 1964. — 324 с.
12. В.М.Глушков. Введение в теорию самосовершенствующихся систем. -Киев: Изд-во КВИРТУ, 1962. — 109 с.
13. В.М.Глушков. Основы безбумажной информатики // М.: Наука. Главная редакция физико-математической литературы, 1982.- 552 с.