【摘要】：針對目前大多數(shù)多核處理器任務(wù)分配優(yōu)化算法沒有考慮關(guān)鍵路徑上節(jié)點對任務(wù)完成時間的重要影響,導(dǎo)致任務(wù)完成總時間延遲的問題,提出了基于關(guān)鍵路徑和任務(wù)復(fù)制(CPTD)的單任務(wù)調(diào)度算法。CPTD算法通過復(fù)制任務(wù)圖中fork節(jié)點的方式將任務(wù)圖轉(zhuǎn)化為與之相對應(yīng)的產(chǎn)品加工樹;再在生成的產(chǎn)品加工樹中找到關(guān)鍵路徑,并采取使關(guān)鍵路徑上節(jié)點的緊前節(jié)點盡早調(diào)度的方式,使關(guān)鍵路徑上節(jié)點盡早開始執(zhí)行,進而使產(chǎn)品加工樹中節(jié)點完成時間得以提前,達到縮短任務(wù)執(zhí)行總時間的目的。理論分析表明,CPTD算法能夠?qū)崿F(xiàn)應(yīng)用程序在多核上充分并行處理,并能縮短任務(wù)完成時間。
[Abstract]:At present, most multi-core processor task allocation optimization algorithms do not consider the critical path node on the task completion time, resulting in the total task completion time delay problem. This paper proposes a single task scheduling algorithm based on critical path and task replication (CPTD). CPTD algorithm transforms the task graph into the corresponding product processing tree by copying the fork nodes in the task graph, and then finds the critical path in the generated product processing tree. In order to make the node in the critical path start to execute as early as possible, the completion time of the node in the product processing tree can be advanced and the total time of task execution can be shortened by making the node on the critical path be scheduled as early as possible. Theoretical analysis shows that the CPTD algorithm can achieve full parallel processing on multi-core applications and shorten the task completion time.
【作者單位】： 哈爾濱理工大學(xué)計算機學(xué)院;哈爾濱工程大學(xué)計算機學(xué)院;
【基金】：國家自然科學(xué)基金資助項目(60873019)
【分類號】：TP332

【參考文獻】

相關(guān)期刊論文 前9條

1 孟憲福;閆玲玲;劉偉偉;;基于動態(tài)任務(wù)優(yōu)先級的網(wǎng)格任務(wù)調(diào)度算法研究[J];大連理工大學(xué)學(xué)報;2012年02期

2 陳莉麗;姚益平;蔡潞;;多核環(huán)境下負載均衡的并行離散事件全局調(diào)度機制[J];國防科技大學(xué)學(xué)報;2012年04期

3 周雙娥,袁由光,熊兵周,歐中紅;基于任務(wù)復(fù)制的處理器預(yù)分配算法[J];計算機學(xué)報;2004年02期

4 邸楠,王韜,李曉明;LilyTask任務(wù)并行環(huán)境中基于任務(wù)關(guān)系的初始任務(wù)分配算法[J];計算機學(xué)報;2005年05期

5 謝志強;楊靜;周勇;張大力;譚光宇;;基于工序集的動態(tài)關(guān)鍵路徑多產(chǎn)品制造調(diào)度算法[J];計算機學(xué)報;2011年02期

6 謝志強;辛宇;楊靜;;基于設(shè)備空閑事件驅(qū)動的綜合調(diào)度算法[J];機械工程學(xué)報;2011年11期

7 徐成;趙林祥;楊志邦;;一種基于多處理器任務(wù)復(fù)制的分簇調(diào)度算法[J];計算機應(yīng)用研究;2012年08期

8 陳芳園;張冬松;劉聰;王志英;;基于取指執(zhí)行時序范疇的多核共享Cache干擾分析[J];計算機研究與發(fā)展;2013年01期

9 何琨;趙勇;陳陽;;分布式環(huán)境下多任務(wù)調(diào)度問題的分析與求解[J];系統(tǒng)工程理論與實踐;2007年05期

【共引文獻】

相關(guān)期刊論文 前10條

1 夏冰;李潔冰;;一種面向任務(wù)、可重構(gòu)的主控中心設(shè)計方案[J];成組技術(shù)與生產(chǎn)現(xiàn)代化;2011年01期

2 黃漾;;分布式環(huán)境下任務(wù)調(diào)度探討[J];電腦知識與技術(shù);2011年19期

3 宋效東;竇萬峰;湯國安;張剛;江嶺;;并行累積可視性分析中的任務(wù)調(diào)度研究[J];地理與地理信息科學(xué);2013年04期

4 何琨;黃文奇;;分布式內(nèi)存機器中優(yōu)化調(diào)度問題的數(shù)學(xué)模型[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2008年02期

5 趙明宇;張?zhí)镂?;一種分布式計算環(huán)境下并行應(yīng)用的調(diào)度算法[J];計算機研究與發(fā)展;2008年04期

6 李仁發(fā);劉彥;徐成;;多處理器片上系統(tǒng)任務(wù)調(diào)度研究進展評述[J];計算機研究與發(fā)展;2008年09期

7 劉慶強;程亮;牟菡渝;;基于推薦機制的人機交互任務(wù)調(diào)度算法[J];佳木斯大學(xué)學(xué)報(自然科學(xué)版);2009年03期

8 夏冰;李金武;裴斐;鄭秋生;;一種分布式安全評估通信與調(diào)度模型[J];計算機工程與應(yīng)用;2011年12期

9 黎忠文;;嵌入式實時系統(tǒng)容錯集成技術(shù)的研究[J];計算機科學(xué);2006年05期

10 王小非;方明;;一種基于調(diào)度簇樹的周期性分布實時任務(wù)調(diào)度算法[J];計算機科學(xué);2007年03期

相關(guān)會議論文 前1條

1 夏冰;王志奇;鄭秋生;李向東;;政務(wù)終端安全面臨的問題與對策研究[A];第27次全國計算機安全學(xué)術(shù)交流會論文集[C];2012年

相關(guān)博士學(xué)位論文 前8條

1 官東;網(wǎng)格環(huán)境下的HLA仿真關(guān)鍵問題研究[D];中南大學(xué);2011年

2 蔣建春;異構(gòu)多核嵌入式軟件關(guān)鍵問題研究[D];重慶大學(xué);2011年

3 寇瑋華;基于并行分層式鏈路分布式數(shù)據(jù)更新的協(xié)議及副本復(fù)制研究[D];西南交通大學(xué);2004年

4 趙明宇;集群系統(tǒng)的調(diào)度算法研究[D];哈爾濱工業(yè)大學(xué);2007年

5 蘭舟;分布式系統(tǒng)中的調(diào)度算法研究[D];電子科技大學(xué);2009年

6 張建軍;基于Fork-Join任務(wù)圖的調(diào)度算法研究[D];華中科技大學(xué);2010年

7 劉彥;異構(gòu)多核片上系統(tǒng)的任務(wù)調(diào)度及應(yīng)用研究[D];湖南大學(xué);2009年

8 王忠凱;動車組運用檢修計劃優(yōu)化方法的研究[D];中國鐵道科學(xué)研究院;2012年

相關(guān)碩士學(xué)位論文 前10條

1 閆思柱;可重構(gòu)嵌入式系統(tǒng)軟硬件劃分及任務(wù)調(diào)度算法研究[D];哈爾濱理工大學(xué);2010年

2 趙磊;適應(yīng)多核處理器的任務(wù)調(diào)度研究[D];哈爾濱理工大學(xué);2010年

3 李金武;分布式主機安全評估關(guān)鍵技術(shù)研究[D];中原工學(xué)院;2011年

4 曹立強;基于SWE的傳感規(guī)劃服務(wù)的研究與設(shè)計[D];西安工業(yè)大學(xué);2011年

5 張建強;基于任務(wù)并行策略的多核程序優(yōu)化研究[D];遼寧師范大學(xué);2011年

6 徐鈞磊;退火進化算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用和研究[D];南京信息工程大學(xué);2011年

7 邵俠;存在延遲約束的綜合柔性調(diào)度的研究[D];哈爾濱理工大學(xué);2011年

8 常寧寧;基于設(shè)備工序緊湊的綜合調(diào)度算法的研究[D];哈爾濱理工大學(xué);2011年

9 仇文娟;云計算中依賴任務(wù)動態(tài)并行調(diào)度機制的研究[D];大連理工大學(xué);2011年

10 于鳳;考慮預(yù)期庫存可用性的車間調(diào)度算法研究[D];大連理工大學(xué);2011年

【二級參考文獻】

相關(guān)期刊論文 前10條

1 何琨;趙勇;;網(wǎng)格環(huán)境下資源調(diào)度問題的統(tǒng)一建模與分析[J];華中科技大學(xué)學(xué)報(自然科學(xué)版);2006年03期

2 謝志強,劉勝輝,喬佩利;基于ACPM和BFSM的動態(tài)Job-Shop調(diào)度算法[J];計算機研究與發(fā)展;2003年07期

3 林劍檸;吳慧中;;一種基于動態(tài)決策路徑的網(wǎng)格任務(wù)調(diào)度算法[J];計算機研究與發(fā)展;2008年05期

4 楊志義;楊剛;張海輝;;一種面向服務(wù)的事件驅(qū)動架構(gòu)信息集成平臺構(gòu)造方法[J];計算機研究與發(fā)展;2008年10期

5 邵維忠,梅宏;統(tǒng)一建模語言UML述評[J];計算機研究與發(fā)展;1999年04期

6 謝志強,劉勝輝,喬佩利;電機產(chǎn)品加工的動態(tài)調(diào)度算法[J];計算機集成制造系統(tǒng)-CIMS;2003年06期

7 張德富,李新;求解作業(yè)車間調(diào)度問題的快速啟發(fā)式算法[J];計算機集成制造系統(tǒng);2005年02期

8 范路橋,常會友,朱旭東;一種改進的作業(yè)車間調(diào)度算法及其實現(xiàn)[J];計算機集成制造系統(tǒng);2005年05期

9 梁峰;江志斌;陶俐言;趙大為;;基于事件驅(qū)動的制造資源沖突實時消解方法[J];計算機集成制造系統(tǒng);2007年02期

10 劉振英,方濱興,張毅;TSA-OT:一個調(diào)度Out-Tree任務(wù)圖的算法[J];計算機學(xué)報;2001年04期

相關(guān)博士學(xué)位論文 前2條

1 謝志強;工件間有約束的復(fù)雜產(chǎn)品工序調(diào)度研究[D];哈爾濱理工大學(xué);2009年

2 蘇年樂;仿真模型可移植性規(guī)范的多核并行化研究[D];國防科學(xué)技術(shù)大學(xué);2010年

【相似文獻】

相關(guān)期刊論文 前10條

1 趙歡;江文;李學(xué)輝;;異構(gòu)系統(tǒng)中的綜合性啟發(fā)式任務(wù)調(diào)度算法[J];計算機應(yīng)用;2010年05期

2 蘭舟;孫世新;;基于關(guān)鍵路徑知識的任務(wù)調(diào)度遺傳算法[J];計算機應(yīng)用;2008年02期

3 連順金;求AOE-網(wǎng)中關(guān)鍵路徑的一種算法[J];黎明職業(yè)大學(xué)學(xué)報;2001年02期

4 曾黨泉;;基于AOE網(wǎng)的工作流程主關(guān)鍵路徑的研究[J];科技廣場;2008年08期

5 徐鳳生,黃倩;關(guān)鍵路徑求解的新算法[J];計算機應(yīng)用;2004年12期

6 王雪梅;杜凱;;基于AOE網(wǎng)的多源點多匯點關(guān)鍵路徑研究[J];科技創(chuàng)新導(dǎo)報;2009年14期

7 徐敏;譚文安;;面向軟件系統(tǒng)的指令時序建模與分析方法[J];計算機與數(shù)字工程;2010年11期

8 潘全科,朱劍英;一類解決Job shop問題的改進進化規(guī)劃[J];山東農(nóng)業(yè)大學(xué)學(xué)報(自然科學(xué)版);2005年02期

9 嚴曉浪,季愛明,沈海斌;性能優(yōu)化的現(xiàn)場可編程門陣列快速編譯方法[J];浙江大學(xué)學(xué)報(工學(xué)版);2005年10期

10 張芳;;前N條最短路徑在網(wǎng)絡(luò)中的應(yīng)用[J];福建電腦;2008年05期

相關(guān)會議論文 前10條

1 徐上;;企業(yè)內(nèi)部信息溝通關(guān)鍵路徑的判定及其應(yīng)用[A];推進鐵路新跨越加快經(jīng)濟大發(fā)展——中國科協(xié)2004年學(xué)術(shù)年會鐵道分會場論文集[C];2004年

2 張濤;楊卓;;單任務(wù)和雙任務(wù)事件中腦電活動的信息流特征[A];第一屆全國腦與認知科學(xué)學(xué)術(shù)研討會論文集[C];2005年

3 劉瑞華;涂凍生;;生產(chǎn)加工網(wǎng)絡(luò)的關(guān)鍵路徑與擾動分析[A];1993中國控制與決策學(xué)術(shù)年會論文集[C];1993年

4 劉自寬;譚思彤;涂凍生;;隨機串行生產(chǎn)線性能優(yōu)化的非光滑分析方法[A];1998中國控制與決策學(xué)術(shù)年會論文集[C];1998年

5 李勇建;涂(?)生;;串行生產(chǎn)線存儲單元的序優(yōu)配置[A];2000中國控制與決策學(xué)術(shù)年會論文集[C];2000年

6 李勇建;涂奉生;;具有偏序結(jié)構(gòu)的一般網(wǎng)絡(luò)系統(tǒng)的關(guān)鍵路徑與擾動分析問題[A];第十九屆中國控制會議論文集（一）[C];2000年

7 李勇建;涂凍生;;串行生產(chǎn)線的關(guān)鍵路徑計算與擾動分析[A];2001中國控制與決策學(xué)術(shù)年會論文集[C];2001年

8 趙建;;委托代理模型下國有煤礦經(jīng)理激勵機制設(shè)計[A];第一屆全國安全科學(xué)理論研討會論文集[C];2007年

9 李勇建;涂凍生;;應(yīng)用關(guān)鍵路徑串行再生系統(tǒng)的參數(shù)優(yōu)化[A];2001中國控制與決策學(xué)術(shù)年會論文集[C];2001年

10 楊芳;;離散制造企業(yè)生產(chǎn)計劃與控制管理系統(tǒng)研究[A];'06MIS/S&A學(xué)術(shù)交流會論文集[C];2006年

相關(guān)重要報紙文章 前10條

1 廣文;三星半年多完成全年接單任務(wù)[N];中國船舶報;2011年

2 唐曉玉/譯;關(guān)鍵路徑公司 虛增收入遭起訴[N];中國財經(jīng)報;2003年

3 通訊員 王小英;江閥廠提前4個月完成全年接單任務(wù)[N];中國船舶報;2008年

4 吉林 飄零雪;網(wǎng)頁安全之簡單任務(wù)[N];電腦報;2003年

5 記者　 陸旭升;我市已完成早稻訂單任務(wù)[N];金華日報;2006年

6 ;明確“路標(biāo)”強化執(zhí)行[N];人民郵電;2003年

7 ;明確“路標(biāo)” 強化執(zhí)行[N];人民郵電;2003年

8 寧倫榮;當(dāng)涂縣：超額完成全年糧油訂單任務(wù)[N];糧油市場報;2005年

9 記者 李建永;把城鎮(zhèn)建設(shè)作為率先建設(shè)沿海強市的關(guān)鍵路徑[N];秦皇島日報;2007年

10 本報特派記者 盧建寧;產(chǎn)品走向世界的關(guān)鍵路徑[N];廣西日報;2010年

相關(guān)博士學(xué)位論文 前10條

1 蘭舟;分布式系統(tǒng)中的調(diào)度算法研究[D];電子科技大學(xué);2009年

2 崔萬安;廣義優(yōu)先關(guān)系網(wǎng)絡(luò)關(guān)鍵性分析[D];華中科技大學(xué);2006年

3 高守瑋;一類Flow shop生產(chǎn)調(diào)度問題及其優(yōu)化方法之分析與研究[D];上海交通大學(xué);2007年

4 何琨;多任務(wù)調(diào)度問題的研究與實現(xiàn)[D];華中科技大學(xué);2006年

5 張建軍;基于Fork-Join任務(wù)圖的調(diào)度算法研究[D];華中科技大學(xué);2010年

6 李勇;多Agent系統(tǒng)聯(lián)盟及任務(wù)分配的研究[D];合肥工業(yè)大學(xué);2008年

7 費蓉;動態(tài)規(guī)劃研究及其在電力市場動態(tài)分區(qū)定價問題中的應(yīng)用[D];西安理工大學(xué);2009年

8 張濤;裝備制造業(yè)突破性創(chuàng)新機制與建設(shè)路徑研究[D];燕山大學(xué);2012年

9 劉智全;企業(yè)R&D項目的過程控制與績效評價研究[D];哈爾濱工業(yè)大學(xué);2009年

10 褚春超;工程項目進度管理方法與應(yīng)用研究[D];天津大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 梁紅建;掙值分析法在項目進度費用管理的應(yīng)用研究[D];吉林大學(xué);2007年

2 丁世軍;港口機械產(chǎn)品制造項目工期—費用優(yōu)化研究[D];武漢理工大學(xué);2010年

3 龍凱;關(guān)鍵鏈在Y公司項目管理中的應(yīng)用研究[D];上海交通大學(xué);2008年

4 吳逢慶;改進蟻群算法在車間調(diào)度中的應(yīng)用研究[D];合肥工業(yè)大學(xué);2009年

5 李振宏;隨機環(huán)境下關(guān)鍵路徑問題的研究[D];河北大學(xué);2013年

6 王凱;基于關(guān)鍵路徑的控制圖式的項目時間管理[D];上海交通大學(xué);2011年

7 劉莉;異構(gòu)集群下并行任務(wù)的復(fù)制調(diào)度算法[D];武漢紡織大學(xué);2013年

8 柴佳;關(guān)鍵路徑下工程項目成本預(yù)警系統(tǒng)設(shè)計：一項實地研究[D];西南財經(jīng)大學(xué);2011年

9 趙林祥;基于多核處理器任務(wù)復(fù)制的分簇調(diào)度算法研究[D];湖南大學(xué);2012年

10 鐘志輝;JM ITV項目進度關(guān)鍵路徑管理研究[D];華南理工大學(xué);2011年

，

本文編號：2153799