CSEE E6861y Handout #34f Prof. Steven Nowick 4/9/16 ================================== FINAL CAD PROJECT: CLARIFICATIONS ================================== The following summarizes some clarifications about the project. Listed from most recent to oldest: ====================================================================== 4/9/16 ====================================================================== ------------------------------------------------------------ Simplex Algorithm: Preparing an Initial Tableau (IMPORTANT) ------------------------------------------------------------ Q. Handout #34b highlighted 2 "potential complications" with the Simplex algorithm: (a) your initial LP problem has a 'MIN', not a 'MAX', operation (b) the "basic solution" of your initial tableau is *NOT FEASIBLE* (i.e. includes negative values of variables) Are there any other special cases we need to handle, to produce a feasible initial tableau? A. YES. An additional special case you must handle is: (c) your initial LP problem has a <= (less-than-or-equal) constraint with a NEGATIVE CONSTANT ON THE RIGHT SIDE e.g. x - 3y + 4z <= -2 In this case, you *must* do pre-processing to get a correct initial tableau, based on an appropriate "slack form" (with equality). In particular, do the following: (i) transform the above constraint to >=, by multiplying both sides by -1 Ex. (-1) * [x - 3y + 4z] <==> -x + 3y - 4z (left side) (-1) * [-2] <==> +2 (right side) Result: -x + 3y - 4z >= +2 (ii) convert the resulting >= inequality to slack form (equality) in the usual way -------------------------------------------------------------------------------- --------------------------- Retiming the Source Vertex --------------------------- Q. Can we retime the source vertex? (e.g. v_h in the DM example). A. YES. The source vertex will be treated like any other vertex for retiming, hence the retiming vector entry, r_h, for the source vertex is not restricted to be 0 (though it can be). -------------------------------------------------------------------------------- -------------------------------------------------- Correct Implementation of Floyd-Warshall Algorithm -------------------------------------------------- Q. When implementing Floyd-Warshall, can I change the algorithm to optimize it, have different #'s of iterations from the original one, or alter the intermediate results specified by the original pseudo-code? A. NO! You must follow the standard Floyd-Warshall algorithm, and the setup presented in LS reading to produce both W and D results in a single run. If your algorithm is not iterating the same # of times as the standard Floyd-Warshall algorithm, or not generating the same intermediate results on an iteration-by-iteration basis, then you are *not* correctly implementing the algorithm. In particular, the key invariants of the algorithm are violated. Though there are several different presentation styles for Floyd-Warshall, all have the same notion of what results must be completed on each individual iteration. YOU *MUST* FOLLOW THE ACTUAL ALGORITHM -- SAME # OF ITERATIONS, AND SAME INTERMEDIATE RESULTS UPDATED PER ITERATION. -------------------------------------------------------------------------------- ------------------------------------------ Correct Implementation of Other Algorithms ------------------------------------------ Q. Can I modify other algorithms, such as simplex, FEAS, CP, etc.? A. NO. The fundamental structure, flow and computation of the given algorithms *must* be preserved in your implementation. -------------------------------------------------------------------------------- ------------------------------------------------ Retiming Vectors (Parts I/II): Basic Properties ------------------------------------------------ ============== non-negativity ============== Q. Are the retiming vectors from both Parts I and II always non-negative? A. YES. Both OPT2 and the Simplex method should produce retiming vectors consisting only of 0 and positive entries, never negative entries. =============== integer entries =============== Q. Are the retiming vectors from both Parts I and II always integers? A. YES. If you have followed the algorithms correctly, the resulting retiming vectors should always consist of only integers. -------------------------------------------------------------------------------- -------------------------- Sorting (Part I): Details -------------------------- In the OPT2 algorithm used in Part I, sorting is used to order the candidate clock cycle times, phi, before the loop body. Duplicate entries are also deleted. Q. In which order shall we sort the list of D values, low-to-high or high-to-low? A. Low-to-high. -------------------------------- Binary Search (Part I): Details -------------------------------- In the OPT2 algorithm used in Part I, a binary search of candidate clock cycle times, phi, is required in the outer loop. Q. Is the binary search based on finding the middle entry (index) in the list, or the middle cycle time (value)? A. Locate the middle entry (index). That is, if the sorted list of candidate clock cycle times, has 9 entries, the binary search will pick the 5th (i.e. middle) entry, regardless of its value. ODD-LENGTH LIST: If the list has an odd number of entries (e.g. 9) pick the middle entry (e.g. 5) EVEN-LENGTH LIST: If the list has an even number of entries (e.g. 8) pick the smaller entry near the middle (e.g. 4th, not 5th) -------------------------------------------------------------------------------- --------------------------------------------------------------------------------