A New Framework For Automatic Generation, Insertion and Verification of Memory Built-In Sel

A New Framework For Automatic Generation, Insertion and Veri cation of Memory Built-In Self Test Units
Kamran Zarrineh Test Design Automation IBM Corp. Endicott, NY 13760
The design and architecture of a memory test synthesis framework for automatic generation, insertion and veri cation of memory BIST units is presented. We use a building block architecture which results in full customization of memory BIST units. The exibility and e ciency of the framework are demonstrated by showing that memory BIST units with di erent architecture and characteristics could be generated, functionally veri ed and inserted in a short time. Custom memory test algorithms could be loaded in the supported programmable BIST unit and therefore any type of memory test algorithm could be realized.

Shambhu J. Upadhyaya Dept. of Computer Science and Engineering SUNY at Bu alo Bu alo, NY 14260
ries of modi cations and enhancements. This is time consuming and increases the design time-to-market. A framework for automatic generation and insertion of memory BIST units would facilitate the task of memory testing and improves the time-to-market. The available memory BIST generation/insertion frameworks can only realize a few supported memory test algorithms. This in exibility might translate into higher test logic overhead and/or insu cient memory tests for some memories. A class of these frameworks have a prede ned high level description of a set of memory BIST architectures and based on the memory bitwidth, address space depth, etc., the memory BIST unit is customized. This method has a very limited scope and cannot accommodate testing requirements of di erent types of memories. Another class of memory BIST generation/insertion frameworks requires speci c high level/logic synthesis frameworks for memory BIST generation and insertion. This type of architecture limits the usability of the memory BIST generation/insertion framework. The support for custom isolation logic is another shortcoming of the existing frameworks. An automatic approach and support for functional veri cation of the generated/inserted memory BIST units is not always provided by memory BIST generation/insertion frameworks. In this paper, we propose a memory test synthesis framework to automatically generate/insert memory BIST controllers that are capable of realizing any type of memory test algorithms. To fully reduce the test logic overhead, the proposed memory test synthesis framework provides di erent architectures and designs of the memory BIST components and allows the user to select the most suitable component as well as eliminating one or many of these components from the memory BIST unit. Our proposed framework also provides support for functional veri cation of the generated memory BIST unit. To ensure technology and framework independence, we use behavioral VHDL that can be compiled and veri ed by any high level/logic synthe-


1 Introduction

Digital systems are composed of data paths, control paths and memories. The low cost of memory and high memory demand of high-speed DSP circuits and general microprocessors have made the memory subsystem an important focus of today's designs. Defects in memories are due to shorts and opens in memory cells, address decoder and read/write logic. Memories are more likely to fail than random logic, therefore, they should be tested e ectively. The most popular and widely accepted deterministic test algorithm is the march test. A march test is a nite sequence of march elements applied to each memory cell in the memory in either ascending or descending order before proceeding to the next memory cell 1]. Application of memory test sequences to embedded memories using o -chip testers results in a high test time and test cost due to large size of memories. To overcome this problem, the computed test sequences are generated on-chip using a memory Built-In Self Test (BIST) unit. The architecture of a memory BIST unit depends on the characteristics of the memory-under-test, test algorithm and the overall test strategy of the design. Therefore, memory BIST units could not be re-used from one design to the next unless they undergo a se-

sis as well as simulation frameworks. A set of isolation logic is also created/inserted, if necessary, and then the necessary interconnections between memory BIST unit, functional logic, isolation logic and memory(s)-undertest are made. To accommodate di erent test strategies and diagnostics capabilities, the custom isolation logic could be generated and inserted. The correct function of the isolation logic and the interconnections of di erent isolation logic are also veri ed. The proposed memory BIST architectures are described in Section 2. In Section 3, we describe the details of the proposed memory test synthesis framework. Experimental results are presented in Section 4 and Section 5 concludes the paper. A memory BIST unit consists of a set of structurally independent modules which provide a function for the memory BIST unit. Each module communicates its status through a set of control signals with other modules in the memory BIST unit. The details and capabilities of each memory BIST module depends on the characteristics of the memory-under-test as well as the memory test methodology. The memory BIST unit could be built such that same type of modules with di erent capabilities have similar interface and therefore a module with less function could be replaced with a module with more capabilities without a ecting the overall memory BIST architecture. If the function of a module is not required, that module could be eliminated and its output control signals are tied to their inactive logic value without a ecting the overall function of the memory BIST unit. This memory BIST architecture is called building block architecture and is used in the design of the proposed memory test synthesis framework for automatic generation of memory BIST units. The memory BIST control module asserts and deasserts a set of controlling signals for the memory and other modules of the memory BIST unit based on a selected memory test algorithm and test strategy. A memory BIST controller could be designed as a programmable or a non-programmable controller designed as a microcode-based or Finite State Machine based controller. An e cient programmable memory BIST architecture is presented in 2] and is supported by our proposed framework. This programmable memory BIST architecture has lower logic overhead and is more exible than the methods described in 3, 4, 5]. The presented programmable memory BIST architecture could be used to support memories in di erent stages of their fabrication and therefore results in lower overall logic overhead than conventional memory BIST




Set the necessary paths

Extract the characteristics of the memory-under-test

Memory BIST Module library

Generate an RTL description

Insertion Framework

of a memory BIST unit

Memory BIST
RTL library

2 Proposed Memory BIST Architectures

Verification Framework

Verification VHDL file

Timing File

Figure 1: High Level Flow of Memory Test Synthesis architectures. In addition, our proposed framework supports the generation of the BIST controller's storage module, where the microcode instructions are loaded, using either master/slave ip ops or scan-only registers. In this paper, these architectures are referred to as prgm1 and prgm2 respectively. A set of non-programmable FSM-based controllers which are the logic realizations of March C and March A 6] and their deviations is designed and supported by our proposed memory test synthesis framework. Deviations of March C and A have the added capability to detect read destructive and data retention faults. These algorithms are referred to as March C + , March C ++ , March A+ and March A++ . In March C + (March A+ ) each read operation is replaced by three read operations to excite defects due to disconnected pull-up/down devices in the memory cells. In march C ++ (March A++ ), two march test components Delay *(rd wd rd ) Delay * (rd ) are added to the end of the March C (March A) algorithm to allow detection of data retention faults. In order to facilitate the task of memory BIST generation/insertion and improve the time-to-market for designs, an automatic memory BIST generation/insertion and veri cation framework has been developed. The methodology ow of our proposed memory test synthesis could be described as follows: The user has to provide a set of environment variables (paths) to the framework through our memory test synthesis (.mts) le. The characteristics of the memory-under-test and any requirements on the memory BIST unit are described in the Memory BIST Description Language

3 Memory Test Synthesis

(MBDL). The memory BIST generation framework creates an RTL description of a memory BIST unit and stores it in the memory BIST library. A timing le contains the timing requirements on the I/Os of the modules in the memory BIST unit. This information is used by the timing correction process of the selected logic synthesis framework. A VHDL testbench le is also generated and used for functional veri cation of the generated memory BIST design. The insertion framework loads the design entity containing the memory-under-test and the appropriate memory BIST unit. The speci ed isolation logic is added to the design and the memory BIST unit is connected to the ports of the memory-under-test. Once the memory BIST unit is inserted, the veri cation framework veri es the correct function of the isolation logic and the interconnection of the test and functional modules in the design. A high level ow of the memory test synthesis is shown in Fig. 1. In the next subsections the generation, insertion and veri cation frameworks are described in more detail. The developed building block memory BIST architecture is the foundation for the design of the proposed memory BIST generation framework. Di erent implementations of the memory BIST controllers, address generation, data background generation, response analyzer, read/write control, port selection and memory selection modules are described in synthesizable parameterized VHDL les. These les are compiled and stored in the memory BIST module library. The testing requirements and the characteristics of the memoryunder-test are described in the MBDL le. The rst statement in the MBDL is the speci cation of the VHDL entity and architecture name of the memory BIST unit. This allows generation and insertion of multiple memory BIST units in one design entity. The architecture of memory BIST controllers, microcodebased and FSM-based, is speci ed in the MBDL le. The option N/A for any memory BIST module excludes that module from the generation and insertion process. Memory BIST generation framework assumes that the excluded module is residing external to the memory BIST unit and therefore for each control signal of the excluded module an additional port is added to the generated memory BIST unit and connected to other corresponding memory BIST modules. For programmable memory BIST controllers, the dimensions of their storage unit should be speci ed in the MBDL. Similarly for the FSM-based controller, one of the six supported memory test algorithms should be selected. The memory could be bit-oriented or word-oriented while the type of the address generation module could be binary, LFSR or maximum transition counter 7]. Further-

3.1 Memory BIST Generation Framework

more, the bitwidth, address space depth and in the case of multiport memories the number of read-write pair of ports are speci ed. Three scenarios could arise for design entities with multiple memories: 1) one memory BIST for each memory, 2) one memory BIST testing all memories simultaneously and 3) one memory BIST testing all memories in a series. For high bitwidth memories using shared memory BIST methodology, MBDL allows speci cation of dedicated memory BIST components wherever possible or sharing each module among all memories in the cluster. Depending on the physical location of the memories, this option could result in substantial saving in wiring or area overhead. The desired clock rate of the memory BIST unit should be also speci ed in the MBDL. The clock rate is used to assert timing constraints on the I/Os of the generated memory BIST unit and for functional veri cation. The proposed memory BIST generation framework extracts the necessary information in the MBDL le and generates a top shell VHDL le for the memory BIST unit. The generated top level VHDL is rst compiled and then passed to a high level synthesis framework for generation of RTL design. The generated RTL is saved in a library for future reference. The memory BIST insertion framework requires the name of the design entity that contains the memory(s)under-test, the name of the memory(s)-under-test themselves and the name of the isolation logic for each group of ports of the memory(s)-under-test. An extension to the MBDL grammar is necessary to allow the speci cation of this information. The memory BIST insertion framework loads the speci ed design entity and the generated memory BIST unit. Then, an instance of the generated memory BIST unit is created in the design entity. The insertion framework supports a set of RTL primitives. If necessary, custom isolation logic could be described in structural VHDL using the supported primitives. The insertion framework groups the ports of the memory-under-test into: data input, address, data output and read/write clocks. An identi cation sub-pattern in the name of these ports is speci ed by the user in the .mts le. The insertion framework searches in the name of each port for the speci ed sub-patterns and classi es the port in the appropriate category. This capability ensures that our proposed memory test synthesis framework is independent of high level/logic synthesis tools. A custom isolation logic could be speci ed for each class of the memory ports. This information could be speci ed in the extended MBDL le. The isolation cell name N/A speci es that no isolation should be generated and inserted for the speci ed port type, however,

3.2 Memory BIST Insertion Framework

if not speci ed the default (2:1 multiplexer) isolation logic is used. Based on the type of the ports of the memory-under-test, memory BIST unit and the isolation logic ports, the necessary connections are made. The pseudo code of the insertion algorithm is shown in Fig. 2.
Memory BIST Insertion () {
for every specified design entity { for every MemoryBIST=load_generated_memory_BIST() { MemoryDesign = Determine the specified memories(memory_list); for every memory in MemoryDesign { for every pin in memory { find_its_memory_BIST_corresponding_pin(pin) if (insert_isolation_logic) { insert the selected isolation logic(); } make the necessary connections(); } } } }

implementation of the isolation logic and the interconnections of the memory BIST unit to the memory and other external test control I/Os. We call the rst veri cation approach functional veri cation and the second structural veri cation. A hybrid method consisting of both functional and structural veri cation could be designed to verify the existence and correct functioning of a given diagnostics algorithm in the memory BIST unit. We have used some of the characteristics of the symbolic trajectory evaluation approach to create a functional veri cation method that ts well with our memory test synthesis ow. In our approach, the function of the memory BIST unit is divided into: reset state, test algorithm state, end state, fail state and terminate state. Successful veri cation of these states ensures the correct functioning of the memory BIST unit. A VHDL package le has been developed to support the generated VHDL testbench le. To verify the reset state, the memory BIST unit is pushed into the reset state and the values of the memory BIST unit are checked. The speci ed memory test algorithm is described in the veri cation parameter le (VPF) similar to the grammar of march test representation described in 6]. The memory test algorithm is divided into a set of march test components. The veri cation of the march test algorithm is decomposed to the veri cation of each march test component. A march test component consist of an address order, one or more read and/or write test data pattern (test data pattern) operations. Veri cation of the address generation module is to prove that the module is a monotonically increasing/decreasing function or proving that the actual address maps to the expected address value for a given clock cycle. The polarity of the test data signal for a given clock cycle is extracted from the test algorithm description. For word-oriented memories the value of the required set of data background patterns are also speci ed in the VPF. The correct data background patterns are loaded based on the bitwidth of the memoryunder-test. The loaded data background pattern is the expected value and based on the test data polarity, its true or complement value is compared with the actual test data. Veri cation of the read/write enable signals is to prove that the actual value of the test read/write enable signals maps to the expected value of these signals computed from the memory test algorithm. Each march test component consists of one or more operations that are repeated for each address. The functional veri cation run time might become high for memory BIST units that support serial shared, multiport, high bitwidth word-oriented memories with very

3.3.1 Functional Veri cation Framework


Figure 2: Pseudo Code of the Insertion Framework Di erent formal veri cation approaches have been proposed to ensure correctness of a digital logic design 8]. In theorem proving method the relationship between speci cation and an implementation is regarded as a theorem in a logic. This theorem should be proved within the framework of proof calculus. The speci cation of a design is in the form of a logic formula in the model checking veri cation approach. The truth of this logic formula is determined with respect to a semantic model provided by an implementation. In equivalence checking veri cation approach, the equivalence of a speci cation and an implementation is checked. The language containment shows that the language representing an implementation is contained in the language representing a speci cation. In symbolic trajectory evaluation the properties of a system are speci ed as assertions about circuit state in the form of pre and post-conditions and veri ed using symbolic simulation. This method has been successfully used for veri cation of PowerPC memories 9]. Robust test methodology is a structured and orthogonal array based functional vector generation method. This method works both for input-dependent output values and state dependent output values as long as the relationships are well dened 10]. Veri cation of the generated/inserted memory BIST unit could be divided into veri cation of the correctness of 1) functioning of the memory BIST unit and 2)

3.3 Memory BIST Veri cation Framework

deep address space. To ensure that our method is scalable and is applicable to all memory BIST units generated by our proposed framework, the functional veri cation method uses a uniform random variable to check the state of the memory BIST unit for m unique sampling points. Sampling the entire address space is achieved by setting m=fentire address spaceg and is a subset of the described method. To check the end state, at the end of the test algorithm state, the control signals of the memory BIST unit to other external test controllers are sampled after several clock cycles. The memory BIST unit is restarted and at the clock cycle that the rst read operation would occur the inputs to the response analyzer is mismatched with the test data compare signals. Prior to the time of the next read operation the mismatched signals are set back to the correct values. The number of clock cycles from the rst read operation and the time the fail bit of the memory BIST unit is set, is counted and compared with the expected number of clock cycles speci ed in VPF. This ensures the correct operation of the response analyzer and the correct number of pipeline delays. To verify the terminate state the memory BIST unit is reset and started for a random number of cycles and then suddenly the terminate signal is asserted. This condition should force the memory BIST unit into its terminate state. A high level overview of the functional veri cation model is shown in Fig. 3.
VHDL testbench VHDL Simulation Package File Memory BIST RTL

from the I/Os to the memory BIST unit. A theorem proving method is used to verify that the isolation logic is a perfect mutually exclusive function. The structural veri cation framework would place stuck-at 0/1 on the output of the isolation logic, tie the control signal to select the functional path and then try to test the stuckat faults using the memory test input. This operation is also performed for the functional path and repeated for all cells in the isolation logic. The proposed memory test synthesis framework has been designed and implemented. The memory BIST generation framework is implemented using UNIX shell script, sed/awk and synthesizable VHDL languages. The memory BIST insertion framework uses C/C++ programming languages and an internal command language called Bscript. The memory BIST veri cation framework uses UNIX script, sed/awk command languages and VHDL simulation languages. To quantify the productivity gains of using the proposed framework, we generated, inserted and veri ed memory BIST units for a set of memory(s)-undertest in both not-sharing and serial sharing con gurations. The memory(s)-under-test is assumed to be word-oriented with bitwidth of 8, address depth of 1K and three read/write pair of ports. Three identical memories per cluster are used for serial con guration. All experiments were run on a PowerPC 250 workstation with AIX 4.1 operating system and VHDL Analyzer (CLSI) for VHDL compilation, HIS for High Level Synthesis, Model Technology Inc. for VHDL testbench simulation and TestBench for automatic test pattern generation were used. The time (seconds) to generate and insert di erent architectures of memory BIST units for not-shared and shared memory con gurations are summarized in Table 1. The rst column speci es the name of the memory BIST architecture, the second through fth columns specify the memory BIST generation and insertion time (seconds) for not shared and serial shared con gurations respectively. The memory BIST generation time is the time to generate an RT-level memory BIST unit. The insertion time includes the time to insert the memory BIST unit, generate and insert default isolation logic (2:1 multiplexers). Experimental results show that the longest time for generation and insertion of memory BIST units is 26 and 120 seconds respectively. Performing these tasks manually would take an experienced Design for Test designer days. March C is used for functional veri cation of programmable memory BIST architectures. The entire address space of the memory BIST unit is sampled in the functional veri cation process. The time to generate

4 Experimental Results


Verification File

VHDL Functional Simulation


Figure 3: Flow of Functional Veri cation Framework

3.3.2 Structural Veri cation Framework

A simulationbased method is used to ensure that the memory BIST unit could be accessed from the speci ed I/Os. Therefore, both 0/1 logic values are propagated


Table 1: Generation & Insertion Time (sec)
Not Shared Generate Insert
25.9 23.0 21.8 22.5 22.9 21.7 22.4 22.8 98.4 97.9 100.3 102.1 88.9 93.8 96.0 110.3 25.5 21.8 24.3 25.2 25.9 23.8 24.9 25.3

Prgm1 Prgm2

Shared Generate Insert
119.6 115.7 116.1 111.5 114.2 96.5 99.1 102.8

C + March C ++ March C March A + March A ++ March A

the VHDL testbench les and the time to run VHDL simulation framework (MTI) are summarized in Table 2. The rst column speci es the name of the memory BIST architecture. The second through fth column shows the time (seconds) to generate the VHDL testbench le and the VHDL simulation of the memory BIST units assuming not shared and shared con gurations respectively. The longest time to automatically generate a VHDL testbench le was 6.3 seconds while the manual generation of this le might take hours. The experimental results show that the VHDL simulation time increases as the architecture of the memory BIST becomes more complex. Our functional veri cation framework could reduce the number of sampling addresses and maintain the simulation time within acceptable level. Considering the repetitiveness nature of the march test algorithms and since unique addresses are selected, good veri cation coverage is achieved.

that exists in the architecture of the memory BIST unit and select the optimal architecture. The supported programmable memory BIST architecture allows realization of any custom march test. The area overhead of the supported programmable memory BIST unit is comparable with other conventional FSM-based memory BIST units. Di erent design and implementations of the same type of memory BIST modules could also be used. This enhances the capability of the memory BIST unit to accommodate memories with di erent characteristics and test requirements. The proposed memory test synthesis allows using custom as well as a set of default isolation logic. This enables the memory BIST to exploit existing memory BIST Design for Test (DfT) logic and extends the scope of the framework. The experimental results demonstrated that any style of memory BIST could be generated, inserted and veri ed in seconds and minutes compare to days and weeks if done manually and therefore huge reduction in time-to-market for designs could be achieved. The functional veri cation framework is scalable to accommodate large and complex memory BIST units. The proposed veri cation framework could be extended to accommodate memory test algorithms with di erent structures and characteristics than march tests.

References 1] M. Marinescu.
2] 3] 4] 5] 6] 7]

Table 2: Functional Veri cation Time (sec)
Not Shared Generate Simulate
6.2 5.9 4.9 5.1 5.1 4.9 5.0 5.0 116.0 111.3 109.3 224.9 182.4 166.1 250.3 224.5 6.3 6.1 5.2 5.2 5.1 5.3 5.2 5.2

Prgm1 Prgm2

Shared Generate Simulate
360.2 347.8 347.2 652.6 524.1 490.7 728.4 669.6

C C+ ++ March C March A + March A ++ March A
March March

In addition, TestBench automatically drops the faults residing on inactive paths as a part of its fault list building process and therefore has negligible overhead for the design used in these experiments. In this paper the design and architecture of a memory test synthesis framework to generate, insert and verify the correct functioning of memory BIST units were presented. By using a building block architecture full customization of memory BIST units was achieved. This degree of customization would allow the memory test engineers to fully exploit any degree of freedom

5 Conclusion

8] 9] 10]

Simple and e cient algorithms for functional RAM testing. In Proc. Int. Test Conf., pages 572{576, 1982. K. Zarrineh and S. J. Upadhyaya. On Programmable Memory Built-In Self Test Architectures. To appear in Design Automation and Test in Europe, March 1999. H. Koike, T. Takeshima, and M. Takada. A BIST Scheme Using Microprogram ROM for Large Capacity Memories. Proc. Int. Test Conf., pages 815{822, 1990. P. G. Shephard III, W. V. Huott, P. R. Turgeon, R. W. Berry Jr., G. Yasar, F. J. Cox, P. Patel, and J. B. Hanley III. Programmable built-in self test method and controller for arrays. U. S. Patent No. 5,633,877, May 1997. I. Schanstra, D. Lukita, A.J. van de Goor, K. Veelenturf, and P. J. van Wijnen. Semiconductor Manufacturing Process Monitoring Using BIST for Embedded Memories. In Proc. Int. Test Conf., pages 872{881, 1998. A.J. van de Goor. Testing Semiconductor Memories: Theory and Practice. John Wiley and Sons, U.S.A, 1991. B. F. Cockburn and D. P. Sarda. A Synthesizable RAM BIST Circuit for Applying an O(n.log2 (n)) Test that Detects Scrambled Static Pattern Sensitive Faults. In Records of the IEEE Int. Workshop on Memory Technology, Design and Testing, pages 57{63, 1996. J. Abraham and P. Bose. Microprocessor Testing: Performance and Functional Validation. In Int. Test Conference Tutorial, pages 23{29, 1998. M. Pandey, R. Raimi, D. L. Beatty, and R. E. Bryant. Formal veri cation of powerpc arrays using symbolic trajectory evaluation. In Proc. Design Automation Conf., pages 649{654, 1997. S. Stoica. Functional design veri cation process and methods. In Int. Test Conference Tutorial, pages 40{45, 1998.


ABSTRACT A Utility Framework for the Automatic Generation of Audio-Visual Skims
An experiment in automatic generation of test suites for protocols with verification techno
A Framework for Coarse-Grain Optimizations in the On-Chip Memory Hierarchy
PWB Warpage Analysis and Verification using an AP210 Standards-Based Engineering Framework and Shado
A compilation framework for distributed memory parallelization of data mining algorithms
Simulation Framework for Training Chest Tube Insertion Using Virtual Reality and Force Feed
Correct code-generation in a generic framework
Sequential Circuit Test Generation in a Genetic Algorithm Framework
Dynamic memory management for the Loci framework