Douglas Do
email: douglas@dcc.ufmg.br

Couto Teixeira

Caroline Collange

Fernando Magno
email: fernando@dcc.ufmg.br

Quintão Pereira

Fusion of calling sites *

The increasing popularity of Graphics Processing Units (GPUs), has brought renewed attention to old problems related to the Single Instruction, Multiple Data execution model. One of these problems is the reconvergence of divergent threads. A divergence happens at a conditional branch when different threads disagree on the path to follow upon reaching this split point. Divergences may impose a heavy burden on the performance of parallel programs. In this paper we propose a compiler-level optimization to mitigate this performance loss. This optimization consists in merging function call sites located at different paths that sprout from the same branch. We show that our optimization adds negligible overhead on the compiler. It does not slowdown programs in which it is not applicable, and accelerates substantially those in which it is. As an example, we have been able to speed up the well known SPLASH Fast Fourier Transform benchmark by 11%.

Introduction

Graphics Processing Units (GPUs) are becoming a staple hardware in the high-performance world. They provide a simple, cheap, and efficient platform in which parallel applications can be developed [START_REF] Nickolls | The gpu computing era[END_REF]. Since the release of CUDA, in early 2006 [START_REF] Garland | Parallel computing experiences with CUDA[END_REF], a plethora of programming patterns and algorithms have been designed to run in this environment, touching multiple fields of knowledge, including Biology, Chemistry and Physics [START_REF] Navarro | A survey on parallel computing and its applications in data-parallel problems using GPU architectures[END_REF].

The basic operating principle of this hardware consists in running the threads of Single Program, Multiple Data (SPMD) programs in lockstep, so to exe-cute their identical instructions on Single Instruction, Multiple Data (SIMD) units. This execution model is, nowadays, known as Single Instruction, Multiple Threads (SIMT), a term coined by Nvidia's engineers [START_REF] Nickolls | The gpu computing era[END_REF]. SIMT execution has gained momentum beyond the graphics processing ecosystem. SPMD programming environments like OpenCL1 , OpenACC2 or OpenMP 4.03 can target SIMD architectures like GPUs, multi-core CPUs with SIMD extensions, and even Intel Xeon Phi accelerators.

Nevertheless, in spite of all these advances, programming SPMD applications for SIMD architectures remains a challenging task. One of the reasons behind this difficulty is a phenomenon known as Thread Divergence. When facing a conditional branch, two threads diverge if they disagree on which path to take. Divergences are a problem because they have an impact on the program's performance. In other words, a divergence splits threads into two groups, upon reaching a conditional branch. Only one of these groups contain threads that do useful work at a given point in time.

We have designed, implemented and tested a compiler optimization that mitigates this performance loss. We name this optimization Fusion of Calling Sites (FCS). Our optimization relies on a simple idea: threads should enter functions in lockstep to minimize the effects of divergences. Therefore, whenever a function is invoked at the two different paths that stem from a conditional test, we merge the two calling sites into one single invocation of that function. This optimization can benefit implicit SIMD architectures, such as those found in GPUs, and explicit SIMD hardware like the Xeon Phi. In the latter case, the compiler merges threads together to form SIMD instruction, handling divergence with mask-predicated instructions [START_REF] Karrenberg | Improving performance of opencl on cpus[END_REF].

As we show in Section 3, our algorithm scans blocks of code within the program, performing the merging whenever it is possible. In this paper, we demonstrate that our optimization is: (i) easy to implement, (ii) innocuous when non-applicable and (iii) effective when used. Our optimization has low computational complexity in practice. In other words, it always applies a constant number of operations per pair of calling sites that it merges. If a program does not present any opportunity for this merging to happen, then we do not impose any runtime overhead onto the compiler, nor onto the executable program, once it is deployed. In Section 4, we show the potential of our optimization through a toy benchmark, and show its applicability in the well-known implementation of Fast Fourier Transform available in SPLASH 4 . In the former benchmark, FCS reduces the number of divergent instructions by 55%, and on the latter by 11%.

Overview of the Approach

Figure 1 will let us illustrate thread divergences. This phenomenon characterizes the Single Instruction, Multiple Data execution model typical of Graphics Processing Units. These processors organize threads in groups that execute in lockstep. Such groups are called warps in NVIDIA's jargon, or wavefronts in AMD's. We can imagine that threads in the same warp use different arithmetic and logic units, but share the same instruction control logic. Control flow divergences happen when threads in a warp follow different paths after processing the same branch. If the branching condition is data divergent, then it might be true to some threads, and false to others. In face of divergences, some threads will take the "then" part of the branch in Figure 1, and others will take the "else" part. Due to the shared instruction control logic, only one group of threads will be allowed to do useful work at a given instant. The execution trace at the bottom of Figure 1 shows which threads are active at each cycle, assuming an architecture that allows four threads simultaneously in flight.

When two threads diverge, the hardware should reconverge them as earlier as possible to maximize the amount of active workers per cycles. A reconvergence point is the earliest instruction in the program where we can expect control flow paths to join regardless of the outcome or target of the divergent branch. Fung et al. have shown that the post-dominator of a branch is -usually -the best place to reconverge threads [START_REF] Fung | Dynamic warp formation and scheduling for efficient GPU control flow[END_REF]. We say that a node v in a CFG post-dominates a node u if any path from v to the end of the CFG must go across u. In Figure 1, basic block end is the postdominator of every other block. Yet, as Fung et al. themselves have also shown, reconverging threads at the post-dominators of branches is far from being a perfect solution to divergences. Figure 1 illustrates An execution trace of the program. If a thread t executes an instruction at cycle j, we mark the entry (t, j) with . Otherwise, we mark it with •. In this example we assume that each invocation of function divide takes one hundred cycles to execute.

l 0 : c = T id % 2
16 m = T id × 1000 • • 17 a = T id + 1 • • 18 d1 = divide(m, a) • • . . . 118 m1 = T id × 2000 • • 119 a1 = T id + 2 • • 120 p = read() • • 121 p1 = p × a1 • • 122 d2 = divide(m, a) • • . . . 222 print(p1) • • 223 sync 224 R = phi(d1, d2) 225 print(R)
this situation particularly well. The divide function is invoked at both sides of the branch in Figure 1. Even though this function must be executed by all the threads that reach the divergent branch, these threads will be entering the function at different execution cycles due to the divergence. Consequently, the instructions that constitute function divide will be called twice: once for the threads in the "then" part of the branch, and another time for the threads in the "else" part. In this case, reconverging threads at post-dominators of divergent points will not avoid the redundant execution of divide. If divide runs for a long time, then we will be missing the opportunity to share many execution cycles among different threads. The goal of FCS is to reconverge threads at the entry points of functions. We will accomplish this goal by changing the structure of the program's control flow graph, as we will explain in the next section.

Fusion of Calling Sites

Figure 2 provides a high-level view of FCS. The function merge call site tries to join call sites, until this action is no longer possible. If a merging happens, then the function invokes itself recursively, otherwise the optimization terminates. Candidate branches are found via the function find joinable calls, which is also depicted in Figure 2. This procedure looks for paths that stem from the same branch b and that lead to different calls of the same function F . If the cost of transforming the program's control flow graph is lower than a certain threshold, then the prospective branch is sent to function merge cfg, which is in charge of transforming the program.

We use the program from Figure 1 as an example to illustrate our transformation. The program in that figure has one candidate branch, at label 1 . Our function find joinable calls will detect two paths from this branch leading to invocations of the same function. The first path is formed by the sequence of labels

1 2 → 3 → 4 . The second path if formed by the sequence 1 → 5 → 6 → 7 → 8 → 9 .
After finding the paths, our routine merge cfg will produce a new version of the program.

Figure 4 provides an overview of the transformation that merge cfg performs. This function creates a common label, e.g., r , that will join the two call sites that we want to fuse. We use the φ-functions of the Static Single Assignment [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF] sentation in which each variable has only one definition site [START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF]. Nowadays, almost every compiler uses this intermediate representation to manipulate programs. The SSA format relies on φ-functions to join different variables into common names. Going back to Figure 4, an instruction such as a 1 = φ(a 11 , a 21 ) will assign to variable a 1 the value of a 11 if the program flow reaches that operation through label 1 , and will assign a 21 to a 1 , if the program flow comes through label 2 . Figure 5 shows the program that we obtain after applying the FCS optimization onto the function seen in Figure 1. This time we have only one invocation site for function divide, which will be reached independent on the way that we branch at targeting such(l 1 ) and succ(l 2 ) rename every use of r 1 to r in P rename every use of r 2 to r in P P' = strictify_program(P) return P' ter our transformation, we may have programs that are not strict, as we have seen in the example. To obtain strictness back, we apply the function strictify program in the transformed code. This function inserts dummy definitions to all the variables defined within the scope of the branch, and that were used after the fused call. In our example, p 1 is the only such variable. If a variable is used at one side of the branch, then the dummy definition is inserted in the other side. Figure 6 shows this transformation.

Termination: The function merge call site always terminates due to a simple argument: the fusion of two function call sites do not enable the fusion of further calls. In other words, if a program has a number N of branches that pass the profit test performed by the function find joinable calls; then no more than N branches will be fused by our optimization. Therefore, as the number of branches in a program is limited, our algorithm is guaranteed to terminate.

Complexity:

We call function merge call site recursively at most once per potentially profitable branch in the program. Each call of this function scans all the conditional tests in a program, look-l 3 : ... ing for the most profitable fusion (see line 14 of find joinable calls in Figure 2). If we have O(N ) blocks in the program, we may have to inspect O(N ) branches. Each inspection is O(N ), as it involves a traversal of the paths that sprout away from the conditional. If two calls must be merged, then we resort to function merge cfg, whose complexity is bound by strictify program. This last function is standard in compilers, and runs in O(N ). Therefore, our functions (merge call site, merge cfg and strictify program) run -together -in O(N 4 ).

This complexity may seem very high at a first glance. However, in practice only a handful of branches lead to two different calls of the same function. Furthermore, if we order the branches by profit, then we can inspect each one of them in line 14 of find joinable calls at most once. Therefore, in practice our optimization runs in O(N 2 ), where N is the number of basic blocks in the program code.

Experimental Results

Experimental setup. The of call sites may be applied onto SPMD programs running on SIMD machines, following the SIMT execution model. There are several different computer architectures that fit into this model, from GPUs and vector units (SSE, MMX, etc) to Long's Minimal Multi-Threading architectures [START_REF] Long | Minimal multi-threading: Finding and removing redundant instructions in multi-threaded processors[END_REF]. As the transformation is performed at source code level, our technique makes no assumption about the way the SPMD code is later transformed into SIMD instructions. Evaluating FCS separately on each programming environment and each platform would be tedious. Furthermore, this approach would produce results that are hard to generalise. Therefore, we chose to evaluate FCS on generalpurpose parallel applications in a micro-architectureagnostic simulator which models an ideal SIMT machine. This simulator has been implemented by Milanez et al. [START_REF] Milanez | Thread scheduling and memory coalescing for dynamic vectorization of SPMD workloads[END_REF], who have made it publicly available. The simulator is implemented on top of the PIN binary instrumentation framework 5 . The Pin tool reads the binary and produces traces representing every instruction that each thread executes. Then, we replay the traces using different heuristics (that we describe in the next paragraph) to re-converge threads. To perform the code transformation, we have used the LLVM compiler [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transformation[END_REF]. Our performance numbers have been obtained in the following way: we run the PIN-based simulator on the original program that LLVM produces at its -O3 optimization level.

Then, we apply FCS on that binary, and re-run the simulator.

Heuristics for Thread Reconvergence: our simulator accepts different thread reconvergence heuris-tics. Such heuristics determine the next instruction to be fetched in an SIMT architecture. We chose to simulate four heuristics: MinPC, MinSP-PC, MaxFun-MinPC, and Long-MinSP-PC. These heuristics are described below:

Min-PC: this technique, due to et al. [START_REF] Quinn | Compiling C* programs for a hypercube multicomputer[END_REF], is the thread reconvergence heuristics typically adopted in the implementation of graphics processing units: in face of divergent lines of execution, the fetcher always chooses the heuristics with the smallest Program Counter (PC) to process. The rational behind this heuristics is simple: in the absence of backward branches, given two program counters: n and n + 1, the latter will be executed after the former. By fetching the instruction at the lowest PC, the hardware maximizes the chance of keeping the threads in lockstep execution.

MinSP-PC: this approach was proposed by Collange [START_REF] Collange | Stack-less SIMT reconvergence at low cost[END_REF] and is on top of Quinn's Min-PC heuristic [START_REF] Quinn | Compiling C* programs for a hypercube multicomputer[END_REF]. It is used in programs that contain function invocations, and its bedrock is the fact that when a function is called, the stack grows down. Thus, threads running more deeply nested function calls have smaller Stack Pointers (SP). Based on this observation, this heuristic fetches instructions to threads with the smallest SP, because it assumes that these threads are behind in the program's execution flow.

MaxFun-MinPC: this heuristic, Maximum Function Level -Minimum PC, is similar to MinSP-PC, but instead of choosing the smallest SP, it chooses the thread that has the highest number of activation records on the stack. Therefore, this heuristic would have the same behavior of MinSP-MinPC if all activation records had the same size.

Long: Long et al. [START_REF] Long | Minimal multi-threading: Finding and removing redundant instructions in multi-threaded processors[END_REF] have created a heuristic to analyze redundancies in SIMD programs. Their key idea is to add memory to each thread. One thread uses the memory of the others to advance or stall. If the current PC of a thread t0 is in the recent history of another thread t1, then thread t0 is probably behind t1. In this case, t0 needs to progress to catch up with t1. The idea of Long's heuristic can be used to create other heuristics. When multiple threads have the same highest priority, the original heuristic executes these threads alternately, but the variations of Long's heuristic use other policies to choose the next thread to execute. In this paper we used Long's with Min-PC: when multiple threads have the highest priority, the basic block of the threads with smallest PC is executed first. Then, all priorities are recounted again for the next choice.

The Benchmarks: To probe the effectiveness of the FCS optimization, we chose to apply it on gen- LoC: number of lines of code, including comments; Inst: number of assembly instructions; Trace: number of instructions in millions, that each benchmark executes with its standard input Merge: number of call sites that we have merged.

eral purpose SPMD applications from the PAR-SEC/SPLASH benchmark suite [START_REF] Bienia | The PARSEC benchmark suite: characterization and architectural implications[END_REF].

We have used three programs from these collections: FFT, Fluidanimate and Swaptions. Figure 8 shows some characteristics of these benchmarks. These are the PARSEC programs that we manage to compile using LLVM 3.4. These programs are large, and contain only a handful of branches that touch the same function call through different program paths. Therefore, the benefits that we can expect from the application of FCS on these benchmarks is limited. Hence, to demonstrate the possibilities of our optimization, we shall apply it also onto the program first seen in Figure 1. Performance analysis: Figure 9 shows the result of combining our optimization with different heuristics and different numbers of available threads. Numbers above bars show relative speedup compared to not using our optimization. We performed these experiments on an Intel Xeon CPU E5-2620 2.00GHz processor with 16 GB of DDR2 RAM running Linux running Ubuntu 12.04 (Kernel 3.2.0). Nevertheless, our results do not dependend on these features, as they have been produced through simulation. Our experiments let us draw some conclusions. MinPC-based heuristics (MinSP-PC and MinPC) tend to benefit more from FCS. This advantage exists because such heuristics favour the synchonization of threads before a function call. For instance, in Figure 5 both, MinPC and MinSP-PC, will fetch the instructions in all the smaller labels, e.g., 2 -9 , before grabbing r , which lays further ahead in the program's binary layout. Consequently, the heuristic published by Long et al. does not benefit as much, because it has been designed in a way that is totally oblivious to the invocation of functions. Figure 9 also shows that our optimization does not impact negatively the benchmarks that we have tested. The only exceptions are due to MinPC in Swaptions (four threads) and in FFt (16 threads). This negative impact is due to back-edges, e.g., jumps that lead the program's flow back to the beginning of a loop. In face of repeat-style iterators, which test the exit condition at the end, MinPC may fail to reconverge threads within the loop. In this case, the slightly larger code that we produce ends up causing an increase on the number of instructions that are not shared among threads. We have not observed this behavior in the other heuristics. There are other divergence aware optimizations that target loops, instead of branches, as we do. For instance, Carrillo et al. [START_REF] Carrillo | A controlstructure splitting optimization for gpgpu[END_REF] have designed a code transformation called Branch Splitting, which divides parallelizable loops enclosing multi-path branches. In this way, they produce multiple loops, each one with a single control flow path. In similar lines, Lee et al. [START_REF] Lee | Openmp to gpgpu: a compiler framework for automatic translation and optimization[END_REF] have proposed Loop Collapsing, a technique that reduces divergences by combining multiple divergence loops into common iterators. Han et al. [START_REF] Han | Reducing branch divergence in gpu programs[END_REF] have further extended Lee's approach with the notion of Iteration Delaying. This transformation recombines loops containing divergent branches, so that threads tend to remain together for a longer time. None of these optimizations is designed to handle function calls specifically, and, more importantly: none of them would be able to carry out the optimization that we discuss in this paper. Function-Aware Heuristics to Reconverge Threads: there exist different heuristics implemented at the hardware level that enforce early reconvergence of divergent threads [START_REF] Dechene | Multithreaded instruction sharing[END_REF][START_REF] González | Thread fusion[END_REF][START_REF] Long | Minimal multi-threading: Finding and removing redundant instructions in multi-threaded processors[END_REF]. In particular, Milanez et al. [START_REF] Milanez | Thread scheduling and memory coalescing for dynamic vectorization of SPMD workloads[END_REF] have proposed the Min-SP-PC technique, one of the heuristics that we use in this paper. We emphasize that our work is orthogonal and complementary to these research efforts. Our optimization can be applied on programs independent on the heuristic used to reconverge threads. Nevertheless, as we have observed in Section 4, some of these heuristics yield greater benefit when combined with our approach.

Conclusion

This paper has introduced Fusion of calling sites, a new compiler optimization that mitigates the negative impact caused by divergences on applications running in SIMD fashion. This optimization consists in rearranging the control flow graph of a program, so to merge different function call sites at common program points. In this way, the merged function can be invoked together by divergent threads. There exists, presently, a great deal of effort to develop techniques, at the hardware and software level, to reduce the effects of divergences. Our work is complementary to these efforts: gains are cumulative with the increasing performance of graphics cards, and it adds a negligible cost over compilation time. More importantly, we believe that optimizations such as Fusion of calling sites contribute to shield application developers from particularities of the parallel hardware, such as divergence and reconvergence of threads.

Software:

the software used in this paper, including our simulator and binary instrumentation tool, is available at https://github.com/dougct/ function-call-fusion.

l 1 :

 1 bz c, l 5 l 2 : m = T id × 1000 l 3 : a = T id + 1 l 4 : d 1 = divide(m, a) l 5 : m 1 = T id × 2000 l 6 : a 1 = T id + 2 l 7 : p = read() l 8 : p 1 = p × a 1 l 9 : d 2 = divide(m 1 , a 1 ) l 10 : print(p 1 )

Figure 1 :

 1 Figure 1: (Top) A program whose performance may experience a slowdown due to divergences. (Bottom)An execution trace of the program. If a thread t executes an instruction at cycle j, we mark the entry (t, j) with . Otherwise, we mark it with •. In this example we assume that each invocation of function divide takes one hundred cycles to execute.

Figure 2 :

 2 Figure2provides a high-level view of FCS. The function merge call site tries to join call sites, until this action is no longer possible. If a merging happens, then the function invokes itself recursively, otherwise the optimization terminates. Candidate branches are found via the function find joinable calls, which is also depicted in Figure2. This procedure looks for paths that stem from the same branch b and that lead to different calls of the same function F . If the cost of transforming the program's control flow graph is lower than a certain threshold, then the prospective branch is sent to function merge cfg, which is in charge of transforming the program.We use the program from Figure1as an example to illustrate our transformation. The program in that figure has one candidate branch, at label 1 . Our function find joinable calls will detect two paths from this branch leading to invocations of the same function. The first path is formed by the sequence of labels 1 2 → 3 → 4 . The second path if formed by the sequence 1 → 5 → 6 → 7 → 8 → 9 . After finding the paths, our routine merge cfg will produce a new version of the program.Figure4provides an overview of the transformation that merge cfg performs. This function creates a common label, e.g., r , that will join the two call sites that we want to fuse. We use the φ-functions of the Static Single Assignment[START_REF] Cytron | Efficiently computing static single assignment form and the control dependence graph[END_REF] (SSA) form to join function arguments. SSA form is a program repre-

Figure 3 :Figure 4 : 2 l 1 : bz c, l 5 l 2 : 1 l 4 : goto l r l 5 : 1 l 9 :Figure 5 :

 342152145195 Figure 3: Routine that transforms the program's control flow graph. We let succ( ) be the unique successor of label .

  l p : p aux = NULL l 4 : goto l r l 7 : ...

l 8 : p 1 p × a 1 l 9 :Figure 6 :

 8196 Figure 6: New definitions of p 1 to ensure strictness.

Figure 7 :

 7 Figure 7: (Top) The same program from Figure 1 after being optimized. (Bottom) An execution trace of the program. If a thread t executes an instruction at cycle j, we mark the entry (t, j) with the symbol . Otherwise, we mark it with •.

Figure 8 :

 8 Figure 8: The benchmarks that we have analyzed. LoC: number of lines of code, including comments; Inst: number of assembly instructions; Trace: number of instructions in millions, that each benchmark executes with its standard input Merge: number of call sites that we have merged.

Figure 9 :

 9 Figure 9: Execution time reduction after applying FCS.

  let r 1 = F(p 11 , ..., p 1n ) be at l 1 in P let r 2 = F(p 21 , ..., p 2n ) be at l 2 in P

	let p 1 = ɸ(p 11 , p 21 )
	...
	let p n = ɸ(p 1n , p 2n )
	replace l 1 by "goto l r " in P
	replace l 2 by "goto l r " in P
	create "l r : p 1 ; ...; p n ; r = F(p 1 , ..., p n );
	create "l r+1 : branch equal to l b
	1 . The branch immediately after the new label r is
	used to preserve the program flow after the execution
	of divide.
	Ensuring Strictness: We notice that the trans-
	formed program contains a path in which variable
	p 1 is used without being defined: 0 → 1 → 2 →

3 → 4 → r → r+1 → 1 0. In this case we say that the program is not strict. Strictness is a very important requirement imposed by the Static Single merge_cfg(): input: Program P, Label l b l 1 , l 2 output: Program P'

  Branch Distribution hoists instructions up or down divergence paths to join them at common program pointswe can perform this merging in the middle of divergence paths. Branch Fusion[START_REF] Coutinho | Divergence analysis and optimizations[END_REF] is a generalization of Branch Distribution; however, it does not merge function calls. In other words, the optimization of Coutinho et al. bails out when faced with divergent branches that contain call instructions -this is the exact case that we handle.

	5 Related Work
	Other Divergence Aware Optimizations: this
	paper introduces a new optimization to mitigate the
	performance loss caused by divergences in GPGPU
	applications. There are a number of different opti-

mizations that serve the same purpose; however, they reduce divergences in different ways

[START_REF] Carrillo | A controlstructure splitting optimization for gpgpu[END_REF][START_REF] Coutinho | Divergence analysis and optimizations[END_REF][START_REF] Han | Reducing branch divergence in gpu programs[END_REF][START_REF] Lee | Openmp to gpgpu: a compiler framework for automatic translation and optimization[END_REF][START_REF] Zhang | Streamlining GPU applications on the fly: thread divergence elimination through runtime thread-data remapping[END_REF][START_REF] Zhang | On-the-fly elimination of dynamic irregularities for GPU computing[END_REF]

. For instance, Han et al.'s

[START_REF] Han | Reducing branch divergence in gpu programs[END_REF]

http://www.khronos.org/opencl/

http://www.openacc.org/

http://openmp.org/

http://www.capsl.udel.edu/splash/

http://www.pintool.org/

This work was partially supported by CNPq, CAPES, FAPEMIG.