Shared memory many-core processors such as GPUs have been extensively used in accelerating computation-intensive algorithms and applications. When porting existing algorithms from sequential or other parallel architecture models to shared memory many-core architectures, non-trivial modifications are often needed to match the execution patterns of the target algorithms with the characteristics of many-core architectures. Ray traversal is a fundamental process in many applications, and is commonly accelerated by spatial decomposition schemes captured in hierarchical data structures (e.g., kd-trees). However, ray traversal using hierarchical data structures needs to conduct repeated hierarchical searches. Such search process is time-consuming on shared memory manycore architectures since it incurs considerable amounts of expensive memory accesses and execution divergence. In this paper, we propose a novel spatial decomposition based data structure, called Shell, which completely avoids hierarchical search for ray traversal. In Shell, a structure is built on the boundary of each region in the decomposed space, which allows any ray traversing in a region to find the next neighboring region to traverse using table lookup schemes, without any hierarchical search. While our ray traversal approach works for other spatial decomposition paradigms and many-core processors in higher dimensional scenes, we illustrate it using kd-tree on GPU for 3D scenario and compare with the fastest known kd-tree searching algorithms for ray traversal. Experimental results in graphics ray tracing and radiation dose calculation show that our approach improves the performance by 3.5-5.5χ over the fastest known kd-tree based approaches.

Monte Carlo based ray tracing (MCBRT) is the foundation of simulating the transport of particles in an inhomogeneous medium, and arises in different applications such as global illumination in graphics rendering and dose calculation in radiation therapy. Due to the computation intensive nature of MCBRT, GPUs have been extensively adopted to accelerate it. However, memory bandwidth becomes a new bottleneck for GPU-based implementations due to the lack of data locality in the MCBRT random memory access patterns. To tackle this issue and consequently improve performance of MCBRT, we present a new locality enhancing method, called LEMCBRT, on CPU-GPU heterogeneous systems. LEMCBRT is based on task partitioning and scheduling, which enhances both the spatial and temporal data locality by organizing random rays into coherent groups. We also develop a CPU-GPU pipeline scheme to reduce the overhead in such ray organization process. To show the applicability of our LEMCBRT method, we apply it to a dose calculation problem in radiation cancer treatment, achieving 6-8X speedup over the best-known GPU solutions on various clinical cases of radiation therapy.

Remarkable progress has been made in the past few decades in various aspects of radiation therapy (RT). However, some of these promising technologies, such as image-guided online replanning and arc therapy, rely heavily on the availability of fast dose calculation. In this article, based on a popular dose calculation algorithm, the Collapsed-Cone Convolution/Superposition (CCCS) algorithm, we present a multi-FPGA accelerator to speed up radiation dose calculation. Our performance-driven design strategy yields a fully pipelined architecture, which includes a resource-economic raytracing engine and high-performance energy deposition pipeline. An evaluation based on a set of clinical treatment planning cases confirms that our FPGA design almost fully utilizes the available external memory bandwidth and achieves close to the best possible performance for the CCCS algorithm while using less resource. Compared with an existing FPGA design which aimed to accelerate the identical algorithm, the proposed design achieved 1.9X speedup by providing better memory bandwidth utilization (81.7% v.s. 43% of the available external memory bandwidth), higher working frequency (90MHz v.s. 70MHz) and less logic resource usage (25K v.s. 55K logic cells). Furthermore, it obtains a speedup of 20X over a commercial multithreaded software on a quad-core system and 15X performance improvement over closely related results. In terms of accuracy, the measured less than 1% statistical fluctuation indicates that our solution is practical in real medical scenarios.

Ray tracing within a uniform grid volume is a fundamental process invoked frequently by many applications, especially radiation-dose calculation methods in radiotherapy. However, the conflicting features between the GPU memory architecture and the memory-accessing patterns of volume ray tracing lead to inefficient usage of GPU memory bandwidth and waste of capability of modern GPUs. To improve the ray tracing performance on GPU, we propose a lookup-table-based ray tracing method which is specially optimized towards the GPU memory system for processing a massive number of rays. The proposed method is based on a key observation that many of these applications normally involves a massive number of rays, but their ray tracing may not need to follow a specific execution order. Therefore, we divide the 3D space into many regions (called pyramids) and group together the rays falling into the same pyramid. For each ray group, the volume is rotated and resampled for their raytracing. This divide-and-rotate strategy allows the memory access of the ray tracing process to adopt a table-lookup approach and leads to better memory coalescing on GPU. Our proposed method was thoroughly evaluated in four volume setups with randomly-generated rays. The collapsed-cone convolution/superposition (CCCS) dose calculation method is also implemented with/without the proposed approach to verify the feasibility of our method. Compared with the direct GPU implementation of the popular 3DDDA algorithm, our method provides a speedup in the range of 1.91--2.94X for the volume settings we used. Major performance factors, including ray origins, volume size, and pyramid size, are also analyzed. The proposed technique was also found to be able to give a speedup of 1.61--2.17X over the original GPU implementation of the CCCS algorithm. Our experiment results indicate that the proposed approach is capable of offering better coalesced memory access which eventually boosts the raytracing performance on GPU. Moreover, our approach is conceptually simple and can be readily included into various applications.

The problem of calculating accurate dose distributions lies in the heart of modern radiation therapy for cancer treatment. Software implementations of dose calculation algorithms are highly costly in terms of CPU time. This paper proposes a multi-engine hardware design for 3D dose calculation based on the collapsed-cone algorithm. The performance of the hardware with one engine (100 Mhz) is already superior to the software counterpart executed on a 2.4 GHz PC. By exploiting the inherent parallelism of the collapsed-cone algorithm, the proposed two-level design with multiple engines can achieve almost a linear speedup compared with the one-engine design. Due to its modular approach, the design can also be easily implemented on a multi-FPGA system for an even greater speedup.