Межпроцедурные оптимизации «Ошибочности» значений для функционального языка, ориентированного на научные вычисления

Математические методы моделирования, управления и анализа данных

S. N. Zinin

Siberian State Aerospace University named after academician M. F. Reshetnev, Russia, Krasnoyarsk

SOFTWARE TOOL FOR DEVELOPING OF MATHEMATIC MODELS OF AVIATION INSTRUMENTS

Here is covered a software tool for developing mathematic models describing a real aviation instruments behavior. The choice of architecture solution is carried out by an altimeter application example.

© Знннн Q K, 2009

УДК 004.432.42

Р. И. Идрисов

Институт систем информатики имени А. П. Ершова Сибирского отделения Российской академии наук, Россия, Новосибирск

МЕЖПРОЦЕДУРНЫЕ ОПТИМИЗАЦИИ «ОШИБОЧНОСТИ» ЗНАЧЕНИЙ ДЛЯ ФУНКЦИОНАЛЬНОГО ЯЗЫКА, ОРИЕНТИРОВАННОГО НА НАУЧНЫЕ ВЫЧИСЛЕНИЯ

Свойство «ошибочности» значения характеризует выход за пределы представления либо ошибку при произведении вычисления. Хранение такого свойства для вычислительных задач позволяет получать частичные результаты вычислений. Представлен новый метод межпроцедурного анализа на основе статического развернутого графа зацепленности потоковой программы, который позволяет существенно оптимизировать вычисление таких значений на стадии статического анализа программы.

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

В большинстве современных языков программирования в качестве механизма работы с ошибками вычислений используются исключения (try-catch), это нарушает структурность программы и приводит к более сложному распараллеливанию. Для получения частичных результатов в этом случае требуется дополнительное программирование и описание исключительных случаев. Хранение свойства «ошибочности» делает механизм получения частичных результатов более универсальным, но требует реализации дополнительной логики проверки этого свойства в компиляторе и среде поддержки времени исполнения (RTL).

Межпроцедурный анализ относится в первую очередь к анализу потока данных, который по-

ступает при вызове в процедуру и из нее. В рамках данной работы под межпроцедурным анализом будем понимать анализ влияния вызова процедуры на контекст вызова [1] и определение влияния контекста вызова на исполнение вызываемой процедуры [2]. Возникновение и развитие такого вида анализа непосредственно связано с развитием потокового анализа, началом которого можно считать создание системы автоматизации программирования АЛЬФА [3]. В трансляторе АЛЬФА процедурные вызовы анализировались отдельно, производилась подстановка висячих процедур, частично анализировались совмещения параметров и присутствовал анализ записываемых переменных. С момента создания системы АЛЬФА, анализ процедурных вызовов стал неотъемлемой частью оптимизирующего транслятора. Об этом свидетельствуют дальнейшие публикации по оптимизирующим трансляторам [4]. Приблизительно в начале 1980-х гг. межпроцедурный анализ был выделен в качестве отдельного вида анализа [5].

Под развернутым статическим графом зацеп-ленности программы в данной работе понимается граф, состоящий из функций исходной программы и их возможных копий, которые связываются с местами их фактического вызова отношением «вызывающий» и «вызываемый». Анализ такого графа дает более точную информацию о потоке

Решетневские чтения

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

Межпроцедурный анализ значений элементов массивов и оптимизации проверки их «ошибочности» позволяет существенно повысить производительность результирующей программы, это было показано в рамках внедрения данных алгоритмов в компилятор функционального языка Sisal 3.2 [6] системы SFP [7].

Библиографический список

1. Евстигнеев, В. А. Методы межпроцедурного анализа (обзор) / В. А. Евстигнеев, В. А. Серебряков // Программирование. 1992. № 3. С. 4-15.

2. Антонов, А. С. Современные методы межпроцедурного анализа программ / А. С. Антонов // Программирование. 1998. № 5. С. 3-14.

3. АЛЬФА-система автоматизации программирования / под. ред. А. П. Ершова ; АН СССР. Сиб. отд-ние. Новосибирск : Наука, 1967.

4. Методы декомпозиции, синтеза и оптимизации в многоязыковой системе программирования : препр. / И. В. Поттосин ; АН СССР. Сиб. отд-ние, ВЦ. Новосибирск, 1974.

5. Sharir, M. Two approaches to interprocedural data flow analysis / M. Sharir, A. Pnueli // Program Flow Analysis: Theory and Applications ; ed. S. Muchnick, N. D. Jones. Prentice Hall Inc, 1981.

6. Язык функционального программирования SISAL / В. А. Евстигнеев, Л. В. Городняя, Ю. В. Гус-токашина // Интеллектуализация и качество программного обеспечения. Новосибирск, 1994.

7. SFP - An interactive visual environment for supporting of functional programming and supercomputing / V. N. Kasyanov [et. al.] // WSEAS Transactions on Computers. Vol. 5, № 9. Athens: WSEAS Press, 2006. P. 2063-2070.

R. I. Idrisov

A. P. Ershov Institute of Informatics Systems, Russian Аcademy of Science, Siberian Branch, Russia,Novosibirsk

OPTIMIZING OF THE «IS_ERROR» PROPERTY IN THE SCIENTIFIC FUNCTIONAL LANGUAGE

The «iserror» property indicates an exit from representation limits or an comuptation error. Keeping of such a property for computational tasks allows receiving partial results of calculations. In this work we present a new metod of an interprocedural analysis, based upon expanded static dataflow call graph wich allows optimizing of calculation of such values at a stage of the static analysis of the program.

© HgpncoB P. H., 2009

УДК 62-506.1

О. А. Иконников

Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, Россия, Красноярск

НЕПАРАМЕТРИЧЕСКИЙ АЛГОРИТМ ИДЕНТИФИКАЦИИ ПРИ МОДЕЛИРОВАНИИ ДИНАМИЧЕСКИХ ПРОЦЕССОВ

Рассматривается методика построения непараметрических алгоритмов идентификации линейных динамических систем. Приводятся некоторые результаты численных исследований построенных алгоритмов.

Сущность предлагаемого подхода к решению задачи идентификации рассматриваемого класса объектов состоит в построении непараметрических оценок весовой функции и отказа, вследствие этого, от выбора априори порядка уравнения, описывающего данный объект (идентификация в широком смысле). Основой для восстановления

весовой функции системы служат наблюдения реакции объекта на некоторые стандартные сигналы.

Пусть на вход линейной динамической системы (ЛДС) подано единичное возмущающее воздействие 0 < t < T, где Т - время окончания переходного процесса, а 1(0 — функция Хэвисай-