リサーチグループ

並行コンピューティング

並行プログラミングは、過去数10年において人気を集めてきました。それぞれの言語とプラットフォームが対応するプリミティブを提供しているため、複数のNMAノードを備えるだけでなく、メモリモデルの緩和などによりシステムの複雑さが増すにつれ、効果的に使用することが困難となりました。実際、このことから、有効な並行アルゴリズムを構築するにはどうすればよいのか、進捗の保証、効率性、公平性の最適なトレードオフはどれであるのか、すべてのアルゴリズムの正確性をどのように確認すればよいのか、といった様々な重要な問題が生じています。こういった問題の一部は、学問的に部分的な回答を得ることができますが、実用的な問題の多くは未解決です。私たちは、実用的に妥当性を備え、理論的に価値のあるソリューションを提供するだけでなく、並列の分野で活動するほかの研究者や開発者の手立てとなる品質の高いツールを提供することで、こういった問題に答えることを主な目的としています。

次のようなテーマに注目しています。

  • 並行アルゴリズムとデータ構造
  • 不揮発性メモリ(NVM)
  • テストと検証
  • パフォーマンス分析、デバッグ、最適化
  • 並列プログラミング言語およびモデル
  • メモリの再利用

発行文献の全リストは、こちらをご覧ください。

メインプロジェクト:

Kotlinコルーチンの同期および通信プリミティブ

従来の並行プログラミングには、共有ミュータブルステートの操作が必要です。このプログラミングに代わるものがCommunicating Sequential Processes(CSP)モデルで、データは明示的な通信を介して共有されます。Kotlinコルーチンは、このモデルをKotlin言語に取り入れたライブラリで、プロセスがコルーチン(軽量のスレッド)を通じて表現されます。このため、コルーチン間の通信と同期には、よく知られているロックとセマフォから始まり、チャネルで終わるいくつかの抽象化が必要です。コルーチン間でデータを転送するための特殊なプロデューサーとコンシューマー構造です。このプロジェクトでは、有効なプリミティブを開発することとそれらをKotlinコルーチンに採用することに焦点が当てられています。
https://github.com/Kotlin/kotlinx.coroutines

Lincheck: JVMの並行性テスト

Lincheckは、JVMベースの言語における並行アルゴリズムをテストするための実用的なツールで、ストレステストと有界モデル検証の両方がサポートされています。JCStressなどの一般的なテストツールと比べた場合、Lincheckには、検査されるすべての演算、その正確性に関する特性、および各シナリオに使用される呼び出し数を指定することで、宣言的に並列テストを作成できるという大きなメリットがあります。おおまかに言えば、Lincheckは一連の並列シナリオを作成し、ストレステストまたはモデル検証モードでそのシナリオを実行し、指定された正確性を満たす結果を説明できる順次実行が存在するかどうかを確認します。Lincheckには上述の機能が備わっているだけでなく、緩和されたデータ構造セマンティクス、プロデューサー/コンシューマー構造とコルーチン実装で人気を集めているデュアルデータ構造設計、およびNVRAM向けに設計された耐性の高いデータ構造をサポートした初のテストツールでもあります。
https://github.com/Kotlin/kotlinx-lincheck

T並行グラフアルゴリズム

並列グラフ処理は、理論的観点と実用的観点の両方において、学問的によく研究された基本的なテーマです。しかし、ソーシャルナットワーク分析やコンパイラーなどの一部のアプリケーションでは、これらのアルゴリズムがオンライン、つまり並行であることが必要とされています。このプロジェクトでは、グラフ処理のさまざまな側面に対して実用的に功利的な並行アルゴリズムを構築することを目的としています。これには、一部のアルゴリズムに対する優先式スケジューラとしてマルチキューを使用すること、またはエッジの挿入と削除におけるオンラインの動的接続の問題が含まれます。今日では、ハードウェアプラットフォームのほとんどに複数のNUMAソケットが備わっているため、こういったアルゴリズムをNUMA対応にすることが不可欠となっています。

インターンシップ

一年を通じて、インターンを採用しています。コンピューターサイエンスまたは数学の強力な学歴をお持ちで、並行プログラミングに関する知識を有している方を優遇します。詳細については、Nikita Koval(nikita.koval@jetbrains.com)までメールでお問い合わせください。

グループメンバー

Nikita Koval
Nikita Koval
リサーチラボ/グループ長
Alexander Fedorov
Alexander Fedorov
研究員
Dmitry Khalanskiy
Dmitry Khalanskiy
研究員
Maria Sokolova
Maria Sokolova
研究員