Conflict-Free Vectorization of Associative Irregular Applications with Recent SIMD Architectural Advances

逐次アルゴリズムの並列化の知見のために読む

Abstract

間接メモリアクセスを伴う不規則なアプリケーション
は、従来、SIMD処理には不向きとされていました。近年、いくつかの進歩が見られるものの、SIMD処理には不向きとされてきました。
を実現するためには、高価なデータ再編成か有利な入力配分が必要です。
性能を発揮します。本研究では、インベクターリダクションという新しいベクトル化手法を提案し、効率的に
連想不規則アプリケーションの高速化を実現します。この
不規則削減の連想性を利用するアプローチ
で、SIMDベクトル内のデータ競合を解決する。我々は、新しい競合検出機能を持つインベクターリダクションを実装した。
インテル AVX-512 命令セットでサポートされる命令と、それを容易にするプログラミングインターフェースを提供します。
このような連想不規則アプリケーションのベクトル化を実現しました。
従来のアプローチと比較すると、インベクターリダクションは
データ再編成のオーバーヘッドを大幅に削減し、不利な条件下でも高いSIMD利用率を達成します。
入力分布 評価結果より、我々の
このアプローチは、多様な不定期アプリケーションのベクトル化で効率的です。
グラフアルゴリズム、粒子シミュレーションコード、ハッシュベース集計などのアプリケーションを対象としています。我々のベクトル化
は、元の逐次処理と比較して1.5倍から5.5倍の高速化を達成しました。
のコードをIntel Xeon Phiのシングルコアで動作させた場合、従来のコードに比べ
競合アプローチであるコンフリクトマスキングベースのベクトル化。
を1.4倍から11.8倍で実現しました。