6.896 Lecture 9 Notes

Optimal retiming: This is the main topic of the notes. It seems to be a technique for optimizing the timing of a digital circuit. Lemmas and Theorem: The notes present several lemmas and a theorem related to optimal retiming. These mathematical statements provide the foundation for understanding the concept. Mathematical Notation: The notes use various mathematical symbols and notations, including: W(u,v): This likely represents the weight or delay of a path between nodes u and v. D(u,v): This might represent the critical path delay between nodes u and v. r(v): This could be a retiming function, assigning a value to each node. Gr: This might represent a retimed graph. Constraints and Linearity: The notes mention "O(E) constraints of type 1/2" and "linear," suggesting that the problem of optimal retiming can be formulated as a linear programming problem. Linear programming: Problem statement: Given a matrix A, vectors b and c, the goal is to find a vector x that maximizes the dot product c^T * x subject to the constraint Ax ≤ b. Visual representation: The image includes a diagram illustrating the matrix A, vectors b and c, and the inequality constraint Ax ≤ b. General algorithms: Simplex method: A practical algorithm but with exponential worst-case time complexity. Interior-point methods: Polynomial-time algorithms that are becoming more practical. Feasibility problem: The problem of finding a solution x that satisfies Ax ≤ b, without considering the optimization objective. Difference constraints: A special case of linear programming where each row of the constraint matrix A contains exactly one 1 and one -1, with the rest being zeros. An example of such a system is provided. Constraint Graph: A vertex vi is created for each unknown xi. An edge vivj is added with weight aij if there is a constraint xj - xi ≤ aij. Theorem 1: If the constraint graph has a negative weight cycle, then the system of constraints is unsatisfiable. Proof: Suppose there is a negative weight cycle v1 → v2 → ... → vk → v1. Then, x2 - x1 ≤ a12, x3 - x2 ≤ a23, ..., xk - xk-1 ≤ ak-1,k, x1 - xk ≤ ak1. Adding these inequalities, we get 0 ≤ the weight of the cycle < 0, which is a contradiction. Theorem 2: If there is no negative weight cycle, then the system of constraints is satisfiable. Proof: Add a new vertex s with 0-weight edges to each vertex vi. Let δ(s, vi) be the weight of the shortest path from s to vi. Claim: xi = δ(s, vi) is a solution. Bellman-Ford Algorithm: Purpose: Finds shortest paths from a source vertex to all other vertices in a graph or determines if a negative-weight cycle exists. Initialization: d[v] = 0 if v is the source vertex. d[v] = ∞ otherwise. Main loop: Iterates |V|-1 times. For each edge (u, v): Relaxes the edge: d[v] = min{d[v], d[u] + w(u,v)}. Negative-Weight Cycle Detection: If after the |V|-1 iterations, there's an edge (u,v) such that d[v] > d[u] + w(u,v), a negative-weight cycle exists. Correctness: Proved by induction (details omitted here). Running Time: O(|V||E|) Optimal Clock Period: The notes outline a process to find the optimal clock period for a circuit: Compute W and D: Calculate the weights and delays of the circuit elements. Sort elements of D: Sort the delays in ascending order. Binary Search: Use binary search to find the largest clock period that doesn't introduce a negative-weight cycle. Retime the Circuit: Use the values found in the previous step to retime the circuit.