计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2014年
3期
580-590
,共11页
推测多线程%线程划分%模糊聚类%自动并行化%代价评估
推測多線程%線程劃分%模糊聚類%自動併行化%代價評估
추측다선정%선정화분%모호취류%자동병행화%대개평고
speculative multithreading%thread partitioning%fuzzy c-means clustering%automatic parallelization%cost estimation
推测多线程(Speculative Multithreading,SpMT)技术是一种实现非规则程序自动并行化的有效途径.然而,如何有效评估由诸如控制、数据依赖等因素导致的多种并行开销并实现最优线程划分一直是制约加速比性能提升的关键问题.基于启发式规则的传统划分方法虽然可以取得一定的加速效果,但由于启发式规则只能对多种并行开销进行定性评估,因而导致只能得到经验上较优的线程划分.针对传统划分方法的局限性,文中首次提出并实现了一种基于模糊聚类的线程划分方法.在该方法中,作者首先提出一种评估模型来定量评估各种并行开销,然后通过深入分析各种并行开销来确定最佳的线程解搜索空间,最终利用聚类方法实现有效线程解空间搜索以求取更优的线程划分.基于Olden程序集的测试结果表明,文中提出的线程划分方法可以有效地对非规则程序进行划分,其平均加速比可达到1.85.
推測多線程(Speculative Multithreading,SpMT)技術是一種實現非規則程序自動併行化的有效途徑.然而,如何有效評估由諸如控製、數據依賴等因素導緻的多種併行開銷併實現最優線程劃分一直是製約加速比性能提升的關鍵問題.基于啟髮式規則的傳統劃分方法雖然可以取得一定的加速效果,但由于啟髮式規則隻能對多種併行開銷進行定性評估,因而導緻隻能得到經驗上較優的線程劃分.針對傳統劃分方法的跼限性,文中首次提齣併實現瞭一種基于模糊聚類的線程劃分方法.在該方法中,作者首先提齣一種評估模型來定量評估各種併行開銷,然後通過深入分析各種併行開銷來確定最佳的線程解搜索空間,最終利用聚類方法實現有效線程解空間搜索以求取更優的線程劃分.基于Olden程序集的測試結果錶明,文中提齣的線程劃分方法可以有效地對非規則程序進行劃分,其平均加速比可達到1.85.
추측다선정(Speculative Multithreading,SpMT)기술시일충실현비규칙정서자동병행화적유효도경.연이,여하유효평고유제여공제、수거의뢰등인소도치적다충병행개소병실현최우선정화분일직시제약가속비성능제승적관건문제.기우계발식규칙적전통화분방법수연가이취득일정적가속효과,단유우계발식규칙지능대다충병행개소진행정성평고,인이도치지능득도경험상교우적선정화분.침대전통화분방법적국한성,문중수차제출병실현료일충기우모호취류적선정화분방법.재해방법중,작자수선제출일충평고모형래정량평고각충병행개소,연후통과심입분석각충병행개소래학정최가적선정해수색공간,최종이용취류방법실현유효선정해공간수색이구취경우적선정화분.기우Olden정서집적측시결과표명,문중제출적선정화분방법가이유효지대비규칙정서진행화분,기평균가속비가체도1.85.