全域照明演算法可以模擬真實3D影像的場景，特別包括光線追蹤和光子映射演算法，但必須耗費龐大的運算時間。為了提升這些演算法的性能，並降低系統的功率消耗，多處理器平台(MPSoC)已經成為愈來愈受歡迎的系統晶片(SoC)平台。因此，在本論文中，我們建立一個同質的多處理器平台以實現這些演算法 。在建立的平台中，使用網格晶片網路(NoC)和適應性的蟲洞路由演算法，完成資料在核心之間的傳輸。此外，我們亦詳細考慮資料在網路傳輸的負載平衝和相依性，以降低資料傳輸的成本與時間。完成的系統經由不同的核心數目組合，執行可以達到時脈週期精確度的模擬，以量測其性能。實驗結果顯示，光線追蹤和光子映射演算法在8 × 8多處理器平台上，最大分別可以達到62.74和44.3的加速度比。

Global illumination, especially ray tracing and photon mapping, is a very powerful but computational-intensive technique for realistic 3-D image synthesis. To facilitate the required high amounts of computations and to lower the power dissipation of the resulting system, the multiprocessor system-on-chip (SoC) platforms have become popular. To demonstrate this, we construct in this thesis a homogeneous multiprocessor SoC (MPSoC) platform on which parallel algorithms for both ray tracing and photo mapping are developed. In the platform, a mesh NoC with an adaptive wormhole routing method is in charge of data transmission between cores. Besides, the load balancing and data dependency in all rendering stages are considered carefully to decrease the communication cost and computation time of the system. The performance of the resulting system is then evaluated through cycle-accurate simulations with different number of cores. The simulation results show that outstanding speed-up of 62.74 in ray tracing and 44.3 in photon mapping for an 8-by-8 MPSoC platform are achieved.

Bibliography
[1] I. Al-Furajh, S. Aluru, S. Goil, and S. Ranka, \Parallel construction of multidi-
mensional binary search trees," IEEE Transactions on Parallel and Distributed
Systems, vol. 11, no. 2, pp. 136{148, Feb. 2000.
[2] C. Aykanat, V. Isler, and B. Ozguc, \E cient parallel spatial subdivision algo-
rithm for object-based parallel ray tracing," Computer-Aided Design, vol. 26, no.
12, pp. 883{890, 1994.
[3] C. Benthin, I. Wald, M. Scherbaum, H. Friedrich, \Ray tracing on the cell proces-
sor," IEEE Symposium on Interactive Ray Tracing, pp. 15{23, 18-20, Sep. 2006.
[4] J. Duato, and S. Yalmanchili, Interconnection Networks|An Engineering Ap-
proach, Morgan Kaufmann Publishers, Elsevier Science, 2003.
[5] Ch. Ericson, Real-Time Collision Detection, Morgan Kaufmann Publishers, Else-
vier Science, 2005.
[6] S. Guntury, and P. J. Narayanan, \Raytracing dynamic scenes on the GPU using
grids," IEEE Transactions on Visualization and Computer Graphics, vol. 18, no.
1, pp. 5{16, Jan. 2012.
[7] J. Gunther, S. Popov, H. P. Seidel, and P. Slusallek, \Realtime ray tracing on
GPU with BVH-based packet traversal," IEEE Symposium on Interactive Ray
Tracing, pp. 113{118, Sep. 10-12, 2007.
[8] T. Hachisuka, Ray tracing on graphics hardware, Tech. Reprot, University of
California at San Diego, 2009.
[9] T. Hachisuka, and H. Jensen, \Parallel progressive photon mapping on GPUs,"
Proceedings of the SIGGRAPH, Asia Sketches, 2010.
[10] J. Hanika, and A. Keller, \Towards hardware ray tracing using xed point arith-
metic," IEEE Symposium on Interactive Ray Tracing, pp. 119{128, Sep. 10-12,
2007.
[11] H. He, T. Wang, Q. Xu, and Y. Xing. , \Multi-core parallel of photon mapping,"
Visual Information Communication, Springer US, pp. 365{374, Jan. 01, 2010.
[12] J. Heinly, Sh. Recker, K. Bensema, J. Porch, and Ch. Gribble, \Integer ray
tracing," Journal of Graphics, GPU, and Game Tools, vol. 14, no. 4, pp. 31{56,
2009.
[13] W. Jarosz , H. W. Jensen , and C. Donner, \Advanced global illumination using
photon mapping," ACM SIGGRAPH 2008 classes, Los Angeles, California, Aug.
11-15, 2008.
[14] K. Klimaszewski, and T. W. Sederberg, \Faster ray tracing using adaptive grids,"
IEEE Computer Graphics and Applications, vol. 17, no. 1, pp. 42{51, Jan./Feb.
1997.
[15] I. LazEnyi, and L. Szirmay-Kalos,\Speeding up the virtual light sources algo-
rithm," Proceedings of the 20th Spring Conference on Computer Graphics, pp.
112{120, 2004.
[16] T. Moller, and B. Trumbore, \Fast, minimum storage ray-triangle intersection,"
Journal of Graphics Tools, vol. 2, no. 1, pp. 21{28, 1997.
[17] A. S. Nery, "E cient hardware implementation of ray tracing based on an em-
bedded software for intersection computation," Journal of System Architecture,
Apr. 2011.
[18] A. S. Nery, N. Nedjah, F. M. G. Franca, and L. Jozwiak, \A parallel ray tracing
architecture suitable for application-speci c hardware and GPGPU implementa-
tions," Proceedings of the 14th Euromicro Conference on Digital System Design
(DSD), pp. 511{518, Aug. 31-Sep. 2, 2011.
[19] M. Pharr, and G. Humphreys, Physically Based Rendering, From Theory To
Implementation, second edition, Morgan Kaufmann Publishers, Jul. 12, 2010.
[20] T. J. Purcell, C. Donner, M. Cammarano, H. W. Jensen, and P. Hanrahan,
\Photon mapping on programmable graphics hardware," Proceedings of the ACM
SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware. Eurographics
Association, pp. 41{50, Jul. 31-Aug. 04, 2005.
[21] J. Schmittler, I. Wald, and Ph. Slusallek, \SaarCOR: A hardware architecture
for ray tracing," Proceedings of the ACM SIGGRAPH, EUROGRAPHICS Con-
ference on Graphics Hardware, pp. 27{36, Sep. 01-02, 2002.
[22] J. Schmittler, S. Woop,D. Wagner, and P. Slusallek, \Realtime ray tracing of
dynamic scenes on an FPGA chip," Proceedings of the ACM SIGGRAPH, Euro-
graphics Conference on Graphics Hardware, pp. 95{102, Aug. 29-30, 2004.
[23] M. Shevtsov, A. Soupikov, and A. Kapustin, \Highly parallel fast k-d tree con-
struction for interactive ray tracing of dynamic scenes," Computer Graphics Fo-
rum, vol. 26, pp. 395{404. 2007.
[24] Sh. Singh, and P. Faloutsos, \SIMD packet techniques for photon mapping,"
IEEE Symposium on Interactive Ray Tracing, pp. 87{94, 2007.
[25] J. Spjut, A. Kensler, D. Kopta, and E. Brunvand, \TRaX: A multicore hardware
architecture for real-time ray tracing," IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, vol. 28, no. 12, pp. 1802{1815, Dec.
2009.
[26] J. S. Sven Woop, and P. Slusallek, \Rpu: A programmable ray processing unit
for realtime ray tracing," Proceedings of ACM SIGGRAPH, vol. 24, no. 3, pp.
434{444, 2005.
[27] M. Tamura, H. Takizawa, and H. Kobayashi, \A parallel image generation algo-
rithm based on photon map partitioning," Proceedings of computer Graphics and
Imaging, 2008.
[28] F. Van Reeth, P. Monsieurs, P. Bekaert, and E. Flerackers, \Ray tracing op-
timization utilizing projective methods," Proceedings of International Computer
Graphics 1996, pp. 47{53, 24-28 Jun. 1996.
[29] W. Wolf, A. A. Jerraya, and G. Martin, \Multiprocessor system-on-chip (MP-
SoC) technology," IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, vol. 27, no. 10, pp. 1701{1713, Oct. 2008.
[30] J. Yang, S.E. Lee, C. Chen, and N. Bagherzadeh, \Ray tracing on a networked
processor array," International Journal of Electronics, vol. 97, no. 10, pp. 1193{
1205, Oct. 2010.
[31] H. J. Yoon, S. Eun, and J. W. Cho. \Image parallel ray tracing using static load
balancing and data prefetchiog," Parallel Computing, vol. 23, no. 7, pp. 861{872,
Jul. 1997.
[32] P. Zhou, and X. Meng, \SIMD friendly ray tracing on GPU," The 12th
International Conference on Computer-Aided Design and Computer Graphics
(CAD/Graphics), pp. 87{92, 15-17 Sep. 2011.
[33] K. Zhou, Q. Hou, R. Wang, and B. Guo, \Real-time k-d tree construction on
graphics hardware," Proceedings of the SIGGRAPH Asia, vol. 25, no. 5, Dec.
2008.
[34] http://standards.ieee.org/getieee/1666/download/1666-2011.pdf
[35] http://sourceforge.net/projects/simit-arm/ les/simit-arm/release
[36] http://simit-arm.sourceforge.net/