We propose a generalized method for adapting and optimizing algorithms for eficient execution on modern graphics processing units (GPU). The method consists of several steps. First, build a control flow graph (CFG) of the algorithm. Next, transform the CFG into a tree of loops and merge non-parallelizable loops into parallelizable ones. Finally, map the resulting loops tree to the tree of GPU computational units, unrolling the algorithm's loops as necessary for the match. The mapping should be performed bottom-up, from the lowest GPU architecture levels to the highest ones, to minimize of-chip memory access and maximize register file usage. The method provides programmer with a convenient and robust mental framework and strategy for GPU code optimization. We demonstrate the method by adapting to a GPU the DPLL backtracking search algorithm for solving the Boolean satisfiability problem (SAT). The resulting GPU version of DPLL outperforms the CPU version in raw tree search performance sixfold for regular Boolean satisfiability problems and twofold for irregular ones.
Modern graphics processing units (GPU) execute computer vision and ”big data” processing
tasks eficiently. Those tasks belong to the class of ”embarrassingly parallel” problems, which
perfectly matches the ”single instruction, multiple data” (SIMD) [
The paper structure consists of the following sections: Section 1 consists of a survey of prior research regarding GPU code optimization;
Section 4 provides a detailed example of applying the method to adapt a complex algorithm to GPU platform, assessing the resulting performance; Section 5 concludes the paper by briefly discussing the method’s performance and prospects.
Since early 2000s, the concept of general-purpose GPU programming made a leap from a
curiosity to the ”magic sauce” behind the ongoing industrial AI revolution. Many excellent
GPU programming platforms were released in this period, ranging from vendor-specific (i.e.
CUDA [
While trying to abstract the hardware details, these platforms either force the programmer
to use rigid library primitives (e.g. matrix multiplication) or add too much abstraction trying
to encompass too many possible hardware architectures [
To our experience, the literature and didactic materials on the topic of GPU programming are lacking in the description of the big picture, focusing on technical details instead. In the present work we intend to bridge this gap by providing the programmer with a robust mental model of the optimization process.
An algorithm, by definition, is a sequence of well-defined actions required to solve a particular problem. Some algorithms may involve a very high number of actions and thus must be executed by a computer. However, (almost) all algorithms are created by humans and expressed in humanreadable forms, such as mathematical formulae or programming languages. To understand and manipulate complex algorithms, humans break those expressions down into smaller subroutines and compress repeating steps using loops [11]. Every algorithm written within the paradigm of structured programming [12], as well as any mathematical formula, can be expressed as a tree of subroutines or subformulae (Figure 1). Also, every loop in an algorithm can be unrolled into a fixed sequence 1 of repeating operations [14]. Thus, all finite algorithms or formulae can be unfolded into a human-comprehensible tree of operations.
Modern GPUs are designed to execute algorithms that primarily consist of a very high number of simple independent operations (e.g. floating-point multiplications and additions). GPU architecture can be split down into several organizational levels (OL), containing several computational units of the same type, such as ALUs or multiprocessors. Thus, every modern GPU can be represented as a tree of computational units 1.
In the GPU code, OLs existence is evident in the form of explicit and implicit synchronization primitives, warp shufle instructions, atomic memory access instructions, thread identifiers and compiler intrinsics.
CPUs, GPUs and FPGAs represent diferent strategies of increasing performance of code execution:
1Of course, there exist algorithms with an unknown number of operations and programs that can never stop[13]. For simplicity, we only talk about algorithms consisting of a limited number of operations in this paper. CPU tries to be smart about executing programs, with long instruction pipelines and branch predictors powering the superscalar paradigm. In a sense, CPUs try to do depth-first visiting of the computation tree; GPU instead relies on the programmer or compiler exposing the parallelism of the executed algorithm. GPU’s strategy can be loosely matched to breadth-first visiting of the computation tree; FPGA becomes the algorithm, reconfiguring the hardware to match the computation tree.
Superficially, FPGA strategy of reconfiguration seems more promising in terms of performance. But there are reasons why GPUs are much more popular at the moment. One downside of FPGAs is those come at an increased price due to redundant interconnect fabric and physical limitations. Also, GPUs are mass-consumer devices, further pushing down their cost. Another point is that there are many more software engineers than there are hardware engineers. Overall, matching software to hardware makes for a better strategy than the other way around.
A GPU consists of several multiprocessors of SIMD architecture [
Getting good performance from a GPU for a given algorithm is a matter of assigning the algorithm tree to the tree of the GPU’s computational blocks in the most eficient way possible. The proposed method consists of the following steps (Figure 2):
Map the tree of loops to the tree of GPU computational units, according to the limitations of the GPU hardware.
basic blocks (BB) connected by directed edges of control lfow. Each BB represents a sequence of instructions with a single input and a single output point. CFG starts with the entry block and ends with the exit block. Thus, CFG represents all possible paths of execution of the associated program [15]. The CFG is a subtype of a flowchart and thus can be built manually. As an alternative the CFG can be built by an automated code analysis tool.
At this step, the programmer (or an automated tool) should be able to map the algorithm tree to the hardware tree. The loop unroll transformation [15] could be applied to split the nodes of the algorithm tree as necessary. After the initial mapping is done, the primary optimization strategy is to position the loop nodes and their variables as deep into the hardware tree as possible. The idea is that the lower the level of a computational unit, the closer it is to its associated memory store and the faster the computation. However, lower-level computational units typically have more limitations, such as the SIMD branching problem or gather-scatter limitations. Also, the amount of storage associated with lower computational units become smaller.
Mapping a loop to a hardware level means assigning each iteration of the loop in a way that avoids waiting for results of computation performed by the other units of the same level. For example, mapping the loop of multiplication of elements of the vector V to a scalar to the warp lanes level means that lane of a warp will execute = , storing the result into the variable local to the lane. Both and could be stored either in the registry file or in the onboard memory, but the operation stays local to the lane since no lane will have to wait for results from others.
One good example is mapping operations of a convolutional neural network (CNN) to a GPU. For a simple CNN, it is even possible to match every neuron to a SIMD lane one-to-one naively. That makes sense since CNNs’ deal with reducing visual images into a small number of logical symbols, basically reversing the purpose that GPUs were initially designed for.
To demonstrate our method in action, we adapt the DPLL algorithm to the GPU platform. DPLL is a widely known backtracking search algorithm for solving the Boolean formula satisfiability problem [18]. The algorithm features multiple nested loops, complex control flow and intensive memory access. To this moment, authors are not aware of any implementation of DPLL that runs entirely on a GPU.
The DPLL algorithm is the most popular algorithm for deciding the satisfiability of a Boolean problem expressed in the conjunctive normal form (CNF). Since the time of its discovery in 1961 [18], DPLL was enhanced in every aspect, yet the core idea remained the same: • guess a variable and assign a value to it; • simplify the problem according to the guess • repeat the above steps until either the solution is found or a contradiction is encountered, in which case • backtrack and try a diferent value for the guessed variable
Efectively, DPLL is a tree walk algorithm (Figure 3). To avoid complicating the example we only discuss the basic DPLL here.
A simplified CFG for DPLL algorithm is shown at Figure 4. 99% of computation happens inside the Boolean Constraint Propagation (BCP) procedure, which is thoroughly optimized in modern SAT solvers [19]. The idea of BCP is to infer as much as possible from a single guessed variable. For every variable guessed, BCP looks into each clause that contains the variable’s literals that could render the formula unsatisfiable. If the clause contains only a single free literal after the assignment, that literal’s variable is added to the propagation queue. If BCP results in an assignment conflict, the solver invokes the backtracking procedure. Otherwise, DPLL proceeds to guess variables until every clause in the formula is satisfied.
DPLL CFG can be viewed as a hierarchy of loops with a (generally) unpredictable number of iterations: 1. the top-level loop 1 of guessing a variable value, i.e. tree walk; 2. the BCP loop 2 for simplifying the formula; 3. checking the clauses of a variable - loop 3; 4. checking the literals of a clause for conflicts or logic inference opportunities - loop 4. Only 1 iterations can be performed in parallel since it is trivial to break the search tree into any desired number of sub-trees[20]. 2 iterations are interdependent because of every iteration changing the state of the formula’s variables. Finally, 3 and 4 iterations can be parallelized. The resulting tree contains just a single branch in each level, making it look like a hierarchy (Figure 5).
Loops’ iteration counts are highly dependent on the nature of the underlying problem expressed by the CNF. Our estimation of the average iteration count is based on typical parameters of problems used in the yearly SAT race competition [21].
For our analysis, the most important aspects of the architecture are the warp size and the maximum number of in-flight warps. Let us consider diferent variants of assigning the algorithm loops to a GPU.
Take 1 We start by trying to fit as many loop levels to as low a level of the GPU as possible to utilize the fast on-chip memory. Here, we are naively putting all the loops 1.. 4 at the warp lane level. The result is too much state data kept by each thread, which does not fit into the on-chip memory and registry file.
Take 2 To decrease the memory usage, we try to move 1.. 3 a step up from the lane level to the warp level. The move helps with the memory problem because all the common parts (i.e. CNF clauses, Boolean values states) are now shared by a single warp, leaving only literals-check specific data to the lane level. However, there are often not enough literals to fill a single warp, which results in many lanes idling.
Take 3 We can do better by combining 3 with 4 and assigning the result to the lane level, while keeping 1 and 2 at the warp level. Still, the number of 4 iterations multiplied by 3 iterations is not always enough to fill more than a single warp. Unfortunately, our model shows that 2 cannot be parallelized, so we cannot merge it with 3.. 4. Also, the 1 can exhaust its assigned iterations pretty fast, leaving the whole multiprocessor idle. Take 4 To solve the problem of idle multiprocessors, we add a specialized 0 loop of workstealing [22], so threads of a warp can now dynamically ask each other for search tree branches that still must be checked. The same kind of exchange happens between warps. Also, to avoid lanes idling because SIMD ALUs are out of work, we apply the nested loops merge transform [23] to merge 2 and 3. However, the merge requires us to parallelize 1, getting us back to the ”Take 1” variant with added work stealing (Figure 6). To solve the registry pressure problem, we store common CNF data at the GPU level.
We implemented2 the ”Take 4” version of DPLL described above for NVIDIA GPUs in CUDA C language. To estimate the eficiency of the adaptation method, we also built a CPU version of the same algorithm. Table 1 contrasts the Boolean constraints propagation speed of the GPU-adapted DPLL variant running on a GPU to the performance of the same code running on a CPU. The performance is measured in millions of literal checks per second. • the classic Pigeonhole problem [24], • a synthetic benchmark with a regular structure [24].
As Table 1 shows, the adaptation procedure enabled eficient execution of the DPLL algorithm on a GPU. However, GPU performance is very dependent on the structure of the underlying problem. The CPU implementation of DPLL is much more robust to changes in the problem structure. Our earlier observation explains this efect with the fact that CPUs are designed to be much more adaptable than GPUs (see Section 2).
We proposed a method for adapting the algorithm to GPU architecture and demonstrated it by adapting a complex search algorithm (DPLL) to GPU. The method is based on the mental model of matching the computation tree to the hardware tree. The model allows the programmer to convert an algorithm to GPU hardware while avoiding iterations of trial and error and guiding architectural choices towards optimal performance. The method is not bound to any particular programming language, but instead based on common notions of loops and structured programming, providing a convenient mental framework for GPU code optimization. One possible direction for future research is creating extensions for existing profilers and IDEs to provide the programmer with hints about the estimated performance of the GPU code. Accelerator Programming, in: 2015 International Conference on Parallel Architecture and Compilation (PACT), IEEE, San Francisco, CA, 2015, pp. 138–149. URL: https://ieeexplore. ieee.org/document/7429301/. doi:10.1109/PACT.2015.17. [7] S. Verdoolaege, J. Carlos Juega, A. Cohen, J. Ignacio Gómez, C. Tenllado, F. Catthoor, Polyhedral parallel code generation for CUDA, ACM Transactions on Architecture and Code Optimization 9 (2013) 1–23. URL: https://dl.acm.org/doi/10.1145/2400682.2400713. doi:10.1145/2400682.2400713. [8] J.-Y. Liou, X. Wang, S. Forrest, C.-J. Wu, GEVO: GPU Code Optimization Using Evolutionary Computation, ACM Transactions on Architecture and Code Optimization 17 (2020) 1–28.
URL: https://dl.acm.org/doi/10.1145/3418055. doi:10.1145/3418055. [9] T. Chen, T. Moreau, Z. Jiang, L. Zheng, E. Yan, H. Shen, M. Cowan, L. Wang, Y. Hu, L. Ceze, C. Guestrin, A. Krishnamurthy, TVM: An Automated End-to-End Optimizing Compiler for Deep Learning, in: 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), USENIX Association, Carlsbad, CA, 2018, pp. 578–594. URL: https://www.usenix.org/conference/osdi18/presentation/chen. [10] N. A. Kataev, S. A. Chernykh, Automation of program parallelization in SAPFOR, in: Scientific Service and Internet: Proceedings of the 22nd All-Russian Scientific Conference (September 21-25, 2020, online), 2020, pp. 362–376. URL: https://keldysh.ru/abrau/2020/ theses/24.pdf. doi:10.20948/abrau- 2020- 24. [11] H. Abelson, G. J. Sussman, Structure and interpretation of computer programs, The MIT
Press, 1996. [12] C. Böhm, G. Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM 9 (1966) 366–371. URL: https://dl.acm.org/ doi/10.1145/355592.365646. doi:10.1145/355592.365646. [13] P. Bernays, Alonzo Church. An unsolvable problem of elementary number theory. American journal of mathematics, vol. 58 (1936), pp. 345–363., Journal of Symbolic Logic 1 (1936) 73–74. URL: https://www.cambridge.org/core/product/identifier/S0022481200038998/type/ journal_article. doi:10.2307/2268571. [14] A. V. Aho, J. D. Ullman, Principles of compiler design, Addison-Wesley series in computer science and information processing, world student series ed ed., Addison-Wesley, Reading, Mass., 1977. [15] F. E. Allen, Control flow analysis, ACM SIGPLAN Notices 5 (1970) 1–19. URL: https: //dl.acm.org/doi/10.1145/390013.808479. doi:10.1145/390013.808479. [16] C. Lattner, V. Adve, LLVM: A compilation framework for lifelong program analysis & transformation, in: International Symposium on Code Generation and Optimization, 2004. CGO 2004., IEEE, San Jose, CA, USA, 2004, pp. 75–86. URL: http://ieeexplore.ieee.org/ document/1281665/. doi:10.1109/CGO.2004.1281665. [17] C. Lengauer, Loop parallelization in the polytope model, in: G. Goos, J. Hartmanis, E. Best (Eds.), CONCUR’93, volume 715, Springer Berlin Heidelberg, Berlin, Heidelberg, 1993, pp. 398–416. URL: http://link.springer.com/10.1007/3-540-57208-2_28. doi:10.1007/ 3- 540- 57208- 2_28, series Title: Lecture Notes in Computer Science. [18] M. Davis, H. Putnam, A Computing Procedure for Quantification Theory, Journal of the ACM 7 (1960) 201–215. URL: https://dl.acm.org/doi/10.1145/321033.321034. doi:10.1145/ 321033.321034. [19] N. Eén, N. Sörensson, An Extensible SAT-solver, in: G. Goos, J. Hartmanis, J. van Leeuwen, E. Giunchiglia, A. Tacchella (Eds.), Theory and Applications of Satisfiability Testing, volume 2919, Springer Berlin Heidelberg, Berlin, Heidelberg, 2004, pp. 502–518. URL: http:// link.springer.com/10.1007/978-3-540-24605-3_37. doi:10.1007/978- 3- 540- 24605- 3_37, series Title: Lecture Notes in Computer Science. [20] O. S. Zaikin, S. E. Kochemazov, On black-box optimization in divide-and-conquer SAT solving, Optimization Methods and Software (2019) 1–25. URL: https://www.tandfonline. com/doi/full/10.1080/10556788.2019.1685993. doi:10.1080/10556788.2019.1685993. [21] T. Balyo, M. Heule, M. Jarvisalo, SAT Competition 2016: Recent Developments, Proceedings of the AAAI Conference on Artificial Intelligence 31 (2017). URL: https://ojs.aaai.org/index. php/AAAI/article/view/10641. [22] R. D. Blumofe, C. E. Leiserson, Scheduling multithreaded computations by work stealing,
Journal of the ACM (JACM) 46 (1999) 720–748. Publisher: ACM New York, NY, USA. [23] V. Bulavintsev, Flattening of data-dependent nested loops for compile-time optimization of gpu programs, International Journal of Open Information Technologies 7 (2019) 7–13. [24] H. H. Hoos, T. Stützle, SATLIB: An online resource for research on SAT, Sat 2000 (2000) 283–292.