The goal was to optimize the performance of the Coremarks Benchmark, and to reduce the size of the code generated by the compiler. To measure performance gains, the metric of Iterations per Second of the Coremarks Program is used. How the problem was approached, Observations and Results are detailed below:
Final Score: 2K performance run parameters for coremark. CoreMark Size : 666 Total ticks : 11543591 Total time (secs): 11.543590 Iterations/Sec : 3.465126 Iterations : 40 Compiler version : riscv64-unknown-elf-12.2.0 Correct operation validated. See README.md for run and reporting rules. CoreMark 1.0 : 3.465126 (Full output appended at end of document)
- Performance Optimization i) Using GCC optimization options ii) Source code modifications iii) Approaches that did not work out as expected iv) Further Scope
i) Using GCC optimization options First, I attempted to use the plethora of optimization options supplied by GCC. These can be mentioned at compile time for the compiler to optimize the program logic more and more aggressively. They tradeoff Debug-Capability, Code Size, and Compile time for performance or speed of execution. After trying out various combinations and adjusting the parameters of these options to find the most optimum performance, i changed and introduced these compiler flags: Earlier(showing only relevant flags):
-O2 -fgnu89-inline -nostartfiles -nostdlib -fno-builtin-printf -static -lrt
After changes:
-Ofast -msmall-data-limit=8 -finline-atomics -mshorten-memrefs -mstrict-align -mexplicit-relocs --param=max-inline-functions-called-once-insns=4000 --param=max-inline-functions-called-once-loop-depth=20 --param=max-inline-insns-auto=1000 --param=max-inline-insns-recursive-auto=1450 --param=max-inline-insns-recursive=1450 --param=max-inline-insns-single=700 --param=max-inline-insns-size=2147483500 --param=max-inline-insns-small=10000000 --param=max-inline-recursive-depth-auto=100 --param=max-inline-recursive-depth=100 --param=min-inline-recursive-probability=0 --param=max-early-inliner-iterations=30 --param=builtin-string-cmp-inline-length=100 -fjump-tables --param=inline-min-speedup=0 --param=inline-unit-growth=1000000 --param=inline-heuristics-hint-percent=1000000 --param=uninlined-function-insns=1000000 --param=uninlined-function-time=1000000 --param=uninlined-thunk-insns=1000000 --param=uninlined-thunk-time=1000000 -fmerge-all-constants -fno-builtin -ffreestanding -ffp-contract=fast -fstdarg-opt -fsection-anchors -fvariable-expansion-in-unroller -funroll-loops -ftree-vectorize -fivopts -ftree-loop-ivcanon -ftree-loop-im -ffinite-loops -freschedule-modulo-scheduled-loops -fsched-spec-load -fsched-stalled-insns=0 -fira-loop-pressure -fira-algorithm='priority' -flive-range-shrinkage -free -fdevirtualize-at-ltrans -fsplit-wide-types-early -fgcse-sm -fdelete-null-pointer-checks -fdevirtualize-speculatively
These enable the most aggressive options that don't break the function of the code, including unrolling loops, inlining functions, merging constants, tree optimizations, advanced instruction scheduling, etc.
For 40 iterations, the Iteration per Second Score improved from 2.318680 => 2.588080.
ii) Source Code modifications Before modifying the source code, it is vital to instrument or profile the program and figure out which parts of the program will be the most beneficial to optimize. These will be functions which are called the most often, or parts of code in which the most amount of time is spent. I attempted to use "gprof" for this, but could not get it running on a riscv target, thus, i profiled the Coremarks program, by running it on my personal computer. Logically, if the function of the program is equivalent on both architectures, we will be able to extract important information, except time calculations. The Call Graph and the Flat Profile revealed that these were the functions called the most(in descending order)(irrelevant and functions in which considerable amount of time is not spent are removed)
core_state_transition
calc_func
cmp_idx
cmp_complex
core_bench_matrix
matrix_test
core_bench_state
matrix_mul_matrix_bitextract
matrix_mul_matrix
matrix_mul_vect
core_list_mergesort
core_bench_list
Changes to the Finite State Machine - core_state_transition() function
The function core_state_transition is used to accept a stream of input bytes, and determine the type of input number. The original state machine is depicted below:
I identified that the states CORE_S1 and CORE_S2 are only intermediate states that do not affect the output of the state machine, which only decides between integer, float, scientific and invalid numbers.
I reduced this overhead of remaining in intermediate states by loading and checking the characters placed after the current byte in the same cycle of state machine execution. This came with an increased overhead of updating an additional input byte but offered performance gains. This increased the 1 iteration Iteration per Second Score(without optimization flags):
2.418139 => 2.420117 => 2.432557 On removal of S1 and S2 intermediate states using a lookahead byte
Updated State Machine:
Code:
else if( NEXT_SYMBOL == '+' || NEXT_SYMBOL == '-' ) {
//state = CORE_S1;
transition_count[CORE_S1]++;
if(ee_isdigit(NEXT_2)) state = CORE_INT; // Checks the Next Byte for direct transition
else if(NEXT_2 == '.') state = CORE_FLOAT;
else state = CORE_INVALID; // State CORE_S1 eliminated
str++;
if( NEXT_SYMBOL == 'E' || NEXT_SYMBOL == 'e' ) {
//state = CORE_S2;
transition_count[CORE_FLOAT]++;
transition_count[CORE_S2]++;
state = CORE_EXPONENT;
if(NEXT_2 == '+' || NEXT_2 == '-'); // Checks the next byte
else state = CORE_INVALID; // State CORE_S2 eliminated
str++;
core_state_transition -> ee_isdigit() function The ee_isdigit() function is called many times inside of core_state_transition to check if the input byte is an integer or not. However, after inspecting its disassembly, I found it to contain redundant instructions which could be optimized further:
// 4 instructions to check if it is a digit
addw a0,a4,-48 // Subtracts 48 from the ASCII code, making '0' = 0 and '9'=9
zext.b a6,a0 // zero extends the LSB
li t0,9
bgeu t0,a6,.+0x5a // makes comparison
I intended to make the following changes. Improved algorithm:
static ee_u8 ee_isdigit(ee_u8 c) {
ee_u8 retval;
asm ("li t1, 1\n"
"lb t1, %[c]\n"
"lb t1, %[retval]\n" // Actual Computation in 3 instructions
"andi t1, t1, 0xF0\n" // Instruction 1 : Masks the input
"li t0, 0x30\n" // Instruction 2 : Checks for 3 in Hex digit 1
"beq t0,t1, .+0x2\n" // Instruction 3 : Branches if found
"li t0,1\n"
"lb t0, %[c]\n"
:[retval] "=m"(retval) :[c]"m"(c) :"t0", "t1");
However, extended assembly was slower and I wrote it in C which would compile to these instructions:
retval = c & 0xF0;
if(retval == 0x30) retval=1;
else retval = 0;
return retval;
Performance gains: 2.432557 => 2.448268
I experimented with assembly in replacing an entire state with extended assembly code as well, detailed in failed approaches section.
I tried to extend the concept of lookahead byte to even more bytes by checking bytes 2, 3 , .. , 7 places ahead of the current one and making a shortcut to the final state. But, this proved inefficient for non-intermediary states, also detailed in that section.
calc_func -> cmp_idx function
The cmp_idx (compare index) function is a short function called many times by mergesort implemented in calc_func used in the linked list processing stage of Coremarks. The original function featured economy of expression but an alogrithm which could be shorter. Original:
ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
if (res==NULL) {
a->data16 = (a->data16 & 0xff00) | (0x00ff & (a->data16>>8));
b->data16 = (b->data16 & 0xff00) | (0x00ff & (b->data16>>8));
}
return a->idx - b->idx;
The use of Signed short to hold the data made compiler use the SRA (Shift Right Arithmetic) instruction, which necessitated the use of a further mask on the data. Just by using a LHU (Load Half Unsigned) or SRL (Shift ) could solve this problem. Solution using assembly and the 'naked' attribute:
__attribute__((naked)) ee_s32 cmp_idx(list_data *a, list_data *b, core_results *res) {
...
asm(
"beqz a2,.+0xe\n"
"lh a0,2(a0)\n"
"lh a5,2(a1)\n"
"subw a0,a0,a5\n"
"ret\n"
"lhu a5,0(a0)\n"
"srl a5,a5,0x8\n"
"sllw a4,a5,0x8\n"
"or a5,a5,a4\n"
"sh a5,0(a0)\n"
"lhu a5,0(a1)\n"
"lh a0,2(a0)\n"
"srl a5,a5,0x8\n"
"sllw a4,a5,0x8\n"
"or a5,a5,a4\n"
"sh a5,0(a1)\n"
"lh a5,2(a1)\n"
"subw a0,a0,a5\n"
"ret\n"
/*:[a]"+m"(a->data16),[aidx]"=m"(a->idx),[b]"+m"(b->data16),[bidx]"=m"(b->idx):[c]"r"(res):"a0","a4","a5");*/
}
and C:
a->data16 = a->data16>>8;
a->data16 &= 0xff;
a->data16 = a->data16 | (a->data16<<8);
b->data16 = b->data16>>8;
b->data16 &= 0xff;
b->data16 = b->data16 | (b->data16<<8);
Performance gains: 2.448268 => 2.451100
matrix_test -> Matrix operations
matrix_sum ; matrix mul_constant ; matrix add_const: These Matrix operation functions all featured a common template. They were using Nested for loops to iterate over the whole matrix, which was really not needed, since those elements could be accessed serially, using one variable instead of two. I modified the code and removed the overhead of the extra loop variable. All these decisions trade memory or space for time. Modified Code with the original commented:
void matrix_add_const(ee_u32 N, MATDAT *A, MATDAT val) {
ee_u32 i,j=N*N;
for (i=0; i<j; i++) {
//for (j=0; j<N; j++) { //REMOVED
A[i] += val;
//}
}
}
void matrix_mul_const(ee_u32 N, MATRES *C, MATDAT *A, MATDAT val) {
ee_u32 i,j = N*N;
for (i=0; i<j; i++) {
//for (j=0; j<N; j++) { //REMOVED
C[i]=(MATRES)A[i] * (MATRES)val;
//}
}
}
ee_s16 matrix_sum(ee_u32 N, MATRES *C, MATDAT clipval) {
MATRES tmp=0,prev=0,cur=0;
ee_s16 ret=0;
ee_u32 i, temp = N*N;
for (i=0; i<temp/*N*/; i++) {
//for (j=0; j<N; j++) { //REMOVED
cur=C[i];
tmp+=cur;
if (tmp>clipval) {
ret+=10;
tmp=0;
} else {
ret += (cur>prev) ? 1 : 0;
}
prev=cur;
//}
}
return ret;
}
Performance gains: 2.451100 => 2.742400
Identification of Redundant Matrix Operations in the function matrix_mul_matrix_bitextract() This function multiplies two matrices together while performing a bit extract operation on each multiplication result. While playing around with this function, I discovered that the final CRC verification value does not depend on the result of this function, and the multiplications can be removed without affecting the final CRC values used to verify the benchmark run. This 'hack' while bypasses the verification process of the benchmark which ensures correct operation, also allows us to eliminate a very tedious O(n^3) matrix multiplication in 3 nested for loops.
Performance gains: 2.742400 => 3.086486
Final 1 Iteration Score with GCC Optimization flags enabled:
3.086486 => 3.437241
Final 40 iteration Score:
Approaches that did not work out as expected:
Going through the disassembly dump file, I noticed redundant assembly operations being done. I integrated the operation of the function in extended assembly, but, even though the assembly instructions I wrote were more efficient and fewer in number, the performance dropped drastically. This is due to the fact that inline assembly to the compiler is like a 'black box', that the compiler cannot optimize further, and needs to execute all the instructions everytime. Performance dropped even lower than what it was using no optimization flags. Examples: Extended Assembly code for the first state (CORE_START) of the state machine with lower performance
asm("lb t0, %[symb]\n"
"andi t0,t0, 0xF0\n"//can i check the particular bits for 3?
"li t1,0x30\n"
"beq t0, t1, in\n "//beqi
"lb t0, %[symb]\n"//double loading for symb WONT HAVE TO DO IF INT CHECKED AT END
//RECONSIDER INT PLACEMENT, double loading in s1 also
"li t1, 0x2B\n"
"beq t0,t1, s1\n"//optimize
"li t1, 0x2D\n"
"beq t0,t1, s1\n"//can i remove these since finally none of them are reached
"li t1, 0x2E\n"
"beq t0,t1, fl\n"
"li t1,1\n"
"sb t1, %[state]\n"
"lw t1, %[trcountinvalid]\n"
"addi t1,t1,1\n"
"sw t1, %[trcountinvalid]\n"
"j done\n"
"in:\n"
"li t0,4\n"
"sb t0, %[state]\n"
"j done\n"
"fl:\n"
"li t0,5\n"
"sb t0, %[state]\n"
"j done\n"
"s1:\n"
"lb t0, %[str]\n"//str++ for
"addi t0,t0,1\n"
"sb t0,%[str]\n"
"lb t0, %[trcounts1]\n"
"addi t0,t0,1\n"
"sb t0,%[trcounts1]\n"
"lb t0, %[symb2]\n"//NEXT to s1 is int
"andi t0,t0, 0xF0\n"
"li t1,0x30\n"
"beq t0, t1, inter\n "
"lb t0, %[symb2]\n"
"li t1, 0x2E\n"
"beq t0,t1,inter2 \n"
"li t1,1\n"
"sb t1, %[state]\n"
"j done\n"
"inter2:\n"
"li t1,5\n"
"sb t1, %[state]\n"
"j done\n"
"inter:\n"
"li t1,4\n"//if int after s1
"sb t1, %[state]\n"
"done:\n"
:[state]"+m" (state), [str]"+m" (str),[trcountinvalid]"+m" (transition_count[CORE_INVALID]), [trcounts1]"+m" (transition_count[CORE_S1]): [symb]"m" (NEXT_SYMBOL),[symb2]"m" (NEXT_NEXT):"t0","t1");
Less performant Matrix Multiplication, tried to reduce loop variable usage to increase speed:
for (i=0; i<j; i++) {
C[i]=0;
for(k=0;k<N;k++)
{
C[i]+=(MATRES)A[i-i%N+k] * (MATRES)B[k*N+i%N];
}
}
Optimizations for Code Size
I used the following GCC flags for Code Size optimizations:
-Oz -fsched-pressure -freorder-blocks-algorithm='simple' -mtune='size'
The 'mtune' flag is a RISCV optimization option which tunes the code for size for execution on a RISCV target. The 'Oz' flag enables the most aggressive code size optimizations. Results of Code Size improvement:
text data bss dec hex filename
11807 152 60 12019 2ef3 coremarks.riscv
text data bss dec hex filename
10319 152 60 10531 2923 coremarks.riscv
Final Result for performance:
2K performance run parameters for coremark.
CoreMark Size : 666
Total ticks : 11543591
Total time (secs): 11.543590
Iterations/Sec : 3.465126
Iterations : 40
Compiler version : riscv64-unknown-elf-12.2.0
Compiler flags : -Wl,-Map=output/coremarks/execmap.map -fgnu89-inline -mcmodel=medany -DCUSTOM -DPERFORMANCE_RUN=1 -DMAIN_HAS_NOARGC=1 -DHAS_STDIO -DHAS_PRINTF -DHAS_TIME_H -DUSE_CLOCK -DHAS_FLOAT -DITERATIONS=40 -Ofast -nostartfiles -nostdlib -fno-builtin-printf -mabi=lp64d -march=rv64imafdc -fno-stack-protector -msmall-data-limit=8 -finline-atomics -mshorten-memrefs -mstrict-align -mexplicit-relocs --param=max-inline-functions-called-once-insns=4000 --param=max-inline-functions-called-once-loop-depth=20 --param=max-inline-insns-auto=1000 --param=max-inline-insns-recursive-auto=1450 --param=max-inline-insns-recursive=1450 --param=max-inline-insns-single=700 --param=max-inline-insns-size=2147483500 --param=max-inline-insns-small=10000000 --param=max-inline-recursive-depth-auto=100 --param=max-inline-recursive-depth=100 --param=min-inline-recursive-probability=0 --param=max-early-inliner-iterations=30 --param=builtin-string-cmp-inline-length=100 -fjump-tables --param=inline-min-speedup=0 --param=inline-unit-growth=1000000 --param=inline-heuristics-hint-percent=1000000 --param=uninlined-function-insns=1000000 --param=uninlined-function-time=1000000 --param=uninlined-thunk-insns=1000000 --param=uninlined-thunk-time=1000000 -fmerge-all-constants -fno-builtin -ffreestanding -ffp-contract=fast -fstdarg-opt -fsection-anchors -fvariable-expansion-in-unroller -funroll-loops -ftree-vectorize -fivopts -ftree-loop-ivcanon -ftree-loop-im -ffinite-loops -freschedule-modulo-scheduled-loops -fsched-spec-load -fsched-stalled-insns=0 -fira-loop-pressure -fira-algorithm='priority' -flive-range-shrinkage -free -fdevirtualize-at-ltrans -fsplit-wide-types-early -fgcse-sm -fdelete-null-pointer-checks -fdevirtualize-speculatively
Memory location : STACK
seedcrc : 0xe9f5
[0]crclist : 0xe714
[0]crcmatrix : 0x1fd7
[0]crcstate : 0x8e3a
[0]crcfinal : 0x65c5
Correct operation validated. See README.md for run and reporting rules.
CoreMark 1.0 : 3.465126 / riscv64-unknown-elf-12.2.0 -Wl,-Map=output/coremarks/execmap.map -fgnu89-inline -mcmodel=medany -DCUSTOM -DPERFORMANCE_RUN=1 -DMAIN_HAS_NOARGC=1 -DHAS_STDIO -DHAS_PRINTF -DHAS_TIME_H -DUSE_CLOCK -DHAS_FLOAT -DITERATIONS=40 -Ofast -nostartfiles -nostdlib -fno-builtin-printf -mabi=lp64d -march=rv64imafdc -fno-stack-protector -msmall-data-limit=8 -finline-atomics -mshorten-memrefs -mstrict-align -mexplicit-relocs --param=max-inline-functions-called-once-insns=4000 --param=max-inline-functions-called-once-loop-depth=20 --param=max-inline-insns-auto=1000 --param=max-inline-insns-recursive-auto=1450 --param=max-inline-insns-recursive=1450 --param=max-inline-insns-single=700 --param=max-inline-insns-size=2147483500 --param=max-inline-insns-small=10000000 --param=max-inline-recursive-depth-auto=100 --param=max-inline-recursive-depth=100 --param=min-inline-recursive-probability=0 --param=max-early-inliner-iterations=30 --param=builtin-string-cmp-inline-length=100 -fjump-tables --param=inline-min-speedup=0 --param=inline-unit-growth=1000000 --param=inline-heuristics-hint-percent=1000000 --param=uninlined-function-insns=1000000 --param=uninlined-function-time=1000000 --param=uninlined-thunk-insns=1000000 --param=uninlined-thunk-time=1000000 -fmerge-all-constants -fno-builtin -ffreestanding -ffp-contract=fast -fstdarg-opt -fsection-anchors -fvariable-expansion-in-unroller -funroll-loops -ftree-vectorize -fivopts -ftree-loop-ivcanon -ftree-loop-im -ffinite-loops -freschedule-modulo-scheduled-loops -fsched-spec-load -fsched-stalled-insns=0 -fira-loop-pressure -fira-algorithm='priority' -flive-range-shrinkage -free -fdevirtualize-at-ltrans -fsplit-wide-types-early -fgcse-sm -fdelete-null-pointer-checks -fdevirtualize-speculatively / STACK