Руководитель: д.ф.-м.н. Абрамов С.М.
Зав. кафедрой: д.ф.-м.н., профессор, Осипов Г.С.
Задача распараллеливания программ включает в себя:
При использовании этого подхода зачастую требуются, как значительные трудозатраты, так и затраты времени.
Однако при статическом анализе невозможно для многих случаев предусмотреть все сочетания условий, которые могут возникнуть в процессе выполнения программы. В общем случае оптимальное решение этой задачи найти не удается, т.к. алгоритмически эта задача является неразрешимой. В следствии чего наблюдается снижение эффективности использования аппаратных средств и возникает необходимость ручной доводки программы. Также статические подходы распараллеливания являются плохо адаптируемыми к изменению конфигурации вычислительной системы (например к увеличению числа процессорных элементов).
Таким образом, несмотря на то, что ручное статическое распараллеливание и автоматическое статическое распараллеливание являются основными подходами к распараллеливанию на сегодняшний день они не позволяют создавать наиболее эффективные и универсальные программы для выполнения на вычислительных комплексах с параллельной архитектурой.
Именно этот подход использовался в экспериментальной системе автоматического динамического распараллеливания построенной на модели автотрансформация вычислительной сети-Т-системе разрабатываемой в Исследовательском центре мультипроцессорных систем института программных систем.
В каждый момент времени состояние процесса вычисления представлено в виде сети, узлами которой являются процессы (вызовы Т-функций) и данные, расположенные в звеньях-тегированных участках памяти фиксированного размера. Дуги, объединяющие звенья в сеть представляются в виде особого рода указателей. В начале вычисления сеть состоит из одного корневого процесса.
Узел-процесс соответствует некоторому вызову Т-функции.
Процесс имеет:
Звенья-потребители содержат так называемые невычисленные значения. Если некоторый процесс попытается использовать такое значение для вычисления выражения, его выполнение прервется, и он будет объявлен неготовым к выполнению. Когда соответствующее значение будет вычислено и звено-потребитель получит обычное значение, процесс перейдет в состояние готовности, и его выполнение может быть продолжено. Данный механизм является единственным механизмом синхронизации процессов.
Процессы составляют активную часть сети при ее трансформации. Выполняясь, процесс создает новые данные, а также модифицирует и/или деактуализирует свои собственные данные. Кроме того, выполняющийся процесс может создать новые фрагменты сети за счет вызова Т-функций. При этом порождаются новые процессы, им передаются в качестве входов (аргументов) фрагменты уже имеющейся сети а их выходы соединяются дугами с звеньями-потребителями.
Т-функции являются чистыми функциями, побочные эффекты запрещены. Это дает возможность распределять процессы между процессорами и, таким образом, распараллеливать выполнение вычислений.
С каждым процессом в Т-системе связан свой поток управления (thread), соответствующий выполнению Т-функции пользовательской программы. Таким образом, в рамках одного соисполнителя (Т-системы), являющегося с точки зрения ОС Linux обычным пользовательским процессом, должны сосуществовать множественные потоки управления.
Аппарат множественных потоков управления реализован в компоненте Tthreads Т-системы.
В каждом ПЭ (Linux-машине) выполняется один или несколько экземпляров Т-системы, являющихся в терминах ОС Linux процессами пользовательского уровня.
Каждый из этих экземпляров Т-системы (соисполнителей) имеет возможность обмениваться сообщениями со всеми соисполнителями, работающими в рамках той же задачи пользователя. Для этого используются средства, предоставляемые программным интерфейсом сетевого протокола IP и реализованные в компоненте LMCE Т-системы.
Каждый экземпляр Т-системы ответственен за локальную организацию вычислений в виде автотрансформации вычислительной сети и за взаимодействия с другими соисполнителями.
Совокупность всех экземпляров Т-системы образует распределенную операционную среду параллельного выполнения задачи пользователя.
Звено является элементарной тэгированной единицей памяти, используемой при построении Т-структур. Размер звена в данной реализации Т-системы 12 байтов выбран достаточным:
Т-структурами будем называть расположенные подряд одиночные звенья и мультизвенья.
Одиночные звенья представляют собой одиночное звено со скалярным значением, держатели и одиночные звенья потребители (звенья с неготовыми значениями).
Звено-держатель это указатель специального вида, удерживающий (указывающий на) Т- структуру имеет тэг TTAG_HOLDER и содержит адрес первого звена в Т-структуре и количество звеньев в ней. Так как держатель является одиночным звеном он может входить в некоторую Т-структуру.
Звено-потребитель содержит невычисленное значение (и имеет тэг TTAG_NOTREADY), то есть такое значение, которое должно быть в дальнейшем вычислено как результат (один из выходов) процесса одного из совокупности процессов, параллельно выполняющихся в Т-системе.
Мультизвено служит для хранения данных объем которых больше 10 байтов и состоит из расположенных подряд N+1 звена. Первое звено является заголовком бестэговой области (мультизвена) и имеет тэг со значением TTAG_PACKED. Непосредственно за данным звеном следует несколько (N>=0) бестеговых звеньев, образующих область (до 12N байтов) для хранения произвольных данных. Данные хранящиеся в мультизвене называются упакованными данными.
На входы процесса подаются параметры вызываемой функции, а его выходы рассматриваются как поставщики возвращаемых Т-функцией значений. На входы процесса могут быть поданы: скалярное значение, держатель списка, ссылка на выход другого процесса (неготовое значение), а выходы могут быть присоединены к различным потребителям, в числе которых могут быть: звено, входящее в состав Т-структуры, вход процесса, выполняющего системный вызов SPARK.
Поставщики и потребители фундаментальные понятия вычислительной сети. Поставщиками обычно являются выходы процессов, потребителями могут быть практически любые звенья, в их числе и входы любых процессов. Когда мы говорим, что поставщик присоединен к потребителю, мы подразумеваем, что на поставщика возложена обязанность сформировать в будущем некоторое значение и передать его указанному потребителю. Мы будем говорить, что звено, являющееся потребителем, содержит невычисленное значение, в отличие от настоящих (вычисленных) значений, таких как числа и держатели.
Вновь созданный системным вызовом SPARK процесс объявляется готовым. Объявление процесса готовым подразумевает, что процесс попадает очередь готовых процессов, откуда он со временем будет выбран главным потоком управления (Т-системой) для выполнения. Порождающий процесс после завершения вызова SPARK продолжает свое выполнение.
Во время выполнения процесса могут возникнуть условия, при которых его выполнение не может быть продолжено. В этом случае процесс приостанавливается (засыпает), а когда упомянутые условия исчезают, возобновляется (будится), то есть снова объявляется готовым.
Важный частный случай системного вызова ALT(x) имеет алиасное имя: WAIT(x). Системный вызов WAIT(x) гарантирует, что после его выполнения звено x имеет готовое значение.
В результате выполнения вызова SEND(x,y) может быть передано как готовое, так и неготовое значение, находящееся в звене x. При рассылке неготового значения, потребители поставщика y становятся потребителями того же поставщика, что и у звена x. Заметим, что семантика вызова SEND(x,y) одна и та же во всех случаях: все потребители поставщика y получают то значение, что имеет звено x.
Т-система находится в стадии разработки и реализация с ее использованием реальных задач имеет большое значение для исследования ее возможностей и свойств с целью определения направлений ее развития.
В качестве реальной задачи для распараллеливания на Т-системе была выбрана задача построения реалистических изображений методом трассировки лучей.
Метод трассировки лучей является методом визуализации трехмерных сцен. Сценой является определенный набор геометрических объектов, источников света, сред и т.д., их характеристик, а также различных свойств описываемого пространства варьирующихся в зависимости от формата сцены.
В настоящее время есть множество программных продуктов для визуализации трехмерных сцен и специализированных программ для создания сцен. Поэтому существуют десятки различных форматов описания сцен.
Наиболее популярные из них: MTV, POV-Ray , Polyray, Vivid, QRT , Rayshade, RTrace 8.0, PLG формат для использования с приложением REND386/Avril, Raw triangle формат, RenderMan RIB, Autodesk DXF, Wavefront OBJ, RenderWare RWX, 3D Metafile (Apple Quickdraw 3D), Virtual Reality Modeling Language 2.0 для приложения RTRACE/PLG и другие.
В данной реализации метода трассировки лучей в качестве формата входного файла содержащего сцену был выбран NFF формат, являющийся минимальным языком для описания трехмерных сцен. В формате содержатся описания геометрии и основных характеристик поверхности объектов, расположения источников света, характеристик точки обзора, характеристик "взгляда" и размера создаваемого изображения.
В данной программе реализованы геометрические объекты: сфера, параллелепипед, плоскость и полигон (многоугольник), позволяющий реализовывать объекты практически любой сложности.
Для упрощения реализации и повышения эффективности алгоритма были использованы некоторые принципы объектно-ориентированного программирования, такие как: виртуальные функции и наследование.
Объекты сцены создаются при разборе входного файла данных в NFF формате, наделяются определенными свойствами поверхности и среды и получают указатели на свои функции-методы Intersect и GetTexture.
Метод Intersect ищет точку пересечения геометрического объекта, методом которого она является, с трассируемым лучом.
Метод GetTexture возвращает в качестве результата данные о характеристиках поверхности объекта в заданной точке. Эти данные включают в себя вектор нормали к поверхности в данной точке, цвет объекта, характеристики среды объекта и т. д.
Созданные объекты регистрируются в структуре данных, представляющей объекты сцены, при помощи функции AddToScene которая добавляет в массив указателей на объекты сцены указатель на новый объект, приведенный к базовому типу, который содержит лишь указатели на функции-методы Intersect и GetTexture данного добавляемого типа объекта и инкрементирует счетчик объектов сцены.
Подобным образом производится работа с источниками света.
В основе метода лежит моделирование распространения света в рамках геометрической оптики.
где n - нормаль к поверхности объекта в точке пересечения.
Таким образом направляющий вектор t преломленного луча :
где
При построении реалистических изображений считается, что поверхность обладает и диффузной, и зеркальной отражаемостью с определенными коэффициентами. В данной реализации поверхность объекта имеет такие характеристики, как: коэффициент фоновой освещенности, коэффициент диффузного отражения, коэффициент зеркальной отражаемости и коэффициент преломления.
Возможны два подхода к задаче отслеживания лучей формирующих изображение сцены:
При этом подходе отслеживаются все лучи, в то время как заметный вклад в изображение вносит лишь небольшая их часть. Тем самым значительная часть работы окажется проведенной впустую. Эта избыточность в полном отслеживании лучей требует больших вычислений и существенно сказывается на объеме затрат.
Этого недостатка лишен метод обратной трассировки лучей, отслеживающий лишь те лучи, которые достигают наблюдателя. При этом лучи трассируются в обратном направлении-от наблюдателя через картинную плоскость (экран) до ближайшего пересечения с каким-либо объектом сцены. Картинная плоскость (экран) является набором точек, которые в дальнейшем после расчета их освещенности образуют изображение заданного размера. В данной реализации расположение точек экрана в пространстве вычисляется с помощью функции Camera и зависит от глобальной системы координат, учитывающей направление обзора наблюдателя и его месторасположение. Освещенность соответствующей точки картинной плоскости определяется долей световой энергии, отбрасываемой точкой пересечения в направлении наблюдателя, которая, в свою очередь, складывается из энергии, непосредственно полученной от источников света (и соответственно отраженной и преломленной в направлении наблюдателя), и энергии, полученной от других объектов сцены.
В данной реализации рассчитывается освещенность для трех базовых цветов: красного, зеленого и синего. Для RGB-представления цвета в программе используется структура данных состоящая из трех вещественных чисел, что обуславливает очень качественную цветовую гамму. Поэтому в качестве графического формата, достаточно простого для использования, удовлетворяющего требованиям высокого качества изображения и представляющего интенсивность цвета в спектре RGB, был выбран графический формат TARGA RGB 24 бита на точку.
В этой модели наблюдаемая освещенность вычисляется по формуле:
Первое слагаемое служит для моделирования диффузного обмена энергией между объектами. Определять вклад в диффузную освещенность других объектов непосредственно трассировкой лучей затруднительно, в связи с чем обычно вводят фоновое освещение, равномерно приходящее со всех сторон. Коэффициент Ka определяет вклад фоновой освещенности.
Второе слагаемое соответствует непосредственному диффузному отражению;
Третье слагаемое моделирует непосредственное зеркальное отражение света по формуле Фонга. Использование модели поверхности как идеально зеркальной является не совсем корректным и приводит к большим ошибкам, особенно при работе с точечными источниками света. Поэтому делается разумное допущение о том, что поверхность состоит из множества идеальных микрозеркал с заданным законом распределения нормалей каждого микрозеркала относительно нормали к поверхности.
Здесь член hi - вектор нормали микрозеркала, член (n, hi)^p описывает закон распределения (чем больше степень p, тем ближе поверхность к идеально зеркальной), коэффициент Ks соответствует зеркальной отражаемости поверхности.
Суммирование, как и во втором слагаемом, ведется по всем видимым источникам света.
Четвертое слагаемое соответствует зеркально отраженной энергии, идущей от других тел. Для ее определения луч отслеживается из точки пересечения в направлении отражения.
Последнее слагаемое соответствует преломленной энергии, идущей от других тел. Для ее определения луч трассируется из точки пересечения в направлении преломления. Коэффициент Kt определяет вклад преломленного света.
Алгоритм трассировки лучей является существенно рекурсивным: для определения энергии, которую приносит луч из точки, требуется отслеживать дополнительные лучи, выходящие из точки в направлении отражения и преломления, что в свою очередь может опять потребовать отслеживания дополнительных лучей и так далее.
Таким образом получаем дерево трассировки луча, узлам которого соответствуют точки пересечения лучей с объектами, а ребрам-лучи.
Теоретически дерево трассировки луча может быть бесконечно глубоким. Поэтому в реализации происходит отсечение по глубине (ограничивается максимальная глубина дерева).
Во-первых выполнялось предварительное вычисление некоторых характеристик геометрических объектов. То есть вычисление всех параметров которые необходимы к моменту вызова функций проверки и не зависят от трассируемого луча и точки его пересечения с объектом (например: квадрат радиуса для сферы или нормали к ребрам для полигонов) производится на этапе обработки входного файла, содержащего сцену, и создания внутреннего (программного) представления объектов сцены.
Во-вторых в реализации использовался "Bounding volumes method". Метод был предложен Кларком в 1976 году. Этот метод заключается в окружении сложных объектов (для которых задача определения точки пересечения с лучом является трудоемкой) более простыми объектами, такими как: сферы, параллелепипеды и цилиндры.
В результате сложный объект проверяется на пересечение с лучом лишь в том случае когда трассируемый луч пересекает более простой объект, окружающий сложный. Это дает большое ускорение, так как избавляет от трудоемких и ненужных вычислений.
При создании сцен для тестирования программы не использовались дополнительные программные продукты предназначенные для моделирования сцен. Для тестирования в основном использовались сцены создаваемые программами из набора SPD генерируемые в формате NFF.
При параллельной работе соисполнителей на разных компьютерах каждый процесс (гранула параллелизма) будет интенсивно работать со всеми характеристиками и объектами сцены. В случае если данные хранились бы разрозненно каждому процессу приходилось бы производить большое количество сетевых транзакций-запросов неготовых значений и их передач. Что привело бы к сильному увеличению, как времени выполнения задачи, так и нагрузки на сеть.
Поэтому в распараллеленной версии программы все объекты сцены, источники света и необходимые характеристики после создания и инициализации укладываются в упакованную сцену которая и передается каждому процессу в качестве аргумента.
Построение упакованной сцены происходит следующим образом:
В начало упакованной сцены укладывается структура которая содержит данные о точке обзора, вектор направления обзора, цвет заднего плана (background) сцены, данные о стандартных средах воздух и стекло, порог и геометрический порог-константы используемые алгоритмом трассировки, коэффициент глобального фонового освещения, максимальную глубину трассировки, базовые вектора глобальной системы координат и размер генерируемого изображения. Структура также содержит указатель на массив указателей на источники света, количество источников света, указатель на массив указателей на геометрические объекты сцены и количество объектов сцены.
Затем укладываются массив указателей на источники света и массив указателей на геометрические объекты, затем сами массивы источников света и геометрических объектов сцены.
Для реализации полигонов в упакованную сцену после указателей на геометрические объекты укладываются такие структуры данных для каждого полигона, как: массивы вершин полигона и массивы нормалей к ребрам полигона. С целью оптимизации алгоритма нормали к ребрам каждого полигона вычисляются заранее и укладываются в сцену, в частности для ускорения работы метода Intersect, который определяет пересекается ли данный объект трассируемым лучом и, если да, то в какой точке.
При сборке мусора и при передаче данных между процессорными элементами объекты находящиеся в звеньевой области памяти изменяют свое положение.
Указатели корректируются только в том случае если они являются элементами держателя (holder), так как в нашем случае это условие не выполняется, то все внутренние указатели обеспечивающие доступ к объектам сцены и другим элементам были реализованы как относительные, то есть представляют собой смещение от начала структуры данных сцены до конкретного элемента сцены.
Одним из преимуществ построения структур данных в виде упакованной сцены также является то, что такой вариант позволил избежать полной переделки программы, так как данные содержащиеся в упакованной сцене хранятся в виде пригодном для использования функциями, разработанными в процессе реализации последовательного (непараллельного) варианта алгоритма.
Минимальной гранулой параллелизма-процессом Т-системы является функция, ассоциирующаяся в процессе выполнения с процессом Т-системы.
Такая функция может запускать аналогичные функции-процессы используя Т-системный вызов SPARK, а также может обращаться к обычным последовательным (не параллельным) функциям, которые будут выполнятся на ее фоне. Такими функциями в параллельной реализации являются-главная функция программы и функция реализующая построение фрагмента изображения.
Далее с использованием Т-системного вызова SPARK происходит запуск функции-процесса RenderScene.
Т-функции RenderScene в качестве аргументов передается упакованная сцена, координаты генерируемого фрагмента изображения, его размеры и расстояние между точками картинной плоскости (экрана).
В случае если фрагмент изображения достаточно велик (т.е. количество точек картинной плоскости содержащейся во фрагменте не меньше заранее заданного числа) фрагмент разделяется пополам. Затем с использованием Т-системного вызова SPARK запускаются две новые Т-функции RenderScene с характеристиками соответственно первого и второго участков разделенного фрагмента в качестве аргументов.
В случае когда фрагмент недостаточно велик для дальнейшего деления; на фоне Т-функкии RenderScene вызывается непараллельная функция RenderScene. Именно эта функция реализует построение изображения методом трассировки лучей.
В результате выполнения Т-функция RenderScene возвращает либо держатель пары звеньев, удерживающих результат функций-процессов запущенных при разделении задачи, либо держатель упакованной структуры данных содержащей посчитанный фрагмент изображения с заголовком, который имеет данные о размере и расположении фрагмента изображения.
Таким образом результатом выполнения Т-функции RenderScene является динамически развивающиеся бинарное дерево, которое после стабилизации содержит в качестве листьев посчитанные фрагменты изображения с заголовками.
В главной Т-функции после запуска Т-функции RenderScene для ожидания результата RenderScene выполняется Т-системный вызов ALT, использующий неготовый результат RenderScene. После выполнения Т-системного вызова ALT главная Т-функция программы получает управление в тот момент времени, когда результат головной Т-функции RenderScene, запущенной из главной Т-функции, является уже готовым значением, то есть когда отработала Т-функция RenderScene и, в случае если выполнение производилось на другом процессорном элементе, произошла сетевая транзакция.
Таким образом главная Т-функция в качестве результата, возвращенного Т-функцией RenderScene, получает держатель корня бинарного дерева.
Далее производится нерекурсивный обход этого дерева и вывод фрагментов построенного изображения в файл в формате TARGA.
Для обхода дерева используется нерекурсивный алгоритм, так как листьями нестабилизированного дерева вычислений могут быть неготовые значения, и, как следствие этого, процесс может быть приостановлен для ожидания когда неготовое значение будет вычислено. Существует вероятность, что в этот момент произойдет сборка мусора, что сделает указатели находящиеся в стеке вызова функций неактуальными из-за изменения расположения данных в звеньевой области.
Эксперимент включал в себя:
Ниже (Таблица 4.1) приведены характеристики отдельных ПЭ, входивших в состав вычислительной системы.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее (Таблица 4.3) приведены результаты измерения
времени вычисления стандартной сцены на различных конфигурациях вычислительной
системы состоящей из двух ПЭ. Приведены суммарная вычислительная мощность
вычислительной системы, вычислявшаяся как сумма вычислительных мощностей
ПЭ, входящих в состав системы, время расчета полученное усреднением результатов
измерений (по 10 измерений для каждой конфигурации вычислительной системы)
и стандартное отклонение полученной средней величины.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Была произведена непараллельная реализация алгоритма визуализации трехмерных сцен методом трассировки лучей, соответствующая основным принципам метода и использующая некоторые дополнительные методы и программные решения, накопленные в данной области, для повышения эффективности реализации.
Для ввода исходных данных сцены используется стандартный формат NFF, избавляющий от неудобного и негибкого способа инициализации сцены непосредственно в коде программы и позволяющей использовать специальные программные пакеты для моделирования сложных сцен.
Для вывода готового построенного изображения также используется стандартный формат TARGA использующийся во всех популярных пакетах обработки графической информации.
Затем, была выполнена модификация непараллельной версии алгоритма. Была получена реализация алгоритма в рамках Т-системы, ориентированная на параллельное выполнение, с которой была произведена серия экспериментов с целью изучения зависимости прироста производительности, получаемого при параллельном построении изображения, от суммарной вычислительной мощности процессорных элементов, входящих в состав вычислительной системы.