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 в интерактивном режиме. Гибридная хеш-таблица основана на современных идеях из теории хеширования. Одним из наиболее интересных результатов является компромисс между сроками строительства, временем доступа и рационального использования пространства. В описанной здесь реализации есть баланс этих трех метрик, но в приложениях, которые требуют редкого обновления, или которые имеют неограниченное место хранения, можно использовать различные проектные решения.


 

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

29336. Коррекция структурных свойств изображения 54.5 KB
  Коррекция резкости изображения Коррекция резкости изображения в системе поэлементной обработки может осуществляться двумя методами: аппертурным и программным. Аппертурный метод включает аппертурную коррекцию резкости изображения по методу нерезкого маскирования при этом коррекция производится непосредственно при сканировании изображения. В соответствие с этой процедурой производится обработка массива цифровой информации формируя сигнал нерезкого изображения путем интегрирования нескольких пиксель в окрестностях обрабатываемой пиксели.
29337. Геометрические преобразования в системе поэлементной обработки изображения 62 KB
  В процессе преобразования на этапе сканирования формируется пиксель размер которого уже выбран в соответствии с масштабом окончательного изображения. Сложнее при масштабировании изображения записанного в виде цифрового массива высокого разрешения. Сложнее при увеличении или уменьшении изображения не в целое число раз.
29338. Технология обработки изобразительной информации 53.5 KB
  Соотношение свойств изображения на входе системы и свойств изображения которые должны получить на выходе системы диктует ряд преобразований это технологические преобразования. Часть системных преобразований может служить в качестве технологических например преобразование изображения из позитивного в негативное при фотографировании так же могут быть использованы изменения полярности и зеркальности. Так обработка штрихового изображения и растрового изображения цветного или чернобелого осуществляется с использованием разных технологий....
29339. Вычисление экспонирования 39.5 KB
  При правильном выборе экспозиции для широких и узких штрихов и просветов очень узкие штрихи и просветы будут воспроизведены с искажениями. При необходимости возможно воспроизвести геометрически точно штрихи и просветы относящиеся к классу очень узких или суперузких при использовании материала с бесконечно большим коэффициентом контрастности. Однако при таком выборе условий экспонирования все остальные штрихи и просветы в том числе широкие и узкие будут воспроизводиться геометрически не точно а с определенными искажениями геометрических...
29340. Условия результата получения штриховой продукции при коэффициенте контрастности фотографического материала меньше бесконечности 63.5 KB
  Если Dmax полученная  Dmax требуемой то не выполняется одно из требований штрихового изображения и необходимо произвести изменения условий проведения процесса. Градиент получаемого фотографического изображения будет определяться градиентом характеристической кривой: где g 0 градиент оптического изображения где gф градиент фотографического изображения если t= const lgt=0 то lgH=lgE Можем подвести итоги. Факторы влияющие на воспроизведение штрихового изображения: характеристика самого оригинала как правило на входе имеем штрихи с...
29341. Бинарное изображение и битовая карта 49.5 KB
  На воспроизведение штрихового изображения влияют 2 группы факторов: 1 группа факторы определяющие зону размытия пограничной кривой. Определяет резкость изображения на входе аналогично фокусировке в системе фотоаппарата фактор апертурной фильтрации. Эта дискретность возникает как на стадии сканирования вследствие строчной развертки так и на стадии синтеза изображения так же вследствие строчной развертки. В целом границу такого дискретизированного изображения вследствие возникшей ступенчатой структуры можно также представить в виде...
29342. Воспроизведение тонового изображения 46 KB
  Это оригиналы представленные в виде цифровых изображений изготовленных цифровым способом: с помощью цифровых фотокамер методом сканирования. Эта обработка в основном соответствует той обработке в которой нуждаются оригиналы первого класса в системах цифровой обработки. Традиционные оригиналы представляют собой оригиналы аналогового типа в отличие от оригиналов второго класса которые всегда имеют дискретизацию двух видов: в пространстве и по уровню.
29343. Требования к точности для разных классификаций оригиналов 44 KB
  Однако в случае невозможности создания колометрически точного воспроизведения возможно 2 пути решения: 1 формирование колометрически точного воспроизведения большинства цветов изображения и сведения к максимальному приближению тех цветов которые находятся вне цветового охвата. В случае воспроизведения изображения для каталогов цвета чаще всего не являются насыщенными и входят в цветовой охват и задачей является точное воспроизведение необходимых цветов возможно даже за счет искажения цветов окружающих предметов. Ко второму классу...
29344. Special Literary Vocabulary 24.36 KB
  A term unlike other words directs the mind to the essential quality of the thing phenomenon or action as seen by the scientist in the light of his own conceptualization. With the increase of general education and the expansion of technique to satisfy the evergrowing needs and desires of mankind many words that were once terms have gradually lost their quality as terms and have passed into the common literary or even neutral vocabulary. Such words as 'radio' 'television' and the like have long been incommon use and their terminological...