(54.236.62.49) 您好!臺灣時間:2021/03/06 11:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張育蒼
研究生(外文):Yu-Tsang Chang
論文名稱:以現場可程式化邏輯閘陣列結構導向同步放置與全域繞線的測度法
論文名稱(外文):An Architecture-Driven Metric for simultaneous Placement and Global Routing for FPGAs
指導教授:張耀文張耀文引用關係
指導教授(外文):Yao-Wen Chang
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1999
畢業學年度:87
語文別:英文
論文頁數:68
中文關鍵詞:現 場 可 程 式 化 閘 陣 列放 置全 域 繞 線測 度 法
外文關鍵詞:FPGAPlacementGlobal RoutingMetric
相關次數:
  • 被引用被引用:0
  • 點閱點閱:189
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
由於其低設計成本、使用者可程式化和較短的設計週期,現場可程式化邏輯閘陣列 (FPGAs) 已經成為一種很普及的邏輯電路設計方法。現場可程式化邏輯閘陣列的繞線資源 (routing resources) 是由導線段 (wire segments) 及可程式化開關 (programmable switches) 所組成; 再者,為了同時增進電路效能及保有合理的可繞度,現場可程式化邏輯閘陣列的繞線軌道 (routing tracks) 通常會由不同長度的導線段所組成。現場可程式化邏輯閘陣列的繞線動作乃是藉由控制導線間的可程式化開關來完成導線段之間的連通。可程式化開關有很高的電阻與電容,以致於會導致較大的訊號延遲。在過去的文獻顯示:電路在做繞線時,所使用的開關總數 (而非導線段的總長度) 對於控制繞線延遲 (routing delay) 與繞線成本 (cost) 的影響最大。所以,在現場可程式化閘陣列的繞線中,電路做繞線時使用的開關數總並不一定與繞線時使用的導線段長度成正比。
由於分段式繞線結構 (segmented architecture),傳統測量繞線成本 (如導線段總長,訊號延遲時間,通道阻塞程度等等) 都只是依據在幾何最短距離(geometric distance) 和 (或) 通道疏密度 (channel density) ,這樣子的測度方式對於現場可程式化邏輯閘陣列並不準確。再者,繞線通道的通道阻塞程度應該是依據各個不同長度的次通道 (subchannel) 可使用導線段,而不是只去計算整個通道的疏密度。在過去的所做過放置 (placement) 與全域繞線 (global routing) 的研究文獻中,他們通常都只有考慮單一長度的導線段。為了充分發揮分段式結構以及利用各種長度的繞線軌道,我們提出了一個以現場可程式化邏輯閘陣列結構為導向的測度法 (metric) 去同步放置與全域繞線。這個新的測度法考慮了目前仍可使用的各種長度次通道內導線段與其長度資源去將繞線成本最佳化。為了要去探索我們所提出新測度法的效用,我們將新測度法與傳統的測度法分別應用到同步放置與全域繞線的演算法中,做放置與全域地繞 SEGA 測試電路 (benchmark circuits) 。然後,將其各自全域繞線之後的結果再分別餵入 SEGA 細部繞線器 (detailed router) 中 (因為SEGA 細部繞線器可以考量分段式繞線結構) 去得到最後的繞線結果。在實驗中,我們將所提出的結構導向的新測度與傳統測度法分別應用在近似 Xilinx XC4000E, XC4000EX與 Lucent ORCA2C的商業用現場可程式化邏輯閘陣列結構上面。實驗結果顯示比之前的傳統測度法在所使用的繞線軌道數目 (面積) 、最大線段延遲時間、平均線段延遲時間方面各平均地減低 (改進) 了7.8%, 22.4%, 20.1%。

Due to their low prototyping cost, user programmability and short turnaround time, Field Programmable Gate Arrays (FPGAs) have become a very popular design style for ASIC applications. FPGA routing resources typically consist of wire segments and programmable switches; to improve circuit performance and maintain reasonable routability simultaneously,
FPGA routing tracks usually consist of wire segments with a versatile set of lengths. Routing in FPGAs is performed by programming the switches to make connections between wire segments. The switches usually have high resistance and capacitance, and thus incur significant delays. Researchers have shown that the number of segments (i.e. number of switches used), instead of geometric distance, travelled by a net is the most crucial factor in controlling the routing delay and cost in an FPGA. Thus, in FPGA routing, the number of switches used by a signal is not necessarily proportional to the
wirelength of the signal.
Due to the segmented routing architectures, the traditional measure of wiring cost (wirelength, delay, congestion, etc)
based on geometric distance and/or channel density is no longer accurate for FPGAs. Further, the congestion information of a routing channel shall be measured by the available segments of specific lengths, instead of the density in a whole channel alone. Previous work often considers only unit-length wire segments during placement and global routing
phase. To remedy the deficiency, we propose an architecture-driven metric for simultaneous FPGA placement
and global routing in this thesis. The new metric considers the available segments and
their lengths to optimize the wiring cost for placement and global routing. To explore the effects of our new metric on routing solutions, we incorporate the architecture-driven and traditional metrics into a simultaneous placement and global routing algorithm to place and globally route the SEGA benchmarks. The global routing results generated from each metric are then fed into SEGA detailed router (which can consider the segmented routing architecture) to
obtain the final routing solutions. Experiments show that the new metric results in
respective average reductions of 7.8\%, 22.4\%, and 20.1\% in the number of tracks used (area), maximum net delay, and average net delay based on the Xilinx XC4000E-like, XC4000EX-like, and Lucent ORCA2C-like architectures, compared with the traditional metric of geometric distance and channel density.

Chapter 1. Introduction
1.1 What is an FPGA
1.2 Implementation Process of an FPGA Design
1.3 Symmetric-Array Based FPGA Architectures
1.4 Placement Strategies
1.5 Routing Strategies
1.6 Motivation
1.7 Previous Work
1.7.1 FPGA Placer and Global Router
1.7.2 FPGA Detailed Router
1.8 Our Contributions
Chapter 2. Preliminaries
2.1 Segmentation Architecture
2.2 Segmentation tradeoffs between timing and routability
2.3 Problem Specification
Chapter 3. The Architecture-Driven Metric and Simultaneous Placement and Global Routing Algorithm
3.1 Overview
3.2 The New Architecture-Driven Metric
3.2.1 Our New Architecture-Driven Metric
3.2.2 The Traditional Metric
Chapter 4. Experiments and Results
4.1 Benchmark Preparation
4.2 Detailed Routing Results
Chapter 5. Concluding Remarks
5.1 Conclusion
5.2 Future Work
Appendix
Appendix A. APR User's Manual
A.1 Overview
A.2 Compiling APR
A.3 File Formats
A.3.1 Circuit Netlist (.net) Format
A.3.2 FPGA architecture description
A.3.3 Placement File Format
A.3.4 Global Routing File Format
Bibliography

M. J. Alexander and G.Robins, ``An Architecture Independent Unified Approach to FPGA Routing,'' in Proc. of ACM/SIGDA Physical Design Workshop, 1994.
M. Alexander and G. Robins, ``New performance-driven FPGA routing algorithms,'' in Proc. ACM/IEEE Design Automation Conf., San Francisco, CA, pp. 562-567, June 1995.
M. J. Alexander, J. P. Cohoon, J. L. Ganley, G. Robins, ``Performance-Oriented Placement and Routing for Field-Programmable Gate Arrays,'' Proc.~EuroDAC, pp. 80--85,1995
M. A. Breuer, ``A class of min-cut placement algorithm,'' in Proc. ACM/IEEE Design Automation Conf., pp. 284--290, 1977.
V. Betz and J. Rose, ``VPR: A New Packing, Placement and Routing Tool for FPGA Research,'' Seventh International Workshop on Field-Programmable Logic and Applications, London, UK, 1997, pp. 213 - 222.
V. Betz and J. Rose, ``Directional Bias and Non-Uniformity in FPGA Global Routing Architectures,'' Proc. IEEE International Conference on Computer Aided Design San Jose, CA, 1996, pp. 652 - 659.
S. D. Brown, J. Rose, and Z. G. Vranesic, ``A detailed router for field-programmable gate arrays,'' in Proc. IEEE International Conference on Computer Aided Design, pp. 382--385, Nov. 1990.
S. D. Brown, J. Rose, and Z. G. Vranesic, ``A detailed router for field-programmable gate arrays,'' in IEEE Trans. Computer-Aided Design, vol. 11, pp. 620--628, May 1992.
S. Brown, G. Lemieux, and M. Khellah,
``Segmented Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays'', Journal of VLSI Design, 4(4), pp. 275--291, 1996.
Y. -W. Chang, S. Thakur, K. Zhu, and D. -F. Wong, ``A new global routing algorithm for FPGAs,'' in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, pp. 380--385, San Jose, CA, Nov. 1994.
Y.-W. Chang, D. F. Wong, and C. K. Wong, ``FPGA global routing based on a new congestion metric,'' Proceedings of IEEE International Conference on Computer Design (ICCD) , pp. 372--378, Austin, TX, Oct. 1995.
C. -D. Chen, Y. -S. Lee, C. -H. Wu, and Y. L. Lin, ``TRACER-fpga: a router for RAM-based FPGAs,'' in IEEE Trans. Computer-Aided Design, vol. 14, no. 3, pp. 371--374, Mar. 1995.
C. E. Cheng, ``RISA: Accurate and Efficient Placement Routability Modeling,'' in IEEE/ACM Design Automation, pp. 690--695, 994.
T.H. Cormem, C.E. Leiserson, and R.L. Rivest, ``Introduction to Algorithms,'' The MIT Press, 1990.
E. W. Dijkstra, ``A Note on Two Problems in Connection With Graphs,'' in Numerische Mathematik, 1(1959), pp. 269--271.
A. E. Dunlop and B. W. Kernighan, ``A Procedure for Placement of Standard Cell VLSI Circuit", IEEE Transactions on CAD, pp. 218-225, 1985
C. Ebeling, L. McMurchie, S. A. Hauck and S. Burns, `` Placement and Routing Tools for Triptych FPGA,'' IEEE Trans. on VLSI, pp.473-482, Dec 1995
B. Fallah and J. Rose, ``Timing-Driven Routing Segment Assignment in FPGAs,'' in Canadian Conference on VLSI, 1992.
J. Frankle, ``Iterative and Adaptive Slack Allocation for Performance-Driven Layout and FPGA Routing,'' in Proc. 29th
ACM/IEEE Design Automation Conference, pp. 536--542, 1992.
Hanan, Kurtzberg, ``Placement techniques", Design Automation of Digital Systems, pp. 213-282, 1972.
M. Khellah, S. Brown, and Z. Vranesic, ``Modelling routing delays in SRAM-based FPGAs,'' Proc.~Canadian Conf.~on VLSI, 1993.
E. S. Kuh and M. Marek-Sadowska, ``Global routing,'' in Layout Design and Verification, T. Ohtsuki, Ed. Amsterdam, Netherlands: North-Holland, 1985.
U. Lauther, ``Top-down Hierarchical Global Routing for Channelless Gate Arrays Based on Linear Assignment,'' in Proc. of IFIP VLSI87, 1987, pp. 109--120.
C. T. Lee, ''An algorithm for path connections and its applications,'' in IRE Trans. Electron. Compute., vol. EC-10, pp. 346--365, Sep. 1961
Y. -S. Lee and C. -H. Wu, ``A performance and routability driven router for FPGAs considering path delay,'' in Proc. ACM/IEEE Design Automation Conf., pp. 557--561, San Francisco, CA, June 1995.
G. Lemieux and S. Brown, ``A Detailed Router for Allocating Wire-Segments in FPGAs,'' in ACM Physical Design Workshop, California, April 1993.
G. G. Lemienx, S. D. Brown and D. Vranesic, ''On two-step routing for FPGAs,'' in Proc. ACM International Symposium on Physical Design, pp. 60--66, Napa Valley, April 1997.
Lucent Technologies Inc., ORCA OR2CxxA (5.0 V) and OR2TxxA (3.3 V) Series Field-Programmable Gate Arrays, Aug.~1996.
S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, ''Optimization by Simulated Annealing,'' in Proc. Science, pp. 671--680, May 13, 1983.
L. McMurchie and C. Ebeling, ``Pathfinder: A Negotiation-Based Performance-Driven Router for FPGAs,'' ACM/SIGDA International Symposium on FPGAs, pp. 111--117, 1995.
Sudip K. Nag and Rob A. Rutenbar, ``Performance-Driven Simultaneous Place and Route for Island-Style FPGAs,''
In International Conference on Computer-Aided Design. pp.332-338, IEEE/ACM, 1995
Quinn, Jr, and Breuer, ``A force directed component placement procedure for printed circuit boards", IEEE Transactions on CAD, 1979.
S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor, ``The Rectilinear Steiner Arborescence Problem,'' in Algorithmica, 1992, pp. 277--288.
Y. Saab. ``A Fast Clustering-based Min-cut Placement Algorithm with Simulated-annealing Performance,'' VLSI Design: An International Journal of Custom-Chip Design, Simulation, and Testing, pp 5(1):37-48, 1996
K. Shahookar and P. Mazumder. ``VLSI Cell Placement Techniques,'' ACM Computing Surveys, pp. 23(2):143-220, June 1991
N. Sherwani, Algorithms for VLSI Physical Design Automation, 2nd Ed., Kluwer Academic Pub., 1995.
Y. C. Sun, T. C. Wang, C. K. Wong, and C. L. Lin, ``Routing for Symmetric FPGAs and FPICs,'' in IEEE Trans. Computer-Aided Design, vol. 15, no. 1, pp. 20--31, Jan. 1997.
N. Togawa, M. Sato, and T. Ohtsuki, ``Maple: A Simultaneous Technology Mapping Placement, and Global Routing Algorithm for Field-Programmable Gate Arrays,'' Proc.~of ICCAD, pp.156--163, 1994.
N. Togawa, M. Sato, and T. Ohtsuki, ``Simultaneous Placement, and Global Routing Algorithm for FPGAs,'' Proc.~of ISCAS, pp.483--486, 1994.
S. D. Brown, R. J. Francis, J. Rose, and Z. G. Vranesic, Field-Programmable Gate Arrays, Kluwer Academic Publishers,
Boston, MA, 1992.
Y.-L. Wu and M. Marek-Sadowska, ``Graph Based Analysis of FPGA routing,'' in Proc. of Euro-DAC, pp. 104--109, 1994.
Xilinx Inc., The Programmable Logic Data Book, 1996.
K. Zhu and D. F. Wong, ``Switch Bound Allocation for Maximizing Routability in Timing-Driven Routing of FPGA's,''
IEEE Trans. on CAD, vol. 17, no. 4, pp.316--323, Apr.~1998.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔