A Multiple-FPGA Parallel Computing Architecture for Real-time Simulation of Deformable Objects

Abstract

<p>In recent years there has been a growing interest in computer-based surgical planning,<br />virtual-reality enabled training of medical procedures, and computer gaming all involving non-rigid deformable objects. High-fidelity simulations of haptic interaction with deformable objects is computationally demanding. The Finite Element Method (FEM) is known to produce relatively accurate solution for continuum mechanics-based models of soft-object deformation. Linear elastic FE models require solving a large sparse system of equations. The solution accuracy can be improved by increasing the resolution of the finite element mesh resulting in a larger number of equations and hence greater computational complexity. Depending on the mechanical characteristics of the soft-object, to maintain stability and high fidelity in haptic interaction, the update rate should be in the range of 1001000Hz. This, for example, means that for a moderately-sized three-dimensional mesh of 6000 nodes, a set of 18000 linear equations must be solved within 1-10ms.</p> <p>In this thesis, hardware-based parallel computing is proposed for finite-element<br />(FE) analysis of soft-object deformation models. In particular, a distributed implementation of the (CG) algorithms on .\' Field Programmable Gate Array (FPGA)<br />devices connected in a ring configuration is developed. This Parallel architecture<br />can be utilized to solve the large system of equations arising from FE models at high update rates required for stable haptic interaction. Massive parallelization of the computations is achieved by customizing the hardware architecture to the problem at hand and employing a large number of adaptive fixed-point computing units in parallel. The proposed hardware architecture satisfies three important criteria: (i) it meets the haptic rendering timing constraint by enabling an update rate of 400Hz; (ii) it attempts to simulate as many nodes as possible, given the available resources on the FPGA devices employed in this work and (iii) it is scalable both within an FPGA and also across multiple FPGA devices.<br />This research builds upon our group's earlier work in [1]. In that paper a novel highly parallelized single-FPGA architecture was proposed for solving system of equations arising from FEM using Conjugate gradient method. In this thesis, a multiple-FPGA architecture based on that design has been proposed. The contributions in the new multiple-FPGA design can be summarized as follows.</p>