____________________________________________________________________________ CSEE E6861 Handout #23a Prof. Steven Nowick March 4, 2016 ____________________________________________________________________________ ____________________________________________________________________________ MIDTERM CAD PROGRAMMING PROJECT ____________________________________________________________________________ ____________________________________________________________________________ OVERVIEW: In this problem, you will create a small CAD tool for multi-level logic optimization, for one of the most critical and powerful steps: MULTI-CUBE EXTRACTION. Your tool will read in a file for a logic network, identify the optimal multi-cube expression to extract (i.e. with best 'gain', or overall cost improvement), and output the resulting modified logic network. Multi-cube extraction is covered in the assigned De Micheli reading, as well as in Handout #20. It was also covered in detail in class in lecture #7 (Thursday, March 3). The particular approach you will be using is an advanced and elegant 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, top p. 374-top p. 378. A good small example of a simple rectangle formulation of multi-cube extraction is given in Example 8.3.18 (p. 376) and Table 8.1 (p. 377). It allows a precise formulation of the optimal multi-cube extraction problem. This advanced approach was introduced by Rick Rudell (UC Berkeley, later at Synopsys R&D) as part of his PhD thesis (1989). NOTE: The discussion of a "cube-variable" matrix from bottom p. 374 to bottom p. 375 relates to *single-cube* extraction. It is required reading, and relevant, but not used in this tool assignment. Your focus will instead be on the "kernel-cube incidence matrix" (or "kernel-cube matrix") from bottom p. 375 to mid p. 376 (and table on p. 377) used for *multi-cube* extraction. 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 multi-cube extraction to perform. As part of this work, you will generate useful intermediate information, including on prime rectangles, costs, etc. ____________________________________________________________________________ ======== DETAILS: ======== DUE DATE: Monday March 28, 4:00pm 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 (2-3 pages). Details will be announced shortly. DEMO: You will need to set up a demo to present your tool to Kshitij. 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 CAD tool problem. Both students in a group will receive the same grade. However, for the small midterm homework + SIS problems, *only solo work is allowed*. GRADING: The entire combined 'midterm homework and CAD project' is worth 21% of your final grade. It includes 3 parts: homework (written problems and SIS CAD tool problem), and this CAD programming problem. The written + SIS parts together count as one 'homework' and count 6% of your final course grade. The current part (CAD tool) is worth 15% 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 .16 # there are a total of 16 variables that appear across all the functions f1 = ab + c f2 = abc + aj + ghj + ij f3 = d + ef + ghi f4 = ghk + ik + km ... 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) Generate All Kernels/Co-Kernels for Each Local Function =========================================================== Before you can set up the "kernel-cube (incidence) matrix", you first need to obtain all kernels (and corresponding co-kernels) of each of the local functions. To do so, you will implement the "KERNELS" algorithm, presented in De Micheli on p. 369 (Algorithm 8.3.4). (It is a more optimized version of the basic algorithm R_KERNELS.) This algorithm should be run on each of the read-in local functions, resulting in the complete set of kernel/co-kernels pairs for each such function. ____________________________________________________________________________ ================================================ (c) Construct the Kernel-Cube (incidence) Matrix ================================================ You will construct the corresponding kernel-cube matrix in your tool. Follow the guidelines in the De Micheli reading. It should include the information presented in the matrix of TABLE 8.1 (p. 377). IMPORTANT CHANGES: There are a few small changes you will make in the structure of Table 8.1, to eliminate unnecessary information, and better column headers (some are missing in De Micheli!): - 1st column: ADD HEADER "kernels" - 2nd column: DELETE -- not needed - 3rd column: ADD HEADER "ID" - 4th column: ADD HEADER "row #" - 5th column: This is the whole rest of the table (right side); - eliminate the header row that contains subscripted variables (e.g. 'xa xb ...'), it is not needed You should use a uniform approach to entering the kernels and cubes 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) Kernel ordering in the matrix: In a kernel-cube matrix, kernels are listed in rows. List the kernels in the following order: (1) from top to bottom, first list all kernels of function f1, then of function f2, then of function f3, etc. (where each local function is indicated by its corresponding ID); and (2) when listing each kernel, it should be written with its cubes in alphabetical order (e.g. ab + ac + def), where the cubes are ordered alphabetically from left to right, and the variables within a cube are ordered alphabetically (i.e. *not* 'ba', rather use 'ab'); and (3) when listing the set of kernels for a given local function, list them top to bottom in alphabetical order (e.g. top to bottom, 'a + d', 'ab + e', 'ac + f', 'acd + b', 'bx + g', etc.). (iii) Cube ordering in the matrix: In a kernel-cube matrix, the cubes are listed in columns. Follow the same cube ordering scheme used in De Micheli Table 8.1: (1) from left to right, first list all cubes with 1 variable, then with 2 variables, then with 3 variables, etc.; and (2) when listing a group of cubes with N variables, list them left to right in alphabetical order (for example, in Table 8.1., the 2-variable cubes are listed left to right as ac ad bc bd cd ...). ____________________________________________________________________________ ================== (d) Print Commands ================== You will need to provide 3 basic print commands: (i) printout of a table of all kernels in the matrix; (ii) printout of a table of all cubes in the matrix; and (iii) printout of the entire kernel-cube matrix. More details are provided below. ------------------------------------- (i) print command for list of kernels ------------------------------------- Include a command which allows you to print out a table (into a file) of all kernels (Boolean sum-of-products) and their associated row #'s and ID. At the bottom of this table, also print out the total number of kernels in the table. The format for each line should be: row# ID kernel 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)'. Kernels should be printed out in order of their row numbers, based on the same ordering (top-to-bottom) as defined in part (c)(ii) above. e.g. 1 1 ab + dx 2 1 ace + y 3 1 d + p + z 4 2 bd + e 5 2 c + y .... Total Number of Kernels: 12 ------------------------------------ (ii) print command for list of cubes ------------------------------------ Include a command which allows you to print out a table of cubes and their associated column #'s. The format for each line should be: "column# cube" The cubes should be printed following the left-to-right order in which they are listed in the matrix, as described in part (c)(iii) above. Once complete, at the bottom of your file, also print out the total number of cubes. Use 'tab' to line up each column. For example: 1 a 2 c 3 ab 4 bcd ..... Total Number of Cubes: 13 ----------------------------------------------------- (iii) print command for the entire kernel-cube matrix ----------------------------------------------------- Include a command which allows you to print out the entire matrix constructed in (c). The format should be very similar to that of the figure in De Micheli p. 377, Table 8.1, but with the modifications ("Important Changes") listed in part (c) above. 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. ____________________________________________________________________________ ========================================== (e) Compute and Print All Prime Rectangles ========================================== Compute all prime rectangles in the kernel-cube matrix, and create a command to print them out in a list to a file. Use the notation presented in De Micheli, pp. 374-376: e.g. to print out the prime rectangle listed in Example 8.3.18, list: ({1,4},{1,2}). All prime rectangles must contain 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. ____________________________________________________________________________ ================================================ (f) List/Evaluate All Candidate Prime Rectangles ================================================ Print out a restricted list of all prime rectangles (following similar instructions to part(e) above), which now eliminates: (i) those with only 1 column, and (ii) those which contribute to only 1 local function (i.e. to only 1 ID). This restricted list is the set of "candidate" prime rectangles for multi-cube extraction. For each such prime rectangle, also list: (1) the algebraic term for the corresponding multi-cube expression (i.e. kernel intersection) extracted. For example, in De Micheli, Example 8.3.18, "a + b" would be listed. (2) "gain" of the rectangle, i.e. the overall literal reduction in the network if you use this rectangle for multi-cube extraction: (# of literals in logic network before the corresponding multi-cube extraction) - (# of literals in logic network after the corresponding mutli-cube extraction) Note that this 'gain' is largely an area metric, since it evaluates the overall literal reduction in the network. Use the same basic print format as in part (e), but now also attach the "gain" of the candidate prime rectangle at the end of each line. Use the same sorted order to print out the rectangles as defined in (e) above. 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}) c + fg 3 ({1,3,5},{1,2,4}) a + b + de 5 ({1,3,5,6},{1,2}) a + b 8 ({2,3,4},{6,8}) hj + kmp 9 .... Total Number of Canditate Prime Rectangles: 19 ------------ Print this result to a distinct file, with a an appropriate name which identifies the step. ____________________________________________________________________________ ======================================= (g) List Best Candidate Prime Rectangle ======================================= From the list (f) above, identify the 'best' multi-cube expression to extract (or if there is a tie, list all best solutions), that is, the one(s) with highest "gain". You may combine this step with (f) above, and simply append the result of step (g) to the end of the output file for step (f). For this optimal prime rectangle (or multiple ones, if there is a tie), also list the algebraic multi-cube expression associated with it, and the names of the local functions from which it will be extracted. If there is more than one best candidate prime rectangle, use the same sorted order to print out the rectangles as defined in (e). For example: Optimal Multi-Cube Extraction Choice(s): ({2,3,4},{6,8}) hj + kmp 9 (optimal choice) ____________________________________________________________________________ ____________________________________________________________________________ ================================================ (h) List Updated Logic Network (post-extraction) ================================================ Using the best multi-cube extraction choice from part (g), you are to list the revised set of local functions of the network, after performing this extraction. If there were several best choices with same gain in (g), pick just one: the one which is first in the list of part (g). Your output file should follow the identical format of the given input file above (see part(a) above). However, it should contain the revised local functions after multi-cube extraction is performed. In particular, if the original input file was given by: ----------------------------------------------------- .20 # of local functions in file .16 # there are a total of 16 variables that appear across all the functions f1 = ab + c f2 = abc + aj + ghj + ij f3 = d + ef + ghi f4 = ghk + ik + km ... f20 = ... .e #end of the file ----------------------------------------------------- Then your output file will also list the same local functions as before (in the case 20 of them, from f1 to f20). However, there are two changes: (i) before f1, an additional line is inserted, representing the new local function for the extracted expression, using the special output X (this local function corresponds to the newly-created node in the logic network) (ii) each of the existing local functions that uses X (after multi-cube extraction) should be modified to reflect the extraction. In particular, in the above example, if the multi-cube expression, gh + i, were extracted (formed as the intersection of the kernel "a + gh + i" of f2, and the kernel "gh + i + m" of f4), then the output file, which represents the result of extracting the multi-cube expression "gh + i", would be: ----------------------------------------------------- .21 # of local functions in file .17 # there are a total of 17 variables that appear across all the functions X = gh + i f1 = ab + c f2 = abc + aj + Xj f3 = d + ef + ghi f4 = Xk + km ... f20 = ... .e #end of the file ----------------------------------------------------- The optimized logic network has one new node added (containing the extracted local function X), feeding as input into two existing nodes (f2 and f4, each with modified local functions). FORMATTING NOTE: In the output file header, the # of local functions has been increased by 1 (to 21), and the # of variables has been increased by 1 (to 17). Also note that, when inserted into the local function expressions for f2 and f4, the variable "X" appears first in the resulting cube, followed by the corresponding co-kernel (j in f2, k in f4). ____________________________________________________________________________ ____________________________________________________________________________