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

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

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

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

Решение первой проблемы берет на себя технология OurGrid. Технология OurGrid представляет собой законченное решение для выполнения BoT-приложений (Bag-of-Task) на grid-узле. BoТ-приложения представляют собой параллельные приложения, задания которых могут работать независимо друг от друга. Под независимостью понимается, отсутствие необходимости выполнять задания в определенном порядке. Технология OurGrid позволяет задавать конфигурацию выделяемых ресурсов (количество рабочих машин, их архитектуру и производительность) в момент обработки задания на выполнение. Поэтому программист имеет возможность для ручной настройки этой конфигурации ресурсов динамически, без перекомпиляции исходного кода программы, выполняемой на grid-узле.

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

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

Для решения второй проблемы используется платформонезависимый язык программирования Java. Код программы написанной на языке Java не привязан к какой-либо конкретной операционной системе или архитектуре процессора. На каждой машине, которая может использоваться как вычислительный элемент grid-узла (GUM), должна быть установлена виртуальная машина языка Java (Java Virtual Machine, JVM). Именно JVM обеспечивает выполнение Java-программы, на конкретном физическом процессоре и операционной системе. Конечно данный подход приводит к некоторым дополнительным затратам дополнительной оперативной памяти и снижению производительности, но именно такой способ позволяет разрабатывать единственную программу, сразу для большого числа различных операционных систем и процессоров.

Рассмотрим пример использования grid-технологий для нахождения гамильтоновых путей в графе.

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

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

Для понимания принципа распараллеливания данной задачи рассмотрим граф, представленный на рис. 1, состоящий из 6 вершин.

Рис 1. Взвешенный связный граф

Задача: начиная с первой вершины обойти все вершины и вернуться обратно в первую, при этом найти маршрут с минимальными затратами(длиной).

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

№	Маршрут	Длина маршрута	№	Маршрут	Длина маршрута
1	1, 2, 3, 4, 5, 6, 1	23	11	1, 4, 6, 5, 3, 2, 1	21
2	1, 2, 3, 4, 6, 5, 1	16	12	1, 5, 3, 2, 6, 4, 1	28
3	1, 2, 3, 5, 4, 6, 1	25	13	1, 5, 3, 4, 6, 2, 1	21
4	1, 2, 3, 5, 6, 4, 1	21	14	1, 5, 4, 3, 2, 6, 1	30
5	1, 2, 6, 4, 3, 5, 1	21	15	1, 5, 6, 2, 3, 4, 1	26
6	1, 2, 6, 5, 3, 4, 1	24	16	1, 5, 6, 4, 3, 2, 1	16
7	1, 4, 3, 2, 6, 5, 1	26	17	1, 6, 2, 3, 4, 5, 1	30
8	1, 4, 3, 5, 6, 2, 1	24	18	1, 6, 2, 3, 5, 4, 1	35
9	1, 4, 5, 3, 2, 6, 1	25	19	1, 6, 4, 5, 3, 2, 1	35
10	1, 4, 6, 2, 3, 5, 1	28	20	1, 6, 5, 4, 3, 2, 1	23

Табл.1 гамильтоновы циклы для графа, приведенного на рис. 1

Пути с максимальными затратами – это пути № 9 и №18. С минимальными затратами – 2 и 16. Именно пути №2 и №16 наиболее интересны с точки зрения нахождения оптимального решения для поставленной задачи.

Так как вершина старта и финиша – одна и та же вершина, то максимально возможное число замкнутых маршрутов в полносвязном графе составит (n+1)!, где n– количество вершин графа. В общем случае длины всех маршрутов различные и один из них оптимальный (самый короткий), при условии что он существует.

В настоящее время известно несколько алгоритмов решения задачи коммивояжера, отличающиеся друг от друга эффективностью. Одним из алгоритмов нахождения гамильтоновых путей является алгоритм с возвратом (back-tracking algorithm). Чтобы найти оптимальный путь, необходимо рассмотреть все возможные гамильтоновы циклы, и из них выбрать путь с минимальными затратами. При увеличении числа вершин n количество рассматриваемых вариантов стремительно растет. Поэтому на современных персональных компьютерах даже для небольших графов n<20, работа алгоритма с возвратом по нахождению оптимального пути может продолжаться достаточно длительное время.

Чтобы сократить время решения задачи можно воспользоваться grid-узлом. Идея заключается в том, чтобы различным GUMам задать различные начальные условия по нахождению оптимального пути. Например, для рассмотренного выше графа можно сформировать четыре (по числу ребер исходящих из вершины №1) различных начальных условия. Первому GUMу необходимо найти оптимальное решение в графе, с условием, что путь обязательно должен начинаться с вершин 1, 2. Для второго GUMа, начало пути должно пролегать через вершины 1 и 4. Для третьего, через вершины 1 и 5. И для четвертого GUMа, через вершины 1, 6. Таким образом, первоначальное множество всевозможных гамильтоновых путей разбивается на четыре непересекающихся подмножества. Каждый из GUMов в процессе решения задачи находит оптимальный путь в своем подмножестве гамильтновых путей. Так для нашего примера первый GUM найдет маршрут под № 2 (длина равна 16). Второй GUM под № 11 (21). Третий под № 16 (16). Четвертый под № 20 (23). Теперь необходимо выбрать оптимальное решение из четырех предоставленных. Для данного примера это либо путь №2 либо 16.

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

Java-апплет поиска минимальных гамильтоновых путей с помощью GRID-узла МОЦ Aptech.