[發明專利]一種面向多核平臺的多線程劃分及靜態均衡調度方法

有效

• 申請號: 201610022466.0
• 申請日: 2016-01-13
• 公開（公告）號: CN105700959B
• 公開（公告）日: 2019-02-26
• 發明（設計）人: 付雄;湯中睿;鄧松;程春玲;王俊昌
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F9/48
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 田凌濤

1.一種面向多核平臺的多線程劃分及靜態均衡調度方法，其特征在于,包括如下步驟：

步驟001.初始化系統各線程上所對應的負載G_load_m＝0，G_load_m表示系統第m個線程上所對應的負載，m＝{1,…,M}，M表示系統線程的數量；然后針對待處理任務進行劃分，獲得計算邏輯相互獨立的各個任務塊，構成任務塊集合，并且各個任務塊不可進一步劃分，并進入步驟002；

步驟002.針對任務塊集合，獲取各個任務塊的計算時間，分別作為對應任務塊的粒度值，并進入步驟003；

步驟003.獲得任務塊集合中所有任務塊粒度值所對應的粒度平均值，并判斷粒度平均值是否小于等于預設粒度平均值，是則將任務塊集合中所有任務塊所對應的待處理任務，任意分配至其中一個線程上，由該線程針對該待處理任務進行串行處理，針對該待處理任務的調度策略結束；否則進入步驟004；

步驟004.根據任務塊集合中所有任務塊粒度值所對應的粒度平均值，獲得任務塊集合中所有任務塊粒度值所對應的粒度值方差，并判斷粒度值方差是否小于預設方差閾值，是則進入步驟005；否則進入步驟006；

步驟005.判斷系統線程的數量M是否大于等于任務塊集合中任務塊的數量N，是則將任務塊集合中各個任務塊一一對應任意分配至各線程當中，由該各線程分別針對所分配的任務塊進行處理，針對任務塊集合中所有任務塊所對應的待處理任務的調度策略結束；否則將第i個任務塊分配至第m個線程上，i＝{m,m+M,…,m+KM}，K為大于等于1的整數，m+KM≤N，實現針對任務塊集合中各個任務塊的分配，由系統各個線程分別針對所分配的任務塊進行處理，針對任務塊集合中所有任務塊所對應的待處理任務的調度策略結束；

步驟006.獲得任務塊集合中所有任務塊粒度值的總和平均分配至系統M個線程的平均值，作為系統單線程負載范圍標準值G_thread_avg，同時判斷任務塊集合中各任務塊所對應的最大粒度值是否大于G_thread_avg，是則獲取任務塊集合中各任務塊所對應的最大粒度值與G_thread_avg之間的差值，作為系統單線程負載波動范圍值ΔG_thread，然后進入步驟007；否則預設系統單線程負載波動范圍值ΔG_thread，然后進入步驟007；

步驟007.提取任務塊集合中所有大于系統單線程負載范圍標準值G_thread_avg的粒度值所對應的各個任務塊，將該各個任務塊一一對應任意分配至各線程當中，用該各個任務塊的粒度值分別更新對應各線程上所對應的負載，并在任務塊集合中刪除該各個任務塊，將任務塊集合中剩余各個任務塊按其所對應的粒度值由大至小的順序進行排序，更新任務塊集合，獲得任務塊集合中任務塊的數量N'，然后進入步驟008；

步驟008.初始化m＝1，n'＝1，進入步驟009；

步驟009.判斷G_load_m+G_C_n'是否小于等于G_thread_avg+ΔG_thread，是則將任務塊集合中第n'個任務塊分配至第m個線程當中，用G_load_m+G_C_n'的值更新第m個線程上所對應的負載G_load_m，并在任務塊集合中刪除該任務塊，更新任務塊集合，然后進入步驟011；否則進入步驟010；其中，G_C_n'表示任務塊集合中粒度值按由小至大順序第n'個任務塊所對應的粒度值；

步驟010.判斷n'是否等于N'，是則進入步驟013；否則用n'+1的值更新n'，返回步驟009；

步驟011.判斷第m個線程上所對應的負載G_load_m是否大于等于G_thread_avg-ΔG_thread，是則進入步驟012；否則令n'＝1，并返回步驟009；

步驟012.判斷m是否等于M，是則針對任務塊集合中所有任務塊所對應的待處理任務的調度策略結束；否則用m+1的值更新m，并令n'＝1，然后返回步驟009；

步驟013.判斷第m個線程上所對應任務塊的數量是否大于1，是則將第m個線程上最后所分配的任務塊退回至任務塊集合當中，并更新任務塊集合，然后進入步驟014；否則進入步驟015；

步驟014.判斷任務塊集合中是否存在位于步驟013中所退回任務塊下一個位置的任務塊，是則將任務塊集合中步驟013中所退回任務塊的下一個任務塊分配至第m個線程當中，用G_load_m加該任務塊粒度值的和更新第m個線程上所對應的負載G_load_m，并在任務塊集合中刪除該任務塊，更新任務塊集合，然后進入步驟011；否則返回步驟013；

步驟015.判斷第m個線程上所對應任務塊的數量是否等于1，是則進入步驟016；否則進入步驟017；

步驟016.判斷第m個線程上是否存在大于系統單線程負載范圍標準值G_thread_avg的粒度值所對應的任務塊，是則進入步驟017；否則將第m個線程上最后所分配的任務塊退回至任務塊集合當中，并更新任務塊集合，然后進入步驟014；

步驟017.判斷m是否大于1，是則用m-1的值更新m，并返回步驟013，否則在預設系統單線程負載波動范圍值ΔG_thread基礎上，按預設波動范圍擴大并更新ΔG_thread，然后返回步驟009。

2.根據權利要求1所述一種面向多核平臺的多線程劃分及靜態均衡調度方法，其特征在于：所述步驟007中，提取任務塊集合中所有大于系統單線程負載范圍標準值G_thread_avg的粒度值所對應的各個任務塊，將該各個任務塊按其粒度值由大至小的順序進行排序，將系統各線程按其順序與該各個任務塊依序進行一一對應，將該各個任務塊分別分配至對應線程上，用該各個任務塊的粒度值分別更新對應各線程上所對應的負載。