非同步电路设计

1、非同步電路設計 期末考參考答案1. (4%)Draw a 3-stages 4-phase dual-rail 2-bit data path.(5-4)2. (3%)Design a 4-phase bundled-data demultiplexer.(5-7)3. (5%)Design a 4-phase bundled-data Merge with inputs x and y. What is the inputs assumption? Why? Assume input x is active, explain that there is a glitch in the C-e

2、lement of y-ack.(5-9)(1)COMPONENT4-phase bundled datayzxyzxy-reqx-reqy-ackz-ackx-acky-reqz-reqx-reqCCMerge(wait for one)(2) Mutually exclusive inputs(3) 如果input不互斥，在x-req active之後，z-req傳至下級，在下級使z-ack active之後，如果y-req也active了，則除了x-ack外，y-ack也會active，但input y的data卻是還沒傳到下一級，電路動作發生錯誤。4. (4%)Draw an asym

3、metric C-element and design it in transistor level. Explain its application.(5-10)如果能確定電路動作中，b¯一定在a¯之前，則b¯的輸入可以省略，所以可以節省一個transistor，增快電路速度。5. (5%)Design a bundled-data arbitrating Merge.(5-14)6. (3%)Draw a 2-input OR in dual-rail PLA notation.(5-25)7. (8%)Design adders without/with G

4、enerate and Kill in dual-rail PLA notation and compare them in speed.(5-26)ADDabcsda.ta.fb.fb.tc.fc.ts.ts.fd.fd.tCCCCCCCCa.ta.fb.fb.tc.fc.ts.ts.fd.fd.tCCCCCCCCCCGENKILL左邊是沒有Generate與Kill的電路，右邊是有Generate與Kill的電路，在ripple carry adder中速度的瓶頸在於carry的傳遞，現在如果有設計Generate與Kill的adder有機會可以在後面的carry還沒傳遞上來時便決定自身的

5、carry給下一級，所以速度較快。8. (3%)Explain Null Convention Logic.(pp 69)將電路動作的控制做在gate之中，如上圖的兩個gates，數字代表inputs中有多少個以上的input為active則output為active，而如果所有input為inactive則output為inactive，其他狀況則output不變，所以一個n-inputs的NCL gate如果數字為1則行為如同OR gate，如果數字為n則行為如同C-element。9. (6%)Assume a hybrid adder is an adder with bundled-

6、data inputs and dual-rail carries. Design two hybrid adder in weak indication and strong indication.(5-32)Sum：Carry：(1)weak indication(2) strong indication10. (4%)Explain fundamental mode and input/output mode.(6-3)(a) fundamental mode：必須在所有inputs、outputs以及internal nodes都是stable的狀態下，environment才能更改一

7、個input的值。(b) Input/output mode：只要input與output的值是stable狀態，environment就可以更改一個以上的input值，而不必在意內部是否處於stable狀態。11. (4%)Explain transport delay and inertial delay(pp 83)(a) transport delay：又稱為pure delay，單純的將訊號shift過去，不做任何變動。(b) inertial delay：較接近實際狀況的delay，只要時間不足，訊號的短期變化會被gate過濾掉。12. (4%)Explain Petri-net,

8、 STG, and SG.(6-5)(1) perti-net：petri-net是由directed arcs和兩種node：transitions、places組成，可用來建構或分析不同的系統(2) STG：STG是petri-net加上input free choice、1-bounded、liveness的限制，在省略了一些簡單的place(one arc in，one arc out)而成，另外還可以依需求的不同，加上consistent state assignment、persistency、complete state coding之類的限制。(3) SG：SG是將各狀態進行編

9、碼，形成SG內部的node，另外以directed arcs相連接，這些arc代表訊號的變化，因此SG遠比STG複雜，但在可以用在電路合成(synthesis)。13. (5%)Explain th hazard in f=ab + bc + ca. How to solve it?(6-13)在此電路如果三個AND gate之中有一個的速度特別慢，例如bc的AND gate特別慢，則在上面的signal transition中會因為bc的true太慢形成而導致c的訊號形成一個glitch。解決的方法可有：(1) 增加一個delay element：將hazard隱藏在delay之中。(2)

10、使用更複雜的電路：用完備的電路避免掉訊號轉換時的glitch。14. (6%)Draw Karnaugh maps to explain static-1 hazard and dynamic-10 hazard. (pp95)(1) static-1 hazard如果state依照12,13,15,14的順序來走，則state 14的output邏輯值應該維持在1，但實際上由於15的1是由d的值通過OR gate得來，而14的1是由b&c之後通過OR gate得來，當state由15轉成14，即d變為0，如果AND gate的速度太慢來不及接上，則output將會先轉成0，等AND

11、gate的值上來後才恢復成1，此為static-1 hazard。(2) dynamic-10 hazard會發生在4,6,2,0的state transition flow，在state 4會自然轉換到state 6，此時如果將b降為0會進入state 2，在自然轉換到state 0，output也應該由1變為0，但在state 6時會使得b&c的值為1，如果此gate太慢時會使得在state 2, 0之間原本降為0的output會有個1的pulse再回到0，此為dynamic-10 hazard。15. (4%)Draw two possible variable z states

12、 implementation templates using (simple) state holding elements.(pp 96)(1)使用S-R latch(2)使用C-element16. (7%)Assume variable zs set logic and reset logic is z-set = ab and z-reset=bc,respectively. Draw the circuit in gat-level, and show implementations in dynamic CMOS and static CMOS.(pp 100)(1) dynam

13、ic CMOS implementation(2) static CMOS implementation17. (6%)Explain the six characteristics of STG： 1-bounded, liveness, consistent state assignment, persistency, and complete state coding. (pp 88)(1) Input free choice: The selection among alternatives must only be controlled by mutually exclusive i

14、nputs.(2) 1-bounded: There must never be more than one token in a place.(3) Liveness: The STG must be free from deadlocks.(4) Consistent state assignment: The transitions of a signal must strictly alternate between _ and _ in any execution of the STG.(5) Persistency: If a signal transition is enable

15、d it must take place, i.e. it must not be disabled by another signal transition. The STG specification of the circuit must guarantee persistency of internal signals (state variables) and output signals, whereas it is up to the environment to guaranteepersistency of the input signals.(6) Complete sta

16、te coding (CSC): Two or more different markings of the STG must not have the same signal values (i.e. correspond to the same state). If this is not the case, it is necessary to introduce extra state variables such that different markings correspond to different states. The synthesis tool Petrify wil

17、l do this automatically.18. (12%)In the timing diagram, a and b are inputs and c and d are outputs. According to the diagram, draw its STG and SG, and then design c and d.(6-23)abcd(1) STGd+a-a+b+c-c+b-b+c+d-(2)SGRR00b+01R0c+0F10a+b+1R00110Rc-00F0b-d+11R1a-F110111Fd-c+(3)The Karnaugh map of cset(c)=

18、d+abreset(c)=borc=d+ab+bc000100011110cdab0R00xxRxx x1xF11x1110(4)The Karnaugh map of ddcbaabcdset(d)=abcreset(d)=cord=abc00011110cdab000100R0xx1xx xFx000x111019. (3%)What is the static type checking in asynchronous circuit? (pp 118)由於在不同data validity的元件連結時，可能取擷取到invalid的data而發生錯誤，所以在建構完電路後必須檢查連接處的da

19、ta validity的正確性，data validity有其強弱性，強的可以包容弱的，但強的不可傳給弱的。BROADEXTENDED EARLYEARLYLATEweakstrong20. (4%)Explain the semi-decoupled latch controller. (pp120)原本的latch必須在下一級的handshake完成之後才可latch住資料，而semi-decoupled latch controller則在Rout下降後即可latch住資料，所以Ain可獨立於Rout，使得latch可有更高的concurrent特性。21. (6%)說明課本圖6.13。

20、圖6.13分別描述了如果以圖6.12的電路來實現圖6.11的STG，則可能會產生static-1 hazard與dynamic-10 hazard：(a) static-1 hazard：如果state依照12,13,15,14的順序來走，則state 14的output邏輯值應該維持在1，但實際上由於15的1是由d的值通過OR gate得來，而14的1是由b&c之後通過OR gate得來，當state由15轉成14，即d變為0，如果AND gate的速度太慢來不及接上，則output將會先轉成0，等AND gate的值上來後才恢復成1，此為static-1 hazard。(b) dy

21、namic-10 hazard：會發生在4,6,2,0的state transition flow，在state 4會自然轉換到state 6，此時如果將b降為0會進入state 2，在自然轉換到state 0，output也應該由1變為0，但在state 6時會使得b&c的值為1，如果此gate太慢時會使得在state 2, 0之間原本降為0的output會有個1的pulse再回到0，此為dynamic-10 hazard。22. (6%)課本6.4節告訴我們，可以用state-holding gates方法，實做有關states的電路，請說明圖6.14的兩種做法。圖6.14提出了兩

22、種做法，一種是採用SR latch，另一種是使用c-element，在SR latch部分：當input滿足了set logic則此block的output為1，因此latch的output也被改為1，同樣滿足reset logic會使latch的output改為0，而其他的input並不會改變output值，使得state保留。在c-element部分，平時若input不滿足set logic也不滿足reset logic，則c-element接受的input是10，output值不變，當input滿足set logic會使得上面的block output為1，使的c-element的inp

23、ut為11，故output也變為1，同樣若是input滿足reset logic，會使下面block output為1，經inverter之後輸入c-element為0，因此c-element的input為00，output轉為0。23. (10%)說明與STG有關的1-bounded、liveness、consistent state assignment、persistency、complete state coding。(a) 1-bounded：在任一個place或是arc上不會同時擁有兩個以上的token。(b) liveness：所有訊號transition會被再度觸發，沒有dea

24、dlocks。(c) consistent state assignment：訊號一定再+、-之間交替轉換，如req+之後一定會有req-，不能在接req+。(d) persistency：當訊號轉換因某個事件被觸發，則在訊號轉換完成之前此事件不能消失，如a*->b*，在b的轉換完成之前a不能有訊號轉換發生。(e) complete state coding：所有不同的state不能有相同的編碼，如果有此狀況發生則加入內部狀態變數來解決。24. (3%)說明Petrify environment。使用petrify時，是採用petrify的對STG的文字敘述，經由petrify這套軟體配

25、合上library，可以產生一個petrify的equation，也可以利用draw_astg來產生圖形化的STG，另外可以用write_sg產生state graph。25. (5%)說明講義第6-50頁為何是serial circuit。說明講義第6-73頁。此圖形在req+->ack+這個arc，因為ack+還另外需要ACK+的事件來觸發，而且此事件絕對在req+之後，因此前述的arc可以省略，同樣的道理可以省略掉ACK+與REQ-、ACK-與REQ+還有req-與ack-之間的arcs，化簡後的結果如下：由上圖可知，在接收到上一級的req訊號後，本級會直接先發REQ訊號給下一級，如此層層傳遞到最後一級，再由environment收到acknowledge之後，同樣層層傳遞至本級，本級才可回傳ack+給上一級，同樣