チャネルルーティング

図1：チャネル配線問題。チャネルの上下の番号付きピンは接続されなければなりません。チャネルの左右に指定されたネットは、チャネルのその端まで移動させなければなりません。

チャネル配線は、集積回路の配線の一種です。通常、2層の相互接続層を使用し、チャネルの上部と下部にある指定されたピンを接続する必要があります。指定されたネットはチャネルの左右にも配線する必要がありますが、配線の順序は任意です。チャネルの高さは指定されません。必要な高さはルータによって計算されます。

図2: 上記のチャネルルーティング問題に対する解決策。解決策は一つではなく、これは多くの可能性のうちの1つにすぎません。

チャネルの密度は、チャネル内の各 x について定義され、そのxにおける垂直線の左右両側に現れるネットの数です。最大密度は、チャネルの高さの下限値です。「循環制約」は、少なくとも2つの列において、2つのピンが同じ列（ただし順序は異なる）に現れる場合に発生します。図示の例では、ネット1と3が循環制約の影響を受けています。これは、例のネット1に示されているように、「ドッグレッグ」構造によってのみ解決できます。

チャネルルータは集積回路用配線技術の初期の形態の一つであり^{[ 1 ]}、長年にわたり広く用いられ、YACR ^{[ 2 ]}はおそらく最もよく知られているプログラムである。しかし、現代のチップは2層以上の相互接続層を備えている。チャネルルータをより多くの層に拡張する試みがなされたものの^{[ 3 ] 、 [ 4 ]、}この手法はピンが移動できないセル上配線ではうまく機能しなかったため、あまり普及することはなかった。近年では、エリアルータが一般的に主流となっている。

参照

• 順列グラフ

参考文献

1. Feller, A. 1976.低コストで迅速なランダムロジックカスタムLSIデバイスの自動レイアウト. 第13回設計自動化会議議事録（サンフランシスコ、カリフォルニア州、米国、1976年6月28～30日）. DAC '76. ACM Press、ニューヨーク、NY、79-85.
2. Reed, J., Sangiovanni-Vincentelli, A., Santomauro, M.;新しいシンボリックチャネルルータ: YACR2、Computer-Aided Design of Integrated Circuits and Systems、IEEE Transactions on、Vol.4、Iss.3、1985年7月、ページ: 208- 219
3. Braun, D., Burns, J., Davadas, S., Ma, HK, Mayaram, K., Romeo, F., Sangiovanni-Vincentelli, A. 1986. Chameleon: 新しい多層チャネルルータ. 第23回ACM/IEEE設計自動化会議（米国ネバダ州ラスベガス）議事録. Annual ACM IEEE Design Automation Conference. IEEE Press, Piscataway, NJ, 495-502.
4. Fang, S., Feng, W., Lee, S. 1992. 「多層チャネル配線問題への新たな効率的アプローチ」第29回ACM/IEEE設計自動化会議議事録（カリフォルニア州アナハイム、米国、1992年6月8日～12日）。ACM IEEE設計自動化会議年次会議。IEEE Computer Society Press、カリフォルニア州ロサンゼルス、579-584ページ