Эволюционное и революционное будущее геометрических 3D-ядер

Ядра и многоядерность

(Познакомиться подробнее c состоянием процессорной индустрии и прогнозами ее развития можно в многочисленных аналитических обзорах — например, в следующем: часть 1 и часть 2, или с их русскоязычным вариантом в блоге компании Интел: часть 1 и часть 2.)

Надо ли говорить, что фокус разработки вычислительно сложного ПО заметно сдвинулся. Теперь, чтобы нацеливаться на использование вычислительной техники недалекого будущего, необходимо разрабатывать масштабируемые параллельные алгоритмы — то есть такие, производительность которых увеличивается пропорционально увеличению количества процессоров или процессорных ядер. И для которых, в идеале, имеется возможность запуска не только на десктопах, но и на кластерных (суперкомпьютерных) системах.

К сожалению, далеко не все задачи современного мира (или вычислительной математики) можно эффективно распараллелить. Например, было бы странно привлекать десяток грузчиков для работы по перетаскиванию единственного мешка с картошкой. И, тем более, было бы странно привлекать двух женщин к рождению одного ребенка в надежде на то, что процесс пройдет существенно быстрее, чем за положенные 9 месяцев. Другое дело, если мешков — несколько сотен, или планируемых детей — больше одного. Параллелизм тогда поможет.

Реальные задачи повседневной жизни являются набором подзадач, часть из которых поддается распараллеливанию, а часть — нет. В этом случае итоговая эффективность определяется законом Амдала, декларирующим, что «потолок» коэффициента ускорения от распараллеливания определяется нераспараллеливаемой подзадачей. На практике это означает, что если, скажем, 20% времени некоего алгоритма тратится на последовательные вычисления, а остальные 80% отлично распараллеливаются, то на 4 процессорных ядрах можно ожидать ускорения не более, чем в 2.5 раза. Ну а на 16 ядрах — не более, чем в 4.

Каким образом всё это проецируется на геометрические ядра? Дело в том, что большинство наиболее трудоемких функций ядра представляет собой сложный набор десятков последовательно работающих и тесно связанных друг с другом алгоритмов. Поэтому, чтобы добиться заметного эффекта, необходимо для каждого из них реализовывать собственную параллельную версию. Грубо говоря, ситуация напоминает войну с пробками в российских мегаполисах — проблемы надо устранять аккуратно на каждом перекрестке, иначе bottleneck гарантирован. К сожалению, «устранять и улучшать» легко в предвыборных обещаниях, а в реальном городском окружении это сделать не так просто — ведь когда дороги проектировались их создатели не думали о буме автомобилизации, случившемся за последние 15 лет. Точно так же и при проектировании современных коммерческих геометрических ядер разработчики не думали о наступлении эры параллельных вычислений (подробнее см. статью Эвана Яреса о ACIS и CGM и заметку в блоге Spatial).

На сегодняшний день о потокобезопасности и поддержке параллельных вычислений заявляют передовики рынка — ACIS и Parasolid. Но о конкретных параметрах эффективности на сложных операциях (типа булевых или блендинга) маркетинговые материалы умалчивают. Если же критически посмотреть на приводимые в этих материалах тщательно подобранные примеры — которые просто идеальны для параллелизма — можно увидеть неплохое, но вовсе неидеальное ускорение. Также любопытна ситуация с ядром CGM — хотя разработчики прямо заявляют, что оно не является потокобезопасным, это не помешало им реализовать функцию для обработки булевых операций с помощью множества процессов операционной системы — когда в память фактически подгружается несколько копий ядра, и они взаимодействуют друг с другом на уровне пересылки сообщений, а не над общей памятью, как это делают потоки (см. видеоролик).

Что же касается PTC Granite One и Autodesk Shape Manager, то здесь информации мало (см. например, о Creo Parametric и о Autodesk Inventor) — скорее всего, это означает, что пока что в области многопоточности гордиться компаниям нечем.

И, наконец, о старте работ по расширению использования параллельных вычислений не так давно упоминали разработчики C3D — ядра, используемого в КОМПАС-3D.

Ядра в облаках

На первый взгляд, ответ тривиален. Ведь какая разница, где установлено ядро — на удаленном сервере или локальном десктопе. Предоставлять пользовательский интерфейс (через веб-клиент, средство виртуализации или посредством обычного «оконного» приложения ОС) — это задача САПР-оболочки, а не ядра. Но вопрос всё-таки в другом — готово ли ядро использовать все доступные в облаке вычислительные ресурсы и при этом мгновенно выдавать решение для задачи любой сложности? Ведь, действительно, одно дело, если «тормозит» локальный десктоп с установленным на нем родным десктопным приложением — это, хотя и неприятно, но простительно. И совсем другое — если на неопределенное время подвисает удаленный сервер, имеющий в распоряжении десятки процессоров — фрустрация пользователя будет обеспечена.

Современные геометрические ядра вряд ли готовы заявить о такой степени масштабируемости параллельных вычислений, чтобы декларировать умение мгновенно решать любую задачу. Но этот факт совсем не смущает компании Autodesk и Dassault Systemes. В этом году они выпустили на рынок облачные САПР — Inventor Fusion 360 на ядре Shape Manager (уже доступный всем желающим за разумные деньги) и SolidWorks Mechanical Conceptual, построенный, вероятно, на ядре CGM (и проходящий сейчас обкатку на десятке клиентов DS). Третьим, похоже, станет стартап Belmont Technology со своим пока секретным САПР и объявленным использованием ядра Parasolid.

Мы наш, мы новый мир построим

Мы уже приводили подробную технологическую информацию о геометрическом ядре RGK, разрабатываемом с 2011 по 2013 гг., (см. часть 1 и часть 2). Нескромно отмечу, что на сегодняшний день, если сравнить RGK по комплексу факторов со всеми геометрическими ядрами, можно констатировать, что оно, пожалуй, имеет наиболее продуманный алгоритмический фундамент и архитектуру (в том числе — потокобезопасность и расширенную поддержку многопоточных вычислений), широкий функционал и является своеобразным сочетанием лучших практик и методов, появившихся в геометрическом моделировании за последние 20 лет.

Тем не менее, если говорить о подлинно революционном подходе (с характерным сдвигом парадигмы и с присущими ему надеждами и разочарованиями самих революционеров), то на эту роль больше подходит ядро Gen6, разрабатывающееся калифорнийским стартапом TinkerCAD (сейчас — AirStone Labs) и являющегося основой одноименного облачного САПР TinkerCAD, недавно приобретенного компанией Autodesk.

Хотя TinkerCAD и его геометрическое ядро являются типичным нишевым решением (изначально продукт создавался как средство создания моделей для задач 3D печати) и не могут тягаться по функционалу с САПРом и геометрическими ядрами общего назначения, интерес представляют по крайней мере две реализованные в нем технологические идеи, позволяющие выполнять булевы операции в параллельном режиме на суперкомпьютерах с тысячами процессоров и обеспечивать при этом одновременную работу большого количества пользователей.

Первая — система управления процессами и процессорами на суперкомпьютере, в результате чего пользователь имеет возможность для трудоемких операций получить в свое распоряжении почти все имеющиеся в распоряжении ресурсы (процессоры) суперкомпьютера. Ведь, действительно, пользователи облачного САПР не запустят на выполнение трудоемкие операции одновременно (если, конечно, это не флеш-моб или DDoS-атака).

Вторая — использование объемного (воксельного) представления для твердотельного моделирования (хорошо известного из компьютерной графики) как альтернативу B-rep, использующемуся во всех остальных современных ядрах. Преимущество состоит в том, что воксельное представление позволяет эффективно распараллеливать булевы операции. Так что все они будут выполнены мгновенно.

Тем, кому интересны технологические аспекты, можно порекомендовать посмотреть эту презентацию (впрочем, речь там идет о некоей более ранней версии ядра — Gen4; и, вполне возможно, что в новой версии ядра Gen6 все эти идеи уже были модифицированы), ну а мы сразу перейдем к «воксельным» проблемам:

• Для обеспечения разумной точности требуется хранить огромные объемы данных — ведь неоптимизированный подход требует хранения O(N^3) вокселей, а в случае оптимизации (например, с использованием октантных деревьев) их число может быть уменьшено до O(N^2). Считая, что размер вокселя совпадает с необходимой точностью трехмерного тела eps, получаем, что для достижения относительной точности 10^-5 (т.е. 1 мм на 100 метров) необходимо хранить и оперировать несколькими сотнями гигабайт данных. Даже для современных суперкомпьютеров среднего размера это является непозволительной роскошью. (Для сравнения — геометрические ядра ACIS и Parasolid декларируют 10-11 порядков точности.)
• Отсутствие явных алгоритмов конвертации воксельного представления в B-rep и обратно. Ведь, создавая ядро общего назначения, будет необходимо интегрировать ядро с другими САПР и реализовывать функциональность экспорта/импорта для существующих моделей. Сюда же относится проблема идентификации и параметризации B-rep элементов модели.

А что, если существует альтернативный подход к хранению и обработке воксельного представления, позволяющий избавиться от «квадратичного» объема данных, сохранить свойство масштабируемости параллельных вычислений и сделать органичную конвертацию в B-rep? Cотрудники LEDAS Labs уверенно подтверждают — такая технология имеет право на существование и некоторое время уже интенсивно ими исследуется. Причем, по всей видимости, она окажется полезной не только для чисто «ядерных» целей — как средство трехмерного моделирования, но и для смежных задач, к которым относятся лечение геометрии, геометрическое сравнение моделей , сопряжение цифровой модели с приложениями инженерного анализа и многое другое.

Эволюция вместо революции

И в этом смысле в контексте обсуждения геометрических ядер интересен вопрос — можно ли вообразить эффективное эволюционное улучшение производительности? Или, другими словами, каковы шансы создания масштабируемых параллельных алгоритмов, интегрированных с существующим кодом ядра?

Теоретический фундамент для работы с B-rep структурами, NURBS, построением линии пересечения и другими операциями не только хорошо известен но и, можно сказать, является стандартным (см., например, работы Хоффманна, Хохмайера, NURBS Book и др). По сути, геометрические ядра отличаются друг от друга способом реализации, деталями алгоритмов (хотя именно в них, как известно, и скрывается дьявол), и тем, как эти операции составляются из многочисленных базовых функций — строительных кирпичей. Поэтому, если среди разнообразных вариантов реализаций удастся найти и сделать тот вариант, который дает неплохой стабильный результат на больших моделях, то это уже могло бы стать достижением, обеспечивающим заметные конкурентные преимущества и оправдывающим затраты на разработку альтернативной «параллельной» функции.

Кроме того, подобный подход привлекателен и по нескольким другим причинам — он обеспечивает лучшую согласованность результатов параллельной операции с ее последовательным вариантом и не требует реализации большинства вспомогательных базовых функций. Здесь показателен упоминавшийся опыт CGM — как сообщают разработчики, поддержку параллельных вычислений им удалось выполнить сравнительно небольшой командой и без обеспечения потокобезопасности.

Впрочем, маркетинговый материал о CATIA V62012 ничего не сообщает о конкретных цифрах, а лишь декларирует, что существуют некие сценарии, на которых было достигнуто некое ускорение. Но, надо сказать, специалисты из LEDAS Labs делают оптимистичный прогноз потенциалу этой (эволюционной) технологии — при правильной организации параллельных вычислений выигрыш для больших моделей может быть очень и очень заметным.

Кто победит?