Максимов Н.В., Партыка Т.Л., Попов И.И. Архитектура ЭВМ и вычислительных систем (2005) (1186253), страница 59
Текст из файла (страница 59)
Как правило, для замещенияблоков применяются две основные стратегии: случайная иLRU-стратегия.В первом случае, чтобы иметь равномерное распределение, блоки-кандидаты выбираются случайно. В некоторых системах, чтобыполучить воспроизводимое поведение, которое особенно полезно вовремя отладки аппаратуры, используют псевдослучайный алгоритмзамещения.Во втором случае, чтобы уменьшить вероятность выбрасыванияинформации, которая скоро может потребоваться, все обращения кблокам фиксируются.
Заменяется тот блок, который не использовался дольше всех (LRU — Least-Recently Used).Достоинство случайного способа заключается в том, что егопроще реализовать в аппаратуре. Когда количество блоков увеличивается, алгоритм LRU становится все более дорогим и часто толькоприближенным.
В табл. 3.4 показаны различия в долях промаховпри использовании алгоритма замещения LRU и случайного алгоритма.2973.5. Системы памятиТаблица 3.4. Влияние стратегии замещения на долю промаха при разных размерахкэш-памяти и ассоциативностиАссоциативность,размер кэш-памяти,Кбайт2-канальная стратегия4-канальная стратегия8-канальная стратегияLRURandomLRURandomLRURandom165,185,694,675,294,394,96641,882,011,541,661,391,532561,151,171,131,131,121,12Из таблицы видно, что при большом размере кэш-памяти стратегии замещения несущественно влияют на эффективность памяти.Организация памяти в однопроцессорных ВСОднопроцессорные ВС были первыми вычислительными системами, в которых была реализована иерархическая структура памяти.Как правило, однопроцессорные ВС представляют собой совокупность процессора, памяти и внешних устройств (ВНУ), соединенных с помощью общей шины (рис.
3.35).Применение кэша в таких системах обусловлено только экономической эффективностью функционирования систем с кэшпамятью:• алгоритм сквозной записи (Write Through) или сквозного накопления (Store Through);• алгоритм простого свопинга (Simple Swapping) или обратнойзаписи (Write Back);• алгоритм свопинга с флагами (Flag Swapping) или обратной записи в конфликтных ситуациях с флагами (CUX);• алгоритм регистрового свопинга с флагами (FRS).ШинаОсновная память!Рис. 3.35. Однопроцессорные ВС с иерархической системой памяти298Глава 3.
Вычислительные системыАлгоритм сквозной записи. Это самый простой алгоритм свопинга. Каждый раз при появлении запроса на запись по некоторому адресу обновляется содержимое области по этому адресу как в быстрой, так и в основной памяти, даже если копия содержимого поэтому адресу находится в быстром буфере. Такое постоянное обновление содержимого основной памяти, как и буфера, при каждом запросе на запись позволяет постоянно поддерживать информацию,находящуюся в основной памяти, в обновленном состоянии.Поэтому, когда возникает запрос на запись по адресу, относящемуся к области, содержимое которой не находится в данный момент в быстром буфере, новая информация записывается просто наместо блока, которое предполагается переслать в основную память(без необходимости пересылки этого слова в основную память), таккак в основной памяти уже находится его достоверная копия.Данный алгоритм несложен для реализации и понимания, поэтому он был широко распространен в системах с кэш-памятью.Данный алгоритм также просто позволяет реализовать когерентность данных для мультипроцессорных систем с раздельными кэшами и общей памятью.Обратной стороной простоты алгоритма является его малая эффективность: в нем не заложена тенденция к минимизации доли об-Записьв кэшОбновлениесправочника\ОжшРис.
3.36. Блок-схема алгоритма сквозной записи3.5. Системы памяти299ращений к основной памяти При увеличении объема кэш-памятидоля обращений к основной памяти асимптоматически приближается к доле обращений для записи в основную память (а не к нулю).На рис 3.36 приведена блок-схема алгоритма сквозной записи.Алгоритм простого свопинга. Данный алгоритм не сложнее алгоритма сквозной записи.
Обращения к основной памяти имеют место в тех случаях, когда в быстром буфере не обнаруживается нужное слово. Эта схема свопинга повышает производительность системы памяти, так как в ней обращения к основной памяти непроисходят при каждом запросе на запись, что имеет место при использовании алгоритма сквозной записи. Однако в связи с тем, чтосодержимое основной памяти не поддерживается в постоянно обновленном состоянии, если необходимого слова в быстром буферене обнаруживается, из буфера в основную память надо возвратитькакое-либо устаревшее слово, чтобы освободить место для новогонеобходимого слова.
Поэтому из буфера в основную память сначалапересылается какое-то слово, место которого занимает в буференужное слово. Таким образом, происходят две пересылки между быстрым буфером и основной памятью.Алгоритм свопинга с флагами. Данный алгоритм является улучшением алгоритма простого свопинга. В алгоритме простого свопинга, когда в кэш-памяти не обнаруживается нужное слово, происходит два обращения к основной памяти — запись удаляемогозначения из кэша и чтение нового значения в кэш. Если слово стого момента, как оно попало в буфер из основной памяти, не подвергалось изменениям, т. е. по его адресу не производилась запись(оно использовалось только для чтения), то нет необходимости пересылать его обратно в основную память, потому что в ней и такимеется достоверная его копия; это обстоятельство позволяет в рядеслучаев обойтись без обращений к основной памяти.
Если, однако,слово подвергалось изменениям с тех пор, когда его копия была впоследний раз записана обратно в основную память, то приходитсяперемещать его в основную память. Отслеживать изменения словаможно, пометив слово (блок) дополнительным флаговым битом.Изменяя значение флагового бита при изменении слова, можносформировать информацию о состоянии слова; пересылать в основную память необходимо лишь те слова, флаги которых оказываютсяв установленном состоянии.Алгоритм регистрового свопинга с флагами.
Повышение эффективности алгоритма свопинга с флагами возможно за счет уменьшения эффективного времени цикла, что можно получить при введении регистра (регистров) временного хранения между кэш-памятью300Глава 3. Вычислительные системыи основной памятью. Теперь, если данные должны быть переданы избыстрого буфера в основную память, они сначала пересылаются врегистр (регистры) временного хранения; новое слово сразу же пересылается в буфер из основной памяти, а уже потом слово, временнохранившееся в регистре, записывается в основную память.
Действияв ЦП начинают опять выполняться, как только для этого возникаетвозможность. Алгоритм обеспечивает совмещение операций записив основную память с обычными операциями над буфером, что обеспечивает еще большее повышение производительности.Способы улучшения эффективности подсистемы памяти в однопроцессорных ВС. Прежде всего, эффективное быстродействие кэшадолжно быть примерно равно быстродействию процессора.
Еслиполное эффективное время обращения к системе памяти с использованием буфера превышает время базового цикла процессора, тодля уравнивания ее быстродействия с быстродействием процессораможно прибегнуть к конвейерной организации процесса обработкиинформации. Когда кэш-память работает с такой же скоростью, какпроцессор, никакой необходимости в конвейерной работе процессора нет. Делать быстродействие кэш-памяти более высоким, чембыстродействие процессора, не имеет смысла, так как процессор(или процессоры) требует обслуживания со стороны памяти с интервалом, не меньшим чем время его рабочего цикла.Современные процессоры выполняют команды со скоростью отнескольких команд в такт до нескольких десятков тактов на команду.
Кроме того, используется конвейерная обработка команд. Дляувеличения своей производительности процессоры обычно вначалепроизводят выборку предполагаемо необходимых данных и команд,а затем исполняют их. Исходя из таких положений, необходимо добиваться того, чтобы кэш-память действовала со скоростью тактовой частоты процессора.На производительность памяти очень сильно влияет алгоритмсвопинга. Как отмечалось выше, наиболее эффективным алгоритмом для однопроцессорных ВС является регистровый свопинг сфлагами.
При увеличении размера кэш-памяти стратегия замещения данных не имеет значения, поэтому можно применять наиболеепростую — случайную стратегию.Необходимо также использовать совмещение работы буфернойи основной памяти.Большой класс задач, решаемых на ЭВМ, имеет дело с большимиобъемами данных, хранимых в массивах. Для улучшения производительности ВС на таких задачах можно применять многомодульнуюсистему основной памяти с горизонтальным расслоением (рис.
3.37).3.5. Системы памяти301Рис. 3.37. Память с горизонтальным расслоениемПри такой организации основной памяти при последовательномобращении к элементам массивов наблюдается увеличение производительности подсистемы памяти, так как кэш ждет меньшее времядо освобождения памяти. Обратной стороной увеличения производительности является уменьшение надежности памяти, посколькупри выходе из строя одного модуля из адресного пространства выпадают ячейки, расположенные через некоторый шаг, что повлияетна все процессы, находящиеся в памяти. Для увеличения производительности и надежности одновременно можно применять так называемую блочно-модульную структуру памяти. Данный подход характерен для многопроцессорных ВС.Иерархическая память многопроцессорных ВСВ структурной организации многопроцессорной системы наиболее существенен способ связи между процессорами и памятью системы.Как известно, параллельные вычислительные системы делятсяна два больших класса: SIMD и MIMD. В настоящее время осваиваются супервычисления на системах из микропроцессоров с кэш-памятью и разделяемой — логически общей и физически распределенной основной памятью.Существующие параллельные вычислительные средства классаMIMD образуют три подкласса: симметричные мультипроцессоры(SMP), кластеры и массово-параллельные системы (МРР).Однако степень масштабируемости SMP-систем ограничена впределах технической реализуемости одинакового для всех процессоров доступа в память со скоростью, характерной для однопроцессорных компьютеров.
На данный момент SMP-структура наиболеераспространена в классе профессиональных рабочих станций набазе RISC-процессоров.302Глава 3. Вычислительные системыДля построения систем с большим числом процессоров применяются кластерный или МРР-подходы. Оба эти направления используют SMP как системообразующий вычислительный модуль(ВМ).Кластерная система образуется из модулей, объединенных системой связи или разделяемыми устройствами внешней памяти, например дисковыми массивами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
