基于分布樹的負(fù)載均衡模型研究和應(yīng)用.pdf

1、在并行計(jì)算中，隨著問題規(guī)模增大，需要考慮如何分配負(fù)載來達(dá)到均衡。在一個(gè)由多個(gè)處理機(jī)組成的集群系統(tǒng)中，相互作用的任務(wù)必須分配到多個(gè)處理機(jī)上，以充分利用系統(tǒng)資源。許多科學(xué)計(jì)算和應(yīng)用中都是以樹作為數(shù)據(jù)結(jié)構(gòu)的，所以研究分布樹的負(fù)載均衡模型具有非?，F(xiàn)實(shí)的意義，除了可應(yīng)用于電磁散射的并行精確計(jì)算以外，對(duì)以樹結(jié)構(gòu)為計(jì)算基礎(chǔ)的工程應(yīng)用，也有推廣和參考價(jià)值。如果分布樹的負(fù)載不均衡，則將導(dǎo)致整個(gè)并行算法的效率降低，而且體現(xiàn)不出并行算法的優(yōu)點(diǎn)。 本文

2、分析了幾種不同的構(gòu)建分布樹的模型，每種構(gòu)建模型都代表不同的負(fù)載劃分方法，并對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行了闡述，指出其適合的應(yīng)用范圍。在對(duì)幾種不同模型的研究基礎(chǔ)上，提出了一種新的構(gòu)建分布樹的模型，即均分某一層(非最細(xì)層)的方式來構(gòu)建分布樹。此模型可以避免使用傳統(tǒng)的基于最細(xì)層分配所導(dǎo)致的負(fù)載不均衡現(xiàn)象，適合空結(jié)點(diǎn)比較多、且同一層上每個(gè)結(jié)點(diǎn)的孩子數(shù)不規(guī)則的樹型結(jié)構(gòu)。 在對(duì)并行多層快速多極子算法(MLFMA)原理研究的基礎(chǔ)上，將不同的分布樹構(gòu)建模