Effiziente parallele Implementierung eines expliziten Euler-Verfahrens für Grafikprozessoren durch Diamant-Tiling

E izien e pa allele Implemen ie ung eines explizi en Eule -Ve ah ens ü G a ikp ozesso en du ch Diaman -Tiling Julien Kulbe Bay eu h Repo s on Pa allel and Dis ibu ed Sys ems No. 3, Ma ch 2012 Uni e si y o Bay eu h Depa men o Ma hema ics, Physics and Compu e Science Applied Compu e Science 2 – Pa allel and Dis ibu ed Sys ems 95440 Bay eu h Ge many Phone: +49 921 55 7701 Fax: +49 921 55 7702 E-Mail: b p[email p o ec ed]y eu h.de Ezien e pa allele Implemen ie ung eines explizi en Eule -Ve ah ens ü G akp ozesso en du ch Diaman -Tiling Mas e a bei Uni e si ä Bay eu h Leh s uhl ü Angwand e In o ma ik 2 Be eue : P o . D . Th. Raube , D . M. Ko ch und D . C. Schol es Julien Kulbe 20. Mä z 2012 Ich e klä e hie mi , • dass ich die o liegende A bei ohne emde Hil e und ohne Ve wendung ande e als de angegebenen Hil smi el e ass habe, • dass ich säm liche e wende en Quellen e wähn und gemäÿ gängigen wis- senscha lichen Zi ie egeln ko ek zi ie habe. Inhal s e zeichnis 1 Ein üh ung 1 1.1 Mo i a ion................................ 1 1.2 Ziele................................... 1 1.3 Au baude A bei ........................... 2 2 OpenCL 3 2.1 Au bau eines OpenCL P og amms . . . . . . . . . . . . . . . . . . 4 2.2 Op imie ung eines OpenCL P og amms . . . . . . . . . . . . . . . 6 2.2.1 LoopUn olling......................... 6 2.2.2 Vek o isie ung ......................... 7 2.2.3 Anzahl de Wo ki ems und Wo kg oups . . . . . . . . . . . 7 2.2.4 Lese- und Sch eibzug ie au den globalen Speiche . . . . . 8 2.2.5 Lokale Speiche . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.6 Ba ie s............................. 9 3 ODE-Sys eme und Lösungs e ah en 11 3.1 Deni ion on ODE-Sys emen . . . . . . . . . . . . . . . . . . . . . 11 3.2 Explizi es Eule -Ve ah en . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Ausgewähl e P oblems ellungen . . . . . . . . . . . . . . . . . . . . 14 4 CPU Implemen ie ung des explizi en Eule -Ve ah ens 17 4.1 Sequen ielle Ve sion . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 P h eads pa allelisie e Ve sion . . . . . . . . . . . . . . . . . . . . 17 5 Linea e OpenCL Ve sionen 21 5.1 Unop imie e linea e OpenCL-Ve sion . . . . . . . . . . . . . . . . 21 5.2 Ve besse ung des Speiche zug ismus e s . . . . . . . . . . . . . . . 25 5.3 Vek o isie ung de P oblem unk ion . . . . . . . . . . . . . . . . . . 29 5.4 P obleme und E kenn nisse bezüglich des linea en OpenCL-Ve ah ens 30 6 Diaman -Tiling 31 6.1 Mo i a ion................................ 31 6.2 Synch onisa ion............................. 31 6.3 Speiche e ah en............................ 32 6.4 Bes immung de Diaman g öÿe . . . . . . . . . . . . . . . . . . . . 33 i Inhal s e zeichnis 7 Zeilenweises Diaman -Tiling 35 7.1 Implemen ie ung des Hos codes . . . . . . . . . . . . . . . . . . . . 36 7.1.1 Ve g öÿe ung de Anzahl de Diaman en . . . . . . . . . . . 37 7.2 Implemen ie ung des Ke nels . . . . . . . . . . . . . . . . . . . . . 42 7.3 Lau zei und Speedup des zeilenweisen Diaman -Tilings . . . . . . 45 7.4 P obleme und E kenn nisse des Diaman -Tilings . . . . . . . . . . 51 8 Spal enweises Diaman -Tiling 53 8.1 Implemen ie ung des Hos codes . . . . . . . . . . . . . . . . . . . . 53 8.2 Implemen ie ung des Ke nels . . . . . . . . . . . . . . . . . . . . . 54 8.3 Lau zei des spal enweisen Diaman -Tilings . . . . . . . . . . . . . 58 8.4 P obleme und E kenn nisse des spal enbasie en Diaman -Tilings . 58 9 Waben-Tiling 61 9.1 Mo i a ion................................ 61 9.2 Au baude Waben........................... 61 9.3 E mi eln de op imalen Wabeng öÿe . . . . . . . . . . . . . . . . . 63 9.4 Lau zei und Speedup des Waben-Tilings . . . . . . . . . . . . . . . 66 9.5 P obleme und E kenn nisse des Waben-Tilings . . . . . . . . . . . 66 10 E aluie ung 69 10.1 E aluie ung zum Einsa z on G akp ozesso en . . . . . . . . . . . 69 10.2 E aluie ung zum Op imie en on Algo i hmen un e G akp ozes- so en................................... 70 11 Zusammen assung 73 ii 1 Ein üh ung 1.1 Mo i a ion Viele na u wissenscha liche P oblems ellungen lassen sich au ma hema ische Be- sch eibungen du ch Die en ialgleichungssys eme zu ück üh en. Das Lösen diese Au gaben is eine de Schwe punk e de nume ischen Ma hema ik. Da diese Sys- eme seh g oÿ sein können und das Lösen seh lange Zei in Ansp uch nimm , is das Pa allelisie en und Op imie en on Algo i hmen zum Lösen on Die en- ialgleichungssys emen ein in e essan es Thema. Die heu igen G akp ozesso en bie en du ch eine Vielzahl an Mul ip ozesso en einen wesen lich höhe en G ad an Pa alleli ä als CPUs. Aus diesem G und s ell ge ade das Pa allelisie en au mode nen G akka ena chi ek u en eine He aus o de ung da . G akp ozesso en bie en un e schiedliche G anula i ä ss u en zum Pa allelisie en. Sie bes ehen meis aus meh e en Mul ip ozesso en und diese wiede um aus meh e en Ke nen. Jede G anula i ä ss u e besi z dabei Eigenscha en und Besonde hei en, die beach e und analysie we den müssen, um ih Po en ial olls ändig auszuschöp en. 1.2 Ziele Das Ziel de A bei is es, einen ezien en Algo i hmus zum Lösen on Die- en ialgleichungen ü G akka en zu en wickeln. Dazu wi d das Eule -Ve ah en e wende , da es on de S uk u seh ein ach is und iele Möglichkei en zum Op imie en bie e . Abe auch ande e Ve ah en lassen sich ü die GPU po ie en. Dabei muss imme abgewäg we den, welche Op imie ungen ü das Ve ah en an- gewende we den können. Zue s soll eine Implemen ie ung en wickel we den, die sich am Algo i hmus des Eule -Ve ah ens ü CPU o ien ie . Da sich in diese Ve sion de Algo i hmus am bes ehenden Code o ien ie , we den hie nu einige wich ige Op imie ungen ü G akp ozesso en angewende . Au wendige Op imie ungen, wie zum Beispiel un e schiedliche Speiche hie a chien we den in diese Ve sion nich be ach e , da da ü g oÿe Ände ungen am bes ehenden Code no wendig sind. Diese e s e Ve sion, linea e OpenCL-Ve sion genann , dien als G undlage ü alle wei e en Ve sionen. Das Ziel diese Implemen ie ung is es, zu zeigen, dass bes ehende CPU Code mi wenigen Ände ungen ezien au G akka en po ie we den kann. Dabei wi d die Lau zei de GPU-Ve sion au e schiedenen Ha dwa e A chi ek u en e mi el und mi de Lau zei de bes ehenden CPU-Ve sion e glichen. Das nächs e Ziel is es, einen Algo i hmus zu en wickeln, de möglichs iele Ei- 1 KAPITEL 2. OPENCL sein, wie die Anzahl de Recheneinhei en. Is die Anzahl de Wo kg oups jedoch g öÿe als die de Recheneinhei en, muss au eine gleichmäÿige Ve eilung de A - bei au die un e schiedlichen Recheneinhei en geach e we den. Es soll e also die Anzahl de Recheneinhei en de G akka e abge ag we den, um dann die Anzahl de Wo kg oups au die Anzahl de Recheneinhei en zu se zen, beziehungsweise au ein ganzzahliges Viel aches da on, sowei dies möglich is . Die Anzahl de Wo ki ems eine Wo kg oup soll e mindes ens so g oÿ sein, wie on eine Recheneinhei pa allel bea bei en we den kann. Au AMD GPUs wi d diese G öÿe als wa e on und bei NVIDIA als wa psize bezeichne . Au heu igen G akka en be äg sie 32 ode 64 Wo ki ems. Jede Recheneinhei besi z eine beg enz e Anzahl an Regis e n, die au die einzelnen Wo ki ems e eil wi d. Je g öÿe die Anzahl de Regis e p o Wo ki em is , des o ge inge is die maximal mögliche Anzahl an Wo ki ems p o Wo kg oup. Die maximale Anzahl de Wo i- ems p o Wo kg oup kann du ch clGe Ke nelWo kG oupIn o abge ag we den. 2.2.4 Lese- und Sch eibzug ie au den globalen Speiche Zum Aus ausch on Da en zwischen Hos und De ice kann de Hos au den glo- balen Speiche des De ices zug ei en. De globale Speiche is alle dings de lang- sams e Speiche des De ices und aus diesem G und soll e e such we den die Lese- und Sch eibzug ie au den globalen Speiche zu minimie en. Beim Zug i au den globalen Speiche soll e da au geach e we den, welches Zug ismus e am bes en om De ice un e s ü z wi d. Die G akka e is op i- mie ü 128-Bi We e (= ie oa -We e). Es is also a sam, jeweils 128 Bi am S ück zu lesen ode zu sch eiben. Des Wei e en soll e anges eb we den, dass alle Wo ki ems gleichzei ig benachba e Blöcke de G öÿe 128-Bi laden. Das ideale Zug ismus e (nach [8, S. 583]) lieg o , wenn jedes Wo ki em bei seinem Wo - ki emindex beginn oa 4 (ode in 4) We e zu lesen. Diese An angswe wi d in den olgenden I e a ionen um die Gesam zahl de Wo ki ems e höh bis alle Da en aus dem Globalen Speiche gelesen wu den. Dies üh dazu, dass alle Wo ki ems gleichzei ig einen g oÿen Block on jeweils 128-bi We en lesen (siehe Abbildung 2.2). uin id = globale Wo ki em Id uin ids = Anzahl globale Wo ki ems o ( idx = id ; idx < il e Wid h ; idx += ids ) { 4 . . . } 2.2.5 Lokale Speiche Um die Anzahl de Lese- und Sch eibzug ie des globalen Speiche s zu op imie- en, is es sinn oll, häug benu z e Da en zue s in den lokalen Speiche zu laden und e s am Ende de Be echnung wiede in den globalen Speiche zu speiche n. Jede Recheneinhei e üg übe einen lokalen Speiche . Diese is ypische weise 8 2.2. OPTIMIERUNG EINES OPENCL PROGRAMMS id=0 id=1 id=2 id=3 1. I e a ion 2. I e a ion id=0 id=1 id=2 id=3 ids 3. I e a ion id=0 id=1 id=2 id=3 Abbildung 2.2: Zug ismus e des globalen Speiche s wesen lich schnelle als de globale Speiche . Es können jedoch nu die Wo ki ems eine Wo kg oup au den lokalen Speiche de Recheneinhei zug ei en, au de sie abgea bei e we den. Das s ell ü Da en, die on meh e en Wo kg oups geb auch we den, ein P oblem da . Um Da en zwischen e schiedenen lokalen Speiche n aus- zu auschen, müssen sie übe den globalen Speiche ausge ausch we den. Dazu is abe eine Synch onisie ung de Wo ki ems no wendig. 2.2.6 Ba ie s Ba ie s dienen zu Synch onisie ung on Wo ki ems. OpenCL bie e Ba ie s abe nu p o Wo kg oup an. Eine globale Ba ie ü alle Wo ki ems is du ch die Ve - eilung de Wo kg oups au e schiedene Recheneinhei en nich p ak ikabel. Eine globale Ba ie läss sich ealisie en, indem ein Ke nel beende wi d und sich so- mi auch alle Wo ki ems beenden. De Hos kann nun einen neuen Ke nel s a en und synch onisie somi alle Wo ki ems. Da dies ela i lange daue , soll e e - such we den, die Anzahl de globalen Ba ie s zu minimie en und Sie du ch lokale Ba ie s zu e se zen. 9 3 ODE-Sys eme und Lösungs e ah en 3.1 Deni ion on ODE-Sys emen Viele na u wissenscha liche P obleme lassen sich au gewöhnliche Die en ialglei- chungen ( ODE , o dina y die en ial equa ion) mi gegebenem An angswe (IV, ini ial alue) zu ück üh en. Solche P obleme we den als IVPs (ini ial alue p o- blems) bezeichne . Ein IVP bes eh zum einen aus Gleichungen, die das zei liche Ve hal en des Sys ems besch eiben (Gleichung 3.1) und zum ande en aus dem An angswe , de das Sys em zum Zei punk 0 besch eib (Gleichung 3.2). Die Lösung des P oblems bes eh in de Bes immung des Zus ands des Sys ems zu einem bes imm en Zei punk e> 0 (aus üh liche e In o ma ionen nden sich in [3] und [13]). Abbildung 3.1 zeig ein exempla isches ODE-P oblem. Die du chgezogene Ku - e zeig den physikalisch exak en Ve lau , de jedoch bis au den An angswe bei y0 unbekann is . Die ges ichel e Ku e zeig den be echne en Ve lau eines Lö- sungs e ah ens ü das gegebene ODE-P oblem mi den be echne en Punk en yi zu den Zei punk en i . y0( ) = ( , y( )) (3.1) y( 0) = y0 (3.2) De Ausgangswe wi d als n-s ellige Vek o modellie . Aus diesem Ausgangs- we we den i e a i mi eine gegebenen Sch i wei e h neue Vek o en mi We en be echne , die den Zus and des Sys em zum Zei punk i ep äsen ie en. Das expli- zi e Eule -Ve ah en is eine Me hode zu Lösung diese Sys eme. Dieses Ve ah en is eine ein aches Ve ah en, um IVPs zu lösen. Es wi d da ü eine es o gegebene Sch i wei e h > 0 gewähl . Mi diese Sch i wei e we den dann die Zus ände des Sys ems zu den Zei punk en i= 0+i·h, i ∈N (3.3) be echne . 11 KAPITEL 3. ODE-SYSTEME UND LÖSUNGSVERFAHREN y 0 1 2 e Physikalisch exak e Ve lau Nume isch be echne e Ve lau Abbildung 3.1: Be echne es und exak es Ve hal en eines IVPs 3.2 Explizi es Eule -Ve ah en Lis ing 3.2 zeig den Pseudocode des explizi en Eule -Ve ah ens. H besch eib dabei die Zei die enz zwischen 0 und e . In jedem Zei sch i we den aus dem n-s elligen Vek o y _ cu ü die neuen We e y _ new ü den Zei punk +h be- echne . Die nächs e I e a ion e wende dann y _ new als Ausgangswe e ü den Zei sch i +h . In de Implemen ie ung wi d dies dadu ch gelös , dass y _ cu und y _ new e ausch we den. Die Funk ion ode_e al_comp besch eib das spezi- sche P oblem, welches gelös we den soll. Sie be echne ü eine gegebene Kompo- nen e j des Vek o s aus den ak uellen We en die S eigung de We e zum Zei punk . Diese Ände ung, wi d mi de Sch i wei e h gewich e , au den ak uellen We addie : yj, +h=yj, +h·ode _ e al _ comp(j, , y ) (3.4) Da aus e gib sich de neue We de Komponen e j. Die Me hode be echne genau den Ein ag mi Index j de ech en Sei e des ODE-Sys ems aus Gleichung 3.1. Diese neu be echne en We e besi zen keine ge- gensei igen Abhängigkei en und können dahe auch pa allel zueinande be echne we den. Die Be echnung de Lösung ü ein spezisches P oblem kann einen hohen Beda an Rechenau wand da s ellen, da zum einen die Anzahl de Komponen en seh g oÿ sein kann und zum ande en die Auswe ung de Me hode ode_e al_comp seh komplex sein kann. Au g und des hohen Rechenau wands und des hohen G a- des an Pa alleli ä bie e es sich an, ODEs au GPUs zu be echnen. Abbildung 3.3 zeig das p inzipielle Vo gehen da ü , wie aus den n Ausgangs- we en i e a i die nächs en n We e bis zum Endzei punk e be echne we den. Die scha ie en We e s ellen dabei Ein äge des Vek o s da , welche schon be- 12 3.2. EXPLIZITES EULER-VERFAHREN y_cu = Ausgangswe e_des_ODE_Sys ems ; o ( i = 0; i < H / h ; i++) { = _0 + i ∗ h; o ( j = 0; j < n; j++) { 5 y_new[ j ] = y_cu [ j ] + h ∗ ode_e al_comp( j , , y_cu ) ; swap(y_new, y_cu ) ; } } p in y_cu Abbildung 3.2: Pseudocode explizi es Eule e ah en echne wu den. Die weiÿen Ein äge kennzeichnen dagegen noch nich be echne e We e. Zu Be echnung jedes Elemen s y _ new[j] , j je 1,...,n ü den Zei punk i+1 we den bis zu 2·k+ 1 Ausgangswe e om Zei punk i benö ig . Im allgemeinen Fall könn en alle We e om Zei sch i i geb auch we den zu Be echnung on y _ new[j] . Bei ielen na u wissenscha lichen P oblemen läss sich abe ein k be- s immen welches wesen lich kleine als die Sys emdimension n is . Die G öÿe k , die das Speiche zug ismus e und die Lokali ä de Funk ion cha ak e isie , is die Zug isdis anz. Die Zug isdis anz gib an, wie g oÿ de Abs and om zu be echnenden We mi Index j zum Index j+k des benö ig en We es maximal is . i i+1 e k n 0 1 y_cu y_new k Abbildung 3.3: p inzipielles Vo gehen zu Be echnung 13 KAPITEL 3. ODE-SYSTEME UND LÖSUNGSVERFAHREN 3.3 Ausgewähl e P oblems ellungen Als Beispiele ü simulie ende Sys eme wu den de B üssela o (B uss2d-P oblem) und ein Modell ü das Schwingen eine Sai e (S ing-P oblem) e wende . De B üssela o is ein Modell zu Besch eibung chemische Oszilla o en. In Abbildung 3.4 is das B üssela o -P oblem da ges ell . Das Sys em bes eh aus zwei e schiedenen S oen mi den Konzen a ionen A und B in einem zweidi- mensionalen Gi e . Das zweidimensionale Gi e bes eh aus m∗m Gi e punk en. De n-s ellige Vek o des esul ie enden Sys ems ep äsen ie die Konzen a ionen de beiden S oe in den m2 Gi e punk en. Jedes Käs chen on S o A und B s eh dabei ü eine Konzen a ion, die in dem n-s elligen Vek o abgespeiche wi d. Um die We e des zweidimensionalen Gi e s des B üssela o s im Speiche abzubilden, we den die We e zeilenweise jeweils abwechselnd ü die Konzen a ion ü S o A und B im Speiche abgeleg . Zu Be echnung de neuen Konzen a ion on S o A mi Punk P = 22, we den die We e de Konzen a ion on A on allen an- g enzenden Gi e punk en on P und on P selbs , sowie die Konzen a ion on S o B im Punk P benö ig . Beim B üssela o mi einem m∗m Gi e dessen We e zeilenweise abgeleg sind, en sp ich die Zug isdis anz eine olls ändigen Zeile des Gi e s. Sie be äg 2m, da jeweils die We e on S o A und B p o Zeile abgeleg sind. Die Zug isdis anz wächs demnach mi de Sys emg öÿe. 4,4 5,3 5,4 5,5 6,4 m 20 56 56 51 57 63 52 64 58 S o B 20 21 5,3 28 23 24 m S o A 24 63 645,4 5,44,4 6,45251 5,3 16 5,5 2 * m 2 * m 4,2 21 2316 2858 57 59 22 Zug i sdis anz 59 22 Abbildung 3.4: Abbildung des B üssela o s im Speiche Das S ing-P oblem ([3, S. 27]) besch eib das Sys em eine schwingenden Sai e, die an beiden Enden es eingespann is . Die Sai e wi d du ch äquidis an e Abs än- de in Massepunk e un e eil . De n-s ellige Vek o ep äsen ie die Auslenkun- gen sowie die Geschwindigkei en in den e schiedenen Massepunk en. Um die neue 14 3.3. AUSGEWÄHLTE PROBLEMSTELLUNGEN Auslenkung on Punk P zu be echnen, wi d die Geschwindigkei on P selbs , de o he gehenden Punk P-1 und de nach olgenden Punk P+1 geb auch . Die Zu- g isdis anz be äg dabei 3. Die Zug isdis anz is also hie unabhängig on de G öÿe des Sys ems (siehe Abbildung 5.7). 00 1 2 3 4 5 678 9 10 5 5'4'43'3 3 Abbildung 3.5: S ing P oblem 15 4 CPU Implemen ie ung des explizi en Eule -Ve ah ens 4.1 Sequen ielle Ve sion Als Ausgangspunk de Op imie ung s eh eine Implemen ie ung des explizi en Eule -Ve ah ens on D . M. Ko ch [7] zu Ve ügung. Lis ing 4.1 zeig den zen- alen Teil de Be echnung. Die Pa ame e de Funk ion sind: die S a zei zu de die Be echnung beginnen soll ( 0 ), die An angswe e ( y0 ) zum S a zei punk , die Zei spanne ( H = e− 0 ) übe die be echne we den soll, ein Zeige au das Feld, in dem de Lösungs ek o ( y ) einge agen we den soll und die Sch i wei e ( h ). Die Sys emg öÿe n wi d du ch das zu lösende ODE-P oblem o gegeben ( ode_size ). Die Felde y0 und y besi zen jeweils n Ein äge ü die n An angswe e beziehungs- weise Endwe e des Sys ems. Im Algo i hmus wi d zue s ein Feld Y allokie , in dem die Zwischenwe e de Be echnung gespeiche we den. Dieses Feld is 2∗n g oÿ, da es genügend Speiche pla z ü die ak uellen We e, sowie ü die neu be- echne en We e des Sys ems bie en muss. Die Anzahl de Be echnungssch i e ( s eps ) wi d du ch s eps = Zei spanne übe die be echne wi d (H) Sch i wei e (h) (4.1) e echne . Danach we den die Ausgangswe e on y0 in das Feld Y kopie , um die Be echnung zu ini ialisie en. In den einzelnen Be echnungssch i en wi d je- weils das ak uelle ( Y_cu ) und das neue Feld ( Y_new ) al e nie end bes imm . Anschlieÿend we den ü jeden einzelnen We des ODE-Sys ems die neuen We e aus den ak uellen We en gemäÿ de Fo mel 3.4 be echne . 4.2 P h eads pa allelisie e Ve sion Es we den in de P h eads Ve sion zwei Da ens uk u en e wende , die übe A - gumen e e ügba sind. Einmal eine Da ens uk u die sich alle Th eads eilen und eine ü jeden Th ead p i a . In de gemeinsamen Da ens uk u s ehen die Anzahl de Th eads, die S a zei , die Felde mi den An angs-, End- und Zwischenwe en und eine globale P h eads-Ba ie . Jede Th ead besi z da übe hinaus noch eine p i a e Da ens uk u ü die Th eadnumme und den S a - bzw. Endindex de Komponen en, die e in jedem Zei sch i be echnen soll. In de Be echnungs unk- ion we den zue s die Da en ü die gemeinsamen und p i a en Da ens uk u en 17 KAPITEL 5. LINEARE OPENCL VERSIONEN einen e gleichba en We zu e hal en (P h eads-Ve sion mi 4 Th eads, OpenCL- Ve sion mi 512 lokalen Wo ki ems und 30 Wo kg oups). Au de x-Achse is die Sys emg öÿe au ge agen und au de y-Achse die en sp echende Lau zei in Se- kunden. Es wu den e schiedene Lau zei en gemessen. Die Gesam lau zei is die komple e Lau zei des Lösungs e ah ens mi Be echnung und Ini ialisie ung. Die Ke nellau zei is dagegen die Lau zei , die ü die Be echnung geb auch wu de. Es is zu sehen, dass bei de P h eads-Ve sion die Gesam - und Ke nellau zei na- hezu iden isch sind, da die Ini ialisie ung bei P h eads, die E s ellung de Th eads, nich lange daue . Bei de OpenCL-Ve sion is dagegen die Ini ialisie ungszei we- sen lich höhe . Bei OpenCL muss zue s die G akka e ge unden und ini ialisie we den, de Ke nel muss geladen und kompilie we den und die Da en müssen zwi- schen Hos und De ice ans e ie we den. Diese O e head zu Ini ialisie ung is ü e schiedene Sys emg öÿen nahezu kons an und deshalb nu bei seh kleinen Sys emen ü die Gesam lau zei signikan . Die P h eads-Ve sion is ü kleine Sys eme schnelle als die OpenCL-Ve sion, da die Ini ialisie ungszei bei OpenCL haup sächlich ü die Lau zei e an wo lich is . Fü g oÿe Sys eme, bei de die Ini ialisie ungszei keinen wesen lichen Bei ag zu Lau zei meh beis eue , is die OpenCL-Ve sion doppel so schnell wie die P h eads-Ve sion. Es wi d deu lich, dass schon diese ein ache unop imie e Ke nel au eine GPU zu eine Ve besse ung de Lau zei gegenübe eine CPU-Ve sion üh . 0.01 0.1 1 10 100 10000 100000 1e+06 1e+07 Lau zei en in Sekunden Sys emg oesse n lin. OpenCL Gesam lau zei lin. OpenCL Ke nelzei P h eads Gesam lau zei P h eads Ke nelzei Abbildung 5.1: Lau zei de linea en OpenCL-Ve sion und de P h eads-Ve sion 24 5.2. VERBESSERUNG DES SPEICHERZUGRIFFSMUSTERS 5.2 Ve besse ung des Speiche zug ismus e s Zu Ve besse ung des OpenCL-Ke nels wu de zue s das Zug ismus e au den globalen Speiche e ände (siehe dazu Punk 2.2.4). Bishe wu de ü jedes Wo k- i em beziehungsweise ü jeden Th ead ein An angs- und Endindex be echne . Dieses Ve hal en is jedoch ü heu ige CPU-A chi ek u en op imie , die nich einzelne We e laden, sonde n ganze Cachezeilen. Die meis en GPUs besi zen abe keine Caches und laden ypische weise 128-bi Blöcke. In Lis ing 5.3 is de Ke - nel mi e besse em Zug ismus e da ges ell . Jedes Wo ki em be echne dabei imme ie oa -We e / 128-bi Blöcke. De An angsindex jedes Wo ki ems is dabei seine globale Wo ki em Id * 4. Somi we den in de e s en I e a ion de Schlei e die e s en 4∗Wo ki emanzahl We e on y be echne . Fü die nächs e I e a ion wi d de An angsindex um genau diese Anzahl on 4∗Wo ki emanzahl wei e gezähl . Dies üh dann zu dem in Kapi el 2.2.4 besch iebenen op imalen Speiche zug ismus e on GPUs. In jede I e a ion we den dann ie ak uelle We e gelesen und ie neue We e gesch ieben. Dies üh implizi zu einem Loop Un olling ( gl. Kapi el 2.2.1). o ( in i = 4 ∗ id ; i <= ode size − 4; i+= 4 ∗ ids ) { 2 y_new[ i ] = y_cu [ i ] + h ∗ ode_e al_comp( i , , y_cu ) y_new[ i +1] = y_cu [ i +1] + h ∗ ode_e al_comp( i +1, , y_cu ) y_new[ i +2] = y_cu [ i +2] + h ∗ ode_e al_comp( i +2, , y_cu ) y_new[ i +3] = y_cu [ i +3] + h ∗ ode_e al_comp( i +3, , y_cu ) } Lis ing 5.3: op imie es Speiche zug ismus e des linea en OpenCL-Ve ah ens In G ak 5.2 is die Ke nellau zei de unop imie en und de op imie en linea- en OpenCL-Ve sion da ges ell . Es wi d deu lich, dass bei kleinen Sys emg öÿen du ch die Op imie ung keine Ve besse ung de Lau zei en zu messen is . Alle dings üh das Speiche zug ismus e schon bei mi le en Sys emg öÿen zu eine e heb- lichen Ve besse ung de Lau zei . Bei de g öÿ en gemessenen Sys emg öÿe üh die Op imie ung zu einem Speedup on 3,6 im Ve gleich zu nich op imie en Ve sion. In G ak 5.3 sind ü das S ing-P oblem die Gesam lau zei en de beiden li- nea en OpenCL-Ve sionen de P h eads-Ve sion gegenübe ges ell . Es is wiede zu sehen, dass die OpenCL-Ve sionen bei kleinen Sys emg öÿen du ch die Ini iali- sie ung schlech e e Lau zei en haben als die CPU-Ve sion. Bei g öÿe en Sys emen sind jedoch die GPU-Ve sionen wesen lich schnelle , die op imie e Ve sion e eich dabei eine Beschleunigung bis zum 7,4- achen de CPU-Ve sion. Um die Lau zei en mi einande e gleichen zu können, is es no wendig, die op imale Anzahl an lokalen und globalen Wo ki ems ü jeden Ke nel zu bes im- 25 KAPITEL 5. LINEARE OPENCL VERSIONEN men. Die lokalen Wo ki ems, also die Wo ki ems p o Wo kg oup, we den du ch die NVIDIA GTX 280 au maximal 512 beg enz . In G ak 5.4 is de Speedup de Ke nellau zei en gegenübe den lokalen Wo ki ems au ge agen. Es wu de da- bei bei jede Ku e eine es e Anzahl an Wo kg oups einges ell und die lokalen Wo ki ems on eins bis 512 a iie . Fes e Anzahl p o Wo kg oup bedeu e , dass die Anzahl de globalen Wo ki ems sich aus: globale _ Wo ki ems =lokale _ Wo ki ems ∗Wo kg oups (5.1) be echne . De Speedup jede Ku e wu de dabei jeweils au die Lau zei mi einem glo- balen Wo ki em bezogen. Bei eine Wo kg oup is zu Beginn ein linea e Ans ieg des Speedups zu beobach en, de spä e dann imme wei e abach . Das Maxi- mum on 250 wi d bei 512 Wo ki ems, also de maximalen Anzahl, e eich . Die op imale Anzahl an Wo ki ems p o Wo kg oup is hie die maximale Anzahl an Wo ki ems p o Wo kg oup ü die en sp echende GPU. Es s ell sich also die F age wa um dies so is , wenn nu 8 Ke ne p o Recheneinhei exis ie en. Eine Besonde - hei dieses Ke nels sind die ielen Speiche zug ie au den globalen Speiche . Je meh Wo ki ems zu Ve ügung s ehen, des o besse kann die GPU die La enzen de Speiche zug ie e s ecken. Ande s sieh es bei 30 Wo kg oups aus, also eine ollen Auslas ung de GPU. Hie gib es nu bis ca. 64 Wo ki ems p o Wo kg oup einen s a ken Ans ieg des Speedups bis au das 1100- ache (en sp ich e wa einem Speedup om 35- achen p o Wo kg oup). Danach bleib de Speedup kons an . Dies lieg da an, dass bei 30 Wo kg oups iel meh globale Wo ki ems ak i sind und au den Speiche zug ei en. Bei e wa 30 Wo kg oups mi jeweils 64 Wo ki ems, also 1920 globalen Wo ki ems, is die Bandb ei e des globalen Speiche s ausgelas e und es komm zu keinem wei e en Speedup meh . In G ak 5.5 wu den die Wo ki ems p o Wo kg oup kons an gehal en und die Anzahl de Wo kg oups a iie . Bei allen Ku en is an angs wiede ein linea e Ans ieg des Speedups zu sehen, de dann abach und sich eine Obe g enze nähe . Wenn die Ku e abach , is wiede die maximale Bandb ei e e eich . Je g öÿe die Anzahl de lokalen Wo ki ems is , des o wenige Wo kg oups we den benö ig , um diesen maximalen Speedup zu e eichen. Fü diesen Ke nel soll e die Anzahl an lokalen und globalen Wo ki ems möglichs hoch gewähl we den um den maximalen Speedup zu e hal en (zum Beispiel lokale Wo ki ems: 512, Wo kg oups: 30 au de GTX 280). 26 5.2. VERBESSERUNG DES SPEICHERZUGRIFFSMUSTERS 0.01 0.1 1 10 100 10000 100000 1e+06 1e+07 Lau zei Sys emg oesse n S ing - lin. OpenCL S ing - op . Speiche zug B uss2d - lin. OpenCL B uss2d - op . Speiche zug i Abbildung 5.2: Lau zei en de linea en OpenCL Implemen ie ungen 0.1 1 10 100 10000 100000 1e+06 1e+07 Lau zei Sys emg oesse n lin. OpenCL lin. OpenCL (op . Speiche zug i ) P h eads Abbildung 5.3: Lau zei en de Implemen ie ungen 27 KAPITEL 5. LINEARE OPENCL VERSIONEN 0 200 400 600 800 1000 1200 0 100 200 300 400 500 600 Speedup lokale Wo ki ems Wo kg oup=1 Wo kg oup=30 Abbildung 5.4: Speedup de Wo kg oups 100 200 300 400 500 600 700 800 900 1000 1100 0 10 20 30 40 50 60 Speedup Wo kg oup 128 lokale Wo ki ems 256 lokale Wo ki ems 512 lokale Wo ki ems Abbildung 5.5: Speedup de lokalen Wo ki ems 28 5.3. VEKTORISIERUNG DER PROBLEMFUNKTION 5.3 Vek o isie ung de P oblem unk ion Da sich die ie Be echnungszeilen in Ke nel 5.3 seh ähnlich sehen, lieg es nahe, diese zu ek o isie en ( gl. Kapi el 2.2.2). Die Schlei e sieh dann so aus: o ( in i = id ; i < ODE_SIZE / 4; i += ids ) { y_new[ i ] = y_cu [ i ] + h ∗ ode_e al_comp4( i , , y_cu ) ; } Die no male P oblem unk ion be echne ü einen gegebenen Index genau einen Rückgabewe . Wi d die Schlei e ek o isie , muss auch die P oblem unk ion an- gepass we den, sodass ü einen gegebenen Index ie Rückgabewe e be echne we den. In Lis ing 5.6 und 5.7 sind die o iginale und die ek o ise e P oblem unk- ion ü das S ing-P oblem abgebilde . Da an is e sich lich, dass das Umsch eiben nich i ial is , da alle Feldzug ie au die ek o isie en We e angepass we den müssen. Bei komplexe en Funk ionen soll e dahe abgewäg we den, ob sich de Au wand ü das Umsch eiben de Funk ion im Ve gleich zum Geschwindigkei s- gewinn lohn . loa ode_e al_comp (..) 2 { i ( i % 2 == 0) e u n y [ i +1]; e u n STRING_mod_K ∗ STRING_mod_K ∗ 7 (y [ i − 3] − 2 ∗ y [ i − 1] + y [ i +1]) ; } Abbildung 5.6: o iginal S ing-P oblem loa 4 ode_e al_comp4 ( . . ) 2 { loa 4 es ; es . x = y [ i ] . y ; es . z = y [ i ] .w; 7 es . y = STRING_mod_K ∗ STRING_mod_K ∗ (y [ i − 1].z − 2 ∗ y [ i ] . x + y [ i ] . z) ; es .w = STRING_mod_K ∗ STRING_mod_K ∗ (y [ i ] . x − 2 ∗ y [ i ] . z + y [ i +1].x) ; 12 e u n es ; } Abbildung 5.7: ek o isie es S ing-P oblem In G ak 5.8 wi d die Ke nellau zei de ek o isie en Ve sion des S ing-P o- blems mi de bishe igen Ve sion e glichen. Es is zu sehen, dass das Vek o isie- 29 KAPITEL 5. LINEARE OPENCL VERSIONEN en de P oblem unk ion einen Speedup um das 2,5- ache zu nich ek o isie en Funk ion geb ach ha . Bei de Be echnung g öÿe e Sys eme is es sinn oll, die P oblem unk ion umzusch eiben. 0.01 0.1 1 10 100 10000 100000 1e+06 1e+07 Ke nellau zei Sys emg oesse n lin. OpenCL lin. OpenCL (op . Speiche zug i ) lin. OpenCL ( ek. P oblem .) P h eads Abbildung 5.8: Lau zei de ek o isie en P oblem unk ion 5.4 P obleme und E kenn nisse bezüglich des linea en OpenCL-Ve ah ens Du ch das Loop-Un olling, das Ve ände n de Zug iss uk u au den globalen Speiche und das Anpassen de P oblem unk ion konn en Lau zei e besse ungen e ziel we den. Um abe wei e e Op imie ungssch i e anzugehen, beda es eine genaue en Analyse des Algo i hmus, ü wei e e Lau zei e besse ungen. Ein P o- blem is , dass in jedem Ke nelau u nu ein Zei sch i be echne wi d. Dies üh dazu, dass das Synch onisie en des Hos s iel Zei benö ig . Wie in Kapi el 2.2.6 besch ieben, soll e e such we den ein G oÿ eil diese globalen Ba ie s du ch lo- kale zu e se zen. Wei e hin lau en bishe alle Speiche ope a ionen übe den globalen Speiche , welche de langsams e Speiche is . Es soll e also e such we den, einen G oÿ eil de Be echnungsda en om globalen Speiche in den lokalen Speiche zu e legen, um eu e I/O-Speiche zug ie zu spa en. 30 6 Diaman -Tiling 6.1 Mo i a ion Viele An angswe p obleme de ODE-Sys eme besi zen eine besch änk e Zug is- dis anz. Das heiÿ , die Zug isdis anz is wesen lich kleine als die P oblemg öÿe n . Fü die olgenden Algo i hmen wi d da on ausgegangen, dass das P oblem ei- ne besch änk e Zug isdis anz au weis , ande en alls muss eine de o he igen Algo i hmen benu z we den. Das P inzip des Diaman -Tilings wu de in [12] benu z , um Fini e-Die enzen- Me hoden (FDTD, ni e-die ence ime-domain) au Meh ke np ozesso en zu be- echnen. Du ch den Einsa z on Diaman -Tiling wu de die Speiche wiede e wen- dung e öh und es konn en dadu ch Lau zei e besse ungen e ziel we den. Es wu - den dabei auch un e schiedliche Tile o men un e such . Dabei s ell e sich he aus, dass die Diaman -Tiles die bes e Pe o mance ü Da anabhängigkei en bei FDTD bie en. In de o liegenden A bei wi d da au au gebau und das Diaman -Tiling in e - schiedenen Implemen ie ungen e glichen. In Kapi el 9 wi d auch eine al e na i e Tile o m un e such . 6.2 Synch onisa ion Basie end au de Zug isdis anz acc _ dis kann de n-s ellige Vek o in Blöcke gleiche G öÿe mi jeweils block _ size ( ≥ Zug isdis anz acc _ dis ) We en un e - eil we den. Dies ha den Vo eil, dass die We e in Block j zum Zei sch i i nu ih en eigenen Block j , den o he gehenden Block j−1 und den nach olgenden Block j+ 1 benö igen (siehe Abbildung 6.1). Dami kann das P oblem behoben we den, dass p o Ke nelau u nu ein Zei sch i be echne wi d. Die Idee is , jede Recheneinhei eine bes imm e Anzahl (= dia_blocks ) an Blöcken zuzu eilen. Aus diesen dia _ blocks Blöcken zum Zei punk i können dia _ blocks −2 neue Blöcke ü den Zei sch i i+1 be echne we den. Es we den p o be echne em Zei sch i zwei Blöcke wenige , da die äuÿe s en Blöcke nich mi be echne we den können, weil sie Abhängigkei en zu Blöcken ande e Wo kg oups haben. De Vo eil dabei is , dass nach einem Zei sch i die Wo ki ems de Wo kg oup übe eine lokale Ba ie synch onisie we den können. E s wenn die Anzahl de Blöcke nu noch 2 be äg und keine wei e en Blöcke meh be echne we den können, muss de Ke - nel beende we den und es wi d global synch onisie . Aus diesem Mus e e gib sich die un e e Häl e eines Diaman en ( gl. Abbildung 6.1). 31 KAPITEL 6. DIAMANT-TILING Die Diaman en we den au die Wo kg oups / Recheneinhei en e eil . Dabei wi d ein ähnliches Mus e benu z wie in Kapi el 2.2.4. Jede Wo kg oup beginn mi dem Diaman en ih e Wo kg oup Id (Anm: eindeu ige Index jede Wo k- g oup), ü jeden wei e en Diaman en wi d de I e a ionszähle um die Anzahl de Wo kg oups wei e gezähl , bis alle Diaman en de I e a ion be echne wu - den (in Abbildung 6.2 wu den die Diaman en au zwei Wo kg oups e eil ). Die Be echnungen eine Wo kg oup sind unabhängig on denen ande e Wo kg oups und we den pa allel zu diesen ausge üh . Das Be echnen on meh e en Diaman en eine Wo kg oup e olg sequen iell. E s wenn alle Wo kg oups ih e Diaman en be echne haben, kann die nächs e I e a ion ges a e we den. Nachdem alle un e- en Häl en be echne wu den, wi d deshalb eine globale Ba ie benö ig , um die Konsis enz de be echne en Da en siche zus ellen. dia_blocks block_size Abbildung 6.1: Au bau eines Diaman en 6.3 Speiche e ah en Da die Be echnung jedes Diaman en nu au eine Recheneinhei e olg , können die Da en ü den Diaman im lokalen Speiche de en sp echenden Wo kg oup abgeleg we den. Aus den Abbildungen 6.1 und 6.2 is e sich lich, dass die nächs en Diaman en die zwei äuÿe s en Blöcke (sch ae e Blöcke) jedes Zei sch i es de un e en Häl e ü ih e Be echnung de obe en Häl e des Diaman en benö igen. In jedem Zei sch i de un e en Häl e müssen also die zwei äuÿe s en Blöcke wiede in den globalen Speiche gesch ieben we den. In Abbildung 6.3 is zu sehen, dass es du ch das Ve auschen on y_new und y_cu in jedem Zei sch i möglich is , alle Blöcke des Diaman en zu speiche n, ohne noch benö ig e We e zu übe sch eiben. In de Abbildung we den alle ge aden 32 6.4. BESTIMMUNG DER DIAMANTGRÖßE Zei sch i e (g ob sch ae ) in dem o de en Teil des 2n We e g oÿen Vek o s y gesch ieben und die unge aden Zei sch i e ( ein sch ae ) im hin e en Teil des Vek o s. Bei de Be echnung de obe en Häl e des Diaman en müssen die zwei äuÿe s- en Blöcke, die on den o he gehenden Diaman en be echne wu den, geladen we den. Die Da en we den dabei om globalen Speiche in den lokalen Speiche kopie . Die Be echnungen de Zei sch i e inne halb des Diaman en e olg nu noch au Da en im lokalen Speiche . Die Be echnungszei inne halb des Diaman- en e kü z sich, da die Zug iszei en au den lokalen Speiche ge inge sind als au den globalen Speiche und nu noch au Da en im lokalen Speiche zugeg ien wi d. Es en s eh abe auch ein Meh au wand, da die Da en e s zwischen den e schiedenen Speiche n kopie we den müssen. 1212 2 12 12 1 2 1 2 1 2 1 2 1 2 1 1 1 2 1 2 1 2 1 2 Abbildung 6.2: Volls ändiges Diaman -Schema, Au eilung de Diaman en au (2 Wo kg oups) 6.4 Bes immung de Diaman g öÿe Eine ideale Au eilung wä e es, die n We e in so iele Diaman en wie es Rechenein- hei en gib zu un e eilen, dami jede Wo kg oup einen Diaman be echne . Dami e gib sich ü die Anzahl de Blöcke p o Diaman : dia _ blocks =n block _ dis ∗Recheneinhei en (6.1) Um Fallun e scheidungen und degene ie e Diaman en zu e hinde n, wi d die Anzahl de dia _ blocks Blöcke imme au die nächs g öÿe e ge ade Zahl e höh , da ü die Diaman en, wie sie in Abbildung 6.1 da ges ell sind, imme eine ge ade Anzahl an Blöcken benö ig wi d. Ein ande es wich iges En scheidungsk i e ium ü die Blockanzahl p o Diaman is die G öÿe des lokalen Speiche s. Is diese 33 KAPITEL 7. ZEILENWEISES DIAMANT-TILING mul dia_blocks local_size 1 690 22.144 2 340 10.944 Als Resul a e häl man olgendes: in ge aden I e a ionen be echnen 30 Wo kg oups zwei Diaman en mi jeweils 340 Blöcken in unge aden I e a ionen be echnen 29 Wo kg oups zwei Diaman- en, zwei Wo kg oups be echnen nu einen Diaman en Lau zei en de d ei S a egien In Abbildung 7.4 is die Ke nellau zei mi den un e schiedlichen S a egien da - ges ell ü e schiedene Sys emg öÿen n. Bei eine Sys emg öÿe on übe 60.000 eich de o handene lokale Speiche pla z nich meh ü alle Diaman en und eini- ge Wo kg oups müssen meh e e Diaman en be echnen. Den g öÿ en Lau zei sp ung mach dabei die zwei e S a egie, da hie nu eine Wo kg oup zwei Diaman en be- echnen muss und alle ande en Wo kg oups wa en müssen, bis de e s e seine A bei beende ha . Bei de e s en und d i en S a egie müssen alle Wo kg oups zwei Diaman en be echnen, die abe nu die halbe G öÿe haben. Bei eine wei- e en E höhung de Sys emg öÿe bis e wa 120.000 komm es zu keine wei e en Ve g öÿe ung de Lau zei de zwei en S a egie, da schon die e s e Wo kg oup zwei Diaman en olle G öÿe be echne und dami die höchs e Lau zei au weis . Bei den ande en beiden Va ian en komm es zu einem gleichmäÿigen Ans ieg de Lau zei . Es is zu sehen, dass die Sp ünge bei de E höhung de Diaman anzahl signikan ü die Lau zei sind. Die Ve g öÿe ung de Blockanzahl p o Diaman äg jedoch wenige zu Lau zei bei. Meis ens wi d du ch die d i e S a egie die minimale Lau zei ü e schiedene Sys emg öÿen e ziel . Mi den e mi el en We en ü die cha ak e is ischen G öÿen des Ke nels kann de Ke nel ini ialisie we den. Dem Ke nel wi d zusä zlich zu den o he igen A - gumen e noch die Blockg öÿe block _ size , die Zug isdis anz und die Anzahl de Blöcke dia _ blocks übe geben. Danach olg die Schlei e übe die In eg a ionssch i e, die die einzelnen Ke ne- lau u e s a e . Da jede Diaman so iele Zeilen hoch hoch wie e Blöcke b ei is , be echne jede Diaman auch dia _ blocks Zei sch i e. Die nächs e I e a ion s a e dann genau (dia _ blocks/2) ∗h spä e als de o he ige. (siehe Lis ing 7.5). 40 7.1. IMPLEMENTIERUNG DES HOSTCODES 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 50000 60000 70000 80000 90000 100000 110000 120000 130000 Ke nellau zei Sys emg oesse n 1. S a egie 2. S a egie 3. S a egie Abbildung 7.4: un e schiedliche Diaman e eilungss a egien . . . in s eps = H / h; loa = _0 ; in max_i e = (2 ∗ s eps ) / dia_blocks ; 5 se ze Ke nela gumen ( block_size ) se ze Ke nela gumen ( dia_blocks ) o ( i e = 0; i e <= max_i e ; ++i e ) { 10 se ze Ke nela gumen ( i e ) se ze Ke nela gumen ( ) s a e Ke nel ( global , lokal ) wa e au Beendigung des Ke nels 15 = i e ∗ dia_ iles / 2 ∗ h_ ; } Abbildung 7.5: Ke nel s a en im Hos code 41 KAPITEL 7. ZEILENWEISES DIAMANT-TILING 7.2 Implemen ie ung des Ke nels De Ablau des Ke nels is in Lis ing 7.6 schema isch da ges ell . De Vek o y en häl die Ausgangsda en, die om Hos zum De ice kopie wu den. De Vek- o y _ l is ein Speiche be eich im lokalen Speiche de Recheneinhei in dem die Wo kg oups die Be echnungen du ch üh en. Jede Wo kg oup wi d au eine Re- cheneinhei ausge üh und besi z deshalb einen lokalen Speiche be eich, de un- abhängig on den ande en Wo kg oups is . Das lokale Feld jede Wo kg oup is dabei an angs nich o ini ialisie . de __ke nel sol e ( . . . , __global loa 4 ∗ y , 3 __local loa 4 ∗ y_l) {diaman en = Anzahl de Diaman en p o Zeile s eps = dia_ iles / 2 − 1; o (g oup = 0; g oup < diaman en ; g oup+=wo kg oups) { 8 // obe e Diaman hä l e o ( s ep = s eps ; s ep >= 0; s ep −− ){ lade We e aus y nach y_l be echne neue We e in y_l } 13 // un e e Diaman hä l e o ( s ep = 1; s ep <= s eps ; s ep++) { be echne neue We e in y_l speiche e We e on y_l nach y } 18 ba ie } } Abbildung 7.6: Pseudocode des zeilenweisen Diaman -Ve ah ens Die Anzahl de p o Zei sch i zu be echnenden Diaman en wu de zu o im Hos bes imm . Jede Wo kg oup besi z eine Schlei e übe die Anzahl de Diaman en, die sie zu be echnen ha . Da ü einen Diaman en de gesam e lokale Speiche benu z wi d, müssen die Diaman en au eine Recheneinehi nacheinande be- echne we den. Die Diaman en au e schiedenen Recheneinhei en we den abe pa allel bea bei e . Die Va iable s eps gib die Höhe bzw. die Anzahl de Zei sch i e p o Diaman - häl e an. s ep = 0 en sp ich dem Zei sch i in de Mi e des Diaman en, bei dem die maximale Anzahl an Blöcken zu be echnen is . Jede ande e S u e s ep des Diaman en besi z 2∗(s eps −s ep) Blöcke. Zunächs wi d die obe e Häl e des Diaman en be echne (siehe Abbildung 7.7 on s ep 5 bis 0). In diese Phase we den in jedem Zei sch i 4 Blöcke (sch a - e e gelbe Blöcke) om globalen Speiche in den lokalen Speiche kopie . Die 42 7.2. IMPLEMENTIERUNG DES KERNELS Be echnung de neuen Blöcke (sch ae e blaue Blöcke ) e olg danach nu noch im lokalen Speiche . De lokale Speiche is wiede in zwei Teilbe eiche ü y _ new und y _ cu un e - eil , die nach jedem Zei sch i e ausch we den. In Abbildung 7.7 is zu sehen, dass in s ep = 5 in das linke Feld (= y _ cu ) die We e om globalen Speiche geladen we den und au de ech en Sei e des Feldes ( y _ new ) we den die neu be- echne en We e abgeleg . Im nächs en Zei sch i ( s ep = 4 ) wi d dann das ech e Feld zu y _ cu und die nächs en We e om globalen Speiche we den neben die zu o be echne en We en geladen. Die neu be echne en We e we den dann im linken Feld abgespeiche und übe sch eiben die zu o geladenen We e, da diese nich meh geb auch we den. globale Speiche lokale Speiche Diaman schema s ep 0 1 2 3 4 5 2 1 3 dia_blocks =12 s ep = 5 s ep = 4 s ep = 3 s ep = 0 s ep = 1 s ep = 2 s ep = 5 4 5 Abbildung 7.7: Speiche e ah en des zeilenweisen Diaman -Tilings 43 KAPITEL 7. ZEILENWEISES DIAMANT-TILING Das Laden, Speiche n und Be echnen on We en e olg wiede nach dem Sche- ma aus Kapi el 2.2.4. Es wi d o jedem Laden, Speiche n und Be echnen de S a - und Endindex de We e be echne und on allen Wo ki ems pa allel bea bei e . id = lokale Wo ki em Id n = Anzahl de lokalen Wo ki ems o se = S a ad esse des Diaman en im globalen Speiche block_end = Endad esse des Diaman en im globalen Speiche 5 local_o se = O se des Diaman en im lokalen Speiche . . . in begin = o se + s ep ∗ block_size; in end = block_end − s ep ∗ block_size; 10 o ( i = begin + id ; i < end ; i += n) { local_i = i − o se + local_o se ; y_new[ local_i ] . x = y_cu [ local_i ] . x + h ∗ ode_e al_comp (4 ∗ i , , &y_cu [ local_o se − o se ]) ; . . . 15 } Abbildung 7.8: Be echnungen beim Diaman -Ve ah en im lokalen Speiche Nachdem die obe e Häl e be echne wu de, kann die un e e Häl e be echne we den (in Abbildung 7.7 un en on s ep 1 bis 5). In diese Phase de Be echnung eines Diaman en sind schon alle benö ig en Da en im lokalen Speiche o handen und es können so o die nächs en Zei sch i e be echne we den ohne Da en neu aus dem globalen Speiche anzu o de n. Nach dem Be echnen jede Zeile müssen die äuÿe s en ie Blöcke wiede in den globalen Speiche gesch ieben we den, da sie zu Be echnung de nächs en Diaman en benö ig we den. Nach de Aba bei- ung des Diaman en bes eh de komple e globale Vek o aus neu be echne en We en und diese können ü den nächs en Diaman en wiede als Ausgangswe e benu z we den. (Anm: In Abbildung 7.7 bes eh de globale Be eich nich nu aus neu be echne- en We en nach s ep = 5 . Dies lieg da an, dass es nu ein Ausschni des globalen Speiche s is und die noch gelben Blöcke on ande en Diaman en be echne we - den.) 44 7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS 7.3 Lau zei und Speedup des zeilenweisen Diaman -Tilings Tes sys em P h eads/GTX280 GTX580 CPU: P ozesso 2x AMD Op e on 270 In el E5530 Anzahl Ke ne 2 4 Tak ung 2.0 GHz 2.4 GHz GPU: G akka e NVIDIA GTX 280 NVIDIA GTX 580 Recheneinhei en 30 16 Anzahl Ke ne 240 512 Ke ne p o Recheneinhei 8 32 globale Speiche 1023 MB 1536 MB lokale Speiche 16 kB 48 kB L2 Cache / 768 kB Be iebssys em Linux Ke nel 2.6.37 Compile gcc 4.6.2 Im Folgenden we den die gemessenen Speedups de OpenCL-Ve sion mi Dia- man -Tiling be ach e . Es wu de ü alle Messungen das S ing-P oblem mi eine Sys emg öÿe on 80.000 e wende . In Abbildung 7.9 wi d de Speedup in Abhän- gigkei on de Anzahl de Wo kg oups mi 128 und 256 lokalen Wo ki ems p o Wo kg oup da ges ell . Hie bei soll e beach e we den, dass wegen dem wesen lich komplexe en Ke nelcode nun meh Regis e als in de linea en OpenCL-Ve sion benö ig we den. Da jede Wo kg oup nu eine bes imm e Anzahl an Regis e n ü alle Wo ki ems besi z , is die maximale Anzahl lokale Wo ki ems nu noch 256. Fü eine höhe e Anzahl an Wo ki ems kann ein iden isches Ve hal en beobach e we den. Es gib einen linea en Speedup bis zu 30 Wo kg oups, da bei 30 Wo k- g oups alle 30 Recheneinhei en komple ausgelas e sind. Bei übe 30 Wo kg oups gib es einen s a ken Ab all des Speedups, da es je z eine ungleichmäÿige Ve ei- lung de Diaman en/Wo kg oups au die Recheneinhei en gib . Bei 60 Wo kg oups gib es wiede eine Las balancie ung und es e gib sich de gleiche Speedup wie bei 30 Wo kg oups. Die Anzahl de Wo kg oups soll e in de Diaman -Ve sion also möglichs ein Viel aches de Recheneinhei en sein. In G ak 7.10 is de Speedup in Abhängigkei on de Anzahl lokale Wo ki ems da ges ell . Es is wiede an angs ein linea e Ans ieg des Speedups es zus ellen, de sich ab 125 lokalen Wo ki ems eine Kons an en nähe . De maximale Speedup on 750 lieg bei e wa 160 lokalen Wo ki ems, es we den also wiede wesen lich 45 KAPITEL 7. ZEILENWEISES DIAMANT-TILING meh lokale Wo ki ems als Ke ne p o Recheneinhei benö ig , um den maximalen Speedup zu e eichen. Dies läss da au schlieÿen, dass wiede Speiche bandb ei en den Speedup beg enzen. Die Anzahl de Wo ki ems soll e also im Ideal all au übe 100 lokale Wo ki ems gese z we den. In Abbildung 7.11 sind die Lau zei en de Diaman -Ve sionen im Ve gleich zu den o he igen Algo i hmen au ge agen. Es we den zusä zlich zu dem be ei s o - ges ell en Diaman -Ve ah en noch zwei wei e e be ach e . Ein Ve ah en benu z lediglich globalen Speiche und keinen lokalen Speiche und bei einem ande en wu de zusä zlich die P oblem unk ion ek o isie . Ve gleichba sind dahe das Diaman -Ve ah en mi dem linea en OpenCL-Ve ah en und die beiden Ve ah- en mi de ek o isie en P oblem unk ion. Die Diaman -Ve sion e eich dabei einen Speedup on 1,75- ache, de linea en OpenCL Ve sion. Das heiÿ , dass die Ve wendung des lokalen Speiche s und de Einsa z lokale Ba ie s die Lau ei des Ke nels as halbie . Bei den Ve sionen mi de ek o isie en P oblem unk ion is de Speedup du ch das Diaman -Ve ah en jedoch wesen lich ge inge . Bei kleinen Sys emg öÿen wi d noch ein Speedup on 1,5 e eich , bei g öÿe en Sys emen nu on 1,05. Die U sache da ü is in Abbildung 7.12 zu e kennen. In Abbildung 7.12 is die no mie e Ke nellau zei gegenübe de Sys emg öÿe au ge agen. Die no mie e Ke nellau zei be echne sich aus: no mie e Ke nellau zei = Ke nellau zei Sys emg öÿe n (7.5) Sie s ell die du chschni liche Be echnungszei ü ein einzelnes Elemen da . Bei beiden Diaman -Ve sionen is zu sehen, dass mi wachsende Sys emg öÿe die no - mie e Lau zei ge inge wi d (bis zu eine Sys emg öÿe on 60.000). Dies lieg da an, dass bei g öÿe en Sys emen auch die einzelnen Diaman en g öÿe we den und dami de lokale Speiche besse ausgenu z we den kann und es wenige globa- le Ba ie s gib . Ab eine Sys emg öÿe on 60.000 müssen abe meh e e Diaman en on eine Wo kg oup be echne we den (siehe Abbildung 7.4). Deshalb s eig die Lau zei sp ungha wiede an. Bei 60.000, also eine ollen Ausnu zung des lokalen Speiche s, wi d ein Minimum de no mie en Lau zei e ziel , da bei eine ollen Ausnu zung des lokalen Speiche s de höchs e Speedup des Diaman -Ve ah ens e eich wi d. Jede wei e e Ve g öÿe ung des Sys ems b ing keinen wei e en Spee- dup meh ü jedes einzelne Elemen . Dieses Speedupmaximum wi d imme wiede bei Viel achen on 60.000 e eich . De Speedup des Diaman -Ve ah ens is also p imä abhängig on de G öÿe des lokalen Speiche s. Die linea e OpenCL-Ve sion dagegen ha einen s e igen Speedup p o Einzelele- men . Bei kleinen Sys emen is die no mie e Lau zei wesen lich schlech e als die de Diaman -Ve sionen, bei g öÿe en Sys emen wi d abe annähe nd die Lau zei de Diaman -Ve sion e eich . De Speedup de linea en OpenCL-Ve sion is s a k abhängig on de Anzahl de globalen Ba ie s. Da bei allen Sys emg öÿen die Anzahl de globalen Ba ie s kons an is , äll die Aus üh ungszei ü die glo- balen Ba ie s ü kleine Sys eme wesen lich s ä ke ins Gewich als bei g öÿe en Sys emen, bei denen die Be echnung de Elemen e signikan ü die Lau zei is . 46 7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS 0 100 200 300 400 500 600 700 800 0 10 20 30 40 50 60 Speedup Wo kg oups 128 lokale Wo ki ems 256 lokale Wo ki ems Abbildung 7.9: Speedup de lokalen Wo ki ems 1 10 100 1000 5 25 50 125 300 Speedup lokale Wo ki ems 1 Wo kg oup 30 wo kg oups Abbildung 7.10: Speedup de Wo kg oups 47 KAPITEL 7. ZEILENWEISES DIAMANT-TILING 0.01 0.1 1 10 100 10000 100000 1e+06 1e+07 Ke nellau zei Sys emg oesse n linea e OpenCL Ve sion lin. OpenCL Ve sion ( ek. P oblem .) Diaman Tiling ( ek. P oblem .) Diaman Tiling (ohne lokalen Speiche ) Diaman Tiling Abbildung 7.11: Lau zei de Ve sionen 5e-07 1e-06 1.5e-06 2e-06 2.5e-06 3e-06 3.5e-06 4e-06 4.5e-06 5e-06 5.5e-06 6e-06 10000 100000 1e+06 1e+07 no mie e Ke nellau zei Sys emg oesse n lin. OpenCL ( ek. P oblem .) Diaman Tiling Diaman Tiling ( ek. P oblem .) Abbildung 7.12: no mie e Lau zei de Ve sionen 48 7.3. LAUFZEIT UND SPEEDUP DES ZEILENWEISEN DIAMANT-TILINGS Wenn de Speedup de Diaman -Ve sion p imä on de G öÿe des lokalen Spei- che s abhäng , dann müss e sich die Lau zei die enz de Diaman -Ve sion zu linea en OpenCL-Ve sion bei GPUs mi einem g öÿe en lokalen Speiche e g ö- ÿe n. Um dies zu un e suchen, wu den die Lau zei messungen auch au eine NVI- DIA GTX 580 du chge üh , die 48kB lokalen Speiche besi z , im Gegensa z zu GTX 280 mi nu 16kB. Dabei muss jedoch beach e we den, dass die GTX 580 einen L2 Cache besi z . Jede Speiche an age au den globalen Speiche läd da- he nich nu einen 32bi We , sonde n 128By e, also eine komple e Cachezeile. In Abbildung 7.13 is die no mie e Lau zei bei e schiedenen P oblemg öÿen zu sehen. Die Lau zei en de Diaman -Ve sionen und de linea en Ve sionen sind na- hezu iden isch. Dies lieg da an, dass die linea e Ve sion linea au den globalen Speiche zug ei und dahe s a k om Cache p o ie . Die Diaman -Ve sion läd imme nu einzelne Blöcke om globalen Speiche und kann dahe wei wenige om Cache p o ie en als die linea e Ve sion. Da die Diaman -Ve sion ü GPUs ohne Cache op imie wu de, wu de in Abbildung 7.14 de Cache du ch dekla ie en de Vek o en als ola ile umgangen. ola ile bewi k , dass die GPU gezwungen wi d, jeden We zu laden und dami nich om Cache p o ie en kann. Die Lau - zei en de Diaman -Ve sionen bleiben dabei nahezu kons an , da sie nich om Cache p o ie en. Die Lau zei en de linea en Ve sionen s eigen jedoch. Auÿe dem is zu beobach en, dass die linea en Ve sionen om Vek o isie en de P oblem- unk ion s a k p o ie en und beim Diaman -Ve ah en das Vek o isie en zu as keinem Speedup üh . Dies läss da au schlieÿen, dass beim Diaman -Ve ah en die Speiche bandb ei e e schöp is und, dass dahe die Vek o isie ung de P o- blem unk ion nu noch zu eine ge ingen Beschleunigung üh . In Abbildung 7.15 wu den die Lau zei en ü das B üssela o -P oblem au de GTX 580 gemessen. Das B üssela o -P oblem ha eine wesen lich g öÿe e Zug is- dis anz als das S ing-P oblem, welche auch mi de G öÿe des Sys ems wächs . Dies ha zu Folge, dass die Blöcke de Diaman en wesen lich g öÿe sind. Fü das Diaman -Tiling wi d eine gewisse Mindes anzahl an Blöcken o ausgese z , dami es eek i a bei en kann. Du ch die ge inge lokale Speiche g öÿe wu de dahe au de GTX 280 au Messungen mi dem B üssela o -P oblem e zich e . Die Abbil- dung 7.15 zeig die no mie en Lau zei en ü e schiedene Sys emg öÿen au de GTX 580. Ohne Cache is die Diaman -Ve sion wesen lich schnelle als die linea e Ve sion, mi Cache is die linea e Ve sion besse als die Diaman -Ve sion, da sie seh s a k om L2 Cache p o ie . 49 KAPITEL 8. SPALTENWEISES DIAMANT-TILING de __ke nel sol e ( . . . , __global loa 4 ∗ y , __local loa 4 ∗ y_l) { 5 g oups = Anzahl de Diaman en // = mul s eps = dia_ iles ; o (g oup = 0; g oup < g oups ; g oup+=wo kg oups ) { o ( diag = 0; diag < s eps ; diag++){ o ( heigh = 0; heigh < s eps /2; heigh ++) { 10 i ( diag == 0 | | heigh == 0) lade We e aus y in y_l be echne We e in y_l i ( diag >= s eps − 2 | | heigh == s eps − 1) speiche e We e aus y_l in y 15 ba ie } } } } Abbildung 8.3: Pseudocode des spal enweisen Diaman -Ve ah ens Be ach e wi d das S ing-P oblem mi eine Zug isdis anz on 4 (Anm: Zug isdis anz on 3 wi d au das nächs g öÿe e Vel ache on 4 au ge un- de , du ch die Vek o isie ung mi oa 4-We en) die Be echnung wi d on jeweils 512 lokalen Wo ki ems du chge üh da aus e gib sich eine Blockg öÿe on: block_size = 512 Wo ki ems * 4 We e = 2048 We en Die Anzahl de We e die beim spal enweisen Diaman -Tiling geladen/gespeiche we den müssen p o Zeile: unop imie : alle ie Blöcke we den olls ändig kopie → 4 Blöcke * 2048 We e = 8192 We e op imie : zwei olls ändige Blöcke und zwei Blöcke bis zu Zug isdis anz → 2 Blöcke * 2048 We e + 2 Blöcke * 4 We e = 4104 We e Im Ve gleich dazu die Anzahl de We e die beim zeilenweisen Diaman -Tiling geladen/gespeiche we den p o Zeile: → 4 Blöcke * 4 We e = 16 We e → Du ch die Op imie ung konn e de Beda an zu speiche nden We en as hal- bie we den. De Beda beim zeilenweisen Diaman -Tiling is jedoch insbesonde e ü kleine Zug isdis anzen wesen lich ge inge . 56 8.2. IMPLEMENTIERUNG DES KERNELS lokale Speiche Diaman schema dia_blocks =6 3 B C D E 1 2 GF H JI LK654 13 121110987 A 1817 161514 B CA B C 1 B C1 E F E F3 B C1E F3JI B C1E F3JI7 B C1E F3JI7 D2 B C1E F3JI7 D24 B C1E F3JI7 D24I8 B K1E F3JI17 L24I18 JI15 I16 JI11 I12 diag = 0 diag = 1 diag = 5 Abbildung 8.4: Spal enweises Diaman -Tiling 57 KAPITEL 8. SPALTENWEISES DIAMANT-TILING 8.3 Lau zei des spal enweisen Diaman -Tilings Die Lau zei messungen ü das spal enweise Ve ah en wu den alle au de GTX 580 du chge üh . Da das Ve ah en ü g oÿe Blöcke ausgeleg is , is zu e wa - en, dass ge ade das B üssela o -P oblem on de Op imie ung p o ie . Fü das B üssela o -P oblem können abe nu au de GTX 580 g öÿe e Messungen du ch- ge üh we den, da bei de GTX 280 de kleine e lokale Speiche nu ü ge inge Sys emg öÿen Messungen zuläss . In Abbildung 8.5 is die no mie e Lau zei des S ing-P oblems ü die GTX 580 da ges ell . Es is zu sehen, dass ü kleine Sys emg öÿen keine Messungen ü das spal enbasie e Ve ah en exis ie en, da du ch die Ve g öÿe ung de Blöcke nich genügend Blöcke exis ie en und somi das Diaman -Ve ah en nich eek i a bei en kann. Ab eine Sys emg öÿe on 100.000 wi d de gesam e lokale Spei- che benu z und de maximale Speedup des Ve ah ens kann e eich we den. Die Lau zei is jedoch g öÿe als beim zeilenweisen Ve ah en. Dies kann mi de Ve - g öÿe ung de Blöcke beg ünde we den. Zum einen e inge dies die Zei sch i e p o Diaman und üh dami zu meh globalen Ba ie s. Zum ande en e höhen dies die Anzahl de We e, die zwischen den Speiche n kopie we den müssen. In Abbildung 8.6 is die no mie e Lau zei ü das B üssela o -P oblem ü die GTX 580 da ges ell . Du ch die g öÿe e Zug isdis anz des B üssela o -P oblems müssen die Blöcke ab eine bes imm en P oblemg öÿe nich wei e e g öÿe we - den (ab n= 125.000 ). Es is zu sehen, dass das spal enbasie e Ve ah en auch hie kaum eine Lau zei e besse ung e zielen kann. Das lieg o allem da an, dass de Speedup du ch die eek i e e Speiche ausnu zung und du ch die höhe e Anzahl on lokalen Ba ie s kompensie wi d. 8.4 P obleme und E kenn nisse des spal enbasie en Diaman -Tilings Es ha sich he ausges ell , dass o z de eek i e en Speiche ausnu zung des spal enbasie en Diaman -Tilings keine Lau zei e besse ungen zum zeilenweisen Diaman -Tiling e ziel we den konn en. Dies lieg da an, dass zum einen die g öÿe- en Blöcke zu meh Speiche - und Ladeope a ionen üh en und zum ande en meh lokale Ba ie s benö ig we den und dami die Wo ki ems häuge un e b ochen we den. Das spal enbasie e Ve ah en bie e dahe keine Lau zei e besse ungen zum zeilenweisen Diaman -Ve ah en. Das spal enweise Ve ah en bie e abe da- hingehend einen Vo eil, dass sich dadu ch P obleme mi g oÿen Zug isdis anzen lösen lassen, ü die ansons en de Speiche beim zeilenweisen Ve ah en nich aus- eichen wü de. 58 8.4. PROBLEME UND ERKENNTNISSE DES SPALTENBASIERTEN DIAMANT-TILINGS 0 5e-07 1e-06 1.5e-06 2e-06 2.5e-06 3e-06 3.5e-06 10000 100000 1e+06 1e+07 no mie e Ke nellau zei Sys emg oesse n ode=STRING_MOD lin. OpenCL zeilenweises Diaman . spal enweises Diaman . Abbildung 8.5: no mie e Ke nellau zei S ing 4e-07 6e-07 8e-07 1e-06 1.2e-06 1.4e-06 1.6e-06 1.8e-06 2e-06 0 50000 100000 150000 200000 250000 300000 350000 400000 450000 500000 no mie e Ke nellau zei Sys emg oesse n ode=BRUSS2D-MIX lin. OpenCL zeilenweises Diaman . spal enweises Diaman . Abbildung 8.6: no mie e Ke nellau zei B uss2d 59 9 Waben-Tiling 9.1 Mo i a ion Das Waben-Tiling is eine Va ia ion des zeilenweisen Diaman -Tilings. Du ch die beiden bishe o ges ell en Ve sionen des Diaman -Tilings wu de deu lich, wie wich ig es is , die Anzahl de Ba ie s zu minimie en und die A bei zwischen den Ba ie s zu maximie en. Beim spal enweisen Ve ah en gab es iele lokale Ba ie s und wenig A bei ü jedes Wo ki em, was sich nega i au die Lau zei ausgewi k ha . Beim zeilenweisen Ve ah en wa die Anzahl de Ba ie s ge ing, die A bei p o Zeile jedoch s a k un e schiedlich. An de b ei es en S elle bei s ep = 0 (sie- he Abbildung 7.7) is die A bei maximal, an den obe en und un e en Rände n des Diaman en sind jedoch nu wenige Elemen e p o Zeile zu be echnen. Ge ade bei kleinen Zug isdis anzen, bei denen die Blöcke nu aus wenigen Elemen en bes ehen, we den an den Rände n nich alle Wo ki ems beschä ig . Das Waben- Tiling e such genau dies zu e besse n. Beim Diaman -Tiling be echne e jede Diaman mi dia _ blocks Blöcken genau dia _ blocks−1 Zei sch i e. Beim Waben- Tiling wi d eine es e Anzahl an Sch i en p o Diaman o gegeben (= s eps ) und dami we den die Enden jedes Diaman en abgeschni en. Das E gebnis is , dass auch an den obe en und un e en Rände n noch genügend A bei ü alle Wo ki ems o handen is . Ein ande e Fak o de dazu bei äg , dass die linea e OpenCL Ve sion seh gu e Lau zei en e ziel , is , dass de linea e Zug i au g oÿe zusammenhängende Be eiche des globalen Speiche s, wie e in Kapi el 2.2.4 besch ieben wu de, ü die G akka en op imal is . Dieses Speiche zug ismus e kann abe nu in de linea- en Ve sion e eich we den. In den Diaman e sionen we den p o Zeile nu zwei ehe kleine zusammenhängende Be eiche zwischen globalen und lokalen Speiche übe agen. Beim Waben-Tiling kann de Speiche an den Randzeilen wiede linea übe agen we den und das op imale Zug ismus e kann e eich we den. 9.2 Au bau de Waben Abbildung 9.1 zeig das p inzipielle Schema beim Waben-Tiling. Das Aba bei en und Be echnen de Diaman en du ch die Wo kg oups e olg wie bei de zeilenwei- sen Diaman -Ve sion. Jede Wo kg oup be echne ih en Diaman en zeilenweise. Eine Besonde hei des Waben-Tilings is , dass die Waben ineinande e sch änk sind. Da die e schiedenen I e a ionen sich nun übe lage n, kann Fo mel 6.1 nich meh zu Au eilung de Waben au die Wo kg oups benu z we den. Die G öÿe 61 KAPITEL 9. WABEN-TILING Abbildung 9.1: Waben-Tiling eines Blockes wi d wie beim zeilenweisen Diaman -Ve ah en au das nächs e Viel- ache on ie de Zug isdis anz gese z , dami die Blöcke so klein wie möglich we den, um unnö ige Speiche ope a ionen zu e meiden. Die Gesam zahl alle Blöcke ( dia _ blocks _ sum ) be echne sich aus de P oblem- g öÿe ge eil du ch die G öÿe eines Blockes: dia _ blocks _ sum =n/block _ size (9.1) 2 1 0 3 3 Wabe Wabe Zwischenwabe 0 1 2 2 s eps = 3 dia_blocks dia_blocks - 2 * s eps dia_blocks Abbildung 9.2: Wabe und Zwischenwaben mi s eps = 3 Beim zeilenweisen Diaman -Tiling wu den alle Blöcke au die Wo kg oups e - eil . Beim Waben Tiling müssen die Blöcke jedoch au die Waben (gelbe Waben) und die Zwischenwaben (blaue Waben) au ge eil we den. Zu Bes immung diese Au eilung be ach e man einen Zei sch i , de s ep = 0 eine Wabe en sp ich . In Abbildung e comb2 en sp ich dies s ep = 3 eine Zwischenwabe. Die Au eilung 62 9.3. ERMITTELN DER OPTIMALEN WABENGRÖßE wi d so o genommen, dass es in solch einem Zei sch i bei wo kg oups Waben imme wo kg oups−1 Zwischenwaben gib . Die maximale Anzahl an Blöcken p o Zei sch i de Waben wi d wiede als dia _ blocks bezeichne . In einem Zei sch i , in dem eine Wabe bei s ep 0 die maximale Anzahl an Blöcken p o Zei sch i be- echne , haben die en sp echenden Zwischenwaben ge ade die kleins e Anzahl an Blöcken (siehe Abbildung e comb2). Die kleins e Anzahl de Blöcke is abhängig on dem Zei sch i nach dem eine Wabe abgeschni en wi d. In de Abbildung wi d jede Wabe und Zwischenwabe nach dem Zei sch i 3 (= s eps) nach oben und un en abgeschni en. Die Anzahl de Blöcke bei de maximalen Anzahl on Zei sch i en is dia _ blocks −2∗s eps . Die Gesam zahl alle Blöcke muss au die wo kg oups Waben und die wo kg oups −1 Zwischenwaben e eil we den: dia _ blocks _ sum = Blöcke de Waben + Blöcke de Zwischenwaben dia _ blocks _ sum =wo kg oups ∗dia _ blocks + (wo kg oups −1) ∗(dia _ blocks −2∗s eps) Du ch Um o mung läss sich da aus die Anzahl de Blöcke p o Diaman ü eine bes imm e Sch i wei e ( s eps ) be echnen: dia _ blocks _ sum = 2 ∗wo kg oups ∗dia _ blocks+ (wo kg oups −1) ∗(−2∗s eps)−dia _ blocks dia _ blocks _ sum + 2 ∗s eps∗(wo kg oups −1) = (2 ∗wo kg oups −1) ∗dia _ blocks dia _ blocks =dia _ blocks _ sum + 2 ∗s eps ∗(wo kg oups −1) 2∗wo kg oups −1 9.3 E mi eln de op imalen Wabeng öÿe Wi d die G öÿe de Waben minimie ( s eps = 0 ), so wi d ein ähnliches Ve hal en wie beim linea en OpenCL-Ve ah en e ziel . Es wi d dabei das op imale Zug is- mus e ü alle We e om globalen Speiche e ziel , da alle We e au einmal geladen we den. Jedoch we den die Da en im lokalen Speiche nich wiede e wen- de . We den die Waben e g öÿe , e häl man einen posi i en Eek , indem die We e im lokalen Speiche nun wiede e wende we den. Alle dings gib es auch einen nega i en Eek , da de Zug i au die globalen Da en nich meh imme dem op imalen Mus e olg . We e am Rand müssen in jedem Sch i wiede nach- geladen we den, was zu einem nich op imalen Zug is e hal en au den globalen Speiche üh . Wi d die Wabeng öÿe maximie , e gib sich da aus das Ve hal en des zeilenweisen Diaman -Tilings. Du ch Va ia ion de G öÿe s eps is es möglich 63 KAPITEL 9. WABEN-TILING einen op imalen We zu e eichen, de ü die jeweilige Ha dwa e den Komp o- miss zwischen eine Wiede e wendung des lokalen Speiche s und den op imie en Speiche zug ien au den globalen Speiche nde . Nach olgend sind die Lau zei en des S ing-P oblems mi eine Sys emg öÿe on 2.000.000 da ges ell . In Abbildung 9.3 is die Lau zei ü die GTX 280 mi ca. 500 Blöcken p o Diaman in Abhängigkei on de maximalen Sch i wei e s eps au ge- agen. E wa ungsgemäÿ wi d bei kleinen Sch i wei en mi wachsende Sch i - wei e die Lau zei ge inge , da eine Wiede e wendung du ch den lokalen Speiche e ziel wi d. Ab eine Sch i wei e on ca. 50 s eig die Lau zei wiede an, da de unop imie e Zug i au den globalen Speiche signikan wi d. Bei de minimalen Lau zei is das Ve häl nis de Wiede e wendung des lokalen Speiche s zum op imie en Speiche zug i au den globalen Speiche op imal. Die Wiede e wendung wi d du ch die max. Sch i wei e cha ak e isie und die Men- ge de Da en, die zwischen den Speiche n ans e ie we den muss, wi d du ch die Anzahl de Blöcke cha ak e isie . Beim Minimum de Lau zei be äg das Ve häl nis de Blöcke p o Diaman zu Sch i wei e: ∼500/40 =∼12.5 . In G ak 9.4 is die Abhängigkei on de maximalen Sch i wei e au de GTX 580 da ges ell . Du ch ih en g öÿe en lokalen Speiche bes eh hie jede Diaman aus ca. 1500 Blöcken. Es is zu sehen, dass das Minimum bei e wa 100 Sch i - en e eich is . Dies is höhe als bei de GTX 280, jedoch im Ve häl nis zu Blockg öÿe ( 1500/100 =∼15 ) s ell sich ein We ähnliche G öÿeno dnung ein. Das bei manchen Sch i wei en au e ende plö zliche Ans eigen de Lau zei en is dadu ch zu e klä en, dass du ch Va ia ion de maximalen Sch i wei e auch die Anzahl an Blöcken und dami die Anzahl an Diaman en e ände wi d und dies zu Lau zei sp üngen üh en kann. Als Beispiel des be ach e man den Lau zei sp ung in Abbildung 9.4: bei eine maximalen Sch i wei e on 100 au 120 komm es zu einem Lau zei - sp ung: Die GTX 580 besi z 16 Recheneinhei en In de olgenden Tabelle sind ü die max. Sch i wei en die Anzahl de Blöcke p o Diaman angegeben, die Gesam anzahl alle Diaman en und das Ve häl nis wenn alle Diaman en au 16 Recheneinhei en au ge eil we den: Sch i wei e Blöcke Diaman en #Diaman en / #16 Rechene. 100 1526 176 11 110 1528 177 11.06 120 1530 178 11.1 Du ch die Ände ung de maximalen Sch i wei e ände sich auch die Anzahl de Blöcke p o Diaman und die Anzahl de Diaman en. Bei 100 is die Anzahl ge ade ein Viel aches de Recheneinhei en, es we den also genau 11 Diaman en on jede Wo kg oup be echne . Ab Sch i wei e 110 muss eine Recheneinhei 12 Diaman en be echnen, was einen Sp ung in de Lau zei e u sach . 64 9.3. ERMITTELN DER OPTIMALEN WABENGRÖßE 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 1 10 100 no mie e Ke nellau zei max. Sch i wei e 128 lokale Wo ki ems ( ek. P oblem unk ion) 128 lokale Wo ki ems 192 lokale Wo ki ems ( ek. P oblem unk ion) 192lokale Wo ki ems Abbildung 9.3: Lau zei en ü e schiedene Maximalsch i wei en GTX 280 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10 100 1000 no mie e Ke nellau zei max. Sch i wei e 512 lok. Wo ki. ( ek. P oblem unk ion) 512 lokale Wo ki ems 256 lok. Wo ki. ( ek. P oblem unk ion) 256 lokale Wo ki ems Abbildung 9.4: Lau zei en ü e schiedene Maximalsch i wei en GTX 580 65 11 Zusammen assung Das Ziel de A bei wa es, das Eule -Ve ah en au G akp ozesso en zu po - ie en und da ü zu op imie en. Dies is zum einem mi dem linea en OpenCL- Ve ah en und zum ande en mi den Diaman -/Waben-Tilings gelungen. Das li- nea e OpenCL-Ve ah en is zwa ein seh ein aches Ve ah en, welches nich alle Op imie ungen de GPU ausnu z , abe es we den gu e Lau zei en e ziel , die we- sen lich schnelle sind als e gleichba e CPU-Ve sionen. Algo i hmen die schon ü die CPU pa allelisie wu den, zum Beispiel mi P h eads ode OpenMP, lassen sich leich ü die GPU po ie en. Au de GPU können dann schon einige wich ige abe ein ache Op imie ungen zu seh gu en Lau zei en üh en, die sich nu schwe mi de CPU e eichen lassen. Das Diaman -/Waben- Tiling is wesen lich komplexe , üh abe auch meis zu noch besse en E gebnissen als das linea e OpenCL-Ve ah en, da es meh Vo - eile de G akp ozesso en ausnu zen kann. Bei seh zei in ensi en Be echnungen, bei denen es wich ig is , die Lau zei zu minimie en, wä e es also on Vo eil den bes ehenden Code de a anzupassen, dass möglichs alle Eigenscha en und Be- sonde hei en de GPUs be ücksich ig we den. Dabei muss beach e we den, dass sich einige Op imie ungen gegensä zlich e hal en können. Wie beim Waben-Tiling gesehen, muss e ein Komp omiss zwischen einem op imalen Zug ismus e und de Wiede e wendung des lokalen Speiche s ge unden we den. De Einsa z on G akp ozesso en zum Lösen on Die en ialgleichungen is bei P oblemen, die lange zum Be echnen benö igen, zu emp ehlen. Das Ini ialisie en de GPU und das Übe se zen des Ke nels benö igen alle dings Zei , die sich übe die Lau zei de Be echnung amo isie en muss. OpenCL ha sich im Lau e de A bei als eine geeinge e P og ammie schni - s elle ü G akp ozesso en he ausges ell , bei de jedoch anzume ken is , dass sie speziell ü G akp ozesso en en wickel wu de. OpenCL-Ke nel lassen sich zwa auch au CPUs aus üh en, jedoch sind iele Besonde hei en au P ozesso en nich o handen und üh en do nich imme zu einem Lau zei gewinn, wie zum Bei- spiel de Einsa z lokale Ba ie s und lokale Speiche . Op imie ungen wie zum Beispiel das Speiche zug ismus e , e hal en sich au CPU und GPU eilweise nach eilig, sodass spezielle Ke nel ü GPU und CPU en wickel we den müssen, um den op imalen Speedup au allen De ices zu e hal en. Wa um nde die GPU P og ammie ung o z eno me Geschwindigkei ss ei- ge ungen gegenübe P ozesso en noch keine b ei e Ve wendung in komme ziellen P og ammen? Ein G und kann da in gesehen we den, dass bishe keine s anda di- sie e Schni s elle ü alle G akp ozesso en zu Ve ügung s and. Jede G ak- ka enhe s elle be o zug e seine eigene API (NVIDIA CUDA, ATI S eam). Mi 73 KAPITEL 11. ZUSAMMENFASSUNG OpenCL s eh eine geeigne e Schni s elle ü alle G akka en zu Ve ügung, die den Einsa z on GPUs ü allgemeine Be echnungen wei e e b ei en kann. Die jüngs e Ve gangenhei ha gezeig , dass die S eige ung de Geschwindig- kei on P ozesso en zum G oÿ eil du ch die E höhung de Anzahl de Ke ne und nich meh so seh du ch E höhung des P ozesso ak es e eich wi d. Deshalb is zu e wa en, dass de Einsa z on G akka en zu Be echnung on zei in en- si en P ozessen in Zukun zunimm . Einen wich igen Fak o we den dabei PC Spiele da s ellen, da sie den Sys emen du ch imme neue Inno a ionen wie e bes- se e Physik Modellie ung und KI imme meh Leis ung ab e langen. Beispiele, bei dem de Geschwindigkei sgewinn on GPUs ü nich G ak-bezogene Au ga- ben benu z wi d, sind Spiele wie Ba man: A kham Ci y und Ba man: A kham Asylum ([5],[4]), die die Physik des Spiels du ch GPU-Physix ([11]) be echnen lassen. Abe auch Au gaben des wissenscha lichen Rechnens, nu zen imme meh G akp ozesso en zum Be echnen. Dahe beziehen schon d ei de ün schnells en Supe compu e ([1]) einen G oÿ eil ih e Rechenkapazi ä en aus G akka en. Soll en sich in de Indus ie einhei liche S anda ds bei de GPU-P og ammie ung du chse zen, mi APIs, die auch übe meh e e Jah e hinweg bes ändig sind, so is zu e wa en, dass die GPU-P og ammie ung in Zukun imme b ei e e Ve wen- dung nde . 74 Li e a u e zeichnis [1] TOP500 Supe compu e Si e. Websi e: h p: // www . op500 . o g , besuch am 13.03.2012. [2] Amazon. Websi e: h p: // www . amazon . de , besuch am 2.12.2011. [3] E. Hai e , S.P. Nø se , and G. Wanne . Sol ing o dina y die en ial equa i- ons: Nons i p oblems . Sp inge se ies in compu a ional ma hema ics. Sp in- ge , 1993. [4] PC Games Ha dwa e. Websi e: h p: // www . pcgamesha dwa e . de / aid , 8503 63 / Ba man-A kham-Ci y-T aile -zeig -GPU-Physx-Upda e-Bild e gle ich-mi -und-ohne-E ek e-in-hohe -Au loesung / Ac ion-Spiel / News / , besuch am 14.12.2011. [5] Eidos In e ac i e. Websi e: u lh p://www.ba mana khamci y.o g/, besuch am 14.12.2011. [6] Kh onos OpenCL Wo king G oup. The OpenCL Specica ion, e sion 1.1 , 2011. [7] Ma hias Ko ch. Ezien e Implemen ie ung eingebe e e Runge-Ku a- Ve ah en du ch Ausnu zung de Speiche zug islokali ä . Doc o al hesis, Uni e si y o Bay eu h, Decembe 2006. [8] Adam Lake. Game P og amming Gems 8 . Cou se Technology, 2010. [9] Mic oso . Di ec Compu e. Websi e: h p: // www . mic oso pdc . com / 2009 / P0 9-16 , besuch am 14.12.2011. [10] NVIDIA. Cuda. Websi e: h p: // www . n idia . de / objec / cuda _home _new _de . h ml , besuch am 14.12.2011. [11] NVIDIA. GPU-Physix. Websi e: h p: // www . ge o ce . com / Ha dwa e / Tech nologies / physx , besuch am 14.12.2011. [12] Daniel A. O ozco and Guang R. Gao. Mapping he FDTD Applica ion o Many-Co e Chip A chi ec u es. In P oceedings o he 2009 In e na ional Con- e ence on Pa allel P ocessing , ICPP '09, pages 309316, Washing on, DC, USA, 2009. IEEE Compu e Socie y. [13] K. S ehmel and R. Weine . Nume ik gewöhnliche Die en ialgleichungen . Teubne S udienbüche . B.G. Teubne , 1995. 75 Li e a u e zeichnis [14] Kane S. Yee. Nume ical solu ion o ini ial bounda y alue p oblems in ol ing maxwell's equa ions in iso opic media. IEEE T ans. An ennas and P opaga- ion , pages 302307, 1966. 76 Zusammen assung Die hie o liegende A bei beschä ig sich dami , das explizi e Eule -Ve ah en au G akp ozesso en zu op imie en. Dabei we den die Speiche hie a chien, loka- le Da enwiede e wendung, Ausnu zung de Speiche bandb ei e de GPU und die Synch onisie ung zwischen Hos und De ice genaue un e such . Dabei we den zwei Implemen ie ungen nähe be ach e , das Diaman -Tiling und das linea e Ve ah- en, da sie sich gu eignen um die Op imie ungen genaue zu un e suchen. Es s ell sich dabei he aus, dass Op imie ungen wie die lokale Da enwiede e wendung und de op imale Zug i au den Speiche sich gegensä zlich e hal en. Ein Misch e - ah en (das Waben-Tiling), dass dabei die Vo eile des linea en Ve ah ens und des Diaman -Tilings e ein , üh dahe zu den bes en Lau zei en. Abs ac The aim o he hesis is o in es iga e he Eule me hod o GPUs. The goal is o analyze he memo y hie a chies, local da a- euse, memo y bandwid h o he GPU and he synch oniza ion o he hos and he de ice. Two implemena ions a e conside ed close he diamond iling and he linea me hode, since hey a e well sui ed o in es iga e u he imp o emen s. I u ns ou ha he op imiza ions as local da a- euse and op imum access o he memo y bandwid h beha e con a y. In he end a combined sys em ( he honeycomb iling) ha combines he ad an ages o he linea me hod and he diamond iling leads o he bes esul s.