Spekulacje dla symulacji. Innowacja w weryfikacji

Opublikowane ponownie przez Plato

Obserwuje: 0

To ciekawy pomysł, wykorzystujący wspieraną sprzętowo równoległość spekulatywną do przyspieszenia symulacji, z pewnym zwrotem akcji wymagającym niestandardowego sprzętu. Paul Cunningham (starszy wiceprezes/dyrektor generalny, weryfikacja w Cadence), Raúl Camposano (Silicon Catalyst, przedsiębiorca, były dyrektor techniczny Synopsys, a obecnie dyrektor techniczny Silvaco) i ja kontynuujemy naszą serię pomysłów na badania. Jak zawsze, opinie mile widziane.

Spekulacje do symulacji

Innowacja

Wybór w tym miesiącu to Chronos: efektywny paralelizm spekulacyjny dla akceleratorów. Autorzy zaprezentowali artykuł na konferencji 2020 Conference on Architectural Support for Programming Languages and Operating Systems i pochodzą z MIT.

Wykorzystanie równoległości przy użyciu procesorów wielordzeniowych to jedna z opcji dla aplikacji, w których równoległość jest oczywista. Inne algorytmy mogą nie być tak łatwe do partycjonowania, ale mogą skorzystać na wykonaniu spekulatywnym wykorzystującym wewnętrzny równoległość. Zwykle wykonanie spekulatywne zależy od spójności pamięci podręcznej, co jest dużym obciążeniem, szczególnie w przypadku symulacji. Ta metoda omija potrzebę spójności, fizycznie lokalizując wykonywanie zadań w celu obliczenia kafelków według docelowego obiektu do odczytu i zapisu, zapewniając wykrywanie konfliktów lokalnie, bez potrzeby globalnego zarządzania koherencją. Zadania mogą być wykonywane spekulacyjnie równolegle; każdy wykryty konflikt można rozwinąć z zadania poprzez jego zadania podrzędne, a następnie ponownie wykonać bez konieczności zatrzymywania innych wątków.

Tutaj jeszcze jedna uwaga. Ta metoda obsługuje symulację opartą na opóźnieniu, w przeciwieństwie do większości technik przyspieszania sprzętowego.

Pogląd Pawła

Wow, co za wspaniały, wysokooktanowy papier z MIT! Zapytany o obliczenia równoległe, od razu myślę o wątkach, muteksach i spójności pamięci. Tak są oczywiście projektowane nowoczesne procesory wielordzeniowe. Ale to nie jedyny sposób obsługi równoległości w sprzęcie.

W artykule zaproponowano alternatywną architekturę równoległości, zwaną Chronos, opartą na uporządkowanej kolejce zadań. W czasie wykonywania zadania są wykonywane w kolejności sygnatury czasowej, a każde zadanie może tworzyć nowe podzadania, które są dynamicznie dodawane do kolejki. Wykonywanie rozpoczyna się od umieszczenia niektórych zadań początkowych w kolejce i kończy się, gdy w kolejce nie ma już żadnych zadań.

Zadania w kolejce są rozdzielane równolegle do wielu elementów przetwarzających (PE) – co oznacza, że Chronos spekulacyjnie wykonuje przyszłe zadania przed zakończeniem bieżącego zadania. Jeśli bieżące zadanie unieważni jakiekolwiek spekulacyjnie wykonane przyszłe zadania, wówczas działania tych przyszłych zadań są „cofane” i są ponownie umieszczane w kolejce. Właściwa implementacja tej koncepcji w sprzęcie nie jest łatwa, ale dla użytkownika zewnętrznego jest piękna: po prostu kodujesz swój algorytm tak, jakby kolejka zadań była wykonywana szeregowo na jednym PE. Nie trzeba kodować żadnych muteksów ani martwić się o impas.

Autorzy implementują Chronos w SystemVerilog i kompilują go do FPGA. Znaczna część artykułu poświęcona jest wyjaśnieniu, w jaki sposób zaimplementowali kolejkę zadań i wszelkie niezbędne rozwinięcia sprzętu w celu uzyskania maksymalnej wydajności. Chronos jest porównywany z czterema algorytmami dobrze dopasowanymi do architektury opartej na kolejce zadań. Każdy algorytm jest implementowany na dwa sposoby: po pierwsze przy użyciu dedykowanego PE specyficznego dla algorytmu, a po drugie przy użyciu gotowego 32-bitowego wbudowanego procesora RISC-V o otwartym kodzie źródłowym jako PE. Wydajność Chronosa jest następnie porównywana z wielowątkowymi implementacjami oprogramowania algorytmów działającymi na serwerze Intel Xeon o cenie podobnej do FPGA używanej w Chronos. Wyniki są imponujące – Chronos skaluje się od 3 do 15 razy lepiej niż przy użyciu serwera Xeon. Jednak porównanie tabeli 3 z rysunkiem 14 trochę mnie martwi, że większość tych korzyści pochodziła z PE specyficznych dla algorytmu, a nie z samej architektury Chronos.

Biorąc pod uwagę, że jest to blog weryfikacyjny, naturalnie przybliżyłem test porównawczy symulacji na poziomie bramki. Branża EDA dużo zainwestowała, aby spróbować zrównoleglić symulację logiczną i okazało się, że trudno jest dostrzec duże korzyści poza kilkoma konkretnymi przypadkami użycia. Wynika to głównie z tego, że wydajność większości rzeczywistych symulacji jest zdominowana przez instrukcje ładowania/przechowywania, których brakuje w pamięci podręcznej L3 i które wychodzą do DRAM. W tym artykule porównano tylko jeden przypadek testowy i jest to mały 32-bitowy adder typu carry save. Jeśli czytasz tego bloga i chciałbyś przeprowadzić dokładniejsze testy porównawcze, daj mi znać – jeśli Chronos naprawdę dobrze skaluje się w rzeczywistych symulacjach, miałby ogromną wartość komercyjną!

Pogląd Raula

Głównym wkładem tego artykułu jest Model realizacji Zlokalizowanych Przestrzennie Uporządkowanych Zadań (SLOT). który jest wydajny w przypadku akceleratorów sprzętowych wykorzystujących równoległość i spekulację oraz w przypadku aplikacji generujących zadania dynamicznie w czasie wykonywania. Obsługa dynamicznej równoległości jest nieunikniona w przypadku symulacji, a synchronizacja spekulacyjna jest atrakcyjną opcją, ale narzut związany ze spójnością jest zbyt wysoki.

SLOT unika potrzeby spójności, ograniczając każde zadanie do działania (zapisu) na pojedynczym obiekcie i obsługuje uporządkowane zadania, aby umożliwić atomowość wielu obiektów. Aplikacje SLOT to uporządkowane, dynamicznie tworzone zadania charakteryzujące się znacznikiem czasu i identyfikatorem obiektu. Znaczniki czasu określają ograniczenia dotyczące zamówień; identyfikatory obiektów określają zależności danych, tj. zadania są zależne od danych wtedy i tylko wtedy, gdy mają ten sam identyfikator obiektu. (jeśli istnieje zależność odczytu, zadanie można wykonać spekulatywnie). Wykrywanie konfliktów staje się lokalne (bez skomplikowanych struktur śledzenia) poprzez mapowanie identyfikatorów obiektów na rdzenie lub płytki i wysyłanie każdego zadania tam, gdzie jest mapowany jego identyfikator obiektu.

Połączenia Chronos System został zaimplementowany w architekturze AWS FPGA jako system składający się z 16 kafelków, z których każdy zawiera 4 specyficzne dla aplikacji elementy przetwarzające (PE), pracujący z częstotliwością 125MHz. Ten system jest porównywany z zestawem bazowym składającym się z 20-rdzeniowego/40-wątkowego Intel Xeon E2.4-5v2676 3 GHz, wybranego specjalnie ze względu na cenę porównywalną z układem FPGA (ok. 2 USD/godz.). Uruchamiając pojedyncze zadanie na jednym PE, Chronos jest 2.45 razy szybszy niż linia bazowa. Wraz ze wzrostem liczby jednoczesnych zadań implementacja Chronos skaluje się do samowzględnego przyspieszenia 44.9x na 8 kafelkach, co odpowiada 15.3-krotnemu przyspieszeniu w stosunku do implementacji procesora. Porównali także implementację opartą na architekturze RISC-V ogólnego przeznaczenia, a nie na PE specyficznych dla aplikacji; PE były 5 razy szybsze niż RISC-V.

Artykuł zrobił na mnie wrażenie, ponieważ obejmuje wszystko, od koncepcji, przez definicję modelu wykonania SLOT, po implementację sprzętu i szczegółowe porównanie z tradycyjnym procesorem Xeon dla 4 aplikacji. Wysiłek jest znaczny, Chronos to ponad 20,000 5.4 linii SystemVerilog. Rezultatem jest średnie przyspieszenie 4x (z XNUMX aplikacji) w porównaniu z wersjami równoległymi oprogramowania, ze względu na większą równoległość i częstsze wykorzystanie wykonywania spekulatywnego. Praca jest również warta przeczytania w celu zastosowania do zadań niesymulacyjnych; artykuł zawiera trzy przykłady.

Udostępnij ten post przez: