English    Русский


Ілюстрації. Література. Додаткові матеріали Перелік друкованих робіт академіка АН СРСР В.М.Глушкова.Російською мовою Комп'ютери. Перефірійні прилади. Мережі. Використання комп'ютерів в системах Віктор Михайлович Глушков. Життя та творчість. Зміст В.М.Глушков - основоположник інформаційних технологій в Україні та колишньому СРСР

В.М.Глушков - піонер математичної теорії обчислювальних систем та засновник Інституту кібернетики HАH України

Сергієнко І.В., Капітонова Ю.В.
м.Київ, Україна
Доповідь на Міжнародній конференції
"Комп'ютери в Європі. Минуле, сучасне, майбутнє."
Київ, жовтень, 1998 р.

Вступ

У 1956-1982 рр. в Українській Академії наук працював Віктор Михайлович Глушков, після захисту в Московському Державному університеті докторської дисертації по дослідженню і розв'язанню узагальненої п'ятої проблеми Гільберта, що склало йому славу одного з провідних алгебраїстів світу. Крім математичної освіти В.М.Глушков мав технічну, оскільки прослухав повний курс на факультеті теплофізики Новочеркаського політехнічного інституту. Очоливши лабораторію обчислювальної математики і техніки Інституту математики АН УРСР, вiдому своїми роботами по першим у СРСР обчислювальним машинам ("МЭСМ", "СЭСМ", "Киев"), В.М.Глушков зумiв сформулювати програму наукових дослiджень, в основi якої лежала фундаментальна iдея iнтеграцiї кiбернетики, математики й обчислювальної технiки. В.М.Глушков одним з перших узявся за побудову математичної теорiї обчислювальних систем. При цьому малися на увазi, принаймнi, двi мети. Перша - винахiд математичних конструкцiй, що адекватно вiдображає властивостi компонентiв електронних обчислювальних машин (ЕОМ) i ЕОМ у цiлому, якi можна було б використовувати як моделi вiдповiдних компонентiв, i друга - створення математичної технiки їхнiх трансформацiй з метою вiдображення процесiв рiшення задач проектування цих компонентiв з тим ступенем деталiзацiї, що доступна вiдповiднiй технологiї виготовлення ЕОМ. На цьому шляху йому удалося досягти чудових результатiв у загальнiй теорiї цифрових автоматiв, теорiї дискретних перетворювачiв, алгебрi алгоритмiв, теорiї структур даних i рiвнобiжних обчислень. Вiн одним з перших розпочав розробляти iдею iнтелектуалiзацiї ЕОМ i запропонував ряд нетрадиційних архітектурних рішень для ненейманівських ЕОМ.

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

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

На базі цих методів була реалізована "Мала система синтезу цифрових автоматів" (на ЕОМ "Киев"), перший прототип майбутніх систем автоматизації проектування ЕОМ.

Дискретні перетворювачі

Теоретико-автоматні методи стали застосовуватися при проектуванні окремих блоків обчислювальних машин. Однак вони мали істотний недолік, зв'язаний з обмеженням на число станів використовуваних автоматів в якості моделі. Тому наступним кроком у розвитку теорії проектування стала формалізація рішення задачі блокового й алгоритмічного проектування пристроїв. Це було зроблено В.М.Глушковим у серії основних робіт середини 1960-х років, що відкрили новий етап розвитку математичної теорії дискретних систем. У цих роботах В.М.Глушкова була запропонована нова концепція нескінченного автомата, придатна для уточнення ряду практичних задач синтезу й оптимізації логічних структур ЕОМ і застосування в процесі їхнього рішення формально-алгебраїчних методів. У новій моделі процесор ЕОМ представляється у вигляді композиції двох автоматів - керуючого й операційного. Керуючий автомат, так само як і керуюча голівка машини Тьюринга, має кінцеве число станів, у той час як безліч станів операційного автомата, взагалі кажучи, нескінченно і складається з усіляких заповнень декількох кінцевих чи нескінченних в одну чи обидві сторони регістрів, аналогічних стрічкам машини Тьюринга. Однак на відміну від машин Тьюринга перетворення, виконувані на регістрах, можуть бути нелокальними і змінювати відразу всі розряди регістра. Конструктивність відповідних перетворень забезпечується тим, що вони задаються за допомогою рекурсивних визначень спеціального виду. Ця спеціалізація відповідає тому, що реально на довгих регістрах схеми для одного розряду чи групи розрядів періодично повторюються. Такі перетворення були названі періодичо-визначеними. Композиція керуючого й операційного автоматів, розглянута в цих роботах, являє собою окремий випадок загального поняття дискретного перетворювача, що досліджувалося надалі в роботах В.М.Глушкова і його учнів [3]. Ці дослідження розвивалися в двох напрямках. Перший напрямок - дослідження абстрактно-алгебраїчних задач, таких, як розпізнавання еквівалентності, оптимізації за часом роботи дискретних перетворювачів, вивчення співвідношень, систем утворюючих у напівгрупах перетворень операційного автомата та ін.

Другий напрямок пов'язаний з розробкою прикладних систем автоматизації проектування ЕОМ, мов для опису алгоритмів функціонування пристроїв, методів і алгоритмів проектування пристроїв і їхніх композицій. Істотний вплив на розвиток теорії дискретних перетворювачів зробили задачі спільного проектування схемного і програмного устаткування ЕОМ, удосконалення технології проектування, задачі проектування багатопроцесорних систем. Ідея періодично-визначеного перетворення, використана при побудові першої автономної моделі ЕОМ, виявилася після відповідного очевидного узагальнення на випадок багатомірних регістрів надзвичайно корисною для дослідження питань паралельної реалізації функцій над структурами даних. Використання моделі дискретного перетворювача значно розширилося, коли було усвідомлено, що вона годиться для представлення багатьох пар компонент ЕОМ. Наприклад, програма й ЕОМ, процесор і пам'ять, мікропрограмні пристрої та ін.

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

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

На конкретних прикладах мікропрограмних алгебр, породжених арифметичними мікроопераціями й умовами на одномірних регістрах була продемонстрована фундаментальна ідея проектування алгоритмів: для того щоб одержати необхідне уявлення алгоритму, його варто представити в придатній алгебрі і, вивчивши співвідношення цієї алгебри, перетворити це уявлення, домагаючись поліпшення тих чи інших його характеристик - часу, пам'яті і т.п. Була доведена також фундаментальна теорема про регуляризації довільних мікропрограм: перетворення, виконуване будь-якою мікропрограмою, може бути представлено виразом у мікропрограмній алгебрі, породженої тими ж елементарними операторами й умовами, що використовуються в даній мікропрограмі. Оскільки конструкції мікропрограмної алгебри носять загальний характер, а проектування пристроїв ЕОМ являє собою лише одну з багатьох областей її застосування, згодом цю алгебру стали називати алгеброю алгоритмів чи системою алгоритмічних алгебр. Ідея використання багатоосновних алгебр для представлення різних аспектів взаємодії компонент ЕОМ є актуальною і до цього часу, коли на перший план висуваються проблеми керування процесами в глобальних мережах (Іnternet та ін.).

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

Значний внесок у розвиток алгебри алгоритмів був внесений К.Л.Ющенко і Г.Є.Цейтліним. Їхня монографія "Алгебра, языки, программирование", написана разом з В.М.Глушковим, переведена на багато мов і багато років служить базовою монографією з теорії програмування.

Теорія структур даних і рівнобіжні обчислення

У середині 80-х років ХХ століття стало ясно, що особливу актуальність здобувають питання ефективності організації обчислень в ЕОМ.

З одного боку, мікромініатюризація елементної бази, а з іншого, явне виділення в комп'ютерах компоненти системного програмного забезпечення, що мала тенденцію до міграції в апаратуру. Крім того, моделі і методи проектування, що одержали реалізацію в різних засобах автоматизації проектування (наприклад, серія систем "ПРОЕКТ", "Чертеж", "КАПР" та ін.), у перспективі повинні були забезпечити проектування архітектури ЕОМ у цілому. У вигляді цього були досліджені й одержали розвиток теорія структур даних і методи блокового проектування ЕОМ. Монографія В.М.Глушкова в співавторстві з Капітоновою Ю.В. і Летичевським О.А. "Автоматизация проектирования вычислительных машин" стала своєрідним продовженням представлення моделей, методів і засобів побудови багатомашинних і багатопроцесорних ЕОМ з єдиною базою проектування компонентів схемного і програмного устаткування.

Використання понять абстрактного автомата, дискретного перетворювача, магазинного автомата, періодично-визначеного перетворення на нескінченному регістрі і побудова на базі цих понять теорії, що відбиває еволюційний процес створення засобів автоматизації ЕОМ, таїть у собі багато невикористаних можливостей для побудови теорій і методів проектування перспективних ЕОМ. Дуже плідною є ідея використання пари мікропрограмних алгебр і згодом алгебри алгоритмів для рішення проблем побудови програмного забезпечення ЕОМ. Зокрема, ідея побудови систем проектування програм на основі перетворення виразів у багатоосновних алгебрах не тільки не втратили своєї актуальності, але, можна вважати, є перспективною основою на найближче десятиліття.

Внутрішній інтелект ЕОМ

Коли з'явилася мова АЛГОЛ-60, В.М.Глушков став одним з перших її пропагандистів і прихильником широкого впровадження в практику програмування. У той же час він ясно усвідомлював прірву, що лежить між структурою неймановської ЕОМ і мовами високого рівня. Наявність цієї проблеми приводило до складних процедур трансляції і втрати ефективності програм у порівнянні з програмуванням у машинно-орієнтованих мовах. Тоді була сформульована ідея підвищення рівня внутрішньої мови ЕОМ, що можна розглядати як розвиток внутрішнього, тобто закладеного в апаратуру, інтелекту ЕОМ. Ця ідея не тільки вимагала перегляду безлічі машинних команд ЕОМ, але істотно змінювала технологію обробки програми в машині. Однією з можливих доповнень до цієї обробки була багаторівнева інтерпретація, а точніше, багаторівнева система трансляції з інтерпретацією. Крім теоретичного обгрунтування цієї ідеї був здійснений ряд розробок ЕОМ під керівництвом В.М.Глушкова.

Спочатку була "ПРОМІНЬ" - машина з елементами інтерпретації мови високого рівня. Потім проект машини "Україна", де планувалося як внутрішню мову використовувати АЛГОЛ. Проект цей не був реалізований.

Найбільш повно апаратну реалізацію мов високого рівня удалося здійснити в малих ЕОМ серії "МИР" ("МИР-1", "МИР-2", "МИР-3"). Структурна інтерпретація мов високого рівня "МИР" і "АНАЛИТИК" дозволила одержати ефективну реалізацію роботи з дійсними числами довільної розрядності, цілими числами необмеженої розрядності, точних операцій над дробовими раціональними числами й ін. Система "АНАЛИТИК" була однією з перших систем комп'ютерної алгебри, а в мові "АНАЛИТИК" уперше була широко використана техніка переписування алгебраїчних виразів (застосування співвідношень), що у даний час є основою технології декларативного програмування.

У машинах серії "МИР" можна було проводити аналітичні перетворення, у тому числі диференціювання й інтегрування формул.

Архітектура ЕОМ серії "МИР" була не традиційною для того часу. Пошуки нових архітектурних рішень продовжувалися на програмних прототипах багатьох прикладних систем і програмних комплексів розробок інституту того часу. Серед цих систем - засоби обчислень, ефективної організації моделювання "СЛЭНГ" і "НЕДИС", Пакети прикладних програм для науково-технічних і економічних розрахунків.

Архітектура ЕОМ

В.М.Глушков вніс значний вклад у розвиток нових концепцій ненейманівських комп'ютерів. У його роботах неодноразово зустрічається обговорення ідеї ЕОМ з мозкоподібною структурою. У 1974 році на Конгрес ІФІП у Стокгольмі він, разом із групою вчених з Москви і Ленінграда виступає з ідеєю рекурсивної ЕОМ. Крім конкретних пропозицій за структурою рекурсивної обчислювальної машини - РОМ - у доповіді міститься глибока критика принципів нейманівської архітектури, обгрунтовується необхідність відмовлення від цих принципів і пропонуються нові принципи організації роботи ЕОМ. В.М.Глушкова в першу чергу цікавить проблема необмеженого нарощування продуктивності і ресурсів ЕОМ.

Ідея рекурсивної ЕОМ явно була навіяна ідеями складних алгебраїчних (математичних) конструкцій і математичною технікою умоглядного маніпулювання ними. Тут - організація рекурсивних обчислень, зняття обмежень на фізичні параметри ресурсів (пам'ять, процесори, комунікаційне поле), максимальне наближення внутрішньої мови машини до мови формулювання задач, використання різноманітних універсальних алгоритмів обчислень, що відрізняються одне від одного способами представлення даних і механізмами обчислень. Оскільки повною мірою ідеї рекурсивної обчислювальної машини не могли бути реалізовані в той час у силу технологічних обмежень, було знайдено компромісне рішення в ідеї макроконвеєра (1978 рік). Суть ідеї макроконвеєрної організації обчислень складається в спеціальному представленні виконуваної розподіленої програми, що полягає в тому, щоб дотримувався деякий баланс між величинами обмінних і обчислювальних операцій для процесорів, що беруть участь у виконанні програми. В.М.Глушков організував колектив розроблювачів, фахівців з комп'ютерної техніки, загальносистемному математичному забезпеченню і методам рішення прикладних задач. До початку 80-х років проект принципово нової макроконвеєрної ЕОМ, що включав в архітектуру серії різнорідних процесорів, комунікаційне поле, загальносистемну (операційна система і система програмування) і прикладну компонентність, був розроблений, установлені зв'язки з промисловістю. Після 1982 р. роботи з макроконвеєра продовжувалися. Учні і послідовники В.М.Глушкова під керівництвом В.С.Михалевича довели проект до промислової реалізації ("ЄС 2701" і "ЄС 1766") і вирішили на макроконвеєрі ряд складних науково-технічних задач. Ці багатопроцесорні супер-ЕОМ показали високу ефективність макроконвеєрної організації обчислень. Вирішувались задачі розрахунку конструкції літака, поширення теплової хвилі при ядерному вибуху, моделювання клімату світового океану. Досягався лінійний ріст продуктивності в міру збільшення кількості процесорів, демонструвалася живучість системи в міру зменшення кількості процесорів. Реальна швидкість обчислень на 48 робочих процесорах складала 0,5 млрд. оп/с. Варто помітити, що елементна база цих машин була ІІІ покоління. Помітимо, що в процесі створення цих машин одержали подальший розвиток засоби моделювання і проектування архітектури, алгоритмів функціонування і структури ЕОМ. За своїми ідеями і структурі, архітектура макроконвеєрної ЕОМ ще в середині 80-х випереджала світовий рівень обчислювальної техніки і випередила реалізовані пізніше багато ідей організації багатопроцесорних ЕОМ з розподіленою пам'яттю. Однак роботи з подальшого удосконалення і випуску макроконвеєрних ЕОМ були зупинені в силу відомих причин. Досвід технічних розробок, здійснених під керівництвом В.М.Глушкова, послужив джерелом створення загальної математичної теорії проектування обчислювальних систем, що продовжує розвиватися і в даний час учнями і послідовниками В.М.Глушкова. Дослідження в цій області ведуться Інститутом кібернетики імені В.М.Глушкова за підтримкою міжнародних фондів (ІNTAS, CRDF) у відповідних міжнародних проектах.

Системи, що самоорганізовуються, і штучний інтелект

Початок 1960-х років пов'язаний з формуванням уявлень про сутність кібернетичної науки, пошуками перспективних напрямків її розвитку, зміцненням і розширенням колективу вчених-кібернетиків у Києві, встановленням зв'язків з науковими школами СРСР, активною популяризаторською діяльністю, пошуками шляхів рішення найважливіших народногосподарських задач із застосуванням ЕОМ. Оскільки теорія автоматів до цього часу була найбільш розробленим розділом теоретичної кібернетики, природно було шукати інші області її застосування крім задач проектування дискретних пристроїв. Однією з таких областей стало моделювання процесів самоорганізації і самовдосконалення. Цьому присвячений ряд оригінальних робіт. Ці роботи знайшли відображення в монографії "Введение в кибернетику", що переведена на багато мов, і до сьогодення залишається одним із кращих введень у предмет кібернетичної науки. Задачу дослідження систем що самоорганізуються і самоудосконалюються В.М.Глушков вважав однією з найбільш важливих і цікавих задач кібернетики, оскільки на шляху рішення цієї задачі можлива розгадка багатьох таємниць процесу мислення.

В.М.Глушков поставив своєю ціллю дати опис теорії систем, що самоорганізуються, як деякої математичної теорії. Це йому удалося в монографіях "Введение в теорию самосовершенствующихся систем" (1961 р.). Його пропозиції по "критерію самоорганізації", "критерію навчання" і "критерію доцільного поводження" залишаються прикладом точних міркувань щодо цих інтуїтивних понять до цього часу.

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

Під керівництвом В.М.Глушкова в 1960-х - 1970-х роках в Інституті кібернетики АН УРСР широким фронтом велися роботи зі створення систем штучного інтелекту. Тут і роботи з розпізнавання образів (зорових, мовлення, мовних і т.п.), дослідження в області робототехніки, математичної лінгвістики, інформаційних систем та багато чого іншого. Однак найближчою для нього проблемою, якою він багато займався безпосередньо сам протягом усієї своєї кібернетичної діяльності, була проблема автоматизації пошуку доказів теорем. Ще в 1958 р., вивчаючи як опонент докторську дисертацію А.І.Ширшова, В.М.Глушков зробив спробу перевірити знайдені А.І.Ширшовим тотожності в кільцях і алгебрах Лі за допомогою програми на машині "Урал". Він уважно стежив за роботами по створенню алгоритмів виведення теорем у СРСР і за рубежем, ініціював проведення відповідних досліджень в Інституті кібернетики. Під його керівництвом на початку 1960-х років були проведені експерименти по машинній реалізації алгоритму Тарского і деяких інших алгоритмів пошуку виводу в розв'язних теоріях. З проблемою доказів зв'язувалися роботи з аналітичним викладенням і їхній реалізації в машинах серії "МИР". До кінця 1960-х років сформувалася нова точка зору на проблему пошуку доказів. Суть її зводиться до наступного. Насамперед, необхідно розробити практичну формальну мову для запису математичних пропозицій і їхніх доказів. Ця мова повинна бути близькою до природної мови математики і фактично являти собою формалізацію тієї частини природної мови, на якій пишуться книги з математики. Реалізацією мови математики є "алгоритм очевидності", що перевіряє правильність математичних тверджень, написаних у мові, якщо докази досить докладні, чи знаходять у них пробіли, що вимагають розшифровки. На базі цих засобів будується "інтелектуальна" інформаційна система, що дозволяє накопичувати знання і користуватися ними в процесі виконання математичних досліджень. Відкриття нових математичних фактів і пошук доказів складних теорем, повинні виконуватися в діалоговому режимі з математиком. При цьому використовуються програмувальні спеціалізовані дедуктивні засоби, що створюються динамічно на базі мови, алгоритмів очевидності й інформаційної системи.

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