Принцип условного перехода.

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

Принцип хранимой программы

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

ВОПРОС: Как можно использовать для модификации программы команду %: %,А1,А2,А3; которая, передает управление команде, размещенной в ОЗУ по адресу А2,

2. пересылает содержимое слова ОЗУ А1 в А3 (А3=А1).

Ответ: Замена команд другими командами программы, изменение порядка следования команд, и т.д.

Использование двоичной системы счисления для представления информации в ЭВМ.

ВОПРОСЫ: 1. Почему числа - степень двойки предпочтительны для измерения параметров оборудования ЭВМ. 2. Почему нумерация строк ОЗУ начинает с нуля.

Ответы: 1. Потому что они характеризуют, сколько двоичных слов может быть обработано или запомнено оборудованием, то есть характеризуют оборудование именно с точки зрения принципов работы ЭВМ. 2. Потому что строки ОЗУ адресуются смещением относительно начала ОЗУ. Соответственно первая строка имеет нулевое смещение, поэтому они и адресуются с 0.

Структура традиционных ЭВМ

Классические (Von Neumann architecture) ЭВМ имеют следующую структуру:

АЛУ + УУ + <кд........кд.....кд> + ОЗУ, где

ОЗУ (Оперативное Запоминающего Устройства) - память для хранения программ и данных. Таблица, каждая строка которой содержит команду или данное в двоичной системе счисления

УУ (Устройства Управления), устройство, которое последовательно выбирает команды из ОЗУ, дешифрирует их и организует выполнение заданных операций в АЛУ.

<кд........кд.....кд> последовательность команд и данных, причем данные как читаются из ОЗУ, так и туда же записываются.

Совокупность АЛУ и УУ принято называть процессором (ЦПУ,CPU), резервируя слово ЭВМ (ПЭ) для полного вычислительного комплекса. (По словарю А. Синклера "processor" - блок компьютера, выполняющий вычислительные действия). В современных микропроцессорах, микросхема процессора размещается на одном кристалле (чипе) , это: УУ + АЛУ + набор регистров + кэш память. В приведенной схеме не отражены устройства ввода/вывода информации, массовая память для постоянного хранения информации.

Все современные микропроцессоры имеют фон Нейманновскую архитектуру. Для ускорения вычислений которых предложено ряд параллельных архитектур вычислительных машин, для классификации которых , можно использовать нотацию М. Флинна (М.Flynn). (См. вопрос 30).

1. Конвейерная обработка данных.

Пример:

Длительность арифметической операции может быть уменьшена за счет временного перекрытия ее различных фаз, путем конвейеризации вычислительной работы. Для этого механизмы Арифметического Логического Устройства (АЛУ) выполняется по конвейерному принципу. Пусть, работа АЛУ - для сложении данных, разделена на три этапа, на три автономных блока Рi : Р1 - выравнивание порядков операндов, Р2 - операция сложения мантисс, Р3 - нормализация результата, каждый из ко­торых выполняется за один условный такт вычислителя.

A1 = B1+C1

A2 = B2+C2

A3 = B3+C3

A4 = B4+C4

Тогда временная диаграмма работы АЛУ имеет вид:

Устройство 1 такт 2 такт 3 такт 4 такт 5 такт 6 такт

P1 B1+C1 В2+C2 B3+C3 B4+C4 нет работы нет работы

P2 нет работы B1+C1 B2+C2 B3+C3 B4+C4 нет работы

P3 нет работы нет работы B1+C1 B2+C2 B3+C3 В4+С4

ВОПРОСЫ: 1. За сколько тактов будут выполнены эти вычисления, если АЛУ не конвейеризовано. 2. Сокращает ли конвейеризация время выполнения отдельной операции?

Ответы: 1. За 12 тактов. 2. Нет, конвейер предназначен для уменьшения времени выполнения нескольких последовательных команд.

Оптимальную загрузку конвейерных АЛУ можно получить при работе с регулярными структурами, например, по-элементное сложение векторов. В общем случае, пусть работа операционного блока разбивается на n последовательных частей (стадий, выполняемые за одинаковое время), на которых вычислительные операции выполняются в конвейерном режиме. Тогда, если на выполнение одной операции сложения блоку требуется время T, то на обработку N операций сложения время: Tn = (n + N) * (Т / n). Следовательно, если n << N, то ускорение вычислений будет в n раз.

Из-за зависимости по данным конвейеризация может терять эффективность. В таких случаях чаще всего используется оптимизация, заключающаяся в изменении порядка выполнения независимых команд (внеочередное выполнение команд). Методы динамической оптимизации: неупорядоченное выполнение - out-of-order execution, неупорядоченная выдача - out-of-order issue.

Пример:

A1 = B1+C1

A2 = A1+C2

A3 = B3+C3

A4 = B4+C4

8 тактов.

А вместо этого:

A1 = B1+C1

A3 = B3+C3

A4 = B4+C4

A2 = A1+C2

6 тактов.

Время выполнения отдельной скалярной операции на конвейерном вы­числителе равно: Т = S + K, где K - время работы, за которое конвейер выдает очередной результат, а S - время запуска конвейера, время заполнения конвейера, которое без учета времени подготовки операндов, равно: S = K*(m-1), где m - число ступеней конвейера. Производительность конвейерного вычислителя на скалярных операци­ях (число результатов, выдаваемых за единицу времени) равна: R = 1/(S + K).

Время выполнения векторной операции на конвейерном вычислителе равно: Т = S + K*N, где N - длина вектора. Производительность конвейерного вычислителя при векторной работе (число результатов, выдаваемых за единицу времени) равна: R = N/(S + K*N), асимптотическая производительность Rб = 1/K.

1. Зацепление конвейеров.

См. Вопрос 8.

1. Векторно-конвейерные вычислители.

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

Если вместо цикла:

DO L=1,N A(I) = B(I)+C(I) ENDDO

использовать запись алгоритма в виде векторной команды сложения вида:

VADD(B,C,A,N), то векторный вычислитель, выполняющий такие команды, будет вырабатывать результаты на каждом так­те. В таком вычислителе имеется один (или небольшое число) конвейерный процессор, выполняющий векторные команды путем засылки элементов векторов в конвейер с интервалом, равным длительности прохождения одной стадии обработки. Скорость вычислений зависит только от длительности стадии и не зависит от задержек в процессоре в целом.

Так как конвейер для однотипных операций дешевле и быстрее чем для многофункциональных операций, то выгодно их делать специализированными - однофункциональными: например, только для + или только для *. Для их совместного работы используется принцип зацепления конвейеров. Так, в ЭВМ Крей-1 имеется 12 конвейеров, из них 8 могут быть зацеплены, то есть результаты вычисления конвейера могут быть входными аргументами для другого. Операнды (результаты) находятся в памяти верхнего уровня или на регистрах. Для операндов задается: базовый адрес вектора, число элементов, тип данных в каждом элементе, схема хранения вектора в памяти. Некоторые векторные машины могут работать с двух-трех мерными массивами.

1. CISC и RISC архитектуры ЭВМ.

Традиционные процессоры универсальных ЭВМ называются CISC (Complex (Complicated) Instruction Set Computer) - компьютерами с полной системой команд (Семействa Intel ЭВМ от серии ix86 до Pentium и Pentium Pro). Помимо арифметических и логических операций в систему команд ((аппаратно реализуемые функции) включались сложные операции, такие как извлечения корня). Расширение спектра операций облегчает программирование и отладку программ, однако увеличивает трудоемкость разработки процессоров. Время выполнения даже таких операций, как умножение и деление чисел с плавающей запятой варьируется в зависимости от значений аргументов операций, что ограничивает возможности аппаратного планирования совмещенного выполнения команд. Исполнение процессоров на одном кристалле потребовало ревизии системы команд, CISC процессоры не помещались на одном кристалле – чипе СБИС, что привело к реализации компьютеров с сокращенным набором команд - RISC (Reduced Inctruction Set Computing) архитектуры. Традиционное число команд здесь - 128. Выполнение команд, не входящих в этот состав производится программно, для этого в архитектуре предусматривается развитый механизм реализации подпрограмм: реализация запоминания-восстановления регистров, стеки и т.д. Упрощение оборудования, конвейеризация выполнения команд позволило RISC процессорам резко повысить производительность. Недостатки данной архитектуры: отсутствие операций регистр-память вызывают необходимость подкачки данных командами обмена между регистровым файлом процессора и оперативной памятью, а ограниченный формат команд не позволяют минимизировать объем исполняемого кода. Наиболее известны следующие типовые архитектуры RISC процессоров микропроцессоров(МП): PowerPC, PA-RISC, Alpha, SPARC (Scalable Processor Architecture) - МП с изменяемой архитектурой, разработанный в 80 годы в Калифорнийском университете (Беркли); MIPS (Mikroprocessor without Interlocked Pipeline Stages) - МП без блокировки конвейера, разработанный в 80 годы в Стенфордском университете, архитектура запатентована в 1990г.

1. Внеочередное и спекулятивное выполнения команд.

Внеочередное выполнение команд – см. Вопрос 6.

В конвейерных архитектурах устройство выборки команд является та­ким же конвейером, как и другие функциональные устройства. Так, для условного операторы: IF (A<B) GO TO L:S1;L:S2 еще до вычисления значе­ния условного выражения А<В необходимо решать задачу о заполнении кон­вейера команд кодами S1 или S2 – спекулятивного выполнения программы (чтобы не было пропуска тактов конвейе­ра из-за неверно выбранной ветки, коды которой потребуется убирать из конвейера). Про механизмы предсказания переходов см. Вопрос 11.

1. Механизмы предсказания переходов.

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

Аппаратный механизм учета вероятности перехода состоит из блока предсказания переходов. Этот блок, кроме (вместо) статически определенных предпочтений для ветвлений, имеет таблицу переходов, в которой хранится история переходов для каждого (в рамках объема таблицы) перехода программы. Большинства современных микропроцессоров обещают точ­ность предсказаний переходов этим способом выше 90%. Причина повышенного внимания к этому вопросу обусловлена большими за­держками, возникающими при неверном предсказании переходов, что грозит существенной потерей производительности. Используемые в микропроцессо­рах методы предсказания переходов, как уже было сказано, бывают стати­ческие и динамические. Как динамический, так и статический подходы имеют свои преимущества и недостатки.

Статические методы предсказания используются реже. Такие предска­зания делаются компилятором еще до момента выполнения программы. Соот­ветствующие действия компилятора можно считать оптимизацией программ. Такая оптимизация может основываться на сборе информации, получаемой при тестовом прогоне программы (Profile Based Optimisation, PBO) или на эвристических оценках. Результатом деятельности компилятора являются "советы о направлении перехода", помещаемые непосредственно в коды выполняемой программы. Эти советы использует затем аппаратура во время выполнения. В случае, когда переход происходит, или наоборот - как правило, не происходит, советы компилятора часто бывают весьма точны, что ведет к отличным результатам. Преимущество статического подхода - отсутствие необходимости интегрировать на чипе дополнительную аппаратуру предсказания переходов.

Большинство производителей современных микропроцессоров снабжают их различными средствами динамического предсказания переходов, производимого на базе анализа "предыстории". Тогда аппаратура собирает статистику переходов, которая помещается в таблицу истории переходов BHT (Branch History Tab­le).В обоих случаях компилятор не может выработать эффективные рекомендации на этапе трансляции программы. В то же время схемы динамического предсказания переходов легко справля­ются с такими задачами. В этом смысле динамическое предсказание пере­ходов "мощнее" статического. Однако у динамического предсказания есть и свои слабые места - это проблемы, возникающие из-за ограниченности ресурсов для сбора статистики.

1. Управление виртуальной памятью.

Адресация памяти производится с точностью до байта, длина адреса, его разрядность, определяет пространство памяти, которое может быть доступно ("видимо") в программе. Так 32 разрядный виртуальный адрес охватывает пространство в 4 Гбай­та. Это виртуальное пространство - математическая память программы мо­жет не совпадать с реальным, физическим пространством памяти ЭВМ.

Адреса виртуального пространства памяти - виртуальные ад­реса, а адреса физического пространства - физические адреса.

Механизм виртуальной памяти позволяет: