Теория вычислительных систем и программирование в СССР

4

В этом году наша страна разднует 60-летие Великой Октябрьской социалистической революции. Как сказал Генеральный секретарь ЦК КПСС Л. И. Брежнев, отвевая на вопросы главного редактора газеты «Асахи» С. Хата, «за прошедшие 60 лет советский народ под руководством Коммунистической партии прошел путь, который мы впервые гордиться. При жизни одного поколения было поконечно с вековой отсталостью. Наша страна вышла на высокий уровень экономического и научно-технического развития. Если на долю доверологии Российской прихождения лишь немного более 4 процентов мировой промышленной продукции, то сегодня Советский Союз производит пятую ее часть»).

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

«Основными направлениями развития народного хозяйства СССР на 1976—1980 годы» предусмотрено увеличение выпуска средств вычислительной техники в 1,8 раза, дальнейшее развитие производства универсальных и управляющих вычислительных комплексов, поставленные большее задачи по дальнейшему развитию применений ЭВМ в научных исследованиях, на производстве и в экономике.

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

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

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

Первый советский компьютер(МЭСМ) был создан в Академии наук УССР в Киеве под руководством академика С. А. Лебедева в 1951 году. При создании МЭСМ были независимо переоткрыты основные принципы, на которых были построены первые амерikanские и английские компьютеры, — так называемые приццы фон Неймана.

5

Во-первых, это нацице оперативной памяти, разбитой на одинаковые ячейки. Каждая ячейка предназначена для заполнения одного машинного слова, представляющего собой упорядоченный набор двойный цифр 0 и 1. Ячейки памяти снабжены адресами, в качестве которых выступают последовательные целые неотрицательные числа 0, 1, …, n — 1; число ячеек n — объем памяти.

Следующий принцип — нацице специального арифметического устрояства (АЛУ), предназначенного для выполнения простейших операций над словами, в частности, операции сравнения с целым установлениями совпадения или различия двух слов. Другой класс операций составляют арифметические операции (сложения, вычитания, умножения и деления) над словами, рассматриваемых как числа в двойной системе численения.

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

Операции управления вычислительными процессом связаны с третьим принципом фон Неймана — командо-adресьим прицном организации управления. Машинная команда состоит из условийкого кода операции, которое требуется выполнить, и адресов операндов (то есть слов, над которых выполняется операция, и результатата этой операции). Например, в операции сложения a + b = c имеются 3 операнда: a, b, c. Если один или несколько операндов хранятся в заранее определенных ячейках памяти или в специальных запоминающих ячейках — так называемых резистрах АЛУ, то адреса соответствующих операндов в команде могут опускаться. Нанболее существует момент третьего принципа фон Неймана является возможность запоминания в оперативной памяти не только операндов, но и программы вычислительной процесса, представляемой в виде конечной последовательности машинных команд, записанных двойными кодами.

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

Четвертый принцип состоит в неизменности структуры связи устройствами.

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

Рассмотрим задачу программырования для простейшей задачи нахождения факторала n! заданного натурального числа n. Для хранения операндов нам потребуется четые ячейки памяти, в качестве которых мы выберем ячейки с адресами 0, 1, 2, 3. Для управления опустим программму ввода исходных данных и предположим, что к моменту начала работы программы в нулевой ячейке хранится число n, а в первой, второй и третьей ячейках — единицы. Тогда программа вычисления факторала представится следующей программиной (числа следующего сообщения команда); через(i) обозначено содержимое ячейки с адресомi):

4. Сравнить(2) с(0) и, если «равно», то на 8, иначе на следующую команду.
5. Прибавить(3) к(2), результат заслать в 2.
6. Умножить(2) на(1), результат заслать в 1.
7. Перейти к 4.
8. Останов.

Первая команда программы (с адресом 4) представляет собой так называемую команду условия перехода, а четвертая (с адресом 7) — команду безусловного перехода. Заметим, что

6

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

сравнение 001
сложение 010
умножение 011
переход 100
останов 101,

а адреса ячеек от 0 до 8 соответствующими четырехначными двойными кодами, запишем программу в закодированном виде (символом ~ обозначены неиспользовные адреса):

001 0010 0000 1000
010 0011 0010 0010
011 0010 0001 0001
100 0100 ~ ~
101 ~ ~ ~

Заметим, что программа будет работать правильно только тогда, когда она помещена в заданные выше ячейки (от 4-й по 8-ю).

Легко понять, что описанный способ программырования (в машинных кодах) чрезвычайно громоздок и утомительен, в силу чего даже опытные программы в сколько-нибудь сложных программах делают немало ошибок. Ошибки исправляются в процессе отладки программы — последовательной (команда за командой) программы для управления наборов данных (в данном случае, скажем, при n = 2 или n = 3), и контrole работы машины.

Сложность задачи программы управленияусугубляется начиным в компьютерах запоминающих устройств (3У) различных типов: быстрых 3У относимельно малое обмена (внутренних) и более медленных 3У большого обмена (внешних).

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

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

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

Новый шаг вперед на пути управления программырования был сделан в результате создания процесурно-ориентированных универсальных языков программы и соответствующих трансляторов. Подобные языки не привязываются к особенностям выполнения программы в конкретных машинах, широко использоват формулы языка алгебры. Первым отмеченным процессурно-ориентированным языком был так называемый адресный язык, разработанный в 1955—1956 годах В. С. Королюком и Е. Л. Юшенко. Важную роль в развитии теории программырования сыгraf операторный язык, предложенный А. А. Ляпуньым в 1954 году. Программа в этом языке представляется в виде конечной последовательности операторов $P_i$ и логических условий $\alpha_j$, принадлежащих заданным множеством операторов и условий. Переходы, возникшие в результате проверки логических условий, обозначаются стрелками или специальными символами. В записанной выше про-

7

грамме вычисления $n!$ участуют операторы сложения $P_1$, умножения $P_2$, останова $P_3$ и логическое условие $\alpha$ — условие равенства содержимого нулевой и второй ячеек. Программа в операторном языке запишется в следующем виде:

$$S = \prod_{i=1}^{n} P_1 P_2 \prod_{j=1}^{n} P_3.$$

Наличие относительной простой формы записи программы поставило вопрос о формальных преобразованиях программы. Разработкой теории таких преобразований много и успешно заималисы Ю. И. Янов, А. П. Ершов и другие советские математики.

Важным шагом в теории вычислительных систем было становление на начале 50-х годов понятия конечного автоматма. Это устройство, которое может находиться лишь в одном из состояний $a_i$, образующих конечное множество, может переходить из одного состояния в другое под действием приходящих в определенные моменты времени $t = 1, 2, \dots$ входных сигналов $x_j$, образующих конечное множество, и может выдавать выходные сигналы $y_k$, являющиеся функциями пары $(a, x)$ состояния и входного сигнала.

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

В 60-е годы шло дальнейшее развитие вычислительных систем и программирования. Высказанная автором еще в 1958 году идея о повышении уровня машинного языка нашла свое положение в миникомпьютере «МИР-1» (1965 г.), а затем в еще более продвинутой форме в машине «МИР-2» (1969 г.). В машине «МИР-2» внутренний язык особенно богат. Он позволяет операровать не только с целыми числами и десятичными дробями, но и с объIkновенными дробями, а также с формулами, использующими

8

элементарные функции (логарифм, снус и др.) и операции дифференцирования и интеррирования.

Благодаря богатству внутреннего языка процесс трансляции программы со входного языка на машинный практический исход. Специальное многоугольное устройство управления обеспечивает быстро интерпретацию сложных операторов (например, операторов аналитического дифференцирования и интеррирования), благодаря этому «МИР-2» при выполнении формальных преобразований успешно составляется в скорости работы с гораддо более мощными компьютерами, построенными по традиционной неймановской схеме.

Повышение уровня машинного языка означает фактически открытого второго принципиала фон Неймана. После машин серии «МИР» по этому пути пошла американская фирма «Барроуз», а в 70-е годы это направление стало общеприятной линейной развитией вычислительных систем. Другое направление, получившее широкое развитие в 60-е годы, — создание специальных систем программ (так называемых операционных систем) для управления вычислительных процессом и управления программирования в части, касающейся использования сложных неархитических систем памяти.

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

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

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

Системы автоматизации программы и машины в этот период включают много входных языков, так что отдельные блоки одной и той же программы стало возможным записьвать на разных языках. Увеличивающийся международный объем программы привел к необходимости создания международных универсальных процессурно-ориентированных языков. Особо большое распоряжение получил язык «Алгол-60». В современных системах автоматизации программы и машины ширино приемаются и другие языки («Фортран», «PL-1» и др.).

Программисты, разработавшиешие операционные системы и системы автоматизации программирования, называются общно системными программами, в отличие от программтов, разработавших при-

9

кладные программы в той или иной конкретиной предметной области. Если во втором случае главное требование — хорошее значение программы соответствующего предметной области, то в первом случае от программы требуется хорошее владение всем секретами программыского мастерства и понимание архитектуры современных вычислительных систем.

В 60-e годы в СССР сложились сильные школьные системных программ в Москве, Новосибирске, Киеве и в ряде других городов.

Хотя в принципе многое задачи оптимизации операционных систем могут быть облачены в точные математические формулировки, современная математика, как правило, не может еще их решать. Поэтому при оптимизации операционных систем и структуры вычислительных систем широко использовются методы машинного моделирования. Разработаны специальные языки, ориентированные на такое моделирование, например, язык «СЛЭНГ» (1968 г.).《Недис》 (1974 г.) и др.

Важным направлением программрования со второй половины 60-х годов стало создание пакетов приложных программ в различных областях применения. Пакет — это не просто механическое объединение различных программ, но и набор специальных сервисных программ, облачащих их использование, то есть небольшая специализированная операционная система с проблемно ориентированным входным языком. Пакет для формальных вычислений позволяет в машину форматы в привящном для человека виде, например: $x = \sqrt{5,26 + 7,32 \cdot 8,04}$, $y = \sin(\pi/16)$ и т.п.

В теории вычислительных систем автору в 1966 году удалось найти новый подход, позволивший записывать программы в виде формат в некоторых специальной алгебры алгоритмов. В отличие от обычной школьной алгебры, в которой значения переменных принадлежат области всех вещественных чисел, в алгебре алгоритмов имеется две разные предметные области. Однако переменные латинскими буквами) интерпретируют как операторы, отображающие некоторое заданное множество $M$ в себя. Другие переменные (обозначемые греческие буквами) интерпретируют как логические условия, принимающие на множество $M$ два значения: 0 и 1.

Как операторы, так и условия могут быть определены не на всем множестве $M$, а на некоторой его части. Алгебра условий (булева алгебра) и алгебра операторов (полугрупла) изучалась уже давно. Суть идеи автора состоит введение смецанных операций, в которых участвуют как условия, так и операторы. Это следующее операция:

$$\alpha - \text{диизjonция} (P \vee Q),$$

$$\alpha - \text{итерация} \left\{ P \right\},$$

умножение условий на оператор $P \cdot \alpha$.

Не вдаваясь в подробное определение этих операторов, затем лишь что рассмотрена выше программы $S$ может быть записана в виде $\alpha$-итерации: $S = \left\{ P_1 P_2 \right\}$. Доказано, что любая программа, составлена из операторов $P_1, \dots, P_m$ и условия $\alpha_1, \dots, \alpha_n$ может быть записана в виде формальных алгебры алгоритмов с переменными $P_1, \dots, P_m$ и $\alpha_1, \dots, \alpha_n$.

В алгебре алгоритмов, как и в обычной школьной алгебре, существует эквивалентные преобразования формул, то есть преобразовывать программы, не меняя определения его сложного оператора (преобразования на множество данных). Использование подобного алгоритма позволяет в 1969—1973 году построить автоматизированную систему проектирования компьютеров вместе с любыми реализуемыми на них системами программы, повышающего производительность труда при проектовании в 20—30 раз.

В 70-e года теория программрования и вычислительных систем продолжает развивать всема быстрыми темпами. Особенно большое внимание в этот период уделялось технологии составления и методов проверки пра-