[雙語(yǔ)翻譯]--外文翻譯---同類集群上并行任務(wù)圖的進(jìn)化調(diào)度（節(jié)選）

1、中文 中文 5900 5900 字出處： 出處：Hunold Hunold S, S, Lepping Lepping J. J. Evolutionary Evolutionary Scheduling Scheduling of of Parallel Parallel Tasks Tasks Graphs Graphs onto onto Homogeneous Homogeneous Clusters[J]. Clusters[

2、J]. 2011:344-352. 2011:344-352.同類集群上并行任務(wù)圖的進(jìn)化調(diào)度 同類集群上并行任務(wù)圖的進(jìn)化調(diào)度Sascha Hunold，Joachim Lepping摘要：當(dāng)并行程序組合成較大的應(yīng)用程序時(shí)，任務(wù)圖（PTGs）出現(xiàn)，例如，科學(xué)工作流。調(diào)度這些 PTGs 到集群上是一個(gè)具有挑戰(zhàn)性的問(wèn)題，是由于可塑性任務(wù)產(chǎn)生的并行性的附加開(kāi)銷。大多數(shù)算法是基于這樣的假設(shè)：并行任務(wù)的執(zhí)行時(shí)間隨著處理器的數(shù)量增加而增加。但是，這假

3、設(shè)并不完全通用，因?yàn)槿绻幚砥鞯臄?shù)目是多的內(nèi)部使用的塊大小，并行程序的性能經(jīng)常表現(xiàn)的更好。在這篇文章中，我們介紹了 EMTS 算法靜態(tài)調(diào)度 PTGs 到集群上。我們應(yīng)用一種漸進(jìn)式的方法確定每個(gè)任務(wù)分配處理器。進(jìn)化調(diào)度策略保證了 EMTS 可以用于任何底層模型，用于預(yù)測(cè)可塑性任務(wù)的執(zhí)行時(shí)間?？梢钥焖僬业浇鉀Q方案的目的，EMTS考慮其它啟發(fā)式結(jié)果（例如，HCPA，MCPA）作為起始解決方案。實(shí)驗(yàn)結(jié)果表明，EMTS 顯著減少 PTGs 的完成

4、時(shí)間，相比其它啟發(fā)式兩個(gè)非單調(diào)和單調(diào)遞減模式。關(guān)鍵詞： 任務(wù)調(diào)度；并行任務(wù)；進(jìn)化算法；集群1 概述科學(xué)工作流是并行任務(wù)圖的一個(gè)重要類型，并在計(jì)算網(wǎng)格上處理。許多科學(xué)工作流僅僅包含幾個(gè)并行任務(wù)。然而，正如 Cirne 等人所說(shuō)，提交給就是那集群的并行任務(wù)幾乎 98%是可塑性的。一個(gè)可塑性的任務(wù)的處理器的數(shù)量在執(zhí)行之前被確定，并且執(zhí)行期間保持不變。如果這些并行任務(wù)結(jié)合起來(lái)，并且任務(wù)圖（PTGs）出現(xiàn)。幾種算法可以表示為 PTGs，如 St

5、rassen 的矩陣乘法和快速傅里葉變換（FFT）。一個(gè) PTG 的節(jié)點(diǎn)表示計(jì)算，邊表示數(shù)據(jù)或控制的以來(lái)。執(zhí)行 PTG 導(dǎo)致混合并行時(shí)間調(diào)度，因?yàn)楣?jié)點(diǎn)以一種數(shù)據(jù)并行的方式實(shí)現(xiàn)，獨(dú)立的任務(wù)可以同時(shí)執(zhí)行。讓我們以兩種矩陣的大小考察 ScaLAPACK 并行矩陣乘法例程 DGEMM 的執(zhí)行時(shí)間，我們就可以看到，執(zhí)行時(shí)間不單調(diào)遞減，但大多數(shù)的調(diào)度算法假設(shè)單調(diào)遞減的執(zhí)行時(shí)間模型。因此，施加一個(gè)非單調(diào)遞減模型會(huì)導(dǎo)致這些算法低效的執(zhí)行。出于這個(gè)原因，

6、我們專注于這個(gè)問(wèn)題的進(jìn)化算法，我們引入算法 EMTS，其可以再任意的執(zhí)行時(shí)間模型中使用。我們發(fā)現(xiàn)，EMTS 相比于其他啟發(fā)式算法，2.3 問(wèn)題聲明盡我們所知，可塑性的任務(wù) PTGs 調(diào)度算法是在假設(shè)一個(gè)任務(wù)的執(zhí)行時(shí)間隨處理器數(shù)量的增加而增加的基礎(chǔ)上。在這篇文章中，我們解決了如何克服這種限制的問(wèn)題?？梢约僭O(shè)另一種啟發(fā)式方法，將采取一個(gè)事實(shí)，即增加一個(gè)分配也可以增加執(zhí)行時(shí)間。然而，該算法設(shè)計(jì)者會(huì)找到一個(gè)更好的大小分配。由于分配和映射步驟高

7、度依賴于彼此，加上 k 個(gè)處理器，分配可能會(huì)降低相應(yīng)的任務(wù)的并行執(zhí)行時(shí)間，但是它可能同時(shí)增加整體完工時(shí)間。因此，我們希望找到一個(gè)啟發(fā)式方法，這個(gè)調(diào)度問(wèn)題是獨(dú)立用來(lái)描述并行任務(wù)的運(yùn)行時(shí)間模型。為此，我們采用進(jìn)化搜索策略，但不能保證這可能克服陷入局部最優(yōu)解的問(wèn)題。進(jìn)化搜索策略的主要優(yōu)點(diǎn)是：（1）他們可以應(yīng)付大問(wèn)題；（2）他們能夠應(yīng)用于未知搜索空間而無(wú)需得知其結(jié)構(gòu)的精確的數(shù)學(xué)模型；（3）他們能夠優(yōu)化在搜索空間開(kāi)始的任意位置。缺點(diǎn)是，進(jìn)化方法傾

8、向于慢慢收斂到最佳值，以及一個(gè)通常為沒(méi)有度量如何接近當(dāng)前結(jié)果是最佳的解決方案。雖然意識(shí)到這些特性，我們要設(shè)計(jì)一個(gè)進(jìn)化算法用于此調(diào)度問(wèn)題，提供了用于計(jì)算的解決方案，并由此產(chǎn)生完工時(shí)間之間的良好平衡。由于我們通?？梢越灰讜r(shí)間的解決方案質(zhì)量，我們專注于一個(gè)特定的時(shí)間限制。3 EMTS 算法在本節(jié)中提出的算法是基于應(yīng)用和平臺(tái)的模型，這是在第二章提出的，在本文中，一個(gè)同構(gòu)的集群包括相同類型的計(jì)算節(jié)點(diǎn)，也就是說(shuō)，相同的處理器和存儲(chǔ)器大小。此外，任