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 statist ical positron emission tomography image reconstruction algorithms. We prese nt a new, faster algorithm which replaces Siddon's. Further code transforma tions on this algorithm prove to be beneficial in a Maximum Likelihood-Expe ctation Maximization reconstruction algorithm and the result is perfectly s uitable 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 paral lel implementation is 13. Though smaller data formats are used in subword p arallelism, the resulting images are as good as the original ones. (C) 1999 Elsevier Science B.V. AU rights reserved.