Содержание к диссертации
Введение
Глава 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
Список использованных источников ПО
- Среда ATI Stream
- Определение оптимальной степени разбиения для задачи
- Проверка адекватности и оценка эффективности алгоритма
- Построение трехмерного представления по двумерному представлению
Введение к работе
Актуальность исследования. Рассмотрим общую постановку задач, характерную для данной работы: необходимо решить уравнения исходной математической модели при помощи численного метода за заданный или меньший интервал времени. Ход решения задачи назовём процессом критичным по времени. Такие задачи часто возникают при организации оптимального управления либо когда время проведения численного эксперимента превышает время проведения физического эксперимента. Для решения таких задач за заданное время могут быть использованы параллельные вьиисления. Данный подход оправдан с экономической и с технологической сторон. Параллельные вычисления обычно ассоциируются с суперкомпьютерами и кластерными системами. С распространением многоядерных процессоров и видеокарт с унифицированной шейдерной архитектурой появилась возможность реализо-вывать параллельные вычисления с помощью персональных компьютеров. Их стоимость на несколько порядков меньше, чем стоимость суперкомпьютеров. Существует ряд задач, которые можно решить на персональных компьютерах в режиме параллельных вычислений, например: распознавание изображений; расчет электрических и магнитных полей в различных средах; анализ аналоговых сигналов в реальном времени и др. Основные исследования проводились такими учеными как Mark Harris (основоположник направления GPGPU), Sha'Kia Boggan, Daniel М. Pressel, Ryoji Tsuchiyama, Takashi Naka-mura, Takuro Iizuka, Akihiro Asahara, Satoshi Miki, B.B Воеводин, Вл.В. Воеводин, Б.Н.Четверушкин. Однако исследований в данной области проводилось немного, количество литературных источников сильно ограничено, существует ряд разрозненных статей, большинство из которых носит обзорный характер. Кроме того, нет единой стратегии для применения аппаратных средств с целью эффективного использования их вычислительных ресурсов.
Поэтому создание единой среды для проектирования, реализации и исследования эффективных численных методов для математического моделирования критичных по времени процессов, а также оптимизации использования аппаратных ресурсов с точки зрения вычислительной нагрузки, является актуальной научной и практической проблемой. Работа выполнена в рамках Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России 2009 - 2013 годы», государственный контракт № 02.740.11.0624.
Объект и предмет исследования. Объектом исследования являются критичные по времени процессы.
Предметом исследования являются математические модели критичных по времени процессов и алгоритмы решения уравнений таких моделей с использованием параллельных вычислений.
Цель и задачи исследования - уменьшение времени численного решения на ЭВМ уравнений математических моделей критичных по времени процессов при помощью параллельных вычислений.
Для достижения заданной цели в работе решались следующие задачи:
— разработка оптимальной, с точки зрения использования вычислительных ресурсов, модели загрузки имеющихся аппаратных средств при использовании параллельных вычислений для решения поставленной задачи за заданное время;
создание численного метода решения задачи поиска оптимального вычислителя;
разработка комплекса программ для создания, отладки и тестирования параллельных алгоритмов, на основе задачи определения оптимального вычислителя;
исследование работоспособности полученного комплекса программ в производственных условиях.
Методы исследования. В диссертационной работе использовались методы математического моделирования, параллельного и объектно-ориентированного программирования.
Научная новизна:
Впервые предложена математическая модель для поиска оптимального вычислителя с точки зрения загрузки аппаратных средств отдельно взятой ЭВМ.
Модифицированы математические модели: для оптимизации процесса нанесения гальванического покрытия (добавлены уравнения, описывающие поиск оптимального размещения деталей на подвеске, с целью получения наименьшей неравномерности), для анализа аналогового сигнала с синусно-косинусного трансформатора (использован частотный фильтр), для построения трехмерного представления детали по ее двумерному представлению (создано более точное преобразование в полигональное представление через рецепторное).
Разработаны эффективные численные методы и алгоритмы решения уравнений модифицированных моделей расчета процесса нанесения гальванического покрытия, анализа аналогового сигнала, построения трехмерного представления детали, адаптированных к применению параллельных вычислений.
Предложена структура и внутренняя организация комплекса программ ЭВМ, реализующая приведенные параллельные и последовательные алгоритмы численных методов, а также предложен подход к созданию параллельных алгоритмов.
На защиту выносятся:
Математическая модель поиска оптимального вычислителя с точки зрения загрузки аппаратных средств.
Модифицированные математические модели оптимизации процесса нанесения гальванического покрытия, анализа аналогового сигнала с синусно-косинусного трансформатора, построения трехмерного представления детали по ее двумерному представлению.
Алгоритмы и численные методы решения уравнений моделей оптимизации нанесения гальванического покрытия, анализа аналогового сигнала с си-нусно-косинусного трансформатора, построения трехмерного представления детали по ее двумерному представлению.
Структура комплекса программ для реализации параллельных вычислений.
Практическая ценность работы состоит в разработке программного комплекса, при помощи которого созданы параллельные реализации следующих алгоритмов:
решения уравнений математической модели распределения электрического поля и модифицированной модели определения оптимального размещения деталей на подвеске в гальванической ванне;
анализа угла поворота датчика синусно-косинусного трансформатора в реальном времени;
построения трехмерного представления детали по ее двумерному представлению, а также задача преобразования рецепторного представления в полигональное.
Внедрение. Разработанный комплекс программ успешно прошел производственные испытания в ООО «Гранит-М» (г. Уварово Тамбовской области) и принят к использованию при проектировании перспективного гальванооборудования, которое планируется выпускать на этом предприятии. Данный комплекс также принят к использованию в ОАО «Тамбовский завод «Электроприбор» (г. Тамбов) для анализа ряда аналоговых сигналов, поступающих с готовых изделий предприятия, и принятия решения о годности выпускаемой продукции.
Соответствие диссертационной работы паспорту специальности:
Разработаны новые математические модели: поиска оптимального вычислителя, оптимизации процесса нанесения гальванического покрытия, анализа аналогового сигнала, построения трехмерного представления детали по ее двумерному представлению. Пункт 1 паспорта специальности.
Проведены комплексные исследования разработанных алгоритмов параллельных вычислений с применением современной технологии математического моделирования и вычислительного эксперимента. Пункт 4.
Реализованы эффективные численные методы и алгоритмы вычислений уравнений разработанных математических моделей в виде комплекса проблемно-ориентированных программ. Пункт 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 наименований и приложений.
Среда ATI Stream
Кроме того, для реализации параллельных вычислений на архитектуре 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. При этом компиляция производится в момент выполнения, для каждого конкретного случая использования, и именно под конкретные устройства вычисления доступные в системе.
Подводя итог, следует отметить, что в настоящее время существует ряд аппаратных средств и программных инструментов для реализации параллельных вычислений, особенностью которых является доступность. Однако систем на базе этих средств еще не разработано, в то время как существует в них необходимость для решения критичных по времени вычислительных задач в режиме реального времени. Таким образом, задача разработки экономичной системы для создания, отладки и тестирования параллельных алгоритмов решения математического моделирования критичных по времени процессов является актуальной.
В настоящее время для расчета моделирования ресурсоемких процессов используются, в основном, суперкомпьютеры. Операционной системой (ОС) для данного вида машин чаще всего служит GNU Linux [62] и другие ОС семейства Unix. При этом компьютером, на котором разрабатывается программа для решения искомой задачи, является обычный персональный компьютер (ПК). Пользователь реализует алгоритм на своем компьютере, компилирует его и отсылает на исполнение суперкомпьютеру через локальную сеть по одному из стандартных сетевых протоколов, зависящих от предпочтений организации, в которой установлен суперкомпьютер. После отправки скомпилированный алгоритм становится в очередь на исполнение. Когда подходит его очередь, он запускается и исполняется. При этом, если превышается лимит времени, отведенный конкретному пользователю, процесс останавливается, а пользователю приходит уведомление, что его процесс не уложился в отведенное для исполнение алгоритма время. Если же процесс завершается раньше установленного срока, то пользователю отправляются результаты вычислений. По результатам, полученным от суперком пьютера, пользователь должен определить, насколько правильно исполнился его алгоритм, и при удачном его исполнении оценить полученные результаты, при неудачном - приходится переписывать алгоритм. Ввиду длительности ожидания ответа от удаленного суперкомпьютера, ограниченности выходной информации и отсутствия средств удаленной отладки (так как не предоставляется возможности монопольного использования суперкомпьютера, обычно организации приобретают его в единственном экземпляре для работы множества пользователей), разработка программной реализации подобного алгоритма является весьма трудоемкой задачей.
Еще одним вариантом организации параллельных вычислений являются вычислительные кластеры. Кластер - это набор обычных компьютеров, объединенных локальной сетью. Различают дорогие высокопроизводительные кластеры: объединение компьютеров идет по высокоскоростному каналу, и, относительно недорогие, основанные на технологии Beowulf [41], объединенные в обычную локальную сеть типа Ethernet, Myrinet, InfiniBand или аналогичную. Стоимость дорогих решений примерно на порядок меньше аналогичных решений с использованием суперкомпьютеров, однако также является весьма существенной. Стоимость такого решения составляет порой стоимость не одного десятка, а иногда нескольких сотен персональных компьютеров, плюс стоимость организации локальной сети. При этом производительность подобных систем является относительно невысокой. Еще одним недостатком недорогих кластерных решений является существенная, по отношению к скорости работы отдельных узлов, коммуникационная задержка между элементами кластера. Данная задержка обусловлена относительно медленными каналами локальной сети, связывающими компьютеры. Это накладывает определенное ограничение на реализуемый параллельный алгоритм. В частности, задача должна быть разбита таким образом, чтобы расчет отдельных ее элементов превышал временные расходы на прием исходных данных и передачу результатов вычислений для некоторых задач, опери рующих большими объемами данных, и относительно несложными вычислениями. Это может стать узким местом и свести на нет ускорение работы алгоритма при использовании вычислительного кластера. У этого подхода есть еще один серьезный недостаток: задачи, поступающие на рассмотрение и решение, имеют, в основном, фундаментальный характер, то есть задача решается однократно, а потом долгое время анализируются результаты, полученные в ходе моделирования. Для задач, которые требуют постоянного многократного решения, приходится выделять отдельный суперкомпьютер, что во многих случаях нецелесообразно, как с экономической точки зрения, так и с точки зрения использования его ресурсов. Однако, в некоторых случаях, даже ресурсов суперкомпьютера не хватает на периодическое решение поставленной задачи, как, например, анализ метеорологических, астрономических и других объемных данных. Задачи же повседневного характера, хоть и меньшей размерности, но требующие периодического вычисления, решать с использованием суперкомпьютеров нецелесообразно, как с экономической точки зрения, так и с точки зрения слабого использования ресурсов суперкомпьютера, а с использованием ПК слишком долго.
Определение оптимальной степени разбиения для задачи
Этот модуль отвечает за загрузку и сохранение структурированных данных из файлов настройки. Формат хранения настроек является стандартным текстовым конфигурационным файлом "ini". При необходимости, возможно вручную исправить данные, хранящихся в нем настроек в любом текстовом редакторе. Есть поддержка хранения целых чисел в различных форматах (16-ричный, 8-ричный, 10-тичный, двоичный), для дробных чисел используется формат double (число с плавающей запятой двойной точности) при считывании данных из файлов. Также возможно хранение текстовых строк в различных кодировках, при этом её необходимо указывать отдельным полем. Существует возможность ассоциировать переменные с полями структуры настроек, при этом в момент сохранения настроек считываются текущие значения переменных, для ассоциирования данных предложен широкий набор типов данных, включающий целые знаковые и без знаковые числа размерностью 8, 16, 32 и 64 бита, числа с плавающей запятой размерностью 32, 64 и 80 бит, строки в ASCII кодировке и в юникод кодировках UTF-8, UTF-16, UTF-32. Это облегчает хранение изменяемых настроек, избавляет от необходимости в библиотеке при сохранении повторять операцию обмена с переменными обратную операции сделанной при открытии.
Данный модуль предоставляет интерфейс для загрузки и сохранения полученных данных в разнообразные форматы. Также реализует несколько возможных механизмов сохранения, таких как сохранение в файловую систему, либо сохранение в базу данных. В качестве основной базы данных была выбрана СУБД MySQL. Также пользователь может реализовать метод сохранения/загрузки и передать соответствующий интерфейс данному модулю. Модуль также имеет возможность определения параметров входных данных без их полной загрузки, что позволяет выбирать конкретный набор данных и загружать только его для файлов, поддерживающих множество наборов дан ных в одном контейнере. В данном модуле присутствует интерфейс, позволяющий переводить запись углов из десятичного формата в формат градусов, минут и секунд. Основные форматы, работа с которыми реализована в данном модуле: формат wav - стандартный формат звуковых данных; формат par/dat - формат для хранения аналоговых сигналов, разработан фирмой ЗАО «Л-Кард» [72]. Поддерживаются версии формата 1, 1А, 2. Par файл содержит настройки аналого-цифрового преобразователя(АЦП), его название, дату проведения испытания и некоторую служебную информацию в зависимости от версии формата, dat файл содержит данные в двоичном формате, данный формат неизменен для всех версий формата; формат txt - текстовый формат файла, содержащий описание хранимых в нем данных и сами данные, в текстовом формате, здесь также сохраняются все настройки, используемые при съеме сигнала; формат ogg - контейнер для хранения сжатых с потерями звуковых данных, формат Vorbis [73]. Данный контейнер поддерживает хранение сопутствующей информации для звуковых данных. Поля информационной структуры используются для хранения информации об устройстве съема сигнала в формализованном виде; формат пас - контейнер для хранения сжатых без потерь звуковых данных [73], поддерживает несколько потоков в одном файле, позволяет хранить информацию о записанных данных, информационные поля в этом файле имеют такую же структуру, как и в предыдущем случае; формат ucd - контейнер для хранения разнообразных данных поддерживает хранение множества наборов данных в одном файле. Данные могут быть аналоговым сигналом, многомерным массивом или трехмерной моделью. Данные в этом формате сжимаются при помощи алгоритма Lempel-Ziv-Markov chain-Algorithm (LZMA), формат позволяет хранить текстовые данные для каждого из наборов: текстовые данные в формате UTF-16; числовые данные в формате 64-битного целого (int64_t), либо в виде 64-битного дробного числа с плавающей точкой (double). Также для варианта хранение данных, поступающих с АЦП, есть возможность хранения настроек, при которых был произведен съем сигнала, и название устройства, с помощью которого производился съем аналогового сигнала.
Кроме возможности сохранения и загрузки файлов, модуль имеет функциональность, позволяющую отображать стандартные диалоговые окна операционной системы. Модуль позволяет отображать диалоговое окно открытия/сохранения, печати, выбора директории, выбора шрифта. Кроме стандартных диалогов, присутствует собственный для варианта открытия/сохранения, он отображает информацию о файлах, не открывая их. Такая информация представляет собой время проведения испытания, количество испытаний для варианта с множеством экспериментов в одном файле, с отображением всех этих экспериментов при выборе конкретного файла. Также отображается дополнительная текстовая информация описательного характера при наличии ее в файле, данный диалог одинаково подходит как для работы с файловой системой, так и для работы с базой данных. В базе данных каждый эксперимент может храниться, как в виде отдельной записи, так и в виде серии экспериментов под одной записью, основная структура базы данных похожа на используемую во внутреннем формате программного комплекса структуру, для сжатия данных применяется алгоритм LZMA.
Алгоритм LZMA разрабатывается с 2001 года и используется в архиваторе 7-Zip [71] для создания архивов в формате 7z. Алгоритм основан на схеме сжатия данных по словарю, сходной с используемой в LZ77, и обеспечивает высокий коэффициент сжатия, а также позволяет использовать словари различного размера, вплоть до 4 Гб. Данный алгоритм был выбран из-за его достаточно высокой степени сжатия, а также благодаря его открытости для программистов.
Модуль содержит набор функций, позволяющий сжимать входной поток произвольных данных, при этом задается степень сжатия, размер словаря и количество параллельных процессов для реализации процесса сжатия. На выходе получаем сжатые данные со словарем и идентификационными данными необходимыми для распаковки. Поэтому, при распаковке передаем поток сжатых данных, на выходе получаем исходный не сжатый поток, кроме того можем посмотреть настройки, с которыми были сжаты эти данные. Алгоритм является асинхронным и распаковка происходит гораздо быстрее.
Проверка адекватности и оценка эффективности алгоритма
В этом алгоритме имеем три этапа: 2-5, 7- 10и 11 -13, на первых двух этапах имеем по две подзадачи, на третьем - одну. Внутри этапов подзадачи не связаны, т.е. условия (2.1) - (2.7) выполняются, между этапами возникают зависимости класса (2.1) - (2.4). На первом и втором этапах имеем 2 N несвязанных подзадач, на третьем N подзадач. Соотношение последовательных вычислений к параллельным составляет около 0,5 %. Требуемое время анализа сигнала длительностью 1 с составляет порядка 100 - 200 мс. Для проверки устойчивости метода были использованы различные частоты дискретизации при снятии аналогового сигнала 90... 110 кГц.
Разбиение для ЦП всегда происходит на равное количеству процессоров (ядер) число задач. При этом необходимо помнить, что снятие сигнала идет отдельным потоком, и, желательно, не нагружать это ядро другими задачами. В данном случае, подразумевается использование еще одного ядра для этих целей. Для варианта решения на видеокарте подзадачи запускаются в представленном виде без дополнительного объединения. Кроме того, рассмотрим использование контрольного примера для выбора оптимального вычислителя и оптимального разбиения, и сравним теоретические варианты разбиения с реальными замерами времени на конкретном персональном компьютере.
Для получения динамики изменения угла поворота за 1 с получаем: последовательный алгоритм-3,1 с; для разбиения на центральном процессоре (2 ядра) - 1,9 с, ускорение в 1,63 раза, эффективность 82 %, теоретическое ускорение в 1,98 раза; для разбиения на видеокарте 96 вычислителей (8 SIMD блоков 16 потоков в данных каждом) GeForce 8800GTS - 50 мс, ускорение в 62 раза, эффективность 65 %, теоретическое ускорение в 66 раз.
При решении контрольного примера (исходная задача со сниженной размерностью) с помощью математической модели подбора оптимального вычислителя было выяснено, что для центрального процессора оптимальным является разбиение на две подзадачи, так как на процессоре работает одновременно множество потоков, необходимых для работы операционной сис темы, и переключение между потоками дополнительно нагружает ЦП, что подтверждает теоретические исследования.
При реализации задачи на видеокарте оптимальным оказалось разбиение на элементарные этапы алгоритма, управление выполнением которыми осуществляет аппаратно реализованный внутренний менеджер задач. Последовательная реализация была использована для сравнения относительного ускорения работы алгоритма, а также для сравнения полученных результатов, что дало возможность оценить правильность работы параллельной реализации.
Для разбиения на ЦП, полученные результаты оказались абсолютно идентичными для различных разбиений (разбиение производилось на одну, две,..., шесть подзадач). При разбиении задачи на видеокарте результаты были также схожи с учетом погрешности реализации математических операций, разность значений была примерно в 6 - 7 знаке после запятой для чисел с плавающей запятой, максимальные различия чисел наблюдаются в области «нулевых» значений, это связанно с особенностью представления дробных чисел в компьютерной технике.
Таким образом, при использовании алгоритма выбора оптимального вычислителя, была выбрана видеокарта, так как ограничивающее минимальное время обработки было выбранным Тзад=\00 мс, а требованиям по меньшему времени удовлетворяет только видеокарта.
Задача построения трехмерного представления детали по ее двумерному представлению [89-91]. Рассмотрена модификация численного метода преобразования двумерного представления детали в трёхмерное представление, предложенное в работе [89] Поповой М.А. Модификация состоит в введении дополнительного этапа преобразования в рецепторное представление, а затем в итоговое полигональное представление. В результате введения дополни тельного этапа удается сократить количество полигонов в итоговом представлении. Для примера при использовании сетки 100x100 и преобразовании представления куба из двумерного представления в трёхмерное получаем: для не модифицированного метода 58806 полигонов, для модифицированного - 12 полигонов. Адекватность метода подтверждена применением его для ряда представлений, с известным как двумерным, так и трёхмерным видами.
Необходимо определить геометрическое место точек, для задания поверхности результирующего трехмерного представления детали в полигональном виде: PfeiMJi, х2,у2 2, хъуг ъ), i=l,2,...,N. где Pt і-и полигон (в качестве полигонов используются треугольники), N -количество полигонов в итоговом представлении, при котором результирующее трехмерное представление, с заданной точностью, определяемому шагом трехмерной сетки, будет соответствовать исходному двумерному представлению, используемому при нахождении точек поверхности детали. При заданном исходном представлении в виде: Vj(Xuy\ uX2,y2 2), У=1,2,...,М где Vj - отрезок исходного векторного двумерного представления детали, М- количество отрезков. Пример исходных данных, на котором будут рассмотрены детали алгоритма, изображен на рисунке 4.6.
Для промежуточного этапа хранения данных разработана модифицированная математическая модель геометрии, состоящая из рецепторного трехмерного представления объекта, сопряженного с векторным представлением: D(x, у, z) - матрица, элементы которой определяются как: r 1, если это внутренняя точка объекта, {набор отрезков}, если это граничная точка объекта, О, для всех остальных точек. Размерность матрицы совпадает с количеством шагов сетки. Данные вводятся из файла в формате DXF (формат редакторов AutoCAD, nanoCAD, QCAD и т.д.), G2D (текстовый формат) или во внутреннем формате системы. Входные данные представляют собой набор отрезков, из которых состоит чертеж детали (дуги, эллипсы и окружности заменяются набором отрезков), у каждого отрезка имеется параметр, определяющий тип линии (1 - основная линия, 2 - невидимая линия).
Построение трехмерного представления по двумерному представлению
Рассмотрим цикл 5-16, каждая итерация которого не связанна с другими (выполняются условия (2.1) - (2.7)). Внутри этого цикла имеем три этапа для нормалей Nx, Ny и Nz, связанных между собой условиями типа (2.5) - (2.7). На каждом этапе имеем цикл с несвязанными подзадачами для определения точек пересечения с нормалями, так как нормаль однозначно определяет две координаты точки в выходном массиве, условия класса (2.5) -(2.7) соблюдаются.
Для куба описанного вокруг детали размерами 10x10 см, в каждом из направлений OX, OY и 02, а также шага сетки ОД см имеем матрицу векторов 100x100, при этом нужно найти пересечения каждого из данных векторов с отрезками двух проекций и определить вхождение данной точки внутрь третьей проекции. То есть, имеем три последовательных этапа, каждый из которых имеет размерность 100x100. Соотношение последовательных к параллельным вычислениям здесь составляет меньше одного процента, по этому для закона Амдала примем его равным нулю, хотя это и не совсем так. Устойчивость метода проверялась с использованием сетки 80...120 шагов, результаты исследования позволяют говорить об устойчивости метода.
Также как и в предыдущих примерах для ЦП используем разбиение на две подзадачи, для видеокарты, разбиение на максимальное количество подзадач. В качестве тестового примера используется задача для более простой детали (куб) с применением меньшего шага сетки, этот пример будет служить для анализа работы алгоритма выбора оптимального вычислителя, а также для подбора оптимального вычислителя и оптимального разбиения для различных аппаратных архитектур. Рассмотрим построение трехмерного представления заданного примера: последовательный алгоритм - 36,391 с; разбиения на центральном процессоре (2 ядра) - 19,04 с, ускорение в 1,91 раза, эффективность 95 %, теоретическое ускорение в 2 раза; для разбиения на видеокарте 96 вычислителей (8 SIMD блоков 16 потоков в данных каждом) GeForce 8800GTS - 420 мс, ускорение в 86,65 раза, эффективность 90 %, теоретическое ускорение в 96 раз.
Как и в рассмотренных выше примерах при решении контрольного примера оптимальным для центрального процессора является разбиение на две подзадачи, для видеокарты - на максимальное количество подзадач.
В ходе анализа результатов работы различных разбиений на различных вычислительных устройствах также была подтверждена правомерность разбиения на подзадачи с получением схожих с достаточной точностью результатов. Тзад взято равным 1 с. В результате за оптимальный вариант разбиения и исполнения принята видеокарта.
Во всех приведенных выше примерах целесообразность применения альтернативных вычислителей очевидна, кроме того, был рассмотрен лишь малый круг задач, для которых существует необходимость ускорения исполнения. К тому же, последние несколько лет были выпущены более производительные видеокарты, предоставляющие большее количество вычислителей и, соответственно, большую степень параллелизма реализуемых задач. Так как теоретическая степень разбиения рассмотренных, а также многих других задач, достаточно высока, то с появлением новых аппаратных средств появится возможность еще быстрее решать эти задачи, без необходимости их переделывания, достаточно просто запустить алгоритм подбора оптимального вычислителя, который определит степень разбиения и вычислитель.
Разработанный программный комплекс предоставляет среду проектирования и реализации параллельных алгоритмов. Максимально получилось ускорить вычисления, при параллельном режиме работы, примерно в 87 раз. Наиболее уязвимым местом данной системы является достаточно молодой стандарт OpenCL, поддержка которого еще не до конца отработана и реализована на всем спектре вычислительных средств, существующих в наше время. Однако стандарт с момента своего появления получил мощный импульс развития и теперь бурно развивается, что позволяет предполагать появление в ближайшее время большого количества его реализаций. Затраты на аппаратное обеспечение для данной системы минимальны и составляют стоимость персонального компьютера с современной видеокартой, для тех кому недостаточно этой производительности, можно использовать решения на основе технологий NVIDIA SLI [46] или ATI CrossFire [45], которые позволяют объединять несколько видеокарт в одном компьютере. При этом стоимость возрастает примерно в полтора раза. Еще большую производительность можно добиться установкой специализированного вычислителя, например, NVIDIA Tesla. Подобные вычислители имеют стоимость, примерно, как два персональных компьютера. В любом случае, поиск решения на подобного рода вычислителях оказывается дешевле, чем на дорогих суперкомпьютерах и вычислительных кластерах. Также следует отметить, что многие предприятия, на которых есть потребность в подобных вычислениях, не могут позволить себе приобретение суперкомпьютеров, и им приходится пользоваться экспериментальным путем (как например, оптимизации процесса нанесения гальванического покрытия). Данный подход является весьма затратным, как по времени, так и по финансовым вложениям (конечно, менее затратным, чем приобретение суперкомпьютера, но все же гораздо дороже численного эксперимента), что ведет к удорожания готовой продукции, и к более низкому ее качеству, так как при проведении экспериментов невозможно оценить все возможные варианты, исследуются только наиболее интересные с теоретической точки зрения эксперименты, которые необязательно дадут оптимальное значение, а только лишь приближенное к оптимальному.
В процессе исследования были получены следующие результаты:
1. Разработанные эффективные численные методы для решения уравнений модифицированных математических моделей позволяют ускорить вычисления для расчета: электрического поля в гальванической ванне, построения трехмерного представления детали по двумерному представлению, угла поворота датчика синусно-косинусного трансформатора в 83, 87 и 62 раза соответственно.
2. Реализованная модель определения эффективного разбиения и подбора вычислителя позволяет выбрать оптимальную с точки зрения загрузки вычислительную платформу, что ускоряет и упрощает процесс разработки параллельных алгоритмов.
3. Разработан комплекс проблемно ориентированных программ для реализации параллельных алгоритмов, позволяющий создавать, модифицировать и использовать готовые программные решения.
4. Практическая ценность результатов, полученных в диссертационном исследовании, подтверждена актами внедрения в работу на предприятиях ООО «Гранит-М» и ОАО «Тамбовский завод «Электроприбор».
