Программное управление

Размещено на http://www.allbest.ru/

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

программный управление память оперативный

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

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

1945г. - Фон Нейман - венгерский математик сформулировал основные положения программного управления:

1). Данные представляются в двоичной форме и подразделяются на элементы данных - слова.

Слово - машинный элемент информации, обрабатываемый, как единое целое. Словом могут быть представлены команда, символ, число. Слово - это наименьшая обрабатываемая единица.

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

3). Слова данных хранятся в ячейках данных и идентифицируются номерами ячеек (адресом).

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

4). Алгоритм представляется в виде последовательности управляющих слов называемых командами и имеющих операционно-адресную структуру:

Рис.

Здесь:

КОП - код операции, определяет тип действия, способы адресации операндов, тип операндов.

А₁, А_2, А_L - адреса операндов (адресный код);

Адресные коды определяют местоположение операндов.

N = 2^k - максимальное количество команд (для k=8 разрядов N=256);

Под L понимают адресность L=0, 1, 2, 3.

Если L = 0, то команда безадресная. (пример: NOP - отсутствие операции)

Если L = 1, то команда одноадресная, адрес указывает на один операнд, а другой операнд это регистр (какой регистр - это заложено в КОП). Для программиста это неудобно, зато команда короткая.

Если L = 3, то команда имеет три адреса, соответственно под: первый операнд, второй операнд и результат, данная адресность удобна для программиста (самая удобная), но такая команда является длинной. Оптимальное соотношение длина/удобство достигается для команды с двумя операндами.

Если L=2, то команда имеет 2 адреса, соответственно под первый и второй операнды, результат сохраняется в один из операндов (команды sub, add).

Так как m разрядов отводится под адрес операнда, то соответственно емкость памяти: Eпам=2^m [слов]. Разрядность адреса можно найти по формуле:

m=log₂Eпам.

Для IBM Eпам = 4 [Гб] = 2³² [бит].

Следовательно m= log₂2³² = 32 [бит].

5). Процесс выполнения алгоритма сводится к последовательному выполнению команд в порядке, определенном программистом.

Программа хранится в памяти ЭВМ.

Первая команда программы задает начало программы (регистр IP это счетчик команд - указывает на текущую команду).

Исторически существовало несколько систем счисления, в которых физически представляются данные вычислительной системы, это:

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

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

десятичная система - реализованная на лампах с 10-ю состояниями - декатронах.

Физически информация хранится в элементах, имеющим 2 состояния, логически объединение таких элементов в группы могут реализовывать 4, 8, 16 системы счисления (далее с/с).

Удобной для человека является двоично - десятичная система (далее {2-10}) счисления. Часто она необходимо для вывода информации на экран в виде десятичных цифр. Перевод в {2-10} может осуществляться из 2 с/с, а может и не осуществляться если числа в {2-10} системе хранить и обрабатывать с применением {2-10} алгебры. Область применения: в устройствах, где не всегда целесообразно предусматривать универсальный микрокод перевода двоичных чисел в десятичные и обратно по причине небольшого объема программной памяти.

Под цифру в {2-10} отводится 4 бита (как и в 16 с/с), но используются не все возможные комбинации (6 комбинаций не используется).

Для хранения и обработки чисел в {2-10} используются D-коды, например, такие как 8-4-2-1 или например с избытком 6.

Способы адресации:

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

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

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

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

Недостатком косвенной адресации является необходимость в двухкратном обращении к памяти: сначала для извлечения адреса операнда, а затем по этому адресу для обращения к операнду.

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

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

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

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

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

Определяет функционирование процессора в дискретном времени при реализации операций.

Постулаты:

1). Любая операция fg реализуемая операционным устройством (ОУ) рассматривается как сложное действие и разделяется на последовательность элементарных действий, называемых микрооперациями (МО).

2). Для управления порядком следования микроопераций используются логические условия (ЛУ), которые принимают значений «истина» или «ложь».

3). Процесс выполнения операций в ОУ описывается в терминах микроопераций и логический условий и называется микропрограммой (МП). МП - определяет порядок проверки ЛУ и на этой основе порядок следования микроопераций.

4). Микропрограмма - это форма представления функций ОУ, на основе которой определяется структура ОУ и порядок его функционирования во времени.

Рис.

УА - Управляющий автомат - предназначен для формирования управляющих сигналов из множества {Y} в соответствии с ЛУ {X}. Управляющие сигналы yi из множества {Y} инициируют выполнение микроопераций в ОА.

УА - может быть с жесткой логикой и программируемой логикой

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

УА с программируемой логикой - П- автомат - работает медленнее автомата с жесткой логикой, но зато универсален, так как имеет возможность перепрограммирования.

ОА - Операционный автомат. ОА предназначен для выполнения всего множества операций (арифметических и логических), определяемым множеством G(g1, g2, … ,gn), т. е. системой команд процессора. ОА формирует осведомительные сигналы (xi принадлежащих X) о состоянии внутренней памяти {S}, которая определяет последовательность выполнения микроопераций.

ОА по принципу построения можно разделить на E-автомат и M-автомат:

I-автомат - каждому внутреннему слову назначается элемент памяти, он связан со своей комбинационной схемой, на которой проводятся вычисления, вычисления связаны только с этим словом. Для каждого элемента памяти имеется отдельная КС формирования осведомительных сигналов. Есть возможность параллельное обработки слов. Минусы - большое число операционных элементов. Имеется явление простоя оборудования.

M-автомат - в структуре все КС сведены в одну общую схему, что позволяет минимизировать аппаратный затраты. Общая комбинационная схема доступна для всех слов и её выход связан со всеми словами. Выполнение одной операции в единицу времени. М автомат с точки зрения затрат оборудования (не скорости!) более эффективен чем I-автомат.

Т. о. М автомат проигрывает по быстродействию, но имеет экономию в оборудовании. Учитывая свойства I и M автомата используется автомат IM - т.е. с учетом структуры и I и M автомата.

Си - Синхросигнал (синхронизация) - определяет моменты переключений управляющего автомата.

{X} - внутренние осведомительные сигналы.

{G} - множество кодов операций (КОП).

{D} - множество входных данных.

{R} - множество результатов.

Структуры ЭВМ

Достоинства и недостатки архитектуры вычислительных машин и систем изначально зависят от способа соединения компонентов.

В настоящее время примерно одинаковое распространение получили два способа построения вычислительных машин: с непосредственными связями и на основе шины.

1) Структура с непосредственными связями:

Рис.

Здесь:

ПУ - периферийное устройство, осуществляющее ввод - вывод информации.

Порт - буферное устройство, предназначенное для временного хранения данных и для согласования временных (частота работы) и электрических характеристик (уровни напряжения логического «0» или «1») связываемых устройств.

УУ - устройство управления - организует взаимодействие устройств при выполнении программы.

АЛУ - выполняет логические и арифметические операции.

Особенности структуры

Каждое из устройств связано собственным интерфейсом с ядром ЭВМ, имеет собственную разрядность шин: ШД (шина данных) ША (шина адреса) и ШУ (шина управления), т. е. Плюсы: структура наиболее оптимальна и недорога.

Минусы структуры

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

Узким местом является ОП, через которую производятся все пересылки информации, быстродействие ОП определяется производительность ЭВМ.

2). Структура с общей шиной

Рис.

Здесь:

КПДП - контроллер прямого доступа к памяти (ПДП или по англ. DMA)

Интерфейсы общей шины ISA, PCI.

Все устройства ЭВМ связаны единой шиной, на шине в конкретный момент времени могут взаимодействовать только два устройства: ведомое и ведущее.

Общая шина является единым ресурсов для всех устройств, шина выделяется арбитром наиболее приоритетному из устройств.

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

Информация передается блоками.

Плюсы:

Универсальность (с т. з. подключения внешних устройств) и низкая стоимость.

Высвобождение процессора от ввода-вывода.

Минусы:

Пропускная способность общей шины ограничивает производительность ЭВМ

Ограничение на число подключенных внешних устройств.

Чипсет - набор микросхем обрамляющих процессор.

Основные компоненты, установленные на системной плате:

1) Центральный процессор.

2). Набор системной логики (англ. chipset) -- набор микросхем, обеспечивающих подключение ЦПУ к ОЗУ и контроллерам периферийных устройств. Как правило, современные наборы системной логики строятся на базе двух СБИС: «северного» и «южного мостов»:

а).Северный мост (англ. Northbridge), MCH (Memory controller hub), системный контроллер -- обеспечивает подключение ЦПУ к узлам, использующим высокопроизводительные шины: ОЗУ, графический контроллер.

б). Южный мост (англ. Southbridge), ICH (I/O controller hub), периферийный контроллер -- содержит контроллеры периферийных устройств (жёсткого диска, Ethernet, аудио), контроллеры шин для подключения периферийных устройств (шины PCI, PCI-Express и USB), а также контроллеры шин, к которым подключаются устройства, не требующие высокой пропускной способности (LPC -- используется для подключения загрузочного ПЗУ; также шина LPC используется для подключения мультиконтроллера (англ. Super I/O) -- микросхемы, обеспечивающей поддержку «устаревших» низкопроизводительных интерфейсов передачи данных: последовательного и параллельного интерфейсов, контроллера клавиатуры и мыши).

Назначение и структура процессора

Процессор - операционное устройство, осуществляющее процесс обработки данных и программное управление этим процессом.

Функции процессора:

1. Выбор команды из оперативной памяти.

2. Декодирование команды с определением типа действия и способа адресации.

3. Формирование исполнительных адресов операндов и их чтение.

4. Инициирование работы устройств ввода/вывода

5. Прием и обработка запросов на прерывание от устройств ЭВМ, из внешней среды и от выполняемых программ.

6. Контроль и диагностика устройств ЭВМ (контроль - проверка работоспособности элемента ЭВМ; диагностика - определение местоположения неисправного устройства).

Структурная схема процессора:

Рис.

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

УУ- устройство управления, организует контроль и диагностику устройств ЭВМ, организует цикл выполнения команды.

РП - регистровая память (регистровый файл). Предназначен для хранения исходных и промежуточных данных

АЛУ предназначено для выполнения арифметических и логических операций.

АКК - математический сопроцессор (для выполнения операций с плавающей запятой)

МУУ - местное устройство управления, организует операции в АЛУ

ОП - оперативная память, предназначена для хранение программ и данных

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

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

СчАК (IP) - хранит адрес следующей команды, адрес первой команды задается принудительно.

Такты работы (в ромбиках на рисунке показаны пункты тактов):

1) С ПУ задается адрес первой команды принудительно в СчАК.

2,3) По адресу, содержащемуся в СчАК, из ОП считывается первая команда и заносится в РК.

4) Анализируется КОП в УУ.

5,6) Чтение первого операнда в АЛУ.

7,8) Чтение второго операнда в АЛУ.

9) Выполнение операции над операндами в АЛУ.

10) Запись результата в первый операнд

11) Наращивание СЧАК на величину, пропорциональную длине команды. При выполнении команд перехода в СЧАК заносится адрес точки перехода.

Конвейер команд. Виды конфликтов в конвейере команд. Суперконвейрная обработка

Существует два способа повышения производительности процессора:

1) Повышение тактовой частоты работы (достигнут предел в размере около 4 ГГц, ограничение происходит из-за того, что ограничена скорость переключения схем и площадь логического элемента, логический элемент нельзя бесконечно уменьшать в точку)

2) Распараллелить процессы.

Цикл команды можно разбить на несколько этапов: ВК, ДК, ВА, ВО, ИК, ЗК (расшифровка ниже). Если каждый этап будет выполняться отдельным функциональным блоком, то при присоединении их в цепочку получим конвейер команд.

1956 г. акад. Лебедев занимался проблемами по параллельному вычислению.

Этапы команды:

1. Выборка команды (ВК). Чтение команды из памяти и запись ее в РК.

2. Декодирование команды (ДК). Определение КОП и способов адресации операндов.

3. Вычисление адресов операндов (ВА). Вычисление исполнительных адресов операндов в соответствии со способом адресации.

4. Выборка операндов (ВО). Чтение операндов из памяти.

5. Исполнение команды (ИК).

6. Запись результата (ЗР).

Далее рассматривается метрики по преимуществу параллельных вычислений на конвейере над последовательными:

Пусть:

N=9 - число команд, которые требуется выполнить;

К=6 - число ступеней конвейера;

T - время одного такта работы конвейера.

Без конвейеризации время выполнения: Т_бк=K*N*Т =9*6*Т=54*Т

С конвейеризацией: Т_ск=(К+(N-1))*Т=14*Т

1). Ускорение (отношение времени обработки без конвейера ко времени обработки с конвейером), равно:

2). Эффективность доли ускорения на одну ступень конвейера:

E = = = = 4/6 = 0,66; при N >? E>1, т. е. 100% эффективность

3). Пропускная способность или производительность

P= = ; при N >? , P >=F, т.е частота одного такта.

Диаграмма работы конвейера 1,2,3..- такты работы (цветом помечен структурный конфликт):

Таблица

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Команда1

ВК

ДК

ВА

ВО

ИК

ЗР

Команда2

ВК

ДК

ВА

ВО

ИК

ЗР

Команда3

ВК

ДК

ВА

ВО

ИК

ЗР

Команда4

ВК

ДК

ВА

ВО

ИК

ЗР

Команда5

ВК

ДК

ВА

ВО

ИК

ЗР

Команда6

ВК

ДК

ВА

ВО

ИК

ЗР

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

Команда9

ВК

ДК

ВА

ВО

ИК

ЗР

Конфликты в конвейере команд

Посчитанное выше ускорение на 4 единицы - теоретическое значение, т. к. на практике в конвейере возникают конфликты (риски).

Виды рисков:

1). Структурный, когда две или более команды обращаются к одному и тому же ресурсу (например, к памяти).

Способ борьбы с конфликтом:

а). Для исключения структурного риска, память строится по Гарвардской архитектуре (раздельная память данных и команд или раздельный КЭШ данных и КЭШ команд), вдобавок используется многопортовая память.

2). Риск по данным. Возникает при взаимосвязи команд по данным в случаях:

а). Чтение после записи: команда j читает переменную x до того, как команда i успела записать новое значение x, т. е. j ошибочно получает старое значение вместо нового.

б). Запись после чтения: команда j записывает новое значение x до того, как i успела прочитать x, т. е. команда j ошибочно получает новое значение вместо старого.

в). Запись после записи: команда j записывает новое значение x до команды i, т. е. x содержит ошибочно значение i вместо j.

Способ борьбы с конфликтом:

i). Программный. Оптимизирующий компилятор пытается создать такой объектный код, чтобы между конфликтующими командами находились нейтральные команды. Если это не удается, то между конфликтующими командами вставляется команда NOP.

ii). Аппаратный. j задерживается пока не завершится i.

3). Риск по управлению. Возникает из-за неоднородности выбора очередной команды при выполнении команд перехода. Т. е. возникает при выполнении команд условных и безусловных переходов. Вероятность конфликта10-20%.

При выполнении команды безусловного перехода точка перехода становится известна после 2-го этапа выполнения команды (ДК дешифрация команды). При этом загруженные в конвейер последующие команды необходимо сбросить и загрузить в конвейер команду из точки перехода, исход команды становится известен после 5-го этапа (ИК исполнение команды). Если переход должен произойти, то последующие команды сбрасываются из конвейера и загружается команда из точки перехода. (Методы решения вопрос №6)

Суперконвейерная обработка - 1988 год

Эффективность конвейера зависит от частоты подачи на его вход данных для обработки. Для n-кратного увеличения темпа работы конвейера:

1. Можно разбить каждую ступень конвейера на n-подступеней с повышением тактовой частоты в n-раз - суперконвейеризация.

2. Включить в состав процессора n - конвейеров, работающих с перекрытием.

Реализация операций каждой подступени (1-ый способ) производится более простыми аппаратными средствами. К суперконвейерным относятся процессоры у которых число ступеней больше 6.

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

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

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

Диаграмма работы суперконвейера

Таблица

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

6. Методы решения проблемы условного перехода (УП).

Существуют методы решения проблемы условного перехода:

1). Буферы предвыборки

2). Множественные потоки

3). Предсказание переходов

1). Буферы предвыборки

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

Для борьбы с конфликтами по управлению (виды конфликтов рассматривались в вопросе №5) используют 2 буфера:

Рис.

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

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

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

Недостатки: Помимо необходимости дублирования части оборудования, у метода имеется еще один недостаток. Так, если в потоке команд несколько команд УП следуют

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

2). Множественные потоки.

Другим решением проблемы переходов служит дублирование начальных

ступеней конвейера и создание тем самым двух параллельных потоков команд:

Рис.

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

После исхода команды УП к оставшейся части конвейера подключается нужный конвейер.

Недостатки: Основной недостаток метода состоит в том, что на конвейер или в поток может поступить новая команда УП до того, как будет принято окончательное решение по текущей команде перехода. Каждая такая команда требует дополнительного потока.

Т. е. недостатки аналогичны со случаем буфера предвыборки.

3). Предсказание переходов.

До момента выполнения команды УП или при поступлении её на конвейер делается предположение о наиболее вероятном исходе этой команды. Последние команды на конвейер подаются в соответствии с предсказанием. При ошибочном предсказании сбрасывается с последующей загрузкой, начиная с нужной точки. Для того чтобы снижение производительности конвейера не превышало 10%, необходимо, чтобы точность предсказания была не ниже 97,7%.

Различают 2 вида предсказаний:

а). Статическое

б). Динамическое

а). Статическое предсказание переходов:

Статическое предсказание переходов осуществляется на основе априорной (не зависимой от опыта) информации о выполняемой программе. Предсказание выполняется на этапе компиляции программы и в процессе вычисления не меняется.

Стратегии статического предсказания переходов:

1). Переход всегда (ПВ), точность предсказания 53% (фирмы Mips, Sun-Spark, I486)

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

2). Переход никогда (ПН), 47% (Motorolla)

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

Для стратегий 1). и 2). точность предсказания определяется типом данных:



3). По профилированию, 75% (Mips, PowerPC)

Программа выполняется на эталонных данных с накоплением статистики переходов: ПВ и ПН. Стратегия прописывается в разряд поля КОП.

Недостатки: измененный набор данных может существенно влиять на результаты выполнения одних и тех же команд УП.

4). На основе КОП команд УП, 86, 7%

ПВ это условия типа <0, =, >=

ПН это условия типа переполнение, != и др.

5). Предсказание исходя из направления перехода, 80,2% (Spark, HP)

Если адрес точки перехода меньше адреса текущей команды (признак цикла), то такой команде назначается ПВ, иначе ПН.

6). При первом выполнении переход происходит всегда 90,4%

Дальнейшее предсказание зависит от правильности начального предсказания.

Недостаток: для больших программ сложно реализовать, так как необходимо отслеживать большое число ОП.

б). Динамическое предсказание переходов:

Точность предсказания, при динамической схеме предсказания переходов 92-97%

В динамических стратегиях решение о вероятностном исходе команды УП принимается в ходе вычисления исходя из накопленной истории переходов (постприорно) команд УП, которые копятся в процессе выполнения программы.

История переходов фиксируется в таблице: PTH- Pattern History Table - таблица историй для шаблонов.

Элементами, запоминающим историю могут быть (m- разрядность запоминающего устройства):

1). m=1. Автомат Мура.

Имеется всего два сoстояния: 1. переход будет и 2. переход не будет. Если переход был, то автомат переходит в состояние 1. ,если не было то в 2.

2). m=2. Автомат на базе регистра сдвига. После выполнения команды УП содержимое в таблице PTH для этой команды сдвигается влево на 1 разряд, в освободившуюся таблицу заносится 1, если был переход или 0, если нет. Если в элементе PTH (регистры сдвига) есть хотя бы 1 единица, то при выполнении команды УП делается предсказание, что переход будет. Элемент таблицы 2-х разрядный (m=2). Используется в микропроцессорах HP PA-8000. Элемент PHT это регистр сдвига RG(1:2).

Диаграмма работы:

Рис.

3). m=2. На базе реверсивного счетчика (далее Сч), работающего в режиме с насыщением (при комбинации 00 «-1» не производится, при 11 «+1» не производится)

После выполнения УП, если она завершилась переходом, Сч+1, если перехода не было Сч-1. для предсказания используется старший разряд счетчика. Если он равен 1, то предсказание, что переход будет, иначе не будет.

Диаграмма работы:

Рис.

При нарастании числа разрядов счетчика точность предсказания практически не меняется, а затем начинает снижаться (2-3 разряда счетчика оптимально)

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

В качестве шаблонов для доступа к РНТ могут быть взяты:

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

2) регистр глобальной истории GHR; кодовая комбинация в GHR отражает историю выполнения всех последних команд условного перехода.

Идея: Между исходами команд условного перехода в программе существует известная взаимосвязь, учет дает возможность повысить долю правильных предсказаний. Эта идея реализуется схемой с регистром глобальной истории. GHR реализуется как n-разрядный сдвиговый регистр.

3) регистр локальной истории LHR. Как и в схеме с адресом команды перехода, каждый счетчик в РНТ фиксирует историю исхода только одной команды УП, но базируясь на более детальных знаниях, отражающих к тому же и последовательность исходов. В схемах предсказания с LHR присутствует так называемая таблица локальной истории, представляющая собой массив регистров локальной истории.

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

CISC и RISC архитектуры

CISC - Complete instruction set computer. Архитектура с полным набором команд.

До середины 80х годов все процессоры имели архитектуру с полным набором команд.

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

Недостатки CISC:

1. Сложно организовать эффективный конвейер ввиду различных длин команд.

2. реализация сложных команд требуют увеличения управляющей памяти в П-автомате.

3. микропрограммы сложных команд занимают до 60% ПМК (которую приходится увеличивать), при этом их доля в программах примерно 0,2%.

4. на операции вызова процедур и возврата требуется 15-45% вычислительной нагрузки.

5. большая часть операций сводится к операциям присваивания.

RISC - Reduced instruction set computer. Архитектура с сокращенным набором команд.

1980г Дэвид Паттерсон и Карло Сэквин.

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

Для сокращения времени выборки операндов надо, чтобы они хранились не в ОП, а в регистровой памяти.

Особенности RISC:

1. выполнение всех команд за 1 цикл 9кроме команд обращения к ОП).

2. стандартная однословная длина всех команд, определяется разрядностью шины данных.

3. малое число команд <128.

4. малое число форматов команд - до 4.

5. малое число способов адресации - до 4.

6. доступ к памяти только с помощью команд LOAD/SAVE.

7. УУ - автомат с жесткой логикой.

8. большое число регистров - регистровый файл.

9. операции возможны только с операндами, которые расположены в регистровой памяти. Для оптимизации использования регистров RISC применяют программные и аппаратные способы. Программная оптимизация: компилятор выделяет каждой переменной виртуальный регистр, число которых ограничено, затем виртуальные регистры отображаются на ограниченное число физических регистров. Виртуальные регистры, использование которых не перекрывается, отображаются на один и тот же физический регистр. Если во фрагменте программы физических регистров недостаточно, то их роль выполняют ячейки памяти. Задача оптимизации заключается в определении каким переменным в данной точке программы выгоднее выделить физический регистры. Применяется метод «раскраски графа». {Суть: имеется граф, необходимо раскрасить узлы так, чтобы соседние имели разный цвет и общее число цветов было минимальным. Роль узлов выполняют виртуальные регистры, если два виртуальных регистра одновременно применяются в одном фрагменте программы, то они соединяются ребром. Производится раскраска в n цветов. Узлы которые не раскрасились, отображаются на ячейки памяти. Аппаратная оптимизация: позволяет сократить временные задержки при работе с процедурами, т.к. наибольшее время в программах на ЯВУ расходуется на вызовы и возвраты из процедур, что связано с пересылкой большого числа переменных. Используются регистровые окна, упрощающие передачу параметров в подпрограмму. Регистровый файл разбивается на группы регистров, которые называются окнами. Каждой процедуре выделяется отдельное окно в регистровом файле. Все окна имеют одинаковый размер и состоят из трех полей. Левое поле каждого регистрового окна одновременно является правым полем предшествующего ему окна. А среднее поле служит для хранения локальных переменных.



Рис.

Каждой вызванной процедуре выделяется окно непосредственно следующее за окном вызвавшей ее процедуры. Последние k регистров поля j одновременно являются правыми k регистрами окна j+1. Если процедура, занимающая окно j обращается к процедуре, которой должно быть назначено окно j+1, то она может передать при вызове k аргументов. Т.е. k регистров сразу доступны вызванной процедуре безо всяких пересылок.

Эти самые k общих регистров называю регистрами параметров.

Преимущества и недостатки RISC:

+ Одинаковая длина команд упрощает построение конвейера.

+ Унификация команд позволяет реализовать конвейер без организации простоев.

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

+ Упрощенное УУ уменьшает стоимость, повышает надежность, занимает меньше времени на разработку.

+ Большое число регистров ускоряет выполнение арифметических и логических операций за счет исключения обращения к ОП.

+Использование регистровых окон ускоряет передаче параметров.

- Сокращение числа команд приводит к увеличению размера программы при реализации того же алгоритма (~на 30% по сравнению с CISC). Это в свою очередь увеличивает трафик между памятью и процессорм.

- Большой регистровый файл усложняет декодирование, увеличивается время доступа к регистрам

- Устройство с жесткой логикой не гибко. При внесении изменений надо переделывать всю схему.

- Короткие команды усложняют обращение к большому адресному пространству. Исключается прямая адресация (за исключением регистров).

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

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

Структура проца:

Рис.

Блок выборки извлекает команды из ОП через кэш команд

Блок декодирования расшифровывает операцию, определяет адресации.

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

Блок исполнения содержит необходимые функциональные блоки.

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

Для параллельного выполнения 2х скалярных команд необходимо 2 параллельно работающих конвейера команд.

Рис.

Одновременно выбираются 2 команды и в стадии выполнения они распределяются по функциональным блокам.

Таблица

	1	2	3	4	5	6	7	8	9
Команда 1	ВК	ДК	ВА	ВО	ИК	ЗР
Команда 2	ВК	ДК	ВА	ВО	ИК	ЗР
Команда 3		ВК	ДК	ВА	ВО	ИК	ЗР
Команда 4		ВК	ДК	ВА	ВО	ИК	ЗР
Команда 5			ВК	ДК	ВА	ВО	ИК	ЗР
Команда 6			ВК	ДК	ВА	ВО	ИК	ЗР
Команда 7				ВК	ДК	ВА	ВО	ИК	ЗР
Команда 7				ВК	ДК	ВА	ВО	ИК	ЗР

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

Стратегии выдачи и завершений команд:

1. упор выдача, упор завершение

2. упорядоченная выдача, неупорядоченное завершение

3. неупорядоченная выдача, неупорядоченное завершение

Пусть есть проц, который одновременно выбирает 2 команды, имеет 3 функциональных блока и 2 устройства записи результата. Команды

I1 - требует двух тактов работы проца

I3, I4 - конфликт по функциональному блоку

I5 - зависит от результата I4

I5, I6 - конфликт по функциональному блоку

1. упорядоченная выдача, упорядоченное завершение

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

Таблица

Цикл	ДК	ИК	ЗР
1	I1	I2
2	I3	I4	I1	I2
3	I3	I4	I1
4		I4			I3	I1	I2
5	I5	I6			I4
6		I6		I5		I3	I4
7				I6
8						I5	I4

Проводится одновременно выборка и декодирование 2х команд. Чтобы принять очередные команды проц должен ожидать, пока освободится обе части ступени декодирования. Для упорядоченного завершения выдача команд приостанавливается, если есть конфликт по функ. Блоку или для выполнения команды требуется больше одного такта проца. Для 6 команд потребовалось 8 единиц времени.

2. упорядоченная выдача, неупорядоченное завершение

Таблица

Цикл	ДК	ИК	ЗР
1	I1	I2
2	I3	I4	I1	I2
3		I4	I1		I3	I2
4	I5	I6			I4	I1	I3
5		I6			I5	I4
6					I6	I5
7						I6

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

3. неупорядоченная выдача, неупорядоченное завершение

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

Таблица

Цикл	ДК	Окно	ИК	ЗР
1	I1	I2
2	I3	I4	I1, I2	I1	I2
3	I5	I6	I3, I4	I1		I3	I2
4			I4, I5,I6		I5	I4	I1	I3
5			I5		I6		I4	I6
6							I5

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

В каждом цикле проца две команды ступени декодирования пересылаются в окно команд. Команда I6 при данной стратегии может быть выполнена раньше чем I5.

Память ЭВМ. Общие сведения и классификация. Иерархия ЗУ. Виды внутренней памяти ЭВМ

Память ЭВМ

Под памятью ЭВМ понимают совокупность всех запоминающих устройств, предназначенных для приема, хранения и выдачи информации. Характеристики памяти:

1. Место расположения.

- Процессорная (регистровый файл, кэш Л1);

- Внутренняя (память на системной плате: ОЗУ, ПЗУ);

- Внешняя (НМД, НМЛ, CD, магнитооптические диски);

2. Емкость - определяется максимальным количеством информации, которая может быть сохранена в памяти. Е_ПАМ=2^К, к - разрядность шины адреса.

3. Единица пересылки. Для ОЗУ определяется шириной шины данных. Для внешней памяти единица пересылки - блок (4, 8, 16 кб).

4. Место доступа.

- Последовательный доступ. Информация в таких ЗУ хранится в виде записи. Время доступа определяется местоположением требуемой записи на носителе (НМЛ).

- Прямой доступ. Каждая запись имеет уникальный адрес. Обращение производится как адресный доступ к началу записи с последующим последовательным доступом к нужной единице информации внутри записи. Время доступа переменное (НМД).

- Произвольный доступ. Каждая ячейка имеет уникальный адрес. Обращение к любой ячейке занимает одинаковое время и может производится в любой очередности (ОЗУ).

- Ассоциативный доступ (КЭШ). Вид доступа позволяет выполнять поиск ячеек, информация в которых совпадает с заданным образцом. Сравнение осуществляется одновременно для всех ячеек памяти.

5. Быстродействие.

- Время доступа (для памяти с произвольным доступом - это время от момента поступления адреса до момента доступности данных, в ЗУ с подвижными носителями время определяется временем установки носителя в нужную позицию)

- Длительность цикла памяти (период обращения). Применяется для памяти с произвольным доступом - минимальное время между двумя последовательными обращениями к памяти.

- Скорость передачи. Скорость, с которой данные могут передаваться. Для памяти с произвольным доступом 1/Т_Ц. Для другой памяти Т_N=Т_Д+N/R, где Т_N - среднее время считывания или записи N битов, Т_Д - среднее время доступа, N/R - скорость пересылки битов в секунду.

6. Физический тип.

- Полупроводниковая (ОЗУ, ПЗУ)

- Магнитная (винчестер, НМД)

- Оптическая (CD-ROM)

7. Физические особенности

- Энергозависимая (ПЗУ)

- Энергонезависимая

8. Удельная стоимость [бит/руб]

Иерархия ЗУ.

Иерархическая структура памяти предназначена для повышения производительности системы памяти. Производительность процессоров увеличивается в 2 раза за 2 года, а производительность памяти увеличивается в 2 раза в среднем за 10 лет. Иерархическая организация основана на принципе локальности. Существует 3 вида локальности:

1. Локальность программ (команды в программе выполняются последовательно друг за другом. Можно выделить линейные участки выполнения программы).

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

3. Временная локальность (Она возникает при выполнении циклов).

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

Рис.

Фактическая память ЭВМ не ограничена. Особенность иерархии: каждый уровень связан только с соседним. Сверху вниз увеличивается емкость, снизу вверх увеличивается быстродействие. При движении сверху вниз уменьшается частота обращения к памяти со стороны процессора. Увеличивается время доступа. Иерархическая организация памяти приводит к уменьшению стоимости памяти при заданном уровне производительности. При доступе к памяти со стороны процессора поиск информации производится первоначально в памяти верхнего уровня. Наличие информации характеризуется попаданием hit, а если промах miss. При промахе производится поиск в памяти более низкого уровня при построении иерархической памяти используют характеристики: коэффициент попадания (hitrate), коэффициент промахов. Время обращения при попадании - время необходимое для поиска в памяти верхнего уровня при попадании. Потери на промах - время, требуемое для замены блоков в памяти более высокого уровня на блок с нужными данными из памяти более низкого уровня. Потери на промах включают время на замещение блока - время выбора блока в памяти более высокого уровня, который будет замещаться. При замещении блоков возникает проблема согласования в памяти соседних уровней (когерентность, синхронизация) - при записи новой информации на более высоком уровне.

Организация внутренней памяти ЭВМ

Любое ЗУ содержит запоминающий массив ЗМ. Одна ячейка хранит одновременно одно слово памяти и определяет понятие ширины выборки. Способ организации памяти зависит от метода размещения информации в ЗМ и правило ее чтения и записи. Различают 3 вида внутренней памяти:

1. Адресная память (ОЗУ, СОЗУ, ПЗУ, РП)

2. Стековая память

3. Ассоциативная память.

Адресная память.

ЗМ[1..N](1..n)



Рис.

Особенность адресной памяти. Размещение и поиск информации основаны на использовании идентификатора адреса.

БАВ - блок адресной выборки (дешифратор).

РС - регистр слова.

БУС - блок управления считывания.

Расслоение памяти

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

ШД (0:63) - то можно организовать имея две микросхемы 32к х 32.

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

Банк памяти - микросхема меньшей разрядности чем ШД.

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

Стековая память

Доступ к информации организован по дисциплине LIFO (Last input first output). Поэтому его называют памятью магазинного типа. Применение стека: 1) Для хранения интерпретируемых программ (Basic). 2) Для сохранения контекста программ при организации прерываний. Контекст программ - содержимое IP, IF (флага), регистров общего назначения (РОН). 3) Вычисления арифметических выражений с применением польской инверсной записи (ПОЛИЗ)(Пример ПОЛИЗ: y=ab((c+d)/ef-h): Запись в ПОЛИЗ: ab*cd+ef*/h-*>y). 4) Для хранения последовательных элементов данных.

Стеки различают: аппаратный и аппаратно-программный. Аппаратный стек - совокупность n-разрядных регистров, связанных между собой цепями переноса. Достоинство: высокое быстродействие. Недостаток: малый объем (10 регистров).



Рис.

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

Для записи подается сигнал «ЗП». Производится уменьшение на 1 указателя стека, затем через задержку записывается слово в ячейку М. При чтении читается содержимое ячейки М, затем через задержку увеличивается SP на 1 (Команды ЗП А, В, С и ЧТ С, В, А).

Рис.

Ассоциативное запоминающее устройство

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

Рис.

«0» - определяет наличие искомой информации и ее местоположение в АЗУ. Поиски разделяют на сложные и простые. При простом поиске все биты в искомом слове совпадают с битами признака. Если при поиске в слове некоторые разряды могут игнорироваться (маскироваться), то он называется сложным.

Кэш-память ЭВМ. Способы отображения ОП на Кэш память. Алгоритмы замещения информации в Кэш памяти. Алгоритмы согласования Кэш и ОП

Кэш-память

Применение кэш-памяти основано на принципе локальности. При этом кэш-память имеет сравнимые характеристики по быстродействию с процессором, но имеет небольшой объем.



Рис.

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