Распределенные вычисления в малом и среднем офисе

Страница 1 из 3

Роман Лут
В период с 1997 по 2001 работал в компании GSC Game World над 3D-экшеном Venom: Codename Outbreak в качестве программиста графического движка и дизайнера уровней. С 2002 работает в компании Deep Shadows ведущим программистом графического движка. Принимал непосредственное участие в работе над экшен-ролевым проектом Xenus: Boiling Point.

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

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

Я длительное время интересовался концепцией GPGPU^[1] - использования мощности видеокарты для увеличения скорости работы внутренних утилит. Ранние версии нашего редактора уровней рассчитывали освещение (Ambient occlusion^[2] + direct lighting), используя рендеринг видов для сторон полукуба (hemicube) из каждой точки карты освещения (lightmap).

К сожалению, в результате экспериментов выяснилось, что из-за низкой скорости обмена CPU<->GPU, простенький CPU-only рейтрейсер выполняет ту же работу в 2-3 раза быстрее. Возможно, я смог бы добиться каких-то результатов, реализовав весь алгоритм полностью на GPU, но такая реализация требует неоправданно больших трудозатрат. При переносе задачи на GPU приходится отойти от линейного программирования, и адаптировать алгоритмы под архитектуру видеокарты. Только совсем недавно nVidia предоставила более-менее простой framework, предполагающий программирование на C^[3]^[28].

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

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

Прежде чем продолжить, я попрошу читателя нажать CTRL+ALT+DEL и переключиться на закладку "производительность". Взгляните на индикатор "Использование CPU". Думаю, большинство из вас увидит там значение, не превышающее 10%. Если у Вас двухпроцессорная машина - второй процессор практически все время будет свободен.

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

Теперь посчитайте, какая мощность простаивает в среднем офисе (50+ машин) - и Вы получите цифру, дотягивающую до современных суперкомпьютеров.

К сожалению, некоторое традиционное отношение кластерных вычислений в высокой науке долгое время служило для меня ментальным барьером для попыток использования распределенных вычислений для решения "приземленных" практических задач. К счастью, великолепное приложение - Incredibuild^[4] - показало, что их можно использовать не только для практических, но и, возможно, real-time задач.

Набор рабочих станций, соединенных TCP/IP сетью (кластер), можно рассматривать как мультипроцессорную систему с разделенной памятью. Для выполнения расчетов на такой системе наиболее прост и эффективен подход с разделением данных (Data parallel computing).

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

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

Этой работой занимается программное обеспечение кластера. Я долго пытался найти готовое ПО, удовлетворяющее следующим требованиям:

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

Первое же условие отбросило практически всех кандидатов^[5]^[6]. Причина понятна - зачем покупать лицензионную ОС на каждый рабочий узел, если есть бесплатный linux?

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

MPICH2^[7]. Реализация библиотеки MPI для Windows. К сожалению, запускает процессы с нормальным приоритетом, что мешает работе пользователя. Если рабочая станция становится недоступной в процессе использования кластера - это приводит к ошибке.

libGlass^[8]. Несмотря на достаточно удобную модель программирования, я побоялся использовать эту библиотеку, т.к. она долгое время не обновлялась.

Alchemy^[9]. Наиболее интересный кандидат. Предлагает удобную модель программирования, работает на основе .NET framework, что, кстати, теоретически позволяет использовать в качестве рабочей станции, скажем, смартфон Motorola Mpx 200. Содержит наглядные примеры, и продолжает развиваться.

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

После безуспешных поисков, я принял решение разработать библиотеку самостоятельно.

Hxgrid

При разработке библиотеки я ориентировался на следующие дополнительные предположения (кроме приведенных ранее):

для пересылки данных используется локальная сеть 10-1000MBit, по протоколу TCP/IP;
сеть считается внутренней и безопасной; библиотека не содержит абсолютно никаких средств аутентификации и защиты от атак. Хорошая система безопасности, с одной стороны, значительно увеличивает сроки разработки библиотеки, с другой - усложняет использование;
соотношение "время пересылки объема данных/время выполнения задачи на узле" <=0.1. При этом объем данных может составлять до от 0 до 100 Мбайт;
в сети присутствует постоянно доступный сервер, на котором можно запустить программу-координатор;
библиотеку предполагается использовать как для долгих (до нескольких часов), так и полуинтерактивных задач (до нескольких секунд);
в данный момент времени на текущей машине может выполняться только одно приложение, использующее кластер (ограничение текущей версии);
на одной машине могут выполняться одновременно приложение, использующее кластер, агент и координатор;
рабочие узлы могут становиться недоступными или доступными во время использования кластера. Узлы, ставшие доступными, должны включаться в работу немедленно;
кластер может использоваться одновременно несколькими пользователями. Доступные вычислительные ресурсы должны распределяться поровну;
на рабочих узлах необходимо использовать все доступные процессоры;
предполагается использовать библиотеку из C++ и Delphi.

Для сокращения времени разработки, для реализации был выбран Delphi. Библиотека использует COM-подобные интерфейсы^[11]. Библиотека использует Jedy Visual Code Library^[15] и ZLIB^[27].

Настройка кластера

Для начальной установки кластера необходимо скачать дистрибутив^[10.1].

Кластер состоит из трех компонент:

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

Агенты и Пользователи находят Координатор, посылая broadcast сообщения, поэтому при переносе координатора на другую машину или смене IP адреса, не требуется конфигурировать всех агентов.

После получения списка агентов, Пользователь общается с ними напрямую. Это позволяет избежать лишних задержек при передаче данных по сети.
Агенты. Агенты устанавливаются на всех компьютерах в сети. Агент позволяет использовать свободное процессорное время компьютера, на котором он установлен.
Пользователь - приложение, написанное с использованием библиотеки hgGrid.

Модель программирования

hgGrid позволяет выполнять задачи (tasks) на рабочих узлах кластера. Приложение добавляет набор задач в очередь выполнения и ожидает их завершения.

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

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

Каждая задача представляет собой процедуру:

typedef bool (__cdecl TTaskProc)(IAgent* agent, DWORD sessionId, IGenericStream* inStream,
 IGenericStream* outStream);

type TTaskProc = function(agent: IAgent; sessionId: DWORD; inStream: IGenericStream;
 outStream: IGenericStream): boolean; cdecl;

где sessionId - уникальный идентификатор сессии, используется при получении дополнительных данных сессии.

Функция возвращает false, если была прервана (см. ниже).

Такие процедуры должны находиться в DLL. Библиотека осуществляет "доставку кода" процедуры передачей DLL каждому агенту. Процедура TTaskProc должна быть thread-safe. После выполнения задачи на агенте, библиотека передает по сети выходной поток приложению, и вызывает калбек FinalizeTask():

typedef void (__cdecl TFinalizeProc)(IGenericStream* outStream);

type TFinalizeProc = procedure(outStream: IGenericStream); cdecl;

Эта функция тоже должна быть thread-safe.

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

Следующая страница >>

стр. 1 из 3