Лекция 11. Компьютер как система для манипулирования символьными структурами icon

Лекция 11. Компьютер как система для манипулирования символьными структурами

Смотрите также:
Лекция 1, часть 2...
Лекция 5
Любая компьютерная программа представляет собой последовательность отдельных команд...
Реферат по теме: «Устройства компьютера»...
Лекция 01. Введение. Информатика Информация. Компьютер. Системный подход. Операционная система...
Лекция Финансы, финансовая система Лекция посвящена рассмотрению того...
Лекция 14. Мировая экономика как система. (4 ч)...
Стратегии и тактики влияния и манипулирования...
В. А. Галкин Научно-образовательный материал «Автоматизированная система рубежного контроля...
Лекция для родителей «Компьютер: за и против»...
«оценка информации для исключения манипулирования сознанием»: цикл занятий для учащихся 9-10 -Х...
Лекция №9 Стандартизация сетей Понятие "открытая система"...



скачать

Лекция 11. Компьютер как система для манипулирования символьными структурами

11.1. Фон Неймановская модель компьютера

Память данных и память команд содержит слова в двоичном алфавите. Это позволяет объединить их в одно устройство – оперативную память.

В
Формат команды

КОП

Адр 1

Адр 2

Адр ререзультата



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

Рис. 11.1


Что же это за условия?

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

  1. Из памяти по адресу, формируемому Сч. Ком. в УУ процессора, извлекается слово в двоичном алфавите.

Оно поступает в Рг. Ком. УУ, дешифруется и обеспечивает настройку АЛУ на соответствующую операцию.

  1. Процессор извлекает исходные данные из ячеек памяти, адреса которых указаны в команде.

Операнды в виде слов в двоичного алфавита поступает в Рг. АЛУ.

Интерпретация этих слов определяется выполняемой операцией.

  1. Результат пересылается в память данных по указанному адресу.

  2. Процессор переходит к новой инструкции (либо к следующей, либо к той, адрес которой указан в обрабатываемой инструкции).

И так до инструкции СТОП.

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

Принципы фон Неймана:

  • Машина с программным управлением состоит из устройства, исполняющего команды и устройства для хранения информации (данных, команд);

  • Память представляет последовательность нумерованных ячеек, в каждой из которых хранится слово в двоичном алфавите. Оно может задавать операцию, номер (адрес) другой ячейки или элемент данных;

  • Команды для исполнения АЛУ выбираются последовательно одна за другой. Слово, поступающее в УУ, интерпретируется как операция, а слово, поступающее в АЛУ – как данные.

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

  • за словом, представляющим операцию, может следовать несколько операций – чисел, символов или адресов ячеек, с которыми будет определена операция.

  • неизменность структуры физических связей между устройствами машины; подлежат изменению только логические связи.
^

11.2. Общая характеристика выполнения фон-неймановской машинной программы


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

На рис. 11.2 представлена традиционная фон-неймановская архитектура процессора с одним потоком данных и одним потоком команд.

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

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

  2. ^ Управление системой – другая главная функция процессора. Схемы управления позволяют декодировать и выполнять программу. Они обеспечивают запись команд в память на хранение и извлекают их оттуда одну за другой. После извлечения из памяти узел дешифрации декодирует поступившее машинное слово и формирует необходимые для АЛУ управляющие сигналы. На рис. 11.3 приведена обобщенная схема, описывающая логику выполнения программы. Счетчик команд устанавливается на начало последовательности команд, где находится обрабатываемая машиной программа.

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

Последовательность выполнения двух команд A и B: 1) вызов адреса команды A; 2) фиксация команды в регистре команд; 3) дешифрация команды, инкремент программного счетчика; 4) фиксация операндов для команды A; 5) вызов адреса команды B, выполнение операции, запоминание результата во внутреннем регистре; 6) вызов адреса ячейки памяти для хранения результата, запоминание результата во внешней памяти; 7) выборка следующей команды.

Задача программы, таким образом, состоит в том, чтобы последовательно, шаг за шагом, изменять содержимое памяти до тех пор, пока не будет достигнуто завершающее состояние (реализуется так называемая семантика смены состояний). Заметим, что эта задача решается за счет “перекачивания” одиночных слов (адресов, команд, данных) туда и обратно через канал передачи информации, являющийся “узким” местом машины фон Неймана. Заслуживает внимания то обстоятельство, что значительную часть потока слов составляют не полезные данные (в смысле объектов обработки), а всего лишь имена данных, а также операции и данные, служащие лишь для вычисления таких имен. Прежде чем слово можно будет послать через шину, его адрес должен находиться в процессоре; поэтому он должен либо быть послан через шину из памяти, либо генерироваться посредством некоторых операций АЛУ. Если адрес посылается из памяти, то адрес этого адреса должен быть послан из памяти либо генерироваться в процессоре, и т. д. С другой стороны, если адрес генерируется в процессоре, он должен формироваться либо по фиксированному правилу (например, инкремент: “добавить 1 к программному счетчику”), либо по команде передачи управления. Адрес последней также должен быть предварительно послан по шине и т. д.

Здесь уместно привести высказывание Дж. Бэкуса, одного из основоположников процедурного стиля программирования: “… должен существовать менее примитивный способ внесения в память больших изменений, чем мельтешение множества слов туда и обратно через узость фон Неймана. Эта шина является не только узким местом для потока данных задачи, но, что более важно, и интеллектуальной узостью, которая привязывает нас к мышлению “слово за словом” вместо того, чтобы вдохновлять нас на мышление более “крупными” концептуальными частями решаемой задачи”.

Из этих простейших понятий выросли все алгоритмические языки программирования. Понятие ячейки памяти эволюционировало в разнообразные структуры и типы данных, а простейшие инструкции машинного языка превратились в сложные операторы алгоритмических языков высокого уровня. Однако суть процедурного стиля программирования при этом не изменилась. Ее можно свести к двум основным понятиям: операторы присваивания и передачи управления. Переменная связана с пассивным запоминающим устройством, оператор присваивания – с АЛУ и памятью, порядок выполнения операторов – с устройством управления.
^

11.3. Механизмы управления и обмена данными в процессе выполнения программы


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

Два механизма определяют фундаментальные характеристики выполнения программ: механизм управления и механизм обмена данными. Механизм управления сводится к запуску команд либо “по доступности”, когда операция активизируется, если доступны все операнды, либо “по запросу”, когда операция активизируется, если имеется запрос на генерацию ее результатов. Аналогично имеется два принципиально различных механизма обмена данными: непосредственный обмен значениями операндов и передача по ссылке через общедоступную память.

Классическая архитектура фон Неймана использует механизм управления “по запросу” с привлечением принципа потока управления и механизм обмена данными по ссылке через общедоступную память. Рассмотрим в качестве примера программу для оператора := (y+1)*(yz). Этот оператор присваивания осуществляет вызов содержимого ячеек памяти, на которые ссылаются переменные с именами y, z, константы 1, выполнение арифметических операций +, –, * над целыми числами и запоминание полученного результата в ячейке памяти, на которую ссылается переменная x.

Граф связей по данным этого оператора изображен на рис. 11.4.

Здесь зачерненными кружочками “” изображены значения подлежащих обработке данных с именами y, и z, а также значение формируемого результата с именем x. Сплошными линиями представлены связи, отражающие структуру оператора по данным (отношение частичного порядка). Прямоугольниками представлены операции по обработке данных. Программа реализации этого оператора представлена на рис. 11.5.



Соответствующий этой программе граф связей по управлению изображен на рис. 11.6. Здесь же именованными кружочками представлено поле памяти. Прямоугольниками показаны команды с именами I1, I2, I3.

Заметим, что идентификаторы (имена) y, , z используются для ссылки к содержимому памяти, а идентификатор x – для ссылки к адресу ячейки памяти. Роль идентификаторов t1 и t2 двойственна: в командах I1 и I2 они используются для ссылки к адресам ячеек памяти, в команде I3 – для ссылки к содержимому этих ячеек. Соответствующая их интерпретация видна из контекста программы и семантики оператора присваивания.

Память, как уже отмечалось, имеет линейную однородную структуру, состоящую из слов в двоичном алфавите, используемых как для хранения программы, так и для хранения данных. При этом по содержимому элемента памяти нельзя определить тип хранимой в нем информации. При исполнении машинных команд данные трактуются в зависимости от семантики команд, а не от типов самих данных. Уровень такой архитектуры компьютера значительно ниже уровня языков программирования, имеющих средства описания типов данных*. Этот семантический разрыв имеет отрицательные практические последствия для программистов, отлаживающих и использующих программы в такой вычислительной среде.

Возможный вариант программы с явно выделенной решающей частью представлен на рис. 11.7. Первая, содержащая операторы присваивания, формирует связи по данным реализуемого оператора; вторая, содержащая последовательность так называемых управляющих переменных, формирует связи по управлению. Управляющая переменная принимает значения из множества {0, 1}. Единичное значение активизирует выполнение соответствующего оператора решающей части программы, нулевое – дезактивирует.

Выполнение программы можно представить в виде последовательности состояний памяти (вектора значений переменных) и метки управляющей переменной. Эту пару называют конфигурацией, а последовательность конфигураций, порождаемых при выполнении программы,– протоколом выполнения программы. В нашем случае вектор переменных имеет пять компонентов  = <x, y, z, t1, t2>; метку управляющей переменной обозначим k, а конфигурацию <, k> – через r. Для построения протокола выполнения программы, описывающего вычислительный процесс для оператора := (y+1)*(yz), принимается во внимание функция перехода : <i, ki>  <i+1, ki+1>. Эта функция позволяет задать отношение следования на множестве конфигураций; здесь i – порядковый номер конфигурации, порождаемой в процессе выполнения программы.

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

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

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

1. ^ Начальный шаг. Допустим, что значения подлежащих обработке переменных y, z определены в результате отработки оператора “вход y, z”. Содержимое ячеек памяти с именами x, t1, t2 не определено. Имеет место вектор начальных значений 0 = <*, y0, z0, *, *>, где * – неопределенное значение; y0, z0 – начальные значения переменных y, z. Первым элементом управляющей части программы является символ старт, которому приписана метка 0. Тогда начальную конфигурацию программы представим в виде <0, 0>.

2. ^ Шаг выполнения. Допустим, что текущая конфигурация программы имеет вид <i, ki>. В зависимости от того, какой элемент управляющей части следует за меткой ki, необходимо выполнить следующие действия:

а) если элемент с меткой ki представляет собой символ старт, то следующая конфигурация определяется как <0, 0>;

б) если элемент с меткой ki представляет собой символ стоп, то конфигурация <i, ki> является заключительной, а значение переменной x в векторе i = <xi, yi, zi, t1i, t2i> определяет результат выполнения программы;

в) если элемент с меткой ki представляет собой символ управляющей переменной vj, то производятся следующие действия:

  • управляющей переменной vj присваивается значение 1,

  • среди операторов решающей части программы выбирается и выполняется оператор с активной меткой vj,

  • после приписывания нового значения компоненту вектора переменных , которое получено в результате выполнения выбранного оператора присваивания, получим новый вектор значений переменных i+1,

  • управляющей переменной vj присваивается значение 0,

  • определяется значение новой метки как ki+1 = ki+1.

П

Конфигурация

Метки элемента управляющей части программы

Вектор значений переменных

x

y

z

t1

t2

r0

0


*

2

9

*

*

r1

1


*

2

9

*

*

r2

2


*

2

9

3

*

r3

3


*

2

9

3

-7

r4

4


-21

2

9

3

-7

r5

5


-21

2

9

3

-7

Рис. 11.8. Протокол выполнения программы с явно выделенной решающей частью и частью управления для оператора := (y+1)*(yz)
ротокол выполнения программы (рис. ) для вектора начальных условий 0 = <*, 2, 9, *, *> приведен на рис. 11.8.

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

Завершая обсуждение последовательного вычислительного процесса, разворачивающегося в однопроцессорной машине фон Неймана, обратим внимание на возможности механизма многолинейного управления применительно к рассматриваемой задаче в случае наличия в машине двух операционных устройств. Речь идет о такой организации вычислений, когда на одном и том же шаге процесса выполняются операторы t1 := y1+1 и t2 := y2–z (y=y1=y2). Соответствующий граф связей по управлению представлен на рис. 11.9.

О







Вход y, z;

v1

v2

..

..

t1 := y1+1; t2 := y2–z;

x := t1* t2

0

..

Старт

1

2

3

..

..

..

v1

v2

Стоп







Выход x;

Рис. 11.10. Программа, порождающая параллельный вычислительный процесс на машине с механизмом многолинейного управления

бмен данными ведется через общедоступную память путем обращения к ячейкам, имена которых “встроены” в команды. Принято допущение о том, что при загрузке исходного значения переменной y осуществляется его копирование. Дубли располагаются в ячейках с именами y1 и y2, что исключает конфликт при обращении к памяти операционных устройств, реализующих команды I1 и I2 в один и тот же момент времени.

На рис. 11.10 представлена программа, в результате выполнения которой реализуется описанный выше параллельный процесс в машине с механизмом многолинейного управления.

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

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

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


* Тип данных есть метод рассмотрения содержимого памяти. Это содержимое не имеет независимого самостоятельного значения.


* Книга Н. Вирта “Алгоритмы + Структуры данных = Программы” пользуется большой популярностью в среде программистов. См. также учебное пособие Фомичева В.С. Организация вычислительных процессов / ЛЭТИ. Л., 1984.



База данных защищена авторским правом © kursovaya-referat.ru 2017
При копировании материала укажите ссылку