А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 190
Текст из файла (страница 190)
Иначе ~оворя, при ) —.. О внутренний цикл загружает в кэш весь первый столбец У. Заметим, что элементы этого столбца хранятся в и разных строках кэша. Если кзш достаточно большой (или п достаточно мало) лля хранения и строк н кэш больше никем не используется, то столбец для з = О останется в кэше, когда нам потребуется второй столбец У. В этом случае промахов кэша не будет до тех пор, пока не будет достигнуто значение з = с, когда потребуется внести в кэш полностью новое множество строк У.
Таким образом, для завершения первой итерации внешнего цикла (для которой з' = О) потребуется от п~/г до и промахов, в зависимости от того, смогут ли столбцы строк кэша оставаться в нем от одной итерации второго цикла до другой. По завершении внешнего цикла при 1, равном 1, 2 и так далее, может возникнуть большое количество догюлнительных промахов кэша при чтении У (а может, их не будет вовсе), Если кэш достаточно велик для того, чтобы все п~/г строк кэша, в которых хранится матрица У, могли располагаться в кэше, то новых промахов не будет. Таким образом, общее количество промахов кэша в этом случае составит 2пз(с, одна половина — для матрицы Х, а другая — для матрицы У.
Но если кзш может хранить только один столбец У, но не всю матрицу целиком, то потребуется полная загрузка всей матрицы У для каждой итерации внешнего цикла. Таким образом, общее количество промахов кэша окажется равным п~/с+ лз,1с: первый член — для матрицы Х, а второй — для матрицы У. Хуже того, если в кэше нельзя хранить столбец матрицы У полностью, то у нас будет пз промахов на итерацию внешнего цикла, а общее количество промахов составит и /с+и . Построчное распараллеливание Давайте теперь посмотрим, как можно использовать несколько процессоров (скажем, р) для того, чтобы ускорить выполнение программы на рис.
11.5. Очевидный подход заключается в толп чтобы назначить разным процессорам вычисление различных строк 2:. Каждый процессор при этом отвечает за вычисление тур соседних строк (для удобства будем считать, что и делится на р). При таком разделении труда каждому процессору потребуется доступ к и/р строкам матриц Х и У и обращение ко всей матрице У. Один процессор будет вычислять пз/р элементов матрицы у, выполняя пз/р операций умножения и сложения (в этом разделе пара операций — умножения и сложения — рассматривается нами как единая операция). Таким образом, хотя время вычислений и уменьшается пропорционально р, стоимость взаимодействия растет пропорционально р, т.е, каждый из р процессоров должен прочесть оз/р элементов Х и все пз элементов У. Общее количество строк кэша, которые должны быть загружены в каши р процессоров, как минимум 930 Глава 11. Оптимизация параллелизма н локальности равно пз/с + рпз(с; эти два члена соответствуют загрузке Х и копий У.
Если р приближается к и, то время вычисления становится равным О (пз), а стоимость взаимодействия — О (пз). Таким образом, узким местом этой системы становится шина, по которой пересылаются данные между памятью и кэшами процессоров. Итак, при предложенной схеме данных использование большого количества процессоров может не ускорить, а напротив, замедлить вычисления. 11.2.2 Оптимизации Алгоритм умножения матриц на рис. 11.5 демонстрирует, что, хотя алгоритм может многократно использовать одни и те же данные, локальность данных при этом может оставлять желать лучшего. Многократное использование данных дает преимушества при работе с кэшем только в том случае, если многократное использование выполняется в ближайшее время, до того, как данные будут удалены из кэша. В нашем же случае нз операций умножения и сложения используют одни и те же элементы данных матрицы У в слишком разные моменты времени, так что результируюшая локальность оказывается низкой.
Кроме того, в многопроцессорной системе многократное использование дает положительный результат только в том случае, когда данные используются одним и тем же процессором. При рассмотрении реализации параллельных вычислений в разделе !!.2.! мы видели, что элементы У должны были использоваться каждым из процессоров. Таким образом, многократное использование У не означает локальности данных. Изменение схемы данных Один из способов повышения локальности программы заключается в изменении схемы используемых ею структур данных.
Например, постолбцовое сохранение У могло бы повысить степень повторного использования строк кэша для матрицы У. Применимость такого подхода ограничена в силу того, что одна и та же матрица обычно используется в разных операциях. Если У будет играть роль Х в другом матричном умножении, то производительность этого умножения упадет от постолбцового размещения матрицы, поскольку для получения более высокой производительности первая матрица-сомножитель должна храниться в памяти построчно.
Разбиение на блоки Иногда для повышения локальности данных можно изменить порядок выполнения команд. Однако метод перемены циклов не повышает эффективности программы матричного умножения. Предположим, что программа написана так, чтобы считать матрицу Л не по строкам, а по столбцам, т.е.
!тцикл становится внешним, а 1-цикл -- внутренним. В предположении, что матрицы хранятся в памяти, как и ранее, построчно, мы найдем, что теперь у матрицы У наблюдается 11.2. Пример посерьезнее; умножение матриц лучшая временная и пространственная локальность, но это происходит за счет матрицы Х, у которой эти показатели становятся хуже. Другим способом переупорядочения итераций в циклах„который может привести к повышению локальности программы, является разбиение ла блоки, или блокирование (ЫосЫпй). Вместо вычисления результата построчно или постолбцово мы делим матрицу на подматрицы, или блоки, как показано на рис. ! 1.7, и переупорядочиваем операции так, чтобы весь блок использовался в течение короткого промежутка времени. Обычно блоки представляют собой квадраты со стороной длиной В. Если В является делителем п, то все блоки являются квадратами; если не является, то блоки у нижней и правой границы будут меньшего размера.
Рис. 11.7. Матрица, разделенная на блоки размером В На рис. 11.8 показана версия базового алгоритма умножения матриц, в котором все три матрицы разделены на квадратные блоки размером В. Как и на рис. 11.5, считается, что матрица Я инициализирована нулевыми значениями. Мы считаем, что и кратно В; если это не так, то следует изменить строки 4 — 6 так, чтобы верхний предел был равен ппп (гг+ В, п).
Три внешних цикла в строках 1 — 3 используют индексы гг, 22 и кк, которые всегда увеличиваются на В и, таким образом, маркируют левую или верхнюю границу некоторого блока. При фиксированных значениях индексов гг, 22' и И строки 4-7 обеспечивают внесение в блок с верхним левым углом У )1г,22) полного вклада от блоков с верхними левыми углами Х )гг, Ы) и У [кк, д). При корректном выборе размера блоков В можно существенно снизить количество промахов кэша по сравнению с базовым алгоритмом, если матрицы Х, У и Я не помещаются в кэше.
Значение В следует выбирать таким, чтобы можно было разместить в кэше по одному блоку из каждой матрицы. В силу выбранного 932 Глава 11. Оптимизация параллелизма и локальности 1) аког (з 1 2) аког 3) 4) 5) б) 7) — 0; гз < и; гг = гг+В) (3З = О! 33 < и' 33 = 33+В) аког (КК = О! КК < и! КК = КК+В) аког (з = гз; з < аз+В! г++) аког (3 = 33; 3 < 33+В; 3++) ~ог (К = КК; К < КК+В; К++) 2(г,3] = 2(г,3] + Х[г, К]*у[К,3); !'ис. 11.8. Матричное умножение с разбивкой на блоки Другой взгляд на блочное умножение матриц Можно представить, что матрицы Х, У и Я на рис.
11.8 представляют собой не матрицы размером т! х п чисел с плаваюц1ей точкой, а матрицы размером (п7В) х (п7В), элементами которых являются матрицы размером В х В чисел с плавающей точкой. Строки ! — 3 на рис. 11.8 в таком случае аналогичны трем циклам базового алгоритма на рис. 11.5, но для размеров матриц не и, а п(В. Строки 4-7 можно рассматривать как реализацию единой операции умножения и сложения на рис. 11.5. Заметим, что единый шаг умножения представляет собой умножение матриц, которое использует базовый алгоритм на рис. ! 1.5 для чисел с плавающей точкой, являющихся элементами умножаемых матриц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
