Федеральное агентство по образованию
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Новосибирский государственный университет»
С. П. Ковалёв
Лабораторный практикум
по дисциплине «Современные методы
распределённых вычислений»
Введение
В ходе освоения дисциплины выполняются лабораторные практические задания, заключающиеся в проектировании, реализации и развёртывании масштабируемой проблемно-ориентированной системы распределённых вычислений на базе технологий Grid. В качестве программной платформы для реализации системы используется Globus Toolkit версии 3 (допускается использование версии 4). Подробную информацию о работе с платформой Globus Toolkit версии 3 можно найти по ссылке http://gdp.globus.org/gt3-tutorial/.
1. Рекомендации по развертыванию платформы Globus Toolkit
Рекомендуется следующая конфигурация системного окружения рабочей станции, использующейся для выполнения заданий практикума:
-
ОС Linux -
Среда исполнения Java-приложений, развернутая в каталоге /opt/java -
Средство сборки приложений ant, развернутое в каталоге /opt/ant -
Платформа Globus Toolkit, развернутая в каталоге /opt/gt от имени пользователя globus c паролем globus
Если при компиляции/запуске/инсталляции сервисов или клиентов Globus Toolkit появляются исключения вида NoClassDefinitionFound, следует выполнить следующие команды:
$ . /opt/gt/etc/globus-user-env.sh
$ . /opt/gt/etc/globus-devel-env.sh
Имеются примеры сервисов Globus Toolkit, архив которых находится в следующем файле:
~globus/progtutorial-examples_0.4.3.tar.gz.
Распаковка и настройка примеров осуществляется (от имени пользователя globus) следущими командами:
$ cd ~globus
$ mkdir tutorial
$ cd tutorial
$ tar zxf ../progtutorial-examples_0.4.3.tar.gz
$ echo "ogsa.root=/opt/gt/" > build.properties
Для овладения техникой сборки приложений студенту рекомендуется выполнить следующую контрольную последовательность команд.
1. Компиляция сервиса
$ cd tutorial
$ ./tutorial_build.sh \
org/globus/progtutorial/services/core/first/ \
schema/progtutorial/MathService/Math.gwsdl
В результате должен появиться следующий gar-файл:
./build/lib/org_globus_progtutorial_services_core_first.gar
2. Компиляция клиента
$ cd tutorial
$ javac -classpath ./build/classes/:$CLASSPATH \
org/globus/progtutorial/clients/MathService/Client.java
3. Инсталляция сервиса
$ cd /opt/gt/
$ ant deploy -Dgar.name=/opt/globus/tutorial/build/lib/\
org_globus_progtutorial_services_core_first.gar
4. Запуск контейнера Globus
$ /opt/gt/bin/globus-start-container -p 6666 &
Здесь аргумент -p задаёт номер порта для взаимодействия с контейнером.
После запуска этой команды возможно появление несущественных сообщений об исключительных ситуациях. Признаком корректного запуска контейнера является вывод на экран списка имеющихся сервисов.
5. Запуск клиента
$ cd ~/tutorial
$ java -classpath ./build/classes/:$CLASSPATH \
org.globus.progtutorial.clients.MathService.Client \
https://10.4.0.36:6666/ogsa/services/progtutorial/core/first/\
MathService 123
Здесь первый аргумент java-приложения Client – URL сервиса MathService, второй аргумент – число, которое передается сервису.
2. Постановка задачи для практикума
В качестве задачи, реализацию которой необходимо выполнить в виде Grid-системы, предлагается алгоритм КРАБ кластеризации метрического пространства, представляющий собой модификацию известного метода ветвей и границ. Кластеризация состоит в разбиении множества из M элементов в метрическом пространстве на k классов (таксонов) так, чтобы в каждый таксон попали наиболее похожие друг на друга элементы. Сходство элементов определяется метрикой – «расстоянием» между ними. Примером прикладной задачи, решаемой посредством кластеризации, является выявление крупномасштабной структуры Вселенной. Здесь нужно распределить звезды по скоплениям на фотографии звездного неба (в роли метрики выступает обычное расстояние).
Алгоритм кластеризации КРАБ состоит из следующих шагов.
-
Вычисляются расстояния между всеми парами элементов. Строится полный граф с вершинами – элементами, в котором каждому ребру приписано положительное вещественное число – расстояние между вершинами, которые оно соединяет. -
Для полного графа, полученного на этапе 1, строится минимальный связывающий граф , т.е. граф, в котором существуют пути между каждой парой вершин, нет циклов, а сумма длин ребер минимальна. Этот граф имеет M – 1 ребер. -
Для разбиения на k таксонов из графа удаляют k – 1 ребро, в результате чего он разбивается на k отдельных графов (компонент связности). Для нахождения оптимального разбиения перебираются все варианты такого удаления. Оптимальным считается вариант, на котором следующая функция достигает максимума:
,
где:
ek-1 = (e1, …, ek-1) – набор из k – 1 различных ребер,
(ei) – длина ребра ei,
mj(ek-1) – число вершин в j-м таксоне.
Компоненты связности, полученные после удаления k – 1 ребер в оптимальном варианте, и являются искомыми таксонами.
Самым сложным в этом алгоритме является последний шаг, т.к. остальные шаги не требуют большого объема вычислений. Поэтому нужно построить программную систему, выполняющую этот шаг в режиме распределённых вычислений. На вход ей поступает минимальный связывающий граф и число k, на выходе она выдает разбиение вершин входного графа на k «классов схожести». Вершины графа пронумерованы числами от 0 до M – 1.
Граф задается в виде текстового файла, состоящего из M строк. В первой строке указываются имя задачи (последовательность букв и цифр, начинающаяся с буквы), числа M и k, разделенные пробелами. Каждая из остальных M – 1 строк соответствует одному ребру, она содержит три числа, разделенные пробелами: номер первой вершины, номер второй вершины, длина ребра (положительное вещественное число в формате с фиксированной запятой).
Полученное системой разбиение графа записывается в виде файла из k + 1 строк. В первой строке указываются имя задачи и через пробел значение функции f для оптимального разбиения – вещественное число в формате с плавающей запятой с точностью 10 знаков. Каждая из следующих k строк описывает одну компоненту связности в виде списка вершин, входящих в компоненту, в порядке возрастания номеров, разделенных пробелами. Эти строки упорядочены в порядке возрастания номера первой вершины.
Система реализует перебор разбиений, оптимизированный при помощи метода ветвей и границ. Этот метод состоит в следующем. Пусть дано конечное множество U = {u1, …, un} мощности n, на любом его подмножестве V U мощности k–1 определена числовая функция f (V). Предположим, что для функции f задана верхняя оценка – числовая функция H, определенная на любом подмножестве V ' U мощности не превосходящей k – 1, такая, что если V V ', то f(V) H(V '). Необходимо выбрать такое подмножество W U мощности k – 1, на котором достигается максимум функции f. Для этого реализуется следующий алгоритм.
1. Создается набор активных множеств , в него сразу помещается пустое множество. Выбирается стартовое множество W* = {u1, …, uk-1}, вычисляется стартовый рекорд – число f * = f(W*). Состояние выполнения алгоритма полностью характеризуется тройкой <, W*, f *>, причем всегда f * = f(W*).
2. Выбирается некоторое множество W ' = {up1, …, upj}, 1 p1 < … < pj n, из набора , и сразу удаляется из . Возможны два варианта:
2.1. j < k – 1. Вычисляется H ' = H(W ').
Если H ' > f *, то в набор добавляются все (j + 1)-элементные множества Vi = W ' {ui}, i = pj + 1, …, n.
Иначе (H ' f *) дальнейшее расширение множества W ' не приведет к результату, лучшему, чем текущий рекорд f *, в силу определения функции H. Поэтому сразу выполняется переход на шаг 3.
2.2. j = k – 1. В этом случае вычисляем f ' = f(W ').
Если f ' > f *, то рекорд обновляется, полагая f * = f ', W* = W '.
Иначе (f ' f *) выполняется переход на шаг 3.
3. Проверяется, есть ли в наборе хотя бы одно множество.
Если есть, то выполняется переход на шаг 2.
Иначе работу алгоритма завершается и в качестве результата возвращается множество W*.
Для алгоритма КРАБ метод ветвей и границ применяется следующим образом. В качестве U выступает множество ребер графа , состоящее из n = M – 1 элементов, а в качестве W – наборek-1. Представим максимизируемую функцию f в виде:
f (ek-1) = L(ek-1) S(ek-1), где
, 
.
Построим для функций L и S верхние оценки
и 
, определенные на всех наборахem, где 0 m k–1. Положим
,
где e'i, i = m + 1, …, k – 1 – это k – 1 – m ребер графа, имеющих наибольшую длину среди тех, которые не попали в наборem. Очевидно, что для всякогоek-1 em выполняется условие
.
Далее, имеем 
. Можно показать, что для всякогоek-1 em выполняется условие S(ek-1) S(em). Поэтому положим
.
Окончательно, имеем
.
Отметим, что функция H является точной оценкой для f – для всякого набораek-1 имеет место соотношение H(ek-1) = f (ek-1).
Шаг 2 метода ветвей и границ можно выполнять параллельно, для нескольких множеств из одновременно. Для этого реализуется следующая архитектура. Создается управляющий Grid-сервис, который получает входные данные и выдает выходные, и несколько экземпляров рабочего вычислительного Grid-сервиса. Набор создается и ведется управляющим сервисом. Каждый экземпляр рабочего сервиса ведет свой локальный набор s, над которым он производит некоторое количество итераций шага 2. Он получает стартовое наполнение этого набора от управляющего сервиса (это некоторая часть глобального набора ), а возвращает результирующее наполнение и новые значения W* и f * (если они были изменены им). Можно ограничивать количество итераций шага 2, выполненных в ходе одного обращения к экземпляру рабочего сервиса, длительность его работы, либо мощность локального набора s. Эти ограничения следует сделать конфигурируемыми. Критическим фактором увеличения производительности является обмен рекордами между экземплярами рабочего сервиса непосредственно по ходу вычисления: если какой-либо экземпляр нашел новый рекорд, то его необходимо как можно быстрее разослать по всем остальным экземплярам, чтобы они не выполняли лишних вычислений. Это можно сделать с помощью механизма уведомлений (notification), предусмотренного в OGSA. Взаимодействие пользователя с управляющим сервисом осуществляется через web-броузер: должна быть возможность ввести входной файл и получить выходной, а также задать различные конфигурационные параметры системы.
Для студентов, досрочно решивших задачу в указанной постановке, можно предложить реализовать следующую оптимизацию. Если для некоторого набораem известны значения 
и 
, а также определенные дополнительные промежуточные результаты их вычисления, и к этому набору добавляется ребро em+1, то значение H(em+1) можно вычислить гораздо быстрее, чем непосредственно по исходной формуле. Поэтому вместе с каждым элементом набора можно запоминать нужные промежуточные значения. Однако это требует дополнительного расхода памяти, который может быть значительным при больших M и k. Поэтому можно предоставить две реализации вычислительного сервиса, имеющих одинаковый интерфейс: одна экономит память, но работает медленнее, а другая считает быстрее, но тратит дополнительную память. Выбор той или иной реализации для выполнения очередной порции вычислений осуществляется управляющим сервисом динамически, исходя из общего количества времени и памяти, потраченного задачей на момент инициализации этой порции (с учетом наличия свободных экземпляров каждой реализации). Пороговые значения этих параметров следует сделать конфигурируемыми.
3. Контрольные примеры
Для проверки правильности реализации системы предлагаются следующие 4 контрольных примера – графа из 100 вершин.
|
Task1 100 6 59 61 1.39945 71 73 1.37322 30 90 1.33613 11 91 1.30277 50 78 1.28203 33 57 1.2717 5 85 1.62274 68 92 1.58763 10 73 1.47997 43 64 1.45529 31 39 0.850347 21 26 0.845279 56 74 0.838035 8 12 0.835773 62 89 0.824568 81 88 0.816758 15 17 1.22427 3 44 1.19451 44 77 1.15568 7 30 1.05798 20 54 1.00533 82 99 1.00235 39 83 0.988717 62 96 0.987711 41 96 0.790773 13 14 0.78796 32 78 0.781045 34 66 0.762969 15 87 0.747001 37 58 0.737726 2 13 1.05753 59 95 0.647059 37 60 0.639511 46 60 0.631275 75 87 0.624691 31 79 1.04773 38 77 0.72965 46 52 0.724423 38 45 0.718715 0 17 0.711128 2 27 0.913603 24 83 0.88582 71 76 0.811334 58 76 0.807345 16 72 0.804087 19 72 0.705125 22 97 0.685751 4 18 0.685428 48 53 0.656968 57 93 0.651881 6 74 0.609203 9 43 0.593577 3 85 0.578521 34 89 0.573725 1 5 0.537478 19 69 0.530972 48 97 0.525738 22 80 0.523479 30 67 0.517784 90 93 0.510862 56 81 0.495512 36 80 0.477427 1 75 0.475017 9 57 0.456422 50 51 0.448579 28 86 0.437985 23 98 0.419271 41 74 0.418974 42 69 0.275346 28 33 0.262333 4 35 0.249532 37 63 0.228665 47 61 1.41689 65 83 0.885453 64 95 0.871948 14 34 0.851522 23 72 0.370473 49 63 0.36903 40 42 0.35789 53 67 0.343044 84 87 0.319539 8 64 0.317949 16 70 0.309969 51 55 0.30204 35 88 0.187345 27 40 0.143845 18 25 0.412104 79 94 0.411102 20 35 0.383622 23 36 0.376916 79 97 0.373622 11 93 1.43798 25 92 0.280551 5 55 0.277678 6 49 0.138414 52 99 0.131243 29 65 0.125988 21 68 0.0786342 15 47 0.0636104 |
Task2 100 7 54 59 3.84456 25 95 3.78247 11 13 3.76798 29 98 3.61735 27 28 3.03531 62 67 2.91433 5 9 2.86181 72 78 2.83514 57 60 2.7787 32 35 2.77063 77 79 2.71044 0 97 21.7034 43 83 20.1734 35 53 19.4326 0 39 18.2795 4 75 15.5586 42 44 5.52252 4 7 5.0136 1 2 4.77727 73 74 4.67275 28 61 4.53241 78 79 4.22717 61 67 4.1177 22 23 2.67392 12 16 2.66757 3 5 2.58731 55 60 2.55453 25 91 2.35586 98 99 1.87471 32 39 3.33968 68 70 3.31017 11 14 2.33514 42 50 2.2051 82 84 2.15975 16 19 2.11993 7 8 2.06275 51 58 2.01835 74 75 1.99026 67 69 1.97034 93 94 1.95404 81 89 1.92761 56 60 1.89538 44 49 3.20984 43 47 3.12672 21 24 3.10322 21 26 1.87167 6 10 1.85199 2 4 1.8003 32 38 1.7883 83 87 1.75023 29 97 1.68447 41 44 1.67456 33 36 1.66916 26 28 1.66142 8 10 1.63682 17 20 1.60795 40 81 1.60788 31 37 1.56013 29 96 1.5116 34 40 1.49909 71 72 1.49371 1 5 1.29928 72 74 1.26342 30 92 1.24457 13 15 1.22427 16 18 1.19792 63 65 1.04269 45 46 0.448579 37 88 0.360809 36 38 0.35789 76 79 0.319539 34 86 1.44287 52 57 0.952788 31 90 0.866774 14 17 0.853888 62 63 0.830474 27 92 0.824125 73 80 0.816758 64 69 0.811334 11 12 0.78796 41 47 0.724423 54 57 0.704324 43 48 0.656968 85 88 0.604275 93 97 0.583392 81 84 0.510862 33 85 0.467626 53 58 1.39946 53 55 1.39945 95 99 1.39605 64 66 1.37322 37 89 1.35295 46 50 0.30204 25 30 0.262333 10 19 34.4701 9 48 29.1055 67 70 4.01294 87 90 3.99737 22 94 3.92378 |
Task3 100 7 33 35 0.35789 23 86 59.0554 0 13 15.8561 26 67 13.2507 21 22 7.19176 79 80 6.79169 31 34 4.3873 22 24 4.33836 77 78 3.57307 61 63 1.97034 81 85 1.96449 71 75 1.94718 51 55 1.89538 2 4 1.8003 93 95 4.33376 71 72 4.22717 12 13 4.21479 4 50 9.77113 7 8 8.86523 42 43 8.16356 92 95 4.11976 61 64 4.01294 38 40 3.83347 88 90 3.78735 22 23 3.58158 76 80 1.75023 7 9 1.63682 82 85 1.4664 1 5 1.29928 66 68 1.26342 53 92 39.0135 40 76 36.7661 43 44 3.53654 77 79 3.52463 0 97 3.38002 62 64 3.31017 18 20 3.29817 12 14 1.22427 18 19 1.20906 48 50 1.10044 46 48 1.06878 58 60 1.04269 96 98 0.90299 6 10 0.835773 5 51 48.546 32 65 47.9474 47 49 3.27989 32 35 3.05997 87 90 3.03638 57 59 2.98855 11 13 2.96379 36 39 2.94645 62 65 2.87812 88 89 2.79106 52 55 2.7787 86 89 2.49312 91 92 2.44386 73 74 2.3764 23 25 2.32182 70 84 2.30938 27 30 2.19691 16 17 2.1449 36 37 2.08483 6 7 2.06275 68 69 1.99026 54 98 35.0699 18 56 34.6968 37 91 33.5181 17 99 31.7614 73 90 29.7981 15 41 29.4413 46 75 27.6878 8 60 25.5262 59 83 19.1612 57 58 0.830474 70 82 0.545241 41 42 0.448579 26 28 6.22241 66 85 6.21852 56 59 6.13115 49 50 5.8479 36 38 5.6185 11 15 2.66757 33 34 2.61803 96 99 2.61565 3 5 2.58731 97 98 2.54061 28 29 2.52187 16 20 5.17257 31 45 5.14519 28 30 4.96616 53 55 4.923 1 2 4.77727 43 45 4.68432 67 68 4.67275 72 74 4.60192 94 95 4.57149 52 54 4.54413 81 83 0.30488 |
Task4 100 7 33 57 1.2717 7 30 1.05798 28 33 0.262333 4 35 0.249532 37 63 0.228665 35 88 0.187345 27 40 0.143845 6 49 0.138414 2 13 1.05753 31 79 1.04773 20 54 1.00533 15 17 1.22427 3 44 1.19451 44 77 1.15568 82 99 1.00235 39 83 0.988717 31 39 0.850347 21 26 0.845279 56 74 0.838035 8 12 0.835773 62 89 0.824568 81 88 0.816758 71 76 0.811334 58 76 0.807345 16 72 0.804087 41 96 0.790773 13 14 0.78796 32 78 0.781045 34 66 0.762969 15 87 0.747001 37 58 0.737726 38 77 0.72965 46 52 0.724423 11 91 1.30277 50 78 1.28203 4 18 0.685428 48 53 0.656968 57 93 0.651881 59 95 0.647059 9 57 0.456422 50 51 0.448579 1 5 0.537478 19 69 0.530972 48 97 0.525738 22 80 0.523479 37 60 0.639511 46 60 0.631275 75 87 0.624691 6 74 0.609203 38 45 0.718715 0 17 0.711128 62 96 0.987711 2 27 0.913603 24 83 0.88582 65 83 0.885453 64 95 0.871948 14 34 0.851522 19 72 0.705125 22 97 0.685751 30 90 1.33613 9 43 0.593577 3 85 0.578521 34 89 0.573725 36 80 0.477427 1 75 0.475017 30 67 0.517784 90 93 0.510862 56 81 0.495512 5 85 1.62274 68 92 1.58763 10 73 1.47997 43 64 1.45529 11 93 1.43798 47 61 1.41689 59 61 1.39945 71 73 1.37322 28 86 0.437985 23 98 0.419271 41 74 0.418974 18 25 0.412104 79 94 0.411102 20 35 0.383622 23 36 0.376916 79 97 0.373622 23 72 0.370473 49 63 0.36903 40 42 0.35789 53 67 0.343044 84 87 0.319539 8 64 0.317949 16 70 0.309969 51 55 0.30204 25 92 0.280551 5 55 0.277678 42 69 0.275346 52 99 0.131243 29 65 0.125988 21 68 0.0786342 15 47 0.0636104 |
Для справки ниже приводятся ответы к этим примерам.
Task1 1.0424585983E-004
0 1 3 5 15 17 32 38 44 45 47 50 51 55 75 77 78 84 85 87
2 13 14 16 19 22 23 27 34 36 40 42 62 66 69 70 72 80 89 98
4 18 20 21 25 26 35 54 56 68 81 88 92
6 10 37 41 46 49 52 58 60 63 71 73 74 76 82 96 99
7 24 29 30 31 39 48 53 65 67 79 83 94 97
8 9 11 12 28 33 43 57 59 61 64 86 90 91 93 95
Task2 1.1282571342E-004
0 31 32 33 34 35 36 37 38 39 40 81 82 83 84 85 86 87 88 89 90
1 2 3 4 5 6 7 8 9 10 71 72 73 74 75 76 77 78 79 80
11 12 13 14 15 16 17 18 19 20
21 24 26 28 61 62 63 64 65 66 67 68 69 70
22 23 25 27 29 30 91 92 93 94 95 96 97 98 99
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
Task3 2.2521714609E-004
0 11 12 13 14 15 51 52 53 54 55 96 97 98 99
1 2 3 4 5 46 47 48 49 50 71 72 73 74 75
6 7 8 9 10 16 17 18 19 20 56 57 58 59 60
21 22 23 24 25 86 87 88 89 90
26 27 28 29 30 66 67 68 69 70 81 82 83 84 85
31 32 33 34 35 41 42 43 44 45 61 62 63 64 65
36 37 38 39 40 76 77 78 79 80 91 92 93 94 95
Task4 6.2922659785E-006
0 1 3 5 15 17 32 38 44 45 47 50 51 55 75 77 78 84 85 87
2 16 19 22 23 27 36 40 42 69 70 72 80 98
4 18 20 21 25 26 35 54 68 88 92
6 10 37 46 49 52 58 60 63 71 73 76 82 99
7 24 29 30 31 39 48 53 65 67 79 83 94 97
8 9 11 12 28 33 43 57 59 61 64 86 90 91 93 95
13 14 34 41 56 62 66 74 81 89 96