diff options
Diffstat (limited to 'docs/source/appendix/CHAPTER_StateOfTheArt.rst')
| -rw-r--r-- | docs/source/appendix/CHAPTER_StateOfTheArt.rst | 410 |
1 files changed, 410 insertions, 0 deletions
diff --git a/docs/source/appendix/CHAPTER_StateOfTheArt.rst b/docs/source/appendix/CHAPTER_StateOfTheArt.rst new file mode 100644 index 000000000..894d0fbbe --- /dev/null +++ b/docs/source/appendix/CHAPTER_StateOfTheArt.rst @@ -0,0 +1,410 @@ +.. _chapter:sota: + +Evaluation of other OSS Verilog Synthesis Tools +=============================================== + +In this appendix [1]_ the existing FOSS Verilog synthesis tools [2]_ are +evaluated. Extremely limited or application specific tools (e.g. pure +Verilog Netlist parsers) as well as Verilog simulators are not included. +These existing solutions are tested using a set of representative +Verilog code snippets. It is shown that no existing FOSS tool implements +even close to a sufficient subset of Verilog to be usable as synthesis +tool for a wide range existing Verilog code. + +The packages evaluated are: + +- Icarus Verilog [3]_ + +- Verilog-to-Routing (VTR) / Odin-II + :cite:p:`vtr2012}`:raw-latex:`\cite{Odin` + +- HDL Analyzer and Netlist Architect (HANA) + +- Verilog front-end to VIS (vl2mv) :cite:p:`Cheng93vl2mv:a` + +In each of the following sections Verilog modules that test a certain +Verilog language feature are presented and the support for these +features is tested in all the tools mentioned above. It is evaluated +whether the tools under test successfully generate netlists for the +Verilog input and whether these netlists match the simulation behavior +of the designs using testbenches. + +All test cases are verified to be synthesizeable using Xilinx XST from +the Xilinx WebPACK suite. + +Trivial features such as support for simple structural Verilog are not +explicitly tested. + +Vl2mv and Odin-II generate output in the BLIF (Berkeley Logic +Interchange Format) and BLIF-MV (an extended version of BLIF) formats +respectively. ABC is used to convert this output to Verilog for +verification using testbenches. + +Icarus Verilog generates EDIF (Electronic Design Interchange Format) +output utilizing LPM (Library of Parameterized Modules) cells. The EDIF +files are converted to Verilog using edif2ngd and netgen from Xilinx +WebPACK. A hand-written implementation of the LPM cells utilized by the +generated netlists is used for verification. + +Following these functional tests, a quick analysis of the extensibility +of the tools under test is provided in a separate section. + +The last section of this chapter finally concludes these series of +evaluations with a summary of the results. + +.. code:: verilog + :number-lines: + + module uut_always01(clock, + reset, count); + + input clock, reset; + output [3:0] count; + reg [3:0] count; + + always @(posedge clock) + count <= reset ? + 0 : count + 1; + + + + endmodule + +.. code:: verilog + + module uut_always02(clock, + reset, count); + + input clock, reset; + output [3:0] count; + reg [3:0] count; + + always @(posedge clock) begin + count <= count + 1; + if (reset) + count <= 0; + end + + endmodule + +[fig:StateOfTheArt_always12] + +.. code:: verilog + :number-lines: + + module uut_always03(clock, in1, in2, in3, in4, in5, in6, in7, + out1, out2, out3); + + input clock, in1, in2, in3, in4, in5, in6, in7; + output out1, out2, out3; + reg out1, out2, out3; + + always @(posedge clock) begin + out1 = in1; + if (in2) + out1 = !out1; + out2 <= out1; + if (in3) + out2 <= out2; + if (in4) + if (in5) + out3 <= in6; + else + out3 <= in7; + out1 = out1 ^ out2; + end + + endmodule + +[fig:StateOfTheArt_always3] + +.. _sec:blocking_nonblocking: + +Always blocks and blocking vs. nonblocking assignments +------------------------------------------------------ + +The "always"-block is one of the most fundamental non-trivial Verilog +language features. It can be used to model a combinatorial path (with +optional registers on the outputs) in a way that mimics a regular +programming language. + +Within an always block, if- and case-statements can be used to model +multiplexers. Blocking assignments (:math:`=`) and nonblocking +assignments (:math:`<=`) are used to populate the leaf-nodes of these +multiplexer trees. Unassigned leaf-nodes default to feedback paths that +cause the output register to hold the previous value. More advanced +synthesis tools often convert these feedback paths to register enable +signals or even generate circuits with clock gating. + +Registers assigned with nonblocking assignments (:math:`<=`) behave +differently from variables in regular programming languages: In a +simulation they are not updated immediately after being assigned. +Instead the right-hand sides are evaluated and the results stored in +temporary memory locations. After all pending updates have been prepared +in this way they are executed, thus yielding semi-parallel execution of +all nonblocking assignments. + +For synthesis this means that every occurrence of that register in an +expression addresses the output port of the corresponding register +regardless of the question whether the register has been assigned a new +value in an earlier command in the same always block. Therefore with +nonblocking assignments the order of the assignments has no effect on +the resulting circuit as long as the left-hand sides of the assignments +are unique. + +The three example codes in +:numref:`Fig. %s <fig:StateOfTheArt_always12>` +and :numref:`Fig. %s <fig:StateOfTheArt_always3>` +use all these features and can thus be used to test the synthesis tools +capabilities to synthesize always blocks correctly. + +The first example is only using the most fundamental Verilog features. +All tools under test were able to successfully synthesize this design. + +.. code:: verilog + :number-lines: + + module uut_arrays01(clock, we, addr, wr_data, rd_data); + + input clock, we; + input [3:0] addr, wr_data; + output [3:0] rd_data; + reg [3:0] rd_data; + + reg [3:0] memory [15:0]; + + always @(posedge clock) begin + if (we) + memory[addr] <= wr_data; + rd_data <= memory[addr]; + end + + endmodule + +[fig:StateOfTheArt_arrays] + +The 2nd example is functionally identical to the 1st one but is using an +if-statement inside the always block. Odin-II fails to synthesize it and +instead produces the following error message: + +:: + + ERROR: (File: always02.v) (Line number: 13) + You've defined the driver "count~0" twice + +Vl2mv does not produce an error message but outputs an invalid synthesis +result that is not using the reset input at all. + +Icarus Verilog also doesn't produce an error message but generates an +invalid output for this 2nd example. The code generated by Icarus +Verilog only implements the reset path for the count register, +effectively setting the output to constant 0. + +So of all tools under test only HANA was able to create correct +synthesis results for the 2nd example. + +The 3rd example is using blocking and nonblocking assignments and many +if statements. Odin also fails to synthesize this example: + +:: + + ERROR: (File: always03.v) (Line number: 8) + ODIN doesn't handle blocking statements in Sequential blocks + +HANA, Icarus Verilog and vl2mv create invalid synthesis results for the +3rd example. + +So unfortunately none of the tools under test provide a complete and +correct implementation of blocking and nonblocking assignments. + +Arrays for memory modelling +--------------------------- + +Verilog arrays are part of the synthesizeable subset of Verilog and are +commonly used to model addressable memory. The Verilog code in +:numref:`Fig. %s <fig:StateOfTheArt_arrays>` +demonstrates this by implementing a single port memory. + +For this design HANA, vl2m and ODIN-II generate error messages +indicating that arrays are not supported. + +.. code:: verilog + :number-lines: + + module uut_forgen01(a, y); + + input [4:0] a; + output y; + + integer i, j; + reg [31:0] lut; + + initial begin + for (i = 0; i < 32; i = i+1) begin + lut[i] = i > 1; + for (j = 2; j*j <= i; j = j+1) + if (i % j == 0) + lut[i] = 0; + end + end + + assign y = lut[a]; + + endmodule + +[fig:StateOfTheArt_for] + +Icarus Verilog produces an invalid output that is using the address only +for reads. Instead of using the address input for writes, the generated +design simply loads the data to all memory locations whenever the +write-enable input is active, effectively turning the design into a +single 4-bit D-Flip-Flop with enable input. + +As all tools under test already fail this simple test, there is nothing +to gain by continuing tests on this aspect of Verilog synthesis such as +synthesis of dual port memories, correct handling of write collisions, +and so forth. + +.. code:: verilog + :number-lines: + + module uut_forgen02(a, b, cin, y, cout); + + parameter WIDTH = 8; + + input [WIDTH-1:0] a, b; + input cin; + + output [WIDTH-1:0] y; + output cout; + + genvar i; + wire [WIDTH-1:0] carry; + + generate + for (i = 0; i < WIDTH; i=i+1) begin:adder + wire [2:0] D; + assign D[1:0] = { a[i], b[i] }; + if (i == 0) begin:chain + assign D[2] = cin; + end else begin:chain + assign D[2] = carry[i-1]; + end + assign y[i] = ^D; + assign carry[i] = &D[1:0] | (^D[1:0] & D[2]); + end + endgenerate + + assign cout = carry[WIDTH-1]; + + endmodule + +[fig:StateOfTheArt_gen] + +For-loops and generate blocks +----------------------------- + +For-loops and generate blocks are more advanced Verilog features. These +features allow the circuit designer to add program code to her design +that is evaluated during synthesis to generate (parts of) the circuits +description; something that could only be done using a code generator +otherwise. + +For-loops are only allowed in synthesizeable Verilog if they can be +completely unrolled. Then they can be a powerful tool to generate array +logic or static lookup tables. The code in +:numref:`Fig. %s <fig:StateOfTheArt_for>` generates a +circuit that tests a 5 bit value for being a prime number using a static +lookup table. + +Generate blocks can be used to model array logic in complex parametric +designs. The code in +:numref:`Fig. %s <fig:StateOfTheArt_gen>` implements a +ripple-carry adder with parametric width from simple assign-statements +and logic operations using a Verilog generate block. + +All tools under test failed to synthesize both test cases. HANA creates +invalid output in both cases. Icarus Verilog creates invalid output for +the first test and fails with an error for the second case. The other +two tools fail with error messages for both tests. + +Extensibility +------------- + +This section briefly discusses the extensibility of the tools under test +and their internal data- and control-flow. As all tools under test +already failed to synthesize simple Verilog always-blocks correctly, not +much resources have been spent on evaluating the extensibility of these +tools and therefore only a very brief discussion of the topic is +provided here. + +HANA synthesizes for a built-in library of standard cells using two +passes over an AST representation of the Verilog input. This approach +executes fast but limits the extensibility as everything happens in only +two comparable complex AST walks and there is no universal intermediate +representation that is flexible enough to be used in arbitrary +optimizations. + +Odin-II and vl2m are both front ends to existing synthesis flows. As +such they only try to quickly convert the Verilog input into the +internal representation of their respective flows (BLIF). So +extensibility is less of an issue here as potential extensions would +likely be implemented in other components of the flow. + +Icarus Verilog is clearly designed to be a simulation tool rather than a +synthesis tool. The synthesis part of Icarus Verilog is an ad-hoc add-on +to Icarus Verilog that aims at converting an internal representation +that is meant for generation of a virtual machine based simulation code +to netlists. + +Summary and Outlook +------------------- + +Table \ :numref:`tab:StateOfTheArt_sum` summarizes +the tests performed. Clearly none of the tools under test make a serious +attempt at providing a feature-complete implementation of Verilog. It +can be argued that Odin-II performed best in the test as it never +generated incorrect code but instead produced error messages indicating +that unsupported Verilog features where used in the Verilog input. + +In conclusion, to the best knowledge of the author, there is no FOSS +Verilog synthesis tool other than Yosys that is anywhere near feature +completeness and therefore there is no other candidate for a generic +Verilog front end and/or synthesis framework to be used as a basis for +custom synthesis tools. + +Yosys could also replace vl2m and/or Odin-II in their respective flows +or function as a pre-compiler that can translate full-featured Verilog +code to the simple subset of Verilog that is understood by vl2m and +Odin-II. + +Yosys is designed for extensibility. It can be used as-is to synthesize +Verilog code to netlists, but its main purpose is to be used as basis +for custom tools. Yosys is structured in a language dependent Verilog +front end and language independent synthesis code (which is in itself +structured in independent passes). This architecture will simplify +implementing additional HDL front ends and/or additional synthesis +passes. + +Chapter \ :numref:`<CHAPTER_eval>` contains a more detailed +evaluation of Yosys using real-world designs that are far out of reach +for any of the other tools discussed in this appendix. + +…passed 2em …produced error 2em :math:`\skull` …incorrect output + +[tab:StateOfTheArt_sum] + +.. [1] + This appendix is an updated version of an unpublished student + research paper. :cite:p:`VerilogFossEval` + +.. [2] + To the author's best knowledge, all relevant tools that existed at + the time of this writing are included. But as there is no formal + channel through which such tools are published it is hard to give any + guarantees in that matter. + +.. [3] + Icarus Verilog is mainly a simulation tool but also supported + synthesis up to version 0.8. Therefore version 0.8.7 is used for this + evaluation.) |