Functional test generation for the pLRU replacement mechanism of embedded cache memories

Wilson J. Pérez H., Ernesto Sánchez, Matteo Sonza Reorda, Alberto Tonda, Jaime Velasco-MedinaLatw 2011 · DOI

TL;DR

This paper presents a novel Software-Based Self-Testing (SBST) approach to generate functional tests for the pseudo-Least Recently Used (pLRU) cache replacement mechanism. By modeling the pLRU logic as a Finite State Machine (FSM), the authors devise a method to create compact test sequences that can detect faults without requiring hardware modifications, addressing a critical gap in cache testing methodologies.

What Problem Does This Paper Address?

Modern processors rely heavily on cache memories to bridge the performance gap between fast CPUs and slower main memory. While testing the memory array itself is relatively straightforward (e.g., using BIST circuits), testing the cache controller, particularly its replacement policy logic, is significantly more challenging due to limited accessibility. Existing hardware-based solutions often require design modifications. Software-Based Self-Testing (SBST) offers a promising alternative by leveraging the processor's instruction set to run tests without extra hardware. However, creating SBST programs that thoroughly exercise and observe the replacement logic, especially for complex policies like pLRU, is non-trivial. This paper tackles this challenge by proposing a systematic FSM-based approach to generate effective pLRU test sequences.

Methods

The core of the proposed method involves modeling the pLRU replacement mechanism as a Finite State Machine (FSM). Unlike previous FSM models that could lead to state explosion for larger caches, this approach uses the history bits inherent to the pLRU policy to define the FSM states. This significantly reduces the number of states and transitions, making the model manageable.

The process involves:

  1. FSM Modeling: Representing the pLRU logic as an FSM where states are derived from the history bit configurations and inputs are memory accesses (hits or misses).
  2. FSM Traversal Algorithm: Employing an algorithm to generate a sequence of memory accesses that guarantees all transitions in the FSM are traversed. This algorithm is based on the Chinese Postman Problem.
  3. Status Check Sequence: A crucial addition to the standard FSM traversal. This sequence is designed to specifically excite and observe the pLRU replacement behavior, including its susceptibility to "domino effects" (where a sequence of accesses might prevent a block from ever being evicted). This involves carefully crafted sequences of hits and misses to verify the expected eviction behavior.
  4. Test Program Generation: Converting the generated memory access sequences into executable C code for the target processor.

The key novelty lies in the FSM state representation tailored to pLRU's history bits and the inclusion of a specific "status check" sequence to address pLRU's unique fault behaviors.

Datasets

Not discussed in the paper. The evaluation uses a simulated Leon3 processor core with a custom pLRU implementation.

Key Insights and Ideas

  • pLRU's State Representation: Using the history bits of the pLRU policy as the basis for FSM states is a clever way to manage complexity and avoid state explosion, especially for caches with more ways.
  • The "Domino Effect" Challenge: The paper highlights a critical vulnerability in pLRU (and similar policies) where specific access patterns can lead to a block being "stuck" in the cache, never being evicted. This necessitates a specialized test sequence beyond simple FSM traversal.
  • SBST for Replacement Logic: Demonstrates that SBST can be effectively applied to test the complex control logic of cache replacement policies, not just the memory array.
  • Observability via Hit/Miss: The method relies on the observable hit/miss signal, making it applicable without requiring additional hardware for test access.

Key Results

The proposed methodology was evaluated on a 4-way set-associative data cache controller implementing the pLRU policy within a Leon3 processor core.

  • Reduced Test Sequence Length: The FSM representation resulted in significantly fewer states and transitions compared to previous approaches (e.g., 8 states and 40 transitions for a 4-way cache vs. 24 states and 125 transitions in prior work).
  • 100% Fault Coverage: The generated test sequence achieved 100% fault coverage for stuck-at faults on the pLRU replacement circuitry.
  • Compact Test Program: The generated C program for the Leon3 core consisted of 660 memory accesses and was relatively small (15.6 KB), taking approximately 293 K clock cycles to execute.

Limitations and Future Work

  • Limitations:
    • The paper focuses specifically on the pLRU replacement policy. While the FSM approach is generalizable, the specific "status check" sequence is tailored to pLRU's characteristics.
  • The methodology assumes the availability of a "cache monitor" to verify the expected hit/miss behavior, which might require some form of performance counter or timing measurement.
  • Future Work: The authors suggest that the methodology can be extended to other replacement policies and different cache configurations. Further research could explore more sophisticated FSM modeling techniques or automated generation of the "cache monitor" functionality.

Summary updated

BibTeX
@inproceedings{h2011functional,
  author = {Wilson J. Pérez H. and Ernesto Sánchez and Matteo Sonza Reorda and Alberto Tonda and Jaime Velasco-Medina},
  title = {{Functional test generation for the pLRU replacement mechanism of embedded cache memories}},
  booktitle = {Latw},
  year = {2011},
  doi = {10.1109/latw.2011.5985898},
}
Figure