uzluga.ru
добавить свой файл
1


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


Иерархии памяти

  • Идея иерархической (многоуровневой) организации памяти заключается в использовании на одном компьютере нескольких уровней памяти, которые характеризуются разным временем доступа к памяти и объемом памяти. (Время доступа к памяти это время между операциями чтения/записи, которые выполняются по случайным адресам.) Основой для иерархической организации памяти служит принцип локальности ссылок во времени и в пространстве.

  • Локальность во времени состоит в том, что процессор многократно использует одни и те же команды и данные.

  • Локальность в пространстве состоит в том, что если программе нужен доступ к слову с адресом A, то скорее всего, следующие ссылки будут к адресам, расположенным по близости с адресом A.

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

  • сокращению количества обращений к оперативной памяти

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



Схема иерархического построения памяти



Интерливинг



Организация кэш-памяти

  • Кэш-память это высокоскоростная память небольшeго размера с прямым доступом. Она предназначена для временного хранения фрагментов кода и данных. Кэш-память охватывает все адресное пространство памяти, но в отличие от оперативной памяти, она не адресуема и невидима для программиста.

  • Схема построения кэш-памяти

  • Кэш-память построена на принципе локальности ссылок во времени и в пространстве.

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

  • Кэш-контроллер перехватывает запросы процессора к основной памяти и проверяет, есть ли действительная копия информации в кэш-памяти.



Структура кэш-памяти



Схема иерархического построения памяти



Организация кэш-памяти

  • Когда контроллер помещает данные в кэш- память?

  • Загрузка по требованию (on demand).

  • Спекулятивная загрузка (speculative load). Алгоритм предполагает помещать данные в кэш-память задолго до того, как к ним произойдет реальное обращение. У кэш-контроллера есть несколько алгоритмов, которые указывают, какие ячейки памяти потребуются процессору в ближайшее

  • время.



Организация кэш-памяти

  • Когда контроллер выполняет поиск данных в памяти?

  • после фиксации промаха (сквозной просмотр).

  • одновременно с поиском блока в кэш-памяти, в случае кэш-попадания, обращение к оперативной памяти прерывается (отложенный просмотр).



Основные вопросы организации кэш-памяти

  • Алгоритм отображения адресов основной памяти в кэш-память.

  • Алгоритм записи данных и команд из кэш-памяти в основную память.

  • Алгоритм замещения строки в кэш-памяти.

  • Размер кэш-памяти.

  • Длина строки в кэш-памяти.



Алгоритмы отображения

  • Прямой (direct mapping).

  • Ассоциативный (full associative mapping).

  • Множественно-ассоциативный (set-associative mapping).





Пример «буксования» кэш-памяти (32 K) (cache trashing)

  • real*8 a(4096),b(4096),c(4096)

  • common a,b,c

  • do i=1,4096

  • c(i)=a(i)+b(i)

  • enddo





Зависимость количества промахов в кэш-память в зависимости от объема кэш-памяти и степени ассоциативности для длины троки 32 байта





Сравнение алгоритмов отображения адресов

  • Прямой

    • 1 блок – 1 строка
    • Плюс: быстрый поиск, маленькие теги, простая реализация
    • Минус: пробуксовка кэша
  • (Полностью) ассоциативный

    • 1 блок – любая строка
    • Плюс: нет пробуксовки кэша
    • Минус: медленный поиск, большие теги, сложная реализация
  • Множественно-ассоциативный

    • 1 блок – несколько строк
    • Компромиссный вариант


Алгоритмы записи

  • Сквозная запись (Write Through (WT)).

  • Сквозная запись с буфери-зацией (Write Combining).

  • Обратная запись (Write Back (WB)).



Алгоритмы замещения кэш-строк

  • Least Recently Used (LRU)

  • Most Recently Used (MRU)

  • Pseudo-Least Recently Used (PLRU)



Алгоритм замещения (алгоритм псевдо-LRU)



Каким должен быть размер линии кэш-памяти?

  • Размер линии должен быть как минимум в ширину канала памяти

  • Большой размер

  • -- Более эффективное использование канала памяти при последовательном доступе

  • -- Позволяет уменьшать «ассоциативность» кэша и количество линий

  • Маленький размер

  • -- Более эффективное использование канала памяти при произвольном доступе

  • -- Заполнение можно делать за одну транзакцию к памяти



Какими должны быть основные параметры кэша?

  • Размер кэша

    • Большой, чтобы вместить рабочие данные
    • Маленький, для быстрого доступа
  • Степень ассоциативности кэша

    • Большая, чтобы избегать пробуксовки
    • Маленькая, для быстрого доступа
  • Размер строки кэша

    • Большой, чтобы использовать локальность
    • Большой, чтобы уменьшить теги
    • Маленький (доля полезных данных в кэше больше, если данные в памяти распределены произвольным образом)




Эффективное использование иерархии памяти

  • Объем обрабатываемых данных

  • Обход данных



Схема иерархической памяти



Последовательный обход данных (Си)



Последовательный обход данных (Фортран)



Пример обхода данных



Результаты теста: перемножение матриц



Эффект «буксования» кэша



Пример «буксования» кэша: 2D массив



Пример «буксования» кэша: 3D массив



Результаты теста: решение уравнения Пуассона в трехмерной области методом Якоби



Рекомендации

  • Объем активно используемых данных не должен превосходить размер кэша

  • По возможности используйте последовательный обход данных

  • Избегайте одновременного использования данных, расположенных в памяти на расстоянии 32Кб (и кратном 32Кб)



Компиляторы языка Си на МВС-1000

  • Compaq C Compiler v6.4.9

  • команда: ccc

  • оптимизирован для процессоров Alpha

  • GNU C Compiler v2.91

  • команда: gcc или cc

  • формирует код для любого процессора

  • старая версия компилятора, формирует очень медленный код



Ключи оптимизации компилятора ccc



Примеры использования различных ключей оптимизации



Помощь компилятору

  • Используйте средства языка для более точного описания природы и способа использования объектов языка

      • Старайтесь не использовать глобальных переменных
      • Используйте различные переменные для разных вычислений
  • Компилятору должно быть ясно, какие зависимости имеются между данными в программе

      • Старайтесь не использовать указатели
      • Компилируйте все модули программы сразу
  • Не стоит делать вручную то, что может сделать компилятор

      • Не разворачивайте циклы
      • Пишите более ясный и простой код, особенно внутри циклов


Точность вычислений

  • Определяется:

    • типом данных (float/real*4, double/real*8, real*16)
    • размеров вещественных регистров процессора (64 бита для процессоров Alpha)
  • Не зависит от компилятора (ccc, forte)

  • Может меняться в результате преобразования программы:

    • изменение порядка данных
    • изменение порядка операций
    • эквивалентные преобразования выражений
    • оптимизация с помощью компилятора