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

①(計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室 北京 100190)

②(中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190)

③(中國(guó)科學(xué)院大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 北京 100049)

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

1 引言

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

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

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

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

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

因此，當(dāng)前迫切需要一種針對(duì)模塊化SoC的NoC無(wú)死鎖設(shè)計(jì)方法學(xué)。這種方法需要滿足模塊化SoC架構(gòu)靈活的特點(diǎn)，需要充分利用拓?fù)湫畔?，需要?jiǎn)單便捷的快速建構(gòu)，能夠以較少的時(shí)間和人力成本檢測(cè)當(dāng)前結(jié)構(gòu)中潛在死鎖，并有對(duì)應(yīng)的解決方案。

本文主要?jiǎng)?chuàng)新點(diǎn)包含以下3個(gè)方面：

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

(2) 研究了基于AXI的NoC中的3種死鎖，并分別從拓?fù)浜吐酚傻慕嵌忍岢隽私鉀Q方案；

(3) 提出自動(dòng)化的死鎖定位算法“先拓?fù)浜舐酚伞?First Topology Last Routing, FTLR)，大幅降低了硅前死鎖檢測(cè)的難度。將本方法應(yīng)用于真實(shí)模塊化SoC的構(gòu)建中，成功發(fā)現(xiàn)了多處潛在死鎖，大幅縮短了驗(yàn)證時(shí)間。

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

表2 死鎖避免機(jī)制比較

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

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

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

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

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)方法

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

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

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

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

4 3種潛在死鎖及其避免

本節(jié)將介紹發(fā)現(xiàn)的3種死鎖，即雙重路徑死鎖、環(huán)形通道死鎖和橋接死鎖。對(duì)每一種死鎖類(lèi)型，本節(jié)分析了死鎖發(fā)生的拓?fù)涮卣骱吐酚商卣?。最后，本?jié)給出了硬件和軟件上的死鎖避免方法。

4.1 雙重路徑死鎖

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

4.1.1 寫(xiě)通道雙重路徑

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

圖2 雙重路徑死鎖圖示

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

從拓?fù)浣Y(jié)構(gòu)上看，此時(shí)存在寫(xiě)通道的雙重路徑(double write path)。造成這種死鎖需要同時(shí)滿足：

拓?fù)洌簝蓷l路徑上都包含獨(dú)立的AW和W通道；

4.1.2 讀通道雙重路徑

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

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

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

拓?fù)洌赫?qǐng)求端與接收端之間存在至少兩條讀通路(double read path)；其中一條通路存在拆包模塊；

路由： Master可以同時(shí)發(fā)出兩種類(lèi)型的讀請(qǐng)求，并且請(qǐng)求可能被拆分。

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

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

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

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

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

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

拓?fù)洌捍嬖诃h(huán)形通路。

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

4.3 橋接死鎖

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

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

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

圖4 橋接死鎖圖示

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

拓?fù)洌捍嬖趨f(xié)議轉(zhuǎn)換的通路，并且協(xié)議轉(zhuǎn)換模塊為請(qǐng)求和響應(yīng)提供統(tǒng)一的緩沖區(qū)。

路由：存在大量而跨片請(qǐng)求。

4.4 死鎖避免

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

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

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

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

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

對(duì)于上述死鎖，單純?cè)黾泳彌_區(qū)的數(shù)量并不能解決死鎖，這是Dally定理已經(jīng)說(shuō)明的。問(wèn)題不在于緩沖區(qū)的數(shù)量，而在于緩沖區(qū)之間的依賴關(guān)系。

5 死鎖定位

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

本節(jié)基于上述3類(lèi)死鎖的拓?fù)涮卣骱吐酚商卣?，提出一種輕量級(jí)的檢測(cè)方式，用于快速發(fā)現(xiàn)模塊化SoC中這3種類(lèi)型的死鎖。

5.1 死鎖定位算法

本文所提死鎖定位算法，名為先拓?fù)浜舐酚?FTLR)算法。本算法將死鎖的定位過(guò)程分為兩個(gè)階段。第1階段該算法進(jìn)行拓?fù)浞治?，?biāo)識(shí)可能造成死鎖的數(shù)據(jù)通路。第2階段該算法進(jìn)行路由分析，并與拓?fù)渎酚蛇M(jìn)行匹配。如果匹配成功則說(shuō)明存在潛在死鎖。下面介紹本算法的細(xì)節(jié)。

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

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

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

5.2 實(shí)驗(yàn)

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

表3 互連網(wǎng)絡(luò)死鎖檢測(cè)方法對(duì)比

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

FTLR算法可以有效地發(fā)現(xiàn)基于AXI的互連網(wǎng)絡(luò)中潛在的死鎖。相比傳統(tǒng)的驗(yàn)證方法，基于拓?fù)涮卣骱吐酚商卣鞯腇TLR算法發(fā)現(xiàn)死鎖的速度更快、成本更低、結(jié)果更全，可以提高互連網(wǎng)絡(luò)的魯棒性，并且可以在SoC構(gòu)建過(guò)程中反復(fù)執(zhí)行，隨時(shí)發(fā)現(xiàn)問(wèn)題。

算法1 FTLR算法

6 結(jié)束語(yǔ)

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

本文基于真實(shí)異構(gòu)SoC構(gòu)建了死鎖分析模型MSoC，系統(tǒng)性地研究了基于AXI的互連網(wǎng)絡(luò)在模塊化集成過(guò)程中可能引入的潛在死鎖。本文提出了3種死鎖，即雙重通道死鎖、環(huán)形通道死鎖和橋接死鎖，研究了它們的拓?fù)涮卣骱吐酚商卣鳎⑻岢隽藢?duì)應(yīng)的死鎖避免方案。本文進(jìn)一步構(gòu)建了自動(dòng)化的定位工具全面排查和監(jiān)控互連網(wǎng)絡(luò)潛在的死鎖問(wèn)題，極大地縮短了驗(yàn)證時(shí)間、提高了驗(yàn)證效率。本文擴(kuò)展了傳統(tǒng)的Dally理論，填補(bǔ)了AXI互連無(wú)死鎖理論的空白，為模塊化SoC的設(shè)計(jì)提供了幫助。