- •Руководство программиста
- •1. Назначение программы
- •1.1. Назначение
- •1.2. Условия применения
- •2. Характеристика программы
- •2.1. Программа и параллельный алгоритм
- •2.2. Особенности функционального подхода к распараллеливанию
- •2.3. Примеры программ
- •2.3.1. Числа Фибоначчи
- •2.3.3. Рекурсивный обход дерева
- •2.5. Особенности реализации в различных операционных системах
- •2.5.1. OpenTs для Windows
- •2.5.1.1. Платформа Windows Compute Cluster Server
- •2.5.1.2. Инсталлятор
- •2.5.1.3. Набор для разработчика (sdk)
- •2.5.1.4. Интеграция с Visual Studio 2005
- •2.5.1.5. Сборка t-приложений
- •2. Локально в параллельном режиме, используя mpiexec:
- •3. На кластере, используя приложение Cluster Job Submission and Monitoring Console, которое поставляется вместе с Compute Cluster Pack:
- •2.6. Особенности организации параллельных вычислений при помощи т- системы
- •2.7. Программное обеспечение т-системы и дополнительные возможности
- •2.7.2. Архитектура ядра т-системы
- •2.8. Сервисные возможности т-системы
- •2.9. Алгоритм поддержки общей памяти
- •2.9.1. Решения, использованные при построении Суперпамяти
- •2.9.2. Описание архитектуры и программной реализации Суперпамяти
- •2.9.3. Передача значений с узла на узел
- •2.9.4. Алгоритм работы сборщика программного мусора
- •2.9.5. Операции присваивания и «замораживания» неготовых величин
- •2.9.6. Возможное расширение адресного пространства суперпамяти для поддержки распределенных вычислительных сетей
- •2.10. Планирование в OpenTs
- •2.10.1. Постановка задачи
- •2.10.2. Алгоритм планирования
- •Допустим, мы имеем данные t1, t2 и d(t). Рассмотрим эффект от пересылки некоторой задачи с узла 1 на узел 2. Предположим,
- •Где δi зависят от сложности задачи и ее сетевой активности. При этом:
- •2.11. Метапланировщик OpenTs
- •2.12. Поддержка отказоустойчивости исполнения т-приложений
- •2.12.1. Неготовые значения и незавершенные по причине сбоя вычисления
- •2.12.2. Вектор перерождений
- •2.12.3. Вектор посещений
- •2.12.4. Классы повреждений т-функции в случае сбоя
- •3. Обращение к программе
- •3.2. Пример программы, использующей суперпотоки (уровень s)
- •3.3. Использование т-структур и массивов переменного размера
- •3.4. Описание классов реализации системы OpenTs
- •3.4.1. Уровень суперпамяти и суперпотоков
- •3.4.2. Уровень мобильных объектов, мобильных ссылок и мобильных заданий
- •3.4.3. Уровень поддержки т-семантики
- •3.4.4. Сервисные классы
- •3.6. Определение т-контекста во время исполнения программы
- •4. Сообщения
- •4.1. Цветовая схема
- •4.2. Сообщения о фатальных ошибках
- •4.3. Информационные сообщения
- •5. Приложение a. Пример вставки и замены листьев в дереве.
- •6. Приложение b. Использование динамического массива.
2.9.3. Передача значений с узла на узел
Узел, запросивший значение с мастер-узла, заносит пометку в соответствующую «отраженную» ячейку и посылает запрос на мастер узел при помощи коммуникационной библиотеки (в нашем случае — MPI).
Мастер-узел поддерживает массив флагов полученных запросов на чтение (реально он хранится в отраженных ячейках «суперматрицы»). Также хранится массив признаков «отсылались ли данные» для каждого из узлов.
Когда мастер-узел получает запрос на чтение, он проверяет, считывал ли запрашивающий узел данные из ячейки. Если чтение происходит в первый раз с момента последней записи, то данные немедленно отсылаются запрашивающему узлу, в противном случае для ячейки выставляется признак запроса на чтение с запрашивающего узла. Когда в ячейку происходит запись, данные пересылаются всем узлам, у которых уставлен признак запроса на чтение. В любом случае, при пересылке содержимого ячейки по сети какому-либо узлу, выставляется признак «данные отосланы» для данного узла. При записи в «отраженную» ячейку на каком-либо узле, данные немедленно пересылаются на мастер-узел, причем выставляется признак — не пересылать данные обратно на посылающий узел.
В каждом сегменте суперпамяти некоторое количество ячеек можно объявить «общими», то есть не имеющими узла-хозяина (мастер-узла). Запись в эти ячейки на любом узле приводит к немедленной пересылке данных на все узлы. Этот тип ячеек используется для двухстадийной схемы останова Т-системы, а также для поддержки глобальной мемоизации (табулирования значения Т-функций в масштабах всего кластера).
2.9.4. Алгоритм работы сборщика программного мусора
Как известно, распределенные сборщики мусора имеют, как правило, достаточно сложное устройство. Это обусловлено, прежде всего, сложностью самой задачи: с достаточной эффективностью производить сканирование в распределенной системе
Даже задача распределенного подсчета ссылок (с цель автоматического освобождения объектов, которые более не являются достижимыми для программы) является нетривиальной.
Например, наивные схемы с посылкой активных сообщений, которые уменьшают счетчик ссылок в объекте при удалении и увеличивают его при копировании дескрипторов, как правило, не являются работоспособными, так как при нарушении порядка посылки/доставки/обработки сообщений приводят к нарушению целостности. Действительно, если удаление дескриптора после его копирования будет обработано раньше, то память объекта будет освобождена до того, как исчезнет последняя ссылка на этот объект
В литературе описано немало алгоритмов, подчас весьма сложных, которые представляют собой определенные компромиссы между надежностью и эффективностью
В реализации суперпамяти использован достаточно простой подход с использованием взвешенных ссылок. Ключевая идея этого подхода состоит в хранении в дескрипторах взвешенных счетчиков, которые делятся пополам при копировании дескриптора. Как и в случае обычного подсчета ссылок, инвариантом является равенство суммы взвешенных счетчиков и розданных весов. Но, в отличие от наивной схемы, нарушение очередности сообщений не приводит к нарушению целостности. Кроме того, при копировании дескрипторов вообще зачастую не требуется посылать сообщение, что практически вдвое сокращает общее количества передаваемых по сети сообщений. Нами разработана следующая модификация алгоритма со взвешенными ссылками:
При копировании дескриптора, копии дескриптора передается не половина, как в классической схеме, а квадратный корень от веса копируемого дескриптора. Эта схема обладает качественно теми же характеристиками при копировании все более далеких потомков дескрипторов, но выгодно отличается в случае порождении итеративного копирования дескрипторов в цикле. Такая стратегия должна иметь преимущества при преобладании циклов над рекурсивными вызовами, что, как мы полагаем, верно для вычислительных задач, особенно первоначально реализованных на императивных языках (С, С++, Фортран).
