А.В. Ахо, М.С. Лам, Р. Сети, Дж. Д. Ульман - Компиляторы - принципы, технологии и инструментарий (1114947), страница 171
Текст из файла (страница 171)
Вопрос "на засыпку": насколько быстро может выполняться программа на процессоре с параллелизмом на уровне команд? Ответ зависит от нескольких факторов. Е Потенциальный параллелизм программы. 2. Доступный параллелизм процессора. 3. Наша способность выделить параллелизм в исходной последовательной программе. 4. Наша способность найти наилучшее планирование параллельного выполнения при заданных ограничениях планирования.
Если все операции в программе сильно зависят одна от другой, то никакая аппаратная параллельность или методы распараллеливания не ускорят выполнение программы. Была выполнена масса исследовательских работ, посвященных лучшему пониманию, что может дать параллельность и где находятся границы ее применимости. Типичное не численное приложение содержит массу неотьемлемых зависимостей. Например, в таких программах много ветвлений, зависящих от данных, и эти ветвления затрудняют даже предсказание того, какие именно команды будут выполняться, не говоря уже о том, чтобы решать, какие команды могут выполняться параллельно. Следовательно, работа в этой области должна быть сосредоточена не столько на методах планирования, сколько на ослаблении ограничений планирования, включая добавление новых архитектурных возможностей. Численные приложения, такие как научные расчеты и обработка сигналов, обычно допускают большую степень распараллеливания.
Эти приложения работают с большими агрегированными структурами данных; зачастую операции над различными элементами структуры не зависят одна от другой и могут выполняться параллельно. Дополнительные аппаратные ресурсы могут использовать преимушества этой параллельности, так что они часто применяются в высокопроизводительных машинах общего назначения и процессорах для цифровой обработки сигналов. Обычно в таких программах используются простые управляющие 842 Глава 1О. Параллелизм иа уровне команд структуры и регулярные шаблоны обращения к данным, так что для выделения параллельности в таких программах разработаны различные статические методы.
Планирование выполнения кода для таких приложений представляет собой интересную и важную задачу, в которой большое количество независимых операций отображается на большое количество ресурсов. Как выделение параллелизма, так и планирование параллельного выполнения может быть выполнено либо статически программным обеспечением, либо динамически — аппаратным.
В действительности программное планирование может помочь даже при использовании машин с аппаратным планированием. Эта глава начинается с рассмотрения фундаментальных вопросов использования параллелизма на уровне команд, которые одинаковы как при аппаратном, так и при программном управлении параллелизмом. Затем мы рассмотрим основы анализа зависимости данных, необходимого для выделения параллелизма. Эти виды анализа полезны не только для параллелизма на уровне команд, но и, как вы увидите в главе 11, для других оптимизаций. Наконец, мы представим основные идеи планирования кода. Мы опишем методы планирования базовых блоков, метод работы с управлением потоком, сильно зависящим от данных (ситуация, распространенная в программах общего назначения), и метод программной конвейерной обработки, используемый, в первую очередь, для планирования численных программ.
10.1 Архитектуры процессоров Когда мы говорим о параллелизме на уровне команд, то обычно представляем процессор, выполняющий несколько команд за один такт. В действительности возможна машина, выполняющая за один такт только одну операцию, но при этом достигающая параллелизма на уровне команд благодаря использованию концепции конвейерной обрабоаки (р)ре!ш)п8), Далее мы сначала рассмотрим конвейерную обработку, а затем — многоадресные команды. 10.1.1 Конвейерная обработка команд и задержки ветвления Практически каждый процессор — будь то в высокопроизводительной супермашине или в обычном настольном компьютере — использует конвейер (обработки) команд (1пя1гцс1(оп р)ре!1пе).
При использовании конвейера команд выборка новой команды може~ выполняться в то время, когда предыдущая команда все еще находится в конвейере. На рис. 10.1 показан простой пятиэтапный конвейер команд, который сначала выполняет выборку команды (1Е), затем — ее декодирование (1П), выполняет команду (ЕХ), обращается к лама~и (МЕМ) н записывает результат (%В). На диаграмме показано, как одновременно могут выполняться 843 10.1.
Архитектуры процессоров команды г, 1 + 1, 1 + 2, 1 + 3 и 1 + 4. Каждая строка соответствует такту систем- ных часов, а каждый столбец на рисунке определяет, когда выполняются этапы каждой из команд. 1+3 1+4 1 1+1 1+2 1. 1Г 2. П) 1Г 3. ЕХ 111 1Е 4. М ЕМ ЕХ 1О 5. %В МЕМ ЕХ 6. %В МЕМ 7. %В 8. 9. 1Е 1О 1Г ЕХ 113 МЕМ ЕХ %В МЕМ %В Рнс.
10.1, Пять последовательных команд в пятнэтапном конвейере команд 10.1.2 Конвейерное выполнение Некоторые команды требуют для выполнения нескольких тактов. Распространенным примером может служить команда загрузки из памяти. Даже если память, к которой выполняется обращение, находится в кэше, обычно требуется несколько тактов для того, чтобы получить данные из кэша. Мы говорим, что выполнение команды конвейерное (р1ре11пео), если может выполняться следующая команда, которая не зависит от результата предыдущей.
Таким образом, даже если процессор может выполнять только одну операцию за такт, одновременно на разных стадиях выполнения могут находиться несколько команд. Если конвейер содер- Если результат команды доступен в тот момент, когда последующая команда нуждается в данных, процессор может выполнять по команде каждый такт. Выполнение команд ветвления особенно проблематично, поскольку, пока они не будут выбраны, декодированы и выполнены, процессору неизвестно, какая команда будет выполняться следующей. Многие процессоры умозрительно выбирают и декодируют непосредственно следующие друг за другом команды, пока не встречается команда ветвления.
Если же в потоке обнаруживается команда ветвления, конвейер опустошается, и выполняется выборка целевой команды ветвления. Таким образом, ветвления вносят задержку в выборку целевой команды и приводят к "иканию" конвейера. Мощные интеллектуальные процессоры используют аппаратное предсказание результата ветвления на основе истории выполнения и выполняют упреждающую выборку из предсказанной целевой ячейки памяти. Тем не менее при неверном предсказании задержки ветвления наблюдаются и в таких процессорах. 844 Глава 1О. Параллелизм на уровне команд жит и этапов, то потенциально "в полете" могут находиться одновременно п команд.
Заметим, что не все команды полностью конвейеризуемы. В то время как сложения и умножения чисел с плавающей точкой зачастую полностью конвейеризуемы, более сложное и менее часто используемое деление чисел с плавающей точкой таковым зачастую не является. Большинство процессоров общего назначения динамически определяют зависимости между последовательными командами и автоматически приостанавливают выполнение команды в случае недоступности ее операндов. Некоторые процессоры, в особенности встраиваемые в портативные устройства, оставляют проверку зависимостей программному обеспечению по соображениям простоты и снижения энергопотребления процессора. В этом случае компилятор отвечает за вставку в код команд "нет операции" там, где необходимо гарантировать доступность результатов предыдущей операции.
10.1.3 Многоадресные команды Выполняя несколько операций за такт, процессор может одновременно работать с еще ббльшим количеством команд. Наибольшее количество одновременно выполняемых операций может быть вычислено путем умножения количества предварительно обрабатываемых команд на среднее количество этапов конвейера выполнения. Подобно конвейеру, параллельность на многокомандных машинах может управляться как аппаратно, так и программно. Машины с программной обработкой параллельности известны под аббревиатурой РХГИ' (Чегу 1.оп8 1пз~п~с11оп Ъоп1— архитектура процессора с командными словами очень большой длины); машины же с аппаратной обработкой известны под названием сулерскалярньп.
ЧЪ.РМ- машины, как следует из их названия, имеют команды большого размера, которые кодируют операции, выполняющиеся за один такт. Компилятор решает, какие операции будут выполняться параллельно, и явно указывает эту информацию в машинном коде. Суперскалярные же машины автоматически обнаруживают зависимости между командами и выполняют команды, как только их операнды становятся доступными. Некоторые процессоры включаю~ как ЧЕНЧ, так н суперскалярную функциональность. Простые аппаратные планировщики выполняют команды в том порядке, в котором выполняется их выборка. Если планировщик обнаруживает зависимую команду, она и все последующие должны дождаться, пока зависимости не будут разрешены (то есть пока не станут доступны все требующиеся результаты выполнения предыдуших команд). Очевидно, что таким машинам выгодна работа со статическим планировщиком, который размещает независимые операции одна за другой в порядке выполнения.
845 !0.2. Ограничения планирования кода Более сложные планировщики могут выполнять команды "не по порядку". Операции независимо приостанавливаются и не выполняются до тех пор, пока не будут получены все значения, от которых эти операции зависят. Но статические планировщики могут помочь в работе даже столь интеллектуальным планировщикам, поскольку аппаратные планировщики ограничены объемом памяти, в котором могут храниться отложенные операции. Статический же планировщик может разместить независимые операции поближе одна к другой с тем, чтобы более эффективно использовать аппаратные возможности процессора.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
