Параллельная хеш-таблица
или Параллельная хеш-таблица параллельная хеш-карта — это реализация хеш-таблиц, обеспечивающая одновременный доступ нескольких потоков с использованием хэш-функции . [1] [2]
Параллельные хэш-таблицы представляют собой ключевую структуру параллельных данных для использования в параллельных вычислениях , которая позволяет нескольким потокам более эффективно взаимодействовать при вычислениях между общими данными. [1]
Из-за естественных проблем, связанных с одновременным доступом, а именно конкуренции , способ и область одновременного доступа к таблице различаются в зависимости от реализации. Более того, результирующее ускорение может не зависеть от количества используемых потоков, поскольку необходимо разрешить конфликты, что приводит к накладным расходам на обработку . [1] Существует несколько решений для смягчения последствий разногласий, каждое из которых сохраняет корректность операций с таблицей. [1] [2] [3] [4]
Как и их последовательный аналог, параллельные хэш-таблицы можно обобщить и расширить для соответствия более широким приложениям, например, позволяя использовать более сложные типы данных для ключей и значений. Однако эти обобщения могут отрицательно повлиять на производительность, поэтому их следует выбирать в соответствии с требованиями приложения. [1]
Параллельное хеширование [ править ]
При создании параллельных хеш-таблиц функции, обращающиеся к таблице с выбранным алгоритмом хеширования, необходимо адаптировать для параллельного выполнения, добавив стратегию разрешения конфликтов. Такая стратегия требует управления доступом таким образом, чтобы вызванные ими конфликты не приводили к повреждению данных, а в идеале повышали их эффективность при параллельном использовании. Херлихи и Шавит [5] описать, как доступ к хэш-таблице без такой стратегии (в ее примере, основанном на базовой реализации алгоритма хеширования Cuckoo ) может быть адаптирован для одновременного использования. Фан и др. [6] далее опишите схему доступа к таблице, основанную на хешировании с кукушкой, которая не только является одновременной, но и сохраняет эффективность использования пространства своей функции хеширования, одновременно улучшая локальность кэша, а также пропускную способность вставок.
Когда хеш-таблицы не ограничены по размеру и, таким образом, могут при необходимости увеличиваться/сжиматься, алгоритм хеширования необходимо адаптировать для обеспечения выполнения этой операции. Это влечет за собой изменение используемой хеш-функции, чтобы отразить новое пространство ключей таблицы измененного размера. Алгоритм одновременного выращивания описан Maier et al. [1]
Мега-КВ [7] — это высокопроизводительная система хранения значений «ключ-значение», в которой используется хэширование «кукушка» , а индексация KV массово распараллеливается в пакетном режиме с помощью графического процессора. Благодаря дальнейшей оптимизации ускорения графического процессора, проведенной Nvidia и Национальной лабораторией Ок-Ридж , Mega-KV удалось достичь еще одного рекорда пропускной способности в 2018 году (до 888 миллионов операций «ключ-значение» в секунду). [8]
Разрешение конфликтов [ править ]
Как и в случае с любой параллельной структурой данных, параллельные хеш-таблицы страдают от множества проблем, известных в области параллельных вычислений, в результате конкуренции. [3] Примерами таких проблем являются проблемы ABA , состояния гонки и взаимоблокировки .Степень проявления или даже возникновения этих проблем зависит от реализации параллельной хэш-таблицы; в частности, какие операции таблица позволяет выполнять одновременно, а также ее стратегии по смягчению проблем, связанных с конкуренцией. При разрешении конфликтов основная цель та же, что и при работе с любой другой параллельной структурой данных, а именно обеспечение корректности каждой операции с таблицей. При этом, естественно, это должно быть сделано таким образом, чтобы быть более эффективным, чем последовательное решение при одновременном использовании. Это также известно как управление параллелизмом .
Атомарные инструкции [ править ]
Используя атомарные инструкции, такие как сравнение и замена или выборка и добавление , проблемы, вызванные конфликтами, можно уменьшить, гарантируя, что доступ будет завершен до того, как другой доступ сможет вмешаться. Такие операции, как сравнение и замена, часто имеют ограничения на размер данных, которые они могут обрабатывать, а это означает, что типы ключей и значений таблицы должны выбираться или преобразовываться соответствующим образом. [1]
Используя так называемую аппаратную транзакционную память (HTM), табличные операции можно рассматривать как транзакции базы данных . [3] обеспечение атомарности. Примером HTM на практике являются расширения синхронизации транзакций .
Блокировка [ править ]
С помощью блокировок операции, пытающиеся одновременно получить доступ к таблице или значениям внутри нее, могут обрабатываться таким образом, чтобы обеспечить правильное поведение. Однако это может привести к негативным последствиям для производительности, [1] [6] в частности, когда используемые блокировки слишком ограничительны, что блокирует доступ, который в противном случае не конкурировал бы и мог бы выполняться без каких-либо проблем. Необходимо принять дополнительные меры, чтобы избежать еще более серьезных проблем, угрожающих корректности, таких как блокировки, взаимоблокировки или голодание . [3]
Фазовый параллелизм [ править ]
Доступ к хэш-таблице с параллельным этапом группируется путем создания фаз, в которых разрешен только один тип операции (т. е. чистая фаза записи), за которой следует синхронизация состояния таблицы во всех потоках. Формально доказанный алгоритм для этого предложен Шуном и Блеллохом. [2]
Чтение-копирование-обновление [ править ]
Широко используется в ядре Linux , [3] чтение-копирование-обновление (RCU) особенно полезно в тех случаях, когда количество операций чтения намного превышает количество операций записи. [4]
Приложения [ править ]
Естественно, параллельные хэш-таблицы находят применение везде, где полезны последовательные хэш-таблицы. Преимущество параллелизма в данном случае заключается в потенциальном ускорении этих вариантов использования, а также в повышенной масштабируемости. [1] Учитывая аппаратное обеспечение, такое как многоядерные процессоры , которые становятся все более способными к параллельным вычислениям, важность параллельных структур данных в этих приложениях неуклонно растет. [3]
Анализ производительности [ править ]
Майер и др. [1] выполнить тщательный анализ различных параллельных реализаций хеш-таблиц, давая представление об эффективности каждой из них в различных ситуациях, которые могут возникнуть в реальных случаях использования. Наиболее важные выводы можно резюмировать следующим образом:
| Операция | Разногласия | Примечания | |
|---|---|---|---|
| Низкий | Высокий | ||
find | Очень высокое ускорение как при успешных, так и при неудачных уникальных находках, даже при очень высоком уровне конкуренции. | ||
insert | Достигнуто высокое ускорение, высокая конкуренция становится проблематичной, когда ключи могут содержать более одного значения (в противном случае вставки просто отбрасываются, если ключ уже существует). | ||
update | Как перезапись, так и изменение существующих значений достигают высоких скоростей, когда конкуренция остается низкой, в противном случае производительность хуже, чем последовательная. | ||
delete | Фазовый параллелизм достиг высочайшей масштабируемости; Полностью параллельные реализации, где delete использует update с элементами-пустышками были вплотную позади | ||
Как и ожидалось, низкий уровень конфликтов приводит к положительному поведению во всех операциях, тогда как высокий уровень конфликтов становится проблематичным, когда дело доходит до записи. Последнее, однако, в целом представляет собой проблему высокой конкуренции, при которой преимущества параллельных вычислений сводятся на нет из-за естественного требования к управлению параллелизмом, ограничивающему конкурирующий доступ. В результате накладные расходы приводят к ухудшению производительности по сравнению с идеальной последовательной версией.Несмотря на это, параллельные хеш-таблицы по-прежнему оказываются неоценимыми даже в таких сценариях с высокой конкуренцией, если учесть, что хорошо спроектированная реализация все еще может обеспечить очень высокое ускорение за счет использования преимуществ параллелизма для одновременного чтения данных.
Однако реальные случаи использования параллельных хеш-таблиц часто представляют собой не просто последовательности одной и той же операции, а скорее смесь нескольких типов.Таким образом, когда смесь insert и find операций, ускорение и, как следствие, полезность параллельных хеш-таблиц становятся более очевидными, особенно при наблюдении find большие нагрузки.
В конечном итоге конечная производительность параллельной хеш-таблицы зависит от множества факторов, зависящих от ее желаемого применения. При выборе реализации важно определить необходимую степень общности, стратегии обработки конфликтов и некоторые мысли о том, можно ли заранее определить размер желаемой таблицы или вместо этого следует использовать растущий подход.
Реализации [ править ]
- Начиная с Java 1.5 , параллельные хеш-карты предоставляются на основе интерфейса параллельных карт . [9]
- libcuckoo предоставляет параллельные хэш-таблицы для C / C++, позволяющие одновременное чтение и запись. Библиотека доступна на GitHub. [10]
- Строительные блоки потоков предоставляют параллельные неупорядоченные карты для C++, которые допускают одновременную вставку и обход и сохраняются в стиле, аналогичном C++11.
std::unordered_mapинтерфейс. Включены параллельные неупорядоченные мультикарты, которые позволяют существовать нескольким значениям для одного и того же ключа в параллельной неупорядоченной карте. [11] Кроме того, предоставляются параллельные хеш-карты, которые основаны на параллельной неупорядоченной карте и дополнительно допускают одновременное стирание и содержат встроенную блокировку. [12] - Grot обеспечивает параллельное увеличение хэш-таблиц для C++ на основе так называемой фольклорной реализации. На основе этой нерастущей реализации предоставляется множество различных растущих хеш-таблиц. Эти реализации допускают одновременное чтение, вставку, обновление (в частности, обновление значений на основе текущего значения ключа) и удаление (на основе обновления с использованием надгробий ). варианты на базе Intel TSX Кроме того, предусмотрены . Библиотека доступна на GitHub. [1] [13]
- глупость предоставляет параллельные хэш-таблицы [14] для C++14 и более поздних версий, обеспечивающих чтение без ожидания и сегментированную запись на основе блокировок. Как указано на ее странице GitHub, эта библиотека предоставляет полезный функционал для Facebook . [15]
- Junction предоставляет несколько реализаций параллельных хэш-таблиц для C++ на основе атомарных операций, чтобы гарантировать потокобезопасность для любой заданной функции-члена таблицы. Библиотека доступна на GitHub. [16]
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и ж г час я дж к Майер, Тобиас; Сандерс, Питер; Дементьев, Роман (март 2019 г.). «Параллельные хеш-таблицы: быстро и универсально (?)!». Транзакции ACM при параллельных вычислениях . 5 (4). Нью-Йорк, штат Нью-Йорк, США: ACM. Статья 16. doi : 10.1145/3309206 . ISSN 2329-4949 . S2CID 67870641 .
- ^ Jump up to: Перейти обратно: а б с Шун, Джулиан; Белллох, Гай Э. (2014). «Фазово-параллельные хеш-таблицы для детерминизма». SPAA '14: Материалы 26-го симпозиума ACM по параллелизму в алгоритмах и архитектурах . Нью-Йорк: ACM. стр. 96–107. дои : 10.1145/2612669.2612687 . ISBN 978-1-4503-2821-0 .
- ^ Jump up to: Перейти обратно: а б с д и ж Ли, Сяочжоу; Андерсен, Дэвид Г.; Каминский, Майкл; Фридман, Майкл Дж. (2014). «Алгоритмические улучшения для быстрого одновременного хеширования с кукушкой». Материалы девятой Европейской конференции по компьютерным системам . ЕвроСис '14. Нью-Йорк: ACM. Статья № 27. doi : 10.1145/2592798.2592820 . ISBN 978-1-4503-2704-6 .
- ^ Jump up to: Перейти обратно: а б Триплетт, Джош; Маккенни, Пол Э.; Уолпол, Джонатан (2011). «Изменяемые, масштабируемые, параллельные хэш-таблицы с помощью релятивистского программирования» . USENIXATC'11: Материалы конференции USENIX 2011 года, посвященной ежегодной технической конференции USENIX . Беркли, Калифорния: Ассоциация USENIX. п. 11.
- ^ Херлихи, Морис; Шавит, Нир (2008). «Глава 13: Параллельное хеширование и естественный параллелизм». Искусство многопроцессорного программирования . Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc., стр. 316–325. ISBN 978-0-12-370591-4 .
- ^ Jump up to: Перейти обратно: а б Фан, Бин; Андерсен, Дэвид Г.; Каминский, Майкл (2013). «MemC3: компактный и параллельный MemCache с более простым кэшированием и более разумным хешированием» . nsdi'13: Материалы 10-й конференции USENIX по проектированию и внедрению сетевых систем . Беркли, Калифорния: Ассоциация USENIX. стр. 371–384.
- ^ Чжан, Кай; Ван, Кайбо; Юань, Юань; Го, Лэй; Ли, Рубао; и Чжан, Сяодун (2015). « Мега-KV: аргумент в пользу графических процессоров для максимизации пропускной способности хранилищ ключей и значений в памяти». Труды Фонда VLDB, Vol. 8, № 11, 2015.
- ^ Чу, Чинг-Синг; Потлури, Шрирам; Госвами, Аншуман; Венката, Манджунатх Горентла; Имам Нинаанд; и Ньюберн, Крис Дж. (2018) « Проектирование высокопроизводительных операций «ключ-значение» в памяти с постоянными ядрами графического процессора и OPENSHMEM». .
- ^ Документация Java ConcurrentHashMap
- ^ Репозиторий GitHub для libcuckoo.
- ^ Документация по строительным блокам потоков concurrent_unordered_map и concurrent_unordered_multimap
- ^ Документация по строительным блокам потоков concurrent_hash_map
- ^ Репозиторий GitHub для роста.
- ^ Страница GitHub для глупой реализации параллельных хеш-карт.
- ^ Репозиторий GitHub для глупости
- ^ Репозиторий GitHub для Junction.
Дальнейшее чтение [ править ]
- Херлихи, Морис; Шавит, Нир (2008). «Глава 13: Параллельное хеширование и естественный параллелизм». Искусство многопроцессорного программирования . Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc., стр. 299–328. ISBN 978-0-12-370591-4 .
| Общий | |
|---|---|
| Процесс исчисления | |
| Классические задачи | |
