課程名稱︰電子設計自動化導論
課程性質︰複選必修
課程教師︰合開
開課學院：電資
開課系所︰電機
考試日期（年月日）︰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)