The emerging architectures for Processing-in-Memory (PIM) present new challenges to database systems: one of them is how to schedule intra-query execution with the x86 processor to be executed inside the memory. In this paper, we show that ine cient scheduling for PIM degrades performance and increases energy consumption, but the proper PIM operators can reach signi cant improvement in more than one order of magnitude. Therefore, we bring out our vision of a PIM-aware scheduler for intra-query processing.
The new Processing-in-Memory or Processor-in-Memory (PIM) architectures have emerged as a solution to tackle the problem of data movement between memory and processor, although research in database systems is still premature to carry them out. An open issue is how to coordinate intra-query execution between x86 and underlying memory processor to exploit the potential gain from each device.
The choice of the target architecture for processing
impacts directly on query execution because mis-scheduling of
database operators can degrade query performance and
increase energy consumption. For example, operators with
high data reuse bene t from caching mechanism, and thus
the x86 processing becomes appealing. On the other hand,
operators with data streaming behavior are more suitable
for PIM [
Furthermore, current query processing scheduling on
emerging hardware have focused on multi-core architectures to
reduce resource requirements [
Copyright (C) 2018 for this paper by its authors. Copying permitted for
private and academic purposes.
scheduling solutions deal with idiosyncrasies of the
multicore and many-core architectures to run compute-intensive
applications. But, PIM architectures, such as Hybrid
Memory Cube (HMC) [
In this thesis, we focus on investigating how to interleave intra-query execution between the x86 and processing-inmemory. As far as we know, this is the rst e ort in that direction. Existing solutions usually direct data-intensive operators for PIM, however, they neglect the potential of x86 processing using caches for workloads with high temporal and spatial data locality. Thus, our vision is that a database system requires a PIM-aware scheduler for intraquery processing. During a Query Execution Plan (QEP) the database scheduler shall be capable of dispatching operators to suitable devices: PIM and x86. In addition, the database system needs e cient implementations of operators for PIM to bene t from the high bandwidth and the parallelism of the underlying hardware. 2. IMPACT OF DATABASE OPERATORS
Initially, we investigate the set of database operators on
analytic workloads, like TPC-H, because they generate
massive data movement throughout the memory hierarchy [
project select join others 1Q 2Q 3Q 4Q 5Q 6Q 7Q 8Q 9Q 01Q 11Q 12Q 13Q 14Q 15Q 16Q 17Q 18Q 19Q 20Q 21Q 22Q PHC
TPC-H Queries llTA 3. DATABASE OPERATORS INSIDE HMC
In this section, we devise e cient implementations of such
operators inside the HMC evaluating the execution time and
energy consumption. We used the SiNUCA cycle-accurate
in-house simulator [
Surprisingly, TPC-H spends around 56% of the execution time and memory footprint with projections. In a further analysis, we investigate the TPC-H Query 031 to scrutinize the reasons for our ndings. Figure 2 presents a partial execution of the TPC-H Query 03 in a top-down view and shows the interaction among select-project-join operators. The operators select and join generate lters from input columns, such as an array of matching row-ids and bitmaps, and the project operator uses these lters to project other columns in the QEP. Therefore, the impressive impact of projections on TPC-H with MonetDB is because they take the burden to materialize intermediate and nal results of other operators. As shown in the diagram of Figure 2, MonetDB performs projections through two primitives: algebra.projection and algebra.projectionpath. The rst projects a column using as input a set of ltered row-ids (or bitmap) generated by either a select or join. The latter receives as input two sets of ltered row-ids (or bitmaps) from the select and join operators, and combining them to project a column.
We avail the projection operator in the HMC [
Both primitives traverse bitmap vector(s) to lter a projection column. Inside the HMC, HIPE-Projection performs one load of 256-bytes of the input bitmap(s) and, in case of 1We chose Query 03 as it gathers the operators that we are interested in: project, select, join and group-by/aggregation.
bitmap_sel[i] H1, $1 column[i] (pH1) result[j] (pH1) j++ (pH1) algebra.projection (with predication) bitmap_join[i] bitmap_sel[i] H1, H2 H3, $1 column[i] (pH3) result[j] (pH3) j++ (pH3) algebra.projectionpath (with predication)
CUSTOMER c_custkey c_mktsegment 1 BUILDING 2 AUTOMOBILE 3 AUTOMOBILE 4 MACHINERY 5 HOUSEHOLD 6 AUTOMOBILE 7 AUTOMOBILE 8 BUILDING 9 FURNITURE 10 HOUSEHOLD
SELECT c_mktsegment
= “BUILDING”
bat[oid] 70 PROJECTION c_custkey
SELECT o_orderdate
< 1995-03-15 1 45 bat[oid] 7 PROJECTION
o_custkey PROJECTIONPATH(bat[oid], bat[oid], o_orderkey) 310 5741 23541 6 7 98 10 SELECT l_shipdate
> 1995-03-15 1 2 bat[oid] 796 PROJECTION l_orderkey 0.1 0 4 58 bat[int] 9 1
JOIN o_orderkey = l_orderkey 2 4 58 589
1 12 bat[oid] 12 bat[oid] 2 5 bat[int] 8 matched entries, it executes up to 32 parallel loads of 256bytes of the projection column and stores the values into the result vector. Those HIPE-load and HIPE-store instructions are on-chip memory operations, i.e., the load gets data from DRAM dies to HIPE registers within the HMC, while the store does the inverse. Therefore, the HIPE-Projection bene ts from the low on-chip memory latency and it uses the maximum degree of parallelism of the HMC vaults.
Figure 4 shows that HIPE-Projection reduced the execution time by more than one order of magnitude with the
.061 .034 .024 1x 2x 4x 8x 16x 32x
Unroll Depth loop unrolling technique of 32x against the best case of the x86 processor with the unroll depth of 8x2. The energy consumption of the total DRAM accesses normalized by the x86 execution with unroll depth of 1x is present on gure 4. We observe that the HIPE-Projection reduces the energy consumption around 55% and 20% on average for both projection primitives, respectively. Those results are due to the streaming behavior of projections that causes low data reuse and less amount of o -chip data transfers during the copy of data (materialization). Hence, the results endorse the feasibility of the projection operator for PIM.
Considering that select scan is the second most timeconsuming operator (see Figure 1) responsible for almost 21% of the TPC-H execution time. Traditionally it moves data around the memory hierarchy up to the processor to validate lter conditions on database columns. Similar to the projection operator, we avail the select inside HMC with the implementation of the HIPE-Selection, as depicted in Figure 5. HIPE-Selection traverses a database column testing each value against a constant, which causes compulsory loads of 32x 256-bytes of the select column and, in case of matched entries, it executes parallel stores in the result bitmap vector. These memory accesses are on-chip operations. Therefore, HIPE-Selection reaches the maximum degree of parallelism of the HMC and also exploits the low on-chip memory latency. 2The 8x is the deepest unroll generally implemented by compilers due to the reduced number of general purpose registers.
column[i] H1, H2 H3, $1 result[j] (pH3) j++ (pH3) algebra.select (with predication)
100% 90% 80% ion x8 70% tp 68 60% mx su to 50% onC ized 40% y l rnegE ronam2300%% 10% 0% algebra.select (column[], filter) for (int i, j = 0; i < tableSize; i++) if (column[i] < filter) { result[j] = column[i]; j++; } 16 9
1 14 .13 12 )s10 m i(e 8 m T itconeu 64 x E 2 0
We run HIPE-Selection in the agged selection of Figure 2 for performance and energy consumption analysis. Figure 6a shows that HIPE-Selection unrolled 32x reduces the execution time by 76x compared to the best x86 scenario with the unroll depth of 8x. Figure 6b brings the total DRAM energy consumption normalized by the x86 execution with unroll depth of 8x. HIPE-Selection reduces the energy consumption by around 98% of any unroll version. In HIPE-Selection most data transfers take place on-chip, but the selection in the x86 causes o -chip data transfers for the entire column and the result vector (i.e., data movement throughout the cache memory hierarchy). These results corroborate for the feasibility of the select operator for PIM.
The join operator has been studied for years, with
different algorithms to exploit the potential of the x86
processor. Most of the algorithms belong to the classes of hash
join and sort-merge join. However, such algorithms generate
random memory accesses that inhibit the potential of HMC
(high bandwidth and parallelism over contiguous data), and
indeed the HMC is better exploited for streaming
applications [
NLJ streams the join columns, it enforces data reuse when repeatedly traversing the inner loop. Furthermore, the join columns t into the cache hierarchy and thus only the rst compulsory misses occur when loading the columns in the cache. Thereafter, there is no LLC cache misses until the end of the execution while the inner column is reused N times. By contrast, in the HIPE-Join every inner loop iteration cause compulsory LOAD and STORE (in case of matched join values) instructions. The loop unrolling technique reduces such impact due to the high internal bandwidth of the HMC, as depicted in Figure 7. However, it is not enough to improve performance nor energy consumption when using PIM.
140 120 100 ) (sm80 e iTm60 n itceuo40 .693 xE20 1 0 4. PIM-AWARE SCHEDULER
Database system environments with PIM demand careful decision by the QEP to interleave intra-query execution with the x86 processor, but the choice of the best target architecture depends on intra-operator data reuse, which uctuates according to the operator behavior, the cache settings, and data characteristics. This motivates the design of a PIMaware scheduler: our future work on dynamic database operator scheduling for emerging PIM architectures.
The scheduler is a critical performance component of a DBMS: it orchestrates the execution of physical primitives of a QEP. Thus, we envision two scheduling strategies for a PIM-aware scheduler: static scheduling and dynamic scheduling. These strategies receive as input the optimal plan generated by the query optimizer, coordinating intra-query execution between PIM and the x86.
Static scheduling: before query execution, using a classi cation model based on operator pro le to decide in which architecture to process each operator.
Dynamic scheduling: during query execution, beginning with the static scheduling and modifying on-the- y the operator implementation as the scheduler detects abnormal data reuse.
CONCLUSIONS AND FUTURE WORK Although PIM architectures feature as high performance memory by delivering unprecedented bandwidth, data access parallelism and computational power, not every application bene ts from PIM capabilities. Thus, database systems must accurately interleave intra-query processing between PIM and x86. In this direction, we introduce our vision of a PIM-aware scheduler for intra-query processing.
We rst investigate the most impacting database operators in analytic workloads and develop adjusted PIM operators: HIPE-[Projection, Selection and Join]. The rst two proved e cient for the execution time and energy consumption. However, the latter presented another perspective that is the intra-operator data reuse is a heavy factor for scheduling decisions. Our ongoing work is the static scheduling strategy based on operator pro les. Our future work is the dynamic scheduling strategy to reschedule operators on-the- y.