中文題目：EMGA: 一種用于MBIST內存分組的進化式算法

論文題目：EMGA: An Evolutionary Memory Grouping Algorithm for MBIST

錄用期刊/會議：2024 International Symposium of Electronics Design Automation (ISEDA) (EI索引國際會議)

原文鏈接：https://www.ssslab.cn/assets/papers/2024-li-EMGA.pdf

DOI：10.1109/ISEDA62518.2024.10617612

錄用/見刊時間：2024-3-26

作者列表：

1） 李陽 中國石油大學（北京）人工智能學院

2） 段永強 中國石油大學（北京）人工智能學院

3） 張昊 中國石油大學（北京）人工智能學院

4） 牛丹 東南大學 自動化學院

5） 吳梟 北京華大九天科技股份有限公司

6） 金洲 中國石油大學（北京）人工智能學院

 

背景與動機:

MBIST（存儲器內置自測試）是芯片設計和制造中廣泛使用的一種方法，用于檢測和定位內存中的故障。由于現代芯片的存儲器容量很大，因此需要對存儲器進行分組，以便有效地進行管理和測試。傳統的啟發式算法在處理具有較多約束條件和存儲器的MBIST分組問題時，往往面臨時間復雜度高和分組結果質量較差的挑戰。為了克服這些限制，本文提出了一種創新的基于啟發式的MBIST分組算法。該算法通過優化啟發式策略，不僅顯著提高了求解效率，而且在保持高效率的同時實現了高質量的分組結果。

設計與實現:

（1）EMGA框架

 

圖1 總體EMGA算法實現流程

如圖1所示，EMGA 包含三個主要部分。第一部分是解析器和硬分區。由于存儲器類型、功耗和各種分組約束等屬性信息幾乎都存在于存儲器的設計文件中，因此需要從文件中提取存儲器信息和約束，并保存到相應的數據結構中。讀取信息后，我們可以將約束分為硬約束和軟約束。如圖 3 所示，根據硬約束，對內存進行硬分區，得到初始分組。第二部分使用貪心算法來減少每個分組的大小，并根據初始分組快速獲得滿足硬約束和軟約束的結果。第三部分使用遺傳算法來尋找更少的分組，以避免局部最優解。

（2）約束條件

在分組過程中，首先要面對多約束問題。多約束指的是在分組過程中需要同時考慮各種因素或限制。如上述所示，我們選擇了通常最重要的一些約束，（1）和（2）是功率約束和距離約束，（3）中的這些特性是必須滿足的，如邏輯地址映射約束、時鐘約束、類型約束、邏輯端口約束和寫越界約束等。只有滿足所有限制條件的存儲器才能被分為一組，而且最終分組數量越少越好。

（3）貪心算法損失函數的定義

是僅考慮功耗時的分組數，是僅考慮距離時的分組數，λ為，μ為。我們引入權重系數λ和μ，可以靈活地調整功耗和距離在損失函數中的重要性。這允許算法根據具體應用場景的需求，更側重于功耗或距離的優化。Wi是將第 i 個內存添加到當前組后的功耗，Di是將第 i 個內存添加到當前組后的最大距離。Max_Power和Max_Distance是最大功耗和最大距離。我們將功耗和距離的變化除以它們的最大值，使得這兩個量綱不同的指標具有可比性。這樣，算法在每一步都可以公平地比較功耗和距離的影響。故損失函數F定義為：

總的來說，這樣的損失函數定義使得貪心算法能夠在功耗和距離之間進行有效的權衡，從而在每一步都做出最優的選擇，最終得到一個近似全局最優的解。

圖2 遺傳算法流程

（4）遺傳算法優化

通過貪心算法得到的一個優質初始解將會作為遺傳算法的初始輸入。這種組合策略充分發揮了貪心算法的局部搜索優勢和遺傳算法的全局搜索特點。貪心算法通過在每一步選擇當前最優解，快速收斂到一個局部最優解，為遺傳算法提供了一個高質量的起點。遺傳算法則在此基礎上，通過模擬自然選擇和遺傳機制，對解空間進行全局搜索，進一步優化解的質量。這種組合策略不僅提高了算法的搜索效率，還增強了算法的全局搜索能力，使得最終得到的解更加接近全局最優解。

如圖2所示，經過約束分區，目前的約束只剩下軟約束，即功耗和距離。功耗約束類似于一維裝箱問題，加上距離約束后，這個問題可以看成是一個有沖突的一維裝箱問題。在傳統的一維裝箱問題中，遺傳算法的性能最好。遺傳算法通常分為基因編碼和種群迭代兩大部分。在基因編碼階段，我們使用實數編碼。與離散編碼相比，實數編碼提供了更大的解空間，有助于找到更好的解。在群體迭代階段，我們采用了多樣化的交叉和突變技術，以增加跳出局部最優解的可能性。此外，為了提高時間性能，我們采用了空間換時間策略，并引入自適應突變來優化群體質量。

實驗結果及分析:

表1 各個算法的分組數量和運行時間

 

圖 3 各個算法分組數量比較

圖4各個算法運行時間比較 

如上圖實驗結果所示，與其他方法比較，EMGA在最為關注的分組質量方面表現最好。EMGA結合了貪心算法和遺傳算法的優勢。它能快速得到一個初始解，并且能夠通過改進的遺傳算法維護一個多解集合，其中包含了搜索到的多個優秀解。這些解之間可能存在一定的差異，提供了更多的選擇余地。這使得我們的算法比樸素的遺傳算法具有更好的性能。相比之下，模擬退火算法和K-Means算法更容易受局部搜索的限制，可能陷入局部最優解。模擬退火算法相對較容易陷入某個解附近，導致生成更多且相似的分組。K-Means算法本身傾向于找到局部最優解而不是全局最優解。

結論:

本文提出一種結合貪心算法和遺傳算法的策略，以降低功耗、優化內存塊分組并提高內存系統的整體性能。通過利用貪心算法快速找到局部最優解，并將其作為遺傳算法的初始解，我們成功地提高了算法的收斂速度和最終解的質量。這種組合策略充分發揮了貪心算法的局部搜索優勢和遺傳算法的全局搜索特點。實驗結果表明，在不同的數據集和約束條件下，所提出的算法在功耗、距離和執行時間上都有顯著的性能提升。在初始分組階段，貪心算法能快速識別相對最優解，并將其與遺傳算法相結合，進一步提高算法性能。 

通訊作者簡介:

金洲，副教授，中國石油大學（北京）計算機系副教授，入選北京市科協青年人才托舉工程、校青年拔尖人才。主要從事集成電路設計自動化（EDA）方面的研究工作。主持并參與國家自然科學基金青年項目、培育項目、重點項目，科技部重點研發微納電子專項、高性能計算專項青年科學家項目，國家重點實驗室開放課題、企業橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國際會議和期刊上發表60余篇高水平學術論文。獲EDA2青年科技獎、SC23最佳論文獎、ISEDA23榮譽論文獎、IEEJ九州支部長獎等。

聯系方式：jinzhou@cup.edu.cn