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

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

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

今回、ACMチューリング賞*²受賞者のJim Gray氏が創設したソートベンチマークコンテスト*³の中の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で律速するようになりました。表１に示すようにマルチスレッド*⁴化により実行時間を大幅に短縮することで時間と電力の積である電力量を低減したり、DMA*⁵転送の活用により、CPUの負荷を減らし、DRAM、SSDの性能を引き出すなどの施策を駆使して電力効率の向上を狙っています。

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

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

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

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