Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров




Скачать 220.5 Kb.
НазваниеАппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров
страница3/3
Дата03.10.2012
Размер220.5 Kb.
ТипДокументы
1   2   3

ИСПОЛЬЗОВАНИЕ ГРАФИЧЕСКИХ УСКОРИТЕЛЕЙ ДЛЯ ОБЩЕМАТЕМАТИЧЕСКИХ ВЫЧИСЛЕНИЙ

Пантюхин Д.В.

ФГУП НИИ автоматической аппаратуры им. академика В.С. Семенихина

E-mail: neurocomputer@yandex.ru

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

Среди многоядерных процессоров в настоящее время наибольший интерес представляют современные графические процессоры и многоядерный процессор CELL, разрабатываемый фирмами IBM, Sony Group, Toshiba. В последнее десятилетие наблюдается стремительное развитие графической аппаратуры или GPU (Graphics Processing Unit). GPU имеют привлекательную архитектуру, которая характеризуется высокой степенью параллелизма и относительно низкой стоимостью. Используя массивный параллелизм и векторные процессоры, новые графические устройства существенно превышают вычислительные возможности центральных процессоров современных компьютеров. Следствием этого явилось возрастание интереса для выполнения на GPU вычислений общего характера, получившего название GPGPU (General Purpose Graphics Processing Unit).

Требования компьютерной игровой индустрии привело к разработке более быстрых и совершенных архитектур GPU. Исходя из специализации GPU и повышенных требований к быстродействию, GPU вынуждены обладать большими вычислительными ресурсами по сравнению с обычными CPU. Современные GPU (например, NVIDIA GeForce 7800 GTX) содержат 302 миллиона транзисторов по сравнению с Intel P4 Nortword CPU – 50 млн. транзисторов.

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

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

Области использования общематематических графических вычислений. Существует множество публикаций по рассматриваемой теме, многие работы доступны в Internet. Использованы материалы веб-сайта www.gpgpu.org, на котором есть также ссылки на оригинальные работы. Поскольку это англоязычный ресурс, мы надеемся, что данная работа окажется полезной русскоязычным разработчикам высокопроизводительных вычислительных средств на базе графических процессоров.

Ниже перечислены некоторые области знаний и методы, которые были эффективно реализованы на GPU:

  1. Линейная алгебра

    1. LU-разложение;

    2. Решение разряженных систем линейных алгебраических уравнений;

    3. Решение плотных систем;

    4. Матричное умножение;

    5. Линейное программирование.

  2. Обработка сигналов

    1. Быстрое преобразование Фурье;

  3. Обработка изображений;

  4. Математическая физика;

    1. Моделирование потоков жидкостей и газов;

    2. Моделирование поведения твердых тел;

  5. Биология;

  6. Нейронные сети;

  7. Эволюционные алгоритмы;

  8. Поиск в базах данных;

  9. Оптимизация кода.

Для решения задач линейного алгебры на графических процессорах предложено множество работ. В них рассматривается широкий спектр задач линейной алгебры, начиная от матрично-матричного умножения [1-3] и задач линейного программирования [4], до решения разряженных [5-6] и плотных [7-9] систем линейных уравнений. В работах [10-11] рассматриваются общие принципы решения задач линейной алгебры на графических процессорах.

Большое количество работ посвящено решению задач математической физики [12-30]. Моделирование потока жидкости или газа [12-20], процесса передачи теплоты [21], диффузии [25], или поведения твердых тел [26-27] при использовании графических процессоров дает значительный прирост эффективности вычислений. Отдельно отметим работы по моделированию роста кристаллов [28], работы нефтехранилища [29] и полета птиц [30].

В процессе обработки сигналов также применяют графические процессоры для ускорения вычислений. Быстрое преобразование Фурье [31-32] на графическом процессоре выполняется в несколько раз быстрее, чем на центральном процессоре и в то же время гораздо дешевле в реализации.

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

В [36] описана реализация метода Монте-Карла на графических процессорах. А в [37] рассматривается создание высокопроизводительного кластера из графических процессоров.

Наконец, в [38] приводится описание применения графических процессоров для реализации нейронной сети Кохонена. В [39] описывается многослойный персептрон, выполненный на GPU для аппроксимации комплексной световой модели. В [40] описывается реализация нейросетевого алгоритма на GPU, ускоряющего его работу в 20 раз, по сравнению с его работой на CPU (Pentium IV).

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

  • Cg – по синтаксису подобен языку С для обычных процессоров.

  • Brook – этот язык представляет графические вычисления как операции над потоками данных, способен генерировать код в Cg и С++.

  • Sh – так же язык потокового программирования, разработан как надстройка над C++.

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

  • Освобождение центрального процессора для других целей (GPU используется как сопроцессор).

  • Существенное ускорение «длинных» операций, обладающих выраженным параллелизмом.

  • Более быстрое развитие и появление новых видов графических процессоров в сравнении с CPU.

  • Более низкая стоимость графического ускорителя по сравнению с CPU.

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

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

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

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

  • Необходимость использование языков программирования низкого уровня для эффективной реализации алгоритмов и связанная с этим меньшая переносимость программ. Эта проблема исчезает по мере развития языков программирования более высокого уровня (Cg, Brook и т.д.).

Самостоятельные эксперименты. Для проверки высказанных положений на языке Brook был реализован метод бисопряженных градиентов для решения плотных систем линейных алгебраических уравнений. Непосредственное эффективное использование этого метода возможно для систем размерностью 1024*1024, когда матрица системы целиком помещается в видео память. Эксперименты показали, что скорость вычислений (количество выполняемых итераций в секунду) по сравнению с тем же алгоритмом на CPU увеличилась в 3-4 раза (в зависимости от размерности решаемой системы). Однако, в силу неполной поддержки вычислений с плавающей точкой, итеративные процессы на CPU и GPU различались, и в некоторых случаях итеративный процесс на GPU не сходился. В настоящее время делаются попытки создания специальных алгоритмов для поддержки вычислений с двойной точностью.

Литература

  1. E. Scott Larsen, David K. McAllister. Fast Matrix Multiplies using Graphics Hardware. // Supercomputing 2001.

  2. Kayvon Fatahalian, Jeremy Sugerman, Pat Hanrahan. Understanding the Efficiency of GPU Algorithms for Matrix-Matrix Multiplication.

  3. Changhao Jiang, Marc Snir. Automatic Tuning Matrix Multiplication on Graphics Hardware. // The Fourteenth International Conference on Parallel Architecture and Compilation Techniques (PACT) 2005.

  4. Jin Hyuk Jung. Cholesky Decomposition and Linear Programming on a GPU. // Scholarly Paper Directed by Dianne P. O'Leary, Department of Computer Science, University of Maryland, 2006.

  5. Jens Krüger, Rudiger Westermann. Linear Algebra Operators for GPU Implementation of Numerical Algorithms. // Proceedings of SIGGRAPH 2003.

  6. Bolz et al. Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid. // Proceedings of SIGGRAPH 2003.

  7. LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware. // Proceedings of the 2005 ACM/IEEE Super Computing Conference. November 12-18, 2005.

  8. Ádám Moravánszky. Dense Matrix Algebra on the GPU. // From ShaderX 2 Programming, Wordware, 2003.

  9. Dominik Göddeke, Robert Strzodka, Stefan Turek. Accelerating Double-Precision FEM Simulations with GPUs. // Proceedings of ASIM 2005 - 18th Symposium on Simulation Technique.

  10. Thompson et al.Using Modern Graphics Architectures for General-Purpose Computing: A Framework and Analysis. // International Symposium on Microarchitecture (MICRO), Turkey, Nov. 2002.

  11. Chris Trendall, James Stewart. General Mathematics in Graphics Hardware. // Proceedings of Eurographics Workshop on Rendering. 2000.

  12. Kolb, Cuntz. Dynamic Particle Coupling for GPU-based Fluid Simulation. // Graphics-Hardware 2004.

  13. A Particle System for Interactive Visualization of 3D Flows.

  14. Strange Bunny. Open-Source Direct3D Fluid Simulation Library Released

  15. Youquan Liu et al. Real-Time 3D Fluid Simulation on the GPU with Complex Obstacles. // Proceedings of Pacific Graphics 2004, pages 247-256,October 2004

  16. Batty, Wiebe, Houston. High Performance Production-Quality Fluid Simulation via NVIDIA's QuadroFX. // Frantic Films

  17. Mark Harris. Real-Time Cloud Simulation and Rendering. // Ph.D. Dissertation. UNC Technical Report #TR03-040. September, 2003.

  18. Harris et al. Simulation of Cloud Dynamics on Graphics Hardware. // Proceedings of Graphics Hardware 2003.

  19. Greg James and Mark Harris. Simulation and Animation Using Hardware Accelerated Procedural Textures. // Game Developers Conference, 2003.

  20. Li et al. Implementing Lattice Boltzmann Computation on Graphics Hardware. // The Visual Computer.

  21. Goodnight et al. A Multigrid Solver for Boundary Value Problems Using Graphics Hardware. // University of Virginia Technical Report CS-2003-03, January 2003.

  22. Lefohn et. al. A GPU-Based, Three-Dimensional Level Set Solver with Curvature Flow. // University of Utah tech report UUCS-02-017, December, 2002.

  23. Strzodka and Rumpf. PDEs in Graphics Hardware. // University of Duisburg.

  24. Harris et al. Physically-Based Visual Simulation on Graphics Hardware. // UNC Chapel Hill

  25. Chu and Tai. MoXi: Digital Ink Simulation. // ACM Transactions on Graphics (SIGGRAPH 2005 issue), August 2005.

  26. Andrew Bond. Havok FX: GPU-accelerated Physics for PC Games.

  27. Simon Green, Mark Harris. Physics Simulation on NVIDIA GPUs.

  28. Theodore Kim and Ming Lin. Hardware Accelerated Ice Crystal Growth. // Proceedings of ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2003.

  29. Seismic Micro Technology. Oil Reservoir Simulation on GPUs. // European Association of Geoscientists and Engineers Conference & Exhibition.

  30. De Chiara et al. Massive Simulation using GPU of a distributed behavioral model of a flock with obstacle avoidance. // Proceedings of 9th Internation Fall Workshop VISION, MODELLING, AND VISUALIZATION 2004.

  31. Govindaraju et al. GPUFFTW: High Performance GPU-based FFT Library. // UNC Tech. Report 2006.

  32. Kenneth Moreland and Edward Angel. The FFT on a GPU. // Graphics Hardware 2003.

  33. K. L. Fok, T. T. Wong, and M. L. Wong. Evolutionary Computing on Consumer-Level Graphics Hardware. // IEEE Intelligent Systems

  34. K. L. Fok, T. T. Wong, and M. L. Wong. Parallel Evolutionary Algorithms on Graphics Processing Unit. // Proc. of IEEE Congress on Evolutionary Computation 2005.

  1. Parallel Genetic Algorithms on Programmable Graphics Hardware

  2. S.Tomov at al. Benchmarking and Implementation of Probability-Based Simulations on Programmable Graphics Cards. // Computers & Graphics.

  3. Fan et. al. GPU Cluster for High Performance Computing. // Proceedings of the ACM/IEEE SuperComputing 2004 (SC'04), November, 2004.

  4. Bohn C. A. Kohonen feature mapping through graphics hardware.// Proceedings of the Joint Conference on Information Sciences (1998), vol. II, pp. 64–67.

  5. GPU-based multi-layer perceptron as efficient method for approximation complex light models in per-vertex lighting. // http://stud.ics.p.lodz.pl/~keyei/lab/atmoseng/index.html.

  6. Kyoung-Su Oh, Keechul Jung. GPU implementation of neural networks. // Pattern Recognition 37 (2004) 1311 – 1314






Цифровая обработка сигналов и ее применение

Digital signal processing and its applications
1   2   3

Похожие:

Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconМ. Е. Жуковский, Р. В. Усков о применении графических процессоров видеоускорителей в прикладных задачах
В работе рассмотрены основы применения технологии nVidia© cuda для распараллеливания вычислений с использованием графических процессоров....
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconRussian national committee on theoretical and applied mechanics
Алгоритмы рапараллеливания решения нестационарных уравнений газовой динамики на примерах расчета конкретных задач
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconПрограммирование современных графических процессоров с использованием основных языков платформы. Net
Большинство современных интерактивных графических приложений основано на использовании специализированных графических процессоров...
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconПрограмма поспецкурс у "газовая динамика"
Основные части и разделы газовой динамики. Области применения. Характерные черты газовой динамики. Качественные и оценочные данные...
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconУрок по теме: Методы решения логарифмических уравнений
Систематизировать и обобщить знания, умения и навыки, связанные с применением методов решения логарифмических уравнений
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconИсследование новых моделей задач математической физики и создание алгоритмов их решения. В рамках этого проекта: подпроект «Законы сохранения, инварианты, точные и приближенные решения для уравнений гидродинамического типа и интегральных уравнений»
Математические проблемы алгебры, топологии, теории приближения функций и приложения
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconЧисленные методы газовой динамики и теплопереноса
...
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconПроект web-syndic: web-сервер для тестирования и экспериментального анализа алгоритмов решения линейных диофантовых уравнений в неотрицательных целых числах
Целью проекта является разработка алгоритмов генерации тестовых систем оданлду различных классов, разработка web-сервера Web-SynDic...
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconПрименение rkdg метода для численного решения задач газовой динамики
Лакса Фридрихса, кир, hll и hllc. Проведенные расчеты позволяют оценить качество различных схем. Rkdg метод имеет более высокий порядок...
Аппаратное ускорение алгоритмов решения уравнений газовой динамики с применением графических процессоров iconРадиофизический факультет
Ип в различных системах. Также содержание дисциплины направлено на обучение студентов основам решения задач линейной алгебры, решения...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница