Optimizing array-intensive applications for on-chip multiprocessors

• Published in: IEEE transactions on parallel and distributed systems 2005-05, Vol.16 (5), p.396-411
• Main Authors: Kadayif, I., Kandemir, M., Chen, G., Ozturk, O., Karakoy, M., Sezer, U.
• Format: Article
• Language: English
• Subjects: adaptive loop parallelization; Application software; Computer architecture; constrained optimization; Constraint optimization; Design optimization; embedded systems; Energy consumption; Energy measurement; integer linear programming; On-chip multiprocessor; Optimization; Performance analysis; Performance loss; Potential energy; Sleep; Studies
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2005.57

With energy consumption becoming one of the first-class optimization parameters in computer system design, compilation techniques that consider performance and energy simultaneously are expected to play a central role. In particular, compiling a given application code under performance and energy constraints is becoming an important problem. In this paper, we focus on an on-chip multiprocessor architecture and present a set of code optimization strategies. We first evaluate an adaptive loop parallelization strategy (i.e., a strategy that allows each loop nest to execute using a different number of processors if doing so is beneficial) and measure the potential energy savings when unused processors during execution of a nested loop are shut down (i.e., placed into a power-down or sleep state). Our results show that shutting down unused processors can lead to as much as 67 percent energy savings at the expense of up to 17 percent performance loss in a set of array-intensive applications. To eliminate this performance penalty, we also discuss and evaluate a processor preactivation strategy based on compile-time analysis of nested loops. Based on our experiments, we conclude that an adaptive loop parallelization strategy combined with idle processor shut down and preactivation can be very effective in reducing energy consumption without increasing execution time. We then generalize our strategy and present an application parallelization strategy based on integer linear programming (ILP). Given an array-intensive application, our optimization strategy determines the number of processors to be used in executing each loop nest based on the objective function and additional compilation constraints provided by the user/programmer. Our initial experience with this constraint-based optimization strategy shows that it is very successful in optimizing array-intensive applications on on-chip multiprocessors under multiple energy and performance constraints.