All entries for Yu-Chung Hsiao

• Print This Page
• Download as PDF

Modeling and Simulation of Blood Flow in Arterial Networks

• Authors: Y.-C. Hsiao, P. Triverio, T. Moselhy, B. Bond, J. Lee, J. White, L. Daniel

Understanding certain medical conditions requires understanding specific aspects of the blood flow in the arterial network. For instance, diagnosing atherosclerosis requires capturing detailed flow inside an arterial segment. Such a study requires developing accurate solvers for the detailed equations describing both the blood flow and the elastic behavior of the arteries. On the opposite end of the spectrum, studying hypertension requires computing pressure and averaged flow over a larger arterial network. Such analysis requires developing compact computationally inexpensive models of complex segments of the arterial network. These models relate the pressure and average flow at the terminals of the arterial segments and must be easily interconnected to form complex and large arterial networks.

In this project we are developing a 2-D fluid-structure interaction solver to accurately simulate blood flow in arteries with bends and bifurcations. Such blood flow is mathematically modeled using the incompressible Navier-Stokes equations. The arterial wall is modeled using a linear elasticity model ^[1] . Our solver is based on an enhanced immersed boundary method (IBM) ^[2] . As a second step we are developing system identification techniques ^[3] to generate passive models for complex arterial segments such as large arteries, arterial bends, and bifurcations. We have validated our IBM solver results versus reference results obtained from MERCK Research Laboratories for a straight vessel of 10-cm length and 2-cm diameter. Our results for pressure, flow, and radius variations are within 3% of those obtained from MERCK. Furthermore, we are validating our model results by cascading different models and comparing the results of the resulting network to those predicted by the IBM solver. Our preliminary results for pressure and flow at the terminals of the models are within 10% of those obtained from the full simulator. In addition, by using the models we obtain a more than 100,000 times reduction in the computational time.



Figure 1: We use i) our immersed boundary method for incompressible Navier-Stokes to extract a complete model and ii) our system identification technique to construct a reduced model ^[3] . The lower part shows three major artery geometries we use for modeling a cardiovascular system.



Figure 2: A 20-cm artery is constructed by cascading two 10-cm artery models terminated with a matched load. The transient simulation results of the cascaded model are compared with those of a 20-cm artery solved by our immersed boundary method solver.




1. A. Quarteroni, M. Tuveri, and A. Veneziani, “Computational vascular fluid dynamics: problems, models and methods,” Computing and Visualization in Science, vol. 2, no. 4, pp. 163-197, Mar. 2000. [↩]
2. C. Peskin and D. McQueen, “A three-dimensional computational method for blood flow in the heart I. Immersed elastic fibers in a viscous incompressible fluid,” Journal of Computational Physics, vol. 81, no. 2, pp. 372-405, Apr. 1989. [↩]
3. B. Bond, T. Moselhy, and L. Daniel, “System identification techniques for modeling of the human arterial system,” Proc. SIAM Conference on the Life Sciences, July 2010, pp. 12-15. (Invited Paper) [↩] [↩]

A Highly Scalable Parallel Boundary Element Method for Capacitance Extraction

• Authors: Y.-C. Hsiao, L. Daniel
• Sponsorship: SRC/FCRP IFC, SRC/FCRP GRC, Mentor Graphics, AMD

Standard boundary element methods (BEMs) involve both an embarrassingly parallelizable system setup step and a linear system solving step of time complexity O(N³) that cannot be parallelized efficiently. When piecewise constant (PWC) basis functions are adopted to represent solutions, the system solving step dominates the overall computation time (usually more than 90%) and limits the scalability of standard BEMs with the number of parallel computing nodes. For capacitance extraction problems, traditional acceleration techniques, such as the multipole expansion ^[1] and the pre-corrected FFT methods ^[2] , can reduce the solving time complexity to O(N log N). However, available parallelization implementations of these two techniques showed that their parallel acceleration saturates quickly with the number of parallel nodes: their parallel efficiency drops to 40% to 60% at just 8 nodes ^{[3] [4]} .

The aforementioned methods suffer from poor parallel scalability because their underlying solution representation, PWC basis functions, is inefficient for representing charge distribution, resulting in a large linear system. Solving such a large system dominates the overall computation and drastically degrades the parallel efficiency. To circumvent the bottleneck of solving a large system in parallel, we employ our recently developed instantiable basis functions, which are 30 times more compact than PWC basis functions for the same capacitance accuracy ^[5] . Accordingly, the computation for solving a system is reduced from the original 90% of the total time to less than 5%, while the embarrassingly parallelizable part is now dominant (growing from 10% of the total time to more than 95%). In addition, we develop four integration techniques to further accelerate the system matrix filling process by 86%. In our demonstrated examples, our new algorithm is 6 times faster than FastCap ^[1] in a single-core environment and achieves 90% parallel efficiency on a 2-cpu-10-core distributed memory system implemented in C++ with MPI parallelization ^[6] .



Figure 1: The charge distribution solutions represented by (a) 572 PWC basis functions and (b) 17 instantiable basis functions, respectively. The capacitance errors for both cases are 2% with respect to a reference capacitance value extracted by the standard BEM with fine discretization.



Figure 2: (a) An industry provided interconnect example. Our integration techniques accelerate by 86%. The overall algorithm is 6 times faster than FastCap ^[1] for single-threaded execution at the same accuracy (a 2.8% error w.r.t. a reference value). (b) A 24×24 bus example and its parallel efficiency comparison in (c) with the algorithms in ^[3] and ^[4] .




1. K. Nabors and J. White, “FastCap: A multipole accelerated 3-D capacitance extraction program,” IEEE Transactions on Computer-Aided Design, vol. 10, no. 10, pp. 1447-1459, Nov. 1991. [↩] [↩] [↩]
2. J. R. Phillips and J. K. White, “A precorrected-FFT method for electrostatic analysis of complicated 3-D structures,” IEEE Transaction on Computer-Aided Design, vol. 16, no. 10, pp. 059-1072, Oct. 1997. [↩]
3. Y. Yuan and P. Banerjee, “A parallel implementation of a fast multipole-based 3-d capacitance extraction program on distributed memory multicomputers,” Journal of Parallel and Distributed Computing, vol. 61, no. 12, pp. 1751–1774, Dec. 2001. [↩] [↩]
4. N. R. Aluru, V. B. Nadkarni, and J. White, “A parallel precorrected FFT based capacitance extraction program for signal integrity analysis,” Proc. 33^rd annual Design Automation Conference, 1996, pp. 363–366. [↩] [↩]
5. Y.-C. Hsiao, T. El-Moselhy, and L. Daniel, “Efficient capacitance solver for 3d interconnect based on template-instantiated basis functions,” IEEE 18th Conference on Electrical Performance of Electronic Packaging and Systems, 2009, pp. 179–182. [↩]
6. Y.-C. Hsiao and L. Daniel, “A highly scalable parallel boundary element method for capacitance extraction,” Proc. 48^th Annual Design Automation Conference, 2011, pp. 552–557. [↩]