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

有效

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

本發明涉及一種面向多核平臺的多線程劃分及靜態均衡調度方法，提出用于評估分解出任務大小的粒度值參數概念，首先根據一定判斷條件，判斷一個任務是否真正適合多線程并行；其次采用靜態調度策略，相比動態調度來說，沒有在運行階段的調度開銷；最后，不同于一般的靜態調度策略，本發明提出一種啟發式靜態調度策略，考慮了靜態調度時當分解的任務大小差異很大時，會造成各個線程之間負載極不平衡的問題，通過獲取的任務塊的粒度值，可以將差異很大的任務塊合理分配到不同線程上，達到負載均衡。

技術領域

本發明涉及一種面向多核平臺的多線程劃分及靜態均衡調度方法，屬于并行計算領域。

背景技術

提高處理器性能一般取決于兩個方面：一方面是處理器的體系結構的發展；另一個方面是半導體工藝的不斷進步。美國斯坦福大學提出片上多核處理器，為了提高處理器計算能力，將多個內核集成到一個處理器芯片上，而最容易、最簡單、最基本的一種實現方法就是多核。早在上世紀末，IBM和惠普就已經提出雙核處理器的可行性設計。2005年4月，intel全球同步首發基于多核技術桌面產品Intel Pentium D處理器，正式宣告x86處理器多核心時代來臨。

多核技術是在一個處理芯片上包含多個“執行內核”，使處理器能完全并行的執行程序的多線程。如果從操作系統層面來看，多核就是指多個處理器，而每個處理器都獨立擁有全部的計算資源。

處理器架構從單核發展到多核架構的過程中，極大地提高了處理器的性能，同時也帶來了一些問題。如任務調度和負載均衡問題、節點間的通信、Cache一致性問題以及系統異構性問題等。

其中解決負載均衡問題通常有兩種方案，一種是靜態調度，另外一種是動態調度。靜態調度是指程序在編譯階段，就將循環迭代任務近乎平均分配到各個線程上。而動態調度則要到運行階段才動態地將任務分配給空閑的線程，動態調度無需過多的關心循環體大小以及循環迭代任務規模，就能獲得好的負載均衡性能，同時，也會帶來一定的調度開銷。而且現有的并行計算過程中,由于每次線程創建撤銷以及調度均有一定開銷,有些計算任務采用多線程并行后，程序性能會大幅度下降；另外針對適合多線程并行的計算任務，在進行任務調度時，需要為多線程分配任務，靜態調度在程序運行前，就將任務分解并近乎平均得分配給各個線程，當分解的任務大小差異很大時，會造成各個線程之間負載極不平衡，影響程序運行性能。

發明內容

本發明所要解決的技術問題是提供一種面向多核平臺的多線程劃分及靜態均衡調度方法，采用全新設計思路，能夠主動判斷待處理任務是否適合多線程并行處理，并針對多線程并行處理，實現任務調度時多線程之間任務分配的負載均衡，能夠有效提高程序運行的性能。

本發明為了解決上述技術問題采用以下技術方案：本發明設計了一種面向多核平臺的多線程劃分及靜態均衡調度方法，包括如下步驟：

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

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

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

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