A fast, cache-aware algorithm for the calculation of radiological paths exploiting subword parallelism

The calculation of radiological paths is the most important part in statistical positron emission tomography image reconstruction algorithms. We present a new, faster algorithm which replaces Siddon's. Further code transformations on this algorithm prove to be beneficial in a Maximum Likelihood-Expectation Maximization reconstruction algorithm and the result is perfectly suitable for an implementation that exploits the VISual instruction set from Sun or other modern architectural extensions providing subword parallelism. The final speed-up achieved with this new algorithm and its subword parallel implementation is 13. Though smaller data formats are used in subword parallelism, the resulting images are as good as the original ones. (C) 1999 Elsevier Science B.V. AU rights reserved.