П 2.3. УСТРАНЕНИЕ БУКСОВАНИЯ КЭШ-ПАМЯТИ Цели практической работы

  • 1. Исследование влияния эффекта буксования кэш-памяти на время выполнения программы.
  • 2. Освоение способов устранения буксования кэш-памяти.

Буксование кэш-памяти при обработке массивов

Рассмотрим пример программы заполнения элементов массива, которая приводит к буксованию кэш-памяти (листинг 18). Размеры массива в программе установлены в расчете на кэш-память размером 32 Кбайта (см. рис. 14).

Листинг 18. Пример программы, вызывающей эффект буксования кэш-памяти

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

Способы устранения буксования кэш-памяти

Две основные группы способов устранения кэш-буксования основаны:

  • • на смене представления обрабатываемых данных в оперативной памяти;
  • • изменении порядка доступа к ячейкам памяти.

Первый способ применительно к двумерному массиву заключается в увеличении каждой строки массива на несколько элементов. В листинге 19 показана соответствующая модификация программы листинга 18. Общий размер добавляемых к строке элементов должен быть равным размеру строки кэш-памяти или превышать его. В таком случае ячейки из одной колонки массива располагаются в блоках памяти, которые проецируются на разные множества кэш-памяти.

Листинг 19. Устранение эффекта буксования кэш-памяти, способ 1

Примером второго способа устранения является перестановка циклов. Соответствующий модифицированный пример программы приведен в листинге 20.

Листинг 20. Устранение эффекта буксования кэш-памяти, способ 2

Задание к практической работе

  • 1. Написать программу, реализующую алгоритм из выбранного варианта заданий.
  • 2. Определить значение параметра N, при котором в программе происходит буксование кэш-памяти.
  • 3. Модифицировать программу из п. 1 с целью устранить буксование кэш-памяти, изменив представление массива в памяти путем добавления элементов.
  • 4. Модифицировать программу из п. 1 с целью устранить буксование кэш-памяти, изменив обход элементов по столбцам на обход по строкам.
  • 5. Для определенного в п. 2 значения параметра N и при нескольких других значениях в его окрестности измерить время выполнения трех программ из пп. 1, 3 и 4.
  • 6. На основе проведенных измерений сделать выводы об эффективности каждого из способов устранения буксования кэшпамяти.
  • 7. Составить отчет по практической работе. Отчет должен содержать:
    • • титульный лист;
    • • цель практической работы;
    • • график зависимости времени выполнения исходной программы от размера массива в окрестности размера, при котором наблюдается буксование кэш-памяти;
    • • полный компилируемый листинг одной исходной и двух модифицированных программ и команды для их компиляции;
    • • вывод по результатам практической работы.

Варианты заданий

1. Алгоритм умножения двух квадратных матриц размером Ах А: С - А х В, где элемент матрицы С вычисляется по формуле

N

с) у = X ai кРк j • Обход матрицы А должен производиться по строкам,

к=1

а обход матрицы В - по столбцам. Тип элементов матриц: 8-байтный вещественный.

2. Алгоритм итеративного пересчета элементов двумерного массива размером Ах А. Тип элементов: 4-байтный целочисленный. На каждой новой итерации вычисляем новые значения элементов массива, используя значения элементов массива на предыдущей итерации. Новое значение элемента массива qtj вычисляем из старых значений рц по формуле

Все элементы массива, значения которых используются при подсчете нового значения данного элемента, будем называть окрестностью этого элемента. Если у некоторого элемента окрестность выходит за края массива, то вычисления для него не проводить. Для реализации алгоритма требуются два массива одинакового размера. Исходные значения всех четных итераций (включая нулевую) считываются из первого массива, а новые значения записываются во второй массив. На всех нечетных итерациях исходные значения считываются из второго массива, а записываются - в первый. Предлагается использовать следующие параметры алгоритма: размер массива взять такой, при котором размер одной строки будет превышать размер кэш-памяти 1-го уровня (например, N=8192), а число итераций взять примерно 10...20.

Контрольные вопросы

  • 1. В каких случаях может возникать буксование кэш-памяти при обработке массивов? Приведите пример.
  • 2. Как экспериментально обнаружить буксование кэш-памяти?
  • 3. Какими способами можно устранить буксование кэш-памяти?
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >