Высокопроизводительные парал. вычисления на кластерных системах. Воеводин (2005) (1186026), страница 37
Текст из файла (страница 37)
Примерами исследуемого параметра могут быть давление, температура, плотность ит.д. Второй рассматриваемый здесь тип данных для сжатия – непосредственно сами трехмерные скалярные данные, заданные на тетраэдрической сетке. К этому типу данных относятся результаты математического моделирования трехмерных физических задач, результаты натурныхэкспериментов и т.д.При визуализации изоповерхностей трехмерных скалярных данных большого объема нет необходимости (а иногда и возможности)использовать данные полностью с той же точностью, с которой онибыли получены.
Слишком подробные пространственные распределения, получаемые с помощью современных компьютерных систем, вопервых, слишком велики по объему, а, во-вторых, во многом избыточны для их использования в системах визуализации. Поэтому возникаетзадача - обработать поверхность каким-либо алгоритмом сжатия, чтобы уменьшить объем и избыточность данных, но сохранить их приемлемый вид.Сжатие без потерь не решает рассматриваемую проблему визуализации большого объема данных, поскольку оно фактически не умень182шает размер самих данных, а только уменьшает объем, необходимыйдля их хранения. Сжатие без потерь используется в случаях, когда необходимо полностью сохранить исходные данные, и проблему избыточности данных оно не решает.
Таким образом, для целей визуализации необходимо использовать алгоритм сжатия с потерями.Существует еще одна важная проблема обработки рассматриваемых данных. Объем данных может быть настолько большим, что их нетолько нельзя визуализировать, то и поместить в память обычногокомпьютера. Таким образом, сжать подобные данные можно только намногопроцессорных вычислительных системах с распределенной памятью.Как показывает практика, однопроцессорная обработка трехмерных скалярных данных (в отличие от обработки поверхностей) занимает существенное время.
Указанная проблема является еще одной причиной, по которой для сжатия подобных данных необходимо использовать МВС.Однопроцессорный алгоритм сжатия поверхностейНаиболее распространенным и удобным способом задания поверхности является представление ее в виде триангуляции точек в пространстве. Поэтому именно на этот тип поверхностей и рассчитан используемый алгоритм сжатия с потерями. Общая схема работы алгоритма состоит в том, что на его вход поступает исходная поверхность,а на выходе получается новая поверхность как можно меньшего размера, которая, во-первых, занимает объем, допустимый для использования в системах визуализации, и, во-вторых, стремится аппроксимировать исходную поверхность с требуемой точностью. Алгоритм работает с любыми типами поверхностей: они могут задаваться неоднозначными функциями, иметь полости, не являться гладкими, иметь участкисамопересечения, быть несвязными и т.д.Основная идея алгоритма состоит в последовательном упрощениималых участков поверхности с сохранением требуемой точности.
Приэтом проверяется, чтобы получаемый участок новой поверхности оставался на допустимом расстоянии от соответствующего участка исходной поверхности. Требуемая точность передается алгоритму в видеабсолютной ошибки аппроксимации, с которой новая поверхностьдолжна приближать исходную. После каждого упрощения участка поверхности количество точек и треугольников этого участка уменьшается, за счет чего и выполняется сжатие. Последовательное упрощениевсевозможных участков поверхности (удаление избыточности) выпол183няется до тех пор, пока выполняется условие соблюдения требуемойточности.
В процессе модификации поверхности алгоритм также следит за сохранением типа топологии каждого обрабатываемого участкаповерхности.Задача достижения требуемого объема данных в пределах требуемой точности в общем случае может не иметь решения. Чтобы в любомслучае получить какое-либо решение, которое можно визуализировать,в алгоритме поставлен более высокий приоритет именно достижениютребуемого объема. Если в пределах требуемой точности не удаетсядостичь требуемого объема, то параметр максимально допустимойошибки начинает постепенно увеличиваться.Тестирование алгоритма показало, что наиболее высокие коэффициенты сжатия достигаются при сжатии поверхностей, имеющихбольшую площадь участков с малой кривизной и высокую плотностьточек (случаи с наибольшей избыточностью данных).
На рисунке можно видеть результат сжатия тестовой поверхности с некоторой высокойстепенью точности.До сжатияПосле сжатияПараллельный алгоритм сжатия поверхностейОбработку поверхностей большого объема эффективнее выполнять на многопроцессорных вычислительных системах. Распараллеливание используемого алгоритма не вызывает проблем, поскольку фактически он работает последовательно с различными малыми участками184поверхности. Каждый участок поверхности обрабатывается независимо от других участков, поэтому в основу многопроцессорной реализации алгоритма был положен метод геометрического параллелизма. Врезультате при параллельном сжатии исходная поверхность обрабатывается по частям на отдельных процессорах. В течение основного процесса сжатия никакого межпроцессорного взаимодействия не осуществляется.
Для обеспечения последующей связности обрабатываемыхчастей общие точки этих частей предварительно маркируются как неудаляемые. При упрощении малых участков поверхности никаких изменений с маркированными точками не производится. После сжатиявсе части поверхности собираются со всех процессоров и «сшиваются»по маркированным точкам. На окончательном этапе сжатия все «швы»обрабатываются последовательным алгоритмом с заниженным параметром максимально допустимой ошибки. Как показало тестированиеалгоритма, визуальное качество получаемой поверхности вблизи«швов» почти не уступает качеству результатов, получаемых при полной обработке этого же участка поверхности на однопроцессорнойсистеме. На рисунке показан результат сжатия тестовой поверхности,заданной на прямоугольной области (на правом рисунке – вид сверху).Сжатие производилось на 3-х процессорах с некоторой высокой степенью точности.Результат сжатия поверхности на 3-х процессорахПараллельный алгоритм сжатия трехмерных скалярныхданныхНа основе алгоритма сжатия поверхностей разработан алгоритмсжатия трехмерных скалярных данных, заданных на тетраэдрических185сетках.
Сжатие таких данных точно так же можно выполнять на многопроцессорных вычислительных системах. Ввиду гораздо большейобъемности и более сложной структуры трехмерных скалярных данных, время, требуемое на их сжатие, может в сотни раз превышатьвремя обработки их изоповерхностей. Поэтому, как уже было замеченоранее, использование МВС в данном случае играет очень важную роль.Основной идеей алгоритма сжатия данных, заданных на тетраэдрических сетках, является представление данных как множество точекв 4-х мерном евклидовом пространстве и последовательное упрощениемалых областей данных по аналогии с упрощением поверхностей.
Вданном подходе имеет место обращение с физическими значениямисеточной функции как с новой геометрической координатой. Для корректной работы данного способа с классическим расстоянием междуточками в 4-х мерном евклидовом пространстве необходимо предварительно нормализовать (перемасштабировать) значения сеточной функции.В целом, алгоритм для обработки трехмерных скалярных данных иалгоритм для обработки поверхностей отличаются только размерностью.
Немногочисленные отличия касаются, в основном, способа слежения за сохранением типа топологии.ЗаключениеРазработанные методы многопроцессорного сжатия позволяютсжимать исходные данные с любой заданной точностью. Применениеданных алгоритмов довольно актуально, поскольку сжатие данныхбольшого объема является необходимым ключом к возможности ихисследования в системах визуализации. Разработанные алгоритмы довольно универсальны, поскольку они способны обрабатывать широкийкласс исходных данных. Алгоритмы показали свою эффективность набольшом количестве результатов численного моделирования различных физических задач, а также на всевозможных тестовых данных.186ДИНАМИЧЕСКАЯ ВИЗУАЛИЗАЦИЯ ВЕКТОРНЫХПОЛЕЙ, ЗАДАННЫХ НА ТЕТРАЭДРИЧЕСКИХ СЕТКАХБОЛЬШОГО РАЗМЕРАИ.А.
НестеровИнститут математического моделирования РАН, МоскваВ.Г. ЧубченкоМосковский государственный инженерно-физический институтСтремительный рост производительности современных вычислительных систем определяет увеличение объемов данных сопровождающих процессе математического моделирования. Требования к точности расчетов приводят к необходимости использования сеток, содержащих 108-109 и более узлов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
