Введение
Принципы разработки сложных программных продуктов комплексов постоянно эволюционируют, совершенствуются. Объектно-ориентированный подход является неотъемлемой частью и главной методологией проектирования таких систем. Однако существующие сейчас библиотеки параллельного программирования, такие как, написанные для C и Fortran, реализации MPI или, например, NESL, Charm++ и т.д. низкоуровневые, ориентированные только на процедурную или функциональную модель программирования и, таким образом, не совместимы с современным объектно-ориентированным стилем проектирования приложений. Таким образом, стоит острая необходимость в создании инструмента, который позволил бы гармонично вписать модель параллельного программирования в объектно-ориентированную парадигму проектирования приложений. Это одна из целей, которую преследует система параллельного программирования Spring PPI.
Основная идея Spring PPI – концепция асинхронных методов – впервые предложена Ником Бентоном, Лукой Корделли и Кедриком Фоурнетом в модели Polyphonic C#[1]. В Polyphonic C# асинхронный метод – это метод, выполняющийся в отдельном потоке. Spring PPI использует понятие удаленного (distance) метода, который выполняется асинхронно на одном из вычислительных узлов кластера, а также предоставляет программисту высокоуровневый интерфейс для обмена сообщениями между удаленными методами.
Вторая цель Spring PPI – повышение абстрактного уровня проектирования параллельных приложений путем реализации фреймворка паттернов[2] (шаблонных, устоявшихся приемов, методов) параллельного программирования. Таким образом, система позволяет программисту легко использовать испытанные, проверенные приемы проектирования параллельных программ и при разработке алгоритма мыслить на более высоком абстрактном уровне.
Вторая цель Spring PPI – повышение абстрактного уровня проектирования параллельных приложений путем реализации фреймворка паттернов[2] (шаблонных, устоявшихся приемов, методов) параллельного программирования. Таким образом, система позволяет программисту легко использовать испытанные, проверенные приемы проектирования параллельных программ и при разработке алгоритма мыслить на более высоком абстрактном уровне.
Реализация системы Spring PPI
Spring PPI написана на C# и реализована в виде 2-х составляющих: фреймворка параллельного программирования и Run-time системы.
Фреймворк предоставляет программисту интерфейс для создания параллельных приложений. Используя интерфейс фреймворка, программист взаимодействует с Run-time системой, которая обеспечивает корректное выполнение удаленных методов на узлах кластера и поддерживает функционирование каналов как средства обмена сообщениями между удаленными методами.
Основная идея реализации параллелизма – асинхронный вызов удаленных (distance) методов. Таким образом, любой открытый (public) метод можно вызвать асинхронно на кластере. На основе интерфейса вызова удаленных методов Spring PPI реализует паттерн-ориентированный подход к проектированию параллельных приложений. Таким образом, в Spring PPI разработчик может создавать параллельные приложения, рассуждая исключительно в терминах теории паттернов.
Система реализована на основе работы с портами и не использует дополнительных технологий взаимодействия между компьютерами, таких как MSMQ, .NET Remoting, Indigo, WCF и т.д.
Паттерны параллельного программирования, реализованные в Spring PPI
Паттерн представляет собой «высококачественное решение часто встречающейся проблемы при проектировании в определенной предметной области» [3]. «Каждый паттерн описывает некую повторяющуюся проблему и ключ к ее разгадке, причем таким образом, что этим ключом можно пользоваться при решении самых разнообразных задач» [4].
Фреймворк Spring PPI позволяет программисту разрабатывать параллельные приложения, опираясь исключительно на паттерн - ориентированный подход к проектированию. Spring PPI реализует работу со следующими паттернами параллельного проектирования:
1. Singleton
Singleton[6] – базовый, элементарный паттерн, который инкапсулирует в себе выполнение одного удаленного метода на кластере.
2. Pipeline
Паттерн Pipeline применяется, когда «задача может быть разделена на последовательность задач, связанных зависимостью при использовании данных»[3]. Pipeline в Spring PPI представляет собой последовательность (цепочку) Singleton’ов, которые вызываются один за другим. Причем функциональность паттерна разработана таким образом, что выходные данные очередного элемента цепочки могут служить входными данными для обработки последующему элементу, однако это не является обязательным.
3. Master-Slave
Паттерн Master-Slave[3] реализует отношение между удаленными методами «главный-подчиненный». Структура паттерна Master-Slave представлена на рис. 1
Рис. 1 - Структура паттерна Master-Slave
4. Divide and Conquer
Паттерн Divide and Conquer[6](«Разделяй и властвуй») в Spring PPI может описывать сложную древовидную иерархию задач (Singleton’ов). Задачи в дереве связаны отношением «родитель-потомок» («parent-child»). Каждый «родитель» может иметь несколько «потомков» и, что очень важно, каждый «потомок» может иметь несколько «родителей». Общее правило функционирования паттерна таково, что каждый «потомок» запускается автоматически только тогда, когда каждый его «родитель» завершил работу. Пример дерева задач паттерна Divide and Conquer представлен на рис. 2.
Рис. 2 - Пример дерева задач паттерна Divide and Conquer
5. Repository
Repository[2] («хранилище») - паттерн описывающий логику работы процессов (удаленных методов) с общей памятью. Для доступа к хранилищу используется класс SharedMemory. Все хранилище разбивается на ячейки (cells), каждая ячейка имеет свой уникальный идентификатор (ID) строкового типа. В ячейке может храниться объект любого типа - от булевого типа до сложной иерархии разнотипных объектов. Структура паттерна представлена на рис. 3.
Рис. 3 – Структура паттерна Repository
Результаты вычислительных экспериментов
В качестве примера для оценки работы системы было реализовано несколько известных алгоритмов параллельного умножения матриц, а именно – алгоритмы Фокса(Fox), Кеннона(Cannon) и ленточный (striped). Все алгоритмы были реализованы с использованием паттернов Master-Slave и Repository.
Каждый из алгоритмов запускался последовательно на 1-ом, 2-ух и 4-х процессорах. Эксперименты проводились на кластере, построенном на основе локальной сети (100 Мб/с) и компьютерах с тактовой частотой 2.4 ГГц.
На рисунках 4, 5, 6 представлены графики, позволяющие оценить масштабируемость каждого из приведенных алгоритмов умножения матриц.
Рис. 4 – Масштабируемость алгоритма Фокса, реализованного с использованием Spring PPI
Рис. 5 – Масштабируемость алгоритма Кеннона, реализованного с использованием Spring PPI
Рис. 6 – Масштабируемость ленточного алгоритма, реализованного с использованием Spring PPI
Можно сделать вывод, что алгоритмы Кеннона и Фокса показали замечательную масштабируемость, т.е. при увеличении числа вычислительных узлов (процессоров) вдвое – вдвое уменьшалось и время выполнения алгоритма. Особенно хорошо это можно увидеть на матрицах больших размеров. Ленточный же алгоритм демонстрирует худшее повышение производительности при увеличении числа вычислительных узлов – это может быть связано с тем, что данный алгоритм использует больше памяти.
Таким образом, на примере реализации трех известных алгоритмов умножения матриц было продемонстрировано, что Run-time система и интерфейс параллельного программирования Spring PPI представляют собой хорошо масштабируемую систему.
Заключение
Spring PPI реализует высокоуровневую модель параллельного программирования. Данная модель использует понятие удаленного (distance) метода, метода, который выполняется на кластере. Таким образом, модель полностью интегрирована с объектно-ориентированным подходом проектирования программ.
Фреймворк Spring PPI прелагает разработчику использовать паттерны параллельного программирования в качестве способа универсализации и повышения качества подхода к разработке параллельного программного обеспечения. В качестве демонстрации работоспособности и эффективности предложенной модели параллелизма основанного на паттернах, с помощью интерфейса Spring PPI были реализованы классические алгоритмы параллельного умножения матриц: Фокса, Кеннона и ленточный. При проведении тестов все три алгоритма показали достаточно высокий уровень масштабируемости, что говорит о масштабируемости самой Run-time системы Spring PPI.
В ходе над системой будут проводиться работы над дальнейшим совершенствованием и анализом параллельного паттерн - ориентированного фреймворка Spring PPI. Будут проведены работы по созданию и исследованию параллельной модели доступа и обработки данных, источником которых является реляционная база данных. Кроме уже реализованных паттернов будет проводиться работа над анализом и реализацией других шаблонных решений в области параллельного программирования. Планируется использование Spring PPI для реализации параллельных версий алгоритмов из различных предметных областей.
Литература
1. 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
2. Massingill, B.L., Mattson, T.G., Sanders, B.A.: A pattern language for parallel application programming. Technical Report CISE TR 99-022, University of Florida, 1999
3. Berna Massingill. Patterns for Finding Concurrency for Parallel Application Programs.: Department of Computer Science and Engineering, University of Florida, Gainesville
4. K. Alexander et al. Pattern Language. Oxford 1977.
5. Foster I. Designing and Building Parallel Programs. — Addison Wesley.
6. Massingill, B.L., Mattson, T.G., Sanders, B.A.: More Patterns for Parallel Application Programs PLoP 2001