Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

Процессоры, способные одновременно и независимо выполнять несколько команд, обладают исключительно высоким потенциалом производительности и находят все более широкое применение. О процессорах такого типа говорят, что они поддерживают параллелизм на уровне команд (Instruction Level Parallelism, ILP). Далее для краткости они будут называться ILP-процессорами. Класс ILP-процессоров включает суперскалярные процессоры и процессоры с очень длинным командным словом (Very Large Instruction Word, VLIW), к числу которых относятся, в частности, многие модели цифровых процессоров обработки сигналов (ЦПОС).

Важное преимущество ILP по сравнению с параллелизмом многопроцессорных архитектур заключается в том, что программный параллелизм на уровне команд извлекается (аппаратурой или компилятором) автоматически, без дополнительных усилий со стороны прикладных программистов, в то время как использование параллелизма многопроцессорных архитектур подразумевает переписывание приложений.

Для реального использования высокой производительности ILP-процессоров необходимы компиляторы с языков высокого уровня, способные генерировать эффективный код. Применение одних лишь традиционных методов оптимизации кода оказывается совершенно недостаточным. Например, согласно [3] или [41], типичный компилятор для ЦПОС (поддерживающий только традиционные оптимизации) генерирует код, который по времени выполнения может уступать оптимальному в 5-10 и более раз.

В течение последних лет прилагаются значительные усилия по разработке специальных методов оптимизации программ для ILP-процессоров, направленных на выявление и расширение программного параллелизма на уровне команд. Настоящая работа содержит обзор таких методов.

В разделе 2 дается краткий обзор ILP-процессоров и их основных характеристик. Раздел 3 посвящен критериям оптимизации кода для ILP-процессоров. В разделе 4 представлена примерная схема работы компилятора, характеризуются основные задачи, связанные с оптимизацией кода для ILP-процессоров. В разделе 5 дается обзор способов формирования областей (фрагментов компилируемой программы), в рамках которых возможно эффективное распараллеливание. В разделе 6 описываются методы оптимизации, направленные на усиление внутреннего программного параллелизма в рамках выделенных областей. В разделе 7 рассматриваются методы распараллеливания кода в предварительно выделенных областях. Раздел 8 посвящен специфике оптимизации кода для ЦПОС. В разделе 9 приводится информация о языковых расширениях и их роли в увеличении эффективности процессоров. В заключении (раздел 10) представлены некоторые из актуальных нерешенных до настоящего время проблем оптимизации кода для ILP-процессоров.