На данном этапе в направлении создания новых моделей параллелизма можно особенно отметить модель параллельного программирования, предложенную Ником Бентоном, Лукой Корделли и Кедриком Фоурнетом – Polyphonic C#[2]. Данная модель основывается на использовании модели join-исчислений и, так называемых «асинхронных» методов, которые могут выполняться в многопоточном режиме в отдельном потоке.

• создание и повышение эффективности высокоуровневой модели параллельного программирования;
• полная интеграция модели параллелизма с объектно-ориентированной парадигмой программирования;
• исследование и реализация на компонентном уровне паттернов параллельного программирования, как универсального подхода к разработке качественного программного обеспечения;
• создание и исследование параллельной модели доступа и обработки данных в корпоративных приложениях;

Самым важным критерием при классификации систем параллельного программирования является тип параллельного компьютера на архитектуру, которого ориентирована модель программирования. Наиболее распространены на данный момент параллельные компьютеры типа MPP, SMP, NUMA, PVP и кластеры[4].

В архитектуре типа MPP[5] (массивно-параллельная система) система состоит из однородных вычислительных узлов, при этом на каждом узле может быть один или несколько центральных процессоров, у каждого узла есть собственная локальная память, причем прямой доступ к памяти других узлов невозможен. Также в архитектуре MPP должен присутствовать коммуникационный процессор или сетевой адаптер. Могут присутствовать жесткие диски или другие устройства ввода/вывода. С точки зрения программирования под MPP архитектурой важным является присутствие у процессов только локальной памяти, поэтому основными средствами программирования тут будут системы, ориентированные на взаимодействие путем передачи сообщений. Это, прежде всего, различные реализации MPI: MPICH[6], MP-MPICH[7], WMPI[8] и др. Также в последнее время широко используются PVM[9] (Parallel Virtual Machine), а также BSPlib. BSPlib[10] - представляет собой коммуникационную библиотеку, использующую BSP модель параллельного программирования [11]. BSP базируется на двух основных принципах - передаче сообщений и прямом доступе в нелокальную память. Таким образом, эта библиотека частично устраняет недостаток MPP архитектуры связанный с отсутствием общей памяти.

Архитектура типа SMP (симметричная мультипроцессорная система) представляет собой систему, которая состоит из нескольких однородных процессоров и общей памяти. Все процессоры получают доступ к любой точке памяти с одинаковой скоростью. Процессоры могут подключаться к памяти либо с помощью общей шины, либо с помощью, так называемого, crossbar-коммутатора. Наличие общей памяти в данной архитектуре определяет стиль программирования для подобных систем. Общая память очень сильно упрощает взаимодействие между процессами, однако имеет и свой побочный эффект – число одновременно запущенных процессов на компьютерах SMP архитектуры может быть не больше 32. Данное ограничение является неприемлемым при построении масштабируемых систем, поэтому для того чтобы удовлетворять критерию масштабируемости на базе подхода SMP применяются NUMA-архитектуры.

Стандартом программирования для компьютеров с SMP архитектурой стал OpenMP [12]. Применение MPI в рамках данной архитектуры не очень эффективно ввиду использования сообщений как единственного средства взаимодействия между процессами, поэтому создание нового стандарта для машин класса SMP стало просто необходимостью. Этим стандартом и стал OpenMP. OpenMP, по своей сути, является высокоуровневой надстройкой над интерфейсом POSIX-threads. POSIX-threads поддерживается большинством UNIX-систем, однако, ввиду своего низкоуровневого интерфейса и по ряду других причин, не подходит для практического параллельного программирования. OpenMP очень хорошо подходит для быстрого распараллеливания программ, основанных на больших параллельных циклах. Программист может не создавать параллельную версию программы, а просто добавить в текст последовательной программы OpenMP директивы.

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

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

PVP система стоит из узлов, каждый из которых представляет собой подсистему из 1-16 процессоров и общей памяти, т.е. каждый узел функционирует на основе архитектуры SMP. Далее узлы объединяются с помощью коммутатора аналогично MPP.

Кластерные системы представляют собой набор рабочих станций общего назначения и используются в качестве дешевого варианта массивно-параллельного (MPP) компьютера. Для связи узлов используется одна из стандартных сетевых технологий: Fast/Gigabit Ethernet, Myrinet. Узлы кластера могут одновременно использоваться в качестве пользовательских рабочих станций.

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

Система Spring PPI (Spring Parallel Programming Interface) разработана для программирования на кластерах. Основными отличиями Spring PPI от вышеуказанных систем и библиотек являются:

• OpenMP, MPICH, MP-MPICH, WMPI, BSPlib и другие существующие на данный момент библиотеки ориентированы на процедурную либо функциональную модель программирования, Spring PPI представляет модель параллелизма, поддерживающую полностью объектно-ориентированный стиль проектирования;
• одной из основных особенностей Spring PPI является то, что система предоставляет разработчику высокоуровневый паттерн - ориентированный интерфейс для создания параллельных приложений;
• так как Spring PPI поддерживает объектно-ориентированную модель параллелизма, то позволяет разработчику быстро создать параллельную версию своих программ. Необходимо просто заменить вызовы методов, которые осуществляются в локальном режиме, на вызовы этих же методов, в удаленном режиме (на кластере);
• несмотря на то, что Spring PPI изначально разработана для работы на кластере, то есть с использованием архитектуры MPP, которая не предусматривает наличие разделяемой памяти, в Spring PPI существует достаточно эффективная эмуляция работы с общей памятью (паттерн Repository).

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

Фреймворк параллельного программирования Spring PPI предоставляет программисту высокоуровневый объектно-ориентированный интерфейс для создания параллельных приложений. Базовый интерфейс концептуально включает в себя механизмы вызова удаленных методов на кластере и передачи сообщений между удаленными методами (узлами кластера). На основе базового интерфейса строиться абстрактно более высокий, основанный на паттернах параллельного программирования интерфейс, позволяющий разработчику создавать архитектуру параллельного приложения, используя устоявшиеся методы разработки параллельных алгоритмов.

Реализация системы Spring PPI представляет собой 3 программных модуля:

1) библиотека параллельного программирования (Spring PPI) – представляет собой .NET сборку, подключаемую к программе-клиенту кластера и предоставляющая разработчику интерфейс параллельного программирования;

2) администратор кластера (ClusterAdministrator) – программа, запускающаяся на главном, фронтальном компьютере кластера и отвечающая за распределение вычислительных ресурсов кластера между заявками от программ-клиентов кластера;

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

Концептуально диаграмма развертывания системы SpringPPI представлена на рисунке 1.

В общем, система программирования Spring PPI реализована, основываясь на работе с портами, и не использует .NET Remoting, MSMQ, Indigo или какую-либо другую технологию в качестве способа удаленного взаимодействия между компьютерами. Реализация вызовов удаленных вызовов методов базируется на использовании механизмов рефлексии.

Схема асинхнонного вызова удаленного метода в SpringPPI представлена на анимации 1.

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

Spring PPI реализует работу со следующими паттернами параллельного проектирования:

1. Singleton

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

• объект, метод которого будет вызываться удаленно;
• имя метода вышеуказанного объекта;
• набор аргументов, которые необходимо передать методу.

• путем наследования от абстрактного класса Singleton и переопределения виртуального метода OnRun;
• путем наследования от абстрактного класса Singleton и вызова у объекта класса-наследника метода AddOnRunHandler, который в качестве аргументов принимает ссылку на объект, имя метода и набор агрументов для метода, таким образом определяя функциональность Singleton’а.

2. Pipeline

Паттерн Pipeline применяется, когда «задача может быть разделена на последовательность задач, связанных зависимостью при использовании данных»[13].

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

3. Master-Slave

Паттерн Master-Slave[13] реализует отношение между удаленными методами «главный-подчиненный». Схема работы паттерна следующая: существует главный процесс – Master и несколько подчиненных процессов - Slaves. В Spring PPI паттерн реализован так, что главный процесс может взаимодействовать с подчиненными путем посылки сообщений разного типа. Каждый подчиненный процесс для каждого типа сообщения имеет соответствующий обработчик. Таким образом, взаимодействие между главным и подчиненными процессами можно сравнить с механизмом генерации и обработки событий. Главный процесс генерирует события (сообщения определенного типа) и определяет адресата этого события – одного или нескольких подчиненных процессов. Главный процесс также, при необходимости, определяет набор фактический аргументов, которые должны быть переданы «подчиненным» обработчику события. Далее подчиненный процесс обрабатывает событие, посланное ему мастером, путем вызова соответствующего обработчика события. Механизм обработки событий «подчиненным» основан на принципе очереди (FIFO). Каждый подчиненный процесс имеет на входе очередь событий (сообщений) – каждое последующее событие, направленное на обработку «подчиненному» становиться в конец очереди и ждет, пока подчиненный процесс не обработает его.

Структура паттерна Master-Slave представлена на рис. 3

4. Divide and Conquer

Паттерн Divide and Conquer[14](«Разделяй и властвуй») в Spring PPI может описывать сложную древовидную иерархию задач (Singleton’ов). Задачи в дереве связаны отношением «родитель-потомок» («parent-child»). Каждый «родитель» может иметь несколько «потомков» и, что очень важно, каждый «потомок» может иметь несколько «родителей». Общее правило функционирования паттерна таково, что каждый «потомок» запускается автоматически только тогда, когда каждый его «родитель» завершил работу. В Spring PPI каждый «потомок» может иметь несколько «родителей», это свойство, в общем случае, нехарактерно для такой структуры как дерево, однако подобная особенность является очень полезной при моделировании ситуаций, которые очень часто встречаются в параллельном программировании, например, когда одна задача может быть запущена только после того, как отработали несколько других задач (ее «родителей»). Пример дерева задач паттерна Divide and Conquer представлен на рис. 4.

5. Repository

Repository[13] («хранилище») - паттерн описывающий логику работы процессов (удаленных методов) с общей памятью. Для доступа к хранилищу используется класс SharedMemory. Все хранилище разбивается на ячейки (cells), каждая ячейка имеет свой уникальный идентификатор (ID) строкового типа. В ячейке может храниться объект любого типа - от булевого типа до сложной иерархии разнотипных объектов. Процесс записи и чтения данных из ячейки основан на механизме сериализации. Таким образом, если удаленный метод имеет ссылку на объект SharedMemory и знает необходимый идентификатор ячейки, то он может читать и записывать данные в ячейку. Если в момент, когда один удаленный метод (процесс) читает или записывает данные в ячейку, к этой же ячейке обращается второй процесс, то второй процесс блокируется до тех пор, пока первый не завершит операцию доступа к ячейке. После того как первый процесс завершил работать с ячейкой, второй процесс продолжит свою работу. Структура паттерна представлена на рис. 5.

Каждый из алгоритмов запускался последовательно на 1-ом, 2-ух и 4-х процессорах. Эксперименты проводились на кластере, построенном на основе локальной сети (100 Мб/с) и компьютерах с тактовой частотой 2.4 ГГц.

На рисунках 6, 7, 8 представлены графики, позволяющие оценить масштабируемость каждого из приведенных алгоритмов умножения матриц.

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

Таким образом, на примере реализации трех известных алгоритмов умножения матриц было продемонстрировано, что Run-time система и интерфейс параллельного программирования Spring PPI представляют собой хорошо масштабируемую систему.

В ходе работы над диссертацией, была обоснована необходимость применения паттернов параллельного программирования в качестве способа универсализации и повышения качества подхода к разработке параллельного программного обеспечения. Во фреймворке Spring PPI реализованы паттерны параллельного программирования: Singleton, Master-Slave, Pipeline, Divide and Conquer и Repository. В качестве демонстрации работоспособности и эффективности предложенной модели параллелизма основанного на паттернах, с помощью интерфейса Spring PPI были реализованы классические алгоритмы параллельного умножения матриц: Фокса, Кеннона и ленточный. При проведении тестов все три алгоритма показали достаточно высокий уровень масштабируемости, что говорит о масштабируемости самой Run-time системы Spring PPI.

Здесь выложены промежуточные результаты выпускной работы магистра. Ориентировочная дата окончания работы – декабрь 2007 года. В ходе дальнейшего выполнения диссертации магистра будут проводиться работы над дальнейшим совершенствованием и анализом параллельного паттерн - ориентированного фреймворка Spring PPI. Будут проведены работы по созданию и исследованию параллельной модели доступа и обработки данных, источником которых является реляционная база данных. Кроме уже реализованных паттернов будет проводиться работа над анализом других шаблонных решений в области параллельного программирования. Планируется использование Spring PPI для реализации параллельных версий бухгалтерских алгоритмов – таких как формирование базы данных проводок бухгалтерского и налогового учета на основании базы данных документов, а также формирование дебиторско-кредиторской ведомости.

2. 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 Nick Benton, Luca Cardelli, Cedric Fournet, Microsoft Research, Cambridge

3. Материалы сайта проекта Spring PPI http://springppi.dimetrius.com.ua/

4. Материалы портала http://parallel.ru/

5. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002.

6. Официальный сайт реализации MPI - MPICH http://www-unix.mcs.anl.gov/mpi/mpich/

7. Мультипроцессорная реализация MPI - MP-MPICH http://www.lfbs.rwth-aachen.de/content/mp-mpich

8. Реализация MPI для Windows – WMPI : http://dsg.dei.uc.pt/wmpi

9. Оффициальный сайт проекта PVM http://www.epm.ornl.gov/pvm

10. Проект BSPlib http://www.bsp-worldwide.org/implmnts/oxtool/

11. Материалы по стандарту BSP http://web.comlab.ox.ac.uk/oucl/work/bill.mccoll/oparl.html

12. Оффициальный сайт проекта OpenMP http://www.openmp.org

13. 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

14. Massingill, B.L., Mattson, T.G., Sanders, B.A.: More Patterns for Parallel Application Programs PLoP 2001

15. Martin Fowler. Refactoring: Improving the Design of Existing Code. Addison-Wesley Professional, 1st edition, 1999. With contributions by Kent Beck, John Brant, William Opdyke, and Don Roberts.

16. Д. Б. Балтин, А. И. Андрюхин «Трехслойная архитектура приложений основанных на использовании баз данных». Региональная студенческая научно-техническая конференция "Информатика и компьютерные технологии" ДонНТУ декабрь 2006 г.