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

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

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

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

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

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

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

7

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

9 Мотивация использования 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]

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

11 Конвейер OpenGL

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

13 Литература 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.