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

1) Емкость кэш. Емкость кэш - компромиссное решение, она должна быть достаточна мала так, чтобы ее стоимость была сопоставима по стоимость с ОП и она должна быть достаточно большой, чтобы среднее время доступа к системе (по ОП+кэш), определялось временем доступа к кэш. При увеличении емкости кэш-памяти вероятность промахов первоначально снижается, а затем становится практически постоянной, поэтому в настоящее время емкость кэш 512 кб.

ABC - программы.

Рис.

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

Приписки на графике - размеры КЭШ

Рис.

3) Способы отображения ОП на кэш-память. Отображение блока ОП на кэш - это копирование блока в какую-нибудь строку кэш, после чего все обращение к блоку в ОП переадресуется на строку кэш.

E_ОП=256 к слов

E_КЭШ=2 к слов

Для адресации ОП необходимо 18 разрядов адреса, для кэш 11 разрядов.

При этом ОП разбивается по блокам по 16 слов, поэтому 14 разрядов адреса адресуют один из блоков и 4 бита определяют адрес слова в блоке кэш-памяти, 7 старших разрядов определяют номер строки в кэш и 4 младших определяют адрес слова в строке. Т.е. размер блока и строки совпадают.

Прямое отображение

Рис.

При прямом отображении адрес строки i кэш памяти на которую отображается блок j из ОП определяется зависимостью i=j mod m, в нашем случае m-общее число строк в памяти (m=128) i0…127 j=0…16383.

ОП условно строится в виде двумерного массива, в котором число строк равно числу строк в кэш памяти. При этом 14 разрядный адрес блока разбивается на 2 поля: 7 разрядный тэг и 7 разрядное поле строки. Тэгом является 7 старших разрядов адреса блока. При прямом отображении в каждый из блоков ОП i-ой строки отображается на одну и ту же строку в кэш памяти. Прямое отображение самый простой способ отображения. Недостаток способа - жесткое закрепление за определенными блоками ОП одной и той же строки кэш-памяти. Поэтому если происходит обращение к соседним блокам строки ОП, то возникает частое замещение в строке кэш. Память тэга хранит номер строки.

Ассоциативное отображение

В данном способе разрешается загрузка любого блока ОП в любую строку кэш памяти. При этом схему управления кэш выделяют в адресе ОП поле тэга и поле слова. Поле тэга совпадает с адресом блока ОП. Для проверки наличия блока кэш памяти схема управления одновременно проверяет тэги всех слов на совпадение поля тэга адреса, поэтому тэг хранится в ассоциативной памяти тэгов КЭШа.

Рис.

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

Алгоритмы замещения информации в кэш памяти

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

1) LRU - Least Recently Used - наиболее дальнего использования. Замещается строка к которой дольше всего не было обращения. Аппаратная реализация: каждой строке приписывается счетчик, который синхронно меняет свое состояние. При обращении к строке счетчик обнуляется и наибольшее значение одного из счетчиков определяет замещаемую строку.

2) Карабкающаяся страница. Каждой строке кэш назначается индекс, который меняется в соседнем, в этом случае, если было обращение. Если в строке не было обращений, то она перемещается в строку ОП и ближний индекс ОП определяет замещаемую строку.

Рис.

3) FIFO (First input first output). Заменяется строка дольше других находившаяся в кэш. Реализуется с помощью таймера, приписанного к каждой из строк.

4) LFU (Least frequently used) - замена наиболее редко использовавшейся строки. Заменяется строка к которой было меньше всего обращений. Реализуется с помощью счетчика, который меняет свое значение при каждом обращении к строке.

5) Случайное замещение. Реализуется с помощью счетчика, который считает по модулю числа строк в кэш. Мгновенное состояние счетчика определяет замещаемую строку (чтение на лету).

Алгоритмы согласования содержимого кэш памяти и ОП

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

При сквозной записи, если меняется строка в кэш, то автоматически происходит обновление блока ОП. Достоинство: При замещении строки в кэш ее не нужно переписывать в ОП, она удаляется. Недостаток: нет сокращения времени на запись информации в кэш. Обратная запись: в данном алгоритме информация меняется только в кэш, при этом каждой строке приписывается флаг изменения и при необходимости замещение строки и установленном флаге изменения строки, она переписывается в блок ОП. Метод обратной записи более эффективен (на 10% ), так как обращение к памяти - это в основном обращение по чтению. Поскольку обращение по записи от 5-30%. При изменении информации в ОП для соблюдения когерентности ввод информации в ОП автоматически изменяет содержимое определенной строки кэш. Прямой доступ к ОП возможен только через кэш-память.

Методы управления вводом-выводом информации в ЭВМ

Существует 3 способа организации ввода-вывода:

1. программно управляемый ввод-вывод

2. ввод-вывод по прерыванию

3. прямой доступ к памяти DMA

1 - все делается по инициативе процессора и под его контролем. Процессор выполняет программу, которая отслеживает состояние ВУ, выдает команду ВВ-ВЫВ выдав команду процессор должен ждать ее завершения.

2 - после выполнения команды ввода вывода процессор не должен циклически опрашивать МВВ(модуль ввода-вывода), для отслеживания состояния устройства, а должен выполнять другие команды, пока не получит запрос прерывания от контр ВВ. Процессор отвечает за чтение данных из памяти при выводе и за запись данных при вводе. 1-е 2 способа приводят к простою процессора. 3 - DMA исключает простой процессора, и обмен МВВ с памятью производится без участия процессора.

1. Программно управляемый ввод/вывод

Рис.

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

Достоинства: Простая организации ввода-вывода т.к. все функции выполняет процессор. Простая система приоритетов ВУ.

2. ввод/вывод по прерыванию

Рис.

Прерывание

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

Рис.

Идентификация внешних устройств, выставивших запрос на прерывание

Рис.

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

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

3 Векторное прерывание - при организации запросов - ВУ выставляет специальное слово - вектор прерывания. Слово содержит либо адрес МВВ, либо адрес начала прерывающей программы. В данном способе устраняется поиск источника прерывания. Метод реализуется с помощью таблиц векторов прерывания, которые находятся в ОП (для IBM PC - в начальных адресах 256 векторов прерывания, каждый по 4байта).

Рис.

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

3. ПДП

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

Счетчик данных - хранит размер данных в словах. После передачи слова Счт:=Счт-1.

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

Регистр адреса - хранит адрес начальной ячейки памяти.

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

Рис.

Процесс пересылки состоит из 2х этапов.

Операция чтения (ОП>ВУ)

1) КПДП выставляет на ША адрес ячейки ОП и выдает сигнал ЧтЗУ, считанное слово помещается на ШД.

2) КПДП выставляет на ША адрес устройства и формирует сигнал «вывод», по которому производится передача с ШД на ВУ.

Операция записи (ВУ>ОП)

1) КПДП выдает на ША адрес устройства ввод и формирует сигнал «ввод», по которому данные передаются на ШД.

2) КПДП выставляет на ША адрес ячейки ОП и подает сигнал ЗпЗУ, по кот информация с ШД записывается в ОП.

После каждой пересылки логика управления уменьшает СчтД на 1, если он стал равен 0, то передача заканчивается: КПДП снимает сигнал «запрос ПДП». Проц снимает сигнал «подтверждение ПДП» и возвращает системную шину.

Разделение системной шины происходит в 3-х вариантах:

1 Блочная пересылка - КПДП полностью захватывает системную шину от начала до конца обмена. Процессор не имеет доступа к шине.

2 Пропуск цикла - КПДП после передачи каждого слова на один цикл освобождает системную шину, предоставляя ее процессору.

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

Точки организации по ПДП и обмена по прерываниям:

Рис.

Вычислительные системы. Уровни параллелизма. Классификация ВС Флинна. Закон Амдала

Параллелизм - 1-ин из главных способов повышения производительности работы вычислительных систем (ВС). ВС - это такая система которая производит параллельныеые вычисления.

Уровни параллелизмаизма.

1. Уровень заданий - независимые задания выполняются на разных процессорах с малым взаимодействием между собой. Уровень реализуется на ВС с множеством процессоров в мультизадачном режиме.

Положим ВС с 4-мя процессорами, надо отработать задания:

S - для выполнения требуется 1 процессор, M - 2 процессора, L - 4 процессора.

Есть очередь заданий : SMLSSMLLSMM

Таблица

Таблица

Как видно в первой организации последовательности подачи команд на выполнение средний процент загрузки равен 83%, а во втором 100%, следовательно, 1-а из основных задач - организация эффективного ввода данных.

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

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

For i:=1 to N Do

A[i]:=B[i]+C[i]

Если имеем 4 процессора, то распараллеливание следующее:

для 1-го i=1,5,…

для 2-го i=2,6,…

для 3-го i=3,7,…

для 4-го i=4,8,…

Разделение данных необходимо для организации параллелизма уровня программ и это разделение называется декомпозицией данных.

3. Уровень команд - выполнение команды разделятся на фазы, а фазы последовательных команд перекрываются за счет конвейеризации, уровень достигается на ВС с 1-им процессором.

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

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

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

Гранулярность:

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

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

- Мелкозернистый параллелизм (параллельное вычисление мало - около 10-ов команд, единица распараллеливания - элементы выражения или операции цикла).

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

Закон Амдала

В идеальном случае при увеличении числа процессоров (далее CPU) в n раз, производительность так же должна возрасти в n раз, что на практике не возможно т.к. нельзя распараллелить выполнение задачи целиком на все n CPU, кроме того, надо организовывать связи между CPU, а так же использовать дополнительную индексацию при декомпозиции данных.

Оценка производительности или ускорения от числа CPU и распараллеливаемой части программы определяется законом Амдала: S=Ts/Tp - ускорение. (Ts - время без распараллеливания, Tp - с распараллеливанием)

Программный код решаемой задачи состоит из 2-ух частей: последовательной и распараллеливаемой. Пусть f - для операций которые должны выполняться последовательно 1-им CPU, при этом 0 f 1, тогда (1- f ) - доля распараллеливаемой части программы. Если f = 0, то программа полностью распараллеливаемая, что невозможно. Распараллеливаемая часть программы равномерно распределяется по всем CPU:

Рис.

Рис.

Tp=fTs+(1-f)Ts/n

S=Ts/Tp=n/(1+(n-1)f) (*)

Формула (*) выражает зависимость ускорения от числа CPU и доле распараллеливаемой части программы f.

См. правый рисунок. Если в программе 10% последовательных операций, т.е f = 0.1, то при любом числе CPU, ускорение более чем в 10 раз не получить, при этом 10 - это теоретическое значение.

Классификация ВС по Флинну

В основе классификации находится понятие потока - это последовательность команд или данных, обрабатываемая CPU. В зависимости от числа потока команд или данных Флинн разделил ВС на 4 группы:

Таблица. 1. SISD (ОКОД - одиночный поток команд одиночный поток данных).

Таблица. 2. MISD (МКОД - множественный поток команд одиночный поток данных).

Таблица. 3. SIMD (ОКМД - одиночный поток команд множественный поток данных).

Таблица. 4. МIMD (МКМД - множественный поток команд множественный поток данных).

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

Недостаток такой классификации:

1. Невозможность однозначно отнести некоторые ВС к определенному классу (если вектор - единица данных, то вместо SIMD систему можно отнести к SISD).

2. Класс MIMD очень насыщен (большинство систем именно этого класса).

3. Размещено на Allbest.ru