Software & Systems

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

Данная работа представляет расширение T# платформы .NET, реализующее концепцию автоматического динамического распараллеливания программ. Расширение скрывает низкоуровневые детали организации параллельных вызовов, распределения нагрузки и размещения объектов на узлах кластера от программиста. При этом поддерживается привычная объектно-ориентирован­ная семантика C#. Эти свойства позволяют существенно повысить производительность программиста и в создании новых параллельных программ, и в миграции существующих последовательных программ на параллельную архитектуру.

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

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

В данной работе рассматривается подход автоматического динамического распараллеливания программ, обладающий определенными свойствами.

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

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

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

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

Синтаксис T#: T# является расширением C#. Конструкции, связанные с расширением, реализуются за счет использования .NET-атрибутов. В приведенном примере слева показано описание класса с использованием обычного синтаксиса C#, справа этот же класс описан с использованием конструкций расширения:

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

Разделяемые поля описываются с помощью указания атрибута [shared], при этом если Т-метод работает с разделяемыми полями, то нужно перечислить поля и режим доступа в атрибуте [dependancy], а именно, флаг r означает, что поле используется только для чтения, флаг w позволяет использовать поле и для чтения, и для записи.

Создание объекта, содержащего Т-методы, должно осуществляться с помощью вызова метода CreateInstance служебного объекта TProxyFactory:

A a=(A)TProxyFactory.CreateInstance(typeof(A), new object[]{});

где первый аргумент метода – тип cоздаваемого объекта, а второй – аргументы конструктора.

Архитектура и реализация T# состоит из нескольких уровней:

- пользовательский уровень представляет собой T# программы;

- прокси-уровень скрывает от пользователя уровень суперструктуры;

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

- Т-runtime (среда исполнения) содержит низкоуровневые детали реализации, такие как транспортный уровень, планировщик задач.

Пользовательский уровень содержит три атрибута: [parallel] – для описания Т-методов; [shared] – для описания разделяемых полей; [memoizable] – помечает методы, к которым можно применять мемоизацию, а также интерфейс доступа к прокси-уровню с единственным методом, обеспечивающем создание экземпляров объектов, содержащих Т-методы:

TProxyObject.Create Instance(System.Type instanceType, object[]construc­torArguments)

Прокси-уровень обеспечивает прозрачный доступ из пользовательского уровня к уровню
Т-суперструктуры; содержит функциональность создания прокси-объектов для произвольного .NET-типа. Это достигается за счет исполь-
зования библиотеки System.Reflection.Emit, которая позволяет динамически создавать MSIL-код
в процессе работы приложения. Процесс созда-
ния прокси-объекта проходит следующим обра-
зом.

· Создается новый тип данных пронаследованый от базового типа.

· Для каждого виртуального метода, помеченого атрибутом [parallel], создается метод-двой­ник, переопределяющий базовый, и вместо непосредсвенного его выполнения он формирует
Т-метод, используя функциональность уровня
Т-суперструктуры.

· Создается и возвращается пользовательскому уровню экземпляр нового типа (прокси-объект).

Т-суперструктура содержит описание основных Т-структур и реализует Т-семантику (логику работы с готовыми и неготовыми значениями и разделяемыми полями).

Уровень T-runtime (среда исполнения) содержит низкоуровневые детали реализации T# и состоит из следующих подсистем: транспорный уровень, планировщик задач, мемоизация.

Транспортный уровень. В текущей версии T# существуют два варианта транспортного уровня:

· основаный на потоках – полезен при изначальной отладке программы на одном компьютере;

· основаный на .NET Remoting – реализует выполнение методов в пределах кластера. .NET Remoting реализует большую часть низкоуровневых деталей транспортного уровня. Однако есть возможность и переопределить часть реализации транспортного протокола, например создать свой алгоритм сериализации данных (Formatters) и реализацию каналов (Channels).

Помимо этого возможна реализация транспортного уровня на основе web-сервисов для развертывания T# в распределенных гетерогенных сетях.

Планировщик задач. Реализован ленивый алгоритм планировки задач; имеются 3 очереди:

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

- активные задачи текущего узла;

- приостановленные задачи.

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

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

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

· Если очередь активных задач пуста, планировщик выбирает задачу из очереди пренатальных задач и помещает ее в очередь локальных активных задач.

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

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

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