Program Phase Detection with Critical Basic Block Transitions

 

A Critical Basic Block Transition (CBBT) is a transition from one basic block to another that signals a phase change when encountered during program’s execution.

 

In the following examples, large-scale CBBT markings are shown for the gzip and mcf programs.

 

For gzip, three CBBTs are selected from the profile run. The figures below show basic block execution profiles for a self-trained (left) and a cross-trained (right) runs of gzip with the three CBBTs marked with the down triangle, the up triangle, and the circle.

 

 

For mcf, two CBBTs are selected from the profile run. The figures below show basic block execution profiles of a self-trained and a cross-trained runs of mcf with the two CBBTs marked with the up triangle and the circle.

 

 

We can see that the CBBT markings adapt well to changes in the phase length and the number of recurring phases. In the case of mcf, a 5-cycle phase behavior produced by the self-trained input is correctly partitioned into a 9-cycle phase behavior with the cross-trained input. For mcf, the up triangle mark represents CBBT transition into a phase where the two functions—primal_bea_mpp and refresh_potentialare frequently executed whereas the circle marks represents CBBT transition into a phase where the function price_out_impl is frequently executed. For gzip, the first two phase cycles toggle between deflate_fast (down triangle CBBT mark) and inflate_dynamic (up triangle CBBT mark) phases, and the next three cycles between deflate (circle CBBT mark) and inflate_dynamic (up triangle CBBT mark) phases.

 

Click here to download the CBBT source code.

 

For questions or comments, please e-mail paruj AT csl dot cornell dot edu.

 

Reference

Paruj Ratanaworabhan and Martin Burtscher, “Program Phase Detection based on Critical Basic Block Transitions”, Proceedings of the 2008 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS’08), Austin, Texas, April 2008.