[發(fā)明專利]面向多源多核系統(tǒng)的基于超任務(wù)網(wǎng)的多核調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710026904.5
• 申請(qǐng)日: 2017-01-15
• 公開（公告）號(hào): CN107329822B
• 公開（公告）日: 2022-01-28
• 發(fā)明（設(shè)計(jì)）人: 齊德昱;周娜琴;沈陽(yáng);郭靖;張長(zhǎng)建;李雯霖
• 申請(qǐng)（專利權(quán)）人: 齊德昱
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種面向相關(guān)任務(wù)集的多源多核系統(tǒng)調(diào)度方法，其特征在于，將相關(guān)任務(wù)集的到執(zhí)行機(jī)構(gòu)的映射工作分為“相關(guān)任務(wù)集排序”與“執(zhí)行機(jī)構(gòu)映射”兩個(gè)階段；第一階段為相關(guān)任務(wù)集排序階段，進(jìn)行超任務(wù)網(wǎng)的構(gòu)造,將任務(wù)集組織為描述直接與間接相關(guān)性的超任務(wù)網(wǎng)，并在調(diào)度中動(dòng)態(tài)將其調(diào)整為一個(gè)空行度最小的超任務(wù)網(wǎng)；第二階段為執(zhí)行機(jī)構(gòu)映射階段，進(jìn)行虛擬核構(gòu)造，將當(dāng)前空行度最小的超任務(wù)網(wǎng)映射到多源多核系統(tǒng)上執(zhí)行，并當(dāng)物理核數(shù)目少于實(shí)際需求時(shí)進(jìn)行空載度最小的共享；這里，多源多核系統(tǒng)是指集成了多核CPU、多CPU或多主機(jī)上的處理器核，對(duì)外形成一個(gè)多核處理器界面；多源多核系統(tǒng)中的核，可以是對(duì)稱的也可以是非對(duì)稱的；任務(wù)集是可以分配到多核處理器上執(zhí)行的任務(wù)的集合；其中，超任務(wù)網(wǎng)HTW是一種超網(wǎng)絡(luò)，描述任務(wù)集當(dāng)前任務(wù)的直接相關(guān)性與間接相關(guān)性；超任務(wù)網(wǎng)由任務(wù)網(wǎng)生成；任務(wù)網(wǎng)是一種圖，描述任務(wù)集中任務(wù)的直接相關(guān)性；空行度用于描述一個(gè)相關(guān)任務(wù)集中，各個(gè)任務(wù)之間的因?yàn)橄嚓P(guān)性而造成的總的等待時(shí)間；一個(gè)任務(wù)集分配到物理核后，空行度就表示空載度，最佳核共享基于空載度獲取。

2.如權(quán)利要求1所述面向相關(guān)任務(wù)集的多源多核系統(tǒng)調(diào)度方法，所述的相關(guān)任務(wù)集排序與執(zhí)行機(jī)構(gòu)映射兩個(gè)階段，基于核心操作與核心數(shù)據(jù)結(jié)構(gòu)進(jìn)行；基于的核心數(shù)據(jù)結(jié)構(gòu)包括任務(wù)網(wǎng)TW、超任務(wù)網(wǎng)HTW、超任務(wù)序列HTS、核共享圖CM；超任務(wù)序列HTS是HTW的序列化，描述任務(wù)的當(dāng)前分配次序；核共享圖CM描述當(dāng)前任務(wù)到多源多核系統(tǒng)的映射關(guān)系；CM有兩種節(jié)點(diǎn)：任務(wù)節(jié)點(diǎn)和核節(jié)點(diǎn)，相應(yīng)的有兩種弧：任務(wù)節(jié)點(diǎn)到核節(jié)點(diǎn)的弧和核節(jié)點(diǎn)之間的弧；如果任務(wù)T分配在核C上，則T到C有弧，弧權(quán)為T的完成所需剩余時(shí)間；如果核C1當(dāng)前執(zhí)行的任務(wù)需要等待到核C2當(dāng)前執(zhí)行的任務(wù)的完成，則C1到C2有弧，弧權(quán)為等待時(shí)間；虛擬核的構(gòu)造，當(dāng)存在空閑核是直接分配空閑核，并且將所分配的核加入到CM，否則，從CM選擇核共享。

3.如權(quán)利要求1或2所述的面向相關(guān)任務(wù)集的多源多核系統(tǒng)調(diào)度方法，其中，任務(wù)網(wǎng)TW的節(jié)點(diǎn)集是任務(wù)集,弧集是節(jié)點(diǎn)集中的所有的具有直接相關(guān)性的節(jié)點(diǎn)間的弧；TW定義了兩種節(jié)點(diǎn)權(quán)，分別是耗時(shí)權(quán)與等待權(quán)；耗時(shí)權(quán)定義節(jié)點(diǎn)的執(zhí)行所需的時(shí)間長(zhǎng)度，等待權(quán)定義了兩個(gè)相關(guān)節(jié)點(diǎn)間執(zhí)行所需的等待時(shí)間；一個(gè)任務(wù)網(wǎng)TW的超任務(wù)網(wǎng)HTW定義在當(dāng)前時(shí)段中的描述任務(wù)資源競(jìng)爭(zhēng)關(guān)系的任務(wù)競(jìng)爭(zhēng)劃分上，它的節(jié)點(diǎn)集是相應(yīng)的劃分的各個(gè)劃分集，弧表示兩個(gè)劃分集之間的直接相關(guān)關(guān)系；同一個(gè)劃分集中的節(jié)點(diǎn)是當(dāng)前時(shí)段的競(jìng)爭(zhēng)同一種資源的任務(wù)；超任務(wù)網(wǎng)的形式化定義為一個(gè)任務(wù)網(wǎng)TN=(T,V,c,w)的生成網(wǎng)TNH =(TH,A,wh),其中，T為當(dāng)前任務(wù)集；V為定義在T上的二元關(guān)系；c為定義在T上的函數(shù)，w是定義在V上的函數(shù),TH 為節(jié)點(diǎn)集，稱為超節(jié)點(diǎn)，A為弧集，稱為超弧，它們滿足：1）TH = {T1, T2,…, Tn},Tií T，i=1,2, …, n，T1∪T2∪…∪Tn = T, 且若ti , tj? Tr ，則稱ti與 tj競(jìng)爭(zhēng)資源r；2）如果Ti ,Tj ?TH, 那么e = Ti , Tj ?A 當(dāng)且僅當(dāng)存在一個(gè)v ? V，v=a, b，a ?Ti ，b? Tj, i, j ? {1,…n}, i≠j, 稱e為Ti 到Tj的割邊；3）wh(Tj ) = Max{w(a,b)| i, Ti , Tj ?A ; a, b, a? Ti, b ?Tj}；所述空行度，定義為e(t)，其中t為一個(gè)任務(wù)，滿足：1）e(t) = Max{ w(t, s ) | s, t, s?A }：當(dāng)t無(wú)前驅(qū)時(shí)；2）e(t) = Max{ e(p)+w(p,t) | p, p, t?A } +Max{ w(t, s ) | s, t, s?A } ：其他情況；如果任務(wù)網(wǎng)被分配到處理核上執(zhí)行，則任務(wù)的空行度就稱為空載度。