Библиотека для работы с конечными множествами, использующая графический процессор в качестве основного вычислительного устройства Новосибирский Государственный Университет Механико-Математический Факультет Каф. Программирования, Лаборатория Интел

Выполнил : Студент 3его курса ММФ НГУ Лыков Кирилл Олегович Научные руководители: К.ф.-м.н., доцент каф. программирования Скопин И.Н. ……………………. Пасько Е.В. В рамках проекта : Использование графических процессоров для вычислений с плавающей точкой в Java-программах. Exploiting Graphics Processing Units (GPUs) for general purpose computation in Java programming language

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

Представление битовых множеств на GPU Пусть дано некоторое конечное множество целых чисел. Битовой маской этого множества назовем последовательность бит количество которых не меньше чем максимальный элемент множества. Пусть i-ый элемент битовой маски равен 1 если i принадлежит исходному множеству и 0 иначе. Битовая маска храниться в текстурной памяти, а не в оперативной. Это обуславливает специфический формат хранимых данных а именно битовая маска хранится в массиве X*Y*4, где числа X,Y являются степенями двойки.

Операции над битовыми множествами Над множествами существует 3 основных операции – объединение, пересечение и дополнение. Другие операции могут быть получены как композиция перечисленных. В отдельном ряду стоит операция проверки принадлежности объекта множеству. Над битовыми множествами соответственно имеется 3 основных операции и, или и отрицание. Реализуются они на графическом процессоре. Сложность в том, что на GPU аппаратно реализованы только действительные числа.

Архитектура библиотеки Здесь будет UML диаграмма. Сейчас нет, тк RationalRose платная и у меня ее нет. Class Texture class FrShaider class BitSet_Gpu

Вычисления общего назначения на графическом ускорителе General-Purpose Computation on Graphics Hardware

Мотивация использования GPU Скорость –3.0 GHz dual-core Pentium4: 24.6 GFLOPS –NVIDIA GeForceFX 7800: 165 GFLOPs –1066 MHz FSB Pentium Extreme Edition : 8.5 GB/s –ATI Radeon X850 XT Platinum Edition: 37.8 GB/s GPUs становятся все быстрее –CPUs: 1.4×годичный рост –GPUs: 1.7×(pixels) to 2.3× (vertices)годичный рост Современные GPU обеспечивают приемлемую точность вычислений –Поддержка чисел с плавающей точкой ( до 32 битов) См [1]

GPUs становятся все быстрее

Конвейер OpenGL

Основные концепции GPGPU 1. Массив = текстура. CPU array (1D адресация) -> GPU texture (2D адресация) 2. Вычислительное ядро программы = шейдер. Часть программы для CPU ответственная за вычисления переносится соответствующим образом на GPU 3. Вычисление = отрисовка. 4. Получение результатов вычислений в буфер кадра ( frame buffer ).

Литература 1. David Luebke. General-Purpose Computation on Graphics Hardware. University of Virginia. 2. Mark Harris. Mapping Computational Concepts to GPUs. NVIDIA 3. Dominik Göddeke. GPGPU::Basic Math Tutorial.