A Hardware Hot Loop Path Detector for Dynamic Parallelization and Optimization

T. Baba, H. Yanome, K. Ootsu, and T. Yokota (Japan)


Dynamic optimization, loop parallelization, hardware hot loop path detector


Dynamic parallelization and optimization of a loop is a crucial issue for enhancing the performance of sequential programs as loops account for a large fraction of execu tion time. Loop level parallelism can also be extracted efficiently due to its regular structure. Based on the ob servation that only a limited number of paths are executed frequently in hot loops, we propose a hardware hot loop path detector to specify such hot loops and their hot paths accurately so that the dynamic optimizer may utilize the detected information effectively. The detector consists of a stack structured bit-tracing unit that identifies loop paths at a subroutine level, a hot loop detector that detects hot loops by utilizing loop path information and a hot path accumu lator of loop paths. Experiments using SPEC CINT2000 show that loop paths occupy a small fraction (14.46%) of Ball-Larus paths but are detected frequently (64.45% of Ball-Larus paths). A combined small scale hot loop detector and hot path ac cumulator (32 entries each) attain a detection accuracy of 97.10% for the hottest loop path and 93.83% for the top 2 hottest loop paths and their order within hot loops.

Important Links:

Go Back