【摘要】：針對(duì)目前大多數(shù)多核處理器任務(wù)分配優(yōu)化算法沒(méi)有考慮關(guān)鍵路徑上節(jié)點(diǎn)對(duì)任務(wù)完成時(shí)間的重要影響,導(dǎo)致任務(wù)完成總時(shí)間延遲的問(wèn)題,提出了基于關(guān)鍵路徑和任務(wù)復(fù)制(CPTD)的單任務(wù)調(diào)度算法。CPTD算法通過(guò)復(fù)制任務(wù)圖中fork節(jié)點(diǎn)的方式將任務(wù)圖轉(zhuǎn)化為與之相對(duì)應(yīng)的產(chǎn)品加工樹(shù);再在生成的產(chǎn)品加工樹(shù)中找到關(guān)鍵路徑,并采取使關(guān)鍵路徑上節(jié)點(diǎn)的緊前節(jié)點(diǎn)盡早調(diào)度的方式,使關(guān)鍵路徑上節(jié)點(diǎn)盡早開(kāi)始執(zhí)行,進(jìn)而使產(chǎn)品加工樹(shù)中節(jié)點(diǎn)完成時(shí)間得以提前,達(dá)到縮短任務(wù)執(zhí)行總時(shí)間的目的。理論分析表明,CPTD算法能夠?qū)崿F(xiàn)應(yīng)用程序在多核上充分并行處理,并能縮短任務(wù)完成時(shí)間。
[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é)計(jì)算機(jī)學(xué)院;哈爾濱工程大學(xué)計(jì)算機(jī)學(xué)院;
【基金】：國(guó)家自然科學(xué)基金資助項(xiàng)目(60873019)
【分類號(hào)】：TP332

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

【共引文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 蔣建春;異構(gòu)多核嵌入式軟件關(guān)鍵問(wè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 王忠凱;動(dòng)車(chē)組運(yùn)用檢修計(jì)劃優(yōu)化方法的研究[D];中國(guó)鐵道科學(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 李金武;分布式主機(jī)安全評(píng)估關(guān)鍵技術(shù)研究[D];中原工學(xué)院;2011年

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

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

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

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

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

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

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

【二級(jí)參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 記者　 陸旭升;我市已完成早稻訂單任務(wù)[N];金華日?qǐng)?bào);2006年

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

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

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

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

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

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

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

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

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

4 何琨;多任務(wù)調(diào)度問(wèn)題的研究與實(shí)現(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 費(fèi)蓉;動(dòng)態(tài)規(guī)劃研究及其在電力市場(chǎng)動(dòng)態(tài)分區(qū)定價(jià)問(wèn)題中的應(yīng)用[D];西安理工大學(xué);2009年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2153799