А.И.Касинский, ИМВС РАН
Московский центр SPARC технологий
Производительность современных вычислительных систем является сложной функцией от множества взаимосвязанных величин. Эффективность использования аппаратных возможностей ЭВМ является актуальной задачей уже много лет и во многом определяется оптимизациями программ, как в самых текстах, так и в процессе их компиляции в код в оптимизирующих компиляторах. Cовременные микропроцессоры, например Intel и SPARC, имеют несколько арифметических устройств и позволяют выполнять одновременно несколько арифметических команд. К сожалению, большинство арифметических, логических и адресных выражений в программах не приспособлены для такого выполнения без ослабления информационных зависимостей при помощи специальных алгебраических преобразований. Основным способом этих преобразований в общем случае является применение закона ассоциативности и коммутативности. Стандартные способы использования этих законов применяются к отдельным выражениям без учета общих подвыражений. Поэтому был предложен способ распараллеливания выражений на основе модифицированного следствия Шеннона из основной теоремы теории кодирования. Он позволяет достичь минимальной теоретической границы времени выполнения произвольных арифметико-логических выражений, включающих операцию деления, в рамках применения только законов ассоциативности и коммутативности, для случая неограниченного числа арифметических устройств.
Для получения результатов применялся блок оптимизаций в среде экспериментального распараллеливающего компилятора NARCH с множеством входных языков, включая код для VLIW архитектуры микропроцессора Elbrus.
Способ адаптирован также для достаточно аккуратной работы в общих подвыражениях, что дает в среднем положительный эффект уменьшения времени 2% при измерении производительности на примере пакета Spec92. В целом, эффект применения закона ассоциативности разными способами можно оценить 10-15%.
Также реализована возможность влияния на оптимизации вещественных выражений для обеспечения требуемой точности и численной устойчивости.
Литература:
- Дональд Э.Кнут. "Искусство программирования для ЭВМ Т.2 "Получисленные алгоритмы". М."Мир", 1976 (1968).
- Brent,R.P., Kuck,D.J., Mariama,K. "The parallel evaluation of arithmetic expressions without division". IEEE Transactions on Computers, V.C-22, May 1973, 533-534.
- Brent,R.P. "The parallel evaluation of general arithmetic expression". ASM Transactions on Mathematical Software (TOMS), 21, 2, 1974, 201-206.
- А.Ахо, Дж. Хопкрофт, Дж. Ульман. "Построение и анализ вычислительных алгоритмов", М."Мир", 1979 (1976).
