Access Restriction

Author Aleen, Farhana ♦ Pande, Santosh ♦ Sharif, Monirul
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Dynamic execution ♦ Software pipeline ♦ Parallelization
Abstract Streaming applications are promising targets for effectively utilizing multicores because of their inherent amenability to pipelined parallelism. While existing methods of orchestrating streaming programs on multicores have mostly been static, real-world applications show ample variations in execution time that may cause the achieved speedup and throughput to be sub-optimal. One of the principle challenges for moving towards dynamic orchestration has been the lack of approaches that can predict or accurately estimate upcoming dynamic variations in execution efficiently, well before they occur. In this paper, we propose an automated dynamic execution behavior prediction approach that can be used to efficiently estimate the time that will be spent in different pipeline stages for upcoming inputs without requiring program execution. This enables dynamic balancing or scheduling of execution to achieve better speedup. Our approach first uses dynamic taint analysis to automatically generates an input-based execution characterization of the streaming program, which identifies the key control points where variation in execution might occur with the associated input elements that cause these variations.We then automatically generate a light-weight emulator from the program using this characterization that can simulate the execution paths taken for new streaming inputs and provide an estimate of execution time that will be spent in processing these inputs, enabling prediction of possible dynamic variations. We present experimental evidence that our technique can accurately and efficiently estimate execution behaviors for several benchmarks. Our experiments show that dynamic orchestration using our predicted execution behavior can achieve considerably higher speedup than static orchestration.
Description Affiliation: Georgia Institute of Technology, Atlanta, GA, USA (Aleen, Farhana; Sharif, Monirul; Pande, Santosh)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 45
Issue Number 5
Page Count 10
Starting Page 315
Ending Page 324

Open content in new tab

   Open content in new tab
Source: ACM Digital Library