Fast Call Graph Profiling

Abstract

CPUer er ikke-spesialiserte chiper som kan utføre alle beregninger, og de er ikke optimalisert til å utføre noen beregninger mye raskere enn andre. Det er mulig å lage chiper som er optimaliserte til å utføre et begrenset sett med beregninger mye raskere enn en CPU kan gjøre tilsvarende beregninger. Slike chiper kalles akseleratorer. Siden CPU-ytelse has stagnert de siste årene har forskere foreslått å bruke re-konfigurerbare chiper, slik som Field Programmable Gate Arrays og Coarse Grained Reconfigurable Arrays, som akseleratorer som kan akselerere hvilket som helst program. For at programmerer skal vite hvilken del av programmet som bør akselereres så han han kjøre kode som obsererer hvordan hans program oppfører seg. Dersom det er mulig å kjøre programmet en gang med kode som observerer flere forskjellige aspekter ved programmet, uten at koden for de forskjellige aspektene påvirker hverandres observasjoner, så er det mulig å spare tid fordi man trenger kun å kjøre programmet en gang.

I denne oppgaven har jeg undersøkt om det er mulig å observere både hvor mye tid som blir brukt i hver funksjon i koden og observere den dynamiske funksjonskall-grafen i en enkelt kjøring av programmet. For å gjøre dette så har jeg laget Fast Call Graph profiler som observerer funksjonskall-grafen til programmer. Jeg har også evaluert hvor mye dette verktøyet sakker ned koden som det observerer og sammenlignet med hvor mye liknende vertøy sakker ned koden.

Det jeg har funnet er at Fast Call Graph profiler påvirker ikke i noe stor grad hvor mye tid programmet bruker i hver funksjon. Det vil si at det er mulig å både observere hvor mye tid som brukes i hver funksjon og observere den dynamiske funksjonskall-grafen samtidig og få brukbare resultater. Fast Call Grap profiler sakker programmet ned betydelig mindre enn Gprof og innebygd Clang observering, som var de andre verktøyene jeg sammenlignet med.

CPUs are general purpose chips that are able to perform all computations, but they are not optimized to perform any particular computation significantly faster than others. It is possible to create chip that are optimized to perform a limited set of computations that are much faster than the CPU at those specific computations. Such chips are called accelerators. Since CPU performance has stagnated in recent years researchers have suggested using reconfigurable chips such as Field Programmable Gate Arrays and Coarse Grained Reconfigurable arrays as accelerators that can be programmed to accelerate any program. To be able to know which part of a program that should be accelerated the programmer can profile the program to gain information on how the program behaves. If it is possible to profile multiple kinds of information in a single run of the program without the profilers interfering with each other it is possible to save time by not having to run the program multiple times.

In this thesis I have investigated if it is possible to do profile both how much time is spent in each function of the program and profile the dynamic call graph of the program in a single run. To this I have created the Fast Call Graph profiler which can profiles the dynamic call graph of programs. I also evaluated how much overhead the profiler causes and how it compares to similar tools that profile the dynamic call graph.

I found that the Fast Call Graph profiler does not change the time distribution information in any significant way. This means that it is possible to do both time distribution profiling and dynamic call graph profiling in a singe program run and get useful profile results. The overhead of the Fast Call Graph profiler is also significantly lower than the tools I compared it with which were Gprof and the instrumentation built into Clang.