Ресурсные и информационные конфликты в конвейерных системах

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ  УНИВЕРСИТЕТ)

 

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

по дисциплине

«Моделирование ЭВМ»

тема

«Ресурсные и информационные конфликты в конвейерных системах»

 

 

 

 

 

 

 

Выполнила

Студентка

гр. 03-419

Фурсенко В.В.

Работу приняла

Звонарева Г. А.

 

 

 

 

 

 

 

 

 

 

 

 

Москва, 2012

 

Оглавление

 

Теоретический материал 4

Конвейерная организация 4

Информационные и ресурсные конфликты 7

Организация памяти 10

Признаковый обмен и сквозная запись 13

Блоки GENERATE и TERMINATE 14

Блок ADVANCE 15

Блоки SEIZE и RELEASE 16

Блок TRANSFER 16

Блок LOGIC 17

Блок GATE 18

Задание для лабораторной работы 18

Пример выполнения задания 22

Описание используемых в модели обозначений 22

Описание модели 23

Блок-схема модели конвейерной ВС 25

Текст программы-модели конвейерной ВС 28

Выбор времени моделирования 30

Отладка модели 31

Тест 1 31

Тест 2 35

Тест 3 45

Тест 4 54

Анализ результатов моделирования 68

Анализ  влияния длины I-очереди на производительность модели 68

Анализ  влияния количества РАО и РДО  на производительность модели 69

Анализ влияния ширины выборки из кэш-памяти на производительность модели 70

Анализ  влияния формата команд на производительность модели 72

Анализ простоя логики декодирования при загруженной I-очереди 73

Варианты заданий для студентов 75

Вариант 1 75

Вариант 2 75

Вариант 3 75

Вариант 4 75

Вариант 5 76

Вариант 6 76

Вариант 7 76

Вариант 8 76

Вариант 9 77

Вариант 10 77

Список используемой литературы 77

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теоретический материал

Конвейерная организация

 

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

Конвейеры можно классифицировать по двум типам: линейность и статичность^[1]. Если при выполнении одной команды каждый сегмент конвейера используется один раз, то такой конвейер линейный. В противном случае, если в процессе выполнения команды есть повторение работы сегмента, то конвейер является не линейным. В конвейере порядок прохождения сегментов может отличаться, в зависимости от той команды, которая поступила на обработку. Такой конвейер будет динамическим. Если же для всех команд один порядок, то конвейер статический.

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

Использование ресурсов конвейера на каждом шаге задается с помощью таблицы занятости  ресурсов^[1]. Она представляет собой таблицу, где по вертикали идут номера сегментов, а по горизонтали такты работы конвейера.

Используя таблицу занятости можно по-другому  определить классификацию конвейера по статичности. Так, статичный конвейер – это конвейер, у которого все команды имеют одинаковую таблицу занятости^[1]. Если же, конвейер выполняет команды с различными таблицами занятости, то он динамический.

 

 

 

 

 

Допустим, что в конвейер  загружена команда  типа «B», и требуется понять, в каком такте можно будет загружать в конвейер такую же команду.

 

  Чтобы это сделать используется  начальный вектор столкновений (НВС). Он характеризует конфликтность  2х команд, которые могли бы  быть введены в конвейер. Это двоичный вектор и он строится путем наложения одной команды на другую. Если во время наложения где-то произошло совпадение требуемых ресурсов, значит, вводит новую команду в этот такт нельзя, и в вектор ставиться 1 на месте соответствующем текущему такту. После этого таблица вводимой команды смещается на один такт и заново проверяется возможность её ввода в конвейер^[1].

 

Чтобы просчитать, когда можно будет  вводить третью и последующие команды используют граф состояний. Это объединение НВС. Рассмотрим пример на команде «B»:

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

Ключевым  параметром к определению производительности конвейера является латентность  – число единиц времени, разделяющее  команды одной или нескольких таблиц занятости^[2].

Из  модифицированного графа состояний  наглядно видно, что следующую команду  можно вводить двумя циклами:

• 3,8,3,8…
• 4,4,4,4…

Исходя из этого, можно просчитать среднюю задержку (латентность) конвейера:

• T_ср =
• T_ср =

Начальный вектор столкновений используется только в  статических конвейерах.

Так как в динамическом конвейере  фигурирует две или больше команды, то НВС становиться бесполезным. Вместо него используют матрицу столкновений. Рассмотрим на примере команды двух типов «А» и «B»:

 

Информационные  и ресурсные конфликты

 

Конфликтом  при конвейеризации команд называют ситуацию, которая препятствует выполнению очередной команды из потока команд в предназначенном для нее  такте^[2].

Структурные или ресурсные конфликты возникают  в результате того, что аппаратные средства не могут поддерживать все  комбинации команд в режиме их одновременного выполнения с совмещением на конвейере. Это происходит в случае, если какие-то устройства в процессоре не конвейеризованы, либо – присутствуют в единственном экземпляре (не распараллелены). Например, могут возникать конфликты при  обращении к общей кэш-памяти: одну команду необходимо извлечь  из памяти (на первом этапе выполнения), а другая пытается записать результат  в память на заключительном этапе. Для  борьбы с ресурсными конфликтами  в основном применяют три способа^[2]:

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

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

В неконвейерной машинной структуре все операции, связанные с исполнением отдельной команды, завершаются до запуска следующей команды. Таким образом, очередность соответствует логической очередности. При конвейеризации исполнения команд перекрываются, так что некоторые операции, нужные для команд i+1, i+2,…, могут запускаться и быть выполненными до завершения i-ой команды. Если команды i+1, i+2,… зависят от результатов i-ой команды, то получаются помехи, которые должны быть разрешены. Чаще всего методом разрешения помех служит блокировка^[2].

Помеха  возникает, когда к объекту данных (регистру, ячейке памяти) обращаются или  модифицируют его две различные  команды близко расположенные в  программе. Из-за этого при конвейеризации их исполнение перекрывается. Имеется  три класса таких помех^[1]:

1. Чтение после записи (RAW)
2. Запись после чтения (WAR)
3. Запись после записи (WAW)

 

 

 

 

 

 

Для примера рассмотрим фрагмент программы:

Чтение  после записи между командами  i и j (команда j следует после команды i) возникает, когда команда j пытается читать объект модифицируемый командой i. Если операция в команде i не завершится к тому моменту как команда j обратиться к изменяемому i-ой командой объекту, то команда j получит неправильное значение^[2]. В виде программы это можно записать как:

Запись  после чтения происходит, если команда  j хочет модифицировать некоторый объект, который читается командой i. Если j успевает изменить объект до того как команда i прочтет из него информацию, то i получит неправильное значение^[2]. Этой помехе соответствует фрагмент программы:

Помеха  записи после записи существует, когда  обе команды i и j пытаются обновить данный в одном и том же объекте, но i-ая команда может выполниться после     j-ой. Тогда в результате, после выполнения обоих команд значение ячейки памяти или регистра будет равно значению от команды i^[2]. На примере это выглядит так:

Чтобы разобраться и решить данные помехи вводят два определения:

1. Область определения команды i (D(i)) – это множество всех объектов, содержимое которых влияет на исполнение этой команды.
2. Множество значений команды i (R(i)) – это множество всех объектов, содержимое которых может быть изменено во время выполнения команды i.

Таким образом, D(i) – это множество всех объектов, читаемых командой i, а R(i) – это множество всех объектов, которое изменяется командой i^[2]. Исходя из этих двух определений, можно записать условия возникновения помех:

1. RAW – R(i) ∩ D(j) ≠ Ω
2. WAR – D(i) ∩ R(j) ≠ Ω
3. WAW – R(i) ∩ R(j) ≠ Ω

Здесь ∩ - пересечение двух множеств, а  Ω – пустое множество.

Также эти условия можно представить  в графической форме:

 

 

 

Существует  множество способов и приемов  для обнаружения и устранение помех без нарушения работы машины. В большинстве случаев случаи обнаружение помех можно разделить  на два типа^[2]:

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

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

Также существуют два подхода к устранению помехи, если она обнаружена^[2]:

1. Остановить конвейер, если найдена помеха. Если обнаружена команда j, находящаяся в состоянии помехи с ранее инициированной командой i, то все последующие инициации команд j, j+1, j+2,… останавливаются до тех пор, пока команда i не пройдёт через точку конфликта.
2. Остановить команду j, командам j+1, j+2,… разрешается продвигаться по конвейеру. Это даёт возможность командам j+1, j+2,… обогнать команду j в конвейере. Аналогично при проверках на наличие помех для этих команд нужно предусматривать и сравнения с задержанной командой j. Если здесь обнаруживается помеха, то выполнение этих команд также должно быть отложено до тех пор, пока исходная помеха для команды j не будет устранена, и пока этой команде j не будет разрешено продолжаться.

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

Есть  более быстрое решение – короткое замыкание. При нем копия данных, подлежащих записи, непосредственно  передаётся ожидающей команде чтения, избавляя её от необходимости ждать  завершения команды записи и затем  выполнять ещё одно чтение.

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