EDA past exam questions 1718 PDF

Preview

Summary

Past exam questions with answers from 2018 Feb...

Description

INSTITUTE FOR ELECTRONIC DESIGN AUTOMATION Department of Electrical Engineering and Information Technology ¨ Technische Universitat ¨ Munchen Professor Ulf Schlichtmann

Electronic Design Automation

Copyright WS2017/2018- EDA

Date: Begin: Time:

27.02.2018 16:00 75 Minutes

Permitted resources: 1. Course documents, books, printouts, handwritten notes 2. Non-programmable calculator

First name:

Musterl¨osung !!!

Last name:

Musterl¨osung !!!

Student ID:

Musterl¨osung !!!

The exam consists of 9 problems with 75 points. Important Notes: 1. Please insert your name and student ID in the table given above. 2. Use the given space and figures to solve each problem. If the space is not enough, use the back of the page and make clear, to which subproblem the answer corresponds. 3. Return all sheets of paper. 4. Do not use red or green. 5. For each question only one answer is permitted. Cross out invalid answers. 6. Independent subproblems are marked with ⋆.

Points P1

5/ 5

P2

9/ 9

P3

7/ 7

P4

8/ 8

P5

8/ 8

P6

4/ 4

P7

8/ 8

P8

10/10

P9

16/16

Sum

75/75

7. Points for individual problems are given in brackets []. 8. This exam consists of 17 numbered pages.

EDA WS2017/2018

5 2

Problem 1: General Questions [5] a) ⋆ Which of the following statements are true? [5]

Copyright WS2017/2018- EDA

The first step of the layer algorithm is to transform the given SOP-form of a function into its CSOP(canonical SOP)-form. ❅   ❅

The number of elements in the on-set of a minterm is 1, i.e., the cardinality of the on-set is 1.

❅   ❅

Suppose that there is a function f = p1 + p2 + p3 + p4 , where p1 is removable from f , and p4 is removable from f , separately. To check whether p1 and p4 can be removed together, we just need to check either (p2 + p3 )p1 or (p2 + p3 )p4 but not necessarily both.

❅   ❅ ❅   ❅

Cube removal never increases the number of literals in a function. Suppose that there is an ROBDD where bound and free variables are separated by a line and there are 4 nodes that can be directly reached by the bound variables. It is possible to use 3 intermediate variables to decompose the corresponding function.

EDA WS2017/2018

4 3

Problem 2: Quine-McCluskey Method [9] Function f1 is given as follows: f1 (x, y, z, w) = x y w + x yz + xyw + xyz w

Copyright WS2017/2018- EDA

a) ⋆ Use the following table to derive all the prime implicants (denoted by pi for each) by applying Quine’s method, 0-cube

A

1-cube

A

2-cube

A

xy z w

√

xy w

p1

yz

p4

x y zw

√

xz w

p2

− − − − −−

− − −−

x yz w

√

x yz

√

− − − − −−

− − −−

x yz w

√

yz w

√

− − − − −−

− − −−

xyz w

√

yz w

√

− − − − −−

− − −−

xyzw

√

xyw

p3

− − − − −−

− − −−

xyz w

√

xyz

√

− − − − −−

− − −−

and list all derived prime implicants in the following: [4] p1 = x y w p2 = x z w p3 = xyw p4 = yz

EDA WS2017/2018

5 4

The CompSOP-form of a function f2 is given as follows: f2 (x, y, z, w) = xy z + x yz + x z w + y w = p1 + p2 + p3 + p4 where xy z = p1 , x yz = p2 , x z w = p3 , and y w = p4 . b) ⋆ Fill in the following covering table (some minterms in the covering table may not be covered by f2 ), xy z w

x y zw

x y zw

x yz w

x yz w

√

√

xy z

Copyright WS2017/2018- EDA

x yz xz w

√

yw

√

x yzw

xy z w √

xy z w √

xy zw

xyz w

√ √

√

√

and derive the covering condition C based on the covering table (Hint: denoteP the selection variable of pi by τi ), and simplify C to derive the MinSOP-form (within a format as i pi ) of f2 . [5] !

C =1 = (τ3 + τ4 ) · τ4 · (τ2 + τ3 ) · τ2 · (τ1 + τ4 ) · τ1 · τ4 = τ1 τ2 τ4

f2 = p1 + p2 + p4

EDA WS2017/2018

7 5

Problem 3: Heuristic Minimization [7] The CompSOP-form of a function f3 is given as follows: f3 (x, y, z, w) = x y z + x y w + x zw + y z w + yz = p1 + p2 + p3 + p4 + p5 a) ⋆ Concerning literal removal of f3 , is w removable from p4 ? [1] (x y z + x y w + x zw + yz)y z w = x + x + 0 + 0 = x 6= 1 — No!

b) ⋆ Concerning literal removal of f3 , is w removable from p2 ? [1]

Copyright WS2017/2018- EDA

(x y z + x zw + y z w + yz)x y w = z + 0 + z + 0 = z 6= 1 — No!

c) ⋆ Concerning cube removal of f3 , is p4 removable from f3 ? [1] (x y z + x y w + x zw + yz)y z w = x + 0 + 0 + 0 = x 6= 1 — No!

d) ⋆ Concerning cube removal of f3 , is p2 removable from f3 ? [1] (x y z + x zw + y z w + yz)x y w = z + z + 0 + 0 = 1 — Yes!

e) ⋆ Suppose there is a function f4 ∈ B4 . f4 = h4 + z w and (h4 )z w = x y + xy. Is z w removable from f4 ? [1] No.

f) Considering f4 = h4 +z w and (h4 )z w = x y +xy, write down the minterm(s) that is(are) covered by both h4 and z w . [2] x y z w and xyz w

EDA WS2017/2018

3 6

Problem 4: ROBDD and Functional Decomposition [8] The following shows the ROBDD of a function f5 (x1 , x2 , x3 , x4 ).

x3 1

0

x4 x2

x2 x1

Copyright WS2017/2018- EDA

x4 x2 x1

1

0

a) ⋆ Represent (f5 )x3 x4 as a function of x1 and x2 . [1] x2 + x 2 x 1 (x2 + x 1 is also correct)

b) ⋆ Among (f5 )x3 x4 x2 , (f5 )x3 x4 x 2 , (f5 )x3 x 4 x2 , and (f5 )x3 x 4 x 2 , which one is x1 -independent? [1] (f5 )x3 x4 x2

c) ⋆ If x3 and x4 are bound variables while x2 and x1 are free variables, what is the minimum number of intermediate variables that we need to decompose f5 ? [1] 2

EDA WS2017/2018

5 7

Consider y = f6 (x1 , x2 , x3 , x4 ). Suppose that x2 , x3 , and x4 are bound variables while x1 is the only free variable. The following left figure shows the ROBDD of the function, and the right figure shows the resulting circuit. The building block bb1 is implemented using LUTs, and the building block bb2 is implemented using logic gates.

x3 1 x4

x1

x4 x2

x1

y x1

x2 x3

0

1

bb1 LUTs

Copyright WS2017/2018- EDA

x2

bb2

0

z1 z2

x4

d) ⋆ Consider the ROBDD and the resulting circuit. Derive the functions of z1 (x2 , x3 , x4 ) and z2 (x2 , x3 , x4 ). Do NOT simplify the functions, i.e., each implicant should contain three literals and no implicant should be removed. [2] z1 = x2 x3 x4 + x2 x 3 x4 z2 = x2 x3 x4 + x2 x 3 x4 + x 2 x 3 x 4 + x 2 x3 x4 + x 2 x 3 x4 + x2 x 3 x 4

e) ⋆ Derive the composition function y = g(z1 , z2 , x1 ) without simplifying g. [1] g(x1 , z1 , z2 ) = x 1 z 1 z2 + x1 z 1 z 2 + z1 z2

f) ⋆ Which of the following value assignment of z1 z2 is don’t-care: 00, 01, 10, or 11? [1] 10

g) Take advantage of the don’t-care value assignment, simplify y = g(z1 , z 2 , x1 ) and derive its MinSOP-form. [1] g(x1 , z1 , z2 ) = x 1 z 1 z2 + x1 z 1 z 2 + z1 z2 + z1 z 2 = x 1 z2 + x1 z 2 + z1

EDA WS2017/2018

5 8

Problem 5: Circuit with Multiple Outputs [8] f7 and f8 are two output functions of the same circuit. Their CompSOP-forms are given as follows: f7 (x, y, z, w) = x yz + x y z + x y w + x zw + y z w f8 (x, y, z, w) = x y z + x y w + y z w a) ⋆ Derive the multiple implicants of f7 and f8 . There should be 2 implicants after simplification. [2] x y zw + y z w

Copyright WS2017/2018- EDA

b) ⋆ Add the derived multiple implicants to the first columns of the following covering tables and fill in the rest of the covering tables. [3] f7

xy z w

xy z w

√

√

x y zw

x yz xy z

√

xy w

MI

x y zw

MI

yzw

x yzw √

xy z w

√ √

x zw yzw

x yzw √

√

√

√ √

√

f8

√

xy z w

x y zw √

xy w

√

√

yzw

√

xy z

MI

x y zw

MI

yzw

x y zw √

xy z w

√ √

√

√

EDA WS2017/2018

c) Based on above results, derive the optimal covering of f7 and f8 . [2] f7 = x yz + x y w + y z w f8 = x y z + y z w

d) How many literals are saved compared with the original functions (f7 and f8 )? [1]

Copyright WS2017/2018- EDA

12

3 9

EDA WS2017/2018

4 10

Problem 6: State Minimization [4]

Copyright WS2017/2018- EDA

A state output table is given as follows: µ

x=0

x=1

S0

S0 /0

S4 /1

S1

S2 /1

S1 /0

S2

S3 /0

S4 /0

S3

S5 /0

S6 /0

S4

S3 /0

S1 /0

S5

S6 /0

S4 /0

S6

S5 /0

S3 /0

Perform state minimization and give the grouping information within the following format: GA = {all states belonging to GA }, GB = {all states belonging to GB }, · · · ,

where A, B, · · · represent the group indices.

a) ⋆ For 1-equivalent states, give the grouping information. [1] GA = {S0 }, GB = {S1 }, GC = {S2 , S3 , S4 , S5 , S6 }

b) For 2-equivalent states, give the grouping information. [1] GA = {S0 }, GB = {S1 }, GC = {S4 }, GD = {S2 , S3 , S5 , S6 }

c) For 3-equivalent states, give the grouping information. [1] GA = {S0 }, GB = {S1 }, GC = {S4 }, GD = {S2 , S5 }, GE = {S3 , S6 }

d) For 10-equivalent states, give the grouping information. [1] GA = {S0 }, GB = {S1 }, GC = {S4 }, GD = {S2 , S5 }, GE = {S3 , S6 }

EDA WS2017/2018

3 11

Problem 7: Grid Routing [8] The following shows a chip containing 4 modules and its routing area is decomposed into grid cells. 3 wires need to be routed: one from S1 to T1, another from S2 to T2, and the last one from S3 to T3. For each pair of neighboring grid cells, we build 2 opposite directed edges in between them as candidate path segments, and assign a binary variable to each of them. Take grid cell N1 as an example: N1 has 4 neighbors N2, N3, N4, and N5, and thus there are 8 directed edges coming into or going out from N1. If an edge is used to construct exact one routing path, its corresponding variable will be set to 1. If an edge is not used by any routing path, its corresponding variable will be set to 0. E.g., a binary variable, bi , i ∈ {1, 2, 3, 4, 5, 6, 7, 8}, is assigned to each of the 8 edges related to N1, as shown below. Use only given variables to solve the subproblems.

Copyright WS2017/2018- EDA

N5

module

b8

module

S1 S2 S3 N5 N2 N1 N4 N3

module

T1 module T2 T3

b7 b6

b1 N2

N4

N1 b2

b5 b3

b4 N3

a) ⋆ Suppose that we route all 3 wires at the same time. How do we model that the number of routing paths entering N1 is equal to the number of paths leaving N1? (1 constraint: c1 ) [1] c 1 : b1 + b3 + b5 + b7 = b2 + b4 + b6 + b8

b) ⋆ Suppose that we route all 3 wires at the same time and the number of routing paths entering N1 is limited. How do we model that at most 2 paths can enter N1? (1 constraint: c2 ) [1] c 2 : b1 + b3 + b5 + b7 ≤ 2 c) Given c2 , suppose that we introduce a new binary variable bN 1,p in our minimization objective. How do we model that bN 1,p will be set to 1 if N1 is entered twice? (Hint: if bN 1,p can be freely chosen to be 1 or 0, it will be set to 0 by the solver since it is minimized) (1 constraint: c3 ) [1] c3 : b1 + b3 + b5 + b7 ≤ 1 + bN 1,p

EDA WS2017/2018

5 12

d) ⋆ Suppose that we only need to route the S1–T1 wire. Which constraints should we apply to N1 so that if the path enters N1, it will go straight through N1 without changing its direction? (4 constraints: c4 , c5 , c6 , and c7 ) [2] c 4 : b1 = b6 c 5 : b3 = b8 c 6 : b5 = b2

Copyright WS2017/2018- EDA

c 7 : b7 = b4

e) ⋆ Suppose that we only need to route the S1–T1 wire. Which constraints should we apply to N1 so that if the path changes its direction at N1, it must enter N1 from its left or right side and then leave N1 toward its top or bottom side? (4 constraints: c8 , c9 , c10 , and c11 ) [2] c 8 : b3 + b2 ≤ 1 c 9 : b3 + b6 ≤ 1 c10 : b7 + b2 ≤ 1 c11 : b7 + b6 ≤ 1 f) ⋆ Suppose that we only need to route the S1–T1 wire. How do we model that the path cannot go to N3 from N1 unless it enters N1 from N2? (1 constraint: c12 ) [1] c12 : b4 ≤ b1

EDA WS2017/2018

5 13

Problem 8: Placement [10] The following left figure shows a module Module1 with 2 pins: p1 and p2 , whose coordinates are denoted by (xp1 , yp1 ) and (xp2 , yp2 ). φ1 , φ2 , φ3 , and φ4 denote the lengths of the boundary segments. We introduce 4 auxiliary binary variables q1 , q2 , q3 , and q4 to represent 4 rotation options of the module, as shown in the right figure (q1 = 1, q2 = 1, q3 = 1, or q4 = 1 indicates that Module1 is rotated for 0, 90, 180, or 270 degree, respectively). The coordinate of the left-bottom corner of Module1 is always denoted as (x1 , y1 ) regardless of the rotation. xp1 , yp1 , xp2 , yp2 , x1 , and y1 are all continuous variables. Use only given variables to solve the subproblems. 0◦ (q1 = 1)

90◦ (q2 = 1)

φ2

270◦ (q4 = 1)

p1 M odule1

p1

p1

φ1

Copyright WS2017/2018- EDA

180◦ (q3 = 1)

p2

φ3

φ4

p1

p2

p2 p1

(x1 , y1 )

(x1 , y1 ) (x1 , y1 )

p2

p2

(x1 , y1 )

(x1 , y1 )

a) ⋆ How do we model that exactly one of the 4 rotation options will be selected to place Module1 ? (1 constraint: c1 ) [1] c 1 : q1 + q2 + q3 + q4 = 1

b) With c1 , how do we model xp1 , yp1 , xp2 , and yp2 so that the coordinate expression is applicable for all rotation options? (4 constraints: c2 , c3 , c4 , and c5 ) (Hint: multiplication of variables such as x1 q1 is not allowed since it is quadratic but not linear.) [4] c2 : xp1 = x1 + φ1 q2 + (φ3 + φ4 )q3 + φ2 q4 c3 : yp1 = y1 + φ1 q1 + (φ3 + φ4 )q2 + φ2 q3 c4 : xp2 = x1 + φ3 q1 + φ4 q3 + (φ1 + φ2 )q4 c5 : yp2 = y1 + φ4 q2 + (φ1 + φ2 )q3 + φ3 q4

EDA WS2017/2018

5 14

c) We now have a square module Module2 with both its x- and y-dimensions equal to φd . The left-bottom corner of Module2 is always denoted by (x2 , y2 ) regardless of the rotation, where x2 and y2 are both continuous variables. To prevent Module2 from overlapping with Module1 , we introduce 4 new auxiliary binary variables q5 , q6 , q7 , and q8 to denote 4 allowed placement options. Specifically, q5 = 0, q6 = 0, q7 = 0, or q8 = 0 indicates that Module2 is placed at the left, bottom, right, or top side from Module1 , respectively. Considering the rotation of Module1 , how do we model that Module1 and Module2 do not overlap with each other, with the aid of an extremely large constant M? Suppose that c1 is given. (5 constraints: c6 , c7 , c8 , c9 , and c10 ) [5] c6 : x2 + φd ≤ x1 + q5 M;

Copyright WS2017/2018- EDA

c7 : y2 + φd ≤ y1 + q6 M; c8 : x1 + (φ3 + φ4 )(q1 + q3 ) + (φ1 + φ2 )(q2 + q4 ) ≤ x2 + q7 M; c9 : y1 + (φ1 + φ2 )(q1 + q3 ) + (φ3 + φ4 )(q2 + q4 ) ≤ y2 + q8 M; c10 : q5 + q6 + q7 + q8 = 3

EDA WS2017/2018

2 15

Problem 9: Heat Dissipation [16] The following left figure shows a chip containing 25 regions denoted by Rk, k ∈ N, 1 ≤ k ≤ 25. R1, R5, R21, R25 are called corner regions, R2, R3, R4, R6, R10, R11, R15, R16, R20, R22, R23, and R24 are called side regions, and all other regions are called center regions. A corner region has 3 neighbors, a side region has 5 neighbors, and a center region has 8 neighbors. 3 examples are shown in the right figures for R1, R6, and R7.

Copyright WS2017/2018- EDA

Ri

Rj ⇔ Rj is a neighbor to Ri

R1

R6

R11

R16

R21

R1

R6

R1

R6 R11

R2

R7

R12

R17

R22

R2

R7

R2

R7 R12

R3

R8

R13

R18

R23

R4

R9

R14

R19

R24

R5

R10

R15

R20

R25

R1

R6 R11

R2

R7 R12

R3

R8 R13

Suppose that on the chip, there is a kind of components named ”heater”. A heater generates considerable heat, and at most one heater can be put into a region. We introduce a binary variable bk for each Rk: if bk = 1, Rk contains a heater, Otherwise, Rk contains no heater. Suppose that the temperature measured at each Rk is given by a function tempk (ik ), where ik is an integer variable representing the number of heaters contained in Rk plus the number of heaters contained in all neighbors of Rk. The value of tempk (ik ) is represented by a continuous variable tk . Use only given variables to solve the subproblems. a) ⋆ Model i5 by appropriately using some bk . (1 constraint: c1 ) [1] c1 : i5 = b4 + b5 + b9 + b10

b) ⋆ Given that b3 , b9 , b17 , b21 , and b23 must be 0. What is the upper bound of i16 ? [1] 4

EDA WS2017/2018

8 16

c) ⋆ Suppose that R7 and R19 have a special relation: “if i7 ≥ 3, i19 ≥ 4” (Situation 1); and “if i7 ≤ 2, i19 ≤ 3” (Situation 2). Model this relation with an extremely large constant M and 2 auxiliary binary variables q1 and q2 : use q1 = 0 to indicate the occurence of Situation 1, and use q2 = 0 to indicate the occurence of Situation 2. Suppose q1 + q2 = 1 is given. (4 constraints: c2 , c3 , c4 , and c5 ) [4] c 2 : i 7 ≥ 3 − q1 M c3 : i19 ≥ 4 − q1 M c 4 : i 7 ≤ 2 + q2 M

Copyright WS2017/2018- EDA

c5 : i19 ≤ 3 + q2 M d) Model the relation between R7 and R19 again. This time use q1 only (without using q2 ) and replace M by minimum constant values. (4 constraints: c6 , c7 , c8 , and c9 ) [4] c6 : i7 ...