И ни слова о математике, об алгоритмах. Все настолько супер-секретно? Мы на Хабре или где?
Сейчас мы находимся в процессе оформления патента, соответсвенно не имеем права публиковать какие-либо описания алгоритма, нам просто откажут в патенте, если такие публикации найдутся. Пока рано раскрывать все карты, да и данная статься рассчитана больше на пользователей CAD, чем на программистов.
любая современная CAD-система будет использовать процессор где-то на 15%
Этот момент тоже остался нераскрытым для тех, кто на занимается непосредственно CAD. Почему так? Что, никто из основных вендоров до сих пор не озаботился распараллелеить решение СЛАУ? Либо ваше утверждение не совсем верно, либо проблема не столь актуальна в реальной работе.
Вы правы, в сухом остатке мы разработали параллелизуемый алгоритм быстрого решения СЛАУ специфичной для параметрического CAD. Хотя помимо этого для увеличения эффективности мы экспериментируем с различными уравнениями и типами геометрий.
Достоверность утверждения про загрузку процессора на 15% легко проверить самостоятельно, запустив любой CAD.
На самом деле, легко понять откуда берутся эти 15%. Если у вас 4-ядерный процессор Core i7, который с учётом hyper-threading имеет 8 логических процессоров, а солвер работает только в одном потоке (т.е. на одном из этих логических процессоров), то и получаем 12.5% загрузки процессора (100% / 8). Что-то ещё берёт сама CAD-программа, что-то берёт сама Windows – в результате набегает 15-20%. Если же ваш компьютер гораздо лучше – скажем, имеет два процессора Xeon с 12 физическими ядрами (и 24 логическими процессорами) каждый — то загрузка вашей машины будет ещё в шесть раз хуже, т.е. 2-3%.
Актуальна ли эта проблема? И если она актуальна, то почему так происходит? Ответы на эти вопросы могут занять еще одну большую статью, попробую ответить вкратце.
Для начала следует заметить, что решение СЛАУ в общем виде, достаточно сложная (O(n^3)) задача. Стандартные алгоритмы линейной алгебры очень плохо поддаются распараллеливанию.
Естественно производители CAD стараются ускорить расчет. Часто они как могут упрощают задачу, стараясь тем или иным способом отыскивать переменные, которые можно зафиксировать. Однако, как показывают наши примеры, это иногда приводит к крайне неустойчивому поведению (см. пример 4).
Мы заходим с другой стороны. Дело в том, что параметрические ограничения, как правило, применяются к примитивам попарно, первый примитив связан со вторым, второй с третьим и т.д. В результате получается система уравнений с малым количеством значимых переменных для каждого уравнения. У нас может быть ~10^5 уравнений и ~10^6 переменных, но в каждом отдельном уравнении будет участвовать всего 5-8 переменных. То есть матрица СЛАУ будет сильно разрежена. Мы нашли способ использовать эту особенность (что само по себе далеко не тривиально) – наш алгоритм позволяет не обращать всю огромную матрицу, а работать только с маленькими матрицами, и, кроме того, эта работа в значительной степени происходит параллельно.
Почему до этого додумались мы – маленький стартап, а не они – огромные межнациональные корпорации? Во-первых, возможно, мы просто талантливее, почему бы нет? Но есть и второй момент – крупные фирмы, создающие дорогие инженерные программы для профессионалов очень инерционны. Я хорошо знаком с этой ситуацией, до CAD я работал над другим типом инженерных программ – там то же самое. Производители не могут решиться на принципиальные изменения. Они живут по принципу «Работает? Не трогай!» и «Хорошее – враг лучшего», к этому их подталкивают пользователи, которым не хочется переучиваться и привыкать к новому поведению программы. Производители боятся, что резкое изменение программы приведет к разрыву многих контрактов и многомиллионным потерям. Может быть нововведение окажется полезным и, наоборот, программа привлечет много новых пользователей, но риск слишком высок. Каждая следующая версия мало отличается от предыдущей, большинство ресурсов уходят на поддержку и исправление багов, исследованиям уделяется очень мало внимания. Если срочно нужна новая функция, проще поглотить какого-нибудь мелкого производителя и прилепить его программу к основному продукту. За 20-30 лет изначально неплохой продукт превращается в неповоротливого монстра, мысленно живущего еще в 80х – 90х. Например, сейчас в API AutoCAD имеется 4 разных объектных моделей для примитивов. Они содержат одни и те же данные, которые просто унаследовались от разных команд и теперь приходится заботится об их соответствии.
Рано или поздно наступает такой момент, когда новая технологическая среда позволяет применять принципиально иные подходы, но инерционность старых массивных производителей не позволяет воспользоваться этим. Так маленький стартап способен победить многомиллионную корпорацию.
Действительно, в данном случае мы старались, для начала, сделать более наглядные примеры. Постараюсь представить в следующих материалах численные характеристики.
Касательно изменения параметра размерности, то все равно для начала нужно собрать схему, а у SolidWorks не получилось это на первых двух примерах, для остальных программ можно будет сделать такое сравнение к следующему материалу.
Сейчас мы находимся в процессе оформления патента, соответсвенно не имеем права публиковать какие-либо описания алгоритма, нам просто откажут в патенте, если такие публикации найдутся. Пока рано раскрывать все карты, да и данная статься рассчитана больше на пользователей CAD, чем на программистов.
Вы правы, в сухом остатке мы разработали параллелизуемый алгоритм быстрого решения СЛАУ специфичной для параметрического CAD. Хотя помимо этого для увеличения эффективности мы экспериментируем с различными уравнениями и типами геометрий.
Достоверность утверждения про загрузку процессора на 15% легко проверить самостоятельно, запустив любой CAD.
На самом деле, легко понять откуда берутся эти 15%. Если у вас 4-ядерный процессор Core i7, который с учётом hyper-threading имеет 8 логических процессоров, а солвер работает только в одном потоке (т.е. на одном из этих логических процессоров), то и получаем 12.5% загрузки процессора (100% / 8). Что-то ещё берёт сама CAD-программа, что-то берёт сама Windows – в результате набегает 15-20%. Если же ваш компьютер гораздо лучше – скажем, имеет два процессора Xeon с 12 физическими ядрами (и 24 логическими процессорами) каждый — то загрузка вашей машины будет ещё в шесть раз хуже, т.е. 2-3%.
Актуальна ли эта проблема? И если она актуальна, то почему так происходит? Ответы на эти вопросы могут занять еще одну большую статью, попробую ответить вкратце.
Для начала следует заметить, что решение СЛАУ в общем виде, достаточно сложная (O(n^3)) задача. Стандартные алгоритмы линейной алгебры очень плохо поддаются распараллеливанию.
Естественно производители CAD стараются ускорить расчет. Часто они как могут упрощают задачу, стараясь тем или иным способом отыскивать переменные, которые можно зафиксировать. Однако, как показывают наши примеры, это иногда приводит к крайне неустойчивому поведению (см. пример 4).
Мы заходим с другой стороны. Дело в том, что параметрические ограничения, как правило, применяются к примитивам попарно, первый примитив связан со вторым, второй с третьим и т.д. В результате получается система уравнений с малым количеством значимых переменных для каждого уравнения. У нас может быть ~10^5 уравнений и ~10^6 переменных, но в каждом отдельном уравнении будет участвовать всего 5-8 переменных. То есть матрица СЛАУ будет сильно разрежена. Мы нашли способ использовать эту особенность (что само по себе далеко не тривиально) – наш алгоритм позволяет не обращать всю огромную матрицу, а работать только с маленькими матрицами, и, кроме того, эта работа в значительной степени происходит параллельно.
Почему до этого додумались мы – маленький стартап, а не они – огромные межнациональные корпорации? Во-первых, возможно, мы просто талантливее, почему бы нет? Но есть и второй момент – крупные фирмы, создающие дорогие инженерные программы для профессионалов очень инерционны. Я хорошо знаком с этой ситуацией, до CAD я работал над другим типом инженерных программ – там то же самое. Производители не могут решиться на принципиальные изменения. Они живут по принципу «Работает? Не трогай!» и «Хорошее – враг лучшего», к этому их подталкивают пользователи, которым не хочется переучиваться и привыкать к новому поведению программы. Производители боятся, что резкое изменение программы приведет к разрыву многих контрактов и многомиллионным потерям. Может быть нововведение окажется полезным и, наоборот, программа привлечет много новых пользователей, но риск слишком высок. Каждая следующая версия мало отличается от предыдущей, большинство ресурсов уходят на поддержку и исправление багов, исследованиям уделяется очень мало внимания. Если срочно нужна новая функция, проще поглотить какого-нибудь мелкого производителя и прилепить его программу к основному продукту. За 20-30 лет изначально неплохой продукт превращается в неповоротливого монстра, мысленно живущего еще в 80х – 90х. Например, сейчас в API AutoCAD имеется 4 разных объектных моделей для примитивов. Они содержат одни и те же данные, которые просто унаследовались от разных команд и теперь приходится заботится об их соответствии.
Рано или поздно наступает такой момент, когда новая технологическая среда позволяет применять принципиально иные подходы, но инерционность старых массивных производителей не позволяет воспользоваться этим. Так маленький стартап способен победить многомиллионную корпорацию.
Это если коротко.
Касательно изменения параметра размерности, то все равно для начала нужно собрать схему, а у SolidWorks не получилось это на первых двух примерах, для остальных программ можно будет сделать такое сравнение к следующему материалу.