ИСПОЛЬЗОВАНИЕ ГРАФИЧЕСКИХ УСКОРИТЕЛЕЙ ДЛЯ ОБЩЕМАТЕМАТИЧЕСКИХ ВЫЧИСЛЕНИЙ
Пантюхин Д.В.
ФГУП НИИ автоматической аппаратуры им. академика В.С. Семенихина
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:
Линейная алгебра
LU-разложение;
Решение разряженных систем линейных алгебраических уравнений;
Решение плотных систем;
Матричное умножение;
Линейное программирование.
Обработка сигналов
Быстрое преобразование Фурье;
Обработка изображений;
Математическая физика;
Моделирование потоков жидкостей и газов;
Моделирование поведения твердых тел;
Биология;
Нейронные сети;
Эволюционные алгоритмы;
Поиск в базах данных;
Оптимизация кода.
Для решения задач линейного алгебры на графических процессорах предложено множество работ. В них рассматривается широкий спектр задач линейной алгебры, начиная от матрично-матричного умножения [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 не сходился. В настоящее время делаются попытки создания специальных алгоритмов для поддержки вычислений с двойной точностью.
Литература
E. Scott Larsen, David K. McAllister. Fast Matrix Multiplies using Graphics Hardware. // Supercomputing 2001.
Kayvon Fatahalian, Jeremy Sugerman, Pat Hanrahan. Understanding the Efficiency of GPU Algorithms for Matrix-Matrix Multiplication.
Changhao Jiang, Marc Snir. Automatic Tuning Matrix Multiplication on Graphics Hardware. // The Fourteenth International Conference on Parallel Architecture and Compilation Techniques (PACT) 2005.
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.
Jens Krüger, Rudiger Westermann. Linear Algebra Operators for GPU Implementation of Numerical Algorithms. // Proceedings of SIGGRAPH 2003.
Bolz et al. Sparse Matrix Solvers on the GPU: Conjugate Gradients and Multigrid. // Proceedings of SIGGRAPH 2003.
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.
Ádám Moravánszky. Dense Matrix Algebra on the GPU. // From ShaderX 2 Programming, Wordware, 2003.
Dominik Göddeke, Robert Strzodka, Stefan Turek. Accelerating Double-Precision FEM Simulations with GPUs. // Proceedings of ASIM 2005 - 18th Symposium on Simulation Technique.
Thompson et al.Using Modern Graphics Architectures for General-Purpose Computing: A Framework and Analysis. // International Symposium on Microarchitecture (MICRO), Turkey, Nov. 2002.
Chris Trendall, James Stewart. General Mathematics in Graphics Hardware. // Proceedings of Eurographics Workshop on Rendering. 2000.
Kolb, Cuntz. Dynamic Particle Coupling for GPU-based Fluid Simulation. // Graphics-Hardware 2004.
A Particle System for Interactive Visualization of 3D Flows.
Strange Bunny. Open-Source Direct3D Fluid Simulation Library Released
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
Batty, Wiebe, Houston. High Performance Production-Quality Fluid Simulation via NVIDIA's QuadroFX. // Frantic Films
Mark Harris. Real-Time Cloud Simulation and Rendering. // Ph.D. Dissertation. UNC Technical Report #TR03-040. September, 2003.
Harris et al. Simulation of Cloud Dynamics on Graphics Hardware. // Proceedings of Graphics Hardware 2003.
Greg James and Mark Harris. Simulation and Animation Using Hardware Accelerated Procedural Textures. // Game Developers Conference, 2003.
Li et al. Implementing Lattice Boltzmann Computation on Graphics Hardware. // The Visual Computer.
Goodnight et al. A Multigrid Solver for Boundary Value Problems Using Graphics Hardware. // University of Virginia Technical Report CS-2003-03, January 2003.
Lefohn et. al. A GPU-Based, Three-Dimensional Level Set Solver with Curvature Flow. // University of Utah tech report UUCS-02-017, December, 2002.
Strzodka and Rumpf. PDEs in Graphics Hardware. // University of Duisburg.
Harris et al. Physically-Based Visual Simulation on Graphics Hardware. // UNC Chapel Hill
Chu and Tai. MoXi: Digital Ink Simulation. // ACM Transactions on Graphics (SIGGRAPH 2005 issue), August 2005.
Andrew Bond. Havok FX: GPU-accelerated Physics for PC Games.
Simon Green, Mark Harris. Physics Simulation on NVIDIA GPUs.
Theodore Kim and Ming Lin. Hardware Accelerated Ice Crystal Growth. // Proceedings of ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2003.
Seismic Micro Technology. Oil Reservoir Simulation on GPUs. // European Association of Geoscientists and Engineers Conference & Exhibition.
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.
Govindaraju et al. GPUFFTW: High Performance GPU-based FFT Library. // UNC Tech. Report 2006.
Kenneth Moreland and Edward Angel. The FFT on a GPU. // Graphics Hardware 2003.
K. L. Fok, T. T. Wong, and M. L. Wong. Evolutionary Computing on Consumer-Level Graphics Hardware. // IEEE Intelligent Systems
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.
Parallel Genetic Algorithms on Programmable Graphics Hardware
S.Tomov at al. Benchmarking and Implementation of Probability-Based Simulations on Programmable Graphics Cards. // Computers & Graphics.
Fan et. al. GPU Cluster for High Performance Computing. // Proceedings of the ACM/IEEE SuperComputing 2004 (SC'04), November, 2004.
Bohn C. A. Kohonen feature mapping through graphics hardware.// Proceedings of the Joint Conference on Information Sciences (1998), vol. II, pp. 64–67.
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.
Kyoung-Su Oh, Keechul Jung. GPU implementation of neural networks. // Pattern Recognition 37 (2004) 1311 – 1314
Цифровая обработка сигналов и ее применение
Digital signal processing and its applications
|
