支持多優(yōu)先級多輸出通道的數(shù)據(jù)隊列調(diào)度方法和硬件實現(xiàn)

徐金波，?？?，李 琰

(國防科技大學(xué)計算機學(xué)院，湖南 長沙 410073)

1 引言

隨著高性能計算機系統(tǒng)HPC(High Performance Computer)計算速度從千萬億次級(P級，Petascale)向百億億次級(E級，Exascale)的不斷提升[1 - 3]，微處理器芯片和互連網(wǎng)絡(luò)芯片所需處理的數(shù)據(jù)量呈指數(shù)級上升。通常每個ASIC(Application Specific Integrated Circuit)芯片需要使用多個處理部件對多個輸入數(shù)據(jù)源進行處理，這涉及到多個數(shù)據(jù)隊列的調(diào)度問題。

數(shù)據(jù)隊列調(diào)度的類型和調(diào)度方法有多種分類方式[4 - 6]。按照輸出隊列數(shù)量來分類，有多輸入單輸出調(diào)度、多輸入多輸出調(diào)度；按照服務(wù)質(zhì)量來分類，有優(yōu)先級隊列PQ(Priority Queueing)、公平隊列FQ(Fair Queueing)[7]、加權(quán)公平隊列WFQ(Weighted Fair Queueing)[8 - 10]、加權(quán)循環(huán)調(diào)度WRR(Weighted Round Robin)[11]、差額加權(quán)循環(huán)調(diào)度DWRR(Deficit Weighted Round Robin)[12]、可變加權(quán)循環(huán)調(diào)度VWRR(Variably Weighted Round Robin)[13]、通用循環(huán)調(diào)度URR(Uniform Round Robin)[14]等。對于ASIC芯片片內(nèi)的多輸入多輸出調(diào)度問題，已有的調(diào)度方法存在一定的限制或不足。有的方法僅能完成單輸出的調(diào)度；有的方法不能保證所有輸入數(shù)據(jù)都能夠得到合理的資源，甚至?xí)I死；有的方法無法使高優(yōu)先級的輸入隊列得到優(yōu)先調(diào)度；有的方法由于算法較復(fù)雜而不適合于ASIC芯片邏輯實現(xiàn)。

本文針對高性能計算領(lǐng)域的芯片內(nèi)數(shù)據(jù)傳輸問題，提出一種支持多優(yōu)先級多輸出通道的數(shù)據(jù)隊列調(diào)度方法，用于將多個輸入數(shù)據(jù)源的數(shù)據(jù)流根據(jù)多個輸出隊列的資源占用情況進行科學(xué)調(diào)度，實現(xiàn)公平高效和支持多種服務(wù)等級的任務(wù)分發(fā)。本文方法的主要優(yōu)勢如下：

(1)適用范圍廣。通過調(diào)整配置參數(shù)，該方法既可以實現(xiàn)完全公平均衡的隨機分發(fā)模式，也可以實現(xiàn)多種優(yōu)先級的區(qū)分服務(wù)質(zhì)量的模式。

(2)對于隨機模式，隨機分發(fā)模式下處于空閑狀態(tài)的多個輸出通道將會輪流接收輸入源的輸入數(shù)據(jù)。

(3)對于區(qū)分服務(wù)質(zhì)量模式，所有輸入源、輸出通道被劃分為不同優(yōu)先級，使某組輸出通道只接收對應(yīng)優(yōu)先級的輸入源的數(shù)據(jù)。

(4)硬件實現(xiàn)簡單，代價小。將所有輸出通道的資源狀態(tài)信息整合在同一個仲裁器中，從而使得所有輸入數(shù)據(jù)源只使用一個仲裁器即可實現(xiàn)向所有輸出通道的任務(wù)調(diào)度，適用于ASIC芯片邏輯實現(xiàn)。

2 支持多優(yōu)先級多輸出通道的數(shù)據(jù)隊列調(diào)度方法

通過將所有輸出通道的資源狀態(tài)信息整合在同一個仲裁器中，從而使得所有輸入數(shù)據(jù)源只使用一個仲裁器即可實現(xiàn)向所有輸出通道的任務(wù)調(diào)度。該仲裁器在對多個請求進行仲裁的時候，需要以輸出通道的資源狀態(tài)信息為指導(dǎo)，以決定應(yīng)該將仲裁應(yīng)答返回給哪一個請求，以及該得到應(yīng)答的輸入數(shù)據(jù)應(yīng)該分發(fā)到哪一個輸出通道。對于隨機分發(fā)模式，所有輸出通道的資源狀態(tài)信息將對所有的輸入源有指導(dǎo)意義，處于空閑狀態(tài)的輸出通道將會輪流接收輸入數(shù)據(jù)；對于區(qū)分服務(wù)質(zhì)量的模式，不同的輸出通道具有不同的優(yōu)先級，某一優(yōu)先級的輸出通道的資源狀態(tài)信息只對對應(yīng)優(yōu)先級的輸入源有效，這一輸出通道只接收對應(yīng)優(yōu)先級的輸入源的數(shù)據(jù)。

記輸入數(shù)據(jù)源的數(shù)量為n，n個輸入源依次為{I0,I1,I2,…,In-1}；輸出通道的數(shù)量為m，m個輸出通道依次為{O0,O1,O2,…,Om-1}。根據(jù)控制參數(shù)mode_sel選擇采用隨機分發(fā)模式或區(qū)分服務(wù)質(zhì)量模式進行調(diào)度。控制參數(shù)mode_sel為0時，指示當(dāng)前工作模式為隨機通道模式(Random模式)，即處于空閑狀態(tài)的輸出通道將會輪流接收輸入數(shù)據(jù)；控制參數(shù)mode_sel為1時，指示當(dāng)前工作模式為區(qū)分服務(wù)質(zhì)量QoS(Quality of Service)模式，即所有輸出通道被劃分為多組具有不同優(yōu)先級的通道，每組通道的優(yōu)先級相同，不同組的通道的優(yōu)先級不同，某組輸出通道將只接收對應(yīng)優(yōu)先級的輸入源的數(shù)據(jù)。記共有d個不同的優(yōu)先級，配置參數(shù)priority_vector0用于配置每個輸入數(shù)據(jù)源的優(yōu)先級，依次為{p0,p1,p2,…,pn-1}(其中pi= 0,1,2,…,d-1；i=0,1,2,…,n-1)；配置參數(shù)priority_vector1用于配置每個輸出通道的優(yōu)先級，依次為{q0,q1,q2,…,qm-1}；qi= 0,1,2,…,d-1(其中i=0,1,2,…,m-1)。

2.1 Random模式

將mode_sel控制參數(shù)配置為0，使得所有的輸入數(shù)據(jù)源可以公平地使用所有的輸出通道。記n個輸入源的請求向量為{r0,r1,r2,…,rn-1}，ri為0或1(i=0,1,2,…,n-1)，ri為0時表示第i個輸入源不存在數(shù)據(jù)請求，ri為1時表示第i個輸入源存在數(shù)據(jù)請求，所有存在數(shù)據(jù)請求的輸入源將向一個輪轉(zhuǎn)仲裁器請求使用輸出通道。記m個輸出通道的忙閑狀態(tài)向量為{v0,v1,v2,…,vm-1}，vi為0或1(i=0,1,2,…,m-1)，vi為0時表示第i個輸出通道處于忙碌狀態(tài)，當(dāng)前無法接收新的數(shù)據(jù)處理請求，vi為1時表示第i個輸出通道處于空閑狀態(tài)，此時可以接收新的數(shù)據(jù)處理請求。

輪轉(zhuǎn)仲裁器的仲裁令牌輪轉(zhuǎn)規(guī)則如下：仲裁令牌在完成一次仲裁應(yīng)答后將會傳遞給當(dāng)前得到令牌的輸入源的下一個輸入源，即假設(shè)Ii得到了仲裁應(yīng)答，令牌將會傳遞給I(i+1) mod n。

仲裁應(yīng)答的執(zhí)行規(guī)則如下：如果所有vi均為0，表示所有輸出通道均未空閑，這時所有輸入源都無法得到仲裁應(yīng)答；當(dāng)存在至少一個vi為1時，表示至少有一個輸出通道可以接收數(shù)據(jù)處理請求，假設(shè)此時仲裁令牌在Ii位置，如果ri為1，表示Ii存在數(shù)據(jù)請求，那么Ii將得到仲裁應(yīng)答；如果ri為0，表示Ii不存在數(shù)據(jù)請求，那么依次向后查看Ii+1,Ii+2,Ii+3,…,In-1,I0,I1,Ii-1，Ii之后的第一個存在數(shù)據(jù)請求的輸入源將得到仲裁應(yīng)答。

輸出通道的選擇規(guī)則如下：使用一個輸出通道選擇令牌實現(xiàn)輸出通道的輪轉(zhuǎn)，初始狀態(tài)下，通道選擇令牌在O0上，第一個得到仲裁應(yīng)答的輸入源將數(shù)據(jù)輸出到O0；然后通道選擇令牌會輪轉(zhuǎn)到O1上，以此類推；當(dāng)通道選擇令牌輪轉(zhuǎn)到Oi上時，若vi為1，表示Oi處于空閑狀態(tài)，則當(dāng)前得到仲裁應(yīng)答的輸入源將選擇Oi作為輸出通道；若vi為0，表示Oi未處于空閑狀態(tài)，則當(dāng)前得到仲裁應(yīng)答的輸入源將選擇Oi之后的第一個空閑的輸出通道(如Oi+1空閑，則選擇Oi+1)，同時，通道選擇令牌輪轉(zhuǎn)到下一個輸出通道。

2.2 QoS模式

將mode_sel控制參數(shù)配置為1，使得某一優(yōu)先級的輸出通道的資源狀態(tài)信息只對對應(yīng)優(yōu)先級的輸入源有效，這一輸出通道將只接收對應(yīng)優(yōu)先級的輸入源的數(shù)據(jù)。另外，按照應(yīng)用需求對priority_vector0參數(shù)進行配置，同時對priority_vector1參數(shù)進行配置，目的是使得優(yōu)先級較高的任務(wù)可以得到更多的輸出通道。所有的輸入源仍然僅使用一個仲裁器進行數(shù)據(jù)調(diào)度，但不同優(yōu)先級的輸入源將根據(jù)不同的priority_vector0/1參數(shù)進行區(qū)分。

輪轉(zhuǎn)仲裁器的仲裁令牌輪轉(zhuǎn)規(guī)則與Random模式相同，具體如下：仲裁令牌在完成一次仲裁應(yīng)答后將會傳遞給當(dāng)前得到令牌的輸入源的下一個輸入源，即假設(shè)Ii得到了仲裁應(yīng)答，令牌將會傳遞給I(i+1) mod n。

仲裁應(yīng)答的執(zhí)行規(guī)則如下：如果所有vi均為0，表示所有輸出通道均未空閑，這時所有輸入源都無法得到仲裁應(yīng)答；當(dāng)存在至少一個vi為1時，表示至少有一個輸出通道可以接收數(shù)據(jù)處理請求，假設(shè)此時仲裁令牌在Ii位置，如果ri為1且所有與pi相同的qj對應(yīng)的輸出通道Oj中存在一個空閑通道，即vj=1，這表示Ii存在數(shù)據(jù)請求且支持當(dāng)前優(yōu)先級的輸出通道中存在一個空閑通道，那么Ii將得到仲裁應(yīng)答；如果ri為0，表示Ii不存在數(shù)據(jù)請求，那么依次向后查看Ii+1,Ii+2,Ii+3,…,In-1,I0,I1,Ii-1，直到找到一個Ik符合如下條件：rk為1且所有與pk相同的qk對應(yīng)的輸出通道Ok中存在一個空閑通道，即vk=1，則Ik將得到應(yīng)答。

輸出通道的選擇規(guī)則如下：每組具有相同優(yōu)先級的輸出通道使用各自的輸出通道選擇令牌實現(xiàn)本組內(nèi)輸出通道的輪轉(zhuǎn)；初始狀態(tài)下，每組具有相同優(yōu)先級的輸出通道的通道選擇令牌在該組通道的第一個通道上；當(dāng)該組的某個數(shù)據(jù)源得到仲裁應(yīng)答后，若該組優(yōu)先級的通道選擇令牌所在的輸出通道的vi為1，表示輸出通道Oi處于空閑狀態(tài)，則當(dāng)前得到仲裁應(yīng)答的輸入源將選擇Oi作為輸出通道；若vi為0，表示Oi未處于空閑狀態(tài)，則當(dāng)前得到仲裁應(yīng)答的輸入源將選擇Oi之后的本組內(nèi)的第一個空閑的輸出通道(如Oi+1空閑，則選擇Oi+1)，同時，通道選擇令牌輪轉(zhuǎn)到本組內(nèi)的下一個輸出通道。

3 硬件結(jié)構(gòu)設(shè)計與實現(xiàn)

本文所提出的方法可以應(yīng)用于ASIC芯片內(nèi)的數(shù)據(jù)隊列調(diào)度，滿足ASIC芯片內(nèi)多組輸入數(shù)據(jù)對多個輸出通道資源進行請求的需求。其硬件結(jié)構(gòu)主要由輸入數(shù)據(jù)隊列、輸出數(shù)據(jù)隊列、仲裁器、輸出隊列資源感知邏輯和輸出通道選擇邏輯組成。

對于輸入數(shù)據(jù)隊列，通常為每個輸入通道分配一個輸入數(shù)據(jù)隊列，用于緩存待仲裁的數(shù)據(jù)。

同樣地，對于輸出數(shù)據(jù)隊列，通常為每個輸出通道分配一個輸出數(shù)據(jù)隊列，用于緩存由仲裁器選出的待處理的數(shù)據(jù)。

所有輸入數(shù)據(jù)源只使用一個輪轉(zhuǎn)仲裁器來實現(xiàn)向所有輸出通道的任務(wù)調(diào)度。該仲裁器在對多個請求進行仲裁的時候，需要以輸出通道的資源狀態(tài)信息為指導(dǎo)，以決定應(yīng)該將仲裁應(yīng)答返回給哪一個請求，以及該得到應(yīng)答的輸入數(shù)據(jù)應(yīng)該分發(fā)到哪一個輸出通道。輸出通道的資源狀態(tài)信息通過輸出隊列資源感知邏輯獲取，而得到應(yīng)答的輸入數(shù)據(jù)應(yīng)該分發(fā)到哪一個輸出通道則是由輸出通道選擇邏輯控制。

輸出隊列資源感知邏輯實時對每個輸出隊列的資源使用情況進行計算，并判斷每個輸出隊列是否有足夠的空間來容納得到仲裁的數(shù)據(jù)。當(dāng)數(shù)據(jù)進入某個輸出隊列時，該隊列的資源信用遞減；當(dāng)數(shù)據(jù)從該輸出隊列提取出來進行處理時，該隊列的資源信用遞加。每個隊列的資源信用值作為判斷該隊列是否可用的依據(jù)，當(dāng)前信用值大于待放入的數(shù)據(jù)大小時，即可認為數(shù)據(jù)可以放入該隊列。

輸出通道選擇邏輯在Random模式與QoS模式下有所不同。在Random模式下，將輪轉(zhuǎn)選擇空閑的輸出通道作為最終輸出通道；在QoS模式下，不同優(yōu)先級的數(shù)據(jù)通道各自獨立進行選擇，每個優(yōu)先級對各自空閑的輸出通道進行輪轉(zhuǎn)選擇。

圖1給出了在Random模式下進行數(shù)據(jù)調(diào)度的示意圖。

Figure 1 Illustration of data scheduling in Random mode圖1 Random模式下數(shù)據(jù)調(diào)度示意圖

以10輸入5輸出(即n=10,m=5)的數(shù)據(jù)調(diào)度為例，對Random模式下的數(shù)據(jù)隊列調(diào)度方法進行說明。如圖1所示，初始狀態(tài)下，ri=0(i=0,1,2,…,9)，vj=1(j=0,1,2,3,4)，仲裁器令牌在I0上，通道選擇令牌在O0上，將mode_sel控制參數(shù)配置為0進入Random模式。

(1)T0時刻(仲裁器令牌位于無數(shù)據(jù)請求的輸入源上的情形)，r1,r2,r4變?yōu)?，由于令牌在I0上，但r0為0，因此I1獲得仲裁應(yīng)答，r1在得到應(yīng)答后將變?yōu)?；由于通道選擇令牌在O0上，且v0為1，因此獲得應(yīng)答的I1將選擇O0輸出，v0將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I2上，通道選擇令牌輪轉(zhuǎn)到O1上。

(2)T1時刻(仲裁器令牌位于有數(shù)據(jù)請求的輸入源上的情形)，r2,r4仍在等待輪轉(zhuǎn)仲裁器應(yīng)答，因此r2,r4仍為1，另外，r1由于出現(xiàn)了新的數(shù)據(jù)請求而再次變?yōu)?，r6也因為有數(shù)據(jù)請求而變?yōu)?；由于仲裁器令牌在I2上，且r2為1，因此I2獲得仲裁應(yīng)答，r2在得到應(yīng)答后將變?yōu)?；由于通道選擇令牌在O1上，且v1為1，因此獲得應(yīng)答的I2將選擇O1輸出，v1將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I3上，通道選擇令牌輪轉(zhuǎn)到O2上。

(3)T2時刻(通道選擇令牌位于非空閑的輸出通道上的情形)，經(jīng)過一段時間后，部分輸出通道可能變?yōu)榉强臻e狀態(tài)，假設(shè)此時只有v0,v2為1，另外，r0,r3,r4,r6為1，仲裁器令牌在I7上，通道選擇令牌在O3上；由于r7為0，仲裁器令牌在I7上，因此I0獲得仲裁應(yīng)答，r0在得到應(yīng)答后將變?yōu)?；由于通道選擇令牌在O3上，但v3為0，因此獲得應(yīng)答的I0將選擇下一個空閑的O0輸出，v0將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I1上，通道選擇令牌輪轉(zhuǎn)到O1上。

以此類推，輪轉(zhuǎn)仲裁器持續(xù)進行調(diào)度作業(yè)。

圖2給出了在QoS模式下進行數(shù)據(jù)調(diào)度的示意圖。

Figure 2 Illustration of data scheduling in QoS mode圖2 QoS模式下數(shù)據(jù)調(diào)度示意圖

如圖2所示，初始狀態(tài)下，ri=0(i=0,1,2,…,9)，vj=1(j=0,1,2,3,4)，仲裁器令牌在I0上，通道選擇令牌在O0上。首先將mode_sel控制參數(shù)配置為1以進入QoS模式；其次將priority_vector0配置為{0,0,0,0,0,1,1,1,1,1}，即I0,I1,I2,I3,I4的優(yōu)先級為0,I5,I6,I7,I8,I9的優(yōu)先級為1(假設(shè)共支持2種優(yōu)先級)；然后將priority_vector1配置為{0,0,0,1,1}，即O0,O1,O2可接收優(yōu)先級為0的輸入數(shù)據(jù)，O3,O4可接收優(yōu)先級為1的輸入數(shù)據(jù)。

(1)T0時刻(仲裁器令牌位于無數(shù)據(jù)請求的輸入源上的情形)，r1,r2,r4變?yōu)?，由于令牌在I0上，但r0為0，因此I1獲得仲裁應(yīng)答，r1在得到應(yīng)答后將變?yōu)?；由于I1的優(yōu)先級為0，而優(yōu)先級為0的通道選擇令牌在O0上，且v0為1，因此獲得應(yīng)答的I1將選擇O0輸出，v0將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I2上，優(yōu)先級0的通道選擇令牌輪轉(zhuǎn)到O1上，優(yōu)先級1的通道選擇令牌仍位于O3上。

(2)T1時刻(仲裁器令牌位于有數(shù)據(jù)請求的輸入源上的情形)，r2,r4仍在等待輪轉(zhuǎn)仲裁器應(yīng)答，因此r2,r4仍為1，另外，r1由于出現(xiàn)了新的數(shù)據(jù)請求而再次變?yōu)?，r6也因為有數(shù)據(jù)請求而變?yōu)?；由于仲裁器令牌在I2上，且r2為1，因此I2獲得仲裁應(yīng)答，r2在得到應(yīng)答后將變?yōu)?；由于I2的優(yōu)先級為0，而優(yōu)先級為0的通道選擇令牌在O1上，且v1為1，因此獲得應(yīng)答的I2將選擇O1輸出，v1將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I3上，優(yōu)先級0的通道選擇令牌輪轉(zhuǎn)到O2上，優(yōu)先級1的通道選擇令牌仍位于O3上。

(3)T2時刻(輪轉(zhuǎn)仲裁器應(yīng)答從優(yōu)先級0切換到優(yōu)先級1的情形)，若r1,r4,r6為1，由于仲裁器令牌在I3上，但r3為0，因此I4獲得仲裁應(yīng)答，r4在得到應(yīng)答后將變?yōu)?；由于I4的優(yōu)先級為1，而優(yōu)先級為1的通道選擇令牌在O3上，且v3為1，因此獲得應(yīng)答的I4將選擇O3輸出，v3將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I5上，優(yōu)先級0的通道選擇令牌仍保持在O2上，由于優(yōu)先級1的輸出通道只有O3，因此優(yōu)先級1的通道選擇令牌仍位于O3上。

(4)T3時刻(優(yōu)先級1無通道空閑的情形)，若r1,r6為1，由于仲裁器令牌在I5上，I5的優(yōu)先級為1，而可以接收優(yōu)先級1的輸入請求的輸出通道只有O3，且未處于空閑狀態(tài)，因此r6為1的I6也無法獲得仲裁應(yīng)答，進而，優(yōu)先級為0的I1得到了仲裁應(yīng)答，r1在得到應(yīng)答后將變?yōu)?；由于I1的優(yōu)先級為0，而優(yōu)先級為0的通道選擇令牌在O2上，且v2為1，因此獲得應(yīng)答的I1將選擇O2輸出，v2將變?yōu)?；同時，仲裁器令牌輪轉(zhuǎn)到I2上，優(yōu)先級0的通道選擇令牌輪轉(zhuǎn)到O0上，優(yōu)先級1的通道選擇令牌仍位于O3上。

以此類推，輪轉(zhuǎn)仲裁器持續(xù)進行調(diào)度作業(yè)。

4 實驗結(jié)果

基于該數(shù)據(jù)隊列調(diào)度方法，本文在天河超級計算機系統(tǒng)的網(wǎng)絡(luò)接口芯片中對軟硬件接口數(shù)據(jù)隊列的調(diào)度進行了優(yōu)化，并在軟模擬環(huán)境、硬件仿真環(huán)境以及FPGA驗證環(huán)境中進行了測試。

4.1 實驗場景

在天河超級計算機系統(tǒng)的網(wǎng)絡(luò)接口芯片中，軟件將作業(yè)編譯為大量描述符指令發(fā)送給芯片進行處理。多個線程之間的描述符指令需要通過合理的任務(wù)調(diào)度以達到公平性或?qū)崿F(xiàn)QoS需求。為了實現(xiàn)更高的吞吐率，網(wǎng)絡(luò)接口芯片提供2套描述符處理部件對描述符進行處理。當(dāng)系統(tǒng)不存在QoS需求時，2套處理部件以負載均衡的方式同時工作，可以達到提高系統(tǒng)吞吐率的目的；當(dāng)系統(tǒng)存在QoS需求時，2套部件配置不同的優(yōu)先級，分別接收不同優(yōu)先級的線程的描述符指令，從而為不同的線程提供不同的服務(wù)質(zhì)量。

為了滿足上述需求，將本文提出的支持多優(yōu)先級多輸出通道的數(shù)據(jù)隊列調(diào)度方法應(yīng)用于網(wǎng)絡(luò)接口芯片中。該芯片最大可支持64個線程，即存在64個輸入數(shù)據(jù)隊列，每個數(shù)據(jù)隊列保存對應(yīng)線程的描述符指令；數(shù)據(jù)隊列調(diào)度部件與2套數(shù)據(jù)處理部件之間分別使用1個輸出數(shù)據(jù)隊列進行數(shù)據(jù)緩存，因此共有2個輸出數(shù)據(jù)隊列。仲裁器實現(xiàn)64輸入2輸出的數(shù)據(jù)仲裁。通過寄存器控制接口實現(xiàn)對調(diào)度器工作模式(Random模式或QoS模式)以及優(yōu)先級參數(shù)的配置。數(shù)據(jù)處理邏輯工作頻率為1 GHz。

4.2 多輸出通道與單輸出通道對調(diào)度時間與處理時間的影響

為了評價多輸出通道對描述符事務(wù)處理速度的優(yōu)化效果，本節(jié)分別測試了使用多輸出通道與單輸出通道時的數(shù)據(jù)調(diào)度時間與描述符處理時間，并進行比較。實驗將數(shù)據(jù)調(diào)度部件配置為Random模式。

本文所提出的調(diào)度器硬件設(shè)計方案可以支持對輸出通道的開關(guān)配置，通過寄存器控制接口可以關(guān)閉其中一個輸出通道，將所有數(shù)據(jù)調(diào)度到一套處理部件上進行處理。這種方式可以保證多輸出通道與單輸出通道的處理時間的比較結(jié)果是在同樣的實驗環(huán)境中獲取的，以保證數(shù)據(jù)客觀有效。

首先，為了比較多輸出通道與單輸出通道的數(shù)據(jù)調(diào)度時間，需要構(gòu)建一種測試場景使軟件輸入數(shù)據(jù)的速度為系統(tǒng)的性能瓶頸，這時，處理部件的處理速度足夠快，以至于輸出通道總是處于可用狀態(tài)，從而可以充分反映出多輸出通道與單輸出通道的調(diào)度時間的比較結(jié)果。本文將所有描述符配置為短消息類型，處理部件在收到這種描述符后不需要執(zhí)行DMA(Direct Memory Access)內(nèi)存操作，可以立刻產(chǎn)生數(shù)據(jù)報文并發(fā)送，因此處理速度足夠快，使數(shù)據(jù)調(diào)度部件與處理部件之間的輸出隊列始終可以接收調(diào)度部件輸出的數(shù)據(jù)。圖3給出了64個線程發(fā)送并處理短消息描述符所需的時間與描述符數(shù)量之間的對應(yīng)關(guān)系。執(zhí)行時間從描述符進入數(shù)據(jù)調(diào)度部件的輸入隊列開始計算，到數(shù)據(jù)報文從數(shù)據(jù)處理部件輸出接口發(fā)出為止?？梢钥闯?，當(dāng)系統(tǒng)受限于軟件輸入描述符數(shù)據(jù)的速度時，雙輸出通道與單輸出通道的執(zhí)行時間非常接近。例如，1 024個描述符的單通道和雙通道執(zhí)行時間分別為6 749 ns和6 881 ns，差距為2%；8 192個描述符的單通道和雙通道執(zhí)行時間分別為51 034 ns和51 621 ns，差距為1.2%；262 144個描述符的單通道和雙通道執(zhí)行時間分別為1 114 538 ns和1 117 892 ns，差距為3‰。此時，處理部件處理描述符的時間代價為固定的，且輸出通道始終空閑，可以隨時接收仲裁器的輸出數(shù)據(jù)，這表明雙輸出通道的調(diào)度時間與單輸出通道的調(diào)度時間是基本接近的。該實驗結(jié)果說明，本文提出的多輸出隊列的調(diào)度過程產(chǎn)生的額外時間代價非常小。

Figure 3 Comparison of scheduling time between dual-output-channel and single-output-channel圖3 雙輸出通道與單輸出通道的調(diào)度時間比較

然后，為了驗證多輸出通道在DMA內(nèi)存操作事務(wù)處理方面相對于單輸出通道的提升，進行如下實驗：每個描述符指令對應(yīng)一個DMA內(nèi)存讀取事務(wù)，每個DMA事務(wù)執(zhí)行的內(nèi)存讀取的數(shù)據(jù)量在64 B～819 200 B隨機變化。在該場景下，處理部件需要更多時間來處理每個描述符。通過使用多輸出通道，可以配置多套處理部件對描述符進行處理，從而提高并行性。圖4給出了64個線程發(fā)送并處理DMA類型描述符所需的時間與描述符數(shù)量之間的對應(yīng)關(guān)系。執(zhí)行時間從描述符進入數(shù)據(jù)調(diào)度部件的輸入隊列開始計算，到所有數(shù)據(jù)報文從數(shù)據(jù)處理部件輸出接口發(fā)出為止。可以看出，通過使用雙輸出通道及對應(yīng)的處理部件，DMA事務(wù)的執(zhí)行時間相對于單輸出通道大大減少。例如，1 024個描述符的單通道和雙通道執(zhí)行時間分別為15 943 ns和8 523 ns，比值為1.87；16 384個描述符的單通道和雙通道執(zhí)行時間分別為170 966 ns和90 782 ns，比值為1.88；131 072個描述符的單通道和雙通道執(zhí)行時間分別為1 064 224 ns和534 928 ns，比值為1.99。原因在于雙輸出通道的數(shù)據(jù)調(diào)度部件可以滿足雙處理部件實現(xiàn)并行處理的數(shù)據(jù)調(diào)度需求。該實驗結(jié)果說明，本文提出的多輸出隊列調(diào)度方案對于提升芯片處理事務(wù)的速度具有顯著作用。

Figure 4 Performance improvement for DMA transactions with dual-output-channel圖4 雙輸出通道對DMA內(nèi)存事務(wù)的性能優(yōu)化

4.3 多優(yōu)先級對服務(wù)質(zhì)量的影響

為了評價本文工作中的多優(yōu)先級調(diào)度方式對服務(wù)質(zhì)量的影響，進行如下實驗：將64個線程分為2組，16個線程配置為較高的優(yōu)先級0，另外48個線程配置為較低的優(yōu)先級1。優(yōu)先級0的線程使用0號輸出通道，優(yōu)先級1的線程使用1號輸出通道。每個線程發(fā)送并處理相同數(shù)量的DMA內(nèi)存讀取描述符，每個描述符所處理的DMA內(nèi)存數(shù)據(jù)大小固定為1 024 B。實驗時，數(shù)據(jù)調(diào)度部件配置為QoS模式。

圖5給出了0號通道與1號通道的執(zhí)行時間比較結(jié)果。執(zhí)行時間從描述符進入數(shù)據(jù)調(diào)度部件的輸入隊列開始計算，到所有數(shù)據(jù)報文從數(shù)據(jù)處理部件輸出接口發(fā)出為止?？梢钥闯?，16個高優(yōu)先級的線程使用單獨的輸出通道與處理部件，執(zhí)行時間遠低于另外48個低優(yōu)先級使用另一組輸出通道的執(zhí)行時間。例如，1 024個描述符(每個線程發(fā)送16個描述符)的0號高優(yōu)先級通道和1號低優(yōu)先級通道的執(zhí)行時間分別為1 583 ns和4 601 ns，比值為1∶2.9；32 768個描述符的0號高優(yōu)先級通道和1號低優(yōu)先級通道的執(zhí)行時間分別為35 796 ns和100 426 ns，比值為1∶2.8；262 144個描述符的0號高優(yōu)先級通道和1號低優(yōu)先級通道的執(zhí)行時間分別為275 670 ns和745 172 ns，比值為1∶2.7。該實驗結(jié)果說明，本文提出的多優(yōu)先級多輸出隊列調(diào)度方案可以實現(xiàn)對不同線程的服務(wù)質(zhì)量的區(qū)分。

Figure 5 Comparison of execution time between different priority groups in dual-output-channel QoS mode圖5 QoS模式下雙輸出通道的執(zhí)行時間對比

4.4 資源使用情況

為了評價本文的多優(yōu)先級多輸出通道調(diào)度器的硬件實現(xiàn)代價，本節(jié)將其與單輸出通道的調(diào)度器進行了硬件資源情況比較。資源比較工作在自主開發(fā)的FPGA驗證平臺上進行，F(xiàn)PGA采用Xilinx Virtex UltraScale VU440芯片。

表1給出了64輸入2輸出調(diào)度器與64輸入1輸出調(diào)度器的邏輯資源(FPGA芯片的查找表LUT使用情況)統(tǒng)計對比情況；表2給出了64輸入2輸出調(diào)度器與64輸入1輸出調(diào)度器的寄存器資源統(tǒng)計對比情況。所統(tǒng)計的硬件資源主要包括輸入數(shù)據(jù)隊列、輸出數(shù)據(jù)隊列、仲裁器、輸出隊列資源感知邏輯、輸出通道選擇邏輯等部分，處理部件不包含在統(tǒng)計范圍內(nèi)。結(jié)果表明，增加輸出通道需要增加的硬件資源主要包括輸出數(shù)據(jù)隊列所增加的寄存器資源、輸出隊列資源感知邏輯與輸出通道選擇邏輯所需要的邏輯資源，而仲裁器本身并不需要增加新的資源。所增加的寄存器資源和邏輯資源僅占整個調(diào)度器邏輯的一小部分，雙輸出通道與單輸出通道相比所增加的邏輯資源為583，只比單輸出通道的總邏輯資源多1.5%；雙輸出通道與單輸出通道相比所增加的寄存器邏輯資源為286，只比單輸出通道的總邏輯資源多1.4%。

Table 1 Comparison of logic resources between dual-output-channel and single-output-channel表1 雙輸出通道與單輸出通道調(diào)度器的邏輯資源(LUT占用情況)對比

Table 2 Comparison of register resources between dual-output-channel and single-output-channel表2 雙輸出通道與單輸出通道調(diào)度器的寄存器資源對比

5 結(jié)束語

本文針對高性能計算領(lǐng)域的芯片內(nèi)數(shù)據(jù)傳輸問題，提出了一種支持多優(yōu)先級多輸出通道的數(shù)據(jù)隊列調(diào)度方法，用于將多個輸入數(shù)據(jù)源的數(shù)據(jù)流根據(jù)多個輸出隊列的資源占用情況進行科學(xué)調(diào)度，實現(xiàn)公平高效和支持多種服務(wù)等級的任務(wù)分發(fā)。所提出的方法適用范圍廣，可以通過調(diào)整配置參數(shù)，使之工作在Random模式或QoS模式下，將該方法應(yīng)用于ASIC芯片設(shè)計時具有硬件實現(xiàn)代價低的優(yōu)勢?；谠摂?shù)據(jù)隊列調(diào)度方法，在天河超級計算機系統(tǒng)的網(wǎng)絡(luò)接口芯片中對軟硬件接口數(shù)據(jù)隊列的調(diào)度進行了優(yōu)化，并進行了實際測試。實驗結(jié)果表明，所實現(xiàn)的多輸出隊列調(diào)度器與傳統(tǒng)的單輸出隊列調(diào)度器相比并未產(chǎn)生額外的時間代價；多輸出隊列調(diào)度方案對于提升芯片處理事務(wù)的速度具有顯著作用；同時，配置為QoS模式時可以實現(xiàn)對不同線程的服務(wù)質(zhì)量的區(qū)分，且為靈活可配置的；另外，多優(yōu)先級多輸出通道的仲裁器硬件實現(xiàn)與單輸出通道的仲裁器實現(xiàn)相比，并未增加明顯的硬件實現(xiàn)代價。