А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 197
Текст из файла (страница 197)
третий индекс, /с, может быть любым. Таким образом, решением приведенного выше уравнения является любой вектор [1, — 1, т] для некоторого гп. Иначе говоря, динамическое обращение к А [з, 1, г + Я во вложенности циклов с индексами з, у' и lс повторно используется не только другим динамическим обращением А [з,у, з + Я с теми же индексами з и у и другим й, но и динамическим обращением А (т + 1,1' — 1, з + у] с индексами т + 1, у — 1 и любым й.
а 4 Интересно заметить, что хотя в данном случае решение имеется, его не будет при замене одного из третьих компонентов 1+ у иа 1+ у -Ь 1, те. в данном примере оба обрашения работают с теми злементами массивов, которые лежат в двумерном подпространстве Я, определяемом как "третий компонент равен сумме первых двух". Если же заменить 1+ у на з + у + 1, то ни один из элементов второго обращения не будет лежать в 5, и повторное использование будет отсутствовать как таковое. Другими словами, уз = уз и зз = зг+ 1. Заметим, что повторное использование наблюдается вдоль з'-оси пространства итераций, т.е. итерация (тз,уз) встречается через п итераций (внутреннего цикла) после итерации (11, уз). Таким образом, перед повторным использованием записанных данных проходит много времени.
Эти данные могут к тому времени оказаться удаленными из кэша. Если кэш хранит две последовательные строки матрицы л., то обращение У [з — 1, Я не приводит к промаху кэша и обгцее количество промахов во всей вложенности циклов составляет пз/с, где с — количество элементов в строке кэша.
В противном случае количество промахов удваивается, так как оба статических обращения требуют новой строки кэша для каждых с динамических обращений. а 962 Глава 11, Оптимизация параллелизма и локальности Хотя здесь мы этого и не делаем, мы можем провести аналогичные рассуждения и для группового пространственного повторного использования. Как и при рассмотрении собственного пространственного повторного использования, мы просто убираем из рассмотрения последнее измерение. Величина повторного использования различна для разных категорий.
Собственное временное повторное использование дает наибольшие преимущества: Й-мерное нуль-пространство приводит к повторному использованию одних и тех же данных О (и") раз. Величина собственного пространственного повторного использования ограничена длиной строки кэша. И наконец, величина группового повторного использования ограничена количеством обращений в группе. 11.5.5 Упражнения к разделу 11.5 Упражнение 11.5.1. Вычислите ранг каждой из матриц на рис. 11.20. Укажите для них максимальное множество линейно независимых столбцов и максимальное множество линейно независимых строк. 0 1 5 1 2 3 4 1 2 6 5 6 7 8 2 3 7 9 10 12 15 3 4 8 3 2 2 3 0 0 1 0 1 1 1 1 1 5 6 3 а) б) в) Рис.
11.20. Вычислите ранги и нуль-пространства этих матриц Упражнение 11.5.2. Найдите базис нуль-пространства для каждой из матриц, представленных на рис. 11.20. Упражнение 11.5.3. Предположим, что пространство итераций имеет размерно- сти (переменные) 1, 1 и к. Для каждого из приведенных далее обращений опишите подпространства, которые обращаются к одному элементу массива: а) А [1,1,1+Я; б) А [г, 1+ 1, 1 + 2[; 1в) А[с,г,у+1]; ! г) А [1 — 1,1 — )с,)г — 1!. ! Упражнение 11.5.4.
Предположим, что к построчно хранящемуся в памяти массиву А выполняются обращения из следующей вложенности циклов: 963 ! !.5. Повторное использование данных аког(г = 0; г <= 100; г++) аког(э О э<100!3++) аког()с = 0; )с <= 100! )с++) <Некогорое обращение к А> Для каждого из приведенных далее обращений укажите, можно ли переписать циклы так, чтобы обрагцение к А демонстрировало собственное пространственное повторное использование, т.е.
последовательно использовались строки кэша целиком. Покажите, как именно следует переписать циклы, если это возможно. Примечание: переписывание циклов может включать как их перестановку местами, так и введение новых индексов циклов. Однако изменить схему размегцения данных массива вы не можете: массив не может стать постолбцовым. Еще одно примечание: в общем случае переупорядочение индексов может быть допустимым и недопустимым, в зависимости от критериев, которые будут рассматриваться в следующем разделе. Однако в данном случае, когда каждое обращение состоит просто в присваивании нулевого значения, вам не надо беспокоиться о влиянии переупорядочения циклов на программу с точки зрения семантики. а) А[г+1,з.+)с,3] = 0 !! б) А[3+)с, 1, г] = 0 в) А[г, 3, )с, 1.+3+)с] = 0 !! г) А[3., 3 )с, г+3, г+)с] = 0 Упражнение 11.5.5. В разделе 1!.5.3 говорилось, что пространственная локальность достигается в том случае, когда в наиболее глубоко вложенном цикле изменяется только последняя координата массива, к которому выполняется обращение.
Однако это утверждение зависит от нашего предположения, что массив хранится построчно. Как будет звучать данное утверждение при постолбцовом хранении массива в памяти? ! Упражнение 11.5.6. В примере 1!.28 мы видели, что наличие повторного использования между двумя схожими обращениями сильно зависит от конкретных выражений для координат массива. Обобщите это наблюдение для определения того, для каких функций 1[(,2) существует повторное использование между обращениями А [г, ),1+ Я и А [1 + 1, ! — 1, ( (г, 5)[. ! Упражнение 11.5.7.
В примере 11.27 мы предположили, что если строки матрицы У будут такими большими, что не будут помещаться в кэше, то количество промахов кэша станет больше необходимого. Если матрица г, обладает указанным свойством, как можно переписать вложенность циклов для обеспечения группового пространственного повторного использования? 964 Глава 11. Оптимизация параллелизма и локальности 11.6 Анализ зависимости данных в массивах Распараллеливание и оптимизация локальности часто меняют порядок операций, выполняемых исходной программой.
Как и в случае любой оптимизации, изменение порядка операций не должно влиять на выход программы. Поскольку в общем случае невозможно точно определить, что именно делает программа, оптимизация кода обычно использует простые, консервативные тесты, которые позволяют гарантировать, что выход программы остается неизменным: мы убеждаемся, что операции с любой ячейкой памяти выполняются в одном и том же порядке как в исходной, так и в оптимизированной программах. В этом разделе мы сосредоточимся на работе с массивами, т.е.
рассматриваемыми ячейками памяти являются элементы массивов. Два обращения — не важно, для чтения или для записи — являются независимыми (т.е. могут быть переупорядочены), если они обращаются к разным ячейкам памяти. Кроме того, операции чтения не изменяют состояние памяти, а потому также являются независимыми. Как и в разделе 11.5, мы говорим, что два обращения зависимы через данные (г)ага г)ерепг)еп1), если они обращаются к одной и той же ячейке памяти и хотя бы одно из них является операцией записи. Чтобы гарантировать, что модифицированная программа делает то же, что и исходная, относительный порядок выполнения каждой пары зависимых через данные операций в новой программе должен быть сохранен.
Вспомним из раздела 10.2.1, что существует три вида зависимостей через данные. 1. Истинная зависимость. За записью следует чтение из той же ячейки памяти. 2, Антиэависимость. За чтением следует запись в ту же ячейку памяти. 3. Зависимость через выход. Выполняются две записи в одну и ту же ячейку памяти. Ранее зависимости данных определялись для динамических обращений. Мы говорим о том, что статическое обращение зависит от другого статического обращения, если существует динамический экземпляр первого обращения, который зависит от некоторого экземпляра второго обращения.з Легко видеть, как зависимости данных могут использоваться при распараллеливании. Например, если между обращениями в цикле не обнаружено никаких зависимостей, можно легко назначить каждую итерацию отдельному процессору.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
