¬аше окно в мир —јѕ–
 
Ќовости —татьи јвторы —обыти€ ¬акансии Ёнциклопеди€ –екламодател€м
—татьи

16 но€бр€ 2016

ƒостичь ускорени€ за счЄт многопоточности в —јѕ–

јлександр —пиваков

јлександр —пиваков

јвтор Ч математик-программист в компании C3D Labs.

ѕо мнению экспертов компании LEDAS, эта стать€ представл€ет собой образцовый технологически-попул€рный материал, который изложен образцовым же русским €зыком.

Ќедавно на страницах isicad по€вилась новость об оптимизации программного обеспечени€ C3D Labs под много€дерную архитектуру Intel. ¬полне веро€тно, что среди многоуважаемой аудитории портала найдутс€ читатели, дл€ которых не €вл€етс€ очевидной сложность постановки и решени€ задачи подобного рода. Ќиже € постараюсь рассказать о методах оптимизации вычислений в геометрическом €дре и дать ответ на вопрос Ц почему ускорение вычислений за счЄт многопоточности в области —јѕ– есть нетривиальна€ задача.

ћатематическа€ модель физических тел

Ќачну издалека, а именно с математической модели объектов трЄхмерного мира. Ѕольшинство €дер CAD-систем оперируют с граничным представлением. ¬ переводе на человеческий €зык это означает следующее: пространство делитс€ на две части Ц заполненную материалом и всЄ остальное. √раница этих двух частей представл€ет собой стыкующиес€ кусочки разных поверхностей так, чтобы между ними не было щелей. “о, как именно стыкуютс€ кусочки и кака€ часть заполнена материалом Ц называетс€ Ђтопологиейї. Ќо она не очень хорошо подходит дл€ иллюстрации многопоточности. ј вот описание поверхностиЕ Ўтука, вроде, проста€, пока не вступает в свои права вычислительна€ математика. ЅерЄтс€ (прошу прощени€ за столь вольный стиль изложени€) декартова система координат, и в ней задаютс€ функции радиус-вектора (x,y,z) в параметрической области (u,v). ¬ формулах x, y, z, u, v Ц это числа с плавающей точкой. ƒл€ указани€, какой кусочек поверхности брать, используютс€ кривые. — ними уже разнообразнее: кривые могут быть определены как в области определени€ поверхности u(t), v(t), так и в трЄхмерном пространстве (x,y,z). «десь t Ц тоже число с плавающей точкой, называетс€ Ђпараметром кривойї. —обственно, на кривых € и проиллюстрирую некоторые трудности, которые возникают, едва стоит зан€тьс€ написанием кода.

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

»так, вычислительна€ математика: страна чудес, где, например, сумма мен€етс€ от перестановки слагаемых. Ќо это довольно тонкие эффекты, к которым порой приходишь через гораздо более насущные задачи. ј именно Ц придумать способы подсчЄта радиус-вектора (u,v) при произвольных допустимых значени€х параметра t. —пособов много: аналитические или специальные функции дл€ каждой координаты, различные сплайны и так далее. ¬о всех способах есть ухищрени€, которые позвол€ют уменьшить потребное число арифметических операций, и за каждый из этих способов приходитс€ платить свою цену: или операций слишком много, или приходитс€ заниматьс€ поиском, или всЄ вместе. ѕричЄм, речь идЄт именно об арифметических операци€х, а не каких-то ещЄ, потому что большинство способов изобреталось в эпоху, когда в ходу были таблицы Ѕрадиса, логарифмические линейки и механические арифмометры. Ќужно ли говорить, что каждый знак после зап€той нужно было обосновывать (о, да, неустойчивость алгоритмов!), потому как они переводились в человеко-часы? Ќужно его обосновывать и теперь, потому что прогресс вычислительной техники позволил расширить круг решаемых задач, и р€д задач, которые некогда считались суперсложными, перешли в разр€д даже не рутинных, а вспомогательных. —оответственно, требовани€ к точности и быстродействию не стали менее актуальными. “очность недостаточна Ц результат будет практически неприменим. “очность избыточна Ц результат успеет устареть прежде, чем будет получен.

„то такое кэширование и что оно даЄт

«адача оптимизации вычислительного алгоритма формулируетс€ так: сократить количество необходимых операций, поскольку оно определ€ет врем€ вычислений. ƒл€ многих задач уже сформулированы эффективные вычислительные алгоритмы. “ем не менее, дл€ прикладных задач наибольшую ценность представл€ют не те алгоритмы, которые вход€т в библиотеки, а реализованные самосто€тельно, с учЄтом специфики применени€.

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

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

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

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

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

–ассмотрим самое прекрасное, что есть в двумерии, согласно ѕифагору Ц окружность. ¬сЄ просто: u(t) = cos(t), v(t) = sin(t) Ц единичный радиус, начало координат. ѕервым делом нужно Ђзагнатьї t в диапазон от 0 до 2π. ƒалее могут быть варианты, например, использовать формулы приведени€ (навешивать на синус и косинус знаки плюс и минус в зависимости от, скажем так, Ђобсто€тельствї), а считать синус-косинус в диапазоне вчетверо более коротком Ц до π/2. “еоремой ѕифагора пользоватьс€ не будем, потому что там всЄ равно придЄтс€ расписывать р€д “ейлора, но уже дл€ квадратного корн€. ћожно работать итерационным методом, кому что нравитс€.

ѕерейдЄм к численным оценкам. ѕосчитаем, сколько потребуетс€ выполнить арифметических операций, чтобы вычислить синус угла с заданной точностью, использу€ р€д “эйлора. ¬ качестве примера возьмЄм угол 30 градусов: дл€ получени€ точного значени€ ½ до 15 знака (с машинной точностью) мне пришлось просуммировать 7 членов р€да:

C3D многопоточность формулы

„етыре члена р€да дают Ђмусорї в 8 знаке, 3 члена Ц в шестом. Ёто соответствует максимальной степени, в которую возводитс€ параметр: 13, 7 и 5, соответственно. ≈сли считать по схеме √орнера и €вно использовать тот факт, что суммируютс€ только нечЄтные степени, то дл€ суммировани€ многочлена 7 степени потребуетс€ 8 операций:
C3D многопоточность формулы

» так каждый раз? ¬ общем случае Ц да. ј в частном? Ёто зависит от того, каков частный случай.

¬ том случае, когда нужно посчитать значени€ при двух близких значени€х параметра, можно укоротить р€д “ейлора. Ќасколько близких и насколько укоротить Ц это зависит от требуемой точности. ƒопустим, нас устраивает точность до восьмого знака. ƒл€ вычислени€ значени€ косинуса с такой точностью потребует суммировать р€д до восьмой степени. ќценки показывают, что дл€ разницы углов π/50 (как со знаком плюс, так и минус) р€д “ейлора дл€ синуса и косинуса можно укоротить до третьей и четвЄртой степеней, соответственно. ј потом используютс€ формулы дл€ вычислени€ синуса и косинуса суммы углов:

C3D многопоточность формулы

¬ этом примере хорошо видно, почему имеет смысл считать синус и косинус, а не пользоватьс€ теоремой ѕифагора: можно сохранить в кэше предыдущее значение параметра и значени€ синуса и косинуса угла, которые ему соответствуют. Ўесть операций на вычислени€ по формулам плюс 8 операций дл€ вычислени€ р€да, итого 14 против 16. —овсем небольшой выигрыш дл€ каждой последующей близкой точки, сокращение затрат от силы процентов на дес€ть. ≈сли бы не одно важное обсто€тельство.
C3D многопоточность рис 1

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

ќценка трудоЄмкости точного расчЄта была сделана так, будто была заранее известна степень аппроксимирующего многочлена. ƒл€ того, чтобы определить степень, следует вычисл€ть каждый член р€да по отдельности и сравнивать его со значением точности, чтобы при достижении порога завершить расчЄт. «атраты на вычисление всех членов р€да примерно соответствуют вычислению по схеме √орнера, но ведь члены р€да ещЄ нужно просуммировать. ¬ зависимости величины угла необходимое число членов р€да, которое определ€ет число операций, может варьироватьс€ в ту или иную сторону, но в рассматриваемом примере вместо 16 следует писать 24. » выигрыш становитс€ пор€дка сорока процентов: 14 против 24. Ёто уже кое-что!

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

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

— тех пор, как много€дерные процессоры стали даже не просто доступны, а начали восприниматьс€ как нечто само собой разумеющеес€, всЄ более актуальной стала задача написани€ такого кода, который позвол€л бы задействовать аппаратные средства максимально эффективно. ”скорение может быть достигнуто за счЄт одновременного выполнени€ разных расчЄтов на разных процессорах или €драх.

—амо по себе наличие нескольких €дер не обеспечивает ускорени€ вычислений, а лишь предоставл€ет дл€ этого аппаратную возможность. ћногопоточность Ц это всего лишь один из способов задействовать имеющиес€ аппаратные возможности. ѕотоки Ц это объекты €дра операционной системы, которые могут очень эффективно взаимодействовать между собой, использу€, грубо говор€, оперативную пам€ть. ¬ идеале дл€ корректной работы потоков нужно, чтобы они не использовали одни и те же участки пам€ти. ¬ случае геометрического €дра Ц одни и те же кэши.   сожалению, в случае граничного представлени€ геометрическа€ модель так устроена, что дл€ подавл€ющего большинства операций не гарантирует такого разделени€, если всЄ оставить в таком виде, как было в эпоху одно€дерных процессоров.

ќптимизиру€ алгоритмы дл€ многопоточной среды, не следует полагатьс€ на ускорение, которое бы достигалось только за счЄт использовани€ много€дерности. ¬о-первых, потому что не все задачи хорошо распараллеливаютс€. ¬о-вторых, следует учитывать, что потоками и аппаратными ресурсами, например, €драми, управл€ет не прикладна€ программа и не геометрическое €дро, а операционна€ система. —ам тот факт, что работа программы зависит не только от труда еЄ автора, указывает на необходимость оптимизации того кода, который исполн€етс€ внутри потока. ¬ некотором смысле давно разработанные и оптимизированные Ђоднопоточныеї алгоритмы €вл€ютс€ эталоном быстродействи€ дл€ своих Ђмногопоточныхї модификаций.

ѕока не встал вопрос о многопоточности, пожалуй, единственным фактором, который ограничивал использование кэшей, был объЄм доступной оперативной пам€ти. “ребование работы в многопоточной среде привело к ревизии архитектуры программных комплексов и практической реализации вычислительных алгоритмов.

—обственно, обеспечение работоспособности в многопоточной среде при сохранении эффективности Ђоднопоточнойї реализации и €вл€етс€ одним из ноу-хау C3D Labs. ѕри развитии в этом направлении приходитс€ модифицировать архитектуру системы так, чтобы выполн€лс€ р€д условий:

  1. ќбеспечивалась максимальна€ эффективность от использовани€ многопоточности.
  2. —охран€лась эффективность в однопоточном варианте.
  3. ќбеспечивалась максимальна€ совместимость кода.
  4. ”слови€ 1-3 распростран€лись на максимально возможное число операций.
–ешение первой задачи по сути означает поиск компромисса между безопасностью и эффективностью. Ћюбые проверки сто€т байтов пам€ти и тактов процессорного времени. Ёто сложна€ и интересна€ работа, но она уже принесла первые результаты.

≈сть и другие услови€, например, требование кроссплатформенности. ќно накладывает ограничение на используемые технические средства. ѕрименение технологии OpenMP дл€ оптимизации кода €дра C3D как раз позволило одновременно решить проблемы кроссплатформенности и совместимости.

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


„итайте также:


¬акансии:

јктуальное обсуждение

RSS-лента комментариев

ƒавид Ћевин
ƒавид Ћевин
ќт редактора: –оботизаци€ Ч шанс дл€ человека реализовать своЄ назначение
ѕроект ЂЌародное —јѕ–-интервьюї

—лучайна€ стать€:

isicad Top 10

—амые попул€рные материалы

   ‘орумы isicad:

isicad-2010 isicad-2008
isicad-2006 isicad-2004

ќ проекте

ѕриглашаем публиковать на сайте isicad.ru новости и пресс-релизы о новых решени€х и продуктах, о проводимых меропри€ти€х и другую информацию. јдрес дл€ корреспонденции - info@isicad.ru

ѕроект isicad нацелен на

  • укрепление контактов между разработчиками, поставщиками и потребител€ми промышленных решений в област€х PLM и ERP...
ѕодробнее

»нформаци€ дл€ рекламодателей


¬се права защищены. © 2004-2017 √руппа компаний «Ћ≈ƒј—»

ѕерепечатка материалов сайта допускаетс€ с согласи€ редакции, ссылка на isicad.ru об€зательна.
¬ы можете обратитьс€ к нам по адресу info@isicad.ru.