Распределенные вычисления - это способ решения трудоемких вычислительных задач с использованием нескольких процессоров или компьютеров, чаще всего объединенных в параллельную вычислительную систему. [1]

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

Появление распределенных вычислений относят к 1973 году, когда Джон Шох и Джон Хапп из калифорнийского научно-исследовательского центра Xerox PARC написали программу, которая по ночам запускалась в локальную сеть PARC и заставляла работающие компьютеры выполнять вычисления. [2]

В 1978 году советский математик Виктор Глушков работал над проблемой макроконвейерных распределённых вычислений. Он предложил ряд принципов распределения работы между процессорами. [2]

В 1988 году Арьен Ленстра и Марк Менес написали программу для факторизации длинных чисел. Для ускорения процесса программа могла запускаться на нескольких машинах, каждая из которых обрабатывала свой небольшой фрагмент. [2]

28 января 1997 года стартовал конкурс RSA Data Security на решение задачи взлома методом простого перебора 56-битного ключа шифрования информации RC5. Благодаря хорошей технической и организационной подготовке проект, организованный некоммерческим сообществом distributed.net, быстро получил широкую известность. [2]

Распределенные вычисления нашли свое применение в астрономии (проект SETI@home, целью которого является поиск внеземных цивилизаций путем распределения космического шума, записываемого радиотелескопом, на отдельные блоки), в биологии (проект Folding@home, целью которого является изучение строения дефектных белков), а также в других сферах науки включая и математику.

Целью данной работы является разработка распределенного алгоритма для поиска центра неориентированного дерева.

Описание модели

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

Опр. Лист - это вершина дерева, не имеющая потомков (ее степень равна единице). [3]

Приведем словесное описание алгоритма (поэтапное):

1. Первичная инициализация: множество незаблокированных вершин совпадает с множеством всех вершин дерева, степени всех вершин нулевые.

2. Отправка сообщений №1: каждая незаблокированная вершина отправляет соседям свой уникальный идентификационный номер - UID.

3. Подсчет степени вершин (синхронно).

4. Отправка сообщений №2: каждая незаблокированная вершина отправляет соседям свою степень - deg_i.

5. Для каждой незаблокированной вершины проверяем выполнение следующих условий: если степень вершины равна единице и степень соседа (единственного) не равна единице, то данная вершина блокируется (X_i = 0). Если степень вершины равна нулю (все соседние вершины заблокированы), то алгоритм завершает свою работу (первый критерий остановки, если центр состоит из одной вершины). Если степень вершины равна единице и степень соседа также равна единице, то алгоритм завершает свою работу (второй критерий остановки, если центр состоит из двух вершин).

6. Если алгоритм незавершен, то повторяются все пункты при условии, что часть вершин была заблокирована.

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

Псевдокод алгоритма:

1. Initialization(M); (это функция инициализации, в самом начале каждая вершина будет иметь нулевую степень deg_i = 0 и M:=V)

2. Sent(M, UID); (это функция синхронной отправки сообщений, где каждая незаблокированная вершина (процессор) отправит соседям свой UID)

3. Deg(M); (каждая вершина посчитает свою степень)

4. Sent(M, deg(M)); (каждая незаблокированная вершина отправит свою степень)

Рассмотрим разработанный распределенный алгоритм на конкретном примере.

Рис. 1.1

Пусть сеть представлена неориентированным деревом, изображенным на Рис. 1.1. На первом шаге алгоритма, множество незаблокированных вершин совпадает с множеством всех вершин дерева, т.е. M = {1,2,3,4,5,6,7,8,9,10,11,12,13}. Выполняя две последовательные отправки сообщений, а также подсчет степеней вершин (пункты 2 - 4 алгоритма), установили, что на первом шаге алгоритма будут заблокированы вершины с номерами 1,2,3,4,5,6. Действительно, степени этих вершин равны единице и степени их соседей отличны от единицы (например, для вершины с номером 5 deg = 1, а n_deg = 4), а значит они будут заблокированы. Вершины, заблокированные на первом шаге, отмечены на Рис. 1.2. красным цветом.

Рис. 1.2

На втором шаге алгоритма множество М = {7,8,9,10,11}. Все вершины вновь имеют степень равную нулю (инициализация). После двух последовательных отправок сообщений установили, что вершины с номерами 7,8,9,10 будут заблокированы на втором шаге. К примеру, для вершины с номером 9 deg = 1 (потому что вершина с номером 3 была заблокирована на предыдущем шаге и не может отправить сообщение), n_deg = 3, а значит, она должна быть заблокирована. Аналогичные рассуждения справедливы и для других вершин. Вершины, заблокированные на втором шаге, отмечены на Рис. 1.3. красным цветом.

Рис. 1.3

На третьем шаге алгоритма множество М = {11,12,13}. Для вершин вновь произведена инициализация. После двух последовательных отправок сообщений установили, что вершины с номерами 11 и 12 будут заблокированы на данном шаге. Для i = 11: deg = 1, n_deg = 2; для i = 12: deg = 1, n_deg = 2. Данные вершины отмечены красным цветом на Рис. 1.4. Проводя следующий шаг метода, установили, что вершина с номером 13 является центральной (выполнится первый критерий остановки, т.к. deg = 0).

Рис. 1.4

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

Размещено на http://www.allbest.ru/

Рис. 2

К примеру, рассмотрим дерево, представленное на Рис. 2. Число вершин дерева равно шести. На первом шаге метода множество незаблокированных вершин М = {1,2,3,4,5,6}, а степени всех вершин нулевые (первичная инициализация). После двух последовательных отправок сообщений и подсчета степеней вершин установили, что на первом шаге алгоритма будут заблокированы вершины с номерами 1,2,3,4 (их степени равны единице, а степени соседей равны трем). На следующем шаге алгоритма сработает второй критерий остановки (степени вершин 5 и 6 равны единице и они являются соседями), поэтому центр дерева состоит из двух вершин с номерами 5 и 6.

Заключение

неориентированное дерево псевдокод алгоритм

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

Оценим трудоемкость алгоритма по числу шагов. Очевидно, что число шагов метода совпадает с радиусом дерева (иначе это противоречило бы определению центра графа). Таким образом, для оценки числа шагов алгоритма необходимо провести оценку радиуса дерева с n вершинами. Предположим, что все вершины кроме листов имеют k потомков, где k - это максимальная из степеней вершин дерева или степень сети. Будем рассматривать уровни дерева от его центра и до листов. Тогда запишем общее число вершин дерева, суммируя количество вершин на каждом уровне, получим:

1 + k + k² + … + k^R = n, где R - это радиус дерева или число уровней, а n - это общее число вершин. Очевидно, что выражение слева представляет геометрическую прогрессию с множителем k. Запишем ее сумму в виде: k^R - 1 = n*(k - 1) и выразим радиус R = log_k(1 + n*(k - 1)) ? log_k(n). Таким образом, оценка числа шагов имеет вид O(log(n)).

Аналогичным способом находится оценка по числу сообщений O(n*log(n)). На каждом шаге число сообщений можно оценить O(n), а оценка числа шагов O(log(n)).

Таким образом, результатом данной работы является распределенный алгоритм поиска центра неориентированного дерева, имеющий трудоемкость по числу шагов O(log(n)) и трудоемкость по числу сообщений O(n*log(n)).

Список литературы:

1. Эндрю Таненбаум, Мартин ван Стеен Распределенные системы. Принципы и парадигмы = Andrew S. Tanenbaum, Maarten van Steen. "Destributed systems. Principles and paradigms". -- Санкт-Петербург: Питер, 2003. -- 877 с.

2. Словарь по кибернетике Под редакцией академика В. С. Михалевича. -- 2-е. -- Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. -- 751 с.

3. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: Учебник. - Нижний Новгород: изд-во ННГУ, 2005. 307 с.

4. A. Goldberg, M. Luby, S. Plotkin and G.E. Shannon, Parallel symmetry breaking in sparse graphs SIAM J. Disc. Math. Vol. 1, No. 4, pp. 434-446, November 1988.

5. Panconesi A. and Rizzi R., Some simple distributed algorithms for sparse networks. , 2001. p7.

6. David A. Patterson and John L. Hennessy. Computer Organization and Design (Second Edition) Morgan Kaufmann Publishers, 1998. ISBN 1-55860-428-6, pg 715

7. В.А. Крюков «Операционные системы распределённых вычислительных систем (распределённые ОС)». Лекции для 4 курса факультета ВМК МГУ.

8. David W. Walker, "The design of a standard message-passing interface for distributed memory concurrent computers", Parallel Computing, v.20, n 4, April 1994, 657-673.

9. Nancy Lynch, Distributed Algorithms, San Francisco Morgan Kaufmann Publishers, 1996 , pp 904.

Размещено на Allbest.ru