Współbieżna tablica mieszająca
Współbieżna wątkom tablica skrótów ( mapa mieszania współbieżnego ) to implementacja tablic mieszających umożliwiająca współbieżny dostęp wielu za pomocą funkcji mieszającej .
Współbieżne tablice skrótów reprezentują kluczową współbieżną strukturę danych do użytku w obliczeniach współbieżnych , która umożliwia wydajniejszą współpracę wielu wątków w celu obliczeń między współdzielonymi danymi.
Ze względu na naturalne problemy związane z równoczesnym dostępem - a mianowicie rywalizację - sposób i zakres współbieżnego dostępu do tabeli różni się w zależności od implementacji. Ponadto wynikające z tego przyspieszenie może nie być liniowe w stosunku do liczby używanych wątków, ponieważ rywalizacja musi zostać rozwiązana, co powoduje narzut związany z przetwarzaniem . Istnieje wiele rozwiązań łagodzących skutki rywalizacji, z których każde zachowuje poprawność operacji na stole.
Podobnie jak w przypadku ich sekwencyjnego odpowiednika, współbieżne tablice skrótów można uogólniać i rozszerzać, aby pasowały do szerszych aplikacji, na przykład umożliwiając stosowanie bardziej złożonych typów danych dla kluczy i wartości. Te uogólnienia mogą jednak negatywnie wpłynąć na wydajność i dlatego powinny być wybierane zgodnie z wymaganiami aplikacji.
Równoczesne haszowanie
Podczas tworzenia współbieżnych tablic mieszających funkcje uzyskujące dostęp do tabeli za pomocą wybranego algorytmu mieszającego należy dostosować do współbieżności, dodając strategię rozwiązywania konfliktów. Taka strategia wymaga zarządzania dostępami w taki sposób, aby wywołane przez nie konflikty nie skutkowały uszkodzeniem danych, a idealnie zwiększały ich efektywność, gdy są używane równolegle. Herlihy i Shavit opisują, w jaki sposób dostępy do tablicy mieszającej bez takiej strategii - w jej przykładzie opartym na podstawowej implementacji algorytmu mieszającego Cuckoo - mogą być przystosowane do współbieżnego użycia. Fan i in. dalej opisują schemat dostępu do tabeli oparty na mieszaniu z kukułką, który jest nie tylko współbieżny, ale także zachowuje wydajność przestrzenną swojej funkcji mieszającej, jednocześnie poprawiając lokalizację pamięci podręcznej, a także przepustowość wstawiania.
Gdy tabele mieszające nie są ograniczone rozmiarem i dlatego mogą rosnąć/zmniejszać się w razie potrzeby, algorytm mieszający musi zostać dostosowany, aby umożliwić tę operację. Pociąga to za sobą modyfikację używanej funkcji skrótu w celu odzwierciedlenia nowej przestrzeni klucza w tabeli o zmienionym rozmiarze. Algorytm rosnącego współbieżnie opisali Maier i in.
Mega-KV to wysokowydajny system przechowywania klucz-wartość, w którym używane jest mieszanie z kukułką , a indeksowanie KV jest masowo równoległe w trybie wsadowym przez GPU. Dzięki dalszym optymalizacjom akceleracji GPU przez NVIDIA i Oak Ridge National Lab , Mega-KV pobił kolejny rekord przepustowości w 2018 roku (do 888 milionów operacji klucz-wartość na sekundę).
Obsługa rywalizacji
Podobnie jak w przypadku każdej współbieżnej struktury danych, współbieżne tablice skrótów cierpią z powodu różnych problemów znanych w dziedzinie obliczeń współbieżnych w wyniku rywalizacji. Przykładami takich problemów są problem ABA , warunki wyścigu i zakleszczenia . Stopień, w jakim te problemy się manifestują lub nawet występują, zależy od implementacji współbieżnej tablicy skrótów; w szczególności, jakie operacje tabela umożliwia jednoczesne uruchamianie, a także strategie łagodzenia problemów związanych z rywalizacją. Podczas obsługi rywalizacji główny cel jest taki sam, jak w przypadku każdej innej współbieżnej struktury danych, a mianowicie zapewnienie poprawności każdej operacji na stole. Jednocześnie powinno to być naturalnie wykonane w taki sposób, aby było bardziej wydajne niż rozwiązanie sekwencyjne stosowane równolegle. Jest to również znane jako kontrola współbieżności .
Instrukcje atomowe
Używając atomowych instrukcji , takich jak porównaj i zamień lub pobierz i dodaj , problemy spowodowane rywalizacją można zmniejszyć, zapewniając, że dostęp zostanie zakończony, zanim inny dostęp będzie miał szansę zakłócić. Operacje takie jak porównywanie i zamiana często wiążą się z ograniczeniami co do rozmiaru danych, które mogą obsłużyć, co oznacza, że typy kluczy i wartości w tabeli muszą być odpowiednio dobrane lub przekonwertowane.
Korzystając z tak zwanej sprzętowej pamięci transakcyjnej (HTM), operacje na tablicach można traktować podobnie jak transakcje w bazie danych , zapewniając atomowość. Przykładem zastosowania HTM w praktyce są Transactional Synchronization Extensions .
Zamykający
Za pomocą blokad operacje próbujące uzyskać równoczesny dostęp do tabeli lub wartości w niej zawartych mogą być obsługiwane w sposób zapewniający prawidłowe zachowanie. Może to jednak prowadzić do negatywnego wpływu na wydajność, w szczególności gdy stosowane blokady są zbyt restrykcyjne, blokując w ten sposób dostęp, który w innym przypadku nie byłby możliwy i mógłby zostać wykonany bez powodowania problemów. Należy podjąć dalsze rozważania, aby uniknąć jeszcze bardziej krytycznych problemów, które zagrażają poprawności, jak w przypadku żywych blokad, impasów lub głodu .
Współbieżność faz
Jednoczesna faza grupuje tablice skrótów, tworząc fazy, w których dozwolony jest tylko jeden typ operacji (tj. czysta faza zapisu), po których następuje synchronizacja stanu tabeli we wszystkich wątkach. Shun i Blelloch podali formalnie sprawdzony algorytm.
Odczyt-Kopiuj-Aktualizacja
Szeroko stosowana w jądrze Linuksa funkcja odczytu-kopiowania-aktualizacji (RCU) jest szczególnie przydatna w przypadkach, gdy liczba odczytów znacznie przekracza liczbę zapisów.
Aplikacje
Naturalnie współbieżne tablice mieszające znajdują zastosowanie wszędzie tam, gdzie przydatne są sekwencyjne tablice mieszające. Zaleta, jaką zapewnia tutaj współbieżność, polega na potencjalnym przyspieszeniu tych przypadków użycia, a także zwiększonej skalowalności. Biorąc pod uwagę sprzęt, taki jak procesory wielordzeniowe , które stają się coraz bardziej zdolne do współbieżnych obliczeń, znaczenie współbieżnych struktur danych w tych aplikacjach stale rośnie.
Analiza wydajności
Maier i in. przeprowadzić dogłębną analizę różnych współbieżnych implementacji tablic mieszających, dając wgląd w skuteczność każdej z nich w różnych sytuacjach, które mogą wystąpić w rzeczywistych przypadkach użycia. Najważniejsze ustalenia można podsumować w następujący sposób:
| Operacja | Twierdzenie | Notatki | |
|---|---|---|---|
| Niski | Wysoki | ||
znajdować |
Bardzo wysokie przyspieszenia zarówno w przypadku udanych, jak i nieudanych unikalnych znalezisk, nawet przy bardzo dużej rywalizacji | ||
wstawić |
Osiągnięto wysokie prędkości, duża rywalizacja staje się problematyczna, gdy klucze mogą przechowywać więcej niż jedną wartość (w przeciwnym razie wstawki są po prostu odrzucane, jeśli klucz już istnieje) | ||
aktualizacja |
Zarówno nadpisywanie, jak i modyfikacje istniejących wartości osiągają duże prędkości, gdy rywalizacja jest utrzymywana na niskim poziomie, w przeciwnym razie działa gorzej niż sekwencyjne | ||
usuwać |
Współbieżność faz osiągnęła najwyższą skalowalność; W pełni współbieżne implementacje, w których usuwanie używa aktualizacji z elementami fikcyjnymi, były tuż za nimi |
||
Zgodnie z oczekiwaniami niska rywalizacja prowadzi do pozytywnego zachowania w każdej operacji, podczas gdy wysoka rywalizacja staje się problematyczna, jeśli chodzi o pisanie. To ostatnie jest jednak ogólnie problemem o dużym sporcie, w którym korzyści wynikające z obliczeń współbieżnych są negowane z powodu naturalnego wymogu kontroli współbieżności ograniczającej rywalizujące dostępy. Wynikowy narzut powoduje gorszą wydajność niż w przypadku idealnej wersji sekwencyjnej. Mimo to współbieżne tablice skrótów nadal okazują się nieocenione nawet w scenariuszach o tak dużej rywalizacji, gdy obserwuje się, że dobrze zaprojektowana implementacja może nadal osiągać bardzo duże prędkości, wykorzystując zalety współbieżności do jednoczesnego odczytu danych.
Jednak rzeczywiste przypadki użycia współbieżnych tablic skrótów często nie są po prostu sekwencjami tej samej operacji, ale raczej mieszanką wielu typów. W związku z tym, gdy używana jest kombinacja wstawiania i znajdowania , przyspieszenie i wynikająca z tego użyteczność współbieżnych tablic skrótów stają się bardziej oczywiste, zwłaszcza podczas obserwowania dużych obciążeń związanych z wyszukiwaniem .
Ostatecznie wynikowa wydajność współbieżnej tablicy skrótów zależy od różnych czynników w zależności od pożądanego zastosowania. Przy wyborze implementacji ważne jest, aby określić niezbędną ogólność, strategie obsługi rywalizacji i przemyślenia, czy rozmiar pożądanej tabeli można określić z góry, czy zamiast tego należy zastosować podejście rosnące.
Implementacje
- Od wersji Java 1.5 współbieżne mapy skrótów są dostarczane w oparciu o interfejs współbieżnych map .
- libcuckoo zapewnia współbieżne tablice skrótów dla C / C++ , umożliwiające współbieżne odczyty i zapisy. Biblioteka jest dostępna na GitHubie.
-
Bloki konstrukcyjne wątków zapewniają współbieżne nieuporządkowane mapy dla C++ , które umożliwiają jednoczesne wstawianie i przechodzenie i są utrzymane w stylu podobnym do interfejsu C++ 11
std::unordered_map. Uwzględnione są współbieżne nieuporządkowane multimapy, które umożliwiają istnienie wielu wartości dla tego samego klucza we współbieżnej nieuporządkowanej mapie. Dodatkowo dostarczane są współbieżne mapy skrótów, które opierają się na współbieżnej nieuporządkowanej mapie i ponadto umożliwiają współbieżne wymazywanie i zawierają wbudowane blokowanie. - Grow zapewnia współbieżnie rosnące tablice skrótów dla C++ na podstawie tak zwanej implementacji folkloru . W oparciu o tę nierosnącą implementację podano wiele różnych rosnących tablic mieszających. Implementacje te pozwalają na równoczesne odczyty, wstawianie, aktualizacje (zwłaszcza aktualizowanie wartości na podstawie bieżącej wartości w kluczu) i usuwanie (na podstawie aktualizacji przy użyciu nagrobków ). Poza tym dostępne są warianty oparte na Intel TSX . Biblioteka jest dostępna na GitHubie.
- Folly zapewnia współbieżne tablice skrótów dla C++ 14 i nowszych wersji , zapewniając czytniki bez czekania i oparte na blokadach, podzielone na fragmenty programy piszące . Jak stwierdzono na stronie GitHub, ta biblioteka zapewnia użyteczną funkcjonalność dla Facebooka .
- Junction zapewnia kilka implementacji współbieżnych tablic skrótów dla C++ na podstawie operacji atomowych, aby zapewnić bezpieczeństwo wątków dla dowolnej funkcji składowej tabeli. Biblioteka jest dostępna na GitHubie.
Zobacz też
Dalsza lektura
- Herlihy, Maurice; Szawit, Nir (2008). „Rozdział 13: Jednoczesne mieszanie i naturalna równoległość”. Sztuka programowania wieloprocesorowego . San Francisco, Kalifornia, USA: Morgan Kaufmann Publishers Inc., s. 299–328. ISBN 978-0-12-370591-4 .