А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 188
Текст из файла (страница 188)
Временная локальность означает использование некоторых данных несколько раз за короткий промежуток времени. Пространственная локальность означает, что за небольшой промежуток времени выполняется обращение к данным, находящимся рядом друг с другом. Важным видом пространственной локальности является совместное использование элементов данных из одной строки кэша. Причина такого выделения в том, что когда требуется один элемент из строки кэша, то в кэш загружается вся строка целиком, и, вероятно, все элементы строки будут находиться в кэше до тех пор, пока программа будет постоянно их использовать.
Такая пространственная локальность приводит к минимизации промахов кэша, что, в свою очередь, существенно ускоряет работу программы. Ядра часто могут быть написаны различными семантически эквивалентными способами, существенно отличающимися локальностью данных (и производительностью). В примере 11.2 показан альтернативный способ написания кода, эквивалентного коду из примера 11.1.
921 !!.1. Фундаментальные концепции Пример 11.2. Так же, как и в примере 11.1, данный код находит квадраты разно- сти элементов векторов Х и У; аког(х = О; з < и; з++) [ 2[з] = Х[з.] — У[з.); йот(з = О! т < и! з++) ( К[э] = Я['] * 2['); ) Первый цикл находит разности, второй — квадраты разностей. Код наподобие приведенного — не редкость в реальных программах, поскольку так можно оптимизировать программу для использования на векторных машинах, представляющих собой суперкомпьютеры с командами для выполнения простых арифметических операций над векторами за один раз. В примере 11.1 тела обоих циклов собраны в один.
Обе программы выполняют одни и те же вычисления. Какая же из них будет работать быстрее? Цикл в примере 1! .1 имеет более высокую производительность в силу лучшей локальности данных. Каждая разность возводится в квадрат сразу же после вычисления; более того, разность может быть сохранена в регистре, возведена в квадрат и только затем полученное значение можно записать в ячейку памяти Я [() (в отличие от кода в данном примере, где первая запись Я [г) выполняется существенно ранее его использования). Если размер массива превышает размер кэша, в нашем примере во втором цикле потребуется новая загрузка Я [(] из памяти.
Таким образом, этот код должен работать существенно медленнее, чем код из предыдущего примера. а Пример 11.3. Предположим, что мы хотим установить все элементы построчно хранящегося в памяти массива У (о способах хранения массивов мы уже говорили в разделе 6.4.3) равными О. На рис. 11.3, а и б обнуление элементов выполняется соответственно по столбцам н по строкам. Для получения одного варианта кода из другого его достаточно просто транспонировать. С точки зрения пространственной локальности предпочтительно обнулять массив построчно, поскольку все слова в строке кэша обнуляются последовательно.
В случае постолбцового обнуления, хотя каждая строка кэша повторно используется последовательными итерациями внешнего цикла, строки кэша перед повторным использованием будут сброшены, если размер столбца превышает размер кэша. Для получения наивысшей производительности мы распараллеливаем внешний цикл на рис. 11.3, б так же, как делали это в примере 1!.1 и как показано на рис.
11.3, в. Б Два приведенных выше примера иллюстрируют несколько важных характеристик, относящихся к численным приложениям, работающим с массивами. 922 Глава 11. Оптимизация параллелизма н локальности Ест (Э =01 Э <и; Э++) аког (з = О; Х < и; з++) г(',э) = о; а) Постолбцовое обнуление массива аког (з= О; з<п; з++) йот (э = 0; э < пг э++) 2[',Э) = О; б) Построчное обнуление массива Ь = сез1(п/М)! Гог (з = Ь*р; з < !атп(п,Ь*(р+1)); з++) Гог (э = О! э < п; э++) 2(',Э) = О; в) Распараллеленное построчное обнуление массива Рнс. 11.3.
Последовательный н параллельный коды обнуления элементов массива ° Код для работы с массивом часто содержит много распараллеливаемых циклов. ° Если цикл распараллеливаем, то его итерации могут выполняться в произвольном порядке. Они могут быть переупорядочены, чтобы получить существенное повышение локальности данных.
° При создании больших модулей параллельных вычислений, независимых друг от друга, их последовательное выполнение обычно имеет тенденцию к высокой локальности данных. 11.1.5 Введение в теорию аффинных преобразований Написать корректную и эффективную последовательную программу — дело непростое, но написать корректную и эффективную параллельную программу— дело куда более сложное. Уровень сложности возрастает с уменьшением зернистости параллелизма.
Как мы видели выше, для получения высокой производительности программисты должны особое внимание уделять локальности данных. Исключительно трудна также задача преобразования существующей последовательной программы в параллельную. Очень сложно обнаружить все зависимости в программе, в особенности если эта программа не знакома, как свои пять пальцев. Еше сложнее отладить параллельную программу, что связано с недетерминистическим характером ошибок.
В идеальном случае распараллеливающий 923 11.1. Фундаментальные концепции компилятор автоматически транслирует обычные последовательные программы в эффективные параллельные, оптимизируя при этом их локальность. К сожалению, компиляторы без высокоуровневого знания о приложении могут только сохранить семантику исходного алгоритма, который может плохо поддаваться распараллеливанию. Кроме того, выбор реализации алгоритма программистом может дополнительно ограничить параллелизм программы.
Успешность распараллеливания и оптимизации локальности была продемонстрирована для множества численных приложений на языке гогггап, которые выполняют аффинный доступ к массивам. Отсутствие в языке указателей и соответствующей арифметики облегчает анализ программ. Заметим, что не все приложения используют аффннные обращения к массивам.
Многие численные приложения работают с разреженными матрицами, обращение к которым выполняется косвенно, через элементы другого массива. В этой главе мы остановимся на распараллеливании и оптимизации ядер, состоящих, в основном, из десятков строк. Как продемонстрировано в примерах 11.2 и 11.3, параллелизм и оптимизация локальности требуют выделения отдельных экземпляров циклов и выяснения их взаимоотношения друг с другом. Эта ситуация существенно отличается от анализа потоков данных, при котором мы объединяли в одно целое информацию, связанную с отдельными экземплярами. В задаче оптимизации циклов с обращениями к массивам мы используем три вида пространств. Каждое пространство может рассматриваться как точки одномерной или многомерной структуры.
1. Пространство итераций представляет собой множество динамически выполняемых в процессе вычислений экземпляров итераций, т.е. множество комбинаций значений, которые принимают индексы циклов. 2. Пространапво данных представляет собой множество элементов массива, к которым выполняется обращение. 3.
Пространство процессоров представляет собой множество процессоров в системе. Обычно этим процессорам назначены целочисленные номера или векторы для того, чтобы отличать один процессор от другого. В качестве входных данных мы получаем последовательный порядок, в котором выполняются итерации, и аффинные функции обращения к массивам 1например, Х 11, 1+ 11), которые указывают порядок обращения экземпляров из пространства итераций к элементам пространства данных. Выходные данные оптимизации также представляют собой аффинные функции, определяющие, что и когда должен делать каждый процессор.
Для указания, что должен делать каждый процессор, мы используем аффинную функцию, назначающую процессорам экземпляры из исходного пространства итераций. Для 924 Глава 11. Оптимизация параллелизма и локальности Пример 11.4. На рис. 11.4 проиллюстрированы различные пространства и их взаимоотношения для программы й1оас Е[100]; 1от(1 = 0; 1 , 10; 1++1 Е[1+10] = Е[з.]; Область данных, к которым выполняется обрапзение 9 1О !! 19 20 [] ... рп О 1 Пространство данных Аффинная инлексная функция Пространство итераций Аффинное разбиение Пространство процессоров О 1 Рис.
! 1.4. Просзрансзва изераций, данных и процессоров к примеру 11.4 Три пространства и отображения между ними выглядят следующим образом. 1. Пространство итераций. Пространство итераций представляет собой множество итераций, идентификаторы которых задаются значениями, хранящимися в индексных переменных. Вложение циклов (!оор лез!) глубиной т( (т.е. д вложенных циклов) имеет с( индексных переменных и, таким образом, моделируется д-мерным пространством. Пространство итераций ограничено нижней и верхней границами индексов циклов. В нашем примере определения, когда он должен это делать, используется аффинная функция, отображающая экземпляры из пространства итераций в новое упорядочение.
План порождается путем анализа зависимостей данных и шаблонов использования в функциях обращения к массивам. В приведенном ниже примере демонстрируются три описанные пространства — итераций, данных и процессоров. В нем также неформально описываются важные концепции и вопросы, которые должны быть решены при использовании данных пространств для распараллеливания кода. Все эти концепции будут детально рассмотрены в последующих раздела~.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
