ПараллельноехешірованіенаGPU в реальному часі
У рефераті представлений ефективний алгоритм паралелізму даних для побудови великих хеш-таблиць на мільйони елементів в режимі реального часу. Розглядаються два паралельних алгоритму: класичний підхід розрідженого ідеального хеширования і хешування методом зозулі, при якому елементи упаковуються щільно, дозволяючи елементу зберігатися в одному з декількох можливих місць. Пропонується також гібридний підхід, який використовує обидва алгоритму. Було виміряно час побудови таблиць, час доступу і використання пам'яті запропонованих реалізацій, і демонстрація в режимі реального часу на великих наборах даних: для 5 мільйонів пар ключ-значення хеш-таблиця будується за 35,7 мс, використовуючи в 1,42 рази більше пам'яті , ніж самі вхідні дані, і можна отримати доступ до всіх елементів цієї хеш-таблиці за 15,3 мс. Для порівняння, для сортування тих же даних потрібно 36,6 мс, а доступ до всіх елементів за допомогою бінарного пошуку вимагає 79,5 мс.
Хешування (іноді хешування, англ. Hashing) - перетворення вхідного масиву даних довільної довжини в вихідну бітову рядок фіксованої довжини. Такі перетворення також називаються хеш-функціями або функціями згортки.
Хеш-таблиця - це структура даних, що реалізує інтерфейс асоціативного масиву, а саме, вона дозволяє зберігати пари (ключ, значення) і виконувати три операції:
операцію додавання нової пари;
операцію видалення пари по ключу.
Колізією хеш-функції h називається два різних вхідних блоку даних x та y таких, що h (x) = h (y). Колізії існують для більшості хеш-функцій, але для «хороших» хеш-функцій частота їх виникнення близька до теоретичного мінімуму.
Поява програмованих графічних апаратних засобів дозволило паралельним графічним процесорам (GPU) обчислювати та використовувати різні уявлення даних.
Наприклад, дослідники недавно продемонстрували ефективне паралельне побудова для ієрархічних просторових структур даних, таких як k-d дерева (k-мірні дерева). Взагалі, істотна проблема для дослідження - це визначення відповідних паралельних структур даних, які можуть бути створені, змінені і до яких був би доступ. Інструментальних засобів для обробки структур даних і пов'язаних з ними алгоритмів залишається значно більше на скалярною архітектурі, наприклад на центральному процесорі (CPU), ніж на паралельній архітектурі, наприклад на графічних процесорах (GPU).
У цій статті розглядається проблема реалізації паралельної структури даних, яка забезпечує довільний доступ до мільйонів елементів і яка може бути побудована за короткий термін. У такої структури даних є численні застосування в комп'ютерній графіці, зосередженої на додатках, які повинні зберігати рідкісний набір пунктів в компактному поданні. На центральному процесорі найбільш поширена структура даних для такого завдання - хеш-таблиця. Однак звичайні послідовні алгоритми для будівництва та виклику хеш-таблиць не легко перевести до паралельної середовищі GPU по трьом причинам.
Алгоритми заповнення традиційної хеш-таблиці мають тенденцію залучати послідовні операції. Формування ланцюжка, наприклад, вимагає, щоб багато елементів були додані до кожного зв'язного списку, який вимагав би перетворення в послідовну форму доступу до структури списку на GPU.
2) .Последовательность проб.
Послідовність, в якій проглядаються осередку хеш-таблиці, називається послідовністю проб. Кількість проб, необхідних для пошуку елемента в типових послідовних хеш-таблицях, змінюється в залежності від запиту, наприклад, для ланцюжка потрібне проходження зв'язкових списків, які розрізняються по довжині. Це призведе до неефективності в GPU, де SIMD ядра змусять всі нитки чекати найгірший випадок.
Хеш-таблиці за своєю природою мають невелику наповненістю в будь-якому випадку побудови або доступу, так що обчислювальні ієрархії мають мало можливостей для підвищення продуктивності.
Одним з головних переваг хеш-таблиці в послідовних обчисленнях є те, що це, по суті, динамічні структури даних, для яких час видалення та вставки має вигляд O (1). Але часто немає необхідності мати динамічну структуру даних на GPU: якщо деякі або всі елементи даних в хеш-таблиці змінюються на кожному кроці, то таблиця відновлюється з нуля.
Побудова хеш-таблиць в режимі реального часу і час доступу корисно використовувати в самих різних додатках, які вимагають розріджених даних. Наприклад, для графічних додатків: просторове змішування для виявлення перетину рухомих даних, а також геометричне хешування для функції відповідності. Виявляється, що просторовий хеш на віртуальній 1283 сітці може бути побудований на кожному кадрі приблизно за 27 кадрів в секунду. Геометричне хешування - це групові GPU додатки, що вимагають інтенсивного довільного доступу до таблиці пар характерних точок.
3 Види хеширования
3.1 Ідеальне хешування
Як і в багатьох роботах по створенню хеш-таблиць на GPU, ми концентруємося на побудові ідеальної хеш-таблиці. Класичне побудова ідеальної хеш-таблиці Фрідмана та ін. [1984] (FKS-побудова) грунтується на спостереженні, що якщо розмір таблиці m набагато більше, ніж число елементів n. особливо якщо m = О (n2). то з деякою постійною ймовірністю випадково обрана хеш-функція не матиме колізій зовсім, і буде давати постійний час пошуку. Щоб отримати постійне час пошуку при лінійному просторі, в FKS-побудові використовується дворівнева таблиця. На верхньому рівні елементи хешіруются в сегменти, а нижній рівень хешірует сегмент з k елементів в буфер розміру O (k 2). Поки кожен сегмент має тільки O (1) очікуваних елементів, очікуваний розмір хеш-таблиці дорівнює O (n) і час пошуку кожного елемента O (1). Основний недолік в тому, що для досягнення оптимального завантаження, скажімо, 1/4, потрібно дуже багато маленьких сегментів.
3.2 Хешування з множинним вибором (альтернативне) і хешування методом зозулі
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-побудови, спочатку знаходимо хеш-функцію першого рівня для поділу на більш дрібні сегменти. В рамках кожного сегмента, потім використовуємо паралельне хешування методом зозулі для розміщення елементів за трьома підтаблиці. Оскільки воно виконується повністю на внутрикристальной пам'яті, то на практиці виявляється дуже швидким.
У цьому розділі описується реалізація, яка використовує програмно-апаратну архітектуру CUDA, що дозволяє робити обчислення з використанням графічних процесорів NVIDIA.
Припустимо, що входом є безліч n елементів - цілих пар ключ-значення (k, v). де всі ключі є унікальними. Процес побудови наводиться в алгоритмі 1, і складається з двох етапів.
1 етап розподіляє елементи між сегментами з використанням хеш-функції h. переставляючи дані так, щоб елементи кожного сегмента знаходилися в безперервній області пам'яті, це покращує доступ до пам'яті структури для 2 етапу.
2 етап паралельно будує окремі хеш-таблиці за методом зозулі для кожного сегмента, використовуючи швидку пам'ять, що розділяється, а потім переписує свої таблиці в глобальну пам'ять в єдиний масив, чергуючи ключі і значення.