ABSTRACT
The execution time of Pascal-like programs can be decreased by putting solutions to problems in their maximally parallel forms. In this study Pascal-like programs are considered, and analysis of parallelism is performed by using a dynamic recent data dependency graph (DDG). The means taken in this paper is able to derive maximally parallel versions of the programs and to minimize the execution time. The advantage of this means is not only to save the effort in implementation but also to possess generality and high-efficiency resulting from dynamically locating parallelism in program. The study shows that the maximally parallel program can run in considerably less time than that needed to run the original sequential Pascal-like program.
- 1.Chattergy,R., & Pooch,U.N. A distributed function computer with dedicated processors. Computer J. Vol.22, No.1 (1979) pp37-40Google ScholarCross Ref
- 2.Evans,D.J., & Williams,S.A. Analysis and detection of parallel processable code. Computer J. Vol.23, No.1 (1980) pp66-72Google ScholarCross Ref
- 3.Foulk,P.W.,& Nassar,S.M. Analysis of parallelism in nested DO loops. J. Syst. & Softw. Vol.5, No.1 (1985) pp73-80 Google ScholarDigital Library
- 4.Hellerman,H. Parallel processing of algebraic expressions. IEEE TC. Vol.15 (1966) pp82-91Google Scholar
- 5.Kuck,D.J. Parallel processing of ordinary programs. Advances in Computers Vol.15 (1976) ppi19-179Google Scholar
- 6.M.Di Manzo, A.L.Frisiani,& G.Olimpo. Loop optimization for parallel processing. Computer J. Voi.22, No.3 (1979) pp234-239Google ScholarCross Ref
- 7.Nagl,M. Application of graph rewriting to optimization and parallelization of programs. Computing Suppl. 3. (1981) ppi05-124Google Scholar
- 8.Ramamoorthy,C.V.,& Gonzalez,M.J. A survey of techniques for recognizing parallel processable streams in computer programs. Proc. AFIP. 1969 FJCC.Google Scholar
- 9.Stone,H.S. One-pass compilation of arithmetic expressions for a parallel processor. CACM Vol.10 (1967) pp220-223 Google ScholarDigital Library
- 10.Towel, R. A. Control and data dependence for program transformations. Report No. UIUCDCS-R-76-788. (1976). University of Illinois at Urbana- Champaign.Google Scholar
Index Terms
- Dynamic detection of parallelism in Pascal-like program
Recommendations
Machine Independent AND and OR Parallel Execution of Logic Programs: Part II-Compiled Execution
In pt.I, we presented a binding environment for the ANDand OR parallel execution of logic programs. This environment was instrumental inrendering a compiler for the AND and OR parallel execution of logic programs machineindependent. In this paper, we ...
Implementation of a parallel Prolog interpreter on multiprocessors
IPPS '91: Proceedings of the Fifth International Parallel Processing SymposiumDescribes the implementation of the Reduce-OR process model for the parallel execution of logic programs in an interpreter for parallel Prolog. The interpreter supports full OR and independent AND parallelism in logic programs on both shared and ...
Parallel motion estimation on the MDSP multiprocessor
Motion estimation (ME) is a process for removing temporal redundancies in video sequences. It contributes most of the compression ratio and consumes typically 60-80% of the video encoding time. This paper investigates parallel execution of ME on the ...
Comments