Article

Free access

Dynamic feedback: an effective technique for adaptive computing

Authors:

Pedro C. Diniz,

Martin C. RinardAuthors Info & Claims

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

Pages 71 - 84

https://doi.org/10.1145/258915.258923

Published: 01 May 1997 Publication History

Abstract

This paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a different optimization policy. The generated code alternately performs sampling phases and production phases. Each sampling phase measures the overhead of each version in the current environment. Each production phase uses the version with the least overhead in the previous sampling phase. The computation periodically resamples to adjust dynamically to changes in the environment.We have implemented dynamic feedback in the context of a parallelizing compiler for object-based programs. The generated code uses dynamic feedback to automatically choose the best synchronization optimization policy. Our experimental results show that the synchronization optimization policy has a significant impact on the overall performance of the computation, that the best policy varies from program to program, that the compiler is unable to statically choose the best policy, and that dynamic feedback enables the generated code to exhibit performance that is comparable to that of code that has been manually tuned to use the best policy. We have also performed a theoretical analysis which provides, under certain assumptions, a guaranteed optimality bound for dynamic feedback relative to a hypothetical (and unrealizable) optimal algorithm that uses the best policy at every point during the execution.

References

[1]

S.P. Amarasinghe and M.S. Lain. Communication optimization and code generalion for distributed-memory machines. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and implementation, SIGPLAN Notices 28(7). ACM, July 1993.

Digital Library

[2]

J.M. Anderson and M,S. Lam. Global opfmizations for parallelism and locality on scalable parallel machines. In Proceedings of the SIG- PLAN'93 Conference on Programming Language Design and lmplernentation, SIGPLAN Notices 28(7). ACM, July 1993.

Digital Library

[3]

J. Auslander, M. Philipose, C. Chambers, S. Eggers, and B. Bershad. Fast, effective dynamic compilation, in Proceedings of the SIGPLAN '96 Conference on Program Language Design and Implementation, Philadelphia, PA, May 1996.

Digital Library

[4]

J. Barnes and P. Hut. A hierarchical O(NlogN) force-calculation algorithm. Nature, pages 446--449, December 1976.

[5]

E. Brewer. High-level optimization via automated statistical modeling. in Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of ParaUel Programming, Santa Barbara, CA, July 1995.

Digital Library

[6]

C. Chambers and D. Ungar. Customization: Optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language. In Proceedings of the SIGPLAN '89 Conference on Program Language Design and Implementation, Portland, OR, June 1989.

Digital Library

[7]

P. Chang, S. Mahlke, W. Chen, and W. Hwu. Profile-guided automatic inline expansion for C programs. Software--Practice and Experience, 22(5):349-369, May 1992.

Digital Library

[8]

W. Chen, S. Mahlke, N. Warter, S. Anik, and W. Hwu. Profile-assisted instruction scheduling. International Journal of Parallel Programming, 22(2):151-181, April 1994.

Digital Library

[9]

A. Cox and R. Fowler. Adaptive cache coherency for detecting migratory shared data. In Proceedings of the 20th international Symposium on Computer Architecture, May 1993.

Digital Library

[10]

P. Diniz and M. Rinard. Synchronization transformations for parallel computing. In Proceedings of the Twenty-fourth Annual ACM Symposium on the Principles of Programming Languages, Paris, France, January 1997. ACM.

Digital Library

[11]

D. Engler. VCODE: A retargetable, extensible, very fast dynamic code generation system. In Proceedings of the SIGPLAN '96 Conference on Program Language Design and Implementation, Philadelphia, PA, May 1996.

Digital Library

[12]

B. Falsafi, A. Lebeck, S. Reinhardt, I. Schoinas, M. Hill, J. Lares, A. Rogers, and D. Wood. Application-specific protocols for user-level shared memory. In Proceedings of Supercomputing '94, November 1994.

Digital Library

[13]

M. Fernandez. Simple and effective link-time optimization of modula- 3 programs. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995.

Digital Library

[14]

S. Freudenberger, J. Schwartz, and M. Sharir. Experience with the SETL optimizer. ACM Transactions on Programming Languages and Systems, 5(1):26--45, January 1983.

Digital Library

[15]

S. C. Goldstein, K. E. Schauser, and D. E. Culler. Lazy Threads: Implementing a fast parallel call. Journal of Parallel and Distributed Computing, 37( I):5-20, August 1996.

Digital Library

[16]

S. Graham, P. Kessler, and M. McKusick. gprof: a call graph execution profiler. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, Boston, MA, June 1982.

Digital Library

[17]

D. Grove, J. Dean, C. Garret, and C. Chambers. Profile-guided receiver class prediction. In Proceedings of the Tenth Annual Conference on Object-Oriented Programming Systems, Languages and Applications, Austin, TX, October 1995.

Digital Library

[18]

M. Gupta and P. Banerjee. Demonstration of automatic data partitioning techniques for parallelizing compilers on multicomputers. iEEE Transactions on Parallel and Distributed Systems, 3(2):179- 193, March 1992.

Digital Library

[19]

J. Harris, S. Lazarmos, and R. Michelena. Tomographic string inversion. In 60th Annual International Meeting, Society of Exploration and Geophysics, Extended Abstracts, pages 82-85, 1990.

[20]

U. Holzle and D. Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of the SIGPLAN '94 Conference on Program Language Design and Implementation, Orlando, FL, June 1994.

Digital Library

[21]

K. Kennedy and U. Kremer. Automatic data layout for High Performance Fortran. In Proceedings of Supercomputing '95, San Diego, CA, November 1995.

Digital Library

[22]

G. Kiczales. Beyond the black box: open implementation. IEEE Software, 13(1), January 1986.

Digital Library

[23]

D. Knuth. An empirical study of FORTRAN programs. Software--- Practice and Experience, 1:105-133, 1971.

[24]

P. Lee and M. Leone. Optimizing ML with nm-titr~ code genexation. In Proceedings of the SIGPLAN '96 Conference on Program Language Design and Implementation, Philadelphia, PA, May 1996.

Digital Library

[25]

D. Lenoski. The Design and Analysis of DASH: A Scalable Directory- Based Multt~orocessor. PhD thesis, Stanford, CA, February 1992.

Digital Library

[26]

S.i. rung and J. Zahorjan. Improving the performance of nmthne parallelization. In Proceedings of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 83-91, San Diego, CA, May 1993.

Digital Library

[27]

E. Mohr, D. Kranz, and R. Halstead. Lazy task creation: a technique for increasing the granularity of parallel programs. In Proceedings of the 1990 ACM Conference on Lisp and Functional Programming, pages 185-197, June 1990.

Digital Library

[28]

W. Morris. Ccg: a prototype coagulating code generator. In Proceedings of the SIGPLAN '91 Conference on Program Language Design and Implementation, Toronto, Canada, June 1991.

Digital Library

[29]

K. Pettis and D. Hansen. Profile guided code positioning. In Proceedings of the SIGPLAN '90 Conference on Program Language Design and Implementation, White Plains, NY, June 1990.

Digital Library

[30]

J. Plevyak, V. Karamcheti, X. Zhang, and A. Chien. A hybrid execution model for fine-grained languages on distributed memory multicomputers. In Proceedings of Supercomputing '95, San Diego, CA, November 1995.

Digital Library

[31]

J. Plevyak, X. Zhang, and A. Chien. Obtaining sequential efficiency for concurrent object-oriented languages. In Proceedings of the Twenty-second Annual ACM Symposium on the Prinaples of Programming Languages. ACM, January 1995.

Digital Library

[32]

L. Rauchwerger and D. Padua. The LRPD test: speculative ran-time parallelization of loops with privatization and reduction parallelization. In Proceedings of the SIGPLAN '95 Conference on Program Language Design and Implementation, La Jolla, CA, June 1995.

Digital Library

[33]

M. Rinard and P. Diniz. Commutativity analysis: A new analysis framework for parallelizing compilers. In Proceedings of the SIGPLAN '96 Conference on Program Language Design and Implementation, Philadelphia, PA, May 1996. (http'.//www. cs.ucsb, edub,marfn/~r/pldi96.ps).

Digital Library

[34]

M. Rinard, D. Scales, and M. Lam. Heterogeneous Parallel Programruing in Jade. in Proceedings of Supercomputing ~92, pages 245-256, November 1992.

Digital Library

[35]

T. Romer, D. Lee, B.Bershad, and J. Clan. Dynamic page mapping policies for cache conflict resolution on standard hardware. In Proceedings of the First USENIX Syngn~sium on Operating Systems Design and Implementation, pages 255 -266, Monterey, CA, November 1994.

[36]

R. Saavedra and D. Park. Improving the effectiveness of software prefetching with adaptive execution. In Proceedings of the } 996 Conference on Parallel Algorithms and Compilation Techniques (PACT '96, Boston, MA, October 1996.

Digital Library

[37]

J. Saltz, H. Berryman, and J. Wu. Multiprocessors and run-time compilation. Concurrency: Practice & Experience, 3(6):573-592, December 1991.

[38]

J. Singh, W. Weber, and A. Gupta. SPLASH: Stanford parallel applications for shared memory. Computer Architecture News, 20(1):5--44, March 1992.

Digital Library

[39]

D. Wall. Global register allocation at link time. In Proceedings of the SiGPLAN '86 Symposium on Compiler Construction. ACM, June 1986.

Digital Library

Cited By

Mustafa D(2022)A Survey of Performance Tuning Techniques and Tools for Parallel ApplicationsIEEE Access10.1109/ACCESS.2022.314784610(15036-15055)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3147846
Jouneaux GBarais OCombemale BMussbacher GDe Meuter WBaniassad E(2021)Towards self-adaptable languagesProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486753(97-113)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486753
Stephenson MRangan RKeckler S(2021)Cooperative Profile Guided OptimizationsComputer Graphics Forum10.1111/cgf.1438240:8(71-83)Online publication date: 28-Nov-2021
https://doi.org/10.1111/cgf.14382
Show More Cited By

Index Terms

Dynamic feedback: an effective technique for adaptive computing

Recommendations

Dynamic feedback: an effective technique for adaptive computing

This paper presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses a ...
Eliminating synchronization overhead in automatically parallelized programs using dynamic feedback

This article presents dynamic feedback, a technique that enables computations to adapt dynamically to different execution environments. A compiler that uses dynamic feedback produces several different versions of the same source code; each version uses ...
Dynamic and static feedback control for second order infinite‐dimensional systems
Abstract
This paper considers dynamic feedback stabilization for abstract second‐order systems, where the dynamic feedback controller is designed as another abstract second order infinite/finite‐dimensional system. This makes the closed‐loop system PDE‐PDE ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

May 1997

365 pages

ISBN:0897919076

DOI:10.1145/258915

Chairmen:
Marina Chen
Boston Univ., Boston, MA
,
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

ACM SIGPLAN Notices Volume 32, Issue 5
May 1997
365 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/258916
Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Marina Chen
Boston Univ., Boston, MA
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI97

Sponsor:

SIGPLAN

PLDI97: Conference on Programming Language

June 16 - 18, 1997

Nevada, Las Vegas, USA

Acceptance Rates

PLDI '97 Paper Acceptance Rate 31 of 158 submissions, 20%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

78
Total Citations
View Citations
822
Total Downloads

Downloads (Last 12 months)110
Downloads (Last 6 weeks)30

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mustafa D(2022)A Survey of Performance Tuning Techniques and Tools for Parallel ApplicationsIEEE Access10.1109/ACCESS.2022.314784610(15036-15055)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3147846
Jouneaux GBarais OCombemale BMussbacher GDe Meuter WBaniassad E(2021)Towards self-adaptable languagesProceedings of the 2021 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3486607.3486753(97-113)Online publication date: 20-Oct-2021
https://dl.acm.org/doi/10.1145/3486607.3486753
Stephenson MRangan RKeckler S(2021)Cooperative Profile Guided OptimizationsComputer Graphics Forum10.1111/cgf.1438240:8(71-83)Online publication date: 28-Nov-2021
https://doi.org/10.1111/cgf.14382
Weyns D(2019)Software Engineering of Self-adaptive SystemsHandbook of Software Engineering10.1007/978-3-030-00262-6_11(399-443)Online publication date: 12-Feb-2019
https://doi.org/10.1007/978-3-030-00262-6_11
Shevtsov SBerekmeri MWeyns DMaggio M(2018)Control-Theoretical Software AdaptationIEEE Transactions on Software Engineering10.1109/TSE.2017.270457944:8(784-810)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2704579
Zangerl PThoman PFahringer T(2017)Characterizing Performance and Cache Impacts of Code Multi-versioning on Multicore Architectures2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)10.1109/PDP.2017.77(209-213)Online publication date: 2017
https://doi.org/10.1109/PDP.2017.77
Vuduc RDemmel JBilmes J(2016)Statistical Models for Empirical Search-Based Performance TuningThe International Journal of High Performance Computing Applications10.1177/109434200404129318:1(65-94)Online publication date: 26-Jul-2016
https://doi.org/10.1177/1094342004041293
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe S(2015)Autotuning algorithmic choice for input sensitivityACM SIGPLAN Notices10.1145/2813885.273796950:6(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2813885.2737969
Ding YAnsel JVeeramachaneni KShen XO’Reilly UAmarasinghe SGrove DBlackburn S(2015)Autotuning algorithmic choice for input sensitivityProceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2737924.2737969(379-390)Online publication date: 3-Jun-2015
https://dl.acm.org/doi/10.1145/2737924.2737969
Maggio MKlein CÅrzén K(2014)Control strategies for predictable brownouts in cloud computingIFAC Proceedings Volumes10.3182/20140824-6-ZA-1003.0066947:3(689-694)Online publication date: 2014
https://doi.org/10.3182/20140824-6-ZA-1003.00669
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents