Войти
Одновременные обращения к одной и той же хеш-таблице. A одновременный хэш-таблица (параллельная хеш-карта ) - это реализация хэш-таблиц, позволяющая одновременный доступ для нескольких потоков с использованием хэш-функции .
Параллельные хеш-таблицы, таким образом, представляют собой ключевую параллельную структуру данных для использования в параллельных вычислениях, которые позволяют нескольким потокам более эффективно взаимодействовать для вычислений между общими данными.
Из-за естественных проблем, связанных с одновременным доступом, а именно конкуренции - способ и область действия, в которой к таблице можно получить одновременный доступ, различаются в зависимости от реализации. Более того, результирующая скорость может быть нелинейной с количеством используемых потоков, поскольку необходимо разрешить конфликт, что приводит к накладным расходам на обработку . Существует несколько решений для смягчения последствий разногласий, каждое из которых сохраняет правильность операций с таблицей.
Как и их последовательные аналоги, параллельные хеш-таблицы могут быть обобщены и расширены для соответствия более широкие приложения, например, позволяющие использовать более сложные типы данных для ключей и значений. Однако эти обобщения могут отрицательно повлиять на производительность, и поэтому их следует выбирать в соответствии с требованиями приложения.
При создании параллельных хэш-таблиц функции, обращающиеся к таблице с выбранным алгоритмом хеширования, должны быть адаптированы для параллелизма путем добавления стратегии разрешения конфликтов. Такая стратегия требует управления доступом таким образом, чтобы конфликты, вызываемые ими, не приводили к повреждению данных, в идеале повышая их эффективность при параллельном использовании. Херлихи и Шавит описывают, как доступ к хеш-таблице без такой стратегии - в этом примере, основанном на базовой реализации алгоритма хеширования Cuckoo - можно адаптировать для одновременного использования. Fan et al. дополнительно описать схему доступа к таблице, основанную на хешировании с кукушкой, которое не только является параллельным, но также сохраняет эффективность использования пространства для своей функции хеширования, а также улучшает локальность кеша, а также пропускную способность вставок.
Если размер хеш-таблиц не ограничен и, следовательно, разрешено увеличиваться / уменьшаться при необходимости, алгоритм хеширования необходимо адаптировать, чтобы разрешить эту операцию. Это влечет за собой изменение используемой хэш-функции для отражения нового ключевого пространства таблицы с измененным размером. Алгоритм параллельного роста описан Майером и др.
Mega-KV - это высокопроизводительная система хранения ключей и значений, в которой используется хеширование с кукушкой, а индексирование KV широко распараллеливается в пакетный режим на GPU. Благодаря дальнейшей оптимизации ускорения графического процессора в NVIDIA и Oak Ridge National Lab, компания Mega-KV достигла нового рекорда производительности в 2018 году (до 888 миллионов операций с ключом-значением в секунду).
Одновременный доступ, вызывающий конкуренцию (отмечен красным). Как и любая параллельная структура данных, параллельные хэш-таблицы страдают от множества проблем, известных в области параллельного вычисления в результате раздора. Примерами таких ситуаций являются проблема ABA, состояние гонки и взаимоблокировки. Степень, в которой эти проблемы проявляются или даже возникают вообще, зависит от реализации параллельной хеш-таблицы; конкретно, какие операции таблица позволяет запускать одновременно, а также ее стратегии для смягчения проблем, связанных с конкуренцией. При обработке конфликтов основная цель такая же, как и для любой другой параллельной структуры данных, а именно обеспечение правильности для каждой операции с таблицей. В то же время это, естественно, должно быть сделано таким образом, чтобы при одновременном использовании было более эффективным, чем последовательное решение. Это также известно как управление параллелизмом.
Использование атомарных инструкций, таких как сравнение и замена или fetch-and-add, проблемы, вызванные конфликтом, можно уменьшить, если обеспечить завершение доступа до того, как другой доступ сможет помешать. Такие операции, как сравнение и замена, часто имеют ограничения относительно того, какой размер данных они могут обрабатывать, что означает, что типы ключей и значений таблицы должны быть выбраны или преобразованы соответствующим образом.
Использование так называемого оборудования Транзакционная память (HTM), операции с таблицами можно представить во многом как транзакции базы данных, обеспечивая атомарность. Примером HTM на практике являются Transactional Synchronization Extensions.
С помощью locks операции, пытающиеся одновременно получить доступ к таблице или значениям в ней, могут быть обработаны таким образом, чтобы гарантировать правильное поведение. Однако это может привести к отрицательному воздействию на производительность, в частности, когда используемые блокировки слишком строгие, блокируя доступ, который в противном случае не конкурировал бы и мог бы выполняться без каких-либо проблем. Необходимо предпринять дополнительные меры, чтобы избежать еще более серьезных проблем, угрожающих корректности, таких как временные блокировки, взаимоблокировки или голодание.
Одновременный доступ, сгруппированный в отдельные фазы. Фаза параллельных групп хэш-таблицы доступ путем создания фаз, в которых разрешен только один тип операции (т.е. чистая фаза записи), за которой следует синхронизация состояния таблицы по всем потокам. Формально проверенный алгоритм для этого предложен Шуном и Блеллохом.
Широко используется в ядре Linux, чтение-копирование- update (RCU) особенно полезен в случаях, когда количество чтений намного превышает количество записей.
Естественно, параллельные хеш-таблицы находят применение везде, где полезны последовательные хеш-таблицы. Преимущество параллелизма заключается в потенциальном ускорении этих сценариев использования, а также в повышенной масштабируемости. Принимая во внимание оборудование, такое как многоядерные процессоры, которые становятся все более способными к параллельным вычислениям, важность параллельных структур данных в этих приложениях неуклонно растет.
Maier и другие. провести тщательный анализ различных реализаций параллельных хэш-таблиц, чтобы получить представление об эффективности каждой из них в различных ситуациях, которые могут возникнуть в реальных случаях использования. Наиболее важные выводы можно резюмировать следующим образом:
| Операция | Разногласия | Примечания | |
|---|---|---|---|
| Низкое | Высокое | ||
найти | Очень высокое ускорение как при успешных, так и при неудачных уникальных находках, даже при очень высокой конкуренции | ||
insert | Достигнуто большое ускорение, высокая конкуренция становится проблематичной, когда ключи могут содержать более одного значения (в противном случае вставки просто отбрасываются, если ключ уже существует) | ||
update | Как перезапись, так и модификация существующих значений достигают высокого ускорения, когда конкуренция остается низкой, в противном случае работает хуже, чем последовательное | ||
удаление | Фазовый параллелизм достиг максимальной масштабируемости; Полностью параллельные реализации, в которых deleteиспользует updateс фиктивными элементами, сильно отставали от | ||
Как и ожидалось, низкая конкуренция приводит к положительному поведению во всех операциях, тогда как высокая конкуренция становится проблематичным, когда дело касается письма. Последнее, однако, является проблемой высокой конкуренции в целом, когда преимущество параллельных вычислений сводится на нет из-за естественного требования управления параллелизмом, ограничивающего конкурирующие доступы. В результате накладные расходы вызывают худшую производительность, чем у идеальной последовательной версии. Несмотря на это, параллельные хеш-таблицы по-прежнему оказываются неоценимыми даже в таких сценариях с высокой конкуренцией, если учесть, что хорошо спроектированная реализация может по-прежнему обеспечивать очень высокое ускорение за счет использования преимуществ параллелизма для одновременного чтения данных.
Однако реальные варианты использования параллельных хеш-таблиц часто представляют собой не просто последовательности одной и той же операции, а скорее смесь нескольких типов. Таким образом, когда используется смесь операций insertи find, ускорение и результирующая полезность параллельных хеш-таблиц становятся более очевидными, особенно при наблюдении findтяжелых рабочих нагрузок..
В конечном итоге результирующая производительность параллельной хеш-таблицы зависит от множества факторов в зависимости от ее желаемого приложения. При выборе реализации важно определить необходимую степень общности, стратегии обработки разногласий и некоторые соображения о том, можно ли заранее определить размер желаемой таблицы или вместо этого следует использовать подход увеличения.
std :: unordered_mapинтерфейс. Включены параллельные неупорядоченные мультиотображения, которые позволяют нескольким значениям существовать для одного и того же ключа в параллельной неупорядоченной карте. Кроме того, предоставляются параллельные хэш-карты, которые основываются на параллельной неупорядоченной карте и дополнительно допускают одновременное стирание и содержат встроенную блокировку.