Profiling an Assembly Program

Project 5: Profiling an Assembly Program

GoalIn this project you will learn how to find where a program spends most of the execution timeusing statistical profiling, and you will implement your own statisticalprofiler.Task 0: Download the initial sources and start tsearch_asm6.sTo start your project clone the project5 repository:git clone /homes/cs250/sourcecontrol/work/$USER/project5-src.gitcd project5-srcThe implementation of binary tree search in C is similar to the one from project4. You will copyyour implementation from tsearch_asm5.s into tsearch_asm6.sTo test the implementation type

data 149 $ ./run_bench.sh

================== Running TreeSearch Iterative in C benchmark ================

Total CPU time: 4.125084397 seconds

real 0m7.960s

user 0m7.830s

sys

0m0.124s

================== Running ASM 6 benchmark ================

…

It will also try to run the tsearch_asm6.s but it will fail if it is not implemented yet.Task 1:Insert profiling code in the benchmark

The file profil.c implements the code that starts profiling the program, and writes the histogram

of the file at the end:void start_histogram();void print_histogram();Open the file profil.c and see how start_histogram creates an array of counters, that is passedto profil(), that creates the execution histogram. Se代写Profiling an Assembly Program e "man profil". This histogram is an array ofintegers, where every integer represents an instruction or group of instruction. profil() activates atimer that every .01secs looks at the program counter of the program,and increments thecounter in the histogram that corresponds to that program counter.Open the file tsearch_bench_better.c and find the main(). Then above main, you will insert theexternal prototypes of start_histogram() and print_histogram(): as follows.Also call

start_histogram() at the beginning of main() and print_histogram() at the end.

extern void start_histogram();

extern void print_histogram();

/*

* Main program function. Runs the benchmark.

*/

__attribute__ (( visibility("default") ))

int

main(int argc, char **argv)

start_histogram();

…..

print_histogram();

}Modify run_bench, so both gcc compilation commands link profil.c

echo ================== Running TreeSearch Iterative in C benchmark ================

gcc -g -static -o tsearch_bench_iterative_c tsearch_bench_better.c tsearch.c AVLTree.c tsearch_iterative.c profil.c || exit 1

…gcc -g -static -o tsearch_bench_asm6 tsearch_bench_better.c tsearch.c AVLTree.c tsearch_asm6.s profil.c || exit 1

…Now type run_bench.

data149 $ ./run_bench.sh

You will find the following file:

ls *.hist

tsearch_bench_iterative_c.hist

Open this file, and you will observe that it contains the program counters in the histogram thatare larger than 0. The counter is multiplied by 1ms, so the counters are displayed in ms. Identifythe program counter where the program is spent most of its time:

Then run the command "nm -v tsearch_bench_iterative_c | less"that prints all the functions in

the program sorted by address, and finds the function that includes this program counter. Usethe up/down arrow keys to navigate "less".data 163 $ nm -vtsearch_bench_iterative_c | less

….

000000000045aee0 T __stpcpy_evex

000000000045b340 T __strchr_evex

000000000045b5e0 T __strchrnul_evex

000000000045b840 T __strcmp_evex

000000000045bcb0 T __strcpy_evex

000000000045c100 T __strlen_evex

000000000045c280 T __strncmp_evex

000000000045c7f0 T __strncpy_evex….__strcmp_evex is the function where tsearch_bench_iterative_c spends most of its time.Now to find the assembly instruction type "objdump -d tsearch_bench_iterative_c | less" thatprints the assembly instructions that make the program and their address in the program. Findthe assembly instruction that includes the counter 45b870, that is 45b86c . This is because0x45b870 is larger than 45b86c but smaller than 45b873.objdump -dtsearch_bench_iterative_c | less000000000045b840 <__strcmp_evex>:45b840:f3 0f 1e fae

0f b6 04 17movzbl (%rdi,%rdx,1),%eaxThe instruction marked in red is the instruction that is taking the most time.Task 2: Write your own profiler program.Using the example in Task1, write a program myprof.c that prints a table with the top 10

functions where the program spends most of its time and it will also print for each function,which instructions take most of the time . The program will take thfollowing arguments:myprof progThe program will open prog.hist, and store the entries in an array of structs with the programcounter and the time in ms. Then it will call system("nm -v prog > nm.out") using the system()function (see man system) that executes a command inside a C program, and redirect it into afile nm.out. Myprof will read nm.out, and it will also store the entries in an array of structs withprogram counters and function names. Then for every pc in the histogram, it will increment thetime in ms of the corresponding function. After this is done, it will sort the functions by time, andidentify the 10 top functions where the execution spends most of the time. Finally, it will alsoprint the assembly code of these functions using objdump, and print the time spend in eachassembly instruction. Only the instructions with a time greater than 0 are printed.The output will look like the following example:myprof tsearch_bench_iterative_cT

e8 cc e3 ff ffcall460ca0Task 3:Using your profiler, improve your tsearch_asm6.sUsing your profiler, optimize your implementation in tsearch_asm6.sGradingThe grading will be done during lab time. You don't need to turn in the implementation since thegit repository will have your most recent implementation.