О роли языковых расширений
В различных реализациях компиляторов с языка Си для ILP-архитектур делаются попытка отразить на уровне входного языка специфику этих процессоров и особенности программирования для них ([14], [33]). Операции над комплексными, векторными, матричными данными, явно выраженные в терминах исходного языка, могут быть непосредственно отражены в эффективные связки команд ILP-процессоров.
Комплексный тип данных зафиксирован в последнем стандарте языка Си [37]:
#include <complex.h>
complex float x, y = 1.0 + 3.0 * I;
Для комплексного типа определен набор обычных операций и библиотечных функций.
Векторные и матричные операции, привлекательные с точки зрения возможности напрямую использовать параллелизм на уровне команд, к сожалению, плохо “встраиваются” в синтаксис языка Си, поскольку имена массивов трактуются как описатели. Поэтому, например, в стандарте ANSI Numerical C, разработанном группой NCEG (Numerical C Extension Group) для численных приложений, введены понятия итератора и оператора суммирования, отражающие семантику матричных операций.
Пример описания и использования итератора:
iter I = N;
A[I] = sin (2 * PI * I / N)
Этот фрагмент программы эквивалентен следующему тексту на стандартном Си:
int i;
for (i = 0); i < N; i++)
{
A[i] = sin (2 * PI * i / N);
}
Пример вычисления произведения матриц с использованием итераторов и операторов суммирования:
iter I=N, J=N, K=N;
A[I][J] = sum (B[I][K] * C[K][J]);
Суммирование здесь производится по итератору K. В общем случае суммирование проводится по всем свободным итераторам, т.е. итераторам, которые не встречаются в том же итераторе вне оператора суммирования.
В работе [33] также предлагаются некоторые другие расширения, отражающие специфику ЦПОС – пространства памяти, циклические буферы.
Положительные стороны такого рода расширений — краткость и естественность исходных текстов, возможность эффективно отобразить высокоуровневые операции в оптимальный для заданной целевой платформы код.
Заключение
Круг вопросов, связанных с генерацией эффективного кода для ILP-архитектур, охватывает проблемы формирования областей планирования, снятия зависимостей по данным и по управлению, алгоритмы планирования (распараллеливания) кода, соотношение между планированием и распределением регистров.
Несмотря на обилие уже разработанных и опробованных подходов, создание эффективного компилятора для ILP-процессора в каждом конкретном случае остается непростой задачей. Сложность проблемы связана отчасти с тем, что эффективность практически всех методик существенно зависит как от аппаратных особенностей процессора (степень параллелизма, количество регистров, поддержка условного и упреждающего исполнения), так и от характера компилируемых программ (планирование в расширенных областях наиболее эффективно для программ управляющего характера; в программах вычислительного характера эффект от их применения менее значителен).
Наиболее сложной, по-видимому, остается проблема генерации эффективного кода для ЦПОС. Для VLIW-процессоров с регулярной организацией командного слова основным препятствием к распараллеливанию команд является недостаточность программного параллелизма, поэтому усилия разработчиков компиляторов для них направлены, в основном, на его повышение (за счет расширения областей планирования и снятия зависимостей по данным и по управлению). При успешном решении этой задачи быстрые алгоритмы эвристического списочного планирования могут давать приемлемые результаты. В ЦПОС, в силу нерегулярности кодирования, распараллеливание команд затрудняется, в первую очередь, многочисленными сложными ограничениями кодирования. Поэтому для них необходимы более сложные и трудоемкие переборные методы, такие как [45] или [29]. В связи с этим особый интерес представляет разработка практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков.
Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы.
Преобразования циклов, направленные на усиление программного параллелизма – развертка циклов, слияние и разбивка циклов, конвейеризация циклов.
Преобразования, направленные на ослабление зависимостей по данным – перемещение кода, переименование регистров, дублирование переменных суммирования в циклах и др.
Применение методов глобального планирования потока команд на основе алгоритма списочного планирования.
Использования аппаратных средств поддержки упреждающего выполнения и упреждающего чтения данных.
Совмещение планирования команд и распределения регистров.
Применение локального планирования на основе целочисленного линейного программирования;
Реализация языковых расширений.
При выборе конкретных методов и их параметров необходимо учитывать уровень аппаратного параллелизма и другие особенности целевого процессора, а также характер типичных приложений.
Благодарности
Автор выражает благодарность Виктору Зиновьевичу Шнитману и Андрею Геннадьевичу Шадскому за полезные консультации.
Литература
Ахо А., Сети Р., Ульман Д., Компиляторы: принципы, технологии и инструменты. – М., Издательский дом "Вильямс", 2001.
Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, том 2. - М., Мир, 1978.
Балашов В.В., Капитонова А.П., Костенко В.А., Смелянский Р.Л., Ющенко Н.В. Метод и средства оценки времени выполнения оптимизированных программ. - Программирование #5, 2000, c. 52 61.
Вьюкова Н.И., Галатенко В.А., Самборский С.В., Шумаков С.М. Описание VLIW-архитектуры в оптимизирующем постпроцессоре. М.: НИИСИ РАН, 2001.
Дорошенко А.Ю., Куйвашев Д.В. Архитектура модульного кросс компилятора для микропроцессоров с очень длинным командным словом. - Проблемы программирования, 2000 г., N 3-4, с. 122-134 (на укр. языке).
Дорошенко А.Ю., Куйвашев Д.В. Интеллектуализация векторизующих компиляторов для микропроцессоров с длинным командным словом. - Проблемы программирования, 2001 г., N 1-2, с. 138-151 (на укр. языке).
Евстигнеев В.А. Некоторые особенности программного обеспечения ЭВМ с длинным командным словом (обзор). - Программирование, 1991, N 2, стр. 69-80.
Ершов А.П. Введение в теоретическое программирование. - М., Наука, 1977.
Калашников Д.В., Машечкин И.В., Петровский М.И. Планирование потока инструкций для конвейерных архитектур. - Москва, МГУ, Вестник Московского университета, серия 15 (вычислительная математика и кибернетика), N4, 1999, с. 39-44.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. - М., Мир, 1985.
Скворцов С.В. Оптимизация кода для суперскалярных процессоров с использованием дизъюнктивных графов. - Программирование 1996, N 2, стр. 41-52.
Французов Ю.А. Обзор методов распараллеливания кода и программной конвейеризации. - Программировние, 1992, N 3, стр. 16-37.
Шланскер М.С., Рау Б.Р. Явный параллелизм на уровне команд. Открытые Системы, #11-12, 1999.
ADSP-21000 Family. C Tools Manual. - Analog Devices, Inc. http://www.analog.com/publications/documentation/CTools_manual/books.htm
Allen J.R., Kennedy K., Porterfield C., Warren J.D. Conversion of Control Dependence to Data Dependence. Proceedings of the 10th ACM Symposium on Principles of Programming Languages. Jan. 1983, pp. 177-189.
Araujo G., Malik S. Optimal Code Generation for Embedded Memory Non-Homogeneous Register Architectures. - 8th Int. Symp. on System Synthesis (ISSS), 1995, pp. 36-41.
Araujo G., Malik S., Lee M. Using Register-Transfer Paths in Code Generation for Heterogeneous Memory-Register Architectures. - In ACM IEEE Design Automation Conference (DAC), number 33, pp. 591-596, June 1996.
Banerjia S., Havanki W.A., Conte T.M. Treegion Scheduling for Highly Parallel Processors. - Proceedings of the 3rd International Euro-Par Conference (Euro-Par'97, Passau, Germany), pp. 1074-1078, Aug. 1997.
Benitez M. E., Davidson J. W. Target-specific Global Code Improvement: Principles and Applications. - Technical Report CS-94-42, Department of Computer Science, University of Virginia, VA 22903.
Bernstein D., Rodey M. Global Instruction Scheduling for Superscalar Machines. - Proceedings of the SIGPLAN '91 Conference on Programming Language Design and Implementation, pp.241-255, June 1991.
Berson D. A., Gupta R., Soffa M. L. Integrated Instruction Scheduling and Register Allocation Techniques. - In Proc. of the Eleventh International Workshop on Languages and Compilers for Parallel Computing, LNCS, Springer Verlag, Chapel Hill, NC, Aug. 1998.
Bharadwaj J., Menezes K. McKinsey C. Wavefront Scheduling: Path Based Data Representation and Scheduling of Subgraphs. The Journal of Instruction-Level Parallelism, May 2000.
Bruggen T., Ropers A. Optimized Code Generation for Digital Signal Processors. - Institute for Integrated Signal Processing, http://www.ert.rwth-aahen.de/coal .
Chang P. P., Mahlke S. A., Chen W. Y., Warter N. J., Hwu W. W. IMPACT: An architectural framework for multipleinstruction-issue processors," in Proceedings of the 18th International Symposium on Computer Architecture, pp. 266-275, May 1991.
Eichenberger A. E., Davidson E. S., Abraham S. G. Minimizing Register Requirements of a Modulo Schedule via Optimum Stage Scheduling. - International Journal of Parallel Programming, February, 1996.
Eichenberger A. E., Lobo S. M. Efficient Edge Profiling for ILP-Processors. - Proceedings of PACT 98, 12-18 October 1998 in Paris, France..
Fisher J. A. Global code generation for instruction-level parallelism: Trace Scheduling-2. - Tech. Rep. HPL-93-43, Hewlett-Packard Laboratories, June 1993
Fisher J.A. Trace scheduling: A Technique for Global Microcode Compaction. - IEEE Transaction on Computers, vol. 7, pp. 478-490, July 1981.
Gebotys C. H., Gebotys R. J. Complexities In DSP Software Compilation: Performance, Code Size, Power, Retargetability. 1060-3425/98, IEEE, 1998.
Grossman J.P. Compiler and Architectural Techniques for Improving the Effectiveness of VLIW Compilation. – submitted to ICCD 2000.
Havanki W. A., Banerjia S., Conte T. M. Treegion Scheduling for Wide Issue Processors. - Proc. 4th Intl. Symp. on HighPerformance Computer Architecture, Feb. 1998, pp. 266-276.
Hoogerbrugge J., Augusteijn L. Instruction Scheduling for TriMedia. - The Journal of Instruction-Level Parallelism, February 1999
Horst E., Kloosterhius W., Heyden J. A C Compiler for the Embedded R.E.A.L DSP Architecture. - Материал получен с телеконференции comp.dsp.
Hsu P.Y.T., Davidson E.S. Highly Concurrent Scalar Processing. - Proceedings of the 13th Annual International Symposium on Computer Architecture, pp. 386-395. June 1986.
Hwu W.W., Mahlke S.A., Chen W.Y., Chang P.P., Warter N.J., Bringmann R.A., Quelette R.G., Hank R.E., Kiyohara T., Haab G.E., Holm J.G., Lavery D.M. The Superblock: An Effective Technique for VLIW and Superscalar Compilation. - The Journal of Supercomputing, vol. 7, pp. 229-249, May 1993.
IA-64 Application Developer's Architecture Guide. - Intel, May 1999.
ISO/IEC 9899:1999(E). Programming Languages - C. - ISO/IEC, 1999.