Краткий_Курс (Краткий курс ПОД), страница 3
Описание файла
Файл "Краткий_Курс" внутри архива находится в папке "Краткий курс ПОД". PDF-файл из архива "Краткий курс ПОД", который расположен в категории "". Всё это находится в предмете "параллельная обработка данных" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 3 страницы из PDF
Механизмывиртуальной памяти реализуется путем разбиения памяти и виртуальной ифизической на одинаковые страницы, обычно, размером 4 Кбайта. Адресразделяется на две части в соответствии с принятой длиной страницы: номерстраницы (а) и адрес внутри страницы - сдвиг, смещение (б ). ТрансляцияадресаВиртуальный адрес Физический адреса б ->с б9Аппаратно трансляция адресов производится при помощи таблицыстраниц. Каждой странице виртуальной памяти соответствует строка в таблицестраниц, объем которой соответствует числу страниц виртуальной памяти.
В iстроке таблицы хранится: N страницы (блока) физической памяти, котораясоответствует данной виртуальной, статус доступа (чтение, запись), признакзаписи. Полный физический адрес получается добавлением к физическомуадресу, полученного из таблице страниц, смещения внутри страницы (б).Реальная структура таблицы страниц имеет более сложный вид.8 Чередование адресов(расслоение) памяти (interleaved memory)Расслоение памяти: память делится на М банков с автономным управлениемтак, что при последовательной выборки повторное обращение к одному банкупроизойдет через М обращений, поэтому возможно совмещение временивыборки.Для банков одинаковой емкости:B1,B2,B3,..Bm-1 адрес iтрансформируется в адрес d внутри банка Bb расчетом:i=d * m + b, где d=>0, 0<=b<=m-1При расслоении на четыре распределение адресов в банках будет:Адреса в банках-b Банк 1 Банк 2 Банк 3 Банк 400123Распределение14567адресов i2891011При конвейерном доступе при М-кратным расслоении и регулярнойвыборке доступ к памяти возможен в интервале 1/М цикла памяти.
Новозможны конфликты по доступу, если шаг регулярной выборки коррелируетсяс числом банков памяти.9. Назначение и структура кэш-памяти.Для ускорения доступа к оперативной памяти используется буферизацияданных и объектного кода в памяти, скорость которой значительно выше основной.Если бы доступ к любым типам данных был случайным, то буферизация была быбесполезным.
Эффект от буферизации можно определить среднему временивыборки: t = t2*p+ t1*(1-p), где t1 - среднее время доступа к данным основнойпамяти, t2 - среднее время доступа к данным из буфера (t2<t1), p - вероятностьналичия данного в буфере. Очевидно, среднее время зависит от вероятности р иизменяется от среднего времени доступа к основной памяти (при p=0) до среднеговремени доступа непосредственно в буфер (при p=1). Кэш (cache, cache memory)память, как правило, на порядок более быстрая, чем основная, размещается вкачестве буферной, между процессором и основной памятью и служит длявременного хранения (в рамках своего объема) всех данных, потребляемых илигенерирумых процессором.
В много-уровневых кэшах элементами связки:10"процессор - основная память" могут выступать сами кеши. Алгоритм кэшированиясостоит в следующем:1. По каждому запросу процессора происходит поиск требуемого данного в кэшпамяти (места для записи генерируемого данного).2. Если данное (место) есть в кэше - кэш попадание (cache hit), то оно передается впроцессор (из процессора).3. Если нужного данного нет в кэше - кэш промах (cache miss), данное из основнойпамяти пересылается в кэш память, и передаются также процессору. При переполнениикэша (нет места для записи), из него удаляются (модифицированные данныесохраняются в основной памяти) часть данных, обычно, наименее востребованные.Традиционным кэшем является "процессорный" кэш или кэш первого уровня(первичный) или кэш (L1 Cache), имеющийся на любом микропроцессоре.
Этобуферная память объемом от 4 Кбайт до 16 Мбайт, в которой размещаются вседанные, адресуемые процессором, и из которой данные поставляются процессору.Эта память значительно быстрее основной, но меньшего объема, поэтому механизмкэширования обеспечивает обновление кэша, обычно, сохраняя в нем тольконаиболее часто употребляемые данные.
Обмен между основной и кэш памятямипроизводится квантами, объемами 4 - 128 байт - копируются "строки кэша" (cacheline), содержащие адресуемое данное.Обычно, программный код кешируется через особый, I кэш память, отделеннойот кэша данных D-кэша. Выборка данных из кэша (hit time) прозводится, обычно, заодин такт синхронизации (оценки 1 - 4 такта), потери при кеш промахе оцениваются в8 - 32 такта синхронизации, доля промахов (miss rate) - 1% -20%. По определению,эффект кэширования основан на предположении о многократном использованииданных (Data reuse) из кэш памяти.
Принято различать две формы многократногоиспользования данных кэша:- временное использование (temporal reuse). пространственное использование (spatial reuse). Временное использование означает,что некоторое данное, загруженные в кэш, может использоваться, по крайней мере,более двух раз. Пространственное использование кэша предполагает возможность использовать некоторый пространственный набор данных - строки кэша. Архитектуракэш памяти: полностью ассоциативная, частично ассоциативная и кэш память спрямым отображением.10. Кэш память с прямым отображением.Архитектуракэш-памятиспрямымотображением(direct-mapped)характеризуется наличием явной зависимости между адресами буферной иоперативной памяти, причем каждому адресу кэша соответствуетадресаоперативной памяти, кратные размеру кэш памяти.
Память кэша состоит их памятиданных и памяти тэгов. Пусть, длина строки кэша равна 32 байтам, размер кэша – 4Кбайт, тогда кэш память для данных состоит из 128 строк. ОЗУ разделено на блоки,размером в 4Кбайт, каждый содержит 128 строк. В нулевой строке кэша может бытьразмещены 0 или 128, или .... строки ОЗУ, в первой – 1 или 129 или.. строки т и.д.11Для каждой заполненной строки данных кэша известен тэг – номер блока ОЗУ,которому принадлежит строка.
Тэги хранятся в специальной памяти - памяти тэгов,размер которой – 128 строк. Длина строки памяти тэгов зависит от размера ОЗУ. Еслиобъем ОЗУ – 4 Гбайт, тогда полный адрес - 32 бита можно представить в виде полей:20 рр – тэг (T), 7 рр – номер строки таблиц кэша (S), 5 рр – номер байта в строке (N).Поиск запрошенного байта (T-S-N) в кэше с прямым распределением производитсятак:1.Из памяти данных и памяти тэгов кэша одновременно считываются S-ные строки.2 Если содержимое считанной строки памяти тэгов равно Т – кэш попадание, этозначит, что считанная S строка памяти данных кэша содержит запрашиваемыйбайт и его номер в строке есть N.3.
Если содержимое считанной строки памяти тэгов не равно Т – кэш промах, и тогдаT-S строка ОЗУ переписывается в S строку памяти данных кэша, а Т записывается вS строку памяти тэгов. Затем, см по п. 1.Кэш память Pentium III (Celeron).Кэш память процессоров данного типа состоит из кэшей 1и 2 уровней.Кэш первого уровня (L1) размером в 32 Кбайта разделен на кэш кода- I кэш память, икеш данных – D кэш по 16 Кбайтов каждый. Каждый кэш (I и D) выполнен какчастично ассоциативный с коэффициентом четыре (4-way). Строки кеша состоят из32 байтов. Кэш (16 Кбайтов) поделен на четыре банка по 4 Кбайта (128 строк),каждый из которых есть кэш с прямым распределением, при этом, любой строке ОЗУможет соответствовать одна из четырех соответствующих строк банков кэша.Соответсвенно, имеются четыре памяти тегов по 128 строк.
При запросе данного изпроцессора (T-S-N) одновременно считываются четыре S строки данных кэша ичетыре S строки тэгов. Если содержимое одной из считанных строк тэга равно Т, кэшпопадание и запрашиваемый байт выбирается из S строки данных того банка кэша, укоторого строка тегов совпала с Т. Если содержимое строк памяти тэгов не равно Т– кэш промах.
Тогда, по алгоритму LRU выбирается один из четырех банков кэша, ив него T-S строка ОЗУ переписывается в S строку памяти данных кэша, а Тзаписывается в S строку памяти тэгов.Для кэша второго уровня нет разделения на I кэш память, и кеш данных – Dкэш. Размер кэша может быть для различных моделей процессора составлять128,256,512, .. Кбайт, он также частично ассоциативный с коэффициентом четыре (4way), при этом размер банков будет соответственно равен 32,64,128 Кбайт.
Строкикэша 32 байта.11. Cтратегии обновления основной памяти.Cтратегии обновления основной памяти две: метод сквозной записи и методобратной записи.Кэш-память с немедленной (сквозной) запиcью в ОЗУ (write-through).12Такой кэш при операции 'запись' данного в память всегда записываетданное в основную память и ,возможно, в кэш, если он содержит отображениесоответствующей ячейки памяти.Кэш-память с отстроченной запиcью в ОЗУ (write-back).При данной схеме записи данное записывается только в кэш (насоответствующее адресу основной памяти место). Обновление содержимогоосновной памяти производится при выталкивании строки кеша, при выборкиданного по адресу другими абонентами, которым доступна память: вывод,другие процессоры.
Естественно, при первом способе записи кэш-эффектотсутствует, но реализация второго способа дороже.12. Конвейеризация вычислительных операцийДлительность арифметической операции может быть уменьшена за счетвременного перекрытия ее различных фаз, путем конвейеризации вычислительнойработы. Для этого механизмы Арифметического Логического Устройства (АЛУ)выполняется по конвейерному принципу. Пусть, работа АЛУ - для сложенииданных, разделена на три этапа, на три автономных блока Рi : Р1 - выравниваниепорядков операндов, Р2 - операция сложения мантисс, Р3 - нормализациярезультата, каждый из которых выполняется за один условный такт вычислителя. Ипусть на таком АЛУ выполняются вычисления:A1 = B1+C1A2 = B2+C2A3 = B3+C3A4 = B4+C4Тогда временная диаграмма работы АЛУ имеет вид:Устройство 1 такт2 такт3 такт 4 такт 5 такт6 тактP1B1+C1В2+C2B3+C3 B4+C4 нет работы нет работыP2нет работы B1+C1 B2+C2 B3+C3 B4+C4нет работыP3нет работы нет работы B1+C1 B2+C2 B3+C3В4+С4Вычисления будут выполнены за 6 тактов работы вычислителя, причем,здесь, только два такта работы оборудование было загружено полностью.ВОПРОС !!!! За сколько тактов будет выполнены эти вычисления, еслиАЛУ не конвейеризовано.
Сокращает ли конвейеризация время выполненияотдельной операции ?Оптимальную загрузку конвейерных АЛУ можно получить при работе срегулярными структурами, например, по-элементное сложение векторов. Вобщем случае, пусть работа операционного блока разбивается на nпоследовательных частей (стадий, выполняемые за одинаковое время), накоторых вычислительные операции выполняются в конвейерном режиме. Тогда,если на выполнение одной операции сложения блоку требуется время T, то наобработку N операций сложения время: Tn = (n + N) * (Т / n).
Следовательно,если n << N, то , то ускорение вычислений будет в n раз.13Фактором, снижающим производительность конвейеров, является конфликты поданных. Так вычисления:Вычислениядругая форма этих вычисленийA1 = B1+C1A2 = A1+C2 A2 = (B1+C1)+ C2A3 = B3+C3 A3 = B3+C3A4 = B4+C4 A4 = B4+C4для правильной работы будут выполняться на два такта дольше:Устр. 1такт 2такт 3такт 4такт 5такт 6такт 7такт 8тактP1B1+C1 н/р н/р A1+C2 B3+C3 B4+C4 н/рн/рP2н/р B1+C1 н/р н/р A1+C2 B3+C3 B4+C4 н/рP3н/р н/р B1+C1 н/рн/р A1+C2 B3+C3 В4+С4На этой диаграмме видно, что количество простаивающих тактов работыоборудования “н/р” – “конвейерных пузырей “ (pipeline bubble) стало больше.13. Внеочередное выполнение командМетоды динамической оптимизации: неупорядоченное выполнение “out-of-orderexecution” , неупорядоченная выдача “out-of-order issue” основаны на изменениипорядка вычислений.