Chulalongkorn University Theses and Dissertations (Chula ETD)

การทวนสอบวงจรอสมวารแบบควอไซดีเลย์อินเซนซิทีฟโดยซิกแนลทรานสิชันกราฟ

Other Title (Parallel Title in Other Language of ETD)

Verification of quasi-delay-insensitive asynchronous circuits by the signal transition graph

Year (A.D.)

1999

Document Type

Thesis

First Advisor

อาทิตย์ ทองทักษ์

Faculty/College

Graduate School (บัณฑิตวิทยาลัย)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.1999.1222

Abstract

การทวนสอบวงจรเป็นกระบวนการที่ใช้ตรวจสอบความถูกต้องตรงกันระหว่างคุณลักษณะของวงจรที่ได้ออกแบบไว้กับวงจรที่ได้จากการสังเคราะห์ วิทยานิพนธ์ฉบับนี้นำเสนอการออกแบบและพัฒนาขั้นตอนวิธีการทวนสอบวงจรอสมวารแบบควอไซดีเลย์อินเซนซิทีฟเชิงลำดับชั้นโดยใช้วิธีการจำลองเชิงเหตุการณ์ ขั้นตอนวิธีการทวนสอบวงจรแบ่งเป็นสองขั้น ได้แก่ ขั้นที่หนึ่งทำการทวนสอบแต่ละวงจรย่อย และขั้นที่สองทำการทวนสอบทั้งวงจรโดยจะพิจารณาเฉพาะสัญญาณเชื่อมต่อของแต่ละวงจรย่อย ในแต่ละขั้นของการทวนสอบจะใช้วิธีการจำลองเชิงเหตุการณ์ด้วยภาษา Verilog กับเวกเตอร์ทดสอบที่สร้างขึ้นมา การสร้างเวกเตอร์ทดสอบจะได้มาจากวิเคราะห์ซิกแนลทรานสิชันกราฟโดยใช้เทคนิคต่างๆ ร่วมกัน ได้แก่ เทคนิคการคอนแทรคซิกแนลทรานสิชันกราฟ แนวความคิดการวิเคราะห์คุณสมบัติ concurrent temporal relation ของการเปลี่ยนแปลงสัญญาณในซิกแนลทรานสิชันกราฟสำหรับวงจรที่มีการทำงานแบบอินพุต-เอาต์พุต และเทคนิคการทดสอบเส้นทางพื้นฐาน นอกจากนี้ยังประยุกต์ใช้เทคนิคการประเมินความเชื่อถือได้ด้านเวลาของวงจรอสมวารเพื่อตรวจสอบความถูกต้องในการทำงานของวงจรที่มีโมเดลความหน่วงแบบควอไซดีเลย์อินเซนซิทีฟด้วย ขั้นตอนวิธีการทวนสอบวงจรอสมการที่ได้นำเสนอในงานวิจัยฉบับนี้ เป็นวิธีการทวนสอบอย่างกึ่งแบบแผนแบบ smart simulation นับเป็นวิธีการทวนสอบที่ได้นำเสนอเพื่อแก้ไขข้อจำกัดของวิธีการทวนสอบแบบเดิม ซึ่งจากผลการทดลองในการสร้างเวกเตอร์ทดสอบเพื่อทำการทวนสอบขั้นที่หนึ่งกับเกณฑ์เปรียบเทียบสมรรถนะแสดงให้เห็นว่าเมื่อนำตัววัดทางซอฟต์แวร์ ได้แก่ ค่าความซับซ้อนไซโคลเมติกมาใช้เป็นแนวทางกำหนดจำนวนเวกเตอร์ทดสอบจะสามารถลดจำนวนเวกเตอร์ทดสอบได้เท่ากับ 21.08% จากจำนวนเวกเตอร์ทดสอบที่เป็นไปได้ทั้งหมด และสามารถลดจำนวนเวกเตอร์ทดสอบได้เท่ากับ 87.81% เมื่อเทียบกับวิธีการทวนสอบแบบทั้งวงจร นอกจากนี้ขั้นตอนวิธีการทวนสอบเชิงลำดับชั้นยังมีข้อดีอื่นๆ อีก ได้แก่ ช่วยลดความซับซ้อนในการทวนสอบทั้งวงจร สามารถตรวจพบความผิดพลาดได้รวดเร็วโดยไม่จำเป็นต้องทำการทวนสอบทั้งวงจรเสร็จสิ้น และสามารถนำผลการทวนสอบมาใช้กับวงจรย่อยที่มีโครงสร้างเหมือนกันได้อีก

Other Abstract (Other language abstract of ETD)

The circuit verification is a process to assure the correctness between the implemented circuit and its specification. This thesis proposes a design and development of the hierarchical verification process for Quasi-Delay-Insensitive (QDI) asynchronous circuits based on event-driven simulation. The complete verification process has two levels. First, we will verify each sub-circuit, with respect to its specification and then we will verify the whole circuit by considering only interconnected signals between sub-circuits. In each level of verification, we apply the test vector with event-driven simulation developed by Verilog in order to verify the asynchronicity of the circuit. The test vector is derived from the analysis of the Signal Transition Graph (STG) using various techniques including STG contraction, analysis of the concurrent temporal relation on STG based on input-output mode circuit's operation, and basis path testing. Moreover, we apply the timing-reliability evaluation of asynchronous circuittechnique to verify correctness of the QDI circuit's operation. Our approach is the smart simulation which is arranged in a semi-formal method. It can avoid the limitations of traditional verification methods. Experimemting with a set of benchmark circuits, the proposed approach shows high performance when measured by software metric i.e. cyclomatic complexity, which determines the number of test vectors. The results show a 21.08% reduction in numbers of all test vectors required for the first level of verification and an 87.81% reduction in numbers of all test vectors from the flat verification. In addition, our approach can also be carried out in a hierarchical structure. It also has other advantages such as reducing the complexity which is found in the whole circuit verification method, and quickly finding problems in the preliminary level without finish examining the whole circuit. Lastly, the verification results can be applied to similar sub-circuits without repeating the verification process

Link to Full Text

Share

COinS