読者です 読者をやめる 読者になる 読者になる

PGconf.SV 2016 and PL/CUDA

I've participated PGconf Silicon Valley 2016 held at the South San Francisco Conference Center.

I could have a presentation here. Its title is PL/CUDA - Fusion of HPC Grade Power with In-Database Analytics.
Its slides are below:
https://www.slideshare.net/kaigai/pgconfsv2016-plcuda/

What is PL/CUDA?

PL is an abbreviation of Procedural Language. In PostgreSQL, we have some PL options like PL/pyhton, PL/R and so on.
This functionality allows to implement SQL functions with different program languages individually.
For example, this SQL function definition is described with "SQL" language.

CREATE OR REPLACE FUNCTION sample(int, int)
RETURNS int
$$
  SELECT $1 + $2;
$$ LANGUAGE 'sql'

We can describe the code block between the $$ marker in SQL-language.

It means we can use other programming language for SQL function definition if another LANGUAGE is given.
So, it is never strange to have CUDA language here.

PL/CUDA is a procedural language which supports CUDA code block for user defined SQL function.
It allows to embed a heavy computing portion within a SQL query, and invokes GPU kernels transparently.

As literal, DBMS is database management system. It implies heavy computing is not a primary workload for DBMS, and it is almost correct. So, people who want to run heavy analytic algorithm usually exports the data from the database for more computing performance. However, here is two downsides. The first is network traffic to export the data set. If DBMS would have enough computing capability, all we have to export is results of the analytic algorithm. The other is loss of SQL flexibility on the post-process of the analytic algorithm. If we could finish the algorithm core in database, it is quite easy to join the result with other tables, to make a summary using GROUP BY or window functions.

PL/CUDA is a solution to solve these problems. The code block in the function declaration shall be put into GPU kernel, then PG-Strom's infrastructure build the GPU kernel on the fly and execute on GPU devices with thousands threads. Its function arguments and results are automatically move to/from GPU devices.

Actually, PL/CUDA changes the concept of PG-Strom a bit. It originally intended to accelerate SQL by GPU transparently, thus existing SQL shall be accelerated with no query changes.
On the other hands, PL/CUDA assumes the core logic of algorithm is implemented manually for each use case.
Why we changed this concept? It is based on user's feedback.
Even if we don't need to describe CUDA code, right now, nobody implements complicated analytic algorithms in SQL, thus, it means user has to write up a new code to process them either SQL or CUDA. I'm not certain whether SQL is suitable language for this purpose, and most of known algorithm assumes procedural languages.
So, we thought writing a CUDA code may be a valuable option in some use cases, especially, processing of advanced algorithms. We call this type of GPU utilization manual optimization mode, in contradistinction to the existing automatic code generation from SQL; automatic optimization mode.

Array-Matrix

One other thing we need to pay attention is data-format and memory bus utilization rate when GPU kernel handles the data-format.
PostgreSQL adopts row-oriented data format. It is an I/O optimal data format for transactional workloads.
On the other hands, it has a downside when we reference individual columns within a record. Because the location of column is not predictable unless reading the record actually, we have to walk on records from the head, thus, it takes larger number of memory access.
It is unignorable penalty when we run a logic on GPU which has relatively smaller memory cache. In case of column-oriented data format, location of the data can be determined uniquely by pointer of the array and thread-id.

In addition, column-oriented data format has an advantage for GPU devices from the standpoint of memory bus utilization rate.
Unit size of GPU's memory transaction is usually 32bytes/256bits. If multiple processor cores requires coalesced memory location simultaneously, these multiple memory accesses are consolidated to a single memory transaction, then, a single memory transaction will load 8 x 32bits variables at once. This scenario pulls up the maximum utilization rate from the memory bus of GPUs; that is much higher than CPU/RAM bandwidth.
When we run a particular calculation by multiple processor cores, it tends to reference same columns simultaneously. Columns are scattered in row-oriented data structure, so it is hard to pull out the maximum utilization rate of memory bus.

However, columnar-format is not always winner. Transformation from row-format to column-format needs extra cost prior to GPU invocation, and it is hard to justify the data transformation cost for usual SQL operations like JOIN, GROUP BY, etc...
One candidate is highly computing intensive workload like advanced analytic algorithm which we will implement using PL/CUDA.

Fortunately, PostgreSQL already has a data-type which is almost equivalent to the column oriented data format. It is array data type, and we call the array data type with no NULLs and consists of fixed-length data type array-matrix.
An aggregate function array_matrix(variadic datatype[]) consumes multiple rows then produce a 2-dimensional array data. Any elements are re-ordered per column, and data location is predictable by the offset and width of the element data type.

f:id:kaigai:20161116145333p:plain

We usually call PL/CUDA function with array-matrix arguments.

Usecase.1 - Similarity Search on Drug Discovery

The first usecase I introduced is a similarity search workloads on drug-discovery *1.

First of all, I like to introduce the background of the problem we tackled.
When researcher tried to find out a candidate of new drug, it has to be "active" to the target protein which is related to the target disease. Some chemical compounds are inactive, some other chemical compounds are active but toxicity. Academic papers, daily published by somewhere, report relationship between a target protein and chemical compounds. So, researcher can gather the public data of chemical compounds relevant to a particular protein.

On the other hands, people said the total number of chemical compounds we can obtain as a test reagent and investigate are about 10,000,000. It is too expensive to purchase and test them in laboratory, with brute-force approach. So, researcher is motivated to pick up chemical compounds which have higher probability of active to the target protein.
It is an approach to search "similar" chemical compounds to the known ones; which are already reported in academic papers and etc...

Similarity is to define a distance between two chemical compounds. Euclid distance is one approach usually used to define geometrical distance between two points.
We used a combination of Jaccard index *2 and k-NN (nearest neighbor) method in our trial.

The k-NN method is used to define distance between a set of items and an item. Once we calculate all the distance between items, than picks up the largest k distances and considers its average the representative distance between them.
Jaccard index can be used when characteristics of two items are described in a bitmap. We consider the ratio of bitmap-AND and bitmap-OR as similarity of two items.

According to the logic, if number of query compounds set is Q, we once need to calculate Q similarities for each database item; that is about 10M. Than, these similarity must be sorted for each database item. Thus, total amount of computing order is almost O(DxQ) + O(DxQlogQ).
It is not small. If Q is 1000, we need to handle 10billion combination to process the logic.

The PL/CUDA function we implemented (knn_gpu_similarity()) did nothing special. It once computes the similarity between two chemical compounds by a processor core for each combination, then run the bitonic-sorting to pick up the largest k-similarities.
This PL/CUDA function takes two array-matrix that are constructed from the relation scan on the fly, or statically pre-built.
Once similarity search gets completed, it unnest the matrix to a generic stream of records by matrix_unnest, then processes the results set using usual SQL features (tables JOIN and window function here).

Its performance is quite impressive. We compared to the same logic based on CPU.
In case of the largest query set (1000), it reduces the response time more than x150 times faster.
It may have a power to change the workstyle of researcher. 3,000sec (=50min) is a timescale for batch job. It is too long to wait in from of the workstation. On the other hands, 20sec is scale for interactive operations; which allows try&error on research process.


Usecase.2 - Data Clustring (k-means)

The second usecase is clustering analysis.
k-means is a representative method for non-hierarchical cluster analysis, used for unsupervized learning.

This algorithm tries to get the final clustering with iteration of simple operations.
First, it assigns a cluster for each item randomly as initial state.

Second, makes a centroid for each cluster according to the initial state.

Next, choose the cluster of every items according to the centroid updated on the last step.

Next, update the centroid according to the latest cluster; updated on the last step.

Then, break the iteration if cluster assignment gets converged or reached to the threshold of the iteration.

The data-set we tried to apply k-means() clustering is a collection of city traffic data at Aarhus, Denmark, by the CityPlus project.
iot.ee.surrey.ac.uk

This dataset contains traffic data (car count, avg speed, ...) in 449 observation point all around the city. The total amount of sensor data is 13.5M records.
In this trial, we applied k-means() algorithm on the raw dataset, then make a summary for each observation point. We assumed each observation points belong to the most frequent cluster.
Then, mapped it on the google map using static map APIs.

The result is below:

It looks to me the blue observation points are bypass highway; many car count and high speed.
On the other hands, green line seems to me the way to the downtown, thus many car but slow speed.
I'm not sure the characteristics of the red line, but appears on the beltway frequently.

Because all the clustering calculation is executed inside of the database, it is quite easy to control the input data.
Below is the same diagram when weekdays and weekend.

  • weekdays


  • weekend

Here is a little difference between them, however, the diagram of weekend categorize the road to the downtown with same color of the highway. So, it has less traffic on the weekend, thus, car speed is higher than the case of weekday.

For the arrangement, all I did is just adding a WHERE clause on the query to kick k-means clustering. Utilization of the SQL flexibility is one of the biggest advantage of PL/CUDA, in addition to the performance benefit.

SELECT report_id, k, c
  FROM (SELECT report_id, k, c,
               row_number() OVER (PARTITION BY report_id
                                  ORDER BY c DESC) rank
          FROM (SELECT report_id, k, count(*) c
                  FROM matrix_unnest(
                        (SELECT gpu_kmeans ( array_matrix(
                                               int4_as_float4(report_id),
                                               avg_measured_time,
                                               avg_speed,
                                               vehicle_count),
                                             5)
                           FROM tr_rawdata
                          WHERE extract('dow' from timestamp) in (0,6)
                        )
                       ) R(report_id int, k int)
                 GROUP BY report_id, k
               ) __summary_1
       ) __summary_2
   WHERE rank = 1;

*1:KaiGai Kohei, Yoshimori Atsushi, Efficient Similarity Search Using Multiple Reference Molecules on PG-Strom architecture, CBI Annual Meeting, 2016

*2:also called Tanimoto index

PL/CUDAでk-means法を実装する

前回のエントリでは、CBI学会で発表を行った、PL/CUDAによる類似化合物の検索について説明した。

今回は、コレとはまた別のワークロードに対する応用という事で、クラスタリング処理のIn-Database実装に挑戦してみた。
トライしてみたのは k-means法 によるクラスタリング。非階層クラスタリングの領域では最も頻繁に使用される(と、言われている)アルゴリズムで、計算量もそこそこ大きい。

k-meansクラスタリングとは

教師なし学習方式の一つで、所与のデータ群を一定数(=k個)のグループに分類するためのアルゴリズムである。
以下のステップを一定回数、またはクラスタに属するデータ群に変化がなくなるまで繰り返す。

1.初期クラスタをランダムに設定する。

2.各クラスタの中心点を計算する。

3.各データ要素の属するクラスタを更新する。各データ要素はクラスタ中心点が最も近傍であるクラスタに割り当てられる。

4.新しいクラスタ定義に基づいて、各クラスタ中心点を再計算する。

5.以下繰り返し・・・。

これをPL/CUDAで実装するとどうなるか?

基本的には上記のアルゴリズムを愚直にCUDAで実装する事になるので、特別な事はしていない。
一回のPL/CUDA関数呼び出しの中で何度も繰り返し処理を行う形になるので、メインのGPU Kernelは1スレッドで起動し、Dynamic Parallelismを使って別のGPU Kernelを起動する形にする方が合理的である。

関数定義の中身に興味がある方は、こちらをどうぞ。
toybox/gpu_kmeans.sql at master · kaigai/toybox · GitHub

In-databaseでクラスタリングする

以下の図はお試し的に10000件のランダムデータを5つのクラスタに分割してみたもの。綺麗に分類されている。

ただ、ランダムデータだけだと面白くないので、来週のPGconf.SVでの発表に向け、そこそこ件数が多くてクラスタリングに適したデータは無いかと探してみたら・・・あった。

iot.ee.surrey.ac.uk

FP7ファンドの支援を受けたCityPulseというプロジェクトが収集しているデータで、デンマークのオーフス(Aarhus)市の自動車通行状況を調査したデータが公開されている。
これは、ある二地点間を通過した自動車の台数や平均速度がタイムスタンプと共に収集されているもので、2014年2月~6月の四ヵ月間のデータが全部で1350万レコード。
これをクラスタリングにかけると、どこの道路とどこの道路の通行状況が似ているのか分かるはず。

と、いう事でやってみた。

まず、PL/CUDAを用いて実装したgpu_kmeans()関数は以下のように定義されている。
第一引数にクラスタ化すべきデータとそのID値をreal[]行列として与え、第二引数にはクラスタ数を与える。

CREATE OR REPLACE FUNCTION
gpu_kmeans(real[],    -- ID + Data Matrix
           int,       -- k-value (number of clusters)
           int = 10,  -- max number of iteration
           int = 1)   -- seed of initial randomness
RETURNS int[]

これをクエリの中で使用すると以下のようになる。
少しGoogle Map Static APIを勉強して、SQLから直接URLを生成するようにしてみた。
ただ、URL長の制限が8KBという事で、線を何百本も引くような地図は作れないため、泣く泣く125件分だけに限定して地図を生成している。

WITH
summary AS (
SELECT report_id, k, c
  FROM (SELECT report_id, k, c,
               row_number() OVER (PARTITION BY report_id
                                  ORDER BY c DESC) rank
          FROM (SELECT report_id, k, count(*) c
                  FROM matrix_unnest(
                          (SELECT gpu_kmeans(array_matrix(
                                               int4_as_float4(report_id),
                                               avg_measured_time,
                                               avg_speed,
                                               vehicle_count),
                                             5)
                             FROM tr_rawdata
                          )
                       ) R(report_id int, k int)
                 GROUP BY report_id, k
               ) __summary_1
       ) __summary_2
   WHERE rank = 1
),
location AS (
SELECT point_1_lat, point_1_lng,
       point_2_lat, point_2_lng,
       CASE k WHEN 1 THEN 'red'
              WHEN 2 THEN 'blue'
              WHEN 3 THEN 'green'
              WHEN 4 THEN 'purple'
              ELSE 'orange'
       END col
  FROM summary s, tr_metadata m
 WHERE s.report_id = m.report_id
),
path_definition AS (
SELECT 'path=color:' || col || '|weight:3|' ||
       point_1_lat::text || ',' || point_1_lng::text || '|' ||
       point_2_lat::text || ',' || point_2_lng::text path_entry
  FROM location
 LIMIT 125 -- becuase of Goole Map API restriction
)
SELECT 'http://maps.google.com/maps/api/staticmap?' ||
       'zoom=11&' ||
       'size=640x480&' ||
       'scale=2&' ||
       string_agg(path_entry, '&') ||
       '&sensor=false'
  FROM path_definition;
$ wget -O map.png "`psql traffic -At -f ~/traffic.sql`"

その結果がこれ。
f:id:kaigai:20161113145405p:plain

どうやら、青の区間は高速道路かバイパス道路で、比較的自動車の台数が多くスピードが出ているクラスタに見える。
一方、緑の区間ダウンタウンに向かう道路なので、慢性的な渋滞に悩まされているのだろうか?
赤は少し判断に迷うが、そのどちらでもない、といった所のようである。


また、これは中核となるkmeansクラスタリングSQLの中に埋め込んでいるので、抽出条件を変えるだけで簡単に母集団を切替える事ができる。
以下の例は、個々のデータのタイムスタンプを用いて、ウィークディ(月曜~金曜)とウィークエンド(土曜、日曜)でそれぞれクラスタリング、図を作ってみたケース。

■平日

■週末

微妙な差ではあるが、週末のケースでは、ダウンタウンに向かう道路がハイウェイと同じ色に分類されている。
平日に比べると交通量が減る分、自動車がスイスイ進むという事だろうか。

閑話休題。今週のPGconf.SVでは、この辺のネタも交えてPL/CUDAメインで話をしてくる事になります。

PL/CUDAによるIn-database Analytics ~創薬におけるワークロードを例として~

GPU PostgreSQL


やや場違い感が否めないが、今週、CBI学会(計算情報化学生物学会)2016年大会でポスター発表を行ってきた。

発表タイトルは『Efficient Similarity Search Using Multiple Reference Molecules on PG-Strom architecture』というもので、要は、創薬分野で新薬の候補となる化合物を類似度サーチする際に、PG-Stromを用いて高速かつIn-Databaseで行ってしまおうという試みである。

前提となる利用シーンは、例えば次のようなシチュエーションである。
ある疾患には特定のたんぱく質が作用する事が分かっており、また、世界各地で発表される研究論文の中には『このたんぱく質には〇〇〇という化学物質が活性を持っている』というような事が記載されている。こういった組合せは別に1:1という訳ではなく、別の研究論文には化合物△△△が、別の論文には□□□が、程度の多寡はあれ活性を持っていたという事が書かれている訳である。

研究者は、このような研究論文からデータを引っ張ってきて、『タンパク質Xに対して活性を持つ化学物質の組』というのを作る。これを便宜上、Query Chemical Compounds (Q)と称する事にする。

一方、薬剤の候補となる化合物の探索空間としては概ね1000万件程度が知られている。これを便宜上、Database Chemical Compounds (D)と称する事にする。これらがどのような化学的特徴を持つのかという事は分かっているものの、目的となるたんぱく質に活性を示すのか否かは個別に調べてみる必要がある。但し、調べるといってもそれなりに費用・時間を要するため、適切なものを効率的に絞り込まねばならない。

f:id:kaigai:20161028230831p:plain

ここで使用するのが類似度探索(Similarity Search)である。既に学術論文等で目的のたんぱく質に活性を示す事が報告されている化学物質に"近い"化合物を、1000万件の探索空間から絞り込む事ができれば、関連しそうな化合物に一気に網をかける事ができる。

選択の基準となるのが、化合物同士の"近さ"であるが、幾つかの方法が考えられる。中心点距離や平均値を用いる方法もあるが、今回はk-NN(k-Nearest Neighbor)法を用いた。
これは、Q化合物群とあるD化合物間の距離(類似度スコア)を全て計算した上で、そのうち最も近傍にあるk個の距離の平均値を代表距離とするものである。

この時、類似度スコアの計算量としては概ねO(QxD)のオーダーとなる。
つまり、Q化合物群が1000個、D化合物群が1000万個である場合には、100億通りの組合せに対して類似度スコアを計算する必要があり、そこそこしんどい計算になる。

今回の研究で使用したアプローチは、Q化合物群、D化合物群を共にPostgreSQLのテーブルに格納し、ここから読み出したデータをPL/CUDA関数の引数として与え、この関数の内部で①類似度スコアの計算、②並び替え(ソート)、③上位k件の平均値導出、までを並列に実行してやろうというものである。

PL/CUDAというのはPG-Stromが提供するPostgreSQLのProcedural Languageの一つで、SQL関数の定義部分にCUDAコードを直接記述する事ができる。実行時には、このコードブロックがGPU Kernel関数のテンプレートの中にスポっと挿入され、PG-Stromのインフラを使ってコードをビルド、GPUでの並列実行を行う。
関数の引数や返り値は、本来はRAM<-->GPU間で転送する必要があるが、この辺はSQL関数の定義から機械的に生成できる部分であるので、PG-Stromが全て面倒をみてくれる。今回は、Matrixに相当するデータ構造としてPostgreSQLの2D配列データ構造を使用してデータの受け渡しを行った。

そして、ひとたびk-NN法類似度サーチのロジックをPL/CUDA関数に組み込めば、あとは見慣れたSQLのパズルである。
例えば、以下のようなクエリを用いてfinger_print_queryテーブルから読み込んだQ化合物群、finger_print_10m_matrixテーブルから読み込んだD化合物群を、PG-Stromの提供するarray_matrix()関数を用いて2D配列データに変換し、PL/CUDA関数の引数として与えている。

PL/CUDA関数の返り値もまた2D配列であるが、これも同様にPG-Stromの提供するmatrix_unnest()関数により、一般的なN行のレコードへと戻している。

PREPARE knn_sim_rand_10m_gpu_v2(int)	-- arg1:@k-value
AS
SELECT float4_as_int4(key_id) key_id, similarity
  FROM matrix_unnest((SELECT rbind(knn_gpu_similarity($1,Q.matrix,D.matrix))
                        FROM (SELECT cbind(array_matrix(id),
                                           array_matrix(bitmap)) matrix
                                FROM finger_print_query
                               LIMIT 99999) Q,
                             (SELECT matrix
                              FROM finger_print_10m_matrix) D))
    AS sim(key_id real, similarity real)
ORDER BY similarity DESC
LIMIT 1000;

ではこれで性能はどれ位出るのか?手元の環境で計測してみたところ、同じロジックをCPUで実装((knn_gpu_similarity()と等価なknn_cpu_similarity()関数をCで実装))して実行した場合と比べ、問題サイズが大きい場合では130倍を超える応答時間の改善を確認できた。

f:id:kaigai:20161029000200p:plain

Q-size CPU(E5-2670v3) GPU(Tesla K20) GPU(Tesla M40) 高速化率(CPU vs M40)
10 30.25s 13.23s 13.41s x2.3
50 145.29s 14.49s 13.54s x10.7
100 295.95s 15.99s 14.04s x21.1
500 1503.31s 27.11s 17.47s x86.1
1000 3034.94s 43.88s 22.58s x134.4

In-Databaseでのデータ解析処理でここまで応答時間が変わってくると、計算の運用に関わる従来の前提も色々と変わってくることになる。

一つ考えられるシナリオとしては、計算性能を担保するために外部のアプリケーションを使用してデータ解析を行っていたような利用シーンで、In-Database処理が十分な計算性能を出すようになった結果、データをエクスポートする必要がなくなるという事。これは、Hadoop方面の人が言うように『データのある場所で計算を行う』アプローチであり、最近の技術トレンドと合致している。

そしてもう一つの副次的な効果として、PL/CUDA関数の結果がSQLのデータ構造として返却されるという事は、データ解析ロジックの中で最もヘビーな計算処理を終えた後のデータに対して、JOIN、Window関数、ORDER BY、GROUP BYといったSQLの構文を使って非常にフレキシブルなデータの加工・後処理が可能になるという事である。

これらは、研究者がデータを多面的・多角的に眺めて新たな知見を得る事に役立つが、従来50分を要していた処理が22秒まで短縮された事と併せ、研究に不可欠なTRY&ERRORに適した環境を提供してくれることだろう。

同期DMAと非同期DMA

GPU PostgreSQL SSD

おっとっと、やらかしてしまった(但し、良い方に)。

PG-Strom + NVMe-Stromでのパフォーマンス計測の際に、SSDからロードしたデータ以外に、例えばテーブル定義情報や定数パラメータといったSQLの実行に必要な情報は一般的なRAM-to-GPU DMAで転送していたのだけども、ココがうっかり同期DMAになっていたために、本来の性能を発揮できないでいた。

そこで、きちんと非同期DMAを実行できるようにコードを修正し、改めてPG-Strom + NVMe-Stromの実行速度を測り直した数字が以下の通り。じゃん。

f:id:kaigai:20160908214519p:plain

ワークロードは変わらず、以下の三種類のクエリを64GB/7億件のテーブルに対して実行した。

  • Q1: 比較的シンプルな検索条件を持つスキャン
  • Q2: 比較的複雑な検索条件を持つスキャン
  • Q3: 文字列マッチ(LIKE句)を持つスキャン

応答時間が概ね42~43secの範囲に収まっているのがお分かりいただけると思う。
これをスループットに直すと、64GB / 43sec = 1524MB/sec のレートでデータを処理できており、Intel SSD 750のカタログスペック 2200MB/s からすると概ね70%程度となる。

応答時間に殆ど差が見られないという事で、これは、GPUで実行するクエリの評価はI/Oよりも短時間で完了するために、非同期DMA転送の裏側に隠ぺいされてしまったと考える事ができる。

CUDAでは非同期で実行する個々のタスク(例えば、RAM=>GPUへのデータ転送、GPU Kernelの実行、など)の順序関係を制御するために、ストリーム(CUstream)という制御構造を持っている。
ある種当然ではあるが、ホスト側から送出されてくるデータを用いて計算しようというGPU Kernelは、少なくともデータ転送が終わらなければ実行できないし、計算結果をデバイス側⇒ホスト側に転送する時も、GPU Kernelの実行が終わっていないと、計算途中のGPU RAMのイメージを送りつけられても困惑する限りである。

CUDAの持つRAM=>GPUのデータ転送用APIには二種類あり、一つは cuMemcpyHtoD() などの同期API。これは、関数が呼び出された時点で呼び出し元をブロックし、RAM-to-GPU DMAを用いてデータを転送する。関数から戻った時点で、既にGPU側のバッファにデータの転送は終わっており、ストリームとは無関係に使用できる。
もう一つは cuMemcpyHtoDAsync() などの非同期API。これは、ストリームにDMA要求が突っ込まれた順番に、非同期にデータ転送を行う。GPU Kernelの実行開始なども、ストリームに要求が突っ込まれた順序を元にした依存関係を壊さないように、ただし、DMAチャネルなどのリソースが空けば待っているタスクはどんどん実行される。

ただし、cuMemcpyHtoDAsync()を用いても必ずしも非同期DMAになるかと言えば、少々落とし穴があり、CPU側のRAMを『ここはDMAバッファだからスワップアウトしないでね』とCUDAランタイムに登録した領域以外を転送元/転送先に指定した場合、黙って同期DMAモードで動作するのである。
今回の場合がそれで、本来はDMAバッファを cuMemHostRegister()で登録しておかねばならないところを忘れていた。Orz

結果、本来であれば次々とデータ転送を行えるところが、ストリームに突っ込んだ cuMemcpyHtoDAsync() が実行可能になるまでブロックされた挙句、同期DMAを行ったものだから、トータルの処理時間が随分と間延びした形になっていた。あーあ。

まぁ、スコアとしては前に計測した時から50%ほど伸びて、対PostgreSQLで見てみると、3~4倍程度のスループットを発揮しているので善しとしよう。

(EN) GpuScan + SSD-to-GPU Direct DMA

GPU SSD PostgreSQL

An article for none-Japanese readers....

What I'm recently working on is a feature to load data blocks from NVMe-SSD to GPU using peer-to-peer DMA.
It allows to bypass the CPU/RAM under a series of data loading process, thus, also allows to reduce number of expensive data copy.
Once data blocks are loaded onto the GPU's RAM, we can process individual records within the blocks, by thousands processor cores, according to the GPU binary which shall be generated based on SQL query.

Here is my longstanding project; PG-Strom that is an extension of PostgreSQL to off-load multiple SQL workloads on GPU devices, transparently. It has been developed for four years, and now supports simple scan, tables join, aggregation and projection.
Its prime focus is CPU intensive workloads, on the other hands, it didn't touch storage subsystem of PostgreSQL because the earlier version of PG-Strom assumes all the data set shall be pre-loaded onto physical memory. No need to say, we had a problem when we want to process a data-set larger than physical RAM.

One my solution is a feature enhancement to support data loading using SSD-to-GPU Direct DMA.
Please assume a use case of a large table scan when its WHERE clause filters out 90% of rows. Usually, DBMS once loads entire data blocks from the storage to RAM, then evaluate individual records according to the WHERE clause. However, this simple but massive calculation is a job GPU can process much more efficiently, and can eliminate 90% of the data prior to loading onto CPU/RAM. It also enables to keep much more valuable data rather than cache out by junk data.

f:id:kaigai:20160825002243p:plain

Once we could load data blocks to GPU prior to CPU, we already have a feature to run tables join and (partial) aggregation on GPU. From the standpoint of CPU, it looks like the storage system gets an intelligence to run a part of SQL workloads, because row-filtering, tables join and aggregation are already done when data stream is arrived at CPU in respond to its i/o requests.

A few days before, the initial version of SSD-to-GPU Direct DMA driver gets working. So, I tried to measure its throughput to load data blocks from a test file to GPU RAM. The result was remarkable.
The "NVMe-Strom" is a record of SSD-to-GPU Direct DMA. Its throughput to load data blocks onto GPU device exceeds about 2200MB/s; which is catalog spec of Intel SSD 750(400GB).
It is also twice faster than a pair of usual read(2) and cuMemcpyHtoDAsync; that it a CUDA API to kick asynchronous RAM-to-GPU DMA. When i/o size is smaller, its system-call invocation cost drives down the throughput furthermore.
f:id:kaigai:20160905215358p:plain

  • CPU: Intel Xeon E5-2670 v3 (12C, 2.3GHz)
  • GPU: NVIDIA Tesla K20c (2496C, 706MHz)
  • RAM: 64GB
  • OS: CentOS 7 (kernel: 3.10.0-327.18.2.el7.x86_64)
  • FS: Ext4 (bs=4096)

In addition, I tried to measure the performance of a few SQL queries:

  1. A large table scan with simple WHERE clause
  2. A large table scan with complicated WHERE clause
  3. A large table scan with LIKE clause

The tables size is about 64GB, contains 700million rows. The result is quite interesting.

f:id:kaigai:20160908214519p:plain
*1

The result of "PG-Strom" (red) shows the performance of GPU acceleration based on the existing storage system of PostgreSQL. It implies the throughput is dominated by i/o, thus unavailable to complete tables scan less than 140sec.
It is valuable when WHERE clause takes complicated expression, but less advantage in other cases.

On the other hands, "PG-Strom + NVMe-Strom" (blue) broke this limitation. In case of simple query, it scans the 64GB table by 42.67sec, thus, its processing throughput is 1535MB/s.
We can expect PG-Strom is more valuable for more CPU intensive workloads, like JOIN or GROUP BY, rather than simple tables scan. I expect the pair of PG-Strom and NVMe-Strom will accelerate this kind of workloads going beyond the existing i/o boundary.
I'm really looking forward to benchmarks of the workloads that contains JOIN and GROUP BY when I could add support of SSD-to-GPU Direct DMA on these features!

QUERY for table construction)

CREATE TABLE t_64g (id int not null,
                    x float not null,
                    y float not null,
                    z float not null,
                    memo text);
INSERT INTO t_64g (SELECT x, random()*1000, random()*1000,
                             random()*1000, md5(x::text)
                     FROM generate_series(1,700000000) x);

postgres=# \d+
                         List of relations
 Schema |       Name       | Type  | Owner  |  Size   | Description
--------+------------------+-------+--------+---------+-------------
 public | t                | table | kaigai | 965 MB  |
 public | t_64g            | table | kaigai | 66 GB   |

QUERY1)
SELECT * FROM t_64g WHERE x BETWEEN y-2 AND y+2;

QUERY2)
SELECT * FROM t_64g WHERE sqrt((x-200)^2 + (y-300)^2+ (z-400)^2) < 10;

QUERY3)
SELECT * FROM t_64g WHERE memo LIKE '%abcd%';

*1:Performance was measured again because asynchronous DMA mode was not enabled in the previous result. Thus, synchronous copy blocked unrelated tasks.

GpuScan + SSD-to-GPU Direct DMA

SSD GPU PostgreSQL

前回の動いた!SSD-to-GPU Direct DMA - KaiGaiの俺メモの記事では、Intel SSD 750とNVIDIA Quadro K1200を使って、Raw-I/OでのSSD-to-GPU Direct DMAが動くところまでを紹介した。

この時点で測定できたSSD-to-GPU Direct DMAのスループットは概ね1400MB/s程度で、VFS経由のスループット1100MB/sを約20%程度上回るものであった。

ただ、Quadro K1200のスペックは以下のようなもので、お世辞にもハイパフォーマンスを期待して使用するタイプのカードではない。*1

チップ GM107GL (CC5.0)
CUDAコア数 512コア, 1000MHz
メモリ容量 4GB GDDR5
メモリ帯域 80GB/s, 128bit

という事で、同じくGPUDirect RDMAに対応した Tesla K20c を使って同じように測定を行ってみた。その結果が以下の通り。

驚いたことに、GPUへのデータロードがIntel SSD 750のカタログスペック通り、2200MB/sまで出ている。
一方で、VFS経由のデータロードは自宅のPCで実行した時と大差ない。

これは当然といえば当然で、①SSD->(VFS)->RAM ②RAM->GPUと二段階のコピーを行わねばならないが、①のSSD->(VFS)->RAMはカタログスペックでも高々2.2GB/sの帯域しか無いにも関わらず、②のRAM->GPUは10GB/sを越える帯域を持っているため、支配項は①の処理であり、ここはGPUの種類に関係のない箇所である。

なお参考までに、VFS経由でSSD->RAMへとデータロードを行った場合のスループットをddコマンドを用いて計測してみた。

基本的にはI/Oサイズが大きいほうが、システムコール呼び出しのオーバーヘッドが少ない分、性能上は有利である。(実際にBlock-I/Oが発行されるのはもっと細かい単位になるが)
ただ、PostgreSQLのブロックサイズは基本8KB、ビルド時のコンフィグによっては32KBまで拡大可能だが、この程度のI/Oサイズでは高速ストレージの応答時間に対するシステムコール呼び出しオーバーヘッドが無視できないレベルになってしまい、スループットが700MB/s程度まで落ち込んでしまっている。
また、もしかしてPage Cacheにコピーを持つ事がオーバーヘッドの主因なのではと思い、O_DIRECT付きのI/Oを試してみたが、こちらは外れ。I/Oサイズを32MB取ったにも関わらず、却ってパフォーマンスの低下を招いてしまった。

で、ここまでが前フリでRaw-I/OでのSSD-to-GPU Direct DMAのおさらい。

昨日、ようやくGpuScanとSSD-to-GPU Direct DMAを統合することができ、全体的にはまだまだバグバグ不安定*2ではあるものの、なんとか一発動かすことができた。

以下のグラフは、64GB/7億件のレコードを持つテーブルに対して3種類のスキャンクエリを実行し、その応答時間を計測したもの。
比較対象は以下の3つで、結果はクエリの応答時間であるので、これが短いほどベター。

各クエリは以下の通り

  1. 比較的シンプルな条件句を持つスキャンクエリ
    • SELECT * FROM t_64g WHERE x BETWEEN y-2 AND y+2;
  2. 比較的複雑な条件句を持つスキャンクエリ
    • SELECT * FROM t_64g WHERE sqrt((x-200)^2 + (y-300)^2+ (z-400)^2) < 10;
  3. 文字列パターンマッチを含むスキャンクエリ
    • SELECT * FROM t_64g WHERE memo LIKE '%abcd%';

まず気になるのが、検索条件の複雑さに関わらず、従来のPG-Stromの応答時間が概ね140s前後に収まっていること。
PG-StromのGPU側処理は非同期で実行されるため、I/Oが十分に遅いようであれば検索条件の評価は完全にI/Oの裏側に埋もれてしまい、そこが処理性能の差としては見えなくなってしまう。
つまり、Intel SSD750 + Ext4上に構築したデータベースのスキャンにおいては、64GB / 140sec = 468MB/s 程度のスループットPostgreSQLのストレージ層の全力であるように見える。*3

一方で、PG-Strom + NVMe-Stromのケース。
比較的条件句がシンプルでDMAバッファが次々に空いたと考えられるQ1のケースでは、64GB / 67.19sec = 975.38MB/s のスループットを発揮している。

これだけでも既にPostgreSQLのシーケンシャルリードの限界を越えているのだが、PostgreSQLのストレージ層がRaw-I/Oの帯域587.38MB/sに対しておよそ20%減の468MB/sで処理できている事を考えると、まだ伸ばせる余地はあるように思える。
データの転送自体はDMAで非同期処理になるとはいえ、このレベルのI/O要求を出し続けるとなると、コマンドの発行だけでも相当なCPU負荷になる。例えば、PostgreSQL 9.6の新機能であるCPU並列にGpuScanが対応し、複数のワーカが同時にSSD-to-GPU Direct DMAを発行し続ければ、NVMe-SSDの理論帯域まで使い切る事も可能かもしれない。

現時点では、スキャンを担当するGpuScanへの対応を行ったところだが、GpuJoinやGpuPreAggのロジックでも全く同じ原理を用いてSSD-to-GPU Direct DMA機能を実装することができる。

元々、CPU負荷が高い方が、PostgreSQLとの差が付きやすいというのはQ2の結果を見ても明らかである。
所詮、GpuScanは条件句の評価にすぎないが、よりCPUインテンシブなJOINやGROUP BYの処理をSSD-to-GPU Direct DMAベースで実装し、パフォーマンスを測定するのが楽しみになってきた。

*1:このカードを購入した経緯は エルザ・ジャパン様の対応が神レベルだった件 - KaiGaiの俺メモを参照。

*2:例外処理で色々とアカン事が起こったりする。:-)

*3:この辺、何かチューニングの余地があるかもしれないが、今回はそこまで掘り下げられていない。

動いた!SSD-to-GPU Direct DMA

SSD GPU


ここしばらく、NVMe-SSDからGPUへとPeer-to-Peer DMAを行うためのLinux kernelドライバを書いている。

これは昨年末のPGconf.JPのLTでアイデアを先に発表したもので、従来は、例えばテーブルスキャンに際して90%の行がフィルタリングされる場合であっても、データをストレージからRAMにロードしていた。しかし、どうせフィルタリングするのであれば、バッファのために利用したRAMのうち90%は無駄である。

基本的なアイデアは、ストレージからのデータロードに際して、CPU側のRAMではなく、GPU側のRAMへロードし、そこで数百~数千コアの計算能力を使って行のフィルタリングや、あるいは、テーブル同士のJOINや集約演算を行ってしまう。そして、これらの前処理が終わった段階でCPU側へデータを書き戻してやれば、CPUから見ると『ストレージからデータを読出したら、既にJOINもGROUP BYも終わっていた』という状態を作り出す事ができる。

まだPostgreSQL側での対応が済んでいないが、やっとドライバだけは動くようになったので簡単な性能テストを行ってみた。

まず、GPUの情報を確認してみる。
搭載しているのはQuadro K1200で、これはドライバの必要とするGPU Direct DMA機能に対応している。

で、デバイスを nvidia-smi -q で確認すると、つらつらとデバイス情報が表示される。
このモデルはGPU RAMを4GB搭載しているが、実はGPU Direct DMAでは搭載RAMの全ての領域を同時に使用できる訳ではない。
ここでBAR1 Memory Usageと書かれたエリアが256MB存在するが、これがPCIバスを通じてホスト側の物理アドレス空間にマップする事のできる大きさで、いわば4GBのGPU RAMを256MB分の大きさの窓から覗くようなものである。

[kaigai@magro ~]$ nvidia-smi -q

==============NVSMI LOG==============

Timestamp                           : Thu Aug 25 00:49:35 2016
Driver Version                      : 352.93

Attached GPUs                       : 1
GPU 0000:01:00.0
    Product Name                    : Quadro K1200
    Product Brand                   : Quadro
           :
    FB Memory Usage
        Total                       : 4095 MiB
        Used                        : 9 MiB
        Free                        : 4086 MiB
    BAR1 Memory Usage
        Total                       : 256 MiB
        Used                        : 1 MiB
        Free                        : 255 MiB
    Compute Mode                    : Default
           :

なお、このBAR1領域は、Tesla K40/K80やM40といった上位モデルでは、物理アドレスサイズを越える16GBが用意されており、これらのGPUを持っているリッチメンであればBAR1領域の小ささに悩む必要もないハズである。

とりあえず、今は手元にQuadro K1200しかないので、これでトライ。

データ転送のパターンとしては、32MBのバッファを6個確保し、ファイルの内容を順にこれらのバッファに非同期転送を行う。非同期転送が完了したタイミングでCUDAからコールバックが呼び出されるため、バッファが空いたらすかさず次の非同期転送をキューイングしていく。

本来であれば、GPUで何か処理を実行してデータサイズを減らしてからCPU+RAMへ書き戻すのが正しい姿であるが、まだGPU側で処理すべき事を実装できていないので、ここは単純にSSDから読み出した内容を同じバッファへと書き戻す事とした。

通常のVFS経由でのデータロードだと、上記の図のようになる。
read(2)でSSDからバッファにデータをロードし、これをcuMemcpyHtoDAsync()とcuMemcpyDtoHAsync()を使ってCPU RAM⇔GPU RAM間でPCI-Eバスを介して移動させる。

一方、SSD-to-GPU Direct DMAを使用した場合、データの流れはシンプルになる。
SSDからGPUPCI-Eバスを介してPeer-to-Peerでデータ転送が行われ、その後、GPU RAM⇒CPU RAMへの転送が行われる。

かなり乱暴に考えても、CPU RAMに一旦コピーする手間が省ける分は処理性能が稼げるはずである。

これを、OSのキャッシュの影響を避けるため、16GB搭載のマシン上で40GB、100GBの二つのファイルに対して実行してみた。

結果は以下の通り。

性能指標としては、データ転送量を一連の処理時間で割ったスループットを使用している。
SSD-to-GPU Directのケースが最も早く、概ね1.4GB/s程度のスループットを出している。ただし、Intel SSD 750 (400MB)のカタログスペックはシーケンシャルリード 2200MB/s と記載してあるので、これに比べるとまだデバイスの性能を発揮しているとは言い難い。
とりあえず、ドライバが動きましたという段階なのでアレだが、今後、どこで引っかかっているかは調べる必要がある。

一方、VFS経由でデータをロードした場合は1.1GB/s程度のスループットに留まっている。これは、SSD⇒CPU RAMへのデータ転送が余分に必要となっている分、不可避の差とも言える。ただ、これはPostgreSQLでのワークロードを反映しているとは言えない。
というのも、1.1GB/sを記録したケースというのは、read(2)にバッファサイズである32MBを与えた場合であって、システムコール呼び出しに関わるオーバーヘッドが極めて少ないと言えるため。
通常、PostgreSQLのI/Oの単位は8KBで、コンフィグで設定を変えたとしても32KBまでしか増やす事ができない。
こうなると、40GBや100GBといった大きさのファイルをスキャンする際、特にNVMe-SSDのような高速デバイスを使う場合だと、システムコールの呼び出しが律速要因となってしまうため、大幅にスループットが低下しているのが判る。

現在、PostgreSQL側の対応も実装中であるので、単純なI/Oだけでなく、実際にPostgreSQL+PG-Stromにクエリを食わせてみた時の性能値についても追って報告したい。