再構成可能なチップをプログラミングするための古典的なアルゴリズムの長年の弱点を割る

EPFL、AMD、およびNovi Sad大学の研究者は、世界中で何百万もの再構成可能なチップをプログラムするアルゴリズムの長年の非効率性を明らかにしました。

通信、自動車、航空宇宙などの多くの産業 粒子物理学 フィールドプログラム可能なゲートアレイ（FPGA）と呼ばれる特別な種類のチップに依存しています。従来のチップとは異なり、FPGAはほぼ無限に再構成でき、カスタムチップを設計するには数年かかり、大金がかかる速いモービングフィールドで非常に貴重になります。しかし、この柔軟性にはキャッチが伴います。FPGA効率は、プログラムに使用されるソフトウェアに大きく依存します。

1990年代後半以来、Pathfinderとして知られるアルゴリズムはFPGAルーティングのバックボーンでした。その仕事：オーバーラップを作成することなく、何千もの小さな回路コンポーネントを接続します。

何十年もの間、それは非常にうまく機能し、標準になりました。しかし、サーキットが大きくなるにつれて、エンジニアはイライラする減速や時折完全な失敗に遭遇し始めました。機能するはずだったデザインは、しばしば「Unrotable」とラベル付けされていました。

現在、Novi Sad大学とテクノロジー企業AMDの同僚とともに、コンピューターおよびコミュニケーション科学の学校にあるParallel Systems Architecture Laboratory（PARSA）の研究者とともに、この古典的なアルゴリズムの内部の仕組みを解くことに一歩近づいてきました。

彼らに 紙、で最高の論文賞を受賞しました 第33 IEEE国際シンポジウム フィールドプログラム可能なカスタムコンピューティングマシンでは、なぜこれらの障害が発生し、パスファインダーの限界をどのように克服できるかを明らかにしました。

アルゴリズムの亀裂

「実際、Pathfinderが時々失敗することは驚くことではありません」とShashwat Shrivastava、博士号は説明しました。 Parsaの学生と論文の最初の著者。

「非常に早い段階で、研究者はFPGAルーティングの背後にある問題は非常に困難であることを示しました。その後、元のアルゴリズムの作成者は、少数の協力者とともに、Pathfinderが成功しない場合を発見しましたが、そのようなケースは実際には表示されないと指摘しました。」

何十年もの間、それは正しいように見えました。Pathfinderは驚くほどうまくいきました。

「実際、Pathfinderは非常にうまく機能したため、人々はめったにアルゴリズムに疑問を投げかけませんでした。内部を冒険するのではなく、何が起こっているのかを確認するのではなく、パラメーターを微調整したり、大規模なサーキットを変更したり、大規模なFPGAに切り替えたりしました」

「この理由の一部は、Pathfinderが実際に実用的に重要な例で実際に行っていることを理解することがかなり困難であるということです。現代の回路は非常に大きいため、信号は真のオンチップジャングルを形成します。」

森に入ります

「だから、私たちは本当にジャングルの個々の木を見る必要がありました」とシュリバスタバは続けました。「私は本当に木を意味します。各信号 – 回路コンポーネント間の情報を運ぶ接続は、他の信号を重ねることなく複数の宛先に到達します。FPGAルーティングは、基本的にチップの各信号に1つのツリーを構築することです。」

Pathfinderに依存している別のプロジェクトに取り組んでいる間、チームは直観に反する結果を見続けました。最初は、彼らは外部の要因を非難しました アルゴリズム 自体。最終的に、彼らは制御された例を必要としていることに気づきました。解決策が間違いなく存在し、どのパスファインダーが成功すべきかという小さな、トリッキーなケースです。

「実際の実用的な例と、実際に何が起こっているのかを理解するために、それらの多くが必要でした」とShrivastavaは説明します。 「それで、私たちは、実際の回路から小さな困難な問題を自動的に抽出するためのフレームワークを構築しました。パスファインダーがこれらとどのように苦労しているかを見ると、非常に長い間隠されていた問題を明らかにするのに役立ちました。」

パートナーシップのパワー

「このブレークスルーは、業界のサポートがなければはるかに困難だっただろう」とシュリバスタバの博士号、ミルジャナ・ストジロヴィッチは言った。アドバイザー。 「最初から、AMDのChirag RavishankarとDinesh Gaitondeと協力しました。彼らは、FPGAを商用デバイスにできるだけ近いモデルを支援し、調査結果が実際の影響を与えることを保証しました。」

フレームワークの準備ができたら、物事はすぐに動きました。チームは、パスファインダーがしばしば必要以上のルーティングツリーを構築し、重複のリスクを高めることを発見しました。問題は、木に新しい枝を作成し、追加した順序から生じました。

「振り返ってみると、これは直感的ですが、どういうわけかそれは長年にわたってほとんど気付かれませんでした」とシュリバスタバは言いました。 「私たちの最初のソリューションは簡単でした。別の注文を試して、最小のツリーになるものを選択します。実験的には、驚くほどうまくいきました。」

チームは現在、よりスケーラブルなソリューションを調査しています。 「Summer@EPFLインターンが大きく貢献していることを特に誇りに思っています。そのうちの1人であるSun Tanakaも、この論文の共著者です」とStojilovićは付け加えました。

「私たちの発見は、何百万ものFPGAがどのようにプログラムされているかを再構築し、これらの再構成可能なチップの将来の世代の設計に影響を与える可能性があります。」