Понятие алгоритма.

Лекция 2. Многоуровневая компьютерная организация.

1.1. Принципы программного управления

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

Понятие алгоритма.

2. Принцип программного управления.

Алгоритм – некоторая однозначно определенная последовательность действий, состоящая из формально заданных операций над исходными данными, приводящая к решению за конечное число шагов.

Свойства алгоритмов:

1. дискретность алгоритма (действия выполняются по шагам, а сама информация дискретна)

2. детерменированность (сколько бы раз один и тот же алгоритм не реализовывался для одних и тех же данных результат один и тот же)

3. массовость (алгоритм “решает задачу” для различных исходных данных из допустимого множества и дает всегда правильный результат)

Программа – описание алгоритма на каком-либо языке.

Современные ЭВМ строятся на одном принципе – принципе программного управления. В основе принципа программного управления лежит представление алгоритма в форме операторной схемы, которая задает правило вычислений, как композицию операторов (операций над информацией) двух типов: операторов, обеспечивающих преобразование информации, и операторов, анализирующих информацию с целью определения порядка выполнения операторов. Реализация этого принципа в различных ЭВМ может быть разной. Используемый в современных компьютерах принцип программного управления был предложен в 1945 году Дж. фон Нейманом [2], и с тех пор неймановский принцип программного управления используется в качестве основного принципа построения ЭВМ. Этот принцип включает следующие положения.

1. Информация кодируется в двоичной форме и разделяется на единицы (элементы) информации, называемые словами.

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

3. Слова информации размещаются в ячейках памяти машины и идентифицируются номерами ячеек, называемыми адресами слов.

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

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

Дадим некоторые короткие комментарии перечисленных положений принципа программного управления.

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

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

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

В четвертом положении принципа программного управления утверждается, что программа представляется в ЭВМ в виде упорядоченной линейной последовательности команд следующего вида:

1 r 1 m 1 m 1 m 1 m 1 m

КО

А

А

...

...

А

Здесь прямоугольник обозначает слово информации, части которого, имеющие определенный смысл, принято называть полями. Так, КО, А , А , ... , А - поля команды, представляющие соответственно код операции и адреса операндов, участвующих в операции. Сверху указаны номера двоичных разрядов полей: код операции состоит из r битов, каждое поле адреса операнда А - А содержит m битов. Приведенное представление команды характеризует структуру или, иначе, формат команды.

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

Неймановский принцип программного управления не является единственно возможным принципом функциональной организации ЭВМ. Так, Дж. Айлиф в [3 ] предлагает принципы построения машины, отличной от традиционных неймановских машин. Отличия сводятся в основном к следующему.

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

Во-вторых, вследствие линейности памяти ЭВМ ( см. пояснения к п.5), программист вынужден любую структуру данных (вектор, матрицу, таблицу) спроектировать на линейную цепочку адресов I, I+1, ......I+N. Затем при обработке информации из структуры данных, приходится выделять адреса отдельных структурных элементов. Процедуры размещения в памяти и выделения из нее отдельных элементов достаточно сложны. Дж. Айтлиф предлагает вносить описание структуры данных непосредственно в память машины и за счет этого обеспечить автоматическое выявление адресов отдельных элементов в процессе выполнения программы, что также должно уменьшить число потенциальных ошибок программиста.

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