WIXLIB

can be accelerated on multicore machines [16] and on GPUs[11]. Notably, Thrust, a library of algorithms implementedin CUDA intended as a GPU-aware library similar to theC Standard Template Library, includes a MapReduceimplementation [24].In some cases, a MapReduce framework has become a replacement for a traditional SQL database, though its useremains limited. The advantage of one over the other remains a hotly debated topic, both are very general methodsthrough which data can be processed. MapReduce requiresthe programmer to write a specific query procedurally, whileSQL’s power lies in its simple declarative syntax. Consequently, MapReduce most useful for handling unstructureddata. A key difference is that the simplicity of the MapReduce paradigm makes it simple to implement in CUDA,while no such SQL implementation exists. Additionally thelimited use of MapReduce restricts any GPU implementation to a small audience, particularly given that the memoryceilings of modern GPUs inhibit their use in the huge-scaledata processing applications for which MapReduce is known.2.3Programming AbstractionAnother notable vector of research is the effort to simplifythe process of writing GPGPU applications, CUDA applications in particular. Writing optimal CUDA programs requires an understanding of the esoteric aspects of NVIDIAhardware, specifically the memory heirarchy. Research onthis problem has focused on making the heirarchy transparent to the programmer, performing critical optimizationduring compilation. One such project has programmerswrite CUDA programs that exclusively use global memory,then chooses the best variables to move to register memory, shared memory, etc. during the compilation phase [17].Other projects such as CUDA-lite and hiCUDA have theprogrammer annotate their code for the compiler, whichchooses the best memory allocation based on these notes,an approach similar to the OpenMP model [10, 25]. Yetanother project directly translates OpenMP code to CUDA,effectively making it possible to migrate parallel processorcode to the GPU with no input from the programmer [15]. Acommon thread in this area is the tradeoff between the difficulty of program development and the optimality of the finished product. Ultimately, programming directly in CUDAremains the only way to ensure a program is taking full advantage of the GPU hardware.Regardless of the specifics, there is clear interest in providing a simpler interface to GPGPU programming than thosethat currently exist. The ubiquity of SQL and its pervasiveparallelism suggest that a SQL-based GPU interface wouldbe easy for programmers to use and could significantly speedup many applications that have already been developed withdatabases. Such an interface would not be ideal for all applications, and would lack the fine-grained optimization ofthe previously discussed interfaces, but could be significantlysimpler to use.3.3.1SQLITEOverviewSQLite is a completely open source database developed bya small team supported by several major corporations [20].Its development team claims that SQLite is the most widelydeployed database in the world owing to its use in popularapplications, such as Firefox, and on mobile devices, suchas the iPhone [22]. SQLite is respected for its extreme simplicity and extensive testing. Unlike most databases whichoperate as server, accessed by separate processes and usuallyaccessed remotely, SQLite is written to be compiled directlyinto the source code of the client application. SQLite is distributed as a single C source file, making it trivial to adda database with a full SQL implementation to a C/C application.3.2ArchitectureSQLite’s architecture is relatively simple, and a brief description is necessary for understanding the CUDA implementation described in this paper. The core of the SQLiteinfrastructure contains the user interface, the SQL commandprocessor, and the virtual machine [21]. SQLite also containsextensive functionality for handling disk operations, memory allocation, testing, etc. but these areas are less relevantto this project. The user interface consists of a library ofC functions and structures to handle operations such as initializing databases, executing queries, and looking at results.The interface is simple and intuitive: it is possible to opena database and execute a query in just two function calls.Function calls that execute SQL queries use the SQL command processor. The command processor functions exactlylike a compiler: it contains a tokenizer, a parser, and a codegenerator. The parser is created with an LALR(1) parsergenerator called Lemon, very similar to YACC and Bison.The command processor outputs a program in an intermediate language similar to assembly. Essentially, the commandprocessor takes the complex syntax of a SQL query and outputs a set of discrete steps.Each operation in this intermediate program contains anopcode and up to five arguments. Each opcode refers to aspecific operation performed within the database. Opcodesperform operations such as opening a table, loading datafrom a cell into a register, performing a math operation ona register, and jumping to another opcode [23]. A simpleSELECT query works by initializing access to a databasetable, looping over each row, then cleaning up and exiting.The loop includes opcodes such as Column, which loads datafrom a column of the current row and places it in a register,ResultRow, which moves the data in a set of registers to theresult set of the query, and Next, which moves the programon to the next row.This opcode program is executed by the SQLite virtualmachine. The virtual machine manages the open databaseand table, and stores information in a set of ”registers”,which should not be confused with the register memory ofCUDA. When executing a program, the virtual machine directs control flow through a large switch statement, whichjumps to a block of code based on the current opcode.3.3UsefulnessSQLite was chosen as a component of this project for anumber of reasons. First, using elements of a well-developeddatabase removes the burden of having to implement SQLquery processing for the purposes of this project. SQLitewas attractive primarily for its simplicity, having been developed from the ground up to be as simple and compactas possible. The source code is very readable, written in aclean style and commented heavily. The serverless design ofSQLite also makes it ideal for research use. It is very easy

to modify and add code and recompile quickly to test, andits functionality is much more accessible to someone interested in comparing native SQL query execution to execution on the GPU. Additionally, the SQLite source code is inthe public domain, thus there are no licensing requirementsor restrictions on use. Finally, the widespread adoption ofSQLite makes this project relevant to the industry, demonstrating that many already-developed SQLite applicationscould improve their performance by investing in GPU hardware and changing a trivial amount of code.From an architectural standpoint, SQLite is useful for itsrigid compartmentalization. Its command processor is entirely separate from the virtual machine, which is entirelyseparate from the disk i/o code and the memory allocation code, such that any of these pieces can be swappedout for custom code. Critically, this makes it possible to reimplement the virtual machine to run the opcode programon GPU hardware.A limitation of SQLite is that its serverless design means itis not implemented to take advantage of multiple cores. Because it exists solely as a part of another program’s process,threading is controlled entirely outside SQLite, though it hasbeen written to be thread-safe. This limitation means thatthere is no simple way to compare SQLite queries executedon a single core to SQLite queries optimized for multicoremachines. This is an area for future work.4.4.1IMPLEMENTATIONScopeGiven the range of both database queries and database applications and the limitations of CUDA development, it isnecessary to define the scope of of this project. We explicitlytarget applications that run SELECT queries multiple timeson the same mid-size data set. The SELECT query qualification means that the GPU is used for read-only data. Thisenables the GPU to maximize its bandwidth for this caseand predicates storing database rows in row-column form.The ’multiple times’ qualification means that the project hasbeen designed such that SQL queries are executed on dataalready resident on the card. A major bottleneck to GPUdata processing is the cost of moving data between deviceand host memory. By moving a block of data into the GPUmemory and executing multiple queries, the cost of loadingdata is effectively amortized as we execute more and morequeries, thus the cost is mostly ignored. Finally, a ’mid-sizedata set’ is enough data to ignore the overhead of settingup and calling a CUDA kernel but less than the ceiling oftotal GPU memory. In practice, this project was designedand tested using one and five million row data sets.This project only implements support for numeric datatypes. Though string and blob types are certainly very useful elements of SQL, in practice serious data mining on unstructured data is often easier to implement with anotherparadigm. Strings also break the fixed-column width dataarrangement used for this project, and transferring character pointers from the host to device is a tedious operation.The numeric data types supported include 32 bit integers,32 bit IEEE 754 floating point values, 64 bit integers, and64 bit IEEE 754 double precision values. Relaxing these restrictions is an area for future work.4.2Data SetAs previously described, this project assumes data staysresident on the card across multiple queries and thus neglects the up-front cost of moving data to the GPU. Basedon the read-only nature of the SQL queries in this projectand the characteristics of the CUDA programming model,data is stored on the GPU in row-column form. SQLitestores its data in a B-Tree, thus an explicit translation stepis required. For convenience, this process is performed witha SELECT query in SQLite to retrieve a subset of data fromthe currently open database.The Tesla C1060 GPU used for development has 4 gigabytes of global memory, thus setting the upper limit ofdata set size without moving data on and off the card during query execution. Note that in addition to the data setloaded on the GPU, there must be another memory blockallocated to store the result set. Both of these blocks are allocated during the initialization of the program. In additionto allocation, meta data such as the size of the block, thenumber of rows in the block, the stride of the block, and thesize of each column must be explicitly managed.4.3Memory SpacesThis project attempts to utilize the memory heirarchy ofthe CUDA programming model to its full extent, employing register, shared, constant, local, and global memory [19].Register memory holds thread-specific memory such as offsets in the data and results blocks. Shared memory, memory shared among all threads in the thread block, is usedto coordinate threads during the reduction phase of the kernel execution, in which each thread with a result row mustemit that to a unique location in the result data set. Constant memory is particularly useful for this project sinceit is used to store the opcode program executed by everythread. It is also used to store data set meta information,including column types and widths. Since the program andthis data set information is accessed very frequently acrossall threads, constant memory significantly reduces the overhead that would be incurred if this information was storedin global memory.Global memory is necessarily used to store the data seton which the query is being performed. Global memory hassignificantly higher latency than register or constant memory, thus no information other than the entire data set isstored in global memory, with one esoteric exception. Localmemory is an abstraction in the CUDA programming modelthat means memory within the scope of a single thread thatis stored in the global memory space. Each CUDA threadblock is limited to 16 kilobytes of register memory: when thislimit broken the compiler automatically places variables inlocal memory. Local memory is also used for arrays thatare accessed by variables not known at compile time. Thisis a significant limitation since the SQLite virtual machineregisters are stored in an array. This limitation is discussedin further detail below.Note that texture memory is not used for data set access.Texture memory acts as a one to three dimensional cachefor accessing global memory and can significantly acceleratecertain applications[19]. Experimentation determined thatusing texture memory had no effect on query performance.There are several reasons for this. First, the global data setis accessed relatively infrequently, data is loaded into SQLiteregisters before it is manipulated. Next, texture memory

is optimized for two dimensional caching, while the dataset is accessed as one dimensional data in a single block ofmemory. Finally, the row-column data format enables mostglobal memory accesses to be coalesced, reducing the needfor caching.4.4Parsed QueriesAs discussed above, SQLite parses a SQL query into anopcode program that resembles assembly code. This projectcalls the SQLite command processor and extracts the results, removing data superfluous to the subset of SQL queriesimplemented in this project. A processing phase is also usedto ready the opcode program for transfer to the GPU, including dereferencing pointers and storing the target directlyin the opcode program. A sample program is printed below,output by the command processor for query 1 in AppendixA.0:Trace0001:Integer60 102:Integer0203:Goto017 04:OpenRead0205:Rewind015 06:Column0137:Le114 38:Column0239:Ge214 310: Column00511: Column01612: Column02713: ResultRow53014: Next06015: Close00016: Halt00017: Transaction00018: VerifyCookie 01019: TableLock02020: Goto040A virtual machine execution of this opcode procedure iterates sequentially over the entire table and emits result rows.Note that not all of the opcodes are relevant to this project’sstorage of a single table in GPU memory, and are thus notimplemented. The key to this kind of procedure is thatopcodes manipulate the program counter and jump to different locations, thus opcodes are not always executed inorder. The Next opcode, for example, advances from onerow to the next and jumps to the value of the second argument. An examination of the procedure thus reveals theblock of opcodes 6 through 14 are executed for each row ofthe table. The procedure is thus inherently parallelizableby assigning each row to a CUDA thread and executing thelooped procedure until the Next opcode.Nearly all opcodes manipulate the array of SQLite registers in some way. The registers are generic memory cellsthat can store any kind of data and are indexed in an array.The Column opcode is responsible for loading data from acolumn in the current row into a certain register.Note the differences between a program of this kind anda procedure of primitives, as implemented in previous research. Primitives are individual CUDA kernels executedserially, while the entire opcode procedure is executed entirely within a kernel. As divergence is created based onthe data content of each row, the kernels execute differentopcodes. This type of divergence does not occur with aquery-plan of primitives.4.5Virtual Machine InfrastructureThe crux of this project is the reimplementation of theSQLite virtual machine with CUDA. The virtual machineis implemented as a CUDA kernel that executes the opcode procedure. The project has implemented around 40opcodes thus far which cover the comparison opcodes, suchas Ge (greater than or equal), the mathematical opcodes,such as Add, the logical opcodes, such as Or, the bitwiseopcodes, such as BitAnd, and several other critical opcodessuch as ResultRow. The opcodes are stored in two switchstatements.The first switch statement of the virtual machine allowsdivergent opcode execution, while the second requires concurrent opcode execution. In other words, the first switchstatement allows different threads to execute different opcodes concurrently, and the second does not. When theNext opcode is encountered, signifying the end of the datadependent parallelism, the virtual machine jumps from thedivergent block to the concurrent block. The concurrentblock is used for the aggregation functions, where coordination across all threads is essential.A major piece of the CUDA kernel is the reduction whenthe ResultRow opcode is called by multiple threads to emitrows of results. Since not every thread emits a row, a reduction operation must be performed to ensure that the resultblock is a contiguous set of data. This reduction involvesinter-thread and inter-threadblock communication, as eachthread that needs to emit a row must be assigned a uniquearea of the result set data block. Although the result set iscontiguous, no order of results is guaranteed. This saves themajor overhead of completely synchronizing when threadsand threadblocks complete execution.The reduction is implemented using the CUDA atomicoperation atomicAdd(), called on two tiers. First, eachthread with a result row calls atomicAdd() on a variablein shared memory, thus receiving an assignment within thethread block. The last thread in the block then calls thisfunction on a separate global variable which determine’s thethread block’s position in the memory space, which eachthread then uses to determine its exact target row based onthe previous assignment within the thread block. Experimentation has found that this method of reduction is fasterthan others for this particular type of assigment, particularlywith sparse result sets.This project also supports SQL aggregation functions (i.e.COUNT, SUM, MIN, MAX, and AVG), though only for integer values. Significant effort has been made to adhereto the SQLite-parsed query plan without multiple kernellaunches. Since inter-threadblock coordination, such as thatused for aggregation functions, is difficult without using akernel launch as a global barrier, atomic functio

memory size and the host to GPU device memory transfer time. Though future graphics cards will almost certainly have greater memory, current NVIDIA cards have a maxi-mum of 4 gigabytes, a fraction of the size of many databases. Transferring memory blocks between the CPU and the GPU remains costly. Consequently, staging data rows to the GPU