автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы и комплекс программ параллельных вычислений при математическом моделировании критичных по времени процессов

На правах рукописи

ПОПОВ Александр Сергеевич

АЛГОРИТМЫ И КОМПЛЕКС ПРОГРАММ

ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ПРИ МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ КРИТИЧНЫХ ПО ВРЕМЕНИ ПРОЦЕССОВ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

3 МАЙ Ш1

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

005016435

005016435

Работа выполнена на кафедре «Системы автоматизированного проектирования» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Тамбовский государственный технический университет» (ФГБОУ ВПО «ТГТУ»).

Научный руководитель доктор технических наук, профессор,

профессор кафедры «Системы автоматизированного проектирования» ФГБОУ ВПО «ТГТУ»

Литовка Юрий Владимирович

Официальные оппоненты: доктор технических наук, профессор,

профессор кафедры «Системы искусственного интеллекта» ФГБОУ ВПО «СГТУ им. Гагарина Ю.А.» Большаков Александр Афанасьевич

доктор технических наук, профессор, заведующий кафедрой «Информационные технологии, моделирование и управление» ФГБОУ ВПО «ВГУИТ» Абрамов Геннадий Владимирович

Ведущая организация федеральное государственное автоном-

ное образовательное учреждение высшего профессионального образования «Южный федеральный университет» г. Ростов-на-Дону

Защита состоится 23 мая 2012 г. в 15 часов 30 минут на заседании диссертационного совета Д 212.260.07 при ФГБОУ ВПО «ТГТУ» по адресу: г. Тамбов, ул. Ленинградская, д. 1, ауд. 160.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью организации, просим направлять по адресу: 392000, г. Тамбов, ул. Советская, д. 106, ФГБОУ ВПО «ТГТУ», ученому секретарю диссертационного совета Д 212.260.07.

С диссертацией и авторефератом можно ознакомиться в библиотеке ФГБОУ ВПО «ТГТУ».

Автореферат разослан 22 апреля 2012 г.

Ученый секретарь диссертационного совета доктор технических наук, доцент

С.Я. Егоров

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность исследования. Рассмотрим общую постановку задач, характерную для данной работы: необходимо решить уравнения исходной математической модели при помощи численного метода за заданный или меньший интервал времени. Ход решения задачи назовём процессом критичным по времени. Такие задачи часто возникают при организации оптимального управления либо когда время проведения численного эксперимента превышает время проведения физического эксперимента. Для решения таких задач за заданное время могут быть использованы параллельные вычисления. Данный подход оправдан с экономической и с технологической сторон. Параллельные вычисления обычно ассоциируются с суперкомпьютерами и кластерными системами. С распространением многоядерных процессоров и видеокарт с унифицированной шейдерной архитектурой появилась возможность реализо-вывать параллельные вычисления с помощью персональных компьютеров. Их стоимость на несколько порядков меньше, чем стоимость суперкомпьютеров. Существует ряд задач, которые можно решить на персональных компьютерах в режиме параллельных вычислений, например: распознавание изображений; расчет электрических и магнитных полей в различных средах; анализ аналоговых сигналов в реальном времени и др. Основные исследования проводились такими учеными как Mark Harris (основоположник направления GPGPU), Sha'Kia Boggan, Daniel M. Pressel, Ryoji Tsuchiyama, Takashi Naka-mura, Takuro Iizuka, Akihiro Asahara, Satoshi Miki, B.B Воеводин, Вл.В. Воеводин, Б.Н.Четверушкин. Однако исследований в данной области проводилось немного, количество литературных источников сильно ограничено, существует ряд разрозненных статей, большинство из которых носит обзорный характер. Кроме того, нет единой стратегии для применения аппаратных средств с целью эффективного использования их вычислительных ресурсов.

Поэтому создание единой среды для проектирования, реализации и исследования эффективных численных методов для математического моделирования критичных по времени процессов, а также оптимизации использования аппаратных ресурсов с точки зрения вычислительной нагрузки, является актуальной научной и практической проблемой. Работа выполнена в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России 2009 - 2013 годы», государственный контракт № 02.740.11.0624.

Объект и предмет исследования. Объектом исследования являются критичные по времени процессы.

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

Цель и задачи исследования - уменьшение времени численного решения на ЭВМ уравнений математических моделей критичных по времени процессов при помощью параллельных вычислений.

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

- создание численного метода решения задачи поиска оптимального вычислителя;

- разработка комплекса программ для создания, отладки и тестирования параллельных алгоритмов, на основе задачи определения оптимального вычислителя;

- исследование работоспособности полученного комплекса программ в производственных условиях.

Методы исследования. В диссертационной работе использовались методы математического моделирования, параллельного и объектно-ориентированного программирования.

Научная новизна:

1. Впервые предложена математическая модель для поиска оптимального вычислителя с точки зрения загрузки аппаратных средств отдельно взятой ЭВМ.

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

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

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

На защиту выносятся:

1. Математическая модель поиска оптимального вычислителя с точки зрения загрузки аппаратных средств.

2. Модифицированные математические модели оптимизации процесса нанесения гальванического покрытия, анализа аналогового сигнала с синусно-косинусного трансформатора, построения трехмерного представления детали по ее двумерному представлению.

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

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

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

• решения уравнений математической модели распределения электрического поля и модифицированной модели определения оптимального размещения деталей на подвеске в гальванической ванне;

• анализа угла поворота датчика синусно-косинусного трансформатора в реальном времени;

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

Внедрение. Разработанный комплекс программ успешно прошел производственные испытания в ООО «Гранит-М» (г. Уварово Тамбовской области) и принят к использованию при проектировании перспективного гальванооборудования, которое планируется выпускать на этом предприятии. Данный комплекс также принят к использованию в ОАО «Тамбовский завод «Электроприбор» (г. Тамбов) для анализа ряда аналоговых сигналов, поступающих с готовых изделий предприятия, и принятия решения о годности выпускаемой продукции.

Соответствие диссертационной работы паспорту специальности:

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

2. Проведены комплексные исследования разработанных алгоритмов параллельных вычислений с применением современной технологии математического моделирования и вычислительного эксперимента. Пункт 4.

3. Реализованы эффективные численные методы и алгоритмы вычислений уравнений разработанных математических моделей в виде комплекса проблемно-ориентированных программ. Пункт 5.

Апробация работы. Результаты диссертации докладывались и обсуждались на XXI - XXIII международных научных конференциях «Математические методы в технике и технологиях» (Саратов, 2008; Псков, 2009; Саратов, 2010), 7 Международной конференции «Покрытия и обработка поверхности» (Москва, 2010), на VII Всероссийской научной конференции «Защитные и специальные покрытия, обработка поверхности в машиностроении и приборостроении» (Пенза, 2010).

Публикации. Основные положения диссертации отражены в 12 публикациях, в том числе в 4 статьях в рецензируемых журналах, а также в 2 программах, зарегистрированных в ФИПС.

Личный вклад автора в статьи. В статьях 1, 5, 6, 8 - 10 опубликованы общие принципы выбора вычислителя, используемые в данной работе, в статьях 2, 3, 7 разработаны модифицированные: математическая модель, численный метод и алгоритм построения трехмерного представления детали по ее двумерному представлению, в статьях 4, 8 описан реализованный комплекс

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

В первой главе рассматривается современное состояние процесса создания и реализации алгоритмов параллельных вычислений. Проанализированы современные программные и аппаратные средства для реализации параллельных вычислений.

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

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

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

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

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

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

1. Выявить возможность распараллеливания исходного алгоритма, а также последовательные этапы, где присутствует такая возможность.

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

3. Сформировать параллельный алгоритм на каждом из последовательных этапов, задать входные и выходные данные этапов.

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

5. Оценить эффективность параллельной реализации алгоритма.

6. Разработать комплекс проблемно-ориентированных программ для реализации параллельных алгоритмов.

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

Необходимо определить набор вычислителей £2 из набора вычислителей, присутствующих в системе Ph а также степени разбиения на каждом из них 7V, с использованием контрольного примера, построенного для текущей задачи Q, при которых разность заданного времени работы Г,ад, и времени выполнения заданной задачи Трж, полученной на основе выполнения контрольного примера Q и аппроксимированное до размерности и сложности искомой задачи, будет положительной и минимальной:

{т _ т >о

л зад i рас — "s Т'зад - Урас —► min.

При следующих ограничениях:

С = fiinc(i,N), Ne [l.tfj, « = U,...,ND, I Tt = QTP? + QcPf + (Q? + Qd )/f Q? = QT P/ ,

tt_T,Nt T __ T-'*NT

v- 4 m

где Тм — время исполнения на i-м вычислителе с разбиением на N задач; fiinc (г, N) - вычисляемая функция, выполняющая расчет на вычислителе, с

заданной степенью разбиения и возвращающая время исполнения задачи на нем; г - номер вычислителя; N - количество разбиений; Л^ - количество элементарных подзадач (размерность по всем координатам контрольного примера); N0 - количество вычислителей в системе; ()т, - оценочная сложность элементарного разбиения; Р? - производительность одного элемента /-го вычислителя (функция частоты); Qc - связанность элементарных задач (0 для несвязанных); Р. - межэлементная передача данных (отношение производительности вычислителя ко времени передачи между элементами, маленькое для моноблочных вычислителей, большое для различных сетей); Qf - оценочный объем передаваемого элементарного разбиения; - объем данных элементарного разбиения; Р? - время, затрачиваемое на передачу, между основной системой и г-м вычислителем; Р/ - размер одной команды вычислителя; 7|г - оценочное время исполнения искомой полноразмерной задачи на г-м вычислителе; Р^ - количество вычислительных элементов г'-го устройства; Ыт - размерность исходной задачи; Кс - коэффициент, характеризующий степень упрощения исходной задачи для получения контрольного примера (для задач, в которых получение контрольного примера идет только за

счет снижения размерности, коэффициент равен 1); Т?т - оценочное время исполнения искомой полноразмерной задачи на г-м вычислителе на основе экспериментальных данных при наиболее выгодном разбиении; 7]э - минимальное время работы при оптимальном разбиении.

Использовать несколько вычислителей в связке целесообразно, когда их производительности примерно равны, а также издержки на передачу данных между вычислителями при высокой связанности искомой задачи ниже времени расчета на них. Для определения набора вычислителей £2 используются следующие дополнительные уравнения для каждого С/.

где Cj - j-й набор индексов с примерно одинаковой производительностью; Nc - количество наборов; Nj - количество элементов в j- м наборе.

При этом в каждый из наборов входит не обязательно максимальное количество вычислителей, кроме того, один вычислитель может участвовать в нескольких наборах. Наборы составляются таким образом, чтобы время выполнения задачи на них оказалось ниже Гзад, после чего добавление в набор прекращается. Двух одинаковых наборов не должно существовать. Из всех наборов, у которых время выполнения меньше Т3№, выбирается набор с наименьшим количеством вычислителей и наименьшим временем исполнения

/=1,2,...,ЛГС

при этом. Если наборов, у которых время исполнения ниже Гмд нет, выбирается набор с наименьшим временем исполнения.

Для определения оценочного времени исполнения на нескольких вычислителях, с учетом распределения задачи по вычислителям, используется следующее соотношение:

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

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

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

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

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

Структурная схема программного комплекса показана на рис. 1.

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

ния/сохранения настроек приложения в конфигурационные ¡ш-файлы, сохранения загрузок данных, а также архивации/разархивации файлов при открытии/сохранении на основе открытого алгоритма Ь2МА. Для работы с внешними аналоговыми источниками данных реализован модуль для работы с аналого-цифровыми преобразователями фирмы ЗАО «Л-Кард». Также создан комплект быстрой разработки библиотек для реализации конкретного алгоритма параллельных вычислений.

Модуль Загрузки/Сохранения данных —► Модуль LZMA архивирования Модуль Параллельных задач

Модуль Загрузки модулей <— Модуль Ядра —► Модуль Загрузки библиотек

*

Модуль Загрузки настроек Библиотеки решаемых задач Модуль Интерфейса

Рис. 1. Структурная схема программного комплекса

Основные классы модулей данной системы:

• модуль ядра реализует общую функциональность комплекса программ, осуществляет загрузку вспомогательных модулей;

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

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

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

Для анализа увеличения скорости расчета для различных алгоритмов был использован следующий персональный компьютер AMD Athlon Х2 3800+/4r6/NVIDIA GeForce 8800 GTS (320 Mb)/Windows XP Pro SP2.

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

размещений составляет более 60%. Результаты решения задачи сравнивались с экспериментальными данными, что подтвердило адекватность данного численного метода.

Необходимо найти координаты всех базовых точек деталей (х„ у,), t = 1, 2,..., п, где п - количество деталей, при которых суммарная неравномерность гальванического покрытия:

п

% =YsRt -»min.

*=1

где R, - неравномерность покрытия t-i\ детали.

Неравномерность для каждой из деталей рассчитывается по формуле

с j 2пш1 '

^ 8<

при следующих ограничениях:

r d2(p(x,y,z) d2q>(x,y,z) Э2ф(x,y,z) п d(f>(x,y,z),

Э*2 Ьу2 dz2 ' дп = °'

J (<р(х, у, z) + F, (¿(х, у, Sa=U, [<р{х, у, z) + F2 {i(x, у, zj)\ ^ = 0,

i(x, у, z) = -xgrad((pO, y,z)), 8, {x,y,z) = — i, {x, y, z)Ax,

P

J= 1, 2,..., n,

где <p(x, y, z) - потенциал в точке; S„ - поверхность изолятора (стенки ванны из изолирующего вещества); F,(i) - функция анодной поляризации; F2(i) - функция катодной поляризации; U - напряжение между катодом и анодом; Sa -поверхность анода; Skt - поверхность t-ro катода; % - электропроводность электролита; 5,(х, у, z) - толщина гальванического покрытия в точке i-ro катода; Э - электрохимический эквивалент вещества; р - плотность металла покрытия; Дт - время процесса.

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

Дополнительные ограничения:

• детали не могут пересекаться и выходить за границы ванны;

• технологическое ограничение силы тока zmin < ikt < irwi;

• минимальная толщина покрытия больше заданной б,1™1 > 8™ .

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

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

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

С д2(?(х,у,г) Э2фО,У,2)_п дфс,у,г)\

' _ ^ » "ч м« >

<

дх2 ду2 ' Эй

(q<x,^z) + F1(i(x,^z))]|1se =U, {<?(x,y,z) + F2{i(x,y,z))\Ski =0,

<

.i(x,y,z) = -Xgrad{q(x,y,z)), 5t{x,y,z) = -il{x,y,z)AT, t= 1,2,...,п.

ду2 + dz2 (<p(x,^z) + fl(i(x,^r))]|Se = U, {<?(x,y,z) + F2{i(x,y,z))]Ski =0,

.i(x,у,z) = -xgrad^O,у,z)), 5,(*,у,.z) = — it(*,у,г)Дх, t = 1,2,..., n.

Обозначим через q>*; ■ к, ф-'^ значения потенциала в узле сетки с координатами Xj, }'j, zb полученные при решении подзадач ХоУ и ZoY соответственно.

Тогда решение искомой задачи будет определяться как среднее арифметическое и :

h V

Ф<|М = Ф<-М^ФЛМ, 1 = 0,1.....иь 7 = 0,1,А=0,1,...,из.

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

Разностный оператор с использованием пятиточечного шаблона:

( Фы,./ - 2фл/ + Ф,-+|г/ | - 2фм- + <рц+1 Фг^-Фи .

5--1--^-— и, -= и,

л,2 1'у(Л К

, ФП[,у-фП1-1,; Ф,М+Ф,',2 , 77 / Ф/,2 ~ Ф/,1 ч „

ф,>2+ф,>2-1 | г .Ф,>| -Ф.У.1-К _0 2 21 }1у(п2)

Краевые условия содержат нелинейные функциональные зависимости что не позволяет решать задачу как систему линейных уравнений. Зададим начальное приближение функции распределения плотности тока на катоде, т.е. /°(/) =(ф1и, _ ф,,,, _ 3)//гу(«2), г = 1,2, ..., щ, и точность е, выполнения краевого условия.

До начала работы метода прогонки необходимо задать начальное приближение функции во всех узлах сетки, т.е. ф,-^ ,к = 0 и величину е2 точности

решения (критерия окончания итерационного процесса метода прогонки).

На каждой внутренней строке у = 2, 3, ..., и2 - 1 методом прогонки решаем уравнение

ф1-и5)-2ф1*+°'5)

/ , 2

1 +

hi hid)

n(*+o,s) _.

hi

h;u)

где k - номер итерации, (к+ 0,5)-я итерация вводится для повышения точности.

Устойчивость метода проверялась с использованием сетки 80... 120 шагов, полученные результаты позволяют говорить об устойчивости метода.

При решении задачи имеем следующие результаты вычислений по скорости:

• последовательный алгоритм - 7 сут 4 ч 15 мин;

• для разбиения на центральном процессоре (2 ядра) - 3 сут 22 ч 27 мин ускорение в 1,82 раза, эффективность использования вычислителей -91%, теоретическое ускорение в 2 раза, исходя из закона Амдала;

• для разбиения на видеокарте 96 вычислителей (8 SIMD блоков 16 потоков данных в каждом) GeForce 8800GTS - 2 ч 6 мин 58,1 с, ускорение в 82,6 раз, эффективность — 85%, теоретическое ускорение в 96 раз.

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

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

Необходимо найти в заданный момент времени tn дискретное значение угла поворота датчика СКТ а„ на основании исходных данных синуса S„ и косинуса С„ угла при заданной частоте фильтрации сигнала © при следующих ограничениях:

г 2iakn N—\ 2nikn дг-1 2takn

Хк=1упе~,гк = ^спе » ,s:=j-zx:e » , J л=0 и=0 V k=0

лч s*

C*= —Vf> n ,a = arctg—¡- , л = 0, ...,N- 1, £= 0,..., JV- 1, ^ it=o С

где C„ - значения исходных сигналов с обмоток трансформатора; JV - количество снятых за один цикл точек исходного сигнала (зависит от АЦП); Хк, Yk - частотные характеристики входных сигналов; X , У, - частотные характеристики сигналов после фильтрации; S^ , С* - дискретные значения

результирующего сигнала синуса и косинуса соответственно с применением частотного фильтра; а„ - дискретные значение угла поворота СКТ.

Для фильтрации исходного сигнала воспользуемся дискретным преобразованием Фурье (ДПФ). Так как датчик работает на частоте 400 Гц, то можно фильтровать сигнал с частотой 0 более 800 Гц. После преобразования в обеих частотных характеристиках обнуляются частоты выше 800 Гц (больше полезного сигнала).

Рассмотрим параллельную и последовательную реализацию основной части алгоритма численного метода решения данного примера.

1. Съем исходных сигналов Sn и С„, п = 0,1,..., N— 1.

2. Цикл вычисления прямого ДПФ к- 0,1,..., N - 1.

5. Увеличение к, если к < N— 1, то переход к п. 3.

6. Обнуление частот характеристики больших 0.

7. Цикл вычисления обратного ДПФ и = 0, 1,..., N - 1.

8. S =— > X cos --9. С =-> У, cos —- .

n ДГ i-t к I AT I n -tJ ¿-I к \ JJ

k=OV V W J J JV V JV J J

10. Увеличение n, если n < N— 1, то переход к п. 7.

11. Цикл вычисления угла поворота и = 0, 1, ...,N- 1.

12. a^aretgfc/c;).

13. Увеличение п, если п < N— 1, то переход к п. 11.

14. Вывод результирующей дискретной зависимости угла a(i).

В данном алгоритме имеем три этапа: 2 - 5, 7 - 10 и 11 - 13, на первых двух этапах имеем по две подзадачи, на третьем - одну.

Для проверки устойчивости метода были использованы различные частоты дискретизации при снятии аналогового сигнала 90...110 кГц.

Для получения изменения угла поворота за период 1 с получаем:

• последовательный алгоритм - 3,1 с;

• для разбиения на центральном процессоре (2 ядра) - 1,9 с, ускорение в 1,63 раза, эффективность 82%, теоретическое ускорение в 1,98 раза;

• для разбиения на видеокарте 96 вычислителей (8 SIMD блоков 16 потоков в данных каждом) GeForce 8800GTS - 50 мс, ускорение в 62 раза, эффективность 65%, теоретическое ускорение в 66 раз.

Пример III. Задача построения трехмерного представления детали по ее двумерному представлению. Рассмотрена модификация численного метода преобразования двумерного представления детали в трёхмерное представление, предложенное в работе [2]. Модификация состоит в добавлении дополнительного этапа преобразования в рецепторное представление, а затем в итоговое полигональное представление. В результате добавления дополнительного этапа удается сократить количество полигонов в итоговом представлении. Для примера при использовании сетки 100x100 и преобразовании представления куба из двумерного представления в трёхмерное получаем: для немодифицированного метода - 58 806 полигонов, для модифицированного -12 полигонов. Адекватность метода подтверждена применением его для ряда представлений, с известным как двумерным так и трёхмерным видами.

Необходимо определить геометрическое место точек для задания поверхности результирующего трехмерного представления детали в полигональном виде:

Р,(х\,Уи zf, х2,у2, z2; х3,у3, z3), i = 1, 2,..., N, где Р- г'-й полигон (в качестве полигонов используются треугольники), N -количество полигонов в итоговом представлении, при котором результирующее трехмерное представление будет соответствовать исходному двумерному с заданной точностью, определяемому шагом трехмерной сетки, используемому при нахождении точек поверхности детали.

Заданное исходное представление имеет вид

Vj (хъ Уи zu х2, у2, z2), 7=1,2,..., М,

где Vj - отрезок исходного векторного двумерного представления детали; М -количество отрезков.

Входные данные (рис. 2) представляют собой набор отрезков, из которых состоит чертеж детали (дуги, эллипсы и окружности заменяются набором прямых), у каждого отрезка имеется параметр, определяющий тип линии (1 -основная линия, 2 - невидимая линия). Рис. 2. Общий вид входных данных

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

а) б)

Рис. 3. Матрица базового блока (а). Итоговая матрица (б)

Рассмотрим реализацию основной части алгоритма численного метода.

1. Ввод исходных данных = 1, 2,..., М.

2. Решение уравнений определения проекций (V- , М/), (У-, М), (V- , Мл).

3. Выделение блоков В? , В^, В'ч , д = 1, 2,..., Мъ.

4. Построение куба и решение уравнений для нахождения и определения массивов точек Д/х, у, г).

5. Цикл для всех блоков ^ = 1,2,..., Мь.

6. Цикл для всех нормалей Ы°х г = 1,2, ..., (и + I)2

7. Решение уравнений для нахождения точек поверхности 0<,(х,у,г), для г'-й нормали.

8. Увеличение г на 1, если г < (и + I)2, то переход к п. 6.

9. Цикл для всех нормалей Ы°у г = 1, 2, ..., (и + I)2.

10. Решение уравнений для нахождения точек поверхности О^х, у, г), для г'-й нормали, с учетом уже заполненных данных.

11. Увеличение г на 1, если г < (и + I)2, то переход к п. 9.

12. Цикл для всех нормалей Ы^ г' = 1, 2,..., (п + 1)'.

13. Решение уравнений для нахождения точек поверхности Д,(х, у, г), для г'-й нормали, с учетом уже заполненных данных.

14. Увеличение г на 1, если г < (п + I)2, то переход к п. 12.

15. Проверка краевых точек на вхождение в у, г).

16. Увеличение q на 1, если q < Mb, то переход к п. 5.

17. Объединение матриц Dq(x, у, z).

18. Построение результирующего полигонального представления.

19. Вывод итогового трехмерного полигонального представления.

Цикл 5-16 и 6 -8, 9-11,12-14 можно вычислять параллельно.

Устойчивость метода проверялась с использованием сетки 80... 120 шагов,

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

Варианты построения трехмерного представления для примера:

• последовательный алгоритм - 36,391 с;

• для разбиения на центральном процессоре (2 ядра) - 19,04 с, ускорение в 1,91 раза, эффективность 95%, теоретическое ускорение в 2 раза;

• для разбиения на видеокарте 96 вычислителей (8 SIMD блоков 16 потоков в данных каждом) GeForce 8800GTS - 420 мс, ускорение в 86,65 раза, эффективность 90%, теоретическое ускорение в 96 раз.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Разработанные эффективные численные методы для решения уравнений модифицированных математических моделей позволяют ускорить вычисления для расчета: электрического поля в гальванической ванне, построения трехмерного представления детали по двумерному представлению, угла поворота датчика синусно-косинусного трансформатора в 83,87 и 62 раза соответственно.

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

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

4. Практическая ценность результатов, полученных в диссертационном исследовании, подтверждена актами внедрения в работу на предприятиях ООО «Гранит-М» и ОАО «Тамбовский завод «Электроприбор».

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в рецензируемых журналах:

1. САПР гальванических процессов / A.C. Попов, Ю.В. Литовка, Г.А. Кириченко, М.А. Попова // Вестник Тамбовского государственного технического университета. - Т. 14,-№4.-Тамбов, 2008.-С. 882-891.

2. Алгоритм формирования объемной геометрической модели детали из чертежа проекций / A.C. Попов, Ю.В. Литовка, В.В. Пэк, М.А. Попова //

Вестник АГТУ. Сер. «Управление, вычислительная техника и информатика». - Астрахань, 2009. - № 2 - С. 152 - 160.

3. Построение трехмерной сетки детали для расчета распределения гальванического покрытия по ее поверхности / A.C. Попов, Ю.В. Литовка, М.А. Попова // САПР и графика. - М., 2010. - № 1. - С. 68-69.

4. Система исполнения параллельных вычислительных процессов / A.C. Попов, Ю.В. Литовка // Радиотехника. - М., 2010. - № 5. - С. 60 - 67.

Прочие публикации:

5. Попов, A.C. Постановка задачи решения уравнения Лапласа при помощи параллельных вычислений / A.C. Попов, Ю.В. Литовка // Математические методы в технике и технологиях : сб. тр. XXI Междунар. науч. конф. -Т. 6. - Саратов, 2008. - С. 89-90.

6. Попов, A.C. О параллелизации вычислений в САПР гальванических процессов / A.C. Попов, Ю.В. Литовка // Математические методы в технике и технологиях : сб. трудов XXII Междунар. науч. конф. - Т. 10. - Псков, 2009. -С. 99-101.

7. Попов, A.C. Ввод графической информации в системе управления гальваническими процессами / A.C. Попов, Ю.В. Литовка, М.А. Попова // Математические методы в технике и технологиях : сб. тр. XXIII Междунар. науч. конф. - Саратов, 2010. - С. 47-48.

8. Попов, A.C. Система разработки и отладки алгоритмов параллельных вычислений / A.C. Попов // Математические методы в технике и технологиях : сб. тр. XXIII Междунар. науч. конф. - Саратов, 2010. - С. 157 - 159.

9. Система автоматизированного проектирования и управления гальваническими процессами / A.C. Попов, Ю.В. Литовка, Г. А. Кириченко, М.А. Попова // Тез. докл. 7 Междунар. конф. «Покрытия и обработка поверхности». - М., 2010. -С. 57-58.

10. Проблемы разработки комплексов программ моделирования и оптимизации гальванических процессов / Ю.В. Литовка, Г.А. Кириченко, М.А. Попова, A.C. Попов // Защитные и специальные покрытия, обработка поверхности в машиностроении и приборостроении : тез. докл. VII Всерос. науч. конф. - Пенза, 2010.-С. 46-48.

11. Свидетельство об официальной регистрации программы для ЭВМ № 2010614479. Система для разработки отладки и тестирования параллельных алгоритмов / A.C. Попов. - 2010.

12. Свидетельство об официальной регистрации программы для ЭВМ № 2010614480. Программа для построения трехмерной модели по двумерному чертежу / A.C. Попов, М.А. Попова. - 2010.

Подписано в печать 17.04.2012 Формат 60 х 84/16. 0,93 усл.-печ. л. Тираж 100 экз. Заказ № 192

Издательско-полиграфический центр ФГБОУ ВПО «ТГТУ» 392000, Тамбов, ул. Советская, д. 106, к. 14

61 12-5/3058

Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Тамбовский государственный

технический университет»

На правах рукописи

Попов Александр Сергеевич

АЛГОРИТМЫ И КОМПЛЕКС ПРОГРАММ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ ПРИ МАТЕМАТИЧЕСКОМ МОДЕЛИРОВАНИИ КРИТИЧНЫХ ПО ВРЕМЕНИ ПРОЦЕССОВ

Специальность 05.13.18 - «Математические модели, численные методы и комплексы программ»

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н., профессор Ю.В. Литовка

Тамбов - 2012

Оглавление

Введение...................................................................................................................3

Глава 1. Обзор систем параллельных вычислений..............................................8

1.1. Среда США...................................................................................................17

1.2. Среда ATI Stream...........................................................................................25

1.3. Среда OpenCL.................................................................................................32

1.4. Выводы............................................................................................................38

Глава 2. Описание методики распараллеливания исходной задачи................42

2.1. Выявление возможности распараллеливания исходной задачи...............43

2.2. Определение оптимальной степени разбиения для задачи.......................45

2.3. Формирование параллельного алгоритма задачи.......................................49

2.4. Проверка адекватности и оценка эффективности алгоритма....................50

2.5. Использование методики подбора вычислителя........................................51

Глава 3. Программный комплекс организации параллельных вычислений... 53

3.1. Модуль ядра.......................................... ...........................................................56

3.2. Вспомогательные модули.............................................................................57

3.3. Библиотеки решаемых задач............................... ...........................................65

Глава 4. Примеры решаемых задач.....................................................................66

4.1. Задача оптимального размещения деталей на подвеске............................67

4.2. Анализ аналогового сигнала.........................................................................79

4.3. Построение трехмерного представления по двумерному

представлению.......................................................................................................85

Заключение..........................................................................................................108

Список использованных источников................................................................110

Приложение А. Справки о внедрении на предприятиях.................................119

Приложение Б. Свидетельства о государственной регистрации программ

для ЭВМ...............................................................................................................121

Приложение В. Внешний вид программы........................................................123

ВВЕДЕНИЕ

Актуальность исследования Рассмотрим общую постановку задач, характерную для данной работы: необходимо решить уравнения исходной математической модели при помощи численного метода, за заданный или меньший интервал времени. Ход решения задачи назовём процессом критичным по времени. Такие задачи часто возникают при организации оптимального управления либо когда время проведения численного эксперимента превышает время проведения физического эксперимента. Для решения таких задач за заданное время могут быть использованы параллельные вычисления. Данный подход оправдан с экономической и с технологической сторон. Параллельные вычисления обычно ассоциируются с суперкомпьютерами и кластерными системами. С распространением многоядерных процессоров и видеокарт с унифицированной шейдерной архитектурой появилась возможность реализовывать параллельные вычисления с помощью персональных компьютеров. Их стоимость на несколько порядков меньше, чем стоимость суперкомпьютеров. Существует ряд задач, которые можно решить на персональных компьютерах в режиме параллельных вычислений, например: распознавание изображений; расчет электрических и магнитных полей в различных средах; анализ аналоговых сигналов в реальном времени и др. Основные исследования проводились такими учеными, как Mark Harris (основоположник направления GPGPU), Sha'Kia Boggan, Daniel M. Pressel, Ryoji Tsuchi-yama, Takashi Nakamura, Takuro Iizuka, Akihiro Asahara, Satoshi Miki, B.B. Воеводин, Вл.В. Воеводин, Б.Н. Четверушкин. Однако исследований в данной области проводилось немного, количество литературных источников сильно ограничено, существует ряд разрозненных статей, большинство из которых носит обзорный характер. Кроме того, нет единой стратегии для применения аппаратных средств с целью эффективного использования их вычислительных ресурсов.

Поэтому создание единой среды для проектирования, реализации и исследования эффективных численных методов для математического моделирования критичных по времени процессов, а также оптимизации использования аппаратных ресурсов с точки зрения вычислительной нагрузки, является актуальной научной и практической проблемой. Работа выполнена в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России 2009 - 2013 годы», государственный контракт №02.740.11.0624.

Объект и предмет исследования. Объектом исследования являются критичные по времени процессы.

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

Цель и задачи исследования - уменьшение времени численного решения на ЭВМ уравнений математических моделей критичных по времени процессов при помощи параллельных вычислений.

Для достижения заданной цели в работе решались следующие задачи:

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

• создание численного метода решения задачи поиска оптимального вычислителя;

• разработка комплекса программ для создания, отладки и тестирования параллельных алгоритмов, на основе задачи определения оптимального вычислителя;

• исследование работоспособности полученного комплекса программ в производственных условиях.

Методы исследования. В диссертационной работе использовались методы математического моделирования, параллельного и объектно-ориентированного программирования.

Научная новизна:

1) Впервые предложена математическая модель для поиска оптимального вычислителя с точки зрения загрузки аппаратных средств отдельно взятой ЭВМ.

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

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

4) Предложена структура и внутренняя организация комплекса программ ЭВМ, реализующая приведенные параллельные и последовательные алгоритмы численных методов, а также предложен подход к созданию параллельных алгоритмов.

На защиту выносятся:

1. Математическая модель поиска оптимального вычислителя с точки зрения загрузки аппаратных средств.

2. Модифицированные математические модели оптимизации процесса нанесения гальванического покрытия, анализа аналогового сигнала с синус-

но-косинусного трансформатора, построения трехмерного представления детали по ее двумерному представлению.

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

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

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

• решение уравнений математической модели распределения электрического поля и модифицированной модели определения оптимального размещения деталей на подвеске в гальванической ванне;

• анализа угла поворота датчика синусно-косинусного трансформатора в реальном времени;

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

Внедрение. Разработанный комплекс программ успешно прошел производственные испытания в ООО «Гранит-М» (г. Уварово Тамбовской области) и принят к использованию при проектировании перспективного гальванооборудования, которое планируется выпускать на этом предприятии. Данный комплекс также принят к использованию в ОАО «Тамбовский завод «Электроприбор» (г. Тамбов) для анализа ряда аналоговых сигналов, поступающих с готовых изделий предприятия, и принятия решения о годности выпускаемой продукции.

Соответствие диссертационной работы паспорту специальности:

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

2. Проведены комплексные исследования разработанных алгоритмов параллельных вычислений с применением современной технологии математического моделирования и вычислительного эксперимента. Пункт 4.

3. Реализованы эффективные численные методы и алгоритмы вычислений уравнений разработанных математических моделей в виде комплекса проблемно-ориентированных программ. Пункт 5.

Апробация работы. Результаты диссертации докладывались и обсуждались на XXI - XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Саратов, 2008, Псков, 2009, Саратов, 2010), 7 Международной конференции «Покрытия и обработка поверхности» (Москва, 2010), на VII Всероссийской научной конференции «Защитные и специальные покрытия, обработка поверхности в машиностроении и приборостроении» (Пенза, 2010).

Публикации. Основные положения диссертации отражены в 12 публикациях, в том числе в 4 статьях в рецензируемых журналах, а также в 2 программах, зарегистрированных в ФИПС.

Глава 1. Обзор систем параллельных вычислений

Литературы по параллельным вычислениям написано достаточно много [1-60], однако в основном она посвящена использованию суперкомпьютеров и вычислительных кластеров, лишь в некоторых изданиях [41, 44-56] описаны способы реализации параллельных вычислений на персональном компьютере, в частности на видеокарте с унифицированной шейдерной архитектурой. На электронном ресурсе [41] содержится множество разрозненных статей по различному применению шейдерной архитектуры, не имеющих однако общей стратегии исследования. На ресурсе [44] в основном отдается предпочтение применению параллельных вычислений на центральном процессоре. В работах [45, 48] основное направление имеет технология ATI Stream, предназначенной для аппаратного обеспечения компании AMD, и лишь немного упоминается технология OpenCL, для гетерогенных вычислительных систем. В работах [46, 47] уделено большее внимание технологии CUD А, для видеокарт фирмы NVIDIA. В работах [46, 50, 51] имеется описание и общие архитектурные принципы OpenCL. В работах [52, 53] описаны общие составления программ под OpenCL, однако нет анализа их работы на аппаратных средствах, и не описаны общие принципы для построения параллельных алгоритмов. Работы [54-56] представляют особый интерес в плане описания развития и становления технологии использования средств видеокарты для решения общенаучных задач (GPGPU), однако они предлагают лишь некоторые основные моменты и ряд примеров реализации параллельных вычислений на видеокарте, ориентированных на программиста. Исходя из вышесказанного, видно, что обобщение подхода к созданию алгоритмов параллельных вычислений на отдельно взятой ЭВМ и их реализация в виде комплекса проблемно ориентированных программ, а также обеспечение оптимальной загрузки вычислительных ресурсов, является неохваченной современной литературой темой.

Тенденции в развитии параллельной архитектуры можно проследить на следующей короткой исторической справке.

- 7 января 2002 года компания Intel представила свой первый процессор Pentium 4 с технологией Hyper-threading [44] (псевдо многоядерность).

- 26 мая 2005 года компания Intel анонсировала свой первый двуядер-ный процессор Pentium D для ПК, это были по сути два процессора Pentium 4, размещенных на одном кристалле, что оказалось неудачной попыткой.

- Июнь 2005 года компания AMD представила первый двуядерный процессор Athlon 64 Х2 [45] для ПК.

- Ноябрь 2006 года Intel Core 2 Extreme [44] - первый 4-х ядерный процессор компании Intel для ПК.

- 8 ноября 2006 года компания NVIDIA [46] анонсировала первую видеокарту с унифицированной шейдерной архитектурой GeForce 8800 GTX\GTS [46] и средство для создания неграфических приложений CUDA [46, 47]} чт0 позволило осуществлять научные вычисления на графическом процессоре. Пиковая производительность для GeForce 8800 GTX — 518,4 Гфлопс (345,6 для GTS). Для процессоров Intel Core 2 Duo 3.0 GHz [44] -примерно 20 Гфлопс. Nvidia GeForce 8800 GTX содержит 8 SIMD [44-47] процессоров, каждый из которых способен выполнять 16 одинаковых операций с разными входными данными параллельно (в модели GTS - 6 SIMD процессоров), всего 128 потоковых процессоров.

- Май 2007 года компания AMD выпустила серию видео карт с унифицированной шейдерной архитектурой Radeon HD 2ХХХ [45] и средство для создания неграфических приложений ATI Stream [48].

- 19 ноября 2007 года AMD Phenom Х4 - первый 4-х ядерный процессор от AMD.

- 23 марта 2010 года компания Cray Inc. [43], лидер на миром рынке суперкомпьютеров, анонсировала запуск новой линейки кластеров СХ1000, предлагающих использовать GPGPU на технологии Tesla компании NVIDIA.

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

Compute Unified Device Architecture (CUDA) - среда создания программ для исполнения на графическом процессоре компании NVIDIA. На основе этой среды строится реализация OpenCL для видеокарт NVIDIA. CUDA представляет собой несколько модифицированный язык С, компилятор для перевода программ на CUDA в байт код, набор средств Runtime для запуска скомпилированных приложений и специализированный драйвер, поддерживающий запуск приложений CUDA.

ATI Stream - среда создания программ для исполнения на графическом процессоре компании AMD. На основе этой среды строится реализация OpenCL для видеокарт и процессоров AMD. Для компиляции используется компилятор Brook+ для расширенного языка С. Для исполнения используется ATI Compute Abstraction Layer (CAL) библиотека драйвера.

- 9 декабря 2008 года Khronos Group [49] утвердила стандарт OpenCL 1.0 [44, 45, 46, 49-53]. OpenCL - среда для написания компьютерных программ, связанных с параллельными вычислениями на различных графических и центральных процессорах. OpenCL разрабатывается и поддерживается некоммерческим консорциумом Khronos Group, в который входят много крупных компаний, включая Apple, AMD, Intel, NVIDIA, Sun, Sony и др.

OpenCL - это платформо-независимый инструмент для реализации параллельных вычислений на различных платформах [61] и вычислительных устройствах. OpenCL предоставляет интерфейс для создания приложений, как для центрального процессора, так и для процессора видеокарт, и в принципе для любого типа процессоров, для которых будет создана реализация интерфейса программирования. OpenCL имеет средства для оценки параметров устройства, необходимые для определения на каком из устройств проводить вычисления в зависимости от аппаратного обеспечения. Основой

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

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

В настоящее время для ра