Микроархитектурный уровень

Оглавление Блок 1 3 МИКРОАРХИТЕКТУРНЫЙ УРОВЕНЬ 3 ТРАКТ ДАННЫХ 3 РЕГИСТРЫ ТРАКТА ДАННЫХ 4 УСТРОЙСТВО УПРАВЛЕНИЯ (МИКРОПРОГРАММНОЕ) 4 РЕАЛИЗАЦИЯ УСЛОВНЫХ ПЕРЕХОДОВ 5 АРХИТЕКТУРЫ УСТРОЙСТВ УПРАВЛЕНИЯ (ПРОЦЕССОРОВ) 6 МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ 6 ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ДАННЫХ 7 КОНВЕЙЕРИЗАЦИЯ 8 ИЗМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫПОЛНЕНИЯ КОМАНД И ПОДМЕНА РЕГИСТРОВ 9 ПРОБЛЕМА ПЕРЕХОДОВ 10 МЕТОДЫ БОРЬБЫ С УСЛОВНЫМИ ПЕРЕХОДАМИ 11 АРХИТЕКТУРА КОМАНД 12 ОБЗОР УРОВНЯ АРХИТЕКТУРЫ КОМАНД 12 МЕТОДЫ АДРЕСАЦИИ 12 СПОСОБЫ АДРЕСАЦИИ 12 СТЕКОВАЯ АДРЕСАЦИЯ 13 ТИПЫ КОМАНД 13 ТИПЫ ДАННЫХ 13 СТАНДАРТ IEEE 754 ДЛЯ ВЕЩЕСТВЕННЫХ ЧИСЕЛ 14 ДОПОЛНИТЕЛЬНЫЙ КОД 15 ДРОБНЫЕ ЧИСЛА С ФИКСИРОВАННОЙ ЗАПЯТОЙ 15 КОМПЛЕКСНЫЕ ЧИСЛА 15 МОДЕЛИ ПАМЯТИ 15 УРОВЕНЬ ОПЕРАЦИОННОЙ СИСТЕМЫ 17 ОБЗОР 17 ПРОБЛЕМЫ ВИРТУАЛЬНОЙ ПАМЯТИ 17 СТРАНИЧНАЯ ОРГАНИЗАЦИЯ ПАМЯТИ 18 ПРЕРЫВАНИЯ И ИСКЛЮЧЕНИЯ 19 УРОВЕНЬ ЯЗЫКА АССЕМБЛЕРА 20 ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ АССЕМБЛЕР 20 ПРОЦЕСС АССЕМБЛИРОВАНИЯ 20 КОМПОНОВКА МОДУЛЕЙ 21 СВЯЗЬ С БИБЛИОТЕЧНЫМИ ФУНКЦИЯМИ 22 Блок 2 23 АРХИТЕКТУРА ПАМЯТИ 23 ТИПЫ ПАМЯТИ 23 ОРГАНИЗАЦИЯ ПАМЯТИ 24 АРХИТЕКТУРНЫЕ МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ 25 ПАКЕТНЫЙ ДОСТУП К ПАМЯТИ 26 КОНВЕЙЕРНЫЙ ДОСТУП К ПАМЯТИ 27 КЭШ-ПАМЯТЬ 28 СТРАТЕГИЯ РАЗМЕЩЕНИЯ. ПРЯМОЕ РАСПРЕДЕЛЕНИЕ 28 СТРАТЕГИЯ РАЗМЕЩЕНИЯ. АССОЦИАТИВНОЕ РАСПРЕДЕЛЕНИЕ 29 СТРАТЕГИЯ РАЗМЕЩЕНИЯ. НАБОРНО-АССОЦИАТИВНОЕ РАСПРЕДЕЛЕНИЕ 30 СТРАТЕГИИ ОБНОВЛЕНИЯ ОСНОВНОЙ ПАМЯТИ 30 СТРАТЕГИЯ ЗАМЕЩЕНИЯ 31 МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ 32 КЛАССИФИКАЦИЯ КОМПЬЮТЕРОВ ПАРАЛЛЕЛЬНОГО ДЕЙСТВИЯ 32 UMA SMP С ШИННОЙ ОРГАНИЗАЦИЕЙ 33 ПРОТОКОЛ MESI 34 АЛГОРИТМ КОГЕРЕНТНОГО КЭШИРОВАНИЯ SCI 37 Блок 1 МИКРОАРХИТЕКТУРНЫЙ УРОВЕНЬ Микроархитектурный уровень – уровень решения задач, связанных с координацией работ исполнительных элементов (арифметико-логических устройств, регистров и т. п.). ТРАКТ ДАННЫХ Тракт данных представляет собой часть Центрального Процессора (ЦП) Тактовый импульс или синхроимпульс 1 – установка управляющих сигналов(работает устройство управления) 2 – регистры выставляют данные на шины 3 – АЛУ выполняет операцию 4 – сохранение результатов Регистр – элемент, хранящий информацию. При подаче сигнала на правый управляющий вход происходит «выдача» информации из памяти на выход (на шину). При подаче сигнала на левый управляющий вход регистр «запоминает» значение с информационного входа. Регистр N – регистр временного хранения. Каждый из регистров имеет 2 управляющих входа: вход чтения (красная стрелка) и записи (черная стрелка). АЛУ (арифметико-логическое устройство) имеет 2 информационных входа, один выход и управляющие входы (серые стрелки). В зависимости от управляющего сигнала АЛУ может выполнять 1 операцию – сложение, вычитание и т.п. Шины данных – элементы, передающие данные, служат для соединения АЛУ и регистров между собой. Работа тракта данных задается тактовыми импульсами. По заднему фронту тактового импульса начинает работать устройство управления и выставлять сигналы управления (1). На 2 этапе регистр, на который был подан сигнал чтения, выставляет данные на правую шину. После этого на 3 этапе АЛУ выполняет необходимую операцию и на 4 этапе по переднему фронту следующего тактирующего импульса происходит сохранение результата. РЕГИСТРЫ ТРАКТА ДАННЫХ Регистры тракта данных бывают: • общего назначения (например, РгД); • специальные служебные регистры, необходимые для обеспечения работы тракта данных. РгАД – регистр адреса данных РгАК – регистр адреса команд (программный счетчик – хранит адрес текущей команды в ОЗУ) РгД – регистр данных РгК – регистр команд (хранит код команды, который используется для генерации управляющего сигнала) Так же есть дополнительные регистры: флаговый (набор бит, который указывает состояние после операции), указатель стека (указывает на стек) и т.д. Все регистры взаимодействуют с ОЗУ, то есть могут обмениваться информацией с ОЗУ. УСТРОЙСТВО УПРАВЛЕНИЯ (МИКРОПРОГРАММНОЕ) Устройства управления бывают микропрограммные и на основе конечных автоматов (аппаратные). Устройства управления на основе конечных автоматов создаются на основе проектирования конечных автоматов, используя известные входные сигналы (код команды) и сигналы устройства управления. Для выполнения команды (прим, сложение чисел) используется микропрограмма, состоящая из нескольких микрокоманд. Микрокоманда – это набор бит. Часть бит микропрограммы используется для работы Управляющей Памяти. Код команды из РгК считывается в PгAMк, этот код совпадает с адресом первой микрокоманды в программе для выполнения этой команды. Поэтому из УП в РгМк считывается первая микрокоманда (ее код). Большую часть кода микрокоманды составляют биты, соответствующие битам сигнала управления. Если некоторый бит равен 1, то составляется Сигнал Управления, заставляющий АЛУ выполнить определенную операцию, например, сложения. Часть кода микрокоманды составляет адрес следующей микрокоманды, эта часть переписывается в РгАМк, что приводит к выполнению следующей микрокоманды. Последняя микрокоманда в команде поворачивает ключ, что приводит к считыванию следующей команды (микропрограммы). РЕАЛИЗАЦИЯ УСЛОВНЫХ ПЕРЕХОДОВ Выполнение реальных программ требует реализации ветвлений, т.е. в зависимости от результатов выполнения текущей программы должна выполняться та или иная ветвь программы. Условный переход – выполнение той или иной команды в зависимости от условия. Для реализации условных переходов устройства управления используют флаги, выставляемые АЛУ по результатам операции. Адреса микрокоманд, соответствующих разным ветвям микропрограммы, отличаются только одним битом, который зависит от значения флага (0 или 1 – зависит от того, выполнилось условие или нет). Микрокоманда, выполняющая условный переход, подает управляющий сигнал на ключ, по которому соответствующий флаг переписывается в нужную позицию РгАМк. АРХИТЕКТУРЫ УСТРОЙСТВ УПРАВЛЕНИЯ (ПРОЦЕССОРОВ) В зависимости от набора команд выделяют четыре архитектуры УУ: RISC – «уменьшенный набор инструкций» – команд в архитектуре мало, сложность в программировании CISC – «комплексный (большой) набор инструкций» VLIW – «система команд с длинной инструкцией» – позволяет выполнять несколько команд одновременно, параллельно Современные x86 – внешне – CISC-архитектура, внутри – команды архитектуры либо RISC (такие x86 встречаются чаще всего), либо CISC, либо VLIW МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ ОБЗОР К методам повышения производительности относят технологические, схемотехнические и архитектурные методы. Технологические (развитие технологий) – основаны на прогрессе в области изготовления микросхем (нанотехнологии, улучшение свойств материалов) Схемотехнические – основаны на применении более громоздких, но быстрых схем (схемы с параллельным переносом), а также на добавлении новых операций (например, аппаратная реализация умножения и прочее). Архитектурные – основаны на более оптимальном использовании имеющейся технологии (например, применение других комбинаций устройств). Архитектурные методы: 1) параллельная обработка данных; 2) конвейеризация. ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ДАННЫХ Приведенные ниже схемы реально не используются. Add Р1, Р2: 1. РN = R1; 2. Р1=RN+Р1; 3. РгАК=РгАК+1; 4. READ РгАК. Add Р1, Р2: 0. РгАК=РгАК+1; (выполняется на INC) 1. Р1=Р1+Р2, READ РгАК, РгАК=РгАК+1; Идея метода заключается в использовании нескольких исполнительных устройств, которые одновременно выполняют несколько операций. Здесь ускорение работы тракта данных происходит путем добавления к нему дополнительной шины и дополнительного упрощенного АЛУ – инкрементора. Улучшенный тракт данных может одновременно подать значения двух регистров на вход АЛУ и одновременно посчитать адрес следующей команды. Суперскалярные процессоры – процессоры, которые содержат несколько АЛУ и могут выполнять несколько арифметических операций одновременно. КОНВЕЙЕРИЗАЦИЯ III стадия I стадия II стадия I стадия: запись данных в регистры В и С и передача их в АЛУ (выборка операндов) II стадия: выполнение операций в АЛУ, запись результата в регистр А III стадия: сохранение результатов в регистр 1. Такты Add Р1, Р2 Add Р3, Р4 Add Р5, Р6 1 B=Р1, C=Р2 2 A=B+C B=Р3, C=Р4 3 Р1=A A=B+C B=Р5, C=Р6 4 Р3=A A=B+C 5 Р5=A Стадии – это различные части тракта данных, которые при конвейеризации работают параллельно. Таким образом, основная идея конвейеризации заключается в разделении тракта данных на стадии. Повышение производительности достигается за счет того, что на нескольких стадиях могут выполняться параллельно несколько команд. Преимущество конвейеризации: увеличение скорости работы. Недостаток: конвейер может сбиваться. Регистры А, В, С не вносят задержку в работу тракта данных, т.к. не имеют управляющих сигналов и их значения всегда выставлены на шине. По примеру программы можно судить о том, что на данном тракте данных может выполняться одновременно 3 команды. Процессоры, использующие конвейеризацию тракта данных, – конвейеризованные процессоры. ИЗМЕНЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫПОЛНЕНИЯ КОМАНД И ПОДМЕНА РЕГИСТРОВ Для того чтобы избежать остановки и ошибки конвейера, применяют методы изменения последовательности выполнения команд и подмены регистров. 1. Изменение последовательности выполнения команд Программа (ПРОБЛЕМА) Реальный порядок команд (РЕШЕНИЕ ПРОБЛЕМЫ) Р1=Р2+Р3 Р1=Р2+Р3 Р4=Р1+Р5 (используется регистр, значение кот. подсчитывается на предыдущей операции; т.е. конвейер в данном случае может сбиться, ему необходимо ждать окончания 1-й операции) Р6=Р7+Р8 Р6=Р7+Р8 Р4=Р1+Р5 (здесь остановки конвейера для ожидания значения Р1 не потребуется) Причиной сбоя конвейера может являться зависимость операндов текущей команды от результатов предыдущей. В примере программы вторая команда использует значение регистра Р1 и ее выполнение не может начаться до получения результатов 1-й команды. В этом случае процессор может изменить последовательность выполнения команд, начав выполнение последующей команды, если она не зависит от предыдущей. 2. Подмена регистров Программа (ПРОБЛЕМА) Реальный порядок команд и регистры (РЕШЕНИЕ ПРОБЛЕМЫ) Р1=Р2+Р3 Р1=Р2+Р3 Р4=Р1+Р5 Р5’=Р6+Р7 (Р5’ – теневой (временный) регистр) Р5=Р6+Р7 Р4=Р1+Р5 Некая команда Некая команда, Р5=Р5’ При изменении последовательности команд может сложиться такая ситуация, когда нам потребуется записать значение в регистр, первоначальное значение которого требуется для других последующих команд. В этом случае процессор может сохранить значение в теневом регистре, позже переписав его в основной. ПРОБЛЕМА ПЕРЕХОДОВ В конвейеризированных процессорах существует ряд проблем, связанных с одновременным выполнением команд. Одна из таких проблем – проблема условных и безусловных переходов. Безусловный переход (goto, jump) Стадии конвейера 1 Выборка команды Код 1 Код 2 Код 3 ??? Код X Декодирование INC JMP Выборка операндов А X Исполнение A+1 - Сохранение результатов ! В случае если в ходе работы конвейера встречается команда безусловного перехода, выполнение следующей команды откладывается на несколько тактов (конкретно – теряется 2 такта работы процессора), необходимых для декодирования команды безусловного перехода и ожидания адреса следующей команды после перехода. Методов борьбы с безусловными переходами нет. Условный переход Стадии конвейера 1 Выборка команды Код 1 Код 2 Код 3 ??? ??? Код X Декодирование INC JE Выборка операндов А X Исполнение A+1 Сохранение результатов ! В случае команд условных переходов простой конвейера длится большее число тактов (здесь – теряется 3 такта работы процессора). Для получения адреса следующей команды нужно выполнить почти все стадии конвейера. МЕТОДЫ БОРЬБЫ С УСЛОВНЫМИ ПЕРЕХОДАМИ Существует несколько методов борьбы с условными переходами. Можно бороться с условными переходами программными способами, но это сложно и практически не применяется. Поэтому применяют прогнозирование переходов и условное исполнение. 1) ПРОГНОЗИРОВАНИЕ ПЕРЕХОДОВ Динамическое прогнозирование (самый распространенный метод): метод использует вероятности, априорную информацию. Процессор пытается предсказать ветвь, по которой пойдет выполнение программы, и начинает выполнять эту ветвь; если ветвь угадана, то процессор продолжает работу без потери тактов, когда ветвь не угадывается, результаты работы по неправильной ветви отбрасываются, и начинается выполнение правильной ветви. При динамическом прогнозировании ветвь выбирается процессором «на ходу» на основании ранее разработанной статистики о вероятности выполнения ветвей. Статическое прогнозирование: процент правильного прогнозирования выше, чем у динамического; нет большого блока, который управляет проверкой; работает на этапе компиляции или создания программ (программист сам делает); требуется систему определенных команд. При статическом прогнозировании вероятная ветвь выбирается при разработке или компиляции программы и указывается в ходе программы. Двойное исполнение: в случае, если в программе встречается условный переход, начинается выполнение обоих ветвей программы. При вычислении результатов условного перехода неправильная ветвь отбрасывается. Следовательно, этот способ неэффективен, а также требует двух АЛУ. 2) УСЛОВНОЕ ИСПОЛНЕНИЕ (программно-аппаратный способ) Вводятся специальные команды, в зависимости от результата выполнения условия эти команды исполняются или не исполняются. Это особая форма условных переходов, переходов как таковых нет, в зависимости от условия выполняется та или иная определенная команда. АРХИТЕКТУРА КОМАНД ОБЗОР УРОВНЯ АРХИТЕКТУРЫ КОМАНД АРХИТЕКТУРЫ КОМАНД – оболочка для процессора. Промежуточное звено между программой и аппаратным обеспечением. Скрывает детали реализации процессора от программиста. Обеспечивает совместимость новых процессоров с имеющимся ПО. МЕТОДЫ АДРЕСАЦИИ Трехадресная ADD R1, R2, R3 R1 = R2 + R3 Двухадресная ADD R1, R2 R1 = R1 + R2 Одноадресная ADD R1 A = A+R1 Безадресная ADD A = A + B Метод адресации – описывает количество операндов, указываемых для команды. Чем больше операндов, тем менее гибкая адресация. При трехадресной адресации к ходе команды указываются адреса обоих операндов и адрес результата. Такой метод адресации очень гибок, позволяет работать с произвольно расположенными данными. Применяется в RISC-процессорах, в которых операндами могут быть только регистры. Методы адресации с меньшим количеством адресов позволяют упростить процессор, но усложняют его программирование. Двухадресная – менее гибкая, возможно появление промежуточных операций (сумма и вычитание). Плюс данного метода – меньше адресов нужно указывать. Одноадресная – типичный метод адресации при работе с программами. Специальный регистр А (аккумулятор) – регистр с предопределенным адресом, чтобы к нему обратиться не нужно указывать его адрес, процессор и так его знает. Безадресная – работает с аккумуляторами или стеками. СПОСОБЫ АДРЕСАЦИИ Непосредственная MOV R1, 4 Прямая MOV R1, [10] Регистровая MOV R1, R2 Косвенная регистровая MOV R1, [R2] Индексная MOV R1, 10+[R2] Относительная индексная MOV R1, [R2+R3] Способ адресации определяет способ получения операнда. Операнд может быть получен непосредственно из кода команды (непосредственная), по адресу, указанному в коде команды (прямая), из регистра, по адресу, указанному в регистре (регистровая), или с помощью комбинации этих способов (остальные способы). СТЕКОВАЯ АДРЕСАЦИЯ Стек – особый тип памяти, работа с которой может осуществляться с помощью двух операций: поместить на вершину стека и взять из вершины стека. Это простой и легкий в реализации способ работы с памятью, который применяется, когда нужно быстро сохранить небольшое количество данных (например, при вызове функции). ТИПЫ КОМАНД Перемещения данных – перемещают данные между памятью и регистрами. RICS процессоры из памяти данные могут перемещать только в регистры. Арифметические операции – бинарные и унарные. Бинарные операции Арифметические Логические Унарные операции Сдвиги бывают логические, арифметические и циклические. Арифметические и логические Сравнения и условные переходы – необходимы для организации ветвления в программе. Команды сравнения выставляют значения флагов АЛУ. На основании выставленных флагов команды условных переходов выполняют ту или иную ветвь. Смысл: получить условие, а не результат. Вызова процедур – сохраняет состояние процессора и запоминает значения счетчика команд, команды возврата из процедуры восстанавливает эти значения. Управления циклом – изменяет значения счетчика цикла, анализирует условия окончания цикла и выполнение условия. Ввода-вывода – разделяет команды на работу с памятью и внешними устройствами ввода. ТИПЫ ДАННЫХ Числовые Целые Вещественные Комплексные Нечисловые Символьные (ASCII, UNICODE) – символ кодируется 7 битами,8-ой запасной или не используется. UNICODE: 1 символ – 16 бит программы. Логические (булевые) – 0 и 1. все что не ноль – истина. Указатели и массивы. Указатели – тип данных, показывающий адрес в памяти. Битовые – набор флагов. Работа с нечисловыми данными реализуется программами. СТАНДАРТ IEEE 754 ДЛЯ ВЕЩЕСТВЕННЫХ ЧИСЕЛ 1010*24 – двоичная система счисления. 1010 – мантисса 24 – экспонента Если степень двойки ≤127, нули подписываются перед мантиссой и получается число меньше 1. Первая единица в мантиссе не хранится, но она есть всегда. ДОПОЛНИТЕЛЬНЫЙ КОД 510 = 0000 01012 -510 = 1111 10112 Сумма равна нулю в любом представлении. Получить отрицательное число можно, заменив все нули на единицы и в конец прибавить 1. ДРОБНЫЕ ЧИСЛА С ФИКСИРОВАННОЙ ЗАПЯТОЙ 510 = 0000 01012 410 = 0000 01002 2010 = 0001 01002 1/410 = 0.010 00002 1/810 = 0.001 00002 1/3210 = 0.000 01002 КОМПЛЕКСНЫЕ ЧИСЛА Порядок: Real-Imag. МОДЕЛИ ПАМЯТИ Байт Слово. Машинное слово – разрядность процессора. Слово программное равно 16 битам. Выровненные данные: 1 2 3 dword 4 word 8 char 16 dword Не выровненные данные: 1 2 3 dword 4 word char dword_начало 8 dword_продолжение 16 Порядок байтов: Число: 0xA1B2C3D4 Порядок от младшего к старшему (little-endian) 0xD4 0xC3 0xB2 0xA1 Порядок от старшего к младшему (big-endian) 0xA1 0xB2 0xC3 0xD4 УРОВЕНЬ ОПЕРАЦИОННОЙ СИСТЕМЫ ОБЗОР 1. Виртуальная память 2. Управление процессами 3. Драйвера устройств – изолируют программиста от других программных средств. Проблемы работы с физической памятью: ограниченность и незащищенность. Ограниченность преодолевалась постоянной загрузкой/выгрузкой данных. У физической памяти нет регламента по ее использованию программами – незащищенность. Виртуальная память предоставляет свое адресное пространство (4Гб для современных процессоров) для каждого процесса. Виртуальная память решает проблемы физической памяти. ПРОБЛЕМЫ ВИРТУАЛЬНОЙ ПАМЯТИ 1. Загрузка и выгрузка страниц на жестких дисках. Проблема когда это делать. Во время работы или по мере необходимости. 2. Проблема фрагментации возникают из-за первой проблемы. Появление свободного неиспользуемого пространства памяти. 3. Сегментация скорее не проблема, а решение. Сегмент – это область пространства, в котором лежат данные одного типа. Сегментация – это деление памяти на сегменты. СТРАНИЧНАЯ ОРГАНИЗАЦИЯ ПАМЯТИ – метод решения проблемы загрузки/выгрузки страниц. Адрес страницы Смещение внутри страницы Если бит присутствия равен единице, значит, данная страница есть в памяти. Если бит присутствия равен нулю, тогда процессор генерирует прерывание; дальше действует процедура обработки прерывания. Страница может быть выгружена в жесткую память или не создана. Операционная система подгружает нужную страницу с жесткого диска. ПРЕРЫВАНИЯ И ИСКЛЮЧЕНИЯ Источники прерываний – внешние: нажатие на кнопку или любое другое внешнее событие, которое надо обработать. Источники исключений – внутреннее событие, процессор вынужден их обработать и остановить выполнение операции. Вектор обработки прерывания – структура данных, который сообщает, где находится источник операции прерывания. Процедуры обработки прерываний – в них хранятся адреса процедур и адреса команд. Эти процедуры должны быть короткими. Они ставят прерывания в очередь для выполнения. Использование прерываний для многозадачных систем: диспетчер, который выдает процессу время на обработку прерываний. - невытесняющиеся. Обработка происходит в выделенное ей время. Приложение само знает сколько ему надо на обработку. - вытесняющая. Все решает операционная система. Используется прерывание, т.к. иначе приложение остановить нельзя. УРОВЕНЬ ЯЗЫКА АССЕМБЛЕРА ПРИМЕР ПРОГРАММЫ НА ЯЗЫКЕ АССЕМБЛЕР Метка Код операции Операнды Комментарии FORMULA: MOV EAX, I ; регистр ЕАХ=1 ADD EAX, J ; регистр EAX=I+J MOV N, EAX ; N=I+J I DW 3 ; резервируем 4 байта и устанавливаем значение 3 J DW 4 ; резервируем 4 байта и устанавливаем значение 4 N DW ; резервируем 4 байта и устанавливаем значение 0 ПРОЦЕСС АССЕМБЛИРОВАНИЯ Первый проход – составление таблицы символов. Метка Код операции Операнды Комментарии Длина Счетчик адреса команд MARIA: MOV EAX, I EAX=I 5 100 MOV EBX, J EBX=J 6 105 ROBERTA: MOV ECX, К ECX=K 6 111 IMUL EAX, EAX EAX=I*I 2 117 IMUL EBX, EBX EBX=J*J 3 119 IMUL ECX, ECX ECX=K*K 3 122 MARILYN: ADD EAX, EBX EAX=H+J*J 2 125 ADD EAX, ECX EAX=I*I+J*J+K*K 2 127 STEPHANY: JMP DONE Переход к DONE 5 129 Второй проход – составление объектного кода и таблицы символов. В результате получаем объектный код и таблицу символов (внешние или глобальные метки). КОМПОНОВКА МОДУЛЕЙ Этапы компоновщика: 1. разрешает внешние ссылки: вместо неизвестной переменной ставит ее адреса. 2. переделает относительные адреса в абсолютные. СВЯЗЬ С БИБЛИОТЕЧНЫМИ ФУНКЦИЯМИ Статическое связывание, осуществляемое до запуска программы: – не позволяет загружать дополнительные модули; – не позволяет использовать одну процедуру различными программами. Динамическое связывание осуществляется во время выполнения программы. В многозадачных ОС существует рад задач, которые требуется реализовать для многих приложений (например, работа с окнами). Для таких задач имеет смысл создавать библиотечные функции. Существует 2 методы связи с библиотечными функциями: 1. При статическом связывании функция компонуется вместе с программами. При этом при запуске нескольних приложений память загружается несколько раз одним и тем же кодом. При выходе новых версий библиотек нужно перекомпилировать все программы. 2. Динамическое связывание происходит во время запуска программы. При этом необходимо некоторое время на связывание, возникает ряд проблем с нахождением функции, связыванием разных версий и разных библиотек. Блок 2 АРХИТЕКТУРА ПАМЯТИ ТИПЫ ПАМЯТИ RAM (random access memory) – память с произвольным доступом (ОЗУ). Позволяет записывать и считывать информацию. После перезагрузки данные пропадают. 1) Статическая (SRAM) – в качестве элементов памяти используются триггеры. Быстрая и дорогая. Обычно время доступа составляет несколько наносекунд. По этой причине статическое ОЗУ часто используется в качестве кэш-памяти. 2) Динамическая (DRAM) – в качестве элементов памяти используются конденсаторы. Медленная, требует подзарядки, дешевая. Динамическое ОЗУ представляет собой массив ячеек, каждая из которых содержит транзистор и крошечный конденсатор. Конденсаторы могут быть заряжены и разряжены, что позволяет хранить единицы и нули. Динамическое ОЗУ нужен только 1 транзистор, 1 конденсатор на бит. ROM (read only memory) – память только для чтения (ПЗУ). Информация заносится в память при ее изготовлении и не может изменяться. Очень дешевая и позволяет хранить информацию после выключения питания. Применяется для загрузки вычислительных систем, хранения справочных таблиц. NVRAM (non-volatile random access memory) – энергонезависимая память(ППЗУ). Позволяет записывать и считывать информацию и при этом хранит данные при выключении питания. Flash-память – современный тип электронно-перепрограммированного ПЗУ. ОРГАНИЗАЦИЯ ПАМЯТИ Наиболее популярным способом организации памяти является расположение ячеек в виде трехмерного массива. Одна размерность массива соответствует слову процессора. Две других – адрес строки и адрес столбца. ЗЭ – запоминающий элемент; DCx – дешифратор строк; DCy – дешифратор столбцов; n/2 – количество бит адреса» CS – выбор микросхемы; A – адресной вход; 1 – схема «ИЛИ». АРХИТЕКТУРНЫЕ МЕТОДЫ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ Все архитектурные методы повышения производительности используют известные статистические свойства, характерные для большинства программ. Особенности использования памяти: 1. Пространственная локальность данных. Означает, что вероятность последовательного считывания нескольких последовательных адресов данных намного выше, чем вероятность произвольного доступа к данным. 2. Временная локальность данных. Означает, что вероятнее всего программа будет проводить несколько операций над одними и теми же данными. Методы повышения производительности: 1. Пакетная обработка множества запросов к памяти 2. Конвейерная обработка множества запросов к памяти 3. Кэш-память ПАКЕТНЫЙ ДОСТУП К ПАМЯТИ (метод повышения производительности работы с памятью) При пакетном доступе к памяти вся память разбивается на несколько банков. Банк представляет собой несколько ячеек динамической памяти и фиксатор – регистр быстрой статической памяти. При обращении к одной ячейке памяти считывание динамической памяти происходит сразу во всех банках. В случае, если следующий запрос будет к ячейке той же строки, но другому банку, то необходимости считывания с динамической памяти не будет, данные можно взять из фиксатора. КОНВЕЙЕРНЫЙ ДОСТУП К ПАМЯТИ При конвейерном доступе к памяти операция чтения данных развивается по стадиям: запрос данных, считывание из банка памяти, выдача данных. В данной схеме можно не дожидаясь выполнения текущей команды (например, 4 ячейки) начать выполнение чтение новой ячейки (9). КЭШ-ПАМЯТЬ Кэш-память – это небольшой объем быстрой статичной памяти, используемый для хранения наиболее часто запрашиваемых данных. Обращение памяти на кэш происходит с помощью кэш строк. Кэш-строка – минимальный объем кэшированной информации. Размер кэш строки определяется компромиссом: кэш-строка должна быть больше, чтобы эффективнее использовать логику и меньше ,чтобы избежать потерь при кэшировании больших объемов данных. Адрес ячейки разбивается на тэг и адрес внутри кэш-строки. Тэг – метка, которая позволяет определить какому участку памяти соответствует кэш-строка. Ассоциативная память – поиск данных происходит не по адресу, а по содержимому (её реализация очень сложна). Стратегия размещения – показывает, то как отображается кэш-строка в оперативной памяти. Стратегия обновления основной памяти – запись данных. Стратегия замещения – алгоритмы, которые определяют строку и которые можно удалить из кэш. Стратегия выборки СТРАТЕГИЯ РАЗМЕЩЕНИЯ. ПРЯМОЕ РАСПРЕДЕЛЕНИЕ Индекс показывает в какой кэш-строке находится участок памяти, определяет номер кэш-строки. Одному индексу соответствует несколько блоков оперативной памяти (ОП). При обращении к памяти проверяется тег. Если тег адреса совпадает с тегом соответствующей строки, то обращение идёт к кэш-памяти, если нет – к ОП. Недостаток: несколько блоков претендуют на 1 строку. Достоинство: простота. СТРАТЕГИЯ РАЗМЕЩЕНИЯ. АССОЦИАТИВНОЕ РАСПРЕДЕЛЕНИЕ Принцип работы: блок может храниться в любой кэш-строке. При обращении к памяти необходимо тег адреса сравнить с тегами всех строк. Достоинство: нет кокуренции за кэш-строки между блоками. СТРАТЕГИЯ РАЗМЕЩЕНИЯ. НАБОРНО-АССОЦИАТИВНОЕ РАСПРЕДЕЛЕНИЕ Принцип работы: адрес разбивается на 3 части. В место индекса используется адрес группы, в котором могут храниться соответствующие блоки основной памяти. Достоинство: блок основной памяти может храниться в нескольких кэш-строках, сравниваются не все теги, а только теги группы. ОП может храниться только в массиве данных. СТРАТЕГИИ ОБНОВЛЕНИЯ ОСНОВНОЙ ПАМЯТИ Метод сквозной записи: процессор записывает данные только в кэш, а согласование кэш-памяти происходит за счёт кэш или за счёт специальных устройств. Обратная запись: нет необходимости записывать в ОП. Данные записываются в ОП только после удаления кэш-строки. СТРАТЕГИЯ ЗАМЕЩЕНИЯ FIFO (first input, first output) – «очередь» (первый вошёл, первый вышел). Произвольное замещение – строка в кэш выбрасывается случайным образом. LRU (last recently used) – (дольше всего использовавшийся). LRU-стек. Операции: 1) поместить в стек; 2) обратиться к элементу; 3) удалить элемент. МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ КЛАССИФИКАЦИЯ КОМПЬЮТЕРОВ ПАРАЛЛЕЛЬНОГО ДЕЙСТВИЯ SISD (один поток команд с одним потоком данных) – это классическая последовательная компьютерная архитектура фон Неймана. SIMD (один поток команд с несколькими потоками данных) – имеется один блок управления, выдающий по одной команде, но при этом есть несколько АЛУ, которые могут обрабатывать несколько наборов данных одновременно, MISD (несколько потоков команд с одним потоком данных) – довольно странная категория. Здесь несколько оперируют одним набором команд. MIMD (несколько потоков команд с несколькими потоками данных). Здесь несколько независимых процессоров работают как часть большой системы. Мультипроцессоры – машины с общей памятью. Мультикомпьютеры – машины с обменом сообщениями. UMA – однородный доступ к памяти; NUMA – неоднородный доступ к памяти; COMA – доступ только к кэш-памяти. Отличаются друг от друга механизмом доступа к общей памяти. COW – кластеры рабочих станций; MPP – процессор с массовым параллелизмом. UMA SMP С ШИННОЙ ОРГАНИЗАЦИЕЙ Рисунок а) Два или более процессора и один или несколько модулей памяти используют эту шину для взаимодействия. Если процессору нужно считать слово из памяти, он сначала проверяет, свободна ли шина. Если шина свободна, процессор помещает адрес нужного слова на шину, устанавливает несколько управляющих сигналов и ждет, когда намять поместит на шину запрошенное слово. Если шина занята, процессор просто ждет, когда она освободится. При наличии двух или трех процессоров доступ к шине регулировать не сложно, трудности возникают, когда процессоров 32 или 64. Чтобы разрешить проблему, нужно добавить к каждому процессору кэш­память (рисунок б). Кэш-память может находиться внутри мик­росхемы процессора, рядом с микросхемой процессора, на плате процессора. В этом случае считы­вать многие слова можно будет из кэша, трафик на шине снизится, и система сможет обслуживать большее количество процессоров. Кэширо­вание дает в данном случае значительный эффект. На рисунке в) каждый процессор имеет не только кэш, но и собствен­ную локальную память, к которой он получает доступ через выделенную локаль­ную шину. SMP – симметричный мультипроцессор. ПРОТОКОЛ MESI 1. Invalid — элемент кэш-памяти содержит недействительные данные. 2. Shared — несколько кэшей могут содержать данную строку; основная память обновлена. 3. Exclusive — никакой другой кэш не содержит эту строку; основная память обновлена. 4. Modified — элемент действителен; основная память недействительна; копий элемента не существует. Протокол MESI используется в процессорах для слежения за шиной. UMA С КОММУТИРУЕМОЙ СТРУКТУРОЙ Перекрестная коммутация на протяжении многих десятилетий ис­пользуется в телефонных коммутаторах, позволяющих произвольным образом связывать группы входящих и исходящих линий. На каждом пересечении горизонтальной (входящей) и вертикальной (исхо­дящей) линии находится коммутационный узел (crosspoint), который можно от­крыть или закрыть в зависимости от того, нужно соединить горизонтальную и вертикальную линии или нет. На рисунке а) три узла закрыты, благодаря чему одновременно устанавливается связь между следующими пара­ми процессор-память (001, 000), (101, 101) и (ПО, 010). Лучшее свойство перекрестной коммутации : неблокирующая - процессор всегда сможет соединиться с нужным модулем памяти, даже если некоторые линии или узлы уже заняты (предполагается, что сам модуль памяти доступен). Худшее свойство перекрестной коммутации : число узлов растет как п2. СС-NUMA При большем количестве устройств в коммутации структура усложняется. Доступ становится неоднородным, т.е. доступ к удаленным элементам будет больше. Система состоит из 256 узлов, в которой каждый узел состоит из одного процессора и 16-мегабайтного ОЗУ, связанного с процес­сором локальной шиной. Общий объем памяти составляет 232 байт. Она разделе­на на 226 строк кэша по 64 байт каждая. Память статически распределена по уз­лам: адреса 0-16 М располагаются в узле 0, адреса 16-32 М — в узле 1 и т. д. Узлы связаны коммуникационной сетью. Сеть может быть реализо­вана в виде решетки, гиперкуба или иметь другую топологию. Сначала процессор, выдав­ший команду, передает ее диспетчеру памяти, который транслирует ее, чтобы по­лучить физический адрес. Диспетчер памяти разделяет этот адрес на три части (рисунок б). В десятичной системе счис­ления эти три части представляют собой узел 36, строку 4 и смещение 8. Диспет­чер памяти видит, что слово памяти, к которому производится обращение, на­ходится в узле 36, а не в узле 20, поэтому посылает запрос через сеть в узел 36, где находится нужная строка, узнает, есть ли строка 4 в кэше, и если да, то где именно. Когда запрос приходит в узел 36, он направляется в устройство каталога. Уст­ройство проверяет таблицу из 218 элементов (один элемент на каждую строку кэ­ша) и извлекает элемент 4. На рисунке в) видно, что строка отсутствует в кэше, поэтому устройство вызывает строку 4 из локального ОЗУ, отправляет ее узлу 20 и обновляет элемент каталога 4, показывая, что эта строка находится в кэше узла 20. АЛГОРИТМ КОГЕРЕНТНОГО КЭШИРОВАНИЯ SCI Роль узлов: 1. Разделяющие читатели 2. Исключительные писатели 3. Аннулирование при записи 4. Ведение учета Состояние данных: 1. Сырые – после того, как считались. 2. Свежие – только что считанные. 3. Устаревшие – модифицированные. SCI – расширяемый связной интерфейс. Алгоритм остановок на каталогах, в которых хранится 2-х уровневая система информации кэш-строк.