技術トピックス

システム技術

ソートベンチマークコンテストにおいて「KioxiaSort」がワールドレコード更新

ビックデータ解析やウェブ検索などに利用されるデータのソート*1は、現代社会には必要不可欠な技術です。データのソートは、コンピューティングやメモリ/ストレージ性能の向上とソートアルゴリズムの改善に伴い、時間の短縮が進められています。
 

一方、現代社会においてエネルギー問題は重要な課題であり、コンピューティング性能向上に伴う電力量増大も解決しないといけない問題です。そのため、データソートの時間短縮だけでなく、データソートにかかる電力量削減は非常に重要となっています。
 

今回、ACMチューリング賞*2受賞者のJim Gray氏が創設したソートベンチマークコンテスト*3の中のJouleSortと呼ばれる、データソートで消費した電力量を競うカテゴリにおいて、我々が開発したデータソートアルゴリズムKioxiaSortを用いた記録が2019年11月27日にワールドレコードに認定されました。
 

今回のKioxiaSortのソートアルゴリズムは、典型的なMergeソートを発展させたものであり、図1の通り2つのフェーズに分けられます。ソートされていない1TBのファイルをDRAMにのり切る程度のファイルに分割し、その中でソートするChunked Sortフェーズ、ソートされた複数ファイルをマージするMergeフェーズです。ここで、Chunkは大きなファイルをいくつかの塊に分けることを指しています。1TBのデータを分割しソートを行うため、Chunked Sort フェーズではソートされた複数のファイルが出来上がります。その後Mergeフェーズでソートされた複数ファイルをソート関係を維持しながらマージして、最終的にソートされた1TBのファイルが完成します。
 

これらのソートは図2に示す通り、1台のPCにBiCS FLASH™が搭載されたSSD 9台を搭載して実行しました。その中の1台はキオクシア クライアントSSD XG5-PをOS用ドライブとして利用しています。
 

大規模データのソートでは、CPU、DRAM、SSDを効率よく使う必要があります。これまではSSDで律速している部分が多かったのですが、SSDの高性能化の結果、CPUやDRAMで律速するようになりました。表1に示すようにマルチスレッド*4化により実行時間を大幅に短縮することで時間と電力の積である電力量を低減したり、DMA*5転送の活用により、CPUの負荷を減らし、DRAM、SSDの性能を引き出すなどの施策を駆使して電力効率の向上を狙っています。
 

図2の環境でKioxiaSortを実行した結果、1TBのデータソートを89キロジュール*6で達成し、従来の記録を大幅に更新しました(図3)。また、1TBのソートにかかった時間は8分45秒であり、ストレージのスループットは7.6GB/sとなりました*7
 

これは、最新のBiCS FLASH™ SSDを用いて現代社会の基盤技術であるデータソートを高電力効率で実行した結果であり、これによって、今後のAI、5G時代に向けてSSDを用いたデータソートアルゴリズムの最適化がエネルギー問題解決の一助となる可能性を示しました。
 

今後も、我々はBiCS FLASH™およびそれを用いた製品で社会貢献を目指し、研究開発を続けていきます。

*1…データをある規則に従って順番に並び替える(整列する)こと

*2…計算機科学分野で革新的な功績を残した人物に年に1度ACM(Association for Computing Machinery)から贈られる賞

*3…http://sortbenchmark.org/ ご参照

*4…一つのコンピュータプログラムを実行する際に、複数の処理の流れを並行して進めること
(シングルスレッドではプログラムの処理の流れが一本のみ)

*5…Direct Memory Access。CPUを介さずに直接メモリにアクセスする方法。

*6…電力量やエネルギーの単位。1ジュール(1 J (Joule)=1 W・s)

*7…http://sortbenchmark.org/KioxiaSort2019.pdf ご参照

記載されている社名・商品名・サービス名などは、それぞれ各社が商標として使用している場合があります。

図1:KioxiaSortアルゴリズムフロー

図1:KioxiaSortアルゴリズムフロー

図2:KioxiaSort実行環境

図2:KioxiaSort実行環境

表1:Mergingフェーズにおける電力量のスレッドによる違い

表1:Mergingフェーズにおける電力量のスレッドによる違い

図3:JouleSortコンテスト ワールドレコード推移

図3:JouleSortコンテスト ワールドレコード推移

関連リンク