1. АНАЛИЗ СТРУКТУРНОЙ СЛОЖНОСТИ

Методы и алгоритмы структурного анализа подробно рассмотрены в [2, 3]. В частности, результаты этого анализа позволяют строить эффективные стратегии планирования процессов параллельного выполнения функциональных программ на кластерах [2].

1.1 Структурная сложность

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

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

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

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

, (1.1.1)

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

Введем необходимые далее определения.

1. Переменная непосредственно зависит от в (1.1.1), если входит в терм . Отношение непосредственной зависимости между и обозначим .

2. Множество переменных, принадлежащих транзитивному замыканию непосредственной зависимости для будем обозначать [ ] и будем называть [ ] – множеством или классом транзитивности . Для пустого множества введём символ . Ясно, что если [ ] = , то – терм-композиция только базисных функций.

3. Функция определена рекурсивно, если .

4. Рекурсивное определение является простым, если .

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

6. Определение – простое, если не является рекурсивным и [ ] не содержит рекурсивных определений.

7. Определения и взаимно рекурсивны, если и . Легко показать, что в этом случае .

8. Назовём классом взаимной рекурсивности для множество всех взаимно рекурсивных с определений. Будем обозначать класс взаимной рекурсивности для через . Очевидно, что для взаимно рекурсивных определений классы взаимной рекурсивности будут эквивалентны. Легко показать, что неэквивалентные классы взаимной рекурсивности не пересекаются.

9. Определение вложено (строго вложено) в , если (если и ). Очевидно, взаимно рекурсивные определения вложены друг в друга. Если определение – циклическое определение (простое циклическое определение), то будем также говорить, что – циклическое вложение в определение (простое циклическое вложение в ).

10. Введём отношение строгого включения ( ) между классами , которое позволяет сравнивать структурную сложность определений функций , в (1.1.1). При этом интуитивно ясно, что если , то со структурной и вычислительной точек зрения не сложнее . Для , , т.е. можно принять, что структурная и вычислительная сложность равны.

11. Назовём и в (1.1.1) независимыми, если . При определения и в (1.1.1) будем полагать частично зависимыми по переменным, входящим в пересечение .

12. Назовём степенью рекурсивности в (1.1.1) суммарное количество рекурсивных определений в , положив её равной 0, если таких определений нет.

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

14. Назовём степенью взаимной рекурсивности в (1.1.1) суммарное количество входящих в функций таких для всех

15. Назовем степенью непосредственной зависимости от в (1.1.1) суммарное количество вхождений в терм

Введённое отношение включения, а также отношения равенства и пересечения между множествами , , позволяет сравнивать по структурной и вычислительной сложности различные определения функций в (1.1.1). Кроме того, рекурсивные определения задают некоторый более высокий уровень структурной и вычислительной сложности функций по сравнению с простыми определениями. Этот факт используется в разработанном алгоритме планирования параллельного выполнения функциональных программ на вычислительных системах, в котором разрешено только рекурсивно определённые функции назначать на различные компьютеры системы, увеличивая таким образом “зернистость” распараллеливания и уменьшая интенсивность межкомпьютерных обменов в процессе параллельного выполнения функциональной программы [2, 3]. Изложенный подход к анализу структурной сложности функциональных программ по их функциональным схемам можно расширить для того, чтобы иметь возможность более точной дифференциации по сложности определяемых в программе функций.

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

Рассмотрим следующий пример.

Пусть задана функциональная схема

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

рис. 1.1.1 Граф непосредственной зависимости

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

В рассмотренной схеме имеются следующие классы взаимной рекурсивности:

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

рис. 1.1.2 Граф вложенности

рис. 1.1.3 Обозначения вершин ациклического графа: а – нерекурсивное определение X, б – циклическое определение X, в – класс взаимной рекурсивности .

1.2 Демонстрация работы подсистемы структурного анализа

В рамках создания инструментальной среды проектирования функциональных программ на языке FPTL [1], разрабатываемой в научной группе Кутепова В.П., была реализована подсистема структурного анализа функциональных программ, интегрированная в среду Microsoft Visual Studio 2005.

Рассмотрим работу подсистемы на примере функциональной программы сортировки массива методом пузырька (программа BubbleSort – см. Приложение 1).

Для перехода к структурному анализу, необходимо выбрать соответствующий пункт меню на панели инструментов FPTL (см. рис. 1.2.1).

Рисунок 1.2.1 - Вызов подсистемы структурного анализа

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

Рисунок 1.2.2 – Окна структурного анализа

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

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

• Вывести вершину – возможность вывода графа непосредственной зависимости функции, изображаемой данной вершиной, в отдельном окне (напр., для функции SCANREC1 – см. рис. 1.2.3).

• Переименовать – возможность переименования вершины.

• Удалить – удаление вершины (и всех смежных с ней ребер) из графа.

• Сделать рекурсивной – добавление петли к вершине, т.е. связи с самой собой; если вершина уже являлась до этого рекурсивной, степень непосредственной зависимости увеличивается на единицу (на графе отображается в виде числа рядом с ребром).

• Задать сложность – задание целочисленного значения сложности выбранной вершине (на графе отображается рядом с вершиной).

• Транзитивное замыкание – возможность свернуть/развернуть транзитивное замыкание функции, изображаемой данной вершиной (напр., для функции SCANREC1 – см. рис. 1.2.4).

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

Рисунок 1.2.3 – Граф непосредственной зависимости для функции SCANREC1

Рисунок 1.2.4 – Граф со свернутым транзитивным замыканием функции SCANREC1