Amaterous:経路選択法による高性能並列ルータ  [in Japanese] Amaterous : A Parallel Wire Router with Path Selection Method  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

本論文では,経路選択法による新たな並列ルータ{it Amaterous}を提案する.これまでに提案された多くの並列配線手法と同様に,Amaterousには大域および詳細の2つの配線フェーズがある.しかし,従来手法での並列化ボトルネックである詳細配線結果の大域配線へのフィードバックがAmaterousでは除去されており,2つの配線フェーズが独立にかつ効率的に並列化されている.このフィードバック除去のために,Amaterousではc-pathと呼ぶ配線容量を最大化する候補経路を,大域配線に先だってあらかじめ配線する.大域配線では,このc-pathの中からいくつかを選択する経路選択法により各ネットの大域経路を決定する.詳細配線では,選択されたc-pathを変形することによって最終的な詳細経路を得るため,大域経路に対応する詳細経路が必ず得られることが保証される.したがって詳細配線の結果を大域配線が知る必要はなく,詳細から大域へのフィードバックを除去することができる.我々はAmaterousを16ノードのPCクラスタに実装し,3種のMCMベンチマークによる性能評価を行った.その結果,最大12倍の台数効果が得られ,Amaterousの効率性が実証された.また高性能並列ルータの1つであるAmon2に比べて,Amaterousは1.2?3.6倍高速であることも明らかになった.This paper proposes a new parallel wire routing algorithm named {\emAmaterous}. As many successful parallel wire routers, Amaterous has globaland detailed routers, but the feedback from the detailed to the global isremoved so that both routers are parallelized efficiently and independently.For this feedback removal, Amaterous has an additional routing phase named{it capacity path (c-path) router} that draws all the possible paths ineach rectangular region of each routing layer prior to the global routing.Since the global router picks c-paths to form the global path of a net, itis assured that the global path is always converted successfully to itsdetailed counterpart which the detailed router generates from the c-paths.Therefore the global router does not need to know the result of the detailedrouting and thus the feedback from detailed to global is removed.We implemented Amaterous on a 16-node PC cluster and measured its performancewith three MCM benchmarks. The result shows up to 12 fold speedup provingthe efficiency of our algorithm. It is also shown that Amaterous is 1.2 to3.6 times as fast as a state-of-art parallel router Amon2.

This paper proposes a new parallel wire routing algorithm named Amaterous. As many successful parallel wire routers, Amaterous has global and detailed routers, but the feedback from the detailed to the global is removed so that both routers are parallelized effciently and independently. For this feedback removal, Amaterous has an additional routing phase named capacity path (c-path) route that draws all the possible paths in each rectangular region of each routing layer prior to the global routing. Since the global router picks c-paths to form the global path of a net, it is assured that the global path is always converted successfully to its detailed counterpart which the detailed router generates from the c-paths. Therefore the global router does not need to know the result of the detailed routing and thus the feedback from detailed to global is removed. We implemented Amaterous on a 16-node PC cluster and measured its performance with three MCM benchmarks. The result shows up to 12 fold speedup proving the efficiency of our algorithm. It is also shown that Amaterous is 1.2 to 3.6 times as fast as a state-of-art parallel router Amon2.

Journal

  • Transactions of Information Processing Society of Japan

    Transactions of Information Processing Society of Japan 42(4), 732-744, 2001-04-15

    Information Processing Society of Japan (IPSJ)

References:  16

Cited by:  5

Codes

  • NII Article ID (NAID)
    110002725766
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    5750238
  • NDL Source Classification
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL Call No.
    Z14-741
  • Data Source
    CJP  CJPref  NDL  NII-ELS  IPSJ 
Page Top