4.2 Метод произвольной выборки

В методе произвольной выборки прикладная программа должна обеспечивать сквозную нумерацию заданий и быть готова в любой момент выдать задание с номером N из диапазона прикладной задачи. Результаты вычислений также могут приходить в произвольном порядке, но гарантируется, что все результаты будут получены и только один раз. В этом методе не требуется хранить в окне заданий сам запрос и результат вычислений, хранятся только номера пакетов, которые сейчас находятся в процессе вычислений. Если возникает необходимость послать пакет другому вычислительному узлу (при истечении времени ожидания), то прикладная программа запрашивается еще раз и заново выдает задание. Полученный от вычислительного узла результат расчета сразу же отдается прикладной программе.

4.3 Архитектура центрального сервера для реализации методов последовательной и произвольной выборки

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

Напомним, что прикладная программа взаимодействует с сервером X-Com через один из 3-х интерфейсов: Java, C/C++, Files. В каждом из этих интерфейсов предусмотрены независимые блоки функций как для одного, так и для другого метода.

В блоке логики сервера есть два независимых модуля реализующие соответственно два методов разбиения исходной задачи. Помимо этих 2-х модулей в блоке логики сервера есть общая часть, которая отвечает за:

идентификацию узла

ведение базы данных (информация об узлах, вычислительных возможностях узлов, а также о статистике соединений)

проверку корректности результата

5. Точки взаимодействия прикладной программы с системой X-Com

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

Серверная часть прикладной программы управляет формированием заданий для расчета на узлах. Программа может быть реализована на любом средстве программирования, важно только, чтобы она удовлетворяла API X-Com.

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

Отметим, что интерфейсы вычислительной части прикладной программы не связаны с интерфейсами взаимодействия для серверной части прикладной программы, более того они не используют методы последовательной и произвольной выборки (метод разбиения исходной задачи на блоки не влияет на расчет каждого блока).

6. Ход вычислений в системе X-Com

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

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

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

6.1 Разбиение исходной задачи на блоки и нумерация этих блоков

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

6.2. Начальный момент времени и соединение узлов с сервером

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

Каждый узел все время пока он функционирует, периодически посылает запросы “дай задание” на сервер. Если произошел сбой соединения, либо сервер еще не готов узел снова ожидает некоторое время и повторяет попытку.

6.3 Подключение и идентификация узла

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

Возможны четыре типа соединений:

“Дай задание” - первичный запрос результата;

“Получи результат - дай следующее задание” - возврат рассчитанного задания и запрос следующего. Этот запрос делается в одной сессии для оптимизации сетевого взаимодействия;

“Получи задание” - возврат рассчитанного задания и сообщение о завершении работы. Сообщение о завершении работы может произойти и без возврата результата, это важно, чтобы корректно определить на сервере статус вычислительного узла;

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

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

6.4 Первичный запрос задания

В начальный момент времени все узлы обращаются к серверу с запросом “дай задание”. Предположим, что некоторый узел установил соединения и прошел процедуру идентификации.

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

Затем задание на расчет через блок логики, серверный коммуникационный блок, клиентский коммуникационный блок попадает на узел.

6.5 Расчет задания на узле

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

Окончив расчет, узел посылает результат расчет на сервера. Для этого используется запрос “Получи результат - дай следующее задание”.

6.6 Получение сервером результатов вычислений

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

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

6.7 Окончание вычислений

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

6.8 Структуры данных сервера для хранения информации об узлах

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

6.9 Перераспределение заданий в методе произвольной выборки

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

В методе произвольной выборки есть три варианта организации хода вычислений:

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

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

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

В последнем варианте при необходимости выдачи нового задания сервер вначале просматривает список уже розданных заданий, и если время ожидания какого-либо из них истекло, выдает его. Если все времена заданий, которые сейчас находятся в обработке, не истекли, то прикладная программа запрашивается об очередном задании.

Время ожидания ответа рассчитывается как расчетное время ожидания ответа умноженное на коэффициент K_wait. Расчетное время ожидания ответа, в свою очередь, определяется исходя из статистики работы с каждым конкретным клиентом и размера текущего задания. Коэффициент K_wait - важный атрибут работы системы: при его увеличении мы ожидаем пакет в течении большего времени и соответственно меньше шанс, что мы пошлем один и тот же пакет двум разным вычислительным узлам (задержка может быть связана как с неточностью предсказания времени расчета, так и с загрузкой вычислительно узла), с другой стороны при увеличении этого коэффициента мы увеличиваем размеры окна, что ведет в прикладной программе к увеличению времени ожидания очередной порции данных, а также увеличение размеров окна требует дополнительных ресурсов памяти центрального сервера.

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

6.10 Фоновые процессы на сервере

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

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

6.11 Проверка корректности результата

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

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

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

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

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

Страницы: 1, 2