Курсовая работа (т): Изучение возможностей массивно-параллельных вычислений в применении к задачам математической физики

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

СОДЕРЖАНИЕ

Введение

. Литературный обзор

. Методы и методики исследований

. Задача о малых колебаниях

.1 Постановка задачи. Вывод уравнения

3.2 Решение задачи методом Фурье

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

.1 Дискретный подход к вычислению коэффициентов

.2 Быстрое преобразование Фурье и библиотека CUFFT

4.3 Реализация FFT для задачи о колебаниях струны и мембраны

. Вычисление методом Лежандра-Гаусса

.1 Квадратуры Лежандра-Гаусса

.2 Расчет узлов и весовых коэффициентов

.3 Реализация на С

. Параллельный расчёт амплитуд

.1 Массивно-параллельный расчёт амплитуд

.2 Оценка выигрыша во времени

Заключение

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

Приложение

ВВЕДЕНИЕ

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

Одной из главных характеристик любого вычислительного устройства является его быстродействие. Для оценки производительности компьютеров обычно используется единица flops (от английского Floating Point Operations per Second), показывающая количество операций с плавающей запятой в секунду, которое выполняет оцениваемая вычислительная система.

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

Сегодня принято относить к суперкомпьютерам системы с пиковой мощностью более 10 Терафлопс (среднестатистический современный персональный компьютер несёт в себе производительность порядка 0.1 Терафлопс). На самом деле реальное быстродействие всегда оказывается заметно ниже пикового /2/.

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

Кроме того, для некоторых задач последовательные архитектуры обработки становятся неэффективными при увеличении тактовой частоты в связи с существованием так называемого «фон-неймановского узкого места» в канале пересылки данных между центральным процессором и памятью, что ведёт к ограничению производительности при последовательном потоке вычислений /6/.

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

Максимальное ускорение, которое можно получить от распараллеливания программы на N процессоров, дается законом Амдала /2, 7/:

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

Цель работы

Изучение возможностей массивно-параллельных вычислений в применении к задачам математической физики.

Задачи исследований

Для достижения указанной цели были поставлены следующие задачи:

) построение оптимального алгоритма параллельного расчета при решении задач о колебаниях струны и мембраны с использованием технологии NVIDIA CUDA;

) вычисление коэффициентов с помощью алгоритмов быстрого преобразования Фурье средствами библиотеки CUFFT;

) параллельное вычисление коэффициентов методом квадратур Лежандра-Гаусса;

) визуализация задачи с использованием библиотеки OpenGL;

) сравнительный расчёт времени вычисления.

1. ЛИТЕРАТУРНЫЙ ОБЗОР

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

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

В то же время настоящая революция произошла в области обработки графических данных. В начале 90-х рост популярности графических операционных систем дал толчок для создания рынка процессоров нового типа - 2D-ускорителей, которые позволяли выполнять аппаратно операции с растровыми изображениями, что способствовало повышению качества отображения /10/.

Вообще термин «графический процессор» (GPU, Graphics Processing Unit) по легенде был впервые использован корпорацией Nvidia. Сейчас современные GPU представляют из себя массивнопараллельные вычислительные устройства с очень высоким быстродействием (свыше одного терафлопа) и большим объемом собственной памяти /2/.

Всё началось с Voodoo Graphics - графического ускорителя, созданного в 1995 году компанией ЗDFх, простого растеризатора, переводящего треугольники в массивы пикселов, который получал на вход уже спроецированные центральным процессором вершины. Этот незамысловатый ускоритель мог обрабатывать до одного миллиона полигонов и выводить на экран до сорока пяти миллионов пикселей в секунду, тем самым легко обгоняя CPU. Причина такой производительности кроется в одновременности обработки пикселов. Это, собственно, и привело к широкому распространению графических ускорителей ЗD графики.

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

Быстрая эволюция графических процессоров после появления Voodoo привела к созданию ускорителей, которые могли самостоятельно обрабатывать вершины и накладывать текстуры. Выпуск карты GeForce 256 компанией NVIDIA способствовал расширению возможностей GPU в еще большей степени, теперь графические процессоры умели совершать геометрические преобразования, рассчитывать освещение сцены и выполнять некоторые другие несложные, но весьма полезные операции. /2, 21/

Если же рассматривать развитие GPU с точки зрения параллельности вычислений, то самым большим прорывом стал выпуск в 2001 году GeForce 3 - процессора, отвечавшего тогда еще только появившемуся стандарту Microsoft DirectX 8.0, согласно которому графическое оборудование должно было предоставлять возможность программируемой обработки вершин. Фактически это значило, что разработчики программного обеспечения получили возможность самостоятельно решать, какие именно типы расчетов будут производится на видеокарте.

Вообще основным назначением GPU в начале 2000-x было вычисление цвета отдельного пикселя с помощью так называемых пиксельных шейдеров. На вход пиксельного шейдера подаются координаты точки и набор дополнительных данных, таких как начальный цвет, текстурные координаты или прочие атрибуты, а на выходе получается цвет этой точки. Но так как всякая арифметика, производимая над входными параметрами, теперь полностью определялась программистом, в роли цвета могли выступать любые данные. Так, если входные данные имели числовой тип, то программист мог написать шейдер, который выполнял бы над ними произвольные операции.

Так графические ускорители превратились в SIМD-процессоры. SIMD (Single Instruction Multiple Data) или векторный процессор - это параллельный процессор, в котором операндами некоторых команд могут выступать упорядоченные массивы данных - векторы, в отличие от скалярных процессоров, которые могут работать только с одним операндом в единицу времени. SIМD-процессор получает на вход поток однородных данных и параллельно выполняет над ними одну и ту же инструкцию. Возникло абсолютно новое в программировании направление - GPGPU (General Purpose Computing on Graphics Processing Units, GPU общего назначения) - техника использования графических процессоров для решения не связанных с графикой задач, решением которых обычно занимается центральный процессор. /10, 21/

Скорости вычисления на GPU были гигантскими, однако модель программирования значительно ограничивалась рамками стандартной задачи рендеринга. Входные параметры обязательно должны были быть приведены к формату цветов или текстурных блоков, кроме того, не поддерживались операции с памятью типа scatter, позволяющие записывать данные в произвольные ячейки. Было сложно предугадать поведение GPU в отношении чисел с плавающей точкой. И, самое главное - «общение» разработчика с графическим процессором осуществлялось исключительно посредством одного из графических интерфейсов программирования приложений (API, Application Programming Interface), в числе которых были OpenGL и DirectX, поскольку никакого другого способа взаимодействия с видеокартой не существовало. Это означало, что программист должен был обладать навыками в написании программ на шейдерных языках, что было достаточно неудобным условием.

В ноябре 2006 года компания NVIDIA анонсировала серию графических акселераторов GeForce 8, базирующихся на архитектуре CUDA (Compute Unified Device Architecture). Эта новая архитектура включала в себя особую шейдерную доработку, которая позволяла каждому арифметически-логическому устройству (ALU, Arithmetic Logic Unit) в микросхеме быть использованным при вычислениях общего назначения в соответствии со стандартом чисел одинарной точности. Кроме того, CUDA обеспечивала произвольный доступ к памяти и к программно-управляемому кэшу, так называемой разделяемой памяти (shared memory).

Позже, чтобы облегчить процесс программирования, компания NVIDIA создала специальный язык CUDA C. По своей сути, это расширение стандартного языка C, содержащее в себе новые функции, обеспечивающие взаимодействие с архитектурой CUDA. Помимо этого языка был также предложен специальный драйвер, который позволил избежать «общения» с видеопроцессором через графические API и уйти от представления общей задачи в формате задачи рендеринга. /10/

CUDA базируется на том соображении, что графический процессор (в среде GPGPU называемый также устройством, device) может служить сопроцессором к CPU (host). Программа, написанная на языке CUDA C использует и графический, и центральный процессоры, и последовательный код выполняется CPU. За распараллеленную часть вычислений отвечает видеокарта.

Всякое GPU, выпускаемое NVIDIA, включает в себя нескольких кластеров текстурных процессоров. Каждый такой кластер - это текстурный блок и два или три потоковых мультипроцессора. Мультипроцессоры, в свою очередь, содержат до восьми вычислительных устройств, а также два функциональных блока. Одна операция одновременно выполняется всеми потоками в варпе (warp). Варп - это группа, включающая 32 потока-нити, минимальное количество потоков, которое обрабатывают мультипроцессоры. По аналогии с SIMD такой способ обработки назвали SIMT (Single Instruction Multiple Threads).

Мультипроцессор обладает шестнадцатью килобайтами разделяемой памяти, которая позволяет обмениваться данными потокам, которые исполняются им. Потоки, исполняемые разыми мультипроцессорами, взаимодействовать друг с другом не могут, это одна из особенностей архитектуры /10, 12, 13/.

Функция, выполняемая видеокартой, обычно называется ядром (kernel). Каждый параллельно выполняемый экземпляр ядра получил название блока (block); всякий блок исполняется только одним мультипроцессором, но мультипроцессор может исполнять несколько блоков. Блоки обычно дробятся на потоки - нити (threads). В силу особенностей разделяемой памяти обмениваться данными могут только нити одного блока. Все блоки и их нити объединяются в сетку (grid), которая может быть одно- и двумерной. Блоки по отношению к нитям также могут иметь несколько измерений (до трёх включительно). В настоящее время существуют аппаратные ограничения на количество нитей в блоке - до 512 (всего) и на количество блоков в сетке - до 65535 (по каждому измерению).

Файлы программ, написанных на CUDA C, имеют расширение *.cu, и могут содержать в себе как функции, выполняемые CPU, так и функции-ядра. Для их разграничения в языке существуют особые спецификаторы: служебное слово  перед названием функции указывает на то, что она будет выполнятся GPU и вызываться может только из GPU. Спецификатор  означает полную принадлежность функции к центральному процессору. А для того чтобы обеспечить запуск фрагмента, выполняемого видеокартой, с CPU используется спецификатор .

На функции, исполняемые графическим процессором, накладывается ряд определённых ограничений. В частности, не разрешается брать адрес -функций, не поддерживается рекурсия и внутренние переменные типа static. Также все функции, исполняемые GPU, должны иметь строго постоянное число аргументов. /2/

Вызов функции-ядра  осуществляется при помощи синтаксического правила:

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