Автоматизированные инструментальные средства оптимизации исходных кодов больших программных систем

Automated tools for optimizing the source code of large software

УДК 004.021

06.10.2017
 

Выходные сведения:
Томаев М. Х. Автоматизированные инструментальные средства оптимизации исходных кодов больших программных систем // ИТпортал, 2017. №4 (16). URL: http://itportal.ru/science/tech/avtomatizirovannye-instrumentalnye-/

Авторы:
Томаев М. Х., к.т.н, доцент кафедры «Автоматизированной обработки информации» Северо-Кавказского Государственного Горно-Металлургического Института (Государственного Технологического университета). Владикавказ, Российская Федерация (362021 Россия, г. Владикавказ, ул. Николаева 44),
e-mail: tmxwork@mail.ru.

Authors:
Tomaev M. H., Ph.D., assistant professor of dept. «Automated information processing» North-Caucasian Institute of Mining and Metallurgy (State Technology University). Владикавказ, Russian Federation (362021 Russian, Vladikavkaz, street Nikolaeva 44), e-mail: tmxwork@mail.ru.

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

Keyword:
automation, optimization, program, sub-system, module, criterion, model, method, quality, performance

Аннотация: 
В статье представлены результаты научно-исследовательской работы, основная цель которой — создание моделей и методов оптимизации пользовательского исходного программного кода. В первой главе раскрывается идея метода оптимизации, минимизирующего время работы с «медленной» памятью ЭВМ (внешними носителями информации), обосновывается его актуальность. Вторая глава описывает содержание работы: 1) подходы к формулировке и решению многокритериальных оптимизационных задач, способы определения критериев качества; 2) дискретные оптимизационные модели, минимизирующие время работы с медленной памяти больших программных систем (размер которых существенно превышает доступный объем оперативной «быстрой» памяти) 3) эффективные методы решения, позволяющие сократить время поиска оптимума, по сравнению с общими комбинаторными алгоритмами. 4) программный продукт, представляющий собой надстройку к популярной среде разработки Microsoft Visual Studio (используется технология VSIX) и реализующий предложенные подходы в виде автоматизированного средства оптимизационных преобразований. В третьей главе перечисляются значимые научные (математические модели) и прикладные (алгоритмы и программный продукт) результатов, полученные при выполнении данной работы. Заключительная глава включает подведение итогов и оценку перспектив дальнейших исследований в направлении создания новых технологий оптимизации пользовательских исходных программных кодов.

Работа выполнена при финансовой поддержке РФФИ (Российский Фонд Фундаментальных Исследований) и Министерства образования и науки Республики Северная Осетия — Алания в рамках научного проекта № 17-41-15081217.

Annotation: 
The article presents the results of research work, the main objective of which is the creating of the models and methods for user’s source program code optimization. In the first Chapter explains the idea of optimization method that minimizes the time of work with the «slow» computer memory (external storage media), its relevance is justified. The second Chapter describes the content of the work: 1) approaches to the formulation and decision of multicriteria optimization problems, ways of determining quality criteria; 2) discrete optimization models that minimize the slow memory access time in the large software systems (the size of which considerably exceeds the available amount of the «fast» memory — RAM). 3) effective solutions, allowing to reduce the search time of the optimum, compared to the general combinatorial algorithms. 4) software program product which is the add-on to the popular development environment «Microsoft Visual Studio» (using technology VSIX) and implement the proposed approaches in the form of automated tools for the optimizing transformations. The third Chapter lists important scientific (mathematical models) and applied (algorithms and software) results obtained after the execution of this work. The final Chapter includes a summary and evaluation of perspectives for further research in the direction of creating new technologies of the user program source codes optimization.

This work carried out with the financial support of RFBR (Russian Foundation for basic Research) and the Ministry of education and science of the Republic of North Ossetia — Alania in the framework of scientific project No. 17-41-15081217.

1. Введение

Целью исследований, выполненных в рамках гранта РФФИ № 17-41-15081217, является создание технологии, обеспечивающей автоматизацию процессов оптимизации [1, 2, 3] пользовательских исходных программных кодов на основе объективно сформулированных критериев качества. Основным научным результатом работы стала система дискретных моделей, представляющих собой формальную постановку поиска оптимальной декомпозиции [3, 4, 5] пользовательской программной системы, минимизирующей время работы с внешней [6, 7] медленной памятью (глава 2 — задачи (7), (8)). Для решения этих задач предложены эффективные алгоритмы (глава 3), не использующие комбинаторных процедур. Прикладным результатом стала программная реализация методов решения оптимизационных моделей: В частности, был создан автоматизированное инструментальное средство, дополняющее возможности популярной среды разработки MS Visual Studio модулем оптимальной декомпозиции. Выполнены тестирование и отладка программного продукта.

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

Предлагаемый в работе подход к оптимальному разбиению (декомпозиции) исходного кода опирается на анализ пользовательского алгоритма, структура которого, для удобства формулировок, описана в терминах теории графов [8, 9, 10, 11].  Дерево переходов состояний описывает последовательность вызова элементарных неделимых программных единиц. В прикладной программной разработке, реализованной в рамках данной работы, в качестве элементарной единицы была принята функция, так как в состав большинства операционных систем включены удобные средства оформления пользовательского объектного кода в виде библиотек функций. К примеру, в ОС Windows набор функций подсистемы можно оформить в виде динамически подключаемой библиотеки (dynamic link library — DLL).  Минимизация времени на обслуживание операций загрузки подобных библиотек составляет смысл оптимизации работы с медленной памятью.

2. Материалы и методы

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

Для программ простейшей линейной структуры [12, 13, 14] задачу выбора оптимального состава подсистем, минимизирующего время работы программы с медленной памятью можно сформулировать в терминах теории графов в виде задачи поиска кратчайшего пути. Данный подход нагляднее представить на следующем примере:

Пусть пользовательский алгоритм содержит 4 функции, размер каждой из которых равен (в условных единицах): 1, 1, 2, 2.  Путь верхняя граница оперативной памяти, доступной программе 4 единицы, тогда все возможные варианты подсистем удобно представить в виде графа (рис.1), на котором каждая вершина — это состояние программы (текущее состояние вектора данных), а дуги — это подсистемы, переводящие программу из одного состояния в другое. К примеру, дуга (1,2) соответствует подсистеме, включающей только первую функцию, а дуга (3,4,5) — это подсистема, содержащая функции 3 и 4. Граф на Рис.1 содержит только варианты подсистем, суммарный размер функций которых меньше либо равен 4.

         Рис.1. Граф вариантов подсистем.

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

1)  (1 — 3 — 5) Первый модуль включает функции «1» и «2», а второй — функции «3» и «4».

2) (1 — 4 — 5) Первый модуль включает функции «1», «2» и «3», а второй — только функцию «4».

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

Простые линейные системы (в которых последовательность вызова функций никогда не меняется, независимо от входных данных) больших масштабов на практике встречаются крайне редко. Наличие условных операторов в коде системы обуславливает возможность существования множества способов завершения программы. В этом случае термин «производительность» может требовать уточнения, так как время работы программы зависит от последовательности вызова функций. В данной работе предлагается подход, основанный на «пессимистической» оценке вероятностей операторных переходов, основанный на том, что для оценки качества пользовательского кода выбирается наиболее протяженный по длине путь, составленный из последовательных вызовов функций. Аналогично, для зацикленных программ (систем мониторинга окружающей среды, распознавания, АСУТП непрерывных производственных процессов и подобных систем) выбирается участок, представляющий собой контур максимальной длины. Важно отметить, что в большинстве систем в структуре алгоритма [15] присутствуют как контура[16, 17, 18, 19], так и варианты завершения. В таком случае, участок зацикливания имеет безусловный приоритет по сравнению с линейным участком (в условиях, когда вероятности переходов в условных операторах заранее не известны), так как время зацикливания в одном из контуров теоретически может стремиться к бесконечности. С учетом данных положений, процесс выбора оптимального состава подсистем, минимизирующего работу с медленной памятью, можно разбить на два этапа:

На первом решается задача минимизации времени работы с внешней (медленной памятью) в максимальном контуре:

                                               (1)

где

        – булева переменная, равная единице если j-ая функция, размещается в i-м варианте подсистемы и нулю в противном случае.

         – время загрузки j-ого варианта подсистемы. .

         – индекс критерия. Номер одного из вариантов завершения, т.е. одного из путей  из начального состояния программы в конечное (терминальное) состояние.

        – размер j-ого варианта подсистемы (равен сумме объемов всех включенных в неё функций).

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

                       (2)

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

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

На втором этапе выполняется поиск оптимального состава подсистем для конечного участка, соответствующего максимальному пути из начального состояния программы в один из вариантов завершения (3).

                        (3)

где

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

                              (4)

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

В общем случае, решение задач (1), (3) требует использования различного рода комбинаторных [20] алгоритмов, имеющих переборный характер, и, соответственно, высокую вычислительную сложность. Однако, экспериментальное исследование входных данных, а именно времени, затрачиваемого программой на обслуживание внешних носителей в момент загрузки подсистемы в быструю память, позволило выявить частный случай, наиболее распространенный на практике, позволяющий применить иные, более эффективные, методы решения по сравнению с комбинаторными.

Время чтения данных с внешнего носителя, включает две составляющие:

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

2)    Время непосредственно чтения данных — происходит с линейной скоростью и, соответственно, прямо пропорционально объему считываемого блока данных.

Таким образом время загрузки программной системы, разбитой на N подсистем равно:

                                           (5)

где

 N — количество подсистем. 

 — время подготовки (позиционирования) устройства чтения.

S — скорость чтения с устройства чтения.

— размер i-й подсистемы.

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

                                                   (6)

Можно сделать вывод что выигрыш, получаемый при выборе оптимальной декомпозиции в задачах (1), (3) зависит только от числа подсистем и всегда равен:

                                                                        (7)

где

       — число подсистем, выбранных при решении задач (1), (3).

Учитывая (7), в задачах (1), (3) можно принять значения входных данных  равными константе , т.е. задача минимизации времени поиска решения заменяется эквивалентной задачей минимизации числа подсистем. Т.к. фактическое значение  является величиной постоянной и не влияет на решение, то данной работе оно было принято равным единице:

                                                                 (8)

Далее будет предложен эффективный метод решения, основанный на выводах (7), (8).

2.2. Методы решения оптимизационных задач

Использование свойства (8) позволяет предложить быстрый алгоритм (Алгоритм 1) декомпозиции функций на линейных участках программ (пример решения подобной задачи был рассмотрен в предыдущей главе).

 В следующем алгоритме используются обозначения:

     — размер -й подсистемы. Размер каждой из подсистем и их количество окончательно будут вычислены к концу работы алгоритма.

    — размер -й функции. Эти значения предварительно известны (входные данными алгоритма).

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

Алгоритм 1.

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

Алгоритм 2.

1)    На графе, описывающем алгоритм пользователя, выполняется поиск максимального по времени работы контура .

2)    Размеры функций, составляющих контур подаются на вход Алгоритма 1 (в качестве входных переменных ). Выполняется оптимальная декомпозиция функций.

3)    На графе, описывающем алгоритм пользователя, выполняется поиск максимального по времени варианта завершения программы .

4)    Размеры функций, составляющих максимальный путь подаются на вход Алгоритма 1 (в качестве входных переменных ). Выполняется оптимальная декомпозиция функций, таким образом, чтобы не нарушалась декомпозиция, полученная на шаге 2.

5)    Конец алгоритма.

Методы поиска контуров и экстремальных путей (шаги 1 и 3) используют подходы, изложенные в работе [3].

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

2.3. Описание программной реализации. Оптимизационное дополнение (Add-In) для Microsoft Visual Studio

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

1)    Модуль «CodeOptimizationToolsExtension.vsix» — представляет собой дополнение (Add-In) к популярной среде MS Visual Studio. Технология VSIX позволяет модифицировать стандартный интерфейс среды разработки, добавляя собственные элементы управления (меню, панели инструментов и т.д.). VSIX-модуль используется для добавления новых пунктов в меню «Tools» среды Visual Studio (рис.2):

2)    Приложение «OptimalDecomposition.exe» — представляющее собой средство поиска оптимального состава подсистем (рис.3).

Рис. 2. Новые пункты в меню «Tools» MS Visual Studio 2015.

Первый пункт меню — «Run Optimal Software Decomposition Tool» выполняет запуск непосредственно модуля декомпозиции, автоматически подгружая в него код активного файла, открытого в этот момент в Visual Studio.

Рис.3. Окно модуля оптимальной декомпозиции.

Второй пункт меню — «About Optimal Software Toolkit», — содержит краткие сведения о программе (рис.4).

Рис.4. Окно с краткими сведениями о программе.

Пункт меню «User Guide. Help Topics» вызывает руководство пользователя, включающее описание возможностей программы, технические характеристики, требования к системе, а также подробную инструкцию по эксплуатации (рис.5). Инструкция составлена в формате «RTF» и расположена в файле «UserGuideOPT.rtf».

Рис.5. Руководство пользователя.

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

1)    Загрузка исходного кода — возможна двумя способами : 

а) Автоматически при выборе пункта «Run Optimal Software Decomposition Tool» в меню «Tools» главного окна MS Visual Studio. Если в этот момент имеется хотя бы одно активное окно, содержащее исходный код, то будет выполнено автоматическое копирование соответствующего текста и окно инструмента декомпозиции (рис.2) появится с предварительно заполненным элементом редактирования в своей левой области.

б) Второй способ загрузки документа заключается в использовании кнопки «Открыть» вверху окна (первая кнопка панели инструментов)

2)    Анализ исходного кода — является первым и обязательным этапом оптимизации. Для его запуска необходимо воспользоваться кнопкой «Анализ» на панели (в группе «Оптимизации» в правой области). Результаты анализа отражаются в таблицах «список функций» и «Критерии».

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

Практическая реализация полученных с помощью разработанного программного продукта рекомендаций зависит от версии ОС и реализованных в ней технологий поддержки модульности. В частности, в ОС Windows, декомпозиция исходного варианта кода на DLL-библиотеки будет заключаться в замене вызовов функций, помещенных в библиотеку, обращением к библиотеке с помощью пары API-функций «LoadLibrary» / «FreeLibrary», а также вызовом «GetProcAddress» для получения адреса экспортируемых функций.  

3.    Результаты и обсуждение

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

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

Выбранная модель программной реализации — надстройка «Add-In» к среде «Microsoft Visual Studio», — позволила обойти ряд технических вопросов (напрмер, проблема валидации пользовательского кода), не находящихся в центре данного исследования, но являющихся технологически необходимыми. Кроме того, совместимость с популярной средой «Microsoft Visual Studio», являющейся фактическим стандартом для разработчиков на платформе Windows, также облегчает переход на новые оптимизационные технологии широкому кругу разработчиков.

4.    Выводы

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

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

1.Касьянов В. Н. Практический подход к оптимизации программ. // Препринт /ВЦ СО АН СССР.—Новосибирск, 1978.— № 135,— 43 с.
2.Касьянов В. Н. Введение в теорию оптимизации программ.— Новосибирск, 1985.— 259 с.
3.Касьянов В. Н. Смешанные вычисления и оптимизация программ // Кибернетика.— 1980.— № 2.— С. 51—54.
4.Гроппен В.О. Принципы оптимизации программного обеспечения ЭВМ. Изд. Ростовского университета. 1993 г.
5.Гроппен В.О., Томаев М.Х. Модели, алгоритмы и средства программной поддержки проектирования оптимальных программных продуктов //Автоматика и телемеханика. 2000.
6.Томаев М.Х. Технологии глобальной оптимизации пользовательских программных кодов. Автоматизация и управление в технических системах. – 2015. – № 3. – С. 16-30. DOI: 10.12731/2306-1561-2015-3-2. URL: auts.esrae.ru/15-277.
7.Гроппен В.О. Мазин В.В. Эффективная реализация одной стратегии взаимодействия внешней и оперативной памяти ЭВМ//Тезисы докладов XI всесоюзного совещания по проблемам управления. Ташкент, 1989 г. С. 202.
8.Касьянов В. Н. Перераспределение памяти в крупноблочных программах //Трансляция и модели программ.— Новосибирск, 1980.— С. 81—93.
9.Евстигнеев В. А. Применение теории графов в программировании. — М.: Наука, 1985.- 351 с.
10.Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. М.: Синтег, 2001.
11.Касьянов В. Н. Анализ управляющих графов программ //Системное программирование.— Новосибирск, 1973.— Ч. 1.— C.134-154.
12.Мартынюк В. В. Об анализе графа переходов для операторной схемы //ЖВММФ.— 1965.- Т. 5.- № 2.- С. 298-310.
13.Касьянов В. Н. Быстрый алгоритм выделения максимальных линейных участков в программе //Математическая теория и практика систем программного обеспечения.— Новосибирск, 1982.— С. 81—87.
14.Касьянов В. Н. Эквивалентные преобразования линейных участков программ //Трансляция и преобразования программ.— Новосибирск, 1984.— С. 56—61.
15.Касьянов В. Н. Анализ структур программ //Кибернетика.- 1980.- № 1.- С. 48-61.
16.Касьянов В. Н. Разгрузка участков повторяемости.— Препринт/ВЦ СО АН СССР.—Новосибирск, 1979.—№ 178.—26 с.
17.Дзелинская А. А. Чистка циклов в крупноблочных схемах // Языки и системы программирования.— Новосибирск, 1981.- С. 64-74.
18.Любимский Э. 3. О формальной постановке вадачи реализации циклов // Программирование.— 1979.— № 5.— С. 3—10.
19.Любимский Э. 3., Миташюнас А. Ю. О задаче реализации составных циклов //Программирование.— 1981.— № 1.
20.Родзин С.И., Родзина О.Н. Поиск оптимальных решений комбинаторных задач: теория, эволюционные алгоритмы и их приложения для проблемно-ориентированных информационных систем. Информатика, вычислительная техника и инженерное образование. Изд. Южный Федеральный Университет. Ростов-на-Дону, 2014 — С. 18-33.

References

1.Kas’yanov V. N. Prakticheskij podhod k optimizacii programm. // Preprint /VC SO AN SSSR.—Novosibirsk, 1978.— № 135,— 43 p.
2.Kas’yanov V. N. Vvedenie v teoriyu optimizacii programm.— Novosibirsk, 1985.— 259 p.
3.Kas’yanov V. N. Smeshannye vychisleniya i optimizaciya programm // Kibernetika.— 1980.— № 2.— p. 51—54.
4.Groppen V.O. Principy optimizacii programmnogo obespecheniya EHVM. Izd. Rostovskogo universiteta. 1993.
5.Groppen V.O., Tomaev M.H. Modeli, algoritmy i sredstva programmnoj podderzhki proektirovaniya optimal’nyh programmnyh produktov //Avtomatika i telemekhanika. 2000.
6.Tomaev M.H. Tekhnologii global’noj optimizacii pol’zovatel’skih programmnyh kodov. Avtomatizaciya i upravlenie v tekhnicheskih sistemah. – 2015. – № 3. – S. 16-30. DOI: 10.12731/2306-1561-2015-3-2. URL: auts.esrae.ru/15-277.
7.Groppen V.O. Mazin V.V. EHffektivnaya realizaciya odnoj strategii vzaimodejstviya vneshnej i operativnoj pamyati EHVM//Tezisy dokladov XI vsesoyuznogo soveshchaniya po problemam upravleniya. Tashkent, 1989 . p. 202.
8.Kas’yanov V. N. Pereraspredelenie pamyati v krupnoblochnyh programmah //Translyaciya i modeli programm.— Novosibirsk, 1980.— p. 81—93.
9.Evstigneev V. A. Primenenie teorii grafov v programmirovanii. — M.: Nauka, 1985.- 351 p.
10.Burkov V.N., Zalozhnev A.YU., Novikov D.A. Teoriya grafov v upravlenii organizacionnymi sistemami. M.: Sinteg, 2001.
11.Kas’yanov V. N. Analiz upravlyayushchih grafov programm //Sistemnoe programmirovanie.— Novosibirsk, 1973.— CH. 1.— p.134-154.
12.Martynyuk V. V. Ob analize grafa perekhodov dlya operatornoj skhemy //ZHVMMF.— 1965.- T. 5.- № 2.- p. 298-310.
13.Kas’yanov V. N. Bystryj algoritm vydeleniya maksimal’nyh linejnyh uchastkov v programme //Matematicheskaya teoriya i praktika sistem programmnogo obespecheniya.— Novosibirsk, 1982.— p. 81—87.
14.Kas’yanov V. N. EHkvivalentnye preobrazovaniya linejnyh uchastkov programm //Translyaciya i preobrazovaniya programm.— Novosibirsk, 1984.— p. 56—61.
15.Kas’yanov V. N. Analiz struktur programm //Kibernetika.- 1980.- № 1.- p. 48-61.
16.Kas’yanov V. N. Razgruzka uchastkov povtoryaemosti.— Preprint/VC SO AN SSSR.—Novosibirsk, 1979.—№ 178.—26 p.
17.Dzelinskaya A. A. CHistka ciklov v krupnoblochnyh skhemah // YAzyki i sistemy programmirovaniya.— Novosibirsk, 1981.- p. 64-74.
18.Lyubimskij EH. 3. O formal’noj postanovke vadachi realizacii ciklov // Programmirovanie.— 1979.— № 5.— p. 3—10.
19.Lyubimskij EH. 3., Mitashyunas A. YU. O zadache realizacii sostavnyh ciklov //Programmirovanie.— 1981.— № 1.
20.Rodzin S.I., Rodzina O.N. Poisk optimal’nyh reshenij kombinatornyh zadach: teoriya, ehvolyucionnye algoritmy i ih prilozheniya dlya problemno-orientirovannyh informacionnyh sistem. Informatika, vychislitel’naya tekhnika i inzhenernoe obrazovanie. Izd. YUzhnyj Federal’nyj Universitet. Rostov-na-Donu, 2014 — p. 18-33.