| Granularity Analysis for Exploiting Adaptive Parallelism of Declarative Programs on Multiprocessors |
| |
| 作者姓名： | 田新民 王鼎兴 沈美明 郑纬民 温冬婵 |
| |
| 作者单位： | Department of Computer Science and Technology，Tsinghua University，Beijing 100084 |
| |
| 摘 要： | 1IntroductionAutomaticparallelexecutionofdeclarativelanguageprograms(e.g.functionprogramsandlogicprograms)isattractive,asitmakestheuseofparallelcomputersveryeasy,andtheprogrammerneednotbeconcernedwiththespecificsoftheunderlyingparallelarchitecture.However,ifseveralprocessorsareexecutingconcurrently,exploitingadaptiveparallelismishardduetonon-determinismoftaskgranularityanddatadependenciesamongtasks.TheearlysolutionproposedbyConeryandKibler2]usesanorderingalgorithmtodeterminedependenciesatrun…
|
Granularity Analysis for Exploiting Adaptive Parallelism of Declarative Programs on Multiprocessors |
| |
| Tian Xinmin ,Wang DingXing,Shen Meiming,Zheng Weimin and Wen Dongchan.Granularity Analysis for Exploiting Adaptive Parallelism of Declarative Programs on Multiprocessors[J].Journal of Computer Science and Technology,1994(2). |
| |
| Authors: | Tian Xinmin Wang DingXing Shen Meiming Zheng Weimin and Wen Dongchan |
| |
| Abstract: | Declarative Programming Languages (DPLs) apply a process model of Horn claun es such as PARLOG8] or a reduction model of A-calculus such as SML7] and are) in principle, well suited to multiprocessor implemelltation. However, the performance of a parallel declarative program can be impaired by a mismatch between the parallelism available in an application and the parallelism available in the architecture. A particularly attractive solution is to automatically match the parallelism of the program to the parallelism of the target hardware as a compilation step. In this paper) we present an optimizillg compilation technique called granularity analysis which identi fies and removes excess parallelism that would degrade performance. The main steps are: an analysis of the flow of data to form an attributed call graph between function (or predicate) arguments; and an asymptotic estimation of granularity of a function (or predicate) to generate approximate grain size. Compiled procedure calls can be annotated with grain size and a task scheduler can make scheduling decisions with the classilication scheme of grains to control parallelism at runtime. The resulting granularity analysis scheme is suitable for exploiting adaptive parallelism of declarative programming languages on multiprocessors. |
| |
| Keywords: | Granularity analysis adaptive parallelism declarative languages grain coalescing grain classification fine-grained tasks coarse-grained tasks multiprocessors |
| 本文献已被 CNKI 等数据库收录！ |
