Description
1. Problem Description In this homework, we are going to implement a special circuit representation, called “AIG” (And-Inverter Graph), from a circuit description file. The generated executable has the following usage: cirTest [-File ] where the bold words indicate the command name or required entries, square brackets “[ ]” indicate optional arguments, and angle brackets “< >” indicate required arguments. Do not type the square or angle brackets. This cirTest program should provide the following functionalities: 1. Parsing the circuit description file in the AIGER format (See Lecture note #09 and http://fmv.jku.at/aiger/ for details). Your program should be able to detect the following types of errors in the file (Note: both line and column numbers start from ‘1’): 1. Cannot open design “c17.aag”!! 2. [ERROR] Line 1: Illegal identifier “aagg”!! 3. [ERROR] Line 1, Col 5: Missing number of variables!! 4. [ERROR] Line 1: Number of variables is too small (3)!! 5. [ERROR] Line 1, Col 5: Extra space character is detected!! 6. [ERROR] Line 6, Col 2: Missing space character!! 2 7. [ERROR] Line 9, Col 1: Illegal white space char(9) is detected!! 8. [ERROR] Line 2: Missing PI definition!! 9. [ERROR] Line 8: Missing AIG definition!! 10. [ERROR] Line 3, Col 1: Missing PI literal ID!! 11. [ERROR] Line 4, Col 1: Missing PO literal ID!! 12. [ERROR] Line 9: Missing “symbolic name”!! 13. [ERROR] Line 1, Col 14: A new line is expected here!! 14. [ERROR] Line 3: Literal “2” is redefined, previously defined as PI in line 1!! 15. [ERROR] Line 7: Literal “6” is redefined, previously defined as AIG in line 5!! 16. [ERROR] Line 3, Col 3: Literal “16” exceeds maximum valid ID!! 17. [ERROR] Line 3, Col 1: Cannot redefine constant (1)!! 18. [ERROR] Line 9: Illegal symbol index(a)!! 19. [ERROR] Line 9, Col 1: Illegal symbol type ()!! 20. [ERROR] Line 9, Col 1: Illegal symbol type (a)!! 21. [ERROR] Line 9, Col 5: Symbolic name contains unprintable char(27)!! 22. [ERROR] Line 10: Symbolic name for “i0” is redefined!! 23. [ERROR] Line 9: PI index is too big (3)!! The above error messages are summarized from the 60+ testcases in the “tests.err” directory. Note that they are NOT intended to be complete. You may be able to detect different types of errors in different testcases. In addition, the error detection may depend on how you parse the circuit description file. Therefore, it is possible that you may detect different error(s) from the reference program. In our grading testcases, we will avoid the ambiguity. So even though you should try to make your error message aligned with ours, you don’t need to spend the majority of your time in making your message exactly the same as ours for some minor differences. Moreover, you can stop the parsing at the first error you detect. You don’t need to detect multiple errors in reading the circuit netlist. However, in case of error, please remember to clean up the partial circuit you have created. Besides, to facilitate our grading, please use the error message printing function “static bool parseError(CirParseError err)” in “cirMgr.cpp” so that the error message can be the same as the reference program. Although you can implement the circuit parser in C++, you can also consider using lex(flex)/yacc(bison). Other tools are forbidden in this homework. 3 Lastly, please note that handling this error message can be very tedious and time-consuming. You are advised NOT to handle them in the beginning. Please focus on parsing the GOOD circuits and continuing for the other commands. The error message handling is only a small portion of the total grades. Don’t get stuck here!! 2. You can assume that the circuit is combinational. That is, no latch (flip-flop) is defined. Besides, you can assume that the netlist is a directed acyclic graph (DAG) and don’t need to check for the loops. However, there may be floating or unused gates. That is, some gates may not be reachable either from primary inputs (PIs) or outputs (POs), or has a fanin that is floating (See the figure below). Your program should be able to report them. In the above case (a), we call this gate “defined but not used”. In case (b), we call it “a gate with floating fanins”. More specifically, we call the floating fanins in (b) “referenced but not defined”, and designate “UNDEF” gate type for them for netlist reporting (See examples in CIRGate command). 3. You should be able to report the circuit in various aspects: circuit statistics/summary, circuit status, circuit netlist in depth-first-search (DFS) order, lists of primary inputs/outputs, and list of floating gates, etc. Note that the DFS order should be constructed by recursive calls from the primary outputs in post-order traversal. That is, a gate will not be printed until all its fanins are reported. The order of POs, as well as the order of fanins in a gate, should follow the orders as defined in the original AIGER file. Floating gates of the cases (a), and (c) above should not be included in the DFS list (Note: cases (b) and (d) should be included) since they cannot be reached from POs. Constant gate (i.e. CONST0) should be included if it is visited during the DFS traversal. You should also provide commands to report the interconnections (i.e. lists of fanins) of a gate. Please see the corresponding commands for details. 4. Please DO NOT perform any optimization in circuit parsing, such as constant propagation, redundant gate removal, and equivalent gate merging, etc. (Note: These optimizations can be evoked by commands in the final project, though.) 5. The TODO’s of this homework are all included in the src/cir directory. It contains a file cirMgr.h to define the circuit manager (i.e. class CirMgr) for circuit construction and reporting, etc. A global variable CirMgr *cirMgr as well as some member functions of class CirMgr should be defined in cirMgr.cpp. You should use this global variable in circuit-related PO PI (a) A gate that cannot reach any PO PO PI (b) A gate that cannot be reached from any PI PO PI (c) A gate that cannot be reached from PI and PO PO PI (d) A gate with a floating fanin 4 commands (defined in cirCmd.cpp) for all the circuit operations. The AIG gate data structure and its constructing functions should be declared and defined in the files cirGate.h and cirGate.cpp. You should at least define the class CirGate. It is up to you whether you want to declare inherited classes of class CirGate such as class CirAigGate, class CirPiGate, etc. 6. You should define the data members and member functions for the classes CirMgr and CirGate on your own. However, please follow the naming convention in other homework/classes and be cautious on the memory and runtime efficiency. 7. Each gate should have a unique gate ID, which is equivalent to the variable ID as derived in the AIGER file. That is, the IDs for PIs and AIG gates are the values of the corresponding literal IDs divided by 2. 8. For each PO, you should define a distinct PO gate whose single fanin is the AIG gate as defined in the AIGER file. See the following example: aag 10 2 0 3 3 2 4 16 17 6 6 2 4 10 1 2 16 10 6 This allows an AIG gate to fanout to multiple POs (e.g. Gate 8) potentially with inverted phases, or to other AIG gate(s) (e.g. Gate 3). The IDs for POs are numbered from the maximum variable IDs (as defined in the header line, not the max AIG gate ID) plus 1 (i.e. 11 in this case). Note that they are different from the IDs defined in the PO section of the AIGER file. (See 3. for the order of POs) 9. There should be a mechanism (e.g. flags) to control the dependency of the circuit operations/commands. For example, the circuit netlist should be constructed before any other circuit operations. 2. Supported Commands In this homework, you should support these new commands: CIRRead: read in a circuit and construct the netlist CIRPrint: print circuit 11 5 8 3 1 2 0 12 13 5 CIRGate: report a gate CIRWrite: write the netlist to an ASCII AIG file (.aag) Please refer to Homework #3 and #4 for the lexicographic notations. 2.1 Command “CIRRead” Usage: CIRRead <(string fileName)> [-Replace] Description: Read the circuit from the file “fileName” and store it in the global variable cirMgr. If the circuit has been read, issue an error “Error: circuit already exists!!” unless the option “-Replace” is issued. In the latter case (even with the same filename), delete the original circuit and discard all the circuit related data, create a new one, and print out the message “Note: original circuit is replaced…”. Note that with “-Replace” option the original circuit will be deleted even if the new circuit construction fails. In such case, cirMgr should be reset to NULL (0). No warning or error message is needed if “-Replace” is issued when cirMgr == 0. Example: cir> cirread test.cir // read in the circuit description file “test.cir” cir> cirr -rep kk.cir // read in the circuit description file “kk.cir” // and replace the original circuit 2.2 Command “CIRPrint” Usage: CIRPrint [-Summary | -Netlist | -PI | -PO | -FLoating] Description: Report circuit information in different ways. If the circuit hasn’t been constructed, print out an error message “Error: circuit has not been read!!”. When “-Summary” is specified, print out the circuit statistics, and when “-Netlist” option is used, list all the gates in the topological (depth-first-search, DFS) order (Note: For the gates in DFS list only, those unreachable from POs won’t be printed, even they are PIs). The “-PI”, “-PO” and “-FLoating” options will report the lists of primary inputs (PIs), primary outputs (POs) and floating gates, respectively. Example: cirtest> cirprint // print out circuit summary Circuit Statistics ================== PI 20 PO 12 AIG 128 —————— Total 160 6 Note that the statistics of gates should be in the order: { PI, PO, AIG }, no other gate types. The numbers should be consistent with the numbers of PI, PO, and AIG gates in the circuit. If there is no gate for a specific type, print a ‘0’ and do not skip this line. Note that when the circuit is read in, the numbers of PI, PO, and AIG gates must be the same as the numbers declared in the header of the AIG file. cirtest> cirprint –netlist // output the netlist in depth-first-search order [0] PI 1 (1GAT) [1] CONST0 [2] AIG 10 1 0 [3] PI 2 (2GAT) [4] PI 6 (6GAT) [5] AIG 11 !1 6 [6] AIG 16 2 !11 [7] AIG 22 !10 !16 [8] PO 24 !22 (22GAT$PO) [9] PI 7 (7GAT) [10] AIG 19 *!15 7 [11] AIG 23 !16 !19 [12] PO 25 !23 (23GAT$PO) Please pay attention to the alignment of the gate types and IDs. The IDs shown here are the variable IDs as derived from the original AIGER file. The ‘!’ sign means the input is inverted. If the input is undefined (floating), we should put a ‘*’ sign right before ‘!’ and gate ID (e.g. AIG 19 *!15 7). If the names of the PIs/POs are specified in the “symbol section”, print out the names at the end of the lines. The aag file for the above case can be found at “…/tests.fraig/cirp-n.aag”. cir> cirp -pi // print out the PIs PIs of the circuit: 1 2 7 6 3 The PIs are printed out as the same order as specified in the AIGER file. The numbers are their variable IDs. The POs should be printed by the “cirp -po” command similarly. Print “PIs/POs” even if there is zero or only one PI/PO. cir> cirp -fl // report the floating gates Gates with floating fanin(s): 7 Gates defined but not used : 9 10 Print “Gates” even if there is zero or only one floating gate. We report two types of floating gates: (1) Gates with floating fanin(s): referring to the gates with one or multiple undefined fanins. Cases (b), (c) and (d) in the floating-gate definition in Section 1.2 belong to this type. A PO with the fanin undefined should also be reported in this case. 7 (2) Gates defined but not used: referring to the gates that is defined in the AIGER file but are never used by other gates. In other words, it has no fanout. Cases (a) and (c) in the floating-gate definition in Section 1.2 belong to this type. A PI with no fanout should also be reported in this case. Note that case (c) belongs to both types, so it should be reported in both places. Besides, to ease the checking of the reporting correctness, please print out the gates of above two cases (for -Floating) in ascending order of their IDs. The netlist for the above example is: aag 10 2 0 1 6 2 4 6 6 2 4 10 1 2 14 12 10 16 10 6 18 14 16 20 14 16 If we do “CIRPtint -Netlist”, we will get: cir> cirp -n [0] PI 1 [1] PI 2 [2] AIG 3 1 2 [3] PO 11 3 2.3 Command “CIRGate” Usage: CIRGate <<(int gateId)> [<-FANIn | -FANOut><(int level)>]> Description: Report the gates in the circuit. If the “gateId” is not defined in the circuit, report “Error: Gate(gateId) not found!!”. If the option “- FANIn” or “-FANOut” is NOT specified, print out the gate information including ID, name (for PI and PO), gate type, and line number (as appeared in the AIGER file). Otherwise, print out its fanin/fanout cone with the followed option (int level). Put proper indentations for different levels of fanin/fanout printing. If there is an inversion between a gate and its fanin/fanout, put a ‘!’ before the fanin/fanout. If a gate whose fanin(s)/fanout(s) have been reported in previous lines, put a “(*)” after it is printed; do not repeatedly report its fanin(s)/fanout(s). If there is any undefined (i.e. floating) fanin, print “UNDEF” for its gate type. Example: cir> cirg 25 // print out gate (25) 11 9 5 8 3 6 1 2 0 7 10 8 ================================================== = PO(25)”23GAT$PO”, line 9 = ================================================== cir> cirg 19 ================================================== = AIG(19), line 12 = ================================================== cir> cirg 25 -fanin 4 PO 25 !AIG 23 !AIG 16 PI 2 !AIG 11 PI 3 PI 6 !AIG 19 !AIG 11 (*) PI 7 The above command reports the partial circuit as shown on the right-hand side. Please note that if a gate (e.g. AIG 11) whose fanin(s)/fanout(s) have been reported in previous lines, put an “(*)” after it and do not report its fanins/fanouts again in the later encounters. However, do not put “(*)” for a gate if its fanin(s)/fanout(s) haven’t been report. For the above example (AIG 11): cir> cirg 25 -fanin 3 PO 25 !AIG 23 !AIG 16 PI 2 !AIG 11 !AIG 19 !AIG 11 PI 7 If a floating (undefined) fanin is reported in certain gate’s fanins, print “UNDEF” for its gate type. cir> cirg 7 -fanin 1 // Please refer to the netlist in “CIRPrint” command AIG 7 UNDEF 6 AIG 5 Optionally, if a floating fanin ID is issued by this command, you can either report “Error: Gate(gateId) not found!!”, or print out as follows: 23 25 16 19 11 2 7 3 6 9 cir> cirg 6 // Please refer to the netlist in “CIRPrint” command ================================================== = UNDEF(6), line 0 = ================================================== [Orders of fanins/fanouts] The order of fanins should be kept as the same as they are defined in the original file. However, since the order of fanouts depends on how you parse the circuit, we don’t set the restriction here. Our grading testcases will try to avoid the ambiguity in checking the “CIRGate -fanout” command. [Known Problem] If a gate g has two inverted fanins f and !f, then reporting fanouts from f will not be able to distinguish !g from g. This is a limitation in the reference program, and you DO NOT need to handle this. 2.4 Command “CIRWrite” Usage: CIRWrite [-Output (string aagFile)] Description: Write the netlist to an ASCII format AIGER file. The “-Output” option specifies the file name. If it is not specified, print out the AIGER output on the standard output (i.e. the monitor). In the header line, M(Max #vars), I(#PIs), L(#Latches), and O(#POs) should be the same as the original file, while A(#AIGs) should be set as the number of AIG gates in the DFS list. PI and PO definitions in the output file should be exactly the same as the original file, even if some of the PIs are unused or some of the POs are floating. The AIG section, however, contains only the AIG gates in the DFS list of the circuit and should be printed in that order. That is, the gates that cannot be reached from POs will not be included in the output file. The symbol section should print out the symbolic names of PIs and POs in the orders as in the PI and PO lists, even though these orders are different from those in the original file. Comment section is optional. You can leave it blank or write whatever you want. Example: cir> cirwrite -o C17-opt.aag // write out the net list to “C17-opt.aag” 3. What you should do? You are encouraged to follow the steps below for this homework assignment: 1. Read the specification carefully and make sure you understand the requirements. 10 2. Think first how you are going to write the program, assuming you don’t have the reference code. 3. Type “make linux” or “make mac” to switch to a proper platform. The default is linux platform. 4. Understand the AIGER specification. 5. Define the circuit data structure. 6. Implement the circuit reader/parser which should include the following steps: (1) Parsing the netlist description file and constructing the circuit netlist, (2) Generating DFS list of the gates, (3) Checking floating gates, and (4) Checking unused gates. DO NOT handle parsing error message in the beginning. 7. Finish the circuit and gate reporting functions. 8. Test your implementation with the provided testcases. You are also encouraged to create more testcases on your own. 9. If you have time, handle the parsing errors. 10. [Note] The cir command interfaces are already given. You don’t need to implement them. Actually, you are NOT allowed to modify cirCmd.{h,cpp}. They are included in the MustRemove.txt. 4. Grading We will test your submitted programs with various testcases and compare the outputs with our reference program. Minor differences due to printing alignment, spacing, error message, etc can be tolerated. However, to assist TAs for easier grading work, please try to match your output with ours (especially the printed order of gates).
