Parallel Compiler Optimization and Performance Analysis
Overview
In this research, I evaluated how different GCC compiler optimization levels affected the speed of a C++ version of the 0/1 Knapsack problem. The 0/1 Knapsack issue is a classic optimization problem in computer science where the objective is to find the most valued combination of objects that can fit into a container with a limited weight capacity. Each item has a weight and a value, and each item can either be included (1) or excluded (0)—it cannot be divided or picked multiple times. This topic is commonly used to explore optimization methods, dynamic programming, and performance analysis.
Compiler optimization is the process of translating source code into more efficient machine code without affecting the program's output. I measured execution time, gathered hardware performance counters using Linux's perf tool, and examined instruction counts to compare three optimization settings (-O0, -O1, and -O3).
The purpose of this study was to understand how compiler optimizations improve execution performance by removing redundant instructions, enhancing instruction scheduling, optimizing memory access, and producing more efficient machine code. This project increased my understanding of compiler design, computer architecture, CPU performance, and performance benchmarking.
Tools and Technologies Used
-
C++
-
OpenMP
-
GCC Compiler
-
Linux
-
Brooks Computing Cluster
-
Performance Benchmarking
-
Speedup Analysis
-
Amdahl's Law
-
Data Visualization
Speedup
Speedup measures how much faster an optimized program executes compared to the baseline version.
Instruction Reduction
This equation calculates the percentage decrease in executed instructions after optimization.
CPU Performance Equation
This equation explains the relationship between execution time, instruction count, CPI, and processor clock speed.
Memory Instructions
Memory instructions were calculated using the collected hardware performance counters.
ALU Instructions
Memory instructions were calculated using the collected hardware performance counters.
1. Compile the Program Using Different Optimization Levels
Initially, I used three distinct GCC optimization options to compile the knapsack program: -O0, -O1, and -O3. The baseline for comparison was the -O0 build, which turned off compiler optimizations. While the -O3 build used more sophisticated optimization strategies such loop optimizations, function inlining, and instruction scheduling, the -O1 build allowed basic optimizations to increase execution performance.
I was able to compare firsthand how compiler optimizations affect software performance by compiling the same application at different optimization levels.
2. Compile the Program Using Different Optimization Levels
Raw Data
Mean Data
I used the Linux time tool to measure the execution time after compiling each version. Before determining the average execution time, each executable was ran six times to reduce experimental variation.
The baseline build was regularly outperformed by the optimized versions. The execution time was lowered by the -O1 optimization from roughly 26.18 seconds to 2.34 seconds, and by the -O3 optimization to roughly 1.48 seconds. These findings show how compiler optimizations, without changing the original source code, can significantly increase software performance.
3. Analyze the Instruction Mix Using Performance Counters
Performance Counter Results
Calculated Instruction Counts
I then gathered hardware performance counters for every executable using the Linux perf tool. The total number of executed instructions, branch instructions, cache references, LLC loads, and LLC stores were among the information gathered.
I determined how many memory and ALU operations each build executed overall using these measurements. This investigation demonstrated that compiler optimizations greatly decreased all instruction categories, which contributed to the explanation of why the optimized versions ran considerably quicker than the baseline program.
4. Calculate Speedup and Instruction Reduction
I determined the speedup generated by each optimization level and estimated the percentage decrease in the total number of executed instructions after examining the instruction counts.
The -O1 build reduced executed instructions by about 84.36% while achieving an 11.19× speedup over the baseline program. The -O3 build reduced the number of instructions by an additional 31.36% and increased speed by 1.58×. These computations showed how compiler optimization results in significant speed gains.
5. Interpret the Results Using the CPU Performance Equation
In order to have a better understanding of how compiler optimizations impact processor speed, I finally compared the execution times with the instruction reductions. Even though the optimized versions ran a lot less instructions, the observed speedups were not exactly correlated with the instruction count reduction.
I discovered that execution time is influenced by average cycles per instruction (CPI), processor clock cycle time, and the amount of instructions performed using the CPU Performance Equation. By eliminating superfluous instructions, compiler optimizations enhance branch prediction, cache use, register allocation, and instruction scheduling. Therefore, the observed performance increases cannot be fully explained by lowering the number of instructions.
Results, Analysis, and Further Reading
This research showed how compiler optimizations can greatly increase software performance without altering a program's behavior. I learned more about how contemporary compilers produce effective machine code by comparing various optimization settings, tracking execution durations, examining hardware performance counters, and computing instruction reductions.
The experiment also shown that there are other factors besides instruction count that affect execution time. Overall performance is influenced by a number of factors, including CPU architecture, branch prediction, cache behavior, and instruction scheduling. I improved my knowledge of computer architecture, Linux performance tools, compiler optimization, and performance benchmarking through this investigation.