526

Параллельное хеширование на GPU в реальном времени

Реферат

Информатика, кибернетика и программирование

Эффективный алгоритм параллелизма данных для построения больших хеш-таблиц на миллионы элементов в режиме реального времени. Гибридная хеш-таблица основана на современных идеях из теории хеширования. Компромисс между сроками строительства, временем доступа и рационального использования пространства.

Русский

2013-01-06

84 KB

19 чел.

Параллельное хеширование на GPU в реальном времени

Аннотация

В реферате представлен эффективный алгоритм параллелизма данных для построения больших хеш-таблиц на миллионы элементов в режиме реального времени. Рассматриваются два параллельных алгоритма: классический подход разреженного идеального хеширования и хеширование методом кукушки, при котором элементы упаковываются плотно, позволяя элементу храниться в одном из нескольких возможных мест. Предлагается также гибридный подход, который использует оба алгоритма. Было измерено время построения таблиц, время доступа и использование памяти предложенных реализаций, и демонстрация в режиме реального времени на больших наборах данных: для 5 миллионов пар ключ-значение хеш-таблица строится за 35,7 мс, используя в 1,42 раза больше памяти, чем сами входные данные, и можно получить доступ  ко всем элементам этой хеш-таблицы за 15,3 мс. Для сравнения, для сортировки тех же данных требуется 36,6 мс, а доступ ко всем элементам с помощью бинарного поиска требует 79,5 мс.

1 Введение

Хеширование (иногда хэширование, англ. hashing) — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки.

Хеш-таблица – это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции:

  1.  операцию добавления новой пары;
  2.  операцию поиска;
  3.  операцию удаления пары по ключу.

Коллизией хеш-функции h называется два различных входных блока данных x и y таких, что h(x)=h(y). Коллизии существуют для большинства хеш-функций, но для «хороших» хеш-функций частота их возникновения близка к теоретическому минимуму.

Появление программируемых графических аппаратных средств позволило параллельным графическим процессорам (GPU) вычислять и использовать различные представления данных.

Например, исследователи недавно продемонстрировали эффективное параллельное построение для иерархических пространственных структур данных, таких как k-d деревья (k-мерные деревья). Вообще, существенная проблема для исследования – это определение  подходящих параллельных структур данных, которые могут быть созданы, изменены и к которым был бы доступ. Инструментальных средств для обработки структур данных и связанных с ними алгоритмов остается значительно больше на скалярной архитектуре, например на центральном процессоре (CPU), чем на параллельной архитектуре, например на графических процессорах (GPU).

В этой статье рассматривается проблема реализации параллельной структуры данных, которая обеспечивает произвольный доступ к миллионам элементов и которая может быть построена за короткий срок . У такой структуры данных есть многочисленные применения в компьютерной графике, сосредоточенной на приложениях, которые должны хранить редкий набор пунктов в компактном представлении. На центральном процессоре наиболее распространенная структура данных для такой задачи – хеш-таблица. Однако обычные последовательные алгоритмы для строительства и вызова хеш-таблиц не легко перевести к параллельной среде GPU по трем причинам.

1). Синхронизация.

Алгоритмы заполнения традиционной хеш-таблицы имеют тенденцию вовлекать последовательные операции. Формирование цепочки, например, требует, чтобы многие элементы были добавлены к каждому связному списку, который потребовал бы преобразования в последовательную форму доступа к структуре списка на GPU.

2). Последовательность проб.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. Количество проб, необходимых для поиска элемента в типичных последовательных хеш-таблицах, изменяется в зависимости от запроса, например, для цепочки требуется прохождение связных списков, которые различаются по длине. Это приведет к неэффективности в GPU, где SIMD ядра заставят все нити ждать наихудший случай.

3). Разреженное хранение.

Хеш-таблицы по своей природе обладают небольшой наполненностью в любом случае построения или доступа, так что вычислительные иерархии имеют мало возможностей для повышения производительности.

В своей работе Лефевр и Хоппе [2006] одними из первых использовали GPU для доступа к хеш-таблице, и рассматривали вопрос о переменном времени поиска с помощью идеальной хеш-таблицы. В этой статье мы определяем идеальную хеш-таблицу, в которой элемент может быть доступен в худшем случае  за время O(1). Идеальные хеш-таблицы в прошлом были построены  на центральном процессоре, используя в основном последовательные алгоритмы, а затем загружены, и этот трудоемкий процесс ограничивает их применение в статической сфере.

Основной вклад в этой работе – параллельные, GPU-применимые хеш-таблицы, которые дают возможность как построения, так и поиска в интерактивном режиме. Рассматриваются три проблемы, сформулированные выше, с использованием стратегий хеширования, которые являются новыми для GPU. Во-первых , это классическая схема идеального хеширования Фридмана [Фридман и др. 1984], которая является простой и быстрой, но пространственно неэффективной. Во-вторых, недавно разработанный метод кукушки для хеширования [Pagh и Rodler 2001]. Хешированием методом кукушки считается так называемый «множественный выбор» идеального алгоритма хеширования, что обеспечивает высокую загрузку за счет большого времени построения. Новым решением является гибрид этих двух методов, для которых строительство и время доступа, на практике, растет линейно с увеличением числа элементов.

Одним из главных преимуществ хеш-таблицы в последовательных вычислениях является то, что это, по сути, динамические структуры данных, для которых время удаления и вставки имеет вид O(1). Но часто нет необходимости иметь динамическую структуру данных на GPU: если некоторые или все элементы данных в хеш-таблице изменяются на каждом шагу, то таблица восстанавливается с нуля.

Построение хеш-таблиц в режиме реального времени и время доступа полезно использовать в самых разных приложениях, которые требуют разреженных данных. Например, для графических приложений: пространственное хеширование для обнаружения пересечения движущихся данных, а также геометрическое хеширование для функции соответствия. Оказывается, что пространственный хеш на виртуальной 1283 сетке может быть построен на каждом кадре приблизительно за 27 кадров в секунду. Геометрическое хеширование – это групповые GPU приложения, требующие интенсивного произвольного доступа к таблице пар характерных точек.

3 Виды хеширования

3.1 Идеальное хеширование

Как и во многих работах по созданию хеш-таблиц на GPU, мы концентрируемся на построении идеальной хеш-таблицы. Классическое построение идеальной хеш-таблицы Фридмана и др.. [1984] (FKS-построение) основывается на наблюдении, что если размер таблицы m гораздо больше, чем число элементов n, особенно если m = О(n2), то с некоторой постоянной вероятностью случайно выбранная хеш-функция не будет иметь коллизий вовсе, и будет давать постоянное время поиска. Чтобы получить постоянное время поиска при линейном пространстве, в FKS-построении используется двухуровневая таблица. На верхнем уровне элементы хешируются в сегменты, а нижний уровень хеширует сегмент из k элементов  в буфер размера O(k2). Пока каждый сегмент имеет только O(1) ожидаемых элементов, ожидаемый размер хеш-таблицы равен O(n) и время поиска каждого элемента O(1). Основной недостаток в том, что для достижения оптимальной загрузки, скажем, 1/4, требуется очень много маленьких сегментов.

Более поздние работы ориентированы на построение минимальных идеальных хеш-таблиц, которые хранят n элементов в строго отведенных n местах. Минимальные или даже почти минимальные идеальные хеш-таблицы уменьшают пространственные накладные расходы за счет увеличения времени строительства. Пространственная конструкция хеш-таблицы, используемая Лефевром и Хоппе [2006], была основана на одном из этих подходов. Такие конструкции не только дорогие, но еще они по своей сути последовательные, так как расположение элемента в таблице зависит от места положения предыдущих элементов. С другой стороны, FKS-построение является чисто случайным и его довольно просто осуществить параллельно. Теоретически потребуется время O(lg n) на параллельных машинах произвольного доступа CRCW PRAM (Concurrent Read Concurrent Write Parallel Random Access Machine) [Matias, Vishkin 1990].

3.2 Хеширование с множественным выбором (альтернативное) и хеширование методом кукушки

Особый вклад в хеширование с множественным выбором внес в своей работе Azar [2000], который рассматривал обычное формирование цепочек. Автор показал, что с помощью d>2  хеш-функций и хранения элемента в сегменте, содержащем минимальное количество элементов, снижается ожидаемый размер самого длинного списка с O(log n/ log log n) до O(log log n/ log d). Vöcking [2003] использовал несколько подтаблиц, каждую со своей собственной хеш-функцией, и уменьшил ожидаемый размер самого длинного списка до O(log log n/d).

Хеширование методом кукушки [Pagh и Rodler 2001; Devroye и Morin 2003] размещает не более одного элемента в каждой ячейке памяти в хеш-таблице, позволяя элементам перемещаться после их первичного размещения. Как и в случае хеширования с множественным выбором, используется небольшой постоянный набор d>2 хеш-функций, и при этом считается, что d таблиц разделены на подтаблицы. Последовательный алгоритм построения вставляет элементы один за другим. Сначала проверяется, есть ли среди d сегментов пустые. (Здесь мы предполагаем, каждый сегмент может содержать только один элемент; в условиях, когда в сегменте хранится множество элементов, мы проверяем наличие свободного места). Если нет, то элемент "выталкивает" один из содержащихся элементов, и занимает его место. Этим и объясняется название алгоритма: в природе, птенец кукушки выталкивает из гнезда других птенцов. Исключенный элемент проверяет другие возможные сегменты, и рекурсивно выталкивает другие элементы, если необходимо, и так далее.

Для d=2, ожидаемое максимальное количество шагов, необходимых, чтобы вставить элемент, будет равно O(lg n), но, к сожалению, мы можем обеспечить загрузку чуть меньше половины. Для d=3, хеширование методом кукушки может достигать около 90% занятости [Fotakis и соавт. 2005], но теоретические верхние границы для времени вставки оказались гораздо более сложными для d>3.

3.3 Параллельное хеширование методом кукушки

Основная проблема распараллеливания алгоритмов хеширования методом кукушки в определении семантики параллельных обновлений таблицы правильно, чтобы  коллизии между элементами устранялись надлежащим образом . Алгоритм использует три подтаблицы (d=3), каждая размером n*(1+γ)/3, где γ  достаточно большая константа. На первой итерации пытаемся сохранить все элементы в первой подтаблице T1, одновременно записывая каждый элемент на свое место в таблице. Семантика требует, чтобы ровно одна запись была успешной, когда происходят коллизии, и чтобы каждый поток был в состоянии определить эту запись. Это реализуется благодаря записи всех элементов независимо друг от друга, а затем используется вызов синхронизации потоков, чтобы содержимое таблицы не изменялось во время проверки на успех. Примерно 2n/3 элементов терпят неудачу, и они должны быть записаны в подтаблицу T2 на второй итерации. Те элементы, что не смогли попасть в подтаблицу Т2, направляются в Т3. Наконец, те элементы, что потерпели неудачу в T3, возвращаются к T1, выталкивают некоторые элементы, уже находящиеся в подтаблице, и пытаются занять их место. Выселенные элементы, а также те, которые не смогли найти место в T1, продолжают те же действия в T2. Итерации продолжаются до тех пор, пока все элементы не найдут свое место в таблице, или до максимального числа итераций, и в этом случае считается, что была выбрана неудачная хеш-функция. Хотя при d=2 для последовательного алгоритма максимальное ожидаемое число итераций O(lg n); гораздо труднее получить теоретические значения верхней границы при d>3. Тем не менее, на практике мы видим, что число итераций умеренное.

Однако параллельное хеширование методом кукушки не будет эффективным для построения больших хеш-таблицы на GPU, так как каждая итерация требует перетасовки элементов в глобальной памяти с глобальной синхронизацией на каждой итерации. Но это очень подходит для таблиц, которые могут быть рассчитаны на маленькой и быстрой встроенной памяти внутри кристалла. Таким образом, можно использовать гибридный метод. Как и в схеме FKS-построения, сначала находим хеш-функцию первого уровня для разделения на более мелкие сегменты. В рамках каждого сегмента, затем используем параллельное хеширование методом кукушки для размещения элементов по трем подтаблицам. Поскольку оно выполняется полностью на внутрикристальной памяти, то на практике оказывается очень быстрым.

4 Применение

В этом разделе описывается реализация, которая использует программно-аппаратную архитектуру CUDA, позволяющую производить вычисления с использованием графических процессоров NVIDIA.


4.1 Основные хеш-таблицы

Предположим, что входом является множество n элементов – целых пар ключ-значение  (k, v), где все ключи являются уникальными. Процесс построения приводится в алгоритме 1, и состоит из двух этапов.

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

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

Algorithm 1

Basic hash table implementation

Алгоритм 1.

Реализация основной хеш-таблицы

Phase 1: Distribute into buckets of size 512

1: compute number of buckets required

2: allocate output space and working buffers

3: for each in parallel do

4:  compute h(k) to determine bucket bk containing k

5:  atomically increment count[bk], learning internal offset[k]

6: end for

7: perform prefix sum on count[ ] to determine start[ ]

8: for each key-value pair (k, v) in parallel do

9:  store (k, v) in buffer at start[bk] + offset[k]

10: end for

Этап 1: Разделение на сегменты размером ≤ 512

1: вычислить количество требуемых сегментов

2: выделить место для  выходных данных и рабочих буферов

3: for each для каждого  parallel do

4  вычислить хеш-функцию h(k), чтобы определить сегмент bk, содержащий k

5:  атомарно увеличить count[bk], запоминая внутреннее смещение offset[k]

6: end for

7: суммировать приставки по count[], чтобы определить начало start[]

8: for each для каждой пары ключ-значение (k, v) parallel do

9:  хранить (k, v) в буфере start[bk] + offset[k] (начало + смещение)

10: end for

Phase 2: Parallel cuckoo hash each bucket

1: for each bucket b in parallel, using one block per bucket do

2: build parallel cuckoo hash containing the items in b

3: write out tables T1, T2, T3 and hash functions g1, g2, g3

4: end for

Этап 2: Параллельное хеширование методом кукушки для каждого сегмента

1: for each для каждого сегмента b, используя один блок на сегмент  parallel do

2:  построить параллельные хеш-таблицы, содержащие элементы из сегмента b

3:  вывести подтаблицы T1, T2, T3 и хеш-функции g1, g2, g3

4: end for

5 Выводы

Хеш-таблицы на миллионы элементов могут быть успешно построены и доступны на GPU в интерактивном режиме. Гибридная хеш-таблица основана на современных идеях из теории хеширования. Одним из наиболее интересных результатов является компромисс между сроками строительства, временем доступа и рационального использования пространства. В описанной здесь реализации есть баланс этих трех метрик, но в приложениях, которые требуют редкого обновления, или которые имеют неограниченное место хранения, можно использовать различные проектные решения.


 

А также другие работы, которые могут Вас заинтересовать

30586. Методы и методика журналистского творчества 35 KB
  Интервью от англ. По содержанию интервью делятся на так называемые документальные интервью изучение событий прошлого уточнение фактов и интервью мнений цель которых выявление оценок взглядов суждений и т.Есть формализованное интервью стандартизированное и структуризованное общение: интервью имеет четкую структуру; каждый вопрос логически вытекает из другого а все вместе они подчинены общему замыслу беседы; открытые закрытые и полузакрытые вопросы. Неформализованном интервью ориентировано на глубинное познание объекта и...
30587. Налоговое регулирование внешнеэкономической деятельности предприятия 126.5 KB
  Целями налогового регулирования импорта и экспорта являются: поддержание рационального соотношения вывоза и ввоза товаров, валютных доходов и расходов на территории РФ. Налоговое регулирование импорта направлено, в основном...
30588. Личность журналиста в системе журналистики 31 KB
  Личность журналиста в системе журналистики. то же самое в вопросе № 49: индивидуальные характеристики творческой личности Творческая индивидуальность журналиста особое качество личности которое она приобретает и выявляет в конкретном виде данной деятельности Компоненты творческой индивидуальности: Знания общекультурные и профессиональные Умения опыт самостоятельный творческий подход Желания журналиста его потребности: мотивы интерес желания страсть внешние материальные и духовные внутренние. Мотивация журналиста:...
30589. Диалог как основа творчества 30.5 KB
  Диалог как основа творчества. Познание ограничивается самим собой и лишь диалог как форма предполагающая активную деятельность выводит на орбиту социального. Диалог как точно подметил Л. Диалогизм ваейшая черта человеческого бытия.
30590. Ассоциативность мышления журналиста 14.14 KB
  Ассоциация проявляется в метафоре. Эпитет весны здесь выступает и как ассоциация. Ассоциация должна быть яркой и жизненной.а Ассоциация является одним из составляющих творческого начала.
30591. Фантазия, воображение в творчестве журналиста 15.08 KB
  Фантазия воображение в творчестве журналиста.Фантазия и воображение широко используются в творчестве журналиста. Фантазия и воображение являются для журналиста одновременно и помощником и неприятелем. Воображение позволяет представить результат труда до его начала тем самым ориентируя журналиста в процессе творческой деятельности.
30592. Отражение в творчетстве журналиста 13.92 KB
  Отражение в творчетстве журналиста. На уровне организма отражение первично проявляется в раздражимости как возникающей под воздействием внешних и внутренних стимулов способности живой материи отвечать на воздействие избирательной реакцией соответствующей особенностям источника. Такое отражение в процессе развития преобразуется в чувствительность как способность иметь ощущения первичные психические образы среды. Отражение служит предпосылкой развития более сложных форм.
30593. Эмоциональная и реальное в журналистике 14.05 KB
  Эмоции психическое отражение в форме непосредственного пристрастного переживания жизненного смысла явлений и ситуаций обусловленного отношением их объективных свойств к потребностям субъекта.Простейшая форма эмоции т. Эмоции в творчестве выражают оценки явлениям событиям. Трудно представить себе репортаж без эмоции.
30594. Проявление эстетической активности в безобразном и трагическом 14 KB
  Но само изображение жука привлекает нас силой эстетического воздействия. Художественное изображение привлекает внимание именно как эстетически организованное изображение.Проявления комического безобразного трагического в реальной действительности лишь тогда становятся эстетическими реальностями когда они переходя в художественное изображение приобретают тем самым эстетическую организованность и начинают действовать уже не только как бытовые проявления комического безобразного и трагического но и художественного т.