____________________________________________________________________________ CSEE E6861 Handout #23d Prof. Steven Nowick March 15, 2013 ____________________________________________________________________________ ____________________________________________________________________________ MIDTERM CAD MINI-PROJECT: ---------------------------------------------------------------- FUNCTION "SIMILARITY" EVALUATION TOOL: INPUT/OUTPUT FORMAT AND PROGRAM REQUIREMENTS ---------------------------------------------------------------- This handout provides details on the input and output requirements and assumptions for the Midterm CAD mini-project Problem #2 - Function "SIMILARITY" evaluation tool. The handout includes instructions on: (i) some hints on developing the algorithm, (ii) input file format, (iii) output formats/requirements and what to hand in, and (iv) FAQs. ____________________________________________________________________________ ____________________________________________________________________________ ============================== (a) Hints on the algorithm ============================== This section provides some hints and guidelines for your tool design. The unate recursive algorithm you design needs to handle two input functions instead of one. You need to be aware of the following two points: (i) Termination rules: The termination rules need to specify some features on both input covers, or some relationships between them. (ii) Splitting variables: At each recursion step, you should pick *the same variable* for both covers and then cofactor operation is performed on both covers with respect to the same variable. ============================== (b) Input File Format: basics ============================== The input of the "SIMILARITY" problem is *TWO* fully-specified functions. We assume both of them are given in PLA formats. You can assume the file names of the two input PLAs are 'f.pla' and 'g.pla'. The PLA format is basically the same as that in SIS tool, as indiccated in the handouts for HW #1. ------- HEADER: ------- Assume the PLA file always has: 1st line: .i XXX 2nd line: .o 1 (where XXX lists # of inputs) Example: for a 23 input single-output function, the header will be: .i 23 .o 1 ----- BODY: ----- The PLA format follows the usual structure, which you have seen from espresso examples. For example, for a 5-input 1-output function, rows are of the form: 000-1 1 1100- 1 etc. ------- FOOTER: ------- Assume the PLA file always has: last line: .e ------------------------ OTHER FORMATTING ISSUES: ------------------------ There might be *extra spaces* at the beginning or ending of each line. You can assume *no blank extra lines* between the two header lines, or between the last header line and the start of body, or between lines within the body, or between the last line of the body and the footer line (.e). Also, there is no extra space line at the beginning or end of the PLA file (i.e. the 1st line must contain the information of input #, and the last line must be the footer). -------------------------------------------------------------------- ============================================= (c) Input File Format: variable names/number ============================================= # of inputs: You will need to handle only up to 20 INPUT VARIABLES. input variable names/order: Assume input variable names: x0, x1, x2, x3, ..., x19 (all lower-case) Assume the above ordering of inputs. That is, if the given function has only 5 inputs, assign the names x0-x4 in order (left to right, for the columns of the input part of the PLA files) -------------------------------------------------------------------- ============================================= (d) Output File Format: recursion tree ============================================= Your program *must* save the final recursion tree structure into a file named "recursionTree.txt". Basically, for *every node* in the tree, you have to report: (i) the splitting variable (if it is not a leaf) or termination rule that applies (if it is a leaf) (ii) the returned result at the node. In this problem, the returned result should be a number. You need to figure out the meaning of the number yourself. The following shows an example of a final recursion tree. The example tree only has 3 levels. It can possibly have many more levels in real cases. ------------------------------------------ Example final recursion tree .begin //is not needed in your file ==level 1== //root level, this is the 1st line of the file 1. x0 0.5 //x0 is the splitting variable of root, 0.5 is the returned value //space line between levels ==level 2== //level 2, totally 2 nodes 1. B1 0.75 //left child, terminated by B1 2. x1 0.25 //right child, continue recursion //space line between levels ==level 3== //level 3, totally 4 nodes 1. null //already terminated at level 2 2. null 3. B1 0.25 //left child of node 2 in level 2 4. B3 0.25 //right child of node 2 in level 2 .end //is not needed in the file -------------------------------------------- More comments on the example: (i) The returned value of level 1 (i.e. root node) is actually the *FINAL ANSWER* of the problem. (ii) Do NOT add addition space at the beginning or end of each line. (iii) Do NOT add additional space lines at the beginning or the end of the file. Also, only have one space line between levels. (iv) If a node only has one child (i.e. half of the recursion tree is pruned, label the other child as 'null'. An example is the rule U2 of tautology checking. (see handout #11) (v) Comments shown in the above example are *NOT* required in your output file. -------------------------------------------------------------------- ================================================ (e) Output File Format: intermediate PLA files ================================================ Your program *have to* include two execution modes - 'normal' mode and 'verbose' mode. In the 'verbose' mode, your program *have to* store *all* intermediate PLA files. Therefore, the TA can check the correctness of your program easily. However, in *normal* mode, you *SHOULD NOT* store any of the intermediate PLAs. This mode will be used for testing your program on large-scale problems. When you store the intermediate PLAs in the 'verbose' mode, you *have to* create a folder named 'all-PLAs', and store *all* PLAs in that folder. You should name the intermediate PLAs using the following format: (level #).(node #).(cover name).pla Using the previous recursion tree example in section (d), you should have eight intermediate PLAs stored in the folder. Their names are: 2.1.F.pla //two intermediate PLAs for level 2, node #1 (left child) 2.1.G.pla 2.2.F.pla //two intermediate PLAs for level 2, node #2 (right child) 2.2.G.pla 3.3.F.pla //similarly, the four intermediate PLAs for level 3 3.3.G.pla 3.4.F.pla 3.4.G.pla The format of each PLA you stored is the same as input PLA format, presented in section (b). However, you are *not* allowed to add any extra spaces at beginning or end of any line, or any extra space lines anywhere in the file. -------------------------------------------------------------------- ======== (f) FAQs ======== (i) You *should not* include any special rules for small functions (e.g. rule M1 in tautology checking, see handout #11). (ii) Basically, your program for the two mid-term CAD design problems will be tested on clic-lab machines. If you plan to work on any other platform, you need to be aware of compatibility issues. You can write an instruction to tell how to set up the environment properly. (iii) The requirement for the write-up report for both of the two mid-term CAD design problems will be provided later on, about 1-1.5 weeks prior to the deadline. --------------------------------------------------------------------