А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 185
Текст из файла (страница 185)
Узлы графа соответствуют командам. Ребро от узла гп к узлу и с меткой а означает, что команда т должна начаться не ранее чем через а тактов после начала команды п. + Приоритетный топологический порядок. Графы зависимостей данных для базовых блоков всегда ацикличны, и обычно у такого графа имеется много вариантов топологических порядков. Для выбора предпочтительного топо- логического порядка данного графа может использоваться ряд эвристик, например, выбор, в первую очередь, узлов с наибольшими критическими путями. + Планирование списка. Имея приоритетный топологический порядок для графа зависимости данных, мы можем рассматривать узлы этого графа 908 Глава 1О. Параллелизм на уровне команд в указанном порядке. При этом планирование каждого узла в самый ранний из возможных тактов согласуется с временными ограничениями, накладываемыми ребрами графа, планами всех ранее спланированных узлов и ограничениями, связанными с ресурсами машины.
+ Перемещение кода мезкду блоками. При определенных обстоятельствах оказывается возможным перемещение инструкций из блока, в котором они изначачьно размещены, в предшествующий или последующий блок. Преимущества такого перемещения в том, что в новом месте инструкция сможет выполняться параллельно с другими, что невозможно в ее исходном местоположении. Если новое и старое местоположения не связаны отношением доминирования, то вдоль некоторых путей может потребоваться вставка компенсирующего кода, чтобы гарантировать выполнение одной н той же последовательности команд независимо от потока управления.
+ Универсальные циклы. Универсальные циклы не имеют зависимостей меж- ду итерациями, так что любые итерации могут выполняться параллельно. + Программная конвейеризация универсальных циклов. Программная конвейеризация представляет собой метод использования возможностей машины по одновременному выполнению нескольких команд. Итерации цикла планируются таким образом, что они запускаются одна за другой через малые промежутки времени с возможным добавлением команд "нет операции" с целью избежать конфликтов, связанных с ресурсами машины. В результате код цикла может быть выполнен очень быстро и состоять из пролога, эпилога и небольшого внутреннего цикла.
+ Перекрестные циклы. Большинство циклов имеют зависимости данных между итерациями. Такие циклы называются перекрестными. + Графы зависимостей данных для перекрестных циклов. Для представления зависимостей между командами перекрестного цикла ребра должны помечаться парами значений: необходимой задержкой (как в случае графов, представляющих базовые блоки) и количеством итераций между двумя зависимыми командами. + Планирование списка для циклов. Для планирования циклов следует для всех итераций выбрать один план, а также интервал между запусками итераций. Алгоритм включает выведение ограничений на относительные планы различных команд цикла путем поиска наидлиннейших ациклических путей между двумя узлами.
Длины этих путей используют интервал между запусками итераций в качестве параметра, что позволяет определять нижнюю границу данного интервала. 909 !0.7. Список литературы к главе !О 10.7 Список литературы к главе 10 Желающим более глубоко ознакомиться с архитектурой и проектированием процессоров, мы рекомендуем книгу Хеннесси (Неппеззу) и Паттерсона (Рапегаоп) [5). Концепция зависимости данных появилась в работах Кука (Кцс)с), Мураоки (Мцгао)са) и Чена (СЬеп) [6) и Лампорта (Ьашрог!) [8) в контексте компиляции кода для многопроцессорных н векторных машин. Планирование команд впервые было применено при планировании одноуровневого микрокода [2, 3, 11, 12).
Работа Фишера (Р!аЬег) по уплотнению микрокода привела его к концепции тгП%-машины, в которой компилятор мог непосредственно управлять параллельным выполнением операций [3). ! росс (бгоза) и Хеннесси (Неппсаау) [4) использовали планирование команд для обработки отложенных ветвлений в первых наборах команд М1РБ К1БС. Алгоритм из данной главы основан на более общем подходе Бернштейна (Вегпвгеш) и Родега (Ног(еЬ) [1) к планированию операций для машин с параллелизмом на уровне команд. Основная идея, лежащая в основе программной конвейеризации, была изначально разработана Пателем (Раге!) и Дэвидсоном (Рачк)хоп) [9) для планирования аппаратных конвейеров.
Программная конвейеризация впервые использована Рау (Кап) и Глезером (б1аезег) [1О) в компиляции для машины со специально разработанной аппаратной поддержкой программной конвейеризации. Описанный в главе алгоритм основан на работе Лама (1.аш) [7), в которой специализированная аппаратная поддержка не предусматривалась.
1. Вегпа!е!и, Р, апд М. Кос$еЬ, "б!оЬа) !пз!госйоп зсЬедц1!п8 Гог зпрегзса1аг тас!з!поз", Ргос. АСМ ЯБРЕАИ 199! Соп!егепсе оп Ргодгатт!пд Еап8иаде Реядп апг! 1тр1етепга!!оп, рр. 241 — 255. 2. Раздцрга, К, "ТЬс огйап!ха!!оп о( пнсгоргойгаш в!огсз", Сотрийпд Лиг еуз 11:1 (1979), рр. 39-65. 3. Р!зйег, 1. А., "Тгасе зсЬег(ц(!п8: а !есЬпн(пе Гог 81оЬа! ш!сгосог!е сошрасгюп", 1ЕЕЕ Тгапж оп Сотршет С-30:7 (198 !), рр. 478 490.
4. бгоаз, Т. К. апд Неппеазу, !. 1, "Орг!ш!х!п8 де!ауег! ЬгапсЬея", Ргоа 15гп Атша! Ибг!сгйор оп М!сгоргодгатт!п8 (1982), рр. 114 — 120. 5. Неппезау, !. 1, апд Р. А. Ра!гегзоп, Сотригег Агсй!гесгигег А Яиапг!гаг!те Арргоасп, ТЬ!гг) Ейгюп, Могйап Кацйпап, Бап Ргапс!асс, 2003. 6. Кцс)с, Р., г'. Мпгао)га, апг! К СЬеп, "Оп гЬе пшпЬег о( орегабопз з)пш1!апеопз1у ехесцгаЫе !и Рогггап-!Йе ргойгашз апг! !Ье!г геац1йп8 ареег!пр", 1ЕЕЕ Тгапк оп Сотригет С-21: 12 (1972), рр. 1293 — 1310. 910 Глава 1О. Параллелизм на уровне команд 7.
1.агп, М. 8., "Бочаге р(ре11п!п8: ап е1Тесбче ксЬегЫ!п8 гесЬпщпе Гог л).1% пзасЬ!пел", Ргос. АСМ ЯбРЕАЖ !9ВВ Соп~егепсе оп Рюдтатт!пд йап8иа8е Оее!8п аш! !тр!етепгайоп, рр. 318 — 328. 8. 1 агпрогг, 1., "ТЬе рагаПе! ехеспг)оп оГ РО 1оорв", Сотт. АСМ 17:2 (1974), рр. 83-93. 9. Рагс!, 3. Н. апд Е. Я. Раин(коп„"!пзргоч)п8 гЬе гЬгоп8Ьрпг оГ а р!ре11пе Ьу !пвегг)оп оГ де!аул", Ргос. ТЫгг! Аппиа! Бутроегит оп Сотригег Агс!г!!ее!иге (1976), рр. 159-164. 10. Гхап, В. К. апг! С.
Р. б!аевег, "хогне лсЬейн!1п8 1есЬп)г!пел апд ап еая1у всЬедп!аЫе Ьогглопга( агсЬЬесгпге Гог Ь!8Ь регТоппапсе кс)еп66с сопзрпг!пд", Рюс. !4Й Аппиа! ИогЕгбор оп М!сгорго8гатт!пгг (1981), рр. 183 — 198. ! 1. То!гого, М., Е. Тагпшга, апд Т. Та!с!лйа, "Ор6пз!хагюп оГ ппсгорго8гапзл", !ЕЕЕ Тгапл. оп Сотригепг С-30:7 (1981), рр. 491 — 504.
!2. %под, 6., "61оЬа! ор6ппга6оп оГ ппсгорго8гапгв гЬгоп8Ь пюдп1аг соппо! сопвГпзсгв", Рюс. !2й Аппиа! ИЬг!сговор 1п М!сгоргоВгаттид (1979), рр. 1 — 6. ГЛАВА 11 Оптимизация параллелизма и локальности Из этой главы вы узнаете о том, каким образом компилятор может повысить степень параллельности вычислений и локальность численных программ с целью повышения их производительности при работе в многопроцессорных системах. Многие научные, инженерные и коммерческие приложения переполнены вычислениями, выполняемыми в цикле.
Примерами могут служить метеорологические программы, программы для аэрогидродинамических расчетов, программы квантовой хромодинамики для изучения сильных взаимодействий в физике высоких энергий и многие другие. Одним из способов ускорения вычислений является их параллельность. К сожалению, не так легко разработать программное обеспечение, которое будет использовать преимущества параллельной работы на нескольких машинах.
Разделение вычислений на отдельные модули, которые могут выполняться параллельно на нескольких процессорах, — достаточно сложная задача; к тому же такое разделение само по себе не гарантирует ускорение вычислений. Следует также минимизировать межпроцессорное взаимодействие, поскольку связанные с ним накладные расходы легко могут сделать выполняющийся параллельно код более медленным, чем обычный последовательный. Минимизация взаимодействия может рассматриваться как частный случай повышения локальности данных (г1ага!осай1у) программы.
В общем случае мы говорим о хорошей локальности данных программы, если чаще всего процессор обращается к тем же данным, к которым он уже обращался в последнее время. Само собой разумеется, если процессор на работающей параллельно машине сталкивается с высокой локальностью, у него не возникает необходимости в частом общении с другими процессорами. Таким образом, параллельность и локальность должны рассматриваться вместе.
Локальность данных важна для производительности отдельного процессора и сама по себе. Современные процессоры оснащены одним или несколькими уровнями кэшей в иерархии памяти, при этом обращение к основной памяти может занимать десятки тактов, в то время как обращение к кэшу выполняется за несколько тактов. Если программа имеет плохую локальность и часто сталкивается с промахами кэша, ее производительность будет снижена. 912 Глава 11. Оптимизация параллелизма и локальности Еше одна причина, по которой параллельность и локальность рассматриваются вместе, в одной главе, заключается в том, что они используют одну и ту же теорию.
Если мы знаем, как оптимизировать программу для повышения локальности данных„мы также знаем, как поднять степень ее параллелизма. В этой главе вы увидите, что программная модель, использовавшаяся нами при анализе потоков данных в главе 9, неадекватна в случае оптимизации параллелизма и локальности. Причина этого в том, что при работе с потоками данных считалось, что мы не различаем, каким именно образом достигнута данная инструкция; рассматривавшиеся в главе 9 методы использовали тот факт, что разные выполнения одной и той же инструкции неразличимы, например, при выполнении цикла. Для распараллеливания кода мы должны рассматривать зависимости между различными динамическими выполнениями одних и тех же инструкций, чтобы определить, могут ли они выполняться одновременно разными процессорами. В этой главе внимание сосредоточено на методах оптимизации класса численных приложений, которые работают с массивами и обрашаются к ним с использованием простых регулярных шаблонов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
