PARALLEL COMPUTING TECHNOLOGIES IN THE FINITE ELEMENT METHOD

Nowadays engineers and researchers are faced with solving very complex problems in a mathematical modeling and design. Numerical analysis naturally finds applications in all fields of engineering and the physical sciences. The finite element method is a powerful tool for the numerical simulation of a wide range of problems. Implementation of the finite element method in CAD systems on the basis of modern computers allows researchers to solve large scale problems. The finite element method uses a discretization of a continuum domain into a mesh as the starting point. The discretization of complex domains may give large numbers of elements, thus increasing the requirements of computer memory and speed. Modern parallel computers use multiple processing elements simultaneously to solve a problem. Thus implementation of parallel computing into the finite element method is urgent direction of the research. In the finite element method for the numerical solution of partial differential equations, the stiffness matrix represents the system of linear equations that must be solved in order to ascertain an approximate solution to the differential equation. Therefore the article describes parallel algorithms for assembly of stiffness matrix and for solution of linear equations. Also this article contains two numerical experiments: 1) Dirichlet problem on the complex domain (gear); 2) Elasticity problem of three-layer shell. In the end of the article author compares the speed of a solution of these problems with one, two and four parallel cores and makes discussion about the effectiveness of parallel finite element processing.

section_content: Одной из наиболее распространенных классификаций архитектуры вычислительных систем является систематика Флинна [5], которая основана на анализе способов взаимодействия функциональных вычислительных устройств и обрабатываемых данных. В результате различаются основные четыре типа вычислительных систем [5] [6] [7] :

-SISD (Single Instruction, Single Data) -вычислительные системы, в которых используется единственное функциональное устройство для исполнения одного потока инструкций с одиночным потоком данных;

-SIMD (Single Instruction, Multiple Data) -системы с одним потоком инструкций, в которых одна инструкция может применяться к векторам данных (нескольким потокам данных);

-MISD (Multiple Instruction, Single Data) -системы с множественным потоком инструкций и одним потоком данных;

-MIMD (Multiple Instruction, Multiple Data) -вычислительные системы с множественным потоком инструкций и множественным потоком данных. 

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

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

К типу MIMD относятся системы с множеством функциональных устройств: мультипроцессоры (многопроцессорные и многоядерные системы) и мультикомпьютеры (распределенные вычислительные системы, кластеры). 

На современном рынке вычислительных систем в наиболее доступном ценовом диапазоне широко представлены мультипроцессорные системы с общей памятью, которые содержат от 2 до 16 функциональных устройств. Такие вычислительные системы можно использовать для начальной отладки параллельных алгоритмов и оценки их эффективности. Для программирования в таких системах наиболее распространенными являются решения на базе потоков (например, POSIX Threads, Boost. Thread и другие) или стандарта OpenMP (Open Multi-Processing) [8, 9].
section_name: ТИПЫ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ОСНОВНЫЕ ТЕХНОЛОГИИ ДОСТИЖЕНИЯ ПАРАЛЛЕЛЬНОСТИ

section_content: Основная идея метода конечных элементов состоит в том, что любую искомую непрерывную величину (например, температуру, перемещения и другие) можно аппроксимировать при помощи кусочно-непрерывных функций, определенных на элементарных геометрических областях -конечных элементах, образующих дискретную модель области. Для определения значений искомой непрерывной величины в узлах дискретной модели строится система линейных алгебраических уравнений, матрица которой носит название глобальной матрицы жесткости. 

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

Таким образом, в случае достаточно сложных дискретных моделей, этапы построения глобальной матрицы жесткости и последующего решения СЛАУ являются наиболее требовательными к вычислительным ресурсам. Следовательно, внедрение параллельных вычислений при выполнении этих этапов способно дать наиболее значимый результат с точки зрения экономии времени на проектирование и моделирование. 

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

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

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

Время, необходимое для построения глобальной матрицы жесткости при помощи параллельного вычислительного процесса, можно оценить величиной T p ( )

где I -процессорное время, необходимое для интегрирования исходного дифференциального уравнения на одном конечном элементе, m -процессорное время, необходимое для ансамблирования результатов интегрирования на одном элементе, t thread -время, необходимое для инициализации одного вычислительного потока. 

Аналогично, время, необходимое для построения глобальной матрицы жесткости на базе последовательного алгоритма, можно оценить величиной T s
section_name: ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МЕТОДА КОНЕЧНЫХ ЭЛЕМЕНТОВ

section_content: ). 

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

Для решения полученных в результате построения глобальной матрицы жесткости СЛАУ на практике, как правило, используются итерационные методы (напри-

В результате вычислительного эксперимента получены результаты, приведенные в табл. 1 (время в секундах).
section_name: (

section_content: Дана защемленная по контуру трехслойная оболочка, радиус которой 0,4 м, толщина -0,01 м. Внутренний слой: толщина -0,008 м, модуль Юнга -E i = 72017,3327 МПа, коэффициент Пуассона -ν i = 0,2999518536. Внешние
section_name: Исследование прогиба трехслойной круглой оболочки под равномерной нагрузкой

section_content: Таким образом, вычислительные эксперименты показали, что использование параллельных вычислений в методе конечных элементов позволяет сократить время на проектирование и моделирование деталей и конструкций. Из таблиц видно незначительное преимущество во времени при использовании четырех вычислительных потоков относительно двух, что может быть связано с использованием двух виртуальных ядер (которые не обладают аналогичной двум физическим ядрам производительностью). Реализация разработанных алгоритмов на базе библиотек стандарта openMP позволяет рассматривать полученную в ходе исследования кодовую базу в качестве основы для построения кластерной реализации. Перспективным направлением исследований в данном направлении является изучение влияния количества потоков на производительность (или затраченное время). Также важным направлением является изучение производительности многопоточных вычислений в зависимости от количества узлов/элементов в сетке, особенно в СПИСОК ЛИТЕРАТУРЫ
section_name: ВЫВОДЫ

section_name: PARALLEL COMPUTING TECHNOLOGIES IN THE FINITE ELEMENT METHOD

section_content: МАТЕМАТИЧНЕ ТА КОМП'ЮТЕРНЕ МОДЕЛЮВАННЯ Чопоров С. В. Канд. техн. наук, доцент, Запорізький національний університет, Україна ВИКОРИСТАННЯ ТЕХНОЛОГІЙ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ У МЕТОДІ СКІНЧЕННИХ ЕЛЕМЕНТІВ В роботі розглянута проблема впровадження паралельних обчислень у метод скінченних елементів. Розглянуто особливості побудови матриці жорсткості та вирішення отриманої системи лінійних рівнянь на базі паралельних обчислень. Проведено обчислювальні експерименти, які використані для аналізу ефективності запропонованих підходів. 

Ключові слова: метод скінченних елементів, паралельні обчислення, математична модель, обчислювальний метод. 

Choporov S. V. Ph. D. Candidate, аssociate Professor, Zaporizhzhya National University, Ukraine

section_content: Nowadays engineers and researchers are faced with solving very complex problems in a mathematical modeling and design. Numerical analysis naturally finds applications in all fields of engineering and the physical sciences. The finite element method is a powerful tool for the numerical simulation of a wide range of problems. Implementation of the finite element method in CAD systems on the basis of modern computers allows researchers to solve large scale problems. 

The finite element method uses a discretization of a continuum domain into a mesh as the starting point. The discretization of complex domains may give large numbers of elements, thus increasing the requirements of computer memory and speed. 

Modern parallel computers use multiple processing elements simultaneously to solve a problem. Thus implementation of parallel computing into the finite element method is urgent direction of the research. 

In the finite element method for the numerical solution of partial differential equations, the stiffness matrix represents the system of linear equations that must be solved in order to ascertain an approximate solution to the differential equation. Therefore the article describes parallel algorithms for assembly of stiffness matrix and for solution of linear equations. 

Also this article contains two numerical experiments: 1) Dirichlet problem on the complex domain (gear); 2) Elasticity problem of three-layer shell. 

In the end of the article author compares the speed of a solution of these problems with one, two and four parallel cores and makes discussion about the effectiveness of parallel finite element processing. 

Keywords: finite element method, parallel computing technologies, mathematical model, numerical method.
section_name: PARALLEL COMPUTING TECHNOLOGIES IN THE FINITE ELEMENT METHOD