______________________________________________________________________ ______________________________________________________________________ CSEE E6861y Handout #23b Prof. Steven Nowick March 4, 2016 ______________________________________________________________________ ______________________________________________________________________ INTRODUCTION TO MULTI-LEVEL LOGIC OPTIMIZATION USING "SIS" ______________________________________________________________________ ______________________________________________________________________ This handout includes a small tutorial part (first few steps below) followed by short experimental part (last few steps below). IMPORTANT: When you do the experimental part, for consistency and reproducibility, you must follow the directions exactly: exiting and restarting SIS, when to write/read a file, etc. If you do not, due to some peculiarities of the CAD tool environment, your results may not be consistent from run to run, and to the results of other students. ______________________________________________________________________ ______________________________________________________________________ INTRODUCTION SIS is a CAD synthesis package developed at UC Berkeley. It includes both combinational and sequential synthesis algorithms. Many of the algorithms presented in class are included in SIS. You already used "espresso" in Homework 1 for two-level logic minimization. In addition, SIS includes many multi-level algorithms such as extraction, decomposition, resubstitution, simplification, and elimination, which you will use for this assignment. (It also includes algorithms for state minimization and optimal state assignment, which we will not use now.) It also includes the final step in combinational synthesis: technology mapping of abstract gates to actual gates in a 'cell library'. Many of the SIS algorithms form the basis for commercial CAD tools. For this problem, you will be using "SIS". ==> See the top-level class web page, for a help page on "Running SIS." This assignment, you will learn how to run SIS, then apply to 2 large combinational design examples: (i) "bc0" (ii) "xparc" Both are from the espresso examples 'ex/indust' subdirectory. The writeup below is long, but it should be straightforward. Most of it is simply a tutorial walk-through on how to use SIS. _____________________________________________________________________________ _____________________________________________________________________________ SIS OVERVIEW AND RUNS _____________________________________________________________________________ _____________________________________________________________________________ SHORT OVERVIEW In this problem, you will use SIS to do multi-level optimization for 2 EXAMPLES: "bc0" and "xparc" benchmarks (details are below). These examples were reported by Rudell in Ch. 2 of his PhD thesis. It is in the same example subdirectory which you used for HW#1, for the espresso assignments. As usual, each of the example functions is given by an unoptimized PLA file. **FOLLOW THE INSTRUCTIONS BELOW FOR EACH EXAMPLE (one at a time)**: First, you will read in a PLA file for an example, and display it using command line. Next, you will do 2-level minimization, using "espresso". Then, you will do experiments using multi-level optimization, by applying individual transforms to update the logic network. Finally, you will get an introduction to using a pre-packaged script ("rugged script") to automatically apply a sequence of transforms. Details are provided below on how to run a number of multi-level optimization algorithms in SIS. You will (i) apply the optimizations, step-by-step; and (ii) answer a few questions to see if you know what the algorithms do, why they are being used, and discuss what results you are obtaining. _____________________________________________________________________________ GETTING STARTED As in HW#1, you will be reading and writing intermediate files, to save your intermediate optimizations. BE SURE TO READ FROM, AND WRITE TO, YOUR OWN DIRECTORY. (You do not have permission to write to the class directory.) _____________________________________________________________________________ A. MINI-TUTORIAL _____________________________________________________________________________ 0. Starting SIS. Read the top-level class web page on "Running SIS (for Midterm CAD Project)". This page gives you information on accessing or downloading SIS, and setting up your paths and environmental variables. You can also see links in this web page and to the HW#1 "Getting Started with SIS" page for SIS man pages, BLIF (Berkeley Logic Interchange Format) documentation, etc. Most of this is optional, and you only need to look at if you are curious. SIS itself has good online help, which should suffice for the needs of this problem Once you have your setup ready (paths, environmental variables, etc.), go to your home directory (or a new subdirectory), and simply type the command: (./)sis to start up SIS. _____________________________________________________________________________ 1. Reading a PLA. COPY the PLA file for the example benchmark, from the class directory to your own directory. Next, read in the pla. To do this, type to SIS interpreter: read_pla For example, to read in the PLA representation file for the 'bc0' example, type: read_pla bc0 If there is no error message, the PLA is successfully read in. However, it is not displayed. It is represented internally as a data structure in the SIS CAD tool. _____________________________________________________________________________ 2. Displaying Useful Information **USE THE FOLLOWING 2 COMMANDS EACH TIME YOU DO AN OPTIMIZATION.** (i) To DISPLAY the functions associated with each of the vertices, type in the SIS interpreter: print (ii) To display the COST of the logic network, type: print_stats We will use the literal count ("lits(sop)") as the cost of the network. _____________________________________________________________________________ 3. Heuristic 2-Level Minimization Next, do heuristic 2-level minimization of the multi-output function, by typing: espresso To see the result of this step, type the 2 commands listed in #2 above (one at a time): print print_stats You can examine the expression of each vertex in the logic network. ==> Q1. ANSWER Question 1. (see below) _____________________________________________________________________________ 4. Writing the Logic Network. Save this logic network to a file: write_eqn For example, if you are working on the 'bc0' benchmark, save to a file "bc0-1.eqn" (or some similar name), by typing: write_eqn bc0-1.eqn. Look at this file, in "eqn" format, to see how logic equations are described. Note how ! is used to describe negation, etc. This 'eqn' format is used for multi-level logic networks; it is not very different from a commercial Verilog format. _____________________________________________________________________________ 5. Reading the Logic Network. If you ever need to retrieve this logic network, or any other one which you save, you can always read it back; e.g.: read_eqn For example, if you are working on the 'bc0' benchmark, and had previously saved to the current multi-level implementation to a file "bc0-1.eqn" (as indicated above), you would re-read the network by typing: read_eqn bc0-1.eqn However, you DON'T NEED TO DO THIS NOW, since this network is now your "current network", in the SIS interpreter. _____________________________________________________________________________ 6. Multi-level: SINGLE-CUBE EXTRACTION. To do single-cube extraction, type: gcx (As always, try to find the details of "gcx" in manpage.) Do #2 above, to display information. Note the cost of the new solution (it should be reduced). Do #4 above, with a new file name, to SAVE the file in "eqn" format. _____________________________________________________________________________ 7. Multi-level: SINGLE- AND DOUBLE-CUBE EXTRACTION. It is useful to have an extraction step, which extracts (i) single-cube divisors, and (ii) also does a restricted form of kernel extraction where ONLY DOUBLE-CUBE DIVISORS ARE EXTRACTED. You now want to "roll-back" to the logic network you produced in step #3. I.e. apply this step to result of step #3, NOT to result of step #6. To do this, type: read_eqn where "" is the filename for the network you saved in Step #3. Next, do the extraction, by typing: fx (As always, try to find details of "fx" in manpage.) Do #2 above, to display information. Note the cost of the new solution (it should be reduced). Do #4 above, with a new file name, to SAVE the file in "eqn" format. Write down the results of the 2 extractions, "gcx" and "fx"; you will need to compare them later. _____________________________________________________________________________ 8. Multi-level: ELIMINATION Use the command: print_value to list the values of each node, according to the "eliminate" algorithm. This indicates the cost of eliminating each node from the logic network. Note that the "current" logic network is the most recent one, which is the result of applying single- and double-cube extraction ("fx"). Next, do elimination, using a threshold of 2: eliminate 2 Do #2 above, to display information. Do #4 above, with a new file name, to SAVE the file in "eqn" format. _____________________________________________________________________________ 9. Multi-level: REDO SINGLE- AND DOUBLE-CUBE EXTRACTION. Redo this operation, after elimination: fx Do #2 above, to update plot and display information. Do #4 above, with a new file name, to SAVE the file in "eqn" format. _____________________________________________________________________________ 10. Multi-level: ALGEBRAIC (RE-)SUBSTITUTION To do algebraic substitution, type: resub -d (As always, try to find details of "resub" in manpage.) Do #2 above, to display information. Note the cost of the new solution. Do #4 above, with a new file name, to SAVE the file in "eqn" format. ==> YOU HAVE NOW COMPLETED A MULTI-LEVEL SYNTHESIS RUN _____________________________________________________________________________ _____________________________________________________________________________ B. EXPERIMENTS: _____________________________________________________________________________ _____________________________________________________________________________ Follow the steps below exactly. Do not repeat any steps, and **DO NOT WRITE OR READ FILES**. Just do the basic operations of the given steps (including when to exit SIS and restart it). _____________________________________________________________________________ 11. Multi-level: SINGLE-CUBE EXTRACTION - exit SIS, and restart it (a) Do a run for 'bc0' example: - do step #1 above (read_pla) - run 'print_stats' (record these results) - do step #3 above (run espresso) - run 'print_stats' (record these results) - do step #6 above (run gcx) - run 'print_stats' (record these results) ==> exit SIS (b) Do a run for 'xparc' example: restart SIS follow the above steps of (a), but now for the 'xparc' example ==> exit SIS _____________________________________________________________________________ 12. Multi-level: SINGLE- AND DOUBLE-CUBE EXTRACTION, WITH ELIMINATE - exit SIS, and restart it NOTE: follow the indicated steps, but *DO NOT* save and read files, just run the precise commands indicated below. (a) Do a run for 'bc0' example: - do step #1 above (read_pla) - run 'print_stats' (record these results) - do step #3 above (run espresso) - run 'print_stats' (record these results) - do step #7 above (run 'fx') - run 'print_stats' (record these results) - do step #8 above (run 'eliminate 2') - run 'print_stats' (record these results) - do step #9 above (again run 'fx') - run 'print_stats' (record these results) ==> exit SIS (b) Do a run for 'xparc' example: restart SIS follow the above steps of (a), but now for the 'xparc' example ==> exit SIS ==> Q2. ANSWER Question 2. (see below) _____________________________________________________________________________ 13. Multi-level: EXPERIMENTS WITH "EXTRACTION" AND "ALGEBRAIC (RE-) SUBSTITUTION" In this part, you will experiment with and compare the following two commands -- 'fx' and 'resub -d'. Recall that 'fx' extracts (i) single-cube divisors, and (ii) also does a restricted form of kernel extraction where ONLY DOUBLE-CUBE DIVISORS ARE EXTRACTED, while 'resub -d' replaces a subexpression by a variable associated with an existing vertex. FOR EACH BENCHMARK, APPLY THE FOLLOWING TWO SEQUENCEs OF OPERATIONS, (a) and (b), RESPECTIVELY: (a) ==> exit SIS/restart SIS read_pla (Step #1) - print-stats (record results) espresso (Step #3) - print-stats (record results) resub -d (Step #10) - print-stats (record results) (b) ==> exit SIS/restart SIS read_pla (Step #1) - print-stats (record results) espresso (Step #3) - print-stats (record results) fx (Step #7) - print-stats (record results) RUN THE ABOVE SEQUENCES ON BOTH 'bc0' AND 'xparc' BENCHMARKS. ==> Q3. ANSWER Question 3. (see below) _____________________________________________________________________________ 14. AN ALTERNATIVE: USING "SCRIPTS" An alternative to the manual flow above is to use a pre-packaged designer 'script' (see De Micheli, pp. 356-7). A script is a text listing, in a fixed order, of a useful sequence of optimization commands. For this part, you will use a famous script, 'rugged script' (script.rugged). It works quite well on a wide variety of examples, and is often used in research papers to report results. Note that this script does *not* start with 2-level minimization, but goes directly to multi-level optimization. You will now RE-DO the synthesis of both benchmarks ('bc0' and 'xparc'), using the 'rugged script'. DO THE FOLLOWING STEPS: EXIT SIS/RESTART SIS (a) read_pla (b) print_stats (c) source script.rugged (d) print_stats (then exit SIS/restart SIS) _____________________________________________________________________________ QUIT: You are done. You can terminate your session with "sis". _____________________________________________________________________________ WHAT TO HAND IN Hand in the following: (i) answers to three short questions (SEE BELOW); (ii) FOR *EACH* OF THE 2 BENCHMARKS, for each of the following steps: #11, #12, #13, #14 COPY and HAND IN all results of "print_stats" requested within each of these problems ______________________________________________________ QUESTIONS: Q1. 2-LEVEL MINIMIZATION: SOP REPRESENTATION. ==> FOR THE "BC0" BENCHMARK ONLY (First, observe results of "print".) The logic network produced by espresso, in #3, is not explicitly in SOP form. How is this representation equivalent to SOP form? Q2. MULTI-LEVEL OPTIMIZATION: fx + eliminate + fx ==> FOR BOTH THE "BC0" AND "XPARC" BENCHMARKS In problem #12, How does the result of step #8 compare with result of step #7? (i.e. in terms of literal count) How does result of step #9 compare with result of step #7? (i.e. in terms of literal count) What is the role of step #8 (include brief discussion)? Which step in the "espresso" inner loop has a similar role, in heuristic 2-level minimization? Q3. Multi-level: EXPERIMENTS WITH "EXTRACTION" AND "ALGEBRAIC (RE-)SUBSTITUTION" ==> FOR BOTH THE "bc0" AND "xparc" BENCHMARKS Compare the final results in terms of literal counts obtained between (a) and (b). Which sequence of commands provides a better result? From your point of view, which command is more powerful, 'fx' or 'resub -d'? Give some insight as to why you expect these observed differences (3-5 sentences). Hint: Think of the opportunities for simplification provided by the two operations. _____________________________________________________________________________ _____________________________________________________________________________ If you have questions or problems, contact either myself or Kshitij Bhardwaj. _____________________________________________________________________________ _____________________________________________________________________________