А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 191

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 191)

Матричное суммирование представляет собой простое поэлементное сложение чисел с плавающей точкой. порядка циклов каждый блок Я требуется в кэше только один раз, так что (как и в анализе базового алгоритма в разделе 1!.2.1) мы не учитываем промахи кэша, связанные с У. Для загрузки блоков Х и У в кэш требуется Вз/с промахов (вспомним, что с— количество элементов в строке кэша). Для фиксированных блоков Х и У в строках 4 — 7 выполняется Вз операций умножения и сложения (напомним, что эти два действия рассматриваются как единая операция).

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

С другой стороны, если матрицы полностью в кэш не помещаются, то потребуется О (пз,(с) или даже О (пз) про- 933 11.2. Пример посерьезнее: умножение матриц махов кэша. В этом случае использование разбиения на блоки даст существенный выигрыш, в особенности если учесть, что В может быть достагочно большим (например, при В, равном 200, можно разместить все три блока 8-байтовых чисел в кэше размером ! Мбайт).

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

11.2.3 Интерференция кэша К сожалению, к вопросу об использовании кэшей следует добавить еше несколько слов. Большинство кэшей не полностью ассоциативны (см. раздел 7.4.2). Если в кэше с прямым отображением п, кратно размеру кэша, то все элементы одной строки массива размером а х и, будуг конкурировать за одно и то же место в кзше.

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

11.2.4 Упражнения к разделу 11.2 Упражнение 11.2.1. Алгоритм умножения матриц с разделением на блоки, представленный на рис. 11.8, не инициализирует матрицу У нулевыми значениями, как это делает код на рис. 11.5. Добавьте в код на рис. 11.8 шаги, необходимые для корректной инициализации массива е нулями. 934 Глава 11. Оптимизация параллелизма и локальности 11.3 Пространства итераций В простых задачах наподобие матричного умножения применение описанных методов реализуется достаточно просто.

Но в общем случае, хотя описанные методы и применимы, делается это гораздо менее интуитивно. Если же воспользоваться линейной алгеброй, все становится существенно проще даже в общем случае. Как говорилось в разделе 11.1.5, в нашей модели имеется три типа пространств — пространство итераций, пространство данных и пространство процессоров. Сейчас мы начнем наше рассмотрение с пространства итераций.

Пространство итераций вложения циклов определяется, как все комбинации индексных переменных вложения. Зачастую пространство итераций прямоугольное, как в примере умножения матриц на рис. 11.5. Здесь каждый вложенный цикл имеет нижнюю границу 0 и верхнюю границу и — 1.

Однако в более сложных, но при этом достаточно реалистических вложениях циклов верхние и/или нижние границы индексов циклов могут зависеть от значений индексов охватывающих циклов. Вскоре мы познакомимся с примером такой ситуации. 11.3.1 Построение пространств итераций вложений ЦИКЛОВ Сначала опишем вид вложений циклов, с которыми можно работать при помощи рассматриваемых методов.

Каждый цикл имеет один индекс, который предполагается возрастающим на 1 на каждой итерации цикла. Это предположение не приводит к потере общности, поскольку при увеличении на целое число с ) 1 мы всегда можем заменить индекс 1 величиной с( + а с некоторой положительной или отрицательной константой а и увеличивать 1 в цикле на 1. Границы цикла должны записываться как аффинные выражения от индексов внешних циклов.

Пример 11.5. Рассмотрим цикл, в котором на каждой итерации цикла значение ( увеличивается на 3: Гог(а=2;х<=100;з=з+3) Е(з] = 0; Это приводит к тому, что значение 0 присваивается элементам У (2], У ]5], У ]8], ..., У ]98]. Тот же результат можно получить при помощи цикла Кот(З = 0; 1. <= 32; 3++) Е(3*3+2) = 0; Иначе говоря, мы просто заменяем г' на 3) + 2. Нижний предел( = 2 превращается в )' = 0 (простым решением уравнения 3) + 2 =- 2), а верхний предел ( < 100 935 11.3. Пространства итераций становится пределом )' < 32 (из 3) + 2 < 100 получаем ) < 32,67 и округляем полученное значение до 32, так как ) — целое число). с Обычно циклы !ог используются во вложениях циклов. Циклы ттЫ!е и гереа! могут быть заменены циклом (ог, если существует индекс цикла и его нижняя и верхняя границы, как, например, в цикле на рис.

11.9, а, который вполне заменим циклом аког(1=0з 1<100; 1++). з.=О; и)з11е (1<100) ( <Некоторые инструкции с участием 1> = з+1; а) Цикл лЫ!е с очевидными границами — 0; и)з11е (1) ( <Некоторые инструкции> 1 = 1+1; б) Неясно, когда и почему завершается данный цикл 1=0; ийз.1е ( з.<п) ( <Некоторые инструкции, не включающие з или п> — 1+1; в) Значение п неизвестно, так что неизвестно и когда завершается данный цикл Рнс.

11.9. Некоторые циклы юИе Однако некоторые циклы ттИе и гереа( не имеют очевидных границ. Например, цикл на рис. 11.9, б может завершиться, а может и не завершиться, причем нет способа указать, какое условие, связанное с ( в невидимом теле цикла, вызывает его завершение. На рис. 11.9, в показан еще один проблемный случай. Переменная п может быть, например, параметром функции. Мы знаем, что цикл выполняется и раз, но во время компиляции мы не знаем, чему равно и, и можем ожидать, что в случае нескольких выполнений этого цикла всякий раз будет выполняться иное количество итераций. В случаях, подобных представленным на рис. 11.9, б и в, следует полагать, что верхняя граница цикла равна бесконечности. 936 Глава 11. Оптимизация параллелизма и локальности Вложенность циклов глубиной г) может быть смоделирована при помощи дмерного пространства.

Измерения упорядочены, )с-е измерение представляет Й-й вложенный цикл, считая от самого внешнего цикла в глубину. Точка (кы кз,, .., кв) в этом пространстве представляет значения всех индексов циклов; значение индекса внешнего цикла равно хп второго цикла — кз и т.д. Значение индекса наиболее глубоко вложенного цикла равно хт Однако не все точки в этом пространстве представляют комбинации индексов, которые в действительности встречаются в процессе выполнения вложенности циклов. Представляя собой аффинную функцию от индексов внешних циклов, каждая верхняя и нижняя граница цикла определяет неравенство, разделяющее пространство итераций на два полупространства: то, в котором имеются итерации цикла (положительное полупространство), и то, в котором его нет (отрицательное полупространство).

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

Характеристики

Список файлов книги