Эмуляция ткани с использованием структур массивов и Intel® Advanced Vector Extensions (Intel® AVX) с поддержкой 256-битных команд

Скачать статью и посетить домашнюю страницу AVX Cloth

Скачать статью SOA Cloth Simulation with 256-bit Intel® Advanced Vector Extensions (Intel® AVX) [Eng., PDF 582KB]
Домашняя страница AVX Cloth (исходный код, исполняемые файлы, видео)

 

Аннотация

В данной статье описывается программа, в которой при реализации сеточной симуляции ткани используются инструкции расширения Intel® Advanced Vector Extensions (Intel® AVX). Для максимизации параллелизма данных применяется модель данных «структура массивов»( SOA), что позволяет использовать 256-битные инструкции SIMD. Отдельные тканевые объекты перемежаются в памяти. Количество обрабатываемых данных удерживается на минимальном уровне с помощью алгоритма разрешения дистанций на базе ограничивающих связей (distance constraint-based solver). В конце каждого фрейма данные эмуляции эффективно перемещается с транспонированием (8х8) в вершинный буфер, представляющий собой массив структур (AOS), для рендеринга. Если сравнивать оптимизированную последовательную 128-битную версию и 256-битную версию, то производительность возрастает в соответствии с увеличением ширины данных SIMD.

Введение

Модель SIMD эффективнее всего работает в тех приложениях, где данные организованы в виде структуры массивов (SOA). Приложения, работающие с графикой и обработкой изображений, часто являются высокопараллельными и хорошо структурированными и обычно хорошо подходят для использования данной модели. Хорошо известный пример – простые системы частиц, в которых легко использовать формат данных SOA, что приводит к хорошей масштабируемости. С другой стороны, геометрические данные не всегда можно объединить в аккуратные структуры, что относится также и к процессу эмуляции ткани. Как и в большинстве физических процессов, эмуляция куска ткани далека от широкого параллелизма, поскольку все вершины воздействуют друг на друга по много раз за фрейм. Обычные подходы с форматом массива структур, такие как оптимизированные библиотеки классов 4D векторов, не могут эффективно использовать полную ширину 256-битных (8 чисел типа float) операций SIMD, доступных в расширении Intel AVX. Увеличение разрядности регистров SIMD требует других подходов. В этой статье описывается метод с использованием SOA, при котором эмуляция ткани демонстрирует хорошую производительность на операциях SIMD с увеличенной шириной данных.

 

Ткань формата SOA

Параллелизм данных увеличивается при использовании формата данных SOA в процессе эмуляции ткани. Поскольку команды Intel AVX могут параллельно работать над 8 числами float, то нашей задачей становится объединение вместе независимых участков ткани в группы по восемь и производить эмуляцию восьми участков за раз. Количество вершин и топологии для каждого члена группы из восьми должно быть одинаковым. Возможно, это ограничит применение данного метода, но для эмуляции ровной материи на большой картинке приложению должно понадобиться много объектов ткани. Создание многочисленных экземпляров одного и того же объекта является частым приёмом. Позднее для каждого куска ткани можно задать свои уникальные параметры, такие как длина покоя, жёсткость, сила трения, сила ветра, соприкасающиеся поверхности.

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

 

Алгоритм

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

Модели основанные на физике пружин и центров тяжести с прямым эйлеровым интегрированием ограничиваются слабыми пружинами, что приводит к растягиванию структуры и колебаниям, и следовательно, не подходит для симуляции ткани. Неявное интегрирование [Baraff and Witkin SIGGRAPH98] модифицированным методом сопряжённых градиентов позволяет использовать гораздо более жёсткие пружины. Однако при росте количества косвенных операндов работа таких приложений скорее ограничивается пропускной способностью памяти, а не эффективностью операций с плавающей точкой (FLOPS). Далее, если хранить все определители Якоби в разрежённых матрицах, то это приводит к увеличению объёма хранимых данных. Не будем забывать, что при использовании алгоритмов с SOA мы имеем восьмикратное увеличение количества данных, проходящих итерацию по многу раз за фрейм. Есть сильное желание хранить все часто используемые данные в кэше первого уровня процессора. Таким образом, реализации достаточно частой сетки, объём данных при этом методе начинает составлять проблему.

Для нашей программы мы написали очень простой решатель дистанций на базе ограничивающих связей (итеративная проекция позиций). Такие типы систем (T. Jakobsen [Gamasutra03], X. Provost [GI95]) очень легко разрабатывать и они часто используются в современных видеоиграх. В дополнение к существующим срединным решениям эмуляции ткани многие разработчики создают свои собственные реализации, заточенные под специфические требования своих проектов. Наш алгоритм обновляет позиции вершин и не требует большого объёма других данных. На высоком уровне алгоритм просто перебирает каждую ограничивающую связь и сдвигает конечные точки немного ближе к дистанции покоя между ними:
 

Repeat many times (8 to 32)
  For each constraint a,b endpoints
    v = b - a
    u = v/||v||
    e = (||v|| - restlength) * bias
    a = a + u*e
    b = b - u*e

 


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

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

 

 

 

 

 

 

Рис. 1: Сетка из ограничивающих связей ткани

 

 

Взаимодействие с окружением

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

 

 

 

В нашем примере локальный ветерок гуляет туда-сюда по сцене и при каждом проходе меняются его направление и скорость. Ветер является векторной функцией от положения в пространстве w(x,y,z). Он воздействует на каждую точку ткани пропорционально скалярному произведению относительной скорости ветра и нормали к поверхности. Движение ткани в каждой вершине претерпевает изменение вдоль нормали (lift). Мы также тестировали и прямое воздействие ветра, но, поскольку оно было однородным во всех сетях, то не добавляло картине никаких интересных эффектов. В данной реализации не используется никаких развитых аэродинамических моделей, например, эффект Бернулли, и ткань сама никак не воздействует на ветер.

 

 

Рис. 2: Динамика воздействия ветра

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

 

Архитектура и реализация системы

После сбора данных о ветре, столкновениях и других событиях, запускается физическая эмуляция – первый главный шаг процесса обработки. Затем производится рендеринг сеточной структуры. Данные о нормалях и позициях, координаты текстур в формате SOA перемещаются в вершинный буфер (формат AOS), пригодный для использования при прямом рендеринге Microsoft DirectX* (immediate mode). Поскольку при этом возникают преобразования матриц 8х8, то мы на данном этапе можем задействовать инструкции Intel AVX. В итоговом буфере вершин всё так же перемежаются 8 секций ткани (при гранулярности на уровне вершин, а не 32-битных значений с плавающей точкой), поэтому рендеринг выполняется пакетами по 8. При желании можно переписать преобразование (SOA в AOS) и использовать 8 отдельных целевых указателей.
 

Рис. 3: Архитектура системы эмуляции ткани


Intel AVX обладает очень большими возможностями, а ядро процессора способно обработать большой объём виртуальной ткани. По этой причине рендеринг имеет все возможности стать самым узким местом. Используя DirectX* 11 и некоторые базовые библиотеки, мы реализовали однопроходный рендеринг без поддержки теней, что позволило уменьшить издержки. Если использовать более развитый рендеринг, то имеет смысл отвести для него отдельный поток.

Остальной код работает абсолютно независимо. Мы не применяли типичный файл заголовков библиотеки 4D векторов в стиле Intel® SSE, поскольку основной формат в ней был бы массив структур, и мы не смогли бы полностью задействовать возможности Intel AVX. Вместо этого мы успешно использовали шаблоны SOA классов высокого уровня С++, содержащие основные математические типы, такие как 3D вектора – класс vec3<__m256>. Такой метод программирования позволяет сохранять исходный код максимально близким к структуре алгоритма, делает его таким же чистым и простым, как и последовательная версия. В некоторых местах потребовалось ручное вмешательство с помощью встраиваемых функций, что позволило устранить утечку регистров и создать оптимальный ассемблерный код.

Цикл решателя является самым тонким местом приложения. Решатель перебирает ограничивающие условия, которые по количеству почти в 6 раз превышают количество вершин. К тому же этот цикл повторяется по несколько раз (от 8 до 32), чтобы ткань не казалась слишком растяжимой, малоподвижной или мало отзывчивой.

Хотя каждая ограничивающая привязка должна обновляться по несколько раз, высокая точность при этом не нужна. Поэтому мы экономим некоторое время, не применяя метод Ньютона-Рапсона после вычисления приближённого квадратного корня (встраиваемая функция _mm[256]_rsqrt_ps()).

Эмуляция лучше всего работает в 64-разрядной версии, поскольку может использовать 16 регистров YMM. 32- разрядная версия показала более низкую производительность из-за утечки регистров, вызванной возможностью использовать только 8 регистров YMM.

При размере кэша первого уровня 32Кбайта, мы можем использовать по 4КБ на кусок ткани (или 1024 значения типа float при 32-битной точности). Данные для каждой точки ткани включают в себя нормаль, новую позицию, старую позицию, инверсную массу, и скорость. Однако основной цикл работает только с массивом новых позиций и инверсных масс. Отметим, что необходима некоторая дополнительная память для хранения топологии/связок, которые являются одинаковыми для всех частей ткани. Таким образом, оставаясь в рамках кэша L1, мы можем использовать не более 200 вершин. При тестировании наилучшей производительности мы старались держаться этого уровня.

 

 

 

Анализ производительности

Решатель связей является основным узким местом эмуляции. Временные параметры выполнения его кода были замерены как в составе приложения, так и в тестовом окружении с целью определения, все ли пути кода были должным образом оптимизированы и обмерены. Вручную оптимизированные последовательные 128-битная версия Intel AVX и 256-битная Intel AVX тестировались на одном процессоре Интел с микроархитектурой с кодовым именем Sandy Bridge. Приложение является однопоточным. В приведённой ниже таблице указано, сколько в среднем требуется тактов процессора на обновление одной связи, а также полный фреймрейт приложения на данной сцене с наличием большого количества объектов ткани, составляющих в общем более 37000 вершин и около 193000 связей, которые решатель перебирает по 16 раз за фрейм.

 

 

 

 

 

ПоказательЕдиница отсчетаSIMD 4 (128 бит)SIMD 8 (256 бит)
Тактов процессора на обновление одной связи35.59.35.6
Скорость работы решателя1 (базисное значение)3.8X6.3X
FPS1862100
Общее увеличение скорости1 (базисное значение)3.4X5.6X


Результаты показывают вполне логичное ускорение работы при увеличении ширины SIMD данных. В ключевых расчётах решателя использование 256-битных регистров повысило производительность на 50% по сравнению с использованием 128-битных регистров, что привело к повышению общего показателя фреймов в секунду. Очевидно, что формат данных SOA позволяет более эффективно использовать возможности процессора в данном конкретном приложении.

 

 

 

 

Не все сетки имеют размер, позволяющий им вместиться в L1 кэш. К счастью, в микроархитектуре Sandy Bridge предусмотрен хороший аппаратный префетч. Дополнительные тесты эмуляции 8 больших кусков ткани из 25000 точек, требующих использования L2 кэша, показали время 6.5 такта на обновление связи – только на 16% медленнее. Отметим, что такие меши требуют гораздо большего количества итераций, чтобы ткань не казалась слишком растяжимой. Вместо плотных сеток обычно бывает более эффективно использовать разделяющие поверхности или другие виды плиток, позволяющие улучшить визуальные свойства ткани.

 

 

Как показывает работа приведённого здесь примера, одно ядро процессора с поддержкой Intel AVX обладает достаточной мощностью при операциях с плавающей точкой (FLOPS), чтобы обрабатывать дополнительные объёмы ткани, сохраняя при этом высокий показатель фреймов в секунду.

 

Заключение

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

 

Ссылки

  • D. Baraff, A. Witkin: "Large Steps in Cloth Simulation", SIGGRAPH 1998.
  • Kwang-Jin Choi, Hyeong-Seok Ko: "Stable but Responsive Cloth", SIGGRAPH 2002.
  • T. Jakobsen: "Advanced Character Physics", Gamasutra, January 21 2003.
  • H. Enqvist: "The Secrets Of Cloth Simulation In Alan Wake", Gamasutra, April 29, 2010.
  • X. Provot: "Deformation constraints in a mass-spring model to describe rigid cloth behavior", Graphics Interface 1995.
  • Intel® Advanced Vector Extensions (Intel® AVX): http://software.intel.com/ru-ru/avx/

Об авторе

Стэн Мелакс (Stan Melax) получил степени бакалавра и магистра компьютерных наук в университете Альберты в Канаде в начале 90-х. Основное время работал в игровой индустрии, включая такие компании, как BioWare, EA и Ageia. В настоящее время Стэн является специалистом по графическим программам в корпорации Интел, где он помогает разработчикам создавать более быстрый код и более качественные приложения.

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