авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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


ПРОГРАММНЫЕ СИСТЕМЫ: ТЕОРИЯ И ПРИЛОЖЕНИЯ № 1(19), 2014, c. 91–110

ISSN 2079-3316

УДК 004.657

К. Ю. Беседин, П. С. Костенецкий

Моделирование обработки

запросов на гибридных

вычислительных системах с многоядерными

сопроцессорами и графическими ускорителями

Аннотация. Данная статья посвящена оценке эффективности примене-

ния графических ускорителей и многоядерных сопроцессоров в параллель-

ных системах баз данных. Для этого был разработан эмулятор параллель ной СУБД, позволяющий использовать вычислительный кластер, оснащен ный графическими ускорителями NVIDIA и сопроцессорами Intel Xeon Phi.

С помощью данного эмулятора был проведен ряд вычислительных экспе риментов.

Ключевые слова и фразы: Параллельные СУБД, GPU, CUDA, Intel MIC, Intel Xeon Phi.

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

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

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

Работа выполнена при поддержке гранта РФФИ № 12-07-31082 (2012– гг.), № 12-07-00443-а (2012–2014 гг.) и гранта Президента РФ № МК-3711.2013. (2013–2014 гг.) c К. Ю. Беседин, П. С. Костенецкий, c Программные системы: теория и приложения, 92 К. Ю. Беседин, П. С. Костенецкий На данный момент уже существуют работы, посвященные эф фективной реализации специфичных для СУБД алгоритмов с ис пользованием ГПУ. Так, [2, 3] описывают алгоритм работы с дере вом индекса, учитывающий архитектурные особенности современ ных ГПУ и ЦПУ, который может быть использован для организации индекса. Работа [4] предлагает метод ускорения операций над ин дексом, эффективно использующий большое число вычислительных ядер ГПУ. Статьи [5,6] описывают алгоритмы сортировки, [7] описы вает реализацию нескольких алгоритмов операции JOIN. В [8] рас сматриваются реализации запросов SELECT и JOIN. Помимо это го, исследуются новые архитектурные решения, позволяющие наи более эффективно использовать особенности графических ускорите лей. В работе [9] описывается такое совместное использование ГПУ и ЦПУ при обработке запросов, при котором запрос выполняется на ГПУ в тех случаях, когда стоимость выполнения запроса на нем ни же, чем на центральном процессоре (стоимость выполнения запроса вычисляется динамически на основе плана запроса). В статье [10] рассматривается группировка транзакций с целью их последующе го выполнения на графическом ускорителе. Работа [11] предлагает использование ГПУ для оптимизации запросов. В техническом от чете [12] рассмотрена разработка прототипа СУБД, хранящей свои данные в памяти графического ускорителя. Некоторыми авторами проводится адаптация существующих СУБД для использования гра фических ускорителей и оценка эффективности такой адаптации.

Так, в [13] поддержка вычислений с использованием ГПУ была инте грирована в СУБД Oracle 9, в [14] поддержка графических ускори телей была добавлена в WattDB [15], а в работе [16] использовалась SQLite.

Еще одной перспективной многоядерной архитектурой является разрабатываемая компанией Intel архитектура Intel MIC. Количество исследований, посвященных этой архитектуре, меньше, чем количе ство исследований, посвященных ГПУ. Это можно объяснить тем, что ускорители, построенные на основе этой архитектуры, лишь недав но были представлены широкой публике [17]. Однако уже проведе но несколько исследований, посвященных использованию Intel MIC в базах данных. Так, в [18] было проведено сравнение реализаций алгоритма поразрядной сортировки (Radix Sort) для Intel Core i7, NVIDIA GTX 280 и Knights Ferry. Согласно результатам исследова ния, производительность Intel MIC оказалась в 2.2 раза выше, чем Моделирование обработки запросов на гибридных вычислительных системах производительность ЦПУ и в 1.7 раз выше, чем производительность ГПУ. В [2], помимо ЦПУ и ГПУ подробно рассматривается реализа ция предложенного алгоритма поиска в дереве индекса на Intel MIC (Knights Ferry). Для маленьких деревьев (64 тыс. ключей) MIC пока зал в 2.4 раза более высокую производительность, чем ЦПУ и в 4. раза чем ГПУ. Для больших деревьев (16 млн. ключей) производи тельность MIC оказалась в 3 раза выше, чем ЦПУ и в 1.8 раз выше, чем ГПУ.

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

В рамках данной работы был разработан и спроектирован эму лятор параллельной СУБД, позволяющий использовать графические ускорители и NVIDIA и многоядерные сопроцессоры Intel Xeon Phi при обработке реляционных запросов Select и Join. Эмулятор напи сан на языке Си и использует технологии OpenMP, MPI и NVIDIA CUDA. Реализация алгоритмов была выполнена в трех вариантах с учетом архитектуры используемых сопроцессоров. Для достижения высокой степени параллелизма при обработке запроса используется фрагментация отношений по вычислительным узлам. Выполняемые запросы делятся на подзапросы, поровну распределяемые между ра бочими процессами (параллельными агентами). Для коммуникации процессов между собой используется интерфейс MPI.

Методы организации запросов к базе данных Общий алгоритм выполнения запроса SELECT состоит из сле дующих шагов:

загрузить отношение в основную память;

(1) распределить отношение между рабочими процессами;

(2) (3) выполнить выборку;

(4) собрать результаты выборок и соединить их в итоговое отноше ние.

94 К. Ю. Беседин, П. С. Костенецкий Исходное Итоговое отношение отношение { } MPI-процесс L MPI-процесс { L+ } MPI-процесс N 2L { (N-1)L + } K NL Рис. 1. Схема выполнения ЦПУ SELECT Алгоритм выполнения выборки состоит в просмотре всех кортежей отношения и проверке их на соответствие заданному предикату. Вы борка производится в два прохода: во время первого прохода опреде ляется количество отбираемых кортежей, а во время второго прохода заполняется итоговое отношение. Это позволяет избежать использо вания сложных структур данных и связанных с этим накладных рас ходов. Конкретная реализация, несколько отличается в зависимости от версии эмулятора.

Алгоритм ЦПУ SELECT последовательно обрабатывает каж дый кортеж полученного фрагмента исходного отношения, проверяя для него условие выборки. Схема выполнения запроса SELECT пред ставлена на рис. 1. Ниже представлен алгоритм выполнения ЦПУ SE LECT:

последовательно просканировав фрагмент отношения, опреде (1) лить размер результата выборки;

(2) выделить память для хранения результата выборки;

(3) последовательно просканировав фрагмент отношения, сформи ровать результат выборки.

Алгоритм ГПУ SELECT. В данном алгоритме кортежи фраг мента исходного отношения распределяются по потокам CUDA так, чтобы был возможен соединенный (coalesced) доступ к глобальной памяти. Для каждого обрабатываемого кортежа проверяется усло вие выборки. Схема выполнения ГПУ SELECT изображена на рис. 2.

Ниже представлен алгоритм выполнения ГПУ SELECT:

определить число потоков в блоке и число используемых блоков;

(1) подготовить фрагмент отношения в памяти ускорителя;

(2) (3) использовать ускоритель для определения размера результата выборки для каждого потока CUDA;

Моделирование обработки запросов на гибридных вычислительных системах Итоговое отношение { N GPU N+ { N+ 2N LN+ { LN+ (L + 1)N+ K Рис. 2. Схема выполнения ГПУ SELECT вычислить общий размер результата выборки;

(4) для каждого потока CUDA вычислить смещения в результате (5) выборки для вставки кортежей;

подготовить память для хранения результатов выборки на хосте (6) и на ГПУ;

использовать ГПУ для формирования результата выборки;

(7) скопировать результат выборки в память хоста;

(8) освободить используемые ресурсы ускорителя.

(9) Алгоритм Manycore SELECT использует для выполнения сопро цессоры Intel Xeon Phi. Кортежи фрагмента исходного отношения автоматически распределяются по потокам OpenMP. Схема выпол нения Manycore SELECT изображена на рис. 3. Ниже представлен алгоритм Manycore SELECT:

подготовить фрагмент отношения в памяти сопроцессора;

(1) используя сопроцессор, определить размер результата выборки (2) для каждого потока OpenMP;

вычислить общий размер результата выборки;

(3) для каждого потока OpenMP вычислить смещения в результате (4) выборки для вставки кортежей;

сформировать выборку на сопроцессоре;

(5) скопировать результат в память хоста;

(6) освободить ресурсы сопроцессора.

(7) Общий алгоритм выполнения запроса JOIN состоит из следую щих шагов:

загрузить отношения в основную память;

(1) отправить каждому рабочему процессу копию опорного отноше (2) ния;

96 К. Ю. Беседин, П. С. Костенецкий Исходное отношение Итоговое отношение } { Intel Xeon Phi } { } { Рис. 3. Схема выполнения Manycore SELECT распределить тестируемое отношение между рабочими процес (3) сами;

(4) выполнить соединение;

(5) собрать результаты соединений и соединить их в итоговое отно шение.

Для выполнения выборки используются алгоритмы вложенных цик лов и Hash Join [19]. Соединение производится в два прохода: во время первого прохода определяется количество соединенных кор тежей, а во время второго прохода заполняется итоговое отношение.

Это позволяет избежать использования сложных структур данных и связанных с ними накладных расходов.

Алгоритм ЦПУ NESTED LOOPS JOIN последовательно прове ряет каждый кортеж опорного отношения и каждый кортеж тести руемого отношение на возможность соединения. Схема выполнения ЦПУ NESTED LOOPS JOIN изображена на рис. 4. Ниже представлен алгоритм выполнения ЦПУ NESTED LOOPS JOIN:

последовательно выполнив алгоритм вложенных циклов, опре (1) делить размер результата соединения;

(2) выделить память для хранения результата соединения;

(3) последовательно выполнив алгоритм вложенных циклов, запол нить результат соединения.

Алгоритм ГПУ NESTED LOOPS JOIN использует графический процессор для вычисления размера итогового отношения и непосред ственного выполнения выборки. Кортежи отношения делятся между потоками CUDA так, чтобы воспользоваться объединенным (coalesced) Моделирование обработки запросов на гибридных вычислительных системах Опорное Итоговое отношение отношение } { M MPI-процесс MPI-процесс { MPI-процесс N Тестируемое отношение } { L K L+ } 2L (N-1)L + } NL Рис. 4. Схема выполнения ЦПУ NESTED LOOPS JOIN доступом к памяти. Чтобы уменьшить число обращений к глобаль ной памяти ускорителя, интенсивно используется разделяемая па мять блоков CUDA. На рис. 5 изображена схема выполнения JOIN для ГПУ, а ниже представлен его алгоритм:

определить число потоков в блоке и число используемых блоков;

(1) подготовить опорное отношение в памяти ускорителя;

(2) подготовить фрагмент тестируемого отношения в памяти уско (3) рителя;

использовать ускоритель для определения размера результата (4) соединения для каждого потока CUDA;

вычислить общий размер результата соединения;

(5) для каждого потока CUDA вычислить смещения в результате (6) соединения для вставки кортежей;

подготовить память для хранения результатов соединения на хо (7) сте и на ГПУ;

использовать ГПУ для формирования результата соединения;

(8) скопировать результат в память хоста;

(9) освободить используемые ресурсы ускорителя.

(10) Алгоритм Manycore NESTED LOOPS JOIN. Версия алгоритма JOIN для Intel Xeon Phi использует сопроцессор в offload-режиме для выполнения описанных выше проходов. Для распределения нагруз ки по ядрам сопроцессора итераций циклов, используется технология 98 К. Ю. Беседин, П. С. Костенецкий Опорное отношение Итоговое отношение } { GPU M { Тестируемое отношение { N N+ K N+ 2N LN+ LN+ (L + 1)N+ Рис. 5. Схема выполнения ГПУ NESTED LOOPS JOIN OpenMP. Схема выполнения Manycore NESTED LOOPS JOIN изоб ражена на рис. 6. Ниже представлен алгоритм Manycore NESTED LOOPS JOIN:

подготовить опорное отношение в памяти сопроцессора;

(1) подготовить фрагмент тестируемого отношения в памяти сопро (2) цессора;

используя сопроцессор, определить размер результата соедине (3) ния для каждого потока OpenMP;

вычислить общий размер результата выборки;

(4) для каждого потока OpenMP вычислить смещения в результате (5) соединения для вставки кортежей;

сформировать соединение на сопроцессоре;

(6) скопировать результат в память хоста;

(7) освободить ресурсы сопроцессора.

(8) Вычислительные эксперименты Разработанный эмулятор параллельной СУБД был запущен на суперкомпьютере «Торнадо ЮУрГУ», для проведения экспериментов с центральными процессорами Intel Xeon и с многоядерным ускори телем Intel Xeon Phi и на вычислительном кластере ННГУ, для про ведения экспериментов на графических ускорителях NVIDIA Tesla.

Характеристики узлов данных вычислительных систем приведены в табл. 1, 2.

Моделирование обработки запросов на гибридных вычислительных системах Опорное Итоговое отношение отношение } {{ Intel Xeon Phi {{ Тестируемое отношение { } {{ { } } { Рис. 6. Схема выполнения Manycore NESTED LOOPS JOIN Таблица 1. Суперкомпьютер ”Торнадо ЮУрГУ” Процессор Intel Xeon 5680 3.33 GHz Узел Объем ОЗУ 24 / 48 GB Число процессоров Сопроцессор Intel Xeon Phi 7110X Число узлов Число узлов с сопроцессорами Таблица 2. Вычислительный кластер ННГУ Процессор Intel Xeon L5630 2.13 GHz Объем ОЗУ 24 GB Узел Число процессоров GPU NVIDIA Tesla X Число GPU Число узлов с ускорителями Исследование эффективности аппаратных архитектур Моделирование запроса SELECT. Моделировался простейший ва риант запроса SELECT:

SELECT: SELECT * FROM Relation WHERE Attribute = Value;

Для тестирования производительности было использовано отноше ние, состоящее из двух целочисленных атрибутов и содержащее 100 К. Ю. Беседин, П. С. Костенецкий Время (с) 1 2 3 4 5 6 7 8 9 10 11 Процессов MPI Рис. 7. Время выполнения алгоритма ЦПУ SELECT на одном вычислительном узле 1, 1, 1, Ускорение 1, 1, 1, 1, 1, 1, 1 2 3 4 5 6 7 8 9 10 11 Процессов MPI Рис. 8. Ускорение выполнения алгоритма ЦПУ SELECT на одном вычислительном узле 369098752 кортежей. Таким образом, примерный размер отношения — 5.5 GB.

Производительность запроса ЦПУ SELECT тестировалась на вы числительном узле суперкомпьютера «Торнадо ЮУрГУ». Во время тестирования число MPI-процессов эмулятора варьировалось от до 12. На рис. 7 представлена зависимость времени выполнения за проса от числа используемых процессов MPI. На рис. 8 изображено полученное ускорение. Малое ускорение объясняется большими на кладными расходами при передаче данных по сети.

Производительность запроса ГПУ SELECT тестировалась на вы числительном узле кластера ННГУ. Во время тестирования число потоков CUDA, используемых эмулятором, варьировалось от 512 до 6656. Графики времени выполнения и ускорения представлены на рис. 9 и рис. 10 соответственно. Малое снижение времени и ускорение Моделирование обработки запросов на гибридных вычислительных системах 56, 56, 56, 56, Время (с) 55, 55, 55, 55, 512 2048 3584 5120 Потоков CUDA Рис. 9. Время выполнения алгоритма ГПУ SELECT на одном вычислительном узле 1, 1, 1, Ускорение 1, 0, 0, 512 2048 3584 5120 Потоков CUDA Рис. 10. Ускорение выполнения алгоритма ГПУ SE LECT на одном вычислительном узле 70, 70, 70, Время (с) 70, 69, 69, 69, 69, 20 40 60 80 100 120 140 160 180 200 220 Потоков OpenMP 1, Рис. 11. Время выполнения алгоритма Manycore SE LECT на одном вычислительном узле связано с тем, что помимо передачи данных по сети, значительное время тратится на копирование отношения на ускоритель.

102 К. Ю. Беседин, П. С. Костенецкий 1, 1, 1, Ускорение 1, 0, 0, 20 40 60 80 100 120 140 160 180 200 220 Потоков OpenMP Рис. 12. Ускорение выполнения алгоритма Manycore SE LECT на одном вычислительном узле CPU GPU MIC Время (с) 1 2 3 4 5 6 7 Узлов Рис. 13. Время выполнения алгоритма SELECT на нескольких вычислительных узлах Тестирование производительности алгоритма Manycore SELECT выполнялось на суперкомпьютере «Торнадо ЮУрГУ». Во время те стирования число потоков OpenMP варьировалось от 20 до 240. На рис. 11 представлен график времени выполнения запроса. Здесь, как и в случае с графическими ускорителями, к большим накладным рас ходам на передачу отношений по сети добавляется время на копиро вание отношений на сопроцессор. На рис. 12 изображен график уско рения выполнения запроса SELECT в зависимости от числа потоков OpenMP.

Тестирование производительности при выполнении запроса SE LECT в случае использования нескольких вычислительных узлов для ЦПУ и Intel Xeon Phi проводилось на суперкомпьютере «Тор надо ЮУрГУ», а для ГПУ – на вычислительном кластере ННГУ.

Во время тестирования число вычислительных узлов изменялось от 1 до 8. На каждом из узлов был запущен разработанный эмулятор Моделирование обработки запросов на гибридных вычислительных системах 2, CPU 2, GPU 2, MIC Ускорение 1, 1, 1, 1, 0, 1 2 3 4 5 6 7 Узлов Рис. 14. Ускорение выполнения алгоритма SELECT на нескольких вычислительных узлах с параметрами, дающими максимальную производительность в слу чае одного узла. На рис. 13 представлен график времени выполнения запроса SELECT для нескольких вычислительных узлов. На рис. представлен график ускорения выполнения запроса SELECT. Наи лучшее ускорение показал Intel Xeon Phi. Это связано с тем, что пе редача отношения на сопроцессор занимает значительную долю от общего времени выполнения запроса: уменьшение обрабатываемых отдельным сопроцессором фрагментов отношения по мере увеличе ния числа используемых узлов, позволяет получить некоторое уско рение.

Вне зависимости от числа используемых узлов кластера, время выполнения запроса с использованием ГПУ и Intel Xeon Phi пре вышает время выполнения запроса и использованием только цен трального процессора. Таким образом, использование сопроцессоров для смоделированного варианта запроса SELECT менее эффектив но, чем использование центральных процессоров. Это связано с тем, что имеющиеся накладные расходы значительно превышают сокра щение непосредственного времени (то есть, без учета времени пере дачи данных по сети и на сопроцессор/ГПУ) выполнения запросов, вызванного использованием сопроцессоров или графических ускори телей.

Для тестирования производительности при выполнении алгорит ма JOIN использовалось опорное отношение, состоящее из двух ат рибутов и содержащее 33521 кортежей и тестируемое отношение из двух атрибутов и содержащее 33521000 кортежей. В обоих случаях 104 К. Ю. Беседин, П. С. Костенецкий Время (с) 1 2 3 4 5 6 7 8 9 10 11 Процессов MPI Рис. 15. Время выполнения алгоритма ЦПУ JOIN на од ном вычислительном узле Укорение 1 2 3 4 5 6 7 8 9 10 11 Процессов MPI Рис. 16. Ускорение выполнения алгоритма ЦПУ JOIN на одном вычислительном узле значениями атрибутов являются целые числа (int64_t). Таким обра зом, размер опорного отношения — примерно 500 KB, размер тести руемого — примерно 500 MB.

Производительность алгоритма ЦПУ NESTED LOOPS JOIN те стировалась (см. табл. 1) на вычислительном узле суперкомпьюте ра «Торнадо ЮУрГУ». Во время тестирования число MPI-процессов эмулятора варьировалось от 1 до 12. Графики времени выполнения алгоритма и его ускорения представлены на рис. 15 и рис. 16 соответ ственно.

Производительность алгоритма ГПУ NESTED LOOPS JOIN те стировалась на вычислительном узле кластера ННГУ (см. табл. 2).

Во время тестирования число потоков CUDA, используемых эмуля тором, варьировалось от 256 до 24832. На рис. 17 показано время вы полнения данного алгоритма, а на рис. 18— его ускорение.

Моделирование обработки запросов на гибридных вычислительных системах Время (с) 256 4352 8448 12544 16640 20736 Потоков CUDA Рис. 17. Время выполнения алгоритма ГПУ JOIN на од ном вычислительном узле Ускорение 256 4352 8448 12544 16640 20736 Потоков CUDA Рис. 18. Ускорение выполнения Время выполнения алго ритма ГПУ JOIN на одном вычислительном узле Время (с) 20 40 60 80 100 120 140 160 180 200 220 Потоков OpenMP Рис. 19. Время выполнения алгоритма Manycore JOIN на одном вычислительном узле Тестирование производительности при выполнении запроса Many core NESTED LOOPS JOIN, использующего сопроцессор Intel Xeon Phi, выполнялось на вычислительном узле суперкомпьютера «Тор 106 К. Ю. Беседин, П. С. Костенецкий Ускорение 20 40 60 80 100 120 140 160 180 200 220 Потоков OpenMP Рис. 20. Ускорение выполнения алгоритма Manycore JOIN на одном вычислительном узле CPU 250 GPU MIC Время (с) 1 2 3 4 5 6 7 Узлов Рис. 21. Время выполнения алгоритма JOIN на несколь ких вычислительных узлах 2, CPU 2, GPU 2, MIC Ускорение 1, 1, 1, 1, 0, 1 2 3 4 5 6 7 Узлов Рис. 22. Ускорение выполнения алгоритма JOIN на нескольких вычислительных узлах надо ЮУрГУ»(см табл. 1). Во время тестирования число потоков OpenMP варьировалось от 20 до 240. Результаты данного тестиро вания представлены на рис. 19 и рис. 20.

Моделирование обработки запросов на гибридных вычислительных системах Тестирование производительности при выполнении запроса JOIN в случае использования нескольких вычислительных узлов для ЦПУ и Intel Xeon Phi проводилось на суперкомпьютере «Торнадо ЮУрГУ», а для ГПУ – на вычислительном кластере ННГУ. Использовалось от 1 до 8 вычислительных узлов кластера. На каждом из узлов был запущен разработанный эмулятор с параметрами, дающими макси мальную производительность в случае одного узла.

На рис. 21 показана зависимость времени выполнения запроса JOIN в зависимости от числа используемых узлов кластера. Как вид но из графика на рис. 22, все версии эмулятора показывают близкий к линейному рост ускорения по мере увеличения количества исполь зуемых вычислительных узлов кластера.

Графические ускорители NVIDIA и сопроцессоры Intel Xeon Phi позволяют выполнять соединение отношений быстрее, чем централь ные процессоры, обладая схожими ускорениями при использовании нескольких вычислительных узлов. Отсюда можно сделать вывод о том, что они могут быть эффективно использованы для выполнения запросов INNER JOIN в параллельных СУБД.

Заключение В рамках данной работы авторами представлен эмулятор парал лельной СУБД, использующий вычислительный кластер для выпол нения запросов SELECT и JOIN. Разработаны версии запросов для ЦПУ, ГПУ и многоядерных сопроцессоров. Проведен рад вычисли тельных экспериментов, в которых выяснено, что при передаче дан ных шина PCI Express является узким местом для обработки боль ших объемов данных, и при обработке простых реляционных запро сов большую часть времени занимает передача данных на сопроцес сор. В случае с запросами, обладающими высокой вычислительной сложностью, передача данных занимает меньше времени. В этом слу чае высокая производительность сопроцессоров позволяет им эффек тивно обрабатывать такие запросы. Объем передаваемых на сопро цессор данных можно значительно уменьшить, применив поколоноч ное хранение данных. Так, при обработке запросов можно передавать на сопроцессор только те колонки, которые непосредственно требу ются для обработки запроса. Для еще большего снижения объема данных можно воспользоваться высокой эффективностью сжатия в поколоночных СУБД и передавать данные на сопроцессор в сжатом виде. При этом, за счет высокой производительности сопроцессоров, 108 К. Ю. Беседин, П. С. Костенецкий время, требуемое на упаковку и распаковку данных, будет меньше времени, сэкономленного при передаче данных на сопроцессор за счет сжатия. Таким образом, в дальнейшем будут разрабатываться мето ды передачи данных на сопроцессор в сжатом виде и исследование эффективности различных алгоритмов сжатия для многоядерных со процессоров.

Cписок литературы [1] A. D Blas, T. Kaldewey Data Monster // IEEE spectrum, 2009. Vol. 46, no. 9.

[2] C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W.

Lee, S. A. Brandt, P. Dubey Designing fast architecture-sensitive tree search on modern multicore/many-core processors // ACM Trans. Database Syst., 2011.

Vol. 36, no. 4, p. 22:1–22:34. 92, [3] C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, P. Dubey FAST: fast architecture sensitive tree search on modern CPUs and GPUs // ACM SIGMOD International Conference on Managment of data: Proceedings – Indianapolis, USA, June 6–10, 2010: ACM, 2010, p. 339–350.

– [4] P. B. Volk, D. Habich, W. Lehner GPU-based speculative query processing for database operations // First International workshop on accelerating data managment systems using modern processor and storage architectures in conjunction with VLDB – Singapure, September 13, 2010. – [5] D. G. Merrill, A. S. Grimshaw Rewriting sorting for GPGPU stream architectures // 19th international conference on Parallel Architectures and Compilation Techniques: Proceedings – Vienna, Austria, September 11–15, 2010: ACM, 2010, – p. 545–546. [6] N. Satish, C. Kim, J. Chhugani, A. D. Nguyen, V. W. Lee, D. Kim, P. Dubey Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort // The ACM SIGMOD International Conference on Management of data: Proceedings – – New York, USA, June 6–11, 2010: ACM, 2010, p. 351–362. [7] B. He, K. Yang, R. Fang, M. Lu, N. K. Govindaraju, Q. Luo, P. V. Sander Relational joins on graphics processors // ACM SIGMOD international conference on Management of data: Proceedings – New York, USA, June 10–12, – 2008: ACM, 2008, p. 511–524. [8] П. С. Костенецкий Обработка запросов на кластерных вычислительных системах с многоядерными ускорителями // Вестник ЮУрГУ. Серия «Вы числительная математика и информатика», 2012. Т. 47(306). Вып. 2, c. 59– 67. [9] B. He, M. Lu, K. Yang, R. Fang, N. K. Govindaraju, Q. Luo, P. V. Sander Relation query coprocessing on graphics processors // ACM Trans. Database Syst, 2009.

Vol. 34, no. 4, p. 21:1–21:39. [10] B. He, J. X. Yu High-throughput transaction executions on graphics processors // VLDB Endowment: Proceedings – Seattle, Washington, USA, August 29 – – September 3, 2011: VLDB Endowment, 2011. Vol. 4, no. 5, p. 314–325. Моделирование обработки запросов на гибридных вычислительных системах [11] M. Heimel, M. Volker A first step towards GPU-assisted query optimizations // Third International workshop on accelerating data managment systems using modern processor and storage architectures in conjunction with VLDB– Istanbul, – Turkey, August 27, 2012, p. 1–12. [12] M. Christiansen, C. E. Hansen. CUDA DBMS./ Aalborg University Denmark, Copenhagen, Aalborg University, 2009 [13] N. Bandi, C. Sun, D. Agrawal, A. E. Abbadi Hardware acceleration in commertial databases: a case study of spatial operations // 30th international conference on Very Large Databases: Proceedings – Toronto, Canada, August 31 – September – 3, 2004: VLDB Endowment, 2004. Vol. 30, p. 1021–1032. [14] U. R. Vitor, D. Schal. A GPU-operations framework for WattDB./ University of Kaiserslautern Germany, Kaiserslautern, University of Kaiserslautern, 2012 [15] Distributed database system WattDB, 30.10.2012, URL: http://wwwlgis.

informatik.uni-kl.de/cms/dbis/projects/green/wattdb/. [16] P. Bakkum, K. Skadron Accelerating SQL Database Operations on a GPU with CUDA // The 3rd workshop on General-Purpose Computation on Graphics Processing Units: Proceedings – Pittsburg, USA: ACM, March 14, 2010, p. 94– – 103. [17] Intel Delivers New Architecture for Discovery with Intel Xeon Phi Coprocessors:

Combination of Intel Xeon processors and Intel Xeon Phi coprocessors promises to drive high performance computing innovation, 6.05.2013, URL:

http://newsroom.intel.com/community/intel_newsroom/blog/2012/11/12/intel delivers-new-architecture-for-discovery-with-intel-xeon-phi-coprocessors. [18] N. Satish, C. Kim, J. Chhugani, A. D. Nguyen, V. W. Lee, D. Kim, P. Dubey.

Fast sort on CPUs GPUs and Intel MIC architectures: Intel Labs, 2010 [19] Г. Гарсиа-Молина, Д. Ульман. Системы баз данных. Полный курс. Москва:

Вильямс, 2003. – 1088 c. – Рекомендовал к публикации Программный комитет Второго национального суперкомпьютерного форума НСКФ- Об авторах:

Константин Юрьевич Беседин Студент ФГБОУ ВПО ЮУрГУ (НИУ).

e-mail: besedin.k@gmail.com 110 К. Ю. Беседин, П. С. Костенецкий Павел Сегеевич Костенецкий Руководитель Лаборатории Суперкомпьютерного Модели рования. Кандидат физ.-мат. наук. Доцент кафедры систем ного программирования факультета вычислительной мате матики и информатики ФГБОУ ВПО ЮУрГУ(НИУ).

e-mail: kostenetskiy@gmail.com Образец ссылки на эту публикацию:

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

URL: http://psta.psiras.ru/read/psta2014\protect\T2A\ textunderscore1\protect\T2A\textunderscore91-110.pdf K. Y. Besedin, P. S. Kostenetskiy. Simulating of query processing on multiprocessor database systems with modern coprocessors.

Abstract. This paper focuses on evaluation of database multiprocessor architectures with manycore coprocessors and GPUs. We implemented the emulator of parallel DBMS that uses computing cluster with NVIDIA GPUs or Intel Xeon Phi coprocessors for relational query processing. A number of experiments have been done using this emulator. (in Russian).

Key Words and Phrases: Parallel DBMS, GPU, CUDA, Intel MIC, Intel Xeon Phi.



 




 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.