Theoretical bases of mathematical apparatus of parallel computing realization in computer-aided design systems

Full Text

1. ВВЕДЕНИЕ

В современном мире аппаратная часть современных персональных компьютеров постоянно совершенствуется в части распараллеливания вычислительных процессов. Например, Ampere Altra Q80–33 является 80-ядерным серверным процессором на базе ARM. Все большей популярностью для реализации параллельных вычислений пользуются графические процессоры, оснащенные уже не сотнями, а тысячами ядер (например, видеокарта Nvidia RTX 3090 имеет 10496 ядер). Это приводит к тому, что имея достаточное количество средств и времени можно мобилизовать огромные вычислительные ресурсы даже в домашних условиях. Не говоря уже о том, что производство суперкомпьютеров уже стало серийным. Все это ставит новые требования к программному обеспечению, краеугольным камнем которого должны быть параллельные вычисления. Современные же программные продукты не всегда реализованы с поддержкой параллельных вычислений. Это приводит к частому простою вычислительных потоков и сводит их огромный вычислительный потенциал до возможностей одноядерного процессора. На данный момент, подобная картина знакома уже многим пользователям домашних операционных систем, не говоря уже о суперкомпьютерах. Она же характерна для всех без исключения систем твердотельного моделирования и автоматизированного проектирования, у которых лишь немногие операции реализованы с помощью параллельных вычислений. Учитывая темпы цифровизации всех современных отраслей промышленности, включающие построение цифровых двойников изделий и их сопровождение на всех этапах жизненного цикла, приводит к необходимости одномоментно оперировать огромными массивами информации. Уже не фантастикой, а реальностью становятся цифровые двойники целых заводов, содержащие до нескольких миллионов отдельных деталей. Таким образом, чтобы обеспечить потребности в цифровизации производственных циклов, необходима разработка новой концепции программного обеспечения, которая опиралась бы на математический аппарат, способный обеспечить реализацию параллельных вычислений на уровне геометрического ядра систем твердотельного моделирования и автоматизированного проектирования не только на этапе проектирования, но и на этапе сопровождения существования промышленных объектов на протяжении всего их жизненного цикла. А решение научной проблемы разработки математического аппарата параллельных вычислений является актуальной и весьма значимой научной задачей, которая создает предпосылки для формирования новых научных направлений в геометрическом и компьютерном моделировании объектов, процессов и явлений, а также создании высокопроизводительных программных продуктов на их основе.

2. СОВРЕМЕННОЕ СОСТОЯНИЕ ИССЛЕДОВАНИЙ ПО ДАННОЙ ПРОБЛЕМЕ

За последние десятилетия развития компьютерной техники активное распространение получили многоядерные процессоры, которые могут параллельно выполнять несколько вычислительных операций. Это обеспечивает современным компьютерным системам значительный прирост производительности и в значительной мере экономит энергопотребление центрального процессора, что привело к их массовому внедрению для эффективного решения многих научно-технических задач в различных отраслях человеческой деятельности [1–6]. Вместе с тем возникает проблема разработки программного обеспечения, способного в полной мере реализовать потенциал многоядерных процессоров за счет согласованного выполнения параллельных вычислений.

На текущий момент существует два основных подхода к реализации параллельных вычислений: распараллеливание по задачам (message passing) и распараллеливание по данным (data parallel). Распараллеливание по задачам подразумевает фрагментацию решаемой задачи на независимые подзадачи, каждую из которых можно решать отдельно. Одним из недостатков такого подхода является уникальность фрагментации каждой отдельной задачи. Кроме того, далеко не каждая задача может быть подвергнута фрагментации. Распараллеливание по данным является более универсальным подходом, не привязанным к решению конкретной задачи. Такой подход часто используется при решении задач численного моделирования, связанных с формирование многомерной сети точек, формирующих простые геометрические объекты. В математической физике такой подход к реализации параллельных вычислений получил название геометрический параллелизм [7–9].

Несмотря на большое количество исследований [10–15], одним из проблемных секторов внедрения многоядерных компьютерных систем остается компьютерная графика. К сожалению, существующие системы автоматизированного проектирования (САПР) и твердотельного моделирования не используют в полной мере многоядерные возможности современных процессоров. Например, на официальном сайте одного из флагманов САПР компании Autodesk имеется следующая информация: “Программы AutoCAD и AutoCAD for Mac поддерживают технологию многоядерных процессоров только в отдельных областях применения (2D-регенерация). Чтобы воспользоваться всеми преимуществами многоядерных процессоров, необходимо использовать многопоточное программное обеспечение. AutoCAD представляет собой приложение с однопотоковой обработкой”. В отечественных САПР многопоточность также реализована далеко не для всех операций геометрического моделирования. Например, основные многопоточные операции одного из лидеров среди отечественных производителей – геометрического ядра C3D включают: построение плоских проекций, расчет полигональных сеток, расчет массо-центровочных характеристик, операции конвертеров и некоторые другие. Для реализации многопоточности в ядре C3D используется технология OpenMP, которая реализует параллельные вычисления путем выделения ведущего (master) потока, формирующего набор ведомых потоков и распределяя задачи между ними. Таким образом, параллельные вычисления реализуются на программном уровне, а не за счет математического аппарата, что в значительной степени ограничивает их возможности. Одной из причин сложившейся ситуации является отсутствие полной поддержки параллельных вычислений на уровне геометрического ядра системы, ограниченного возможностями математического аппарата. Подобная же картина наблюдается в географических информационных системах и системах дистанционного зондирования Земли [16–19]. Исходя из вышеизложенного разработка математического аппарата геометрического моделирования, способного обеспечить параллельные вычисления на уровне геометрического ядра является актуальной и востребованной научной задачей.

Вообще, вычислительные алгоритмы компьютерной графики, основанные на методах конструктивного геометрического моделирования, прекрасно поддаются распараллеливанию вычислений. Например, в работе [20] приводится пример структуры алгоритма решения задачи Аполлония, допускающей распараллеливание вычислений и их конвейерную организацию, который относится к распараллеливанию по задачам и предусматривает согласованное и единовременное построение нескольких геометрических объектов. Однако, в процессе проектирования нет острой необходимости единовременного построения разных геометрических объектов. Проектировщик, использующий САПР для построения 3-мерной модели, не будет одновременно строить несколько окружностей, прямых или других геометрических объектов. Он будет строить их по очереди, применяя инструменты САПР. Другое дело, что при построении самих геометрических объектов можно и нужно использовать параллельные вычисления. Это приводит к необходимости разработки новой концепции разработки геометрического ядра САПР, основанного на эффективном использовании всех возможных подходов к реализации параллельных вычислений.

3. МАТЕМАТИЧЕСКИЙ АППАРАТ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

В качестве математического аппарата, способного обеспечить эффективную реализацию геометрического ядра САПР нового поколения, предлагается использовать точечное исчисление [21] исходя из следующих соображений. Базовым методом точечного исчисления является метод проецирования геометрического объекта на оси глобальной системы координат, в отличие от начертательной геометрии, в основу которой положен метод проецирования пространственных геометрических объектов на плоскости проекций. Такой подход позволяет переходить от символьных точечных уравнений к системе однотипных параметрических уравнений. Геометрическая интерпретация такого перехода представляет собой параллельное проецирование пространственного геометрического объекта на оси глобальной системы координат. Аналитически этот процесс описывается систематической заменой точек на соответствующие их координаты. Эта операция получила название покоординатного расчета. Вместе с тем покоординатный расчет целесообразно выполнять тогда, когда получено итоговое точечное уравнение моделируемого геометрического объекта, что значительно сокращает время необходимых вычислений. Геометрическое моделирование в точечном исчислении осуществляется на основе геометрической схемы – графического алгоритма построения геометрического объекта с последующим описанием в виде точечных уравнений и вычислительных алгоритмов на их основе. При этом каждой графической операции ставится в соответствие аналитическая операция. Это привело к разработке инструментов геометрического моделирования, инвариантных относительно параллельного проецирования, которые способны обеспечить покоординатный расчет точечных уравнений [22]. Например, определение отрезка прямой в 3-мерном пространстве благодаря инвариантным свойствам параметра точечного исчисления, которым является простое отношение трех точек прямой (рис. 1), выглядит следующим образом:

$M=\left(B-A\right)t+A\iff \left\{\begin{array}{l}x=\left(x_B-x_A\right)t+x_A\\ y=\left(y_B-y_A\right)t+y_A\\ z=\left(z_B-z_A\right)t+z_A\end{array}\right..$

Рис. 1. Геометрическая интерпретация покоординатного расчета для отрезка прямой в 3-мерном пространстве.

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

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

В общем виде точечное уравнение любого геометрического объекта можно представить в виде суммы произведений точек симплекса на функции от текущих параметров:

$M=\sum _{i=1}^n{A}_i{p}_i\iff \left\{\begin{array}{l}{x}_M=\sum _{i=1}^n{x}_{A_i}{p}_i\\ y_M=\sum _{i=1}^n{y}_{A_i}{p}_i\\ z_M=\sum _{i=1}^n{z}_{A_i}{p}_i\\ \mathrm{...}\end{array}\right.,$ (1)

где M – текущая точка, которая своим движением заполняет пространство, формируя геометрический объект; A_i – точки, определяющие исходный симплекс многомерного пространства; p_i – функции от текущих параметров (u, v, w, ...), которые обеспечивают движение текущей точки M; n – размерность пространства исходного симплекса.

Условием принадлежности текущей точки исходному симплексу является суммарное значение функций от текущих параметров равное 1: $\sum _{i=1}^n{p}_i=1$.

Как видно из (1), все параметрические уравнения системы, полученные на основе точечного уравнения, являются полностью однотипными. Меняются только координаты точек симплекса, которые относятся к исходным или промежуточным данным. В этом случае все точки в уравнении (1) по сути являются координатными векторами. Из этих соображений точечное исчисление можно считать особым видом векторного исчисления, способным индуцировать системы однотипных параметрических уравнений, обеспечивая в результате геометрического моделирования, так называемый, скрытый параллелизм. Тогда уравнение (1) будет представлено следующим образом:

$M=\sum _{i=1}^n\left(\begin{array}{c}{x}_{A_i}\\ y_{A_i}\\ z_{A_i}\\ \mathrm{...}\end{array}\right)p_i.$

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

$M=\sum _{i=1}^n{A}_i{p}_i\iff \left\{\begin{array}{l}{x}_M=\sum _{i=1}^n{x}_{A_i}{p}_i\text{ 1-й вычислительный поток}\\ y_M=\sum _{i=1}^n{y}_{A_i}{p}_i\text{ 2-й вычислительный поток}\\ z_M=\sum _{i=1}^n{z}_{A_i}{p}_i\text{ 3-й вычислительный поток}\\ \mathrm{...}\mathit{\text{n}}\text{-й вычислительный поток}\end{array}\right.$ (2)

Как видно из уравнения (2) параметрические уравнения системы являются полностью независимыми друг от друга и обеспечивают полную синхронизацию расчета геометрического объекта в целом, поскольку они одновременно начинаются и одновременно заканчиваются.

Следует отметить, что при определении метрических характеристик геометрических объектов с помощью метрического оператора может понадобиться ряд промежуточных вычислений, предусматривающих особый вид покоординатного расчета, который усложняет распараллеливание вычислений по данным. Эта особенность не является следствием использования точечного исчисления и относится ко всем современным САПР. Вместе с тем, доля таких вычислений несравненно мала и такие вычисления легко поддаются распараллеливанию по задачам.

В исследованиях [24] отмечалось, что выигрыш по времени вычислений не пропорционален числу ядер процессора. Это связано с невозможностью равномерного распределения работы по всем ядрам. Возможна и другая проблема, если загрузка ядер процессора достаточно равномерная, но скорость обмена данными низкая, то основная часть времени будет тратиться впустую на ожидание информации, необходимой для дальнейшей работы данного ядра процессора. В предложенном подходе к распараллеливанию вычислений путем покоординатного расчета все вычисления не просто проходят параллельно, чего можно было бы достичь с использованием обычных систем параметрических уравнений. Результатом покоординатного расчета точечного исчисления является система однотипных параметрических уравнений, в которых отличаются лишь соответствующие координаты точек, а все остальные функции от параметров остаются неизменными, что следует из уравнения (1). Это приводит к тому, что количество математических операций, необходимых для вычисления координат точек, является одинаковым, обеспечивает согласованное выполнение вычислений и минимизирует простой ядер. Таким образом, предложенный подход повышает общую производительность многоядерной системы за счет согласованного выполнения всех вычислительных операций.

4. МОДЕЛИРОВАНИЕ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ С УЧЕТОМ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

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

Исходя из этого рассмотрим пример моделирования кривых 2-го порядка в точечном исчислении. Вообще, за десятилетия развития точечного исчисления было получено множество параметризаций кривых линий и поверхностей на их основе, некоторые из которых приведены в работе [21]. Геометрическая схема конструирования кривой 2-го порядка, которая определяется с помощью инженерного дискриминанта $k=\frac{KC}{T_{1}C}$, представлена на рис. 2. В данном случае кривая является дугой обвода (т. е. имеет касательные в начальной и конечной точках) и проходит через 3 точки: А, К и В.

Рис. 2. Геометрическая схема конструирования кривой 2-го порядка.

Точечное уравнение такой кривой и соответствующая ему система точечных уравнений представлена ниже:

$\begin{array}{c}M=\left(A-C\right)\frac{k{\overline{u}}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+\left(B-C\right)\frac{k{u}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+C.\\ \Updownarrow \\ \left\{\begin{array}{l}{x}_M=\left(x_A-x_C\right)\frac{k{\overline{u}}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+\left(x_B-x_C\right)\frac{k{u}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+x_C\\ y_M=\left(y_A-y_C\right)\frac{k{\overline{u}}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+\left(y_B-y_C\right)\frac{k{u}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+y_C\\ z_M=\left(z_A-z_C\right)\frac{k{\overline{u}}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+\left(z_B-z_C\right)\frac{k{u}^2}{k{\left(1-2u\right)}^2+2\overline{u}u}+z_C\end{array}\right.,\end{array}$ (3)

где $0\le u\le 1$ – текущий параметр; $\overline{u}=1-u$ – дополнение соответствующего параметра до единицы.

В соответствии с [21], при k = 0.5 получим дугу параболы, при 0 < k < 0.5 – дугу гиперболы, а при 0.5 < k < 1 – дугу эллипса.

Рассмотрим другой пример моделирования дуги обвода 3-го порядка на основе конфигурации Дезарга [22] (рис. 3).

$M=\frac{A{\overline{u}}^3+B{u}^2\overline{u}+C{\overline{u}}^{2}u+D{u}^3}{2u^2-2u+1},$ (4)

где $0\le u\le 1$ – текущий параметр.

Рис. 3. Геометрическая схема моделирования дуги обвода на основе конфигурации Дезарга.

С учетом покоординатного расчета точечного уравнения (4) для трехмерного пространства получим систему однотипных параметрических уравнений для каждого из трех вычислительных потоков:

$\left\{\begin{array}{l}{x}_M=\frac{x_A{\overline{u}}^3+x_B{u}^2\overline{u}+x_C{\overline{u}}^{2}u+x_D{u}^3}{2u^2-2u+1}\\ y_M=\frac{y_A{\overline{u}}^3+y_B{u}^2\overline{u}+y_C{\overline{u}}^{2}u+y_D{u}^3}{2u^2-2u+1}\\ z_M=\frac{z_A{\overline{u}}^3+z_B{u}^2\overline{u}+z_C{\overline{u}}^{2}u+z_D{u}^3}{2u^2-2u+1}\end{array}\right..$

Следует отметить, что уравнения (3) и (4) получены на основе классических проективных алгоритмов [23] и в процессе экспериментов показали высочайший уровень устойчивости при изменении исходных данных.

Проверим масштабируемость точечного исчисления на примере моделирования поверхностей (рис. 4) и тел (рис. 5) в трехмерном пространстве.

Рис. 4. Геометрическая схема моделирования 9-точечного отсека поверхности.

Рис. 5. Геометрическая схема определения твердотельной модели параллелепипеда.

Моделирование участка интерполяционной поверхности, проходящей через 9-точек [24], удобно представить в виде вычислительного алгоритма последовательности точечных уравнений, каждое из которых позволяет реализовать параллельные вычисления за счет покоординатного расчета:

$\left[\begin{array}{l}{M}_A=A_1\overline{u}\left(1-2u\right)+4A_2\overline{u}u+A_{3}u\left(2u-1\right)\\ M_B=B_1\overline{u}\left(1-2u\right)+4B_2\overline{u}u+B_{3}u\left(2u-1\right)\\ M_C=C_1\overline{u}\left(1-2u\right)+4C_2\overline{u}u+C_{3}u\left(2u-1\right)\\ M=M_A\overline{v}\left(1-2v\right)+4M_B\overline{v}v+M_{C}v\left(2v-1\right)\end{array}\right.,$

где M ‒ текущая точка отсека параболической поверхности; M_A, M_B, M_C ‒ текущие точки направляющих параболических дуг; A_i, B_i, C_i ‒ исходные точки, координаты которых соответствуют исходной экспериментально-статистической информации; u и v ‒ текущие параметры отсека параболической поверхности; $\overline{u}$ = 1 – u и $\overline{v}$ = 1 – v ‒ дополнение текущих параметров до 1.

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

Следует отметить, что масштабируемость точечных уравнений и вычислительных алгоритмов на их основе также подтверждается геометрической теорией многомерной интерполяции [25] с возможностью обобщения геометрических объектов на многомерное пространство.

В качестве последнего примера рассмотрим твердотельную геометрическую модель параллелепипеда с вершинами A, B, C, D (рис. 5), которая в линейном пространстве определяется простым точечным уравнением и соответствующей ему системой параметрических уравнений:

$\begin{array}{c}M=Au+Bv+Сw+D\left(1-u-v-w\right).\\ \Updownarrow \\ \left\{\begin{array}{l}{x}_M=x_{A}u+x_{B}v+x_{С}w+x_D\left(1-u-v-w\right)\\ y_M=y_{A}u+y_{B}v+y_{С}w+y_D\left(1-u-v-w\right)\\ z_M=z_{A}u+z_{B}v+z_{С}w+z_D\left(1-u-v-w\right)\end{array}\right.,\end{array}$

где A, B, C, D – точки, которые не только сами по себе формируют локальный симплекс трехмерного пространства, но и однозначно определяют положение и размеры параллелепипеда в глобальной системе координат; M – текущая точка, которая своим движением заполняет трехмерное пространство формируя твердотельную модель параллелепипеда; $u=\frac{DP}{DA},v=\frac{DQ}{DB},w=\frac{DR}{DC}$ – текущие параметры, которые изменяются от 0 до 1.

5. ВЫВОДЫ

Исходя из вышеизложенного можно сделать следующие выводы о перспективах использования точечного исчисления в качестве математического аппарата для реализации параллельных вычислений в САПР [26]:

Математический аппарат “Точечное исчисление” позволяет реализовать декомпозицию задач геометрического моделирования на однотипные независимые подзадачи за счет покоординатного расчета и инвариантных свойств точечных уравнений относительно параллельного проецирования.

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

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

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

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

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

ИСТОЧНИК ФИНАНСИРОВАНИЯ

Работа выполнена в рамках государственного задания Министерства науки и высшего образования Российской Федерации (№ 124012000104-5 “Математический аппарат реализации параллельных вычислений в системах геометрического моделирования и автоматизированного проектирования”).

About the authors

E. Konopatskiy

Author for correspondence.
Email: e.v.konopatskiy@mail.ru
Russian Federation, Nizhny Novgorod

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1. Geometric interpretation of coordinate-by-coordinate calculation for a straight line segment in 3-dimensional space.

Download (86KB)

Indexing metadata

3. Fig. 2. Geometric scheme for constructing a 2nd order curve.

Download (63KB)

Indexing metadata

4. Fig. 3. Geometrical scheme of modeling a bypass arc based on the Desargues configuration.

Download (131KB)

Indexing metadata

5. Fig. 4. Geometrical scheme of modeling a 9-point surface section.

Download (95KB)

Indexing metadata

6. Fig. 5. Geometric scheme for defining a solid model of a parallelepiped.

Download (85KB)

Indexing metadata