526

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

Реферат

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

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

Русский

2013-01-06

84 KB

14 чел.

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


 

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

16406. Финансовые функции Excel ПРОЦПЛАТ, ОСПЛТ 72.5 KB
  Финансовые функции Excel ПРОЦПЛАТ ОСПЛТ. Рассмотрим пример вычисления основных платежей платы по процентам общей ежегодной платы и остатка долга на примере ссуды 100000руб. на срок 5 лет при годовой ставке 2 представленной на рисунке: Ежегодная плата вычисляется в ячей...
16408. Финансовые функции Excel. Пример расчета эффективности капиталовложений с помощью функции ПС 145.5 KB
  Финансовые функции Excel. Пример расчета эффективности капиталовложений с помощью функции ПС. Рассмотрим следующую задачу. Вас просят дать в долг 10000 руб. и обещают возвращать по 2000руб. в течении 6 лет. Будет ли выгодна эта сделка при годовой ставке 7 В приведенно на рисунке...
16409. Финансовые функции Excel. Пример расчета эффективности капиталовложений с помощью функции ПЗ 144.5 KB
  Финансовые функции Excel. Пример расчета эффективности капиталовложений с помощью функции ПЗ. Рассмотрим следующую задачу. Вас просят дать в долг 10000 руб. и обещают возвращать по 2000руб. в течении 6 лет. Будет ли выгодна эта сделка при годовой ставке 7 В приведенно на рисунке...
16410. Практическое задание: использование функции вертикального просмотра (ВПР) 65.5 KB
  Практическое задание: использование функции вертикального просмотра ВПР Функция ВПР ищет значение в крайнем левом столбце справочной таблицы и возвращает значение в той же строке из указанного столбца таблицы. Синтаксическая форма ВПРискомое_значение;таблица;...
16411. ФУНКЦИИ EXCEL. ВВОД ФУНКЦИЙ В РАБОЧЕМ ЛИСТЕ EXCEL 133.75 KB
  Лекция 1. ФУНКЦИИ EXCEL Функции Excel это специальные заранее созданные формулы которые позволяют легко и быстро выполнять сложные вычисления. Их можно сравнить со специальными клавишами на калькуляторах предназначенных для вычисления квадратных корней логарифмов и про...
16412. Емпіричне дослідження гендерних особливостей міжособистісної взаємодії у ранній юності 403.5 KB
  Проблема стосунків жінки і чоловіка в суспільстві прадавня. Сьогодні вона набула особливої гостроти оскільки в світі активізується боротьба за ствердження демократичних норм і принципів. У цьому контексті гендерне партнерство (рівні відносини статей), гендерна рівність набувають все більшої актуальності.
16413. Национальные проекты в России, как одна из форм государственного управления. Национальный проект «Демография» 1.23 MB
  Причины депопуляции в ошибках конкретных государственных правителей — Депопуляция процесс объективный, исторически заданный. Для России низкая рождаемость, ведущая к депопуляции, будет иметь катастрофические последствия. — Депопуляция нежелательна, но не катастрофична; противостоять ей можно.
16414. Планирование, как функция управления 113.5 KB
  Планирование как функция управления Понятие функции управления. Функция планирование. Процесс стратегического планирования. I. Суть любого управления – это достижение организацией целей при наиболее оптимальном использовании ресурсов. ...