Алгоритмы триангуляции
Романюк Александр, Сторчак Александр,
Системы синтеза реалистических изображений должны обеспечивать передачу всех свойств моделируемого объекта: объемность, расположение, передачу полутонов, тени, освещение, текстуры поверхности. Чем выше степень реалистичности изображения, тем больше требуется вычислений для его формирования.
Генерация объемных изображений представляет сложную вычислительную задачу, в связи этим на практике выполняют ее декомпозицию. Сложные изображения формируют из фрагментов объектов, для чего их разбивают на составные части. Процесс разбиения поверхности объектов на полигоны получил название тесселяции. Эта стадия на данном этапе развития машинной графики проводится полностью программно вне зависимости от технического уровня 3D-аппаратуры.
В настоящее время появилось большое разнообразие графических акселераторов, которые имеют различные аппаратные графические функции для закраски трехмерных объектов, удаления невидимых частей, наложения текстур и т.п. Для использования преимуществ 3D-ускорителей необходимо сначала программно произвести тесселяцию исходных объектов, а затем передать полученные полигональные области для дальнейшей обработки акселератору.
На практике наиболее часто производится разбиение изображений на треугольники.
Это объясняется следующими причинами:
треугольник является простейшим полигоном, вершины которого однозначно задают грань;
любую область можно гарантировано разбить на треугольники;
вычислительная сложность алгоритмов разбиения на треугольники существенно меньше, чем при использовании других полигонов;
реализация процедур рендеринга наиболее проста для области, ограниченной треугольником;
для треугольника легко определить три его ближайших соседа, имеющих с ним общие грани.
Процесс разбиения полигональной области со сложной конфигурацией в набор треугольников называется триангуляцией. При анализе или синтезе сложных поверхностей их аппроксимируют сеткой треугольников, и впоследствии оперируют с простейшими полигональными областями, т.е.
с каждым из треугольников.
Особый интерес к алгоритмам триангуляции определяется тем, что они используются во многих процедурах машинной графики, таких как формирование поверхностей, закраска, удаление невидимых частей, отсечение.
Приведем пример создания полусферы, проиллюстрировав этапы рендеринга. Полигональная область представляется совокупностью треугольников. При этом важно достаточно точно аппроксимировать внешний контур.
Любая поверхность может быть аппроксимирована с необходимой точностью сеткой треугольников. Точность аппроксимации определяется количеством треугольников и способом их выбора. Для качественной визуализации объекта, находящегося вблизи точки наблюдения, требуется учесть во много раз больше треугольников, чем в ситуации, когда тот же объект расположен на удалении. Даже достаточно грубая сетка полезна на практике, так как методы сглаживания, применяемые в процессе отображения, могут значительно улучшить представление о кривизне поверхности.
Следующий этап – закрашивание граней, ограниченных треугольниками.
Последним этапом является применение алгоритмов сглаживания, которые устраняется ребристость поверхности, эффект Маха.
Поверхности, заданные набором точек
В машинной графике задачу триангуляции можно рассматривать в двух направлениях – это триангуляция полигональных областей и триангуляции набора точек. Последняя имеет место при описании поверхности набором точек и интенсивностями их цветов. Поточечное описание поверхностей применяют в тех случаях, когда поверхность очень сложна и не обладает гладкостью, а детальное представление многочисленных геометрических особенностей важно для практики. К поверхностям такого рода можно отнести участки грунта, формы малых небесных тел, микрообъекты, снятые с помощью электронного микроскопа и другие образования со сложной формой.
Среди методов триангуляции для конечного набора точек, которые задают поверхность, широко используют метод Делоне. Метод предполагает соединение между собой набора точек непересекающимися отрезками прямых линий таким образом, чтобы сформированные треугольники стремились к равноугольности. Триангулированное изображение не может быть отнесено к триангуляции Делоне.
Триангуляция набора точек будет триангуляцией Делоне, если описанная окружность для каждого треугольника будет свободна от точек, то есть внутри ее не будет больше ни одной точки из набора. Две окружности, которые не содержат внутри себя других точек (можно провести окружности и для других треугольников, чтобы убедиться, что они также свободны от точек набора). Внутри области, ограниченной окружностью, попала одна точка другого треугольника. Следовательно, эта триангуляция не относится к типу Делоне.
Алгоритм работает путем постоянного наращивания к текущей триангуляции по одному треугольнику за шаг. Вначале триангуляция состоит из одного ребра, по окончании работы триангуляция является триангуляцией Делоне. На каждой итерации алгоритм ищет новый треугольник, который подключается к границе текущей триангуляции. Поиск и подключение треугольника образно можно представить, как надувание двумерного пузыря, привязанного к одному из ребер границы. Если такой пузырь достигает некоторой, еще не включенной в триангуляцию точки из набора, то образуется треугольник. В случае, когда точка не встречена, обрабатывается следующее ребро границы.
Сколько треугольников нужно?
При моделировании объекта возникает задача, какое количество треугольников нужно использовать? С одной стороны нужно достичь максимального качества при окончательной визуализации, а с другой снизить нагрузку на процессор и 3D-акселератор. Для снижения нагрузки можно использовать менее детализированную триангуляционную сеть, но при этом качество будет далеко не самым лучшим.
При формировании динамических изображений точность представления объектов в кадре из-за его перемещения не воспринимается человеком, в связи с чем нецелесообразно использовать детальную триангуляцию.
При выборе подходов и алгоритмов триангуляции следует руководствоваться целью, которая ставится конкретной задачей. Например, при моделировании объекта, находящегося вдалеке, совершенно нет смысла применять очень детальную сеть для его описания и, наоборот, для близких объектов это очень важно, например, для построения модели головы человека требуется около 60 тыс. треугольников.
Триангуляция полигонов
Рассмотрим наиболее распространенные алгоритмы триангуляции полигонов. Простейшее решение задачи триангуляции состоит в расщеплении полигона вдоль некоторой хорды на два полигона и в дальнейшем рекурсивном разбиении их до ситуации, когда подлежащий триангуляции полигон является треугольником.
Данный способ применим лишь для триангуляции выпуклых полигонов. Выпуклым считается полигон, если отрезок прямой, соединяющий любые его две точки, полностью лежит во внутренней области.
Триангуляция невыпуклых полигонов не так проста, поэтому предварительная разбивка невыпуклых многоугольников на выпуклые существенно упрощает алгоритмы их последующей обработки. Проще всего это можно сделать последовательным переносом и поворотом многоугольника так, чтобы одна из его вершин совпадала с началом координат, а исходящая из нее сторона — с осью ОХ. При расположении каких-либо сторон ниже оси, происходит их отсечение, и алгоритм рекурсивно повторяют для полученных полигонов, пока они не станут выпуклыми.
Приведем универсальный алгоритм. Триангуляцию любого полигона можно осуществить по следующему универсальному алгоритму.
Выбирается крайняя левая вершина и между двумя ее смежными сторонами проводится диагональ. При этом могут иметь место следующие два случая:
диагональ является хордой;
диагональ — не хорда, так как внутрь треугольникапопадает вершина полигона (в общем случае их может быть несколько).
Из всех вершин внутри треугольника вершина d наиболее удалена от стороны ас. Эту вершину будем называть вторгающейся. В случае, когда вторгающейся вершины нет, то полученный треугольник заносят в сетку треугольников, и алгоритм рекурсивно обрабатывает оставшийся полигон до тех пор, пока он не выродится в треугольник. При обнаружении вторгающейся вершины проводится диагональ из текущей до вторгающейся вершины. Полученные полигоны рекурсивно обрабатываются до получения треугольников.
Один из подходов к триангуляции состоит в нахождении внутренней точки области, ограниченной полигоном, и соединении с ней всех вершин.
Учитывая, что триангуляция является подготовительным этапом рендеринга, к выбору внутренней точки могут предъявляться определенные требования. Так, например, при многопроцессорной обработке целесообразно внутреннюю точку выбрать таким образом, чтобы площадь составляющих треугольников была примерно одинаковой. В этом случае будет обеспечена одинаковая степень вычислительной загрузки аппаратуры.
При триангуляции в качестве исходных данных наиболее часто задаются вершины полигона. Задача состоит в том, чтобы представить этот полигон совокупностью составных непересекающихся треугольников. В одном из самых распространенных программных интерфейсов (API) для разработки приложений в области двумерной и трехмерной графики стандарте OpenGL для формирования триангуляционной сетки используются следующие команды:
GL_TRIANGLES. Треугольники. Команда рисует серию треугольников, используя тройки вершин v0, v1 и v2, затем v3, v4 и v5 и т.д. Если количество вершин не кратно 3, оставшиеся точки игнорируются. Команду удобно использовать при описании поверхности, которая в результате тесселяции представляется кроме треугольников и другими геометрическими фигурами, например, прямоугольниками. В этом случае треугольники могут быть не соприкасаться между собой. Команда может использоваться для описания всех треугольников полигона, независимо от того, связаны они или нет между собой, однако из-за дублирования информации о координатах общих вершин память используется нерационально.
GL_TRIANGLE_STRIP. Полоса треугольников. Команда рисует серию треугольников, используя вершины в следующем порядке: v0, v1, v2, затем v2, v0, v3, затем v2, v3, v4, и т. д. При таком подходе каждая следующая вершина вместе с двумя предыдущими задает треугольник. Порядок вершин должен гарантировать, что треугольники имеют правильную ориентацию. Полоса может использоваться для формирования части поверхности.
GL_TRIANGLE_FAN. Команда похожа на GL_TRIANGLE_STRIP, но при формировании треугольников используют вершины в таком порядке: v0, v1, v2, затем v0, v2, v3, затем v0, v3, v4, и т.д. Все треугольники имеют общую вершину v0. Команда позволяет разбить n-угольник на n-2 треугольника. Для этого нужно выбрать одну из n вершин полигона и соединить ее с каждой из n-3 несоседних вершин
Использование инструментов среды ParJava.
Рассмотрим некоторые инструментальные средства среды ParJava, применявшиеся при разработке программ компьютерной алгебры. Средства использовались для анализа динамических характеристик программы и для выявления фрагментов кода, оптимизация которых дает максимальный эффект.
Разрабатывая прикладную параллельную программу в рамках среды ParJava, прикладной программист взаимодействует с графическим интерфейсом среды. Он вводит исходный код программы в окне редактора и помещает введенные файлы в проект, в рамках которого хранятся исходный код параллельной программы, ее байт-код, ее внутреннее представление (статические модели классов), ее модель, ее трассы и профили.
Инструментальные средства среды становятся доступными после того, как пользователь выполнит трансляцию исходного кода во внутреннее представление (строятся статические модели классов): с помощью мыши отмечает транслируемые файлы в диалоговом окне управления проектом и вызывает транслятор. В результате трансляции во внутреннее представление для каждого указанного файла исходного кода (содержащего один или несколько классов) строится абстрактное синтаксическое дерево, которое затем передается преобразователю, строящему набор статических моделей классов – объектов класса FileInfo. Трансляция каждого класса выполняется независимо. Это позволяет в случае изменения исходного кода отдельного класса Java-программы повторно транслировать только файл, содержащий данный класс. После трансляции исходного кода в окне управления проектом начинает отображаться информация о структуре класса: каждый файл исходного кода отображается как корень дерева, потомок которого – класс, описанный в данном файле, для каждого класса в виде потомков выводятся методы и поля данного класса.
Выявление критических фрагментов кода выполняется при доводке параллельной программы, когда прикладной программист ищет код, работа которого сильнее всего влияет на характеристики всей программы. Влияние возникает за счет того, что код выполняется достаточно много раз (тела циклов) или занимает большую часть времени работы программы (например, из-за использования библиотек).
Ручная оптимизация такого кода позволяет ощутимо улучшить всю программу в целом. Поскольку относительно всей программы объем критического кода достаточно мал (как правило, он составляет 10-20%), оптимизировать только его проще и эффективней по времени, чем всю программу. Для выявления критического кода необходим профиль параллельной программы. Для облегчения работы пользователя с профилем, среда ParJava предоставляет возможность визуализации – числовые значения профиля отображаются на набор цветов (оттенки серого: от белого до черного), а исходный код программы подсвечивается определенным цветом, согласно полученному для него числовому значению характеристики. Если программа достаточно большая, такая методика уже не дает требуемой простоты и комфортности в работе. По этому в большинстве систем [6, 7], применяемых для доводки параллельных программ, используется иерархическая навигация по профилю. В среде ParJava также были разработаны и реализованы средства, позволяющие изучать профиль поэтапно, переходя от крупных фрагментов программы к более мелким. Рассмотрим порядок поиска критических фрагментов на примере анализа частотного профиля.
Сбор и анализ частотного профиля программы заключается в последовательном использовании инструментов среды: применение инструментатора к файлам исходного кода, отладочном выполнении программы, работа со средствами визуализации. Вопросы, связанные с техникой сбора профилей параллельной программы освещены в работе [8]. Собранный частотный профиль визуализируется с помощью инструментов среды ParJava в основном окне, содержащем исходный код программы, и окне визуализатора профиля. Окно визуализатора разделено на четыре части, три из которых используются для отображения данных, а четвертое содержит элементы управления (см. рис 1).
Рис. 1. Окно визуализатора с загруженным профилем.
Верхнее левое поле, поле программы, отображает частный профиль методов параллельной программы. Значения показываются в виде трехмерной гистограммы, столбцы которой расположены в виде матрицы.
Краткое описание среды ParJava.
Среда ParJava обеспечивает возможность разработки Java-программ, параллельных по данным, расширяя среду Java стандартным интерфейсом MPI, реализующим симметричные коммуникации. От реализации MPI в среде Java требуется, чтобы она минимизировала латентность и другие накладные расходы на организацию коммуникаций. Этим требованиям удовлетворяет реализация функций MPI в среде Java в виде «привязки» к соответствующим функциям реализации MPI в среде С. Такой подход позволяет использовать высокоэффективные реализации MPI, учитывающие специфику аппаратуры используемого коммуникационного оборудования. Реализации MPI в среде Java удовлетворяет этим условиям.
Среда ParJava предоставляет прикладному программисту набор инструментов, позволяющих во время разработки Java-программы на инструментальном компьютере исследовать динамические характеристики как программы в целом, так и ее частей, и использовать эту информацию для улучшения своей программы. В среде ParJava имеется три группы инструментов: анализаторы (меню Analyze), преобразователи (меню
Transform) и интерпретаторы (меню
Run). В текущей версии среды ParJava доступны следующие инструменты: (а) анализаторы:
Sequential – выделение последовательной части параллельной программы; AmdahlRatio – вычисление отношения Амдаля [1]; ForLoop – анализ возможности распараллеливания заданного цикла for с помощью Омега-теста или теста расстояний [2]; Slice – построение обратного динамического слайса для заданного набора переменных в заданной точке программы; (б) преобразователи:
Transform to IC – построение внутреннего представления параллельной программы; Compile – компиляция внутреннего представления отдельного файла параллельной программы в байт-код;
Build Project – сборка параллельной программы;
Instrumentate – инструментирование параллельной программы с компенсацией обращений к инструментальным функциям; (в) интерпретаторы: Exec – выполнение параллельной программы; Simulate – интерпретация модели параллельной программы.
Во время интерпретация модели параллельной программы активизируется диалоговое окно, в котором пользователь может задавать параметры интерпретации: описание узлов целевого кластера, описание его коммуникационной сети, количество вычислительных узлов кластера.
В результате интерпретации получается оценка времени работы программы, определяются границы области масштабируемости (по Амдалю [1], или по Густафсону [3]).
В настоящее время в среду ParJava интегрируется механизм создания контрольных точек параллельных программ [4]. Поскольку существующие реализации JVM не обеспечивают возможности сохранения своего состояния, была разработана и реализована методика сохранения локальных (стековых) переменных и содержимого кучи JVM. С рядом ограничений (одна нить в каждом процессе, отсутствие пользовательских native-методов), такая методика позволяет восстанавливать состояние JVM по данным, сохраненным на диске. Целостность восстановленного состояния обеспечивается за счет использования коммуникационно-управляемого протокола [5] создания контрольных точек. Реализован механизм, позволяющий оптимизировать расположение контрольных точек в программе за счет использования профиля используемой памяти: если короткоживущие переменные занимают достаточно много места, создание контрольной точки откладывается.
ЛИТЕРАТУРА
1. G. M. Amdahl. Validity of the single processor approach to achieving large scale computing capabilities. // Proc. AFIPS Conference, Reston, VA, vol. 30, pp. 483-485, April 1967.
2. E. Walker. Extracting data flow information for parallelizing FORTRAN nested loop kernels. / Submission for the degree of Doctor of Philosophy. Department of Computer Science, Heslington, the University of York, England. 1994.
3. J. L. Gustafson. Reevaluating Amdahl’s law. // Communications of the ACM, vol. 31, no. 5, pp. 532-533, May 1988.
4. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan and Hennadiy Leontyev. Dynamic Analysis and Trace Simulation for Data Parallel Programs in the ParJava Environment. M. Estrada, A. Gelbukh (Eds.) // Avances en la Ciencia de la Computacion, ENC’04, Colima, Mexico, pp. 481-488.
5. M. Elnozahy and L. Alvisi and Y.~M. Wang and D.~B. Johnson. A survey of rollback-recovery protocols in message passing systems. / Technical report, Carnegie Mellon University, CMU-CS-96-181. October 1996.
6. W. E. Nagel, A. Arnold, M. Weber, H.-C. Hoppe, and K. Solchenbach. VAMPIR: Visualization and analysis of MPI resources. // Supercomputer, 12(1): 69--80, January 1996.
7. B. Carpenter, G. Zhang, G. Fox, Xiaoming Li, Xinying Li, and Y. Wen. Towards a Java environment for SPMD programming. // D. Pritchard and J. Reeve, (eds.), 4th Intern. Europar Conf., LNCS vol. 1470, 1998.
8. Виктор Иванников, Сергей Гайсарян, Арутюн Аветисян, Вартан Падарян. Применение среды ParJava для разработки параллельных программ. // Труды Института СистемногоПрограммирования. 2004. с. 41-62.
9. Victor Ivannikov, Serguei Gaissaryan, Arutyun Avetisyan, Vartan Padaryan. Improving properties of a parallel program in ParJava Environment // The 10th EuroPVM/MPI conference, Venice, Sept. 2003, LNCS v. 2840, pp 491-494.
10. Г.И.Малашонок, А.В.Красиков. Пакет процедур для работы с би-матрицами. Вестник ТГУ, Т.7, вып.1 VII Деpжавинские чтения. 2002, с.76.
11. М.С.Зуев.
Матричные операции.
Самыми распространенными формами хранения матриц являются стандартная построчечная форма хранения всех коэффициентов матрицы (DM), которая применяется для хранения плотных матриц, а также построчечная форма хранения ненулевых коэффициентов матрицы и их индексов (SM), которая применяется для хранения разреженных матриц.
Для организации эффективных рекурсивных параллельных матричных операций необходимо иметь соответствующий формат для хранения матриц.
Таким естественным форматом может служить формат кватернарного дерева (QT). Дерево строится следующим образом. Если порядок матрицы 2n, то она может быть разбита на четыре квадратных блока порядка 2n-1, которые также могут быть разбиты на четыре равных блока, и так – вплоть до элементов. Если блокам поставить в соответствие вершины, а ребрами соединить вершины, соответствующие блокам, с вершинами, соответствующими его подблокам, то в результате получим кватернарное дерево. Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует. Это обеспечивает эффективный способ хранения разреженных матриц (см. также [10 и [11]). Отметим, что при необходимости всякая матрица может быть дополнена до матрицы размера 2n, введением дополнительных нулевых или единичных элементов. Заметим, что обозначения QT, DM и SM происходят от названий: quaternary tree, density matrix и sparse matrix.
Если время вычисления суммы и произведения элементов матриц примерно одинаковые, то применение схемы умножения Штрассена не приводит к ускорению вычислений, если порядок матрицы менее 1287 (см. оценки в [12]). Поэтому в первую очередь были разработаны параллельные программы для стандартного алгоритма умножения матриц. При этом использовались две схемы – простая параллельная схема умножения и рекурсивная блочная схема умножения.
Параллельные алгоритмы компьютерной алгебры
Г.И. Малашонок, А.И. Аветисян, Ю.Д. Валеев, М.С. Зуев.
Труды Института Системного Программирования РАН, 2004 г.
В работе рассматривается разрабатываемая в рамках среды ParJava система компьютерной алгебры. Цель разрабатываемой системы – предоставить возможность эффективного использования параллельных вычислительных систем для проведения аналитических расчетов. В силу разреженности данных система включила в себя несколько версий каждой решаемой задачи за счет различных методов распределения данных между процессами параллельной программы. Статья состоит из 5 разделов. В разделе 2 содержится краткое описание среды ParJava. Перечисляются входящие в нее инструментальные средства. В разделе 3 рассматривается применение инструментов среды для решения задач оптимизации программы, возникающих во время ее разработки. Подробно описывается применение нового метода анализа профилей параллельной программы, позволяющего работать с иерархическим представлением численных характеристик. В разделе 4 описываются разработанные программы компьютерной алгебры, приводятся результаты модельных расчетов, проводимых на кластере ИСП РАН. Раздел 5 подводит итоги проведенной работы.
Параллельные программы компьютерной алгебры.
Можно выделить три типа параллельных программ компьютерной алгебры: статический, динамический и комбинированный.
Пусть вычислительный граф задачи разбит на узловые подграфы, т.е. подграфы, вычисление которых происходит на одном процессорном узле. Если закрепление узлового подграфы за конкретным узлом происходит до начала вычислений, то такую параллельную программу называем статической. Если закрепление узлового подграфа за конкретным узлом происходит непосредственно перед вычислением по этому подграфу, в зависимости от состояния загруженности узлов, то такую программу называем динамической. Программа комбинированного типа – это программа, в которой предусмотрено переключение статического режима в динамический.
Задачи компьютерной алгебры имеют дело, как правило, с существенно разреженными данными. Заранее неизвестно, как будут загружены отдельные узлы. Поэтому статические программы могут оказаться неэффективными. Если же данные однородные и загрузку узлов можно рассчитать заранее, то, очевидно, статические программы предпочтительнее любых других типов.
Простая параллельная схема умножения матриц.
Вычисление произведения двух матриц можно осуществить с помощью представления первого матричного сомножителя в виде вектора матричных блоков. В результате умножения каждого такого блока на второй сомножитель, получаем соответствующий блок матрицы, являющейся произведением. Здесь использован естественный параллелизм задачи умножения матриц.
Был реализован статический вариант такой параллельной программы, в которой число блоков, на которые разбивается первый сомножитель, просто выбирается равным числу процессоров участвующих в вычислении, а размеры всех блоков равны между собой или отличаются не более, чем на одну строку. В каждом из процессоров вычисляется умножает одного блоков первой матрицы на вторую матрицу.
Эксперименты с этой программой показали, что при умножении матриц порядка 1024 в конечном поле коэффициент ускорения равен 77% при использовании 12 процессоров. На рис. 4 показана зависимость скорости вычислений этой параллельной программы от количества процессоров, участвующих в вычислении.
Рис. 4. Вычисление произведения матриц в конечном поле с помощью простой параллельной схемы умножения.
Коэффициент ускорения равен 77%.
Рекурсивная блочная схема умножения матриц.
Когда порядки квадратных матриц сомножителей равны 2n, то матрицы разбиваются на четыре одинаковых квадратных блока и вычисление произведения матриц сводится к вычислению 8 умножений таких блоков, с последующим парным суммированием. Для вычисления произведения блоков снова используется эта же схема. Так можно продолжать вплоть до элементов.
Был реализован динамический вариант такой программы. Одно умножение матриц, которые разбиты на четыре блока, сводится к восьми блочным умножениям и может выполняться параллельно на 8 процессорах. Если при этом еще не все процессоры участвуют в вычислениях, то каждое такое блочное умножение может, в свою очередь, быть реализовано с помощью 8 умножений подблоков. Для управления свободными процессорами и организации блочных операции умножения на конкретных процессорах используется программа диспетчера.
Эксперименты для матриц 512 порядка с небольшими целыми коэффициентами (~228) показали, что при умножении в кольце целых чисел коэффициент ускорения равен 85%, а при умножении в конечном поле коэффициент ускорения равный 86.4%. Использовались 2 и 14 процессоров.
На рис. 5 и 6 показаны результаты двух экспериментов, проведенных для динамических параллельных программ умножения матриц. В этих программах использовался QT-формат хранения коэффициентов. В каждом эксперименте выполнялось умножение матриц 512 порядка. В первом случае коэффициенты матриц – это целые числа в пределах 228. Коэффициент ускорения при переходе с двух на 14 процессоров был равен 85%. Во втором случае коэффициенты матриц берутся из конечного поля, характеристика которого не превосходит 2·108. Коэффициент ускорения при переходе с двух на 14 процессоров составляет 85%.
Рис. 5. Вычисление произведения целочисленных матриц в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 85%.
Рис. 6. Вычисление произведения матриц в конечном поле в QT формате с помощью рекурсивной схемы умножения.
Коэффициент ускорения равен 86%.
Рекурсивная блочная схема вычисления присоединенной и обратной матриц.
Для QT-формата был реализован рекурсивный алгоритм вычисления присоединенной и обратной матриц, а также решения систем линейных уравнений (см. [13] и [14]).
Вычисления производились с плотной случайной целочисленной матрицей 128 порядка, с 28-битовыми целыми коэффициентами. Была составлена программа с помощью рекурсивного алгоритма [14] для QT-формата.
Этот алгоритм вычисления присоединенной матрицы в коммутативной области имеет такую же сложность, что и алгоритма матричного умножения, который в нем используется. Для построения параллельного алгоритма был применен последовательный алгоритм вычисления присоединенной матрицы, в котором все процедуры умножения выполнялись параллельно. Результаты экспериментов приведены на рис 7. Коэффициент ускорения при переходе с двух на 14 процессоров равен 60%.
Рис. 7. Вычисление присоединенной (обратной) матрицы в случае целых коэффициентов в QT формате с помощью рекурсивного алгоритма. Коэффициент ускорения равен 60%.
Умножение полиномов.
Были разработаны программы комбинированного типа для умножения полиномов многих переменных. Вычислительный граф параллельной программы имеет вид бинарного дерева: каждый из полиномов сомножителей представляется суммой двух полиномов, а произведение представляется суммой четырех произведений, в которых участвуют эти слагаемые. Ниже, на рис. 2 и 3, показаны результаты двух вычислительных экспериментов с параллельными программами умножения полиномов. На рисунках представлены графики роста скорости вычислений при увеличении числа процессоров, участвующих в вычислениях.
Рис. 2. Вычисление произведения полиномов в конечном поле. Коэффициент ускорения равен 76%.
На этих графиках и на всех графиках дальше по горизонтальной шкале откладывается количество процессоров, участвующих в вычислениях, а по вертикальной шкале – величина, обратная времени вычислений. За единицу времени принято 100 сек. Верхний луч соответствует 100% роста скорости (теоретический предел), нижний луч соответствует росту скорости, равному 50%. В первом эксперименте вычислялось произведение двух полиномов от трех переменных, содержащих по 17 тысяч мономов. Коэффициенты брались из конечного поля, характеристика которого не превосходила 2·108. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 76%.
Рис. 3. Вычисление произведения полиномов с целыми коэффициентами. Коэффициент ускорения равен 85%.
Во втором эксперименте вычислялось произведение таких же по размеру полиномов, коэффициентами которых были случайные целые числа, не превосходящие по модулю числа 228. Коэффициент ускорения при переходе от двух к шестнадцати процессорам составил 85%.
Продолжение
document.write('');
 |
|
|
|
|
<
| This Web server launched on February 24, 1997 Copyright © 1997-2000 CIT, © 2001-2009 |
|
|
| Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. |
|
Только у нас стоит так дешево. |
Используемые сегодня системы компьютерной алгебры,
Используемые сегодня системы компьютерной алгебры, такие как MAPLE, Mathematica, CoCoA, Reduce, Derive и другие, находят применение при решении задач во многих разделах физики, химии, биологии, в задачах моделирования в электротехнике, робототехнике и других областях.
Эти системы предназначены для работы на персональных рабочих станциях и поэтому ограничены задачами небольшой вычислительной сложности. Они опираются на парадигмы программирования 80х-90х годов, когда закладывались основы для этих систем и ориентированы на последовательную организацию вычислений – их базовые структуры данных являются последовательными структурами.
Аналитические расчеты носят характер задач высокой вычислительной сложности, у которых происходит быстрый рост сложности вычислений при росте объемов входных данных. По этой причине для проведения аналитических вычислений требуется разработка параллельных алгоритмов и проведение расчетов на многопроцессорных вычислительных комплексах, требуется создание системы параллельной компьютерной алгебры. Создание такой параллельной системы представляется перспективным в связи с развитием вычислительных сетей и технологий GRID.
Цель этой статьи – обсудить результаты экспериментов с параллельными алгоритмами компьютерной алгебры, реализованными в среде ParJava и проведенными на вычислительном кластере ИСП РАН.
Каждая параллельная программа выполнялась на высокопроизводительном кластере ИСП РАН, состоящем из восьми узлов, связанных сетями Myrinet и Fast Ethernet. Вычислительный узел кластера работает под управлением операционной системы Linux с ядром версии 2.4.20-8, содержит два процессора Athlon с тактовой частотой 1533 MHz и один гигабайт оперативной памяти. Для передачи данных во время работы параллельной программы используется сеть Myrinet, обеспечивающая полнодуплексный канал с пропускной способностью 2 Gbit/sec; топология сети Myrinet представляет собой сеть Клоза (Clos network). Сеть Fast Ethernet используется только для управления работой кластера: монтирование файловых систем, запуск процессов параллельных программ, сбор данных системного мониторинга вычислительных узлов.
Используемые сегодня системы компьютерной алгебры, такие как MAPLE, Mathematica, CoCoA, Reduce, Derive и другие, находят применение при решении задач во многих разделах физики, химии, биологии, в задачах моделирования в электротехнике, робототехнике и других областях.
Эти системы предназначены для работы на персональных рабочих станциях и поэтому ограничены задачами небольшой вычислительной сложности. Они опираются на парадигмы программирования 80х-90х годов, когда закладывались основы для этих систем и ориентированы на последовательную организацию вычислений – их базовые структуры данных являются последовательными структурами.
Аналитические расчеты носят характер задач высокой вычислительной сложности, у которых происходит быстрый рост сложности вычислений при росте объемов входных данных. По этой причине для проведения аналитических вычислений требуется разработка параллельных алгоритмов и проведение расчетов на многопроцессорных вычислительных комплексах, требуется создание системы параллельной компьютерной алгебры. Создание такой параллельной системы представляется перспективным в связи с развитием вычислительных сетей и технологий GRID.
Цель этой статьи – обсудить результаты экспериментов с параллельными алгоритмами компьютерной алгебры, реализованными в среде ParJava и проведенными на вычислительном кластере ИСП РАН.
Каждая параллельная программа выполнялась на высокопроизводительном кластере ИСП РАН, состоящем из восьми узлов, связанных сетями Myrinet и Fast Ethernet. Вычислительный узел кластера работает под управлением операционной системы Linux с ядром версии 2.4.20-8, содержит два процессора Athlon с тактовой частотой 1533 MHz и один гигабайт оперативной памяти. Для передачи данных во время работы параллельной программы используется сеть Myrinet, обеспечивающая полнодуплексный канал с пропускной способностью 2 Gbit/sec; топология сети Myrinet представляет собой сеть Клоза (Clos network). Сеть Fast Ethernet используется только для управления работой кластера: монтирование файловых систем, запуск процессов параллельных программ, сбор данных системного мониторинга вычислительных узлов.
Результаты экспериментов демонстрируют достаточно высокую
Результаты экспериментов демонстрируют достаточно высокую эффективность полученных программ компьютерной алгебры и закладывают основу для разработки аналогичных программ для других задач. Можно говорить, что сделаны первые шаги на пути создания параллельных алгоритмов компьютерной алгебры.
Реализация авторизационного механизма корпоративной системы с помощью иерархической модели сущностей
В последнее время наблюдается тенденция к интеграции различных независимых информационных систем автоматизации деятельности предприятия в единые информационные системы. Интегрированные системы управления предприятием (ИСУП) могут охватывать как несколько отделов внутри одного предприятия, так и несколько предприятий. Количество пользователей такой интегрированной системы может достигать нескольких сотен. При этом система должна иметь возможности для решения проблемы делегирования полномочий между участниками системы. В данной статье предложен принципиально новый подход к организации авторизационного механизма корпоративной системы.
Каждая ИСУП представлена широким рядом различных сущностей. Сущность - это класс однотипных объектов. С увеличением количества как самих сущностей, так и объектов этих сущностей, неизбежно возникает вопрос об организации эффективного управления этими объектами. Самое основное, что необходимо для эффективного управления - распределение ответственности и обязанностей между участниками системы. Распределение ответственности не только на уровне сущностей, но и на уровне объектов. Такое распределение позволяет эффективно использовать систему с учетом возможности неограниченного расширения. При этом осуществляется строгий иерархический контроль, в том числе, что самое главное - контроль над контролем. Количество уровней иерархии ничем не ограниченно, и определяется текущими требованиями и спецификой деятельности в рамках отдела, или даже в рамках каждого отдельно взятого объекта сущности, который может рассматриваться в данном контексте как субъект бизнес-процессов предприятия или отдельно взятый функциональный блок. Следует заметить, что именно такой подход к распределению полномочий используется в управляющих системах, построенных по принципу иерархии (например, в вооруженных силах, государственных структурах).
Для построения авторизационной подсистемы по предложенному механизму потребуется произвести ряд действий:
Определить набор сущностей системы, действия над объектами которых предполагается делегировать. Построить дерево связей между сущностями, определенными на шаге 1.
При этом корневым элементом будет являться виртуальная сущность Root, соответствующая единственному объекту Root. Эту схему будем условно называть "дерево связей". Сущность Root определяет систему как единое целое, поэтому она содержит единственный объект. Привести модель "Сущность-Связь" к такому виду, чтобы сущность являющаяся родительской в "дереве связей" была связана с дочерней отношением "один-ко-многим". Определить множество делегируемых действий над каждой сущностью.
Одним из ключевых понятий в предложенном механизме является авторизационная роль, или просто роль.
Роль - это настраиваемая совокупность доступных действий. Роли создаются и настраиваются в процессе эксплуатации системы. Если нет необходимости в настраиваемых ролях, тогда они могут быть жестко определены на стадии разработки системы.
Доступ - это назначение определенной роли участнику системы для взаимодействия с объектом, или с его дочерними объектами.
Таким образом, чтобы определить доступ, необходимо определить три вещи:
роль; пользователь; объект, на который распространяется эта роль.
Доступ, определенный на объект родительской сущности распространяется на все присоединенные объекты дочерних сущностей.
Программный код системы, при попытке пользователя совершить то или иное действие над заданным объектом системы, должен предусматривать проверку возможности совершения этого действия. Фрагмент алгоритма кода системы:
...
Если Разрешено_Действие(номер_пользователя, номер_сущности, номер_объекта, номер_действия)
То Произвести_Действие(объект, номер_действия);
...
Функция проверки доступности действия имеет вид:
Функция Разрешено_Действие(номер_пользователя, номер_сущности, номер_объекта, номер_действия)
Если Cуществует_Доступ(номер_пользователя, номер_сущности, номер_объекта,номер_действия)
То вернуть "Истина"
Иначе
Если номер_сущности не равен Root
То
Получить_Родительский_Объект(номер_сущности, номер_объекта, номер_родительской_сущности, номер_родительского_объекта);
вернуть Разрешено_Действие(номер_пользователя, номер_родительской_сущности, номер_родительского_объекта, номер_действия);
Иначе
вернуть "Ложь"
Функция "Существует_Доступ" проверяет наличие доступа пользователя к данному объекту путем проверки всех назначенных ролей, в список доступных действий которых входит заданное действие. Функция "Получить_Родительский_Объект" использует информацию о виде "дерева связей", поэтому авторизационная подсистема должна предусмотреть хранение этой информации.
Рассмотрим небольшой пример. Существует дерево связей (рисунок).
Допустим, существует роль "Полный доступ", в список доступных действий которой входят все возможные действия над всеми сущностями системы. Если назначить эту роль пользователю Петрову на объект Root, то он получит полный доступ над всеми объектами всех сущностей. Если эту роль назначить пользователю Иванову на объект "Филиал № 5" сущности "Филиал", то Иванов обретет полный доступ над филиалом № 5, всеми отделами и складами этого филиала.
Допустим, существует роль "Управление складом", в список доступных действий которой входят действия по манипулированию приходом и расходом товаров на склад. Если назначить эту роль пользователю Петрову на объект Root, то он сможет управлять всеми складами системы. Если назначить эту роль пользователю Петрову на объект "Филиал № 5", то Петров сможет управлять всеми складами филиала № 5. Если назначить эту роль пользователю Сидорову на объект "Склад № 1" филиала № 5, то Сидоров сможет управлять только одним этим складом.
Предложенный механизм авторизации используется в корпоративной системе, функционирующей в НПП "СпецТек" (Санкт-Петербург). Эта корпоративная система предназначена для автоматизации деятельности софтверных и консалтинговых предприятий. Возможность делегирования полномочий позволила использовать систему для одновременного ведения нескольких проектов ПО, на каждый из которых назначается руководитель, разработчики, тестировщики.В отделе консалтинга осуществляется разделение ответственности по договорам с назначением руководителя, технической поддержки. Настраиваемые роли позволяют гибко регулировать полномочия сотрудников в соответствии с организационной структурой предприятия.
Анализ и оптимизация циклов с помощью производящих функций
Труды Института Системного Программирования РАН, 2004 г.
Аннотация
В статье рассматривается метод анализа и оптимизации циклов с помощью производящих функций, состоящий в поиске выражений для конечных значений переменных, которые вычисляются в цикле и замене цикла вычислениями по формуле.
Описание метода
Производящая функция последовательности {an}, n>=0 – формальный степенной ряд:
Переход от последовательностей к их производящим функциям позволяет заменить операции над последовательностями операциями над их производящими функциями.
Идея метода производящих функций состоит в том, что рекуррентное соотношение, определяющее последовательность {an}, переписывают как уравнение для ее производящей функции, это уравнение решают и по найденной производящей функции получают зависимость общего члена последовательности {an} от n.
Для того, чтобы получить алгебраические выражения для значения каждой переменной в зависимости от номера итерации необходимо преобразовать операции, изменяющие значения переменных, в рекуррентные соотношения вида:
где i – номер итерации
t – функция преобразования переменной v, принадлежащая множеству T
Vi-1 – значения переменных, полученные на предыдущей итерации
Vi – значения переменных, полученные на текущей итерации
Производящие функции (или выражения для vi) достаточно просто можно получить для присваиваний вида:
В этом случае для получения выражения для vi достаточно подставить выражения для всех остальных переменных в правую часть или найти производящую функцию для f.
Пользуясь методикой из [2] каждый оператор присваивания вида
где Fv(z) – производящая функция для переменной v
FV – множество производящих функций для переменных, принадлежащих множеству V
G – некоторая алгебраическая функция
Найти алгебраическое выражение (возможно содержащее в себе другие производящие функции) для производящей функции для f можно пользуясь линейностью производящих функций: производящая функция суммы равняется сумме производящих функций.
Для каждого из слагаемых существует следующий выбор: Производящую функцию можно определить непосредственно (например, если слагаемое представляет собой константу, умноженную на переменную) по таблице прозводящих функций из [2]
Производящую функцию нельзя получить непосредственно. Например, ai - bi. В этом случае, необходимо подставить выражения для всех переменных (ai и bi), а затем найти производящую функцию для последовательности, которую генерирует это выражение при изменении i от 0 до бесконечности.
Производящую функцию нельзя получить непосредственно (как в случае 2), но выражения для ai и bi (см. случай 2) невозможно получить без знания выражения для vi+1. В этом случае предлагаемый метод не работает.
Полученные выражения для переменных можно подставить в P, чтобы определить номер итерации на которой произойдет выход из цикла. Если данную задачу удается решить, то цикл может быть заменен вычислениями по формуле или просто подстановкой констант в случае, когда все параметры, входящие в выражения для результирующих переменных известны на этапе компиляции. Рассмотрим несколько примеров
1. Переменная, которая в каждой итерации умножается на константу и к результату прибавляется другая константа
Найдем производящую функцию для данной последовательности
Отсюда можно получить алгебраическое выражение для v в зависимости от номера итерации:
| для c1 = 1: |  |
(*) |
| для c1 <> 1: |  |
2. Линейная комбинация переменных
где k – номер переменной (переменные с номерами меньше k изменились в текущей итерации, с номером большим k – будут изменены позднее)
Применяя манипуляции, подобные использованным в предыдущем пункте, можно получить следующий результат:
Отсюда можно получить выражение для Vk(z), а из него – выражение для vki.
3. Многочлен от переменных, выражения для которых имеют вид (*)
Метод, применяемый в предыдущих примерах здесь не сработает, поэтому необходимо выполнить подстановку выражений для vji в данную формулу, что приведет к появлению многочлена от i:
Производящая функция для in не существует в простой форме, однако ее можно выразить через производящие функции для числа сочетаний:
Отсюда можно получить производящие функции для in:
| i1: |  |
| i2: |  |
и так далее.
Таким образом, производящая функция для vki будет иметь вид:
где ri – коэффициент при in в R(i), а Ii(z) – производящая функция для in.
Существует множество методов оптимизации циклов.
Существует множество методов оптимизации циклов. Большинство методов только изменяют структуру цикла, оставляя его в программе. Среди них выделяется метод оптимизации циклов, которые не выполняют никаких действий, кроме изменения некоторых переменных. Для этого используется интерпретация циклов на этапе компиляции, если количество итераций невелико [3]. Если же число итераций превышает некоторое пороговое значение, то данный метод оказывается неэффективным.
В данной статье рассматривается метод оптимизации циклов следующего вида с помощью производящих функций:
| для ∀ v ∈ V | v = v > C | |
| While (P) | |
| для ∀ v ∈ V | v = T(v, C) |
где:
V – множество переменных, используемых в цикле, N – мощность этого множества
C – множество констант
V > C – множество начальных значений переменных, используемых в цикле
P – предикат, сигнализирующий об окончании цикла, представляющий собой результат применения логических и алгебраических операций к переменным из множества V и константам из множества C
T(V, C) – множество функций преобразования элементов множества V, используемых в цикле
В статье рассмотрен метод анализа
В статье рассмотрен метод анализа циклов с помощью производящих функций. Несмотря на то, что не все циклы могут быть подвергнуты анализу с помощью данного метода, его можно применить для решения нижеперечисленных задач.
1. Данный метод выполняет задачу, обратную описанной в [3, разд. 14.1.1] – т.е. заменяет инкрементальные вычисления вычислениями по формуле. Кроме того, в процессе анализа цикла с помощью данного метода можно найти все его индуктивные переменные.
2. Компилятор, проделав все вышеприведенные вычисления, может либо заменить результат вычислений на константу (если все параметры являются постоянными), либо использовать вместо цикла соответствующую формулу.
3. Если цикл, подобный вышеприведенному, является вложенным в какой-либо другой, то производящие функции для переменных из V можно использовать описанным выше способом при оптимизации главного цикла.
4. Данный метод, как и многие другие методы алгебраической оптимизации, может быть использован только для целых чисел из-за возможной потери точности или переполнения чисел с плавающей точкой.
5. Полученные выражения для переменных могут быть использованы при анализе зависимостей между переменными, определении псевдонимов, устранении общих подвыражений (в том числе и полученных при выполнении аналогичных действий в различных циклах), при устранении незначимых вычислений, при определении индуктивных переменных.
6. Аналогичный подход может быть применен при оптимизации некоторых видов рекурсивных вычислений.
Алгоритм распространения констант, использующий GSA-представление
Алгоритм распространения констант, описанный в [8] использует SSA-представление (Static Single Assignment) программы. В SSA-форму программа трансформируется таким образом, что только одно присваивание может достигнуть точки использования. Так как программы имеют ветвления и точки объединения нескольких путей, то в точках объединения необходимо добавить специальную форму присваивания, названную ?-функцией. ?-функция имеет форму V ← φ(R, S, …), где V, R, S, … – переменные. Количество операндов такой функции равняется количеству предшественников данного узла. Эти предшественники перечисляются в некотором определенном порядке и j-й операнд ?-функции ассоциируется с j?м предшественником узла. Если путь выполнения программы лежит через j?го предка узла, то переменная V получает значение, связанное с j?м аргументом. Каждое исполнение ?-функции использует только один из аргументов, но который именно – зависит от того, из которого узла получил управление данный узел.
В работе [8] алгоритмы распространения констант разделены на те, которые находят простые и условные константы. Алгоритм Sparse Conditional Constant Propagation находит все простые, а также некоторые условные константы. Время работы такого алгоритма пропорционально размеру SSA-графа и каждое SSA-ребро обрабатывается максимум два раза.
Когда необходимо классифицировать переменную в точке слияния, мы используем функцию meet для аргументов ее ?-функции. Но если в процессе своего выполнения программа всегда идет только по одной ветке было бы лучше использовать то значение переменной, которое порождается именно в ней. В методе, описанном в предыдущем разделе, если значение предиката будет постоянным, то выполняемое ребро будет добавлено к рабочему списку. Поэтому в точке слияния выражения будут вычисляться с использованием информации о входящих выполняемых ребрах, что может приводить к неоднократному вычислению одних и тех же выражений.
В методе, использующем GSA, если символ использует значение из точки слияния, то вычисляется значение предиката и определяется путь из которого берется значение.
При использовании φ- функции мы не можем определить по какому пути шло выполнение программы. Но если снабдить φ-функцию предикатом, то, если его значение является константой, можно выбрать нужный аргумент φ-функции, а если нет, то самое лучшее, что можно получить с помощью данного метода – это взять функцию meet от φ-аргументов.
Чтобы выполнить данную задачу необходимо расширить SSA-представление до GSA (gated single assignment), введенное в работе [3], которое позволяет вычислять условные выражения, базирующие на предикатах. В данном представлении ?-функции заменяются на μ- и ?-функции. Большая часть φ-функций, расположенных в заголовках циклов переименовываются в μ-функции, тогда как остальные – преобразуются в ?-функции. ?-функция имеет вид: v = ?(P, v1, v2), что означает, что v принимает значение v1, если P=true и v2, если P=false. В такой форме ?-функция представляет собой конструкцию if-then-else, но она может быть расширена для работы с более сложными условными конструкциями. Алгоритм для преобразования φ-функций в μ- и ?-функции представлен в работе [6].
В данном алгоритме используется представление программы в виде базовых блоков, состоящих из кортежей. Базовые блоки и кортежи внутри них связаны между собой и вместе образуют граф потока данных. Кортежи имеют следующие атрибуты: op, left, right, ssa_link, lattice, где op – код операции, left и right – два операнда. ssa_link – связь, порождаемая алгоритмом преобразования программы в SSA-форму. Поля left, right, ssa_link представляют собой указатели на соответствующие кортежи. Каждая операция (кортеж) также имеет ассоциированное значение – lattice, принадлежащее множеству значений из решетки и представляющее собой результат выполнения операции, который может быть получен на этапе компиляции.
Исходный алгоритм
∀ t ∈ tuples lattice(t) = T unvisited(t) = true
Visit all basic blocks B in the program Visit all tuples t within B if unvisited(t) then propagate(t)
propagate (tuple t) unvisited(t) = false if ssa_link(t) ? 0 then if unvisited(ssa_link(t)) then propagate(ssa_link(t)) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if unvisited(left(t)) then propagate(left(t)) if unvisited(right(t)) then propagate(right(t)) case on type (t) constant C: lattice(t) = C arithmetic operation: if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ⊥ endif store: lattice(t) = lattice(RHS) φ-function: lattice(t) = П of φ-arguments of t ?-function: if lattice(predicate) = C then lattice(t) = lattice value of ?-argument corresponding to C else lattice(t) = П of all ?-arguments of t endif ?-function: lattice(t) = ⊥ η-function: lattice(t) = lattice(η-argument) default: lattice(t) = ⊥ end case end propagate
Недостатки и предлагаемые изменения
В работе [7] показано, что арифметические и логические выражения, включающие ?-функции, можно преобразовывать в несколько вложенных ??функций и арифметических выражений, что позволяет получать константные выражения даже в тех случаях, когда аргументы исходного арифметического или логического выражения не являются константами. Это видно по следующему примеру: if P then a1 = 2 b1 = 1 else a2 = 4 b2 = 2 endif a3 = ?(P, a1, a2) b3 = ?(P, b2, b3) if a3 > b3 then ... endif
В данном случае переменные a3 и b3 будут всегда равны независимо от значения предиката P. Алгоритм, предложенный в [5] не сможет определить отношение значений переменных в данной ситуации.
Предлагаемые изменения алгоритма привели бы предикат a3 > b3 к виду: ?(P, a1 > b1, a2 > b2) = ?(P, true, true) = true.
Предлагаемые изменения алгоритма касаются обработки арифметических и логических выражений и состоят в следующем:
E1, E2 – аргументы арифметического (логического) оператора E1 и E2 не содержат ?-функций, либо обе содержат ?-функции с разными предикатами. Используется обычное правило для вычисления арифметических и логических выражений.
Один из аргументов (E1 для определенности) содержит ?-функцию. Выполняется следующее преобразование:
?(P, V1, V2) op E2 = ?(P, V1 op E2, V2 op E2)
E1 и E2 содержат в себе ?-функции с одинаковыми предикатами. Выполняется следующее преобразование:
?(P, V1, V2) op ?(P, V3, V4) = ?(P, V1 op V3, V2 op V4)
Новый алгоритм
? t ? tuples lattice(t) = T unvisited(t) = true
Visit all basic blocks B in the program Visit all tuples t within B propagate(t)
propagate (tuple t) if not unvisited(t) return unvisited(t) = false label restart:
if ssa_link(t) ? 0 then ssa_link(t) lattice(t) = lattice(t) П lattice(ssa_link(t)) endif if type(t) ? arithmetic operation
propagate(left(t)) propagate(right(t)) endif
case on type (t) constant C: lattice(t) = C arithmetic or logic operation: if type(left(t)) = ?-function or (type(right(t)) = ?-function then if type(left(t)) = ?-function and (type(right(t)) = ?-function or type(ssa_link(right(t))) = ?-function) and (predicate(left(t)) = predicate(right(t)) or type(ssa_link(left(t))) = ?-function) then join_common_predicate(t) goto restart else join_gamma_with_operand(t) goto restart endif else propagate(left(t)) propagate(right(t)) endif
if all operands have constant lattice value then lattice(t) = arithmetic result of lattice values of operands else lattice(t) = ? endif store: lattice(t) = lattice(RHS) ?-function: lattice(t) = lattice(left(t))П lattice(right(t)) ?-function: propagate(predicate(t)) if lattice(predicate(t)) = C then lattice(t) = lattice value of ?-argument corresponding to C else lattice(t) = lattice(left(t)) П lattice(right(t)) endif ?-function: lattice(t) = ? η-function: lattice(t) = lattice η-argument) default: lattice(t) = ? end case end propagate
Функция join_common_predicate – объединяет две ?-функции с одинаковыми предикатами в одну
join_common_predicate (tuple t) tuple new_t = new ?-function predicate(new_t) = predicate(left(t))
left(new_t) = new operation node, same as t ssa_link(left(new_t)) = 0 unvisited(left(new_t)) = true lattice(left(new_t)) = T left(left(new_t)) = left(left(t)) right(left(new_t)) = right(left(t))
right(new_t) = new operation node, same as t ssa_link(right(new_t)) = 0 unvisited(right(new_t)) = true lattice(right(new_t)) = T left(right(new_t)) = left(right(t)) right(right(new_t)) = right(right(t))
t = new_t ssa_link(t) = 0 lattice(t) = T end join_common_predicate
Функция join_gamma_with_operand – объединяет ?-функцию и операнд, который не является ?-функцией join_gamma_with_operand (tuple t) tuple g, op tuple g_left = new operation node, same as t tuple g_right = new operation node, same as t if type(left(t)) = ?-function then g = left(t) op = right(t) left(g_left) = left(g) left(g_right) = right(g) right(g_left) = op right(g_right) = op else op = left(t) g = right(t) left(g_left) = op left(g_right) = op right(g_left) = left(g) right(g_right) = right(g) endif left(g) = g_left right(g) = g_right t = g
unvisited(g_left) = true lattice(g_left) = T ssa_link(g_left) = 0
unvisited(g_right) = true lattice(g_right) = T ssa_link(g_right) = 0 end join_gamma_with_operand
Усовершенствованный алгоритм распространения констант с использованием GSA-представления
Труды Института Системного Программирования РАН, 2004 г.
В данной статье представлены усовершенствования метода распространения констант, использующего GSA-представление (Gated Single Assignment), позволяющие алгоритму находить большее количество констант, чем исходный алгоритм.
Время работы алгоритма
Т.к. в оригинальном алгоритме флаг unvisited для каждого узла не может измениться более одного раза, то это означает, что алгоритм посещает каждый узел единожды, поэтому время его работы может быть оценено как O(N), где N – количество узлов.
Модифицированный алгоритм, как и исходный, посещает каждый узел представления программы единожды. В предельном (невозможном на практике) случае, однако, тип каждого узла может быть преобразован, поэтому время, необходимое для обработки одного узла может увеличиться. Тем не менее, время работы алгоритма также представляет собой величину порядка O(N).
Таким образом, улучшенный алгоритм обладает большими возможностями по обнаружению констант, чем исходный лишь незначительно увеличивая время его работы (при том, что асимптотическая оценка времени работы остается той же).
Для сравнения предикатов можно использовать сравнения указателей на них (т.е. предикаты эквивалентны, если они указывают на один и тот же оператор ветвления) или алгоритм классификации выражений, описанный в [2]. Первый вариант позволяет выполнить сравнения без значительных затрат времени. Второй – позволяет найти одинаковые предикаты, которые не принадлежат одному оператору ветвления, но требует дополнительных затрат времени на классификацию предикатов.
хорошо известная проблема глобального анализа
Распространение констант – хорошо известная проблема глобального анализа потока данных. Цель распространения констант состоит в обнаружении величин, которые являются постоянными при любом возможном пути выполнения программы, и в распространении этих величин так далеко по тексту программы, как только это возможно. Выражения, чьи операнды являются константами, могут быть вычислены на этапе компиляции. Поэтому использование алгоритмов распространения констант позволяет компилятору выдавать более компактный и быстрый код.
Хотя в общем случае проблема распространения констант является неразрешимой, существует множество проявлений этой проблемы, для которых существуют эффективные алгоритмы.
Технологии распространения констант позволяют решить следующие задачи: выражения, вычисляемые на этапе компиляции не нужно вычислять в процессе выполнения программы
код, который никогда не выполняется, может быть удален. Недостижимый код может появляться в тех случаях, когда значение предиката в условном выражении неизменно и известно на этапе компиляции.
увеличение эффективности встраивания процедур.
Распространение констант совместно со встраиванием процедур (когда многие параметры процедур являются константами) позволяет избежать разрастания кода, которое часто является результатом встраивания процедур в места из вызовов
Корпоративные информационные технологии
Ведение рубрики «Экстремальные технологии» невольно выработало у меня определенные стереотипы — например, представление о том, что «экстрим» обычно предлагают небольшие компании, организованные авторами и приверженцами той или иной идеи. Среди них успеха добиваются далеко не все и не сразу. Можно привести целый ряд примеров, когда блестящая идея так и остается идеей или когда путь до массового внедрения занимает долгие годы. Понятно, что без участия отраслевых «тяжеловесов» новую идею редко удается привить обществу, а тех сдвинуть с места не просто. Но бывают редкие исключения, когда процесс ассимиляции той или иной новой технологической идеи занимает всего несколько месяцев, что свидетельствует: она востребована.
Мгновенную метаморфозу, стремительный переход от полной неизвестности до прикрепления на свой флаг ведущими производителями пережила идея общей шины предприятия (Enterprise Service Bus, ESB). Напомним предысторию вопроса. Под влиянием Internet за прошлый, 2002 год в сознании большинства ИТ-профессионалов, ответственных за перспективы развития корпоративных систем, окончательно вызрела мысль о том, что традиционная транзакционная модель устарела, а будущее за средствами, которые смогут обеспечить асинхронный обмен сообщениями между приложениями. Понятно, что такими средствами прежде всего (или только) являются Web-службы. С их помощью может быть создана архитектура, ориентированная на службы (Service Oriented Architecture, SOA), способная удовлетворить этим требованиям. Собственно конструкция, состоящая из служб, не нова. Она существует несколько лет; за это время был разработан стек основных стандартов для Web-служб — UDDI, WSDL и другие, но в первую очередь SOAP.
Следует учесть, что Web-службы уходят корнями в Microsoft. Там они были задуманы как средство доступа к глобальной системе приложений, с глобальными репозиториями, каталогами и т.д. На первом этапе службы были широко разрекламированы, многократно представлены людьми, которые по большей части не понимали сути происходящего.
Впрочем, в своем первоначальном виде они оказались не слишком востребованы. Однако, как это зачастую бывает, тот же самый механизм служб оказался эффективным и востребованным в смежной области. При ближайшем рассмотрении выяснилось, что Web-службы являются вполне подходящим средством для интеграции корпоративных приложений.
Это соображение было воспринято не сразу. Однако в 2003 году, как по мановению волшебной палочки, наступил момент, когда в его справедливости уже никого убеждать не требуется, все аналитики из Gartner, Giga, Meta и других многочисленных «Group» дружно проголосовали «ЗА». Несложно обнаружить, что перед нами — очередной пример заимствования Internet-технологий и их адаптация к корпоративной инфраструктуре, почти также десять лет назад появились сети intranet на основе технологий, почерпнутых когда-то из Глобальной сети. Для полной аналогии остается немногое: нужно подобрать службам, работающим в корпоративных сетях, какое-то иное название или попросту отбросить приставку Web — ведь к WWW они никакого отношения не имеют.
Итак, общий смысл новаций предельно ясен: в системах с архитектурой SOA посредством Web-служб корпоративные приложения могут общаться между собой в асинхронном режиме. Однако оставался не вполне (или даже совсем не) понятен конкретный механизм реализации этого режима взаимодействия. Наиболее красивое решение первыми предложили компании Collaxa и Sonic. При этом Sonic так и назвала этот механизм — SonicXQ Enterprise Service Bus. Вскоре, но заведомо точно после Sonic, концепцию ESB стали проповедовать аналитики Gartner Group. Идея ESB оказалась исключительно красивой и новой. Вот почему в еще пахнущем типографской краской апрельском номере «Открытых систем» общая шина предприятия ESB была представлена как экстремальная технология. Подчеркну: на момент написания статьи ESB ассоциировалась только с компанией Sonic; сомневающимся рекомендую сделать поиск в Сети на Enterprise Service Bus.
Наблюдение первое
Но уже в мае возникло ощущение, что ESB перестает быть экстремальной технологией.
Во-первых, на состоявшемся в мае симпозиуме IBM Software Symposium 2003 в Мюнхене именно эти две технологии и SOA, и ESB оказались в центре внимания. Это серьезный знак. Надо учесть, что хоть корпорация IBM и инвестирует колоссальные средства на исследовательские работы, и получает ежегодно сотни патентов, она по определению не имеет право на экстремизм. С давних времен известно, что IBM проявляет интерес к некоему сегменту рынка, если его объем не менее миллиарда долларов. Вывод: раз IBM положила свой взгляд на ESB, значит, эта технология перестала быть экстремальной. На основании личной беседы с Джейсоном Вейсером, который сейчас является директором всего направления «Web-службы для интеграции приложений и программное обеспечение промежуточного слоя», и участия в круглом столе, посвященном Web-службам, у меня сложилось впечатление, что в IBM в этом направлении пока реально сделано не слишком много. Однако в корпорации явно сложилось понимание значимости ESB и возможности реализации с использованием опыта создания программного обеспечения промежуточного слоя, основанного на обмене сообщениями (Message Oriented Middleware, MOM). С учетом потенциала IBM до реализации этих идей остался всего лишь один шаг.
Во-вторых, в середине мая синхронно поступила еще одна неожиданная весть — на этот раз с другого фронта, представленного BEA Systems, которая является для IBM конкурентом «номер один» по части создания средств для корпоративных платформ. В актуальном интервью, опубликованном в майском номере еженедельника InfoWorld, ведущий специалист BEA Адам Босуорт рассказал о том, что и в его компании тоже намереваются реализовать Services Oriented Architectures средствами Enterprise Service Bus. Здесь, как и в Sonic, предполагается использовать механизмы управления очередями MQ или JMS на базе Java для обеспечения маршрутизации сообщений. Неожиданность этого сообщения для меня лично заключается в том, что в феврале в Орландо мне довелось брать интервью у Адама Босуорта, которое опубликовано в мартовском номере «Открытых Систем». Однако тогда, он ни словом не упомянул ESB; более того, в нашей беседе я сам рассказывал ему о разработках Sonic и ESB. (Не думаю, что мой рассказ повлиял на направление мыслей Адама, скорее, это совпадение.)
Тот факт, что два лидера в области программного обеспечения промежуточного слоя одновременно обратились к одной и той же технологии для реализации корпоративных систем нового поколения, говорит о многом.
Наблюдение третье
Появление и быстрое принятие SOA и ESB — разумеется, не случайное открытие, а следствие необходимости в решении проблемы сложности современных корпоративных систем. Именно о сложности и путях ее преодоления говорили мои собеседники. Но при этом в разговорах обнаружилась еще одна поразительная общность. В системности своего мышления они поднялись над средним инженерным уровнем, они способны увидеть проблему в целом, а не состоящей из частностей. Но, чему не могу не поразиться, они исповедуют довольно ограниченное, я бы сказал, доморощенное представление о системах и системном подходе. Им совершенно неведомы такие научные направления как Общая теория систем и кибернетика просто и кибернетика второго порядка. О, они не знакомы с работами Норберта Винера и Людвига фон Берталанффи, поэтому и в буквальном смысле приходится заново открывать Америку. Слабое знакомство с фундаментальными основами вычислительных систем характерно для многих специалистов даже самого высокого ранга: на одной из недавних конференций вице-президент очень крупной корпорации довольно долго рассуждал о переходе от данных к информации, но не смог ответить на вопрос, чем же данные отличаются от информации, оказавшись не в состоянии дать определение тому и другому.
Наблюдение второе
Ряд занятных совпадений можно продолжить. За синхронностью обращения компаний IBM и BEA к теме ESB обнаруживается много общего, причем не только с технической, но с человеческой точки зрения. Нельзя не поразиться тому, что проповедники идеи ESB Джейсон Вейсер (IBM) и Адам Босуорт (BEA) тоже имеют между собой много общего. Формально они пришли на свои нынешние должности, уйдя из Microsoft, где занимали достаточно высокие посты. Босуорт сделал это примерно два года назад, Вейсер — в начале нынешнего года. Там Вейсер отвечал в Microsoft за направление .NET, а Босуорт — за XML. Не знаю о причинах, которыми руководствовался первый, однако известно, что Адама к уходу побудило разногласие, вызванное отношением к технологиям Java.
Далее — самое интересное. SOA и ESB можно представить не столько технологиями, сколько новой системной философией. Возможно, не случайно, что между Джейсоном и Адамом, которые ответственны в своих компаниях за продвижение идей SOA и ESB, обнаруживается общность человеческих качеств. Они не несут на себе печати «программистского» мышления и не говорят на том, увы, распространенном птичьем языке, который наполовину состоит из специальных терминов. Оба они вполне в состоянии выйти на более высокий уровень абстракции, чему способствует их академическое базовое образование и системный стиль мышления. Стоит обратить внимание на то, что Джейсон в свое время получил степень доктора философии по физике, а Адам в прошлом был историком, специализировался на экономической истории. Однако при этом оба они — настоящие технические «гики». Для работы на их уровне требуется сочетание общего образования и специальных знаний.
Выводы на основании наблюдений
Ускорение темпов переводит востребованные технологии из разряда экстремальных в основные за считанные месяцы. Сложность современных искусственных систем с неизбежностью приближается к сложности живых и социальных систем. Это уже не фантастика, а «реальность, данная нам в ощущениях». Уже сейчас для работы с ними востребованы специалисты, сочетающие профессиональные знания с широтой эрудиции.
