____________________________________________________________________________ CSEE E6861y Handout #34h Prof. Steven Nowick April 17, 2016 ____________________________________________________________________________ ____________________________________________________________________________ Final CAD Project FINAL REPORT AND SUBMISSION INFORMATION ============================================================================ ---------------------- #1. WHAT/HOW TO SUBMIT ---------------------- You are expected to hand in: (i) By email (to kbhardwaj@cs.columbia.edu) -- A tar file containing (a) 'SOURCE' and 'EXECUTABLES' of the two re-timing tools, i.e. PART I and II (b) 'README' file (details see below) (c) 'INPUT/OUTPUT FILES' for the *two* online correlator examples (details see below) (ii) Printed *report* and printed copies of *Input/Output files* for the *2* ONLINE EXAMPLES, handed in to Kshitij, in Room 468 CS Building on Monday 5/2, between 3-4pm. NOTE: The two input files are Handouts #34c and #34d, you must also hand in your corresponding output files. ====== README ====== The 'README' file should include: #1. GROUP MEMBERS: full names #2. DETAILED PROGRAMMING INFORMATION: programming language, platform requirements, etc. This should include: - Which platform you worked on (if you used CLIC/ACIS) - The compilation instructions (not all compilers are compatible) - How to compile and run your tool, and any input arguments - Where the input/output files will be expected - What commands can be used. Please provide the above information for *both* of the tools that you have implemented. #3. MISCELLANEOUS: any clarifications, information on what you didn't do, etc. ================== INPUT/OUTPUT FILES ================== You should totally run 4 experiments - 2 correlator examples on PART I tool, and the same 2 correlator examples on PART II tool. For each correlator example, in PART II, use the optimal cycle time obtained in PART I as the cycle time constraint. Please refer to handout #34e for the output files you need to provide. ========================================================================== ---------------------------------------------- #2. FINAL PROJECT REPORT: Requirements/Format ---------------------------------------------- You should include a *5.75-7.0 PAGE* WRITTEN REPORT to accompany your tool. The report should be neatly formatted, and easily readable, with each of the items below in its own labeled section. The write-up will be graded on content as well as presentation quality. Include the following: -------------------------------- (i) GROUP MEMBERS: full names -------------------------------- ----------------------------- (ii) TOOL OVERVIEW (1 page) ----------------------------- Include: (a) a summary of programming information of your two re-timing tools (not too detailed; please include the more detailed programming information in the README file): - languages, interface, overview of features (b) assumptions on file formats: any assumptions about white space, comments, blank lines, etc., where you are not following the formatting requirements, or not specified in the requirements (c) flow of each tool: an overview of the steps the tool takes, intermediate results generated, any verbose modes, any user options, etc. ----------------------------------------------------- (iii) DATA STRUCTURES AND ALGORITHMS (1.0-1.5 pages) ----------------------------------------------------- Give a summary of the data structures you used, including for: PART I: (a) storing the synchronous network (b) W/D calculation (c) FEAS algorithm PART II: (d) constraint generation (e) simplex algorithm/tableau method Also, provide any useful information on how you implemented the main algorithms mentioned above (WD calculation, FEAS, constraint generation, simplex, etc.), as well as any optimizations that you performed. --------------------------------------- (iv) TESTING METHODOLOGY (1-1.25 pages) --------------------------------------- What test you have done to each of your tools, including what examples you have chosen and why, what problems you found and how you fixed them. ---------------------------------------- (v) ADDITIONAL INSIGHTS (0.5-1.0 pages) ---------------------------------------- Any creative thoughts, findings, insights or other important things you would like us to know. --------------------------------------------- (vi) TECHNICAL QUESTIONS (about 2.25 pages) --------------------------------------------- =================================================================== (a) FLOYD-WARSHALL ALGORITHM: DYNAMIC PROGRAMMING (about 0.5 pages) =================================================================== The Floyd-Warshall (FW) algorithm uses dynamic programming. In class, dynamic programming techniques were introduced for several technology mapping methods. In dynamic programming, the "principle of optimality" holds if an exact solution to a sub-problem at each step is produced only using exact solutions to sub-problems from previous steps. In this problem, you will identify how the FW methodology obeys the principle of optimality. The FW algorithm starts with an initial annotated graph, has several iterations, and then terminates with a final exact result to the complete problem of all-pairs shortest (or longest) paths. Answer the following: - iteration 0: what optimum (i.e. exact) solution is provided *before* any iteration occurs? - iteration 1: what optimum (i.e. exact) solution is provided at the end of this iteration? - iteration i (for arbitrary i > 0): what optimum (i.e. exact) solution is provided at the end of this iteration? ============================================================= (b) RETIMING: HANDLING TOO SLOW OPERATORS (about 0.5 pages) ============================================================ Suppose you are given an initial synchronous network graph G where some vertex "v_k" has a delay d_k = 30. Also suppose that for the min-cycle optimization problem, as presented in DM and LS, the target clock cycle is \phi = 20. Intuitively, it is clear that no retiming of this system G can meet the target cycle time \phi, since the vertex v_k has too coarse granularity, i.e. the function unit block is slower than the target clock cycle. Theoretically,in DM, it is claimed that Theorem 9.3.1 provides precise necessary and sufficient conditions to characterize all feasible retiming vectors under a cycle time target \phi. WHAT TO DO: focusing on the above problem fragment, with vertex v_k, its delay d_k, and target cycle time \phi, clearly show why the constraints (9.4) and (9.5) in the theorem are *always unsolvable*: no retiming vector is feasible. Give a short answer, and justify with a clear technical explanation. ================================================================== (c) RETIMING: EXPLORING ALTERNATIVE RETIMING VECTORS (0.75 pages) ================================================================== In this question, you will explore the option of having several alternative retiming vectors for the same target clock period. In De Micheli, Example 9.3.10 (pp. 466-467), the book gives a constraint graph in Fig. 9.11 which assumes a target clock period of phi_opt = 13. The resulting feasible retiming vector "r_opt" is -[12232100]^T, which is a valid solution to the constraint graph. The book also points out that *another* retiming vector (we will call it "r_alt"), -[11222100]^T is *also* a feasible retiming solution for phi_opt = 13. It also notes that vector "r_alt" is larger: r_alt > r_opt Answer the following: (i) LARGER RETIMING VECTORS: Will *every* legal retiming vector, "r_x", which is larger than "r_opt" (i.e. r_x > r_opt) be a feasible solution for this same clock period "phi_opt"? Answer yes or no. If yes, give a clear justification. If no, give a counter-example. In each case, discuss in a few sentences. (ii) SMALLER RETIMING VECTORS (PT. 1): Will *every* legal retiming vector, "r_x", which is *smaller* than "r_opt" (i.e. r_x < r_opt) be a feasible solution for this same clock period "phi_opt"? Answer yes or no. If yes, give a clear justification. If no, give a counter-example. In each case, discuss in a few sentences. (iii) SMALLER RETIMING VECTORS (PT. 2): If your answer is no, also indicate if there is *any* legal retiming vector, "r_x", which is *smaller* than "r_opt" (i.e. r_x < r_opt) is a feasible solution. Either list an example which is feasible, or argue why none is feasible. ======================================================= (d) SIMPLEX: SELECTING A PIVOT COLUMN (about 0.5 pages) ======================================================= In this question, you are to provide some insights of selecting a pivot column in the tableau method presented in 'zweigmedia' webpage. In the 'zweigmedia' webpage for solving *standard maximization problem* (i.e. initialization is not considered), the pivot column is the column having the negative number with largest magnitude in the bottom row. Answer the following: (i) CHOICE OF NEGATIVE COLUMN Why is a column selected which contains a negative number, but not one containing a positive number? HINT: read Cormen ch. 29.3 carefully, especially the Simplex example. Think of the impact of the choice of pivot in this equivalent non-tableau approach. (ii) OTHER NEGATIVE COLUMNS Suppose an arbitrary negative column is selected in iteration i as the pivot column, which does not have the largest magnitude of the negative columns. - basic solution cost: iteration i vs. i-1 How will the objective cost of the basic solution of the current iteration (i) compare to the cost of the basic solution of the previous iteration (i-1)? - basic solution cost: iteration i -- alternative negative pivots How will the objective cost of the basic solution of the current iteration (i) using the greatest magnitude negative pivot compare with the cost using a smaller magnitude negative pivot? For each part above, give a clear answer, and briefly justify it. HINT: read Cormen ch. 29.3 carefully, especially the Simplex example. You can also try out an example to support your argument. A succinct and clear write-up is preferred to a long vague one. But of course, you are welcome to give a longer write-up if you have more to say. ========================================================================== ---------------------- #3. GRADING GUIDELINES ---------------------- The project will be graded on: (i) *correctness* and *clearness* of the output (about 80%) (ii) report write-up (about 10%) (iii) the overall quality of the project (about 10%) Including: - how easy-to-use and clear your program is - any advanced and efficient data structure been used - any good optimizations done to improve the algorithm - other interesting features, etc. ==========================================================================