Feldkamp-Davis-Kress Algorithm

Computerized Tomography (CT) is widely used in the medical sector to produce tomographic images of specific areas of the body. Succinctly, CT reconstructs an image of the original three-dimensional (3D) object from a large series of two-dimensional (2D) X-ray images. As a set of rays pass through an object around a single axis of rotation, the produced projection data is captured by an array of detectors, from which a filtered back-projection method based on the Fourier slice theorem is typically used to reconstruct the original object. Among various filtered back-projection algorithms, the Feldkamp-Davis-Kress (FDK) algorithm is mathematically straightforward and easy to implement. It is important that the image reconstructed from the acquired data be accurate. The goal of this work is to accelerate the reconstruction using directive-based programming models.

Fig. 2 shows pseudo-code for the FDK algorithm, which is comprised of three main steps:

1. Weighting—calculate the projected data.

2. Filtering—filter the weighted projection by multiplying their Fourier transforms.

3. Back-projection—back-project the filtered projection over the 3D reconstruction mesh.

The reconstruction algorithm is computationally intensive and it has biquadratic complexity (O(N4)), where N is the number of detector pixels in one dimension. The most time-consuming step of this algorithm is back-projection. As shown in Fig. 3, a profiled example of the application shows the back-projection routines in the application accounts for nearly all the runtime (63.04% + 20.85% + 15.63% = 99.52% of the whole application). So the focus of our work is to parallelize the back-projection step.

For implementation purposes we follow the steps given by Kak and Slaney (1988). As shown in Fig. 4A, the back-projection algorithm has four loops. The three outermost loops traverse each dimension of the output 3D object, and the innermost loop accesses each of the 2D detected image slices.

The code is first restructured so that the three outermost loops are tightly nested, and then the collapse clause from OpenACC is applied. This means that every thread sequentially executes the innermost loop. All detected images are transferred from the CPU to the GPU by using the copyin clause, and the output 3D object (i.e., many 2D image slices) is copied from GPU to CPU using the copyout clause. The implementations are evaluated using 3D Logan and Shepp (1975) head phantom data that has 300 detected images and the resolution of each image is 200 × 200. The algorithm produces a 200 × 200 × 200 reconstructed cube. The input and output images are shown towards the end of this section.

Note that results for this application are sensitive to floating-point operation ordering and precision. Hence the floating-point values of the final output on a GPU can differ from the values computed on the CPU. One reason for this is the fused multiply add (FMA) operation Pullan (2009), where the computation rn(X * Y + Z) is carried out in a single step and is only rounded once. Without FMA, rn(rn(X * Y) + Z) is composed of two steps and rounded twice. Thus, using FMA will cause the results to differ slightly; but this does not mean that the FMA implementation is incorrect. The difference in results obtained with and without FMA, respectively, may matter for certain types of codes and not for others. In our case, the observed differences (with and without FMA) were minute. However, if a complex code, e.g., a weather modeling code is under consideration, even minute differences may not be tolerable.

To compile the C version of the FDK algorithm, the following command is used (Fig. 5):

The flag “-ta=tesla” tells the compiler to generate code for the Tesla GPU. We use the option “cc35” to specify the compute capability of the targeted Tesla GPU since the Tesla GPU product family has evolved over time and now contains several generations of devices that differ with respect to their compute capabilities. The flag “nofma” tells the compiler to disable the FMA operation. The flag “-Minfo=accel” tells the compiler to output information when it translates the OpenACC code to GPU code, including information about loop scheduling, data movement, and data synchronization, and more.

In this way various implementation techniques can be explored even in the face of accuracy and precision differences.

The following is the information output by the PGI compiler (Fig. 6):

OpenACC is a model that targets different accelerator architectures. In order to use it for multicore architectures, the following command is required (Fig. 7):

This command differs from the previous compiler command-line in the flags specified: –ta=multicore replaces–ta=tesla. On multicore platforms, a specification of the compute capability is not needed.

Our evaluation includes comparisons among sequential CPU versions, OpenACC versions targeting both multicore and GPUs as well as CUDA versions. The CUDA version was developed manually and the code snippet of back-projection kernel is shown in Fig. 4B.

In the OpenACC version, the three outer loops were collapsed. To keep the comparisons fair, a similar loop scheduling strategy is retained for the CUDA kernels. There are many loop schedules that can be applied by the compiler. The reader is directed to Tian et al. (2016) for more details on using different loop schedule options.

Fig. 8 shows the performance and speedup using different programming models/languages. Compared to the sequential version, the OpenACC multicore, OpenACC GPU, and CUDA versions achieved a speedup of 16.24 ×, 123.47 ×, and 98.93 ×, respectively. The performance of the OpenACC version is slightly better than that of the CUDA code. A probable reason for this is that the OpenACC compiler applied better optimizations while translating OpenACC kernels to CUDA than were implemented in the manually written CUDA kernel.

Matlab can be used to view both the input and the output images. For instance, if the resolution of the output 3D image is 200 × 200, the following Matlab script can be used to view the 180th 2D image slice in the output image (Fig. 9).

The input and output data of the 2D images are shown in Figs. 10 and 11.

2D Heat Equation

Our 2D heat equation application is a stencil-based algorithm with a high computation/communication ratio for which the workload can be distributed across several threads. The implementation uses the GPU’s global memory and obtains good performance, but it could be further improved by using GPU shared memory.

The formula to represent 2D heat conduction is explained in Whitehead & Fit-Florea (2011) and is given in Fig. 12:

where T is temperature, t is time, α is the thermal diffusivity, and x and y are points in a grid. To solve this problem, one possible finite difference approximation is given in Fig. 13:

where ∆T is the temperature change over time ∆t and i, j are indices in a grid.

At program startup, a grid is set up that has boundary points with an initial temperature and inner points for which the temperature must be incrementally updated. Each inner point updates its temperature by using the previous temperature of its neighboring points and itself. The updating step diffuses the temperature from the boundary points through the grid, but it can only progress one grid point per iteration; this means that a large number of iterations can be required to reach a steady temperature state across all points in the grid.

A snippet from our code that implements the stencil-based temperature update is reproduced in Fig. 14. The number of iterations used in our experiments is 20,000, and the grid size is increased gradually from 256 × 256 to 4096 × 4096.

In order to parallelize the application, OpenACC directives are used: “#pragma acc kernels” is inserted at the top of the nested loop inside the temperature updating kernel, and “#pragma acc loop independent” is inserted right before each loop. The “independent” clause is used to tell the compiler that there is no loop-carried dependence in the annotated loop nest. In addition, the copyin and copyout data clauses are added to move the input to GPU and output data from GPU to CPU.

Results of profiling the basic implementation, shown in Fig. 15, indicate that the data is transferred back and forth in every main iteration step.

The cost of data transfer is so high that the parallelized code takes longer to execute than the original version on the host. To avoid transferring the data during each step, a data directive is added surrounding the main iterations; this ensures that the data is transferred only before and after the main loops. After all the iterations have completed, the data in temp1 instead of temp2 needs to be transferred from GPU to CPU since the pointers of temp1 and temp2 have been swapped earlier. In the kernel, the copyin and copyout clauses are replaced by the present clause which indicates that the data are already present on the GPU and thus there is no need to do any data movement.

Fig. 16A shows the OpenACC code snippet after applying data optimization and Fig. 17 shows the corresponding profile result. It is clear that the number of times the data is moved has been reduced from 40,000 to only 3. To enable a comparison, Fig. 16B shows a CUDA implementation of the same kernel.