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


 

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

42167. ДІЇ НАД МАТРИЦЯМИ 137 KB
  Знайти і видати на екран і в файл значення: сум модулів елементів кожного стовпчика матриці А, середнього арифметичного найменших елементів кожного рядка матриці А; обчислити матрицю В, яка визначається за формулами і видати на екран; в матриці А поміняти місцями найбільший за модулем елемент останнього рядка і найменший за модулем елемент першого стовпчика і видати на екран.
42168. Тригери. Опис тригерів на мові VHDL 225.5 KB
  Хід роботи Отримати у викладача завдання на лабораторну роботу відповідно до номера свого варіанту.3 – Примітиви тригерів які використовуються пакетом Qurtus II № варіанта dff jkffe Виписати з довідника параметри мікросхем які використовувались при створенні схеми таблиці дійсності та часові діаграми роботи тригерів. Допуском до виконання лабораторної роботи є розроблена електрична принципова схема та часові діаграми її роботи побудовані з врахуванням затримок. При побудові часових діаграм проглянути всі режими роботи схеми.
42169. Регістри. Принципи побудови та часові діаграми регістрів 133.5 KB
  Допуском на лабораторну роботу є виписані часові діаграми регістра вказаного в стовбці Тип регістра таблиці 6.1 а також схема та часові діаграми роботи трьох розрядного регістра тип якого вказаний в таблиці 6. Зібрати в пакеті Qurtus II схему перевірки стандартного регістра тип якого вказаний в стовбці Аналог таблиці 6. Побудувати часові діаграми для перевірки регістра і порівняти їх з діаграмами виписаними в п.
42170. ИССЛЕДОВАНИЕ СЛОЖНОЙ ЭЛЕКТРИЧЕСКОЙ ЦЕПИ ПОСТОЯННОГО ТОКА 151.5 KB
  Измерить и проверить расчетом потенциалы точек контура сложной электрической цепи. Для расчета простых электрических цепей используют закон Ома для участка цепи не содержащего ЭДС. Например если между двумя точками а и b в электрической цепи включены только пассивные элементы – резисторы то закон Ома для этого участка цепи запишется: .
42171. ИССЛЕДОВВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПОСЛЕДОВАТЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ЕМОСТНОГО СОПРОТИВЛЕНИЙ 247 KB
  Экспериментальное исследование характера изменения тока мощности и падений напряжений на участках последовательной цепи состоящей из активного и емкостного сопротивлений а также построение круговой диаграммы. При прохождении синусоидального тока по цепи изображенной на рис.1а следует иметь ввиду что ток в любом сечении цепи один и тот же а общее напряжение согласно второму закону Кирхгофа равно геометрической сумме...
42172. ИССЛЕДОВВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПОСЛЕДОВАТЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ИНДУКТИВНОГО СОПРОТИВЛЕНИЙ 299.5 KB
  Экспериментальное исследование характера изменения тока мощности и падений напряжений на участках последовательной цепи состоящей из активного и индуктивного сопротивлений а также построение круговой диаграммы. При прохождении синусоидального тока по цепи изображенной на рис.1б ток в любом сечении цепи один и тот же а общее напряжение согласно второму закону Кирхгофа равно геометрической сумме падений напряжений на...
42173. ИССЛЕДОВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПОСЛЕДОВАТЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО, ИНДУКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ. РЕЗОНАНС НАПРЯЖЕНИЙ 271.5 KB
  РЕЗОНАНС НАПРЯЖЕНИЙ Цель работы: Исследование явления резонанса напряжений построение резонансных кривых и векторных диаграмм.1 следует иметь в виду что ток в любом элементе схемы один и тот же а питающее напряжение согласно второму закону Кирхгофа равно алгебраической сумме мгновенных значений напряжений на отдельных элементах схемы: 4.2 приведены векторные диаграммы напряжений и токов схемы рис. Ток совпадает по фазе с напряжением угол  = 0 cos = 1 и этот режим называется резонансом напряжений.
42174. ИССЛЕДОВАНИЕ ТЕХНОЛОГИИ ФОРМАТИРОВАНИЯ СЛОЖНЫХ ПО ФОРМАТУ ДОКУМЕНТОВ 654.5 KB
  Рукописные работы дипломные работы курсовые работы рефераты отчёты и пр. Основная часть рукописной работы Раздел 2 следует за титульным листом начинается со страницы № 2 обычно имеет оглавление. Заголовок 1 для глав работы Заголовок 2 для параграфов. Например для форматирования реквизитов Название организации Исполнитель Руководитель работ Название специальности Тема дипломной работы и пр.
42175. ИССЛЕДОВАНИЕ ЦЕПИ ПЕРЕМЕННОГО ТОКА С ПАРАЛЛЕЛЬНЫМ СОЕДИНЕНИЕМ АКТИВНОГО И ЕМКОСТНОГО СОПРОТИВЛЕНИЙ 203 KB
  Общие теоретические сведения В схеме рис.1 Векторная диаграмма этой схемы представлена на рис. Рис. Диаграмма представленная на рис.Ток совпадает по фазе с напряжением . Из точки О1 откладываем отрезок О1К = I2k /mI , по направлению вектора . Отрезок О1К является хордой круговой диаграммы . В масштабе mz откладываем по направлению отрезка О1К отрезок О1А = R2 /mz и из точки А под углом 900 к линии О1К проводим линию изменяющегося параметра AN’. Перпендикуляр, к линии изменяющегося параметра, опущенный из точки О1 совпадает по направлению с хордой.