Download files
Abstract
In real-time systems, it is crucial to guarantee that all the timing constraints are met at design stage. The WCET of each task has a significant impact on finding a feasible schedule for a set of real-time tasks. If we can reduce the WCET of each program, we are more likely to find a feasible schedule. Therefore, it is important to minimize the WCET of each program. An optimizing compiler plays a key role in reducing the WCET of a program. In this thesis, we investigate three important problems of reducing the WCET of a program executed on clustered VLIW processors, and propose novel, efficient approaches.
Firstly, we investigate the problem of reducing the number of branch mispredictions for a program such that its WCET is minimized, and propose a novel branch correlation-based, hybrid branch prediction heuristic approach. Our approach consists of a static profile-based branch correlation analyzer and a dynamic branch predictor. The static profile-based branch correlation analyzer uses profiling and data dependency analysis to find precise correlations between branches of a program and identifies all the branches that do not have any impact on the WCET of the program. The dynamic predictor uses the correlation information to make online predictions. We have implemented our approach and compared it with the two state-of-the-art branch prediction approaches by using a set of benchmark suites. The experimental results show that our approach outperforms the two state-of-the-art approaches.
Secondly, we investigate the problem of instruction scheduling and register allocation for a program executed on a clustered VLIW processor such that the WCET of the program is minimized, and propose a novel, unified instruction scheduling and register allocation heuristic approach. Our approach iteratively selects a set of basic blocks that may have impact on the WCET found by using WCET-aware graph reduction, performs live range splitting for a set of selected variables in those basic blocks if the set of basic blocks has impact on the WCET, computes the priorities of all the basic blocks selected, and performs integrated instruction scheduling and register allocation for each selected basic block in order of their priorities until the WCET of the program does not change. Our approach is underpinned by a set of novel techniques, including spanning graph-based WCET-aware live range splitting, WCET-aware dynamic register pressure control, WCET-aware basic block prioritization for performing integrated instruction scheduling and register allocation, and WCET-aware spill code handling. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 20 benchmarks. The experimental results show that our approach significantly reduces the WCET.
Lastly, we investigate the hyper-block construction problem for a program executed on a clustered VLIW processor such that the WCET of the program is minimized, and propose a novel WCET-aware hyper-block construction heuristic approach based on a novel WCET-aware basic block priority scheme considering tail duplications. Our approach selects a set of basic blocks with most impact on the WCET, and performs hyper-block construction in a bottom-up way using a novel basic block priority scheme and a WCET-aware tail-duplication cost model, significantly reducing the WCET of a program compared to the state-of-the-art approach. To our best knowledge, our approach is the first one considering tail-duplications in hyper-block construction.