Кузин - Логические основы
.pdf
Глава I. Автоматическое исполнение команд обработки данных
Таблица I.24. Команда ввода: ВВОД 0, 0, A3
Микрокоманда |
|
Микрооперации |
|
Комментарий |
ОЖДКЛ |
|
|
Ожидание нажатия кла- |
|
|
|
|
виши |
|
Пам(А3) := Rввод |
|
ВДВВОД |
Выдача двоичного кода |
|
|
|
|
литеры на шину |
|
|
|
ВДА3 |
Выдача на шину адреса |
|
|
|
|
АЗ |
|
|
|
ЗП |
Инициация записи по |
|
|
|
|
адресу |
|
Таблица I.25. Команда вывода: ВЫВОД A1, 0, 0 |
||||
|
|
|
|
|
микрокоманда |
|
микрооперации |
|
комментарий |
ОЖДвывода |
|
|
|
ожидание ввода |
Rвывод := ПАМ(А1) |
|
ВДА1 |
|
выдача адреса вводи- |
|
|
|
|
мого кода |
|
|
ЧТ |
|
инициация чтения |
|
|
ПРВЫВОД |
|
прием кода на регистр |
|
|
|
|
вывода |
Аналогично представляются и выполняются все остальные команды обработки данных.
6.8.Контрольные вопросы
1.Каким образом алгоритмы преобразования символьных строк обеспечивают исполнение арифметических операций?
2.Команды обработки данных.
3.Исполнение команды сложения.
4.Арифметико-логическое устройство и его функционирование.
5.Сложение и вычитание целых чисел.
6.Арифметическое умножение и деление.
7.Логические команды.
8.Автоматическое исполнение команды обработки данных.
С. Г. Кузин. Логические основы автоматической обработки данных 69
Глава I. Автоматическое исполнение программы
7. Автоматическое исполнение программы
7.1. Понятие линейной программы
Фундаментальным понятием информатики является понятие алгоритма. Алгоритм решения прикладной задачи однозначно определяет способ преобразования исходных данных в результирующие данные. По сути дела, решение прикладной задачи и заключается в таком преобразовании данных.
При конструировании алгоритма предполагается, что существует исполнитель, способный выполнять конечное множество элементарных действий по преобразованию данных. Исполнителем может быть как человек, так и техническое устройство. Обозначение элементарного действия по преобразованию данных называется командой преобразования данных исполнителя. Спецификой алгоритма является представление сложного преобразования любого допустимого исходного набора данных d в результирующий набор данных r в виде последовательности элементарных действий – команд исполнителя. Такую последовательность σ(d)
будем называть траекторией вычислительного процесса решения при-
кладной задачи.
Описание траектории вычислительного процесса на формальном языке программирования и называется линейной программой. Очевидно, что линейная программа состоит только из команд обработки данных (арифметические, логические, ввод, вывод) и заканчивается специальной командой останова.
7.2. Принцип программного управления
Следует сказать, что понятие программы не является следствием изобретения компьютеров. Человечество программировало вычисления задолго до появления подобных вычислительных машин. Исполнителем таких программ являлся человек, оснащенный, в лучшем случае, средством автоматического исполнения арифметических операций (арифмометр, счеты, логарифмическая линейка).
Появившийся задолго до изобретения компьютеров арифмометр также способен автоматизировать только исполнение арифметических операций.
Настоящая революция в области автоматизации вычислений произошла после того, как американский ученый фон Нейман сформулировал свои принципы построения автоматической вычислительной машины. По сути дела, данное учебное пособие последовательно излагает эти принципы.
Итеперь пришла пора рассмотреть самый революционный из них
-принцип программного управления вычислительной машиной.
70 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Автоматическое исполнение программы
Принцип программного управления фон-Неймана формулиру-
ется в виде следующих пунктов.
1.Программа преобразования данных, представленная в двоичном виде, размещается в той же оперативной памяти, что и данные;
2.Электронная схема устройства управления реализует алгоритм главного цикла компьютера, который обеспечивает последовательную автоматическую выборку из оперативной памяти команд
программы и их исполнение.
Примечание. Строго говоря, практически одновременно были предложены два способа хранения программы. Компьютер Гарвардского университета «Марк-1» (1950 год) имел отдельную память для команд. Тогда как в Принстонском университете при участии фон Неймана (начиная с 1947-го года) создавались компьютеры с единой памятью для команд и для данных. Принстонская архитектура стала преобладающей.
Как поместить программу в оперативную память? Вспомним, что программа - последовательность команд. Каждая команда имеет формат:
КОП А1,А2,А3.
Здесь, КОП - код операции, А1, А2, А3 - адреса ячеек оперативной памяти (p- разрядные двоичные последовательности).
Каждый код операции также можно представить r- разрядной двоичной последовательностью. Таким образом, для представления команды используется r+3×p двоичных разрядов. Как правило, команда "не убирается" в один байт и размещается в ячейке размером в несколько байт. Адрес команды определяется как адрес первого байта хранящей эту команду ячейки. Длина команды - число занимаемых командой байт.
Таким образом, в оперативной памяти образуются три области:
1.Область хранения программы;
2.Область хранения данных;
3.Свободная область.
Команды линейной программы должны выполняются последовательно, начиная с первой команды. Необходимо физически реализовать отношение следования команд линейной программы. Т.е. необходимо решить проблему указания того, какая команда должна исполняться после выполнения текущей команды. Здесь возможны два способа такого указания.
Во - первых, можно добавить еще одно (четвертое) поле адреса Аслк, в котором указывается следующая исполняемая команда:
КОП А1,А2,А3,Аслк.
В этом случае мы имеем дело с четырехадресной командой, а линейная программа образует связный список (Рис. I.34). Образно говоря, программа становится похожей на нитку бус, разбросанных по памяти, где в качестве бусин выступают команды программы.
С. Г. Кузин. Логические основы автоматической обработки данных 71
Глава I. Автоматическое исполнение программы
КОП
КОП
КОП
КОП
Рис. I.34. Хранение команд в виде связного списка
Преимуществом такого способа хранения программы является возможность "разбрасывания" команд по памяти произвольным образом. А платой за такую произвольность является большой расход памяти, необходимой для хранения адресов следующих команд.
Если принять достаточно естественное условие, что следующая команда линейной программы хранится в следующей ячейке оперативной памяти, то можно обойтись трехадресной командой.
При этом достаточно иметь лишь один регистр - счетчик команд (СЧК) - на котором хранится адрес следующей исполняемой команды. Очевидно, что для перехода к следующей команде счетчик команд необходимо увеличить на длину команды в байтах (∆).
7.3. Автоматическое исполнение линейной программы
Вычислительная машина с трехадресной системой команд исполняет линейную программу (состоящую только из команд обработки данных), последовательно выбирая команды из памяти и передавая их на регистр команд для автоматического исполнения. Таким образом, после исполнения очередной команды начинает исполняться следующая команда.
Архитектура такой трехадресной, программно - управляемой вычислительной машины приведена в Приложении 2. На рисунке показано, что шина чтения подходит к регистру команд, а счетчик команд соединен с шиной адреса.
При исполнении команды обработки данных, устройство управления автоматическим выполнением команд (УУАВК) генерирует последовательность микроопераций, которые объединяются в микрокоманды.
Исполнение линейной программы обеспечивается Устройством Управления Автоматическим Выполнением Программы (УУАВП),
которое реализует алгоритм главного цикла вычислительной машины
(Таблица I.26).
72 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Автоматическое исполнение программы
Алгоритм главного цикла вычислительной машины реализуется посредством генерации повторяющейся последовательности микрокоманд. Как и прежде, микрокоманда реализуется в виде последовательности микроопераций.
Таблица I.26. Реализация алгоритма главного цикла компьютера
|
Микрокоманда |
Микроопе- |
Комментарий |
|
|
рация |
|
1 |
СЧК := адрес пер- |
ВДА2 |
Выдача адреса первой ко- |
|
вой команды. |
|
манды на шину адреса |
|
|
ПРСЧК |
Прием адреса первой ко- |
|
|
|
манды на счетчик команд |
2 |
РК := ПАМ(СЧК) |
ВДСЧК |
Выдача адреса следующей |
|
|
|
команды на шину адреса |
|
|
ЧТ |
Инициация чтения из опера- |
|
|
|
тивной памяти |
|
|
ПРРК |
Прием считанной из опера- |
|
|
|
тивной памяти команды на |
|
|
|
РК |
3 |
СЧК := СЧК+∆ |
+∆СЧК |
Подготовка к чтению сле- |
|
|
|
дующей команды |
4 |
ВДКОП |
ВДКОП |
Расшифровка кода операции |
5 |
ЕСЛИ КОП(РК) = |
останов |
Окончание исполнения про- |
|
"ОСТАНОВ" |
|
граммы |
6 |
запуск УУАВК |
запуск ко- |
Автоматическое исполнение |
|
|
манды |
команды |
7 |
повторение 2 |
пуск |
Повторение главного цикла |
Особого рассмотрения заслуживает вопрос присвоения перед началом исполнения счетчику команд адреса первой исполняемой команды программы. Мы предполагаем, что этот адрес заносится непосредственно на регистр команд (РК) с пульта - управления вычислительной машиной. И после этого нажимается кнопка "Пуск", вызывающая запуск УУАВП
7.4. Понятие программы и ее автоматическое исполнение
Выше мы рассмотрели представление вычислительного процесса решения прикладной задачи в виде единственной траектории, что привело нас к понятию линейной программы.
Однако, практически все преобразования данных отличаются следующим свойством: способ преобразования исходного набора данных зависит от конкретных значений данных этого набора.
С. Г. Кузин. Логические основы автоматической обработки данных 73
Глава I. Автоматическое исполнение программы
Рассмотрим пример определения корней квадратного уравнения: Ax2+Bx+C = 0. Известно, что, в зависимости от конкретных значений коэффициентов уравнения, его корни вычисляются по трем различным траекториям.
Таким образом, можно утверждать, что, в общем случае, для каждой прикладной задачи существует множество траекторий вычислительного процесса. И это множество сплошь и рядом бесконечное. Конечное
компактное описание множества траекторий вычислительного процесса мы называем моделью вычислительного процесса решения прикладной задачи.
Программа – одна из возможных моделей вычислительного процесса. Она представляет собой линейный текст (последовательность команд), записанный в соответствии с правилами формального языка программирования. Другой известной моделью вычислительного процесса является блок - схема.
Учитывая вышесказанное, становится очевидным, что линейных программ практически не бывает. И можно говорить лишь о линейных участках программ. Однако текст программы по-прежнему остается линейным. Для того чтобы в конечном компактном виде (в виде линейного текста программы) представить множество траекторий вычислительного процесса, в систему команд исполнителя должны быть включены команды, изменяющие порядок выполнения команд преобразования данных. Такие команды принято называть командами управления.
Примечание. Таким образом, последовательность записи команд в тексте программы не совпадает с последовательностью выполнения команд при вводе конкретных исходных данных – траекторией вычислительного процесса. Последовательность записи команд в тексте программы единственная – траекторий множество.
Множество команд (обработки данных и управления) образует
систему команд компьютера.
Как говорилось выше, в систему команд вычислительной машины входят команды управления. Прежде всего, это команда безусловной
передачи управления:
БПУ 0,А2,0.
Смысл этой команды состоит в том, что после ее исполнения начинает исполняться не следующая команда, а команда с адресом А2.
Устройство управления автоматическим выполнением команды для исполнения команды безусловного перехода генерирует последовательность из двух микроопераций:
ВДА2; ПРСЧК.
После этих действий продолжение главного цикла обеспечивает исполнение команды с адресом А2.
74 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Автоматическое исполнение программы
Команда условной передачи управления имеет формат:
УПУ 0,А2,0.
В качестве условия, которое определяет передачу управления на команду с адресом А2, используется отношение к нулю результата предыдущей операции. Результат предыдущей операции может быть равен нулю, не равен нулю, больше нуля, меньше нуля, больше или равен нулю, меньше или равен нулю. Для каждого такого отношения имеется своя команда условного перехода со специфическим кодом операции УПУ.
Если отношение выполняется, то команда условной передачи управления работает как команда безусловной передачи управления, т.е. происходит переход по адресу А2. В противном случае последовательность выполнения команд не нарушается и исполняется команда, следующая в тексте программы за командой условного перехода.
7.5. Система команд вычислительной машины
7.5.1.Классификация команд
Множество команд, каждую из которых может выполнить цен-
тральный процессор, образует систему команд вычислительной маши-
ны. В общем случае формат команды состоит из одного поля кода операции и n адресных полей, в каждом из которых записывается адрес оперативной памяти. Существенной характеристикой команды является ее адресность, т.е. число адресных полей.
Код операции addr1 |
… |
addrn |
Система команд существенным образом определяет тип (архитектуру) вычислительной машины. Однако, вне зависимости от конкретной архитектуры, команды вычислительной машины подразделяются на два класса: команды обработки данных и команды управления выполнением вычислительным процессом. К командам обработки данных относятся:
•команды преобразования данных (пересылка, арифметические и логические команды).
•команды сдвига кода;
•команды ввода данных в оперативную память;
•команды вывода данных из оперативной памяти;
Команды управления реализуют безусловную и условную передачу управления, а также обращение к подпрограммам и возврат из подпрограмм.
Команды обработки данных можно классифицировать по числу адресов; наиболее часто используются одноадресные и двухадресные команды. Команды управления, как правило, одноадресные.
С. Г. Кузин. Логические основы автоматической обработки данных 75
Глава I. Автоматическое исполнение программы
7.5.2.Команды обработки данных
Одноадресные команды пересылки реализуют обмен данными между оперативной памятью и регистром арифметического устройства. Причем последний задается по умолчанию.
Load addr – загрузка содержимого ячейки оперативной памяти в регистр.
Story addr – пересылка содержимого регистра в ячейку оперативной памяти.
Двухадресные команды пересылки осуществляют обмен данными между ячейками оперативной памяти и\или регистрами арифметического устройства.
MOV Аист, Апр – обмен данными между источником и приемни-
ком.
Арифметические и логические команды в современных компьютерах являются также двухадресными.
ADD Аист, Апр – выбирает значения из Аист и Апр, образует их сумму, которую записывает в Апр.
Команды ввода – вывода либо имеют специфический одноадресный формат, либо совпадают по формату с двухадресной командой пересылки MOV.
7.5.3.Команды управления
Одноадресная команда безусловной передачи управления JMP addr заносит адрес "скачка" на счетчик команд, что обеспечивает в качестве следующей команды с этим адресом. Одноадресная команда CALL addr – реализует вызов подпрограммы с запоминанием адреса возврата. Безадресная команда RET обеспечивает возврат из подпрограммы.
Команды условной передачи управления предназначены для проверки определенного условия и, в случае его выполнения, осуществляют передачу управления.
В качестве условий используются разряды регистра флагов автоматически устанавливаемые процессором в соответствии с результатом выполнения каждой команды.
7.6. Принципы функционирования вычислительной машины - компьютера
Мы рассмотрели фундаментальные основы построения вычислительных машин (компьютеров), сконструированных и функционирующих на основании принципов фон - Неймана. Эти принципы сформулировал в середине сороковых годов двадцатого века американский ученый фон - Нейман, который входил в группу создателей одной из первых автоматических цифровых вычислительных машин.
76 С.Г. Кузин. Логические основы автоматической обработки данных
Глава I. Автоматическое исполнение программы
Классическое построение автоматической цифровой вычислительной машины показано на Рис. I.35. Внешние устройства подразделяются на устройства ввода – вывода (монитор – дисплей, клавиатура и т.п.) и на внешние запоминающие устройства (магнитные диски, лазерные диски и т.д.)
Конструкция автоматической цифровой вычислительной машины, очевидная с современной точки зрения, содержит две фундаментальные идеи, которые сыграли выдающуюся роль в развитии вычислительной техники и которые не утратили своего значения и сейчас.
Оперативная память |
|
|
|
|
Устройство |
Устройство |
Арифметико – |
ввода |
|
||
управления |
логическое |
|
|
устройство |
Устройство |
|
|
|
|
|
вывода |
Рис. I.35. Классическое построение автоматической цифровой |
||
|
вычислительной машины. |
|
Первая из них состоит в том, что программа вводится через те же внешние устройства, что и данные и хранится в той же памяти, что и данные. Это обеспечивает:
1.Возможность автоматического исполнения программы;
2.Оперативную перестройку машины с одной задачи на другую без внесения каких - либо изменений в схему машины, делая компьютер универсальным инструментом обработки данных.
Вторая очень важная идея состоит в том, что составляющие программу команды закодированы в виде двоичных последовательностей и по форме ничем не отличаются от данных, с которыми оперирует компьютер. Это дает возможность в необходимых случаях рассматривать программу как набор данных, который можно преобразовывать посредством исполнения другой программы. Следствием этого является возможность построения средств автоматического программирования и средств автоматического управления вычислительным процессом.
Принципы фон - Неймана в сжатом виде формулируются следующим образом:
1. Информация кодируется в двоичной форме и представляется в виде наборов данных. Набор данных разделяется на единицы данных, называемые словами.
С. Г. Кузин. Логические основы автоматической обработки данных 77
Глава I. Автоматическое исполнение программы
2.Разнотипные слова различаются по способу использования, но не по способу кодирования.
3.Слова размещаются в ячейках памяти машины и идентифицируются номерами ячеек, называемыми адресами ячеек (адресами слов).
4.Алгоритм представляется в форме последовательности управляющих слов, которые определяют наименование операции и слова, участвующие в операции. Каждое такое управляющее слово называется командой. Алгоритм, представленный в виде последовательности машинных команд, называется программой.
5.Выполнение преобразования данных, предписанных алгоритмом, сводится к последовательному выполнению команд в порядке, однозначно определяемом программой и конкретным набором исходных данных.
Таким образом, очень распространенное сейчас слово "компьютер" означает: цифровая, универсальная, программно - управляемая вычислительная машина.
Здесь следует сделать два замечания. Во - первых, не все вычислительные машины являются цифровыми. Существует класс аналоговых вычислительных машин, работа которых основана на общности законов, описывающих процессы различной природы.
Так, например, можно построить электронную схему, колебания которой подчиняются тем же закономерностям, что и колебания маятника. И, вместо того, чтобы качать реальный маятник, можно изучать его поведение на электронной аналоговой вычислительной модели (машине) . Это возможно потому, что колебания маятника и колебания электронной схемы описываются одним и тем же дифференциальным уравнением. Самое интересное, что таким же дифференциальным уравнением описывается поведение биологической системы "хищник - жертва" и даже колебательные химические реакции.
В сороковых - пятидесятых годах XX-го века электронные аналоговые вычислительные машины создавали серьезную конкуренцию только что появившимся компьютерам. Но аналоговые машины не выдержали конкуренции с компьютерами по двум причинам:
1.Ограниченность круга решаемых задач (нет возможности решать логические задачи);
2.Малая точность вычислений.
Какое-то время аналоговые машины еще выигрывали гонку в быстродействии вычислений. Но колоссальные темпы роста объема памяти и быстродействия компьютера обеспечили ему приоритет и по этому параметру.
Во - вторых, не все программно - управляемые машины являются универсальными, т.е. допускают ввод и исполнение любой программы. Есть специализированные компьютеры, которые ориентированы на решение одной единственной задачи.
78 С.Г. Кузин. Логические основы автоматической обработки данных