模塊化片上系統(tǒng)中高級可擴展接口的死鎖避免

郭振江 王煥東 張福新 肖俊華*

①(計算機體系結(jié)構(gòu)國家重點實驗室 北京 100190)

②(中國科學院計算技術研究所 北京 100190)

③(中國科學院大學計算機科學與技術學院 北京 100049)

④(龍芯中科技術有限公司 北京 100190)

1 引言

模塊化片上系統(tǒng)(Modular System on Chip,MSoC)作為一種新興的芯片設計方法，為當前摩爾定律與算力需求之間、芯片面積與良率之間、設計復雜度與快速迭代之間的矛盾提供了突破性的解決方案[1–5]。目前，單個獨立芯片的設計遇到了兩方面的挑戰(zhàn)。一是深度學習時代的算力需求每3～4月翻1番，但摩爾定律卻只能每1.5～2年翻1番[6]。二是增大單一芯片面積會導致芯片良率迅速下降，并受到光刻口徑限制，最終撞上“面積墻”。MSoC可以通過封裝多個獨立設計的芯粒(Die)提供更多功能和算力，同時較高的良率、可重復使用的設計、獨立的制程工藝帶來成本收益足夠抵消封裝開銷[7]。國內(nèi)外幾乎同時成立產(chǎn)業(yè)聯(lián)盟制定互連標準也促使SoC進一步向模塊化發(fā)展。

表1整理了近年發(fā)布的多款處理器芯片中的IP組件情況。從中可以看出，這些芯片異構(gòu)集成了不同類型的IP，通常包括多個處理器核、多核GPU、神經(jīng)網(wǎng)絡處理單元(Neural Processor Unit ,NPU)以及各類定制化的組件如圖像信號處理(Image Signal Processing ISP)單元、密碼學加速器Crypto、數(shù)據(jù)壓縮加速器等。這些IP來自不同的設計團隊，多核IP內(nèi)部一般還包含有互連子網(wǎng)絡。模塊化SoC靈活、復雜的結(jié)構(gòu)給片上網(wǎng)絡(Networkon-Chip, NoC)帶來了新的挑戰(zhàn)。

表1 近年發(fā)布的多款處理器芯片的IP組件情況

一方面，現(xiàn)有的無死鎖互連研究缺少拓撲靈活性，不適用于模塊化SoC?，F(xiàn)有的研究大多假設SoC包含多個2D Mesh，并通過有限數(shù)量的邊界路由器在水平或垂直方向互聯(lián)[14,15]。而實際芯片往往具有明顯的非對稱特征，無法嵌入到Mesh當中。此外，實際芯片通常包含多個子網(wǎng)絡，且子網(wǎng)絡間直接連線較多，但現(xiàn)有的研究沒有充分利用這種拓撲信息[16]。

另一方面，現(xiàn)有的無死鎖理論大多基于蟲洞路由，但高級可擴展接口(Advanced eXtensible Interface, AXI)協(xié)議與蟲洞路由不完全相同。第1點不同在于，AXI協(xié)議允許同一個數(shù)據(jù)包的寫請求和寫數(shù)據(jù)之間存在一定的時間間隔。這種特性將引入新的死鎖類型。第2點不同在于，AXI協(xié)議有5個通道。蟲洞路由使用通道依賴圖(C h a n n e l Dependency Graph, CDG)判斷NoC是否存在死鎖，但AXI網(wǎng)絡的CDG非常復雜，并且構(gòu)建過程容易出錯。

因此，當前迫切需要一種針對模塊化SoC的NoC無死鎖設計方法學。這種方法需要滿足模塊化SoC架構(gòu)靈活的特點，需要充分利用拓撲信息，需要簡單便捷的快速建構(gòu)，能夠以較少的時間和人力成本檢測當前結(jié)構(gòu)中潛在死鎖，并有對應的解決方案。

本文主要創(chuàng)新點包含以下3個方面：

(1) 構(gòu)建了一個模擬系統(tǒng)模塊化片上系統(tǒng)MSoC，本系統(tǒng)包含多種異構(gòu)組件和多個子網(wǎng)絡，用于研究實際系統(tǒng)可能遇到的死鎖類型；

(2) 研究了基于AXI的NoC中的3種死鎖，并分別從拓撲和路由的角度提出了解決方案；

(3) 提出自動化的死鎖定位算法“先拓撲后路由”(First Topology Last Routing, FTLR)，大幅降低了硅前死鎖檢測的難度。將本方法應用于真實模塊化SoC的構(gòu)建中，成功發(fā)現(xiàn)了多處潛在死鎖，大幅縮短了驗證時間。

本文包含以下部分：第1節(jié)介紹本文的研究背景和主要貢獻；第2節(jié)介紹互連網(wǎng)絡死鎖避免的相關工作，以及它們在模塊化SoC上的擴展；第3節(jié)介紹本文構(gòu)建的模塊化SoC系統(tǒng)結(jié)構(gòu)和實驗方法；第4節(jié)介紹3種基于AXI的互連網(wǎng)絡的死鎖，提出了對應的解決方案；第5節(jié)介紹自動化死鎖定位方法和實驗結(jié)果；第6節(jié)總結(jié)。

2 相關工作

針對模塊化SoC片上網(wǎng)絡的無死鎖方案大多從單個NoC的無死鎖機制擴展而來，主要的理論依據(jù)是Dally理論：片上網(wǎng)絡無死鎖的充分必要條件是其通道依賴圖中無環(huán)。下面介紹4種避免死鎖的方法，以及如何擴展到模塊化SoC。

基于日期線(Dateline)[17]的方法。該方法將跨過Dateline的數(shù)據(jù)包切換到額外的虛通道(Virtual Channel, VC)中，環(huán)形依賴被轉(zhuǎn)換為兩倍長度的線性依賴，從而避免死鎖。VC可以提高NoC的路徑多樣性，但會增加CDG復雜度，導致建模和分析困難。

基于轉(zhuǎn)彎限制(Turn Restriction, TR)[18]的方法。該方法主要用于2D Mesh，限制數(shù)據(jù)包的轉(zhuǎn)彎方向，避免形成環(huán)路。該方法可以與負載均衡、網(wǎng)絡容錯、功耗控制、近似計算[19–22]等技術結(jié)合，提供魯棒的片上通信服務。但該方法靈活性較差，不適用于不規(guī)則結(jié)構(gòu)的網(wǎng)絡。

基于流量控制(Flow Control, FC)[23]的方法。該方法在鏈路中只有1個空閑緩沖區(qū)時禁止新數(shù)據(jù)包的注入，而擁有空閑緩沖區(qū)的通道不依賴于其他通道，從而避免死鎖。流量控制需要額外的控制邏輯，增加了復雜度。

基于偏轉(zhuǎn)路由(Deflection Routing, DR)[22,24]的方法。該方法消除了NoC中的緩沖區(qū)，因此通道之間也不存在依賴關系，從而避免死鎖。該方法將收到的數(shù)據(jù)包轉(zhuǎn)發(fā)到輸出端口，即使是非生產(chǎn)路徑，導致高負載時性能下降等問題。

上述4種方案主要解決單個NoC的無死鎖問題。由于無死鎖的不可組合性，上述方案需要一定的修改才能擴展到模塊化SoC中。針對3D Mesh，已經(jīng)提出了電梯優(yōu)先(Elevator-First, EF)[24]方法。該方法在每個2D Mesh平面上使用維度優(yōu)先路由，而在平面間使用額外的虛通道保證無死鎖。針對2.5D集成的芯片，模塊化轉(zhuǎn)彎限制(Modular Turn Restriction, MTR)[15]將每個Die的外部抽象成一個虛擬節(jié)點，并施加轉(zhuǎn)彎限制；遠程控制(Remote Control, RC)[16]通過FC機制避免邊界緩沖區(qū)被跨Die請求擁塞，從而消除通道間的依賴。文獻[25]擴展了DR方法，設計專門的交換模塊處理跨Die的請求。

然而，這些方法與如今的模塊化SoC有一些差別。

拓撲方面，由于良率和散熱等因素的影響，目前只有高帶寬存儲(High Bandwidth Memory,HBM)設備仍在使用3D集成技術[26]，模塊化SoC更傾向于與2.5D集成。另外，異構(gòu)IP通常僅提供唯一的訪問接口，不存在多個邊界路由器。最后，模塊化SoC結(jié)構(gòu)靈活，很少使用Mesh結(jié)構(gòu)[8,10,24,25]。因此需要一種針對實際模塊化SoC拓撲結(jié)構(gòu)的無死鎖機制。

路由方面，大多數(shù)IP使用AXI協(xié)議。上述方法都基于蟲洞路由假設，而AXI協(xié)議與蟲洞路由存在一些差別。其次，AXI協(xié)議具有5個通道，這極大增加了構(gòu)建CDG的復雜度。因此，研究基于AXI協(xié)議的無死鎖NoC具有實際意義。

表2比較了上述4種機制和本文所提出方法的適用拓撲、是否需要CDG、是否支持模塊化SoC以及實現(xiàn)開銷。本文所提方法適用于模塊化SoC，面向靈活易擴展的Crossbar或者點對點結(jié)構(gòu)的NoC，并且也不需要構(gòu)建復雜的CDG。

表2 死鎖避免機制比較

基于死鎖恢復的方法[27–31]允許死鎖的發(fā)生，同時檢測死鎖并實施恢復。該方法需要對模塊內(nèi)部做侵入性的修改，這違反了模塊化SoC的設計原則。并且根據(jù)本文實際觀察到的死鎖來看，沒有必要為其設計復雜又昂貴的檢測和處理機制。通過簡單的硬件或軟件修改避免死鎖的出現(xiàn)是最有效的措施。

3 系統(tǒng)結(jié)構(gòu)和實驗方法

本節(jié)首先介紹實驗系統(tǒng)MSoC的結(jié)構(gòu)。該系統(tǒng)符合當前微處理器的主流架構(gòu)，并且基于AXI協(xié)議構(gòu)建其互連網(wǎng)絡。本節(jié)還將介紹針對互連網(wǎng)絡的實驗配置和測試方法。

3.1 系統(tǒng)結(jié)構(gòu)

本文構(gòu)建的模塊化SoC，稱為MSoC，如圖1所示。MSoC包含1個CPU Die、1個GPU Die和1個IO Die，這種結(jié)構(gòu)能夠準確概括當前主流微處理器的基本結(jié)構(gòu)。

圖1 MSoC芯片架構(gòu)圖

MSoC集成的3個Die由不同的團隊獨立設計。其中CPU Die包含2個處理器核(Core)、2個最后一級高速緩存(Last-Level Cache, LLC)、1個內(nèi)存控制器接口(Double Data Rate , DDR)。CPU Die包含兩級互連網(wǎng)絡NoC-0和NoC-1。 IO Die包含高速IO接口如 高速串行計算機擴展總線標準(Peripheral Component Interconnect Express, PCIE)接口(圖1中有4個)以及低速IO接口如USB和GMAC等。高速IO接口連接到NoC-2上，低速IO接口連接到NoC-3上。GPU Die包含1個GPU、1個視頻處理單元(Video Processing Unit, VPU)和顯存(GPU MEMory, GMEM)。

下面介紹MSoC中的Die-to-Die互連。CPU Die通過NoC-0訪問IO Die和GPU Die，訪問GPU Die的通道是用于訪問GMEM的快速通道。IO Die通過NoC-2訪問CPU Die，此時為保持Cache一致性，需要經(jīng)過DMA模塊。IO Die不能質(zhì)檢訪問GPU Die，只能轉(zhuǎn)發(fā)CPU Die訪問GPU Die的請求。GPU Die一方面通過直連通路快速訪問DDR，另一方面復用IO Die的DMA模塊進行一致性訪問。

MSoC還具有Chip-to-Chip互連的能力。兩片MSoC可以通過PCIE進行跨片的內(nèi)存訪問。

圖1中所有IP核均通過AXI協(xié)議連接到NoC上，其中箭頭的方向即代表AXI Master到Slave的方向。兩個Core只有Master接口沒有Slave接口，而DDR剛好相反，只有Slave接口沒有Master接口。其他設備均包含Master接口和Slave接口。每個Master端口有唯一的ID號，用于標明數(shù)據(jù)包的發(fā)送者。

MSoC中的NoC均為Crossbar結(jié)構(gòu)，并通過計算地址窗口命中的方式確定請求的轉(zhuǎn)發(fā)方向?；ミB網(wǎng)絡為提供標準的AXI接口用于對接IP核，包含AW, W, B, AR, R 5個通道。AXI協(xié)議是安謀(Advanced RISC Machines, ARM)公司提出的高級微控制器總線協(xié)議(Advanced Microcontroller Bus Architecture, AMBA)中的高速片內(nèi)總線。相比于蟲洞路由將請求頭(Header)信息附在數(shù)據(jù)前發(fā)送，AXI使用獨立的通道發(fā)送請求和數(shù)據(jù)，即AW通道負責攜帶路由信息，而W用于傳輸數(shù)據(jù)。每個寫事務包含1個AW通道的請求，以及1個或多個W通道的數(shù)據(jù)。同一個數(shù)據(jù)包的AW和W不一定緊鄰，二者之間可能間隔數(shù)個時鐘周期。這是AXI協(xié)議與蟲洞路由協(xié)議的重要區(qū)別。

為了保持結(jié)構(gòu)盡可能簡單，以及保證數(shù)據(jù)盡可能快地交付，MSoC使用死鎖避免機制。由于MSoC的異構(gòu) IP核之間幾乎都是點對點鏈接，因此現(xiàn)有的死鎖避免方法無法直接使用。因此需要全面檢查MSoC中可能出現(xiàn)的死鎖，并給出針對性的避免方案。

3.2 實驗方法

本文使用寄存器轉(zhuǎn)換級電路(Register Transfer Level, RTL)構(gòu)建了整個MSoC的片NoC。Core包含私有的一級Cache，包括32 kB的指令Cache和32 KB的數(shù)據(jù)Cache。私有Cache主要用于模擬Cache一致訪問請求。LLC的大小共2 MB，分為兩個Bank，采用地址位交錯的方式訪問。對于接收到的命中的Cache訪問，LLC將直接回復數(shù)據(jù)；而對于非Cache訪問和未命中訪問，LLC將進一步向DDR請求數(shù)據(jù)。除此之外不會主動發(fā)起對其他設備的訪問。LLC使用MSI目錄維護Cache一致性?；ミB網(wǎng)絡運行在1 GHz，其他模塊通過同步或異步FIFO連接到片NoC上，并采用Round-Robin的方式滿足服務質(zhì)量(QoS)。

Core, GPU和PCIE等模塊的AXI Master接口連接一個隨機數(shù)據(jù)包生成器，可以生成全類型全地址空間的訪問。GMEM, PCIE和DDR的每個AXI Slave接口解析數(shù)據(jù)包，并提供隨機數(shù)據(jù)。每個數(shù)據(jù)包綁定一個計時器，延遲超過0負載延遲的100倍則認為網(wǎng)絡發(fā)生了死鎖。

除了驗證單片MSoC無死鎖，本文還假設可能通過PCIE接口連接兩片MSoC，并研究這種情況下可能出現(xiàn)的新的死鎖模式。

MSoC最大限度地還原了真實模塊化SoC中主要的異構(gòu)組件，以及真實模塊化SoC構(gòu)建時可能出現(xiàn)的一些問題。MSoC進行一定程度的簡化以降低設計難度、提高仿真效率，但足以模擬所有可能的潛在死鎖。在MSoC中，本文發(fā)現(xiàn)了3種類型的死鎖。下一節(jié)介紹這些死鎖。

4 3種潛在死鎖及其避免

本節(jié)將介紹發(fā)現(xiàn)的3種死鎖，即雙重路徑死鎖、環(huán)形通道死鎖和橋接死鎖。對每一種死鎖類型，本節(jié)分析了死鎖發(fā)生的拓撲特征和路由特征。最后，本節(jié)給出了硬件和軟件上的死鎖避免方法。

4.1 雙重路徑死鎖

在基于蟲洞路由的NoC中，邏輯上的環(huán)形依賴體現(xiàn)為拓撲上的環(huán)形通道。而在基于AXI的互連網(wǎng)絡中，死鎖也可能發(fā)生在具有雙重路徑的拓撲結(jié)構(gòu)中。雙重路徑死鎖是本文對Dally理論的重要補充。在兩個節(jié)點間維持路徑多樣性是增加帶寬、降低平均延遲的常用方法，但在基于AXI的互連網(wǎng)絡中反而可能是導致死鎖的原因。

4.1.1 寫通道雙重路徑

考慮圖2中GPU與DDR之間的通路，如圖2(a)所示。GPU與DDR之間存在兩條通路，根據(jù)請求的Cache屬性進行選擇。左側(cè)是Cache類型請求的訪問通道，需要經(jīng)過LLC；右側(cè)是Uncache類型請求的專用通道，不經(jīng)過LLC。圖2中n×m代表AXI交叉開關，n為交叉開關輸入通道的數(shù)量，m為輸出通道的數(shù)量。

圖2 雙重路徑死鎖圖示

GPU依次發(fā)送3個寫請求，前兩個是Cache屬性的AW1, W1和AW2, W2，后一個是Uncache屬性的AW3, W3。AW3通過專用通道先于AW1到達DDR，于是AW1被擋在AW3后面，需要等待W2傳輸完成。而此時，根據(jù)協(xié)議，不包含路由信息的W1無法越過AW1，同一通道的W2不能越過W1。于是W3被堵住無法進入右側(cè)的專用通道，即使右側(cè)通道沒有其他數(shù)據(jù)包。因此，形成了AW1→W3→W2→W1→AW1的循環(huán)依賴，導致死鎖。

從拓撲結(jié)構(gòu)上看，此時存在寫通道的雙重路徑(double write path)。造成這種死鎖需要同時滿足：

拓撲：兩條路徑上都包含獨立的AW和W通道；

4.1.2 讀通道雙重路徑

寫通道可能出現(xiàn)雙重路徑死鎖，因為AW通道和W通道分離。那么讀通道是否有可能引發(fā)類似的死鎖呢？由于AR和R通道方向不一致，因此這種情況下不會發(fā)生死鎖。但如果其中一條路徑涉及拆包模塊，就可能觸發(fā)另一種死鎖。

如圖2(b)所示，GPU向DDR發(fā)送兩個連續(xù)的讀請求AR0和AR1，這兩個請求通過不同的路徑路由。處于某種原因，拆包模塊將AR1拆分成兩個請求，即AR1-0和AR1-1。DDR按AR1-0, AR0,AR1-1的順序接收到3個讀請求，并依次回復R1-0,R0, R1-1，這將導致死鎖，如圖2(c)所示。R0在返回GPU時被R1-0阻擋，必須等到R1-1也傳回GPU后才能繼續(xù)傳遞。但R1-1被R0堵在DDR控制器中無法繼續(xù)傳遞，形成了R0→R1-1→R0的循環(huán)依賴，導致死鎖。需要注意的是，該問題不能通過簡單地增加緩沖區(qū)來避免，因為死鎖發(fā)生的原因是緩沖區(qū)之間存在依賴關系。

出現(xiàn)雙重讀路徑死鎖的條件包括：

拓撲：請求端與接收端之間存在至少兩條讀通路(double read path)；其中一條通路存在拆包模塊；

路由： Master可以同時發(fā)出兩種類型的讀請求，并且請求可能被拆分。

4.2 環(huán)形通路死鎖

環(huán)形通路死鎖是符合Dally理論的死鎖類型，但實際中很少有互連網(wǎng)絡在設計時就存在環(huán)形通路。環(huán)形通路的引入往往是缺乏全局信息的改動造成的。

考慮下面一種情況。出于某些原因，需要將原本屬于GPU的一部分地址空間映射到DDR中。NoC-2作為GPU直接相連的子網(wǎng)絡在其中增加了一處回環(huán)通道，將對這部分地址的訪問請求轉(zhuǎn)發(fā)回NoC-0，如圖3(a)所示。圖3中的數(shù)字標號代表了對應的通道。此時的訪問路徑為①→②→③→④→⑤。而NoC-0中恰好也存在一條回環(huán)通道，用于提供PCIE對GPU的訪問，即圖3(b)中的⑤→④→⑦→②→⑧。這兩種類型的流量如果不加區(qū)分地使用同一物理通道，將構(gòu)成④→⑦→②→③→④的環(huán)形依賴，導致死鎖。只有一種流量也可能導致死鎖，即圖3(c)所示的⑥→④→⑦→②→③→④→⑤。

(1)存貨信息不容易跟蹤，難以獲取。該模式常見商業(yè)場景包含三類：靜態(tài)貨物、動態(tài)貨物、倉單類。這些信息都很難及時的傳遞到商業(yè)銀行端。并且對于存貨有可能被調(diào)換的情況，存貨質(zhì)量監(jiān)督難度大的問題。并且在存貨的監(jiān)管過程中，監(jiān)管的權責分析也沒有那么明確，這也是存貨類融資面臨的問題。

圖3 環(huán)形通路死鎖圖示

出現(xiàn)環(huán)形通路死鎖的條件包括：

拓撲：存在環(huán)形通路。

路由：環(huán)路的各個通道被同時占滿。

4.3 橋接死鎖

模塊化SoC面向未來市場開發(fā)，其組件在設計時并不完全清楚所有可能的場景。本文使用兩片MSoC互連來模擬可能的2.5D封裝，并研究可能導致的死鎖。本文使用PCIE連接兩個芯片，但結(jié)論適用于其他非AXI協(xié)議。

橋接死鎖發(fā)生在協(xié)議級[32]。Dally理論并不適用于協(xié)議級死鎖，因為這種類型的死鎖往往涉及模塊的內(nèi)部實現(xiàn)細節(jié)。AXI協(xié)議為請求和響應使用獨立的物理通道，但PCIE協(xié)議并不區(qū)分這兩者。當不同類型的數(shù)據(jù)包使用了同一通道時，就會導致協(xié)議級死鎖。這類死鎖只有在跨片互聯(lián)時才會暴露出來；其他時候控制器可以正常工作，十分隱秘。

本文的AXI-PCIE轉(zhuǎn)換器如圖4所示。PCIE收集需要跨片的AXI數(shù)據(jù)包，將其轉(zhuǎn)換成PCIE格式的信號傳遞給接收端。接收端將其還原為AXI數(shù)據(jù)包，發(fā)送到網(wǎng)絡上。在當前時刻，由于AW1占據(jù)轉(zhuǎn)換器中的緩沖區(qū)，B2無法跨片，而只有等到B1返回，AW1才會從緩沖區(qū)中離開。在另一側(cè)PCIE中，情況類似。占據(jù)緩沖區(qū)的AW2阻擋了B1跨片，等到B2返回才能讓出緩沖區(qū)。這就構(gòu)成了AW1→B1→AW2→B2→AW1的循環(huán)，導致死鎖。

圖4 橋接死鎖圖示

橋接死鎖發(fā)生的拓撲條件和路由條件包括：

拓撲：存在協(xié)議轉(zhuǎn)換的通路，并且協(xié)議轉(zhuǎn)換模塊為請求和響應提供統(tǒng)一的緩沖區(qū)。

路由：存在大量而跨片請求。

4.4 死鎖避免

本節(jié)討論死鎖避免的方法。

寫通道雙重路徑死鎖可以通過軟件的方式避免。軟件編程人員需要控制數(shù)據(jù)包的類型，保證任何時間內(nèi)都只有Cache的訪問或Uncache的訪問。兩種模式切換時需要保證所有已經(jīng)發(fā)出去的請求都已完成。也可以通過硬件的方式避免，例如控制每個寫請求都只包含一個寫數(shù)據(jù)。但這會影響協(xié)議的性能。

讀通道雙重路徑死鎖可以通過軟件或硬件的方式避免。軟件上可以將控制請求的長度，用多個短請求代替單個長請求。硬件上可以在模塊接入互連網(wǎng)絡之前增加拆包模塊，提前拆分數(shù)據(jù)包。

環(huán)形通道死鎖需要硬件上的解決方案，單純軟件的方案可能過于復雜。各個模塊單獨設計時保證其內(nèi)部無死鎖，死鎖是在模塊集成和修改時引入的，這說明需要重新設計集成方案。在上述案例中，解決方法是去掉在NoC-2處的回環(huán)設計，在NoC-1中處理相關的地址路由。也可以在環(huán)中加入流控機制，避免通道中所有緩沖區(qū)被占滿。

橋接死鎖也需要硬件上的解決方案。PCIE控制器需要為AXI的請求和響應準備不同的緩沖區(qū)，并賦予響應更高的優(yōu)先級。該方法適應與所有涉及跨片連接兩個AXI網(wǎng)絡的接口。

對于上述死鎖，單純增加緩沖區(qū)的數(shù)量并不能解決死鎖，這是Dally定理已經(jīng)說明的。問題不在于緩沖區(qū)的數(shù)量，而在于緩沖區(qū)之間的依賴關系。

5 死鎖定位

基于CDG的死鎖定位方法需要同時考慮AXI的5個通道之間的依賴關系，基于UVM隨機驗證的方法則需要大量的人力和時間。因此迫切需要一種NoC中潛在死鎖的定位方法，并要求該方法可以根據(jù)設計進度隨時反饋。

本節(jié)基于上述3類死鎖的拓撲特征和路由特征，提出一種輕量級的檢測方式，用于快速發(fā)現(xiàn)模塊化SoC中這3種類型的死鎖。

5.1 死鎖定位算法

本文所提死鎖定位算法，名為先拓撲后路由(FTLR)算法。本算法將死鎖的定位過程分為兩個階段。第1階段該算法進行拓撲分析，標識可能造成死鎖的數(shù)據(jù)通路。第2階段該算法進行路由分析，并與拓撲路由進行匹配。如果匹配成功則說明存在潛在死鎖。下面介紹本算法的細節(jié)。

第1階段，F(xiàn)TLR將有向圖G作為輸入，輸出中間結(jié)果集M。G中的點是NoC中模塊或接口，從模塊A直接連接到模塊B的通道表示為從點A到點B的有向邊。中間結(jié)果集M中記錄著從任一Master接口到任一Slave接口的所有數(shù)據(jù)通路，并且特殊標記其中的拆包模塊和橋接模塊。在這一階段，F(xiàn)TLR使用廣度優(yōu)先算法處理圖G。

第2階段，F(xiàn)TLR處理路由規(guī)則集F和中間結(jié)果集M。F通常以表格的形式提供，規(guī)定了不同地址空間、不同類型請求的終點設備和訪問路徑。FTLR在F和M中進行匹配，檢查M中路由能否被同時激活，或滿足其他死鎖發(fā)生條件。如果匹配成功，則定位到死鎖。FTLR算法的流程整理在算法1中。

圖G可以很容易地在NoC的設計文檔中找到，并且可以隨設計改動而迅速調(diào)整。FTLR第1階段的算法復雜度為O(N2)，第2階段的路由表F規(guī)模也為O(N2)，其中N為圖G的頂點數(shù)。在實際場景中，由于設計階段復雜性限制和制造階段成本限制，芯片中的組件數(shù)不會很大，N通常會被控制在30以內(nèi)。這一點也可以從表1中得到體現(xiàn)。因此盡管FTLR算法的復雜度為O(N2)，也完全可以在幾秒鐘的時間內(nèi)完成，這在以年計算的芯片設計周期中占比微乎其微。

5.2 實驗

將本文所提檢測方法應用于MSoC的互連網(wǎng)絡無死鎖驗證中，并與CDG和UVM的方法做對比。UVM采用全系統(tǒng)隨機驗證，分批進行4 500輪測試，每輪測試攻擊發(fā)送125 000數(shù)據(jù)包，數(shù)據(jù)包總量超過 5.6×109次。最終發(fā)現(xiàn)雙重路徑死鎖3處、環(huán)形通路型死鎖1處以及橋接型死鎖2處。測試結(jié)果整理在表3中。

表3 互連網(wǎng)絡死鎖檢測方法對比

在死鎖覆蓋率方面，UVM和FTLR方法可以檢測出所有的死鎖類型，CDG方法無法覆蓋雙重通道死鎖和橋接死鎖。在檢測效率方面，CDG和FTLR方法可以同時報告所有死鎖，而UVM需要逐個報告，并且需要人工調(diào)試波形才能發(fā)現(xiàn)死鎖。在建模難度方面，CDG方法最為復雜，并且很容易出錯；UVM難度一般，只需要RTL代碼即可；而FTLR只需要根據(jù)MSoC的芯片架構(gòu)圖就可以完成建模，最為簡單。在檢測時間方面，UVM方法需要長時間的運行測試并且需要人工調(diào)試波形，因此可能需要幾周的時間；CDG方法需要復雜的建模，因此可能需要幾天的時間用于建模；而FTLR方法只需要幾個小時就可以完成建模到檢測的全過程。本文方法大幅減少了驗證時間和人力投入，并且可以隨時根據(jù)網(wǎng)絡結(jié)構(gòu)進行調(diào)整，具有一定的靈活性。

FTLR算法可以有效地發(fā)現(xiàn)基于AXI的互連網(wǎng)絡中潛在的死鎖。相比傳統(tǒng)的驗證方法，基于拓撲特征和路由特征的FTLR算法發(fā)現(xiàn)死鎖的速度更快、成本更低、結(jié)果更全，可以提高互連網(wǎng)絡的魯棒性，并且可以在SoC構(gòu)建過程中反復執(zhí)行，隨時發(fā)現(xiàn)問題。

算法1 FTLR算法

6 結(jié)束語

模塊化SoC的設計理念正在被越來越多的處理器廠商使用，這給基于AXI的互連網(wǎng)絡帶來了新的無死鎖挑戰(zhàn)。首先，AXI協(xié)議不同于傳統(tǒng)的蟲洞路由，需要對原有理論的擴展。其次，多種功能的組件在集成時經(jīng)常會發(fā)生改動和調(diào)整，這可能在原本無死鎖的互連子網(wǎng)絡之間引入新的死鎖，為此需要全程的、增量的、靈活的監(jiān)控方案。最后，為了避免在多芯片跨片互連或2.5D集成時引入?yún)f(xié)議級死鎖，協(xié)議轉(zhuǎn)換、拆包模塊等特殊組件需要預留足夠的資源。

本文基于真實異構(gòu)SoC構(gòu)建了死鎖分析模型MSoC，系統(tǒng)性地研究了基于AXI的互連網(wǎng)絡在模塊化集成過程中可能引入的潛在死鎖。本文提出了3種死鎖，即雙重通道死鎖、環(huán)形通道死鎖和橋接死鎖，研究了它們的拓撲特征和路由特征，并提出了對應的死鎖避免方案。本文進一步構(gòu)建了自動化的定位工具全面排查和監(jiān)控互連網(wǎng)絡潛在的死鎖問題，極大地縮短了驗證時間、提高了驗證效率。本文擴展了傳統(tǒng)的Dally理論，填補了AXI互連無死鎖理論的空白，為模塊化SoC的設計提供了幫助。