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

Информатика, вычислительная техника и управление УДК 004.65 DOI: 10.14529/cmse150106

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

С.О. Приказчиков, П.С. Костенецкий

Работа посвящена вопросам применения графических процессоров для обработки запросов в параллельных системах баз данных. Целью данной работы является оценка эффективности выполнения запросов к сжатой базе данных без предварительной распаковки с использованием графических ускорителей, поддерживающих технологию CUDA. Объем внутренней памяти ГПУ на порядки меньше, чем объем оперативной памяти современных вычислительных систем. Это ограничивает размер базы данных, которую можно загрузить в память ГПУ и как следствие не позволяет раскрыть весь вычислительный потенциал графического процессора. Предлагается подход для обработки запросов над сжатыми данными на ГПУ. На основе предложенного подхода реализован эмулятор параллельной СУБД. Аналогичный эмулятор разработан для ЦПУ. Приведены результаты вычислительных экспериментов и произведена оценка эффективности данного подхода.

Ключевые слова: графические процессоры, параллельная обработка запросов, CUDA.

Введение

В настоящее время известно большое количество исследований обработки запросов к базам данных в оперативной памяти [4, 5, 9, 12], но использование графических ускорителей (ГПУ) и многоядерных сопроцессоров [11] открывает новые перспективы исследований в этой области [1, 2, 7]. Целью данной работы является оценка эффективности выполнения запросов к сжатой базе данных без предварительной распаковки с использованием графических ускорителей, поддерживающих технологию СИБА. Объем внутренней памяти ГПУ на порядки меньше, чем объем оперативной памяти современных вычислительных систем. Это ограничивает размер базы данных, которую можно загрузить в память ГПУ и как следствие не позволяет раскрыть весь вычислительный потенциал ГПУ. Для снижения влияния объема видеопамяти на возможность хранения в ней больших баз данных применяется сжатие. Предполагается, что сжатие позволит не только увеличить объем хранимой базы данных, но и повысит производительность по сравнению с обработкой несжатых данных.

Статья организована следующим образом. В разделе 1 описана реализация алгоритма выборки для ГПУ и ЦПУ. Раздел 2 описывает проводимые вычислительные эксперименты. В заключении подведены итоги исследования.

1 Статья рекомендована к публикации программным комитетом Международной суперкомпьютерной конференции «Научный сервис в сети Интернет: многообразие суперкомпьютерных миров -2014»

1. Реализация

На текущий момент разработан эмулятор СУБД [6], позволяющий выполнять запрос SELECT над сжатыми данными, непосредственно на ГПУ с использованием технологии CUDA и, для сравнения, эмулятор для ЦПУ, работающий по технологии OpenMP.

Для сжатия был выбран и реализован алгоритм RLE [8, 10]. Основным преимуществом использования данного алгоритма в СУБД является возможность выполнения многих реляционных запросов без предварительной распаковки данных.

Реляционное отношение базы данных хранится в сжатом виде в памяти ГПУ. Кортежи отношения имеют по два атрибута, первый атрибут — номер кортежа (идентификатор), второй атрибут — значение (строка символов). На первом этапе алгоритм производит поиск строк, длина которых совпадает с размером искомой строки. Так, каждый блок производит выборку из нескольких подряд идущих кортежей. Каждый поток блока выполняет сравнение одного символа искомой строки с символом в строке базы данных. При такой организации распараллеливания соблюдается принцип memory coalescing [3], что позволяет свести к минимуму влияние латентности доступа к памяти ГПУ. Для распараллеливания на ГПУ используется разбиение кортежей реляционного отношения по блокам CUDA. На конечном этапе номера кортежей, содержащих совпавшие строки, записываются в выходной массив. Передаются не кортежи целиком, а только их номера с целью уменьшить объем передаваемых данных по шине PCI Express. Шина PCI Express имеет на несколько порядков меньшую скорость передачи данных, чем оперативная память и внутренняя память ГПУ, поэтому данный подход позволяет значительно повысить общую производительность при обработке данных.

2. Вычислительные эксперименты

Вычислительные эксперименты проводились с использованием разработанного эмулятора СУБД на оборудовании, характеристики которого приведены в табл. 1.

Таблица 1

Оборудование для экспериментов

Оборудование Характеристики

Процессор Intel Core i7-3610QM 2.3 ГГц

ОЗУ 8 Гб DDR3-1600

Твердотельный накопитель Plextor M5 Pro PX-128M5P, 128 Гб, SATA III

Системная шина PCI Express 2.0

Графический ускоритель Модель NVIDIA GeForce GTX 670M

Объем видеопамяти 3 072 Мб

Ядер CUDA 336

Тактовая частота ядра 620 МГц

Тактовая частота памяти 3 000 МГц

Пропускная способность 72 Гб/с

памяти

Разрядность памяти 192-bit

Для проведения вычислительных экспериментов было сгенерировано 4 тестовых отношения. Размер отношений, а также коэффициент сжатия строк в кортежах представлены в табл. 2.

Таблица 2

Характеристики тестовых отношений

№ тестовой Размер отношения (количество Коэффициент Объем в сжатом виде,

БД кортежей) сжатия Мб

1 4 519

2 33 000 000 2 1 039

3 1,33 1 562

4 1 2 077

2.1. Исследование эффективности операции выборки над сжатыми данными

Было произведено исследование эффективности операции выборки над сжатыми данными в сравнении с обработкой несжатых данных.

——Обработка несжатых данных

-Обработка сжатых в 1,33 раза данных —•—Обработка сжатых в 2 раза данных - Обработка сжатых в 4 раза данных

—— Обработка несжатых данных —а— Обработка сжатых в 1,33 раза данных —•—Обработка сжатых в 2 раза данных ——Обработка сжатых в 4 раза данных

128 192

Количество потоков на блок CUDA

128 192

Количество потоков на блок CUDA

а) Время б) Ускорение

Рис. 1. Выполнение алгоритма ГПУ SELECT на одном вычислительном узле

Как видно из графиков времени выполнения операции выборки из тестовых баз данных с использованием ГПУ (см. рис. 1а) и с использованием ЦПУ (см. рис. 2а), при применении сжатия мы получаем максимальный прирост скорости в 3,2 раза на ГПУ и в 3 раза на ЦПУ.

а) Время б) Ускорение

Рис. 2. Выполнение алгоритма ЦПУ SELECT на одном вычислительном узле

На графике сравнения времени выполнения операции выборки на ГПУ и на ЦПУ (см. рис. 5) видно, что при использовании ГПУ выборка выполняется быстрее независимо от размера базы данных.

О 500 1000 1500 2000

Размер БД

Рис. 3. Время выполнения алгоритмов ЦПУ и ГПУ SELECT на одном вычислительном узле над сжатыми в 4 раза данными

Заключение

В работе рассматривались вопросы применения графических процессоров для обработки запросов в параллельных системах баз данных. Предложен подход для обработки запросов над сжатыми данными на ГПУ. На основе предложенного подхода реализован эмулятор параллельной СУБД. Аналогичный эмулятор разработан для ЦПУ. Приведены результаты вычислительных экспериментов и произведена оценка эффективности данного подхода. Установлено, что выполнение выборки над сжатыми данными на ГПУ эффективнее, чем на ЦПУ в 1,2 раза. Небольшое преимущество ГПУ объясняется тем, что в качестве тестовой конфигурации имелся достаточно производительный процессор Intel Core i7-3610QM и не очень производительный графический ускоритель NVIDIA GeForce GTX 670M. На следующем этапе исследования тестирование будет произведено на новейших ГПУ NVIDIA Tesla K40 и многоядерных сопроцессорах Intel Xeon Phi.

Работа выполнена при финансовой поддержке Минобрнауки РФ в рамках ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы» (Соглашение № 14.574.21.0035).

Литература

1. Беседин, К.Ю. Моделирование обработки запросов на гибридных вычислительных системах с многоядерными сопроцессорами и графическими ускорителями / К.Ю. Беседин, П.С. Костенецкий / / Программные системы: теория и приложения: электрон. научн. журн. Института программных систем им. А.К. Айламазяна РАН. — 2014. — T. 5, № 1(19). — С. 91-110.

2. Беседин, К.Ю. Применение многоядерных сопроцессоров в параллельных системах баз данных / К.Ю. Беседин, П.С. Костенецкий / / Параллельные вычислительные технологии (ПаВТ'2013): труды международной научной конференции (1-5 апреля 2013 г., г. Челябинск). — Челябинск: Издательский центр ЮУрГУ, 2013. — С. 583.

3. Боресков, А.В. Параллельные вычисления на GPU. Архитектура и программная модель CUDA / А.В. Боресков, Н.Д. Марковский, Д.Н. Микушин и др. — М.: Издательство Московского университета, 2012. — 336 с.

4. Костенецкий, П.С. Технологии параллельных систем баз данных для иерархических многопроцессорных сред / П.С. Костенецкий, А.В. Лепихов, Л.Б. Соколинский // Автоматика и телемеханика. — 2007. — № 5. — C. 112-125.

5. Костенецкий, П.С. Моделирование иерархических многопроцессорных систем баз данных / П.С. Костенецкий, Л.Б. Соколинский // Программирование. - Москва: МАИК «Наука/Интерпериодика». — 2013. — Т. 39, № 1. — С. 3-22.

6. Костенецкий, П.С. Моделирование параллельных систем баз данных: учебное пособие / П.С. Костенецкий, Л.Б. Соколинский — Челябинск: Фотохудожник, 2012. — 78 с.

7. Сафина, Ю.Н. Моделирование аппаратной архитектуры и коммуникационных сетей вычислительных кластеров с гибридными узлами для параллельных систем баз данных / Ю.Н. Сафина, П.С. Костенецкий // Параллельные вычислительные технологии (ПаВТ'2012): Труды международной научной конференции (г. Новосибирск, 26-30 марта 2012 г.). — Челябинск: Издательский центр ЮУрГУ, 2012. — С. 741.

8. Abadi, D. Integrating compression and execution in column-oriented database systems / D. Abadi, S. Madden, M. Ferreira // Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, 2006. — P. 671-682.

9. Пан, К.С. Разработка параллельной СУБД на основе последовательной СУБД Post-greSQL с открытым исходным кодом / К.С. Пан, М.Л. Цымблер / / Вестник ЮУрГУ. Серия «Математическое моделирование и программирование». — 2012. — № 18(277). Вып. 12. — С. 112-120.

10. Костенецкий, П.С. Исследование эффективности различных методов сжатия при передаче данных из основной памяти в память сопроцессора Intel Xeon Phi / П.С. Костенецкий, К.Ю. Беседин // Вычислительные методы и программирование. — 2014. — Т. 15, № 4. — С. 593-601.

11. Иванова, Е.В. Использование распределенных колоночных индексов для выполнения запросов к сверхбольшим базам данных / Е.В. Иванова, Л.Б. Соколинский // Параллельные вычислительные технологии (ПаВТ'2014): труды международной научной конференции (1-3 апреля 2014 г., г. Ростов-на-Дону). — Челябинск: Издательский центр ЮУрГУ, 2014. — С. 270-275.

12. Соколинский, Л.Б. Параллельные машины баз данных / Л.Б. Соколинский // Природа. — 2001. — № 8. — C. 10-17.

Приказчиков Степан Олегович, старший лаборант лаборатории суперкомпьютерного моделирования, Южно-Уральский государственный университет (Челябинск, Россия), prikazchikovso@susu.ru.

Костенецкий Павел Сергеевич, к.ф.-м.н., доцент, руководитель лаборатории суперкомпьютерного моделирования, Южно-Уральский государственный университет (Челябинск, Россия), kostenetskiy@susu.ru.

Поступила в редакцию 11 декабря 2014 г.

Bulletin of the South Ural State University Series "Computational Mathematics and Software Engineering"

2015, vol. 4, no. 1, pp. 64-70

DOI: 10.14529/cmse150106

USING GRAPHICS ACCELERATORS FOR QUERY PROCESSING OVER COMPRESSED DATA IN PARALLEL DATABASE SYSTEMS

S. O. Prikazchikov, South Ural State University

prikazchikovso@susu.ru,

P.S. Kostenetskiy, South Ural State University

kostenetskiy@susu.ru.

This article talks about using graphics processors for query processing in parallel database systems. The goal is to evaluate query execution efficiency over compressed database without decompression on multicore GPUs which support CUDA technology. GPU's memory size is significantly smaller than modern computer system's RAM size. This fact affects database's size can be loaded into GPU's internal memory, thus computing potential of GPU can not be used efficiently. The new approach presented in this article allows query processing over compressed data on GPU. An emulator of parallel DBMS is developed based on this approach. The similar emulator for a CPU is designed. Results of computational experiments are presented and analysis of efficiency of the proposed approaches is performed.

Keywords: databases, graphics processors, parallel query processing.

References

1. Besedin K.Y, Kostenetskiy P.S. Simulating of query processing on multiprocessor database systems with modern coprocessors // MIPRO 2014 Proceedings of the 37th International Convention. May 26-30, 2014. Opatija. Croatia, 2014. P. 1835-1837.

2. Besedin K.Y., Kostenetskiy P.S. Primenenie mnogoyadernykh soprotsessorov v paral-lel'nykh sistemakh baz dannykh [Using multi-core coprocessors in parallel database systems]. Parallel'nye vychislitel'nye tekhnologii (PAVT'2013): Trudy mezhdunarodnoy nauchnoy konferentsii (1-5 aprelya 2013 g., g. Chelyabinsk). Chelyabinsk: Izdatel'skiy tsentr YuUrGU [Proceedings of the International Conference Parallel Computational Technologies (PCT'2014), April 1-5, 2013, Chelyabinsk, Russia. Chelyabinsk: SUSU publishing center], 2013. P. 583.

3. Boreskov A.V, Markovskiy N.D., Mikushin D.N. et al. Parallel'nye vychisleniya na GPU. Arkhitektura i programmnaya model' CUDA [Parallel calculations on GPU. Architecture and program CUDA model]. M.: Izdatel'stvo Moskovskogo universiteta [Bulletin of publishing house of the Moscow university], 2012. 58 p.

4. Kostenetskii P.S., Lepikhov A.V., Sokolinskii L.B. Technologies of parallel database systems for hierarchical multiprocessor environments / / Automation and Remote Control. 2007. Vol. 68, No. 5. P. 847-859.

5. Kostenetskii P.S., Sokolinsky L.B. Simulation of Hierarchical Multiprocessor Database Systems // Programming and Computer Software. Vol. 39, No. 1. 2013. P. 10-24.

6. Kostenetskiy P.S., Sokolinskiy L.B. Modelirovanie parallel'nykh sistem baz dannykh: uchebnoe posobie [Modeling of parallel database systems: manual]. Chelyabinsk: Fotokhudozhnik [Bulletin Chelyabinsk: Pictorialist], 2012. 78 p.

7. Safina Yu.N., Kostenetskiy P.S. Modelirovanie apparatnoy arkhitektury i kommu-nikatsionnykh setey vychislitel'nykh klasterov s gibridnymi uzlami dlya parallel'nykh sistem baz dannykh [Simulation of hardware architecture and communication networks of computing clusters with hybrid nodes for parallel database systems].Parallel'nye vychislit-el'nye tekhnologii (PaVT'2012): Trudy mezhdunarodnoy nauchnoy konferentsii (g. Novosibirsk, 26-30 marta 2012 g.) Chelyabinsk: Izdatel'skiy tsentr YuUrGU [Proceedings of the International Conference Parallel Computational Technologies (PCT'2012), March 26-30, 2012, Novosibirsk, Russia. Chelyabinsk: SUSU publishing center]. 2012. P. 741.

8. D. Abadi, S. Madden, M. Ferreira. Integrating compression and execution in column-oriented database systems / / Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, 2006. P. 671-682.

9. Pan C.S., Zymbler M.L. Razrabotka parallelnoj SUBD na osnove posledovatelnoj SUBD PostgreSQL s otkrytym ishodnym kodom [Development of a Parallel Database Management System on the Basis of Open-Source PostgreSQL DBMS]. Vestnik Yuzho-Uralskogo gosudarstvennogo universiteta. Seriya «Matematicheskoe modelirovanie i programmiro-vanie» [Bulletin of South Ural State University. Series: Mathematical Modeling, Programming & Computer Software]. 2012. No. 18(277). Vol. 12. P. 112-120.

10. Kostenetskiy P.S., Besedin K.Yu. Issledovanie effektivnosti razlichnykh metodov szhatiya pri peredache dannykh iz osnovnoy pamyati v pamyat' soprotsessora Intel Xeon Phi [Efficiency Evaluation of Some Compression Methods for Data Transfer between Main Memory and Intel Xeon Phi Coprocessors]. Vychislitel'nye metody i programmirovanie [Numerical methods and programming]. 2014. Vol. 15, No. 4. P. 593-601.

11. Ivanova E.V., Sokolinsky L.B. Ispol'zovanie raspredelennykh kolonochnykh indeksov dlya vypolneniya zaprosov k sverkhbol'shim bazam dannykh [Using distributed column indexes for query execution over very large databases]. Parallel'nye vychislitel'nye tekhnologii (PaVT'2014): trudy mezhdunarodnoy nauchnoy konferentsii (1-3 aprelya 2014 g., g. Ros-tov-na-Donu). Chelyabinsk: Izdatel'skiy tsentr YuUrGU [Proceedings of the International Conference Parallel Computational Technologies (PCT'2014), April 1-3, 2014, Rostov-na-Donu, Russia. Chelyabinsk: SUSU publishing center]. 2014. P. 270-275.

12. Sokolinsky L.B. Parallel'nye mashiny baz dannyh [Parallel database machines]. Priroda [Nature]. 2001. № 8. P. 10-17.

Received December 11, 2014.