3D LineExplore: 多層PCBの幾何学的配線のための3Dライン探索法

あらゆる機器の内部にある回路基板のための賢い配線

スマートフォン、ノートパソコン、車には、チップ間で信号を運ぶ銅の小さな高速道路が隠れています。電子機器がより多くの部品をより小さな空間に詰め込むにつれて、プリント基板（PCB）上にこれらの微視的な「道路」を描く作業は、ハードウェア設計で最も難しい工程の一つになっています。本論文は、これらの経路を三次元で自動的に計画する新しい手法を提示し、設計の高速化、エラーの減少、そして日常的に使うデバイスの性能向上を約束します。

従来の配線が直面する壁

現在の自動PCBルータは、多くがチェス盤のようなグリッドを前提に考えます：基板を小さな正方形に区切り、A*などのアルゴリズムでピン間の最安経路を探索します。これは機能しますがトレードオフがあります。グリッドが粗いと経路が不正確になり設計ルールに違反する恐れがあり、非常に細かいと探索空間が爆発して特に複数層基板での遅延が致命的になります。多層ではトレースがビアと呼ばれる小さな穴を介して層を移るためです。グリッドレス手法は人工的な格子を避け形状に直接作用しますが、これまでは主に平面（2次元）レイアウトに限られ、真の3次元多層配線を効率的に扱うのが難しい状況でした。

安全な経路を探る3D“レーダー”

著者らは3D LineExploreを導入します。これは多層にわたる連続空間で直接動作するグリッドレスの配線手法です。その中核は「レーダー」に着想を得た走査アルゴリズムです。すべてのグリッドセルを調べる代わりに、現在点の周囲の局所近傍を見渡し、部品や既に配置された配線といった近傍の障害物を特定し、それらの形状から重要な角点を収集します。これらから、配線が安全に通れる有望な“探索点”のコンパクトな集合を提案します。もし直近の近傍から経路が得られない場合は走査半径を拡大しますが、必要なときだけ拡大します。この選択的なプロービングにより探索は焦点を保ち、冗長な探索を避け、ターゲット点を層間に投影したり、ビア候補を表す特別な探索点を追加したりすることで自然に多層へ拡張します。

コストで最良経路を導く

探索点が確定すると、第二のモジュールが実際の経路を選びます。この障害回避ヒューリスティック経路アルゴリズムはガイド付き探索のように振る舞います：既に移動した距離、各候補点までの距離、別の層へドリルするビアの追加コスト、目的地までの直線推定距離を評価します。これらの要素を単一のコスト関数と優先度付きキューで用いることで、アルゴリズムは常に最も有望な次の一歩を展開します。内部では、フルグリッドを敷くことなく可能な移動のスパースなグラフが構築されます。ターゲットピンに到達すると、保存された前駆ノードへのリンクをたどって開始点まで復元され、障害物を避けつつ層を切り替えるのが価値あるときだけ行う完全な3D経路が得られます。

複雑なネットの整理と線の研ぎ澄まし

実際のPCBは通常、単一のピン対だけを接続するわけではありません。多くのネットは3本以上のピンを結び、デッドエンドや絡み合った経路を生みやすいです。3D LineExploreはこれらのケースに対し、多ピンのネットを最近傍ピン対の列に分解して一つずつ配線し、失敗があれば修復することで対処します。もし計画どおりに接続できない場合、アルゴリズムは近くの既に接続済みピンへの代替結合を探し、最小限の追加配線でネットを復元します。すべての接続が確保された後、後処理段階で配線の物理形状を改善します。多くの高速設計では鋭い直角よりも約135度の折れを好みます。これは製造を容易にし電気的反射を減らすためです。著者らは幾何学的な“平行四辺形”調整を導入し、ポリライン区間を滑らかで135度制約を満たす経路へと変形しつつ、すべての接続を保持し新たな衝突を避けます。

新手法の実地テスト

チームは11個の公開ベンチマーク基板（単純なものから複雑なものまで）で3D LineExploreを評価し、FreeRouting、ELECTRA、DeepPCB、および最適化された3D A*アルゴリズムなどの商用・学術ツールと比較しました。これらのケース全体で、新手法は必要なピン対の約98%を接続することに成功し、既存のルータに匹敵するかそれを上回りました。より注目すべきは総配線長が平均で短く、ある主要な商用ツールより約15%短かった点で、信号遅延や電力損失の低減に寄与します。混雑を回避するためにビアをやや多用することもありましたが、このトレードオフは空間利用を改善し各層での混雑を軽減しました。速度面では、ワンパス設計と適応的局所走査の組み合わせにより多くの設計が数秒で完了し、ある設定では適応探索により全基板を力任せに探索する方法と比べて配線時間が90%以上短縮される一方で配線長はわずかに増加するにとどまりました。

将来の電子機器にとっての意義

要するに、3D LineExploreはPCB設計者に対し、熟練者が行うような配線のやり方を多層基板で可能にします：局所を見渡し、有用な候補経路だけを選び、短い経路と層を変えるコストを秤にかけるのです。細かなグリッドの重いオーバーヘッドを避けつつ、厳しい設計ルールを守り、製造可能な滑らかなトレースを生成します。電子機器がますます複雑化・小型化するなかで、将来の機械学習による誘導と組み合わせると、このようなアプローチは自動配線をより高速かつ信頼性の高いものにし、新世代の機器がより早く市場に出て効率的に動作するのを助ける可能性があります。

引用: Sun, N., Zhang, J., Xu, N. et al. 3D LineExplore: a 3D line exploration method for multi-layer PCB geometric routing. Sci Rep 16, 6588 (2026). https://doi.org/10.1038/s41598-026-36925-0

キーワード: PCB配線, 多層基板, グリッドレスアルゴリズム, 電子設計自動化, 3D経路計画