科研動(dòng)態(tài)
EMGA:?一種用于MBIST內(nèi)存分組的進(jìn)化式算法
中文題目：EMGA: 一種用于MBIST內(nèi)存分組的進(jìn)化式算法
論文題目：EMGA: An Evolutionary Memory Grouping Algorithm for MBIST
錄用期刊/會(huì)議：2024 International Symposium of Electronics Design Automation (ISEDA) (EI索引國(guó)際會(huì)議)
原文鏈接：https://www.ssslab.cn/assets/papers/2024-li-EMGA.pdf
DOI：10.1109/ISEDA62518.2024.10617612
錄用/見(jiàn)刊時(shí)間：2024-3-26
作者列表：
1） 李陽(yáng) 中國(guó)石油大學(xué)（北京）人工智能學(xué)院
2） 段永強(qiáng) 中國(guó)石油大學(xué)（北京）人工智能學(xué)院
3） 張昊 中國(guó)石油大學(xué)（北京）人工智能學(xué)院
4） 牛丹 東南大學(xué) 自動(dòng)化學(xué)院
5） 吳梟 北京華大九天科技股份有限公司
6） 金洲 中國(guó)石油大學(xué)（北京）人工智能學(xué)院
背景與動(dòng)機(jī):
MBIST（存儲(chǔ)器內(nèi)置自測(cè)試）是芯片設(shè)計(jì)和制造中廣泛使用的一種方法，用于檢測(cè)和定位內(nèi)存中的故障。由于現(xiàn)代芯片的存儲(chǔ)器容量很大，因此需要對(duì)存儲(chǔ)器進(jìn)行分組，以便有效地進(jìn)行管理和測(cè)試。傳統(tǒng)的啟發(fā)式算法在處理具有較多約束條件和存儲(chǔ)器的MBIST分組問(wèn)題時(shí)，往往面臨時(shí)間復(fù)雜度高和分組結(jié)果質(zhì)量較差的挑戰(zhàn)。為了克服這些限制，本文提出了一種創(chuàng)新的基于啟發(fā)式的MBIST分組算法。該算法通過(guò)優(yōu)化啟發(fā)式策略，不僅顯著提高了求解效率，而且在保持高效率的同時(shí)實(shí)現(xiàn)了高質(zhì)量的分組結(jié)果。
設(shè)計(jì)與實(shí)現(xiàn):
（1）EMGA框架
圖1 總體EMGA算法實(shí)現(xiàn)流程
如圖1所示，EMGA 包含三個(gè)主要部分。第一部分是解析器和硬分區(qū)。由于存儲(chǔ)器類型、功耗和各種分組約束等屬性信息幾乎都存在于存儲(chǔ)器的設(shè)計(jì)文件中，因此需要從文件中提取存儲(chǔ)器信息和約束，并保存到相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中。讀取信息后，我們可以將約束分為硬約束和軟約束。如圖 3 所示，根據(jù)硬約束，對(duì)內(nèi)存進(jìn)行硬分區(qū)，得到初始分組。第二部分使用貪心算法來(lái)減少每個(gè)分組的大小，并根據(jù)初始分組快速獲得滿足硬約束和軟約束的結(jié)果。第三部分使用遺傳算法來(lái)尋找更少的分組，以避免局部最優(yōu)解。
在分組過(guò)程中，首先要面對(duì)多約束問(wèn)題。多約束指的是在分組過(guò)程中需要同時(shí)考慮各種因素或限制。如上述所示，我們選擇了通常最重要的一些約束，（1）和（2）是功率約束和距離約束，（3）中的這些特性是必須滿足的，如邏輯地址映射約束、時(shí)鐘約束、類型約束、邏輯端口約束和寫(xiě)越界約束等。只有滿足所有限制條件的存儲(chǔ)器才能被分為一組，而且最終分組數(shù)量越少越好。
（3）貪心算法損失函數(shù)的定義
是僅考慮功耗時(shí)的分組數(shù)，
是僅考慮距離時(shí)的分組數(shù)，λ為
，μ為
。我們引入權(quán)重系數(shù)λ和μ，可以靈活地調(diào)整功耗和距離在損失函數(shù)中的重要性。這允許算法根據(jù)具體應(yīng)用場(chǎng)景的需求，更側(cè)重于功耗或距離的優(yōu)化。Wi是將第 i 個(gè)內(nèi)存添加到當(dāng)前組后的功耗，Di是將第 i 個(gè)內(nèi)存添加到當(dāng)前組后的最大距離。Max_Power和Max_Distance是最大功耗和最大距離。我們將功耗和距離的變化除以它們的最大值，使得這兩個(gè)量綱不同的指標(biāo)具有可比性。這樣，算法在每一步都可以公平地比較功耗和距離的影響。故損失函數(shù)F定義為：
總的來(lái)說(shuō)，這樣的損失函數(shù)定義使得貪心算法能夠在功耗和距離之間進(jìn)行有效的權(quán)衡，從而在每一步都做出最優(yōu)的選擇，最終得到一個(gè)近似全局最優(yōu)的解。
圖2 遺傳算法流程
（4）遺傳算法優(yōu)化
通過(guò)貪心算法得到的一個(gè)優(yōu)質(zhì)初始解將會(huì)作為遺傳算法的初始輸入。這種組合策略充分發(fā)揮了貪心算法的局部搜索優(yōu)勢(shì)和遺傳算法的全局搜索特點(diǎn)。貪心算法通過(guò)在每一步選擇當(dāng)前最優(yōu)解，快速收斂到一個(gè)局部最優(yōu)解，為遺傳算法提供了一個(gè)高質(zhì)量的起點(diǎn)。遺傳算法則在此基礎(chǔ)上，通過(guò)模擬自然選擇和遺傳機(jī)制，對(duì)解空間進(jìn)行全局搜索，進(jìn)一步優(yōu)化解的質(zhì)量。這種組合策略不僅提高了算法的搜索效率，還增強(qiáng)了算法的全局搜索能力，使得最終得到的解更加接近全局最優(yōu)解。
如圖2所示，經(jīng)過(guò)約束分區(qū)，目前的約束只剩下軟約束，即功耗和距離。功耗約束類似于一維裝箱問(wèn)題，加上距離約束后，這個(gè)問(wèn)題可以看成是一個(gè)有沖突的一維裝箱問(wèn)題。在傳統(tǒng)的一維裝箱問(wèn)題中，遺傳算法的性能最好。遺傳算法通常分為基因編碼和種群迭代兩大部分。在基因編碼階段，我們使用實(shí)數(shù)編碼。與離散編碼相比，實(shí)數(shù)編碼提供了更大的解空間，有助于找到更好的解。在群體迭代階段，我們采用了多樣化的交叉和突變技術(shù)，以增加跳出局部最優(yōu)解的可能性。此外，為了提高時(shí)間性能，我們采用了空間換時(shí)間策略，并引入自適應(yīng)突變來(lái)優(yōu)化群體質(zhì)量。
實(shí)驗(yàn)結(jié)果及分析:
表1 各個(gè)算法的分組數(shù)量和運(yùn)行時(shí)間
圖 3 各個(gè)算法分組數(shù)量比較
圖4各個(gè)算法運(yùn)行時(shí)間比較
如上圖實(shí)驗(yàn)結(jié)果所示，與其他方法比較，EMGA在最為關(guān)注的分組質(zhì)量方面表現(xiàn)最好。EMGA結(jié)合了貪心算法和遺傳算法的優(yōu)勢(shì)。它能快速得到一個(gè)初始解，并且能夠通過(guò)改進(jìn)的遺傳算法維護(hù)一個(gè)多解集合，其中包含了搜索到的多個(gè)優(yōu)秀解。這些解之間可能存在一定的差異，提供了更多的選擇余地。這使得我們的算法比樸素的遺傳算法具有更好的性能。相比之下，模擬退火算法和K-Means算法更容易受局部搜索的限制，可能陷入局部最優(yōu)解。模擬退火算法相對(duì)較容易陷入某個(gè)解附近，導(dǎo)致生成更多且相似的分組。K-Means算法本身傾向于找到局部最優(yōu)解而不是全局最優(yōu)解。
結(jié)論:
本文提出一種結(jié)合貪心算法和遺傳算法的策略，以降低功耗、優(yōu)化內(nèi)存塊分組并提高內(nèi)存系統(tǒng)的整體性能。通過(guò)利用貪心算法快速找到局部最優(yōu)解，并將其作為遺傳算法的初始解，我們成功地提高了算法的收斂速度和最終解的質(zhì)量。這種組合策略充分發(fā)揮了貪心算法的局部搜索優(yōu)勢(shì)和遺傳算法的全局搜索特點(diǎn)。實(shí)驗(yàn)結(jié)果表明，在不同的數(shù)據(jù)集和約束條件下，所提出的算法在功耗、距離和執(zhí)行時(shí)間上都有顯著的性能提升。在初始分組階段，貪心算法能快速識(shí)別相對(duì)最優(yōu)解，并將其與遺傳算法相結(jié)合，進(jìn)一步提高算法性能。
通訊作者簡(jiǎn)介:
金洲，副教授，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)系副教授，入選北京市科協(xié)青年人才托舉工程、校青年拔尖人才。主要從事集成電路設(shè)計(jì)自動(dòng)化（EDA）方面的研究工作。主持并參與國(guó)家自然科學(xué)基金青年項(xiàng)目、培育項(xiàng)目、重點(diǎn)項(xiàng)目，科技部重點(diǎn)研發(fā)微納電子專項(xiàng)、高性能計(jì)算專項(xiàng)青年科學(xué)家項(xiàng)目，國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題、企業(yè)橫向課題等。在DAC、TCAD、TODAES、SC、PPoPP、IPDPS、TCAS-II、ASP-DAC等重要國(guó)際會(huì)議和期刊上發(fā)表60余篇高水平學(xué)術(shù)論文。獲EDA2青年科技獎(jiǎng)、SC23最佳論文獎(jiǎng)、ISEDA23榮譽(yù)論文獎(jiǎng)、IEEJ九州支部長(zhǎng)獎(jiǎng)等。
聯(lián)系方式：jinzhou@cup.edu.cn