[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

RAT: RC Amenability Test for Rapid Performance Prediction

Published: 01 January 2009 Publication History

Abstract

While the promise of achieving speedup and additional benefits such as high performance per watt with FPGAs continues to expand, chief among the challenges with the emerging paradigm of reconfigurable computing is the complexity in application design and implementation. Before a lengthy development effort is undertaken to map a given application to hardware, it is important that a high-level parallel algorithm crafted for that application first be analyzed relative to the target platform, so as to ascertain the likelihood of success in terms of potential speedup. This article presents the RC Amenability Test, or RAT, a methodology and model developed for this purpose, supporting rapid exploration and prediction of strategic design tradeoffs during the formulation stage of application development.

References

[1]
Alexandrov, A., Ionescu, M. F., Schauser, K. E., and Scheiman, C. 1997. Loggp: Incorporating long messages into the logp model for parallel computation. J. Paral. Distrib. Comput. 44, 1, 71--79.
[2]
Allen, M. P. and Tildesley, D. J. 1987. Computer Simulation of Liquids. Oxford University Press, Oxford, UK.
[3]
Banerjee, P., Bagchi, D., Haldar, M., Nayak, A., Kim, V., and Uribe, R. 2003. Automated conversion of floating point matlab programs into fixed point FPGA based hardware design. In Proceedings of the 11th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 263--264.
[4]
Bondalapati, K. and Prasanna, V. 1999. Dynamic precision management for loop computations on reconfigurable architectures. In Proceedings of the 7th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 249--258.
[5]
Bondalapati, K. K. 2001. Modeling and mapping for dynamically reconfigurable hybrid architectures. Ph.D. thesis, University of Southern California, Los Angeles, CA.
[6]
Bosque, J. L. and Perez, L. P. 2004. HLogGP: A new parallel computational model for heterogeneous clusters. In Proceedings of the IEEE Symposium on Cluster Computing and the Grid.
[7]
Brown, S. D., Rose, J., and Vranesic, Z. G. 1993. A stochastic model to predict the routability of field-programmable gate arrays. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 12, 12, 1827--1838.
[8]
Buttari, A., Dongarra, J., Kurzak, J., Langou, J., Langou, J., Luszczek, P., and Tomov, S. 2007. High Performance Computing and Grids in Action. IOS Press.
[9]
Chang, M. and Hauck, S. 2002. Precis: A design-time precision analysis tool. In Proceedings of the 10th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM). 229--238.
[10]
Culler, D., Karp, R., Patterson, D., Sahay, A., Schauser, K. E., Santos, E., Subramonian, R., and von Eicken, T. 1993. Logp: Towards a realistic model of parallel computation. In Proceedings of the 4th ACM Symposium on Principles and Practice of Parallel Programming. 1--12.
[11]
Degalahal, V. and Tuan, T. 2005. Methodology for high level estimation of FPGA power consumption. In Proceedings of the ACM Conference on Asia South Pacific Design Automation (ASP-DAC). 657--660.
[12]
Enzler, R., Plessl, C., and Platzner, M. 2005. System-level performance evaluation of reconfigurable processors. Microprocess. Microsyst. 29, 2-3, 63--75.
[13]
Fang, W. M. and Rose, J. 2008. Modeling routing demand for early-stage FPGA architecture development. In Proceedings of the ACM Symposium on Field Programmable Gate Arrays (FPGA). 139--148.
[14]
Fortune, S. and Wyllie, J. 1978. Parallelism in random access machines. In Proceedings of the 10th ACM Symposium on Theory of Computing. 114--118.
[15]
Fu, W. and Compton, K. 2006. A simulation platform for reconfigurable computing research. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'06). 1--7.
[16]
Gaffar, A., Mencer, O., Luk, W., Cheung, P., and Shirazi, N. 2002. Floating-point bitwidth analysis via automatic differentiation. In Proceedings of the IEEE International Conference on Field-Programmable Technology (FPT). 158--165.
[17]
Grobelny, E., Bueno, D., Troxel, I., George, A., and Vetter, J. 2007. Fase: A framework for scalable performance prediction of hpc systems and applications. Simulation: Trans. Soc. Model. Simul. Int. 83, 10, 721--745.
[18]
Grobelny, E., Reardon, C., Jacobs, A., and George, A. 2007. Simulation framework for performance prediction in the engineering of rc systems and applications. In Proceedings of the Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA).
[19]
Herbordt, M. C., VanCourt, T., Gu, Y., Sukhwani, B., Conti, A., Model, J., and DiSabello, D. 2007. Achieving high performance with FPGA-based computing. IEEE Computer 40, 3, 50--57.
[20]
Maidee, P. and Bazargan, K. 2006. Defect-tolerant FPGA architecture exploration. In Proceedings of the 13th IEEE Conference on Field Programmable Logic and Applications (FPL). 1--6.
[21]
Manohararajah, V., Chiu, G. R., Singh, D. P., and Brown, S. D. 2006. Difficulty of predicting interconnect delay in a timing driven FPGA CAD flow. In Proceedings of the ACM Workshop on System-Level Interconnect Prediction (SLIP). 3--8.
[22]
Nagarajan, K., Holland, B., Slatton, C., and George, A. D. 2008. Scalable and por architecture for probability density function estimation on FPGAs. In Proceedings of the 16th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM).
[23]
Nelson, M., Humphrey, W., Gursoy, A., Dalke, A., Kal, L., Skeel, R. D., and Schulten, K. 1996. Namd---a parallel, object-oriented molecular dynamics program. Int. J. Supercomp. Appl. High Perform. Comput. 10, 4, 251--268.
[24]
Pearlman, D. A., Case, D. A., Caldwell, J. W., Ross, W. S., Thomas E. Cheatham, I., DeBolt, S., Ferguson, D., Seibel, G., and Kollman, P. 1995. Amber, a package of computer programs for applying molecular mechanics, normal mode analysis, molecular dynamics and free energy calculations to simulate the structural and energetic properties of molecules. Comput. Phys. Comm. 91, 1-3, 1--41.
[25]
Perri, S., Corsonello, P., Iachino, M. A., Lanuzza, M., and Cocorullo, G. 2004. Variable precision arithmetic circuits for FPGA-based multimedia processors. IEEE Trans. (VLSI) 12, 9, 995--999.
[26]
Quinn, H., Leeser, M., and King, L. S. 2007. Dynamo: A runtime partitioning system for FPGA-based hw/sw image processing systems. J. Real-Time Image Process. 2, 4, 179--190.
[27]
Shih, K., Balachandran, A., Nagarajan, K., Holland, B., Slatton, C., and George, A. 2008. Fast realtime lidar processing on FPGAs. In Proceedings of the Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA). Las Vegas, NV.
[28]
Singh, A. and Marek-Sadowska, M. 2002. Fpga interconnect planning. In Proceedings of the ACM Workshop on System-Level Interconnect Prediction (SLIP). 23--30.
[29]
Singh, D. P., Manohararajah, V., and Brown, S. D. 2005. Two-stage physical synthsis for FPGAs. In Proceedings of the 13th IEEE Conference on Custom Integrated Circuits. 171--178.
[30]
Smith, M. and Peterson, G. 2005. Parallel application performance on shared high performance reconfigurable computing resources. Perform. Eval. 60, 107--125.
[31]
Steffen, C. 2007. Parameterization of algorithms and FPGA accelerators to predict performance. Reconfigurable System Summer Institute (RSSI). Urbana, IL.
[32]
Tschoke, S., Lubling, R., and Monien, B. 1995. Solving the traveling salesman problem with a distributed branch-and-bound algorithm on a 1024 processor network. In Proceedings of the Symposium on Parallel Processing.
[33]
Valiant, L. G. 1990. A bridging model for parallel computation. Comm. ACM 33, 8, 103--111.
[34]
Wang, X., Braganza, S., and Leeser, M. 2006. Advanced components in the variable precision floating-point library. In Proceedings of the Conference on Field-Programmable Custom Computing Machines (FCCM).
[35]
Xu, M. and Kurdahi, F. 1999. Accurate prediction of quality metrics for logic level design targeted towards lookup-table-based FPGA's. IEEE Trans. VLSI Syst. 7, 4, 411--418.

Cited By

View all
  • (2019)XPPEProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3288756(727-732)Online publication date: 21-Jan-2019
  • (2019) SpExSim: assessing kernel suitability for C-based high-level hardware synthesisThe Journal of Supercomputing10.1007/s11227-017-2101-z75:8(4062-4077)Online publication date: 1-Aug-2019
  • (2017)Optimizing FPGA Performance, Power, and Dependability with Linear ProgrammingACM Transactions on Reconfigurable Technology and Systems10.1145/307975610:3(1-23)Online publication date: 29-Jun-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Reconfigurable Technology and Systems
ACM Transactions on Reconfigurable Technology and Systems  Volume 1, Issue 4
January 2009
161 pages
ISSN:1936-7406
EISSN:1936-7414
DOI:10.1145/1462586
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2009
Accepted: 01 October 2008
Revised: 01 September 2008
Received: 01 May 2008
Published in TRETS Volume 1, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. FPGA
  2. formulation methodology
  3. performance prediction
  4. reconfigurable computing
  5. strategic design methodology

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)1
Reflects downloads up to 04 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2019)XPPEProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3288756(727-732)Online publication date: 21-Jan-2019
  • (2019) SpExSim: assessing kernel suitability for C-based high-level hardware synthesisThe Journal of Supercomputing10.1007/s11227-017-2101-z75:8(4062-4077)Online publication date: 1-Aug-2019
  • (2017)Optimizing FPGA Performance, Power, and Dependability with Linear ProgrammingACM Transactions on Reconfigurable Technology and Systems10.1145/307975610:3(1-23)Online publication date: 29-Jun-2017
  • (2016)A Framework for Evaluating and Optimizing FPGA-Based SoCs for Aerospace ComputingACM Transactions on Reconfigurable Technology and Systems10.1145/288840010:1(1-29)Online publication date: 24-Sep-2016
  • (2015)Reconfigurable Computing ArchitecturesProceedings of the IEEE10.1109/JPROC.2014.2386883103:3(332-354)Online publication date: Mar-2015
  • (2015)A Parallelizing Matlab Compiler Framework and Run Time for Heterogeneous SystemsProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.51(232-237)Online publication date: 24-Aug-2015
  • (2014)Mission control: A performance metric and analysis of control logic for pipelined architectures on FPGAs2014 International Conference on ReConFigurable Computing and FPGAs (ReConFig14)10.1109/ReConFig.2014.7032539(1-6)Online publication date: Dec-2014
  • (2014)Performance modeling of pipelined linear algebra architectures on FPGAsComputers and Electrical Engineering10.1016/j.compeleceng.2013.10.01540:4(1015-1027)Online publication date: 1-May-2014
  • (2013)Performance modeling for FPGAsInternational Journal of Reconfigurable Computing10.1155/2013/4280782013(7-7)Online publication date: 1-Jan-2013
  • (2013)DynafuseProceedings of the ACM/SIGDA international symposium on Field programmable gate arrays10.1145/2435264.2435300(201-210)Online publication date: 11-Feb-2013
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media