Szukam przykładów algorytmów ogólnego zastosowania (czyli niezwiązanych z grafiką), dla których udowodniono, że działają o rząd wielkości szybciej na GPU niż na CPU. Wykorzystam te przykłady do kreatywnego myślenia o innych algorytmach, które mógłbym zaimplementować na GPU.
Odpowiedzi:
Od razu przychodzi mi na myśl kilka rzeczy:
Specjalny klient Bitcoin został napisany do korzystania z GPU do wykonywania skrótów kryptograficznych. Klient GPU zazwyczaj działa ponad 10 razy lepiej niż klient SMP CPU w typowym systemie 4-rdzeniowym. Bitcoin zależy od obliczenia dużej liczby niepowiązanych skrótów kryptograficznych, które można obliczać równolegle.
Projekt Folding @ Home oferuje klienta GPU do symulacji dynamiki molekularnej. Obliczenia te są wykonywane dla poszczególnych wiązań między atomami w różnych środowiskach i warunkach. Matematyka jest stosunkowo prosta, ale musi zostać obliczona miliardy razy dla każdej wiązań, aby zasymulować zaledwie nanosekundy aktywności.
Popularnym przykładem „zabawki” stosowanym przez zwolenników obliczeń na GPU jest problem n-body .
Wspólne dla tych rzeczy jest to, że są krępująco równoległe . Oznacza to, że problem można rozłożyć na niewielką liczbę dyskretnych obliczeń, które są wykonywane wiele razy na dużym zestawie danych. Jest to rodzaj obliczeń, w których GPU jest dobra.
Złożone obliczenia zależne od wyników poprzednich obliczeń nie są dobrze dostosowane do GPU.
Transkodowanie wideo i audio jest doskonałym przykładem. Jest to konwersja z jednego formatu pliku na inny. Przykładem jest MPEG-2 do H.264.
Uwaga Transkodowanie wideo nie jest związane z grafiką 3D. Nie można kodować wideo przy użyciu modułu do cieniowania wierzchołków i pikseli.
Wydobywanie bitcoinów za pomocą GPU stało się bardzo popularne.
... elektroniczny system kasowy peer-to-peer. Tworzenie i przesyłanie bitcoinów opiera się na otwartym protokole kryptograficznym i nie jest zarządzane przez żaden organ centralny. Każdy bitcoin jest podzielony na osiem miejsc po przecinku, tworząc 100 milionów mniejszych jednostek zwanych satoshi. Bitcoiny można przesyłać przez komputer lub smartfon bez pośredniej instytucji finansowej.
Przetwarzanie transakcji bitcoinami jest zabezpieczone przez serwery zwane górnikami Bitcoin. Serwery te komunikują się przez sieć internetową i potwierdzają transakcje, dodając je do księgi, która jest okresowo aktualizowana i archiwizowana. Oprócz archiwizacji transakcji każda nowa aktualizacja księgi tworzy nowe bitcoiny ...
Inna aplikacja dotyczy rynków finansowych do handlu w czasie rzeczywistym przy użyciu modeli takich jak Black-Scholes .
... Kluczowym warunkiem korzystania z opcji jest obliczanie ich wartości godziwej. Znalezienie sposobów skutecznego rozwiązania tego problemu cenowego było aktywną dziedziną badań od ponad trzydziestu lat i nadal jest przedmiotem nowoczesnej inżynierii finansowej. Ponieważ coraz więcej obliczeń zostało zastosowanych do problemów związanych z finansami, znalezienie skutecznych sposobów implementacji tych algorytmów we współczesnych architekturach stało się ważniejsze.
W tym rozdziale opisano, jak efektywnie wycenić opcje za pomocą procesora graficznego. Nasze oceny wykonujemy przy użyciu dwóch różnych modeli wyceny: modelu Blacka-Scholesa i modeli kratowych. Oba te podejścia dobrze odwzorowują GPU i oba są znacznie szybsze na GPU niż na nowoczesnych procesorach. Chociaż oba mają również bezpośrednie odwzorowania na GPU, wdrożenie modeli sieci wymaga dodatkowej pracy z powodu współzależności w obliczeniach ...
Dobra gra Conwaya jest dobrym przykładem akademickim.
... Wszechświat Gry Życia jest nieskończoną dwuwymiarową ortogonalną siatką kwadratowych komórek, z których każda jest w jednym z dwóch możliwych stanów, żywym lub martwym. Każda komórka wchodzi w interakcje z ośmioma sąsiadami, które są komórkami sąsiadującymi poziomo, pionowo lub po przekątnej. Na każdym etapie występują następujące przejścia:
- Każda żywa komórka z mniej niż dwoma żywymi sąsiadami umiera, jakby była spowodowana niedostateczną populacją.
- Każda żywa komórka z dwoma lub trzema żyjącymi sąsiadami żyje w następnym pokoleniu.
- Każda żywa komórka z więcej niż trzema żywymi sąsiadami umiera, jakby była przeludniona.
- Każda martwa komórka z dokładnie trzema żywymi sąsiadami staje się żywą komórką, jakby przez rozmnażanie.
Początkowy wzór stanowi zalążek systemu. Pierwsze pokolenie powstaje przez zastosowanie powyższych zasad jednocześnie do każdej komórki w nasieniu - narodziny i śmierci zachodzą jednocześnie, a dyskretny moment, w którym to się dzieje, jest czasem nazywany tyknięciem (innymi słowy, każde pokolenie jest czystą funkcją poprzedni). Reguły są nadal stosowane wielokrotnie, aby tworzyć kolejne pokolenia ...
Problemy wymagające dużej matematyki, które można wykonać równolegle. Tam, gdzie kiedyś pracowałem, chcieliśmy grać z procesorami graficznymi, aby dodawać / odejmować / mnożać 2 macierze w celu opracowania korelacji genetycznej. Po raz pierwszy usłyszałem o procesorach graficznych o tym, że były one wykorzystywane przez finansową firmę programistyczną do wykonania niektórych czynności związanych z modelowaniem (monte carlo i tak dalej). Przydałoby się to w łamaniu kodu.
Procesory graficzne prawdopodobnie nie pomogą w bardziej regularnych problemach programistycznych, w których wystarczy kilka rdzeni procesora, ponieważ większość zwykłych programów wymaga tylko kilku równoległych procesów. (może się różnić w przypadku pamięci / dysku, który jest znacznie szybszy niż obecnie)
Może jestem bardzo specyficzny dla matematyki / nauk ścisłych / inżynierii, ale przychodzi mi na myśl algorytm FFT.
Widziałem już ten test porównawczy FFT i chociaż ma on kilka lat, myślę, że był dobrze zrobiony takim, jakim jest: http://www.sharcnet.ca/~merz/CUDA_benchFFT