Archive for the 'GPU' Category

GPU Aggregation Algorithm Scales Well with Multiple GPUs

Published on June 14, 2010 in Business Intelligence, GPU, In-Memory and Palo. 2 Comments

A few weeks ago, we had the chance to test the Palo GPU Accelerator on a HighStation 550 XLR8 with 8 Tesla C1060 GPUs provided by the French company Carri Systems. Eight is the current maximum number of GPUs that can fit on one motherboard (and there is only one type of motherboard capable of holding 8 GPUs). Our main interest was how well the GPU aggregation algorithm would scale when more than 4 GPUs are used. In the upper part of the picture below you can see the 8 GPU Boards tightly fitted next to each other.

Bild

The figure below shows the performance scaling for the query performance with a real-world report and database from a prospective Jedox customer. As can be seen, performance scaling is almost linear for up to 4 GPUs and continues to scale to a speedup factor of 5.7 for 8 GPUs.

Bild

We think that Palo GPU performance scaling has no theoretical limit but is stopped only by
(a) hardware limitations, i.e. the number of GPUs that can be used in one system
(b) the cube size: cubes with very few filled cells will not benefit much from multiple GPUs
(c) the specific queries sent to the server: queries that are “simple” in the sense that already fast cannot be further sped up
The last point is most probably responsible for the slightly decreasing slope above 4 GPUs in our test. We have broken down the above analysis to each of the four individual PALO.DATAC queries in the test report (each querying a different cube), in order to see whether different queries scale differently.

Bild

As expected, some queries and/or cubes can benefit significantly more from multiple GPUs than others. The first query (Cube 1) scales extremely well until 7 GPUs, where a speedup factor of 6.4 is achieved, but seems to end there; the query on Cube 2 scales well until 8 GPUs, wheres for Cube 3 and Cube 4, scaling essentially stops after 4 GPUs (the last value of Cube 3 might be attributed to a measuring error). Note, however, that the latter two queries are already answered very fast (< 100 ms) on 4 GPUs and hence any further speedup will not as noticeable as for the other two.

Parallel algorithms for Palo Cube Rules

Published on February 5, 2010 in Business Intelligence, GPU, In-Memory, Palo and Palo for Excel. 4 Comments

In the previous weeks several people asked me, why Jedox so far is the only BI company that invests in the GPU technology. GPUs make sense when the speed of execution matters. And speed does matter for Palo users, especially when it comes down to financial planning and simulation.

Whenever planning data or planning assumptions are changed at the base level, all aggregations have to be recalculated as quickly as possible to get new consolidated results for a new planning scenario. To deliver this speed, already back in 2005 the Palo developers decided to use an in-memory technology for Palo, which by itself delivers more speed than a disk-based or relational approach.

Choosing in-memory was a wise decision and a lucky one as well, because GPU acceleration actually is only effective in an in-memory architecture (also including the graphic memory of a GPU). GPUs are not helping much on a hard disk or inside a relational database.

Recently I had an interesting conversation with Dr. Tobias Lauer from the Institute of Computer Science at the University of Freiburg. Tobias is one of the research genius behind Palo GPU and he explained how Palo benefits from the parallel algorithms that run in today’s GPUs. This is what I understood from him:

A parallel algorithm utilizes hardware architectures with multiple processing units (processors or processor cores) by executing simultaneously (= in parallel) individual steps of a program that would otherwise be computed sequentially. Depending on the number of available processors, one can distinguish multi-core moderate parallelism (e.g., 2-16 cores) and massive parallelism (hundreds or more processors).

The latter category includes modern GPUs, each consisting of several hundred processing units. Since all the individual processors of a GPU usually execute the same code at the same time, this architecture is suitable for data-parallel (the same operation on many different data) rather than task-parallel applications (different things to be executed simultaneously).

A very simple example from the business intelligence context would be the function

turnover(P) = quantity(P) x price (P)

for a product P. Instead of storing all three figures in the OLAP database, it is sufficient (and for reasons of memory requirement and data consistency even desirable) to save only the quantity and price for a product P and to calculate the turnover dynamically (by an Cube Rule) from those.

For the calculation of the total turnover of a whole group W of products, the equation turnover(W) = quantity(W) x price (W) will lead to a wrong result if quantity(W) is the cumulative total number of all goods and price(W) is the aggregated price. Hence, the individual turnover for each product in the group W must be calculated first, before they can finally be summed up (or, using Palo terminology: we have to use an N-rule). Sequential programs need to run each of the calculations after one another, roughly like this:

1. For each product P in W do (sequentially):
a. Find the quantity and price of P
b. Multiply the two values
c. Add that product to the result
2. Return result

Our new approach is to do these individual calculations in parallel, i.e. to calculate simultaneously. Graphics processors (GPUs) are ideal architectures for this: the same operation (here: multiplication) is executed on many different data sets (here: quantities and prices of all products). A bit over-simplified, our algorithm performs the following steps:

1. Find quantities and prices for all the products P in W simultaneously.
2. Match these records so that quantity and price of the same product are placed next to each other (very quick through parallel sort)
3. Multiply all related pairs (quantity, price) simultaneously and store the results in an array.
4. Add up the array to get the overall result (very quickly by parallel reduce)
5. Return result

Unlike the above sequential algorithm, our parallel approach can perform two steps – finding data and multiplication – for all data sets almost simultaneously. The sorting and the final summation are accomplished by standard algorithms of parallel computing which are also very fast.

In initial tests we have seen very promising results, where our parallel approach has achieved significant speedups compared to the sequential algorithm currently used in Palo.