2D mesh處理機陳列上多處理分配策略研究.pdf

1、獨創(chuàng)性聲明本人聲明所呈交的學位論文是本人在導師指導下進行的研究工作和取得的研究成果，除了文中特別加以標注和致謝之處外，論文中不包含其他人已經發(fā)表或撰寫過的研究成果，也不包含為獲得云注王些太堂或其他教育機構的學位或證書而使用過的材料。與我一同工作的同志對本研究所做的任何貢獻均已在論文中作了明確的說明并表示了謝意。學位論文作者簽名：唧承簽字日期沙7聲㈨日學位論文版權使用授權書本學位論文作者完全了解云洼王些太堂有關保留、使用學位論文的規(guī)定。特

2、授權云洼王些太堂可以將學位論文的全部或部分內容編入有關數(shù)據(jù)庫進行檢索，并采用影印、縮印或掃描等復制手段保存、匯編以供查閱和借閱。同意學校向國家有關部門或機構送交論文的復印件和磁盤。(保密的學位論文在解密后適用本授權說明)學位論文作者簽名。柳不簽字日期：厶’年≥月f日I導師簽名：簽字日期：≥口，鄉(xiāng)年鄉(xiāng)月／日摘要隨著網絡和并行計算的發(fā)展，人們對計算能力的要求越來越高，而并行計算機成為實現(xiàn)高性能計算最有效的技術途徑之一。為了提高性能，在空間共

3、享的并行計算機中，一種有效的處理機分配算法至關重要。一個好的處理機分配算法應該在盡可能小的開銷下，為到來的任務找到合適的處理機結點進行分配。在mesh連接的多處理機結構上，已經提出了許多的連續(xù)分配和非連續(xù)分配算法。連續(xù)分配算法要求分配給一個并行任務的結點是連續(xù)的并且和多處理機系統(tǒng)中的拓撲結構相同，因此產生的外部碎片較高；在非連續(xù)分配中提高鄰接性的目的是為了降低處理機碎片，但是由于結點之間消息傳遞的距離變長了，通信開銷也隨之增大。本文就2

4、Dmesh結構的多處理機系統(tǒng)中處理機的搜索和分配算法進行了較深入的研究，提出了一種不同于以往的非連續(xù)分配算法，該算法是基于系統(tǒng)中當前可用的空閑子網進行分配的。首先，本文系統(tǒng)闡述了并行計算和互聯(lián)網絡的發(fā)展，對并行計算中的任務調度和處理機分配的聯(lián)系與區(qū)別進行了探討；其次，在系統(tǒng)分析了已有的連續(xù)分配和非連續(xù)分配算法的基礎上，提出了一種相對簡單高效的最大空閑子網搜索方法，根據(jù)系統(tǒng)中已分配子網的列表，利用空閑子網和已分配子網的空間相減運算，找到當