• University of Texas, Dallas

• EEDG 6301

EE 6301: Advanced Digital Logic When you submit your homeworks, to help us grade and identify your work, you need to comply with the following guidelines carefully: • Have a cover page for your homework and write clearly: (1) your name as it appears in your student ID card, (2) course name/number, and (3) homework number. For these problems, please include enough information (e.g. description and picture of the circuits, results, etc.) 1. Given the following 3 circuits, convert them into a timing dag. Read the supplemental material on the topological sorting algorithm on eLearning. Let the internal arcs of all inverters be one time unit, all OR and AND gates two time units, and all NAND and NOR gates 3 time units. Wire delays scale linearly with fanout, ie., wires with one connected have delay 1, wires with two connections have delay two, etc. a) Perform a topological sort on the three graphs. How can you use the topological sort in an algorithm to perform static timing analysis? Find the arrival times at each node. b) Contrast this to Dijkstra’s shortest path algorithm. Run Dijkstra’s algorithm on circuit a. 2. Now let’s modify graph 2 into a scheduling problem. Decompose the NAND gate into a AND gate and an inverter. Each gate will become an operation. Convert the internal arcs of the gates into an operation time equal to the internal edge weights. With the modified graph, find the window or mobility of each node in the graph. You may use the algorithm of your choice but show the steps.