Grafikbehandlingsenheter (GPU) har i stor utsträckning använts för att accelerera algoritmer som uppvisar massiv dataparallalism eller aktivitet parallellism. När sådan parallellism inte är inneboende i en algoritm, tar beräkningsforskare till att helt enkelt replikera algoritmen på varje multiprocessor av en NVIDIA GPU, till exempel, för att skapa sådan parallellism, vilket resulterar i pinsamt parallella ensemble körs som ger betydande aggregerad hastighet-upp. Den grundläggande frågan med sådana ensemble körs är dock att problemets storlek för att uppnå denna upphastighet är begränsad till tillgängliga delade minne och cache för en GPU multiprocessor. Ett exempel på ovanstående är dynamisk programmering (DP), en av de 13 dvärgarna i Berkeley. Alla kända DP implementationer hittills använda grov-grained tillvägagångssätt av pinsamt parallella ensemble körs eftersom en finare-grained parallellisering på GPU skulle kräva omfattande kommunikation mellan flera processorer av en GPU, som lätt kunde lamslå prestanda som kommunikation mellan multiprocessorer är inte naturligt stöds i en GPU. Följaktligen tar vi upp ovanstående genom att föreslå en finkornig parallellisering av en enda instans av DP-algoritmen som är kartlagd till GPU. Vår parallellisering innehåller en uppsättning tekniker som syftar till att avsevärt förbättra GPU-prestanda: matrisomriktning, sammanslagen minnesåtkomst, timing, och GPU (snarare än CPU) synkronisering. Den specifika DP-algoritm som vi parallelliserar kallas Smith-Waterman (SWat), som är en optimal lokal sekvensjusteringsalgoritm. Vi använder denna SWat algoritm som en baslinje för att jämföra vår GPU implementation, dvs., CUDA-SWat, med vår Cell implementation, dvs. Cell-SWat.
År 2009, Xiao m.fl. REF tar upp problemet med hur man kartlägger den dynamiska programmeringen på en grafikprocessor.
On the Robust Mapping of Dynamic Programming onto a Graphics Processing Unit
{'venue': '2009 15th International Conference on Parallel and Distributed Systems', 'journal': '2009 15th International Conference on Parallel and Distributed Systems', 'mag_field_of_study': ['Computer Science']}