Simple Ray-Tracing

Написал для разминки простую демку рей-трейсинга.

В сцене 40 треугольников, включая "солнце". В пиксельном шейдере брутфорсом ищется пересечение для закастованных лучей. Потом строится второй луч по направлению к солнцу и ищется пересечение с любым блокером - получается тень. Геометрия трансформируется в world space в compute-шейдере перед проходом рейтрейсинга.

На моей старенькой ATI занимает около 3-4 мс в разрешении 512x512.

AdBlock

У меня в Хроме стоит Adblock Plus, и я всё чаще стал замечать, как на различных сайтах вывешиваются жалобы с просьбой отключить эту штуковину. Видимо, статистика кликов по баннерам серьёзно упала, раз многие стали плакать крокодильими слезами. "Внезапно" на 3DNews появилась аналогичная жалоба, значит их тоже прижало. К счастью (а для кого-то к несчастью), окно браузера - это не зомбоящик, где рекламодатели могут втюхивать рекламу с выкрученным на максимум звуком, всё режется также просто как и добавляется. Что интересно, так это посмотреть чем эта война закончится:

1. Сайт вынудит меня добавить их в список исключений
2. Заставят искать другой похожий ресурс
3. Найдут иной способ монетизации
4. Будут показывать рекламу только домохозяйкам, которые не слышали про баннерорезки
5. Загнутся

Мне кажется, что создатели всяких блокировщиков могут озолотиться, добавляя сайт в список исключений за вознаграждение от его владельцев или рекламодателей. Хотя Яндекс например рассматривает это как шантаж... Ничего личного, но смотреть на назойливые баннеры уже надоело. Попробуйте заставить, а мы посмотрим :)

Windows 10 is a flop

Поставил на виртуалку Windows 10 Build 10240. Немного поюзал, запустил новый MS Edge, метро-приложения, магазин...

Убила новая морда у окошек - выглядит вырвиглазно, потеряна какая-то строгость и чёткость UI, которая была в Windows XP/7. Всё какое-то новомодное и неуклюжее. Разнобой в интерфейсах, начиная от меню Пуск, продолжаясь в Проводнике и Панели управления и кончая метро-приложеними, просто поражает. Это какая-то сборная солянка из MFC, .NET и XAML, части которой делали разные отделы внутри корпорации и в разное время, а потом всё это собрали в один билд и назвали Windows 10. Что-то сломалось внутри Microsoft, и недавние перестановки в топ-менеджменте это только подтверждают. В общем желания ставить новую Виндоуз основной ОС не возникает, по крайней мере до широкого распространения DirectX 12 в играх.

P. S. Браузер Edge действительно неплохо оптимизирован, например на старом ноутбуке с Intel Core M фильмы с video.mail.ru в нём воспроизводятся плавнее, чем в Chrome.

Dynamic BVH

Первая рабочая реализация BVH дерева для skinned моделей:

Структура дерева предрассчитывается и размещается в нескольких GPU-буферах. Меш модели скинится, и описывающие объёмы дерева рассчитываются динамически в compute shader-e под геометрию меша.

Skinned модель и её BVH

Простой линейный алгоритм, легко ложащийся в real-time на GPU. Пока что это пробная реализация, имеющая недостатки: структура дерева далека от оптимальной (до близкой к оптимальной нужно много допиливать), каждый меш в модели строит своё дерево отдельно (а нужно хотя бы одно дерево на всю модель).

Трассировка отдельного луча на CPU

Кроме рекурсивной трассировки, я набросал на CPU итеративную версию алгоритма, т. к. DX11-шейдеры не поддерживают рекурсию. Итеративная версия использует std::stack, и практически аналогична по смыслу рекурсивной. На GPU такой стэк можно реализовать в виде фиксированного массива в шейдере (SM 4.0 indexable temp) и индекса в этом массиве. Вероятно, возможны другие варианты итеративного алгоритма, это станет предметом рассмотрения в будущем. 

Также у меня появились мысли, что трассировку можно разделить на два этапа: на первом мы составляем список листьев, которые пересекает луч, а на втором этапе проходим по всем найденным листьям и выполняем тест пересечения луча и треугольника. Это упростит шейдеры каждого из этапов, т. к. бранчинг в них работать не будет и не даст возможности отделить вычисления пересечения с нодами от вычислений пересечения с треугольниками.

Pixar Releases Free Non-Commercial RenderMan

RenderMan

Закон Амдала

При чтении IT ресурсов наткнулся на так называемый Закон Амдала. Он описывался ещё на заре появления многоядерных процессоров в десктопных конфигурациях, например здесь:

Программное обеспечение многоядерных систем

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

Недавно на 3Dnews появилась любопытная статья:

Эксперимент: 12-ядерный процессор в десктопе, 

которая в полной мере подтверждает график, приведённый ещё в статье 2006 года. Т. е. за 10 лет лечебная пилюля так и не была найдена.

Итак, что же мы имеем? 

1) Тактовая частота CPU застряла где-то в районе 4-5 ГГц;

2) Cкорость вычислений на отдельном ядре почти не растёт; 

3) Дальнейшее наращивание размеров кэшей разного уровня возможно, но заранее можно предсказать, что это даст какие-то проценты производительности, не более.

4) Со стороны ПО масса проблем. Даже последние игры с поддержкой DX11, грубо говоря - однопоточны, т. к.однопоточен сам DirectX. Даже видеокодеки x265 плохо масштабируются после определённого барьера.

5) 12-ядерный процессор в десктопных конфигурациях лишён смысла.

Неудивительно теперь, почему Intel медлит с выпуском мультиядерных процессоров в обычный пользовательский сегмент. Себестоимость производства таких кристаллов обойдётся дороже, а значит и стоковая стоимость будет выше. А когда пользователи увидят результаты тестов этих процессоров, они зададутся вопросом - за что они платят, покупая новую модель? Неудивительно, что Intel бросились в энергоэффективность - уменьшают нормы техпроцесса, поют на каждом шагу про TDP, добавляют AVX, AVX2, AVX 3 и ещё Бог знает какие инструкции... А правда тут одна - развитие процессоров заходит (или уже зашло) в тупик, и трудно сказать, как будет действовать Intel (и другие), и что их ждёт в будущем.

Fastest memcpy

В Сети полно тредов с обсуждением, можно ли обогнать memcpy из С lib. Из спортивного интереса я тоже решил поэкспериментировать с этим, зная что многие пытаются использовать SSE для копирования памяти через регистры xmm. Сделаем несколько допущений:

1) Большой кусок памяти (мегабайты).
2) Память выровненна по границе 16 байт.
3) Таргет CPU с обязательным наличием SSE2.
4) Соревнуемся с memcpy из VS 2012.

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

После различных попыток я в конце-концов остановился на комбинации SSE интринсиков _mm_stream_load_si128 / _mm_stream_si128 для копирования блоков памяти и _mm_prefetch(_MM_HINT_NTA) для указания процессору о том, что не нужно загрязнять кэш данными, так как они используются только короткое время. В x64 используются дополнительные регистры xmm8-xmm15, чтобы сократить кол-во блоков (итераций цикла) копирования. Тестовая программа состоит из 1000 циклов копирования кусков памяти размером 16Mb. Каждый цикл повторяется 10 раз чтобы удостовериться в правильности времени выполнения.

Результаты для процессора AMD FX-8320, release x86 и x64:

Судя по тому, что время отличается незначительно для x64, можно сделать вывод что CRT версия проигрывает из-за универсальности. Если бы не было 1000 циклов, эффект от ускорения был-бы несущественным. В x86 ускорение уже значительное, возможно Microsoft не удосужились оптимизировать runtime для архитектуры Bulldozer.

Кроме этого, я решил реализовать мультипоточную версию функции копирования и посмотреть, исполняется ли она эффективнее на многоядерном процессоре. Мультипоточная версия очень проста: она использует функции API Windows CreateThread/Semaphore, а также WaitForMultipleObjects для ожидания окончания работы множества потоков основным потоком. Это обеспечивает ясность над процессом распределения инструкций. Блок памяти делится на равные (по возможности) части и каждая часть копируется отдельным потоком.

Результаты для x64.
2 потока:

4 потока:

 8 потоков:

Как видно, использование самописного SSE и двух потоков в сумме даёт прирост в скорости около 40%. Дальнейшее увеличение кол-ва потоков практически не имеет смысла, т. к. прирост ни разу не линейный, а ядра становятся заняты. Уже после того, как код был написан и протестирован, выяснилось, что обычная память не допускает одновременного доступа к разным адресам, и что это умеет делать только Dual Port RAM.

Для чистоты эксперимента - x86 build, 8 потоков:

Максимальный прирост в скорости копирования - приблизительно двукратный. Да, x86 memcpy оказалась медленнее всего!

Наконец проверим загруженность ядер CPU копированием через xmm регистры.
2 потока:

 4 потока:

 8 потоков:

Масштабирование идеальное.
Выводы:

1) Обогнать memcpy из MSVCR (на AMD) можно.
2) В общем случае многопоточное копирование всё же имеет смысл.
3) Задействование большого кол-во ядер (> 2-4) бессмысленно, из-за того что память не допускает одновременного доступа к разным ядресам.

Update.

Результаты на Core i7-4790:

Результаты на Core i7-3770: