配線設計支援方法、配線設計支援プログラム、及び配線設計支援装置

【課題】バスの配線経路の設計精度を向上させること。
【解決手段】コンピュータが、一以上の配線層を含む配線領域に対して、それぞれ図形によって表現された複数のバスの経路を前記バス間で交差しないように生成する配線プラン生成手順と、前記バスごとに、当該バスが接続される部品内からの当該バスの所属ネットごとの配線の引き出しの可否の検証を行う妥当性判定手順と、前記妥当性判定手順によって全ての前記所属ネットが引き出せることが確認された前記バスの前記所属ネットを示す図形を前記配線領域に記録する配線プラン確定手順とを実行し、前記妥当性判定手順によって少なくとも一部の前記所属ネットが引き出せないことが確認された前記バスについて前記配線プラン生成手順を再実行する。

【特許請求の範囲】
【請求項１】
コンピュータが、
一以上の配線層を含む配線領域に対して、それぞれ図形によって表現された複数のバスの経路を前記バス間で交差しないように生成する配線プラン生成手順と、
前記バスごとに、当該バスが接続される部品内からの当該バスの所属ネットごとの配線の引き出しの可否の検証を行う妥当性判定手順と、
前記妥当性判定手順によって全ての前記所属ネットが引き出せることが確認された前記バスの前記所属ネットを示す図形を前記配線領域に記録する配線プラン確定手順とを実行し、
前記妥当性判定手順によって少なくとも一部の前記所属ネットが引き出せないことが確認された前記バスについて前記配線プラン生成手順を再実行する配線設計支援方法。
【請求項２】
前記妥当性判定手順は、
前記部品の少なくとも各ピン、各水平ピン間、各垂直ピン間、及び各対角ピン間を前記所属ネットの配線のボトルネック箇所とし、前記各ボトルネック箇所に水平ピン間、垂直ピン間、又は対角ピン間に応じた配線容量を付与するボトルネック配置手順と、
前記ボトルネック箇所ごとに入り口ノード及び出口ノードの二つのノードを生成するノード生成手順と、
それぞれの前記ボトルネック箇所について、同一の前記ボトルネック箇所内の前記入り口ノードから前記出口ノードへの有向枝を生成し、垂直又は水平方向に隣接する前記ボトルネック箇所間において一方の前記出口ノードから他方の前記入り口ノードへの有向枝を相互に生成し、前記対角ピン間のボトルネック箇所と当該対角ピン間の全ての斜め隣の前記ボトルネック箇所との間において一方の前記出口ノードから他方の前記入り口ノードへの有向枝を相互に生成し、生成された全ての有向枝に、当該有向枝によって接続される前記ノードが属する前記ボトルネック箇所に付与された前記配線容量の最小値を枝容量として付与する有向グラフ生成手順と
前記所属ネットごとに、配線の引き出し対象のピンに対応するボトルネック箇所の前記入り口ノードから配線の出口に係る前記ボトルネック箇所の前記出口ノードまでの間において、１以上の前記枝容量が付与された前記有向枝を使用して最短経路を探索する経路探索手順と、
探索された経路に使用された各有向枝に、経路に使用された使用回数を付与する使用回数付与手順と、
前記経路探索手順によって最短経路が探索された所属ネットの数に基づいて前記バスの配線の成否を判定する配線成否判定手順とを有し、
前記経路探索手順は、前記使用回数が前記枝容量を超えないように前記最短経路を探索する請求項１記載の配線設計支援方法。
【請求項３】
前記妥当性判定手順は、
前記ボトルネック箇所の相対的な位置関係において外周に位置し前記使用回数が１以上の前記有向枝を前記入り口ノードから前記出口ノードへの有向枝として有する前記ボトルネック箇所の該出口ノードから前記引き出し対象のピンに対応するボトルネック箇所の出口ノードまでを前記使用回数が１以上の有向枝に沿って遡ることによって形成される経路を配線の概略経路として確定する概略経路確定手順を有し、
前記概略経路確定手順は、遡られた前記有向枝の前記使用回数を当該有向枝の遡りの回数に応じて減ずる請求項２記載の配線設計支援方法。
【請求項４】
前記概略経路確定手順は、前記外周に位置し前記使用回数が１以上の前記有向枝を前記入り口ノードから前記出口ノードへの有向枝として有する前記ボトルネック箇所が複数有るときは、前記外周における一定方向に従って、遡りを開始する前記ボトルネック箇所を順番に選択し、前記一定方向に応じて、遡りにおいて優先させる前記有向枝を選択する請求項３記載の配線設計支援方法。
【請求項５】
前記妥当性判定手順は、前記経路探索手順より前に、
前記配線の引き出しの可否の検証対象とされている第一の前記バス以外の第二の前記バスの所属ネットの引き出し対象のピンのピン間の第一の前記ボトルネック箇所、前記第二のバスの前記配線の出口の第二の前記ボトルネック箇所、及び前記第一のボトルネック箇所と前記第二のボトルネック箇所とを接続する前記ボトルネック箇所の前記配線容量を一時的に０とする防護壁生成手順を有する請求項２乃至４いずれか一項記載の配線設計支援方法。
【請求項６】
コンピュータに、
一以上の配線層を含む配線領域に対して、それぞれ図形によって表現された複数のバスの経路を前記バス間で交差しないように生成する配線プラン生成手順と、
前記バスごとに、当該バスが接続される部品内からの当該バスの所属ネットごとの配線の引き出しの可否の検証を行う妥当性判定手順と、
前記妥当性判定手順によって全ての前記所属ネットが引き出せることが確認された前記バスの前記所属ネットを示す図形を前記配線領域に記録する配線プラン確定手順とを実行させ、
前記妥当性判定手順によって少なくとも一部の前記所属ネットが引き出せないことが確認された前記バスについて前記配線プラン生成手順を再実行する配線設計支援プログラム。
【請求項７】
一以上の配線層を含む配線領域に対して、それぞれ図形によって表現された複数のバスの経路を前記バス間で交差しないように生成する配線プラン生成手段と、
前記バスごとに、当該バスが接続される部品内からの当該バスの所属ネットごとの配線の引き出しの可否の検証を行う妥当性判定手段と、
前記妥当性判定手段によって全ての前記所属ネットが引き出せることが確認された前記バスの前記所属ネットを示す図形を前記配線領域に記録する配線プラン確定手段とを実行し、
前記妥当性判定手段によって少なくとも一部の前記所属ネットが引き出せないことが確認された前記バスについて前記配線プラン生成手段を再実行する配線設計支援装置。

【図１】