Home

Vorlage zur Erstellung von Haus- und Diplomarbeiten

1. AUFGABES TASK 11 4 TASKS NAME b 32 Task Ii 4 OPTIMIZATIONTYPE 1 NAME ROOT IMPORTANCE 1 OPTIMIZATIONTYPE 1 FAILURE PROBABILITY 0 5 IMPORTANCE 1 LEVEL 3 FAILURE PROBABILITY 0 5 PRIORITY 4 LEVEL 3 TIMING 0 PRIORITY 4 RESOURCHO S AO TIMING 0 IORELATIONS RESOURCES ORELATION IORELATIONS INPUT 48 ORELATION OUTPUT 87 INPUT 48 69 93 90 96 CONDITION true OUTPUT 66 CONDITION true SUBTASKS SUBTASKS TASK ill 4 TASK 20 NAME Par2 NAME Bottom OPTIMIZATIONTYPE 1 OPTIMIZATIONTYPE 1 IMPORTANCE 1 IMPORTANCE 1 FAILURE PROBABILITY 0 5 FAILURE PROBABILITY 0 5 LEVEL 3 EVEN Se 4 9 PRIORITY eu PRIORITY TIMING 0 TIMING 0 EESQUEGESEE E2208 ME AN REISOURERS ion NY IORELATIONS IORELATIONS IORELATION ORELATION INPUT Sa xeu INPUT Al 54 7e n OULEUI da S guuisum 1575 j CONDITION true jJ CONDITION true SUBTASKS SUBTASKS MAGIC 29 1 TASK 41 NAME top NAME d 32 OPTIMIZATIONTYPE 1 OPTIMIZATIONTYPE 1 IMPORTANCE 1 IMPORTANCE 1 FAILURE PROBABILITY 0 5 FAILURE PROBABILITY 0 5 LEVEL 3 LEVEL 3 PRIORITY 4 PRIORITY 4 TIMING O TIMING 0 RESOURCES 8 20 jy 7 RESOURCES A Sri many IORELATIONS ORELATIONS ORELATION ORELATION INPUT 75 gy 3 INPUT 93 OUTPUT 84 63 60 OUTPUT 181 CONDI
2. HCDM File Syntax incorrect The information is entered in the wrong way Recheck the grammar Scheduling File Syntax incorrect The information is entered in the wrong way due to the grammar Verify that the scheduling file got the correct format The correct format is stated in the VHDLGenerator Reference Manual Components File Syntax incorrect The information is entered in the wrong way Recheck the grammar The converting to VHDL failed Make sure that the data flow graph is specified in a correct way no loops no tasks without inputs Testbench could not be created Recheck if VHDL code is testable More Ports are assigned to the component than allowed Increase either number of ports or decrease number of component ports The Input port bit width does not fit with the specified component input bit width Change either Input Bit Width of Port or component The output port bit width does not fit with the specified component output bit width Change either Output Bit Width of Port or component Figure 27 Error Type Reference The Data Flow Graph Compiler page 42 3 4 The Converter stage The VHDL Converter stage finally converts all collected and pre processed data to synthesizable VHDL code We make use of the Java streaming concepts already discussed in Chapter 3 2 2 to write a character stream into a text file 3 4 1 The VHDL Code Generator In the DFG a task can only fire if all of its inputs are
3. REICTEN CES NE tote ubt cM p Loc AO EAE tc cUm 81 List of Figures VIII List of Figures Figure l proposed Design POWs sedici oca merda at sanes c RAO E SON 2 Figure 2 Task EEN 6 Figure 3 HCDM Task Graph example screenshot 7 Figure 4 Data Flow Graph example sie tete ea Ge se hada 8 Figure 5 Task description an HCDM o itti ee See EE tas Se ges Ie Ede 10 Figure 6 Model of a classical compiler eee eee eene Ge AA EG 12 Figure 7 Model of the Data Flow Compiler esee 13 Figure 8 EE 17 Figur 9 Parser State E 18 Figure 10 Task declaration inside HCDM sese eene 19 Figure 11 BNF description of Parser pattern uie e cipere se d Ser bo teta cons 20 Figure 12 Scheduling File example uidit D tee iiem pde ut aiti c n 22 Figure 13 Components File example ii s aded eredi etre tae eoa ASe de ce 23 Figure 14 O n NOTES T Ee ER EE OR EE Een 25 Figure 15 O ndoy D Sons usn resti a apex aia Vo Tes qub osa A mt 25 Figure 16 Quicksort pseudo COG vs doeet mega detenci De EE e Dia M des Uus EE 26 Figure 17 Vertex Coloring pseudo code RS ER GE ND N ee Ge 28 Figure 18 Compatibility GEED ES aene de Ga ad 29 Figure 19 Non minimum Coloring Figure 20 Minimum Coloring 29 Figure 21 Left Edge pseudo code iis se se esa Eed 31 Figure 22 Left Edge pseudo code for VD Generator 33 Figure 23 Error Level classification 252 uei ea b pares et lebe eaten 34 Figure 24 Exc
4. 70 BINDING Par2 myAnd 2 b 32 Input 2 Bottom myOr 1 top myXor 1 a 32 Input 3 Par3 myAnd 1 result 32 Output_1 Figure 12 Scheduling File example In the first line of the scheduling file the start and stop times of the tasks are listed Keywords are here the task names of the task that are already stored in the ArrayList variable To every task the start time and stop time token is assigned Later on one single time unit produced by HCDM will mapped to a single clock cycle inside the VHDL code Note that the first entries in the scheduling file are the external inputs and outputs These have to be removed out of the task array afterwards Also the word true is only used as delimiter and is therefore ignored during the parsing process When the schedule parsing has finished the parsing of the component binding starts The trigger for the binding line is the keyword BINDING which is the first word in line Extracted Tokens are associated to the respective task 3 2 2 5 Parsing the Components File The components on which the tasks run have to be specified somewhere For that reason a text file is created to enter the needed components To simplify the parsing work we can completely abstract from the components behavior In fact it is only necessary to define the interface of a component The behavior will be included later as a library inside the generated VHDL code Figure 13 shows how the components file looks l
5. IEEE Design Automation Conference LosAngeles USA CA 90089 0781 Automated Synthesis of Data Paths in Digital Systems IEEE Transactions on Computer Aided Design Volume 5 July 1986 Lin T C and Cyre W R 1997 An algorithm based on the Hungarian method for register reduction during complex functional unit allocation Southeastcon 97 Engineering new New Century Proceedings IEEE Blacksburg USA April 1997 Zhang S and Dai W W M 2000 Linear Time Left Edge Algorithm INT L Conference on Chip Design Automation Proceedings of ICDA2000 Beijing China February 2000 Cooke J 1998 Constructing Correct Software the basics London Springer Verlag pp 10 11 Oh M 1999 Transformation and VHDL Code Generation from Coarse grained Data Flow Graph online Department of Computer Engineering Seoul National University Available at http peace snu ac kr publications data 142 ms 1999 oh moonwook pdf Accessed at 14 September 2006 References page 84 20 21 22 23 24 24 Oh M and Ha S 1998 Synthesizable VHDL Code Generation from Data Flow Graph Proceedings of the 5th Asia Pacific Conference on Hardware Description Languages Seoul Korea July 1998 Fletcher J 2001 AWT vs Swing online Borland Developer Network Available at http bdn borland com article 0 1410 26970 00 html Accessed 23 August 2006 Eckstein R and Loy M and Wood D 1998 Java Swing
6. VCC zu XORCY E FlipFlops Latches 3t Clock Buffers sd BUFGP 2d 3t IO Buffers 193 4 IBUF 161 OBUF 332 Selected Device 3s200ft256 5 Number of Slices Number of Slice Flip Flops Number of 4 input LUTs Number of IOs Number of bonded IOBs Number of GCLKs 401 outof 1920 20 612 outof 3840 1596 348 outof 3840 996 194 194 outof 173 112 1 outof 8 12 Figure 40 Synthesis report without register Conclusions page 66 Final Report Final Results RTL Top Level Output File Name VhdlCodeGenerated ngr Top Level Output File Name VhdlCodeGenerated Output Format NGC Optimization Goal Speed Keep Hierarchy NO Design Statistics IOs 194 Cell Usage BELS 545 GND ga INV 32 LUTI 29 LUT2 SCH LUT2L zu LUT3 3S LUT3 D 8 LUT3_L 2 LUT4 236 LUTAD 39 LUTAL SH MUXCY 39 MUXF5 64 VCC cil XORCY 29 FlipFlops Latches FDC 173 FDCE 359 FDE 388 Clock Buffers N BUFGP ze IO Buffers 28105 IBUF 161 OBUF 22 Selected Device 3s200ft256 5 Number of Slices 434 outof 1920 22 Number of Slice Flip Flops 593 outof 3840 15 Number of 4 input LUTs 461 outof 3840 1296 Number of IOs 194 Number of bonded IOBs 194 outof 173 112 Number of GCLKs outof 8 12 Figure 41 Synthesis report with left edge register minimization A comparison of bot
7. c CompInReg3 lt reg 0 museo il emele lt Vis timer timer 1 reg D lt CompOutRegl ue l enable lt UE timer lt timer 1 CompInReg6 reg 1 CompInReg7 lt reg 0 enpmREA cc grote Ji ease lt gt JL timer timer 1 result CompOutReg3 mie l emele lt Ur timer lt timer 1 83 gt timer lt 83 end of Schedule others gt timer lt timer 1 only count up end case end if end process end arc Figure 45 complete VHDL code with register minimization Appendix B page 77 The used components for the boolean equation look the same for both versions The XOR component library IEEE use IEEE std logic 1164 al1 entity myXor is jou Ellis reseta 8 dm erter leges enable alm see lonis as aia eccl logie ies or Si corato 0 b in std logic vector 31 downto 0 result out std logic vector 31 downto 0 end myXor architecture RTL of myXor is begin process clk resetn variable delay integer range 0 to begin if resetn 0 then delay 0 result lt others gt 0 elsif CLK event and CLK 1 then if enable 1 then if delay 20 then result lt a xor b delay 0 delay delay 1 result lt others end if else delay 0 result lt others gt 0 end if end if end process end RTL Figure 46 The used XOR component Appendix B page 78 The OR Component library IEEE use IEEE std l
8. idee 1 1e onmp9uss ege my Am oM emele ONE rec uc uomo eger dew 2 emele lt 07 timer lt timer 1 CompInReg2 lt c CompInReg3 lt reg 0 going emelle lt Lr timer timer 1 ies 3 EE EE mul 1 emele lt gg timer lt timer 1 POmpilinieg om Si CompInReg7 reg 3 CompInReg8 lt reg 2 mys 1 cele lt Vs timer timer 1 result CompOutReg3 myo ll eneble lt p timer lt timer 1 timer lt 83 end of Schedule others gt timer timer 1 only count up end case Appendix B page 74 end if end process end arc Figure 44 complete VHDL code without register minimization Next the VHDL code with register optimization is stated library ieee use deee sC logue T sl entity VhdlCodeGenerated is pere mels shia eet lones erer Eat abs scel logie gua see logue SEC one ajay sec og e ec on ais stad locie Veetor downto in GTE legie Veetor downto in std logic vector 31 downto result s Gut Secl logie e cb on orco sie ODIT downto 31 31 downto 31 S end VhdlCodeGenerated architecture arc of VhdlCodeGenerated is component myXor is port es gad see legues oeren im eel lecuer eat ie da stel io gate El gua grel logie mees 6 downt om b sin std logic veetor 31 downto 0 result out std logic vector 31 downto end component myXor component myAnd is port eis gai seel lecues reste Ca abs Ste lene emalsltes da STel lo
9. S dowaise 0 result out std logic vector 31 downto 0 end component myXor component myAnd is port Us Baber Seel Oey regetane im scel lene emeles dm siecl o ge a in std logic vector 31 downto 0 bind Ste logde ee orn dowe U e result son Gto logre iwexeow Sil clown d z end component myAnd component myOr is port Gils mS t CIN o gate MESS CTS tM o ge elles dm sel og c a in std logic vector 31 downto 0 I gam Ste logado vectori coco MO e sin Stel logie ese Melon oa result sout Sec logie vector ol come OD end component myOr Appendix B page 72 Signal timer integer range 0 to 1000 signal myXor 1 enable std logie s 2 signal myAnd 1 enable std logic Z signal myAnd 2 enable std logie Z signal myOr 1 enable std logie s Vap ownto ownto ownto ownto signal CompInReg0 std logic vector signal CompInRegl1 std logic vector signal CompInReg2 std logic vector signal CompInReg3 std logic vector ownto ownto ownto ownto signal CompInReg5 std logic vector signal CompInReg6 std logic vector signal CompInReg7 std logic vector signal CompInReg8 std logic vector hers gt Z hers gt Z 2 3 3 3 signal CompInReg4 std logic vector 3 ownto 3 3 3 3 GEK IE Na Ee HE AE EE 7 hers gt Z signal CompOutReg0 std logic vector 31 downto 0 hers gt Z signal CompOutRegl std logic vector 31 downto 0 hers har sign
10. The Lifetime of a variable is defined as the interval from its birth to its death where the former is the time at which the value is generated as an output of an operation and the latter is the latest time at which the variable is referenced as an input to another operation 2 So first step would be to find the BirthTime and DeathTime of every task result As it has been already turned out during the parsing of the Tasks it is always quite useful to extract the desired information and store it into an object ArrayList for further processing We will proceed here in the same way For these purposes a class TaskOuputLifetime is created that contains the following attributes which have to be set for every task TaskName BirthTime DeathTime RegisterName and RegisterBitWidth So the ArrayList is filled with TaskOutputLifetime objects corresponding to every task The BirthTime attribute is identically with the Stoptime attribute inside the task object and can be taken over directly Note that the Stoptime is stated inside the scheduling file and has been parsed in the parser stage before The DeadTime is found out with a bit more effort If an output variable is used as input for more than one component we need to find the component with the latest StartTime i e we are looking for the maximum of all possible proceeding DeathTimes So we first check which are the successor tasks of our current task Then the StartTime of each is collected into an
11. end process end RTL Figure 48 The used AND component The testbench is the same for both versions Appendix B page 80 library ieee use ieee std logic 1164 all entity VhdiCodeGenerated Testbench is end VhdlCodeGenerated Testbench architecture tb arc of VhdlCodeGenerated Testbench is component VhdlCodeGenerated is port mclk in std logic resetn in std logic in std logic vector 31 downto 0 in std logic vector 31 downto 0 in std logic vector 31 downto 0 in std logic vector 31 downto 0 in std logic vector 31 downto 0 result out std logic vector 31 downto 0 end component VhdlCodeGenerated signal tb_clk std logic 0 signal tb resetn std logic signal tb a std logic vector 31 downto 0 others gt Z signal tb b std logic vector 31 downto 0 others gt Z signal tb e std logic vector 31 downto 0 others gt Z signal tb d std logic vector 31 downto 0 others gt Z signal tb c std logic vector 31 downto 0 others gt Z signal tb result std logic vector 31 downto 0 others gt Z begin tb VhdlCodeGenerated port map mclk gt tb clk resetn gt tb resetn a gt tb a b gt tb b e gt tb e d gt tb d c gt tb result gt tb result tb clk lt not tb clk after 20 ns clock working at SOMhz tb resetn lt 1 after 0 ns 0 after 5 ns after 10 ns tb a lt 10011111000100001001 1
12. The VHDLGenerator GUI The VHDLGenerator GUI is composed of the two classes GUIPanel and GUIFrame GuiFrame contains the main method from which the program is started The entry method is the constructor of GUIPanel Inside the GUIPanel the used components and labels are declared We need to choose a layout manager to determine the position and size of every component Java Swing offers several layout managers We choose the GridBagLayout which is a bit more complex but also more powerful layout manager With GridBagLayout it is possible to place components at any desired horizontal or vertical position The panel is organized in rows and columns that form cells of arbitrary size Each component is placed inside a cell Figure 32 23 shows an example how the cell organisation could look like GridBagl ayoutDemo Long Named Button 4 Figure 32 GridBagLayout example screenshot GridBagLayout works basically with two objects of type GridBagLayout and GridBagConstraints that implement the model inside the MVC architecture The GridBagLayout is the layout manager that organizes the components on the panel based on predefined constraints The constraints are set with the GridBagConstraints object GridBagConstraints objects got several attributes that could be set to define the exact position and size of every component individually We are making most use out of the attributes gridx and gridy These two are used to define a number of
13. VHDL code with register minimization sess 76 The used XOR componenti EH 77 The used OR component is ect eter gura sitet qua ev o cbe eo 78 The used AND component eege REESEN a We LEVIS ies 79 The generated VHDL tesibenchecioasi gente ee eddie bodas nse 81 Introduction page 1 1 Introduction Common hardware design flows that are in use today can not satisfy the correctness requirements of cryptographic applications where an implementation error might violate the security For this reason the Faculty of Integrated Circuits and Systems at the Technical University of Darmstadt started to develop a new design flow appropriate for cryptographic applications In contents of this work a VHDLGenerator is designed which is part of that new developed hardware design flow The objective of this VHDLGenerator is to convert a Data Flow Graph description into synthesizable VHDL code A central aspect of the design flow is the desired support for automated verification after code entry Although it is aimed towards cryptography most aspects can be adopted to other domains We will discuss first how the new design flow looks like and then we explain how this work is related to it Finally the overall structure is explained The proposed design flow is shown in Figure 1 1 The different design phases are represented in the left column The middle column denotes the actions required in the corresponding design phase while the right c
14. array After having done this we go The Data Flow Graph Compiler page 28 through this array compare all elements with each other pick up the highest value and assign this value to the DeathTimes attribute of the current TaskOutputLifetime object The procedure is then repeated for every task until all lifetimes of the task outputs are found With this data now the optimum number of needed output register can be calculated using a minimization algorithm There are basically two different methods to proceed Finding the minimum number of registers either using Clique Partitioning or using Graph Coloring Clique Partitioning is described in 2 and has been first implemented by Tseng 15 We observe that solving the register optimization with clique partitioning is NP Complete It does not guarantee an optimal result The second alternative is the Graph Colouring approach This algorithm promises optimal results with complexity O n 2 An appropriate representative of Graph Colouring algorithms is the Left Edge Algorithm We will first explain the theoretical background of the left edge algorithm talk about its development and then show how it is realized inside VHDL Converter Accordingly to 2 the underlying theory of the Left Edge Algorithm is the Graph Colouring optimization problem The Graph Colouring searches a vertex colouring with a minimum number of colours In the algorithm below the different colours are represented by integ
15. program is basically the same that is also used to describe the behaviour of a compiler for high level languages In fact if we define a compiler accordingly to 5 as a program that translates programs written in a high level programming language into native machine language of a digital computer the VHDL Converter can be considered as a complier In fact the program shows similar characteristics as a compiler and we will orientate on the principles of compiler construction 3 1 Compiler in general In the next section the basic components of a common compiler are stated Figure 6 Object program Code Code H generator El Optimizer shows the model of a common compiler Source program Lexical Syntactic Semantic Analyzer ed Analyzer m Analyzer Figure 6 Model of a classical compiler The compilation process is composed out of two parts The analysis of the source program and the synthesis of its corresponding object program During the analysis part the source program is fragmented into its basic parts and processed via a lexical syntactic and semantic analyser The pattern to distinguish between between keywords and relevant information are taken out of tables The Lexical Analyzer needs tables to look up the Keyliterals while the Syntactic Analyzer looks up the Keywords The Data Flow Graph Compiler page 13 The extracted raw material is forwarded then to the synthesis which builds the equivalent objec
16. system automatically An object is created and a message is added AII we have to do is write an appropriate handler that catches the exception add an individual text and finally print out the whole message Level two faults are safety critical and also more difficult to detect Let us see why and how they could appear VHDLGenerator does not take care whether the produced VHDL code is compilable or not It just converts given input files into text file which contents could be interpreted as VHDL code No guarantee of syntactical or semantic correctness is given Some of these errors inside the VHDL code are detected by the VHDL Compiler and can therefore be corrected afterwards But we could also imagine a scenario where errors are not even recognized during the synthesis So in order to reduce possible error sources VHDLGenerator should adapt to at least two faulty level two user inputs Every tasks runs on a component that got a specified number of input ports So a task needs as many inputs branches as the corresponding component got input ports We should beware of assigning more ports because then one will be unused Assigning fewer ports will lead to floating ports which causes undetermined system behaviour Once it is checked whether the number of input ports fit we further have to verify the bit length of each port In the Components File the bit length of every component port is stated in brackets next to the identifier The Input por
17. the cell in x and y direction where you want to place the current component With the insets variable the border space to adjacent components could be set Once all desired constraints are set the GridBagConstraints objects and our component are handed over to the GridBagLayout manager via the method setConstraints component GridBagConstraints Then the constraints of the next The Graphical User Interface page 51 components are set That way we draw the GUI step by step with all the components we would like to include When designing the GUI one has to take care that the different fields and buttons are arranged in a logic and concise way More on this topic inside the user manual in the last section of this chapter The execution of the model does not do much but draw the specified button field and switches on the panel When pressing a button nothing happens because we have not implemented yet the Controller i e accordingly to the Swing model the Delegate The Delegate is formed out of methods called listeners For every component a listener is created that reacts on actions that are performed by the user If for example a button is pressed the corresponding method is initiated and a specified action takes place The Graphical User Interface page 52 4 4 GUI Reference Manual In the following a short reference manual is given how to work with VHDLGenerator Although the meaning of the different options or fields are pre
18. the end all partitions are concatenated Figure 16 9 gives pseudo code for the Quicksort algorithm Quia elksiosete 2 l 18 dL mug exe 2 then split PARTITION X 1 r 3 Cuek Sorne iO 1Lz eyed stie 4 ns ce eeneg SEE Ia PARTITION X l r i joiwoe X L 2 a i 3 j esL 4 while TRUE E do repeat j j 1 6 until X j lt pivot 7 repeat icitl 8 until X i gt pivot 9 sus Ae 10 then exchange X i e X j 11 else return j Figure 16 Quicksort pseudo code The Data Flow Graph Compiler page 27 3 3 2 Register Optimization The implemented VHDL Converter has to deal with resource constraints On one hand the number of available instances of one component type is limited This implicates a scheduling of the tasks which is done by the HCDM tool and will not be discussed further On the other hand we want to use a minimum amount of registers A result coming out of one of the components has to be stored in a register until it is further processed A register in VHDLGenerator is considered to be a signal of type std logic vector with the same bit length as the result vector Depending on the task hierarchy not every result needs a private register A register could be reused once the previous value has been passed to the input of the next component So we would like to find an algorithm for yielding an optimum number of registers A result of a component can be considered as a variable with a certain lifetime
19. the scheduling information and generate synthesizable VHDL source code Introduction page 3 When starting to design the VHDLGenerator program one has to partition the incidental converting work It turned out to be of great advantage to introduce three different working stages The structure of this thesis mirrors directly the internal stages of the VHDLGenerator program Composed out of three processing stages the input is parsed then pre processed and finally converted to VHDL code All three stages are written in Java 24 The first stage parses the necessary files in order to extract all relevant information The Parser stage is described in chapter 3 3 The second stage is the PreConverter stage described in chapter 3 4 This stage contains the heavy weighted methods that do most of the work Register minimization Exception handling and the setting of the case statements are only some tasks that are handled by the PreConverter stage The third and final stage converts the pre processed data to VHDL code Because of the extensive work of the PreConverter the methods of this stage are more light weighted The VHDL generator stage is subject of chapter 3 4 VHDLGenerator offers a fourth optional stage Depending on the users settings a testbench for the converted VHDL code can be created How the testbench is constructed is explained in chapter 3 4 2 The VHDLGenerator usage is greatly simplified by creating a Graphical User Inte
20. to the right outputs at the specified point of time So we can adhere that the VHDL code for scheduling and register allocation is generated correctly page 61 Conclusions yrsa suf avega pajeleuetepoapuh Code parauabapoopu E ysay Tofuyquyouaqysay payereuebepoapya 7 ar ofluyqyyouaqisay payerauabepoopyay g q jofujqyuouaquse pajereusBepoopu er romuyqyyouaqieal papeiausbepoopu p ETE EEN Usa lof yquupueqgea payeieuaBapoopyay HOI puefu yuguaqser UE ynsay puefiuycqyyoueqisey paereuabapoopuw OC puefuyquupuaqse pajereuebepoopu y j puefuquouequsa patsisuatepoopl Bel qqpueqer pejersusbepogpu Z Bay qy youagysay paersuaapoapun Bei quuoueqisei perejeueGapoopun Balyqyyouaqisay pareisuebepoopua EGannoduco quupuegisal pareleueDapoopun Bannodwooyqy yaueqieay pareteuebepoopun 1Bennoduooyqyupuequse pajeieueBepooppup KE gbeniduoo quuoueqisar payelausbapoopyiy _ Bewudwoayqyyouaqisay payelauabiapoapya EET EN gbaiuduoo quApuaqusa pajeleuebeposypy fetuduooyqyuaueqise pajersuebapooput Ganyduooyqyuouamsej pajersusbepooput Banadwoayqyyouaqysay pajersuatiepoaput IGanduoo quupuagisal pajersueGepooput beruduooyqyupusqiser pajeleusbapoopu ague rof yqyuouaqgse payeiauabapoopya seus 7 puedwyqyyouaqsay payerauabapogpya y eus puefu qupuegsel payereuaBepoapyr l I Se ionfuyqyyouaqisey pajereueBepoopul Lg cp zr EL WI SY ay N sts sp EN zr ur wr sg sg a
21. 10110110000 after 0 ns 00100010010100110001010010111100 after 1000 ns 1100110011100100000000100001 1110 after 2000 ns 11110111100011101100010110111010 after 3000 ns 11010110010001111110100110110110 after 4000 ns tb b lt 01001110111110000010110010111110 after O ns 10101111110101101010101000010100 after 1000 ns tb_d lt 100010001011 01011100011111111110100101110100 after 2000 ns 0010000001 1101100000001111111100 after 3000 ns 1101111100011 0010000001 101101010000001 1000110 after 4000 ns 001010001011 tb e lt 0010100100000001 1110001011010100 after 0 ns 1110010101011 11110011011000010010101101110010 after 1000 ns 0001100110011 00010111100111110001111101010010 after 2000 ns 01000010011000110011100111011000 after 3000 ns 10101001011010110011100101110110 after 4000 ns tb_c lt 01011011111 0111110011101 0000010101111 001010000101 010110000101 end tb_arc References page 81 Figure 49 The generated VHDL testbench References 1 Klaus S 2006 System Level Entwurfsmethodik eingebetteter Systeme Aachen Shaker Verlag pp 101 106 pp 129 131 2 DeMichelli G 1994 Synthesis and Optimization of Digital Circuits New York McGraw Hill Inc pp 37 42 pp 100 102 pp 119 123 p 240 pp 61 64 pp 64 67 References page 82 3 4 5 7 Rozenberg G and Salomaa A 1997 Handbook of Formal Languages Vol 1 Word Language Grammar B
22. AMES Names of each behaviours that are implemented by this class e Task NAME The name PRIORITY priority for list scheduling Appendix A page 70 TIMING default time behaviour as long as no component binding exist RESOURCES a list of resources on which the task can be implemented LEVEL parameter for the graphical representation OPTIMIZATIONTYPE Kommunikations oder funktionaler Task IMPORTANCE importance of this task for error free function of the system FAILURE PROBABILITY breakdown probability of this task Appendix B page 71 Appendix B The generated VHDL code for the register minimized version and the non minimized version are stated below The testbench as well as the used VHDL components are the same for both First the generated VHDL code without register optimization then the code with register optimization are stated library ieee use deee std logic 1164 all entity VhdlCodeGenerated is port mclk in std logic TESE Er ala ste leguer 3 im siel ocn cM OCIO in std logic vector in std logic vector downto in std logic vector downto SS Aa Eet togte vector TM Cows tecie s out stal logie vectori dowe OP end VhdlCodeGenerated downto downto 31 31 eal 31 architecture arc of VhdlCodeGenerated is component myXor is port es gad ete lemper resetni im st Logier Guislollies dm diese a in std logic vector 31 downto 0 birds ediiogiclveetons
23. Flow Graph Compiler page 33 ALGORITHM VHDL GENERATOR LEA BEGIN i SORT tasks in ascending order to their start times 2 EXTRACT all Lifetimes and store them E LOOP 4 Take first element out of lifetimes 6 LOOP Compare to all other lifetimes 9 IF Deathtime of first Lifetime Birthtime of next Lifetime 8 ASSIGN both tasks to same register 9 END IF 10 REMOVE first lifetime out of list JEL END LOOP 12 END LOOP Figure 22 Left Edge pseudo code for VHDLGenerator Note that PreConverter also offers another method with name allocateOutputRegister This method allocates non minimized registers to the tasks i e every task gets a separate output register This method could be used instead of the doLeftEdgeAlgorithm method when we do not have to deal with resource constraints The user of VHDLGenerator has can choose between these two modes in the graphical user interface 3 3 3 Error detection and recovery techniques Although various tests have shown that VHDLGenerator program itself accomplishes its job in a correct way you are never aware of faults that are introduced from the user s side What is desirable is software that reacts robust to the users input Software is robust if it describes reasonable behaviour even when it is misused or used in error 12 Of course reasonable is an expandable item We will define it here for the VHDLGenerator in a way that we say the program should catch inputs t
24. M EE 15 3 2 2 1 Java streaming concepts in general 15 3 2 2 2 Parsing inside VHDL Converter 16 3 2 2 3 Parsing the HCDM files oae rade Goes 18 3 2 2 4 Parsing the Scheduling File s 22 3 2 2 5 Parsing the Components File sss 22 3 9 The PreGOmverler SUE aus esos te at dete e sates ale ROME CR NE US 23 32 1 Sorting of the Tasks gi ERBEN e ROI ENTER 23 3 3 2 Regisier Opi Ee EE 27 3 3 3 Error detection and recovery techniques usus 33 3 3 3 1 Java Exception handling in general 35 3 3 3 2 Exception handling inside VHDLGenerator 37 AA The Converter EE 42 3 4 1 The VHDL Code Generator 42 Contents VII 3 4 2 The VHDL Testbench Generator rires 44 3 4 2 1 Testbenches in general s eoo erre e veces oss 44 3 4 2 2 Testbench creating for VHDL Converter 44 4 The Graphical User IBterfage ses ated ein edere desi shapes secs is eod 47 41 Java Swing vs 23 WT Ls side t cai o qued esol dae eue bes sedere e base 47 4 2 The Model View Controller Architecture in Java 48 4 3 Ihe VHDE Generator Ee eelere 50 4 4 GUI Eu EE 52 MEC Veit MER CN 56 2L The Test POSE OE EG ls 56 5 3 Simulation Results Lope reete det der 60 Ded Synthesis ReSulfs le onere Ae 65 ee da OE Noses 68 Appendix EE 71
25. ORELATION OUTPUT 166 1 NPUT To53 ID CONDITION true OUTPUTS 5l CONDITION true SUBTASKS SUBTASKS Figure 35 HCDM description Conclusions page 60 HCDM schedules the different tasks on the components as follows twee 2 wi32 EI 9 9 C132 Q0 5 O Do X32 0 NIE EIN Oy p tes 20 penea 20 40 Vs Para 20 40 Bel 40 4 GO Bottom 60 70 rasul szl VO 10 Yy BINDING 4 Queue mel 2 eli 32 i Lmyoune 1 oll 32 Taput 2 Boccom uyode L ieop wuyexo 35 alS2 Tnput 3 else 4 Part myAnmd 1 Pars myAnd 1 els Lem 5 esult 32 OwtpuE 1 H Figure 36 HCDM Boolean example scheduling The data is extracted and parsed like explained before Depending whether we have chosen register minimization or non register minimization the received VHDL code looks different The complete generated VHDL Code as well as the corresponding testbench are added to the appendix B 5 2 Simulation Results Let us first verify the correct circuit behaviour of the basic version where we do not make use of the register minimization algorithm We simulate the VHDL code together with the needed components by means of the generated testbench Waveforms demonstrate the correct behaviour The encircled parts of the waveforms in figure 37 to 39 indicate the results of the single components At this point in time we only acknowledge that the results are shifted
26. Path field This field specifies the directory and name of the VHDL code file produced by VHDLGenerator Errors that are related with this field contain error code 1 4 Default Button The Default Button sets back the file path fields to its initial value After pressing Enter the path is taken There exist four Default Buttons one for every text field Register Minimization Algorithm With this radio button one can select either Left edge algorithm or none minimization algorithm Left edge algorithm allocates a minimum number of result registers accordingly to chapter 3 3 2 When choosing none minimization algorithm every component result receives a separate register The register minimization is The Graphical User Interface page 54 done inside the PreConverter stage so possible errors that are related to this button contain error code 1 5 The Create VHDL Testbench checkbox When having marked this field a testbench for the current VHDL model is created The test bench is placed into the same directory as the generated VHDL code For every input port five different random vectors are created The Open VHDL Source File checkbox When having marked this field the produced text file specified at VHDLFilePathfield is opened using the notepad exe of Windows or some other specified program The File is opened after having pressed the Generate VHDL Button and no error occurred If the previous Create Testbench checkbox is
27. Sebastopol O Reilly amp Associates USA Sun Microsystems Inc How to use GridBagLayout online Available at https cis med ucalgary ca http Java sun com docs books tutorial uiswing layout gridbag html Accessed 27 Oktober 2006 SHOUFAN A Rekonfigurierbare Prozessoren online Available at http www vlsi informatik tu darmstadt de student_area rp rekpro 5_6 uebung loesungen 1 pdf Accessed 15 November 2006 Sun Microsystems Inc JAVA API Available at http java sun com j2se 1 3 docs api Accessed 20 November 2006
28. TION true CONDITION true SUBTASKS SUBTASKS Conclusions page 59 TASK 35 TASK 26 NAME Par3 NAME ell 3 OPTIMIZATIONTYPE 1 OPTIMIZATIONTYPE 1 IMPORTANCE 1 IMPORTANCE lees FAILURE PROBABILITY leen FAILURE PROBABILITY Os DOT JL eS Og BEVELE 3 PRIORITY 4 PRIORITY 4 TIMING 0 TIMING 0 RESOURCES po DUE D DE RESOURCES rr moa IORELATIONS IORELATIONS ORELATION ORELATION INPUT 60 81 INPUT GS OUTPUT 445 vr OUTPUT 75 4 CONDITION true CONDITION true SUBTASKS SUBTASKS TASK 38 MASI 2 d NAME eq i NAME e 32 OPTIMIZATIONTYPE 1 OPTIMIZATIONTYPE 1 IMPORTANCE ec IMPORTANCE 1 FAILURE PROBABILITY Oss FAILURE PROBABILITY LOS eh GEVEL db 3 DEVBSL d 3 og PRIORITY 4 PRIORI d A TIMING 0 TIMING O RESOURCES C650 RESOURCES i900 IORELATIONS IORELATIONS ORELATION IORELATION INPUT 96 INPUT 90 ONTEER 72 OUTPUT 81 CONDITION true CONDITION true SUBTASKS SUBTASKS TASK 44 TASK 32 NAME result 32 NAME Parl OPTIMIZATIONTYPE 1 OPTIMIZATIONTYPE 1 IMPORTANCE 1 IMPORTANCE 1 FAILURE PROBABILITY Oso FAILURE PROBABILITY dreet LEVEL dp Ss ft LEVEL 3 PRIORITY ER PRIORITY sd TIMING 0 TIMING 0 RESOURCES bes ra UG M RESOURCES 220 X m5 20 5 IORELATIONS ORELATION ORELATIONS NPUT 57 I
29. Task in order to store all tokens Tokens are stored inside attributes of this class The Parser pattern can be described best in terms of a Backus Naur Form BNF The BNF in figure 11 is referenced to the HCDM grammar stated in the appendix and only describes the fields that are extracted by the parser name e NAME lt taskname gt lt port gt lt taskname gt 9 lt string gt port 8 lt portname gt lt leftdelimiter gt integer lt rightdelimiter gt lt portname gt Sl stica gt iorelation gt GINEUT V lt aehligics UU euro fo es HIH idlist E al eee H xls integer lt digit gt lt integer gt lt digit gt lt string gt lt letter gt lt string gt lt letter gt lt letter gt vas ier ae ed ai Asta GEE N ES IW AE digit VIE al Nd ES BE ae ES ee IE o LE CALLE ree LUE EE Gas lt leftdelimiter gt en Obs lt rightdelimiter gt s M Figure 11 BNF description of Parser pattern The Data Flow Graph Compiler page 21 Two important not yet mentioned design rules have to be taken into account when drawing DFG s with HCDM 1 When we model a component with a task symbol in HCDM we have to take care that we are drawing the corresponding inputs of the task in exactly the same order as they are stated inside the component entity If we do so HCDM will assign ascending branch numbers to the task and VHDLGenerator can parse the associations corre
30. UNIVERSITAT POLIT CNICA DE CATALUNYA Development of a VHDL Generator for Scheduled Data Flow Graphs MASTER THESIS submitted by HAGEN STUBING 2 telecom Escola T cnica Superior d Enginyeria E BCN de Telecomunicaci de Barcelona UNIVERSITAT POLIT CNICA DE CATALUNYA IV Honour declaration Hereby I assure that the presented thesis was made without any help of third persons and only with the indicated sources and means AII the figures and paragraphs taken from the sources are clearly marked Darmstadt 21 11 2006 Preface The presented work is created in contents of a master thesis that I have prepared for the Universitat Politecnica de Catalunya in Spain At the Technical University of Darmstadt this thesis is submitted as a Studienarbeit The thesis consists of three parts The enclosed CD Rom contains the VHDLGenerator program with the corresponding installation files as well as the source code The documentation of the VHDLGenerator Program is the paper at hand For quick reference a user manual is available The user manual is a copy of the most important notes helpful when starting to work with VHDLGenerator The structure of this thesis is closely related to the execution order of the program The development of the VHDLGenerator program required knowledge of different fields of programming For streaming the text files you have to know the Java streaming concepts while the VHDLGenerator error
31. ained Java streaming concepts and the Parser state machine to extract the relevant information out of the HCDM File The HCDM file contains a lot of not needed or redundant information Figure 10 demonstrates how Tasks are stated inside the HCDM grammar The Data Flow Graph Compiler page 19 TASK 14 NAME Par2 TASK DECLARATION OPTIMIZATIONTYPE 1 IMPORTANCE 1 FAILURE_PROBABILITY 0 5 LEVEL 3 PRIORITY 4 TIMING 0 RESOURCES 220 5 20 IORELATIONS IORELATION INPUT 84181 HIERACHICAL RELATION OUTPUT 78 TO OTHER TASKS CONDITION true SUBTASKS TASK 17 NAME b 32 EXTERNAL INPUT DECLARATION OPTIMIZATIONTYPE 1 IMPORTANCE 1 FAILURE_PROBABILITY 0 5 LEVEL 3 PRIORITY 4 TIMING 0 RESOURCES 4 0 IORELATIONS IORELATION INPUT 48 OUTPUT 87 OUTGOING BRANCH CONDITION true Figure 10 Task declaration inside HCDM The Data Flow Graph Compiler page 20 In fact the only information we want to get is the name and bit width of external inputs the task names and the hierarchical relation between them So out of the HCDM grammar we choose the keywords NAME INPUT and OUTPUT When the state machine is in the WordIDcheck state the Token is constructed when the WordID is set So during the transition from this state back to the initial state the token has to be stored somewhere We decided to build a class with name
32. ains a PRIORITY field where the parameter for list schedul ing has to be entered Safety critical task can be marked inside the IMPORTANCE field Furthermore the failure probability of a task can be taken into account inside the FAILURE PROBABILITY field In the last section the relation between the tasks are de fined Tasks are connected over branch numbers inside IORELATION These are all fields that are important for the original purpose of HCDM which is to perform scheduling and binding for embedded systems When using HCDM for generating VHDL code most of these parameters will be ignored In fact we only consider here the ones that are relevant for our VHDL conversion More to this in the chapter on parsing The Scheduling File produced by HCDM is quite self explanatory and does not really need a specified grammar The first line defines the start time and stop time of every task In the second line the binding of every task with its resource is stated The Data Flow Graph Presentation page 11 2 7 HCDM and Data Flow Graphs As mentioned before HCDM has been created to design Task Graphs That means that the tool does not provide any methods to represent external operators needed for the Data Flow Graph Without changing the HCDM program itself it is still possible to adapt its functionality to create DFGs which will be described next For creating the Task Graph HCDM provides two graphical elements Circles that represent the Tasks a
33. ains an optimal solution and is of complexity O n 14 Kurdahi and Parker 14 grabbed this idea and used the same principle for register minimization There the wires correspond to the previous discussed lifetime of variables and the routing tracks are the to be minimized registers The left and right edges of the wires are considered to represent the birth and death time of a variable formally known as lifetime Accordingly to 14 all different lifetimes have to be collected inside a table We have already discussed the procedure at the beginning of the chapter Having done this the goal of the Left Edge Algorithm is to assign output variables wires to registers tracks so as to minimize the total number of registers tracks to store the output value Two wires cannot share a track if they overlap in space whereas two variables cannot share a register if they overlap with their lifetimes The presented algorithm is used inside the program REAL Program for REgister ALlocation which has been developed by Kurdahi and Parker Very similar to The Data Flow Graph Compiler page 32 VHDLGenerator REAL gets as input a data flow graph whose operations have been scheduled along with a lifetime table of the values in the DFG REAL also has to deal with resource constraints like number and type of operators used to implement the operations Scheduling can be overlapping In the paper of Kurdahi and Parker also register allocation for conditional br
34. al CompOutReg2 std logic vector 31 downto 0 hers EC signal CompOutReg3 std logic vector 31 downto 0 hers atq others others others others semen reg 0s stoi logic eco sil cowarto 0 enome mec ils Stel logue eeneg do mie AE Sagal reci 22 SEC locie ves ors SL cernco O s sulgimell reg 33 eet logie vectori comto 0 s begin myXor 1 myXor port meng Elle gt molk ses Ecce gt miroir il endolori gt CompInReg0 b gt CompInRegl result gt CompOutReg0 myAnd_1 myAnd Owe mead Elle gt melk escena ccce gt mano l aa keen gt CompInReg2 b gt CompInReg3 result gt CompOutRegl myAnd 2 myAnd porc meng ells gt mele resetn gt recetna sie gt myandod 2 quelole a gt CompInReg4 b gt CompInReg5 result gt CompOutReg2 myOr 1 myOr some map Ells melk se eed gt AE Salle mM MEDI CompInReg6 b gt CompInReg7 c gt CompInReg8 result gt CompOutReg3 Appendix B page 73 process mclk resetn begin if resetn 0 then timer lt 0 result lt others gt 0 elsif mclk event and mclk 1 then case timer is when 0 gt ComplInReg0 lt a CompInRegl lt b groe dL enable lt Vitg timer timer 1 reg 0 lt CompOutReg0 mor il quaole lt VOE timer lt timer 1 CompInReg2 lt e CompInReg3 lt reg 0 ize Il emelle lt Lr CompInReg4 lt d CompInReg5 lt reg 0 mardi 2 compo lt le timer timer 1
35. anches is discussed Conditional branches are not supported by HCDM so far and will not be discussed in contents of this work As REAL is optimal for non pipelined designs with no conditional branches we also expect VHDLGenerator to give optimal results when using the same algorithm As implemented inside VHDLGenerator the Left Edge Algorithm works in a quite simple but efficient way The encoding in Java is realised based on the pseudo code shown in figure 22 Lifetimes are extracted as explained before Note that the first step of the Left Edge algorithm the ordering of the lifetimes is done inherently when the tasks are sorted by their lifetimes as shown in part 3 1 1 The next step would be to pick up the first lifetime allocate it to a register colour and check for overlapping with other lifetimes If we consider the tasks to be sorted in ascending order to their Start Times a criterion for non overlapping lifetimes can be formulated quite easy Two Lifetimes do not overlap when the death time of the first is smaller or equal the start time of the next lifetime Outputs with non overlapping lifetimes are packed into one register Then the first element is deleted and the algorithm starts again The whole procedure is repeated until all lifetimes are processed As a final step the found lifetime register pairs are transferred to the tasks in a way that inside the task object the corresponding OutputRegister attribute is set The Data
36. applications the Flip Flops will be a more sever resource constraint Appendix A page 68 Appendix A HCDM describes the task graph in terms of bnf grammar Backus Naur form that allows a flexible number of parameters Note that here the complete HCDM grammar is stated although we will only take care of some of the fields The modified grammar used for the parser is stated in chapter 3 2 2 3 MC lt hedm gt lt resourcelist gt lt resources gt lt resource gt behaviorlzst gt lt behaviors gt lt behavor gt lt tasklist gt lt tasks gt lt task gt iorelations gt l HCDM lt id gt lt params N lt resourcelist gt lt behaviorlist gt lt tasklist gt lt edgelist gt RESOURCES IT lt resorces gt H 0 lt resource gt lt resources gt RESOURCE lt id gt N lt params N BEHAVIORS lt behaviors 7 N lt behavior gt lt behaviors gt BEHAVIOR lt id gt P NAME lt string gt N SIZE lt integer gt H lt params N TASKS tasks gt N 0 lt task gt lt tasks gt TASK lt id N lt params gt IORELATIONS lt iorelations N SUBTASES lt tasks gt N 0 lt iorelation gt lt dorelations gt Appendix A page 69 lt iorelation gt IORELATION INPUT lt idlist gt H OUTPUT l
37. arsed text The tokens are stored for further processing If we pick up the idea of seeing the VHDLGenerator as a Complier there has to be a third stage following the semantic analysis During this step the actual meaning of The Data Flow Graph Compiler page 15 the collected tokens is determined and an intermediate form of source code is generated The semantic analysis is done inside the PreConverter class and will be explained in the following sections 322 The HCDM Parser The implemented HCDM Parser is orientated on the previously introduced parser theory We only make some slight changes in the nomenclature for the parser program code Instead of naming the assembled literals as Lexemes they are named as Words For the documentation we will use both synonyms Furthermore it is not possible to run the two processes for Syntax Analysis and Lexical Analysis in parallel as it is recommended That is basically due to the fact that Java is interpreted sequentially So we need to serialize the two processes How the serialization is realized can be seen from the state chart below To convert the Data Flow Graph into synthesizable VHDL code the necessary information from three text files has to be parsed Before we come to discuss the parser itself basic concepts of streaming text files in Java need to be explained 3221 Java streaming concepts in general In order to parse the available data has to be serialized previously This mea
38. checkPorts Highly saftey critical Difficult to detect HdcdmParser java Less saftey critical Easy to detect LEVEL 1 2 a o El EX 3 Wal o 3 D 2 o lt 5 9 x Figure 23 Error Level classification On the third level we want to handle faults that result neither into an error nor into a failure These faults are made at the behavioural description of the input In our case this means that the entered algorithm graph does not follow its specification Like in a compiler these kinds of faults cannot be detected because they take into account the given specification on which the entered algorithm is based VHDLGenerator has no knowledge about that The only chance to get rid of these The Data Flow Graph Compiler page 35 faults is to demonstrate the programmer how his implemented algorithm works The programmer himself has to compare the result with the desired specification and perform possible changes In this chapter we will only discuss the faults of level one and two because these are the kind of faults that are treated by the HCDMParser and PreConverter stage Third level faults are subject of chapter 3 4 3 3 3 Java Exception handling in general Java offers comfortable constructs to catch and handle errors in form of exceptions in programs In general an exception in Java is an event which occurs during the execution of a program and disrupts the normal flow of the program s instructio
39. chitecture Swing uses a modified Model View Controller Architecture MVC We will first explain the MVC and then show how these concepts are modified for Swing As it can be seen from Figure 30 the architecture is composed of the interaction of three instances The Graphical User Interface page 49 Model View Controller The Model describes the properties of the component Properties are for example the colour size or labelling The View is responsible for z Model representing the component graphical depending on the adjustments made before Because the view is View Controller separated one can easily interchange the Look amp Feel Figure 30 classical MVC architecture The Controller is responsible for the interaction with the user It receives an input like a mouse click or a menu select and processes it Processing means here that a proper action inside software takes place The Controller also notifies the Model to update the View In Practice the classical division between View and Controller turned out to have a to high communication complexity Therefore the Swing architecture uses a modified architecture View and Controller are merged together to the Delegate Inside the Delegate the Controller is called Listener The Listener listens for events that take place on the component and perform the desired action Figure 31 Swing MVC architecture The Graphical User Interface page 50 4 3
40. ctly 2 Ifa task got more than one proceeding task HCDM will generate an output branch for each proceeding task In VHDL these outputs should only be related to one VHDL component output Note that VHDLGenerator is aware of that and discards the different branches in a way that it produces a single output that is routed to every following component That way the parser goes from task to task extracts the relevant information and puts everything into a variable of type ArrayList Once all tasks are extracted the external input and output ports need to be separated from the real tasks to generate the top level interface So an algorithm is started that identifies input and output ports allocates them to the respective task and deletes them out of the ArrayList To filter out the external ports we make use of the previously mentioned fact that external Inputs are designed tasks that are direct successors of the root task and external Outputs have outgoing branches back to the root task The bit length of every input or output port is parsed from the name by using the discussed Java StringReader concepts The Data Flow Graph Compiler page 22 3224 Parsing the Scheduling File The second file produced by HCDM is a scheduling file like it is shown in figure 12 The scheduling file is parsed in the same manner as the HCDM file true b 32 0 0 a 32 0 0 top 0 20 Par2 20 40 Par3 20 40 Bottom 60 70 result 32 70
41. d Task Graph Figure 2 3 shows an example of a Data Flow Graph 2 5 HCDM in general The HCDM tool implements a set of genetic algorithms to generate an optimal resource binding and scheduling for a set of allocated resources and a CoDesign Model CDM A CDM is an extended Task Graph Model The HCDM flow graph is basically described in terms of processes their resources and the relations between them Processes can be considered as tasks that run on a specified resource A resource could be a physical component on which the process The Data Flow Graph Presentation page 9 runs To every pair of process and resource and execution time is associated which describes for which period of time the process is running on the resource The different processes can be connected by branches Branches represent data dependencies i e a process followed by a second process connected by a branch indicates that the calculation of the second process is dependant on the results of the first process In that way a directed hierarchical graph for representing algorithms of any kind can be drawn The Task Graph is entered graphically via a graphical user interface From the graphical representation a text file is generated that represents the textual description of the graph Note that the drawn HCDM data flow graph does only specify the data dependencies of the implementation It does not contain a sequential ordering of the operations The order is genera
42. d dn pegpet parereueDapoopu insel quouaquser payeiauabepoopyy e CC SEES eee GE ayqyyaueqisay pojeuetepoopyyy Lopes pereisusbapoopu Siss parisusfopcopu upsds pasten EE EE EN Figure 37 Result of myXOR 1 page 62 Conclusions o C3IUCUL psum ETE EE N AC Dis pareauatepoopu Cous paresuefopoopui KEN wasan lowflu qywouequsaj parersuabapoopu por Liowfiquuouequser parereuafapoopui nsa of qywoueqisa pejersueDapoopu 9 august perereueDapooput oC august parereueDspoopuh By Iofu qyuouaqser payelouaBapooppyy KEE EE TE SEN rp L iof quuouequser perersuaBapoopui OC puefiuyqyuausqyse parereueBapooput e puefurqyupuequar pareisuDapoopu ageua puefiuqupuequse paersueGapoopun wesal puefiuyquuouaqgse payerauaBapoopyry 1 beduup edel pajersusbepoopun Balyqyyouaqisay epeasfeprobin 7 beijqyupuaqgsa payeleuabepoopyay TEE ELE Beyqyupusqer peyereuebapoopysy EN Ne Sannodwooyqy youaqisay pajersusbepoopu Bannodwoayqyyouaqsay payelauabiapoojpyA pbianudwoo qyyouaqisay payeiauabepoapyr J Banadwoo qy youeqisey paielauebepoopu gBanudwoa qyyoueqysa payeieuaBepoapyn gbaluidwoorqy youaqisay pajersusbepoopu y Baduoayqyyoueqsay paperaustapcopu Bauduoayqyyouaqysay pasten aanuduoo qyupuaqsej paersua apopy ege qypuaqsar pasten Baruduoa qyyoueqysay perereustepoopun agua C u ie pajersuatepoopuv ageus beduecht Fep ebe ales pufu qytuaq
43. de is given out The user can correct the error by means of the two error tables in chapter 3 3 3 The Exit VHDLGenerator Button The Exit Button closes the VHDL Generator program Conclusions page 56 5 Conclusions To demonstrate the correctness of the VHDLGenerator program we construct a basic test example The test program consists of a boolean equation and is constructed in a way that for the reader it is easy to read the results but still the full functionality of VHDLGenerator is demonstrated 5 1 The Test Program The realized Boolean equation contains four external inputs with 32 bit each The Inputs are processed and combined via three different components XOR AND and OR component All components are available as VHDL code and are registered inside the components entry file Allocated are 2 AND 1 XOR and 1 OR component The equation is entered into HCDM Converter as follows F a b c d e a b c a b d a b e The corresponding data flow graph as well as the HCDM description are shown in figure 34 and figure 35 For clarity reasons the HCDM description is reduced to its functional parts Notice again that all external inputs are drawn as successor tasks of the Root task which is an essential condition for the parser External outputs share the same output branch with the Root task Conclusions page 57 H Dtt Current Model vias Figure 34 HCDM Boolean DFG screenshot Conclusions page 58
44. detection is based on Java exception handling Because the output file is written in a hardware description language VHDL one has to deal with the constraints of hardware design Furthermore the theoretical background of minimization algorithms has to be understood in order to realize the Left Edge Algorithm that is used for register minimization So as heterogeneous as the knowledge base is as heterogeneous is the structure of this thesis The different topics are addressed in the order they are executed inside the VHDLGenerator program Every chapter is related to one working step of VHDLGenerator It always starts with a general explanation and theoretical background of a used concept and then explains how the theory is adapted to the specific case Hagen St bing Contents VI Contents Honour e EE IV ies E V pnr a m VI List of Figures eT VIII JniroducUol EE 1 2 The Data Flow Graph Presentatlon aie beet Baa dre ls 4 2 1 Data Representation Form a u eee e rete secet oe eek gese Seege 4 2 2 EN 5 2 3 gt Task EE 6 24 Data EE 8 2 9 HCDM in DEMET A emesos site sunt Ra ipe dea Dota des 8 2 0 HGEDM EIERE o ee enemics ente tent Gens 9 2 1 HCDM and Data Flow Graphs eene tecti nut 11 3 The Data Flow Graph Compiler eoe cd apatite alee 12 Sik Compilers DECat dts E Odes aU AE 12 2 25 Ihe Parser EE 14 JT Parser EE ade cubana sa ease ena eee uS 14 3 2 2 The HED
45. e simple If the path of the file is given to the constructor of FileReader the file is opened in the read modus automatically If the opening fails a FileNotFoundException is thrown So the method call always has to be placed inside a try catch block More on the topic error and exception handling in section 3 3 3 Within a loop the method read applied to the FileReader object returns the text sampled character by character The return value is of type int and typcasted to char This will be the smallest data unit the parser will work with According to parser theory this single char value is nominated as Literal Inside the Parser code it will not only be necessary to parse a whole text file but also to parse tokens out of a string For this issue we use an instance of the class StringReader A string can be streamed in the similar way as a file The Parser only absorbs information out of text files and therefore we only need instances of type Reader But later on it will be required to stream the converted VHDL code back into a text file The output streaming in Java is done simultaneously as for the input stream The used instance is of type FileWriter and implements the interface Writer Like previously the full path of the destination file is handed over by the constructor The method write appends a given string to the end of the text The call has to be done inside a try catch block 3 2 2 Parsing inside VHDL Converter To construc
46. ec ma Melo vt o ES reg 28 Ste logre vector Sil conco Oys myXor_1 myXor port map myAnd_1 myAnd port map myAnd 2 myAnd port map myOr 1 myOr port map clk gt gt Comp el gt clk gt gt Comp clk gt mel n MELK n MELK n mc Reg2 b gt Comp Reg4 b Comp resetn resetn n n n k resetn resetn enabl Reg0 b Comp resetn enabl Reg3 resul resetn enabl Reg5 resul Regl resul EE EO DEM CA na El El others gt others gt others gt myXor 1 enabl CompOutRegO myAnd 1 enabl CompOutRegl myAnd 2 enabl CompOutReg2 spes ncc CM gt mOr l enaolspe gt CompInReg6 b gt CompInReg7 c gt CompInReg8 result gt CompOutReg3 Appendix B page 76 process mclk resetn begin if resetn 0 then timer lt 0 result lt others gt 0 elsif mclk event and mclk 1 then case timer is when 0 gt ComplInReg0 lt b CompInRegl lt a myXor 1 enable lt timer lt timer 1 reg 0 lt CompOutReg0 mesos lt gt ur timer lt timer 1 CompInReg2 lt e CompInReg3 lt reg 0 ue Goede lt IUE CompInReg4 lt d CompInReg5 lt reg 0 mane 2 wolle lt UI timer timer 1 reg i eorpore cM une 1L enable lt 1007 reg 2 lt CompOutReg2 mandi 2 melle lt gr timer timer 1 CompInReg2 lt
47. ed Java Parser 3 2 1 Parser Theory In general parsing is defined as a process that analyzes a given sequence of literals and tries to extract the desired information according to a predefined grammar That is the so called syntax analysis Before the information could be analyzed the given sequence needs to be sampled literal by literal to extract the keywords The elementary operation of every syntax analysis is called lexical analysis The lexical analysis got as an input the literal sequence of the to be parsed data It identifies literals that belong together and passes them as Lexemes one layer up to the syntax analysis The syntax analysis then uses the given grammar to figure out the meaning of every Lexeme and the relation between adjacent Lexemes So a Parser can be thought of having two layers that work in parallel On the first layer a Lexemer scans the input sequence and produces valid Lexemes To distinguish between two successive Lexemes the Lexemer needs to know the predefined separation literals Separation literals can be set for example as white space or closing braces According to Maximal Munch Rule literals are assembled until such a separation literal appears On the second layer a Tokenizer absorbs the Lexemes and produces tokens according to the grammar Tokens are considered to be a pair of Lexemes First Lexeme indicates the token type and second the token value In most cases these two Lexemes are consecutive in the p
48. eption handling in Java soes Ge Moe vete reete ot oed es ede 36 Figure 25 throw Statement i ott esta Ke tes essa de aua De e ENT Va ge qu eub Ue va dS Ue ada eis 36 Fig re EE eene 37 Figure 27 Error RE 41 Fig re 28 VHDL Testbent is ie oso ee tco bere do dle iss ob a DE E 44 Figure 29 concatenating algorithm description 45 Figure 30 classical MVC architecture 5e te Se ee KG ee ee ve ad e eaae uude 49 Figure 31 Swing MVC architecture eegend eege ders ede litige ER 49 Figure 32 GridBagLayout example screenshot 50 IX Figure 33 Figure 34 Figure 35 Figure 36 Figure 37 Figure 38 Figure 39 Figure 40 Figure 41 Figure 42 Figure 43 Figure 44 Figure 45 Figure 46 Figure 47 Figure 48 Figure 49 VHDLGenerator GUI screenshot 52 HCDM Boolean DFG screenshot 57 HCDM deseription EE ee 59 HCDM Boolean example scheduling esee 60 Result of IRVXOR usse di dise eU bd siii e otek beds 61 Result of myAND 1 and myAND 2 ee ees se ee ee ee nnne nennen 62 Figure 5 6 Final result of myOR I ecdesia e egen 63 Synthesis report without registert 1252 ciis tiov eed eese dice Ee 65 Synthesis report with left edge register minimization esses 66 VHDL code without register minimization esee 67 VHDL code with Left Edge register minimization ee es se ee se 67 complete VHDL code without register minimization ueueeooo se 74 complete
49. er numbers ERT EX COLOR G V E for i 1 to V c 1 while da vertex adjacent to V with color do C ap die babel Wwalitia codo Es a ex GS a v5 we Figure 17 Vertex Coloring pseudo code The Data Flow Graph Compiler page 29 At the beginning every node got a colour number of 0 The algorithm is applied to the compatibility graph in figure 18 Note that compatibility graphs are undirected graphs Figure 18 Compatibility Graph The result is shown in Figurel9 In comparison figure 20 shows the optimum colouring So the colouring graph algorithm does not yield optimal results One way to improve the algorithm is the swapping colour method In our example we reach the optimal solution either by backtracking or by swapping the colours of vertex v5 and v4 Figure 19 Non minimum Coloring Figure 20 Minimum Coloring Fortunately the Left Edge Algorithm holds an interesting property The underlying graph built with our concept of lifetimes of variables belongs to a subgroup of graphs called interval graphs Colouring the intervals is equivalent to colouring the vertices For interval graphs the colouring algorithm needs polynomial time for solving and The Data Flow Graph Compiler page 30 one important note the result is optimal This is based on the fact that interval graphs have perfect vertex elimination scheme For detailed description on the definition of perfect grap
50. erlin Springer Verlag Reps T 2001 Maximal Munch Tokenization in Linear Time University of Wisconsin USA September 2001 pp 1 3 Lutz M and Schmitt F J 1997 Vom Prozessor zum Programm M nchen Carl Hanser Verlag pp 90 103 Ralston A and Reilly E D and Dahlin C A ed 1993 Encyclopedia of Computer Science Third Edition New York Van Nostrand Reinhold pp 207 208 Tremblay J P and Sorenson P G 1985 The Theory and Practice of Compiler Writing New York McGraw Hill pp 5 8 pp 138 150 pp 182 196 8 Aho A V and Sethi R and Ullman J D 1986 Compilers Principles Techniques and Tools Reading Addison Wesley pp l 15 pp 83 86 9 Atallah M J 1999 Algorithms and Theory of Computation Handbook London CRC Press LLC pp 3 1 3 25 10 Lamont M Sorting Algorithms online Available at http linux wku edu lamonml algor sort sort html Accessed 23 July 2006 11 CAR Hoare 1962 Quicksort Computer Journal Vol 5 1 pp 10 15 References page 83 12 13 14 15 16 17 18 19 Hehner E C R 1993 A Practical Theory of Programming New York Springer Verlag pp 67 68 A Hashimoto and J Stevens 1971 Wire routing by optimizing channel assignment within large apertures Proceedings of the 8th Design Automation Workshop Atlantic City USA June 1971 Kurdahi F J and Parker A C 1987 REAL A Program for REgister ALlocation
51. fferent processing steps of the PreConverter are explained Special attention is taken on the part about register optimization The concepts are discussed in the same order as the related methods are executed inside the PreConverter code 3 3 1 Sorting of the Tasks During the execution of the VHDLGenerator program it occurs quite often that we have to sort arrays Ports need to be sorted by their branch number case statements by their execution time and tasks by their start time So because of the high usage of The Data Flow Graph Compiler page 24 sorting algorithm it is worth to have a deeper look in it in order to choose the most appropriate one When we want to perform the Left Edge algorithm it is of great importance to have the tasks sorted in ascending order to their Start Times So the first step of the PreConverter stage is the sorting of the tasks An appropriate algorithm for sorting has to be selected Appropriate algorithm means here that we want to find an algorithm that sorts a given set of items with the lowest complexity We define complexity here as number of steps and time units In general one can categorize sorting algorithms either by their algorithm structure Divide amp Conquer form 9 or by their complexity 10 Using the second categorization most of the common sorting algorithms are divided further into basically two classes of algorithms with respect to their execution time For the first class of algor
52. find consistence Hence we can state that the generated VHDL code works correct for the tested values Depending on whether we have chosen register minimization or non register minimization we obtain different VHDL source code When comparing the two descriptions in terms of waveforms we can asses that the circuit behaviour is the same for both circuits Note that for reasons of clarity the waveforms of the register minimized version are not added So we can state further that using the left edge register minimization for the VHDL code generation does not have any influence on the functional behaviour of the resulting circuit That characteristic is a necessary condition for any minimization step you perform on digital circuits Conclusions page 65 5 3 Synthesis Results Next step will be to check whether the generated VHDL description passes the synthesis In figure 40 and the Synthesis reports of register minimization and register non minimization are opposed The relevant parts are highlighted Final Results RTL Top Level Output File Name VhdlCodeGenerated ngr Top Level Output File Name VhdlCodeGenerated Output Format NGC Optimization Goal Speed Keep Hierarchy NO Design Statistics IOs 194 Cell Usage BELS 2 3l GND 1 INV 52 LUTI 28 LUT2 214 LUT2_D 32 LUT2_L 1 LUT3 178 LUT3 D 32 LUT3_L SH LUT4 84 LUTAD als LUTAL 36 MUXCY 88 MUXF5 13
53. fiqyuoueqyse perersuetepoopun MI EL N pe Neu ec balelueBepoopuN EE EES ETE EN Inseljguuauequel pereleusGepoopup SMEER pareisuatepoopu qyupueqsa pareieuatapoopun aygyupusqsa paeiauatepoopuy ip ege pareisuetepoopu qyqytpusquar parereuetepoopuy Figure 39 Figure 5 6 Final result of myOR 1 Conclusions wwesaljquupuaqsa palerauabepoopuiy p gute pajesusfapoopu Conclusions page 64 Next step would be to verify the produced program for its arithmetical results That means we want to know whether the gained results are correct according to the specified boolean equation For that reason we have to take a look at the random input values that are generated by the TestbenchGenerator The random port assignments for this example are Input Port Assignment a 10011111000100001001110110110000 b 01001110111110000010110010111110 01011011111110110110001011101000 100010001011100001 10000100010000 0010100100000001 1110001011010100 cC If we put these values into the proposed boolean equation and calculate by hand we yield F a b c d e a b c a Db d a amp b e a amp b c d tel 10101101111100111111001010011010 9 01001110111110000010110010111110 01011011111110110110001011101000 10001000101 1100001 10000100010000 0010100100000001 1110001011010100 001110010000010100000001 11010110 Comparing the result computed by hand with the result delivered by the program we
54. gie e gadw ere iogdelvestor Si dowe 0 b sin std logic vector 31 downto 0 resulte sout Sul logie eeor Aldo 09 end component myAnd component myOr is port eds gabs Sicel heyepier escons mS tegi o gue enable dn std logie a in std logic vector 31 downto 0 b in std logic vector 31 downto 0 sia etel logie vector Si Cloyne 201 result out Sto logie vector 21 downte OM end component myOr Appendix B page 75 signal timer signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal signal begin integer range 0 to 1000 myXor_1 enable std_logic myAnd 1 enable std logic myAnd 2 enable std logic myOr 1 enable std logic Comp Comp Comp Comp Comp Comp Comp Comp Comp Reg0 Regl Reg2 Reg3 Reg4 Reg5 Reg6 Reg7 Reg8 o ja tei 43k a gor s qf e CompOutRegO CompOutRegl CompOutReg2 CompOutReg3 std std stg std std std std std std Seam Sec Secu SEE Jost vector locale eeneg logic vector logue sweetie tocco Nocte ect on Logie vector logic vector Logie vector logde vector logie veecor logic vector logic vector Z gg Us Z SU ownto ownto ownto ownto ownto ownto ownto ownto ownto OAAR TE LOOD Pos 31 downto 31 downto 31 downto 31 downto zeg 0g ero logie vector rti downteo 0 s reg lg stad Og e
55. h reports yields that the left edge register minimization reduces the number of needed flip flops on the target device Conclusions page 67 If we take a closer look to the produced codes we can figure why the second version needs less resources In the figures above the segment where the temporary output registers are stated are shown for each code version The non minimized version needs one output register for each of the four instantiated VHDL component signal reg Os sed logie veccor Il dente 9 signal weg l3 std logie weetes 3l owe 9 signal reg 23 sed logic veccor Il downto 7 signal reg 3g std logic vector 3l downto 7 Figure 42 VHDL code without register minimization In comparison the LEFT EDGE ALGORITHM reduces the number of needed registers to three sigmal weg 03 siel logie wecror 31 downto 7 sigmal reg ie stel logue wecror Si dewnto 7 sigmal reg 22 stel logue weoror Si dewnto 7 Figure 43 VHDL code with Left Edge register minimization So we conclude that the reduced amount of needed output registers generated by the LEFT EDGE Algorithm is the cause for reduced amount of used flip flops In contrast the number of LUT4 is increasing compared to the non optimized variant The additional resources are used for multiplexing the inputs for the registers Depending on the application the user can decide whether to have minimized flip flops or less usage of combinatorial logic In most
56. handles exception last method where to handle the exception Figure 24 Exception handling in Java Exceptions objects are created and thrown using the keywords new and throw Messages are added over the constructor field The throw statement could be embedded for example into an if clause like public void example throws ExceptionType if condition throw new ExceptionType Message Figure 25 throw statement In the calling method all methods that might throw an exception have to be placed inside a try catch block Methods following after a try statement are executed and in case of an exception the runtime system jumps into the appropriate catch block The stress lies upon appropriate catch block The calling method can only handle exceptions that are part of one of its catch blocks If for example a method throws an The Data Flow Graph Compiler page 37 exception of type IOException then the calling method needs a case statement that covers this type An example is shown in figure 26 tae t example throws a ExceptionType catch FileNotFoundException f catch ExceptionType eil Figure 26 try catch There exist other concepts like the finally block which will not be discussed here When writing an Exception handler for VHDLGenerator we will need to know how to create own Exception classes and how to throw catch and handle Exceptions in Java 3 3 3 2 Exception handling
57. hat lead to a failure The user should be informed where and why the error occurred Furthermore it is often of use to test the obtained results against the specification for faults How to write system level tests for VHDL programs will be part of chapter 3 4 The Data Flow Graph Compiler page 34 We categorize possible faults into three abstraction levels on which they may appear Figure 23 illustrates the different error levels where the intensity of the color indicates the impact of the error on the design On first level there are the faults that are inserted on the syntactical level That means for some reason the given input is faulty and cannot be further processed In our case a level one fault could be a mistake due to the grammar of the to be parsed text Level one faults can be detected as an error very soon during the processing of the program and therefore do not lead to a failure On the second level we have to deal with faults that entered in a way that they are not detected as an error by the program itself The faults are handed over through the whole process and end in a complete failure when the final operation is put into process These kinds of faults are the worst because they may end in production errors So it is highly recommendable to catch these faults and transform them into an error before they end up into a failure TestbenchGenerat or java Saftey critical Difficult to detect PreConverter java
58. hs and perfect vertex elimination scheme take a look inside 2 For Perfect Vertex Elimination Scheme there is no need of backtracking or colour swapping The original Left Edge Algorithm as proposed by Hashimoto and Stevens 13 has been developed to solve channel routing problems The goal was to assign wires to a minimum number of routing tracks As a first step the wires are sorted with increasing order of their left end points from the left edge of the channel That is the reason why this algorithm is called Left Edge Now the assignment starts The first wire at the left is assigned to the first track Then we find the first wire whose left edge is to the right of the last selected wire and assign this one to the current track If we reach the last column the assigned wires are removed and a new track is started This algorithm is repeated until no more wires can be assigned to tracks Figure 21 14 shows the pseudo code for the proposed algorithm The Data Flow Graph Compiler page 31 Algorithm LEA Begin 1 Sort all nets on their left most end positions 2 gitt ihe tracks Milo soos p ty im as time Moses ef 3 for each net n sorted list 4 tor Galcl vo d em dL ce el 5 if n doesn t overlap vith any nets in f 6 then assign n to f 7 endfor 8 delete n from the list 9 endfor END Figure 21 Left Edge pseudo code As it can be seen Left Edge algorithm uses a Greedy approach Nevertheless the Left Edge Algorithm g
59. ig difference is that the Swing components are operating system independent All used components inherit from the class ComponentUI and are therefore purely written in Java Components provided by the operating systems are no longer used We decide to take most of the components out of the Swing classes because compared to AWT Swing got the following advantages Swing Components are available for all operating systems The Graphical User Interface page 48 Programs using the swing components look the same for all operation systems That is useful with respect to the portability of our VHDLGenerator program We want VHDLGenerator GUI to run also on different operating systems like Linux or Windows XP without a significant change of the GUI panel Swing Components are 10096 coded in Java that implicates that we are also compatible to other hardware platforms Swing Components uses Pluggable Look and Feel that allows an interchangeable graphical representation Swing contains more than four times as many components as AWT Beside all advantages there exist only some small drawbacks that are negligible Because all components are emulated in Java the execution reduces a slightly in speed But with regard to the working power of actual computers the difference is not really noticeable 4 2 The Model View Controller Architecture in Java To make full use of all the Java Swing GUI power one has to understand the underlying ar
60. ike Note that the commentary will at the beginning will be ignored by the parser The Data Flow Graph Compiler page 23 NOTE Enter all used components with their input and output ports except the clk reset and enable which are generated automatically NAME myXor INPUT a 32 b 32 OUTPUT result 32 NAME myAnd INPUT a 32 5 32 OUTPUT result 32 NAME myOr INPUT a 32 b 32 c 32 OUTPUT result 32 Figure 13 Components File example So to every component the following information has to be entered the components name the inputs ports and output ports with the adequate bit width Every component is expected to have a clock a reset and an enable input So thesis parameters are not entered by hand but generated automatically The components are parsed separately from the tasks and stored inside a different ArrayList called UsedComponents We will need them later for components declaration inside the VHDL code Furthermore they are used for error detection which will be subject of chapter 3 3 3 3 3 The PreConverter stage The Parser stage delivers two objects for further processing One is called Tasks and contains all assigned tasks with their specified attributes The other is called AllComponents and contains an ArrayList of all used VHDL components The goal of the PreConverter stage is now to prepare the collected data for the final VHDL Converter stage In the following chapter the theory of the di
61. inside VHDLGenerator As mentioned in the introduction of this chapter one of the goals of the HCDMParser and PreConverter stage is to catch and handle faults of level one and two First we like to figure out all possible faults that might appear when executing VHDLGenerator and categorize them The table in Figure 27 shows one out of several possibilities how to classify the different faults The table is thought as a reference for the user to get a more detailed documentation of the error message printed out by VHDLGenerator Every error got an error code that is printed out Errors belonging to level one are of format 1 x level two starts with 2 x The Java Exception Type divides the levels further into the different Exception classes All possible exceptions could be only generated in classes that contain executable methods namely HCDMParser PreConverter and VHDLGenerator The location column gives information about working step in which the exception was thrown Finally a description of the error and short proposition for solving is given The Data Flow Graph Compiler page 38 Note that all exceptions thrown are forwarded up to the very first calling method where they are handled Level one exceptions occur when input data is faulty and the runtime system cannot proceed These exceptions are safety non critical because they result directly in an error and do not sneak through the whole process They are generated by the Java runtime
62. ithms the execution time increases quadratic ally with the number of items The second class needs n log n complexity with being n the number of items Figure 14 and 15 10 demonstrate how typical algorithms of each class behave for large n Big O notation is used where the O represents the complexity of the algorithm n stands for the number of items to be sorted and the whole expression inside parenthesis determines a measure for complexity Inside the complexity class the algorithms may still vary in their constant runtime factor how much time each of the n log n steps takes The Data Flow Graph Compiler page 25 Bubble Insertion Selection Shell Figure 14 O n sorts 07 Figure 15 O n log b sorts As it can be seen the Quick Sort algorithm yields the best performance Quick sort works onto the divide and conquer principle and uses recursive structures That may cause problems for applications with resource limitation For VHDLGenerator we The Data Flow Graph Compiler page 26 expect to have sufficient computation power and memory space so that recursion is not a drawback for us The dividing partitioning works in a way that we first choose a pivot element AII elements that are greater than the pivot element are put into a new partition All elements that are smaller than the pivot are put into a second partition Then the algorithm is repeated for each partition separately At
63. led nodes The relations E are the edges between the vertices Graphs can be categorized into two groups directed graphs and undirected graphs Undirected graphs are graphs that express a slack relation between vertices with temporal order between them A compatibility graph is a good example for an undirected graph We will work with compatibility graphs in chapter 3 3 2 in context of register optimization A directed graph got a directed dependency between consecutive vertices In short a directed graph is an undirected graph but with a temporal order of its vertices The HCDM Tool uses directed graphs Directed graphs can be used to represent procedural languages with imperative semantics That means we want to express an algorithm with a language that takes care of the execution order Calculation of one step is therefore based on results of the previous steps which gives us a temporal order The representation of the calculation flow is done graphically in terms of its vertices the tasks represented as nodes and its relations the dependencies represented as branches The direction is indicated by drawing an arrow We discuss the differences between two types of sequencing graphs the task graph and the data flow graph The Data Flow Graph Presentation page 6 2 3 Task Graphs The Task Graph is the one implemented forhe HCDM Generator This sequencing graph has only task vertices That includes that also the dependencies onl
64. literal is not a valid literal that means not a KeyLiteral or part of Lexeme the parser breaks off the current iteration and takes the next literal in line If the literal is valid but not a KeyLiteral the literal is accumulated to the current Lexeme KeyLiterals are defined for example as white space or closing braces If one of these characters comes out of the stream the Lexeme accumulation is aborted and the WordID is checked If a matching WordID is set the current Lexeme has to be the second Lexeme of a token pair So the Token is stored Analogous if the WordID is not set the current Lexeme is neither a non relevant Lexeme nor a KeyWord of a token pair In the last case the corresponding WordID is being set and the state machine continues accumulating literals The Data Flow Graph Compiler page 18 No valid Literal break check Literal a Word Length 0 break WordlD set add Token valid Literal Key Literal stop Literal Accumulation Accumulate Literal to Lexem Check WordID Set WordID Word break Figure 9 Parser State Chart 3 2 2 3 Parsing the HCDM file The file that contains most of the needed information is the HCDM hcdm txt file The HCDM file is as already described in chapter 2 a textual description of the data flow graph So once the graph is drawn inside HCDM the tool creates this file and saves it into a specified directory We now want to use the expl
65. marked then the also the generated Testbench file is opened The Generate Button The Convert Button starts the VHDL converting process in the following order 1 A HCDMParser object is created and the three text files are parsed in the order they are represented on the graphical user interface 2 An object of type PreConverter is created The HcdmParser object is handed over as an argument to the constructor The status of the register minimization radio button is stored into an attribute The method parse applied to PreConverter object does the pre converting job 3 An object of type VHDLConverter is created The PreConverter object is handed over as an argument to the constructor The method convert applied to VHDLConverter converts the data into VHDL code 4 Depending on the status of the Open VHDL File checkbox the VHDL file is opened by notepad exe or some other specified program The Graphical User Interface page 55 The Message Field The Message Field gives all information of the current state of the program When new directories are entered into one of the four path fields and confirmed with Enter then the actual valid path of the corresponding field is given out When pressing the Generate VHDL button the user is informed about the start of the convert process If everything performs well a message appears that tells that the converting process succeeded If not an error message with the according error co
66. mpiler page 45 testbench variables it is quite helpful that the VHDL Converter class hands over an ArrayList called EntityInputPorts that contains the interface of our VHDL model If we do so the testbench variables can be allocated much easier The assigned testvectors are constructed per default using a random pattern The algorithm for designing the random pattern is slightly tricky The Java API provides a class called Random When applying the method nextInt to an instance of the Random class a pseudo random 32 bit integer number is given back The method toBinaryString returns the corresponding binary value as a string We have to deal with basically two major problems that occur when calling the nextInt method If the generated random number does not cover all the given port bit width we get a truncated bit vector that leads to errors during the VHDL compiling process That is why we have to pad leading zeros in this case Another problem is the limited range of the produced random values Unfortunately the Java API only provides indexed random methods up to 32 bit integer values That means we receive a maximum bit width of 31 bit 1 bit reserved for the sign VHDLGenerator is planned to be used for description of encryption algorithms where bit length of 128 bit and more are quite common To create appropriate testbenches we need to be able to extend the vector format to an arbitrary length This is realised in VHDL Generator by c
67. nd directed branches that represent the data dependencies If we want to represent external operators the task circles could be used We use pseudo tasks to implement external inputs External Inputs are defined as Tasks that are direct successors of the root task We can identify them by comparing the branch numbers In quite the same manner the external outputs are simulated Outputs are defined to be the last tasks inside the DFG They have outgoing branches back to the root task which is an adequate characteristic for filtering them out The name of the external operators is handed over the same name field as used for the task names see HCDM grammar In the later converted VHDL code these inputs also own a certain bit length Inside the HCDM grammar for the Task construct there are several possible fields where to hand over the data type In principle it is possible to enter the bit length into any of the predefined Task fields like IMPORTANCE LEVEL or TIMING that are not used for our DFG converting Because of simplicity and particularly because of consistential reasons we decide to enter the bit length right behind the variable name separated by brackets That implies that when parsing the Task NAME field to VHDL the name itself and the bit length have to be separated and stored individually The Data Flow Graph Compiler page 12 3 The Data Flow Graph Compiler The nomination and structure that is applied to the VHDL Converter
68. ns The program flow is then bended over to the exception handling routine All exceptions are thrown inside the execution of a method Methods that are able to throw exceptions got the extension throws Exceptions next to the method identifier Exception is a Java class of its own There exist several classes that inherit from Exception and specify the different types of Exceptions Note that one can also create an own exception class and define a specific behaviour there So throwing an exception means creating an instance of this class and hand it over to the runtime system The runtime system has to find an appropriate handler for the exception As first step the runtime system gives the exception to the method above that calls the method in which the exception is thrown The calling method either has to catch the exception and handle it or forward it to the method above In the last case a new exception object has to be created that encapsulates the original exception message That way an exception can be handed from the method it occurred up to the first method executed in the program If not before the exception has to be definitely handled there The scheme is shown in the figure 24 The Data Flow Graph Compiler page 36 Method in which exception occurs throws Looking for an appropriate Calling method handler with exception handler forwards Looking for an appropriate Calling method handler with exception handler
69. ns we need to find a method to read the data in and give it out literal by literal In our case the data will be at text file and a literal will be a single char value Java offers the possibility to handle data in form of streams that means to read and create streams A stream can be considered as a batch of data on its way from some source to some specified destination The big advantage is that we can abstract from the kind of data that is streamed That way the destination process does not have to care about where the stream comes from and the source process does not have to take care where the string is going to In our case we are parsing from a text file into a storage variable of type Array List All inputs and outputs in Java are realized as streams To use streams the package java io has to be included The streams descend all from a common abstract class The class nputStream implements the interface Reader OutputStream The Data Flow Graph Compiler page 16 implements the interface Writer All classes that inherit from one of the two classes provide the basic same functionality The class Reader offers interfaces to open read and close files The class InputStreamReader and StringReader implement that interface For our purpose we will use these two classes and another subclass called FileReader which inherits from nputStreamReader to read the text files produced by HCDM To create and read streams with these classes is quit
70. ogic 1164 all entity myOR is jou el reseta B sa ee Losie emables a gol lox as da eccl logio vectori corato OE js Ta gvel logie re Cit Ore ol down oMON es da srol logt vector sil clowaneo 0 result out std logic vector 31 downto end myOR architecture RTL of myOR is begin process clk resetn variable delay integer range 0 to 31 begin if resetn 0 then delay 0 result lt others gt 0 elsif CLK event and CLK 1 then if enable 1 then if delay 10 then result lt a or b or c delay 0 delay delay 1 result lt others gt end if else delay 0 result lt others gt 0 end if end if end process end RTL Figure 47 The used OR component Appendix B page 79 The AND Component library IEEE use IEEE std logic MUGA all entity myAND is poren Eli reseeca s di geel Losies emeles da Sol logies ag im Gueol logue vector 3i Glewmee 0 log aua Stel lorcue veters sil cdevmceo 0 result out std logic vector 31 downto 0 end myAND architecture RTL of myAND is begin process clk resetn variable delay integer range 0 to 31 begin if resetn 0 then delay 0 result lt others gt 0 elsif CLK event and CLK 1 then if enable 1 then if delay 20 then result lt a and b delay 0 delay delay 1 result lt others gt end if else delay 0 result lt others gt 0 end if qol is
71. ollowing section gives a short introduction into the concepts of GUI programming in Java In the last section the VHDLGenerator GUI itself is discussed That section is also part of the reference manual 4 1 Java Swing vs AWT The Java Foundation Classes JFC offer two basic sets of components used for building a GUI The Abstract Window Toolkit AWT and Swing Before starting we have to figure out which one is best to use for our case Let us emphasize some properties of both sets and point out the main differences The AWT classes provide a rich set of user interface components and a robust event handling model for GUI programming The included Layout Manager allows the creating of flexible window layouts which do not depend on a particular window size or screen resolution The AWT components depend on native code counterparts called peers to handle their functionality Therefore these components are also called heavyweight components in contrast to lightweight components which are used inside the Swing classes The AWT delegates the painting of components as well as monitoring and controlling to the runtime system Actual graphical operating systems like Windows XP or MacOSX got complex libraries that contain the desired components These libraries are only available in a compiled form as binary data Therefore you do not have the possibility to change or extend the given components The Swing classes contain all features of the AWT The b
72. olumn gives concrete examples for each design phase Introduction page 2 Flow Action Example Formal Specification Code Entry al Domain Specific Language Y Verification Algorithmic ode Automated CDM Generation y Simulation HCDM Model Allocation and CoDesign Model Scheduling CDM Scheduled HCDM Model Code Generation Y VHDL HDL Synthesis FPGA Netlist Place amp Route Figure 1 proposed Design Flow The first step consists of the Code Entry Phase There the developer generates an algorithmic implementation in the design language The implementation has to follow the requirements of a formal specification An automated verification tool is used to test the implementation against the specification given by the developer The next step in the design flow is an automated scheduling and allocation process For this purpose the HCDM tool is used The HCDM Generator is a tool that has been created by Stephan Klaus 1 in contents of a dissertation at the Technical University of Darmstadt HCDM is used to describe data dependencies between different tasks in form of task graphs Scheduling and resource allocation is done automatically A more detailed description of the HCDM tool is given in chapter 2 The last step of the design flow is the Code Generation Right at this point starts the work of the implemented VHDLGenerator Its purpose is exactly to parse the results of HCDM i e the data flow graph together with
73. oncatenating the random 32 bit values The description of the concatenating algorithm can be formulated as described in figure 29 1 Concatenate n times the 31 bit generated random value nc N iscalculated as n PortBit D 1 rounded down to next integer number 2 Do zeros padding every time the random number does not go over the full 31 bit range 3 Pad the remaining bits of port width with random values The remainder is calculated as remainder PortBitWidth n x 31 4 Do zero padding if generated random number does not go over the full range of the remainder width 3 Assign concatenate random value to testbench variable Figure 29 concatenating algorithm description With the described algorithm random test vectors of arbitrarily size can be constructed The Data Flow Graph Compiler page 46 The corresponding assignment time for every test vector is generated out of the Runtime variable handed over from the previous stage The testbench serves as evaluation for the structural design A functional verification is not possible because VHDLGenerator does not have information on the functionality Thus for example CRC cyclic redundancy check could not be tested because the Random class does not provide methods that generate correct checksums The Graphical User Interface page 47 4 The Graphical User Interface Using the Graphical User Interface GUI is a comfortable way to work with VHDLGenerator The f
74. ph Compiler page 44 342 The VHDL Testbench Generator This chapter treats with the third class of error types not yet discussed in chapter 3 3 These errors appear on the logic level The user should have a possibility to compare the current implementation to the given specification 3 4 3 1 X Testbenches in general For VHDL models it is quite common to write so called testbenches for testing purposes A testbench is a VHDL description itself with the difference that we do not define a port interface The port declaration inside the entity is kept empty The tested model is instantiated as a component and port mapped to internal test signals The internal testbench signals receive test vectors at different points in time using concurrent statements The keyword after followed by a time notation tells the simulator tool to assign that value at the specified point in time Note that the after clause is not synthesizable and only used for simulation purposes Figure 26 VHDL Testbench The testbench and the proper VHDL code are handed over to the simulator which represents the circuit behaviour in graphical form as a wave 3 4 3 X Testbench creating for VHDL Converter The name as well as the directory are constructed using the entered VHDL File path The testbench uses basically the same concepts of streaming and declaration methods for the VHDL statements as the VHDLConverter stage For assigning the The Data Flow Graph Co
75. putPorts and setOutputPorts are responsible for this work Then the underlying architecture has to be written The architecture starts with the declaration of used components Fortunately the used components are already The Data Flow Graph Compiler page 43 extracted inside the PreConverter stage They are all stored in the variable UsedComponents and with a proper framework of the VHDL syntax they can be pushed directly to the output stream Every Input and Output Port of the components needs a buffer variable over which values are entered and red The results of the components are written to registers The method for allocating the registers is called declareRegister Depending on the used algorithm in the PreConverter stage one register per component result or a minimum number of registers according to LEFTEDGE algorithm is generated After the begin clause in VHDL the port map is done Named pormapping is used for the generated VHDL code The scheduling in VHDL has to be realized inside a process statement that is sensitive to c k and reset We need a scheduler variable that triggers the corresponding inputs to components and takes the results back at the right point of time The scheduler is realized as a counter that is incremented at every rising edge of the clock The case statements are elaborated during the PreConverter Stage and can be put directly into the output stream with the right VHDL framework The Data Flow Gra
76. ready and the scheduled component is free to process When generating the VHDL code these semantics should be implemented carefully in the code so that the resulting hardware has got the same behaviour intended by the original DFG The conversion is done correctly when the DFG description and the synthesized hardware have the same input to output characteristics The ports define the interface of our entity and are generated first The whole design is synchronous which means inputs and outputs of components are written and read synchronously to the clock So first input will be c k The clock should work at the same frequency used for the DFG scheduling and will be distributed to all components later on For synchronous design it is also quite common to define a reset signal to set the circuit back to the initial state The global reset is defined as low active Third input is a one bit wide input called enable that starts the processing of every component These three single bit inputs are the same for every DFG entity and are generated automatically Next come the input and output ports of the DFG Because the PreConverter has already processed the data the Input and Output ports are easy to find If a task got an external input or output it is already stated in one of its attributes So VHDLGenerator just has to check if some Tasks got same ports and then write the port with corresponding bit length into the output stream The methods setIn
77. rface GUI that is presented in chapter 4 To demonstrate the correct behaviour of VHDLGenerator a benchmark program is constructed Chapter 5 tells how the test program and its results look like The Data Flow Graph Presentation page 4 2 The Data Flow Graph Presentation In the next sections it is explained why we use Data Flow Graphs to describe high level hardware applications The background of graph theory is explained more in detail than it would have been necessary for this chapter But when it comes to explain Register Optimization this additional information will be helpful The HCDM tool is introduced as an easy and comfortable way to create task graphs The basic differences between Task Graphs and Data Flow Graphs are described It is explained how the Task Graphs generated by HCDM are manipulated in order to obtain Data Flow Graphs 2 1 Data Representation Form When generating VHDL code it is of great importance to use an appropriate representation form for implementation that reflects the basic nature of hardware description languages Hardware implementations allow for example parallel computation So our chosen data representation form should support parallel structures also And second we target dataflow intensive algorithms While this is a severe limitation in general for HW implementations it is acceptable The Control Flow is described implicitly by the presetting for scheduling and allocation inside HCDM F
78. t 2dlist gt H CONDITION lt conditionlist gt H lt edgelist gt EDGES lt edges gt edges lt edge gt lt edges gt edge HEDGE s id 7 NODES lt idlist gt F lt params gt F lt params gt lt param gt lt params gt lt param gt lt string lt string 2 N lt condition gt true false lt conditionlist gt lt conditionlist gt N lt statesequences 7 N lt statesequences gt l e statesequence 7 V lt statesequences gt lt statesequence gt lt cond gt lt statesequence gt lt cond gt integer lt integer gt lt idlist gt lt integer gt lt idlist gt lt integer gt lt digit gt lt integer gt lt digitt gt PP PEPESE per 8 9 70 lt string gt lt allascit codeserl gt lt string gt In the following the parameter that are provided by each component hCDM NAME The name ROOT ID of the root task CURRENT ROOT ID of current root CURRENT LEAFS list of Task ID of node of actual detail grade Resource NAME The name COST costs of this resource NUMBER maximum amount that are allowed to use TYPE communication or functional resource CONNECTED list of functional resources that are connected via a communication resource Behavior class N
79. t program modules For our VHDLGenerator program we orientate on that classical compiler model Thereby the basic structure is kept the same to some extend Figure 7 shows the adjusted compiler model for VHDLGenerator Data Flow Graph Scheduling Components description description description Lexical Syntactic Semantic Code DE Analyzer liis dd as Optimizer Generator Error nal recognizer Generator VHDL Testbench Figure 7 Model of the Data Flow Compiler As it can be seen instead of one source program we receive three text files that need to be extracted In the drawing the analyzers are related to the Java classes in which they are executed The boxes in beige indicate the membership to each class Before the VHDL Code is generated an output register optimisation is performed via Left Edge algorithm in the code optimization phase during the PreConverter stage Possible errors are detected and printed out Optional a testbench could be generated In the following we will explain more in detail how the different stages work The Data Flow Graph Compiler page 14 3 2 The Parser stage In this section the design of the HCDM parser will be developed First an introduction to parsing theory is given where the different concepts and term declarations are explained It is shown how these concepts are applied to the actual problem A state chart diagram is developed to demonstrate the behaviour of the implement
80. t the VHDL Code basically three different text files need to be parsed The HCDM file that describes the tasks ports and the hierarchical relation between them The scheduling file sets start and stop times for the tasks and how they are bind to the components The scheduling is necessary because we are dealing with limited The Data Flow Graph Compiler page 17 resources We also need to know which components are available and how their interface looks like This information is contained in the components file The parsing procedure is quite the same for every text file of the three so we will explain it only once First it is explained how the parsing is realized in general Second the information we want to extract out of every file is stated The parsing process can be explained in terms of a deterministic finite state machine that is shown in figure 9 To understand the state chart some explanation of the expressions needs to be given Expression Meaning valid Literal a literal that is a possible part of a Lexeme word KeyLiteral A literal that determines the end of a Word Word Lexeme Word_ID Stores the meaning of the consequent Lexeme to built the token pair not relevant Lexem Lexeme that is not part of a Token KeyWord First Lexeme of a Token indicates the type of the token Figure 8 State Chart expressions The program enters into the checkLiteral state every time a new literal is pushed out of the stream If the current
81. ted during the scheduling and does not require any further user interaction The designer has to define the resources and the tool will generate a corresponding scheduling and allocation 2 6 HCDM Grammar HCDM produces two different output text files One is a file with the textual description of the graph The other text file describes the scheduling for the different tasks on the specified components For parsing these two files later on the meaning of the grammar of these two files is important The whole HCDM grammar and an example of a graph text file written with the HCDM grammar are added to the appendix of this thesis For demonstration we state here an example of a task description written in HCDM Further examples are following in the chapter on parsing The Data Flow Graph Presentation page 10 TASK 14 NAME Par2 PTIMIZATIONTYPE 1 MPORTANCE 1 URE PROBABILITY ds e Vlak d s RIORITY 4 IMING 0 ESOURCES 25 20 5 20 ELATIONS IORELATION INPUT 84 181 OUTPUT 78 P COINDILIILON d dex kal p oC pi EI 2S teal ing E Oo D SUBTASKS Figure 5 Task description in HCDM One can see that the graph description always starts with a declaration of the used resources Shortly after the tasks are defined Each task contains several fields for setting task parame ters The HCDM grammar cont
82. ts bit length has to match with this bit length Otherwise similar problems than for the previous case appear We have to check for over and under assignment of bit length All level two faults are detected by the method checkPorts inside the PreConverter stage The Data Flow Graph Compiler page 39 checkPorts throws an exception of type PortException PortException is a self made Exception type that does nothing more than specify the level two exceptions and store messages The procedure for finding the errors is straightforward One loop iterates all tasks and compares the number of ports with the associated component ports If a mismatch occurs a PortException with error report is thrown The same procedure applies for a bit width mismatch The Data Flow Graph Compiler The Data Flow Graph Compiler page 41 Error Code 1 7 1 7 1 7 1 8 1 9 2 0 22 D Java Exception Exception Exception Exception Exception Exception PortException PortException PortException Location PreConverter PreConverter PreConverter VHDLConverter TestbenchGenerator PreConverter PreConverter PreConverter Description the VHDL file could not be found on the computer Make sure that the spelling is correct and that the specified program is able to read text files Note that the code is a simple text file and can always be opened by a text editor like notepad or Kedit
83. tty self explanatory some detailed information for documentation reason is given When starting the VHDL Generator the user interface looks like in Figure 33 In VHDLGenerator the order of the program execution is directly mirrored to the GUI That means that information is entered in the same order as it is processed later on Figure 33 VHDLGenerator GUI screenshot The Graphical User Interface page 53 HCDM File Path field In the first field the path of the HCDM file has to be entered A default path is given that is taken automatically when no other path is specified Note that when entering a new path the directories have to be separated by Otherwise the path is not taken correctly Confirm the new entered path with Return The actual path is given out inside the message box Errors that are related with this field contain error code 1 1 For further information please take a look at the exception table in Chapter 3 3 3 Scheduling File Path field The second field is for entering the directory of the Scheduling file Here the same properties as already explained for the HCDM File Path Field hold Errors that are related with this field contain error code 1 2 Components File Path field The third field is for entering the directory of the Components file Here the same properties as already explained for the HCDM File Path Field hold Errors that are related with this field contain error code 1 3 VHDL File
84. uar payerauabepoopyA RUE sayy youaqysay payelaueBapoopy nseiyqyupuaqgse perereusBepoopu Sjqyvpuaqgp parersusbapoopu y D nsdeg peersuebapooipuh B M Vouagisal perersueapoopu y ejqupueqiser paereuebapoopuhy EET EI ujeselyqyuouamsa payplouaBapoopya xpu qyuouemse pajereusBepoopuw 2 1 and myAND Figure 38 Result of myAND page 63 lonfiy qy youaqisay payeleuaBepoopyA KEE E ey hinn e pet pajeleuabepoopup eier o u gu eet perereuaDepoopu Verst o ugu eet payeleuabapooppyA Yp odaduperbet peleraueepoopuk ansar ofiy qy youaqisay perereusbapoopu oy lofiujqyuouequsar PejereueGepoopyv qy Iofiujqyuouequsar peiereuabapoopu e Iofiu qyuauequsar pejereuabapoopu aeus loftujquvpuaqser payeiauaBapoapy EE MB n edel PareraueBapoapy MEE pareieua apoapya oC Puefiuyqyyouaqisay paleiauaBepoopun ez puefiuyqyyouaqisay pajersusGepoopuy geit puefuyqyuouequei VETTE EE SN qy puefiqyupueqsa pereieuetepoopun ejl puefitjqyuoueqsa pareieuatepoopuw euo Redu dusel pareisuatepoopu E N EK E Cape payeleuaBapoopya 7 Bay qyyouaqysay payereuaBapoopya Bay qyyouaqysaypayereuaBapoopya 7 Bayqyyouaqisay payereuebepoopyyy Bannoduco quyoveggei pereievaSepoopiy LEEN Sannoduoa qyyouaqyay payelauabepoopy y dbannoduco dusel perersuatepoopun TE EE EN TEE N TE EE EN Bamduoo qyyauaqsay payeleuabepoopy y TE ETE EN e62nidwoo qy youaqisay pajersuaBepoopua TT TEE N Bauduoo ayVeueael pajeieua5apopya TEE N ES io
85. urthermore the representation form should be easy to extract by means of a parser Given the two criteria of parallel data representation and simplicity of extraction a graph based description turns out to be the best solution We will use Data Flow Graphs which are a subtype of graphs that also allow representing external inputs and outputs In fact Data Flow Graphs show similar characteristics as digital hardware components In the DFG a task can only fire if all of its inputs are ready and the scheduled component is free to process In the same manner VHDL Components are constructed A general description of graph based data representation is following in the next section To cover our second goal of extraction simplicity the previous mentioned HCDM tool could be used This tool allows drawing Task Graphs graphically via a GUI It The Data Flow Graph Presentation page 5 generates automatically a textual graph description which follows a well defined grammar that could be used to construct a pattern for the parser Moreover HCDM also includes timing aspects It performs scheduling of different tasks on predefined resources That issue covers the synchronisation aspect of common VHDL design With respect to these aspects HCDM is considered to be an appropriate tool The last sections of these paragraphs are dedicated to the HCDM tool 2 2 Graphs in general A graph G V E consists of vertices V and its relations E Vertices are often cal
86. y relate tasks Task Graphs have two important characteristics They are acyclic and polar Acyclic means that the graph includes a partial order between its tasks Polar means that it got a source vertex at the beginning and sink vertex at the end of the graph In the HCDM tool the source vertex and the sink vertex are joined to the Root task Figure 2 Task Graph example This task does not implement any function but indicates the begin and the end of the graph This fact will be important later when it comes to parsing of the tasks All the initial tasks are successors of the Root Task and all final tasks are predecessors of the Root Task Figure 2 1 shows an example of a task graph Corresponding Tasks graphs designed by HCDM could look like the example in Figure 2 2 The Data Flow Graph Presentation page 7 Figure 3 HCDM Task Graph example screenshot The Data Flow Graph Presentation page 8 2 4 Data Flow Graphs Compared to the Task Graph the Data Flow Graph DFG includes additional vertices To every task in the graph possible external operators are appended So a Data Flow Graph does not only give the data dependency between two consecutive tasks but also the dependency of every task on external inputs out1 out2 out3 Figure 4 Data Flow Graph example The destination for the task result can be either another component or an external output port So a Data Flow Graph could be considered as an extende

Vorlage zur Erstellung von Haus- und Diplomarbeiten

Contents

Download Pdf Manuals

Related Search

Related Contents