Graphics Processing Units (GPU) have significantly more applications than just rendering images. They are also used in generalpurpose computing to solve problems that can benefit from massive parallel processing. However, there are tasks that either hardly suit GPU or fit GPU only partially. The latter class is the focus of this paper. We elaborate on hybrid CPU/GPU computation and build optimisation methods that seek the equilibrium between these two computation platforms. The method is based on heuristic search for bi-objective Pareto optimal execution plans in presence of multiple concurrent queries. The underlying model mimics the commodity market where devices are producers and queries are consumers. The value of resources of computing devices is controlled by supply-and-demand laws. Our model of the optimization criteria allows finding solutions of problems not yet addressed in heterogeneous query processing. Furthermore, it also offers lower time complexity and higher accuracy than other methods.
General-Purpose computing on Graphics Processing Units (GPGPU) involves utilization of graphics processing units (GPU) in tasks traditionally handled by central processing units (CPU). GPUs offer a notable processing power for streams.
Execution of database queries is an example of a successful application of
GPGPU. The current research focuses on using the GPU as a co-processor [
An application of GPU requires transferring data from the CPU memory
to the graphical device memory. The data transfer is usually time-consuming. It
may diminish the gain of the acceleration credited to GPU. This situation can be
improved by using lightweight compression methods that can significantly reduce
the costs associated with communication [
The previous research efforts focused on the creation of query plans based
on a cost model. This approach finds plans with the best throughput. However,
it does not allow modelling all phenomena that can occur in heterogeneous
systems. Performing a query as soon as possible is not always cost effective [
In this paper, we propose a query optimization model based on the commodity market. A query plan is bi-objectively optimized to minimize: the processing time and the value of consumed resources. For the user, a small difference in execution time can be negligible. Thus, it is worth optimizing a query, so that the execution time satisfies the user while other costs are minimized. In this case, the cost may be, e.g. the responsiveness of the system, power consumption, heat production, etc. One can also consider expressing the cost in financial terms. 2
2.1
From the parallel processing’s point of view, CPU accompanied by a GPU coprocessor is a shared nothing architecture. A GPU card has its own memory or a separate area in the CPU main memory. Thus, the data has to be explicitly transferred from the CPU main memory to the GPU main memory. Similarly, the results produced by GPU have to be transferred back to the CPU main memory. This data transfer often introduces significant overhead. Thus, it is important to include the transfer cost in the total execution time of an operation. This cost is also a component of the execution time prediction.
Contemporary computer systems often include more than one GPU. Then, it is possible to combine multiple computational units in a single query plan. Such plans are called heterogeneous query processing. Each device may have a different communication cost (e.g. PCIe or shared memory) with the CPU main memory. Furthermore, devices can often communicate directly between each other. Therefore, the main problem of heterogeneous query processing is the construction of such a query plan that uses only computational units from which query performance will benefit most and yet will minimize used resources.
Bress et. al. [
Problem 2 Critical Query - since the GPU memory, the concurrent GPU kernels execution and the PCIe bus bandwidth are all limited, only the critical queries should be selected to use GPU (i.e., queries that benefit from GPU usage and are important from global perspective).
Problem 3 Optimization Impact - as concurrent heterogeneous queries will influence each other, it is important to consider this aspect in the planning process. 2.2
In this paper we address these problems by showing that they may be solved by
applying a supply-and-demand pricing model taken from a commodity market.
In such a market resource owners (processing devices) price their assets and
charge their customers (queries) for consumed resources. Other pricing models
may also be used [
In the supply-and-demand model when supply (available resources) or
demand (needed resources) changes, the prices will be changed until an equilibrium
between supply and demand is found. Typically the value of a resource is
influenced by: its strength, physical cost, service overhead, demand and preferences
[
Bi-objective optimization is a problem where optimal decisions need to be taken
in the presence of trade-offs between two conflicting objectives. It is a special
case of multiple criteria decision making. Typically there are no solutions that
meets all objectives. Thus, a definition of an optimum solution set should be
established. In this paper we use the predominant Pareto optimality [
The main aim of the new query planner is to propose a solution to the problems listed in Section 2.1, i.e., Execution Time Prediction, Critical Query and Optimization Impact. Furthermore, this planner also addresses heterogeneous GPU cards and distributed processing. In this paper we propose a method to build heterogeneous query plans based on the economics of commodity markets. It is characterized by the fact that the resource producers determine the cost of their resources and resource consumers jostle for resources. Furthermore, the resources owners provide information on the quality of their resources, i.e., the estimated processing time. 3.1
Aou1i1 (D1); Aou2i2 (D2); Aou3i3 (D3); : : : ; Aounin (Dn) Mu ;ui1 (D1); Mui1 ;ui2 (D2); Mui2 ;ui3 (D3); : : : ; Muin ;u (Dn) (1)
Fx(QShet) = X fx(Aou; D) +
Aou(D)
X Mu0;u00 (D) gx(Mu0;u00 ; D) (2) 3.2
Input: QSlog = o1o2o3 : : : on - logical query sequence, u - base unit, x 2 f t time, c - cost, b - bioptimization g - optimization type
Result: QShybrid 1 seq_list = []; 2 for u in U do 3 Qu = Su(QSlog; u ); 4 QFu = Fx(Qu) ; 5 append (u; Qu; QFu) to Seq_list; 6 end 7 QShybrid = pop minimum Qu (by QFu) sequence from Seq_list; /* e.g. Ft(Qu) */ 8 for (u, Qu, QFu) in Seq_list do 9 A, B, C = DiffSeq (QShybrid; Qu; u; x); 10 val; start; end = M axSubseq(A; B; C); 11 if val > 0 then 12 Qhybrid(start : end) = Qu(start : end) ; /* subarray subsitution */ 13 end 14 end 15 return Qbase
In this section, we introduce the algorithm that searches for a heterogeneous query plan, i.e., a plan that operates on more than two devices.
For simplicity let us assume that x = t, ft(Aou; Di) = trun(Aou; Di) and gt(Mu;u0 ; D) = tcopy(Mu;u0 ; D). Later in this article we will define functions fc; gc and fb; gb to fit the model of the commodity market and the bi-objective optimization. Let Su(QSlog; u ) return such QShet that each operation oi 2 QSlog is replaced with an algorithm from unit u algorithm pool, i.e., Aoui 2 APoi and the base device is set to u . Note that there is a specially designated computing unit u from which the processing starts. It also collects the data in the end of processing, since the GPU computing is controlled by a CPU side program.
The algorithm OptimalSeq starts by creating a query sequence for each computing unit and estimating the processing cost for each item of this sequences (lines 2-6). Next, one sequence (which minimizes Fx(Qu)) is selected as the base sequence. It will be improved in later steps (line 7). Then, the algorithm iterates over remaining query sequences in QShybrid in order to find such segments in the remaining query sequences which improve original sequence (by replacing
corresponding segment of the original sequence). This is done by calculating the improvement and copy cost arrays in DiffSeq and finding maximal sequence segment in MaxSubseq. A following variant of the proposed algorithm should also be considered. Suppose that only one query sequence segment may be inserted (i.e., choose one sequence segment from remaining k 1 sequences with the biggest), this minimizes number of involved computational units and reduces overall communication costs.
The procedure DiffSeq simply calculates element wise difference between two
query sequences fx(Aoub ; Di) fx(Aou; Di) and copy costs from/to unit. The
procedure MaxSubseq is based on Kadane’s algorithm for maximum subarray
problem [
The complexity of OptimalSeq is O(k n) where k is the number of devices (usually small) and n is the number of operations of the sequence. Su,Fx, DiffSeq and MaxSubseq have the complexity O(n). 3.3
To cope with the problems mentioned in Section 2.1, additional criteria are necessary – in this work an approach based on a simple economic model is proposed. Each consumer (client) has a query budget that can be used to pay for the resources used to process queries. Each computational unit is a service provider (producer) of services available in units algorithm pool APui . Each service provider establishes its own pricing for execution of any service from APui . Pricing of the service depends on: Procedure MaxSubseq(A, B, C) – the estimation of needed resources (the size of the data D, the performance of the task Aouii ), – pricing of needed resources (the load of device ui – the greater the load on the device, the higher cost of using the device), – the preference of the device (e.g. device may prefer larger jobs and/or tasks that give a greater acceleration on the GPU).
First, pricing for using the resources of computational unit is established. This depends on the previous load of the device: the higher demand for computational unit, the higher price for using it. This is a periodic process which calculates prices every tup seconds by calculating computational unit price Pu. Let 0 < Lcurr < 1, 0 < Lprev < 1 be current and previous computational unit load factors. Additionally, let Lth be a threshold below which prices should decrease, and Pmin be the minimal price. Then the price is calculated using the following formula4: (max(Pmin; Pu (1 + (1 PuU) ) if ( P > 0 ^ U > 0) _ ( P < 0); Pu :=
Pu
otherwise,
(3)
where Pu = Lcurrent Lthreshold and Uu = Lcurrent LP revious. This is
similar to the dynamic pricing model proposed in [
To reflect the preference of the device in price we need to define a function
returning speedup factor between base device u (defined in the previous section)
4Slightly abusing notation we will also denote the new price by Pu.
and current device: speedup(Aou; Di) = trun(Aou ; Di)=trun(Aou; Di). Then we
define a cost function as crun(Aou; Di) = speedu#pD(Ai ou;Di) Pu, where speedu#pD(Ai ou;Di)
part combines the estimation of needed resources and the preference of the
device. A computational unit with high speedup on given operation will get a
discount per data size when pricing this operation. Similarly, operations with a
lower speedup factor will be charged more per quantity. Additionally it is
observed [
It is also important to include cost of data transfer, let us define it as if u,u’ share memory ccopy(Mu;u0 ; D) := (0
#Di bandwidth(#Di;u;u0) (Pu + Pu0 )=2 otherwise where bandwidth returns estimated bytes per second between u and u0 computational units. If direct data transfer is not available between u and u0 devices, then transit device will be used (e.q. two GPU cards without direct memory access will communicate using CPU RAM).
Now let fc(Aou; Di) = crun(Aou; Di) and gc(Mu;u0 ; D) = ccopy(Mu;u0 ; D). A solution minimizing the cost may be found under the previous assumptions and using procedure OptimalSeq. 3.4
As finding Pareto optimal bi-objective query plan is NP-hard (bi-objective
shortest path problem) [
We will use a priori articulation of preference approach which is often applied
to multi-objective optimization problems. It may be realized as the scalarization
of objectives, i.e., all objective functions are combined to form a single function.
In this work we will use weighted product method, where weights express user
preference [
fb(Aou; D) = crun(Aou; D)wc trun(Aou; D)wt ;
gb(Mu;u0 ; D) = ccopy(Mu;u0 ; D)wc tcopy(Mu;u0 ; D)wt :
where wt and wc are weights which reflect how important cost and time is (the
bigger the weight the more important the feature – values of fb; gb are higher
than 1). It is worth to mention that a special case with wt = wc = 1 (i.e., without
any preferences) is equivalent to Nash arbitration method (or objective product
method) [
In order to evaluate this model we prepared a proof of concept and evaluated it using custom developed simulation environment. Simulation environment was deDevice o1 o2 o3 o4 o5 o6 GPU1 20 11 6 0.38 14 15 GPU2 5 11 6 0.33 4.66 5 CPU2 1 1 1.09 1 1.27 1.36 (a) Average speedup of operation oi on given device compared to CPU1
Option
Unit threshold Unit minimal price
CPU1 CPU2 GPU1 GPU2 0.75 0.75 0.4 0.4
5 5 70 70 (b) Pricing model configuration veloped using Python and SimPy framework. All presented experiments are derived from simulation. There where four devices defined in environment: CPU1, CPU2, GPU1, GPU2. Data transfer bandwidth between CPU* $ GPU* was measured on real system, bandwidth of GPU1 $ GPU2 was calculated using CPU1 as transit device. Following weights in bi-objective scalarization were used wt = wc = 1 (i.e., without any preferences setting). Other settings of the simulation environment are gathered in Tables 2b and 2a. Simulation environment generates new query sequences, when spawn event occurs. Spawn event is generated randomly in a fixed interval and generates randomly set of query sequences (with fixed maximum). Every query sequence consists of maximally six operations and operates on random data volume. In the simulation the processed data size has a direct (linear) influence on processing speed. Each device has got a limited number of resources; a database operation can be performed only if needed resources are available. In other cases the operation is waiting. After generating desired number of query sequences the simulation stops spawning of new tasks and waits until all generated query sequences are processed. 4.2
Figure 1a presents simulated execution time of three scheduling frameworks processing a pool of generated sequences of queries. To each generated query sequence an optimization criterion (time, cost or bi-optimization) was assigned with equal probability 1=3. Optimization criteria are only used if query scheduling framework supports it, otherwise default criteria is used. All scheduling frameworks process exactly the same pool of generated query sequences.
Compared frameworks are based on OptimalSeq algorithm but use different
objective function. Time objective planner uses only ft and gt functions as
optimization criteria; this means that it has no idea on load of each of devices. Self
Tuning Planner is based on idea presented in Breß et. al. [
As expected Time Objective Planner is the slowest one since it has no
knowledge on the current load of devices. A solution suggested in [
As our framework support different types of optimization in the Figure 1b, we present an impact of optimization type on processing performance. As it may be observed, time optimization is the most appropriate for query processing with high priority or with execution time constraint (like interactive queries or ad hoc data mining). Cost optimization is appropriate for operations with low priority or without time constraint (like batch processing or periodic jobs). Optimization of both cost and time (without preferences) leads to moderate processing speed but with better load balancing which is discussed later.
As proposed economic model is an important part of presented framework, in Figure 1 interaction between device load 1c and established device pricing 1d is illustrated. Notice how increased load influences unit pricing according to the formula 3. It is worth noting that pricing model may be tuned for specific applications (see Table 2b for this simulation settings). 4.3
In Section 2.1 we cite three challenges of Hybrid Query Processing initially
presented in Breß et.al. [
Multiobjective query optimization was considered i.a. in Stonebraker et.al. [
In our framework a user supplies an optimization objective for a query a priori (time, cost or bi-objective). Also as our model addresses the optimisation of co-processing interaction a simpler commodity market model could be used instead of a bidding model.
An extended overview on utilization of a GPU as a coprocessor in database
operations may be found in [
It is worth to mention two surveys: the first one describing economic models
in grid computing [
In this paper, we proposed a bi-objective optimization framework for
heterogeneous query plans. We also presented an algorithm for creating query sequences
in a heterogeneous environment with a single objective. This algorithm may be
used to construct query sequences similar to [
The preliminary experiments are very promising. We achieved good load balancing of the simulated devices combined with better optimization results.
In future work, an extended evaluation of the presented framework is needed,
including; examination of parameters’ influence on the model behaviour, careful
assessment against Hybrid Query challenges. Another interesting field is
extension of this model beyond CPU/GPU co-processing. Finally, the framework will
be evaluated in a prototype time-series database [