research-article

A Multiple-FPGA parallel computing architecture for real-time simulation of soft-object deformation

Authors:

Behzad Mahdavikhah,

Shahin Sirouspour,

Nicola NicoliciAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 4

Article No.: 81, Pages 1 - 23

https://doi.org/10.1145/2560031

Published: 10 March 2014 Publication History

Abstract

Hardware-based parallel computing is proposed for acceleration of finite-element (FE) analysis of linear elastic deformation models. An implementation of the Preconditioned Conjugate Gradient algorithm on N Field Programmable Gate Array (FPGA) devices solves the large linear system of equations arising from the FE discretization. The system employs a large number of customized fixed-point computing units with a high-throughput memory architecture. An implementation of this scalable architecture on four Altera EP3SE110 FPGA devices yields a peak performance of 604 Giga Operations per second. This enables haptic simulation of a 3-dimensional deformable object of 21000 elements at an update rate of 400Hz.

References

[1]

A. Alsaraira, I. Brown, R. McColl, and F. Lim. 2007. Instrument-tissue segment interaction using finite element modeling. In Proceedings of the 29th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBS'07). 2760--2763.

[2]

M. Ament, G. Knittel, D. Weiskopf, and W. Strasser. 2010. A parallel preconditioned conjugate gradient solver for the poisson problem on a multi-gpu platform. In Proceedings of the 18th Euromicro International Conference on Parallel, Distributed and Network-Based Processing. 583--592.

Digital Library

[3]

K. J. Bathe. 1996. Finite Element Procedures. Prentice Hall.

[4]

N. Bell and M. Garland. 2008. Efficient sparse matrix-vector multiplication on cuda. NVIDIA Tech. Rep. NVR-2008-004, NVIDIA Corporation.

[5]

M. Bro-Nielsen. 1998. Finite element modeling in surgery simulation. Proc. IEEE 86, 3, 490--503.

[6]

L. Buatois, G. Caumon, and B. Lévy. 2007. Concurrent number cruncher an efficient sparse linear solver on the gpu. In Proceedings of the High Performance Computation Conference (HPCC'07).

Digital Library

[7]

H. Courtecuisse, H. Jung, J. Allard, C. Duriez, D. Lee, and S. Cotin. 2010. GPU-based real-time soft tissue deformation with cutting and haptic feedback. Progress Biophys. Mol. Biol. 103, 2, 159--168.

[8]

H. Delingette, G. Subsol, S. Cotin, and J. Pignon. 1994. A craniofacial surgery simulation testbed. Visualiz. Biomed. Comput. 2359, 1, 607--618.

[9]

M. Delorimier. 2005. Floating-point sparse matrix-vector multiply for FPGAs. Master's thesis, California Institute of Technology Pasadena, CA.

[10]

M. Delorimier and A. Dehon. 2005. Floating-point sparse matrix-vector multiply for fpgas. In Proceedings of the ACM/SIGDA 13th International Symposium on Field-Programmable Gate Arrays (FPGA'05). ACM, New York, 75--85.

Digital Library

[11]

S. P. Dimaio and S. E. Salcudean. July 2005. Interactive simulation of needle insertion models. IEEE Trans. Biomed. Eng. 52, 7, 1167--1179.

[12]

M. Ferrant, A. Nabavi, B. Macq, P. Black, F. Jolesz, R. Kikinis, and S. Warfield. 2002. Serial registration of intraoperative mr images of the brain. Med. Image Anal. 6, 4.

[13]

G. Goumas, K. Kourtis, N. Anastopoulos, V. Karakasis, and N. Koziris. 2008. Understanding the performance of sparse matrix-vector multiplication. In Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'08). 283--292.

Digital Library

[14]

P. Hinterseer and E. Steinbach. 2006. A psychophysically motivated compression approach for 3d haptic data. In Proceedings of the 14th Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems. 35--41.

Digital Library

[15]

J. Hu, S. Quigley, and A. Chan. 2008. An element-by-element preconditioned conjugate gradient solver of 3d tetrahedral finite elements on an fpga coprocessor. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'08). 575--578.

[16]

K. H. Huebner, D. L. Dewhirst, D. E. Smith, and T. G. Byrom. 2001. The Finite Element Method for Engineers 4th Ed. Wiley.

[17]

L. Jerabkova, T. P. Wolter, N. Pallua, and T. Kuhlen. 2005. Adaptive soft tissue deformation for a virtual reality surgical trainer. Stud. Health Technol. Inform. 111, 219--222.

[18]

N. Kapre and A. Dehon. 2009. Parallelizing sparse matrix solve for spice circuit simulation using fpgas. In Proceedings of the International Conference on Field-Programmable Technology (FPT'09). 190--198.

[19]

G. Karniadakis and R. M. II Kirby. 2003. Parallel Scientific Computing in C++and MPI: A Seamless Approach to Parallel Algorithms and Their Implementation. Cambridge University Press.

Digital Library

[20]

A. Kinsman and N. Nicolici. 2011. Automated range and precision bit-width allocation for iterative computations. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 30, 9, 1265--1278.

Digital Library

[21]

S. Li and W. K. Liu. 2007. Meshfree Particle Methods. Springer.

Digital Library

[22]

A. Liu, F. Tendick, K. Cleary, and C. Kaufmann. 2003. A survey of surgical simulation: Applications, technology, and education. Presence: Teleoperators Virtual Environ. 12, 6, 599--614.

Digital Library

[23]

Y. Liu, S. Jiao, W. Wu, and S. De. 2008. Gpu accelerated fast fem deformation simulation. In Proceedings of the IEEE Asia Pacific Conference on Circuits and Systems (APCCAS'08). 606--609.

[24]

R. Mafi, S. Sirouspour, B. Mahdavikhah, B. Moody, K. Elizeh, A. Kinsman, and N. Nicolici. 2009. A parallel computing platform for real-time haptic interaction with deformable bodies. IEEE Trans. Haptics 3, 3.

Digital Library

[25]

B. Mahdavikhah, R. Mafi, S. Sirouspour, and N. Nicolici. 2010. Haptic rendering of deformable objects using a multiple fpga parallel computing architecture. In Proceedings of the 18th Annual ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA'10). ACM, New York, 189--198.

Digital Library

[26]

B. Marami, S. Sirouspour, and D. Capson. 2011. Model-based 3D/2D deformable registration of mr images. In Proceedings of the Annual International Conference of the IEEE Engineering in Medicine and Biology Society. 4880--4883.

[27]

U. Meier and R. Eigenmann. 1991. Parallelization and performance of conjugate gradient algorithms on the cedar hierarchial-memory multiprocessor. ACM SIGPLAN No. 26, 7, 178--188.

Digital Library

[28]

U. Meier, O. López, C. Monserrat, M. Juan, and M. Alcaiz. 2005. Real-time deformable models for surgery simulation: A survey. Comput. Methods Programs Biomed. 77, 3, 183--197.

Digital Library

[29]

S. Moghimi, S. Sirouspour, and P. Malysz. 2008. Haptic-enabled collaborative training with generalized force and position mappings. In Proceedings of the Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems. 287--294.

Digital Library

[30]

A. Nealen, M. Mueller, R. Keiser, E. Boxerman, and M. Carlson. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809--836.

[31]

Y. Saad. 2003. Iterative Methods for Sparse Linear Systems. SIAM.

Digital Library

[32]

H. F. Shi and S. Payandeh. 2008. Gpu in haptic rendering of deformable objects. In Proceedings of the 6th International Conference on Haptics (EuroHaptics'08). Springer, 163--168.

Digital Library

[33]

B. Smith, P. Bjorstad, and W. Gropp. 2004. Domain Decomposition. Cambridge University Press.

[34]

G. D. Smith. 1986. Numerical Solution of Partial Differential Equations: Finite Difference Methods. Oxford University Press.

[35]

F. L. Stasa. 1985. Applied Finite Element Analysis for Engineers. Holt, Rinehart, and Winston.

[36]

J. Sun, G. Peterson, and O. Storaasli. 2007. Sparse matrix-vector multiplication design on fpgas. In Proceedings of the 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. 349--352.

Digital Library

[37]

Z. A. Taylor, M. Cheng, and S. Ourselin. 2007. Real-time nonlinear finite element analysis for surgical simulation using graphics processing units. Med. Image Comput. Comput. Assist. Interv. 4791, 701--708.

Digital Library

[38]

B. Thomaszewski, S. Pabst, and W. Blochinger. 2007. Exploiting parallelism in physically-based simulations on multi-core processor architectures. In Proceedings of the Eurographics Symposium on Parallel Graphics and Visualization. 69--76.

Digital Library

[39]

W. Wiggers, V. Bakker, A. Kokkeler, and G. Smit. 2007. Implementing the conjugate gradient algorithm on multi-core systems. In Proceedings of the International Symposium on System-on-Chip. 1--4.

[40]

X. Wu and F. Tendick. Multigrid integration for interactive deformable body simulation. In Proceedings of the International Symposium on Medical Simulation (ISMS'04). S. Cotin and D. Metaxas, Eds., Lecture Notes in Computer Science, vol. 3078, Springer, 92--104.

[41]

Z. Yan, L. Gu, P. Huang, S. Lv, X. Yu, and X. Kong. 2007. Soft tissue deformation simulation in virtual surgery using nonlinear finite element method. In Proceedings of the 29th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBS'07). 3642--3645.

[42]

D. Zerbato, S. Galvan, and P. Fiorini. 2007. Calibration of mass spring models for organ simulations. In Proceedings of the International Conference on Intelligent Robots and Systems. 370--375.

[43]

J. Zhang, S. Payandeh, and J. Dill. 2002. Haptic subdivision: An approach to defining level-of-detail in haptic rendering. In Proceedings of the 10th Symposium on Haptic Interfaces For Virtual Environments and Teleoperator Systems.

Digital Library

[44]

Y. Zhong, B. Shirinzadeh, G. Alici, and J. Smith. 2005. A new methodology for deformable object simulation. In Proceedings of the IEEE International Conference on Robotics and Automation. 1902--1907.

[45]

L. Zhuo and V. K. Prasanna. 2005. Sparse matrix-vector multiplication on FPGAs. In Proceedings of the 13th International Symposium on Field-Programmable Gate Arrays. 63--74.

Digital Library

Cited By

Tomii RNarumi T(2024)A Hardware Solver for Simultaneous Linear Equations with Multistage Interconnection NetworkProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665299(81-89)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665299
Corrêa CNunes FRanzini ENakamura RTori R(2019)Haptic interaction for needle insertion training in medical applications: The state-of-the-artMedical Engineering & Physics10.1016/j.medengphy.2018.11.00263(6-25)Online publication date: Jan-2019
https://doi.org/10.1016/j.medengphy.2018.11.002

Index Terms

A Multiple-FPGA parallel computing architecture for real-time simulation of soft-object deformation
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

A Parallel Computing Platform for Real-Time Haptic Interaction with Deformable Bodies

Real-time simulation of haptic interaction with deformable objects is computationally demanding. In particular in finite-element (FE) based analysis of such interactions, a large system of equations must be solved at an update rate of 100-1,000 Hz for ...
Synthesizable Standard Cell FPGA Fabrics Targetable by the Verilog-to-Routing CAD Flow
Special Section on Field Programmable Logic and Applications 2015 and Regular Papers

In this article, we consider implementing field-programmable gate arrays (FPGAs) using a standard cell design methodology and present a framework for the automated generation of synthesizable FPGA fabrics. The open-source Verilog-to-Routing (VTR) FPGA ...
FPGA-based fine-grain parallel computing (abstract only)
FPGA '11: Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays

FPGAs are increasing in computing power at a significant rate while the non-recurring engineering costs and time-to-market remain significant lower than those for application-specific integrated circuits (ASICs), encouraging FPGAs to be used in areas ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 13, Issue 4

Regular Papers

November 2014

647 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2592905

Editor:
Sandeep K. Shukla
Virginia Tech, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

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

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 10 March 2014

Accepted: 01 November 2012

Received: 01 June 2012

Published in TECS Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Ontario Centres of Excellence (OCE) for this project
Quanser Consulting Inc., the Health Technology Exchange (HTX)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
684
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tomii RNarumi T(2024)A Hardware Solver for Simultaneous Linear Equations with Multistage Interconnection NetworkProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665299(81-89)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665299
Corrêa CNunes FRanzini ENakamura RTori R(2019)Haptic interaction for needle insertion training in medical applications: The state-of-the-artMedical Engineering & Physics10.1016/j.medengphy.2018.11.00263(6-25)Online publication date: Jan-2019
https://doi.org/10.1016/j.medengphy.2018.11.002

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents