Автор перевода: Похилько С. И.
Источник: Информация научно-технического института. г. Моруцци, Пиза, Италия.
Источник (англ.): Sorting on GPUs for
large scale datasets: A thorough comparison
Учитывая требование больших вычислительных мощностей в современных видео играх, появились графические процессоры (как Cell / BE) предназначенные для чрезвычайно быстрой обработки объемных графических данных (например, полигонов и пикселей). В действительности, учитывая эффективность / затраты, такого типа процессоры используют также для обработки больших объемов данных и задач общего назначения.
Для некоторых задач, таких как веб-поиск информации, результаты, полученные в срок вычислительной задержки, превосходят те, которые получены с помощью классических процессоров. В последнее время были предприняты некоторые шаги, направленные на развитие основных моделей программирования, таких как Bingsheng, Wenbin, Qiong, Naga, и Tuyong (2008), разработка карт, базы редакторов карт, на графических процессорах, а Kruijf и Sankaralingam (2007) представили реализацию редакторов карт для сотовых архитектур.
Основная идея в современных процессорах, как графических, сотовых от Sony / BE, и многоядерных процессорах – ставить несколько вычислительных ядер (от пары до нескольких сотен) на одном чипе. В современных процессорах общей практики уделяется огромный процент кристаллам, для механизмов кэш-памяти и управления памятью, в целом. В отличие от стандартных процессоров, большинство современных многоядерных кристаллов направленно на реализацию вычислительных блоков. По этой причине, они могут выполнять специализированные расчеты с большими потоками данных, чем традиционные процессоры. Однако, это трудно для программистов - писать приложения, которые в состоянии достичь максимального уровня производительности.
В этой статье мы отклоняемся от обычной сортировки большого количества данных на современных графических процессорах, чтобы предложить новое сортирующее решение, которое может сортировать массив целых чисел «на месте». На самом деле, сортировка является основной проблемой в области компьютерной науки, которая была широко исследована в течение последних пяти лет, но она все еще остается узким местом во многих случаях с участием больших объемов данных. Кроме того. Сортировка представляет собой основной строительный блок для крупномасштабных распределенных систем.
Прежде всего, как мы покажем в разделе 3, сортировка является основной операцией для индексирования. Большой объем индексации требует масштабируемую сортировку. Во-вторых, техника, которую мы представляем здесь жизнеспособным для распределенных систем ИК, так как она предназначена для работы на графических процессорах, которые рассматриваются как основной строительный блок для будущих поколений дата-центров (Barroso & Holzle, 2009). Нашу «битонную» сортировку можно рассматривать как альтернативу для сортировки больших объемов данных на графических процессорах.
В ходе нашего исследования мы изучали новые функции карты сети битонической сортировки (СБС) на графических процессорах, использования его высокой пропускной способности, интерфейс памяти. Мы также представляем схему секционирования данных, которая улучшает эксплуатации и максимально пропускную способность, с которой данные передаются на чип и с чипа памяти. Стоит заметить, что сортировка на основе битонических сетей использует меньше памяти, чем другие (например, (Cederman & Tsigas, 2008; Sengupta, Harris, Zhang, & Owens, 2007)), и позволяет обрабатывать больше данных. Пространственная компактность является важным аспектом при сортировке больших объемов данных, как того требует крупномасштабные распределенные системы для поиска информации (LSDS IR).
Для разработки нашего алгоритма сортировки в модели программирования потоков, мы использовали популярную модель BSN, и адаптировали ее к нашей целевой архитектуре. Битоническая сортировка является одной из самых быстрых (Batcher, 1968). Благодаря своей большой эксплуатации, битоническая сортировка является одним из самых ранних параллельных алгоритмов сортировки, предложенных в литературе (Batcher, 1968). Он был использован во многих приложениях. Таковы, например, «разделяй и властвуй», используемые в вычислении быстрого преобразования Фурье (Govindaraju и Manocha, 2007), веб-поиска информации (Capannini, Silvestri, Baraglia, & Nardini, 2009), и некоторые новые групповые сети (Al-Hajery & Batcher, 1993).
Основной вклад этой статьи является следующее:
1. Мы проводим детальную экспериментальную оценку состояния дел в современной технике на GPU сортировке и сравниваем их на разных наборах данных различного размера, и покажем преимущества принятия на месте решения по сортировке больших объемов данных.
2. С помощью выполнения ограничений новой расчетной модели введнной Capannini, Silvestri, и Baraglia (2010), мы разрабатываем метод для повышения производительности (как теоретический, так и эмпирический) сортировки использованием бабочки сетей (например, битонической сортировки). Наши теоретические оценки и эксперименты показывают, что в соответствии с предложенным методом повышения производительности битоническая сортировка также превосходит другие алгоритмы.
Эта статья организована следующим образом:
В прошлом, многие авторы представили битоническую сортировку сетей на графических процессорах (например, Govindaraju, Gray, Kumar, & Manocha, 2006) но они используют аппаратные средства с предыдущими поколениями графических процессоров, которые не поддерживают такой же уровень программирования, как современные.
Так как большинство алгоритмов сортировки ограничены памятью, то по-прежнему актуальны разработки эффективных методов сортировки на графических процессорах.
Purcell, Donner, Cammarano, Jensen, and Hanrahan (2003) представляют собой реализацию битонической сортировки на графических процессорах, основанную на оригинальной идее представленных Kapasi соавт. (2000). Авторы применили свой подход к отсортировке фотонов в пространственных данных структуры, которая обеспечивает эффективный механизм поиска GPU на основе фотонных карт. Компаратор полностью реализован на фрагментах логических единиц, включая арифметические, логические и текстурные операций. Авторы сообщают, что их реализация будет вычислять связи, а не пропускные способности границы, и они достигают пропускной способности гораздо ниже теоретического оптимума целевой архитектуры.
В (Kipfer, Segal, & Westermann, 2004, 2005) показано, улучшенная версия битоническая сортировка, а также сортировка слиянием. Они представляют собой улучшенную битоническую процедуру сортировки, что позволяет достичь выигрыша в производительности за счет минимизации не числа выполняемых команд в программе, а числа текстурных операций.
Greb and Zachmann (2006) представлен подход к параллельной сортировки архитектура потоковых процессоров на основе адаптивных битонической сортировки (Bilardi & Nicolau, 1986). Они представляют собой реализацию на базе современных программируемых аппаратных графических процессорах, показывает, что они могут конкурировать с общими последовательными алгоритмами сортировки не только с теоретической точки зрения, но и с практической. Хорошие результаты достигаются при использовании эффективного линейного доступа к памяти потока, путем объединения оптимальных подходов времени алгоритмов.
Govindaraju, Raghuvanshi, and Manocha (2005) реализовали сортировку в качестве основного вычислительного компонента для гистограммы приближения. Это решение основано на периодической балансировке метода сортировки по сети Dowd, Perl, Rudolph, and Saks (1989). Для того чтобы достичь высокой вычислительной производительности GPU, они использовали сортировки сети на основе алгоритма, каждый этап вычисляется с использованием растеризации. Позже, они представили гибридный вариант битонического рода, который может сортировать огромные объемы данных, называемый GPUTeraSort (Govindaraju и соавт., 2006). Этот алгоритм был предложен для сортировки записей, содержащихся в базах данных с помощью GPU. Этот подход использует данные и параллельно задачи для выполнения с интенсивным использованием памяти и вычислительной мощности задач на GPU, в то время как процессор используется для выполнения ввода / вывода и управления ресурсами. Cederman и Tsigas (2008) показали, что GPU-Quicksort является хорошей альтернативой сортировки. Алгоритм рекурсивных разделений последовательностей должны быть отсортированы по отношению к оси. Это делается параллельно, каждая GPU-нить, пока вся последовательность будет отсортированна. В каждом разделе итерации, берется новое сводное значение, и в результате две новых подпоследовательности создаются так, что можно сортировать самостоятельно каждым потоком блока. Проведенные экспериментальные точки из оценки превосходство GPU-быстрая сортировка по сравнению с другими GPU на основе алгоритмов сортировки. В последнее время Sengupta и соавт. (2007) представляют поразрядную сортировку и реализацию быстрой сортировки на основе сегментированных примитивов сканирования. Авторы представили новые подходы к реализации нескольких классических приложений, использующих эти примитивы, и показали, что это примитивы представляют собой отличное поле для широкого круга задач по параллельным аппаратным обеспечениям.
Крупномасштабные и распределенные приложения, как информационно-поисковые, так и сканирование, индексирование и обработки запросов должны использовать вычислительную мощность новых вычислительных архитектур, идти в ногу с экспоненциальным ростом веб-содержимого.
В этой статье мы сосредоточим наше внимание на основной фазе одного из основных компонентов крупномасштабных поисковых систем индексирования.
В индексации фазы, каждый поступающий документ преобразуется в набор употребляемых слов, которые называют хитами. Для каждого слова просмотров записи: частота, положение в документе, и некоторые другие сведения. Индексация, то, может рассматриваться как своего рода операция на множестве записей, представляющих срок вхождения (Baeza-Yates, Castillo, Junqueira, Plachouras, & Silvestri, 2007). Записи представляют собой различные вхождения каждого члена в каждом отдельном документе. Эффективная сортировка этих записей с помощью хорошо сбалансированной памяти и дискового пространства, является весьма сложной задачей. В последние годы было показаны такого рода подходы (Witten, Moffat, & Bell, 1999), или однопроходных алгоритмов (Lester, 2005), являются эффективными в некоторых сценариях, в частности, где индексация больших объемов данных должна быть выполнена с ограниченными ресурсами. Своего рода подход впервые делает проход через все коллекции сборки termID-DocID пар. Затем он сортирует пары с termID как первичный ключ и док-ID в качестве вторичного ключа. Наконец, он организует docIDs для каждого termID в списке сообщений (также вычисляет статистику, как срок и документ частоты). Для небольших коллекций, все это может быть сделано в памяти. Когда памяти не хватает, мы прибегаем к использованию внешних алгоритм сортировки (Manning, Raghavan, & Schutze, 2008). Основным требованием такого алгоритма является минимизация числа случайных дисков во время сортировки. Возможный подход - заблокированные сортировки на основе индексирования (BSBI). BSBI работает сегментациями коллекции в части равного размера, он сортирует termID-DocID пар каждой части в памяти, наконец, хранит промежуточные результаты, которые сортируются на диске. Когда все сегменты сортируются, он объединяет все промежуточные результаты в конечный индекс. Более масштабируемую альтернативу однократно в памяти индексирования (SPIMI). SPIMI используются термины, а не termIDs, пишет каждого блока словарь на диске, а затем начинается новый словарь для следующего блока. SPIMI может индексировать коллекции любого размера, если есть достаточно места на диске. Алгоритм анализирует документы и превращает их в поток термин DocID пары, называемые маркеры. Жетоны затем обрабатываются по одному. Для каждого маркера, SPIMI добавляет размещения непосредственно в список сообщений. В отличие от BSBI где все termID-DocID пары собираются и сортируются, в каждом SPIMI список сообщений растет динамично. Это означает, что его размер регулируется, как он растет. Это имеет два преимущества: это быстрее, потому что нет сортировки требуется, и это экономит память, поскольку он отслеживает срок список сообщений относится к, так termIDs проводок не должны быть сохранены. Когда память закончится, пишется SPIMI индекс блока, который состоит из словаря и проводки списки на диск. Перед этим SPIMI виды условий для облегчения окончательного слияния шаг: если каждый блоков сообщений списки были написаны в несортированном порядке, объединение блоков не может быть достигнуто путем простого линейного сканирования. Последний шаг SPIMI - объединить блоки в конечный инвертированный индекс. В SPIMI временная сложность ниже, потому что нет сортировки меток, это, как правило, является предпочтительным по отношению к BSBI. В целом, как индексирование методы, которые мы отметим, сортировка является одним из основных шагов: BSBI виды termID-DocID пары все части в памяти, SPIMI виды условий для облегчения окончательного слияние (Manning и соавт., 2008).