Достичь ускорения за счёт многопоточности в САПР

Математическая модель физических тел

Перевод формул в числа

Что такое кэширование и что оно даёт

Практика показывает, что зачастую набор значений параметра, для которых вычисляется радиус-вектор, подчиняется некой закономерности или статистике. Именно на предположении о том, что значения параметра не являются произвольными, основан такой метод оптимизации, как кэширование данных.

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

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

Следующий пример иллюстрирует, как работает кэширование.

Затраты на вычисление

Перейдём к численным оценкам. Посчитаем, сколько потребуется выполнить арифметических операций, чтобы вычислить синус угла с заданной точностью, используя ряд Тэйлора. В качестве примера возьмём угол 30 градусов: для получения точного значения ½ до 15 знака (с машинной точностью) мне пришлось просуммировать 7 членов ряда:

В том случае, когда нужно посчитать значения при двух близких значениях параметра, можно укоротить ряд Тейлора. Насколько близких и насколько укоротить – это зависит от требуемой точности. Допустим, нас устраивает точность до восьмого знака. Для вычисления значения косинуса с такой точностью потребует суммировать ряд до восьмой степени. Оценки показывают, что для разницы углов π/50 (как со знаком плюс, так и минус) ряд Тейлора для синуса и косинуса можно укоротить до третьей и четвёртой степеней, соответственно. А потом используются формулы для вычисления синуса и косинуса суммы углов:

Рисунок 1. Точность аппроксимации функции многочленами разной степени

Понятно, что кэш сплайна будет отличаться от кэша дуги, что кэш поверхностей будет устроен иначе. Важен сам принцип.

Программная надстройка над аппаратным базисом

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

Оптимизируя алгоритмы для многопоточной среды, не следует полагаться на ускорение, которое бы достигалось только за счёт использования многоядерности. Во-первых, потому что не все задачи хорошо распараллеливаются. Во-вторых, следует учитывать, что потоками и аппаратными ресурсами, например, ядрами, управляет не прикладная программа и не геометрическое ядро, а операционная система. Сам тот факт, что работа программы зависит не только от труда её автора, указывает на необходимость оптимизации того кода, который исполняется внутри потока. В некотором смысле давно разработанные и оптимизированные «однопоточные» алгоритмы являются эталоном быстродействия для своих «многопоточных» модификаций.

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

Собственно, обеспечение работоспособности в многопоточной среде при сохранении эффективности «однопоточной» реализации и является одним из ноу-хау C3D Labs. При развитии в этом направлении приходится модифицировать архитектуру системы так, чтобы выполнялся ряд условий:

1. Обеспечивалась максимальная эффективность от использования многопоточности.
2. Сохранялась эффективность в однопоточном варианте.
3. Обеспечивалась максимальная совместимость кода.
4. Условия 1-3 распространялись на максимально возможное число операций.

Есть и другие условия, например, требование кроссплатформенности. Оно накладывает ограничение на используемые технические средства. Применение технологии OpenMP для оптимизации кода ядра C3D как раз позволило одновременно решить проблемы кроссплатформенности и совместимости.

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