Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Использование закона ассоциативности для параллельного вычисления арифметико-логических выражений

А.И.Касинский,  ИМВС  РАН
Московский центр 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).
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика