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

На правах рукописи

?7ь ОД

ТОМАЕВ МУРАТ ХАСАНБЕКОВИЧ

СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ОПТИМАЛЬНЫХ ПРОГРАММНЫХ КОМПЛЕКСОВ

Специальность: 05.13.12 - «Системы автоматизации пр.;ектир' вания (промышленность)»

АВТОР > Г ."■••ссертации на соиек. и ". '.гнои с -еп; кандидата те::.. ¡т;(.:,их. науг.

Владикавказ - 2000

Работа выполнена в Северо-Кавказском ордена Дружбы народов государственном технологическом университете.

Научный руководитель:

доктор технических наук,профессор В.О. Гроппен

Официальные оппоненты:

доктор технических наук,профессор Т.С. Гуриев кандидат физико-математических наук Е.С. Каменецкий

Ведущая организация:

Владикавказский институт управления. Защита состоится 27 июня 2000 г. в 1330 на заседании диссертационного совета № 063.12.03 при Северо-Кавказском ордена .Дружбы народов государственном технологическом } 11верситете, по адресу: 362021, РСО-Алания, г. Зладикавка?. ул. Николаева, 44. :ЖГТУ.

С дис^сг- яцией можно ознакомиться в -'лилиотске Сев^ро-Ка1 лзск'то о]' .-.ена Мружоы н.фсдов государственна /о технологи ск . о ун : .ер лте .а.

Аб1:п :фсрат разс.-ла;* Л И'';0 I.

Ученый секретарь диссертационного совета

д.т.н., профессор

Б.А. Хасцаев

г

-ОЬ,Г)

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

Актуальность работы.

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

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

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

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

мени выполнения приложения либо объем используемой при этом

памяти.

Цель работы.

Целью работы является создание средств программной поддержки САПР оптимальных программных продуктов. Задачи, решаемые в данной работе включают:

1. Определение целей оптимизации программных комплексов.

2. Разработка алгоритмов поиска оптимальной декомпозиции пользовательских программ.

3. Разработка программных реализаций выбранных алгоритмов.

4. Создание комплексного пакета средств программной поддержки САПР оптимального программного обеспечения.

Методика исследований.

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

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

- Программные средства поддержки САПР оптимальных программных комплексов.

г

- Алгоритмы и программные средства представления исходных и оптимальных программных кодов в виде взвешенных ориентированных графов. Научная новизна:

Обобщены и дополнены ранее развитые подходы к оптимизации программных единиц.

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

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

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

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

Внедрение САПР ОПО снижает стоимость разработки качественного программного обеспечения, позволяет повысить эффективность эксплуатации используемого парка ЭВМ, в полной мере задействовав ресурсы имеющихся электронно-вычислительных систем. Все это также позволит снизить расходы на приобретение нового, более

производительного оборудования. В реализованной работе отсутствует привязка к какой-либо аппаратной платформе или к какому-либо системному программному обеспечению, что, очевидно, также расширяет возможности внедрения САПР OIIO.

Достоверность и обоснованность научных положений, выводов н рекомендаций подтверждается аналитическими исследованиями и совпадением полученных в результате проведенных экспериментов данных с теоретическими выводами. Реализация работы.

На основе научно-обоснованных методов оптимизации программного обеспечения реализована система автоматизированного проектирования оптимальных программных продуктов, которая позволяет автоматически модифицировать исходные тексты программных пакетов созданных на популярных языках высокого уровня (BASIC, Фортран, Паскаль) соответственно заданным критериям оптимизации. Разработанный программный продукт позволяет значительно упростить технологию создания эффективных программных продуктов.

Результаты диссертационной работы используются в Государственном комитете РСО-Алания по статистике а также в Фонде обязательного медицинского страхования для разработки программного обеспечения. Апробация работы.

Основные положения диссертации докладывались на ежегодных научно-технических конференциях СКГТУ, а также на расширенных заседаниях кафедры Автоматизации обработки информации.

Разработанная САПР ОПО используется в учебном процессе, и применяется для ознакомления учащихся с принципами оптимизации программного обеспечения, а также для контроля знаний студентов.

Публикацнн.

Основные положения опубликованы в 5 статьях. Объем работы.

Диссертация состоит из введения, 4 глав, выводов, заключения и списка литературы, насчитывающего 105 наименований, содержит 15 рисунков, 7 таблиц и 145 страниц машинописного текста.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ. Постановка задач проектирования оптимальных программных комплексов.

Выбор цели оптимизации тесно связан с учетом человеческого фактора. Так, достаточно разумным представляется допущение , что пользователь-пессимист будет стремиться минимизировать верхнюю границу времени счета либо объема используемой оперативной памяти, а оптимист - нижнюю. В первом случае оптимальная декомгози-ция конечного алгоритма, минимизирующая верхнюю границу времени поиска решения его программной реализацией применительно к ЭВМ, объём свободной оперативной памяти которой равен V, в режиме CHAIN может быть определена с помощью следующей модели [1]:

Fx = max^rnax £ </>'g"I>(/,/)min; V»,Z*('J) = 1;

• J (1)

max V(j)sign^ z(i, j) < V; J i

где

z{i,j) - булева переменная, равная единице, если i-й оператор

алгоритма пользователя реализуется j-й программной единицей, и нулю в противном случае; г(_/) - верхняя граница времени работы j-ой программной единицы;

V(j) - верхняя граница объема оперативной памяти,

используемого j-ой программной единицей; V - объем свободной оперативной памяти используемой ЭВМ.

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

Переход к режиму OVERLAY соответствует замене в (1) единственного неравенства следующим:

V(f)

min , + max V(j)sign£ z(i, j) < V (2)

j signZz(i,J) j i

i

Аналогичная декомпозиция зацикленного алгоритма, который реализуется программными единицами, функционирующими в режиме CHAIN, может осуществляться на модели, отличающейся от (1) лишь целевой функцией. Последняя в этом случае имеет вид:

F2= шах £ rO>/g«2>(ij)->min (4)

akeA(G) jeH(ak) i

где A(G) - множество контуров на графе G(X,U), множество вершин X, которого соответствует состояниям вектора переменных алгоритма

пользователя, а дуга (/,_/)е£/ отвечает оператору, переводящему вектор переменных из ¡-го состояния в ^ое.

Физически (4) означает минимизацию верхней границы времени однократного зацикливания в контурах множества А(0), что соответствует одному из критериев качества программных реализаций алгоритмов такого рода.

Пусть конечный алгоритм преобразуется в зацикленный добавлением | ХТ | операторов безусловного перехода, которые позволяют переходить из любого терминального состояния в начальное. Пусть каждому такому переходу соответствует некая фиктивная программная единица с нулевым временем выполнения и нулевым объемом используемой оперативной памяти. Графически это соответствует добавлению в конечный ориентированный граф С(Х,1/),А(0) — 0,

подмножества дуг с нулевыми весами, идущих из вершин подмноже-т

ства X в вершину-источник х0 еХ, преобразующих С(Х,и) в

С1{Хх,и1),А{С

Пусть - множество контуров, образующихся при допол-

нении графа С(Х,и) дугой (<7,0) , для Ул; е ХТ.

Так как такие операторы безусловного перехода имеют нулевые время счета и объем занимаемой памяти, то, очевидно:

£ *(',./) =тах I т(j)signZz(i,j)

в*бЛ,«ч)уе Н(ак) г / М1/{0,Я)} >

Отсюда следует, что оптимальной декомпозиции такого рода отвечает равенство:

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

Если целью оптимизации является декомпозиция конечного алгоритма, которой отвечает программная реализация, минимизирующая объём используемой оперативной памяти в режиме CHAIN при условии, что верхняя граница времени счета не превысит времени ©, то система (1) преобразуется к виду:

F3 = max V( j)sign£, z(i, j) min

J i

Vi,2>(/J) = l;

• ' (6) Vi,\/j,z(iJ) = 1,0;

max max £ <0

xqeXT f je{Lf i

Переход к режиму OVERLAY при сохранении прочих условий соответствует замене в (С) целевой функции левой частью неравенст-ва(2):

V(f)

F4 = min . JJ + maxV(J)sigriZz(i, j) -> min (7) j SlgriZz(l,J) j i

i

Аналогичный подход к зацикленным алгоритмам приводит к формальной постановке, отличающейся от (6) лишь последним ограничением - оно в этом случае заменяется неравенством: max 2 T{j)sigriZz{i,j)<® (8)

akeA(G) ;ея(?А) i

Здесь 0 представляет собой верхнюю границу времени однократного зацикливания.

Очевидно, что систему (6) и её модификации можно также рассматривать, как формальное описание антагонистической позиционной

игры двух лиц с полной информацией и нулевой суммой, что позво-г

ляет использовать для её решения те же подходы, что и для решения системы (1).

Наконец, несколько строк об алгоритмах, склонных к зацикливанию, т.е. таких, которые могут как благополучно завершиться, так и бесконечно циклиться. Граф G(X,U), соответствующий процедурам такого рода, обладает непустыми множествами контуров и терминальных вершин: A(G) Ф 0\ХТ Ф 0. Рассмотренные выше модификации конечного алгоритма, преобразующие его в зацикленный введением фиктивных операторов безусловного перехода с "нулевыми" характеристиками, позволяют избежать оптимизации по Парето применительно к склонным к зацикливанию алгоритмам и свести их оптимальную декомпозицию к оптимальной декомпозиции зацикленных процедур: можно показать, что оптимальная декомпозиция последнего совпадает с одной из оптимальных в смысле Парето декомпозиций исходного алгоритма. Это позволяет далее отказаться от поиска решения многокритериальных задач оптимальной декомпозиции алгоритмов пользователя.

Другим аспектом проектирования оптимальных программных продуктов является размещение данных в памяти ЭВМ и определение оптимальных размеров кэш-блоков. Если все файлы пользователя первоначально размещены на внешнем носителе, а в оперативной памяти созданы блоки кэширования, каждый из которых предназначен для сканирования «своего» файла, причём a priori известны размер каждого файла и вероятность обращения к нему либо число таких обращений, то формальная постановка задачи минимизации числа обращений к внешним носителям имеет вид:

т

(9)

V/,1 <и,<ш,

Очевидно, что, если существует оптимальное решение (9), в котором 3/: £/, = ^, то это означает, что I —й файл должен быть размещён в оперативной памяти. Если перемещения такого рода запрещены, то

нижней границе решения системы отвечает вектор £/ для которого справедливо:

(10)

В [3,8] предложен алгоритм поиска решения (9), использующий систему (10) в качестве отправной точки, в окрестностях которой ищутся целочисленные планы.

Если в рассмотренных выше в п.п.З моделях справедливо:

У/,г(У) = 1 (П),

то минимизация верхней границы времени поиска решения вырождается в минимизацию верхней границы числа обращений к внешней памяти. Это позволяет объединить эти модели с системой (9). Подход такого рода описан ниже. 6. Объединение и декомпозиция моделей.

Учёт условия (11) в моделях (1) и (2), позволяет формально поставить задачу поиска таких стратегий композиции программных

единиц и размещения данных в двухуровневой памяти ЭВМ, которые г

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

п т W Р

F6= max £ signZ z(h j) + ZУ, -fr1- -> min;

akeA(G) jeH(ak) i=1 t=1 U,

V/,2>(/,/) = 1;

J

maxrO>/g«izay) + £i/( <F; (12>

J /=1 /=1

Vf.y,=sign{Wt-Ut); Vt,l<Ut <IVt;

z(i,j) = 1,0; / = 1,2 ,...,n\j = 1,2,.... Легко убедиться, что переход к режиму overlay соответствует замене первого неравенства системы (12) следующим:

" V( f) т max VißsignZ z{i, j) + min-^-+ Z f/, < Г

1 1=1 ' signZz{i,j) '=I

i=i

Поиск решения (12) осуществляется последовательным разделением величины V на две части - Va и Vb: Va +Vb =V. Первое слагаемое левой части играет роль размера свободной оперативной памяти, используемой для размещения программных единиц, а второе слагаемое представляет собой размер свободной оперативной памяти, используемой для хранения и кэширования файлов. Это позволяет осуществить декомпозицию (12) на две подзадачи - одной

из них является поиск оптимальной композиции программных единиц при условии, что объем используемой оперативной памяти не превысит величины Уа, а другая отличается от (9) тем, что величина ^заменяется в ней на Уь. Значение целевой функции (12) равно сумме целевых функций обеих подзадач. Таким образом поиск решения (12) сводится к поиску минимума функции Поскольку по-

следняя является унимодальной, поиск решения может вестись с помощью дихотомии, интерполяции или квадратичной аппроксимации.

Случаи, допускающие применение эффективных процедур.

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

1. Пусть целью оптимизации является поиск оптимальной декомпозиции зацикленного алгоритма, множество контуров А(Э), которого содержит только простые контура ак б

тогда существует подмножество вершин Xх С.Х, для которых выполняется:

2У(/,4) = 2,при /=1.л (13)

В случае, если целью оптимизации является минимизация нижней границы времени счета(стратегия «Оптимист»), то замена всех вершин .X еХ5, на Х+ иГ, позволяет представить исходный алго-

я ч ч

ритм в виде конечного ориентированного графа, для которого реше-

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

2.Пусть целью оптимизации является оптимальная декомпозиция конечного алгоритма, минимизирующая нижнюю границу времени выполнения программы, работающей в режиме CHAIN. Тогда формальную постановку задачи при заданном ограничении объема оперативной памяти можно представить в виде следующей модели:

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

а также дугами, соответствующими всем возможным сочетаниям операторов при данном ограничении объема доступной оперативной памяти V, то будет справедлива следующая теорема. Теорема. Решение задачи, формальная постановка которой

(14)

j

max y(j)sign£z(i, j) < V; z(i,j) = 1,0; i = 1,2 ,..,n;j = 1,2,...

max

VxqeXT,t(q,s) = 0 (15)

представлена в модели (14) соответствует решению задачи поиска минимального пути на графе из начального состояния в вершину 8. Доказательство.

Пусть граф 0(Х,и), соответствующий конечный алгоритму пользователя, содержит п состояний, включающих ш терминальных вершин.

Пусть 7^- решение задачи (14), а 7^- решение задачи поиска кратчайшего пути (16) из начального состояния в вершину в модифицированного графа.

' У

V* • еХ\(хх,х1 ):£ 2(/,У)=1 г(],к)\

/ * (16)

0=2 2(1,0=1; / /

1. пусть 7;>Г2.

Отсюда следует, что минимальный путь Т,т!п (0,5), соответствующий решению задачи (16) меньше, чем путь 7/(0,д), соответствующий решению (14). Так как согласно равенству (15) вес каждой дуги, заходящей в вершину Б, равен нулю, то путь 1/(0,д) не является минимальным среди всех возможных путей в одну из терминальных вершин, а соответствующая программная декомпозиция не соответствует нижней границе времени счета, что противоречит целевой функции задачи (14).

2. Пусть Тх<Тг.

г

Т.е. соответствующий решению задачи поиска кратчайшего пути (16) путь Lmjn (0, s) длиннее, чем l/(0,q), но это возможно только в случае, когда существует X S XT,t(q,S)>0, что противоречит

условию (15). Теорема доказана.

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

САПР ОПО: структура, алгоритмы, интерфейс.

САПР ОПО реализована на языке Visual С++ и содержит 4 исполняемых модуля.

Главный модуль инициализируется в момент запуска САПР, он отвечает за создание нового исходного кода пользователя или открытие уже существующего. Непосредственно при активизации данного участка программы происходит создание и индексация объектов-словарей, содержащих набор зарезервированных слов для каждого из 3-х используемых в САПР языков программирования: Бейсика, Паскаля и Фортрана. Благодаря применению объектно-ориентированного подхода удалось создать базовый класс, в котором были реализованы все универсальные методы, выполняющие заполнение, индексацию, поиск зарезервированных имен управляющих операторов и функций.

Следующий модуль активизируется при создании нового или открытии существующего документа, содержащего исходный код пользователя. На данном этапе решаются следующие задачи:

1) Определение входного языка программирования;

2) Выделение зарезервированных слов и используемых переменных;

3) Определение весовых характеристик каждого оператора;

4) Создание матрицы смежности, описывающей управляющую логику алгоритма пользователя;

5) Определение типа алгоритма.

6) Представление алгоритма пользователя в виде графа.

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

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

Матрица смежностей инициализируется в момент открытия файла и её содержимое обновляется в соответствии с изменениями, вносимыми пользователем в текст программы.

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

Алгоритм, разработанный для отображения графа по-

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

Третий модуль САПР отвечает за ввод основных параметров оптимизации в том числе:

1. Выбор цели оптимизации. Т.е. оптимизация по времени счета либо по объему используемой оперативной памяти.

2. Выбор режима функционирования программы(«СНАШ» или «OVERLAY»).

3. Выбор стратегии оптимизации пользовательского алгоритма (для всех типов кроме линейных алгоритмов): оптимизация по верхней либо по нижней границе времени сче-та(«Пессимист» либо «Оптимист»),

4. Ввод размеров и числа обращений к используемым в программе файлам.

5. Определение объема доступной оперативной памяти ЭВМ.

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

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

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

В зависимости от типа алгоритма и параметров оптимизации для поиска оптимальной декомпозиции используется один из следующих методов решения:

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

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

Оптимальное распределение оперативной памяти между программой и файлами пользователя достигается в результате апрокси-мации полиномом N экспериментальных точек в диапазоне \+У„ где

V. - объем памяти выделенный под программные единицы. I

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

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

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

Постановка н результаты экспериментальной проверки САПР ОПО.

Экспериментальные исследования проводились с целью проверки эффективности выбранных процедур поиска оптимальной декомпозиции

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

Эксперименты проводились на рабочей станции со следующими техническими характеристиками:

- Процессор Intel Pentium II с частотой 300 мегагерц.

- Объем оперативной памяти -64 мегабайт.

- Жесткий диск объемом 6 гигабайт.

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

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

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

ЗАКЛЮЧЕНИЕ.

Одним из основных препятствий к широкому внедрению оптимизации при проектировании программных продуктов до последнего времени являлась трудоёмкость поиска оптимальных решений. Затраты времени, связанные с поиском оптимальной декомпозиции алгоритма пользователя и выбором оптимального размещения используемых им данных в памяти ЭВМ, как правило, во много раз превышали выигрыш, полученный при однократном использовании оптимального программного продукта. Достаточно аргументированным в этом случае являлось проектирование неоднократно используемых оптималь-

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

Создание и широкое внедрение пакетов программной поддержки САПР оптимального программного обеспечения кардинально меняет ситуацию. Сокращаются затраты на создание практически любых программных продуктов и, одновременно, повышается качество последних, а более эффективное применение имеющихся ресурсов вычислительных систем позволяет сократить средства, используемые на их модернизацию. Таким образом, последствия внедрения предлагаемой технологии трудно переоценить. Основные результаты работы:

1. Развита и обобщена теория проектирования оптимальных программных комплексов.

2. Созданы эффективные программные средства поддержки САПР оптимальных программных продуктов.

3. Созданы программные средства классификации алгоритмов пользователя и их визуализации в виде взвешенных ориентированных графов.

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

Основные положения диссертации изложены в следующих рабо-

1. Гроппен В.О., Томаев М.Х. Модели, алгоритмы и средства программной поддержки проектирования оптимальных программных продуктов //Автоматика и телемеханика. 2000.

2. Томаев М.Х. Средства программной поддержки САПР оптимальных программных продуктов //Труды СКГТУ, вып.7 2000, Терек.

3. Гроппен В.О., Томаев М.Х. Теоретические принципы проектирования оптимальных программных продуктов// Труды СКГТУ, вып. 7 2000, Терек.

4. Томаев М.Х. Создание оптимального программного обеспечения //Сборник научных трудов аспирантов СКГТУ, 2000.

5. Гроппен В.О., Томаев М.Х. Технология оптимизации конечных горитмов '. Сборник научных трудов аспирантов СКГТУ, 2000.

тах:

ВВЕДЕНИЕ.

Глава 1. Постановка задач проектирования оптимальных программных комплексов.

1.1 Условные обозначения, определения и допущения:.

1.2 Формальные постановки оптимизационных задач.

1.3 Оптимальное кэширование пользовательских файлов.

1.4 Объединение и декомпозиция моделей.

Глава 2. Случаи, допускающие применение эффективных процедур.

2 Л Минимизация нижней границы времени однократного зацикливания циклящихся процедур.

2.2 Минимизация нижней границы времени выполнения ветвящихся программных алгоритмов.

Глава 3. САПР ОПО: структура, алгоритмы, интерфейс.

3.1 Структура САПР и используемые алгоритмы.

3.2 Интерфейс САПР.;.

Глава 4. Постановка и результаты экспериментальной проверки САПР оптимальных программных комплексов.

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

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

Разработка новых ЭВМ, почти всегда, требует создания нового программного обеспечения к нему. Проектирование эффективных программных пакетов связано с большими затратами материальных ресурсов и занимает длительный период времени.

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

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

Использование системного программного обеспечения повысило эффективность эксплуатации используемых аппаратных средств, позволило значительно упростить разработку нового ПО, а также осуществлять тестирование различных узлов электронновычислительных комплексов. Таким образом, использование системного программного обеспечения позволило значительно сократить штат специалистов, осуществлявших контроль за техническим состоянием ЭВМ. Внедрение систем автоматизированного проектирования, позволило снизить стоимость разработки программного обеспечения.

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

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

Все методы оптимизации можно условно разделить на машинно-зависимые, машинно-независимые и универсальные.

Машинно-зависимые осуществляют преобразования, учитывая технические особенности конкретной ЭВМ, и являются наиболее полезными, если необходимо достичь эффективной работы приложения именно на конкретной аппаратной платформе. Однако при попытке переноса программного обеспечения, подвергшегося подобной оптимизации, на другие ЭВМ, эффективность подобного преобразования не является очевидной и, в некоторых случаях, потребует модификации кода для учета специфики нового оборудования. К примеру, в некоторых средах разработки компилятор автоматически модифицирует объектный код, временно размещая переменные, доступ к которым наиболее интенсивен, в определенных регистрах процессора.

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

Многие современные автоматизированные системы разработки содержат инструменты, использующие подобные методы.

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

Второй подход заключается в замене оператора(выражения) или группы линейно расположенных операторов на аналогичный по своему действию оператор, но более эффективный в конкретно взятом случае. К примеру, следующее выражение на языке С требует двукратного обращения к одной и той же переменной X = Х+1;

- первый раз при вычислении значения выражения в правой части операции присваивания, а второй - для сохранения результата. Аналогичное выражение Х++; требует однократного доступа к переменной X - для осуществления операции инкремент. Причем в первом случае выполняется операция сложения, которая отнимает гораздо больше тактов процессорного времени, чем операция инкремент.

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

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

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

Целью работы является создание средств программной поддержки технологии проектирования оптимального программного обеспечения, способного эффективно использовать ресурсы применяемых вычислительных систем. Поскольку существуют различные цели оптимизации программного обеспечения, задачей работы является разработка средств программной поддержки, предназначенных для разработки программных единиц, гарантирующих: а) минимизацию верхней границы времени поиска решения прикладной задачи для конечных алгоритмов; б) минимизацию верхней границы объема используемой оперативной памяти при условии, что время счета не превысит некоторой заданной величины; в) минимизацию верхней границы времени однократного зацикливания для циклящихся процедур. Таким образом, реализация данной работы позволяет, за счёт более эффективного использования ресурсов применяемых вычислительных средств, создавать более эффективное программное обеспечение, обладающее высоким быстродействием и сравнительно невысокими требованиями к объёму используемой оперативной памяти. Реализация работы приведёт, следовательно, к снижению потребности в дорогих ЭВМ и. соответственно, снизит затраты на решение прикладных задач. Отсюда следует актуальность представленной работы.

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

Моделирование процесса проектирования оптимальных программных единиц использует следующие модели теории игр: а) антагонистическую позиционную игру двух лиц с полной информацией; б) игру "с болваном". Для оптимального использования иерархической памяти ЭВМ применяются такие методы дискретного программирования, как методы типа ветвей и границ, динамическое программирование. Совмещение обоих подходов осуществляется сочетанием приведенных выше моделей с методами дихотомии и наименьших квадратов.

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

Предложены также научно обоснованные процедуры поиска оптимальной декомпозиции конечных и зацикленных алгоритмов для тех случаев, когда минимизируется нижняя граница времени счета выполнения программ, функционирующих в режиме CHAIN. На основе научно обоснованных методов оптимизации программного обеспечения реализована система автоматизированного проектирования оптимальных программных продуктов, которая позволяет автоматически модифицировать исходные тексты программных пакетов созданных на популярных языках высокого уровня (BASIC, Фортран, Паскаль) соответственно заданным критериям оптимизации. Разработанный программный продукт позволяет значительно упростить технологию создания эффективных программных продуктов 9

Внедрение САПР ОПО снижает стоимость разработки качественного программного обеспечения, позволяет повысить эффективность эксплуатации используемого парка ЭВМ, в полной мере задействовав ресурсы имеющихся электронно-вычислительных систем. Все это также позволит снизить расходы на приобретение нового, более производительного оборудования. В реализованной работе отсутствует привязка к какой-либо аппаратной платформе или к какому-либо системному программному обеспечению, что, очевидно, также расширяет возможности внедрения САПР ОПО.

Теоретические принципы оптимизации программных продуктов подробно изложены в трудах Гроппена В.О., Летичевского A.A., Касьянова В.Н., Левитина В.В. В представленной работе предлагаются новые более эффективные процедуры для поиска оптимальной декомпозиции конечных и зацикленных алгоритмов, функционирующих в режиме CHAIN, когда целью оптимизации является минимизация нижней границы времени выполнения программы. Решается задача практической реализации методов глобальной оптимизации применительно к некоторым популярным языкам программирования (Бейсик, Паскаль, Фортран).

ЗАКЛЮЧЕНИЕ

Одним из основных препятствий к широкому внедрению оптимизации при проектировании программных продуктов до последнего времени являлась трудоёмкость поиска оптимальных решений. Затраты времени, связанные с поиском оптимальной декомпозиции алгоритма пользователя и выбором оптимального размещения используемых им данных в памяти ЭВМ, как правило, во много раз превышали выигрыш, полученный при однократном использовании оптимального программного продукта. Достаточно аргументированным в этом случае являлось проектирование неоднократно используемых оптимальных программных продуктов со сравнительно слабо меняющимися исходными данными (подсистемы АСУ), либо программ, важность оптимальности которых, даже при однократном применении компенсирует трудоёмкость оптимизации (например, программное обеспечение систем наведения и распознавания целей).

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

1. Аллен Ф. Э. Методы определения информационных связей в программах//Теория программирования.— Новосибирск, 1972- Ч. 2-С. 136-144.

2. Ахо А„ Ульман Дж. Теория синтаксического анализа, перевода и компиляции,— М.: Мир, 1978.— Т. 2.-487 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.— М.: Мир, 1978,— 536 с.

4. Бабецкий Г. И., Бежанова М. М. и др. АЛЬФА-система автоматизации программирования.— Новосибирск: Наука, 1967-308 с.

5. Вальковский В. А., Касьянов В. Н. Крупноблочная сегментация и распараллеливание схем программ // Программирование.— 1976.— п". 1,—С. 16—25.

6. Ветров А. Г., Луцикович В. В. Система построения трансляторов ТУ. Основные принципы выполнения оптимизации транслируемых программ.— Препринт/ИПМ АН СССР,— М„ 1979-№33-15 с.

7. Гвозденко А. А„ Дзелинская А. А., Дзелинский А. М. Алгоритмы конкретизации выражений и чистки циклов в системе СКАТ //Проблемы теоретического и системного программирования.— Новосибирск, 1982.— С. 46—59.

8. Глушков В. М., Цейтлин Г. Е., Ющенко Е. Л. Алгебра. Языки программирования.— Киев: Наукова думка 1978.— 318 с.

9. Годлевский А. Б„ Кривой С. Л. Об оптимизации спроектированных методами «сверху-вниз» программ //Модели в системы обработки информации.— Киев: Вища школа, 1984.— Вып. 3.- С. 2532.

10. Горелик А. М. Средства оптимизации в новой версии трансляторов с языка Фортран.— Препринт/ИПМ АН СССР.— М„ 1979-№12-27 с.

11. Гроппен В.О., Томаев М.Х. Модели, алгоритмы и средства программной поддержки проектирования оптимальных программных продуктов //Автоматика и телемеханика. 2000.

12. Гроппен В.О. Оптимизация программного обеспечения ЭВМ на базе игровых моделей// Автоматика и телемеханика № 8, 1986 г., стр. 135-143.

13. Гроппен В.О., Томаев М.Х. Теоретические принципы проектирования оптимальных программных продуктов// Труды СКГТУ, вып.7 2000, Терек.

14. Гроппен В.О., Томаев М.Х. Технология оптимизации конечных алгоритмов //Научные труды аспирантов СКГТУ, Терек.

15. Гроппен В.О. Мазин В.В. Эффективная реализация одной стратегии взаимодействия внешней и оперативной памяти ЭВМ//Тезисы докладов XI всесоюзного совещания по проблемам управления. Ташкент, 1989 г. С. 202.

16. Гроппен В.О. Мазин В.В. Лавровский В.Л. Теоретические основы создания эффективного программного обеспечения ЭВМ// Тез. Докладов научно-технической конференции посвященной 60-летию СКГМИ, Владикавказ, 1991г. С.202-203.

17. Гроппен В.О. Принципы оптимизации программного обеспечения ЭВМ.// Изд. РГУ, Ростов-на-Дону, 1993 г.

18. Гроппен В.О. Эффективные стратегии использования кэшпамяти.// Автоматика и телемеханика № 1, 1993 г., с. 173-179.

19. Дзелинская А. А. Чистка циклов в крупноблочных схемах // Языки и системы программирования.— Новосибирск, 1981.- С. 6474.

20. Дюар Р. Б. К., Гранд А. и др. Сетл как инструмент построения качественного программного обеспечения //Создание качественного программного обеспечения.— Новосибирск. 1978-Т.2.-С.94-106.

21. Евстигнеев В. А. Применение теории графов в программировании. М.: Наука, 1985,- 351 с.

22. Ершов А. П. Сведение задачи экономии памяти при составлении программ к задаче раскраски вершин графов // Докл. АН СССР,— 1962— Т. 152, IV' 2— С. 785—787.

23. Ершов А. П. Об операторных схемах над общей и распределенной памятью // Кибернетика.— 1968.— № 4.— С. 63—71.

24. Ершов А. П. Универсальный программирующий процессор // Проблемы прикладной математики и механики.— М., 1971.— С. 103—116.

25. Ершов А. П. Аксиоматика распределения памяти//Тр. симпоз. «Теория языков и методы построения систем программирования».— Киев, 1972.— С. 3—21.

26. Ершов А. П. Современное состояние теории схем программ // Проблемы кибернетики.— М.: Наука, 1973.— Вып. 27.-С. 87110.

27. Ершов А. П. Введение в теоретическое программирование (беседа о методе).— М.: Наука, 1977.— 288 с.

28. Ершов А. П. Трансформационный подход в технологии программирования // Технология программирования. Тез. докл. 1 Всесоюзы, конф. Пленарные доклады и общие материалы.— Киев, 1979.— С. 12—26.

29. Ершов А. П. Смешанные вычисления: потенциальные применения и проблемы исследования //Методы математической логики в проблемах искусственного интеллекта. Систематическое программирование.— Вильнюс, 1980.— Ч. 2.— С. 26—55.

30. Ершов А. П. Комплексное развитие системного программного обеспечения — постановка проблемы.— Препринт // ВЦ СО ЛИ СССР,—Новосибирск, 1983,—№ 469.—38 с.

31. Ершов А. П„ Касьянов В. Н., Покровский С. Б. и др. Методика разработки многоязыковых трансляторов на примере системы БЕТА //Математическая теория и практика систем программного обеспечения.— Новосибирск, 1982.— С. 64— 80.

32. Ершов А. П., Курочкин В. М. О некоторых проблемах автоматического программирования //Тр. Всесоюз. совещ. по вычисл. математике и применению средств вычисл. техники.— Баку, 1961.— С. 72—80.

33. Ершов А. П., Сабельфельд В. К. Очерк схемной теории рекурсивных программ //Трансляция и модели программ.— Новосибирск, 1980,—С. 23—43.

34. Зима Е. В. Автоматическое построение систем рекуррентных соотношений // ЖВММФ.—1984,—Т. 24, № 12,—С. 1987— 1992.

35. Иткин В.Э. Критерий реализуемости схем над распределенной памятью // Кибернетика.— 1971.— № 1.— С. 143—145.

36. Касьянов В. Н. Анализ управляющих графов программ //Системное программирование.— Новосибирск, 1973.— Ч. 1.— а 13»-154.

37. Касьянов В. Н. К оценке частоты выполнения операторов и переходов в программе//Программирование.—1975.—М 5.— С. 64—72.

38. Касьянов В. Н. О нахождении аргументов и результатов операторов в схемах с косвенной адресацией // Программирование-— 1976—№1.с. 6—15.

39. Касьянов В. Н. К вопросу о реализации схем над распределенной памятью//Кибернетика.— 1977.—№ 1.— С. 63—68.

40. Касьянов В. Н. Практический подход к оптимизации программ. // Препринт /ВЦ СО АН СССР,—Новосибирск, 1978,— № 135— 43 с.

41. Касьянов В. Н. Разгрузка участков повторяемости.— Препринт/ВЦ СО АН СССР,—Новосибирск, 1979,—№ 178,—26 с.

42. Касьянов В. Н. Анализ структур программ //Кибернетика.-1980.- № 1,- С. 48-61.

43. Касьянов В. Н. Смешанные вычисления и оптимизация программ // Кибернетика,— 1980,— № 2,— С. 51—54.

44. Касьянов В. Н. Перераспределение памяти в крупноблочных программах //Трансляция и модели программ.— Новосибирск, 1980.— С. 81—93.

45. Касьянов В. Н. Свободные интерпретации крупноблочных схем // Теоретические основы компиляции.— Новосибирск, 1980,— С. 24—36.

46. Касьянов В. Н. К обоснованию алгоритмов преобразования крупноблочных программ //Программирование.—1981.— № 3.- С. 16-25.

47. Касьянов В. Н. Вопросы конкретизации программ //Проблемы системного и теоретического программирования.— Новосибирск, 1982,—С. 35—45.

48. Касьянов В. Н. Быстрый алгоритм выделения максимальных линейных участков в программе //Математическая теория и практика систем программного обеспечения.— Новосибирск, 1982.— С. 81—87.

49. Касьянов В. Н. Редуцирующие преобразования программ //Трансляция и оптимизация программ.— Новосибирск, 1983.— С. 86-98.

50. Касьянов В. Н. Спецификация контекста для редукции программ //Проблемы системного я теоретического программирования.—Новосибирск, 1984.—С. 3—14.

51. Касьянов В. Н. Эквивалентные преобразования линейных участков программ //Трансляция и преобразования программ.— Новосибирск, 1984,—С. 56—61.

52. Касьянов В. Н. Введение в теорию оптимизации программ.— Новосибирск, 1985.— 259 с.

53. Касьянов В. Н. Учет априорной информации при анализе свойств состояний программ //Математическая теория программирования.—Новосибирск, 1985.—С. 150—158.

54. Касьянов В. Н., Поттосин И .В. Применение методов оптимизации к проверке правильности программ //Создание качественного программного обеспечения.— Новосибирск, 1978.-7. 1.-С. 225-237.

55. Котов В. Е. Введение в теорию схем программ.//Новосибирск: Наука, 1978,— 258 с.

56. Кривой С. Л. Об одном алгоритме поиска инвариантных соотношений в программах //Кибернетика.—1981.— № 5.— С. 12-18.

57. Лавров С. С. Об экономии памяти в вамкнутых операторных схемах //ЖВММФ- 1961,- Т. 1, № 4,- С. 687—701.

58. Левитин В. В. Реализация оптимизирующего транслятора с языка Паскаль для ЕС ЭВМ.—Препринт/ОНТИ НЦБИ АН СССР,— Пущине, 1982,— 16 с.

59. Летичевский А. А. Эквивалентность и оптимизация программ // Теория программирования.— Новосибирск. 1972.— Ч. 1—С. 166180.

60. Летичевский А. А. Об одном подходе к анализу программ // Кибернетика,— 1979,— № 6,— С. 1—8.

61. Любимский Э. 3. О формальной постановке вадачи реализации циклов // Программирование.— 1979.— № 5.— С. 3—10.

62. Любимский Э. 3., Миташюнас А. Ю. О задаче реализации составных циклов //Программирование.— 1981.— № 1.

63. Мартынюк В. В. Выделение цепей в схемах алгоритмов // ЖВММФ— 1961.— Т. 1, № 1.— С. 151—162.

64. Мартынюк В. В. Об экономном распределении памяти// ЖВММФ,- 1962,- Т. 2, № 3,- С. 445-458.

65. Мартынюк В. В. Об анализе графа переходов для операторной схемы //ЖВММФ.— 1965.- Т. 5.- № 2,- С. 298-310.

66. Миташюнас А. Ю., Тарасов В. В. Об одном свойстве реализации циклов специального вида //Программирование,— 1980.— № 1,—С. 3—10.

67. Непомнящий В.А., Дехтярь М.И. Математическая теория программирования. Обзор зарубежных работ.— Препринт//ВЦ СО АН СССР,—Новосибирск, 1982,—№ 341,—52 с.

68. Оптимизация и преобразования программ.// Материалы Всесоюзного семинара.— Ч. 1, 2.— Новосибирск, 1983.

69. Островский В. В. Формальное исследование алгоритмов реализации циклов оптимизирующими трансляторами. Авто-реф. дис. на соискание учен. степ. канд. физ.-мат. наук.— М.: МГУ, 1983.-16 с.

70. Поддерюгин В. Д. Программа контроля для «СТРЕЛЫ-3» (луч).- М.: ВЦ АН СССР-1960.- 23 с

71. Поттосин И. В. Оптимизирующие преобразования и их последовательность // Системное программирование.— Новосибирск, 1973,—4.t.—С. 128—137.

72. Поттосин И. В. Глобальная оптимизация, практический подход // Тр. Всесоюз. симпоз. по методам реализации новых алгоритмических языков.—Новосибирск, 1975.—Ч. 1.—С. 113— 128.

73. Поттосин И. В. О роли и методах оптимизации программ // Перспективы развития в системном и теоретическом программ мировании,—Новосибирск, 1978.—С.

74. Поттосин И. В. К обоснованию алгоритмов оптимизации программ // Программирование.— 1979.— № 2.— С. 3—13.

75. Поттосин И. В. Направление преобразования линейного участка //Языки системы программирования.— Новосибирск, 1981.— С. 47—63.

76. Поттосин И. В. О математических моделях программ, ориентированных па оптимизацию программ //Mathematical methods in in-formatic.— Varna, 1981.— P. 1—24.

77. Поттосин И. В. Возможности оптимизации программ и перспективы ее развития //Актуальные проблемы развития архитектуры и программного обеспечения ЭВМ и вычислительных сетей,— Новосибирск. 1983.— С. 793—796.

78. С абельфельд В.К. Реализация процедур в многоязыковом трансляторе //Тр. Всесоюз, спмпоз. по методам реализации новых алгоритмических языков.— Новосибирск, 1975,— Ч. 1.— С. 129— 143.

79. Томаев М.Х. Средства программной поддержки САПР оптимальных программных продуктов //Труды СКГТУ, вып.7 2000, Терек.

80. Томаев М.Х. Создание оптимального программного обеспечения //Научные труды аспирантов СКГТУ, Терек.

81. Уичман Б. А. Оптимизация //Мобильность программного обеспечения,—М.: Мир, 1980,—С. 172—183.

82. Ходулев А. Б. Реализация глобального оптимизатора Фортран-программ,—Препринт/ИПМ АН СССР,—М., 1982.— № 92.— 27 с.

83. Ходулев А. Б. Исследование возможностей оптимизации программ на языке фортран: Автореф. дис. на соискание учен. степ, канд. физ.-мат. наук,—М.: ИПМ АН СССР, 1984.—20 с.

84. Черноброд Л.В. Оптимизация теоретико-множественных операций в языке СЕТЛ //Системное и теоретическое программирование,— Новосибирск, 1973.— С. 33—38.

85. Штаркман Вик. С. Исследование методов локальной оптимизации и их реализация в трансляторе с расширенного фортрана (фо-рекс): Автореф. дис. на соискание учен. степ. канд. физ.-мат. наук,— М.: ИПМ АН СССР, 1981.

86. Шура-Бура М. Р., Любимский Э. 3. Транслятор Алгол-60 // ЖВММФ—1964.-Т. 4, № I—С. 96—112.

87. Alien F. E. Program optimization // Ann. Rev. Automat. Program.— 1969,- V. 5,- P. 239-307.

88. Alien F. E. Control Flow Analysis //SIGPLAN Notices.— 1970.— V. 5, № 7,—P. 1—19.

89. Alien F. E. A basis for program optimization //Proc. IFIP Congress 71.—Amsterdam, 1971.—V. 1,—P. 385—390.

90. Alien F. E., Carter J. L. et al. The experimental compiling system //IBM J. Res. and Develop.—1980,—V. 24, №6,— P. 697—715.

91. Babich W. A„ Jazayeri M. The method of attributes for data flow analysis: P. 1. Exhaustive analysis//Acta Inform.— 1978.—V. 10, №3.—P. 245—264; II. Demand analysis—Acta Inform.- 1978,- V. 10, № 3.- P. 265-272.

92. Bauer F. L., Berghammer R., Broy M. et al. The Munich Project CIP //Lecture Notes in Computer Science.—1985,— V. 183.— 275 p.

93. Boyle D., Mundy R., Spence T. M. Optimization and code generation in a compiler for several machine // IBM J. Res. and Develop.— 1980,— V. 24, № 6.— P. 677—683.

94. Busam V. A„ Englund D. E. Optimization of expressions in FORTRAN // Comm. ACM—1969,— V. 12, № 2,— P. 666-674.

95. Cocke J. Global common subexpression elimination // SIGPLAN Notices.- 1970,- V. 5, № 7,- P. 20-24.

96. Cocke J., Kennedy K. An algorithm for reduction of operator strength // Comm. ACM.— 1977,—V. 20, №11 .—P. 850—855.

97. Earley J. High level iterators and a method of data structure choice // J. Comput. Languages.—1975,— V. I, № 4,— P. 321-342.

98. Earnest C. P. Some topics in code optimization // J. ACM,— 1974— V. 21, № 1,— P. 76—102.84

99. Earnest C. P., Baike K. G., Anderson J. Analysis of graphs by ordering of nodes//. ACM.—1972,—V. 19, № 1,—P. 23—42.

100. Faiman R. N„ Jr., Kortesoja A. A. An optimizing Pascal compiler// IEEE Trans, on Software Eng.—1980.— V. 6, № 5— P. 506—511.

101. Fong A. C. Elimination of common subexpressions in very high level languages // Proc. of 4th ACM Symp. on Principles of Program. Languages.— Los Angeles, 1977.— P. 48—57.

102. Fong A., Ullman J. D. Finding the depth of a flow graph // J. Corn-put. and System. Sei.—1977,— V. 15, № 4,— P. 300-309.

103. Groppen V.O. Software optimization by game models //14-th IFIP Conference on System modeling and Optimization. Leipzig, Germany, July 3-7, 1989, p.5-6.

104. Groppen V.O. Models and algorithms of software optimization. //1-st IFAC Workshop on Modeling and Architectures for real-time Control. Abstracts. 11-13 September, 1991, Bangor, North Wales, United Kingdom, p. 46-47.

105. Groppen V.O. Expert systems for computer memory optimal control. // IFAC Workshop on Safety, Reliability and Applications of Emerging Intelligent Control Technologies. Hong Kong, 12-14 December 1994 , p. 226-228.