A New Approach to Multi-objective Error Correcting Code Design Method

Heesung Lee, Euntai KimJournal of Korean Institute of Intelligent Systems 2008 · DOI

Abstract

Error correcting codes (ECCs) are commonly used to protect against soft errors. Single error correcting and double error detecting (SEC-DED) codes are generally used for this purpose. This paper proposes a design method for SEC-DED checker circuits that selectively reduces power consumption, delay, and area. By employing a multi-objective genetic algorithm (MOGA), the design problem is framed as a non-linear optimization. This approach provides a set of non-dominated solutions, allowing users to choose the optimal ECC configuration based on their specific constraints for power, delay, and area. The method is validated using the odd-column weight Hsiao code, demonstrating its effectiveness in generating efficient hardware implementations.

Introduction: Addressing Soft Errors in Memory Systems

As semiconductor technology scales to smaller feature sizes and lower voltages, memory systems become increasingly susceptible to "soft errors"—bit flips caused by cosmic rays or electromagnetic interference. While Error Correcting Codes (ECCs) like SEC-DED are standard solutions, the checker circuits required to implement them introduce overhead in terms of power, silicon area, and latency.

Traditionally, designing these circuits involves trade-offs that are difficult to balance manually. Most existing methods focus on optimizing a single metric or use fixed weightings for different objectives. This research addresses the need for a flexible design framework that can explore the entire trade-off space between power, area, and delay for memory ECC checkers.

Methodology: Multi-objective Genetic Algorithm (MOGA)

The authors focus on Hsiao codes (a type of odd-column weight SEC-DED code) and optimize the construction of the parity-check matrix ($H$-matrix). The $H$-matrix defines how parity bits are generated and checked. A Multi-objective Genetic Algorithm (MOGA) is used to maintain a population of potential $H$-matrices, evolving them to find a set of non-dominated solutions.

A key technical component is the novel chromosome encoding, which represents the $H$-matrix in two parts: a permutation part (mapping memory bits to columns) and a selection part (choosing which high-order odd-weight columns to include).

The chromosome encoding for the H-matrix, divided into permutation and selection segments.

To maintain validity during evolution, the algorithm uses specialized operators: cycle crossover for the permutation segment and arithmetic crossover for the selection segment. Furthermore, the fitness function weights for power, delay, and area are randomized in each generation to ensure thorough exploration of the Pareto front. The method was evaluated using 64-bit memory data sets with varying bitwise profiles, reflecting typical memory usage patterns where switching activity—and thus power consumption—varies across bits.

Results: Navigating the Pareto Front

The primary innovation of this approach is the shift from providing a single design to providing a "menu" of optimal designs, known as non-dominated solutions. In a multi-objective space, a solution is non-dominated if no single objective can be improved without degrading another.

Illustration of dominated vs. non-dominated solutions, representing the trade-offs between power, area, and delay.

The MOGA successfully identified multiple solutions that outperformed previous state-of-the-art methods. For a 64-bit architecture, the tool produced a variety of configurations. For example, it found solutions reducing power consumption by roughly 5-10% compared to standard implementations. While area (gate count) remained relatively stable, the GA minimized variance between XOR tree depths, leading to more predictable timing. This flexibility allows a designer for a mobile device to select a low-power solution, while a server designer might prioritize the lowest possible delay.

Limitations and Future Directions

While effective, genetic algorithms are computationally expensive, and the paper does not deeply discuss convergence times for larger memory widths (e.g., 128-bit). Additionally, the power and delay estimations rely on simplified gate-level models; real-world ASIC or FPGA implementations might introduce routing overheads not fully captured here. Future work could extend this multi-objective approach to other code types or additional hardware constraints like peak current or soft-error masking rates.

Summary updated

Abstract

Error correcting codes는 일반적으로 soft error를 막기 위해서 사용된다. single error의 수정과 double error의 검출(SEC-DED) 코드들은 이런 목적으로 사용된다. 본 논문에서는 이러한 회로의 크기, 지연시간, 전력 소비를 선택적으로 최소로 하는 SEC-DED의 설계방법을 제안한다. 이러한 SEC-DED의 설계는 비선형 최적화 문제로 포함되는데 우리는 다목적 유전자 알고리즘을 이용하여 이 문제를 해결한다. 제안하는 방법은 여러 가지 SEC-DED code들을 제공하여 사용자의 환경에 따라 알맞은 회로를 선택할 수 있도록 한다. 제안하는 방법을 효율적인 ECC코드로 알려져 있는 odd-column weight Hsiao code에 적용하여 그 효율성을 입증하였다. Error correcting codes (ECCs) are commonly used to protect against the soft errors. Single error correcting and double error detecting (SEC-DED) codes are generally used for this purpose. The proposed approach in this paper selectively reduced power consumption, delay, and area in single-error correcting, double error-detecting checker circuits that perform memory error correction. The multi-objective genetic algorithm is employed to solve the non -linear optimization problem. The proposed method allows that user can choose one of different non-dominated solutions depending on which consideration is important among them. Because we use multi-objective genetic algorithm, we can find various dominated solutions. Therefore, we can choose the ECC according to the important factor of the power, delay and area. The method is applied to odd-column weight Hsiao code which is well- known ECC code and experiments were performed to show the performance of the proposed method.
BibTeX
@article{lee2008new,
  author = {Heesung Lee and Euntai Kim},
  title = {{A New Approach to Multi-objective Error Correcting Code Design Method}},
  journal = {Journal of Korean Institute of Intelligent Systems},
  year = {2008},
  doi = {10.5391/jkiis.2008.18.5.611},
}
Figure