一種片上網絡任務調度方法及裝置與流程
2023-11-30 16:30:36 3
本發明涉及電子技術領域，具體而言，涉及一種片上網絡任務調度方法及裝置。
背景技術：
隨著當今社會信息技術的高速發展，掌上智能終端、自動化控制以及大數據計算處理等眾多應用領域對集成電路片上系統的功能和性能提出了更高的要求，多核片上系統的集成度大幅提高，致使極大地增加了片上系統的複雜度及實現難度。高性能多核片上系統的發展趨勢必然是片上網絡的發展及應用。
片上網絡借鑑了計算機網際網路的結構，解決了片上系統傳統總線結構的通信瓶頸問題。但是片上網絡的任務調度是典型的NP問題，具有較高的時間複雜度，需要同時考慮通信功耗及通信時間等性能指標。目前所採用的調度方法主要的是傳統的進化思想，對交叉率、變異率等參數的依賴性強，且上述參數的選擇大多是依靠經驗選取。另外，傳統的進化思想還存在對初始種群的選擇具有一定的依賴性，調度方案易陷入局部最優以及進化算法的並行機制未得到充分利用等缺陷。
技術實現要素：
有鑑於此，本發明的目的在於提供一種片上網絡任務調度方法及裝置，以改善上述問題。
本發明實施例提供一種片上網絡任務調度方法，該方法包括：
根據片上網絡的任務圖以及各任務之間的執行關係進行任務分組，其中，所述執行關係包括並行關係和偏序關係；
生成初始種群，該初始種群包括多個部落，每個部落由與任務分組後得到的所有任務組一一對應的量子染色體構成，不同部落解碼後對應不同的調度方案；
基於量子進化算法及預先設定的用于衡量調度方案性能指標的適應度函數對所述初始種群進行進化迭代，得到最優的調度方案，所述性能指標包括通信功耗及通信時間；
根據所述最優的調度方案，將各個任務組調度到對應的處理核。
本發明另一實施例提供一種片上網絡任務調度裝置，該裝置包括：
任務分組模塊，用於根據片上網絡的任務圖以及各任務之間的執行關係進行任務分組，其中，所述執行關係包括並行關係和偏序關係；
種群生成模塊，用於生成初始種群，該初始種群包括多個部落，每個部落由與任務分組後得到的所有任務組一一對應的量子染色體構成，不同部落解碼後對應不同的調度方案；
進化迭代及調度方案生成模塊，用於基於量子進化算法及預先設定的用于衡量調度方案性能指標的適應度函數對所述初始種群進行進化迭代，得到最優的調度方案，所述性能指標包括通信功耗及通信時間；
任務調度模塊，根據所述最優的調度方案，將各個任務組調度到對應的處理核。
本發明實施例提供的片上網絡任務調度方法及裝置，根據各任務之間的執行關係進行任務分組後，基於量子進化算法及以優化通信功耗和通信時間為目標進行任務調度，減少了調度結果對進化參數及初始種群的依賴性，充分利用了量子進化的並行機制，最終獲得滿足優化性能指標的最優調度方案。
附圖說明
為了更清楚地說明本發明實施例的技術方案，下面將對實施例中所需要使用的附圖作簡單地介紹，應當理解，以下附圖僅示出了本發明的某些實施例，因此不應被看作是對範圍的限定，對於本領域普通技術人員來講，在不付出創造性勞動的前提下，還可以根據這些附圖獲得其他相關的附圖。
圖1為本發明實施例提供的一種智能設備的方框示意圖；
圖2為本發明實施例提供的一種片上網絡任務調度方法的流程圖；
圖3為本發明實施例提供的實驗用例中片上網絡任務圖的示意圖；
圖4為片上網絡為4行4列時的任務調度結果示意圖；
圖5為片上網絡為3行3列時的任務調度結果示意圖；
圖6為本發明實施例提供的一種片上網絡任務調度裝置的功能模塊框圖。
圖標：100-智能設備；110-片上網絡任務調度裝置；120-存儲器；130-處理器；1102-任務分組模塊；1104-種群生成模塊；1106-進化迭代及調度方案生成模塊；1108-任務調度模塊。
具體實施方式
為使本發明實施例的目的、技術方案和優點更加清楚，下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例是本發明一部分實施例，而不是全部的實施例。因此，以下對在附圖中提供的本發明的實施例的詳細描述並非旨在限制要求保護的本發明的範圍，而是僅僅表示本發明的選定實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬於本發明保護的範圍。
如圖1所示，是本發明實施例提供的一種可應用片上網絡任務調度方法的智能設備100的方框示意圖。所述智能設備100可以是，但不限於，PC機、智慧型手機、伺服器等。該智能設備100包括片上網絡任務調度裝置110、存儲器120以及處理器130。
所述存儲器120與處理器130之間可通過一條或多條通訊線路或信號線實現電性連接。所述片上網絡任務調度裝置110包括至少一個可以軟體或固件的形式存儲於所述存儲器120中或固化在所述智能設備100的作業系統中的軟體功能模塊。所述處理器130用於執行所述存儲器120中存儲的可執行模塊，例如所述片上網絡任務調度裝置110所包括的軟體功能模塊及電腦程式等。
如圖2所示，是本發明實施例提供的一種片上網絡任務調度方法的流程圖。所應說明的是，本發明提供的方法不以圖2及以下所述的具體順序為限制。下面將對圖2所示的各步驟進行詳細闡述。
步驟S101，根據片上網絡的任務圖以及各任務之間的執行關係進行任務分組。
本實施例中，所述執行關係包括並行關係和偏序關係。所述並行關係是指兩個任務之間不存在通信依賴，可以被並行執行。所述偏序關係是指兩個任務之間存在通信依賴，執行順序需要分先後。
所述片上網絡的任務圖為有向無環圖。基於該任務圖及任務之間的執行關係進行分組的過程包括如下子步驟：
子步驟S1：選擇所述任務圖中任意一個無前驅結點的任務結點作為起始結點，判斷該起始結點是否存在直接後繼結點，若存在，則沿一條包括所述起始結點的分支順位選擇至少一個後繼結點作為該起始結點的同組任務結點，若不存在，則直接將該起始結點獨立地作為一個任務分組。
子步驟S3：在所述任務圖中對已完成分組的任務結點進行標記，並將尚未被標記的各個任務結點構成的任務圖作為新的任務圖。
以及子步驟S5：基於得到的所述新的任務圖，重複執行步驟S1和S3，直至最初始的任務圖中的所有任務結點已全部被標記。
更進一步地，該方法在進行任務分組前，還預先設定有一用於控制所述任務組包含的任務總數的熱點閾值，以防止任務組包括過多任務時，造成晶片過熱點的產生，致使系統性能不穩定。由此，所述子步驟S1中沿分支構建任務路徑時，所選擇的後繼結點的數目應小於或等於所述熱點閾值。
此外，當在執行所述子步驟S1時，若起始結點存在多個直接後繼結點，則優選具有最大通信量的任務結點作為該起始結點的同組任務結點，然後再在所選擇的任務結點的所有直接後繼結點中繼續選擇具有最大通信量的任務結點作為所述起始結點的同組任務結點，如此下去，直至順位選擇的任務結點數目達到所述熱點閾值或者所有結點都已經被分組完畢。
由上述的描述可以看出，基於有向無環的片上網絡任務圖及任務之間的執行關係進行任務分組時，應從沒有前驅的任務結點開始，沿著一條分支選擇後繼任務結點，構建一條到達葉子任務結點的任務路徑。在構建過程中，只能選擇還未被其他路徑構建過的任務結點。並且如果當前的任務結點存在多個可選分支，則優選通信流量大、通信功耗或者通信時延長等有利於進行性能優化的分支。另外，在每選擇一個新的結點構建任務路徑時，應判斷是否達到預先設置的熱點閥值，若已達到，則結束當前任務路徑的構建，並將該路徑上所包含的任務結點分配至同一任務組。
步驟S103，生成初始種群，該初始種群包括多個部落，每個部落由與任務分組後得到的所有任務組一一對應的量子染色體構成。
本實施例中，生成初始種群的過程為，首先對任務組及所述片上網絡中的處理核進行編號。其中，對任務組進行編號時可以是但不限於，依照每個任務組的構建順序進行依次標號；對處理核進行編號時可以是但不限於，依照每個處理核的位置進行依次編號。
然後，針對各個任務組分別進行概率幅度編碼，生成與該任務組對應的量子染色體。所有的量子染色體構成一個部落。其中，該部落中與第i個任務組對應的量子染色體表示為：
αij表示第i個任務組被調度至第j個處理核的概率幅度，βij表示第i個任務組未被調度至第j個處理核的概率幅度，|αij|2+|βij|2＝1，
i＝1,2…n，j＝1,2…m。其中，n表示任務組的總數目，m表示所述片上網絡中的處理核的總數目。
按照上述生成部落的方法不斷重複，直至生成的部落總數達到預定個數後，將已生成的所有部落構成所述初始種群。
步驟S105，基於量子進化算法及預先設定的用于衡量調度方案性能指標的適應度函數對所述初始種群進行進化迭代，得到最優的調度方案。所述性能指標包括通信功耗及通信時間。
本實施例中，基於所述初始種群進行進化迭代得到最優調度方案的具體過程包括，首先對所述初始種群中的各個部落分別進行解碼，得到每個部落對應的調度方案。
其中，對所述部落進行解碼的方式為，獲取該部落的每個量子染色體中的各個量子位的狀態。然後按照任務組編號，依次針對每個量子染色體將其中所有狀態為1的量子位對應的處理核都納入第一備選處理核集，並將第一備選處理核集中未被標記過的且具有最大概率幅度的處理核標記為該量子染色體對應的任務組所應被調度到的目標處理核。若當前的量子染色體中不存在狀態為1的量子位或者所述第一備選處理核集中的元素已全部被標記過時，則將該量子染色體中所有狀態為0的量子位對應的處理核都納入第二備選處理核集，然後將第二備選處理核集中未被標記過的且具有最大概率幅度的處理核標記為該量子染色體對應的任務組所應被調度到的目標處理核。
其次，按照預先設定的適應度函數計算出每個調度方案的性能指標，並根據所述性能指標以非支配排序算法確定當前的最優調度方案。
本實施例中，所述適應度函數包括計算通信功耗的第一函數以及計算通信時間的第二函數。所述第一函數為:
Power＝Σ1≤i,j≤m(Plink*hopi,j+Pswitch*(hopi,j+1))
其中，i和j表示具有通信依賴關係的兩個處理核的編號。m表示處理核的總數目。hopij表示兩個處理核i和j之間的通信路徑所經歷的鏈路條數，即跳數。Plink表示每條通信鏈路上的功耗。Pswitch表示每個交換結點的功耗。此處採用的Plink和Pswitch兩個功耗參數值來自於R.Das等人在文獻「Design and evaluation of a hierarchical on-chipinterconnect for next-generation CMPs」和「Optimizing NUCA organizations andwiring alternatives for large caches with CACTI 6.0」中提出的模型，是與通信流量相關的函數。
所述第二函數為：
Time＝∑1≤i,j≤m(Tlink*hopi,j+Tswitch*(hopi,j+1))
其中，Tlink表示每一條通信鏈路上傳輸數據的時間。Tswitch表示在一個交換結點中路由緩存排隊的時間。Tlink和Tswitch的參數值來自於N.Muralimanohar等人在文獻「Optimizing NUCA organizations andwiring alternatives for large caches with CACTI 6.0」和「A delay optimal coterie on the k-dimensional folded Petersengraph」中提出的模型，同樣是與通信流量相關的函數。
再次，判斷當前是否已滿足預先設定的迭代終止條件。若滿足，則終止迭代，輸出所述最優調度方案。若不滿足，則選擇預定個數的性能指標最高的調度方案所對應的部落組成精英團，並採用量子旋轉門對位於所述精英團以外的所有滿足預設更新條件的部落中的每個量子染色體進行更新。所述量子旋轉門表示為：
其中，表示待更新的部落中第p個任務組所對應的量子染色體中的第q個量子位。表示更新後的量子位。θ為根據當前的最優調度方案所對應的部落與該待更新的部落之間的性能指標之差確定的旋轉角，該旋轉角的方向由待更新的量子位的概率幅度確定。
本實施例中，所述迭代終止條件可以是達到預先設定的迭代終止次數時，則終止進化迭代。所述更新條件可以是大於預先設定的一性能指標閾值。此外，所述旋轉角的方向確定方式可以是但不限於，當αpq>βpq時設置為正方向，反之設置為反方向。
最後，將更新後的部落與所述精英團共同構成新的種群，並基於該新的種群繼續進行進化迭代，直至滿足迭代終止條件後，輸出當前的最優調度方案。
步驟S107，根據所述最優的調度方案，將各個任務組調度到對應的處理核。
下面示例性的舉出一實驗用例，以更進一步詳細的闡述本實施例提供的片上網絡任務調度方法。如圖3所示，是本實驗用例中的片上網絡任務圖。圖中結點表示任務結點。兩任務結點之間連線上的數字表示通信流量。
基於該任務圖進行分組時，預先設定所述熱點閾值為3，即每個任務組最多包含3個任務結點。然後，選擇不存在直接前驅的任務結點，按照偏序關係，沿著結點分支，依次選擇歸於同一分組的任務結點，直至當任務結點數目超過熱點閥值時終止該次分組。在所述任務圖中除去已完成分組的任務結點後，再重新選擇不存在直接前驅的任務結點開始新一輪任務分組。按此方法，圖3所示的任務圖中的任務被分為8個組，分組情況如下：
組1：0,2,7；組2：1,5,11；組3：3,8,14；組4：4,9,15；
組5：6,12,17；組6：10,16,19；組7：13,18,20；組8:21。
根據構建路徑的結點順序，可以得到任務的調度順序，如表1所示：
表1任務調度順序表
完成上述任務分組後，根據量子進化思想將8個任務組調度至片上網絡的處理核上。本實施例中，採用4行4列的片上網絡，處理核總數為16個。預定生成部落總個數為100，即初始種群包含100個進化部落。設置迭代總次數100次，每代選擇10個性能指標最高的部落構成精英團。每個部落的8個任務組分別進行量子染色體編碼，初始編碼值隨機產生，例如第k個部落Tk中的8個任務組分別對應的8條量子染色體編碼為：
對初始種群的每個部落中的量子染色體進行解碼。每個部落的量子染色體解碼後都得到任務組的一種調度方案。例如上述部落Tk的量子染色體進行解碼，觀察量子染色體的每個量子位的狀態。以第一條染色體Ck1為例，觀察其狀態值為(0,1,1,0,0,1,0,1,1,0,1,1,0,0,0,1)。在量子位取值為1的位序所對應的處理核，即編號為2,3,6,8,9,11,12,16的處理核中選擇還沒有被調度的並且概率幅度值最大的處理核，作為第一個任務組的調度核。以此方法對部落Tk中的其他染色體進行解碼，得到其他任務組的調度核。據此得到部落Tk對應的一種調度方案為：任務組1調度到處理核2，任務組2調度到處理核5，任務組3調度到處理核1，任務組4調度到處理核3，任務組5調度到處理核12，任務組7調度到處理核9，任務組8調度到處理核13。按照此方法對其他部落的染色體進行解碼，得到相應的調度方案，因為設置了100個部落，故可以得到100種調度方案。
根據預先設定的適應度函數計算每一種方案的性能指標，作為評價調度方案的適應度的依據。然後通過非支配排序從中選出最優的方案標記為最優調度方案。並且根據性能指標選取適應度從高到低的10個方案納入精英團。精英團對應的量子染色體自動進入下一輪進化迭代。判斷當前迭代次數是否大於預設值100，如果大於100，則終止進化，輸出當前獲得的最優調度方案，如果小於100，則繼續進行下一次進化迭代。
繼續進行進化迭代時，需要進行量子染色體的更新。根據量子染色體適應度大小，對滿足更新條件的染色體，參考最優調度方案中的染色體對應的量子位進行更新，更新公式如下：
例如當前量子染色體為最優調度方案中的第i條染色體為根據染色體Di和Bi適應度差值，調整旋轉門的角度θ。θ的方向根據量子位的概率幅度進行選取，例如Bi的第1個量子位概率幅度是αi1>βi1，則旋轉角θ為正。帶入更新公式計算，得到更新後的染色體為：
更新後的量子染色體向最優染色體趨近，但是又不完全等同最優染色體，如此在逐漸優化的同時，也避免了陷入過早收斂。
根據上述過程，在進化迭代結束後得到的任務組的最優調度方案如圖4所示。該方案所得通信功耗為1.4058e-06J，通信時間為4.0837e-04ms。若採用3行3列的片上網絡結構，得到的最優調度方案如圖5所示。該方案的通信功耗為1.4297e-06J，通信時間為4.2597e-04ms。
如圖6所示，是本發明實施例提供的一種片上網絡任務調度裝置110的功能模塊框圖。該裝置包括任務分組模塊1102、種群生成模塊1104、進化迭代及調度方案生成模塊1106以及任務調度模塊1108。
所述任務分組模塊1102，用於根據片上網絡的任務圖以及各任務之間的執行關係進行任務分組，其中，所述執行關係包括並行關係和偏序關係。
所述種群生成模塊1104，用於生成初始種群，該初始種群包括多個部落，每個部落由與任務分組後得到的所有任務組一一對應的量子染色體構成，不同部落解碼後對應不同的調度方案。
所述進化迭代及調度方案生成模塊1106，用於基於量子進化算法及預先設定的用于衡量調度方案性能指標的適應度函數對所述初始種群進行進化迭代，得到最優的調度方案，所述性能指標包括通信功耗及通信時間。
所述任務調度模塊1108，根據所述最優的調度方案，將各個任務組調度到對應的處理核。
本實施例提供的各功能模塊的具體操作方法可參照上述方法實施例中各對應步驟的詳細描述，在此不再一一贅述。
在本申請所提供的幾個實施例中，應該理解到，所揭露的裝置和方法，也可以通過其它的方式實現。以上所描述的裝置實施例僅僅是示意性的，例如，附圖中的流程圖和框圖顯示了根據本發明的多個實施例的裝置、方法和電腦程式產品的可能實現的體系架構、功能和操作。在這點上，流程圖或框圖中的每個方框可以代表一個模塊、程序段或代碼的一部分，所述模塊、程序段或代碼的一部分包含一個或多個用於實現規定的邏輯功能的可執行指令。也應當注意，在有些作為替換的實現方式中，方框中所標註的功能也可以以不同於附圖中所標註的順序發生。例如，兩個連續的方框實際上可以基本並行地執行，它們有時也可以按相反的順序執行，這依所涉及的功能而定。也要注意的是，框圖和/或流程圖中的每個方框、以及框圖和/或流程圖中的方框的組合，可以用執行規定的功能或動作的專用的基於硬體的系統來實現，或者可以用專用硬體與計算機指令的組合來實現。
另外，在本發明各個實施例中的各功能模塊可以集成在一起形成一個獨立的部分，也可以是各個模塊單獨存在，也可以兩個或兩個以上模塊集成形成一個獨立的部分。
所述功能如果以軟體功能模塊的形式實現並作為獨立的產品銷售或使用時，可以存儲在一個計算機可讀取存儲介質中。基於這樣的理解，本發明的技術方案本質上或者說對現有技術做出貢獻的部分或者該技術方案的部分可以以軟體產品的形式體現出來，該計算機軟體產品存儲在一個存儲介質中，包括若干指令用以使得一臺計算機設備(可以是個人計算機，伺服器，或者網絡設備等)執行本發明各個實施例所述方法的全部或部分步驟。需要說明的是，在本文中，諸如第一和第二等之類的關係術語僅僅用來將一個實體或者操作與另一個實體或操作區分開來，而不一定要求或者暗示這些實體或操作之間存在任何這種實際的關係或者順序。而且，術語「包括」、「包含」或者其任何其他變體意在涵蓋非排他性的包含，從而使得包括一系列要素的過程、方法、物品或者設備不僅包括那些要素，而且還包括沒有明確列出的其他要素，或者是還包括為這種過程、方法、物品或者設備所固有的要素。在沒有更多限制的情況下，由語句「包括一個……」限定的要素，並不排除在包括所述要素的過程、方法、物品或者設備中還存在另外的相同要素。
應注意到：相似的標號和字母在上面的附圖中表示類似項，因此，一旦某一項在一個附圖中被定義，則在隨後的附圖中不需要對其進行進一步定義和解釋。
以上所述，僅為本發明的具體實施方式，但本發明的保護範圍並不局限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易想到變化或替換，都應涵蓋在本發明的保護範圍之內。因此，本發明的保護範圍應以所述權利要求的保護範圍為準。