Coverage-driven Random Test Generation for Coarse-Grained Reconfigurable Architectures

학위논문 (석사)-- 서울대학교 대학원 : 컴퓨터공학부, 2016. 2. Bernhard Egger.As the complexity of hardware designs keeps increasing, functional verification of microprocessor systems has become one of the main bottlenecks in the hardware development processes. Conventional verification methods are difficult to apply to coarse-grained reconfigurable architectures (CGRA) due to their high complexity and complicated requirements on the generated code. This thesis proposes a coverage-driven verification method for CGRAs to test functionalities through randomly generated test programs. The proposed verification is performed by a comparison with simulation results, and is thus suitable for pre- and post-silicon verification. Our random test program generator (RTPG) builds a graph model of the architecture directly from the CGRA's textual description and produces executable random test programs. The proposed RTPG adopts a guided place and routing algorithm to map operations and operands onto the heterogeneous functional units. To achieve maximum coverage, we employ a routing algorithm with various fitness functions and a heuristic approach for operation scheduling. The RTPG supports custom ISA extensions seamlessly without explicit knowledge about the semantics of operations. Experiments demonstrate that the proposed RTPG is versatile in generating test programs by diverse test templates and quickly achieves a high coverage of the architecture's functionalities. We test the effectiveness of the method on a commercial CGRA, the Samsung Reconfigurable Processor. In a real world evaluation, the generated test programs were able to detect all randomly inserted faults as well as several yet unknown faults in the CGRA architecture.Chapter 1 Introduction 1 Chapter 2 Related Work 6 Chapter 3 Coarse-Grained Reconfigurable Architectures 9 3.1 Target Architecture 9 3.2 Hardware Model 13 3.3 Fault Model 14 3.4 Coverage Metrics 16 Chapter 4 Random Test Program Generator 18 4.1 Test Generation Engine 20 4.2 Routing Algorithm 22 4.3 Data Type Specification 25 4.4 Predicate Network 26 4.5 Test Template Language 27 4.6 Stuck-at fault testing 30 Chapter 5 Coverage-driven Analysis 31 5.1 Available Coverage Analysis 31 5.1.1 Getting available coverage 32 5.2 Improvement of Coverage Rate 34 5.2.1 Instruction Selection Strategy 34 5.2.2 Directed Test Program Generation 35 Chapter 6 Verification Framework 38 6.1 Pre-silicon verification 38 6.2 Post-silicon verification 39 6.3 Operation of Verification framework 39 Chapter 7 Experiments 41 7.1 Coverage of Test Programs 42 7.2 Improvement of Coverage Rate 44 7.2.1 Instruction Selection Strategy 44 7.3 Directed test program generation 46 7.4 Fault Coverage 48 7.5 Discussion 49 Chapter 8 Conclusion 51 Bibliography 52 요약 58Maste