課程名稱︰電子設計自動化導論 課程性質︰複選必修 課程教師︰合開 開課學院：電資 開課系所︰電機 考試日期（年月日）︰2015/12/16 考試時限（分鐘）：230.... 試題 : 1. [8pts] Why is it necessary to follow design rules when drawing layouts? 2. [12pts] Please provide a figure to visualize the following set of design rules: Contact.1 {Minimum width of contact = 0.065um} Contact.2 {Minimum spacing of contact = 0.075um} Contact.3 {Minimum poly enclosure of contact = 0.005um} Contect.4 {Minimum spacing of contact to poly = 0.035um} 3. A min-heap (A) is very similar to the max-heap except that A[parent(i)] <= A[i] for every node i. Please use the corresponding heap algorithm below to answer the following questions. A. [10pts] Initially, array A[i] = 90, 60, 70, 100, 10, 50, 40, 20, for i = 1...8. Suppose we modify the BUILD-MAX-HEAP function below to produce a new function, BUILD-MIN-HEAP. Please run the BUILD-Min-HEAP(A) algorithm and fraw every step in the form of binary trees. (Hint: similar to the figures in our lecture notes.) B. [10pts] Write a new heap sort algorithm to sort the array in decreasing order. =================================== BUILD-MAX-HEAP(A) A.heap-size = A.length for i = [A.length / 2] downto 1 MAX-HEAPIFY(A, i) =================================== ============================================== MAX-HEAPIFY(A, i) l = LEFT(i) r = RIGHT(i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largeset] largest = r if largest != i exchange A[i] with A[largeset] MAX-HEAPIFY(A, largest) ============================================== ================================= HEAPSORT(A) BUILD-MAX-HEAP(A) for i = A.length downto 2 exchange A[l] with A[i] A.heap-size = A.heap-size - 1 MAX-HEAPIFY(A, 1) ================================= 4. [10pts] Given a subject graph and a set of pattern graphs, what are the requirements for a covering to be a legal technology mapping? 5. [20pts] You are given a standard cell library with pattern graphs: inv(1) -inv- buf(0) -inv-inv- nand2(2) =nand- and2(3) =nand-inv- nand3(3) =nand-inv╮ ╞nand- ╯ or2(4) -inv╮ ╞nand- -inv╯ aoi21(3) =nand╮ ╞nand-inv- -inv╯ oai21(3) -inv╮ ╞nand╮ -inv╯ ╞nand- ╯ aoi22(4) =nand╮ ╞nand-inv- =nand╯ nand4(4) =nand-inv╮ ╞nand-inv╮ ╯ ╞nand- ╯ and a logic netlist: =nand╮ ╞nand-inv╮ -inv╯ ╞nand╮ =nand╮ │ ╞nand-inv- ╞nand-inv-inv╯-inv╯ =nand╯ Apply dynamic programming (DAGON algorithm) to find the optimum technology mapping. Show the optimal matchings of every gate and identity a final optimal matching for the subject graph. 6. Given a circuit with a one-bit input and a two-bit register (DFF). Let the input be "op", and the current and next state variables be x[1:0] and y[1:0], repectively. Let the transition function be: y[1:0] = (op == 0) ? (x[1] + x[0]) : (x[1] - x[0]); where the two-bit '+' and '-' operators are defined as follows: '+' operator (out = a + b) ------------------------------ a b out[1] out[2] ------------------------------ 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 0 ------------------------------ '-' operator (out = a - b) ------------------------------ a b out[1] out[2] 0 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 ------------------------------ A. [8pts] What is the transition functions of y[1] and y[0], using variables x[1], x[0], op, and operators { and, or, inv }? Please specify the functions in sum-of-product (SOP) form. Minimization is not required. B. [8pts] Draw the BDDs (without inverted edges) for y[1] and y[0], using the variable order: { x[1], x[0], op }, where x[1] is the top variable. C. [8pts] Draw the BDDs (without inverted edges) for the transition relationship TR(y, x, op), using the variable order: { y[1], y[0], x[1], x[0], op }, where y[1] is the top variable. D. [8pts] Apply existential quantificatin on variable 'op' for the TR to obtain the TR'(y, x), using the variable order: { y[1], y[0], x[1], x[0] ), where y[1] is the top variable. E. [8pts] Let the initial state be x[1:0] = 2'b01. Compute the set of reachable states for time 0, 1, 2, ..., etc., until the fixed point is reached. Represent these set of reachable states (denoted as R0, R1, R2, ..., etc., for time 0, 1, 2, ..., respectively) in BDDs (without inverted edges). Please describe how these BDDs are computed in a sufficient detail. 7. [10pts] Please explain why we don't need the explicit form of the inverse of matrices. 8. [6pts] Please tell the differences of full and sparse matrix. 9. [4pts] Please give the big-O notation of Gaussian elimination. 10. [8pts] Nodes a and b are in distinct partitions. Assume that the respective internal and external costs of node a are 9 and 5, and the respective internal and external costs of node b are 1 and 4. Then, can we swap nodes a and b to reduce the cut cost? Why or why not? 11. Consider the placement of five modules, a, b, c, d, and e and their dimensions, shown in the figure below. ┌────┐ │ e │ └┬┬──┘ ┌─┤│←d │ ││ │c ├┴─┐ ┌┴─┤ │ │a │b │ └──┴──┘ ------------------------ Block Width Height ------------------------ a 3 2 b 3 3 c 2 3 d 1 3 e 5 2 ------------------------ A. [8pts] Derive the B*-tree for the placement shown in the figure. B. [8pts] Show all steps on the B*-tree for evaluating the area cost efficiently. What is the area cost? 12. [8pts] Given a net n with the four pins and their coordinates p1 = (2, 8), p2 = (3, 6), p3 = (7, 4), p4 = (5, 1), let the estimated wire lengths by using the semi-perimeter (HPWL) approximation and the minimum cost Steiner tree be p and q, respectively. Find p and q. 13. [8pts] Find the path from S to T by the A*-search routing for the instance (with the shaded blockage) shown below by defining g(x) to be the label from the source S to the current node of x and h(x) to be the Manhattan distance between x and the target T, where the cost function is given by f(x) = g(x) + h(x). Break the tie by picking the grid cell toward the target T. ┌┬┬┬┬┬┬┬┐ 7 ├┼┼┼┼┼┼┼┤ S = (2, 2) 6 ├┼┼┼┼┼┼┼┤ T = (5, 5) 5 ├┼┼┴┴┴┴┼┤ 4 ├┼┘shaded ├┤ 3 ├┼┬┬┬┬┬┼┤ 2 ├┼┼┼┼┼┼┼┤ 1 ├┼┼┼┼┼┼┼┤ 0 └┴┴┴┴┴┴┴┘ 0 1 2 3 4 5 6 7 14. Fault equivalence: Consider a combinational circuit Y = F(X) where X and Y are input and output vectors, respectively. Let Fa and Fb denote the faulty circuits when faults a and b are present. respectively. Faults a and b are equivalent if Fa ≡Fb, i.e., Fa and Fb are indistinguishable. Fault dominance: Fault a dominates fault b if any test pattern that detects b also detects a. Consider the 2(n+1) single-stuck-at faults associated with an n-input AND, OR, NAND, or NOR gate. A. [10pts] Identify the equivalent fault classes, i.e., dividing faults into classes such that faults in the same class are equivalent. B. [10pts] Identify the fault dominance relationship, i.e., identifying dominating faults and the corresponding dominated faults. C. [10pts] Identify a minimal subset of the 2(n+1) faults, denoted by R, such that if all faults in R are detected, all the 2(n+1) faults are detected. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1450756048.A.3B1.html ※ 編輯: frankyjuang (140.112.25.105), 12/22/2015 12:13:56