Accelerating mesh-based Monte Carlo method on modern CPU
architectures

doi:10.1364/BOE.3.003223

Accelerating mesh-based Monte Carlo method on modern CPU architectures

Qianqian Fang and David R. Kaeli »View Author Affiliations

Biomedical Optics Express, Vol. 3, Issue 12, pp. 3223-3230 (2012)
http://dx.doi.org/10.1364/BOE.3.003223

View Full Text Article

Enhanced HTML Acrobat PDF (1049 KB)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Abstract
Article Info
References (23)
Cited By
Figures (2)
Metrics
Related Content

Abstract

In this report, we discuss the use of contemporary ray-tracing techniques to accelerate 3D mesh-based Monte Carlo photon transport simulations. Single Instruction Multiple Data (SIMD) based computation and branch-less design are exploited to accelerate ray-tetrahedron intersection tests and yield a 2-fold speed-up for ray-tracing calculations on a multi-core CPU. As part of this work, we have also studied SIMD-accelerated random number generators and math functions. The combination of these techniques achieved an overall improvement of 22% in simulation speed as compared to using a non-SIMD implementation. We applied this new method to analyze a complex numerical phantom and both the phantom data and the improved code are available as open-source software at http://mcx.sourceforge.net/mmc/.

OCIS Codes
(170.3660) Medical optics and biotechnology : Light propagation in tissues
(170.5280) Medical optics and biotechnology : Photon migration
(170.7050) Medical optics and biotechnology : Turbid media

ToC Category:
Optics of Tissue and Turbid Media

History
Original Manuscript: July 23, 2012
Revised Manuscript: September 25, 2012
Manuscript Accepted: September 27, 2012
Published: November 12, 2012

Citation
Qianqian Fang and David R. Kaeli, "Accelerating mesh-based Monte Carlo method on modern CPU architectures," Biomed. Opt. Express 3, 3223-3230 (2012)
http://www.opticsinfobase.org/boe/abstract.cfm?URI=boe-3-12-3223

Sort: Author | Year | Journal | Reset

References

D. A. Boas, D. H. Brooks, E. L. Miller, C. A. DiMarzio, M. Kilmer, R. J. Gaudette, and Q. Zhang, “Imaging the body with diffuse optical tomography,” IEEE Signal Proc. Mag.18, 57–75 (2001). [CrossRef]
A. P. Gibson, J. C. Hebden, and S. R. Arridge, “Recent advances in diffuse optical imaging,” Phys. Med. Biol.50, R1–R43 (2005). [CrossRef] [PubMed]
L. H. Wang, S. L. Jacques, and L. Q. Zheng, “MCML - Monte Carlo modeling of light transport in multilayered tissues,” Comput. Meth. Prog. Bio.47, 131–146 (1995). [CrossRef]
D. A. Boas, J. Culver, J. Stott, and A. Dunn, “Three dimensional Monte Carlo code for photon migration through complex heterogeneous media including the adult human head,” Opt. Express10, 159–170 (2002). [PubMed]
Q. Fang and D. A. Boas, “Monte Carlo simulation of photon migration in 3D turbid media accelerated by graphics processing,” Opt. Express17, 20178–20190 (2009). [CrossRef] [PubMed]
H. Li, J. Tian, F. Zhu, W. Cong, L. V. Wang, E. A. Hoffman, and G. Wang, “A mouse optical simulation environment (MOSE) to investigate bioluminescent phenomena in the living mouse with the monte carlo method,” Academ. Radiol.11, 1029–1038 (2004). [CrossRef]
E. Margallo-Balbäs and P. J. French, “Shape based Monte Carlo code for light transport in complex heterogeneous Tissues,” Opt. Express15, 14086–14098 (2007). [CrossRef] [PubMed]
N. Ren, J. Liang, X. Qu, J. Li, B. Lu, and J. Tian, “GPU-based Monte Carlo simulation for light propagation in complex heterogeneous tissues,” Opt. Express18, 6811–6823 (2010). [CrossRef] [PubMed]
C. Wächter, “Quasi-Monte Carlo light transport simulation by efficient ray tracing,” Ph.D. dissertation (Ulm University, Ulm, Germany, 2007).
I. Wald, “Realtime ray tracing and interactive global illumination,” Ph.D. dissertation (Saarland Univ., Saarbrücken, Germany, 2004).
H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol.55, 947–962 (2010). [CrossRef] [PubMed]
Q. Fang, “Mesh-based Monte Carlo method using fast ray-tracing in Plücker coordinates,” Biomed. Opt. Express1, 165–175 (2010). [CrossRef] [PubMed]
Q. Fang, “Comment on ‘A study on tetrahedron-based inhomogeneous Monte-Carlo optical simulation’,” Biomed. Opt. Express2, 1258–1264 (2011). [CrossRef] [PubMed]
CGAL Editorial Board, CGAL User and Reference Manual, 3rd ed. (2009).
Q. Fang and D. A. Boas, “Tetrahedral mesh generation from volumetric binary and grayscale images,” in IEEE International Symposium on Biomedical Imaging: from Nano to Macro, 2009. ISBI ’09 (IEEE, 2009), pp. 1142–1145. [CrossRef]
M. Shevtsov, A. Soupikov, and A. Kapustin, “Ray-triangle intersection algorithm for modern CPU architectures,” in Proceedings of GraphiCon 2007 (2007), Vol. 11, pp. 33–39.
J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Visualiz. Comput. Graphics16, 434–438 (2010). [CrossRef]
D. Badouel, Graphics Gems (Academic, 1990).
M. Saito and M. Matsumoto, Monte Carlo and Quasi-Monte Carlo Methods 2006 (Springer, 2008).
J. Pommier, “Simple SSE and SSE2 optimized sin, cos, log and exp” (2007), http://gruntthepeon.free.fr/ssemath/ .
B. Dogdas, D. Stout, A. Chatziioannou, and R. M. Leahy, “Digimouse: a 3D whole body mouse atlas from CT and cryosection data,” Phys Med Biol.52, 577–87 (2007). [CrossRef] [PubMed]
W. F. Cheong, S. A. Prahl, and A. J. Welch, “A review of the optical properties of biological tissues,” IEEE J. Quantum Electronics26, 2166–2185 (1990). [CrossRef]
S. Powell and T. S. Leung, “Highly parallel Monte-Carlo simulations of the acousto-optic effect in heterogeneous turbid media,” J. Biomed. Opt.17, 045002 (2012). [CrossRef] [PubMed]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Click here to see a list of articles that cite this paper

Figures


Fig. 1	Fig. 2

« Previous Article | Next Article »

OSA is a member of CrossRef.

[1] D. A. Boas, D. H. Brooks, E. L. Miller, C. A. DiMarzio, M. Kilmer, R. J. Gaudette, and Q. Zhang, “Imaging the body with diffuse optical tomography,” IEEE Signal Proc. Mag.18, 57–75 (2001). [CrossRef]

[2] A. P. Gibson, J. C. Hebden, and S. R. Arridge, “Recent advances in diffuse optical imaging,” Phys. Med. Biol.50, R1–R43 (2005). [CrossRef] [PubMed]

[3] L. H. Wang, S. L. Jacques, and L. Q. Zheng, “MCML - Monte Carlo modeling of light transport in multilayered tissues,” Comput. Meth. Prog. Bio.47, 131–146 (1995). [CrossRef]

[4] D. A. Boas, J. Culver, J. Stott, and A. Dunn, “Three dimensional Monte Carlo code for photon migration through complex heterogeneous media including the adult human head,” Opt. Express10, 159–170 (2002). [PubMed]

[5] Q. Fang and D. A. Boas, “Monte Carlo simulation of photon migration in 3D turbid media accelerated by graphics processing,” Opt. Express17, 20178–20190 (2009). [CrossRef] [PubMed]

[6] H. Li, J. Tian, F. Zhu, W. Cong, L. V. Wang, E. A. Hoffman, and G. Wang, “A mouse optical simulation environment (MOSE) to investigate bioluminescent phenomena in the living mouse with the monte carlo method,” Academ. Radiol.11, 1029–1038 (2004). [CrossRef]

[7] E. Margallo-Balbäs and P. J. French, “Shape based Monte Carlo code for light transport in complex heterogeneous Tissues,” Opt. Express15, 14086–14098 (2007). [CrossRef] [PubMed]

[8] N. Ren, J. Liang, X. Qu, J. Li, B. Lu, and J. Tian, “GPU-based Monte Carlo simulation for light propagation in complex heterogeneous tissues,” Opt. Express18, 6811–6823 (2010). [CrossRef] [PubMed]

[9] C. Wächter, “Quasi-Monte Carlo light transport simulation by efficient ray tracing,” Ph.D. dissertation (Ulm University, Ulm, Germany, 2007).

[10] I. Wald, “Realtime ray tracing and interactive global illumination,” Ph.D. dissertation (Saarland Univ., Saarbrücken, Germany, 2004).

[11] H. Shen and G. Wang, “A tetrahedron-based inhomogeneous Monte Carlo optical simulator,” Phys. Med. Biol.55, 947–962 (2010). [CrossRef] [PubMed]

[12] Q. Fang, “Mesh-based Monte Carlo method using fast ray-tracing in Plücker coordinates,” Biomed. Opt. Express1, 165–175 (2010). [CrossRef] [PubMed]

[13] Q. Fang, “Comment on ‘A study on tetrahedron-based inhomogeneous Monte-Carlo optical simulation’,” Biomed. Opt. Express2, 1258–1264 (2011). [CrossRef] [PubMed]

[14] CGAL Editorial Board, CGAL User and Reference Manual, 3rd ed. (2009).

[15] Q. Fang and D. A. Boas, “Tetrahedral mesh generation from volumetric binary and grayscale images,” in IEEE International Symposium on Biomedical Imaging: from Nano to Macro, 2009. ISBI ’09 (IEEE, 2009), pp. 1142–1145. [CrossRef]

[16] M. Shevtsov, A. Soupikov, and A. Kapustin, “Ray-triangle intersection algorithm for modern CPU architectures,” in Proceedings of GraphiCon 2007 (2007), Vol. 11, pp. 33–39.

[17] J. Havel and A. Herout, “Yet faster ray-triangle intersection (using SSE4),” IEEE Trans. Visualiz. Comput. Graphics16, 434–438 (2010). [CrossRef]

[18] D. Badouel, Graphics Gems (Academic, 1990).

[19] M. Saito and M. Matsumoto, Monte Carlo and Quasi-Monte Carlo Methods 2006 (Springer, 2008).

[20] J. Pommier, “Simple SSE and SSE2 optimized sin, cos, log and exp” (2007), http://gruntthepeon.free.fr/ssemath/ .

[21] B. Dogdas, D. Stout, A. Chatziioannou, and R. M. Leahy, “Digimouse: a 3D whole body mouse atlas from CT and cryosection data,” Phys Med Biol.52, 577–87 (2007). [CrossRef] [PubMed]

[22] W. F. Cheong, S. A. Prahl, and A. J. Welch, “A review of the optical properties of biological tissues,” IEEE J. Quantum Electronics26, 2166–2185 (1990). [CrossRef]

[23] S. Powell and T. S. Leung, “Highly parallel Monte-Carlo simulations of the acousto-optic effect in heterogeneous turbid media,” J. Biomed. Opt.17, 045002 (2012). [CrossRef] [PubMed]

OpticsInfoBase

Biomedical Optics Express

Accelerating mesh-based Monte Carlo method on modern CPU architectures