《並行任務調度在多核系統中的線上模型及其算法研究》是依託浙江大學，由葉德仕擔任項目負責人的面上項目。
基本介紹
- 中文名：並行任務調度在多核系統中的線上模型及其算法研究
- 依託單位：浙江大學
- 項目負責人：葉德仕
- 項目類別：面上項目
項目摘要,結題摘要,
項目摘要
隨著多核和眾核系統的發展，如何有效的利用和挖掘並行性是一芝芝歸個具有挑戰和有意義的事情。本項目對並行任務調度因多核出現而產生的新模型和線上算法進行研究。本項目從算法的設計與分析的角度入手（如線上原始-對偶法，隨機算法等），在不改變硬體結構和作業系統的前提下，抽象出基於多核計算系統中的並行任務調度數學模型，並利用組合最佳化和算法設計的相關理論知識來設計高效的算法，並給出算法的性能保證。本項目的主要研究內容為基於多機多核的並行任務調度線上算法研究和基於快取分割的並行任務調度線上算法研究。首先，對多機器且核數不相同的並行任務調度算法進行研究，繼而考慮核間帶網路拓撲結構的並行任務調度算法，同時對並行任務在不同機器間可以遷移的情況進行調度算法研究。另外，我們考慮了快取因素對並行任務的影響，即研究基於快取分割的平行非同類機的線上調度算法和研究基於快取分割的並行任務調度算法；最後實現部分算法、並分析比較。
結題摘要
隨著多核和眾核系統的發展, 如何有效的利用和挖掘並行性是一個具有挑戰和 有意義的事情。本項目對並行任務調度因多核出現而產生的新模型和線上算法進行研究。本項目的主要研究內容為基於多機多核的並行任務調度線上算法研究，及基於快取分割的並行任務線上調度算法研究。悼記駝項目根據研究計畫和研究內容順利進展並完成了預先設定的計畫。戰乘具體來講，主要的研究成果有： 1、 多機多核的線上並行任務調度：研究核速度不相同、集群中核數不同的並行任務調度線上算法，分別給出了常數競爭比的算法。 2、基於快取分割的資源加速調度：將快取分割成若干相同大小的塊數,每個任務只使用一塊快取來加速。對於雙核結構我們設計的線上算法的競爭比，且證明任何線上算法的競爭比與該上屆很接近。並將問題推廣至任意m核的情況。 3、可遷移的並行任務調度算法研究：我們首次提出排序模型中遷移代價顯性的模型，並給出了近似算法、線上算法的分析。 4、基於多機多核的並行任務調度協調機制設計：多機多核系統或者是雲計算往往是分散式計算。本項目研究了計算任務是屬於不同的用戶，且每個用戶可以選擇計算資源。這個模型是用戶與用戶之間的博弈，每個用戶希望能儘快的完成所提交的任務，即完工時間最小。本項目研究平台提供方需要設計相關的機制並使得社會效益得到最佳化。我們首次提出了兩類的協調機制並分析其社會效益。 5、基於資源競爭的並行任務調度博弈：我們將計算任務多維化，如一個任務需要CPU、記憶體、頻寬等d－維資源，這裡d為任意的整數。每個任務都有各自的玩家（如虛擬機）控制，為了獲得更好的船船講采資源，玩家將根據系統的負載等信息自由選擇自己的處理資源。我們考慮了兩種場景，負載均衡和姜市局虛擬機放置博弈，首次提出多維資源競爭的博弈模型。 6、基於混合CPU-GPU的任務調槓棵廈度：給定混合的CPU－GPU系統，我們根據CPU和GPU數目的不同情況，分別設計線上算法。該模型的創新在於給出了介於平行機調度與非同型機調度的線上模型和算法設計罪詢求膠，解決特定處理器異構的調度算法。 本項目預期發表國際期刊或者國際會議論文10～13篇。目前，我們已經發表的論文有14篇論文，其中SCI期刊7篇，國際會議7篇（EI檢索），重要期刊有Future Generation Computer Systems, Journal of Global Optimization，Information processin
