Кафедра ИТ-4 «Персональные компьютеры и сети»

ЛЕКЦИИ

по дисциплине Теория вычислительных процессов

Рекомендуется для направления подготовки

230100 «Информатика и вычислительная техника»

Профиль подготовки

«Вычислительные машины, комплексы, системы и сети»

Квалификация (степень) выпускника - бакалавр

Москва, 2013

1 Общие положения

1.1 Цели и задачи дисциплины

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

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

2 Лекция №1 СХЕМЫ АЛГОРИТМОВ

2.1 Ключевые (основные) вопросы (моменты)

— схемы Ляпунова-Янова;

— программы и микропрограммы.

2.2 Текст лекции

2.2.1 Схемы Ляпунова-Янова

В 1953 году А.А. Ляпунов предложил записывать алгоритмы в виде конечной строки, состоящей из символов операторов (термин введён Ляпуновым) и логических условий, называемых членами схемы, а также верхних и нижних стрелок, которым приписаны натуральные числа:

_{1 1 2 2 2}

ω_н ω₁ z₁ ↑ω₂ ω₃ ↓ z₂ ↑ ω₄ ω₅ z₃ ↑ω₆ ↓ ω₇ ω_к.

В этой схеме кроме начального (ω_н) и конечного (ω_к) операторов используются семь операторов (ω₁,ω₂,…,ω₇) и три логических условия (z₁,z₂,z₃), все символы рассматриваются слева направо. В случае если логическое условие z_i = 0, происходит переход по верхней стрелке, следующей за этим логическим условием, к нижней стрелке с тем же номером без выполнения, стоящих между этими стрелками операторов. В случае если логическое условие z_i=1, выполняется следующий за стрелкой оператор.

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

Логические схемы алгоритмов удовлетворяют следующим условиям:

1) содержат один начальный (ω_н) и один конечный оператор (ω_к);

2) перед оператором ω_н и после оператора ω_к стрелок быть не должно;

3) вслед за каждым логическим условием (z_i) всегда стоит верхняя стрелка;

4) не существует одинаковых (с одинаковыми цифрами) нижних стрелок;

5) для каждой нижней стрелки должна быть по крайней мере одна соответствующая ей (с одинаковой цифрой) верхняя стрелка;

6) для каждой верхней стрелки должна быть точно одна соответствующая ей (с одинаковой цифрой) нижняя стрелка.

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

Благодаря использованию схем появилась возможность исследовать общие свойства программ, не зависящие от примененных конкретных понятий, а также общие их преобразования. Схемы программ стали основным объектом исследования ученика А.А.Ляпунова, Ю.И.Янова, который в 1958 году в своей работе “О логических схемах алгоритмов”, впервые представил разработанные на схемах системы эквивалентных преобразований программ.

В схемах Янова используется лишь одна переменная, все функции и предикаты одноместные, функция f уникальна для каждого присваивания. Дополнительно в вычислительную модель вводится значение s, называемое текущим состоянием мира, которое принадлежит множеству S полных состояний вычислительной системы. Прежде чем обратиться к таким моделям вычислений, как автоматы, отметим, что в 1964 году в работе Ратледжа (J.D.Rutledge, On Ianov’s Program Schemata) была показана адекватность схем, принадлежащих максимальной модели программ без процедур (т.е. схем Ляпунова-Янова), конечным автоматам.

Разновидностью языка, позволяющего описывать логические схемы алгоритмов, является язык граф-схем алгоритмов (ГСА), который используется не только для описания формальных элементов, но дает возможность представить логические условия и операторы в содержательных терминах. Язык граф-схем алгоритмов рассматривается в следующем разделе учебного пособия.

2.2.2 Программы

Один из способов представления алгоритмов – машинная программа, которая согласно стандарту ISO 2382/1-84, представляет собой упорядоченную последовательность команд, подлежащую обработке. Как и для алгоритма, для программы также характерно свойство вложенности (уровни задания, задачи, подзадачи, операции, микрооперации). Эти уровни определяются особенностями программирования и управления вычислительным процессом, при этом их границы не могут быть установлены жестко.

Полный перечень команд, которые способна выполнять вычислительная система образует систему команд. Близость системы команд и множества операций, необходимых для выполнения алгоритма, характеризует степень приспособленности операций, реализуемых аппаратными средствами, к алгоритмам решаемых задач. Чем меньше команд требуется для составления программы реализации какого-либо алгоритма, тем выше программируемость вычислительной машины. Расширяя систему команд вычислительной машины сложными командами, подобными операторам языка высокого уровня, пытаются решить проблему семантического разрыва, заключающуюся в существенном отличии сложных операторов, характерных для языков высокого уровня от простых машинных команд. Однако, данный путь ведет к усложнению аппаратуры и негативно сказывается на производительности вычислительной системы. Большое количество машинных команд различного формата с разнообразными способами адресации операндов характерно для CISC (Complex Instruction Set Computer) архитектуры.

Упростить аппаратные средства вычислительной системы и повысить ее быстродействие можно за счет сокращения числа форматов команд и способов адресации памяти, что было положено в основу RISC (Reduced Instruction Set Computer) архитектуры. RISC архитектура имеет сокращенный набор часто используемых команд и предполагает уменьшение времени выполнения программы за счет сокращения среднего количества тактов процессора, приходящихся на одну команду, а также длительности тактового периода.

Термин “RISC” впервые был использован Паттерсоном и Дитцелем (D.Patterson, D.Ditzel) в 1980 году. Предложенная ими идея заключалась в ограничении списка команд вычислительной машины часто используемыми простыми командами, оперирующими данными, размещенными только в регистрах процессора. Для обращения к основной памяти предлагалось использование отдельных команд чтения и записи.

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

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

Дата добавления: 2014-11-24; просмотров: 283; Нарушение авторских прав

Мы поможем в написании ваших работ!