____________________________________________________________________________ CSEE E6861 Handout #23a Prof. Steven Nowick March 7, 2013 ____________________________________________________________________________ ____________________________________________________________________________ MIDTERM CAD MINI-PROJECT: PART #1: DESIGNING A SINGLE-CUBE EXTRACTION TOOL FOR MULTI-LEVEL OPTIMIZATION ____________________________________________________________________________ ____________________________________________________________________________ OVERVIEW: In this problem, you will create a small CAD tool for multi-level logic optimization. In particular, your tool will be targeted for one of the most critical steps: SINGLE-CUBE EXTRACTION. Single-cube extraction is covered in the assigned De Micheli reading, as well as in Handout #22. It was also covered in detail in class in lecture #7 (Thursday, March 7). The particular approach you will be using is an advanced technique, which is very amenable to building a CAD tool, which is to use a 'matrix representation' and solve a 'rectangle covering problem'. The approach is outlined in detail in De Micheli, p. 374-bottom p. 375. A good small example of a simple rectangle formulation of single-cube extraction is given in Example 8.3.17 (p. 375). (The remainder of the section, bottom p. 375-top p. 378 is on multi-cube extraction, and miscellaneous discussion, so is not relevant for this assignment!, but it is still required reading for the course.) Your tool will read in a a set of equations, one for each node in a logic network, in a text file. It will then output the optimal single-cube extraction to perform. As part of this work, you will generate useful intermediate information, including on prime rectangles, costs, etc. ____________________________________________________________________________ DETAILS: Due Date: at start of class, Thursday, March 28 Languages allowed: C/C++ or Java. For others, you need to ask permission of the instructor and TA. Report Writeup: along with your source code, you will also be producing a short report on your tool (3-4 pages). Details will be announced shortly. Demo: You will need to set up a demo to present your tool to Weiwei. The demo will be run both on examples provided to you in advance, as well as new examples. Group Work: You may work solo or in a group of 2, for this problem. Both students in a group will receive the same grade. I encourage you to work in a group-of-2. Grading: The entire combined 'midterm homework and CAD project' is worth 20% of your final grade. It includes 3 parts: homework (written problems and SIS CAD tool problem), and CAD programming problems part #1 and part #2. The current part (CAD tool part #1) is worth 10% of your final course grade. Input Format: You are NOT allowed to create your own input format for what to read in. Details on required format are provided below. Output Format: You have to follow the guideline in this handout and exactly print out what is asked for. Each output file should also have a meaningful name, for example, "CPS_CubeList(.txt)". Commenting: Your program should have clear comments. We will be looking at your source code. How to Submit: Details will be announced shortly. ____________________________________________________________________________ ____________________________________________________________________________ =========== What to Do: =========== ================= (a) Reading Input ================= Your tool should read the "logic network file (LNF)", which lists the equations in the given logic network, with one equation per line. Each equation corresponds to the local function of one node in the logic network. The input file format is shown below. ------------------------------------ INPUT FORMAT: DETAILED REQUIREMENTS ------------------------------------ Every line in the body of your file (between header and footer) will contain a single local function. You will only need to handle up to 20 local functions, and you can assume that each function will have no more than 5 cubes. Also, you will only need to handle up to 26 variables. For simplicity, assume that all literals are *uncomplemented*, as in much of the basic presentation in De Micheli. That is, the local functions will not have cubes such as xy'z'. (This restriction can be relaxed in a more general approach, but it simplifies presentation and implementation of a CAD tool under the 'algebraic' approach). Also, have one space to the left and right of each '+' character. INPUT FILE EXAMPLE: TEMPLATE #start of the file .20 # of local functions in file .9 # there are a total of 9 variables that appear across all the functions f1 = ab + c f2 = abc + gh + af f3 = d + ef + ghi ... f20 = ... .e #end of the file NOTE: (i) Comments (i.e. #...) will NOT be included in the files, they are just used above to clarify the presentation of format. (ii) You can assume the input is in a correct file format. You do not have to handle errors in the specification of logic formulas, file layout, etc. You can assume that a file contains at least one local function. (iii) The variables used are lower-case alphabets, a-z. Also, no letter is skipped, i.e. you can assume that if variable 'd' occurs in at least one function, then variable 'a', 'b' and 'c' must occur at least one function. In other words, if your file specifies N variables, these variables will be precisely the first N letters (lower-case) of the alphabet. ____________________________________________________________________________ ====================================== (b) Construct the Cube-Variable Matrix ====================================== You will construct the corresponding cube-variable matrix in your tool. Follow the guidelines in the De Micheli reading. It should include all the information presented in the matrix of Example 8.3.17, including labelling of cube row #'s, column variable #'s, and function ID. You should use a uniform approach to entering the cubes and variables in your matrix: (i) How to assign the ID field: If a cube belongs to f12, then use the number 12 as the associated cube ID. (ii) Cube ordering in the matrix: Cubes must be numbered in the exact order in which they appear in the input file (left-to-right, row-by-row top down), i.e. the 1st cube in local function f1 would be cube 1, the 2nd cube is 2, etc. The numbering continues consecutively into the cubes of f2, f3, etc. (iii) Variable ordering in the matrix: Variables must be numbered consecutively in alphabetical order, i.e. 'a' is assigned to 1, 'b' is assigned to 2, etc. ____________________________________________________________________________ ================== (c) Print Commands ================== You will need to provide 3 basic print commands: (i) printout of a table of all cubes in the matrix; (ii) printout of a table of all variables in the matrix; and (iii) printout of the entire matrix. More details are provided below. ----------------------------------- (i) print command for list of cubes ----------------------------------- Include a command which allows you to print out a table (into a file) of all cubes (Boolean product terms) and their associated row #'s and ID. At the bottom of this table, also print out the total number of cubes. The format for each line should be: row# ID product Use 'tab' to line up every column. For example, if you use the C language, you may do 'printf ("%d\t%d\t%s\n",row, ID, product)'. Cubes should be printed out in order of their row numbers. e.g. 1 1 ab 2 1 ace 3 1 d 4 2 bd 5 2 c .... Total Number of Cubes: 12 ---------------------------------------- (ii) print command for list of variables ---------------------------------------- Include a command which allows you to print out a table of variables and their associated column #'s. The format for each line should be: "variable column#" The variables should be printed in alphabetical order. Once complete, at the bottom of your file, also print out the total number of variables. Use 'tab' to line up each column. For example: a 1 b 2 c 3 .... Total Number of variables: 13 ------------------------------------------------------- (iii) print command for the entire cube-variable matrix ------------------------------------------------------- Include a command which allows you to print out the entire matrix constructed in (b). The format should be very similar to that of the figure in De Micheli p. 375, Example 8.3.17. Use 'tab' to line up each column. --------------- Print each of these results to a distinct file, with an appropriate name which identifies which output is being printed. ____________________________________________________________________________ ========================================== (d) Compute and Print All Prime Rectangles ========================================== Compute all prime rectangles in the cube-variable matrix, and create a command to print them out in a list to a file. Use the notation presented in De Micheli, pp. 374-375: e.g. to print out the prime rectangle listed in Example 8.3.17, list: ({1,2,5},{3,5}). All prime rectangles must of at least two rows, but there is no restriction on the number of columns (i.e. may be 1 or higher). Formatting: ----------- (i) list one rectangle per line (ii) the numbers in each {} should be monotonically increasing and each pair separated by comma. (iii) Sort the list of rectangles by the 1st number in the first {}; when there is a tie, use the 2nd number in the first {} to break the tie. (iv) At the bottom of the file, print out the total number of prime rectangles. For example: ({1,2,5},{3,5}) ({1,3,5},{1,2,4}) ({1,3,5,6},{1,2}) ({2,3,4},{6,8}) .... Total Number of Prime Rectangles: 36 ------------ Print this result to a distinct file, with a an appropriate name which identifies the step. ____________________________________________________________________________ ================================================ (e) List/Evaluate All Candidate Prime Rectangles ================================================ Print out a restricted list of all prime rectangles (following similar instructions to part(d) above), which now eliminates: (i) those with only 1 column, and (ii) those which contribute to only 1 local function. This restricted list is the set of candidate prime rectangles for single-cube extraction. For each such prime rectangle, also list: (1) the algebraic term for the corresponding single-cube extracted (e.g. in De Micheli, Example 8.3.17, "ce" would be listed) (2) "value" of the rectangle, i.e. the overall literal reduction in the network if you use this rectangle for single-cube extraction: (# of literals in logic network before the corresponding single-cube extraction) - (# of literals in logic network after the corresponding single-cube extraction) Note that this 'value' is largely an area metric, since it evaluates the literal reduction in the network. Use the same basic print format as in part (d), but now also attach the "value" of the candidate prime rectangle at the end of each line. Use 'tab' to align the columns. Finally, append the total number of candidate prime rectangles in the end of the file. For example: ({1,2,5},{3,5}) 3 ({1,3,5},{1,2,4}) 5 ({1,3,5,6},{1,2}) 8 ({2,3,4},{6,8}) 9 .... Total Number of Canditate Prime Rectangles: 19 ------------ Print this result to a distinct file, with a an appropriate name which identifies the step. ____________________________________________________________________________ ======================================= (f) List Best Candidate Prime Rectangle ======================================= From the list (e) above, identify the 'best' single-cube to extract (or if there is a tie, all the best ones), that is, the one with highest "value". You may combine this step with (e) above, and simply append the result of step (f) to the end of the output file for step (e). For each such optimal prime rectangle choice, also list the algebraic single-cube associated with it, and the names of the local functions from which it will be extracted. For example: Optimal Single-Cube Extraction Choice(s): ({1,3,5,6},{1,2}) 3 ab {f1, f2} ({2,3,4},{6,8}) 3 fh {f3, f5} ____________________________________________________________________________ ____________________________________________________________________________