- различие в производительности процессоров требует соответствующего учета при распределении работы между процессами, выполняющимися на разных процессорах;
- различие в архитектуре процессоров требует подготовки разных выполняемых файлов для разных вычислительных машин.
Решение первой проблемы берет на себя технология OurGrid. Технология OurGrid представляет собой законченное решение для выполнения BoT-приложений (Bag-of-Task) на grid-узле. BoT-приложения представляют собой параллельные приложения, задания которых могут работать независимо друг от друга. Под независимостью понимается, отсутствие необходимости выполнять задания в определенном порядке. Технология 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
Рис 1. Выполнение параллельной программы с использованием grid-узла.
и выглядит следующим образом:
- Пользователь регистрируется в MS Class Server;
- HTML-страница, содержащая Java-апплет загружается на компьютер пользователя;
- Пользователь вводит в апплет исходные данные. Апплет передает данные в MyGrid для выполнения.
- MyGrid делает запрос у Peer, на получение списка компьютеров, способных выполнять задачу;
- Peer, возвращает список свободных компьютеров;
- MyGrid, выбирает компьютеры с подходящей конфигурацией ресурсов и передает данные, необходимые им исходные данные для выполнения задачи;
- Результаты выполнения задачи возвращаются от GUM к MyGrid;
- Результаты выполнения задачи передаются от MyGrid в Java-апплет пользователя, где и отображаются результаты выполнения задачи.
Рассмотрим пример использования grid-технологий для нахождения гамильтоновых путей в графе. Задача нахождения гамильтоновых путей в графе является одной из центральных в теории графов. В отличие от эйлеровых путей, не известно ни одного простого необходимого и достаточного условия для существования гамильтоновых путей в графе. Классическим примером задачи, сводящейся к нахождению гамильтонова пути в графе, является «задача коммивояжера». Задача коммивояжера звучит следующим образом: «В произвольном порядке обойти все вершины замкнутого графа по кратчайшему пути и вернуться в исходную вершину, причем каждая вершина проходится один раз».
Для понимания принципа распараллеливания данной задачи рассмотрим граф, представленный на рис. 2, состоящий из 6 вершин. Задача: начиная с первой вершины обойти все вершины и вернуться обратно в первую, при этом найти маршрут с минимальными затратами(длиной).
Рис 2. Взвешенный связный граф
В таблице 1 для представленного на рис. 2 графа приведены все возможные гамильтоновые циклы. Всего для данного графа существует 20 гамильтоновых циклов, фактически только 10, так как граф неориентированный. Еще 10 симметричных циклов можно получить, изменив на противоположную, последовательность обхода вершин.
Табл.1 гамильтоновы циклы для графа, приведенного на рис. 2
№ |
Маршрут |
Длина маршрута |
№ |
Маршрут |
Длина маршрута |
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 |
Маршруты с максимальными затратами – это маршруты 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-программа, с помощью которой вводится матрица весов графа, и указывается стартовая вершина.
Программа подготавливает файлы с описанием графа и начальными условиями для работы независимых заданий. После чего программа формирует файл (*.jdf) с описанием работы для MyGrid (приведена только его часть):
job :
label : TransportAlgJob
task :
init :
put transport.jar transport.jar
put transport.txt transport.txt
put transport_in_1.txt transport_in_1.txt
remote : nice java -jar transport.jar
transport.txt transport_in_1.txt > transport_out_$TASK.txt
final : get transport_out_$TASK.txt transport_out_$TASK.txt
task :
init :
put transport.jar transport.jar
put transport.txt transport.txt
put transport_in_2.txt transport_in_2.txt
remote : nice java -jar transport.jar
transport.txt transport_in_2.txt > transport_out_$TASK.txt
final : get transport_out_$TASK.txt transport_out_$TASK.txt
Здесь «transport.jar» представляет собой другую Java-программу, выполняемую на GUMах, и непосредственно решающую задачу нахождения гамильтонова пути в графе, описание которого содержится в файле «transport.txt», начальные условия для работы каждого из заданий содержаться в файлах «transport_in_номерзадания.txt». Далее программа запускает работу на выполнение в MyGrid. В результате чего на каждый из GUMов рассылаются файлы «transport.jar», «transport.txt» и файл содержащий начальные условия. На каждом из GUMов запускается на выполнение программа «transport.jar», которая читает файлы с описанием графа и начальными условиями. Результат работы каждого задания помещается в отдельный файл вида «transport_out_номерзадания.txt», которые передаются от GUMов на машину пользователя. Программа на машине пользователя читает файлы с результатами выполнения заданий и сообщает о них пользователю.
