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


 

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

45958. Новые металлические материалы: композиционные материалы, металлические стекла, металлы с памятью формы- свойства, состав, применение 182.71 KB
  Новые металлические материалы: композиционные материалы металлические стекла металлы с памятью формы свойства состав применение. К новым Ме материалам относят: 1 сплавы с эффектом памяти формы 2 ситаллы 3 комп ситаллы которые имеютозиционные материалы 4 порошковые материалы. Композиционные материалы состоят из основы матрицы и упрочнителя. В качестве матрицы используются Ме материалы нержавейка Х18Н8Туглеродные материалы карбонкерамические материалы.
45959. Стекло и керамика: состав, свойства, технология изготовления деталей, применение в машиностроении 13.86 KB
  Стекло и керамика: состав свойства технология изготовления деталей применение в машиностроении. По сост делятся: на силикаты SiO2 алюмосиликатные l2O3SiO2 и бромосиликатные B2O3SiO2. Технология изготовления стеклянных изделий состоит из следующих операций: варка стекла в многотонных печах ванного типа прокатка листового стекла прессование выдувание спекание из стеклянного порошка литье под давлением и центробежное литье. В состав керамики могут входить глины шамит песок полевой шпат и тд.
45960. Производства чугуна: исходные материалы, устройство доменной печи, технология плавки чугуна, продукты доменной плавки 72.17 KB
  РУДЫ ФЛЮСЫ И ТОПЛИВО Железные руды основной исходный материал для выплавки чугуна. Железные руды в отличие от медных и многих других относительно богаты. Наиболее богатые руды содержат 60 железа и больше наиболее бедные 3040. По типу рудного минерала руды бывают следующих основных видов.
45961. Способы изготовления отливок. Изготовление отливок в песчаных формах. Ручная, машинная и вакуумная формовка 15.44 KB
  Основными способами изготовления отливок является литье в песчаные формы по выплавляемым моделям в оболочковые формы в кокиль под давлением и центробежное. Указанными способами можно изготовлять отливки в разовые формы литье в песчаные формы по выплавляемым моделям и в оболочковые формы и в металлические формы литье в кокиль под давлением и центробежное. Литейные формы изготовляют как из неметаллических материалов песчаные формы формы изготовляемые по выплавляемым моделям оболочковые формы для одноразового...
45962. Специальные способы литья: литьё по выплавляемым моделям, литьё в оболочковые формы, литьё в металлические формы, центробежное литьё 19.78 KB
  Специальные способы литья Из специальных способов литья в настоящее время распространены литье в металлические формы центробежное литье литье под давлением точное литье по выплавляемым моделям литье методом вакуумного всасывания и литье в оболочковые формы. Отливки получаются без швов у форм нет разъемов размеры отливок получаются точными чем при литье в землю так как здесь исключены причины потери точности от расколачивания формы моделью при ее извлечении перекос половинок формы подъем верхней опоки и раздутие формы под давлением...
45963. Специальные способы литья: литьё под высоким давлением, непрерывное литьё, электрошлаковое литьё. Преимущества, недостатки, применение 188.05 KB
  Непрерывное литьё Перевод Непрерывное литьё металлов и сплавов процесс получения слитков и заготовок основанный на равномерном перемещении металла относительно зон заливки и кристаллизации. Равномерные скорости подачи жидкого металла его кристаллизации и удаления готовой отливки при Н. обеспечивают постоянство состава строения и свойств металла по всей длине отливки. Путём усиленного отвода тепла благодаря непосредственному охлаждению металла водой можно повысить скорость кристаллизации и при правильно выбранной скорости литья...
45964. Прокат и его производство 47.57 KB
  Процесс прокатки обеспечивается силами трения между вращающимся инструментом и заготовкой благодаря которым заготовка перемещается в зазоре между валками одновременно деформируясь. Способы прокатки Когда требуется высокая прочность и пластичность применяют заготовки из сортового или специального проката. В процессе прокатки литые заготовки подвергают многократному обжатию в валках прокатных станов в результате чего повышается плотность материала за счт залечивания литейных дефектов пористости микротрещин. Существуют три основных...
45965. Свободная ковка: основные операции и инструмент. Горячая объёмная штамповка. Технологический процесс горячей объёмной штамповки 15.85 KB
  Горячая объёмная штамповка это вид обработки материалов давлением при котором формообразование поковки из нагретой заготовки осуществляют с помощью специального инструмента штампа. Горячей объёмной штамповкой можно получать без напусков поковки сложной конфигурации которые ковкой изготовить без напусков нельзя при этом допуски на штамповочную поковку в 3 4 раза меньше чем на кованную Горячей объёмной штамповкой...
45966. Холодная объёмная и листовая штамповка - основные операции и оборудование. Формообразование заготовок из порошковых материалов 50.48 KB
  Операции листовой штамповки делятся на два основных класса: разделительные в которых одна часть заготовки отделяется от другой и формоизменяющие при которых получают изделия сложной формы за счет деформации металла заготовки без его разрушения. Резка последовательное отделение части заготовки от прямой или кривой линии это заготовительная операция. Вырубка операция единовременного отделения материала от заготовки по замкнутому контуру причем отделяемая часть является изделием. Гибка формоизменяющая операция для получения изогнутой...