Способы представления алгоритмов

На практике наиболее распространены следующие формы представления алгоритмов:

1. Словесная (записи на естественном языке);

2. в виде блок-схемы (графический способ)

3. в виде программы (тексты на языках программирования)

Программное управление вычислительным процессом

Все современные вычислительные машины построены по принципам и имеют структуру, предложенную еще в 40–х годах академиком Джоном Фон Нейманом.

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

· вычислительная машина конструктивно делится на ряд устройств: процессор, запоминающее устройство (для хранения программ и данных), устройство ввода–вывода и т.д.;

· наличие хранимой в памяти программы;

· одинаковое представление чисел и команд в виде двоичных кодов;

· принцип микропрограммного управления процессом вычислений;

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

Согласно первому принципу ЭВМ состоит из ряда устройств, взаимодействующих друг с другом в процессе решения задачи. Рассмотрим кратко основные устройства и их функции (рис. 2.1).

Рис.2.1. Структурная схема ЭВМ

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

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

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

Память ЭВМ к настоящему времени приобрела довольно сложную структуру и "расползлась" по многим компонентам. Кроме оперативной, память включает также и постоянную (ПЗУ), из которой можно только считывать команды и данные, и некоторые виды специальной памяти (например видеопамять графического адаптера). Вся эта память вместе с оперативной располагается в едином пространстве с линейной адресацией. В любом компьютере обязательно есть постоянная память, в которой хранится программа начального запуска компьютера и минимальный необходимый набор сервисов (например: ROM BIOS).

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

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

Устройства ввода/вывода (УВВ) служат для преобразования информации из внутреннего представления в компьютере (биты и байты) в форму, доступную окружающим, и обратно. Под окружающими понимаем как людей, так и другие машины (например технологическое оборудование, которым управляет компьютер). К устройствам ввода относятся клавиатура, мышь, джойстик, микрофон, сканер, видеокамера, различные датчики; к устройствам вывода – дисплей, принтер, плоттер, акустические системы (наушники), исполнительные механизмы. Список устройств ввода/вывода безграничен – благодаря фантазии и техническому прогрессу в него входят все новые и новые устройства; так, например, шлем виртуальной реальности из области фантастики вышел в производственно–коммерческую. Устройства хранения к УВВ относить некорректно, поскольку здесь преобразования информации ради доступности внешнему миру не происходит. Устройства хранения вместе с УВВ можно объединить общим понятием периферийные устройства. Существует еще большой класс коммуникационных устройств,предназначенных для передачи информации между компьютерами и (или) их частями. Эти устройства обеспечивают, например, соединение компьютеров в локальные сети или подключение терминала (это УВВ) к компьютеру через пару модемов. Периферийные и коммуникационные устройства снабжаются контроллерами или адаптерами, которые доступны процессору.

Cостав машинных команд

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

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

Машинная программа – это алгоритм, заданный в виде последовательности машинных команд.

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

Машинная команда состоит из двух частей: операционной и адресной.

Операционная часть команды – это группа разрядов в команде, предназначенная для указания кода операции.

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

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

КОП – код операции;

а1 и а2 – адреса ячеек (регистров), где расположены данные, участвующие в операции;

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

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

а2 – адрес ячейки (регистра), где расположено второе из данных, участвующее в операции.

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

Безадресная команда содержит только код операции, а данные для нее должны быть заранее помещены в определенные регистры машины.

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

- операции пересылки данных внутри компьютера;

- арифметические операции над данными;

- логические операции над данными;

- операции обращения к внешним устройствам компьютера;

- операции передачи управления;

- обслуживающие и вспомогательные операции.

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

Адресация регистров и ячеек памяти в компьютерах

Адресация — осуществление ссылки (обращение) к устройству или элементу данных по его адресу; установление соответствия между множеством однотипных объектов и множеством их адресов; метод идентификации местоположения объекта.

Методы адресации

Адресное пространство

· Простая (англ. flat addressing) — указание объекта с помощью идентификатора или числа, не имеющего внутренней структуры.

· Расширенная (англ. extended addressing) — доступ к запоминающему устройству с адресным пространством, бо́льшим диапазоном адресов, предусмотренного форматомкоманды

· Виртуальная (англ. virtual addressing) — принцип, при котором каждая программа рассматривается как ограниченное непрерывное поле логической памяти, а адреса этого поля — как виртуальные адреса.

· Ассоциативная (англ. associative addressing) — точное местоположение данных не указывается, а задаётся значение определённого поля данных, идентифицирующее эти данные (см.: Ассоциативная память).

Исполнение программ

· Статическая (англ. static addressing) — соответствие между виртуальными и физическими адресами устанавливается до начала и не меняется в ходе выполнения программы.

· Динамическая (англ. dynamic addressing) — преобразование виртуальных адресов в физические осуществляется в процессе выполнения программы. Программа при этом не зависит от места размещения в физической памяти и может перемещаться в ней в процессе выполнения.

Кодирование адресов

· Явная (англ. explicit addressing) — адресация путём явного задания адресов в программе.

· Неявная (англ. implied addressing) — один или несколько операндов или адресов операндов находятся в фиксированных для данной командырегистрах или ячейках памяти и не требуют явного указания в команде.

· Абсолютная (англ. absolute addressing) — адресная часть команды содержит абсолютный адрес.

· Символическая (англ. symbolic addressing) — адресная часть команды содержит символический адрес.

Вычисление адресов

· Непосредственная, прямая (англ. immediate (direct) addressing) — адресная часть команды содержит непосредственный (прямой) адрес; адресация путём указания прямых адресов.

· Косвенная (англ. indirect addressing) — адресная часть команды содержит косвенный адрес; адресация посредством косвенных адресов.

· Регистровая (англ. register addressing) — задание адресов операндов в регистрах.

· Базисная (англ. basic addressing) — вычисление адресов в машинных командах относительно содержимого регистра, указанного в качестве базового.

· Базовая (англ. base-displacement addressing) — схема вычисления исполнительного адреса, при которой этот адрес является суммой базового адреса и смещения.

· Относительная (англ. relative addressing) — адресная часть команды содержит относительный адрес.

· Индексная (англ. indexed addressing) — формирование исполнительного адреса осуществляется путём добавления к базовому адресу содержимого индексного регистра.

· Автодекрементная, автоинкрементная (англ. autodecremental, autoincremental addressing) — содержимое регистра индекса изменяется (уменьшается или увеличивается) на некоторое число.

· Постдекрементная, предекрементная, постинкрементная, преинкрементная — автодекрементные и автоинкрементные адресации, при которых уменьшение/увеличение происходит после/до выборки операнда.

· Стековая (англ. stack addressing) — адресация посредством регистра — указателя стека.

· Самоопределяющаяся (англ. self-relative addressing) — адресная часть команды содержит самоопределяющийся адрес.

· Адресация относительно счётчика команд (англ. program counter relative addressing) — адреса в команде указываются в виде разности исполнительных адресов и адреса исполняемой команды. Такой способ адресации не требует настройки (см. также: Позиционно-независимый код).

Способы адресации[править | править код]

Подразумеваемый операнд[править | править код]

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

Подразумеваемый адрес[править | править код]

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

Непосредственная адресация[править | править код]

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

Прямая адресация[править | править код]

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