Введение
В современных условиях необходимость обработки все больших и больших объемов информации постоянно ставит перед программистами задачи повышения производительности разрабатываемых ими систем. Сначала некоторое повышение производительности приложений состояло в подходе ориентированном на многопоточную модель выполнения программ. Однако и этого было недостаточно – как результат получили широкое распространение распределенные, многозвенные программные системы, основанные на использовании кластеров и GRID-сетей. Широкое распространение подобных систем, в свою очередь, ставит задачу создания систем программирования, которые бы позволяли использовать мощь кластерных и GRID-архитектур и в то же время предоставляли бы разработчику простой, понятный и высокоуровневый интерфейс создания параллельных приложений. Систем программирования, которые были бы легко переносимы, надежны, масштабируемы и независимы от исполнительной аппаратной части. Существующие сейчас библиотеки параллельного программирования, такие как, написанная на C и Fortran, MPI (Message Passing Interface)[1] или, например, NESL[2], Charm++[3] очень низкоуровневые, ориентированные только на процедурную или функциональную модель программирования и, таким образом, не подходят для современного объектно-ориентированного стиля создания приложений.
На данном этапе в направлении создания новых моделей параллелизма можно особенно отметить модель параллельного программирования, предложенную Ником Бентоном, Лукой Корделли и Кедриком Фоурнетом – Polyphonic C#[4]. Данная модель основывается на использовании модели join-исчислений и, так называемых «асинхронных» методов, которые могут выполняться в многопоточном режиме в отдельном потоке.
Система параллельного программирования Spring PPI (Spring Parallel Programming Interface) также основывается на модели синхронных и асинхронных (distance- в терминологии Spring PPI) методов, однако характерной чертой системы является перенос выполнения асинхронных методов на другой компьютер (узел кластера), а также предоставление программисту высокоуровневого механизма взаимодействий (обмена сообщениями) между асинхронными методами. Отличающей особенностью системы является реализация паттернов (шаблонных, устоявшихся приемов, методов) параллельного программирования. Таким образом, система позволяет программисту легко использовать испытанные, проверенные приемы проектирования параллельных программ и при разработке алгоритма мыслить на более высоком абстрактном уровне.
Постановка задачи
Основной задачей является внедрение и повышение эффективности параллельного программирования в высокоуровневых языках путем создания системы развертывания и программирования для кластера на базе платформы .NET. Реализация Spring PPI представляет собой реализацию 2-х составляющих – реализацию системы развертывания и администрирования кластера на базе локальной сети произвольной топологии, а также реализацию библиотеки параллельного программирования для кластера.
Система развертывания и администрирования кластера должна представлять собой отказоустойчивую, масштабируемую, гибко настраиваемую систему. Под отказоустойчивостью понимается возможность отката системы и восстановления, работающих на кластере процессов, при выходе из строя одного или нескольких узлов кластера. Под масштабируемостью понимается, прежде всего, линейная зависимость уровня загрузки системы от количества пользователей кластера. Система развертывания кластера также должна отвечать за постоянный сбор статистики нагрузки в целом на кластер и на каждый узел кластера в отдельности.
Библиотека параллельного программирования для кластера должна предоставлять программисту высокоуровневый объектно-ориентированный интерфейс для создания параллельных приложений. Базовый интерфейс концептуально включает в себя механизмы вызова асинхронных методов на кластере и передачи сообщений между узлами кластера. На основе базового интерфейса строиться более абстрактно высокий, основанный на паттернах параллельного программирования интерфейс, позволяющий разработчику создавать архитектуру параллельного приложения, используя устоявшиеся методы разработки параллельных алгоритмов.
Реализация системы
Реализация системы Spring PPI представляет собой 3 программных модуля:
1) библиотека параллельного программирования (Spring PPI) – представляет собой .NET сборку, подключаемую к программе-клиенту кластера и предоставляющая интерфейс параллельного программирования;
2) администратор кластера (Cluster Administrator) – программа, запускающаяся на главном, фронтальном компьютере кластера и отвечающая за распределение вычислительных ресурсов кластера между заявками от программ-клиентов кластера;
3) рабочий узел кластера (ClusterWorkLeaf) – программа, работающая на каждом компьютере кластера и отвечающая за выполнение асинхронных методов, т.е. осуществляющая, основную вычислительную функцию на конкретном узле кластера.
Концептуально диаграмма развертывания системы SpringPPI представлена на рисунке 1.
Рисунок 1 - Диаграмма развертывания системы Spring PPI
В общем, система программирования Spring PPI реализована, основываясь на работе с портами, и не использует .NET Remoting, MSMQ, Indigo или какую-либо другую технологию в качестве способа удаленного взаимодействия между компьютерами. Реализация удаленных асинхронных вызовов методов базируется на использовании механизмов рефлексии.
Основа объектно-ориентированного параллельного интерфейса, реализованного в, подключаемой к программе-клиенту, библиотеке состоит из классов:
-Session-данный класс описывает собой логическую совокупность параллельных вызовов и вычислений и предоставляет интерфейс для асинхронного вызова любого метода на кластере;
-CChannel – канал, средство двунаправленной пересылки сообщений между методами, выполняющимися на кластере;
-классы, реализующие различные паттерны параллельного программирования: PipeLine(«цепочка»), Singleton(«одиночка»), MasterSlave(«главный-подчиненный»), DivideAndСonquer(«разделяй и властвуй»)[5].
Рассмотрим минимальную программу на языке C#, использующую интерфейс Spring PPI для организации параллельных вычислений. Код программы представлен на рисунке 2.
using SpringPPI;
namespace SpringPPIClient
{
[Serializable()]
public class Simple
{ private int _x;
public Simple(int ax)
{_x = ax;}
public void Sum(CChannel ch,int param)
{ch.Send(_x+param);}
}
class Program
{
static void Main(string[] args)
{ /*1*/Session s = new Session();
s.Init();
/*2*/CChannel ch = new CChannel(s);
Simple simple = new Simple(2);
/*3*/s.CallDistanceMethodState(simple, "Sum", new object[]{ch,1});
/*4*/int result = (int)(ch.Receive()[0]);
Console.WriteLine("Distance method result="+result.ToString());
/*5*/s.Close();
}
}
}
Вышеприведенная программа описывает класс Simple и его метод Sum – нахождение суммы поля класса и параметра переданного в качестве аргумента методу, результат посылается в канал, который также был передан как аргумент. Метод Sum будет вызван удаленно на кластере посредством интерфейса Spring PPI.
На первом этапе работы программы (см. рис. 2) происходит создание объекта класса Session-вычислительной сессии. По умолчанию объект Session конфигурируется так, что при вызовах удаленных методов в рамках сессии будут использованы все рабочие узлы кластера. Возможны конфигурации, когда клиентская программа может управлять тем, какая часть узлов кластера доступна в рамках данной сессии, например, может быть задействовано определенное число рабочих узлов или набор конкретных узлов кластера – это в свою очередь позволяет программам-клиентам более рационально использовать вычислительные ресурсы кластера. После создания объекта Session происходит его инициализация на главной машине кластера, таким образом, ClusterAdmistrator уведомлен о том, что на клиенте была проинициализирована сессия, и вскоре в рамках сессии будут осуществляться вызовы удаленных методов на кластере.
На втором этапе работы программы создается объект класса CChannel – средства межпроцессорного взаимодействия в Spring PPI. Любой удаленный метод, на каком узле кластера он бы не выполнялся, если у него имеется ссылка на объект данного класса, может послать или получить сообщение от других удаленных методов. Далее в программе создается объект класса Simple и его целочисленному полю присваивается значение 2.
На третьем этапе происходит непосредственно удаленный вызов метода Sum класса Simple на кластере. Удаленный вызов осуществляется путем вызова метода CallDistanceMethodState класса Session. CallDistanceMethodState принимает в качестве аргументов ссылку на объект, метод которого необходимо вызвать, строковое имя метода и массив значений, которые будут переданы удаленному методу в качестве аргументов. Существует ограничение на классы, методы которых будут вызываться на кластере, эти классы должны быть помечены атрибутом Serializable либо реализовывать интерфейс ISerializable. В целом процедура вызова удаленного метода подразумевает 3 стадии:
1) ClusterAdmistrator выбирает рабочий узел, на котором будет выполняться метод (логика выбора следующего рабочего узла может быть разной: либо ClusterAdmistrator перебирает узлы кластера и поочередно назначает удаленные методы на обработку каждому узлу, либо очередной вызов удаленного метода достается узлу, на котором в данный момент выполняется наименьшее число удаленных методов);
2) копирование объекта, метод которого будет вызываться на узел кластера, выбранный на предыдущем этапе;
3) непосредственное выполнение удаленного метода с использованием механизмов рефлексии на узле кластера.
На четвертом этапе работы программы вызывается блокирующий метод класса CChannel – Receive, который приостанавливает работу программы до тех пор, пока какой-либо из удаленных методов не пошлет в этот канал сообщение. Таким образом, получив сообщение (результат выполнения удаленного метода) в канал программа выводит этот результат на консоль.
На пятом этапе происходит закрытие вычислительной сессии. В рамках этого этапа происходит освобождение ресурсов на главном компьютере и рабочих узлах кластера.
Вся работа кластера происходит в отказоустойчивом режиме. Под отказоустойчивостью понимается работа системы в случае, когда один из узлов кластера выходит строя либо соединение с ним разрывается - в этом случае узел автоматически удаляется из кластера, а если на нем в данный момент выполнялись удаленные методы, эти методы будут заданы для выполнения на другом узле кластера.
Результаты вычислительных экспериментов
В качестве примера для оценки работы системы было реализовано несколько известных алгоритмов параллельного умножения матриц, а именно – алгоритмы Фокса(Fox), Кеннона(Cannon) и ленточный (striped).
Каждый из алгоритмов запускался последовательно на 1-ом, 2-ух и 4-х процессорах. Эксперименты проводились на кластере, построенном на основе локальной сети (100Мб/с) и компьютерах с тактовой частотой 2.4 ГГц.
На рисунках 3, 4, 5 представлены графики, позволяющие оценить масштабируемость каждого из приведенных алгоритмов умножения матриц.
Рисунок 3 – Масштабируемость алгоритма Фокса, реализованного с использованием Spring PPI
Рисунок 4 – Масштабируемость алгоритма Кеннона, реализованного с использованием Spring PPI
Рисунок 5 – Масштабируемость ленточного алгоритма, реализованного с использованием Spring PPI
Таким образом, видно, что при малых размерах матриц ленточный алгоритм показывает производительность несущественно, но выше алгоритмов Фокса и Кеннона. Однако при дальнейшем росте размеров матриц блочные алгоритмы Фокса и Кеннона сильно опережают ленточный алгоритм. Такое поведение не зависит от количества вычислительных процессоров. Подобная зависимость может быть связана с тем, что ленточный алгоритм использует больше памяти и это является решающим фактором, замедляющим работу алгоритма при больших размерах матриц.
Алгоритмы Фокса и Кеннона показывают практически одинаковые результаты производительности, что является закономерным, учитывая схожесть этих алгоритмов и по сути - оба алгоритма являются блочными и по количеству используемой памяти.
Алгоритмы Кеннона и Фокса показали замечательную масштабируемость, т.е. при увеличении числа вычислительных узлов (процессоров) вдвое – вдвое уменьшалось и время выполнения алгоритма. Особенно хорошо это можно увидеть на матрицах больших размеров. Ленточный же алгоритм демонстрирует худшее повышение производительности при увеличении числа вычислительных узлов.
Таким образом, на примере реализации трех известных алгоритмов умножения матриц была продемонстрирована возможность реализации масштабируемых алгоритмов с использованием параллельного интерфейса и Run-time системы Spring PPI.
Заключение
Характерной чертой интерфейса параллельного программирования Spring PPI является предоставление разработчику простого в использовании и высокоуровневого интерфейса для разработки параллельных приложений. Spring PPI полностью интегрирована с платформой .NET, а значит позволяет использовать всю мощь платформы .NET при создании параллельных приложений. Интеграция с платформой .NET также означает совместимость с любым .NET языком будь то C#, VB.NET, C++.NET, Delphi.NET или же другие, менее распространенные языки, вроде CULE.NET. Spring PPI базируется на концепции асинхронных удаленных методов, что позволяет системе органично интегрироваться в объектно-ориентированную модель проектирования приложений. Отличительной особенностью Spring PPI является и то, что помимо базовой функциональности вызова удаленных методов и механизма взаимодействия между ними, система предоставляет разработчику и более высокоуровневый интерфейс, основанный на паттернах параллельного программирования.
В перспективе развития Spring PPI будет продолжена работа над реализацией высокоуровневых интерфейсов параллельного программирования. Будет создана реализация системы под операционной системой Linux на базе платформы MONO, а также планируется создание CASE-средства для проектирования параллельных приложений и последующей кодогенерацией на основе интерфейса параллельного программирования Spring PPI.
Литература
1. W. Gropp, E. Lusk, and A. Skjellum, "Using MPI: Portable Parallel Programming with the Message Passing Interface", MIT Press, 1994.
2. Guy E. Blelloch, "NESL: A Nested Data-Parallel Language (3.1)", CMU-CS-95-170, September 1995
3. Orion Lawlor and L. V. Kale, "Supporting Dynamic Parallel Object Arrays", Journal: Concurrency and Computation: Practice and Experience, John Wiley & Sons, 2003; 15:371-393
4. Nick Benton, Luca Cardelli, Cedric Fournet. Modern Concurrency Abstractions for C# In B. Magnusson (Ed.), Proceedings of the 16th European Conference on Object-Oriented Programming (ECOOP 2002). University of Malaga, Spain. LNCS 2374, Springer-Verlag
5. Berna Massingill. Patterns for Finding Concurrency for Parallel Application Programs.: Department of Computer Science and Engineering, University of Florida, Gainesville