Home

Diplomarbeit - Queens@TUD - Technische Universität Dresden

1. 70 5 4 Maximale Suchdauer MD5 basierter Passw rter VHDL Implementierung 71 5 5 L sungen einiger N Damenprobleme 0 000000 004 74 5 6 26 Damenproblem Ressourcen Nutzung VHDL 04 76 6 1 Performance Uberblick ooa a ee 89 6 2 Entwicklungszeit und Performancel ooa 2 oo 91 102 Tabellenverzeichnis 103 Auflistungsverzeichnis Me a al Du l n al Yen Behe ne eee VE e EE ee E a 37 4 2 Mitrion Bandbreitengraph 42 5 1 Mitrion C Programm zum Test der SRAM Anbindung 2 2 22222200 56 5 2 Mitrion C Programm zum Test des Direct Streaming 4 59 5 3 Umsetzung der MD5 Operationen Runden 1 und 2 in VHDL 67 Puede Baek Se Dace epee Gace 4 Po ee Beg we oe 69 5 5 Damenproblem Mitrion C Bandbreitengraph nach der Optimierung 78 aoe cease ord koa eae Bes Oa ym ee 107 Kate Sip Bee at as epee Be ee se he ca 109 ere 110 Pensa Gt Lert den tee ates ake ge rane E a ge cee 112 A3 Messschleife Direct Streaming 2 2 ee 112 surar Ran EB Bed 114 A 7 Messschleife Memory Mapped Registers 2 0 2 020000 00004 116 i dow Ee Be ee ee ea Se ed E 118 EE Gee te EE 119 ide See aoe Boe Ee Boa en Be 119 lesan wae Saks aca aes 121 oe 123 Pale nee 125 EE 126 Kee 128 A 16 Damenproblem Java Interface 130 104 Auflistungsverzeichnis 105 Literaturverzeichnis AD09 Dev07 Hoc08 10
2. rasclib_cop_commit jcop_desc NULL return RASCLIB SUCCESS JNIEXPORT jint JNICALL Java_jrasc_JRasc_freeFPGA JNIEnv xjenv jobject jobj jint jcop_desc jstring jalgname jboolean iscopy char const xconst astring jenv gt GetStringUTFChars jenv jalgname amp iscopy return freeFPGA amp jcop_desc astring int freeFPGA int cop_desc char const xconst alglID int res char const xconst ustring getenv USER unsigned long debugl unsigned long finish_alg 1 if res rasclib_cop_reg_write xcop_desc finish_alg amp finish_alg 1 RASCLIB_IMMED_CMD RASCLIB_SUCCESS rasclib_cop_commit cop_desc NULL rasclib_cop_wait cop_desc rasclib_cop_close xcop_desc rasclib_resource_return algID 1 rasclib_resource_release l ustring return res Auflistung A 16 Damenproblem Java Interface 20 o package jrasc import java io InputStream import java io OutputStream import java util Date xxProvides access to RASC FPGAs public class JRasc if library cannot be found gt UnsatisfiedLinkError static System loadLibrary rascjni The paket size in bytes to be send private final int inputBytes The paket size in bytes to be received x private final int outputBytes Handle to the represented FPGA configuration x private final int hdl A3 DAMENPROBLEM 131 The identifi
3. mem D memcreat mem_sl0 memcreat Initialize Blocking bits N bhO 0 bits N bu0 0 bits N bd0 0 bits N bits N bits N bhi bul bdl for i in lt 0 L 1 gt uint N q uint N 1 lt lt Ox1F amp cs gt gt uint 32 L i 1 x5 bhO bhO q bud bits N bu0 q lt lt 1 bdO bdO q gt gt 1 bh0 bu0 bd0 mem_bl memwrite mem_b0 L bh1 bul bdl bits N sl bh1 bul bdl mem_sll memwrit tuple mem bits NNN N Explore Solutions uint 46 cntO D int 6 i L ent mem_al while i gt L mem_bt mem_slt untup mem_loop 3 cycles delay slot mem_slt1 memread mem_slt i watch slot 1 cycle delay bp mem_bt1 memread mem_bt i bits N 3 bparray bp bhp bup bdp bparray 0 bparray 1 bparray 2 if free slot has been found and not last column mem_loop if slot bits N 0 amp amp i lt N 1 prepare slots and blocking 2 cycles nslot slot amp uint N uint N slot next slot to try bits set next column blocking and slots N cslots mem bits NNN N mem_b_last mem bits N N mem_sl_last free slots yet to try mem_sl10 L sl thus requiring at most 4 bits ement lid Board Completions 46 Bit should be enough Block RAM tal diagonal up diagonal down mem bits N N mem_loop tup mem_bl mem_s1l1 slot nslot watch cslots set current c
4. 65 70 sraml_wr_cmd_vld lt 0 if rst 1 meml_wr_data lt meml_idx lt others gt write_done lt 0 else if others gt 0 ON sramO_rd_data_vld 1 AND split input into two 64 Bit meml_wr_data 127 downto 80 lt meml_wr_data 79 downto 64 meml_wr_data 63 downto 16 meml_wr_data 15 downto 0 sraml_wr_cmd_vld lt 1 end if if sraml_wr_cmd_vld 1 then meml_idx lt meml_idx 1 end if op_count then FER if meml_idx write_done lt end if end if alg_don end if end process lt write_done lt sram0_rd_data 79 downto 64 lt sram0_rd_data 63 downto 16 lt sram0_rd_data 15 downto 0 then synchronous reset write_done 0 then values and add inc_value to both sram0_rd_data 127 downto 80 inc_value inc_value A l SRAM SCHNITTSTELLE 109 Auflistung A 2 SRAM Latenzmessung mit VHDL E if rst 1 then ctr lt others gt mem2_wr_done lt mem2_rd_start lt mem2_rd_done lt debug4 lt else cbr lt ctr 13 others 20 if mem2_wr_done mem2_wr_data 11 mem2_wr_data 63 mem2_wr_cmd_vld mem2_wr_done lt 25 end if if mem2_rd_start mem2_rd_cmd_vld 30 end if 35 debug4 11 downt mem2_rd_done lt end if end if end if end process 40 mem2_wr_data 63 downto 0 mem2_rd_start lt debug4 23 downto 12
5. time endtime starttime else 55 time endtime starttime2 print results to stdout printf Sf MByte s f MiByte throughput float arguments cycles arguments num_bytes time 1000000 0 60 float arguments cycles arguments num_bytes time 1024 1024 114 ANHANG A QUELLCODES A 3 Memory Mapped Registers Auflistung A 6 Memory Mapped Registers VHDL Implementierung 0 Register 32 is used for flags read and write by host and FPGA possible extractor REG_IN finish_alg 1 u alg_def_reg 32 63 extractor REG_IN adr_used 5 u alg_def_reg 32 4 0 Registers 0 to 15 are used as Register Input 16 64Bit values at once 5 extractor REG_IN fat_in 1024 u alg_def_reg 0 1023 0 Registers 16 to 31 are used as Register Output 16 64Bit values at once extractor REG_IN fat_out 1024 u alg_def_reg 16 1023 0 10 Schnittstelle Signaldefinitionen manage input data proc_input process clk 15 begin if clk event and clk 1 then rising edge fifo_put lt 0 FOR i IN 0 TO 15 LOOP if adr_updated i 1 then 20 fifo_din lt adr i fifo_put lt 1 end if END LOOP end if 25 end process get register update latency proc_debug process clk begin 30 if clk event and clk 1 then rising edge if rst 1 then synchronous reset debug 1 lt others gt 0 debug 2 lt
6. 1 res rasclib_algorithm_reg_write al_desc op_count amp op_count 1 RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS fprintf stderr reg write of op_count failed at d d n __LINE__ res rasclib_perror reg write of op_count res return 1 send value to be added by algorithm to every 64 Bit value res rasclib_algorithm_reg_write al_desc inc_val amp inc 1 RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS fprintf stderr reg write of alg_inc_val failed at d d n __LINE__ res rasclib_perror reg write of alg_inc_val res return 1 start gtod get start time Loop for measuring throughput for i 0 i lt arguments cycles it res rasclib_algorithm_send al_desc sramO_in in arguments num_bytes if res RASCLIB_SUCCESS fprintf stderr send failed at d d n __LINE_ res return 1 rasclib_algorithm_go al_desc start algorithm res rasclib_algorithm_receive al_desc sraml_out out arguments num_bytes if res RASCLIB_SUCCESS fprintf stderr recv failed at d d n __LINE__ res return 1 A 1 SRAM SCHNITTSTELLE 111 60 65 70 75 85 90 95 100 105 110 rasclib_algorithm_commit al_desc NULL rasclib_algorithm_wait al_desc end gtod get end time if arguments vhdl TRUE rasclib_algorithm_reg_read al_desc mem2_latency amp debugl
7. 80 CONV_STD_LOGIC_VECTOR 131 PIPES mod realchars 8 second char has to be reduced by constant chardiffl std_logic_vector 7 downto 0 CONV_STD_LOGIC_VECTOR 131 PIPES realchars 8 does only work if more than 33 different characters are used proc_cmp process clk begin if clk event and clk LI then rising edge check which pipe has found the hash and create plaintext vld_cmp lt 0 FOR p IN 0 TO PIPES 1 LOOP if vout_pipe p 1 then vpipe lt Di vld_cmp lt 1 save all characters first two characters can already be adjusted pipeline depth char 0 lt charctrs CHARS 8 1 downto CHARS 1 x8 CONV_STD_LOGIC_VECTOR PIPES 1 8 chardiff0 char 1 lt charctrs CHARS 1 8 1 downto CHARS 2 x8 chardiffl FOR c IN 2 TO CHARS 1 LOOP char c lt charctrs CHARS c 8 1 downto CHARS c 1 x8 END LOOP end if END LOOP end if clock end process proc_plainout process clk begin if clk event and clk LI then rising edge set the plaintext of unused characters dout_plain 447 downto CHARS 8 lt others gt 0 if rst LI then cvld lt others gt 0 else if vld_cmp 1 then process Chart if char 0 lt vfirstchar then dout_plain CHARS 8 1 downto CHARS 1 x8 lt vrlastchar vfirstchar char 0 CONV_STD_LOGIC_VECTOR vpipe 8 char
8. amp debug rasclib_cop_reg_read cop_desc debug7 amp debug rasclib_cop_commit cop_desc NULL Read DEBUG Registers 1 RASCLIB_IMMED_CMD 1 RASCLIB_IMMED_CMD 1 RASCLIB_IMMED_CMD RASCLIB_IMMED_CMD 1 RASCLIB_IMMED_CMD 1 RASCLIB_IMMED_CMD 1 RASCLIB_IMMED_CMD i On OI VG GA b i H for i 1 i lt 8 i printf debug d 0x 1x t i debug i DEBUG_OUT Updated Latency for i 0 i lt 4 i ulatency ix4 0 unsigned int debug i 1 amp 0xFFF000000000 gt gt 36 debug i A3 MEMORY MAPPED REGISTERS 117 60 65 70 1 amp 0xFFFO00000000000 gt gt 48 ulatency ix4 1 unsigned int debug i 1 amp 0OxFFFO00000 gt gt 24 debugl i 1 amp 0xFFFO00000000 gt gt 36 ulatency ix4 2 unsigned int debug it 1 amp 0xFFFO00 gt gt 12 debug i 1 amp 0 xFFFO000000 gt gt 24 ulatency ix4 3 unsigned int debug i 1 amp 0xFFF gt gt 0 debug i 1 amp 0 for i 0 i lt 16 i for i 0 i lt 3 i platency ix4 0 5 amp 0xFFFOO platency ix4 1 5 amp 0xFFFOO platency 1i 4 2 xFFF000000 platency 1i 4 3 xFFFO00 gt gt 1 for i 0 i lt 12 i DEBUG_OUT n DEBUG_OUT nPoll xFFFO00 gt gt 12 printf SdJ d i ulatency i ing Latency unsigned int debug i 5 000000
9. if sram2_rd_data_vld debug4 35 downto 24 proc_latency process clk begin if clk event and clk 1 then rising edge mem2_wr_cmd_vld lt 0 5 mem2_rd_cmd_vld lt 0 mem2_wr_addr lt others gt 0 mem2_rd_addr lt others gt 0 synchronous reset lt others gt 0 gt 0 45 nue 0 extractor REG_OUT mem2_latency 64 u debug_port 4 gt L I 0 AND sram2_wr_busy 0 then downto 0 lt ctr write current ctr downto 12 lt others gt 0 Ss is PIT 0 AND mem2_wr_done 1 AND sram0_rd_busy 0 then lt E FI lt ctr 1 AND mem2_rd_done 0 then lt Gere o 0 lt sram2_rd_data 11 downto 0 eae 110 ANHANG A QUELLCODES Auflistung A 3 Ausschnitte des C Programms zur Durchsatzmessung des SRAM E 20 25 30 35 40 45 50 55 unsigned long sin unsigned long out int main int argc char xargv evaluate command line arguments variables declaration allocate memory if buffers_make amp arguments lt 0 printf buffers_make failed n return 1 initialize input values arguments size 2 64 Bit values for i 0 i lt arguments sizex2 i zs inti 0 special argument for VHDL implementation if arguments vhdl TRUE if arguments nop TRUE op_count 0 else op_count arguments size
10. 5 Schnittstelle Signaldefinitionen parameter set with algorithm defined register 10 inc_value lt adr0 15 downto 0 start reading when stream data are ready and algorithm is ready strm_in_O_rd_en lt strm_in_data_rdy AND rd_en strm process clk 15 begin if clk event and clk 1 then rising edge rd_en lt 0 strm_out_0_data 127 downto 80 lt strm_in_data 127 downto 80 20 strm_out_0_data 79 downto 64 lt strm_in_data 79 downto 64 inc_value strm_out_0_data 63 downto 16 lt strm_in_data 63 downto 16 strm_out_0_data 15 downto 0 lt strm_in_data 15 downto 0 inc_value if rst 1 then synchronous reset 25 strm_out_0_data_vld lt 0 strm_out_0_data_last lt 0 SEA t0 strm_ou flush lt 0 strm_out data lt others gt 0 alg_done lt 0 30 else if strm_out_almost_busy 0 AND strm_in_complete 0 then rd_en lt 1 end if strm_out_0_data_vld lt strm_in_vld 35 end of stream send last value if strm_in_complete 1 then strm_out_0_data_last lt 1 strm_out_0_flush lt 1 40 end if alg_done lt strm_out_flushed end if end if 45 end process Auflistung A 5 Messschleife Direct Streaming 0 starttime gtod for i 0 i lt arguments cycles itt cop_desc rasclib_cop_open arguments algID arguments io if cop_desc RASC
11. APD 3 4 2 Algorithmen Verwaltung 3 4 3 GNU Project Debugger GDB 3 4 4 Algorithmus Konfigurations Tool 4 Programmierm glichkeiten der SGI RASC Plattform 4 1 Manon SDK von Mitrionicsl 4 1 1 Programmiersprache Mitrion C 4 1 2 Mitrion Virtual Processor 4 1 3 _Mi trion Simulator EN 4 2 1 Hardware Entwurf mit VHDL pete ete Aa ee 4 2 3 Hardware Synthese 5 Fallbeispiele 5 1 _SRAM Schnittstellel 00000020000 5 1 1 Implementierung 5 1 2 Tests und Messungen 5 2 Direct Streaming 22 2 2220 5 2 1 Implementierung 5 2 2 Tests und Messungen 5 3 Kommunikation ber Memory Mapped Registers 11 13 15 19 21 21 23 23 26 27 28 28 29 30 31 32 33 34 36 39 40 43 45 48 49 5 3 1 Implementierung 2222 2 2 Coon SE te ae ee ee D ee e E a eg 54 MD5 Br te F rce A oa u a ac awe ENEE we E E de eS 541 VHDLE Entw rll 2 2046 EE e de en ra A e da 5 4 2 Implementierung mit Mumon C 200200000 NE hoe ple gre bet le me ee a te br EE d ce E e ee ee ee 5 5 1 Backtracking Algorithmus und Parallelisierung 5 5 2 _VHDL Implementierung 0 02 000000004 5 5 3 Implementierung mit Mumon C 2 000000 000 4 5 5 4 Performance o 2 2 u we san aaa nn 6 Auswertung ee ee EE ee 6 2 Vergleich von Mitrion C und V
12. Innherhalb des Mitrion C Programmes k nnen unter Verwendung einer FOR oder FOREACH Schleife die Elemente des Streams verarbeitet werden W hrend die RASC Core Services 5 2 DIRECT STREAMING 59 0lMitrion C 1 5 Options cpp alg name teststrmitc alg id 4242 alg ver 2 define SRAM mem bits 128 2048 5 SRAM SRAM bits 128 main SRAM sram0 SRAM sranl bits 128 strm_in uint 64 inc_val strm_out foreach e in strm_in uint 16 8 inl6 ei uint 16 inl6_0 inl6 0 inc_val 10 uint 16 inl6_4 inl6 4 inc_val bits 128 result inl6_0 inl6 1 inl6 2 in16 3 inl6_4 inl6 5 in16 6 in16 7 result sram0 sraml strm_out Auflistung 5 2 Mitrion C Programm zum Test des Direct Streaming vier Streams je Richtung Eingang Ausgang unterst tzen Kann mit Mitrion C nur ein Eingangs und ein Ausgangs Stream verwendet werden Der Quellcode in 2 zeigt ein einfaches Beispiel zur Nutzung des direkten Streamings Dabei wird wie bei dem Beispiel f r die SRAM Kommunikation jeder 128 Bit Wert in zwei 64 Bit Werte aufgeteilt und zu diesen ein vom Host Programm bergebener Wert addiert Um Verdrahtungsprobleme oder zus tzliche Verz gerungen von vornherein zu vermeiden wurden die Additionen wiederum auf 16 Bit beschr nkt Auch in VHDL ist das Streaming Interface sehr bersichtlich und leicht zu implementieren siehe Quell codeausschnitt im Anhang A A Im Vergleich zur SRAM Ko
13. Jeder dieser Z hler repr sentiert ein ASCH Zeichen wobei der zu durchsuchende Bereich der ASCII Tabelle generisch gew hlt werden kann Der erste Z hler arbeitet mit einer der Pipelinezahl entsprechenden Schrittweite wodurch ebenso viele Nachrichtenbl cke pro Takt erzeugt werden k nnen In diesem VHDL Entwurf wird die Klartextl nge generisch festgelegt was zum einen die Implementierung vereinfacht und zum anderen weniger FPGA Ressourcen ben tigt durch Verwendung von weniger als 56 Zeichen Bei der Umsetzung der MD5 Pipeline besteht das wesentliche Problem in der effizienten und ressourcen sparenden Bereitstellung der Daten in den einzelnen Stufen Ein naiver Ansatz speichert eine Nachricht bis deren Verarbeitung erfolgt ist Die erzeugten Zwischenergebnisse einer Stufe werden dabei tempor r in Registern gehalten bis sie nicht mehr ben tigt werden Eine Pipeline speichert damit immer soviele Nachrichten wie sie gerade verarbeitet Tiefe der Pipeline 512 Bit Der Vorteil dieses Ansatzes liegt darin dass der Klartext zu einem gefundenen Hash direkt anliegt Nachteilig ist der immense Bedarf an 66 5 FALLBEISPIELE MD5 Topmodul clk Start wort valid Hash Klartext Abbildung 5 6 MD5 Brute Force VHDL Entwurf FPGA Fl che allein 4096 Virtex 4 Slices f r die Nachrichtenspeicherung einer Pipeline mit 128 Stufen wenn pro Slice 16 Bit gespeichert werden Um den Fl chenbedarf f r die Speicherung
14. eine Dame pro Takt setzen und damit ein Teilproblem schneller berechnen konnten wird in der aktuellen Implementierung in einem Takt entweder eine Spalte zur ckgesprungen oder eine Dame gesetzt um im folgenden Takt mit 5 5 DAMENPROBLEM 75 XC4VLX200 XC4VLX200 DENSOS NN Vin DIECON Server Kommunikations DB Interface QSlice 0 QSlice s Abbildung 5 10 Infrastruktur und RASC Anbindung von Queens TUD der n chsten Spalte fortzufahren Diesen Geschwindigkeitsverlust gleichen die aktuellen Solver oder L sungsinstanzen mit geringerem Ressourcenbedarf und einem k rzeren kritischen Pfad aus Dadurch kann das Gesamt Design mit h heren Taktfrequenzen betrieben werden und mehr Teilprobleme gleich zeitig berechnen Die feinere Granularit t der Solver erm glicht zudem noch eine bessere Ressourcen ausnutzung des FPGA Die wesentliche Aufgabe f r diese Arbeit bestand in der Adaption des Damenproblem Hardware Designs an die SGI RASC Plattform Abbildung zeigt den prinzipiellen Aufbau und die Infrastruktur des Queens TUD Projektes Die Kommunikationsschnittstelle und damit die RASC Anbindung wurde her vorgehoben Es stehen zwei Xilinx Virtex 4 LX200 FPGAs ein RC100 Blade vgl Abschnitt 3 2 welche in die SGI Altix 4700 vgl Abschnitt 3 1 integriert sind zur Verf gung Auf einem zentralen Server beinhaltet eine Datenbank alle ausstehenden und ber
15. ist werden die Operationen pro Stufe auf zwei Zuweisungen aufgeteilt Vor der Umsetzung in Hardwa re f hrt der Mitrion Compiler Optimierungen durch und passt die Abfolge der Operationen wie sie im Quellcode stehen an Das Ergebnis ist eine 128 stufige Pipeline Um diese mit Daten zu versorgen wur de eine Verschachtelung von FOREACH Schleifen entsprechend der Wortl nge ber einen Bereich der ASCIH Tabelle z B Kleinbuchstaben verwendet Das komplettieren des Nachrichtenblocks kann dann hnlich wie in der VHDL Implementierung durch die feste Zeichenl nge einfach gehalten werden Zudem kann aus dem Datenabh ngigkeitsgraphen des Mitrion Simulators abgelesen werden dass f r die Speicherung des Klartext Nachrichtenblockes wie in der VHDL Implementierung Block RAM verwen det wird Der Mitrion Compiler verwendet zur Speicherung von Vektoren ab einer gewissen Gesamt Bitbreite prinzipiell Block RAM 5 4 MD5 BRUTE FORCE 69 o uint 32 a D state_in 0 uint 32 b_0 state_in 1 uint 32 c_0 state_in 2 uint 32 d D state_in 3 5 erste Runde Stufe 1 und 2 uint 32 a_l a D d_O b_0 amp ef da 0 x 0 OxD76AA478 uints22 2 2 a_l lt lt 7 al gt gt 32 7 b_0 uint 32 d_l d_0 c_0 a_2 amp b 0 c_0O x 1 OxE8C7B756 uint 32 d_2 d_1 lt lt 12 d_1 gt gt 32 12 a_2 10 zweite Runde erste Stufe uint 32
16. neue Modelle dennoch sehr gute FP Leistung und k nnen mit aktuellen Prozessoren mithalten Einen weiteren Geschwindigkeitsschub kann mit FPGAs erreicht werden wenn geringe Bitbreiten ben tigt werden W hrend eine 64 Bit Addition nur etwa doppelt soviel Ressourcen wie eine 32 Bit Addition ben tigt sind es beim Umstieg von 32 Bit auf 64 Bit Multiplikation viermal soviele Ressourcen Bei einfacher Genauigkeit 32 Bit erreicht auch ein Virtex 4 LX200 etwa 46 GFLOP s was fast f nfmal so schnell wie der Wert f r doppelte Genauigkeit 64 Bit aus Tabelle 2 3 ist Zudem werden gute FP Bibliotheken f r Mikroprozessoren in Assembler handoptimiert was einen hnlichen Aufwand wie die Hardware Programmierung mit sich bringt 2 6 FPGAs als Hardware Beschleuniger im HPC Neben anderen Hardware Beschleunigern werden im Hochleistungsrechnen HPC auch FPGAs einge setzt Ein Grund daf r ist der enorme Stromverbrauch auf herk mmlichen Mikroprozessor basierten gro en Rechnersystemen Im Bereich eingebetteter Systeme ist der Stromverbrauch schon lange ein be grenzender Faktor w hrend dies erst seit Kurzem im HPC eine Rolle spielt Abbildung P 6 zeigt die Leistungsaufnahme von FPGAs und GPUs im Vergleich zu CPUs in Abh ngigkeit vom Geschwindig keitsgewinn vgl Formel 2 1 Als Referenz wird ein CPU Kern mit einer Leistungsaufnahme von 20 Watt Popy 20W angenommen ein FPGA mit 25 Watt Prpca 25W und ein GPU mit 125 Watt Papu 125W Um als
17. welche ben tigt werden um das Mitrion C Programm auf dem FPGA auszuf hren ROOT 1 50 0 ch 50 rch 50 BW limited body ch 50 rch 50 Lt iterations 5 Env main foreach lt 5 gt de 50 0 ch 50 rch 50 BW limited body ch 10 rch 10 1 iterations 10 Env main foreach lt 5 gt for lt 10 gt 1 30 0 ch 10 rch 10 Latency limited dataloop body latency 3 0 Auflistung 4 2 Mitrion Bandbreitengraph Zus tzlich gibt der Simulator einen Bandbreitengraph aus vgl Auflistung 4 2 und Quellcode 4 1 Die ser Graph verdeutlicht die Schleifenstruktur eines Mitrion C Programmes nach der Optimierung und zeigt die gesch tzten Latenzen und Durchs tze der Schleifen an Die Latenz einer Schleifenstruktur wird als Anzahl von Taktzyklen bis die Schleife alle Ergebnisse produziert hat angezeigt Die Leerlaufzeit 4 2 HARDWARE ENTWICKLUNGSABLAUF 43 engl choke und damit die Anzahl der Taktzyklen bis eine Schleife erneut ausgef hrt werden kann wird ebenso angezeigt Dazu wird noch die durch andere Mitrion C Programmteile bedingte Leerlauf zeit engl relaxed choke dargestellt Damit ist eine Schleifenstruktur entweder durch deren Bandbreite oder Latenz begrenzt F r eine bandbreitenbegrenzte Schleife werden choke und relaxed choke angezeigt F r eine durch ihre Latenz beschr nkte Schleife wird die zugeh rige Schleifenlatenz angezeigt Da die L nge von Streams dynamisch ist sind die Angaben bei Schleife
18. 53 5 Fallbeispiele Nachdem die Hardware und ihre Kenndaten bereits in den vorangegangenen Kapiteln vorgestellt wur den soll nun die Leistungsf higkeit der SGI RASC Programmierplattform anhand von Benchmarks und Beispielanwendungen bewertet werden Hierf r wurden die in den Abschnitten 3 3 vorgestellten Kom munikationsvarianten implementiert und anschlie end Bandbreiten und Latenzmessungen vorgenom men Mit den Implementierungen des MD5 Algorithmus und des Damenproblems sollen neben dem Leistungsverm gen FPGA basierter Beschleuniger auch die Performance und Implementierungsunter schiede zwischen Mitrion C und VHDL verdeutlicht werden Da Mitrion nur die Ansteuerung eines Koprozessors unterst tzt wird aus Gr nden der Vergleichbarkeit auch nur ein RC100 FPGA betrachtet Dementsprechend verdoppelt sich der gemessene Geschwindigkeitsgewinn f r ein RC100 Blade wenn zwei Prozesse gestartet und damit die FPGAs unabh ngig voneinander angesteuert werden In dieser Arbeit wurden die Mitrion SDK XL v1 5 3 build 535 und Xilinx ISE 9 2 04i verwendet Bei der Betrachtung von Mitrion C Quellcode ist zu beachten dass der Mitrion Compiler Optimierungen vornimmt und damit eine sichere Bestimmung der ben tigten FPGA Takte pro Zuweisung nicht m glich ist Anstelle dessen k nnen die Ausgaben des Kommandozeilen Simulators herangezogen werden Bei der Programmierung von RASC unter Verwendung einer Hardwarebeschreibungssprache m ssen im Gegensat
19. 6 BW limited body ch 1 rch 6 2 iterations 6 Env main foreach 1 solve026 or lt 6 gt 10 1 12 0 ch 6 rch 6 Latency limited dataloop body latency 2 0 3 iterations 1 Env main foreach 1 solveQ26 while 1 11 0 ch 1 rch 6 Latency limited dataloop body en 110 15 nn End Summary Bandwidth Graph 51 MemRead 7 0x0ad0202e00008751001 Blockierung aktuelle Spalte lesen 52 MemRead 7 0x3002fdc noch zu testende Felder lesen 56 11 Watch slot 0x3002fdc Lesevorgang beendet 57 11 Watch cslots 0x3002fd8 Felder der aktuellen Spalte anpassen 20 58 MemWrite 7 0x3002fd8 schreiben 58 MemWrite 8 0x0568125c00030751005 Blockierung naechsten Spalte schreiben 59 11 Watch slots_nc 0x28a87e0 freie Felder der naechsten Spalte 60 MemWrite 8 0x28a87e0 schreiben 62 MemRead 8 0x0568125c00030751005 naechster Durchlauf Auflistung 5 5 Damenproblem Mitrion C Bandbreitengraph nach der Optimierung einer separaten Bedingung untergebracht um die Logiktiefe zu verringern Die Berechnung der gleichen Test Vorbelegungen ben tigte nach der Optimierung 1 Stunde und 48 Minuten wobei 50 Teilprobleme gleichzeitig verarbeitet werden k nnen Der zugeh rige Bandbreitengraph und einige Debug Ausgaben sind in Listing dargestellt Die kritische Schleife wird mit nun noch elf Takten Latenz angegeben Werden zus tzlich die Debug Ausgaben f r den Schleifenrumpf betrachtet Kann der kritisc
20. 8 M Hashes s theoretisch 100 200 300 440 1173 M Hashes s gemessen 100 200 288 440 1173 Effizienz 100 100 96 100 100 Tabelle 5 3 Leistungsvergleich der MD5 Hardware Implementierungen Bei der Mitrion Umsetzung ist ein leichter Rtickgang der Effizienz mit drei Pipelines zu erkennen Dies k nnte daran liegen dass die Generierung des Klartextes aus Timing Griinden mit mehr Pipelines ver n dert werden muss Eine exakte Aussage dariiber kann jedoch aufgrund des compiler generierten Designs nicht getroffen werden Die Effizienz der VHDL Umsetzungen liegt konstant bei rund 100 Auch die Generierung und Riickgewinnung des Klartextes bleibt hinsichtlich ihrer Ressourcen Ausnutzung nahe zu unabh ngig von der Anzahl der Pipelines Ein Vergleich der vorgenommenen Hardware Implementierungen mit Software Umsetzungen auf Gra fikkarten und CPUs zeigt Abbildung Die Messungergebnisse der Nvidia Grafikprozessoren wur den entnommen w hrend die MD5 Brute Force Performance der Prozessoren AthlonX2 5000 und Core2Duo E8400 und des Grafikprozessors Radeon 3850 mit BarsWF MDS5 BruteForcer v0 8 auf normalen Desktop Rechnern gemessen wurde Der Test des Intel Itanium 2 Prozessors basiert auf der xyssl Bibliothek welche auch als Grundlage f r die Hardware Implementierungen verwendet wurde und keine Optimierungen hinsichtlich Befehlsatzerweiterung moderner Prozessoren nutzt BarsWF 0 8 hingegen gilt derzeit als die schnellste Software L sung zur Brute
21. Data Les es RASCLIB_IMMED_CMD if res rasclib_cop_commit jcop_desc if rasc_out_vld 1 Wait 3 jclass jmethodID sleep RASCLIB_SUCCESS break 0s before next Re Try rasclib_cop_reg_read jcop_desc NULL rasc_out_vld return res gt FindClass jenv const clsThread x jenv const mthSleep xjenv Wi JJA 4 xjenv gt CallStaticVoidMethod jenv jenv gt ExceptionClear jenv clsThread mthSleep amp rasc_out_vld 1 java lang Thread gt GetStaticMethodID jenv clsThread jlong 10000L xxxxx Read Fat Register Output 4 64Bit Registers xrxx res rasclib_cop_reg_read jcop_desc out256 fat_out512 ADR_SIZE RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS return res rasclib_cop_commit jcop_desc NULL for j 0 j lt ADR_SIZE j int pos j x 8 byteout pos 7 fat_out512 j amp OxFF byteout pos 6 fat_out512 j amp OxFFO0O gt gt 8 byteout pos 5 fat_out512 j amp OxFFO000 gt gt 16 byteout pos 4 fat_out512 j amp OxFFO00000 gt gt 24 byteout pos 3 fat_out512 j amp OxFFO0000000 gt gt 32 byteout pos 2 fat_out512 j amp OxFFO000000000 gt gt 40 byteout pos 1 fat_out512 j amp OxFFOO0000000000 gt gt 48 byteout pos fat_out512 j amp OxFFOO0000000000000 gt gt 56 3rd and 4th argu
22. Datenabh ngigkeitsgraphen der die Da tenparallelit t und die Parallelit t durch Pipelines visualisiert Jeder Knoten des Graphen repr sentiert eine vom Programm durchgef hrte Operation Jede Kante welche zwei Knoten verbindet stellt eine gerichtete Datenabh ngigkeit dar Normalerweise ist ein Knoten von dar berliegenden Vorg ngerknoten abh ngig Umgekehrte Abh ngigkeiten wenn also ein Knoten von seinem darunter liegendem Vorg n ger abh ngt werden mit gelben Kanten dargestellt Knoten mit einem schwarzen Rand sind Mitrion C Funktionen oder Schleifen und beinhalten einen Untergraphen Wird der Simulator ausgef hrt flie en Daten ber die Kanten durch die Knoten welche entsprechende Operationen auf diesen ausf hren Verschiedene Farben weisen auf den Zustand eines Knotens w hrend der Simulation hin 4 1 MITRION SDK VON MITRIONICS 41 DJ Mitrion Data Dependency Graph va x File View Simulator Help fat Step 12 Speed 1 B Names Types je Daa P P A 5 Input main sramO 1 1 Input main sram1 1 1 sram0 in mem uint 128 2048 sramQ sraml in main out 0 mem uint 128 2048 re i in ng res Gn sraml sral i res g 4 sram a p main sram0 Out 0 1 1 main sram1_final Out 1 0 1 Il H Abbildung 4 3 Mitrion C Simulation mit GUI gr n Der Knoten hat im letzt
23. FORCE 67 ol function md5_logicl2 dino std_logic_vector 31 downto 0 dini std_logic_vector 31 downto 0 ding EE downto 0 din3 std_logic_vector 31 downto 0 dinx std_logic_ nn downto 0 5 Deren std_logic_vector is begin return dinO dinl XOR din2 AND din3 XOR dinl dinx end md5_logicl2 10 function md5_shift tmp std_logic_vector 31 downto 0 shift positive din std_logic_vector 31 downto 0 const std_logic_vector 31 downto 0 return std_logic_vector is 15 variable to_shift std_logic_vector 31 downto 0 begin to_shift tmp const return std_logic_vector unsigned to_shift sl1 shift OR std_logic_vector unsigned to_shift srl 32 shift din 20 end md5_shift Auflistung 5 3 Umsetzung der MD5 Operationen Runden 1 und 2 in VHDL durch w hrend die md5_shift Funktion eine Linksrotation vornimmt Die bergabeparameter shift und const sind Konstanten Der Aufruf dieser Funktionen erfolgt genauso wie in anderen Program miersprachen durch bergabe der Parameter Signalen Ein Auschnitt der VHDL MD5 Pipeline ist in gelistet Jeder von einer MD5 Pipeline erzeugte Hash wird mit dem gesuchten Hash verglichen und bei Uberein stimmung der zugeh rige Klartext erzeugt Der erzeugte Hash kommt in vier 32 Bit Bl cken jeweils um zwei Takte verz gert aus der Pipeline wodurch sich ein Vergleich der einzelnen Bl cke mit den zugeh rigen Teilen des gesuchten Hashes anbietet vgl Quellcode
24. Force Suche von MD5 Hashes und unterst tzt ausschlie lich Prozessoren mit der SSE2 Erweiterung Zudem liegt es auf CUDA oder Brook basierend zur Nutzung von Grafikkarten vor Werden 67 verschiedene Zeichen Gro Kleinbuchstaben Ziffern f nf Sonderzeichen und eine Wort 5 5 DAMENPROBLEM 71 Core2Duo E8400 3GHz Athlon X2 2 8GHz Itanium2 1 6GHz 0 100 200 300 400 500 600 700 800 900 1000 1100 1200 Millionen MD5 Hashes pro Sekunde Abbildung 5 7 MD5 Brute Force Performance Vergleich lange von acht Zeichen betrachtet konnen daraus 67 verschiedene Worter gebildet werden Die schnells te hier vorgestellte Implementierung VHDL Entwurf auf RC100 FPGA ben tigt maximal 4 1 Tage um das Klartextwort zu so einem MD5 Hash zu finden Bei einer L nge von zehn Zeichen l sst es sich mit 64 FPGAs im Durchschnitt in etwa 21 Wochen ermitteln Auf MD5 basierende Passw rter aus zw lf Zeichen sind dagegen nach aktuellem Kenntnisstand f r hinreichend lange Zeit sicher vor solchen An griffen Tabelle 5 4 zeigt eine bersicht der maximalen Suchdauer von Klartextworten verschiedener L nge zu MD5 Hashes durch die schnellste hier betrachtete Implementierung Wortl nge Zeichenraum maximale Suchdauer 6 a z A Z 17 4 Sekunden 6 95 ASCIH Zeichen 10 8 Minuten 8 a z A Z 13 1 Stunden 8 a z A Z 0 9 5 Sonderzeichen 4 1 Tage 8 95 ASCII Zeichen 9 7 Wochen 10 a z A Z 4 0 Jahre 10 95 ASCIH Zeichen 1673 Jahre Tab
25. Schaltungen mit spezieller Funktio nalit t integriert Diese ben tigen weniger Chip Fl che und k nnen schneller getaktet werden als qui valente Schaltungen welche durch normale CLBs abbgebildet werden 2 3 St rken und Schw chen von FPGAs Zur Darstellung einiger St rken und Schw chen von FPGAs werden in diesem Abschnitt fest verdrahtete Chips wie ASICs Mikroprozessoren und andere Hardware Beschleuniger als Vergleich herangezogen Prinzipiell l sst sich feststellen dass FPGAs die Flexibilit t von Software und die Leistungsf higkeit dedizierter Hardware vereinen Eine hohe Verarbeitungsleistung durch FPGAs ist immer dann zu erwarten wenn die Anwendung im Wesentlichen mit Integerverarbeitung und Logikoperationen auskommt und zudem gut parallelisierbar ist Im Vergleich zur parallelen Abarbeitung von Software auf Mehrkernprozessoren oder Rechnersyste men mit vielen CPUs wird bei FPGAs von Hardwareparallelit t gesprochen Sequentielle Algorithmen die auch durch Pipelining keine Parallelverarbeitung erm glichen werden kaum Geschwindigkeitsge winnen erreichen Dies liegt zum einen an den Taktraten von FPGAs die ungef hr um den Faktor zehn geringer sind als bei Mikroprozessoren und zum anderen am zus tzlichen Kommunikationsaufwand W hrend Prozessoren eine feste Verarbeitungsbreite aufweisen kann der Hardware Entwickler die Bit breite von Datentypen und Operationen bestimmen Dies ist einer der entscheidenden Vorteile vo
26. VHDL 0 extractor VERSION 1 4 extractor CS 2 2 extractor SRAM sram0O_in 524288 128 sram 0 0x0000 in u stream extractor SRAM sraml_out 524288 128 sram 1 0x0000 out u stream extractor REG_IN op_count 19 u alg_def_reg 0 18 0 5 extractor REG_IN inc_val 8 u alg_def_reg 0 47 32 Schnittstelle Signaldefinitionen 10 parameters set with algorithm defined register op_count lt adr0 18 downto 0 inc_value lt adr0 47 downto 32 request values from SRAMO 15 memO_rd_cmd_vld lt sramO_rd_cmd_vld memO_rd_addr lt sram0_alg_offset 9 amp mem0_idx amp 0000 read mem process clk begin if clk event and clk 1 then rising edge 20 sramO_rd_cmd_vld lt 0 if rst 1 then synchronous reset mem0_idx lt others gt 0 read_done lt 0 else 25 if read_done 0 AND sramO_rd_busy 0 then sram0_rd_cmd_vld lt 1 end if if sram0O_rd_cmd_vld 1 then 30 memO_idx lt memO_idx 1 end if if memO_idx op_count then read_done lt III 35 end if end if end if end process 40 write values from sramO to sraml meml_wr_be lt X ffff meml_wr_addr lt sraml_alg_offset 9 amp meml_idx amp 0000 meml_wr_cmd_vld lt sraml_wr_cmd_vld write_mem process clk 45 begin if clk event and clk 1 then rising edge 108 ANHANG A QUELLCODES 50 55 60
27. Verbindungsnetzwerk bereit Die Intel Itanium II Doppelkernprozessoren sind mit 1 6 GHz getaktet und haben zwei Multiply Add Einheiten pro Core Damit ergibt sich pro Prozessor eine Flie komma Spitzenleistung von 6 4 GFLOP s 6 4 Milliarden Flie komma Operationen pro Sekunde Eine CPU ist je Kern mit den in Tabelle angegebenen gro en schnellen Caches ausgestattet wodurch bei h ufigem Cache Zugriff eine sehr hohe Anwendungsleistung erzielt werden kann F r die Anwendungsentwicklung ist zu beachten dass es sich um eine IA 64 Prozessorarchitektur handelt die aus drei Befehlen bestehende Instruktionsb ndel mit einer Gr e von 128 Bit verarbeitet und dass z B der Datentyp long prinzipiell 64 Bit verwendet Mit Leistungseinbu en ist die Abarbeitung von IA 32 Anwendungen dennoch m glich Cache Gr e Cache Line Latenz min typ LID 16 KB 64 Bytes 1 1 Takt Lil 16 KB 64 Bytes 1 1 Takt L2D 256 KB 128 Bytes 7 11 Takte L2D 1 MB 128 Bytes 5 10 Takte L3 9 MB 128 Bytes 14 21 Takte Tabelle 3 1 Intel Itanium 2 Montecito Int06 Cache Hierarchie Ein Ausgabe Knoten bestehen aus einer anwendungsspezifischen integrierten Schaltung ASIC mit der Bezeichnung TIO welche zum einen als Cache Koh renzschnittstelle dient und zum anderen g ngi ge E A Schnittstellen wie zum Beispiel PCI X oder PCI Express bereitstellt Die Koh renzschnitt stelle erlaubt es Daten cache koh rent direkt von der E A Schnittstel
28. a_9 a_8 c_8 d_8 amp b_8 c_8 x 1 OxF61E2562 ulnt 32 a LD a_9 lt lt 5 a_9 gt gt 32 5 b_8 5 dritte Runde erste Stuf uint 32 a_l7 a_l6 b_16 c_16 d_16 x 5 OxFFFA3942 uint 32 a_l8 a_17 lt lt 4 a_17 gt gt 32 4 b_16 vierte Runde letzte Stuf 20 Uint 32 b_31 b_30 d_32 c_32 a_32 x 9 OxEB86D391 uint 32 b_32 b_31 lt lt 21 6 31 gt gt 32 21 62323 uint 32 ef out state_in 0 a_32 uint 32 sl_out state_in 1 b_32 25 uint 32 s2_out state_in 2 c_32 uint 32 s3_out state_in 3 d_32 state_out sO_out sl out s2_out s3_out Auflistung 5 4 Mitrion C MD5 Pipeline Mit dem aus der Mitrion C Beschreibung generierten VHDL Design lassen sich durch den Overhead der MVP Verarbeitungseinheiten nur drei Pipelines auf dem Virtex 4 LX200 FPGA umsetzen wobei f r die Beispiel Implementierung auch nur acht Zeichen betrachtet wurden Die Tabelle 5 2 zeigt die Nutzung der FPGA Ressourcen laut den Angaben der Hardware Synthese nach der Plazierung Die vor der Synthese vorgenommene Absch tzung durch Mitrion von 65 Flipflop und 48 Block RAM Nutzung ist beim MDS Algorithmus mit acht Zeichen und drei Pipelines sehr gut und stimmt fast mit den Ergebnissen der Hardware Synthese berein Anzahl der verwendeten Slices 70131 von 89088 79 Anzahl der Slice Flipflops 109008 von 178176 61 Anzahl der 4 Eing
29. arbeiten mit sog In Socket Accelerators wobei einfach ein Mikroprozessor durch einen Pin kompatiblen FPGA er setzt wird Die enge Kopplung von CPU und FPGA f hrt zu einer geringen Latenz zwischen beiden und FPGAs haben zudem noch direkten Zugriff auf die Speicherressourcen des Systems XtremeData s XD2000i und XD2000F sind solche L sungen 21 3 SGI RASC Unter Rekonfigurierbares Anwendungs Spezifisches Computing RASC fasst SGI die Verarbeitung spezieller Anwendungen oder Algorithmen durch rekonfigurierbare Hardware zusammen Im Folgenden wird das RASC System hinsichtlich verwendeter Hardware theoretischen Beschr nkungen zugeh riger Software und ihrer Integration in das Hostsystem SGI Altix 4700 genauer vorgestellt 3 1 SGI Altix 4700 Der Hochleistungsrechner SGI Altix 4700 ist eine Distributed Shared Memory Architektur wobei der Hauptspeicher und damit auch die Speicherkontroller physisch gesehen auf die verschiedenen Knoten verteilt aber logisch als ein gro er gemeinsamer Speicher sichtbar ist Unter der Verwendung spezieller Hardware zur Gew hrleistung der Cache Koh renz ber den verteilten Speicher wird diese System architektur auch als cache coherent Non Uniform Memory Architecture ccNUMA bezeichnet F r den Zugriff der Prozessoren auf den gemeinsamen Hauptspeicher sind spezielle Speicherkontroller sog SHUBs auf den Systemknoten zust ndig Je nachdem ob ein Speicherzugriff auf lokale oder e
30. auf ein fache Glue Logic beschr nkt waren sind sie heute der Umsetzung von sog Ein Chip Systemen SoCs gewachsen FPGAs mit ber einer Million Gatter sind derzeit keine Besonderheit mehr und erm glichen v llig neue Anwendungen Zus tzlich integrieren sie bliche F higkeiten von anwendungsspezifischen Standardprodukten ASSP wie z B PCI Express USB usw Damit stellt die programmierbare Logik einen wesentlichen Beitrag zur Technologie der Zukunft dar In diesem Kapitel werden zun chst einige Beispiele f r die verschiedensten Anwendungsgebiete von FPGAs gegeben Anschlie end wird deren grundlegende Architektur beschrieben und auf die Vorteile und die Schwachpunkte bei der Verwendung programmierbarer Logik eingegangen Die in dieser Arbeit zum Einsatz kommenden Virtex 4 FPGAs und ihre Besonderheiten werden ebenso n her betrachtet Auf die Programmierm glichkeiten von FPGAs wird in Kapitel 4 am Beispiel der RASC Plattform genauer eingegangen und inwiefern vorgefertigte Designs IP Cores und h here parallele Programmiersprachen siehe z B die Nutzbarkeit von FPGAs verbessern und Anwendungsportierung in Hardware er leichtern Schlie lich wird der Einsatz von FPGAs als Hardware Beschleuniger im Hochleistungsrech nen erl utert 2 1 Typische Einsatzgebiete FPGAs haben sich bis heute besonders im Bereich der eingebetteten Systeme etabliert Durch ihre Re konfigurierbarkeit bieten sie weitreichende Einsatzm glichkeiten in
31. cke zwischen Host und lokalem SRAM transportiert werden Der Speicher Controller bedient dann das Interface zum on board SRAM und verkn pft es mit dem Algorithmus und den DMA Bl cken Der Memory Mapped Register MMR Block stellt die Register bereit welche dem Algorithmus Designer zur Verf gung stehen sollen Zu diesen Registern geh ren die Debug Register und die Algorithm Defi ned Registers Beide Registertypen sind 64 Bit breit und k nnen in einer maximalen Anzahl von je 64 Registern verwendet werden Das Request Gate erstellt das SSP Paket f r Lese und Schreibanfragen des FPGA zum Hauptspeicher Der Algorithm Block beinhaltet den vom Benutzer geschriebenen anwen dungsspezifischen Code der den eigentlichen Algorithmus implementiert 26 3 SGIRASC Nicht in der Abbildung dargestellt sind der TNUM tracker welcher Transaktionsnummern innerhalb des FPGA handhabt und der Interrupt Generator welcher Paketdaten erzeugt um den Host im Falle eines direkten Speicherzugriffes DMA zu unterbrechen z B durch das alg_done Flag des Algorithmen Blocks Die von den Core Services ben tigte FPGA Fl che l sst sich minimieren indem nicht alle Komponenten genutzt werden Es ist z B m glich den Memory Controller wegzulassen wenn der Algorithmus den SRAM nicht ben tigt blicherweise werden FPGAs ber eine UART oder eine PCI Steckkarte angesteuert Bei einer UART kann eine Datenrate von bis zu 115200 Bits pro Sekunde 14 4 kByte s er
32. die das Programm auch ben tigt Die zwei wesentlichen Merkmale von FPGAs im Vergleich zu Mikroprozessoren sind die niedrige Takt frequenz von nur wenigen hundert Megahertz MHz und die gro e Anzahl von Logikelementen wel che parallel arbeiten k nnen Damit muss der MVP die M glichkeit der massiven Parallelverarbeitung nutzen um die Ressourcenausnutzung des FPGAs zu maximieren Prozessoren mit einer von Neumann Architektur sind bereits als IP Cores f r FPGAs vorhanden MIPS PowerPC IP Cores leiden aber unter der geringen Taktfrequenz der FPGAs und k nnen durch ihren sequentiellen Datenstrom auch nicht von der Vielzahl von parallel arbeitenden Bausteinen auf dem FPGA profitieren Dementsprechend muss der MVP folgenden Anforderungen gen gen um eine effiziente Abarbeitung zu gew hrleisten e Parallelit t des Befehlssatzes Befehle k nnen gleichzeitig ausgef hrt werden e Parallelit t auf Schleifenebene mehrere Schleifendurchl ufe k nnen parallel ausgef hrt werden e Maximale Nutzung der FPGA Ressourcen durch Anpassung des Prozessors an den auszuf hrenden Algorithmus Wenn beispielsweise die Bedingung einer if Anweisung erst zur Laufzeit ausgewertet werden kann muss der MVP beide Programmzweige in Form von PEs implementieren Dadurch ist es sinnvoll bereits w h 40 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM rend der Auswertung der Bedingung beide Zweige gleichzeitig auszuf hren und dann das Ergebnis des ents
33. empfangen liegt die Latenz zwischen dem Eintreffen dieser bei ca 180 Takten 0 9us Die Kontrolle ob aktuelle Daten vorliegen erfordert mindestens einen zus tzlichen Lesevorgang durch den Host was den effektiven Datendurchsatz verrin gert Es m ssen mindestens soviele 8 Byte Pakete bertragen werden wie Eingangs bzw Ausgangsregister genutzt werden Wird ein ADR bei der bertragung von nur acht Byte 64 Bit pro Durchlauf verwen det liegt der Datendurchsatz bei 0 67 MByte s Die Nutzung von 16 ADRs und 512 bertragenen Werten 4096 Bytes pro Durchlauf erh ht den Durchsatz auf bis zu 4 07 MByte s ohne Synchronisation beim Auslesen der Register Die zus tzliche Abfrage ob Registerwerte bereitstehen verringert den Daten durchsatz je nach Anzahl der verwendeten ADRs um 0 2 bis 0 6 MByte s Die Verwendung von Direct I O oder Buffered I O hat bei diesen geringen Datenmengen jedoch keinen erkennbaren Einfluss auf Durchsatz oder Latenz 5 4 MD5 Brute Force Als Repr sentant f r Kryptographische Verfahren wird in dieser Arbeit die Hashfunktion MD5 Message Digest Algorithm 5 verwendet Sie erzeugt aus einem beliebig langen Klartext einen 128 Bit Hashwert und wurde 1991 von Ronald Linn Rivest entwickelt Als Internet Standard RFC 1321 vgl Riv92 wurde MDS in einer Vielzahl von Anwendungen zur Verschl sselung und wird immer noch zur Integri t tspr fung von Dateien verwendet Bei letzterem wird die aktuell errechnete MD5 Summ
34. etc ben tigt weniger Fl che auf dem Chip und kann schneller getaktet werden als logisch gleichartige Schaltungen unter der Verwendung von CLBs Virtex 4 FPGAs bieten mit dem Dynamic Reconfiguration Port DRP eine einfache M glichkeit hnlich dem Block RAM Interface die Funktionalit t einer Anwendung w hrend der Laufzeit zu ndern Dieser ist in zwei Arten von Funktionsbl cken integriert DCMs und MGTs Detailliertere Informationen zu allen FPGAs der Virtex 4 Serie k nnen der Produktspezifikation Xi107 entnommen werden Auf die Virtex 4 Architektur und integrierte Funktionsbl cken wie Block RAM DCMs und E A Ressourcen wird im Benutzerhandbuch eingegangen w hrend die Konfigurationsm glichkeiten Varianten den Bitstream in den FPGA zu laden zur Verf gung stehende Schnittstellen Aufbau des Bitstreams beschreibt 2 5 Flie kommaverarbeitungsleistung Im Hochleistungsrechnen engl High Performance Computing HPC ist die Verarbeitungsleistung von Gleitkommazahlen ein wesentliches Kriterium um die Leistungsf higkeit eines Systems zu bewerten Als Ma einheit werden Flie kommaoperationen pro Sekunde FLOP s verwendet In diesem Abschnitt wird Gleitkomma oder Flie komma mit der aus dem Englischen kommenden Bezeichnung FP floating point abgek rzt Auch wenn die St rke von FPGAs in anderen Bereichen liegt soll die zu erwartende FP Verarbeitungs leistung n her untersucht werden Als Referenz dienen wie blich Mikro
35. gelesen und beschrieben werden Von SGI sind die ADRs prim r zur bergabe von Parametern vorgesehen sie k nnen aber auch f r eine echte Ping Pong Kommunikation verwendet werden Der Algorithmus erh hlt f r jeden vom Host vor genommenen Schreib oder Lesevorgang eines ADRs eine Signalisierung updated oder polled womit ihm der Zustand der Register bekannt ist Auf der Seite der Host Applikation fehlt eine entsprechen de Synchronisation welche eine Ver nderung eines ADRs signalisiert und muss durch Polling unter Verwendung eines Debug Registers oder ADRs vom Nutzer selber erg nzt werden 3 4 Software Bisher wurde haupts chlich auf die RASC Hardware eingegangen Um diese aus einer Hochsprache ansteuern zu k nnen ist jedoch noch Funktionalit t auf weiteren Ebenen notwendig Abbildung zeigt eine bersicht ber die Abstraktionsebenen von RASC Mit dem Device Manager wird die Or ganisation der Algorithmen vorgenommen welche bei Bedarf in die vorhandenen FPGAs geladen wer 3 4 SOFTWARE 29 Device Bibliotheken Algorithmus Schicht Ger te COP Schicht DE Bibliotheken Kernel Download Ger tetreiber Treiber Algorithmus Konfigurations FPGA FPGA Abbildung 3 5 SGI RASC Abstraktionsebenen vgl SGIOS Betriebssystem Hardware den Fiir den Anwendungsentwickler stehen neben Bibliotheksfunktionen zur Kommunikation mit den FPGAs auch hilfreiche Werkzeuge wie ein erweiterter GNU Projek
36. kann ebenso f r Streaming verwendet werden wie das in Abschnitt 3 3 2 beschriebene direkte Streaming Betrachtet man Abbildung 3 3 genauer stellt man fest dass die Speicheransteuerung mit vollen 200 MHz laufen muss um die von SGI angegebenen maximalen Datenraten zu erreichen 3 3 CORE SERVICES 27 Hierzu wird davon ausgegangen dass von einer 36 Bit breiten Leitung zu bzw von einer SRAM Bank nur 32 Bit verwendet werden 4 Bit f r Datenintegrit t Bei einem QDR I SRAM k nnen gleichzeitig zwei W rter gelesen und geschrieben werden wodurch man auf eine Datenrate von 1 6 GB s je SRAM Bank und Richtung kommt Durchsatz FPGA Taktfrequenz W rter Wortbreite 200 MHz 2 32 Bit 1 6 GB s Da sowohl der Algorithmus als auch die Core Services Zugriff auf den SRAM haben und parallel aus gef hrt werden muss zur Vermeidung einer Zugriffskollision eine Arbitrierung vorgenommen werden Falls solche Zugriffskonflikte auftreten k nnen m ssen sie auch in der Implementierung des Algorith mus behandelt werden Werden die SRAM Zugriffe so eingeplant dass keine Zugriffkonflikte stattfin den k nnen muss keine Arbitrierungsbehandlung implementiert werden Spezielle Direktiven und sog Extractor Anweisungen k nnen dazu genutzt werden den Zugriff auf die SRAM Ports sowohl f r die Core Services als auch f r den Algorithmus einzuschr nken und damit Zugriffkonflikte zu vermeiden Werden SRAM Ports so konfiguriert dass nur der Alg
37. mit 65 Watt Verlustleistung Im Zeitraum von 200 Tagen 4800 Stunden verbraucht damit ein FPGA 120kW Dies entspricht Ener giekosten von 18 und einem CO gt 3 Aussto von 48 kg Wird ein Beschleunigungsfaktor 20 f r die FPGA Implementierung angenommen m ssten anstelle dessen 20 Referenz CPUs arbeiten um die glei che Rechenleistung zu erbringen Dabei w rden Energiekosten von 936 anfallen und 2496 kg CO ausgesto en Im positiven Fall f r Mitrion kann der zu beschleunigende Algorithmus in Mitrion C effizient beschrie ben werden ben tigt dann im Vergleich zur VHDL Implementierung ein Sechstel der Entwicklungszeit und bringt ein Viertel der Performance In ung nstigen F llen kann mit Mitrion jedoch kein Geschwin dikeitsgewinn erreicht werden Ein Grund f r die vergleichsweise geringen Geschwindigkeitsgewinne ist die langsamere Taktung des Mitrion Designs ber die Taktverwaltung der Virtex 4 FPGAs DCMs und FIFOs mit unterschiedlichem Lese und Schreibtakt w re auch eine feinere Einstellung der Taktung des Mitrion Algorithmus denkbar und k nnte zumindest als experimentelle Funktion angeboten werden 6 4 VERBESSERUNGSANS TZE DER RASC PLATTFORM 93 Weitere Gr nde ergeben sich aus dem Mangel an Beschreibungsm glichkeiten vgl Abschnitte und 5 5 3 Mitrion erm glicht mit ca drei Wochen Einarbeitungszeit und einer Woche Entwicklungszeit einen schnellen Einstieg und erreichte in den Messungen im besten Fall einen Ge
38. others gt 0 debug 3 lt others gt 0 35 debug 4 lt others gt 0 ctr_delay lt others gt 0 else ctr_delay lt ctr_delay 1 if adr_updated 0 then 40 debug 1 59 downto 0 lt debug 1 47 downto 0 amp ctr_delay debug 2 59 downto 0 lt debug 2 47 downto 0 amp debug 1 59 downto 48 debug 3 59 downto 0 lt debug 3 47 downto 0 amp debug 2 59 downto 48 debug 4 59 downto 0 lt debug 4 47 downto 0 amp debug 3 59 downto 48 end if 45 end if end if end process manage rasc output 50 proc_rasc process clk begin if clk event and clk 1 then rising edge if rst 1 then synchronous reset rasc_out_full lt 0 55 ctr_rout lt others gt 0 ctr_polled lt others gt 0 debug 5 lt others gt 0 A3 MEMORY MAPPED REGISTERS 115 debug 6 lt others gt 0 60 debug 7 lt others gt 0 else if rasc_out_full 1 then register read done by host if adr_polled 0 then 65 ctr_polled lt ctr_polled 1 get polling latency debug 5 59 downto 0 lt debug 5 47 downto 0 amp ctr_delay debug 6 59 downto 0 lt debug 6 47 downto 0 amp debug 5 59 downto 48 debug 7 59 downto 0 lt debug 7 47 downto 0 amp debug 6 59 downto 48 70 end if end if user defined nu
39. portierbar 97 zwischen FPGA Systemen die Kommunikation mit Nutzeranwendungen oder Bibliotheken erm gli chen Derzeit muss in Frage gestellt werden ob mit der Open Computing Language OpenCL welche als gemeinsame Programmiersprache f r Grafikbeschleuniger und DSPs entwickelt wird auch FPGAs programmiert werden k nnen Der hier vorgestellte Hochsprachenansatz bietet zudem auch nicht die Geschwindigkeitsgewinne die von einem Hardware Beschleuniger erwartet werden Letztendlich bleibt abzuwarten inwiefern sich FPGAs im HPC etablieren k nnen Hierf r ist auch eine Sensibilisierung der Nutzer notwendig da die Portierung von Anwendungen immer einen Entwicklungs aufwand mit sich zieht 98 7 ZUSAMMENFASSUNG UND AUSBLICK 99 Abbildungsverzeichnis We ee ee e ee eeh 9 2 2 FPGA Logikblock und Schaltmatrix vgl WikO9 e 10 2 3 Paritatsbit f r 32 Bit Wert 4 Eingangs LUT links 6 Eingangs LUT rechts 10 2 4 Konfigurierbarer Logikblock CLB der Virtex 4 FPGAs vgl Xil08cJ 14 2 5 Stark vereinfachter Virtex 4 Slice ohne Carry und Speicher Logik vgl T4 ts eae ot Be EEGEN 20 Jee S44 E weber BM a EN e 2 22 3 2 RC100 Blade vgl ISGIO8D NIR EEN EEN ana aka 24 3 3 RASC FPGA Modul vgl SGIOSN 2 24 3 4 RASC Core Services vgl SGIO8P 2 aa 25 3 5 SGI RASC Abstraktionsebenen vgl SGIO8 2 20 02 ee ee 29 4 1 Entwicklungszyklus Mitrion SDK auf SGI RASC vgl M
40. process signal if pipe has found the hash proc_equal process clk begin 30 if clk event and clk LI then rising edge if eghash 1 1 then Vout lt 1 else Vout lt 0 35 end if end if end process Auflistung A 10 MD5 Klartextriickgewinnung in VHDL 0 the range of ASCII characters to be processed constant firstchar positive conv_integer conv_unsigned character POS 8 constant lastchar positive conv_integer conv_unsigned character POS 8 5 std_logic_vectors for first and last ASCII character constant vfirstchar std_logic_vector 7 downto 0 CONV_STD_LOGIC_VECTOR firstchar 8 constant vlastchar std_logic_vector 7 downto 0 CONV_STD_LOGIC_VECTOR lastchar 8 10 number of ASCII characters to be processed constant characters positive lastchar firstchar l the range of ASCII characters for the first plaintext character has to be a multiple of PIPES constant pipes_norm positive getNormPipes firstchar lastchar PIPES constant pipes_ov natural pipes pipes_norm 15 constant realchars positive characters pipes_ov constant vrlastchar std_logic_vector 7 downto 0 CONV_STD_LOGIC_VECTOR lastchar pipes_ov 8 first char has to be reduced by constant chardiff0 std_logic_vector 7 downto 0 120 20 25 30 35 40 45 55 60 65 70 75
41. und FOREACH Strukturen auf der innersten Schleifenebene in Mitrion C zu beschreiben MD5 Brute Force kann ein Geschwindigkeitsgewinn gegentiber einer auf einem CPU laufenden hoch optimierten Software von bis 3 3 gemessen werden Die VHDL Umsetzung ist jedoch noch einmal um einen Faktor 4 1 schneller als Mitrion L sst sich die Anwendung nicht gut in Mitrion C beschreiben Damenproblem so ist mitunter kein Geschwindigkeitsgewinn gegentiber CPUs zu verzeichnen wohingegen die VHDL Umsetzung mit einem Beschleunigungsfaktor von rund 23 ge messen werden konnte Wie beim Hardware Entwurf muss auch bei der Mitrion C Programmierung auf m glichst flache Strukturen geringe Verschachtelung von Bedingungen und Schleifen geachtet werden um eine gute Performance zu erreichen Auch die Ergebnisse der Durchsatzmessungen liegen mit Mitrion hinter den vergleichbaren VHDL Implementierungen was zumindest bei der Verwendung von SRAM auf die geringere Taktung des MVP zur ckzuf hren ist Der maximal erreichbare Direct Streaming Durchsatz der mit 100 MHz getakteten VHDL Implementierung ist dennoch deutlich schneller als die Mitrion Variante weshalb hier von einem Fehler im MVP Design ausgegangen werden kann Abbildung 6 2 zeigt noch einmal die f r Direct I O gemessenen Werte f r die SRAM Kommunikation und das Direct Streaming Der SRAM Kontroller der Core Services scheint derzeit noch ein Flaschenhals zu sein zumal nach den theoretischen Angaben 3 2 GByt
42. werden muss Es k nnen noch viele andere Fehler vorkommen welche allerdings in ihrer Gesamtheit hier nicht aufgez hlt werden sollen Festzuhalten ist jedoch dass mit VHDL mehr Fehler dieser Art entstehen k nnen da auf einer niedrigeren Abstraktionsebene als mit Mitrion C programmiert wird und die Be schreibung des Kontrollflusses aufw ndiger ist Zudem werden bei Mitrion C z B durch Unterscheidung von FOREACH und FOR Schleife sowie das Single Assignment Prinzip und komplett ausformulierte Bedingungszweige Fehler fr hzeitig zur bersetzungszeit erkannt Eine inkorrekte Implementierung und damit ein semantischer oder logischer Fehler kann mit beiden Sprachen anhand einer Simulation bereits aufgedeckt werden Die Mitrion Simulation vgl Abschnitt ist mit der Verwendung von Watch Anweisungen einer Hochsprachenfehlersuche sehr hnlich Beim Aufruf einer solchen Anweisung wird der Inhalt der beobachteten Variable auf der Kommando zeile ausgegeben Zudem kann mit dem grafischen Simulator die Struktur des Programmes angesehen werden wodurch das Aufdecken funktionaler Fehler auch optisch m glich ist Die Fehlersuche in einem 6 2 VERGLEICH VON MITRION C UND VHDL RASC PROGRAMMIERUNG 89 VHDL Entwurf ist aufw ndiger als bei Mitrion C Programmen und wird blicherweise vor der Synthe se mit einem HDL Simulator vgl Abschnitt 4 2 2 vorgenommen Dabei k nnen die an den Signalen und Ports der untersuchten Komponenten und Unterkomponent
43. zugeh rigen Identifikator angespro chen werden Zu jedem auf den RC100 Blades ausf hrbaren Algorithmus geh ren ein Binary und zwei Konfigurationsdateien f r die Core Services und die davon verwendeten Schnittstellen Der Device Manager bernimmt die Verwaltung der Algorithmen die den FPGAs zur Verf gung stehen Er erm glicht das Anzeigen der im System vorhandenen FPGAs das Auflisten der zur Verf gung ste henden Algorithmen und das Hinzuf gen ndern und Entfernen von Algorithmen Als Frontend wird das Kommandozeilenprogramm devmgr verwendet 3 4 3 GNU Project Debugger GDB Eine M glichkeit der Fehlersuche zur Laufzeit einer RASC Anwendung bietet SGI mit der Erweiterung des GDB an Folgende RASC spezifische Kommandos stehen zus tzlich zur Verf gung fpgaactive on off set fpga fpganum N info fpgaregisters regname alias info fr info fpga fpgastep fpgacont fpgatrace on off Mit diesen Kommandos ist es m glich in jedem Takt den Inhalt der Debug und Algorithm Defined Register auszulesen und sich generelle Informationen zum auf dem FPGA laufenden Algorithmus an zeigen zu lassen Eine genauere Beschreibung der Kommandos kann in SGIO8 nachgelesen werden Eine der wesentlichen Beschr nkungen die das Debugging ber den GDB mit sich bringt betrifft das Auslesen der FPGA Register Nur vom Hardware Programmierer nach au en propagierte Register k n nen ausgelesen werden Damit muss s
44. 0000 gt gt 48 unsigned int debug i 0000000 gt gt 36 unsigned int debug i gt gt 24 unsigned int debug i 2 printf d d i platency i finish the algorithm amp OxFFFO000000000 gt gt 36 debug i amp OxFFFO00000 gt gt 24 debug i amp OXFFFOO0 gt gt 12 debug i 5 amp 0 amp OXFFF gt gt 0 debug it 5 amp 0 118 ANHANG A QUELLCODES AA MD5 Brute Force Auflistung A 8 VHDL MDS5 Pipeline Ausschnitt 0 md5 pipeline logic SE EE ee uam EE ramout 0 lt Dinx 0 lst stage plaintext pipeline process clk begin if clk event and clk 1 then rising edge set 2nd stage plaintext input value Dinxl lt Dinx 1 ramout 1 lt Dinxl 10 stages 3 to 15 2nd md5 block stages 16 to 32 FOR i IN 4 TO 7 LOOP stages a4 to a7 15 tmp i 4 lt md5_logicl2 Dina i 6 Dinc i 2 Dind i 4 Dinb i 0 ramout 1 4 Dina itl 0 lt md5_shift2 tmp i 4 shifts 4 Dinb i 1 Dinhex ix4 FOR s IN 0 TO 5 LOOP Dina i 1l stl lt Dina itl s END LOOP 20 stages d4 to d7 tmp i 4 1 lt md5_logicl2 Dind i 6 Dinb i 2 Dinc i 4 Dina i l1 0 ramout i 4 1 Dind i 1 0 lt md5_shift2 tmp i 4 1 shifts 5 Dina i 1l 1 Dinhex i 4 1 FOR s IN 0 TO 5 LOOP 25 Dind i 1 s 1 lt Dind itl s END LOOP stages c4 to c7 tmp i 4 2
45. 8 Int06 KC07 M 08 Mit08a MitO8b PNS PNSO9 Pre05 Riv92 SGI08 ARBEITER Stefan DEEG Matthias Bunte Rechenknechte Grafikkarten beschleunigen Passwort Cracker In c t 2009 Heft 6 2009 DEVINE Christophe MD5 Source Code Webseite Oktober 2007 org code source md5 HOCHBERGER Christian Hardware Synthese fiir eingebettete Systeme Vorlesungsfolien 2008 http www mr inf tu dresden de ILSCHE Thomas JUCKELAND Guido First experiences with SGIRASC at TU Dresden Center for Information Services and High Performance Computing TU Dresden Germany 2008 Forschungsbericht INTEL Dual Core Update to the Intel Itanium 2 Processor Referenz Manual For Softare Development and Optimization Revision 0 9 Januar 2006 KREINDLER Danny CORPORATION Altera How to implement double precision floating point on FPGAs White Paper Oktober 2007 M DER Andreas VHDL Kompakt Universit t Hamburg MIN Fakult t Department In formatik Oktober 2008 MITRIONICS Low Power Hybrid Computing for Efficient Software Accelera tion White Paper 2008 http www mitrion com document Hybrid Computing Whitepaper pdf MITRIONICS Mitrion User s Guide 2008 http forum mitrionics com uploads Mitrion_Users_Guide pdf PREUSSER Thomas B N GEL Bernd SPALLEK Rainer G Queens TUD Projekt queens inf tu dresden de PREUSSER Thomas B N GEL
46. A 9 Die Klartextr ckgewinnung verwendet die Pipeline Tiefe die aktuellen Z hler des Klartextgenerators und die Nummer der Pipeline welche den gesuchten Hash erzeugt hat Pro reproduziertem Zeichen wird ein Takt ben tigt Ein entsprechender Quellcodeausschnitt ist in gelistet Das Design nutzt in der aktuellen Variante noch die Datentypen st d_logicund std_logic_vector welche von den meisten Synthese Tools auch verarbeitet werden k nnen An dieser Stelle w rde sich einen Anpassung mit dem Paket numeric std all anbieten Die Nutzung von selbst geschriebenen Pake ten und darin enthalten Funktionen und Prozeduren erm glicht eine sehr kompakte und bersichtliche Beschreibung der Hardware Die Schnittstelle zu den Core Services kann einfach gehalten werden da nur die Eingabe des Hashes 128 Bit und die Ausgabe des Klartextes maximal 56 ASCII Zeichen 8 Bit 448 Bit Dementspre chend werden insgesamt neun ADRs je 64 Bit f r die Daten bertragung verwendet Der Algorithmus beendet sich wenn der letzte Z hler bergelaufen ist kein Klartext gefunden wurde oder der erste 68 5 FALLBEISPIELE bereinstimmende Hash mit zugeh rigem Klartext berechnet wurde ber ein Debug Register kann das Host Programm ermitteln in welchem Zustand fertig rechnend Klartext gefunden sich der Algorith mus befindet Der C Quellcode zur Kommunikation und Performance Messung ist in gelistet Die derzeitige Hardware Synthese kann acht MD5 P
47. Bernd SPALLEK Rainer G Putting Queens in Carry Chains Institut f r Technische Informatik TU Dresden Germany 2009 Forschungs bericht ftp ftp inf tu dresden de pub berichte tud09 03 pdf ISSN 1430 211X PREUSSER Thomas B VHDL Ein berblick Vorlesungsfolien Juni 2005 RIVEST Ronald L The MD5 Message Digest Algorithm Webseite April 1992 http tools ietf org html rfc1321 SGI Reconfigurable Application Specific Computing User s Guide 2008 106 Literaturverzeichnis Smi96 Som02 SSWW08 Str07 Wag08 Wan98 Wik09 WY05 Xil Xi107 Xil08a Xil08b Xil08c Xil09a Xil09b SMITH Douglas J VHDL amp Verilog Compared amp Contrasted Plus Modeled Example Written in VHDL Verilog and C VeriBest Incorporated 1996 Forschungsbericht SOMERS Jeff The N Queens Problem a study in optimization 2002 jJsomers com nqueen_demo nqueens html STRENSKI Dave SIMKINS Jim WALKE Richard WITTIG Ralph Revaluating FPGAs for 64 bit Floating Point Calculations White Paper Mai 2008 STRENSKI Dave FPGA Floating Point Performance a pencil and paper evaluation White Paper Januar 2007 WAGNER Michael Grafikprozessoren als Hardwarebeschleuniger Vergleich der Ans tze von NVIDIA und AMD zur Nutzung der Ressourcen aktueller Grafikprozessoren fiir allgei meine Anwendungen Zentrum fiir Informationsdienste und Hochleist
48. HDL RASC Programmierung 6 2 1 Entwicklungszeiten ooa ENG ee ee ES ee ae EE 6 2 3 Fehleranf lligkeit und Debugging M glichkeiten 2 2 2 6 2 4 Performance 2 38 2 48 ha ea Kae be ee EEE Do 6 3 Kosten Nutzen Abschatzung und ban 6 4 Verbesserungsans tze der RASC Plattform N Zusammenfassung und Ausblick gt bbildungsverzeichnis Tabellenverzeichnis Auflistungsverzeichnis Literaturverzeichnis IA_Quellcodes EE SE e e e Ee e ee ERT BEE A D Damenproblem s s 2 2 4 6 oo doe Be die Bars EE ae EE ei en e da 81 81 82 83 85 88 89 91 93 95 99 101 103 Abk rzungsverzeichnis ADR API ASCH ASIC ASSP BLAS CLB COP CPLD CPU DCM DGEMM DLL DIMM DMA DSP EEPROM FF FIFO FLOP s FPGA FSM GDB GEMM GPGPU GPU GPRS GUI HDL HPC I O IP LUT MAC MD5 MMR MVP NAS PCI PLD RAM RASC SAN Algorithm Defined Register Application Programming Interface American Standard Code for Information Interchange Application Specific Integrated Circuit Application Specific Standard Products Basic Linear Algebra Subprograms Configurable Logic Block Koprozessor Complex Programmable Logic Device Central Processing Unit Digital Clock Manager Double Precision General Matrix Multiply Delay Locked Loop Dual Inline Memory Module Direct Memory Access Digitaler Signalprozessor Electrically Erasable Programmable Read Only Memory Fl
49. LIB_FAIL fprintf stderr open failed at d d n LINE__ cop_desc 5 rasclib_perror open res return 1 res rasclib_cop_reg_write cop_desc inc_val amp inc 1 RASCLIB_IMMED_CMD A 2 DIRECT STREAMING 113 10 if res RASCLIB_SUCCESS fprintf stderr reg write of inc_val failed at d d n __LINE__ res rasclib_perror reg write of inc_val res return 1 starttime2 gtod send input stream data res rasclib_cop_send cop_desc strm_in in arguments num_bytes if res RASCLIB_ SUCCESS 20 fprintf stderr send failed at d d n __LINE__ res rasclib_perror send res return 1 25 Signal input stream complete rasclib_cop_send_complete cop_desc strm_in if res RASCLIB_SUCCESS fprintf stderr send_complete failed at d d n __LINE__ res rasclib_perror send res 30 return 1 rasclib_cop_go cop_desc start fpga algorithm 35 receive output stream data res rasclib_cop_receive cop_desc strm_out out arguments num_bytes if res RASCLIB_SUCCESS fprintf stderr recv failed at d d n __LINE__ res rasclib_perror receive res 40 return 1 rasclib_cop_commit cop_desc NULL rasclib_cop_wait cop_desc 45 endtime gtod rasclib_cop_close cop_desc rasclib_resource_return arguments algID 1 50 rasclib_resource_release 1 resrv_name if arguments cycles gt 1
50. Latenz der Kommunikation zwischen Mikroprozessor und FPGA mit unter starken Einfluss auf die Performance der Anwendung hat wird sie f r diese theoretische Betrach tung vernachl ssigt Die maximal von einem Mikroprozessor erreichbaren FLOP s errechnen sich aus den pro Takt und Kern durchf hrbaren FP Operationen multipliziert mit der Taktfrequenz und der An zahl der Kerne auf dem Prozessor Damit kann ein Vierkern Opteron Prozessor mit 2 5 GHz theore tisch 40 GFLOP s 4 Operationen Takt 4 Kerne 2 5 GHz bei doppelter Genauigkeit 64 Bit und 80 GFLOP s bei einfacher Genauigkeit 32 Bit erreichen Ein FPGA besitzt weder FP Addierer noch FP Multiplizierer sondern generische Logik welche vom Nutzer konfiguriert werden kann Um also eine vergleichbare maximale 64 Bit FP Verarbeitungsleistung zu bestimmen muss herausgefunden werden wieviele Addierer und Multiplizierer bei welcher Taktfre quenz auf dem FPGA implementierbar sind Die Spitzenleistung berechnet sich dann aus der durch den FPGA zur Verf gung stehenden Logik dividiert durch die von einer FP Verarbeitungseinheiten ben tig ten Logik multipliziert mit der maximal erreichbaren Taktfrequenz des Designs Berechnungsgrundlagen FPGA Als Basis der folgenden Berechnungen dienen vier Dokumente von Xilinx die Kenndaten bersich ten der Virtex 4 Virtex 5 und Virtex 6 Familie Xil07 X1l09a Xil09b und die Spezifikation des Xilinx Floating Point Core X1l08a Aus le
51. MHz 200MHz zu verwendende DMA Streams siehe 3 3 2 SRAM Konfiguration siehe 3 3 1 Anzahl und Konfiguration der Algorithm Defined Register siehe 3 3 3 Anzahl der Debug Register Auswahl des Synthese Tools Multiplikator und Teiler der Supplemental Algorithm Clock Entsprechend der Auswahl erstellt das Tool Konfigurationsdateien Verilog Wrapper Module um das Design des Algorithmus in die Core Services zu integrieren und ein Makefile um den Bitstream auto matisiert erzeugen zu k nnen Der Name des Algorithmus wird zur Benennung der Verzeichnisse und Design Dateien verwendet aus der Taktfrequenz des Algorithmus abgeleitete Taktfrequenz 33 4 Programmierm glichkeiten der SGI RASC Plattform In diesem Kapitel werden zwei M glichkeiten zur Programmierung der SGI RASC Plattform vorge stellt Dies ist zum einen die Mitrion Entwicklungsumgebung Mitrion SDK mit Mitrion C als parallele Hochsprache und zum anderen die Hardwarebeschreibungssprache VHDL als eine herk mmliche Me thode des Hardware Entwurfs Die Alternative zu VHDL ist Verilog in der auch Teile der RASC Core Services implementiert sind Die Entscheidung f r die Verwendung von VHDL und entsprechende Gr n de sind in Abschnitt 4 2 genauer erl utert Desweiteren lag das gr te Fallbeispiel das Damenproblem siehe Abschnitt 5 5 bereits in VHDL Code vor und ich beherrsche die Programmierung mit VHDL besser als mit Verilog Die Software Entwicklung sol
52. Messergebnisse eingegangen wird Der wesentliche Vorteil gegen ber den beiden bereits vorgestellten Kommunikationsvarianten liegt im wechselseitigen Datenaustausch zwischen Host und FPGA ohne dass das Taktsignal des Algorithmus unterbrochen wird Damit ist es dem Algorithmus w hrend seiner Ausf hrung m glich auf sich ver n dernde Eingaben zu reagieren Auch der Host kann auf die Ausgaben des Algorithmus reagieren ohne dessen Ausf hrung beenden zu m ssen Beim Direct Streaming und bei der SRAM Kommunikation hingegen werden einmalig Daten geschickt und nach dem Start Signal auf das Empfangen der Daten gewartet Anschlie end kann der Algorithmus mit anderen Daten neu gestartet werden Die Kommuni kation mit MMRs ist somit f r den Langzeitbetrieb geeignet 5 3 1 Implementierung ber die RASC Core Services k nnen dem Algorithmus Block bis zu 64 sog Algorithm Defined Re gisters ADRs als Modul Eing nge zur Verf gung gestellt werden Hinzu kommen drei Kontrollsignale pro Register um dieses zu beschreiben oder aber zu erfahren ob es vom Host beschrieben oder gelesen wurde Bis zu 64 Debug Register k nnen zus tzlich genutzt werden um w hrend der Ausf hrung des Algorithmus auf dem FPGA eine Fehlersuche zu erm glichen oder einfach nur Daten auszugeben Die Beispiel Implementierung vgl VHDL Quellcodeauschnitt A 6 stellt f r Dateneingang und Daten ausgang je 16 ADRs bereit Um testen zu k nnen wie sich der Durchsatz mit den v
53. PGAs ausnutzen zu k nnen Trotz dieser hardwarenahen Anforderungen ist im Vergleich zu Hardware beschreibungssprachen bei der Programmierung von Mitrion C kaum Wissen ber die zugrundeliegende Hardware notwendig Auch das Verbindungsnetzwerk hat in gro en Rechensystemen starken Einfluss auf die Performance von Algorithmen Wenn zu dessen Ausf hrung Daten ber das Netzwerk bertragen werden m ssen k nnen die Bandbreite und die Latenz begrenzende Faktoren sein sofern der Algorithmus entsprechende Anforderungen an diese besitzt 4 1 Mitrion SDK von Mitrionics Das Mitrion Software Development Kit SDK von Mitrionics ist eine Entwicklungsumgebung welche um die parallele Programmiersprache Mitrion C aufgebaut ist und dient der Umsetzung hochparalleler Algorithmen auf programmierbaren Hardware Plattformen mit FPGAs Derzeit werden sechs hybride Rechnersysteme von der Mitrion Software Plattform unterst tzt Neben Mitrion C Bibliotheken bein Hardware Plattformen mit Standardprozessoren und Hardware Beschleunigern 4 1 MITRION SDK VON MITRIONICS 35 haltet das SDK noch die Mitrion Virtual Processor MVP Architektur einen Mitrion C Compiler und einen Simulator Die Anwendungsbereiche befinden sich in der Bioinformatik der Gen Sequenzierung der Textsuche und der Bildverarbeitung Unabh ngig davon k nnen auch beliebige parallele Algorith men implementiert werden Das Mitrion Benutzerhandbuch stellt die Mitrion Plattform
54. TECHNISCHE UNIVERSIT T DRESDEN FAKULT T INFORMATIK INSTITUT F R TECHNISCHE INFORMATIK PROFESSUR F R RECHNERARCHITEKTUR PROF DR WOLFGANG E NAGEL Diplomarbeit zur Erlangung des akademischen Grades Diplomingenieur f r Informationssystemtechnik SGI RASC Evaluierung einer Programmierplattform zum Einsatz von FPGAs als Hardware Beschleuniger im Hochleistungsrechnen Robert Dietrich Geboren am 10 August 1983 in Dresden Betreuer Guido Juckeland Thomas B Preu er Dresden 30 Juni 2009 Hier Aufgabenstellung einf gen Selbstst ndigkeitserkl rung Hiermit erkl re ich dass ich die von mir am heutigen Tag dem Pr fungsausschuss der Fakult t Elektro technik und Informationstechnik eingereichte Diplomarbeit zum Thema SGI RASC Evaluierung einer Programmierplattform zum Einsatz von FPGAs als Hardware Beschleuniger im Hochleistungsrechnen vollkommen selbstst ndig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel be nutzt sowie Zitate kenntlich gemacht habe Dresden den 30 Juni 2009 Robert Dietrich Kurzfassung Im Hochleistungsrechnen wird heutzutage neben massiver Parallelverarbeitung und entsprechend effi zienter paralleler Programmierung verst rkt spezielle Hardware zur Beschleunigung von Anwendun gen verwendet blicherweise wird dabei ein Problem eine Anwendung oder ein Algorithmus als eine Abfolge von Befehlen Software an die Hardware wie z B Mikroprozessoren od
55. TELLE 57 MByte s 0 0 0625 0 125 0 25 0 5 1 2 4 8 16 32 64 128 256 512 1024 Datenmenge MiByte DirectlO VHDL e DirectlO VHDL 100Mhz DirectlO Mitrion t BufferedlO VHDL gt BufferediO VHDL 100MHz BufferedlO Mitrion Abbildung 5 2 Durchsatz ber den SRAM des RC100 Blades als ein Multibuffering SRAM Segment zu senden Daf r muss auch die Bitstream Konfi gurationsdatei angepasst werden was aber ohne erneute Hardware Synthese m glich ist 5 1 2 Tests und Messungen Die Hardware Synthese konnte f r 100 MHz Taktfrequenz des Algorithmus VHDL und Mitrion mit geringem Aufwand durchgef hrt werden F r 200 Mhz nur VHDL musste der Aufwand jedoch erh ht werden um das Timing der Core Services zu erm glichen Das fertige Design ben tigt bei gleichen Parametern der technologiespezifischen Synthese mit Mitrion 14 und mit der VHDL Implementierung 12 der Slices des Virtex 4 LX200 FPGAs Abbildung zeigt eine bersicht der Messungen zur SRAM Kommunikation Die Datendurchsatzmessungen in wurden mit einer fr heren Version von Mitrion vorgenommen und weisen bei 64 MiByte Paketgr e mit Direct I O h here und mit Buffered I O niedrigere Daten durchs tze auf Diese k nnen jedoch je nach CPU Wahl und Auslastung des Systems um einige hundert MByte s abweichen Damit erreichen die Messungen gerade die H lfte des theoretische Maximums von 3 2 GByte s Auch wenn die Daten ausschlie lich vom Host in den SRAM des RC100 Blade
56. Teile eines Algorithmus werden nicht mehr auf der CPU sondern auf einem oder mehreren FPGAs ausgef hrt In Abschnitt 2 6 wird auf die Funktion von FPGAs als Hardware Beschleuniger im HPC genauer eingegangen 2 2 Aufbau und Grundstruktur Architektur blicherweise sind FPGAs aus einer regelm igen Struktur von konfigurierbaren Logikbl cken CLBs 1 O Ports und Verbindungskan len wie Abbildung P 1 zeigt aufgebaut DOOOODOBOODODODDEAUAD Sem e Ee ee Block RAI Block RAM Block CELS LE ELS LELEL e ee eee ee 5 S565 56 SS SESS SSeS SIS a a a a SIS HEL K r Rer We S SS R RE RR Be We KC SLE SL EE a a RK We We RCM RE a a A We We WC We WE 5 85 86 66 GSS OS GGG GG Abbildung 2 1 Typische Architektur eines FPGA Um eine Schaltung auf einen FPGA abbilden zu k nnen muss dieser ausreichend geeignete Ressourcen bereitstellen W hrend die Anzahl der ben tigten CLBs und V O Ports einfach aus dem Design heraus bestimmt werden kann variiert die Anzahl der Routing Elemente sogar bei Designs mit gleicher Menge an Logik Beispielsweise ben tigt ein Koppelfeld engl crossbar switch mehr Verbindungsressourcen als ein systolisches Array mit der selben Anzahl von Gattern Da ungenutzte Verbindungsressourcen die Kosten erh hen und FPGA Fl che belegen werden nur so viele Verbindungskan le implementiert wie ben t
57. Verh ltnis 1 1 verbessert und im Optimalfall f r den SX240T 4 78 erreicht Tabelle R 3 zeigt einen berblick der Top FPGA Modelle von Xilinx aus den letzten drei Virtex Generationen und ihre FP Performance bei Verwendung von genauso vielen Multiplizierern wie Addierern Damit ist ein direkter Vergleich mit Mikroprozessoren welche Multiplizier Addier Einheiten verwenden m glich Die Werte wurden hier von Hand berechnet und m ssen damit nicht dem Optimum entsprechen sollten aber nicht weit davon entfernt sein FPGA Mult Add Taktfrequenz GFLOP s Virtex 4 LX200 6 25 90 0 153 85 255 00 MHz 9 54 45 90 Virtex 4 SX55 10 0 26 0 277 95 331 50 MHz 5 56 17 24 Virtex 5 LX330 21 26 13340 201 45 348 50 MHz 18 93 42 85 Virtex 5 SX240T 66 0 189 0 337 45 348 50 MHz 44 54 131 73 Virtex 6 LX760 96 60 432 0 219 76 380 18 MHz 68 57 328 48 Virtex 6 SX475T 163 0 504 0 341 24 380 18 MHz 111 24 383 22 Tabelle 2 3 Virtex FPGAs FP Performance Multiplikation Addition 64 Bit 32 Bit Die zweite Spalte gibt an wieviele Multiplizier Addier Einheiten auschlie lich in Logik und mit DSP Slices implementiert wurden DSP Logik FP Einheiten Die in angegebenen maximalen Taktfrequenzen wurden um 15 verringert und sind in Spalte drei eingetragen Da die f r die Virtex 6 FPGAs ben tigten Ressourcen zur Implementierung von FP Verarbeitungseinheiten noch nicht
58. Vorgehensweise zur Analyse von Systemen die f r eine theoretische oder for melm ige Behandlung zu kompliziert sind Dies ist berwiegend bei dynamischem Systemverhalten der Fall Weitere Gr nde f r den Einsatz einer Simulation K nnen z B sein wenn die Untersuchung am realen System entschieden aufw ndiger w re oder das reale System noch nicht existiert Jede Form der Simulation hat nat rlich auch Grenzen wie z B die Begrenztheit der Mittel Rechenkapazit t Zeit etc Aufgrund dieser Einschr nkungen muss ein Modell m glichst einfach sein was bedeutet dass eine grobe Vereinfachung der Realit t vorgenommen wird Dies beeinflusst wiederum die Genauigkeit der Simulationsergebnisse Diese anwendungsunspezifische Betrachtung kann direkt in die Hardware Simulation bernommen wer den Auch wenn es sich um rekonfigurierbare Hardware wie FPGAs handelt ist die Simulation bei der Hardware Entwicklung ein nicht zu untersch tzender Aufwand Sie wird haupts chlich deswegen ver wendet weil die Fehlersuche auf dem FPGA kompliziert ist und eine Hardware Synthese je nach Gr e der Schaltung mehrere Tage dauern kann Ohne Simulation w rde sich der Hardware Entwicklungs zyklus stark verl ngern F r die Simulation paralleler Hardware ist es notwendig die Abl ufe auf ein sequentielles Programm abzubilden Dies wird mit sog Zeitscheiben vorgenommen Es werden alle nebenl ufigen Anweisun gen und Prozesse einzeln ausgef hrt und jede
59. ack Et see Nd 1 iterations 13 D es 2 6 rch 6 Bandwidth Graph BW limited body ch 6 rch 6 Env main foreach lt 1 gt rch 6 BW limited body ch 1 rch 6 1 1 reh 3 6 BW limited body ch 1 rch 6 iterations 1 Env main foreach 1 foreach lt 1 gt 1 6 0 ch 6 rch 6 BW limited body ch 6 rch 6 1 iterations 6 nv main foreach 1 foreach lt 1 gt solveQ26 for lt 6 gt 1 60 0 ch 6 rch 6 Latency limited dataloop body latency 10 0 aa iterations 1 Env main foreach 1 foreach lt 1 gt solveQ26 while 1 15 0 ch 1 rch 6 Latency limited dataloop body latency 15 0 End Summary Bandwidth Graph 126 ANHANG A QUELLCODES 20 25 30 35 40 45 50 55 60 Auflistung A 14 Optimierte Mitrion C Implementierung des Damenproblems Mitrion C 1 5 options define define define define define define Calculates all completions of valid Queens placements on a NxN board cpp N 26 L 6 NNN 78 Nx3 SLICES 2 PREPLACEMENTS 16 PERSLICE 8 under the pre placement provided in cs as D lcol 0 Jcol 1 col L 1 col i 5 bits x This encoding is valid up to L 6 and N 32 when col 0 is placed only up to th middle row x param return D uint 46 solveQueens uint 32 cs create internal RAM cs Pre Plac Number of va blocking horizon
60. aming Port mehr fach Datenstr me empfangen oder senden k nnte ohne das zwischendurch der Algorithmus been det werden muss 95 7 Zusammenfassung und Ausblick In der vorliegenden Arbeit wurde die SGI RASC Plattform untersucht und mit Mitrion C und VHDL zwei Programmierm glichkeiten verglichen Hierf r wurde in einem analytischen Teil die Beschleuniger Technologie vorgestellt und dabei insbesondere auf die verwendeten Virtex 4 FPGAs eingegangen Zu dem wurden Aufbau und Kenndaten des RC100 Blades vorgestellt sowie die Software und Hardware Programmierschnittstelle untersucht Das RC100 Blade integriert sich sehr gut in die Architektur der Altix 4700 und ist mit der vollen Bandbreite von 6 4 GByte s an das NUMAlink4 Netzwerk angeschlos sen Da die Flie kommaverarbeitungsleistung ein typisches Vergleichsma im Hochleistungsrechnen ist wur de diese in einer theoretischen Betrachtung f r mehrere Virtex FPGAs abgesch tzt Die von SGI RASC unabh ngige Untersuchung kann auf verschiedene FPGA basierte Beschleuniger Systeme angewendet werden und zeigt dass FPGAs durchaus mit aktuellen Prozessoren mithalten k nnen andere Hardware Beschleuniger wie z B GPUs in diesem Bereich jedoch bessere Performance bieten Mit dem Damenproblem und dem MD5 Brute Force Algorithmus konnten zwei komplexere Beispiele auf die RASC Plattform portiert und deutliche Leistungssteigerungen gegen ber aktuellen Prozessoren verzeichnet werden Die Kommuni
61. an gegeben sind wurden die Werte der Virtex 5 angenommen Die maximale Taktfrequenz wurde jedoch mit es multipliziert weil Virtex 6 DSP Slices anstelle von 550 MHz mit 600 MHz arbeiten Die FP Performance errechnet sich aus dem mit zwei multiplizierten Produkt der Spalten f nf und sechs da eine Multiplizier Addier Einheit gleichzeitig Multiplikation und Addition durchf hren kann Der begrenzende Faktor f r die Signalverarbeitungs FPGAs ist meist der Logik oder FF Bedarf w h rend bei auf Logik optimierten FPGAs LX die DSP Slices nicht ausreichen damit FP Einheiten in 2 6 FPGAS ALS HARDWARE BESCHLEUNIGER IM HPC 19 CLBs umgesetzt werden und die Taktfrequenz verringert werden muss Virtex 6 FPGAs beinhalten pro Slice acht FFs und vier LUTs wodurch der FF Bedarf kein die FP Performance begrenzender Faktor ist Die schwache Leistung des Virtex 4 SX55 liegt an der geringen Anzahl an FFs und LUTs wodurch bei voller Nutzung der DSP Slices nur etwa 37 der insgesamt verf gbaren DSP Slices verwendet werden k nnen Verglichen mit GPUs siehe Wag08 ist die theoretisch erreichbare FP Performance von FPGAs deut lich geringer NVIDIAs Tesla C870 und AMDs FireStream 9170 haben eine theoretische Maximalleis tung von ber 500 GFLOP s f r einfache Genauigkeit 32 Bit Bei Messungen konnten jedoch maximal 200 GFLOP s erreicht werden Wird der Fakt betrachtet dass FPGAs eigentlich nicht f r FP Verarbeitung entwickelt wurden bieten
62. angs LUTs 116749 von 178176 65 Anzahl der FIFO16 RAMB 16s 164 von 336 48 Tabelle 5 2 MD5 Brute Force FPGA Ressourcen Nutzung Mitrion Obwohl die Ergebnisse vermuten lassen dass noch eine weitere Pipeline implementierbar ist konnte die Verdrahtung des entsprechenden Designs wegen Timing Fehlern nicht erfolgreich beendet werden Auch durch Anpassung der Synthese Parameter konnten keine vier Pipelines implementiert werden Hinzu kommt dass ein Ergebnis erst nach der Durchsuchung des gesamten Zeichenraums aller Zeichenkom binationen zur Verfiigung steht wodurch sich die durchschnittliche Suchzeit verdoppelt Ein bis zur 70 5 FALLBEISPIELE Version 2 0 1 nicht vorhandenes Mitrion C Sprachkonstrukt zur vorzeitigen Beendung des Algorithmus w rde dieses Problem beseitigen 5 4 3 Vergleich der MD5 Implementierungen Die f r die RASC Plattform vorgenommenen Implementierungen verwenden beide in etwa gleich vie le Logik Ressourcen wobei das Mitrion C Design dreimal soviele Block RAM Ressourcen ben tigt In beiden F llen sind noch ber 20 der FPGA Fl che ungenutzt W hrend mit der aktuellen Versi on von Mitrion keine weitere MD5 Pipeline in das Design integriert werden kann sollte es f r den VHDL Entwurf durch anderes Synthese Tool nderung im Entwurf m glich sein Tabelle 5 3 zeigt die Performance beider Implementierungen Mitrion C 100MHz VHDL 146 6MHz parallele Pipelines 1 2 3 3
63. ann zwischen Testbenches Simulationsbeschreibung mit integrierter Fehlererkennung und Test benches welche nur den reinen Zeitverlauf sog Waveforms darstellen unterschieden werden Der Nachteil letzterer ist dass dabei Fehler in der Implementierung durch die manuelle Pr fung leicht ber sehen werden k nnen vorallem bei komplexen Schaltungen 4 2 3 Hardware Synthese Als Synthese aus dem Griechischen synthesis die Zusammensetzung Zusammenfassung Verkn p fung bezeichnet man den Umsatz die Vereinigung von zwei oder mehr Elementen Bestandteilen zu einer neuen Einheit Anders formuliert versucht die Synthese aus mehreren Komponenten und oder Anweisungen ein System zusammenzusetzen Im digitalen Schaltkreisentwurf wird der Begriff der Syn these verwendet um die Umwandlung einer funktionalen Beschreibung einer Schaltung in eine Gatter Netzliste zu beschreiben Ein Hardware Synthese Schritt kann als eine automatisierte Implementierung einer formalen Spezifika tion auf einer niedrigeren Abstraktionsebene betrachtet werden vgl HocO8 Mit niedriger werdender Abstraktionsebene kommen Informationen hinzu wobei ab der Register Transfer Ebene technologies pezifische Daten mit einflie en Abbildung 4 5 zeigt die verschiedenen Abstraktionsebenen von oben nach unten fallender Abstraktionsgrad und die Hardware Synthese Schritte um eine niedrigere Abstrak tionsebene zu erreichen Sowohl f r die aus einem Mitrion C Programm
64. atenmengen wurden durch das erneute Senden des bereits allokierten Speichers ermittelt und bieten dementsprechend keine oder nur geringf gig h here Datenraten Die Halbierung der Segment Gr e einer SRAM Bank f hrte zu einer leichten Verringerung des Datendurchsatzes Neben einer Latenz von 16 Taktzyklen bei 200 MHz Taktfrequenz 80 ns wurde die Bandbreite mit 6 4 GByte s entspricht dem theoretischen Maximum zwischen FPGA Algorithmus und einer 16 MiByte SRAM Bank gemessen F r die Messung der Bandbreite wurden gleichzeitig 8 MiByte in den SRAM geschrieben und gelesen und die ben tigten Takte gez hlt Die Latenz wurde f r einen indizierten Spei cherzugriff ebenso durch Z hlen der Takte ermittelt 5 2 Direct Streaming Das direkte Streaming ist immer dann gut geeignet wenn der Algorithmus keinen indizierten Zugriff auf einzelne Werte ben tigt und Datenstr me direkt verarbeiten kann oder die Block RAM Ressourcen des FPGA als Pufferung ausreichen Zudem verwenden bei dieser Kommunikationsvariante die Core Services am wenigsten FPGA Logik und es werden die h chsten Datendurchs tze erreicht 5 2 1 Implementierung F r Mitrion C ist die Implementierung des direkten Streamings recht einfach Es m ssen neben den Spei cherports ausschlie lich der bergabe und R ckgabe Stream in der Main Funktion angegeben werden Der Speicherkontroller der Core Services wird damit auch integriert wenn der Algorithmus nicht auf den SRAM zugreift
65. ations Bitstream wird in einem Flash Speicher EEPROM gehalten und tiber den Loader FPGA der zwischen einem PCI Port des TIO ASICs und den Algorithmen FPGAs geschalten ist mit tels SelectMap siehe Xil08b geladen Die Core Services siehe Abschnitt 3 bilden zusammen mit dem Algorithmus den Bitstream und sind direkt mit den SSP Ports der TIO ASICs verbunden Verwendet werden Xilinx Virtex 4 LX200 FPGAs siehe Kapitel 2 Ein einzelner FPGA und dessen Anbindung an das System wird als RASC FPGA Hardware Modul bezeichet und ist in Abbildung dargestellt Der TIO ASIC erlaubt den direkte Anschluss an das NUMAIink4 Netzwerk unterst tzt zwei PCI X Busse einen AGP 8X Bus und den Scalable System Port SSP welcher die Schnittstelle zum FPGA bildet Der FPGA kann mit einer Bandbreite von 16 GB s auf seinen lokalen SRAM zugreifen auf den Host und dessen Hauptspeicher mit durch das NUMAlink4 Netzwerk begrenzten 6 4 GB s 3 3 Core Services Auf Seite der rekonfigurierbaren Hardware bilden die RASC Core Services die Schnittstelle zum Al gorithmus SGI stellt sie sowohl als Verilog Quellcode als auch als vorsynthetisierten IP Core fertige Schaltung in Form einer Netzliste bereit Verilog Wrapper Module werden als Verkn pfung zum ei Quad Data Rate static RAM dual in line memory modules pro Taktzyklus k nnen bis zu vier Datenw rter bertragen werden 24 3 SGIRASC 3 2GB s pro DIMM 6 4GB s 6 4GB s 6 4GB
66. b andere Beschleuniger wie Grafikkarten bessere Performance bieten ist Teil der Untersuchungen dieser Arbeit Zur Programmierung von FPGAs gibt es verschiedene M glichkeiten welche zu mehr oder weniger effizienten Schaltungen f hren Auf der niedrigsten Ebene kann eine Schaltung mit Hardwarebeschrei bungssprachen HDLs wie VHDL oder Verilog beschrieben werden Diese haben den gr ten Einfluss auf das Design und bieten f r erfahrene Programmierer die beste Performance Typischerweise sind je doch HPC Programmierer meist keine Hardware Entwickler Um die FPGA Programmierung dem HPC Programmierer dennoch zug nglich zu machen abstrahieren Hochsprachen von der Komplexit t des Hardware Entwurfs Durch diese Sprachen kann auf Kosten der Performance eine deutliche Steigerung der Produktivit t erreicht werden Diese Arbeit soll mit SGI RASC eine HPC Programmierplattform zum Einsatz von FPGAs als Hardware Beschleuniger untersuchen und dabei die Hochsprache Mitrion C im Vergleich zu VHDL evaluieren Dazu wird grundlegendes Wissen ber FPGAs als Zieltechnologie in KapitelP vermittelt wobei speziell auch die hier verwendeten Virtex 4 FPGAs betrachtet werden Die Flie kommaverarbeitung ist keine St rke von FPGAs soll aber dennoch in Abschnitt 2 5 als typisches Leistungskriterium im HPC unter sucht werden In Kaptitel B wird schlie lich die SGI RASC Programmierplattform vorgestellt wobei neben Aufbau und Kenndaten auch auf die Hardware un
67. bare Bandbreite an dieser Schnittstel le auf 6 4 GByte s und ist theoretisch kein Flaschenhals mehr was in Messungen auch best tigt wer den konnte Zudem wird bei der VHDL Implementierung die Latenz von indizierten SRAM Speicher zugriffen aus dem Algorithmus Block gemessen Weiterhin wird zwischen Buffered I O und Direct I O unterschieden vgl Abschnitt 4 1 Abs tze drei und vier 5 1 1 Implementierung Das einfache Mitrion C Programm aus 5 1 verwendet den RC100 SRAM zum Datentransfer zwischen Host und Algorithmus Um auf Speicher Bl cke oder B nke zugreifen zu k nnen werden bei Mitrion C an diese gebundene Instance Tokens verwendet Die SRAM B nke werden in Form solcher Token der main Funktion bergeben und mit dem Schl sselwort mem versehen Eine Gr enangabe zu diesen legt fest wieviele Werte vom Algorithmus gelesen bzw geschrieben werden d rfen F r eine 16 MByte SRAM Bank k nnen minimal 2048 und maximal 1048576 128 Bit Werte bertragen werden Die untere Grenze ist von Mitrion festgelegt w hrend sich die obere Grenze aus der Gr e der Speicherbank ergibt Die Daten werden auch bertragen wenn der Algorithmus diese nicht verarbeitet Um Multibuffering siehe 3 1 letzter Absatz zu erm glichen wird die SRAM Bank in Segmente unterteilt Die Beispiel Implementierung verwendet zwei Segmente pro 16 MByte SRAM Bank wodurch immer ein Vielfaches von 524288 128 Bit Werte pro Richtung zwischen Host und FPGA bertragen w
68. be wird die Netzliste der Schaltung mit den Informationen aus dem Technologie Mapping ver wendet Randbedingungen wie z B Verdrahtung und Ein und Ausg nge der Schaltung m ssen hier mit betrachtet werden Auch dieser Vorgang ist ein NP vollst ndiges Problem und kann nur bei gleichzeiti ger Verdrahtung exakt gel st werden Die Verdrahtung selber ist stark abh ngig von der Zieltechnologie und der Plazierung Bei FPGAs wird diese ber verschiedene Verbindungskan le vollzogen w hrend bei ASICs Metalllagen genutzt werden Die Verdrahtung hat zudem ma geblichen Einfluss auf die Perfor mance einer Schaltung Das sog Place amp Route ist sehr rechenintensiv und kann bei gro en Designs mit harten zeitlichen Be dingungen viele Stunden bis Tage in Anspruch nehmen Der Zeitaufwand h ngt dabei nicht nur von der Komplexit t des FPGA Designs ab sondern auch vom Grad der gew hlten Optimierung Verbin dungswege m ssen m glichst kurz sein um die Signallaufzeiten und den Fl chenbedarf f r benutzte Verdrahtung gering zu halten Mitunter werden auch CLBs verwendet um eine Verdrahtung unter ent sprechenden zeitlichen Bedingungen zu erm glichen Nach der Verdrahtung sind die Signallaufzeiten fest und k nnen f r eine Timing Simulation verwendet werden W hrend der Timing Analyse werden zuvor noch der l ngste Pfad und die damit h chste zu erreichende Taktfrequenz ermittelt 52 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM
69. bis 552 18Kbit Dual Port RAM Bl cken 500 MHz und von 86 bis 1392 KBits als verteilten Speicher Verwendung von CLBs Zudem sind 14 2 FPGAS SLICEL SLICEL Logik verteilter Speicher Schieberegister Logik SHIFTIN COUT a S wg Slice 3 ee SC 2 Schalt matrix Verbindung zu Nachbar CLBs anc Slice 1 Er SHIFTOUT CIN Abbildung 2 4 Konfigurierbarer Logikblock CLB der Virtex 4 FPGAs vgl Xil08c Virtex 4 Slice clk rst Abbildung 2 5 Stark vereinfachter Virtex 4 Slice ohne Carry und Speicher Logik vgl X1l08c 2 5 FLIESSKOMMAVERARBEITUNGSLEISTUNG 15 zwischen 32 und 512 Xtreme DSP Slices 500 MHz und 4 bis 32 Digital Clock Manager DCM Bl cke integriert Durch die unterschiedlich langen Verbindungen erreicht ein Taktsignal die einzelnen CLBs nicht gleichzeitig F r Pipelines z B ist es jedoch wichtig dass sie synchron getaktet sind da sonst undefinierte Werte zustande kommen k nnen Mit Hilfe von Delay Locked Loops DLLs sorgen die DCMs daf r dass der Takt alle CLBs gleichzeitig erreicht Au erdem gibt es f r die FX Plattform sog Hard IP Bl cke fest verdrahtete Schaltungen wie z B PowerPC Prozessor Bl cke bis 450MHz maximal zwei pro FPGA Ethernet MACs zwei oder vier pro FPGA und RocketIO Multi Gigabit Transceiver MGT Bl cke 8 bis 24 pro FPGA Fest verdrahtete Logik f r Multiplizierer Prozessorkerne
70. blockiert die Programmausf hrung bis alle gesendeten Be fehle ausgef hrt wurden rasclib_cop_close gibt alle Host Ressourcen im Zusammenhang mit dem an gebenen Algorithmus frei rasclib_resource_return gibt die Konfiguration eines FPGA frei bleibt reserviert rasclib_resource_release gibt reservierte FPGAs frei Tabelle 3 2 Ausgew hlte Funktionen der rasclib Bibliothek Mit Direct I O k nnen Daten direkt aus den vom Nutzer angelegten Puffern zum FPGA Koprozessor geschickt werden ohne dazwischen in einen Speicherbereich des Kernels kopiert werden zu m ssen Der Speicherbereich muss hierbei an 128 Byte Grenzen ausgerichtet und m glichst kontinuierlich auf den physikalischen Speicher abgebildet sein Unter Nutzung der hugetlbfs Funktion des Linux Kernels kann die rasclib passende Speicherbereiche bereitstellen Bei Buffered IO hingegen wird der Speicherinhalt vorher in einen Speicherbereich des Kernels kopiert Dies ist zwar an keine Voraussetzungen gekn pft bietet aber weniger effektive Bandbreite SGI08 Kapitel 5 3 4 2 Algorithmen Verwaltung Um einen Algorithmus auf den RC100 FPGAs ausf hren zu k nnen muss dieser zuvor als bin re Datei engl Binary unter einem eindeutigen Namen ID im System registriert werden Die Erstellung des Al 3 4 SOFTWARE 31 gorithmus wird in Kapitel 4 genauer erl utert Nachdem das Binary in der Registry eingetragen wurde kann es ber den RASC Abstraction Layer siehe 3 4 1 mit seinem
71. ch erneuter Umsetzung in Hardware wieder im vorhandenen Umfang nutzbar Wird auf ein klei neres System FPGAs mit weniger Logik portiert kann der Algorithmus u U nicht mehr implementiert werden oder es muss die Parametrisierung bei einem generischen Entwurf ver ndert werden Abbildung 4 1 zeigt den Entwicklungszyklus fiir Mitrion C Programme auf der SGI RASC Hardware Im oberen Bereich ist die Softwareentwicklung im unteren Bereich die Umsetzung in Hardware dargestellt 4 1 1 Programmiersprache Mitrion C Um den MVP effektiv programmieren zu k nnen stellt Mitrionics mit Mitrion C eine implizit paral lele Programmiersprache bereit Diese soll den Programmierer dabei unterstiitzen die Anforderungen einer parallelen Ausfiihrung eines Programmes zu erfiillen und zudem leicht und schnell erlernbar sein Der Syntax lehnt sich an bekannte Sprachen wie C C Java C etc an Zus tzlich soll Mitrion C verhindern Verklemmungen Deadlocks oder Wettlaufsituationen Race Conditions zu beschreiben Verwendet man sog Instance Tokens und Streams ist dies aber dennoch m glich In Mitrion C kann der Programmierer eine beliebige Anzahl von untereinander abh ngigen Prozes sen beschreiben wobei die Synchronisation zwischen diesen dem Programmierer verborgen wird Das Scheduling System des MVP sorgt daf r dass Daten zur richtigen Zeit am richtigen Ort sind Prozesse werden implizit durch einzelne Anweisungen oder Anweisungsbl cke erzeugt und in
72. chen den Durchl ufen wird das Taktsignal des Algorithmus angehalten und das Reset Signal aktiviert Damit w rden alle sich in Berechnung befindenden Teilprobleme abgebrochen Hinzu kommt dass Teilprobleme als verloren gelten wenn ihre Berechnung zu lange dauert Werden nun sehr viele Teilprobleme gleichzeitig an den FPGA gesendet um die Solver gut auszulasten werden auch alle L sungen gleichzeitig zur ckgeschickt Ben tigt diese Gesamtberechnung zuviel Zeit gelten die L sungen als verloren Au erdem w rden alle in einem Durchlauf bereits berechneten Teill sungen bei einem Systemabsturz verloren gehen Werden hingegen weniger Teilprobleme pro Durchlauf verarbeitet sinkt die Auslastung der Solver durch die Ein und Auslaufphase Das Design kann bis zu 148 Teilprobleme gleichzeitig berechnen und arbeitet mit einer Taktfrequenz von 126 6 MHz was laut PNS 148 126 6 187SE Slice Aquivalenten auf 100MHz L serinstan zen entspricht Eine schnellere Taktung verhindert das als Baumstruktur realisierte Verteilungsnetzwerk welches die FIFOs mit den Solvern verbindet Die gro en Virtex 4 FPGAs erm glichen die Implemen 5 5 DAMENPROBLEM 77 tierung sehr vieler Solver wodurch sich der kritische Pfad des Verteilungsnetzwerkes verl ngert Eine Verringerung der Taktfrequenz von ausschlie lich dieser Komponente k nnte das Gesamt Design noch einmal beschleunigen 5 5 3 Implementierung mit Mitrion C Der Mitrion C Programmcode wu
73. chon w hrend des Hardware Entwurfs darauf geachtet werden ent sprechende Register mit Debugging Informationen zu belegen um sp ter falls die FPGA Anwendung nicht die gew nschte Funktionalit t aufweist eine Fehlersuche mit dem GDB zu erm glichen Zudem wird derzeit das direkte Streaming ber die Streaming Engines mit dem GDB FPGA nicht unterst tzt F r den Debugging Modus sollte am sog step_flag_out Register welches der Hardware Designer setzen kann eine 1 anliegen Dieses signalisiert den Core Services siehe Abschnitt 3 3 dass ein Taktzyklus beendet wurde Liegt andernfalls eine 0 an kann kein taktgenaues Debugging vorgenommen werden 32 3 SGIRASC 3 4 4 Algorithmus Konfigurations Tool Mit der RASC Version 2 20 wird die Konfiguration des Algorithmus benutzerfreundlicher Um die Core Services und den Algorithmus auf die benutzten Ressourcen abzustimmen werden Konfigurationsdatei en und Wrapper Module ben tigt Bei vorherigen RASC Versionen mussten diese Dateien entsprechend vorhandener generischer Vorlagen vom Hardware Entwerfer manuell erzeugt werden Das SGI RASC Algorithm Configuration Wizard ist ein Tool Command Language TCL Skript und erm glicht es anhand einer grafischen Oberfl che GUT die Ressourcen auszuw hlen die dem Algorith mus zur Verf gung stehen sollen Folgende Einstellungen k nnen vorgenommen werden Bezeichnung des Algorithmus Taktfrequenz des Algorithmus SOMHz 66MHz 100
74. ctlO VHDL DirectlO VHDL 100MHz DirectlO Mitrion r BufferedlO VHDL BufferedIO VHDL 100MHz BufferedlO Mitrion Abbildung 5 3 Direct Streaming Durchsatz nologiespezifischen Synthese mit Mitrion 13 und mit der VHDL Implementierung 7 der Slices des Virtex 4 LX200 FPGAs Der deutlich gr ere Fl chenbedarf des Mitrion Designs begr ndet sich in der unn tigen Integration des Speicherkontrollers W hrend der Tests erreichte diese Kommunikationsvariante mit bis zu 2 4 GByte s bei der bertragung einer kompletten Hugepage die h chsten Datenraten Abbildung 5 3 zeigt die Ergebnisse der durchge f hrten Tests Wie bei der SRAM Kommunikation erh ht sich der Durchsatz mit der Gr e der bertra genen Daten Bei 256 MiByte wird f r Direct I O der maximale Durchsatz erreicht welcher sich bei gr Beren Datenmengen leicht verringert Dies liegt daran dass mit einer Hugepage maximal 256 MiBytes zusammenh ngender Speicher allokiert werden kann und die rasclib_cop_send Funktion nur einen Poin ter auf den Speicherbereich der Daten akzeptiert Nach einem Streaming Durchlauf muss dann die rasclib_cop_close Funktion siehe Tabelle 3 2 aufgerufen werden bevor ein neuer Durchlauf gestartet werden kann Gr ere Datenmengen wurden durch das Senden einer Hugepage in mehreren Durchl ufen bertragen Die Messschleife zur Ermittlung des Durchsatzes ist im Quellcode Listing A 5 dargestellt Das Diagramm zeigt deutlich geringere Datenraten f
75. d Software Schnittstelle eingegangen wird Ei ne grundlegende Einf hrung in die Programmierm glichkeiten Mitrion C und VHDL wird in Kapitel 4 vorgenommen Die Fallbeispiele welche die Grundlage der Evaluierung von Mitrion C bilden wer den in Kapitel 5 beschrieben Dabei wird die mit VHDL und Mitrion C erreichte Performance auch mit anderen Technologien verglichen Die Auswertung in Kapitel soll zum einen das Leistungsverm gen der SGI RASC Plattform bewerten und zum anderen Mitrion C mit VHDL vergleichen und verdeutli chen in welchen F llen sich der Portierungsaufwand rechtfertigt Anschlie end werden in Kapitel 7 die erreichten Ziele zusammengefasst und ein Ausblick f r zuk nftige Untersuchungen gegeben 2 FPGAs Ein Field Programmable Gate Array FPGA ist ein Halbleiterbaustein aus der Familie der Programm able Logic Devices PLDs der durch den Nutzer bzw Hardware Entwickler nach der Herstellung kon figuriert werden kann Um zu spezifizieren wie der Schaltkreis arbeiten soll kommen Schaltpl ne oder Hardwarebeschreibungssprachen HDLs zum Einsatz Jede Funktion die ein anwendungsspezifischer integrierter Schaltkreis ASIC aufweisen kann ist auch in einem FPGA umsetzbar Grundlagenwissen ber FPGAs wird in Wan98 vermittelt Wie Mikroprozessoren folgen FPGAs dem mooreschen Gesetz engl Moore s Law und sind mit der Zeit schneller komplexer und in ihrer Strukturbreite kleiner geworden W hrend FPGAs fr her
76. d die schnellste Verbindung ermittelt vgl Abbildung 5 1 Die Messungen der Transferraten fiir verschiedene Datenmengen wurden dann bei geringer Auslastung des Systems in einem Durchlauf immer auf der gleichen CPU vorgenommen Bei den Messungen wurden maximal 256 MByte entspricht der Gr e einer Hugepage allokiert und Tool zum Binden von Prozessen an CPUs 5 1 SRAM SCHNITTSTELLE 55 diese mehrfach f r die bertragung gr erer Datenmengen an einen FPGA des RC100 Blades geschickt Im RASC Benutzerhandbuch SGIO8 wird empfohlen Daten mit der Gr e einer Hugepage zu schi cken um maximale Datenraten zu erreichen 5 1 SRAM Schnittstelle Die Kenndaten und Konfigurationsm glichkeiten des SRAM Interfaces wurden bereits in Abschnitt 3 3 1 vorgestellt Mitrion nutzt als minimale Implementierung der Kommunikation zwei 16 MByte Spei cherb nke mit 128 Bit W rtern Konfiguration 1 Optional kann noch die verbliebene 8 Mbyte SRAM Bank hinzugenommen werden Andere Konfigurationen wie f nf unabh ngige SRAM B nke oder kein SRAM Speicherkontroller werden nicht unterst tzt Um den maximalen Durchsatz f r die Kommunikation zwischen Host und Algorithmus ber die SRAM Schnittstelle zu ermitteln bietet es sich an die Konfiguration 1 zu implementieren was sowohl in VHDL als auch Mitrion C vorgenommen wurde Durch das Zusammenfassen von zwei SRAM B nken je 8 MByte und 3 2 GByte s Bandbreite verdoppelt sich die nutz
77. den Die Beschr nkung auf einmalige Signalzuweisung gilt nur au erhalb von Prozessen in nherhalb wird der letzte zugewiesene Wert bernommen Bei einem bedingten Anweisungsblock werden im nicht angegebenen alternativen Zweig keine Signale ver ndert Es gibt in VHDL keine R ckgabewer te von Anweisungsbl cken da Signale in einer Komponente global sind und Variablen innerhalb eines Prozesses gelten Das Damenproblem ist ein Beispiel welches in Mitrion C nicht so beschrieben werden kann dass es gute Performance aufweist Gewisse teilweise bewusste Einschr nkungen im Sprachumfang begr nden die sen Umstand Beispielsweise gibt es im Vergleich zu VHDL oder typischen Programmiersprachen keine zu einem Feld engl array vergleichbare Struktur Mitrion Listen k nnen nur sequentiell abgearbeitet werden w hrend Mitrion Vektoren kein indiziertes Schreiben von einzelnen Elementen erlauben Eine Umgehungsl sung engl workaround daf r bietet die Nutzung von Block RAM welcher allerdings die parallele Abarbeitung in Mitrion C Programmen deutlich einschr nkt Allgemein sind Datenstrukturen in VHDL flexibler und k nnen auch vom Programmierer definert werden Eine M glichkeit in Mitrion C Strukturen zu beschreiben sind Tuple Auf Elemente in Tuples kann jedoch nicht indiziert oder durch die Angabe einer Variablenbezeichung zugegriffen werden Sie dienen lediglich dem Zusammenfassen meh rerer Variablen um gerade bei R ckgabewerten von Bl cken da
78. der hnlich und bestehen aus jeweils 16 gleichen Operationen basierend auf einer nichtlinearen Funktion modularer Addition und einer Linkrotation 5 4 MD5 BRUTE FORCE 65 Die in den vier Runden verwendeten Funktionen sind F X Y Z KAY V ELAZ G X Y Z XAZ V YA Z H X Y Z XYZ IX Y Z YS Xv 2 Hierbei stehen 6 A V f r XOR AND OR und NOT Operationen Jeder Durchlauf arbeitet auf einem 512 Bit Nachrichtenblock und ver ndert den Puffer und damit die MD5 Summe Werden nicht mehr als 56 Zeichen ein Nachrichtenblock verwendet ist nur ein Durchlauf notwendig und die Schleife ber die 512 Bit Bl cke entf llt F r die VHDL und Mitrion C Implementierung werden ausschlie lich kurze Nachrichten von bis zu acht Zeichen betrachtet 5 4 1 VHDL Entwurf Die Hardware Beschreibung des MD5 Brute Force Algorithmus basiert auf mehreren parallel arbeiten den Pipelines welche den Hauptteil des Algorithmus umsetzen Die Parallelverarbeitung steckt damit zum einen in der Pipeline Struktur selber und zum anderen in deren Anzahl Hinzu kommt eine Kompo nente zur Erzeugung der 512 Bit Nachrichtenbl cke und eine weitere zur R ckgewinnung des Klartex tes wenn der gesuchte Hash gefunden wurde Eine schematische bersicht der VHDL Implementierung ist in Abbildung5 6 dargestellt Die Erzeugung der Nachrichten wird im Klartext Generator vorgenommen Dieser basiert auf einer der Klartextl nge entsprechenden Anzahl von Z hlern
79. der Nachrichtenbl cke zu verringern kann der Block RAM des FPGA genutzt werden Zudem m ssen Teile 32 Bit Bl cke der Nachricht nur solange gespeichert werden bis sie nicht mehr ben tigt werden mindestens jedoch bis zur ersten Stufe der vierten Runde Wenn vom allgemeinen Fall dass 56 Zeichen pro Nachricht genutzt werden k nnen und die L nge der Nachricht variiert abgesehen wird kann ein Gro teil des Nachrichtenblockes als konstant angenommen werden Die vorgenommene Implementierung passt sich der Wortl nge an und nutzt bei der Verwendung von vielen Zeichen den Block RAM als zirkularen Puffer Dieser ben tigt nur einen Z hler welcher die Schreib und Leseadresse definiert Damit k nnen zwei Puffer in einen Dual Port Block RAM inte griert und Block RAM Ressourcen eingespart werden Die VHDL Funktionen der ersten beiden MD5 Runden welche f r die Umsetzung der Pipeline Stufen verwendet wurden sind inB 3 aufgelistet Wie bei der Mitrion C Implementierung wird jede Stufe zum besseren Timing in zwei Operationen un terteilt wodurch eine Pipeline mit einer Tiefe von 128 Stufen entsteht Die Aufteilung der Einzelopera tionen in jeder Stufe wurde im Vergleich zur Mitrion C Implementierung anders gew hlt um mit dem Design eine h here Taktfrequenz erreichen zu k nnen In beiden Teilstufen werden jeweils zwei 32 Bit Additionen vorgenommen Die md5_logic Funktionen f hren zus tzlich weitere Logik Operationen 5 4 MD5 BRUTE
80. dition und Multiplikation ermittelt und zudem die Speedups zum 2 5 GHz Vierkern Opteron Prozessor angegeben Tabelle 2 zeigt einen Ausschnitt der Ergebnisse dieser theore tischen FPGA FP Betrachtung Nach diesen Werten ist der Virtex 5 SX240T bei jedem beliebigen Verh ltnis von Multiplikation und Ad dition schneller als der Opteron Prozessor Besonders auff llig ist dass sich der FPGA Speedup mit gr 18 2 FPGAS Verh ltnis GFLOP s 64 Bits 32 Bits Speedup over Opteron Add Mult Opteron LX330 SX240T LX330 SX240T nur Add 17 00 34 00 32 96 85 09 29 97 80 39 1 94 2 50 1 76 2 36 8 1 19 13 38 25 33 77 87 43 29 97 84 56 1 77 2 29 1 57 22 21 4 1 21 25 42 50 28 14 90 45 32 10 92 22 1 32 2 13 1 51 2 17 2 1 25 50 51 00 21 71 94 47 34 97 104 40 0 85 1 85 1 37 2 05 1 1 34 00 68 00 18 89 89 04 39 29 122 50 0 56 1 31 1 16 1 80 1 2 25 50 51 00 16 28 88 72 42 37 141 98 0 64 1 74 1 66 2 78 1 4 21 25 42 50 15 07 81 81 43 33 149 64 0 71 1 92 2 04 3 52 1 8 19 13 38 25 14 47 79 08 40 45 153 47 0 76 2 07 2 12 4 01 nur Mult 17 00 34 00 13 47 79 69 37 56 162 52 0 79 2 34 2 21 4 78 Optimal 34 30 94 47 44 94 162 52 Tabelle 2 2 FP Performance von Virtex 5 FPGAs im Vergleich zu Opteron Prozessor Serer Entfernung vom
81. e einer Datei mit einer zuvor errechneten verglichen um zu berpr fen ob die Datei ver ndert oder besch digt wurde Bei der bertragung von Dateien ber das Internet oder auch in Netzwerken ist es blich eine MD5 64 5 FALLBEISPIELE Hash Summe zur Kontrolle der bertragung mitzuschicken Da f r MD5 bekannt ist wie Kollisionen erzeugt werden k nnen vgl WYOS wird es heutzutage immer weniger in Anwendungen wie SSL Zertifikaten oder digitalen Signaturen verwendet welche auf der Resistenz vor Kollisionen aufbauen Wird MD5 genutzt um einfache Passw rter zu speichern so kann dieses mit sog Regenbogentabellen Sammlung von Klartextw rter und zugeh rigem Hash angegriffen werden Das Hinzuf gen eines Zu fallswertes Salt zum Passwort verhindert solche Angriffe Hierbei muss der Zufallswert mit dem Hash abgespeichert werden um die Eindeutigkeit der Abbildung des Eingabewerts auf den Hash Wert zu ge w hrleisten Solche salted Hashes k nnen allerdings noch durch Ausprobieren aller M glichkeiten Brute Force angegriffen und damit der Klartext ermittelt werden Wieviele Zeichen ein Klartextwort haben muss um sicher vor Brute Force Angriffen zu sein zeigen die Performance Messungen der vor genommenen Implementierungen und Vergleiche aus anderen Arbeiten siehe Abschnitt 5 4 3 Ein MDS Hash wird typischerweise als eine 32 stellige Hexadezimalzahl dargestellt Folgendes Beispiel zeigt eine acht Zeichen Byte la
82. e nach Kommu nikationsvariante zwischen 8 000 und 17 000 FFs und 7 000 und 13 000 LUTs vgl Abschnitte 5 1 1 B 2 1 und B5 3 1 Da es m glich ist Kommunikationsvarianten zu kombinieren kann auch eine gr ere Menge an Ressourcen durch die Core Services belegt werden Die Gesamtzahl an LUTs und FFs wird zus tzlich um 33 reduziert siehe KC07 um das Routing des Designs zu erm glichen Damit ste hen f r FP Operationen nur 3 FF s 20 000 FFs und 3 LUTs 20 000 LUTs zur Verf gung vgl grau hinterlegte Spalten aus Tabelle 2 1p SchlieBlich wird noch eine um 15 verringerte maximale Taktfrequenz der FP Schaltungen aus Xil08a angenommen um Verdrahtungsanforderungen gerecht zu werden Performance Absch tzung Mit dem Xilinx Floating Point Core k nnen f r verschiedene FPGAs zus tzlich noch verschiedene Implementierungen vier f r Multiplikation zwei f r Addition vorgenommen werden welche sich hin sichtlich der Nutzung von DSP Slices Logik und Flipflops und der maximal erreichbaren Taktfrequenz unterscheiden So sind FP Operationen ausschlie lich mit CLBs oder unter zus tzlicher Verwendung von DSP Slices umgesetzbar Werden weniger DSP Slices verwendet ist der Bedarf an FFs und LUTs f r die gleiche Anzahl an FP Verarbeitungseinheiten h her und die maximale Taktfrequenz niedriger In ISSWWOS werden die besten Resultate aller m glichen Kombinationen von Implementierungen bezo gen auf das Verh ltnis von Ad
83. e s Datendurchsatz m glich sind und mit Direct Streaming ein Daten durchsatz von 2 4 GByte s praktisch erreicht wurde Die Durchsatzbeschr nkung tritt bei der Kommuni kation zwischen Host und SRAM auf Bei einem Test wurden zwischen Algorithmus Block und SRAM die maximal erreichbaren 3 2 GByte s Datendurchsatz auch praktisch gemessen vel B 1 2 Zudem wur de die SRAM Kommunikation ohne die Verarbeitung der Daten durch den Algorithmus gemessen und 6 3 KOSTEN NUTZEN ABSCH TZUNG UND FAZIT 91 erreichte nur einen maximalen Durchsatz von 1 65 GByte s Anhand dieser Ergebnisse und dem Aufbau des Datenpfades vgl Abbildung 4 kann sich der Flaschenhals nur in einem Teil des Speicherkontrol lers der Core Services befinden 6 3 Kosten Nutzen Absch tzung und Fazit Als Ergebnis der Auswertung werden in diesem Abschnitt Kosten und Nutzen der Anwendungspor tierung abgesch tzt und damit die beiden quantifizierbaren Metriken Entwicklungszeit und Performan ce in einen Zusammenhang gestellt Eine Wirtschaftlichkeitsuntersuchung oder pauschale Absch tzung der Kosten und Nutzen ist aufgrund mangelnder praxisrelevanter Beispiele im Umfang dieser Arbeit nicht m glich Allein die Damenproblem Implementierung arbeitet ber einen l ngeren Zeitraum am Queens TUD Projekt ONST mit jedoch nicht in einem kommerziellen Rahmen Als Grundlage der Absch tzung dienen die Fallbeispiele MD5 Brute Force und 26 Damenproblem Die Kosten werden zeitlich in F
84. eben der hnlichkeit zum Syntax auch ein gewisses Repertoire an Standardkonstrukten erwartet Mitrion C besitzt hier einige Eigenheiten wie z B e Anweisungsbl cke Schleifen und Bedingungen haben R ckgabewerte e einmalige Variablenzuweisungen in einem Block engl single assignment e Unterscheidung zwischen schleifenabh ngigen und unabh ngigen Variablen e Listen und Vektoren anstelle von Feldern engl arrays R ckgabewerte von Anweisungsbl cken werden hinter diesen in Klammern angegeben und erm gli 86 6 AUSWERTUNG chen neben schleifenabh ngigen Variablen das Propagieren von Werten aus einem Block Anlehnend an die C Syntax w ren return Anweisungen u U intuitiver Es gibt die Schleifentypen FOR FOREACH und WHILE Die FOR Schleife muss mindestens eine schleifenabh ngige Variable enthalten w hrend die FOREACH Schleife keine enhalten darf Anweisungen wie break oder continue stehen nicht zur Verf gung Desweiteren k nnen keine einfachen Bedingungen formuliert werden ohne den Alternativ Zweig anzugeben W hrend einige dieser Eigenschaften von Mitrion C der Fehlervermeidung dienen k nnen sie auch als Einschr nkungen betrachtet werden welche eigentlich durch den Compiler oder eine Synthese gehandhabt werden sollten VHDL hingegen erf llt die Erwartungen an eine Hardwarebeschreibungssprache in vollem Umfang Sogar Hochsprachenelemente wie z B Schleifen Funktionen oder abstrakte Datentypen k nnen ver wendet wer
85. ed long finish_alg 0 if res rasclib_cop_reg_write res finish_alg amp finish_alg 1 RASCLIB_IMMED_CMD RASCLIB_ SUCCESS rasclib_cop_commit res NULL rasclib_cop_go res unsigned long reset do rasclib_cop_reg_read res reset amp reset 1 RASCLIB_IMMED_CMD rasclib_cop_commit res NULL jwhile reset Wait 5s until reset is done jclass const clsThread jenv gt FindClass jenv java lang Thread jmethodID const mthSleep jenv gt GetStaticMethodID jenv clsThread sleep J V jJenv gt CallStaticVoidMethod jenv clsThread mthSleep jlong 5000L jenv gt ExceptionClear jenv release not any more needed objects xjenv gt ReleaseStringUTFChars jenv jalgname astring return res receives values from fpga and returns them as byte array JNIEXPORT jint JNICALL Java_jrasc_JRasc_recvByteArray JNIEnv const jenv jclass const clsJRasc jint jcop_desc jbyteArray const jbarray jsize jb_length jenv gt GetArrayLength jenv jbarray Algorithm defined register array length const int ADR_SIZE jb_length ADR_BYTES unsigned long rasc_out_vld unsigned long fat_out512 ADR_SIZE unsigned char byteout jb_length A3 DAMENPROBLEM 129 60 65 70 75 80 85 90 95 100 105 110 115 int res int j i timeout Reduced polling while true Check Availability of
86. ef hrt werden um eine funktionsf hige Hardware Umsetzung zu erhalten Dies hat bei jeder Kommunikationsvariante einige Tage in Anspruch genommen da insbesondere das Timing der von den Core Services bereitgestellten Signalen problematisch war Die finalen Implemen tierungen k nnen jedoch mit wenigen Modifikationen auf andere Beispiele bertragen werden wodurch ein Gro teil des Entwicklungsaufwandes f r diese Schnittstellenbeschreibung nur einmal anf llt Die Datenmanipulation l sst sich dann in VHDL ebenso schnell und knapp wie in Mitrion C beschreiben 84 6 AUSWERTUNG Nach Angaben der Entwickler vgl PNS09 konnte eine erste funktionsf hige VHDL Damenproblem Implementierung in nur drei Stunden erstellt werden Das aktuelle Design ist aber in einem iterativen Prozess entstanden bei der jede berarbeitung erneute Vor berlegungen und Neuimplementierungen mit sich gebracht hat Hinzu kommt die Anbindung an die RASC Plattform welche ungef hr einen Tag in Anspruch genommen hat und durch nderungen am Design und neue Anforderungen mehrfach ange passt wurde Aus einem C Programm abgeleitet konnte eine erste funktional korrekte Implementierung in Mitrion C in etwa zwei Tagen erstellt werden Anschlie end wurden noch mehrere Tage in die Op timierung investiert Weitere angedachte Verbesserungen sollten in wenigen Tagen umgesetzt werden k nnen Die Mitrion C MD5 Implementierung konnte nach Angaben der Entwickler vgl IJO8 in e
87. eits berechneten Teilprobleme Auf den Hosts l uft eine Java Anwendung welche noch nicht berechnete Vorplazierungen anfordert die Kommunikation mit einem oder mehreren FPGAs durchf hrt um schlie lich gel ste Teilprobleme wieder an die Datenbank zu senden Im Falle von RASC wird die Ansteuerung der FPGAs ber das Java Native Interface JNI und die RASC C Bibliothek vgl Abschnitt 3 4 1 vorgenommen Der Quellcode der Damenproblem Java Schnittstelle f r SGI RASC ist in A 16 gelistet die zugeh rigen nativen C Funktionen in A 15 Als RASC Kommunikationsvariante werden Memory Mapped Registers verwendet Die Implementie rung erfolgt hnlich wie in Abschnitt 5 3 I bereits erl utert Es werden ein Eingangs und vier Ausgan gregister verwendet um gleichzeitig zwei Teilprobleme empfangen und mit L sung wieder zur ckschi cken zu k nnen Auf der Eingangsseite werden die empfangenen Werte jeweils in zwei Takten hinter einander in einen 32 Bit breiten und 256 Elemente tiefen Block RAM FIFO geschrieben um bei Bedarf vom Damenproblem Topmodul gelesen zu werden Auf der Ausgangsseite bernimmt ein ebenso tiefer 76 5 FALLBEISPIELE Kommunikation Damenproblem Gesamtdesign verf gbar Slices 5835 7 70370 79 76205 86 89088 FFs 6930 4 106217 60 113147 63 178176 LUTs 6896 4 129880 73 136776 76 178176 BRAM 14 4 0 14 4 336 Tabelle 5 6 26 Damenproblem Resso
88. elle 5 4 Maximale Suchdauer MD5 basierter Passw rter VHDL Implementierung 5 5 Damenproblem Beim klassischen Damenproblem sollen acht Damen auf einem typischen Schachbrett 8 x 8 Felder so positioniert werden dass sich keine zwei davon nach den Schachregeln in einem Zug schlagen k nnen Die Figurenfarbe ist dabei irrelevant und als Annahme gilt dass jede Figur eine beliebige andere schlagen k nnte Um eine L sung zu finden d rfen demnach keine zwei Damen in der gleichen Reihe Spalte oder Diagonale plaziert werden Abbildung 5 8 zeigt eine Plazierung die diesen Anforderungen gen gt F r das klassische Damenproblem gibt es 92 L sungen Wenn solche die durch Spiegeln oder Rotieren des 72 5 FALLBEISPIELE Abbildung 5 8 Eine L sung des Acht Damenproblems Brettes aufeinander abgebildet werden k nnen nur einmal gez hlt werden verbleiben zw lf eindeutige L sungen Ausgehend von diesen k nnte erwartet werden dass durch vier m glichen Drehungswinkel und vier Spiegelungen 12 8 96 L sungen existieren Da jedoch einige Plazierungen selbstsymmetrisch sind und beim Drehen in sich selber bergehen verringert sich die L sungsmenge vgl PNS Fakten Das Problem l sst sich auf die Plazierung von N Damen auf einem N x N Schachbrett verallgemeinern wobei nur L sungen f r N 1 und N gt 4 existieren Die eigentliche Problemstellung sucht nach der Anzahl der L sungen f r ein Damenproblem und damit nach allen
89. en Programm zusammen Die korrekte Funktionsweise wird mit Hilfe von Testf llen berpr ft Bei einer falschen Ausgabe wird der Fehler im Quellcode gesucht und beseitigt Danach wird erneut bersetzt gelinkt und getestet solange bis alle Testbeispiele fehlerfrei durchlaufen Bei der Entwicklung von Hardware kann das zugeh rige Design vor der eigentlichen Implementie rung simuliert und damit auf Fehler untersucht werden W hrend die Simulation bei der Hardware Entwicklung zwingend erforderlich ist ist sie bei der Software Entwicklung berfl ssig Ein Grund daf r ist die Zeit die f r eine bersetzung des Designs ben tigt wird Die bersetzungszeiten f r Software Entw rfe sind in der Regel kurz Die automatisierte Implementierung eines Hardware Entwurfs ben tigt dagegen wesentlich mehr Zeit F r gr ere Designs sind bersetzungszeiten von mehr als einem Tag realistisch Der Mitrion Enwicklungszylkus siehe Abbildung ordnet sich zwischen Hardware und Software Entwicklung ein Wegen der auch f r Mitrion C Programme notwendigen zeitintensiven Hardware Synthese wird Simulation verwendet um die Funktionalit t der Beschreibung zu berpr fen Allerdings findet diese in Mitrion C mit typischen Mitteln der Softwareentwicklung statt Watch Break Points 4 2 HARDWARE ENTWICKLUNGSABLAUF 45 Der herk mmliche Ansatz zur Beschreibung von Hardware und damit auch FPGAs sind Hardwarebe schreibungssprachen HDLs Die am mei
90. en Zeitschritt seine Operation ausgef hrt rot Der Knoten ist angehalten und kann seine Operation nicht ausf hren weil der Aus gang nicht konsumiert werden konnte grau Der Knoten wartet auf Eingangsdaten Daraus kann der Programmierer erkennen wie gut die parallele Abarbeitung des Algorithmus funktio niert In einem gut parallelisierten Programm ist die berwiegende Anzahl der Knoten gr n Abbildung zeigt den graphischen Simulator f r das Mitrion C Programm aus 4 1 Blaue Knoten und Kanten arbeiten mit Instance Tokens also RAM Zugriffen w hrend violette Kno ten Ein oder Ausg nge von Untergraphen darstellen Kanten die w hrend der Simulation einen Wert bermitteln zeigen diesen hellblau hinterlegt an In der Abbilung wurde der Knoten foreach Schleife f r das Schreiben der Ergebnisse in den SRAM bereits aufgeklappt und wartet auf die Ergebnisse der vorherigen Schleife Eine vollst ndige Darstellung aller Formen und Farben von Knoten und Kanten ist in MitO8b zu finden Der Datenabh ngiskeitsgraph welcher durch den Simulator im interaktiven Modus genutzt wird ben tigt noch einige Optimierungsschritte bevor daraus ein MVP erzeugt werden kann Dementsprechend kann der Graph nur genutzt werden um die Funktionalit t des Mitrion C Programmes zu simulieren 42 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM Die wirkliche Performance des Programmes kann nur durch die Ausf hrung des Simulators im Batch Mod
91. en anliegenden Werte und entsprechende Signalverl ufe angesehen werden um Fehler im Entwurf aufzudecken W hrend eine fehlerfreie Simulation mit Mitrion w hrend der Tests stets zu einer korrekten Hardware Umsetzung f hrte war dies bei den VHDL Entw rfen nicht immer der Fall Zur Simulation mit VHDL wird blicherweise eine Testbench erstellt welche das Verhalten der Schnittstelle beschreibt Da f r das Verhalten der Core Services an den Schnittstellen zum Algorithmus von SGI keine Testbench zur Verf gung gestellt wird muss diese laut der Spezfikation in vom RASC Nutzer programmiert werden Eine fehlerhafte oder unvollst ndige Beschreibung der Testumgebung kann jedoch auch zu einer inkorrekten oder nicht funktionierenden Hardware Umsetzung f hren Eine weitere M glichkeit der Fehlersuche ist mit den Debug Registern gegeben In beiden Sprachen k nnen Signale bzw Variablen an diese gebunden und auf Hostseite w hrend der Laufzeit deren Inhalt abgefragt werden Dies kann auch taktweise mit dem GNU Debugger siehe Abschnitt 3 4 3 vorgenom men werden wobei dieser das Direct Streaming nicht unterst tzt 6 2 4 Performance Die Performance der auf die RASC Plattform portierten Fallbeispiele in Mitrion C und VHDL wurde im einzelnen bereits in Kapitel 5 ausgewertet Tabelle 6 I zeigt die besten Messergebnisse der Beispielan wendungen und die Geschwindigkeitsgewinne Sp zwischen den Implementierungen im Uberblick Die Performance Au
92. en zur Ansteuerung der FPGA Koprozessoren bereitstellt 30 3 SGIRASC rung eines Algorithmus ohne bertragung von Daten nat rlich sinnfrei w re Sende und Empfangs Funktionsaufrufe werden pinzipiell in eine Warteliste eingereiht und erst durch die Commit Funktion an die Kernel Device Treiber geschickt w hrend die Lese und Schreibfunktionen je nach bergebenem Flag auch ohne Commit sofort ausgef hrt werden k nnen Sende und Empfangsfunktionen werden f r das bertragen gr erer Datenmengen genutzt siehe Abschnitt 3 2 und 3 3 1 und k nnen mit Direct I O oder Buffered I O arbeiten F r die Verwendung der Lese und Schreibfunktionen zum Zugriff auf die FPGA Register siehe 3 3 3 Funktion Beschreibung rasclib_resource_reserve reserviert eine bestimmte Anzahl von FPGAs rasclib_resource_configure programmiert die reservierten FPGAs mit dem angegebe nen Bitstream rasclib_cop_open signalisiert der rasclib dass ein FPGA mit angegebenem Algorithmus genutzt werden soll und gibt den Deskriptor des verwendeten FPGAs zur ck rasclib_cop_reg_write schickt einen Wert an ein angegebenes FPGA Register rasclib_cop_send sendet Daten an den FPGA Warteliste rasclib_cop_go startet den FPGA Algorithmus rasclib_cop_receive empf ngt Daten vom FPGA Ausgangs Puffer Warteliste rasclib_cop_reg_read liest einen Wert aus einem angegebenen FPGA Register rasclib_cop_commit sendet alle in der Warteliste eingereihten Befehle rasclib_cop_wait
93. er Grafikkarten an gepasst Field Programmable Gate Arrays FPGAs bieten mit der Beschreibung von Hardware einen anderen Ansatz welcher abh ngig von der Problemstellung eine effizientere Verarbeitung erm glicht Gemessen an der Performance k nnen Hardware Beschleuniger zudem eine deutlich geringere Leis tungsaufnahme als CPUs erreichen wodurch auch die Betriebskosten sinken FPGAs erlauben durch die hohe Anzahl von frei programmierbaren Logikbl cken eine sehr feingranulare Parallelverarbeitung und bieten im Vergleich zu ASICs den zus tzlichen Vorteil die Hardware an verschiedene Probleme anpassen zu k nnen Zur Programmierung von FPGAs gibt es verschiedene Ans tze Hardwarebeschrei bungssprachen VHDL Verilog Hochsprachen z B Handel C Impulse C Mitrion C und graphische Tools z B DSPLogic RC Toolbox Die Qualit t der L sung ist mitunter sehr verschieden und soll in dieser Arbeit anhand von Benchmarks und Beispielanwendungen in Mitrion C und VHDL verglichen werden SGI RASC dient dabei als Programmierplattform und wird hinsichtlich ihrer Leistungsf higkeit evaluiert Abstract Todays High Performance Computing uses next to massively concurrent processing and respectively parallel programming additional hardware to speed up applications Hence an algorithm is adapted to hardware e g microprocessors or graphics processing units GPUs as a sequence of instructions soft ware Field Programmable Gate Arrays FPGAs offer a to
94. er Sprachversion language version specifier beginnen Diese bestimmt die Regeln des Parsers die Semantik einiger integrierter Funktionen Daten typen und die Verf gbarkeit von syntaktischen Konstrukten Der Mitrion C Compiler unterst tzt alle vorherigen Versionen solange die Sprachversion im Quelltext angegeben wird Ein Mitrion C Programm wird durch die Abarbeitung der main Funktion ausgef hrt Ihr werden sog Instance Token f r die verwendeten Speicherb nke bergeben Als R ckgabewert liefert sie die finalen Instance Token nachdem alle Zugriffe durchgef hrt wurden Um Makros zu benutzen ruft der Mitrion C Compiler den C Preprozessor auf Include Direktiven d rfen nur au erhalb von Funktionen stehen Die Verwendung von include f r externe nicht Mitrion C Dateien ist f r die gemeinsame Verwendung von Makros in Mitrion C und Host Programm sinnvoll Mitrion C arbeitet mit einem eigenem API welches auf RASCAL siehe 3 4 1 aufbaut um einige Funk tionen erleichtert und an anderer Stelle erweitert wurde Abbildung 4 2 zeigt berblicksweise wie sich Mitrion in SGI RASC integriert Mitrion C ist keine Hardwarebeschreibungssprache sondern eine implizit parallele Programmierspra Host SRAM bank A SRAM bank B Sy Tesch SRAM bank C RC100 FPGA Modul Abbildung 4 2 Integration von Mitrion in SGI RASC vgl MitO8a 4 1 MITRION SDK VON MITRIONICS 39 che die dem Entwickler die M glichkeit geben
95. er of the algorithm to be loaded to the FPGA private final String alg_name private OutputStream out private InputStream in 25 performance evaluation private long starttime private long subboards 30 private JRasc int hdl String alg int inputBytes int outputBytes this hdl hdl this alg_name alg this inputBytes inputBytes this outputBytes outputBytes 35 this starttime new Date getTime this subboards 0 private static native int reserveFPGA String alg 40 private static native int freeFPGA int cop_desc String alg private static native int sendByteArray int cop_desc byte input private static native int recvByteArray int cop_desc byte output 45 Reserve an FPGA and return or representing JRasc instance x param alg the algorithm to be loaded x param inputBytes the paket size in bytes to be send x param outputBytes the paket size in bytes to be received x throws JRascException on failure 50 x throws JRascException final int fd reserveFPGA alg 55 if fd lt 0 throw new JRascException fd return new JRasc fd alg inputBytes outputBytes 60 xx Releases the RASC device x return 0 if successfully or error code public int free 65 return freeFPGA this hdl this alg_name xx Returns an OutputStream to send data to RASC return an OutputStream 70 public synchronized OutputStream getOutputStream final OutputSt
96. erden Optional k nnen Parameter wie der Syntheseaufwand Ausgabe und tempor res Datenverzeichnis auch in einer Benutzeroberfl che eingestellt werden Der Nutzer hat auf die Paramter der Hardware Synthese keinen direkten Einfluss Kann f r den gesamten Prozess aber zwischen drei Aufwandsstufen w hlen Dies ist vorallem ohne Hintergrundwissen ber die zugrundelie gende Hardware einfach zu entscheiden aber f r erfahrene Benutzer rgerlich gerade wenn ein Design nur knapp nicht geroutet werden konnte Eine genauere Anpassung ist nur auf einem Umweg zu er reichen wobei die Mitrion Anwendung zu Beginn der Synthese abgebrochen wird und die tempor ren Dateien im RASC Arbeitsablauf weiterverarbeitet werden z B mit einem Makefile Dieser wird bei der Verwendung von VHDL genutzt und erm glicht eine genaue Anpassung der Hardware Synthese Ein Makefile und eine weitere Datei in welcher die High Level Synthese Optionen aufgelistet sind die nen dazu Zudem wird neben ISE mit Synplify Pro ein zweites Synthese Tool unterst tzt Mitrion nutzt ausschlie lich ISE W hrend der RASC Arbeitsablauf zu keinem Zeitpunkt mehr als acht GByte ben tigt berschreitet Mitrion diese Grenze bei gro en Designs und kann dementsprechend nicht mehr auf kleinen Systemen mit weniger Hautspeicher in akzeptabler Zeit ausgef hrt werden Entwicklungsumgebungen z B Xilinx ISE und Editoren mit Syntax Hervorhebung erleichtern den Ent wurfsprozess mit VHDL Die in f
97. erden muss ber eine foreach Schleife werden die Werte verarbeitet wobei die Funktionen memread und memwrite den 56 5 FALLBEISPIELE 0lMitrion C 1 5 Options cpp alg name testsramitc alg id 4242 alg ver 2 define SIZE 524288 define SRAM mem bits 128 SIZE SRAM SRAM main SRAM sramO SRAM sraml uint 64 inc_val sramO_done sraml_done foreach i in lt 0 SIZE 1 gt inl128 sramO_rd memread sram0O i uint 16 8 inl6 int28 10 uint 16 in16_0 inl6 0 inc_val uint 16 inl6_4 inl6 4 inc_val bits 128 result inl6_0 inl6 1 inl6 2 inl6 3 inl6_4 inl6 5 inl6 6 inl6 7 sraml_wr memwrite sraml i result 15 sramO_rd sraml_wr sramO_done sraml_done Auflistung 5 1 Mitrion C Programm zum Test der SRAM Anbindung indizierten Zugriff auf den SRAM erm glichen Zwei 16 Bit Additionen auf den oberen und unteren 64 Bit der bergebenen Werte werden als einzige Datenmanipulation durchgef hrt und dienen sp ter der berpr fung ob die Daten durch den FPGA korrekt verarbeitet wurden Hierzu wird der aus dem SRAM gelesene 128 Bit Wert in einen Vektor aus acht 16 Bit Werten unterteilt und die unteren 16 Bit eines aus dem Host Programm bergebenen Parameters Nutzung eines Algorithm Defined Register auf das erste und f nfte Vektorelement addiert Die Reduzierung der Addition auf 16 Bit vereinfacht die Verdrahtung des Algorithmuskerns Schlie lich
98. erwendeten ADRs verh lt kann die Anzahl dieser ber einen vom Host bestimmbaren Parameter eingestellt werden Ein Auschnitt aus der Hostanwendung ist in Listing A 7 aufgef hrt Da die ADRs nicht gleichzeitg von den Core Services beschrieben werden wird immer der Wert eines gerade vom Host ver nderten Registers in einem FIFO gepuffert Ist dieser nicht leer werden die enthaltenen Werte in die Ausgangsregister geschrieben Enthalten alle aktuelle Werte wird zus tzlich einem Debug Register diese Information mit geteilt welche der Host durch Polling periodische Anfragen abrufen kann Damit kann sich sowohl 62 5 FALLBEISPIELE verwendete Register 512 x 64Bit Block RAM FIFO Register aktualisiert Register gelesen Abbildung 5 4 Memory Mapped Registers Kommunikationsschema der Algorithmus als auch der Host ber den Zustand der Register informieren Das Prinzip der Beispiel Implementierung ist schematisch in Abbildung 5 4 dargestellt In diesem Entwurf wird ein mit dem Xilinx Core Generator erstellter 512 Werte tiefer 64 Bit First Word Fall Through Block RAM FIFO als Puffer genutzt Zudem werden Z hler verwendet um die Latenz zwischen Register Aktualisierungen und Register Auslesevorg ngen zu messen Mit dem Host Programm kann diese dann ber Debug Register ausgelesen werden Um weitere Ressourcen einzusparen w re es m glich die selben Register als Ein und Ausgang zu ver wenden Allerdings m
99. etzung abgebrochen W hrend der Tests fiel auf dass Mitrion 200448 anstel le von 178176 auf dem Virtex 4 LX200 verf gbaren Flipflops f r die Absch tzung verwendet aus Mitri on Debug Ausgaben die prozentualen Angaben der realen Umsetzung jedoch recht nahe kamen Bei der Verwendung einer HDL kann die Hardware Synthese ber die vom Algorithmus Konfigurations Tool erzeugten und voreingestellten Konfigurationsdateien angepasst werden Damit k nnen f r die Synthese das Technologie Mapping und die Plazierung und Verdrahtung unabh ngig voneinander Einstellungen vorgenommen werden welche mitunter starken Einfluss auf die Umsetzung in die entsprechende Ziel technologie haben k nnen Dieses Optimierungspotenzial kann auch mit Mitrion genutzt werden indem die generierten Dateien angepasst und anschlie end mit der RASC Tool Chain verarbeitet werden Um die Datendurchsatzmessungen der Mitrion und VHDL Implementierungen gut vergleichen zu k n nen wurde zu jeder Kommunikationsvariante ein Host Programm mit dem RASC API siehe geschrieben welchem ber Parameter die zu verwendende Implementierung und die Gr e der zu sen denden Daten mitgeteilt werden Gro e bertragungsraten und geringe Latenzzeiten werden genau dann erreicht wenn das Host Programm auf einem zum RC100 Blade topologisch gesehen nahen CPU ausge f hrt wird Mit dplace wurde das Host Programm mit einer festen Datenmenge auf allen frei verf gba ren CPUs 124 ausgef hrt un
100. ewonne nen Ergebnisse und Erfahrungen ausgewertet Als Kriterien dienen die quantifizierbaren Metriken Ent wicklungszeit und Performance und zus tzlich der Ease of Use die Debugging M glichkeiten und die Fehleranf lligkeit In Abschnitt 6 1 wird zuvor noch untersucht welche Anwendungen zur Beschleu nigung durch FPGA basierte Systeme geeignet sind und welches Beschleunigungspotenzial theoretisch vorhanden ist Als Ergebnis der Auswertung wird in Abschnitt 6 3 betrachtet inwiefern sich der Imple mentierungsaufwand bei den erreichten Ergebnissen mit Mitrion C und VHDL rechtfertigt und in wel chem Verh ltnis Entwicklungszeit und Performance stehen Schlie lich werden in Abschnitt 6 4M ngel von SGI RASC angegeben und Verbesserungsvorschl ge gemacht 6 1 Anwendungsbeschleunigung durch FPGAs berlicherweise werden durch Zusatz Hardware keine kompletten Anwendungen beschleunigt sondern nur Routinen oder Algorithmen welche die Gesamtlaufzeit dominieren Um das Beschleunigungspo tenzial und damit die erreichbare Performance ermitteln zu k nnen m ssen vor der Umsetzung einige Faktoren untersucht werden e Vorhandensein von Schl sselroutinen e Intensit t der Berechnung Verh ltnis von Berechnungen zu Kommunikation e Datenformat Datenorganisation Datentransfer zwischen Host und FPGA Bereitstellungsaufwand e Spezialoperationen z B Flie kommaoperationen oder spezielle mathematische Operationen Ein nicht zu vernachl ssigender Fakt
101. f r die Simulation integrierter Schaltungen zu entwerfen deckt der Sprachumfang von VHDL heute alle w hrend des Entwurfsvorgangs anfallenden Beschreibungen der Schaltung ab VHDL erlaubt die Beschreibung von der Systemebene bis hin zur Gatterebene Digitale Schaltungen bestehen aus Kombinatorik und Speicherelementen Um beides f r reale Hardware nachzubilden ist die grundlegende Denkweise sehr verschieden zu blichen Programmiersprachen wie z B C oder Java VHDL ist eine datengetriebene Sprache in der nicht wie bei anderen prozeduralen Programmiersprachen die Reihenfolge der Befehlsausf hrung im Mittelpunkt steht Komplexe Designs werden durch strukturellen Entwurf hierarchisch aufgebaut Dies geschieht bei VHDL ber Komponenten welche Teil einer bergeordneten Struktureinheit sind Die Komplexit t einzelner Einheiten engl entities Kann von einfachen Gattern bis hin zu vollst ndigen Prozessorkernen reichen 46 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM Sie k nnen Verhalten Datenfluss und Strukturbeschreibungen beinhalten wobei in VHDL Schnittstelle und Implementierung strikt voneinander getrennt werden Eine VHDL Implementierung besteht im wesentlichen aus einer Menge von Prozessen die gleichzeitig abgearbeitet werden und nebenl ufigen Anweisungen welche kombinatorische Logik beschreiben Pro zesse bilden komplexe nebenl ufige Anweisungen wobei die Reihenfolge der Anweisungen innerhalb eines Prozesses v
102. g_write cop_desc fat_in fatin arguments adr_used RASCLIB_IMMED_CMD if res RASCLIB_ SUCCESS fprintf stderr reg write of fat_in failed at d d n __LINE__ res rasclib_perror reg write of fat_in res return 1 rasclib_cop_commit cop_desc NULL fatin fatin targuments adr_used Receive values from RASC FPGA for i 0 i lt arguments fifo arguments adr_used i do polling or not if arguments sync TRUE Wait until all output registers are valid do rasclib_cop_reg_read cop_desc rasc_out_vld amp rasc_out_vld 1 RASCLIB_IMMED_CMD rasclib_cop_commit cop_desc NULL while rasc_out_vld 1 Read Fat Register Output rasclib_cop_reg_read cop_desc fat_out fatout arguments adr_used RASCLIB_IMMED_CMD rasclib_cop_commit cop_desc NULL fatout fatouttarguments adr_used end gtod printf Sf MByte s f MiByte throughput float arguments cycles arguments num_bytes end start 1000000 0 float arguments cycles arguments num_bytes end start 1024 1024 printf Communication f sec n float end start rasclib_cop_reg_read cop_desc debugl amp debug rasclib_cop_reg_read cop_desc debug2 amp debug rasclib_cop_reg_read cop_desc debug3 amp debug rasclib_cop_reg_read cop_desc debug4 amp debug rasclib_cop_reg_read cop_desc debug5 amp debug rasclib_cop_reg_read cop_desc debug6
103. graph f r ein Teilproblem ist im Anhang A 13 zu finden und gibt die kritischen WHILE Schleife mit einer Latenz von 15 Takten an F r die gleichzeitige Berechnung von 20 Test Vorbelegungen ben tigte die daraus entstandene Hardware Umsetzung fast drei Stunden VHDL Umsetzung ben tigte knapp 13 Minuten und es konnten nur etwa 20 Teilprobleme auf einem FPGA gleichzeitig verarbeitet werden Zu beachten ist dass die Vorbelegung mit der l ngsten Berechnung die dominierende ist und damit die Gesamtdauer bestimmt Dieses entt uschende Ergebnis welches langsamer als jeder Software Algorithmus war f hrte zu drei wesentlichen hardwarespezifischen Optimierungen vgl Quellcode A 14 Schreib und Leseoperationen der Blockierungsvektoren wurden zu einer Operation zusammengefasst was zum einen Block RAM Ressourcen einsparen konnte und zum anderen die Latenz der Schleife verringerte Desweiteren wur den die ben tigten Bitbreiten mittels Parametern an die Problemgr e angepasst was wiederum FPGA Ressourcen einsparen konnte Als zus tzliche Optimierung wurden die Anpassung der Blockierung und des n chsten freien Feldes in einer Spalte aus der innersten Bedingungsanweisung herausgezogen und in 78 5 FALLBEISPIELE Summary Bandwidth Graph ROOT 6 0 ch 6 rch 6 BW limited body ch 6 rch 6 1 iterations 1 5 Env main foreach lt 1 gt 1 1 0 ch 1 rch
104. gsm g lichkeiten wodurch sich auch die Entwicklungszeit deutlich verl ngern kann In Mitrion C entstehen Optimierungen h ufig durch Ausprobieren und anschlie ender Bewertung ob eine Verbesserung erreicht wurde Dies kommt durch das Compiler generierte Design welches sich durch geringe Modifikationen des Mitrion C Codes stark ver ndern kann Gute Implementierungen und Optimierungen basieren in beiden Sprachen jedoch meistens auf Erfahrungswerten F r beide Programmierm glichkeiten kommt zur Algorithmusimplementierung noch der Zeitaufwand f r die Hardware Synthese hinzu welche f r die RASC Plattform etwa eine Stunde f r kleine und bis 6 2 VERGLEICH VON MITRION C UND VHDL RASC PROGRAMMIERUNG 85 zu mehreren Tagen f r gro e Designs in Anspruch nimmt An dieser Stelle muss noch erw hnt werden dass Timing Anforderungen innerhalb der RASC Core Services sehr lange Synthesezeiten hervorru fen k nnen w hrend der eigentliche Algorithmus bereits erfolgreich verdrahtet wurde Auch die vielen Komponenten aus denen der MVP aufgebaut ist erh hen die Synthesezeit zu vergleichbaren VHDL Designs F r Software ist der bersetzungsaufwand hingegen deutlich geringer und liegt f r in dieser Arbeit betrachtete Algorithmen im Millisekundenbereich Schlie lich muss der durch den FPGA beschleunigte Algorithmus noch in die Hostanwendung integriert werden Hierzu m ssen zum einen die zu bertragenden Daten bereitgestellt ggf umformatier
105. he Pfad mit zehn Takten Latenz abgelesen werden Ein Takt wird zur Auswertung der Schleifenbedingung ben tigt Es gibt drei wesentliche Unterschiede zur VHDL Implementierung Der VHDL Entwurf erm glicht die gleichzeitige Bearbeitung von ber 140 Teilproblemen und arbeitet mit einer baumf rmigen Verteilungs struktur um die L sungsinstanzen mit Vorplazierungen zu versorgen Die Mitrion C L sung weist jeder L sungsinstanz eine gewisse Anzahl von Vorbelegungen fest zu Durch die unterschiedliche Verarbei tungszeit von Teilproblemen dominiert immer eine L sungsinstanz mit der l ngsten Rechenzeit die Gesamtberechnung Dadurch geht etwa die H lfte der Verarbeitungsleistung verloren wenn pro Durch lauf jeder L ser nur ein Teilproblem berechnet Desweiteren sind die L sungsinstanzen in der VHDL Implementierung schneller Einen Optimierungsansatz bilden die Blockierungsvektoren und die noch freien Felder in einer Spal te welche wie in Software Algorithmen f r jede Spalte gespeichert werden Die derzeitige Mitrion C Implementierung nutzt an dieser Stelle Block RAM Das erh ht die Latenz der Schleife drastisch da zum 5 5 DAMENPROBLEM 79 RC100 FPGA 126MHz Virtex 4 LX160 143MHz Stratix Il EP2SGX90 160MHz Virtex 5 LX50T 163MHz Spartan 3 XC3S1000 92MHz RC 100 FPGA 100MHz Phenom 9850 2 5GHz Dual Core Opteron 2 4GHz Itanium2 1 6GHz 0 50 100 150 200 250 300 350 400 450 500 550 Teilprob
106. herkontroller nicht ben tigt wird Es stehen je vier DMA Streaming Engines f r lesenden und schreibenden Zugriff zur Verf gung Die Verwendung von mehreren Streaming Engines hat allerdings keinen Einfluss auf die Bandbreite Um Daten aus einem Stream zu lesen wird gewartet bis dieser bereit ist und anschlie end eine Le seanfrage read enable gestellt Der Schreibvorgang erfolgt ber eine Schreibaufforderung wenn der Stream bereit ist Die genaue Definition und Verwendung der Signale der Streaming DMA Engine ist in beschrieben Um zu erkennen dass ein Input Stream endet gibt es f r den Algorithmus zwei M glichkeiten Parameter mit der Anzahl der zu lesenden Werte ber ein Algorithm Defined Register bergeben oder das Stream In Complete Signal verwenden welches nach dem Senden des Streams ber einen entsprechenden Funktionsaufruf des RASC API gesendet werden kann Diese Kommunikationsvariante erm glicht es den FPGA als Streaming Koprozessor zu verwenden ohne einen gro en Overhead durch die Core Services zu ben tigen 3 3 3 Memory Mapped Registers F r eine Kommunikation mit kleineren Datenpaketen stehen spezielle 64 Bit Register zur Verf gung Vorgesehen f r die Fehlersuche stehen maximal 64 Debug Register zur Verf gung Diese k nnen durch den Algorithmus beschrieben und vom Host gelesen werden Die maximal 64 Algorithm Defined Regis ters ADRs sind flexibler einsetzbar und k nnen sowohl vom Algorithmus als auch vom Host
107. hnet werden 6 4 Verbesserungsans tze der RASC Plattform W hrend der Implementierung der Fallbeispiele und den entsprechenden Performance Messungen konn ten einige M ngel an SGIRASC festgestellt werden Zudem werden hier noch einige Verbesserungsvor schl ge angegeben welche den Ease of Use der gesamten Programmierplattform erh hen w rden Die Supplemental Clock ein zus tzlich durch die Core Services zur Verf gung gestelltes einstellba res Taktsignal kann aus Gr nden des Timings nur bedingt verwendet werden Eine typische Variante Daten zwischen Taktdom nen zu bertragen sind FIFOs mit asynchronem Schreib und Lesetakt Al lerdings Konnte mit solchen durch den Xilinx Fifo Generator v4 4 erstellten FIFOs das Timing nicht erreicht werden Alternativ wurde im Algorithmus selber eine DCM initialisiert und damit erfolgreich eine Taktanpassung vorgenommen Die Ger teverwaltung f r die FPGAs devmgr hat mitunter mehrere Wochen den Dienst untersagt Die falsche Angabe eines Dateinamens beim Hinzuf gen oder Ver ndern eines Algorithmus f hrte z B dazu 94 6 AUSWERTUNG dass die gesamte Registrierung und Abfrage der Algorithmen nicht mehr funktionierte Fehler wurde bereits behoben Zus tzlich traten andere bisher ungekl rte Fehler auf die mitunter den Absturz des kompletten Systems zur Folge hatten Um den mit einer HDL arbeitenden RASC Nutzer zu unterst tzen w re eine Testbench welche das Verhalten der Co
108. ider FPGAs verdoppelt den angegebenen Geschwindigkeits gewinn Sp und verringert die Amortisationszeiten t4 In dieser Arbeit konnten nur Beispiele mit recht kurzer Entwicklungszeit betrachtet werden wodurch schon nach geringer Laufzeit der beschleunigten Implementierung eine zeitliche Amortisierung auftritt Der Geschwindigkeitsgewinn ist au erdem ein Ma daf r wieviele Referenzsysteme betrieben werden m ssten um die gleiche Performance zu errei chen Um eine Wirtschaftlichkeitsuntersuchung durchzuf hren m ssten noch die Gesamtkosten Entwick lungsingenieur Beschaffungskosten des neuen Systems Energiekosten etc betrachtet und mit dem durchschnittlichen Gewinn in ein Verh ltnis gesetzt werden Aus diesen Ergebnissen und der durch schnittlichen Lebenserwartung eines HPC Systems von f nf Jahren kann dann abgesch tzt werden ob sich der Kauf des Beschleunigersystems rentiert Zudem m ssten schlecht quantifizierbare Faktoren wie z B Ease of Use Fehleranf lligkeit oder Qualit t der Implementierung der Vollst ndigkeit halber in die Untersuchung mit einflie en Zu beachten ist auch dass mehrere Systeme h here laufende Kosten verursachen Werden beispielsweise folgende Daten angenommen k nnen Energiekosten und CO2 AusstoB ber einen beliebigen Zeitraum berechnet werden e 15 Eurocent pro Kilowattstunde 15ct kWh e 400 Gramm CO3 Aussto pro Kilowattstunde 400g kWh e FPGAs mit 25 Watt Verlustleistung e Referenz CPUs
109. idx re32 bits 32 prel28 sol solveQueens uint 32 pre32 uint 128 psol watch psol memwrite sraml idx psoll28 sramOslices sramlslices sramdall sramlall et ney 1 gt 128 ANHANG A QUELLCODES 20 25 30 35 40 45 50 55 Auflistung A 15 Damenproblem Native C Funktionen include lt jni h gt include stdlib h include string h include rasc rasclib h for queens we are using bufferd IO because communication is not critical define IO_TYPE RASCLIB_BUFFERED_IO define ERROR_TIMEOUT 51 int freeFPGA int cop_desc char const xconst algID return value COP descriptor SUCCESS or error code FAILURE JNIEXPORT jint JNICALL Java_jrasc_JRasc_reserveFPGA JNIEnv xjenv jclass const clsJRasc jstring jalgname jint res jboolean iscopy char const xconst astring jenv gt GetStringUTFChars jenv jalgname amp iscopy char const xconst ustring getenv USER kxkkxkxkxkxxxxxxxxxxxxxxxx RASC FPGA Initialization KK KKK KKK KKK KKK KKK KKK KEK reserve one FPGA ustring or resrv_name can be any string if res rasclib_resource_reserve 1 ustring RASCLIB_SUCCESS if res rasclib_resource_configure astring 1 ustring RASCLIB_SUCCESS Jef get descriptor for reserved FPGA in res if res rasclib_cop_open astring IO_TYPE RASCLIB_SUCCESS unsign
110. igt werden um die meisten Designs routen zu k nnen Dies f hrt jedoch dazu dass Schaltungen die von der Anzahl der ben tigten Logik in einen FPGA passen w rden u U nicht geroutet werden k nnen Der typische FPGA Logikblock besteht aus einer Lookup Tabelle LUT mit vier Eing ngen und einem Flipflop wie Abbildung 2 2a zeigt Die meisten FPGAs besitzen zudem noch Carry Logik die schnelle 10 2 FPGAS Verbindungen zwischen mehreren CLBs und damit z B auch schnelle Additionen mit gro er Bitbreite erm glicht Eine 4 Eingangs LUT hat eine Kapazit t von 16 verschiedenen Kombinationen Die in ak tuellen FPGAs verwendete 6 Eingangs LUT erh ht die Kapazit t auf 64 verschiedene Kombinationen Soll beispielsweise ein Parit tsbit f r einen 32 Bit breiten Bus siehe Abbildung 2 3 berechnet werden sind 32 Eing nge ber XOR Verkniipfungen mit einem Ausgang zu verbinden Wird diese Operation mit einer 4 Eingangs LUT durchgef hrt werden elf LUTs und drei Logikebenen ben tigt Mit einer 6 Eingangs LUT l sst sich dieselbe Funktion mit nur sieben LUTs und zwei Logikebenen ausf hren Neben der Ressourceneinsparung durch die Verwendung von weniger LUTs wird auch der kritische Pfad k rzer und die ben tigten Verdrahtungsressourcen verringern sich Vorteile bieten sich dadurch prim r bei der Verwendung von Operationen mit gro er Bitbreite cout a i 7 O oO Kanal Pa emie bees Q 9 b Verbindung programmierbarer cin clk rs
111. ink ProPack und SGI RASC sind Marken von Silicon Graphics Inc in den U S und oder anderen L ndern weltweit Mitrion C Mitrion Virtual Processor und Mitrion Software Development Kit sind Marken und Mitrion ist eine eingetragene Marke von Mitrionics AB Impulse C ist eine Marke von Impulse Accelerated Technologies Inc Handel C ist eine Marke von Agility Design Solutions Inc Intel Itanium und Core2Duo sind Marken der Intel Corporation oder ihrer Tochtergesellschaften in den USA oder anderen L ndern Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist NVIDIA und CUDA sind Marken der NVIDIA Corporation in den USA oder anderen L ndern Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist Xilinx Virtex und Xilinx ISE sind Marken von Xilinx in den USA oder anderen L ndern Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist Synplify Pro ist eine Marke von Synplicity Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist AMD Opteron Phenom AthlonX2 Brook und Radeon sind Marken von Advanced Micro Devices Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist Linux ist eine eingetragene Marke von Linus Torvalds Dies gilt auch wenn es nicht explizit im Text gekennzeichnet ist Andere Marken oder Produktnamen sind Eigentum der jeweiligen Inhaber 134 Erkl rungen zum Urheberrecht
112. ipelines bei einer Taktfrequenz von 146 MHz um setzen Dabei werden Klartexte mit nur acht Buchstaben betrachtet Ab einer Anzahl von neun Pipeli nes bricht das Synthese Tool Xilinx ISE w hrend der High Level Synthese ohne Angabe eines Design Fehlers ab Die Tabelle 5 1 zeigt die Nutzung der FPGA Ressourcen laut den Angaben der Hardware Synthese nach der Plazierung Es kann also vermutet werden dass noch mindestens eine Pipeline bei funktionierender High Level Synthese implementierbar ist Anzahl der verwendeten Slices 67870 von 89088 76 Anzahl der Slice Flipflops 104808 von 178176 58 Anzahl der 4 Eingangs LUTs 118693 von 178176 66 Anzahl der FIFO16 RAMB 16s 58 von 336 17 Tabelle 5 1 MD5 Brute Force FPGA Ressourcen Nutzung VHDL 5 4 2 Implementierung mit Mitrion C Die Implementierung eines MD5 Brute Force Algorithmus in Mitrion C wurde bereits im Zusammen hang mit dem Technischen Report vorgenommen und lehnt sich insbesondere bei der Beschrei bung der MD5 Pipeline stark an den C Code der xyssl Bibliothek an In sind der Zustandspuffer der MD5 Summe und einige Stufen der Pipeline aufgelistet Die angegebenen Konstanten sind vom Al gorithmus vorgegeben Das Kernst ck des Algorithmus ist somit leicht in Mitrion C zu bertragen zumal die Datenabh ngigkeiten zwischen den einzelnen Zuweisungen automatisch gehandhabt werden in VHDL muss der Programmierer f r deren Einhaltung sorgen Wie im Quellcode Listing zu sehen
113. ipflop First In First Out Flie kommaoperationen pro Sekunde Field Programmable Gate Array Finite State Machine GNU Debugger General Matrix Multiply General Purpose Computation on Graphics Processing Unit Graphics Processing Unit General Packet Radio Service Graphical User Interface dt grafische Benutzeroberfl che Hardware Description Language High Performance Computing Input Output dt E A Eingabe Ausgabe Intellectual Property Lookup Tabelle Media Access Control Message Digest Algorithm 5 Memory Mapped Register Mitrion Virtual Processor Network Attached Storage Peripheral Component Interconnect Programmable Logic Device Random Access Memory dt Speicher mit wahlfreiem Zugriff Rekonfigurierbares Anwendungs Spezifisches Computing Storage Area Network SDK SGEMM SoC SRAM SSL TCL UART USB VHDL ZIH Software Development Kit Single Precision General Matrix Multiply System on a Chip Statischer RAM Secure Sockets Layer Tool Command Language Universal Asynchronous Receiver Transmitter Universal Serial Bus Very High Speed Integrated Circuit VHSIC Hardware Description Language HDL Zentrum f r Informationsdienste und Hochleistungsrechnen 1 Einleitung Das Hochleistungsrechnen engl high performance computing HPC hat die Grenze der sequentiellen Verarbeitung bereits vor Jahren erfahren und basiert heute auf massiver Parallelverarbeitung Dabei ist die akkumulierte Rechenlei
114. itung Die Unterschiede liegen in der Anzahl der frei programmierbaren Logikzellen den integrierten fest verdrahteten Spezialbl cken und der Menge an digitalen Signalverarbeitungsbl cken DSP Slices Zudem besitzt jede Plattform FPGA Modelle in verschiedener Gr e und Ausf hrung Die in dieser Arbeit verwendeten Virtex 4 LX FPGAs beinhalten die meisten frei programmierbaren Logikzellen der gesamten Virtex 4 FPGA Familie Xilinx untergliedert die Virtex 4 CLBs in vier sog Slices vgl Abbildungen 2 4 und Da wobei zwei davon ausschlie lich zur Umsetzung von Logik dienen w hrend die anderen Beiden au erdem als ver teilter Speicher oder Schieberegister verwendet werden k nnen Die Slices bestehen jeweils aus zwei 4 Input LUTs und zwei Flipflops womit die Verarbeitungsbreite eines CLBs auf maximal 64 Bit be schr nkt ist Die neueste Generation von Xilinx FPGAs die Virtex 6 Serie hat CLBs bestehend aus zwei Slices mit jeweils vier 6 Input LUTs und vier Flipflops siehe Xil09b was f r heutige Anwendungen von High End FPGAs eine effizientere Aufteilung sein soll Virtex 4 Chips werden aus 300 mm Wafern in 90 nm Technologie produziert w hrend neuere Virtex 6 FPGAs bereits in 40 nm Technologie hergestellt wer den Durch ein effizienteres Verbindungsnetzwerk und kleinere Strukturbreiten kann damit bei gleicher Taktfrequenz die Leistungsaufnahme der FPGAs verringert werden Die Speicherressourcen von Virtex 4 FPGAs reichen von 48
115. kation mit dem RC100 Blade wurde anhand von Mikro Benchmarks getestet und erreichte unter der Verwendung von Direct I O und Direct Streaming einen maximalen Da tendurchsatz von etwa 2 4 GByte s Die Messungen des Datendurchsatzes zwischen Host und SRAM erreichten mit 1 65 GByte s gerade die H lfte des theoretisch M glichen Der FPGA kann hingegen mit voller theoretischer Bandbreite mit dem SRAM kommunizieren was zu der Schlussfolgerung f hrt dass der Flaschenhals im Speicherkontroller der Core Services liegt Die Latenz von indizierten Speicherzu griffen des FPGA auf den lokalen SRAM wurde mit 80 ns gemessen Zus tzlich konnten die Memory Mapped Registers auf den Speicher des Hosts abgebildete FPGA Register neben der Parameter berga be und Debugging Zwecken auch als Variante der Daten bertragung verwendet werden Dadurch wurde die Anbindung der Damenproblem Implementierung an die Infrastruktur von Queens TUD erst m g lich und es konnte ein Beitrag zum Fortschritt des Projektes geleistet werden Alle Fallbeispiele wurden sowohl mit Mitrion C als auch mit VHDL auf die RASC Plattform portiert Basierend auf diesen Implementierungen wurden die verschiedenen Metriken Entwicklungszeit Ease 96 7 ZUSAMMENFASSUNG UND AUSBLICK of Use Fehleranf lligkeit Debugging M glichkeiten und Performance bewertet Mitrion C offenbarte dabei insbesondere Schw chen im Sprachumfang was bei betroffenen Algorithmen zu einer vergleichs weise schlechte
116. ktor kommt aber dennoch hinzu da jede L serinstanz verschiedene Teilprobleme mit unterschiedlichem Rechenaufwand berechnet Uber einen ausreichend langen Zeitraum sollte dieser Faktor aber vernachl ssigbar sein Abbildung B 11 zeigt die Messergebnis se f r einen Zeitraum von zw lf Stunden Test Vorbelegungen wurden genutzt um die Mitrion C und VHDL Implementierung vergleichen zu k nnen wodurch letztendlich auch ein Gesamtvergleich aller Implementierungen m glich wird 80 5 FALLBEISPIELE Das VHDL Design zur Berechnung des 26 Damenproblems erreicht insbesondere auf den gro en FPGAs deutliche Geschwindigkeitsgewinne im Vergleich zu auf CPUs laufenden Software L sungen Die Im plementierung mit Mitrion ist in etwa so schnell wie der AMD Phenom Vierkern Prozessor Wenn die Optimierungsvorschl ge aus Abschnitt 5 5 3 letzter Absatz umgesetzt w rden w re wom glich noch ein Faktor zwei bis drei an Geschwindigkeitsgewinn denkbar dennoch wird das Mitrion Design weit hinter einer VHDL Implementierung des Damenproblems liegen 81 6 Auswertung In den vorangegangenen Kapiteln wurde die RASC Plattform genauer untersucht und anhand von Fall beispielen Praxistests durchgefiihrt Auf diesen Fakten und Messergebnissen aufbauend soll tiberblicks weise das Leistungsverm gen des Systems eingesch tzt und auch Schw chen aufgedeckt werden Zudem werden in Abschnitt 6 2 die mit den beiden Programmierm glichkeiten Mitrion C und VHDL g
117. l uint 32 uint 32 0 lt lt N bhps bups bdps mem_slt4 memwrite mem_slt3 ipl sslipl 85 mem_loop2 tup mem_bht2 mem_but2 mem_bdt2 mem_slt4 ip1 cnt0 mem_loop2 else Count Solution and proceed with preceding Column uint 46 cntOn cntO 1 90 watch cntOn int 32 inn N 2 inn cntOn mem_loop1 itmp cnttmp mem_looptmp cnt0O mem_loop 95 mem_bh_last mem_bu_last mem bd Last mem_sl_last untup mem_al cnt ExtRAM ExtRAM main ExtRAM sram0O ExtRAM sram1 read pre placements from SRAMO 100 sramOpre listpre foreach idx in lt 0 PREPLACEMENTS 1 gt prel28 sram0_pre memread sram0 idx bits 32 pre32 bits 32 prel28 sram0_pre pre32 define number of slices and sequential execution 105 prepls2 reshape listpre lt SLICES gt lt SEQ_PRE gt prepls3 reformat prepls2 SLICES lt SEQ_PRE gt sramlall foreach pres_elem in prepls3 by idx sramlslices foreach pre_elem in pres_elem by idx_pre uint 46 psol solveQueens uint 32 pre_elem 110 psoll28 uint 128 psol sramlps memwrite sraml idx SEQ_PRE idx_pre psol128 watch psol sramlps sramlslices 115 SramOpre sramlall 20 A 5 DAMENPROBLEM ROOT Auflistung A 13 Bandbreitengraph Damenproblem Mitrion C 1 Summary 6 0 ch iterations 1 d
118. l RASCLIB_IMMED_CMD rasclib_algorithm_commit al_desc NULL printf mem2_latency vector 0x 1x debugl printf busy error vector 0x 1x n debug2 latency unsigned int debugl amp 0xFFFO00000 gt gt 24 debugl amp 0xFFFO00 gt gt 12 printf SRAM access latency 1 d clock cycles d ns 200MHz n latency latency 5 buffers_fr arguments io rasclib_huge_clear return 0 allokate memory depending on IO method int buffers_make struct cargs xargs if RASCLIB_DIRECT_IO xargs io in unsigned long rasclib_huge_alloc x args num_bytes out unsigned long zl rasclib_huge_alloc xargs num_bytes if in NULL out NULL buffers_free args io rasclib_huge_clear return 1 else in unsigned long malloc xargs num_bytes out unsigned long malloc args num_bytes if in NULL out NULL buffers_free xargs io return 1 return 0 void buffers_free int iomethod if RASCLIB_DIRECT_IO iomethod rasclib_huge_free in rasclib_huge_free out else free in free out 112 ANHANG A QUELLCODES A 2 Direct Streaming Auflistung A A Direct Streaming VHDL Implementierung 0 extractor CS 2 2 extractor VERSION 1 3 extractor STREAM_IN strm_in 0 0 extractor STREAM_OUT strm_out 0 0 extractor REG_IN inc_val 16 u alg_def_reg 0 15 0
119. l in beiden F llen Mitrion C VHDL als Vergleich dienen wobei auf wesentliche Unterschiede zwischen beiden Programmierm glichkeiten direkt eingegangen wird Zu Be ginn des Kapitels werden noch begrenzende Faktoren f r die Parallelit t eines Systems aufgezeigt zumal performante Probleml sungen mit SGI RASC auf einen hohen Grad an Parallelverarbeitung angewiesen sind Anforderungen der Parallelverarbeitung 1 Verarbeitungseinheiten Ein begrenzender Faktor f r die Parallelit t eines Systems ist die Anzahl der verf gbaren Verar beitungseinheiten Jede dieser Verarbeitungseinheiten ben tigt entsprechend ihrer Aufgabe eine gewisse Fl che auf dem Chip Einfache Operationen ben tigen weniger Fl che und k nnen damit in gr erer Anzahl auf den Chip gebracht werden wodurch sich die m gliche Parallelverarbeitung erh ht 2 Datenabh ngigkeiten Ein weiterer Faktor der die Parallelit t eines Systems begrenzt ist die Anzahl der unabh ngig voneinander verarbeitbaren Daten Zwei Daten sind genau dann unabh ngig voneinander wenn weder das eine noch das andere Datum auf die Berechnung des zweiten Datums einen Einfluss hat Ist eine Abh ngigkeit zwischen zwei Daten vorhanden so k nnen sie nur sequentiell abgearbeitet 34 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM werden Viele Datenabh ngigkeiten f hren zu einer Verminderung der Parallelverarbeitung und damit zu einer Verl ngerung der Laufzeit 3 Simul
120. lbiert zudem noch die zu berechnenden Teilprobleme durch die sich an der Mitteldiagonalen spiegelnden paarweise identischen L sungen Die sechs Damen der Vorplazierung k nnen in 25 204 802 Konfigurationen aufgestellt werden wodurch sich die daraus ergebenden Teilpro bleme ber L sungsinstanzen engl Solver unabh ngig voneinander berechnen lassen 5 5 2 VHDL Implementierung Das VHDL Design basiert wie alle schnellen Algorithmen zur L sung des Damenproblems auf dem Backtracking Verfahren Um m glichst feingranulare Parallelit t zu erreichen und die Dauer der L sung einzelner Teilprobleme gering zu halten wurde eine an die Hardware FPGA angepasste Imple mentierung vorgenommen siehe PNSO09 In Software und auch bei der vorgenommenen Mitrion C Implementierung wird mit Feldern engl arrays von Blockierungsvektoren drei pro Spalte gearbeitet w hrend sich f r die Hardware Umsetzung drei globale Vektoren f r diagonal steigende horizontale und diagonal fallende Blockierungen als effizienter erwiesen haben Damit gilt immer nur eine Spalte als aktiv Bei einem R cksprung wird dann nicht die f r diese Spalte bereits erzeugte Blockierung aus dem Speicher geladen sondern durch Anpassung der globalen Blockierung erneut erzeugt In Hardware ist das in einem Takt m glich und kann ber Schieberegister mit geringem Ressourcenaufwand realisiert werden W hrend fr here Hardware Solver Komponent zur Berechnung eines Teilproblems
121. le z B PCI X Karte ber das NUMAIink4 Netzwerk in den verteilten Hauptspeicher auf den Prozessorknoten zu transportieren Durch den modularen Aufbau der Altix 4700 k nnen auch Special Purpose Blades in das System inte griert werden Dies sind zum einen ber PCI Express angeschlossene Grafikkarten zur Beschleunigung 3 2 SGI RC100 FPGA BLADE 23 von Anwendungen durch GPUs Graphics Processing Units und zum anderen sog RASC Blades Letz tere sind mit FPGAs ausgestattet und erm glichen eine an das Problem angepasste rekonfigurierbare Hardware zu nutzen um Anwendungen auszuf hren siehe Abschnitt 3 2 Die am ZIH installierte Altix 4700 besteht aus 32 Racks und verf gt insgesamt ber 2048 Intel Itani um II Montecito Cores und 6 5 TB Hauptspeicher Das System ist in f nf Partitionen aufgeteilt eine Login Partition drei Rechen Partitionen und eine interaktive Partition mit Grafik und FPGA Knoten Die theoretische Spitzenleistung des Systems betr gt 13 1 TFlop s und belegte zum Zeitpunkt der Inbe triebnahme November 2006 mit gemessenen 11 9 TFlop s Rang 49 unter den 500 schnellsten Rechnern weltweit 3 2 SGI RC100 FPGA Blade Ein SGI RC100 Blade stellt dem Hostsystem zwei anwenderprogrammierbare FPGAs zur Verf gung und ist schematisch gesehen wie in Abbildung 3 2 aufgebaut Es besteht neben den zwei Algorithmen FPGAs mit je f nf 8 MByte QDR II SRAM DIMMS aus zwei TIO ASICs und einem Loader FPGA Der Konfigur
122. leme pro Stunde Abbildung 5 11 26 Damenproblem Leistungsvergleich 10 Stunden von FPGAs und CPUs einen die parallele Ausf hrung von Bedingungspr fung und den beiden Zweigen nicht m glich ist und zum anderen die Zugriffe auf den Block RAM bei Mitrion mehr Zeit als auf normale Register kosten Die Block RAM Nutzung senkt allerdings auch den Bedarf an Flipflops wodurch mehr L sungsinstanzen implementiert werden k nnen Globale Blockierungsvektoren und eine andere L sung zur Ermittlung der bereits gesetzten Damen w ren Verbesserungsans tze Allerdings m ssten alle Block RAM Zugriffe in der WHILE Schleife vermieden werden um eine signifikante Leistungssteigerung zu erzielen An dieser Stelle konnte der Mitrion Support auch keine echten Optimierungsm glichkeiten zur Erh hung der Verarbeitungsleistung finden 5 5 4 Performance Da die Berechnungszeit eines Teilproblems stark von der zugeh rigen Vorplatzierung abh ngt ist es schwierig genaue Vergleiche zwischen Implementierungen zu ziehen Der Damenproblem VHDL Core l uft auf den Virtex 4 FPGAs des RC100 Blades meist ber einen l ngeren Zeitraum und ist an die Infrastruktur des Queens TUD Projektes angeschlossen Ein dem Algorithmus von Jeff Somers hnli ches C Programm wird genutzt um zeitweise Prozessoren parallel dazu rechnen zu lassen Damit kann die Performance von CPUs und der VHDL Implementierung der RC100 FPGAs und anderer FPGAs gut verglichen werden Ein gewisser Zufallsfa
123. lle oder stark begrenzt parallele Aufga ben weiterhin auf Mikroprozessoren gel st werden w hrend berechnungsintensive hochparallele Arbeit auf Hardware Beschleuniger ausgelagert wird Im Vergleich zur Parallelverarbeitung auf mehreren Mikroprozessoren erm glichen FPGAs eine sehr feingranulare Parallelisierung W hrend typische Anwendungsbeschleunigung eine Anpassung an die Hardware z B an Befehlssatzerweiterungen erfordert wird bei FPGAs die Hardware an das Problem angepasst und kann binnen Millisekunden umkonfiguriert werden Heutige FPGAs besitzen genug Lo gikelemente um eine Vielzahl von 64 Bit Verarbeitungseinheiten z B Addierer Multiplizierer etc zu integrieren wobei es dem Programmierer obliegt andere Bitbreiten und spezialisierte problemspezifi sche Operationen zu verwenden 6 1 EINLEITUNG Aktuelle HPC Systeme arbeiten mit einer Vielzahl von Mikroprozessoren welche durch ein Netzwerk mit hoher Bandbreite und geringer Latenz miteinander verbunden sind W hrend FPGAs in eingebetteten Systemen u a Verwendung finden um mehrere Bauteile durch ein einziges zu ersetzen werden im HPC mehrere FPGAs auf einer Platine plaziert und an ein Mikroprozessor basiertes System angeschlossen Die SGI RASC Technologie f r Rekonfigurierbares Anwendungs Spezifisches Computing integriert mit dem RC100 Blade FPGAs als Hardware Beschleuniger in HPC Systeme der Altix 450 4700 Serie Welche Anwendungen sich beschleunigen lassen und o
124. lt md5_logic12 Dinc i 6 Dina itl 2 Dinb i 4 Dind it l 0 ramout i 4 2 30 Dinc itl 0 lt md5_shift2 tmp i 4 2 shifts 6 Dind i 1 1 Dinhex i 4 2 FOR s IN 0 TO 5 LOOP Dinc i l stl lt Dinc itl ai END LOOP 35 stages b4 to b7 tmp i 4 3 lt md5_logicl2 Dinb i 6 Dind it1l 2 Dina i 1 4 Dinc i 1l 0 ramout i 4 3 Dinb itl 0 lt md5_shift2 tmp i 4 3 shifts 7 Dinc it 1 1 Dinhex i 4 3 FOR s IN 0 TO 5 LOOP Dinb i 1 s 1 lt Dinb i l s 40 END LOOP END LOOP stages 33 to 64 45 end if end process AA MD5 BRUTE FORCE 119 Auflistung A 9 MD5 Hash Vergleich in VHDL 0 hash comparison proc_cmp process clk begin if clk event and clk LI then rising edge eghash lt others gt 0 5 1st md5 checksum part available if pipe_vld 1 AND douthash 0 Din_hash 127 downto 96 then eghash 0 lt 1 end if rdy_part 0 lt eghash 0 10 2 clocks later if rdy_part 0 1 AND douthash 3 Din_hash 31 downto 0 then eghash 3 lt 1 end if rdy_part 1 lt eghash 3 15 4 clocks later if rdy_part 1 1 AND douthash 2 Din_hash 63 downto 32 then eghash 2 lt 1 end if rdy_part 2 lt eghash 2 20 6 clocks later if rdy_part 2 1 AND douthash 1 Din_hash 95 downto 64 then eghash 1 lt III end if end if 25 end
125. m glichen Plazierungen die den an gegebenen Anforderungen gen gen Bis heute ist keine Formel zur Berechnung des N Damenproblems bekannt Als obere Schranke f r die L sungsanzahl gilt jedoch N Fakult t N was die Anzahl f r N einander nicht bedrohender T rme ist Aus dem Mangel an einer Berechnungsformel zur Ermittlung der L sungen kommen anstelle dessen Al gorithmen zum Einsatz Die meisten schnellen Implementierungen arbeiten mit dem sog Backtracking Verfahren Dabei wird nach dem Versuch und Irrtum Prinzip engl trial and error vorgegangen d h es wird versucht eine erreichte Teill sung schrittweise zu einer Gesamtl sung auszubauen Kann eine Teil l sung nicht zu einer Gesamtl sung f hren wird der letzte Schritt r ckg ngig gemacht und stattdessen ein alternativer Weg verfolgt Es werden alle in Frage kommenden L sungswege ausprobiert und damit auch alle L sungen gefunden Backtracking arbeitet damit nach dem Prinzip der Tiefensuche Im Folgenden sollen der Algorithmus allgemein und die VHDL und Mitrion C Implementierung eines Backtracking Algorithmus vorgestellt werden An dieser Stelle soll weniger die exakte Umsetzung des 5 5 DAMENPROBLEM 13 Algorithmus in Hardware VHDL als dessen Prinzip und die Schnittstelle zu RASC betrachtet werden Anschlie end wird die erreichte Performance der einzelnen Implementierungen verglichen 5 5 1 Backtracking Algorithmus und Parallelisierung An dieser Stelle soll k
126. m Signalwert ein Ereignis zugeordnet Innerhalb einer Zeitscheibe hat jedes Signal einen festen Wert Da es sich um eine ereignisgetriebene Simulation von Si gnalen handelt brauchen f r eine nachfolgende Zeitscheibe nur Prozesse betrachtet zu werden in denen sich ein Signal aus ihrer Sensitivit tsliste oder einer wait Anweisung ge ndert hat Sowohl die Sensitivi t tsliste als auch wait Anweisungen bewirken dass Anweisungen innerhalb eines Prozesses sequenziell abgearbeitet und dadurch neue Ausgangswerte erzeugt werden Bei der Simulation von Hardware werden prinzipiell zwei Simulationsarten unterschieden Die reine Verhaltenssimulation engl behavioral simulation der beschriebenen Hardware in der die funktionalen Zusammenh nge der Schaltung gepr ft werden und die Simulation der fertig platzierten und verdrah teten Schaltung engl timing simulation Bei letzterer wird die Schaltung zun chst synthetisiert plat ziert und verdrahtet bevor aus der fertigen Schaltungsanordnung Netzliste mit Informationen ber die Verz gerungen die zugeh rigen Laufzeitinformationen entnommen werden Der Vorteil besteht hier in dem genaueren Modell um beispielsweise Zeitablaufprobleme in der Zielhardware bereits w hrend der Simulation erkennen zu k nnen Der wesentliche Nachteil besteht in dem damit verbundenen hohem Rechenaufwand und die im Vergleich zur Verhaltenssimulation lange Simulationszeit 4 2 HARDWARE ENTWICKLUNGSABLAUF 49 Weiter k
127. mber of ADRs polled if ctr_polled adr_used then 75 rasc_out_full lt 0 ctr_polled lt others gt 0 end if if fifo_vld 1 then 80 if rasc_out_full 0 then ctr rout lt ctr_rout 1 end if if ctr_rout adr_used 1 then rasc_out_full lt III 85 ctr_rout lt others gt 0 end if end if end if end if oul end process fifo_rd_en lt 1 when rasc out full 0 AND fifo_empty 0 else 0 manage output data proc_output process clk 95 begin if clk event and clk 1 then rising edge FOR i IN 0 to 15 LOOP adr_wr_data i lt fifo_dout 100 END LOOP adr_wr lt others gt 0 do not write to output registers if rasc_out_full 0 AND fifo_vld 1 then adr_wr conv_integer ctr_rout 3 downto 0 lt III 105 end if end if end process finish algorithm execution intiated by host 110 alg_done lt 1 when finish_alg 1 else 0 116 ANHANG A QUELLCODES Auflistung A 7 Messschleife Memory Mapped Registers 20 25 30 35 40 45 50 SS rasclib_cop_go cop_desc Start Bitstream Engine start gtod for ctr 0 ctr lt arguments cycles ctr unsigned long fatin unsigned long fatout fatin in fatout out for i 0 i lt xarguments fifo arguments adr_used i Send RASC FPGA Input res rasclib_cop_re
128. meist elementare Hardwarestrukturelemente direkt in VHDL abgebildet Signale dienen sowohl zur Zustandsspeicherung innerhalb der einzelnen Prozesse als auch zur Informations bermittlung zwischen Prozessen und Komponenten Die sog 2 Prozessmethode findet vor allem im synchronen FPGA Design Verwendung Die Komponentenarchitektur besteht dann nur noch aus zwei Prozessen Ein meist sehr komplexer rein kombinatorischer Prozess welcher den kom pletten Algorithmus und das Verfahren beinhaltet und ein recht einfacher getakteter Prozess welcher alle Register Zustandsspeicher beinhaltet Dar ber hinaus gibt es sprachliche Erweiterungen in Form von VHDL AMS mit welchen auch analo ge Systeme beschrieben werden k nnen Diese soll den Rahmen elektrischer Simulation verlassen und auch mechanische Elemente Sensoren und Aktoren modellieren um zu einer m glichst vollst ndigen Systemsimulation zu gelangen Mit VHDL ist es auch m glich nicht synthesef higen funktionalen Code zu schreiben Einige Anwei sungen sind nur f r die Simulation verwendbar und k nnen nicht in Hardware umgesetzt werden Nicht synthesef higer Code dient damit der Schaltungssimulation und wird in sog Testbenches beschrieben um die Umgebung der zu synthetisierenden Hardware zu simulieren Damit kann dann das Verhalten von z B Schnittstellenprotokollen getestet werden 48 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM 4 2 2 Simulation Die Simulation ist eine
129. men in der Automobilindustrie Sie erm glicht es Anwendungen sich an wechselnde Bedingungen anpassen zu k nnen ohne dass der komplette FPGA mit einem neuen Bitstream rekonfiguriert werden muss Auf FPGAs basierende L sungen erm glichen es mitunter Markteinf hrungszeiten stark zu verk rzen da das Silizium bereits gepr ft ist und kein langer Fertigungsprozess notwendig ist Der kostenintensive Entwicklungs und Fertigungsprozess von ASICs f hrt dazu dass FPGAs f r kleine und mittlere St ck zahlen kosteng nstiger sind Ab gr eren St ckzahlen macht sich der h here Einzelpreis von FPGAs jedoch bemerkbar Im Vergleich zu ASICs haben FPGAs einen h heren Leistungsbedarf und eine geringere Logikdichte ca zehnfacher Fl chenbedarf bei gleicher Technologie Wird jedoch der Leistungsbedarf moderner CPUs betrachtet sind FPGAs deutlich sparsamer Insbesondere bei einem auch im HPC an Relevanz gewin nenden Ma Performance pro Watt sind FPGAs bei geeigneter Algorithmen Wahl weitaus effizienter Allerdings stehen sie hier in direkter Konkurrenz zu anderen Hardware Beschleunigern z B ClearSpeed GPGPUs welche sehr gute Werte hinsichtlich dem Verh ltnis von Performance zu Leistungsaufnahme aufweisen Fest verdrahtete Logik wie ASICs und Mikroprozessoren erm glichen h here Taktfrequenzen als FPGAs Aktuell sind FPGAs mit bis zu 600 MHz verf gbar typisch sind jedoch 20 bis 250 MHz Die Flexibilit t von modernen Mikroprozesso
130. men zur Verf gung stehen FPGAs haben im Vergleich zu Mikropro zessoren mehrere Adressr ume deren Gr e und Typ schon w hrend der Programm bersetzung bekannt sind Au erdem besitzen FPGAs keine Caches welche auf Grund der gro en Anzahl frei definierbarer Register und der vorhandenen Block RAM Ressourcen ein Takt Zugriffslatenz auch nicht n tig sind Es gibt kein Statusregister oder hnliches und damit keine exakten Fehler wie Division durch Null oder Index au erhalb des Zahlenbereiches Die Fehlersuche auf FPGAs ist komplexer und es ist nicht m glich jede Variable zu jedem Zeit punkt auszulesen Zudem gibt es wenige Debugger zur Fehlersuche in FPGA Programmen Die Anwendungsentwicklung mit der Mitrion Plattform ist einem typischen Software Entwicklungszy klus hnlich Bei der Portierung auf ein anderes rekonfigurierbares Computersystem braucht der Nutzer nur Detailles bez glich der Organisation der Maschine anzupassen Der Mitrion C Quellcode bleibt un abh ngig von der Gr e der Geschwindigkeit und dem verf gbaren Speicher des FPGAs unver ndert 36 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM Quellcode anpassen kompilieren simulieren Mitrion Simulator Prozessor konfiguration Quellcode anpassen Synthese Place amp Route ausf hren C Mithal API Abbildung 4 1 Entwicklungszyklus Mitrion SDK auf SGI RASC vgl MitO8b und ist na
131. ments are start element and array length xjenv gt SetByteArrayRegion jenv jbarray 0 jb_length jbyte zl byteout return RASCLIB_ SUCCESS send byte array as 64Bit values to FPGA JNI jobject jobj jsiz jb_length xjenv EXPORT jint JNICALL Java_jrasc_JRasc_sendByteArray JNI jint jcop_desc jbyteArray jbarray gt GetArrayLength jenv jbarray Env jenv int ADR_SIZE jb_length ADR_BYTES jboolean isCopy signed char carray jenv gt GetByteArrayElements jenv jbarray amp isCopy int j int res unsigned long fat_in128 ADR_SIZE for j 0 j lt ADR_SIZE j does only work for unsigned long 64Bit e g IA64 fat_inl28 j unsigned long carray amp 0xff lt lt 56 unsigned long carray 1 amp Oxff lt lt 48 unsigned long carray 2 amp Oxff lt lt 40 130 ANHANG A QUELLCODES 120 125 130 135 140 145 150 155 unsigned long unsigned int unsigned int GE int x carray 7 x carray 3 amp Oxff lt lt 32 carray A amp Oxff lt lt 24 x carray 5 amp Oxff lt lt 16 carray 6 amp 0Oxff lt lt 8 xff OR AK na amp carrayt 8 Send RASC FPGA Input res rasclib_cop_reg_write jcop_desc in64 fat_in128 ADR_SIZE RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS return res
132. mmunika tionsvarianten betrifft Einige Ans tze wurden bereits in der Auswertung erl utert An dieser Stelle bieten sich nun Vergleiche zu anderen FPGA basierten Programmierplattformen an Sog In Socket Accelerators erm glichen z B eine engere Kopplung der Beschleuniger Chips und CPUs was geringere Latenzen und h here Bandbreiten erm glichen soll Zudem wurde mit Mitrion C nur eine Hochsprache untersucht welche FPGA Systeme als Zielplattform hat Handel C und Impulse C sind weitere Programmiersprachen welche die Nutzung von FPGA basierten Systemen verfolgen Diese ar beiten mit einer Teilmenge der C Funktionalit t und C Erweiterungen zum parallelen Entwurf Eine weitere Herausforderung betrifft die Portierung einer echten Anwendung nicht aus der internen For schung welche bereits Rechenzeit auf den am ZIH installierten Hochleistungsrechnern beansprucht Schlie lich sollte noch untersucht werden inwiefern dynamische partielle Rekonfiguration die Flexibi lit t von FPGAs erh ht und Nutzbarkeit im Bereich des Hochleistungsrechnen verbessert F r den zuk nftigen Erfolg FPGA basierter Systeme im Hochleistungsrechnen k nnte die OpenFPGA Initiative beitragen Diese wird von einer Vielzahl von Firmen und Organisationen unterst tzt und arbei tet an einem einheitlichen Industriestandard zur Integration von rekonfigurierbarer Technologie in leis tungsstarke Rechensysteme Eine allgemeine API Spezifikation soll anbieterunabh ngig und
133. mmunikation ist keine Adressberechnung notwendig da die Daten der Reihenfolge nach abgearbeitet werden Mit dem optional verwendba ren Stream In Complete Signal k nnen zudem ohne die bergabe zus tzlicher Parameter aus Sicht der VHDL Implementierung beliebig lange Streams verarbeitet werden W hrend die eigentliche Operation zwei 16 Bit Additionen sehr kurz beschrieben werden kann m ssen zus tzlich noch die Kontrollsi gnale zu den Core Services angesteuert und eine entsprechende Beschreibung der Schnittstelle nicht im Quellcode Listing enthalten vorgenommen werden Sobald ein Stream bereit ist kann durch das Anfor dern von Werten aus einem Stream gelesen werden Einem Stream werden Daten hinzugef gt indem ein valid Signal f r einen anliegenden Wert gesendet wird Das Senden des Streams wird letztendlich durch das flush Signal initiiert 5 2 2 Tests und Messungen F r eine erfolgreiche Umsetzung in Hardware musste trotz einer geringen Logiktiefe des Algortihmus f r beide Implementierungen ein hoher Hardware Synthese Aufwand gew hlt werden Bei normalem Aufwand gelang es bei der Verdrahtung nicht die zeitlichen Anforderungen engl Timing Constraints der Core Services zu erf llen Das gesamte Design ben tigt bei gleichen Aufrufparametern der tech 60 5 FALLBEISPIELE 2500 2000 1500 MByte s 1000 500 eS ET BEE EDEN er 0 0 0625 0 125 0 25 0 5 1 2 4 8 16 32 64 128 256 512 1024 Datenmenge MiByte 4 Dire
134. n ber Streams nicht determinis tisch und k nnen demnach nicht zur Performance Absch tzung solcher Schleifen verwendet werden Simulation Server Mode Im Server Modus kann der Mitrion Simulator dazu genutzt werden einen auf dem FPGA implementier ten MVP zu emulieren Aus einem auf dem Host ausf hrbaren ANSI C oder Fortran Programm heraus wird der Simulations Server ber die Mithal API aufgerufen Die Funktionsaufrufe sind dieselben wie bei der Ausf hrung des MVP auf dem FPGA Es m ssen lediglich zwei Funktionsaufrufe angepasst werden weil sich die Semantik einiger Argumente ndert Wird der Server Modus verwendet m ssen der Funktion mitrion_fpga_allocate der Port und der Hostname des Simulations Servers bergeben werden Anstelle der Bitstream Bezeichnung muss der Funktion mitrion_processor_create im Server Modus der Dateinamen des Mitrion C Quellcodes bergeben werden 4 2 Hardware Entwicklungsablauf Die typische Hardware Entwicklung beginnt mit einem Hardware Entwurf Dieser wird anschlie end in eine Hardwarebeschreibungssprache HDL bertragen simuliert und mittels automatisierter Vorg n ge auf die Zieltechnologie umgesetzt In dieser Arbeit ist das Ergebnis der Hardware Entwicklung ein Bitstream welcher die notwendigen Informationen enth lt um den FPGA entsprechend der vorgenom menen Spezifikation zu programmieren Auf die einzelnen Stufen der Hardware Entwicklung wird im Verlauf dieses Kapitels noch genauer ei
135. n FPGAs welcher die Anpassung der Hardware an einen Algorithmus auf Bit Ebene erm glicht und damit dazu beitr gt Ressourcen einzusparen 12 2 FPGAS Ein verh ltnism ig schwacher Punkt bei FPGAs ist derzeit noch die Verarbeitung von Flie kommawer ten siehe Abschnitt 2 5 obwohl darauf spezialisierte FPGAs mit vielen DSP Bl cken durchaus gute Flie kommaverarbeitungsleistung erbringen k nnen F r Algorithmen die prim r auf solchen Datenty pen arbeiten sind andere Beschleuniger wie z B ClearSpeed oder Grafikkarten meist besser geeignet und bringen auch bessere Performance Der wesentliche Vorteil von FPGAs gegen ber ASICs ist die Rekonfigurierbarkeit welche es erm glicht eine an bestimmte Anforderungen bereits angepasste Hardware im Nachhinein noch zu modifizieren oder auch zu erweitern Damit bieten FPGAs eine hnliche Flexibilit t wie Software Diese Eigenschaft wird u a daf r genutzt Prototypen zu erstellen um Ideen und Konzepte bereits in Hardware testen zu k n nen F r einen Langzeiteinsatz ist die Rekonfigurierbarkeit ebenfalls von Vorteil da sich ber die Jahre Spezifikationen ver ndern und eine Anpassung der FPGAs ohne erneute Fertigung und Austausch der Hardware m glich ist Damit reduzieren sich u U Wartungskosten Eine weitere Eigenschaft moderner SRAM basierter FPGAs dynamische partielle Rekonfiguration ist zunehmend auch f r Anwendungen in der Praxis interessant z B bei Fahrerassistenzsyste
136. n Performance f hrt Der maximale Geschwindigkeitsgewinn eines RC100 FPGAs ge gen ber einer Referenz CPU ist laut Messungen 3 3 f r Mitrion C und 23 1 f r VHDL Allgemein ist festzustellen dass die Mitrion C Implementierungen in allen Messungen schlechtere Performan ce bieten als die vergleichbaren VHDL Implementierungen Zur Leistungsbewertung der Hardware Implementierungen wurden in der Programmiersprache C Benchmarks geschrieben Die Messungen wurden entweder ber einen l ngeren Zeitraum oder aber unter der Verwendung von Bash Skripten mehrfach durchgef hrt um zeitweise Schwankungen zu interpolieren Eine Kosten Nutzen Absch tzung bringt schlie lich die quantifizierbaren Metriken Entwicklungsauf wand und Performance in einen Zusammenhang und verdeutlicht wann sich eine Anwendungsportierung auf die RASC Plattform lohnt Als Fazit bleibt dass sich der VHDL Entwurf einer geeigneten Anwen dung immer lohnt w hrend mit Mitrion C mitunter keine Geschwindigkeitsgewinne gegen ber aktuellen CPUs erreicht werden k nnen wodurch sich auch der im Durchschnitt geringere Entwicklungsaufwand nicht immer rechtfertigen l sst Die vergleichsweise geringe Leistungsaufnahme von FPGAs kann aller dings schon bei geringen Geschwindigkeitsgewinnen Energiekosten verringern Neben dem noch vorhandenem Optimierungspotenzial der vorgenommenen Implementierungen bietet auch die RASC Plattform selber noch Verbesserungsm glichkeiten was insbesondere die Ko
137. ner Vielzahl von Programmierern und Programmbeispielen nicht vorgenommen werden konnte In die Betrachtung sollen zus tzlich noch die Einarbeitungszeiten mit einflie en Neben den zeit lichen Unterschieden bei der Implementierung gibt es auch gemeinsame Entwicklungsaspekte welche am Ende des Abschnitts kurz besprochen werden Die f r die Micro Benchmarks angefallenen Entwicklungszeiten k nnen verh ltnism ig genau ange geben werden da sie im Umfang dieser Arbeit erstellt wurden und keinen komplexen Algorithmus im plementieren F r beide Sprachen bestand die Aufgabe im Wesentlichen in der Ansteuerung der hard wareseitigen Schnittstelle der RASC Plattform Core Services Bei Mitrion C f llt f r diesen Punkt nahezu keine Entwicklungszeit an da die f r den Nutzer sichtbare Schnittstelle die bergabeparame ter der Main Funktion sind Diese werden wie normale Typen hier Speicher Streams oder Variablen gehandhabt Bei der Verwendung von VHDL hingegen m ssen zum einen Wrapper Module und Konfigurationsda teien erzeugt und zum anderen die Ansteuerung der Schnittstelle zu den Core Services vgl Abschnitte B5 2 Jund 1 1 vorgenommen werden Der zeitliche Aufwand f r die reine Implementierung ist mit etwa einer Stunde Arbeitszeit zu bewerten wenn das Algorithmus Konfigurations Tool vgl Abschnitt 3 4 4 verwendet wird und die Schnittstellenspezifikation bekannt ist Andernfalls muss zuvor die Spezifikati on studiert und Tests durchg
138. nerhalb von Funk tionen explizit vom Programmierer geb ndelt Die Zusammenfassung von Anweisungen in Funktionen ist nicht performance relevant und dient lediglich der Strukturierung In Hardwarebeschreibungsspra 4 1 MITRION SDK VON MITRIONICS 37 0olMitrion C 1 5 options cpp define ExtRAM mem uint 128 2048 ExtRAM ExtRAM main ExtRAM sram0 ExtRAM sraml durch Bandbreite begrenzte Schleif results foreach i in lt 0 4 gt int 16 partsum i durch Latenz begrenzte Schleif 10 sum for j in lt 1 10 gt partsum partsum j partsum watch sum sum sraml_final foreach res in results by i sramlw memwrite sraml i res sramlw 20 sramO sraml_final Auflistung 4 1 Mitrion C Beispielprogramm chen vgl 4 2 1 hingegen muss die Synchronisation von Prozessen und das korrekte taktgenaue Be reitstellen von Daten der Programmierer vornehmen Prozesse und nebenl ufige Anweisung werden in VHDL explizit vom Programmierer beschrieben Obwohl der Syntax von Mitrion C sich an bekannte Hochsprachen der C Familie anlehnt gibt es einige wesentliche Konzepte welche von der ANSI C Programmierung sehr abweichen W hrend in Mitrion C Parallelisierung und Datenabh ngigkeiten im Mittelpunkt stehen ist dies bei traditionellen sequentiellen Programmiersprachen die Reihenfolge der Befehlsausf hrung In Mitrion C gibt es keine Ausf hrungs reihenfolge im he
139. nge ASCH Eingabe und den zugeh rigen MD5 Hash md5 rdietric d6fe591a6f217dc9c7dfd2766b 8bO1A Im Folgenden wird der Algorithmus zur Erzeugung eines MD5 Hashes aus einer Folge von ASCII Zeichen erl utert die VHDL und Mitrion C Implementierung betrachtet und schlie lich die Perfor mance der verschiedenen Umsetzungen verglichen Beide Implementierungen basieren auf der in C ge schriebenen Kryptografie und SSL Bibliothek xyssl Dev07 deren Quellcode frei zug nglich ist Algorithmus Der MD5 Algorithmus wurde so entworfen dass er schnell auf 32 Bit Maschinen ausgef hrt werden kann Zudem ben tigt er keine langen Substitutionstabellen und kann sehr kompakt programmiert wer den MDS erzeugt aus einer Nachricht mit variabler Lange eine Ausgabe fester L nge 128 Bit Vorerst wird die Ausgangsnachricht so erweitert dass ihre L nge in Bits kongruent zu 448 modulo 512 ist indem eine Eins und dahinter Nullen angeh ngt werden Besitzt die Nachricht bereits die geforderte L nge wird dennoch eine Eins angeh ngt Eine 64 Bit Zahl enth lt die Nachrichtenl nge und komplettiert die Nachricht so dass sie durch 512 teilbar ist und blockweise als Eingabe verwendet werden kann Der Hauptalgorithmus von MD5 arbeitet mit einem Puffer aus vier 32 Bit W rtern die zu Beginn mit festgelegten Konstanten initialisiert werden Die Verarbeitung eines 512 Bit Nachrichtenblockes wird in vier sog Runden vorgenommen Diese sind einan
140. ngegangen siehe Abschnitt 4 2 1 Zwischen Hardware und Softwareprogrammierung gibt es einige grundlegende Unterschiede Ein Hard waredesign ist die physische ein Softwaredesign die logische Implementierung einer Funktionalit t Aus technischer Sicht bezeichnet Software alle nichtphysischen Funktionsbestandteile eines softwaregesteu erten Ger tes Hardware gibt den physischen Rahmen vor innerhalb dessen Grenzen eine Software funk tioniert Bei der Hardwareprogrammierung implementiert man f r ein mikroelektronisches System einen bestimmten Umfang an Befehlen welche durch digitale Schaltungen realisiert werden Eine Abfolge von Befehlen die sich in einem Speicher befinden k nnen als Software bezeichnet werden In Abbildung 4 4 44 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM Bitstream Executable i a Hardware Entwicklungsablauf b Software Entwicklungsablauf Abbildung 4 4 Vergleich von Hardware und Softwareentwicklung sind Hardware und Software Entwicklung im berblick dargestellt wobei das Ergebnis ein Bitstream zur Programmierung des FPGA bzw eine ausf hrbare Datei ist Die klassische Vorgehensweise bei der Softwareentwicklung beginnt mit der Beschreibung einer Funk tionalitt t oder einem Algorithmus in einer h heren Programmiersprache wie C C Fortran usw Nachdem der Compiler den Quellcode in Maschinensprache bersetzt hat f gt der Linker einzelne Mo dule zu einem ausf hrbar
141. nikation einsetzbar Sie werden beispielsweise bei der Protokoll Abarbeitung f r verschie dene bertragungsstandards wie GPRS oder Ethernet MAC Layer verwendet Luft und Raumfahrt milit rische Anwendungen In diesem Bereich werden h ufig FPGAs mit strahlungsfesten Geh usen eingesetzt um mit IP Cores Bild und Tonsignale zu verarbeiten Ein weiterer Nutzungsgrund im milit rischen Bereich ist das Verlorengehen der Programmierung des FPGAs wenn kein Strom anliegt und damit die Sicherstellung dass Informationen geheim bleiben Verbraucher Auch f r die Verbraucherelektronik bieten FPGAs kosteng nstige L sungen Sie wer den beispielsweise in digitalen Flachbildschirmen f r das Heimnetzwerk oder in Digitalempf n gern und SetTop Boxen verwendet Industrie Forschung Medizin Marktspezifische angepasste L sungen wie z B Motorkontrolle in der Automatisierung High End Bildverarbeitung in der Medizin oder Erkennung von Mustern in der Biologie spielen in diesen Bereichen eine wesentliche Rolle Speicher und Archivierungssysteme FPGAs eignen sich f r die Realisierung schneller Speicher und Schnittstellensysteme Sie werden unter anderem in NAS und SAN Systemen verwendet Beschleunigung von Algorithmen Mit dieser Art der Anwendung von FPGAs besch ftigt sich diese Diplomarbeit Die rekonfigurierbare Hardware fungiert dabei als Spezial oder Koprozessor 2 2 AUFBAU UND GRUNDSTRUKTUR ARCHITEKTUR 9 Rechenintensive
142. ntfernte sich auf einem anderen Knoten befindende Daten erfolgt ergeben sich unterschiedliche Zugriffszei ten und Bandbreiten Als Betriebssystem wird SuSE Linux Enterprise Server SLES 10 mit dem SGI ProPack 5 verwendet Einzelne Systemknoten der Altix 4700 werden entweder f r rechenintensive Aufgaben verwendet Re chenknoten stellen zus tzlichen Hauptspeicher zur Verf gung Speicherknoten oder es handelt sich um Ein Ausgabe Knoten Alle Knotentypen sind in Form von Blades einer flachen Bauform von Plati nen mit gemeinsamer Strom und L ftungsversorgung realisiert Diese Blades werden mittels des SGI NUMAlink4 Netzwerks zu einem Shared Memory System in einer Fat Tree Topologie zusammenge schaltet Durch dieses modulare System von Knoten lassen sich die verschiedenen Knotentypen nach Belieben variieren wodurch die Anpassbarkeit an spezielle Anforderungen erleichtert wird Ein Rechenknoten Compute Blade vgl Abbildung 3 1 besteht aus bis zu zwei Intel Itanium 2 Mon tecito Prozessoren und einem SHUB Diese Kommunikationskomponente verbindet den Prozessor mit Aufgrund der Bandbreitenbeschr nkung der Speicheranbindung ist in der Altix 4700 am ZIH nur ein Socket best ckt 22 3 SGIRASC 6 4 GByte s 10 7 GByte s Itanium Il Montecito 6 4 GByte s Abbildung 3 1 Altix 4700 Rechenknoten dem physisch lokalen Hauptspeicher und stellt zwei NUMAlink4 Kan le je 6 4 GB s zur Anbindung an das
143. nwendungsbeschleunigung verglichen In der Hochsprache Mitrion C wird ein Algorithmus wie in typischen prozeduralen Programmiersprachen auf funktionaler Ebene beschrieben und durch einen Compiler und dem Konzept des MVP vgl Abschnitt 4 1 2 in eine Hardwarebeschrei bung berf hrt Mit VHDL hingegen wird nicht der Algorithmus beschrieben sondern die Hardware welche den Algorithmus ausf hren soll Dementsprechend findet eine Algorithmusbeschreibung auf un terschiedlichem Abstraktionsniveau statt 6 2 VERGLEICH VON MITRION C UND VHDL RASC PROGRAMMIERUNG 83 Die Verwendung von Mitrion C zur Programmierung der RASC Plattform bringt zwei grundlegende Einschr nkungen mit sich Dies ist zum einen die festgelegte Taktfrequenz des erzeugten Hardware Designs auf 100 MHz und betrifft zum anderen die RASC Kommunikationsm glichkeiten welche nicht in vollem Umfang genutzt werden k nnen siehe Abschnitte 5 1 5 2 1 Jund 5 3 Im Folgenden soll die Entwicklungszeit und die Performance der vorgenommenen Implementierungen der Fallbeispiele genauer betrachtet werden um sp ter Aufwand und Nutzen absch tzen zu k nnen Ease of Use Debugging M glichkeiten und Fehleranf lligkeit sollen einen Einblick in den Program miervorgang verschaffen ohne einen zahlenm igen Vergleich der Sprachen vorzunehmen 6 2 1 Entwicklungszeiten Die Entwicklungszeiten k nnen im Umfang dieser Arbeit nur abgesch tzt werden da eine statistische Grundlage mit ei
144. o eine Energieersparnis von 50 zu erreichen muss die durch den FPGA GPU beschleunigte Anwendung 2 5 12 5 mal so schnell sein _ Precajapu P S 2 1 20 2 FPGAS CPU Kern 20W FPGA Modul 25W GPU 125W GPU 100 eeneg FPGA Leistungsaufnahme im Vergleich zu CPU o 5 10 15 20 25 30 35 40 45 50 55 60 Geschwindigkeitsgewinn Abbildung 2 6 Energieeffizienz von FPGAs und GPUs Diese Darstellung betrachtet jedoch nur die Recheneinheiten selber und vernachl ssigt jegliche Periphrie Komponenten auch wenn diese zur Ansteuerung bzw zum Betrieb notwendig sind Es kommt also noch ein schwer bestimmbarer Faktor hinzu welcher neben Komponenten wie z B Speicher auch die K h lung mit einschlie t Es werden hier ausschlie lich SRAM basierte FPGAs verwendet weil diese unter der Bedingung rekon figurierbar zu sein die beste Performance aufweisen Aktuelle High End FPGAs mit vielen Logikbl cken sind zwar sehr kostenintensiv bieten jedoch viele Zusatzmerkmale und fest integrierte Schaltungen die eine schnelle Anbindung an das Host System erlauben Zudem kann auf derart gro en Chips nahezu jeder Algorithmus implementiert werden In FPGA basierten Beschleuniger Systemen bernimmt ein Host die Ansteuerung und Programmierung der FPGAs In Kapitel Di wird mit SGI RASC ein System vorgestellt welches FPGAs aus der Virtex 4 LX Fa milie siehe Abschnitt 2 4 als Hardware Beschleuniger verwendet Andere Systeme
145. olumn slots A3 DAMENPROBLEM 127 bits N bh_nc bhp bits N Du ne bits N bd_nc bdp write blocking and slot mem_bt2 memwrite mem_btl mem_slt2 70 mem_s1lt3 mem_loop2 tup mem_bt2 mem_loop2 else mem_loop 75 set next i i cnt0O if slot int 6 iml i 1 iml cntO else 80 itmp cnttmp if i lt int 6 ipl i 1 ip1 cnt0 else 85 uint 46 cntOn cntO 1 int 6 inn N 2 inn cntOn itmp cnttmp 90 cnt0O mem_loop mem_b_last cnt memwrite mem_sltl i memwrite mem_slt1 int 6 i 1 slots_nc mem_slt3 loop dependend variable bits N 0 N 1 nslot bits N bup nslot 65 slots_nc bh_nc bu_nc bd_nc nslot gt gt 1 lt lt 1 watch slots_nc 2 cycles int 6 i 1 bh_nc cslots bung and solution counter is last column Count Solution and proceed with preceding Column watch cntOn mem_sl_last untup mem_al 95 define ExtRAM mem bits 128 2048 ExtRAM ExtRAM main ExtRAl sramOslices sramlslices sram0 sramlall sramlall foreach idx_slc in 0 ExtRAM sraml SLICES 1 foreach idx_pre in lt 0 PERSLICE idx idx_slc PERSLICE idx_pre 100 105 prel28 bits 32 uint 46 D D psoll28 sramlps sramOps sramlps sram0ps memread sram0
146. on Bedeutung ist Es wird zwischen kombinatorischen und synchron getakteten Pro zessen unterschieden Kombinatorische Prozesse beschreiben das Verhalten von Schaltnetzen und haben eine Sensitivit tsliste welche die Eingangssignale des Netzes beinhaltet ndert sich eines dieser Signa le wird der Prozess angesto en und es k nnen sich Signale ndern welche wiederum weitere Prozesse ansto en Synchron getaktete Prozesse haben in der Sensitivit tsliste das Taktsignal und das Reset Signal falls ein asynchrones Reset ben tigt wird Sie beschreiben Zustands berg nge von Registern und legen damit die Werte von Signalen fest die zur Taktflanke bernommen werden sollen VHDL ist eine typenorientierte Programmiersprache Zudem werden grunds tzlich drei Klassen von Informationstr gern unterschieden Konstanten Signale und Variablen Einer Konstanten kann blicher weise nur einmal ein Wert zugewiesen werden Dieser ist dann in der gesamten Einheit bekannt und unver nderlich Signale dienen der Informations bermittlung zwischen einzelnen nebenl ufigen Funk tionsbl cken und verkn pfen damit Komponenten und Prozesse untereinander Ihr Zustand ndert sich im Vergleich zu den Variablen immer erst am Ende eines sequentiellen Prozesses Variablen k nnen aus schlie lich innerhalb von sequentiellen Anweisungsfolgen wie Prozessen und Prozeduren verwendet werden Wie bei typischen Programmiersprachen wirken Variablenzuweisungen ohne Verz ger
147. or ist der zus tzliche Kommunikationsaufwand zwischen dem Host programm und dem Hardware Beschleuniger Dieser kann zwischen verschiedenen Anwendungen stark schwanken und in einigen F llen sogar ein Flaschenhals sein wodurch keine Beschleunigung der Ge 82 6 AUSWERTUNG FPGA Anteil 100 Geschwindigkeitsgewinn Anwendung 3 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 Geschwindigkeitsgewinn FPGA Abbildung 6 1 Geschwindigkeitsgewinn einer durch FPGAs beschleunigten Anwendung samtanwendung m glich ist Ein sehr hohes Beschleunigungspotenzial bieten Anwendungen mit ver nachl ssigbarem Kommunikationsaufwand und einer gut parallelisierbaren Schl sselroutine dessen Be rechnungsaufwand die Gesamtlaufzeit dominiert Der Geschwindigkeitsgewinn einer Anwendung unterliegt auch bei der Verwendung von Hardware Beschleunigern dem Gesetz von Amdahl Das Diagramm 6 1 verdeutlicht die erreichbare Performance Steigerung wenn nur ein Teil der Ausf hrungszeit einer Anwendung durch den FPGA beschleunigt wird Es ist zu erkennen dass auch eine hohe Beschleunigung der Schl sselroutine nur dann die Perfor mance der Gesamtanwendung deutlich verbessern kann wenn die Laufzeit des auf den FPGA ausgela gerten Teils zuvor die Gesamtrechenzeit dominiert hat 6 2 Vergleich von Mitrion C und VHDL RASC Programmierung Mit der Verwendung von Mitrion C und VHDL werden in dieser Arbeit zwei vollkommen verschiedene Herangehensweisen zur A
148. orithmus darauf zugreifen kann minimiert das zus tzlich den Logik Overhead der Core Services da entsprechende Logik beim SRAM Kontroller und den DMA Bl cken und auch deren Verdrahtung entfallen Die SRAM Schnittstelle verf gt ber zwei Verfahren zur Datenflusskontrolle Handshaking Verfahren Busy Signal und Crediting Scheme Es ist dem Programmierer berlassen welches er in seinem Entwurf verwendet Eine Erkl rung zu den Signalen die je nach Verfahren benutzt werden ist in SGI08 beschrieben Um Datenmengen zu verarbeiten die nicht in den SRAM des FPGA Blades passen bietet SGI eine Multibuffering L sung an Hierzu werden Eingangs und Ausgangsdaten in jeweils mindestens zwei Segmente pro SRAM Bank unterteilt W hrend der Host Daten in ein Segment des SRAM l dt kann der FPGA Algorithmus auf ein anderes Segment zugreifen Die Umschaltung zwischen den Segmen ten erfolgt ber ein pro genutzter SRAM Bank von den Core Services zur Verf gung gestelltes Offset Register welches die oberen Bits der Speicheradresse bestimmt sofern es vom Algorithmus Designer genutzt wird 3 3 2 Streaming Engines Beim Direct Streaming werden Datenpakete in einem Datenstrom direkt an den Algorithmus Block ge schickt ohne den Umweg ber den SRAM der FPGAs zu nehmen Dies soll zum einen die Latenzzeit des Datentransfers minimieren und verringert zum anderen den Logik Overhead durch die Core Services da 28 3 SGIRASC der Speic
149. orm der Entwicklungszeit tg angenommen w hrend der Nutzen auf den Geschwindigkeitsgewinn Sp vgl Tabelle abgebildet werden kann Wird die Ersetzung des Re ferenzsystems durch das Beschleunigersystem betrachtet kann zudem die zeitliche Amortisierung tA berechnet werden W hrend der Anwendungsportierung finden dann keine Berechnungen statt Abh n gig vom Geschwindigkeitsgewinn der beschleunigten Anwendung kann der Ausfall der Berechnungen nach einer Zeit ta kompensiert werden Tabelle 6 2 zeigt die verwendeten Metriken und die zugeh rige Amortisationszeit vgl Formel 6 1 f r jeweils zwei Entwicklungsstufen der Beispielanwendungen 8 ta tr 6 1 n 1 1 Sp Die in der Tabelle angegebenen Entwicklungszeiten tg sind Sch tzwerte vgl Abschnitt 6 2 1 und es wird nur mit einem FPGA des RC100 Blades als Beschleuniger gerechnet weil nur eine CPU als VHDL Mitrion tg Sp ta Ir Sp ta Damenproblem 1 7 Tage 11 4 16 2 Stunden 2 Tage 0 5 00 Damenproblem 2 14 Tage 22 7 15 5 Stunden 5 Tage 0 9 KS MDS5 Brute Force 1 10 Tage 6 6 42 9 Stunden 3 Tage 3 3 31 3 Stunden MDS5 Brute Force 2 18 Tage 13 3 35 1 Stunden 3 Tage 3 3 31 3 Stunden Durchschnitt o 12 Tage 13 5 23 Stunden 3 Tage 2 0 72 Stunden te Entwicklungszeit t4 Amortisationszeit Sp Geschwindigkeitsgewinn gegen ber CPU Tabelle 6 2 Entwicklungszeit und Performance 92 6 AUSWERTUNG Referenz verwendet wurde Die Nutzung be
150. prechenden Zweiges zur ckzugeben Wird innerhalb eines Zweiges auf Speicher zugegriffen muss zuerst die Bedingung ausgewertet werden bevor ein Zweig abgearbeitet werden kann Der MVP arbeitet nicht wie ein blicher Mikroprozessor mit einem Befehlsstrom Anstelle dessen wer den die zu verarbeitenden Befehle auf dem FPGA in Form von Logik implementiert und ein Datenstrom durch diese geleitet Es ist nicht m glich den MVP in eine bestehende Schaltung einzubinden da die ser nur in Verbindung mit der entsprechenden Anbindung unterst tzter rekonfigurierbarer Systeme und einem angepassten API funktioniert 4 1 3 Mitrion Simulator Mitrionics stellt mit dem Mitrion Simulator ein Werkzeug zur Verf gung mit dem Simulation der Funk tionalit t und Fehlersuche in Mitrion C Programmen vorgenommen werden kann ohne dass der FPGA daf r ben tigt wird Folgende zwei Punkte verdeutlichen die Notwendigkeit der Simulation e Die Debugging M glichkeiten von auf dem FPGA laufenden Anwendungen sind stark begrenzt siehe 3 4 3 e Synthese Plazierung und Verdrahtung ben tigt viel Zeit und verlangsamen die Fehlersuche Der Simulator kann in drei Modi arbeiten die im Folgenden n her erl utert werden Nachdem der Mitrion C Compiler das Programm ohne Fehler bersetzt hat werden entsprechend dem verwendeten Modus Debug Ausgaben angezeigt Simulation mit grafischer Benutzeroberfl che Der Graphical User Interface GUI Modus erzeugt einen
151. prozessoren wobei auch Grafik prozessoren GPUs als Vergleich herangezogen wurden In wird die FP Performance von FPGAs anhand theoretischer Berechnungen abgesch tzt Eine Aktualisierung und Anpassung dieser Leistungs bewertung unter Ber cksichtigung von KC07 wird in SSWW08 vorgenommen Leder Xtreme DSP Slice besteht aus einem 18x18 Multiplizierer einem Addierer und einem Akkumulator 3serielle Transceiver mit 622 Mb s bis 6 5 Gb s Baudrate 16 2 FPGAS FP Verarbeitung findet typischerweise in der verallgemeinerten Matrix Multiplikation engl General Matrix Multiply GEMM Verwendung Um maximale Performance f r Mikroprozessoren zu errei chen werden vom Programmierer hochoptimierte GEMM Funktionen f r einfache Genauigkeit 32 Bit SGEMM und doppelte Genauigkeit 64 Bit DGEMM verwendet und Zeiger auf die zu multiplizieren den Matrizen bergeben Bei FPGAs steht dem Programmierer im Optimalfall eine vom Systemanbie ter mitgelieferte Routine zur Verf gung welche dieselben Zeiger akzeptiert Im ersten Fall wird die GEMM Funktion auf einem Mikroprozessor ausgef hrt und in dessen Speicher gearbeitet Im zweiten Fall wird der Mikroprozessor mittels direktem Speicherzugriff DMA Daten an den FPGA oder ihm zur Verf gung stehende Speicherressourcen bertragen Die durch die rekonfigurierbare Logik berechneten Ergebnisse werden anschlie end wieder in den Speicher des Mikroprozessors bertragen Auch wenn die Bandbreite und
152. r heren Versionen von Mitrion enthaltene Entwicklungsumgebung ge h rt in der aktuellen Version nicht mehr zum Paket und es muss in einem beliebigen Editor programmiert und auf Kommandozeile bersetzt werden Mitrion C erm glicht dem Programmierer einen schnellen Einstieg zur Nutzung von rekonfigurierbarer Hardware ohne Wissen ber diese zu ben tigen Der Mangel an Beschreibungsformen Konstrukten l sst allerdings nicht in jedem Fall die effiziente Programmierung des Algorithmus zu Mit VHDL wird hingegen die Hardware zur Abarbeitung eines Algorithmus beschrieben was in vielen F llen zu ei ner effizienteren Umsetzung f hrt Mitrion C kann mit einigen guten Konstrukten wie die Vektor oder Listenerzeugung ber Bereiche oder der FOREACH Schleife zur einfachen Parallelisierung berzeu gen entt uscht aber gleicherma en durch einen Mangel an Beschreibungsformen z B keine Felder continue break und exit Anweisung 88 6 AUSWERTUNG 6 2 3 Fehleranf lligkeit und Debugging M glichkeiten Beim Programmieren kann zwischen verschiedenen Arten von Fehlern unterschieden werden Lexika lische und syntaktische Fehler werden bereits zur bersetzungszeit vom Compiler erkannt w hrend semantische und logische Fehler meist erst zur Laufzeit festgestellt werden Durch einen fehlerhaften Algorithmus bedingte Fehler k nnen in beiden Sprachen gleicherma en auftreten Die Anzahl lexikalischer und syntaktischer Fehler steigt berlicher
153. r Direct Streaming mit Mitrion und Direct I O W hrend die VHDL Implementierung mit 100 MHz Taktfrequenz sehr nahe an den theoretischen Ma ximalwert von 1 6 GByte s herankommt bleibt die Mitrion Umsetzung unter einem GByte s F r Buf fered I O liegen die gemessenen Werte sehr nahe beieinander wobei die VHDL Implementierung mit 200 MHz die h chsten und die Mitrion Implementierung die niedrigsten Ergebnisse liefern Zudem schwanken die Werte zwischen vergleichbaren Messungen bei gr eren Datenpaketen st rker als bei Direct VO weil eine Pufferung ber einen Speicherbereich des Kernels hinzukommt und dieser mitunter nicht kontinuierlich angelegt werden kann 5 3 KOMMUNIKATION BER MEMORY MAPPED REGISTERS 61 5 3 Kommunikation ber Memory Mapped Registers Anwendungen mit geringer Host FPGA Kommunikation k nnen die sog Memory Mapped Registers MMRs nutzen Mit Mitrion ist die Kommunikation ber MMRs nur stark eingeschr nkt m glich Sie erlauben nur die bergabe von Parametern und k nnen als einfache Ausgabe von Ergebnissen oder Debug Informationen verwendet werden Eine Ping Pong Kommunikation wie sie mit einer HDL m g lich ist kann mit Mitrion C nicht vorgenommen werden W hrend die Core Services Kontrollsignale bereitstellen um zu signalisieren dass der Host ein Register ver ndert oder gelesen hat ist diese Funk tionalit t in Mitrion C nicht verf gbar weshalb im Folgenden nur auf die VHDL Implementierung und deren
154. r Menge von booleschen Funktionen zu finden Da exakte Verfahren wie z B der Quine McCluskey Algorithmus NP vollst ndig sind werden an dessen Stelle Heuristiken verwendet Andernfalls w ren gro e Schaltungen nicht in an nehmbarer Zeit synthetisierbar Die graphische Methode zur Logik Minimierung mittels eines Karnaugh Veitch Diagramms ist f r die Berechnung auf einem Computer ung nstig und wird demnach nicht f r den automatisierten Entwurf verwendet F r FPGAs ist die Aufgabenstellung noch komplexer da eine Funktion mit verschiedenen Grundenelementen des FPGAs realisiert werden kann und damit die Anzahl der m glichen Realisierungen steigt Technologie Mapping An dieser Stelle werden die bereits minimierten Schaltfunktionen Register und andere Makro Module auf die Zieltechnologie abgebildet Dabei werden die Schaltfunktionen in Elemente der Zieltechnologie zerlegt F r ein Full Custom Design wird blicherweise Library Binding Auswahl von Elementen aus einer Bibliothek welche die gew nschte Funktion haben verwendet was bei FPGAs allerdings 4 2 HARDWARE ENTWICKLUNGSABLAUF 51 nicht anwendbar ist Anstelle dessen werden algebraische Ans tze und die funktionale Dekomposition genutzt Plazierung und Verdrahtung W hrend der Plazierung wird die Anordnung der Technologieelemente auf dem Chip vorgenommen d h f r FPGAs werden den physisch vorhandenen CLBs die zu realisierenden Funktionen zugeordnet Als Einga
155. rce Hostprogramm stelle zu suchenden Hash und Startklartext bereit starte den FPGA if res startAlgorithm amp cop_desc lt RASCLIB_SUCCESS fprintf stderr Could not start Algorithm Error Code d n res rasclib_perror Algorithm could not be started res return 1 start gtod speichere Startzeit sende zu suchenden Hash res rasclib_cop_reg_write cop_desc md5hash din_hash SIZE_HASH RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS fprintf stderr reg write of md5hash failed at d d n __LINE__ res rasclib_perror reg write of md5hash res return 1 sende Startklartext res rasclib_cop_reg_write cop_desc md5init din_init SIZE_INIT RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS fprintf stderr reg write of md5init failed at d d n __LINE__ res rasclib_perror reg write of mdSinit res return 1 122 ANHANG A QUELLCODES starte die Suche start_md5 1 res rasclib_cop_reg_write cop_desc start amp start_md5 1 RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS 30 fprintf stderr reg write of start failed at d d n __LINE__ res rasclib_perror reg write of start res return 1 rasclib_cop_commit cop_desc NULL 35 Warte bis der Hash gefunden oder alle Moeglichkeiten durchprobiert wurden do rasclib_cop_reg_read cop_desc rasc_o
156. rde von einer C Implementierung abgeleitet die dem Algorithmus von Jeff Somers sehr hnlich ist Eine erste funktionierende Formulierung des Algorithmus in Mitrion C erforderte etwa 20 Stunden Arbeitszeit und brachte den in Anhang gelisteten Quellcode Er be schreibt im Wesentlichen einen einfachen Backtracking Algorithmus zur L sung eines Teilproblems welches in Form einer Vorplazierung bergeben wird Daraus werden die Blockierungsvektoren und die noch zu testenden freien Felder der ersten betrachteten Spalte ermittelt Zeilen 22 bis 49 Die mem create Anweisungen allokieren Block RAM und ersetzen die Funktionalit t von Arrays aus typischen Programmiersprachen Die tuple Anweisungen fasst mehrere Speichertoken zusammen da in Mitrion C nur ein Speichertoken aus einer Blockanweisung propagiert werden kann f r diese Implementierung allerdings mehrere ben tigt werden Die untup Anweisung entpackt die Elemente wieder aus einem Tu ple F r das 26 Damenproblem betrachtet die WHILE Schleife genau 20 Spalten Sie beinhaltet zwei ineinander geschachtelte Bedingungen Die Erste berpr ft ob eine Spalte noch freie Felder keine Dame wurde zuvor versucht zu plazieren und nicht blockiert enth lt Ist dies nicht der Fall wird zu r ckgesprungen Ansonsten wird mit der zweiten Bedingung berpr ft ob es sich um die letzte Spalte handelt und ggf die L sung gez hlt oder aber die Blockierungen und die freien Felder angepasst Der Mitrion C Bandbreiten
157. re Services an der Schnittstelle zum Algorithmus beschreibt sehr hilfreich und w rde Fehler und entsprechend unn tige Synthesevorg nge vermeiden Die Testbench k nnte neben den Konfi gurationsdateien und Verilog Wrapper Modulen durch das Algorithmus Konfigurations Tool generisch erzeugt werden Weitere Verbesserungsans tze betreffen die in Abschnitt vorgestellten Kommunikationsvarianten deren Funktionalit t erweitert werden k nnte Algorithm Defined Registers Der Host wird derzeit nicht ber eine nderung der Register durch den Algorithmus informiert Eine entsprechende funktionale Erweiterung der rasclib Bibliothek w rde das Polling ber ein zus tzliches Debug Register vgl 5 3 1 berfl ssig machen SRAM Kommunikation Mit der aktuellen Version der RASC Core Services ist es nicht m glich unabh ngig vom FPGA Algorithmus auf den SRAM zuzugreifen Es k nnen ausschlie lich ein mal w hrend der Ausf hrung des Algorithmus Daten vom Host gesendet und empfangen wer den Eine unabh ngige Host SRAM Kommunikation w rde einen dauerhaften Betrieb des FPGA Algorithmus erm glichen Dementsprechend m ssten auch zus tzliche Kontrollsignale in die Core Services integriert werden um den Algorithmus ber die Schreib und Lesevorg nge des Host zu informieren Direct Streaming Wie bei der SRAM Kommunikation ist es nur m glich einmal pro Algorithmus Durchlauf Daten zu senden oder zu empfangen Sinnvoll w re es wenn ein Stre
158. ream res out if res null return res 75 return out new OutputStream private byte buf new byte JRasc this inputBytes private int idx 80 public synchronized void write int b throws JRascException buf idx byte b if idx JRasc this inputBytes public static JRasc reserve String alg int inputBytes int outputBytes 132 ANHANG A QUELLCODES 85 90 95 100 105 110 115 120 int res sendByteArray hdl buf if res lt 0 throw new JRascException res idx 0 D x Returns an InputStream to receive data from RASC x return an InputStream public synchronized InputStream getInputStream final InputStream res in if res null return res return in new InputStream private byte buf new byte JRasc this outputBytes private int idx buf length public synchronized int read throws JRascException if idx gt JRasc this outputBytes int res recvByteArray hdl buf if res lt 0 throw new JRascException res idx 0 performance evaluation JRasc this subboards outputBytes 16 long elapsed new Date getTime starttime System err printlin float JRasc this subboards elapsed 3600000 0 subboards hour return bufl lidx amp 0xff 133 Erkl rungen zum Urheberrecht Silicon Graphics SGI und Altix sind eingetragene Marken und NUMAl
159. reicht werden Im Vergleich dazu k nnen mit PCI Express FPGA Boards deutlich h here Datenraten erreicht werden PCIe 2 0 x32 16 GByte s F r das SGI RC100 Blade stehen drei M glichkeiten zur Verf gung Daten zwischen Host und FPGA zu bermitteln Hierzu z hlen eine Streaming Schnittstelle eine Schnittstelle zum SRAM der RC100 Blades und spezielle 64 Bit Register Memory Mapped Registers Die Bandbreite des Datentransfers zwischen den RC100 FPGAs und einer Host CPU ist durch das NUMAlink4 Netzwerk auf insgesamt 6 4 GB s begrenzt 3 3 1 SRAM Schnittstelle Die Speicheranbindung ber den SRAM der RC100 Blades bietet die M glichkeit Daten vom Host in den SRAM des jeweiligen FPGA zu schreiben und Daten aus dem SRAM des FPGA zu lesen Ab der Version 2 20 bieten die SGI Core Services drei verschiedene Konfigurationsvarianten der f nf pro FPGA vorhandenen 8MB SRAM Banke an 1 zwei 128 Bit Ports je zwei 64 Bit Ports zu einem 128 Bit Port zusammengefasst ein 64 Bit Port 2 f nf voneinander unabh ngige 64 Bit Speicherports 3 keine Ports zum SRAM Ist es nicht m glich die f r die Ausf hrung des Algorithmus ben tigten Daten im Block RAM des FPGA zu halten k nnen diese in den SRAM ausgelagert werden und m ssen nicht zwischen Host und FPGA transportiert werden W hrend f r die Host FPGA Kommunikation eine Bandbreite von 6 4 GB s zur Verf gung steht ist der SRAM selber mit 16 GB s an den FPGA angebunden Die SRAM Kommunikation
160. released res return 1 A3 DAMENPROBLEM 123 A 5 Damenproblem Auflistung A 12 Erster Versuch einer Mitrion C Implementierung des Damenproblems 0 Mitrion C 1 5 options cpp define 26 define L 6 5 define L_1 5 define NL 20 define SLICES 1 define PREPLACEMENTS 1 10 define SEQ PRE 1 PREPLACEMENTS SLICES T define ExtRAM mem bits 128 2048 Calculates all completions of valid Queens placements on a NxN board 15 under the pre placement provided in cs as D lcol 0 Jcol 1 col L 1 col i 5 bits x This encoding is valid up to L 6 and N 32 when col 0 is placed only up to the middle row thus requiring at most 4 bits x param cs Pre Placement 20 return Number of valid Board Completions 46 Bit should be enough uint 46 solveQueens uint 32 cs mem_bh0 memcreate mem uint 32 N mem_bh_last blocking horizontal 25 mem_bu0 memcreate mem uint 32 N mem_bu_last blocking upwards mem bd0 memcreate mem uint 32 N mem_bd_last blocking downwards mem_sl0 memcreate mem uint 32 N mem_sl_last free slots yet to try Initialize Blocking 30 uint 32 bh0 0 uint 32 bud 0 uint 32 bd0 0 uint 32 zero 0 D get blocking from pre placement 35 uUlnEt 32 u106132 011022232 bal bul baly for i 14 lt 0 As tol gt 4 uint 32 q uint 32 1 lt l
161. ren Befehlssatzerweiterungen etc und FPGAs ziehen Nachteile gegen ber ASICs mit sich Da Aufgaben nicht wie bei einem spezialisierten Baustein optimal abgearbeitet Rekonfiguration von Teilen des FPGAs zur Laufzeit w hrend andere Bl cke weiter arbeiten 2 4 VIRTEX 4 FPGAS 13 werden k nnen sind Energieverbrauch Datendurchsatz Chip Fl che Taktfrequenz und andere Zielpa rameter schlechter Ein mitunter entscheidender Punkt der gegen die Verwendung von FPGAs sprechen kann ist der Ent wicklungsaufwand der beim Hardware Entwurf betrieben werden muss siehe Abschnitt und 6 2 1 Zudem sind die Preise moderner High End FPGAs sehr hoch Nicht zu vergessen ist dass auch FPGAs in ihrer Ausstattung z B eingebetteter Speicher analoge Elemente I O Ressouren beschr nkt sind SRAM basierte FPGAs m ssen zudem bei jedem Systemstart konfiguriert werden Es sind also zus tzli che externe Komponenten z B EEPROM oder Flash Speicher und Mikrokontroller notwendig um den Bitstream in den FPGA zu laden Das bedeutet auch dass die Funktionalit t eines FPGAs nicht direkt nach dem Einschalten zur Verf gung steht sondern erst nach dem Laden Dies kann je nach eingesetzter Technik einige Zeit typischerweise im Bereich von Millisekunden dauern 2 4 Virtex 4 FPGAs Die Virtex 4 FPGA Familie umfasst drei Plattformen welche f r verschiedene Anwendungszwecke kon zipiert sind LX Logik FX Features SX Signalverarbe
162. rk mmlichen Sinne Es wird jede Operation sobald ihre Datenabh ngigkeiten erf llt sind sofort ausgef hrt Parallelit t ist in Mitrion C Programmen implizit Ein weiterer Untschied zwischen Mitrion C und anderen Hochsprachen der C Familie ist dass die meis ten Anweisungen au er Deklarationen und Watch Statements in Mitrion C Zuweisungen sind Damit sind if for und while Anweisungen in Mitrion C Ausdr cke die einen Ergebniswert zur ckgeben Die Ternary Operation bedingte Zuweisung aus C ist ein Beispiel f r eine i Anweisung in Form einer Zuweisung In Mitrion C muss eine Anweisung innerhalb eines Blockes ber dessen R ck gabewert propagiert werden um au erhalb des Blockes Einfluss nehmen zu k nnen Ein kurzes Mitrion C Programm verdeutlicht der Quellcode 4 1 Mitrion C geh rt zu den Single Assignment Languages Das bedeutet dass in einem Block einer Variable nur ein einziges Mal ein Wert zugewiesen werden darf Diese wichtige Einschr nkung erm glicht die 38 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM parallele Ausf hrung der Anweisungen eines Blockes sofern keine Datenabh ngigkeiten bestehen F r die Fehlersuche auf Kommandozeile stellt Mitrion C die watch Anweisung zur Verf gung Wie im Code Ausschnitt f r part_sum verwendet kann damit der Wert einer Variablen w hrend der Pro grammausf hrung beobachtet werden Alle Mitrion C Quellcode Dateien m ssen mit Angabe d
163. s 3 2GB s pro DIMM 6 4GB s gt Abbildung 3 2 RC100 Blade vgl SGI08 SelectMap Konfigurations Port Abbildung 3 3 RASC FPGA Modul vgl SGIO8 3 3 CORE SERVICES 25 SSP SRAM Bank 0 SRAM Bank 1 SRAM Bank 2 SRAM Bank 3 SRAM Bank 4 Algorithmus Abbildung 3 4 RASC Core Services vgl SGI08 gentlichen Algorithmus verwendet Die Architektur der Core Services ist in Abbildung 3 4 dargestellt wobei der Ubersicht halber einzelne Komponenten des Kontrollpfades nicht enthalten sind jedoch im Folgenden in ihrer Funktion noch erl utert werden Die Erl uterung der Funktionalit t einzelner Bl cke basiert inhaltlich auf SGIOS Das Empfangsmodul SRM und das Sendemodul SXM beinhalten entsprechende Logik um auf dem FPGA als Schittstelle zum Scalable System Port SSP zu fungieren Es stehen drei beliebig kombinier bare M glichkeiten zur Verf gung um Daten zwischen Host und Algorithmus auszutauschen e Einzelne Lese oder Schreibanfragen von 64 Bit Werten werden durch die Programmed Input Out put PIO request engine behandelt e Datenstr me werden ber die DMA Bl cke verarbeitet und k nnen direkt in den Algorithmus geleitet werden Sowohl der DMA Eingangsblock als auch der DMA Ausgangsblock bestehen aus jeweils bis zu vier unabh ngigen DMA Stream Einheiten e Daten k nnen ber die DMA Bl
164. s Programm bersichtlicher zu gestalten Die wesentliche Vereinfachung der Mitrion C Programmierung im Vergleich zur Hardware Beschreibung betrifft die Bereitstellungen von Daten und die automatische Verwaltung von Datenabh ngigkeiten Da durch kann typisch sequentiell programmiert werden w hrend dem Nutzer die eigentliche datengetrie bene Abarbeitungsreihenfolge von Operationen verborgen bleibt Bei VHDL muss der Programmierer f r die zeitlich korrekte taktgenaue Bereitstellung der Daten sorgen Das folgt allerdings daraus dass es sich um Hardware und keine Algorithmus Beschreibung handelt Wird beispielsweise die Verwendung von Block RAM betrachtet kann diese mit Mitrion C durch einfache Funktionsaufrufe bewerkstelligt 6 2 VERGLEICH VON MITRION C UND VHDL RASC PROGRAMMIERUNG 87 werden In VHDL muss ein Block oder eine Komponente beschrieben werden welche ber Adress Enable und Daten Signale angesteuert wird Bei lesendem Zugriff muss einen Takt bevor der Wert bereit stehen soll die entsprechende Adresse angelegt werden w hrend bei schreibendem Zugriff die Adresse im gleichen Takt wie das Datum angelegt wird Bei Mitrion C braucht der Programmierer sich um solche Hardware Detailes nicht zu k mmern Die Hardware Synthese wird in beiden F llen von der Kommandozeile gestartet Bei Mitrion kann mit dem Aufruf einer Java Anwendung und entsprechender Parameter bergabe sowohl simuliert als auch compiliert oder synthetisiert w
165. s kopiert und anschlie end wieder zur ckgespielt werden bersteigen die Datendurchs tze 1 65 GByte s nicht Dieser Test ist m glich indem der VHDL Implementierung vom Host Programm als Parameter f r die zu ver arbeitenden W rter null bergeben wird Die Speicherbandbreite zwischen SRAM und Algorithmus und die Verz gerung des Algorithmus selber haben dann keinen Einfluss mehr auf den Datendurchsatz zwi schen Host und FPGA Dementsprechend ergaben Messungen f r kleine Datenmengen eine Erh hung des Durchsatzes der jedoch mit zunehmenden Gr e der zu bertragenden Daten vernachl ssigbar wird 58 5 FALLBEISPIELE Allgemein ist festzustellen dass die Werte zwischen Messungen bei der Verwendung gleicher Parameter mitunter um bis zu 150 MByte s schwanken Der Mitrion Virtual Processor wird mit 100 MHz getaktet weshalb der maximale Datendurchsatz auf 1 6 GByte s begrenzt ist Die gemessenen Werte kommen damit durchaus in die N he des theoretischen Maximums Die Ausf hrung mit dem VHDL Design auf 100 MHz best tigen die Daten bertragungsra ten der Mitrion Umsetzung Zudem konnten mit dieser Implementierung Werte kleiner als acht MiByte ein SRAM Bank Segment aufgenommen werden Aus dem Diagramm kann die Gr e des SRAM Segments von acht MiByte abgelesen werden Daten mengen ber die Segment Gr e nutzen Multibuffering Mit 256 MiByte Gr e einer Hugepage ist die maximale Datenrate erreicht Die Werte f r gr ere D
166. schwindigkeitsgewinn von 3 3 gegen ber der schnellsten gemessenen CPU Es ist jedoch nicht jeder Algorithmus effizient in Mitrion C umsetzbar Im allgemeinen ist das Ziel einen Algorithmus unter Verwendung einer FOREACH Schleife mit einer Pipeline Struktur auf der innersten Schleifenebene zu beschreiben W hrend dies bei MDS Brute Force vgl m glich ist und zu einem Geschwindigkeitsgewinn f hrt l sst sich das Damen problem einfach allerdings nicht effizient beschreiben und f hrt zu einer vergleichsweise schlechten Performance In einigen F llen muss ein anderer Ansatz gefunden werden um eine Beschleunigung mit Mitrion C zu erreichen wodurch sich allerdings auch der Entwicklungsaufwand deutlich erh ht Kurze Entwicklungszeiten zur schnellen Portierung eines Algorithmus in VHDL erreichen nicht das Leistungsverm gen ausgereifter Implementierungen sind mitunter dennoch schneller als eine vergleich bare Mitrion C Implementierung Die prinzipielle Herangehensweise zur Algorithmusportierung ist mit beiden Programmierm glichkeiten hnlich da ein guter paralleler Algorithmus auch die Grundlage f r Geschwindigkeitsgewinne bildet Letztendlich ist Mitrion C ein interessanter Programmieransatz der nicht ausgereift ist aber in zuk nftigen Versionen noch Leistungssteigerungen erwarten l sst Mit ei ner guten VHDL Implementierung kann bei geeigneter Algorithmuswahl parallel und gut auf FPGAs umsetzbar immer mit Geschwindigkeitsgewinnen gerec
167. soll die Parallelit t der Verarbeitungsbl cke des FPGA zu nutzen und ihn als Koprozessor in Verbindung mit einem Mikroprozessor zu betreiben Eine Schal tung ansich zu entwerfen ist mit Mitrion C nicht m glich Allerdings bietet Mitrion die M glichkeit VHDL IP Block Plugins ber externe Funktionsaufrufe innerhalb eines Mitrion C Programms zu nut zen Damit lassen sich Teile des Algorithmus die von Mitrion suboptimal umgesetzt werden per Hand in VHDL optimieren Allerdings muss dann auch beachtet werden dass der MVP mit 100MHz l uft und unter dieser Anforderung der VHDL Entwurf vorgenommen werden 4 1 2 Mitrion Virtual Processor Der Mitrion Virtual Processor MVP ist ein feingranularer massiv paralleler rekonfigurierbarer Prozes sor welcher auf FPGAs implementiert wird Er liegt als Architektur vor und wird durch einen in Mitrion C beschriebenen Algorithmus konfiguriert und schlie lich als Soft IP Core ausgegeben Im MVP wird jede Operation oder Menge von Operationen einer Verarbeitungseinheit einem sog Processing Ele ment PE zugeordnet Da ein PE nur einen sehr kleinen Teil des Programmes ausf hrt normalerweise nur eine oder wenige Operationen entsteht eine sehr feingranulare Prozessorstruktur Massive Parallel verarbeitung entsteht dadurch dass eine Vielzahl von PEs gleichzeitig arbeiten und interagieren k nnen F r jedes Mitrion C Programm wird der MVP individuell konfiguriert und beinhaltet nur diejenigen PEs
168. sten genutzten HDLs sind Verilog und VHDL In dieser Arbeit wurden alle Fallbeispiele siehe Kapitel 5 in VHDL geschrieben weshalb im Folgenden ausschlie lich auf diese HDL eingegangen wird Grundlagenwissen zum Entwurf mit VHDL wird in und vermittelt worauf auch die folgenden beiden Abschnitte basieren Einer der wesentlich Gr nde VHDL anstelle von Verilog zu verwenden ist die gr ere Anzahl von Konstrukten zur High Level Modellierung vgl Smi96 wie z B e Anweisungen zur Erzeugung eigener abstrakter Datentypen e Bibliotheken mit Paketen zur Wiederverwendung e Konfigurationsanweisungen f r die Struktur des Entwurfs e Generate Anweisung um wiederkehrende Strukturen zu erzeugen e Anweisung zur Erstellung generischer Modelle mit individuellen Eigenschaften z B Bitweiten Alle aufgez hlten Konstrukte k nnen f r ein synthetisierbares Design verwendet werden Verilog bietet au er der Parametrisierung und entsprechender Parameter berladung von Modellen keine zu VHDL vergleichbaren High Level Konstrukte 4 2 1 Hardware Entwurf mit VHDL Die Sprache VHDL VHSIC Very High Speed Integrated Circuits Hardware Description Language dient der Beschreibung und Simulation von Hardware und ist in Europa die am weitesten verbreite te HDL Das Entwurfsziel kann programmierbare Logik wie Complex Programmable Logik Devices CPLDs oder FPGAs oder festverdrahtete Logik wie z B ASICs sein Urspr nglich entwickelt um Testumgebungen
169. stung auf eine Vielzahl von Prozessorkernen verteilt und kann nur durch effiziente Parallelisierung von Programmen genutzt werden Um Ausf hrungzeiten von Anwendungen zu verk rzen oder wissenschaftliche Berechnungen berhaupt zu erm glichen muss demnach ein hoher Aufwand in die effiziente parallele Programmierung investiert werden Eine weitere Herausforderung im HPC betrifft den immensen Stromverbrauch aktueller Systeme im Teraflop Bereich Wie zuk nftige Exaflop Systeme damit umgehen wird derzeit unter dem Schlagwort Green IT diskutiert Allerdings ist es im Moment noch eine offene Frage wie die erwarteten Leis tungssteigerungen erm glicht werden sollen ohne den CO gt Aussto zu erh hen Einen Beitrag zur Beantwortung dieser Frage k nnten Hardware Beschleuniger wie Grafikchips GPUs und Field Programmable Gate Arrays FPGAs sein Gemessen an der Performance k nnen beide eine deutlich geringere Leistungsaufnahme als CPUs erreichen Dennoch sind solche Beschleuniger nicht dar auf ausgelegt typische Aufgaben eines Mikroprozessors zu erf llen z B Ausf hrung des Betriebssys tems zwingend sequentielle Aufgaben wie Verbindungsaufbau abbau oder Lese Schreiboperationen auf Festplatten Zuk nftige HPC Systeme k nnen demnach aus einer Kombination von CPUs und spe zialisierten Beschleuniger Chips bestehen Aufgabe der HPC Programmierer bleibt dann die effiziente Verteilung der Arbeitslast vorzunehmen Dabei k nnten sequentie
170. swertung betracht einen RC100 FPGA XC4VLX200 wobei der Referenz CPU fiir MD5 Brute Force der Core2Duo Prozessor und f r das Damenproblem der Phenom Prozessor ist CPU Mitrion VHDL Sp Mii Sp VEDL sp VHDL MD5 Brute Force M Hashes s 88 288 1173 3 3 13 3 4 1 26 Damenproblem Teilprobl Std 23 21 531 0 9 23 1 25 3 Tabelle 6 1 Performance berblick Mitrion C Umsetzungen ben tigen im Durchschnitt laut Angaben des Herstellers Mitrionics in etwa dop pelt soviel FPGA Fl che Overhead durch die Processing Elements des MVP wie vergleichbare VHDL Implementierungen was bei einem auf Parallelit t basierendem Design die erreichbare Performance auf die H lfte verringert Diese optimistische Sch tzung konnte durch die Beispiel Implementierungen des MD5 Brute Force Algorithmus und des 26 Damenproblems nicht best tigt werden F r die VHDL Implementierungen wurden in allen Fallbeispielen bessere Messwerte als mit vergleichbaren Mitrion Umsetzungen erreicht 90 6 AUSWERTUNG 2500 2250 2000 1750 1500 sun ger Sen soo gt 1250 MByte s 1000 0 750 500 250 0 0 0625 0 125 0 25 0 5 1 2 4 8 16 32 64 128 256 512 1024 Datenmenge MiByte Direct Streaming VHDL Direct Streaming VHDL 100 Direct Streaming Mitrion ste SRAM VHDL SRAM Mitrion VHDL 100 Abbildung 6 2 Zusammenfassung des Datendurchsatzes mit Direct I O Ist die Anwendung gut durch Pipeline
171. t Ox1F amp cs gt gt uint 32 L 1i 1 5 bhO bhO q bu0 uint 32 bu0 q lt lt 1 bdO bAa0 qg gt gt 1 40 bh0 bu0 bd0 mem_bhl memwrite mem_bh0 L bhl mem_bul memwrite mem_bu0 L bul mem bal memwrite mem_bd0 L bdl 45 uint 32 sl uint 32 uint 32 0 lt lt N bhl bul bdl mem_sll memwrite mem_sl0 L sl tuple mem uint 32 N mem uint 32 N mem uint 32 N mem uint 32 N mem Loop tup mem_bhl mem_bul mem_bdl mem_sl1 50 Explore Solutions uint 46 cntO D int 32 i L ent mem_al while i gt L 55 mem_bht mem_but mem_bdt mem_slt untup mem_loop slot mem_slt1 memread mem_slt i mem_loopl tup mem_bht mem but mem_bdt mem_slt1l i cnt0O mem_loop if slot 0 124 ANHANG A QUELLCODES uint 32 inn i l 60 inn cnt0O mem_loopl else sloti slot amp uint 32 slot itmp cnttmp mem_looptmp if i lt N 1 p i 65 int 32 ipl i 1 slp mem_slt2 memread mem_slt1 i slpp slp sloti mem_slt3 memwrite mem_slt2 i slpp 70 bhp mem_bht1 memread mem_bht i bup mem_but1 memread mem_but i bdp mem_bdt1 memread mem_bdt i bhps bhp sloti 75 bups uint 32 bup sloti lt lt 1 bdps bdp sloti gt gt 1 mem_bht2 memwrite mem_bht1l ip1 bhps mem_but2 memwrite mem_butl ipl bups 80 mem_bdt2 memwrite mem_bdt1 ipl bdps sslip
172. t und zum anderen die Ansteuerung der RASC FPGAs vorgenommen werden Funktion der rasclib Bibliothek vel Tabelle 3 2 erm glichen die Kommunikation wobei Mitrion zus tzlich ein eigenes API anbietet Je nach Bereitstellungsaufwand der Daten liegt der Zeitaufwand im Bereich einiger Stunden Von SGI bereitgestellte Beispiele oder bereits geschriebene Programme helfen dabei den Aufwand zu verringern da die Ansteuerung verschiedener RASC Kommunikationsvarianten sehr hnlich ist 6 2 2 Ease of Use Bedienkomfort oder Bedienbarkeit sind im Grunde durch den Programmierer subjektiv gef hlte Eigen schaften Um diese dennoch bewerten zu k nnen werden sie anhand einiger Fakten und Beispielen ver anschaulicht Zudem sollte beachtet werden dass die Erwartungen gegen ber einer Hardwarebeschrei bungssprache sich von denen einer Hochsprache unterscheiden Um schnell eine einfache Anwendung auf die RASC Plattform zu portieren eignet sich Mitrion sehr gut weil zum einen die Einarbeitungszeit in die vom Syntax C hnliche Sprache recht kurz ist und zum anderen die Schnittstelle zum vorliegenden System einfach gehalten wurde Mit VHDL muss hingegen erst noch die Schnittstelle beschrieben und an das Verilog Wrapper Modul angebunden werden was insbesondere bei der Implementierung erster Beispielandwendungen M he bereitet und das ausf hrliche Studieren des RASC Benutzerhandbuchs SGIO8 erfordert Von einer sich an C anlehenden Hochsprache wird n
173. t Debugger und ein Algorithmus Konfigurationstool zur Verf gung Zudem werden einfache Beispielanwendungen von SGI angeboten um den Einstieg zu erleichtern 3 4 1 Abstraction Layer API Der RASC Abstraction Layer RASCAL ist eine Programmierschnittstelle API f r die kernel device driver und die RASC Hardware und bietet damit eine Schnittstelle zur Ansteuerung der RC100 FPGAs aus einem C oder Fortran Programm heraus RASCAL besteht aus zwei Ebenen wobei nur eine von beiden innerhalb eines Programmes verwendet werden darf die Co Prozessor COP Ebene und die Algorithmen Ebene Die zugrundeliegende COP Ebene stellt Funktionen zur individuellen Ansteuerung der FPGAs als COPs bereit Darauf aufsetzend erm glicht die Algorithmen Ebene mehrere COPs als eine logische Implementierung eines Algorithmus anzusprechen und bernimmt damit die Aufteilung von Daten auf die verschiedenen FPGAs und auch die Steuerung des Multibuffering siehe Abschnitt 3 3 1 auf Seite des Hosts Tabelle 2 gibt einen berblick ber einige rasclib Funktionen wobei die aufgef hrten Funktionen der COP Ebene entsprechende quivalente in der Algorithmen Ebene besitzen Die in der Tabelle stehenden Funktionsaufrufe sind in der Reihenfolge aufgelistet wie sie blicherweise benutzt werden Optional zu verwenden sind die Sende und Empfangs bzw die Lese und Schreibfunktionen wobei die Ausf h Bibliothek des RASC Abstraction Layer welche Funktion
174. t Schalter a Einfacher konfigurierbarer Logikblock b Schaltmatrix Abbildung 2 2 FPGA Logikblock und Schaltmatrix vgl Wik09 Abbildung 2 3 Paritatsbit fiir 32 Bit Wert 4 Eingangs LUT links 6 Eingangs LUT rechts 2 3 ST RKEN UND SCHW CHEN VON FPGAS 11 Ein CLB hat pro LUT nur einen Ausgang an welchem entweder der Wert des Flipflop oder LUT Ausgangs anliegt Die Durchschaltung des LUT Ausgangs erzeugt Logik w hrend ein Flipflop Werte puffert und damit den kritischen Pfad unterbricht Neben den Eing ngen f r die LUTs haben CLBs noch weitere Eing nge wie z B f r das Takt Signal Dieses und andere Signale mit hohem Fanout werden normalerweise ber spezielle Verbindungsressourcen verteilt Weitere spezielle Verbindungsressourcen zwischen benachbarten Logikbl cken k nnen sog Carry Chains implementieren CLBs sind untereinander ber Schaltmatrizen und entsprechende Verbindungskan le gekoppelt In Ab bildung wird eine solche Schaltmatrix mit programmierbaren Schaltern gezeigt F r diesen Fall einer planaren Topologie kann eine Leitung mit drei ebenso an die Schaltmatrix gekoppelten Kan len verbunden werden allerdings eine bestimmte Leitung auch nur auf eine andere Leitung in einem benach barten Kanal umgeleitet werden z B wird Leitung 1 mit Leitung 1 aus einem anderem Kanal verbunden Leitung 2 mit Leitung 2 aus einem anderen Kanal usw In modernen FPGAs siehe Abschnitt D AN werden fest verdrahtete
175. tally different approach through their flexible hardware description which in cases can be more efficient and increase operation speed Depending on their performance hardware accelerators can noticeably reduce the overall power consumption FPGAs provide fine grained parallelism with a large number of programmable logic blocks and can be adapted to a new task in a fraction of a second There are multiple approaches to program FPGAs hardware description languages Verilog VHDL high level languages e g Handel C Impulse C Mitrion C and graphic tools e g DSPLogic RC Toolbox The quality of the resulting hardware designs can in fact be very different which will be compared in this paper using sample implementations and benchmarks in Mitrion C and VHDL Thus the performance of the programming platform SGI RASC will be evaluated in this context Inhaltsverzeichnis 2 1 Typische Einsatzgebietel o oo aaa 2 2 Aufbau und Grundstruktur Architektur 2 2 2 2 oo oo nn 2 3 St rken und Schw chen von FPGAS 2 2 nn 24 Virtex FPGAS ne ace ass Ed Hot a Rw ae ei OP E A Aa A 2 5 Flie kommaverarbeitungsleistung 2 6 FPGAs als Hardware Beschleuniger im HP 3 1 SGI Altix ZOU 3 2 SGI RC100 FPGA Bladel e 3 32 2COfE SEIVICES Eee ae wee d de ee ee oe ee 3 3 1 SRAM Schnittstelle e 3 3 2 Streaming Enges 3 3 3 Memory Mapped Registers 3 4 Software cc co 20 2 2 sur eu 3 4 1 Abstraction Layer
176. tan zugreifbarer Speicher Die Anzahl der Speicherpl tze auf welche gleichzeitig zugegriffen werden kann ist ebenso ein begrenzender Faktor hinsichtlich der Parallelit t eines Systems Um also mehrere Werte gleichzei tig berechnen zu k nnen muss auch eine ebenso gro e Anzahl zur gleichen Zeit beschreibbarer Speicherpl tze vorhanden sein Damit muss jede Verarbeitungseinheit wenn alle gleichzeitig ar beiten sollen die M glichkeit haben ihre erzeugten Werte zu puffern Diese trivialen Regeln vgl Mit08b Kapitel 12 sollten beachtet werden wenn die m gliche Paral lelit t eines Algorithmus eingesch tzt und eine entsprechenden Implementierung davon erstellt werden soll Insbesondere sind die Datenabh ngigkeiten bei der Entwicklung und Bewertung paralleler Algo rithmen von Bedeutung W hrend sie durch den Mitrion C Compiler automatisch erkannt werden muss sich der Programmierer einer Hardwarebeschreibungssprache explizit um deren Erf llung k mmern Mitrion C erleichtert durch implizit parallele Programmierung und die Ausf hrung der Software auf dem MVP siehe die angegebenen Anforderungen zu erf llen 1 und 3 werden gr tenteils automatisch von Mitrion gehandhabt im Algorithmus vorhandene Datenabh ngigkeiten 2 f hren aber dennoch zu sequentieller Abarbeitung Es ist also f r beide die Programmierung von Mitrion C und VHDL ein effizienter paralleler Algorithmus notwendig um die Vielzahl an Verarbeitungseinheiten auf F
177. tmp 1 lt char 1 1 else dout_plain CHARS 8 1 downto CHARS 1 x8 lt char 0 CONV_STD_LOGIC_VECTOR vpipe 1 8 chartmp 1 lt char 1 end if Chart plaintext is valid cvld 0 lt 1 end if process charl if cvld 0 1 then if chartmp 1 lt vfirstchar then dout_plain CHARS 1 x8 1 downto CHARS 2 x8 lt characters chartmp 1 r chartmp 2 lt char 2 1 else dout_plain CHARS 1 8 1 downto CHARS 2 x8 lt chartmp 1 ANHANG A QUELLCODES AA MD5 BRUTE FORCE 121 85 90 95 100 105 110 20 25 chartmp 2 lt char 2 end if cvld 1 lt 1 end if set chars 2 to penultimate FOR c IN 2 TO CHARS 2 LOOP if cvld c 1 1 then if chartmp c lt vfirstchar then dout_plain CHARS c 8 1 downto CHARS c 1 x8 lt vlastchar chartmp c 1 lt char c t1 1 else dout_plain CHARS c 8 1 downto CHARS c 1 8 lt chartmp c chartmp c t1 lt char c 1 end if cvld c lt 1 end if END LOOP set last char if cvld CHARS 2 1 then if chartmp CHARS 1 lt vfirstchar then dout_plain 7 downto 0 lt vlastchar else dout_plain 7 downto 0 lt chartmp CHARS 1 end if cvld CHARS 1 lt III end if end if rst end if end process if last char is processed set output valid vld lt cvld CHARS 1 Auflistung A 11 Daten bertragung MD5 Brute Fo
178. twa drei Arbeitstagen erstellt werden Anschlie end wurden nur wenige Optimierungen durchgef hrt Eine ers te funktionierende VHDL Implementierung ben tigte ca drei Wochen und wurde seither in mehreren Iterationen verbessert wobei noch immer Optimierungen ausstehen Die Einarbeitungszeit in Mitrion C ist insbesondere bei Vorkenntnissen in der Programmiersprache C deutlich geringer als in VHDL da funktional und von der Hardware abstrahiert programmiert wird VHDL Programmierung ben tigt hingegen fundiertes Wissen ber die Hardware Um auf ein vergleich bares Niveau zu kommen wird die Einarbeitungszeit f r VHDL mit einem halben Jahr und f r Mitrion C mit einem Monat abgesch tzt Unter diesen Vorraussetzungen wird ein VHDL Entwurf zur Umsetzung eines Algorithmus etwa viermal soviel Zeit beanspruchen wie ein vergleichbares Mitrion C Programm wenn sich der Algorithmus mit beiden Sprachen umsetzen l sst Die Grundgedanken zum Entwurf eines Algorithmus der sich gut zur parallelen Abarbeitung eignet sind f r beide Programmierm glichkeiten gleicherma en zeitaufwendig und k nnen mit steigender Komplexit t des Problems die Implementie rungszeit bertreffen Eine deutliche Verringerung der Entwicklungszeit kann insbesondere bei Hardwarebeschreibung durch die Wiederverwendung von Entw rfen engl Design Reuse erwirkt werden VHDL Implementierungen bieten zudem durch die Abbildung des Algorithmus auf Hardwarestrukturen mehr Optimierun
179. tzterem k nnen die zur Implementierung von FP Verarbeitungseinheiten ben tigten Ressourcen f r Virtex 4 und Virtex 5 FPGAs entnommen werden Einige Kenndaten ber die in diesem Abschnitt betrachteten FPGAs sind in Tabelle 2 1 zusammenge fasst und werden in den folgenden Berechnungen verwendet Zu beachten ist auBerdem dass die Slices der Virtex Familien unterschiedlich viele FFs und LUTs beinhalten Um die FP Verarbeitungsleistung von FPGAs realistisch absch tzen zu k nnen muss ein Teil der Lo 2 5 FLIESSKOMMAVERARBEITUNGSLEISTUNG 17 FPGA Slices LUTs FFs DSP Slices FP LUTs FP FFs Virtex 4 LX200 89 088 178 176 178 176 96 105 451 105 451 Virtex 4 SX55 24 576 49 152 49 152 512 19 435 19 435 Virtex 5 LX330 51 840 207 360 207 360 192 124 907 124 907 Virtex 5 SX240T 37 440 74 880 74 880 1056 86 507 86 507 Virtex 6 LX760 118 560 474 240 948 480 864 302 827 618 987 Virtex 6 SX475T 74 400 297 600 595 200 2016 185 067 383 467 Virtex 4 Slice 2 FFs und 2 LUTs Virtex 5 Slice je 4 FFs und 4 LUTs Virtex 6 Slice 8 FFs und 4 LUTs Tabelle 2 1 Kenndaten einiger Virtex FPGAs gik fiir die Host FPGA Kommunikationsschnittstelle und den Speicherkontroller reserviert werden In SSWW08 werden daf r 20 000 Flipflops FFs und 20 000 Lookup Tabelle LUTs veranschlagt und in folgenden Berechnungen verwendet F r die RASC Core Services liegt dieser Wert j
180. uhlen 36 4 2 Integration von Mitrion in SGI RASC vgl Mit 8al 2 2222 38 4 3 _ Mitrion C Simulation mit GU 41 4 4 Vergleich von Hardware und Softwareentwicklung 2 2 2 222222 44 4 5 Hardware Synthese im berblick HocO8 Kapitel 1 0 0 49 5 1 Direct IO Streaming Durchsatz aller Knoten 256 MiByte 54 5 2 Durchsatz ber den SRAM des RC100 Bladesl 2 2 2 222 2m en 57 EE BS Gow ee 60 ee ee 62 5 5 Memory Mapped Registers Durchsatzmessung 63 5 6 MD5 Brute Force VHDL Entwurfl 2 2222 2 ee ee 66 5 7 MD5 Brute Force Performance Vergleich 2 2 22 2m mn 71 ward E ee E 4 Bal e a 72 aake Er ed gen E ee 73 PETI yaaa as 75 EE 79 6 1 Geschwindigkeitsgewinn einer durch FPGAs beschleunigten Anwendung 82 6 2 Zusammenfassung des Datendurchsatzes mit Direct UO 90 100 Abbildungsverzeichnis 101 Tabellenverzeichnis 2 1 Kenndaten einiger Virtex FPGAs l 2 22 22 Comm nn 17 2 2 FP Performance von Virtex 5 FPGAs im Vergleich zu Opteron Prozessor 18 2 3 Virtex FPGAs FP Performance Multiplikation Addition 64 Bit 32 Bit 18 3 1 Intel Itanium 2 Montecito Int06 Cache Hierarchiel e 22 3 2 Ausgew hlte Funktionen der rasclib Bibliothek 2 22 22m nennen 30 5 1 MDS5 Brute Force FPGA Ressourcen Nutzung VHDL 68 5 2 _MD5 Brute Force FPGA Ressourcen Nutzung Mon 69 5 3 Leistungsvergleich der MD5 Hardware Implementierungen
181. ult t 8 Eine der heute noch schnellsten Software L sungen des N Damenproblems wurde von Jeff Somers in der Programmiersprache C geschrieben siehe Som02 Eine bersicht der L sungen einiger bisher berechneter Damenprobleme bietet Tabelle 5 5 Eine Tiefensuche eignet sich hervorragend zur Parallelisierung was bei den hier betrachteten Implemen tierungen mit Vorbelegungen von Spalten vorgenommen wurde Dabei werden Damen bereits konflikt frei in den ersten Spalten plaziert und das Problem in Teilb ume aufgegliedert Mit steigender Anzahl vorplazierter Spalten steigt auch die Anzahl versteckter Konflikte wodurch einige Teilb ume zu keiner L sung mehr f hren Zudem erh ht sich der Berechnungsaufwand f r die Vorplazierungen w hrend er f r die Teilprobleme sinkt Eine genauere Betrachtung dieses Problems wird in PNS09 vorgenommen 74 5 FALLBEISPIELE N eindeutige L sungen alle L sungen 1 1 1 5 1 10 8 12 92 15 2 85053E5 2 279184E6 19 6 21012754E8 4 968057848E9 22 3 36376244042E11 2 691008701644E12 23 3 029242658210E12 2 4233937684440E13 24 2 8439272956934E13 2 27514171973736E14 25 2 75986683743434E14 2 207893435808352E15 26 Tabelle 5 5 L sungen einiger N Damenprobleme Das Queens TUD Projekt und damit auch die hier betrachteten Implementierungen verwenden sechs vorplazierte Spalten um das 26 Damenproblem in Teilprobleme aufzuspalten Dies h lt den Kommu nikationsaufwand gering und ha
182. und der MVP Architektur synthetisierte VHDL Be schreibung als auch f r handgeschriebenen VHDL Code muss eine Hardware Synthese durchgef hrt werden um eine der Beschreibung entsprechenden Implementierung zu erhalten Abbildung 4 5 Hardware Synthese im berblick HocO8 Kapitel 1 50 4 PROGRAMMIERM GLICHKEITEN DER SGI RASC PLATTFORM High Level Synthese Dieser erste Synthese Abschnitt zerlegt die Verhaltensbeschreibung in Daten und Kontrollpfad Es wer den im Wesentlichen drei Vorg nge durchgef hrt 1 Allokation Ermittlung der zu verwendenden Ressourcen 2 Binding Zuordnung von Operationen und Variablen zu Ressourcen 3 Ablaufplanung engl Scheduling Planung des zeitlichen Ablaufs aller Operationen Logik Synthese und Logik Minimierung Ein weiterer Synthese Schritt ist die Umwandlung der Komponenten auf Register Transfer Ebene in Schaltfunktionen boolesche Funktionen Wesentliche Aufgaben sind hier e Zustandskodierung von endlichen Automaten FSM bei FPGAs meist One Hot Kodierung e Dekomposition von FSMs Umwandlung komplexer FSMs in eine Komposition einfacher FSMs welche einfacher zu implementieren sind e Darstellung von FSMs durch bergangslogik und Zustandsregister e Abbildung der Datenpfad Komponenten auf Schaltfunktionen W hrend der Logik Minimierung wird schlie lich versucht eine minimale Implementierung gegebener Schaltfunktionen zu erreichen und damit eine kosteng nstige Realisierung eine
183. ung Mit den sog Generics wird ein generischer Hardwareentwurf erm glicht Als Paramter einer Schnitt stelle lassen sich damit Entw rfe schnell und einfach anpassen Das Generate Statement erlaubt die Beschreibung sich wiederholender oder bedingter Strukturelemente In Mitrion C l sst sich eine Para metrierung des Entwurfs ber define Anweisungen l sen VHDL benutzt ein Bibliothekskonzept um den Zugriff auf gemeinsame Datenbest nde zu erm glichen Entw rfe wiederzuverwenden und herstellerspezifische Bibliotheken einzubinden Pakete sind Bestand teile von Bibliotheken und k nnen lokale Typen und Konstanten Komponentendeklarationen Funktio nen und Prozeduren b ndeln Sie werden wie Einheiten in Schnittstelle und Implementierung unterglie dert Ein m chtiges Hilfsmittel f r Verhaltensmodelle sind Funktionen und Prozeduren welche jedoch nur in beschr nktem Umfang in der Synthese unterst tzt werden Eine M glichkeit den Hardware Entwurf gro er System z B SoCs zu vereinfachen und zu beschleuni gen sind IP Cores Intellectual Property Cores In der Halbleiterindustrie werden damit fertige Entw rfe bezeichnet welche in anderen Entw rfen erneut verwendet werden k nnen Design Reuse K rzere Ent 4 2 HARDWARE ENTWICKLUNGSABLAUF 47 wicklungszeiten f hren meist auch zu geringeren Kosten Es wird zudem zwischen Soft IP Cores und Hard IP Cores unterschieden Hard IP Cores sind als fertige Schaltung herstellerseitig un
184. ungsrechnen Diplom arbeit Oktober 2008 WANNEMACHER Markus Das FPGA Kochbuch MITP Verlag 1998 ISBN 3 8266 2712 1 WIKIPEDIA Field Programmable Gate Array April 2009 http de wikipedia WANG Xiaoyun YU Hongbo How to Break MDS and Other Hash Functions Shandong University Jinan 250100 China 2005 Forschungsbericht XILINX Getting started with FPGAs Webseite http www xilinx com company gettingstarted index htm XILINX Virtex 4 Family Overview DS112 v3 0 Produkt Spezifikation Sep tember 2007 nttp www xilinx com support documentation data_ sheets ds112 pdf XILINX Floating Point Operator v4 0 DS335 Produkt Spezifikation April 2008 http www xilinx com support documentation ip_ documentation floating_point_ds335 pdf XILINX Virtex 4 FPGA Configuration User Guide v2 10 April 2008 x com support documentation user_guides ug071 pdf XILINX Virtex 4 FPGA User Guide 2008 http www xilinx com support documentation user_guides ug070 pdf XILINX Virtex 5 Family Overview DS100 v5 0 Produkt Spezifikation Fe bruar 2009 http www xilinx com support documentation data_ sheets ds100 pdf XILINX Virtex 6 Family Overview DS150 v1 1 Produkt Spezifikation Mai 2009 http www xilinx com publications prod_mktg Virtex6_ Overview pdf 107 A Quellcodes A 1 SRAM Schnittstelle Auflistung A 1 Steuerung der SRAM Kommunikation mit
185. urcen Nutzung VHDL aber 96 Bit breiter Block RAM FIFO die Pufferung der Werte Vorplazierung L sung Eine minimale Ressourceneinsparung w re noch durch exakte Anpassung der ADRs und FIFOs an die wirklich ben tig ten Bitbreiten 29 Bit f r die Vorplazierung und 46 Bit f r die L sung m glich Durch die Verwendung von Block RAM kosten die tiefen FIFOs kaum Ressourcen und k nnen f r den unwahrscheinlichen Fall dass alle Teilprobleme mit der Berechnung gleichzeitig fertig werden die L sungen puffern und neue Vorplazierungen bereitstellen Die Bl cke zwischen den FIFOs und ADRs stellen die Empfangs und Sendelogik dar Insgesamt bleibt der Ressourcenbedarf des Kommunikationsmoduls unter 1 der FPGA Fl che wobei f r die gesamte Kommunikation noch die Ressourcen der Core Services hinzukom men Eine bersicht der Ressourcenausnutzung der kompletten Damenproblem Implementierung bietet Tabelle Die Host Anwendung initiiert durch periodische Anfragen engl Polling die L sungs bertragung Da bei wird zur Entlastung der Kommunikation nach einer erfolglosen Anfrage 30 Sekunden gewartet F r jede empfangene L sung wird wieder eine Vorbelegung an den FPGA gesendet Weder das Direct Streaming noch die Kommunikation ber den SRAM eignen sich zur Integration in die Queens TUD Infrastruktur da sie keinen dauerhaften Betrieb mit zwischenzeitlicher Ergebnisabfrage erlauben Daten werden hier pro Durchlauf einmal gesendet und empfangen Zwis
186. urz erkl rt werden wie ein Algorithmus arbeitet der alle L sungen eines Damen problems mit dem Backtracking Verfahren findet Es wird angenommen dass die Tiefensuche spalten weise vorgenommen wird Das Nassi Shneiderman Diagramm in Abbildung 5 9 zeigt das Prinzip des Algorithmus Hierbei muss beachtet werden dass freie durch keine Dame bedrohte Felder in einer Spalte nur in eine Richtung nach oben oder unten besetzt werden k nnen Dies ist beim R ckspringen von Bedeutung weil die dort bereits plaziert Dame nur auf freie Felder in der vereinbarten Richtung gesetzt werden darf Beim Backtracking muss eine Dame entfernt werden wenn zweimal hintereinander nicht gesetzt bzw umgesetzt werden konnte while Spalte gt 0 freies Feld in aktueller Spalte Ja vorhanden nein setze Dame auf n chstes freies Feld entferne Dame ja letzte Spalte ein Spalte Spalte vorletzte Spalte Spalte L sung Abbildung 5 9 Damenproblem Backtracking Algorithmus W hrend ein naiver Brute Force Algorithmus f r das klassische Damenproblem 64 63 62 61 60 59 58 57 fast 60 5 Plazierungen vornimmt und zus tzlich deren G ltigkeit berpr ft setzt eine effizientere Variante in jeder Spalte nur eine Dame 8 Plazierungen Das Backtracking Verfahren kann als sehr effizienter Brute Force Algorithmus angesehen werden und reduziert die durchgef hrten Plazierungen noch einmal deutlich auf unter acht Fak
187. us abgesch tzt werden in welchem die Simulation auf dem optimierten Graphen durchgef hrt wird F r zuk nfige Mitrion Versionen hat Mitrionics einen taktgenauen Graphen vgl Timing Simulation in Abschnitt 14 2 2 angek ndigt der allerdings erst nach der Hardware Synthese siehe Abschnitt 14 2 3 angezeigt werden kann Es werden einige M glichkeiten geboten um durch den Graphen zu navigieren Neben einfachem Ver schieben und Bl ttern k nnen vergr ert verkleinert und Funktions oder Strukturknoten auf und zu geklappt werden Zur schnelleren Simulation ist es m glich Breakpoints zu setzen und die Anzeigege schwindigkeit anzupassen Au erdem kann die Ausf hrung Schritt f r Schritt durchgespielt unterbro chen oder zur ckgesetzt werden Simulation mit Kommandozeile Im Batch Modus l uft das kompilierte Mitrion C Programm ohne Unterbrechung durch und gibt Aus gaben entsprechend im Quellcode angegebener Beobachtungspunkte engl Watchpoints aus Zus tzlich k nnen auch Speicherzugriffe ausgegeben werden Im Gegensatz zum grafischen Debug Modus ist die Simulation im Batch Modus der konkreten Imple mentierung des MVP auf dem FPGA sehr nahe auch wenn keine Hardware Beschr nkungen betrachtet werden Damit erm glicht diese Art der Simulation eine Absch tzung der Performance des Mitrion C Programmes auf dem FPGA Eine entsprechende Konsolenausgabe am Ende des Simulationsdurchlaufs stellt die Anzahl der 1OOMHz Taktzyklen dar
188. uss dann daf r gesorgt werden dass der Host und der Algorithmus nicht gleich zeitig auf diese Register schreiben k nnen 5 3 2 Tests und Messungen Das Design ben tigt laut Ausgaben der Hardware Synthese 9 der Virtex 4 Slices und damit etwas mehr Ressourcen als die Direct Streaming Beispiel Implementierung Allerdings wurden mit 32 ADRs aus Timing Gr nden zus tzlich gepuffert acht Debug Registern und einem 512 Werte tiefen 64 Bit Block RAM FIFO schon vom Algorithmus mehr Ressourcen verwendet Die Durchsatzmessungen zeigen deutlich geringere Ergebnisse als beim Streaming Abbildung 5 5 zeigt den erreichbaren Datendurchsatz bei der bertragung von 512 64 Bit 4KiByte in Abh ngigkeit von den verwendeten ADRs Das hostseitige Polling ist in dieser Messung optional Wird angenommen dass die Ausgangsregister beim Auslesen immer g ltig sind ist keine Anfrage ber deren Zustand notwendig und der Durchsatz erh ht sich Eine solche Annahme kann daraus resultieren dass zwischen dem Schrei erster eingehender Wert wird durchgereicht und liegt direkt am Ausgang an 5 4 MD5 BRUTE FORCE 63 p a a w a gt Datendurchsatz MByte s N 1 2 4 8 16 Algorithm Defined Registers mit Polling ohne Polling Abbildung 5 5 Memory Mapped Registers Durchsatzmessung ben und Lesen eines Registers durch den Host etwa 400 Takte bei 200 MHz Taktfrequenz 2us liegen Werden mehrere Pakete hintereinander vom Host gesendet oder
189. ut_vld amp rasc_out_vld 1 RASCLIB_IMMED_CMD rasclib_cop_commit cop_desc NULL 40 while rasc_out_vld 1 lese den Klartext rasclib_cop_reg_read cop_desc plain448 dout_plain SIZE_PLAIN RASCLIB_IMMED_CMD rasclib_cop_commit cop_desc NULL 45 end gtod speichere Endzeit gebe Klartext aus DEBUG_OUT Plaintext as 64bit hexadecimal values n 50 Lor i 0 i lt SIZE PLAIN i printf 0Ox lx dout_plain i long2String unsigned long long amp dout_plain i DEBUG_OUT n 55 gebe den Zeitbedarf und die Hashes pro Sekunde aus printf Die Programmlaufzeit betrug 1f Sekunden n double end start no of hashes created 1st char 96 characters multiple of implemented pipelines 60 2nd to 5th char ASCII 32 to 126 95 characters printf 31 fM Hashes sec n 96 pow 95 4 1000000 0 end start beende den Algorithmus finish_alg 1 65 res rasclib_cop_reg_write cop_desc finish_alg amp finish_alg 1 RASCLIB_IMMED_CMD if res RASCLIB_SUCCESS fprintf stderr reg write of finish_alg failed at d d n LINE rasclib_perror reg write of finish_alg res return 1 res E 70 gebe den FPGA frei if res freeFPGA amp cop_desc alg_name lt RASCLIB_SUCCESS fprintf stderr Could not release FPGA Error Code d n res 75 rasclib_perror FPGA could not be
190. ver nderbar in den Chip des FPGAs integriert siehe z B Abschnitt 2 4 Soft IP Cores hingegen liegen typischerweise als generische Netzlisten oder aber HDL Quellcode vor Diese Darstellung als Netzliste sch tzt den An bieter vor Reverse Engineering verhindert allerdings auch die Portierung auf beliebige Zielplattformen Daher bieten die FPGA Hersteller in ihren Entwicklungsumgebungen IP Core Generatoren zur Erzeu gung von Netzlisten fiir verschiedene FPGA Modelle an Zudem gibt es Unternehmen die sich darauf spezialisiert haben Teile oder komplette integrierte Schaltkreise zu entwerfen und Lizenzen dieser De signs zu verkaufen Typische Beispiele f r Soft IP Cores sind Mikrokontroller wie PicoBlaze Synthe tisierbare IP Cores die im HDL Quellcode vorliegen erm glichen dem Benutzer Anpassungen auf der funktionalen Ebene vorzunehmen und k nnen sowohl f r FPGAs als auch ASICs benutzt werden Beide Formen von Soft IP Cores werden im frei programmierbaren Bereich eines FPGAs implementiert Ein IP Core im Schaltkreisentwurf ist vergleichbar mit einer Bibliothek in der Hochsprachenprogrammie rung Es gibt zwei typische in VHDL verwendete Programmierstile H ufig wird der Datenflussstil verwendet auch in den Fallbeispielen dieser Diplomarbeit Hierbei werden pro Komponentenarchitektur eine Viel zahl parallel ablaufender meist kleiner synchron getakteter Prozesse und nebenl ufiger Anweisungen beschrieben Mit den Prozessen werden einzelne
191. verschiedenen Bereichen und An 8 2 FPGAS wendungen Besonders in Bereichen in denen Algorithmen oder Protokolle schnell weiterentwickelt werden ist die Verwendung rekonfigurierbarer L sungen vorteilhaft Produkte k nnen so schneller auf den Markt gebracht und an neue Entwicklungen angepasst werden Au erdem lassen sich Entwicklungs fehler durch die Rekonfigurierbarkeit nachtr glich beheben Im Folgenden werden einige Beispiele f r den Einsatz von FPGAs genannt vgl Xil Prototypen FPGA basierte Prototypen dienen der Verifikation eines Hardwareentwurfs Da die Um setzung eines Designs auf einen ASIC sehr kostenintensiv ist kann die Funktionsf higkeit der ent wickelten Hardware vorher auf einem FPGA berpr ft werden Zudem kann die Gesamtsystem Simulation einer komplexen Schaltung nicht mehr effizient durchgef hrt werden Automobilindustrie Die Automobilelektronik nutzt zunehmend FPGA basierte Schaltungen um z B den effizienten Transport von Datenstr men zu steuern mehrere Peripheriefunktionen im Auto zu vernetzen Navigation Infotainment oder Fahrerassistenzsysteme anzusteuern Signalverarbeitung F r L sungen zur bertragung von Video und Audio Daten vom Erzeuger zum Verbraucher und die entsprechende Signalverarbeitung wie z B die Decodierung von Musik Sprache und Datendiensten werden FPGAs eingesetzt Kommunikationstechnik FPGAs sind sowohl in der drahtlosen als auch in der drahtgebundenen Kommu
192. vor Es beschreibt neben der Mitrion SDK und auch den Funktionsumfang von Mitrion C und bietet damit eine Einf hrung in die Programmierung dieser Sprache Ein in Mitrion C geschriebenes Programm kann auf entsprechend unterst tzten Plattformen in Hardware umgesetzt werden genauere Details der zugrundeliegenden Hardware werden dem Programmierer je doch verborgen Der Syntax ist dem von ANSI C sehr hnlich und soll die Einarbeitungszeit f r den Entwickler verk rzen und die Portierung von C Code zu Mitrion C Code erleichtern Das Prinzip der Hardwarebeschreibung basiert auf dem MVP welcher in Mitrion C programmierte Soft ware auf dem FPGA ausf hrt und damit Software von Hardware isoliert Die Anpassung eines Program mes an den MVP wird durch die Processor Configuration Unit der Mitrion SDK vorgenommen Dieser Vorgang besteht aus der Entscheidung ber die ben tigten verarbeitenden Elemente PEs und der Ver schaltung dieser Das Prozessor Design wird vom Mitrion SDK als VHDL Code ausgegeben und kann anschlie end synthetisiert auf die Zieltechnologie abgebildet plaziert und verdrahtet werden Mitrion C und der MVP erben die Beschr nkungen die die Programmierung von FPGAs mit sich bringt e Durch die Umsetzung der Befehle in Logik und damit FPGA Ressourcen ist die maximale L nge von Programmen beschr nkt Die Speicherverwaltung ist vergleichsweise rudiment r Der Nutzer muss daf r sorgen dass Daten in verschiedenen Adressr u
193. weise konstant mit der L nge des Quellcodes Durch den l ngeren Quellcode bei der Umsetzung vergleichbarer Algorithmen werden sol che Fehler beim VHDL Entwurf h ufiger vorkommen als bei Mitrion C Programmen Allerdings gibt es im Verleich zu Mitrion C f r VHDL Entwicklungsumgebungen und Editoren mit VHDL Syntax Hervorhebung was diese Art von Fehler wiederum verringert Einige semantische Fehler wie z B nicht erlaubte Zuweisungen von Signal bzw Variablentypen werden ebenso bereits w hrend der bersetzung erkannt und k nnen meist schnell behoben werden Bei Mitrion C wird Variablen ohne explizite Typ angabe automatisch anhand der ersten Zuweisung ein Typ zugeordnet Dies verringert einerseits Fehler w hrend der bersetzung kann aber zu inhaltlichen Fehlern f hren Ein Beispiel hierf r ist die Addi tion von Zahlen dessen Summe bei Mitrion C ein Bit breiter als der gr ere der beiden Summanden ist VHDL ist hingegen eine streng typenorientierte Sprache und ein verwendetes aber nicht deklariertes Signal f hrt w hrend der Syntaxpr fung zu einem Fehler Eine fehlerhafte VHDL Implementierung folgt h ufiger daraus dass Daten nicht im vorgesehenen Takt am gew nschten Signal anliegen oder es wurde vergessen einem Signal einen Initialwert zu berge ben Solche Fehler im Hardware Design k nnen mit Mitrion C nicht auftreten da Datenabh ngigkeiten automatisch gehandhabt werden und einer Variablen bei der Deklaration ein Wert bergeben
194. werden noch die verarbeiteten Instance Tokens zur ck gegeben Das Mitrion C Programm besteht damit aus einer durch ihre Bandbreite begrenzten Schleife Mitrion Bandbreitengraph wobei jedoch die Speicherzugriffe zu einer sequentiellen Verarbeitung der Daten f hren Die VHDL Umsetzung des Datentransfers ber den RC100 SRAM ist im Wesentlichen deswegen auf wendiger als in Mitrion C weil der Kontrollfluss zwischen Core Services und Algorithmus zus tzlich implementiert werden muss Ein Ausschnitt des VHDL Quellcodes ist im Anhang gelistet Nicht enthalten sind die Schnittstelle und die Signaldefinitionen sowie ein Prozess zur Messung der Latenz von indizierten Speicherzugriffen Der erste Prozess sendet Leseanfragen f r die SRAM Bank 0 an den Speicherkontroller sobald dieser signalisiert dass er bereit ist Dabei werden gelesene Worte gez hlt und beim Erreichen der vom Host Programm bermittelbaren Grenze Algorithm Defined Register keine weiteren Anfragen mehr gesendet Der zweite Prozess nimmt wie bei der Mitrion C Implementierung zwei 16 Bit Additionen vor und schreibt die Werte in SRAM Bank 1 Das Offset Zeilen 16 und 42 f r die Adressierung des Speichers wird durch die Core Services gesetzt und erm glicht Multibuffe ring Im Unterschied zur Mitrion C Implementierung muss die Anzahl der zu verarbeitenden W rter vom Host Programm angegeben werden Dies erh ht die Flexibilit t und erlaubt es Datenpakete kleiner 5 1 SRAM SCHNITTS
195. z zu Mitrion C Implementierungen zus tzlich die Verilog Wrapper Module und die Konfigu rationsdateien erzeugt werden z B mit dem Algorithmus Konfigurations Tool siehe Abschnitt 3 4 4 Wird wie in dieser Arbeit VHDL verwendet muss in der Schnittstelle zum Algorithmus Verilog Modul anschlie end noch die Verdrahtung zu den VHDL Komponenten vorgenommen werden Um zu spezi fizieren welche Kommunikationsressourcen genutzt werden m ssen zus tzlich zu den Konfigurations dateien die Extractor Anweisungen als Kommentare im Quellcode erstellt werden Bei Mitrion C be steht die Schnittstelle zu den Core Services aus ber und R ckgabeparametern der main Funktion Die Wrapper Module und Extractor Anweisungen werden daraus automatisch erzeugt Nach der Beschreibung des Algorithmus folgt die Hardware Synthese welche je nach betriebenem Auf wand zu unterschiedlichen Ergebnissen f hrt Komplexere Optimierungsvorg nge k nnen mit einer gr Beren Wahrscheinlichkeit die Entwurfsanforderungen erf llen beanspruchen jedoch mehr Zeit Mitri on erlaubt die Einstellung des Hardware Synthese Aufwandes in drei Stufen Vor der Generierung des 54 5 FALLBEISPIELE 2800 2400 2000 1600 1200 MByte pro Sekunde Abbildung 5 1 Direct IO Streaming Durchsatz aller Knoten 256 MiByte VHDL Designs werden allerdings noch die voraussichtlich ben tigten FPGA Ressourcen abgesch tzt und ggf die Hardware Ums

Diplomarbeit - Queens@TUD - Technische Universität Dresden

Contents

Download Pdf Manuals

Related Search

Related Contents

Diplomarbeit - Queens@TUD - Technische Universit&auml;t Dresden

Contents

Download Pdf Manuals

Related Search

Related Contents

Diplomarbeit - Queens@TUD - Technische Universität Dresden