- Authors:
- R. T. Hammel,
- D. K. Gifford
We analyze how much the FX-87 static effect system can improve the execution times of five benchmark programs on a parallel graph interpreter. Three of our benchmark programs do not use side-effects (factorial, fibonacci, and polynomial division) and thus did not have any effect induced constraints. Their FX-87 performance was comparable to their performance in a purely functional language. Two of our benchmark programs use side-effects (DNA sequence matching and Scheme interpretation) and our compiler was able to use effect information to reduce their execution times by factors of 1.7 to 5.4 when compared with sequential execution times. These results support our thesis that a static effect system is a powerful tool for compilation to multiprocessor computers. However, the graph interpreter we used was based on unrealistic assumptions, and thus our results may not accurately reflect the performance of a practical FX-87 implementation. The results also suggest that conventional loop analysis would complement the FX-87 effect system.
Cited By
- Bocchino R Alias control for deterministic parallelism Aliasing in Object-Oriented Programming, (156-195)
- Bocchino R and Adve V Types, regions, and effects for safe programming with object-oriented parallel frameworks Proceedings of the 25th European conference on Object-oriented programming, (306-332)
- Bocchino R, Adve V, Dig D, Adve S, Heumann S, Komuravelli R, Overbey J, Simmons P, Sung H and Vakilian M (2009). A type and effect system for deterministic parallel Java, ACM SIGPLAN Notices, 44:10, (97-116), Online publication date: 25-Oct-2009.
- Bocchino R, Adve V, Dig D, Adve S, Heumann S, Komuravelli R, Overbey J, Simmons P, Sung H and Vakilian M A type and effect system for deterministic parallel Java Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications, (97-116)
- Reistad B and Gifford D Static dependent costs for estimating execution time Proceedings of the 1994 ACM conference on LISP and functional programming, (65-78)
- Reistad B and Gifford D (2019). Static dependent costs for estimating execution time, ACM SIGPLAN Lisp Pointers, VII:3, (65-78), Online publication date: 1-Jul-1994.
- Rinard M and Lam M Semantic foundations of Jade Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, (105-118)
- Lam M and Rinard M Coarse-grain parallel programming in Jade Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, (94-105)
- Lam M and Rinard M (1991). Coarse-grain parallel programming in Jade, ACM SIGPLAN Notices, 26:7, (94-105), Online publication date: 1-Jul-1991.
- Jouvelot P and Gifford D Algebraic reconstruction of types and effects Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, (303-310)
Recommendations
Interprocedural dataflow analysis in an executable optimizer
Interprocedural dataflow information enables link-time and post-link-time optimizers to perform analyses and code transformations that are not possible in a traditional compiler. This paper describes the interprocedural dataflow analysis techniques used ...
Joining dataflow with predicates
Dataflow analyses sacrifice path-sensitivity for efficiency and lead to false positives when used for verification. Predicate refinement based model checking methods are path-sensitive but must perform many expensive iterations to find all the relevant ...