Hybrid Multi-FPGA Board Evaluation by Permitting Limited Multi-Hop Routing
Tóm tắt
Multi-FPGA Boards (MFBs) have been in use for more than a decade for implementing systems requiring high performance and for emulation/prototyping of multimillion gate chips. It is important to develop an MFB architecture which can be used for emulation or prototyping of a large number of circuits. A key feature of an MFB is its routing architecture defined by its inter-Field-Programmable Gate Array (FPGA) connections. There are two types of inter-FPGA connections, namely–fixed connections (FCs) connecting a pair of FPGAs through dedicated wires and programmable connections (PCs) which connect a pair of FPGAs through a programmable switch. An architecture which has a mix of both these type of connections is called a hybrid routing architecture. It has been shown in the literature [7] that a hybrid MFB architecture is more efficient for emulation than an architecture with only one type of connections. The cost of an MFB and delay of the emulated circuit on it depends on the number of PCs used for emulation. An objective of a designer of an MFB for circuit emulation is to minimize the required number of PCs. In this paper, we describe algorithms to evaluate the requirement of PCs for many hybrid routing architectures. The requirement of PCs can be reduced if some programmable connections are replaced by a connection using only FCs by routing through FPGAs. Such a routing is called multi-hop routing. We present an optimal and a heuristic algorithm for estimation of PCs when limited number of hops through FPGAs are permitted. The unique feature of our evaluation scheme is that it is generic and treat routing architecture as a parameter. We have used benchmark circuits as well as synthetic cloned circuits for testing our algorithms. Our heuristic algorithm is very fast and gives optimal results most of the time. Our algorithms can be used for actual routing during circuit emulation.
Tài liệu tham khảo
Antonio Frangioni. Dual Ascent Methods and Multicommodity Flow Problems. Ph.D. thesis. Department of Informatica, University of Pisa, 1997.
Cormen, Leiserson and Rivest. Introduction to Algorithms. ISBN-81-203-1353-4, Prentice Hall of India Private Limited, New Delhi, 2002, Second Edition.
Ejnioui, A., and N. Ranganathan. Multi-Terminal Net Routing for Partial Crossbar-Based Multi-FPGA Systems. ACM/SIGDA International Symposium on FPGAs, 1999, pp. 176-184.
Cong, J., et al. FlowMap: An Optimal Technology Mapping Algorithm for Delay Optimization in Lookup-Table Based FPGA Designs. IEEE Transactions. on CAD, vol. 13,no. 1, pp. 1-12, 1994.
Karypis G., and V. Kumar. hMETIS* — A Hypergraph Partitioning Package Version 1.5.3. CS Department, University of Minnesota, 1998.
Hutton, M., J. P. Grossman, J. Rose, and D. Corneil. Characterization and Parameterized Random Generation of Digital Circuits. Proceedings of the DAC, Las Vegas, 1996, pp. 94-99.
M.A.S. Khalid. Routing Architecture and Layout Synthesis for Multi-FPGA Systems. Ph.D. thesis. Electrical and Computer Engineering Department, University of Toronto, Canada M5S 3G4, 1999.
Yang, S. Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. Microelect. Centre of North Carolina, January 1991.
Liu, S., M. Pedram, and A. M. Despain. A Fast State Assignment Procedure for Large FSMs. Proceedings of thirty second ACM/IEEE Design and Automation Conference, 1995.
Jain, S. C., A. Kumar, and S. Kumar. Efficient Embedding of Partitioned Circuits onto Multi-FPGA Boards. Proceedings of tenth International Conference on Field Programmable Logic and Applications FPL-2000, Villach, Austria, pp. 201-210, August 2000.
Jain, S. C., A. Kumar, and S. Kumar. Hybrid Multi-FPGA Board Evaluation by Limiting Multi-Hop Routing. Proceedings of RSP-2002 Workshop, Darmastadt, Germany, July 2002.
Jain S. C., A. Kumar, and S. Kumar. Multi-Hop Routing of Multi-Terminal Nets onto Multi-FPGA Boards. Proceedings of first IEEE International Conference on Field-Programmable Technology, FPT-2002, Chinese University Hong Kong, pp. 298-301, December 2002.
Mak, W. K., et al. On Optimal Board-Level Routing for FPGA based Logic Emulation. Proceedings of Thirty Second DAC Conference, pp. 552-556. 1995.