BACKGROUND
comprehensive understanding of biological structures requires sophisticated techniques in many areas such as the combination of 2d and 3d images or models of biological objects.
examples are the integration of histological cross-sections providing structural information and development-specific distribution patterns of mrna, metabolite concentrations or enzyme activities into a 3d morphological framework  <cit> , the combination of 2d computer tomography  slices with a 3d atlas  <cit> , or the integration of 2d positron emission tomography  slices, providing information about metabolic activity, into a 3d nmr dataset, see figure  <dig>  for reconstruction and 3d visualisation these 2d cross-sections have to be registered at correct spatial positions in a 3d morphological framework.
manual registration of cross-sections is tedious, subjective and very time-consuming.
the accurate registration of images, obtained by diverse imaging techniques, requires automatic multimodal alignment techniques, which is an important research field in biological and medical image processing  <cit> .
such approaches determine the optimal spatial position on the base of suitable similarity functions, such as cross correlation  <cit>  or mutual information  <cit> .
registration by automatic procedures still requires extensive computational resources, so that fast algorithms and the implementation on parallel hardware would greatly enhance the feasibility of these investigations.
the multi-core cell broadband engine  allows fast parallel computation on eight cores per chip, presenting potential as a target for implementation of image registration algorithms  <cit> .
in this paper we implemented and evaluated a multimodal alignment approach based on mutual information on the cbe.
the availability of the inexpensive cbe-driven playstation  <dig> provides the opportunity to simultaneously align a high number of image stacks on a low-cost platform and therefore improves the automatic analysis and visualisation of biological information obtained through diverse imaging methods.
we discuss several cbe-based optimisation methods and compare our results to standard solutions.
cell broadband engine
the cell broadband engine is a microprocessor architecture developed by sony computer entertainment, toshiba and ibm to provide power-efficient and cost-effiective high-performance processing for a wide range of applications.
the first-generation cell processor combines a power processor element  with eight synergistic processor elements   <cit> .
the ppe contains a 64-bit powerpc architecture core  and can run 32- and 64-bit operating systems and applications.
each spe contains a risc core  which is optimised for computational intensive single-instruction-multiple-data  applications.
a single spe can perform up to eight single precision  operations per cycle so that all spes provide a theoretical peak performance of about  <dig> gflops.
all nine computational units communicate with each other, the main memory and i/o devices through the element interconnect bus , which provides a bandwidth of  <dig>  gbyte to each component and a total bandwidth of  <dig>  gbyte/sec  <cit> .
figure  <dig> shows an overview of the initial implementation of cell broadband engine.
there are various types of cell-based systems available, for example, ibm offers blades with two cell processors and several gbyte of ram, appropriate for high performance cluster computing.
sony released the playstation  <dig> game console, equipped with a low cost version of the cell processor.
this version contains seven operating spes  and only  <dig> mb ram  <cit> .
however its price  makes it attractive as an alternative high performance platform.
methods
this section is organised as follows: first we describe the pre-processing of typical 2d and 3d image datasets and then we give a brief description of the automatic multimodal alignment procedure.
the last subsection describes the implementation and optimisation of the algorithms to the cbe in detail.
image processing
the task of multimodal alignment is to register 2d images into a 3d image dataset.
the 2d dataset is given as  with  <dig> ≤ i < and  <dig> ≤ j < and the 3d dataset is given as as  with  <dig> ≤ i <,  <dig> ≤ j < and  <dig> ≤ k < with the same resolution as the 2d dataset.
if necessary, the images have to be adjusted to the same resolution by a pre-processing step.
the 2d dataset could be, for example, a cross-section cut, a 2d ct or a 2d pet slice; the 3d dataset could be, for example, a nmr dataset, a ct dataset or a 3d atlas.
multimodal alignment is a typical image analysis problem.
for the 2d/3d alignment presented here we assume that the direction at which the 2d image should be aligned is given, for example, by the experimental procedure.
without loss of generality, this direction is the z-direction of the 3d dataset.
however, if the direction is not given the algorithm could be easily extended to also find the correct direction, resulting in a heavily increased computing time.
the 2d/3d alignment procedure is divided into successive 2d/2d alignments.
a similarity function  determines for each slice k of the 3d dataset in z direction the optimal translation parameters in x and y direction and the optimal rotation-angle in the xy-plane of the image .
to determine the best parameters, all possible combinations of parameters within the search space were used for the calculation.
the highest similarity value depicts the optimal registration.
to reduce the effort, often the search space is restricted by prior knowledge.
in this study, we used a similarity function based on normalised mutual information, which is very suitable for registration of multimodal registration  <cit> .
given two probability distributions pt , pf  and the joint probability ptf  of target image t and floating image f, the normalised mutual information nmi is defined by means of the kullback-leibler measure  <cit> :
multimodal alignment procedure
the sequential alignments of the 2d slices require a high amount of computing time, because each alignment is independent from another and each parameter combination has to be calculated.
program listing  <dig>  shows the main routine of a sequential multimodal alignment implementation.
the execution time of each subroutine scales well with the size of the dataset so that the majority of the runtime is spent on the inner loop, respectively on the translate- and mutual-information procedures.
optimisations on both these code sections promise the best computation time speedups.
implementation on the cell broadband engine
to exploit the considerable performance of the cbe, architecture-specific properties have to be considered.
well-known sequential programs have to be re-designed and parallel concepts and new architecture-specific restrictions have to be taken into account.
using these features it is possible to obtain optimisation results close to the peak performance of the processor  <cit> .
in the case of our implementation we achieved significant improvements by following these rules:
<dig>  schedule the tasks onto all cores
<dig>  avoid scalars and use vectors instead
<dig>  eliminate and reduce branches on the spe-code
<dig>  avoid 32-bit integer multiplies on the spes
<dig>  manually unroll loops on the spe-code
<dig>  pay attention to the limited local storage of the spe
our algorithm consists of a multi-threaded alignment procedure with one thread for each available spe for the computing work and one manager thread on the ppe managing data-transfers, task-scheduling and i/o operations.
the application source code was implemented in c with simd extensions and spe intrinsics provided by ibm's software development kit  for multi-core acceleration  <cit> .
1) partitioning
the design of a parallel algorithm often requires an efficient partitioning of the computations between the available processing units.
in the case of the cbe it is recommended that the spes performs all heavy computational tasks and the ppe acts as a control unit to organise the task flow, i/o and data transfer operations  <cit> .
the first step in optimising the sequential multimodal alignment program was to break the tasks into discrete portions of work that can be distributed to all available spes.
due to the iterative structure of the algorithm, the 3d dataset can be easily decomposed such that each parallel task works on a portion  of the data.
the ppe organises a job queue to process a fixed amount of independent jobs and sends each spe one slice of the 3d dataset while there is still a slice left to align.
program listing  <dig>  shows a code fragment of the program running on the ppe which manages the task scheduling onto the spes.
in order to fully exploit the available power of the cell processor, the ppe should also be involved in the calculations.
this requires additional programming effort because the spes are much faster in processing than the ppe and they should be supplied immediately with new tasks to reduce unnecessary idling.
due to the excellent predictable performance of the spes  it is possible to stop the ppe calculations at a certain time and manage the job queue without major delays.
2) vectorisation
the main part of the cell processors performance lies in its spes, which are simd vector processors.
they achieve high performance by using large register files  and significant speedup can be achieved using simdisation .
for any given algorithm, vectorisation can usually be applied in different ways.
sometimes it is simple and intuitive to aggregate a set of variables into a vector and perform one operation on it instead of successive operations on each variable.
scalars, which are not appropriate for vectorisation, should be converted to quad-word vectors to avoid wasted instructions for loading and storing them  <cit> .
some compilers do auto-vectorisation, but their capabilities remain limited, so it is recommended to do this task manually.
ibms cell sdk provides several useful c/c++ language extensions, mainly vector data types and operations on these data types  <cit> .
we applied manual vectorisation to all time critical functions to achieve a higher overall performance on the cell spes.
program listing  <dig>  illustrates such a code modification using ibms sdk c language extensions  <cit> .
3) branch reduction
the spes do not provide dynamical branch prediction and a mis-predicted branch leads up to  <dig> wait cycles  <cit> .
to avoid this, static hint branch instructions can be used to indicate the fetch direction or the source code can be made branchless by computing all possible results and selecting the correct one  <cit> .
program listing  <dig>  shows an example of how to eliminate an expensive if-else condition.
this optimisation resulted in more code lines and more single calculations, but requires much less computation time on a spe.
therefore, variable execution times due to mis-predicted branches were eliminated, leading to very predictable spe calculation times.
4) avoidance of int <dig> multiplications
because the current spe contains only a  <dig> ×  <dig> bit multiplier, 32-bit integer multiplies requires four extra instructions  <cit> .
therefore unsigned shorts should be used if possible and arrays should have power-of-two size to avoid multiplication when indexing.
5) unrolling
the technique of loop unrolling provides significant performance improvements, as compilers can automatically schedule operations and optimise computations, if the algorithm consist of many independent operations  <cit> .
in particular nested loops have been unrolled manually to gain a considerably better performance.
it seems to be useful to try several levels of unrolling in order to find an optimal usage of the spe's large register file.
an example of a fourfold unrolled nested loop is shown in program listing  <dig> .
6) limited local storage of the spe
each synergistic processor element  has its own  <dig> kbyte ram for instructions and data which is called local storage   <cit> .
the spes can only execute code in the ls and only operate on data residing in this storage.
instead of direct main memory access, the spe has a programmable dma controller which performs transfers between main memory and ls  <cit> .
our goal for the high-performance implementation of multimodal alignment was to keep all memory requirements of a spe thread in the ls.
the size of our spe program is  <dig> kbyte.
in our application examples  each 2d-image and each 3d-slice is a  <dig> ×  <dig> 8-bit gray-value pixel image, thus we need about  <dig> kbyte for storing the data.
the approximately  <dig> kbyte left on the ls are sufficient to store intermediate results and temporary variables.
the advantage of this approach is that no additional data transfer is necessary.
RESULTS
evaluation platforms
the algorithms were implemented in c with special extensions for vector and simd purposes provided in ibms cbe sdk  <dig>   <cit> .
for performance tests we used a first-generation stand-alone ps <dig> as an inexpensive cell be platform  <cit> .
yellow dog linux  <dig>  with kernel  <dig> .23- <dig> was installed on the console and the source-code was compiled with the gnu c compiler  version  <dig> .
<dig>  the programs can be found as supplementary material additional file  <dig>
we compared the performance of our cbe-optimised alignment program to a message passing interface  parallelised version on a common quad-core opteron system  <cit> .
similar to the described partitioning optimisation for the cbe, the task was divided amongst all processor cores.
not surprisingly the performance scaled well with the number of used cores.
program listing  <dig>  shows the main routine of the mpi-parallelised multimodal alignment procedure.
we tested this implementation on a workstation equipped with two amd opteron  <dig> ,  <dig> gbyte ram and an open suse linux  <dig>  with kernel  <dig> .
<dig> .
on this platform we compiled the source-code with gcc  <dig> .
<dig>  and tested it with openmpi  <dig> .
<dig> and different amounts of parallel used cores.
evaluation example
in this study, we used two 3d nmr datasets of the male and female brain, freely available from the open access series of imaging studies  project  <cit> .
the dimensions of the 3d images were  <dig> ×  <dig> ×  <dig> voxel, an example of the data is shown in figure  <dig>  three modified slices of each nmr datasets and three different 2d pet scans , published by the national institute of aging  <cit> , were used for registrations on the brain data.
the 2d images were converted into gray-values and down-scaled to the respective resolution of the 3d dataset.
because of a given rough pre-alignment the search space could be constrained for the translation from - <dig> to + <dig> pixel and for the rotation-angle from -20° to +20°.
figure  <dig> shows an example of the multimodal registration of a 3d dataset  and an associated 2d image .
the results of the analysis are detailed below and shown in figures  <dig>   <dig> and  <dig>
optimisation results on the ps3
to realise the optimisation steps described above and access the high performance features of the cbe processor, we used a set of arithmetic, compare, logical scalar and mask intrinsics  <cit> .
a timer measured the period of the time-critical calculations in the alignment procedure.
the differences between the results for each optimisation-step  was an indicator for its effectiveness.
we repeated each benchmark-test several times with different combinations of the 3d and 2d images and compared the means of their computation time with each other.
1) partitioning
as a first step we distributed the calculations on all available processor cores .
at the beginning of the calculations, the ppe loaded the 3d volume and the 2d-image, created one thread for each spe and transferred via dma the 2d-image and disjunct nmr-slices to the spes.
after receiving them, the spes computed their local alignment and returned the alignment-parameters to the ppe which stored the best of these alignments.
this was repeated with the next layers of the volume until all slices had been processed.
not surprisingly, the execution time of the whole alignment scales well with the number of used spes .
because the sum of all transfer times took only a small fraction of the overall execution time, overlapped techniques such as double buffering were not implemented.
partitioned alignment, without further optimisations, required an average computation time of  <dig> seconds per nmr slice.
this is an average speedup of  <dig>  compared to a single-core opteron solution, but it does not exhaust the whole potential of the cbe processor.
2) vectorisation
the spes vector architecture requires vectorised source-code to achieve high performance  <cit> .
spes then have the ability to compute similar operations on several variables in each cycle.
we extensively transformed single variable operations to vector variable operations.
because of the recurring dataflow in the main computational routines  this was applicable in a straightforward manner.
the speedup of  <dig>  gained from this optimisation was surprisingly not an outstanding result but may relate to the powerful auto-vectorisation support of the gnu c compiler  <cit> .
however, manually implemented vectorisation provided a significant speed enhancement whereby the playstation  <dig> achieved an acceptable performance in comparison with modern standard processors.
in the case of our implementation, partitioning and vectorisation provides a speedup of  <dig>  compared to a single-core opteron, thus reaching the speed of a dual-core opteron version parallelised with mpi.
3) reduce branches and avoid int <dig> multiplications
as described in the method section, we implemented branchless code and reduced 32-bit integer multiplies as far as possible.
because the multimodal alignment functions contain many conditions , this technique raised the performance significantly.
branchless code with less int <dig> multiplications resulted in a speedup of  <dig>  compared to a single-core opteron solution.
4) explicit unroll
as a last optimisation step, we explicitly unrolled loops to benefit from the large register  on each spe.
the used gnu c compiler offers automatic loop unrolling mainly on simple loops , so in many cases a manual unrolling can result in considerable performance improvements.
in our evaluation example, two- and four-times unrolling led to only minor speedups.
a possible explanation besides existing compiler optimisations is that in most cases the spes registers were nearly completely filled by the assigned data in one single loop cycle; therefore no further significant speedup could be achieved by additional unrolling.
the tests using all optimisation steps show an average speedup of  <dig>  compared to a single-core opteron for the registration of a 2d pet scan.
figure  <dig> shows the benchmark results after each optimisation step with corresponding speedups.
it should be mentioned that the ppe also calculated alignments on some slices.
however, this reduced the overall execution only slightly.
we also investigated the performance of the ppe in comparison to one spe.
our tests show a speed advantage by a factor of four of the optimised spe source-code compared to a vectorised ppe version.
a performance comparison of the optimised cbe alignment program to the mpi-parallelised version is shown in figure  <dig>  the cbe program is nearly  as fast as the mpi-parallelised program computed on four opteron cores.
due to the strict data parallelism of our task a single core opteron reached only about a quarter and a dual core about a half of this performance.
this corresponds to an average speedup of  <dig>  of the optimised cbe alignment compared to the single-core opteron and of  <dig>  to the dual-core opteron, respectively.
ohara et al.
<cit>  reported a similar approach, where they implemented a mutual information based linear registration of monomodal 3d mri images.
the speedup factors in their study are lower ), but a direct comparison with our results ) is difficult.
in addition, their registration algorithm is based on matte's mutual information approach as implemented in insight imaging toolkit   <cit>  library.
however, this fast multi-resolution algorithm does not work well with specific nmr data such as nmr data of barley seeds which we are currently investigating.
discussion and
CONCLUSIONS
in this paper, we have presented a set of optimisation steps to accelerate the computation of a multimodal alignment, a typical image analysis problem, on the cell broadband engine in a playstation  <dig>  this platform seems to be an attractive solution for high performance computing due its considerable high peak performance and its low cost .
an optimised cbe application is very predictable in its execution time and with the knowledge of architecture-specific properties it is possible to reach nearly the peak performance of this processor.
the bottleneck in this algorithm is the computation of the nmi function, which requires most of the computing time.
there is only low communication as for typical image sizes  the program and data fit into the local storage area of the spes.
potential further developments would be the investigation of dma transfer effects for images of bigger size and comparison with other platforms such as graphics processing units.
developing efficient code for the cbe requires several optimisation techniques.
furthermore, the optimised source-code is not easily portable to other architectures.
nevertheless, the comparison with the average execution times on an opteron system shows that in case of our application the cbe processor in the playstation  <dig>  achieves an average speedup of  <dig>  compared to a single-core opteron.
it requires at least four physical opteron cores to reach the speed of the console.
considering the price of the quad-core amd processor  included in a basic workstation , the ps <dig> will meet their reputation as a low-cost high-performance computing platform.
therefore the applicability of the cell broadband engine for common problems in bioinformatics is of current interest and several approaches have been presented  <cit> .
we believe that this platform is an interesting alternative for fast multimodal alignments of 2d and 3d datasets and is able to speedup other tasks in image processing.
authors' contributions
rp and fs designed the study, ms implemented the method, ms, rp and fs analysed the results and wrote the paper, all authors read and approved the final manuscript.
supplementary material
additional file 1
yellow dog linux  <dig>  with kernel  <dig> .23- <dig> was installed on the console and the source-code was compiled with the gnu c compiler  version  <dig> .
<dig>
click here for file
acknowledgements
we would like to thank hendrik rohn for help producing figure  <dig>   <dig> and  <dig> with the 3d extension of the vanted software  <cit> .
this study was partly supported by grants bmbf 0315044a and dfg we 1608/2-1/ <dig>

 comprehensive understanding of biological structures requires sophisticated techniques in many areas such as the combination of 2d and 3d images or models of biological objects. examples are the integration of histological cross-sections providing structural information and development-specific distribution patterns of mrna, metabolite concentrations or enzyme activities into a 3d morphological framework, the combination of 2d computer tomography slices with a 3d atlas, or the integration of 2d positron emission tomography slices, providing information about metabolic activity, into a 3d nmr dataset, see figure for reconstruction and 3d visualisation these 2d cross-sections have to be registered at correct spatial positions in a 3d morphological framework. manual registration of cross-sections is tedious, subjective and very time-consuming. the accurate registration of images, obtained by diverse imaging techniques, requires automatic multimodal alignment techniques, which is an important research field in biological and medical image processing. such approaches determine the optimal spatial position on the base of suitable similarity functions, such as cross correlation or mutual information. registration by automatic procedures still requires extensive computational resources, so that fast algorithms and the implementation on parallel hardware would greatly enhance the feasibility of these investigations. the multi-core cell broadband engine allows fast parallel computation on eight cores per chip, presenting potential as a target for implementation of image registration algorithms. in this paper we implemented and evaluated a multimodal alignment approach based on mutual information on the cbe. the availability of the inexpensive cbe-driven playstation provides the opportunity to simultaneously align a high number of image stacks on a low-cost platform and therefore improves the automatic analysis and visualisation of biological information obtained through diverse imaging methods. we discuss several cbe-based optimisation methods and compare our results to standard solutions. cell broadband engine the cell broadband engine is a microprocessor architecture developed by sony computer entertainment, toshiba and ibm to provide power-efficient and cost-effiective high-performance processing for a wide range of applications. the first-generation cell processor combines a power processor element with eight synergistic processor elements. the ppe contains a 64-bit powerpc architecture core and can run 32- and 64-bit operating systems and applications. each spe contains a risc core which is optimised for computational intensive single-instruction-multiple-data applications. a single spe can perform up to eight single precision operations per cycle so that all spes provide a theoretical peak performance of about gflops. all nine computational units communicate with each other, the main memory and i/o devices through the element interconnect bus, which provides a bandwidth of gbyte to each component and a total bandwidth of gbyte/sec. figure shows an overview of the initial implementation of cell broadband engine. there are various types of cell-based systems available, for example, ibm offers blades with two cell processors and several gbyte of ram, appropriate for high performance cluster computing. sony released the playstation game console, equipped with a low cost version of the cell processor. this version contains seven operating spes and only mb ram. however its price makes it attractive as an alternative high performance platform. methods this section is organised as follows: first we describe the pre-processing of typical 2d and 3d image datasets and then we give a brief description of the automatic multimodal alignment procedure. the last subsection describes the implementation and optimisation of the algorithms to the cbe in detail. image processing the task of multimodal alignment is to register 2d images into a 3d image dataset. the 2d dataset is given as with ≤ i < and ≤ j < and the 3d dataset is given as as with ≤ i <, ≤ j < and ≤ k < with the same resolution as the 2d dataset. if necessary, the images have to be adjusted to the same resolution by a pre-processing step. the 2d dataset could be, for example, a cross-section cut, a 2d ct or a 2d pet slice; the 3d dataset could be, for example, a nmr dataset, a ct dataset or a 3d atlas. multimodal alignment is a typical image analysis problem. for the 2d/3d alignment presented here we assume that the direction at which the 2d image should be aligned is given, for example, by the experimental procedure. without loss of generality, this direction is the z-direction of the 3d dataset. however, if the direction is not given the algorithm could be easily extended to also find the correct direction, resulting in a heavily increased computing time. the 2d/3d alignment procedure is divided into successive 2d/2d alignments. a similarity function determines for each slice k of the 3d dataset in z direction the optimal translation parameters in x and y direction and the optimal rotation-angle in the xy-plane of the image. to determine the best parameters, all possible combinations of parameters within the search space were used for the calculation. the highest similarity value depicts the optimal registration. to reduce the effort, often the search space is restricted by prior knowledge. in this study, we used a similarity function based on normalised mutual information, which is very suitable for registration of multimodal registration. given two probability distributions pt, pf and the joint probability ptf of target image t and floating image f, the normalised mutual information nmi is defined by means of the kullback-leibler measure: multimodal alignment procedure the sequential alignments of the 2d slices require a high amount of computing time, because each alignment is independent from another and each parameter combination has to be calculated. program listing shows the main routine of a sequential multimodal alignment implementation. the execution time of each subroutine scales well with the size of the dataset so that the majority of the runtime is spent on the inner loop, respectively on the translate- and mutual-information procedures. optimisations on both these code sections promise the best computation time speedups. implementation on the cell broadband engine to exploit the considerable performance of the cbe, architecture-specific properties have to be considered. well-known sequential programs have to be re-designed and parallel concepts and new architecture-specific restrictions have to be taken into account. using these features it is possible to obtain optimisation results close to the peak performance of the processor. in the case of our implementation we achieved significant improvements by following these rules: schedule the tasks onto all cores avoid scalars and use vectors instead eliminate and reduce branches on the spe-code avoid 32-bit integer multiplies on the spes manually unroll loops on the spe-code pay attention to the limited local storage of the spe our algorithm consists of a multi-threaded alignment procedure with one thread for each available spe for the computing work and one manager thread on the ppe managing data-transfers, task-scheduling and i/o operations. the application source code was implemented in c with simd extensions and spe intrinsics provided by ibm's software development kit for multi-core acceleration. 1) partitioning the design of a parallel algorithm often requires an efficient partitioning of the computations between the available processing units. in the case of the cbe it is recommended that the spes performs all heavy computational tasks and the ppe acts as a control unit to organise the task flow, i/o and data transfer operations. the first step in optimising the sequential multimodal alignment program was to break the tasks into discrete portions of work that can be distributed to all available spes. due to the iterative structure of the algorithm, the 3d dataset can be easily decomposed such that each parallel task works on a portion of the data. the ppe organises a job queue to process a fixed amount of independent jobs and sends each spe one slice of the 3d dataset while there is still a slice left to align. program listing shows a code fragment of the program running on the ppe which manages the task scheduling onto the spes. in order to fully exploit the available power of the cell processor, the ppe should also be involved in the calculations. this requires additional programming effort because the spes are much faster in processing than the ppe and they should be supplied immediately with new tasks to reduce unnecessary idling. due to the excellent predictable performance of the spes it is possible to stop the ppe calculations at a certain time and manage the job queue without major delays. 2) vectorisation the main part of the cell processors performance lies in its spes, which are simd vector processors. they achieve high performance by using large register files and significant speedup can be achieved using simdisation. for any given algorithm, vectorisation can usually be applied in different ways. sometimes it is simple and intuitive to aggregate a set of variables into a vector and perform one operation on it instead of successive operations on each variable. scalars, which are not appropriate for vectorisation, should be converted to quad-word vectors to avoid wasted instructions for loading and storing them. some compilers do auto-vectorisation, but their capabilities remain limited, so it is recommended to do this task manually. ibms cell sdk provides several useful c/c++ language extensions, mainly vector data types and operations on these data types. we applied manual vectorisation to all time critical functions to achieve a higher overall performance on the cell spes. program listing illustrates such a code modification using ibms sdk c language extensions. 3) branch reduction the spes do not provide dynamical branch prediction and a mis-predicted branch leads up to wait cycles. to avoid this, static hint branch instructions can be used to indicate the fetch direction or the source code can be made branchless by computing all possible results and selecting the correct one. program listing shows an example of how to eliminate an expensive if-else condition. this optimisation resulted in more code lines and more single calculations, but requires much less computation time on a spe. therefore, variable execution times due to mis-predicted branches were eliminated, leading to very predictable spe calculation times. 4) avoidance of int multiplications because the current spe contains only a × bit multiplier, 32-bit integer multiplies requires four extra instructions. therefore unsigned shorts should be used if possible and arrays should have power-of-two size to avoid multiplication when indexing. 5) unrolling the technique of loop unrolling provides significant performance improvements, as compilers can automatically schedule operations and optimise computations, if the algorithm consist of many independent operations. in particular nested loops have been unrolled manually to gain a considerably better performance. it seems to be useful to try several levels of unrolling in order to find an optimal usage of the spe's large register file. an example of a fourfold unrolled nested loop is shown in program listing. 6) limited local storage of the spe each synergistic processor element has its own kbyte ram for instructions and data which is called local storage. the spes can only execute code in the ls and only operate on data residing in this storage. instead of direct main memory access, the spe has a programmable dma controller which performs transfers between main memory and ls. our goal for the high-performance implementation of multimodal alignment was to keep all memory requirements of a spe thread in the ls. the size of our spe program is kbyte. in our application examples each 2d-image and each 3d-slice is a × 8-bit gray-value pixel image, thus we need about kbyte for storing the data. the approximately kbyte left on the ls are sufficient to store intermediate results and temporary variables. the advantage of this approach is that no additional data transfer is necessary.  evaluation platforms the algorithms were implemented in c with special extensions for vector and simd purposes provided in ibms cbe sdk. for performance tests we used a first-generation stand-alone ps as an inexpensive cell be platform. yellow dog linux with kernel.23- was installed on the console and the source-code was compiled with the gnu c compiler version. the programs can be found as supplementary material additional file we compared the performance of our cbe-optimised alignment program to a message passing interface parallelised version on a common quad-core opteron system. similar to the described partitioning optimisation for the cbe, the task was divided amongst all processor cores. not surprisingly the performance scaled well with the number of used cores. program listing shows the main routine of the mpi-parallelised multimodal alignment procedure. we tested this implementation on a workstation equipped with two amd opteron, gbyte ram and an open suse linux with kernel.. on this platform we compiled the source-code with gcc. and tested it with openmpi. and different amounts of parallel used cores. evaluation example in this study, we used two 3d nmr datasets of the male and female brain, freely available from the open access series of imaging studies project. the dimensions of the 3d images were × × voxel, an example of the data is shown in figure three modified slices of each nmr datasets and three different 2d pet scans, published by the national institute of aging, were used for registrations on the brain data. the 2d images were converted into gray-values and down-scaled to the respective resolution of the 3d dataset. because of a given rough pre-alignment the search space could be constrained for the translation from - to + pixel and for the rotation-angle from -20° to +20°. figure shows an example of the multimodal registration of a 3d dataset and an associated 2d image. the results of the analysis are detailed below and shown in figures and optimisation results on the ps3 to realise the optimisation steps described above and access the high performance features of the cbe processor, we used a set of arithmetic, compare, logical scalar and mask intrinsics. a timer measured the period of the time-critical calculations in the alignment procedure. the differences between the results for each optimisation-step was an indicator for its effectiveness. we repeated each benchmark-test several times with different combinations of the 3d and 2d images and compared the means of their computation time with each other. 1) partitioning as a first step we distributed the calculations on all available processor cores. at the beginning of the calculations, the ppe loaded the 3d volume and the 2d-image, created one thread for each spe and transferred via dma the 2d-image and disjunct nmr-slices to the spes. after receiving them, the spes computed their local alignment and returned the alignment-parameters to the ppe which stored the best of these alignments. this was repeated with the next layers of the volume until all slices had been processed. not surprisingly, the execution time of the whole alignment scales well with the number of used spes. because the sum of all transfer times took only a small fraction of the overall execution time, overlapped techniques such as double buffering were not implemented. partitioned alignment, without further optimisations, required an average computation time of seconds per nmr slice. this is an average speedup of compared to a single-core opteron solution, but it does not exhaust the whole potential of the cbe processor. 2) vectorisation the spes vector architecture requires vectorised source-code to achieve high performance. spes then have the ability to compute similar operations on several variables in each cycle. we extensively transformed single variable operations to vector variable operations. because of the recurring dataflow in the main computational routines this was applicable in a straightforward manner. the speedup of gained from this optimisation was surprisingly not an outstanding result but may relate to the powerful auto-vectorisation support of the gnu c compiler. however, manually implemented vectorisation provided a significant speed enhancement whereby the playstation achieved an acceptable performance in comparison with modern standard processors. in the case of our implementation, partitioning and vectorisation provides a speedup of compared to a single-core opteron, thus reaching the speed of a dual-core opteron version parallelised with mpi. 3) reduce branches and avoid int multiplications as described in the method section, we implemented branchless code and reduced 32-bit integer multiplies as far as possible. because the multimodal alignment functions contain many conditions, this technique raised the performance significantly. branchless code with less int multiplications resulted in a speedup of compared to a single-core opteron solution. 4) explicit unroll as a last optimisation step, we explicitly unrolled loops to benefit from the large register on each spe. the used gnu c compiler offers automatic loop unrolling mainly on simple loops, so in many cases a manual unrolling can result in considerable performance improvements. in our evaluation example, two- and four-times unrolling led to only minor speedups. a possible explanation besides existing compiler optimisations is that in most cases the spes registers were nearly completely filled by the assigned data in one single loop cycle; therefore no further significant speedup could be achieved by additional unrolling. the tests using all optimisation steps show an average speedup of compared to a single-core opteron for the registration of a 2d pet scan. figure shows the benchmark results after each optimisation step with corresponding speedups. it should be mentioned that the ppe also calculated alignments on some slices. however, this reduced the overall execution only slightly. we also investigated the performance of the ppe in comparison to one spe. our tests show a speed advantage by a factor of four of the optimised spe source-code compared to a vectorised ppe version. a performance comparison of the optimised cbe alignment program to the mpi-parallelised version is shown in figure the cbe program is nearly as fast as the mpi-parallelised program computed on four opteron cores. due to the strict data parallelism of our task a single core opteron reached only about a quarter and a dual core about a half of this performance. this corresponds to an average speedup of of the optimised cbe alignment compared to the single-core opteron and of to the dual-core opteron, respectively. ohara et al. reported a similar approach, where they implemented a mutual information based linear registration of monomodal 3d mri images. the speedup factors in their study are lower ), but a direct comparison with our results ) is difficult. in addition, their registration algorithm is based on matte's mutual information approach as implemented in insight imaging toolkit library. however, this fast multi-resolution algorithm does not work well with specific nmr data such as nmr data of barley seeds which we are currently investigating. discussion and  in this paper, we have presented a set of optimisation steps to accelerate the computation of a multimodal alignment, a typical image analysis problem, on the cell broadband engine in a playstation this platform seems to be an attractive solution for high performance computing due its considerable high peak performance and its low cost. an optimised cbe application is very predictable in its execution time and with the knowledge of architecture-specific properties it is possible to reach nearly the peak performance of this processor. the bottleneck in this algorithm is the computation of the nmi function, which requires most of the computing time. there is only low communication as for typical image sizes the program and data fit into the local storage area of the spes. potential further developments would be the investigation of dma transfer effects for images of bigger size and comparison with other platforms such as graphics processing units. developing efficient code for the cbe requires several optimisation techniques. furthermore, the optimised source-code is not easily portable to other architectures. nevertheless, the comparison with the average execution times on an opteron system shows that in case of our application the cbe processor in the playstation achieves an average speedup of compared to a single-core opteron. it requires at least four physical opteron cores to reach the speed of the console. considering the price of the quad-core amd processor included in a basic workstation, the ps will meet their reputation as a low-cost high-performance computing platform. therefore the applicability of the cell broadband engine for common problems in bioinformatics is of current interest and several approaches have been presented. we believe that this platform is an interesting alternative for fast multimodal alignments of 2d and 3d datasets and is able to speedup other tasks in image processing. authors' contributions rp and fs designed the study, ms implemented the method, ms, rp and fs analysed the results and wrote the paper, all authors read and approved the final manuscript. supplementary material additional file 1 yellow dog linux with kernel.23- was installed on the console and the source-code was compiled with the gnu c compiler version. click here for file acknowledgements we would like to thank hendrik rohn for help producing figure and with the 3d extension of the vanted software. this study was partly supported by grants bmbf 0315044a and dfg we 1608/2-1/ 
more information and the source code are available from http://cbe.ipk-gatersleben.de. the cell broadband engine, a heterogeneous multi-core processor, provides power-efficient and cost-effective high-performance computing. we show how a typical image analysis and visualisation problem, the multimodal registration of 2d cross-sections and 3d datasets, benefits from the multi-core based implementation of the alignment algorithm. the results demonstrate that the cbe processor in a playstation accelerates computational intensive multimodal registration, which is of great importance in biological/medical image processing. we discuss several cbe-based optimisation methods and compare our results to standard solutions. we evaluate the cbe-driven playstation as a high performance, cost-effective computing platform by adapting a multimodal alignment procedure to several characteristic hardware properties. recent trends in processor architecture combine multiple cores into a single chip to improve overall performance. one application area is image analysis and visualisation, in particular registration of 2d cross-sections into 3d image datasets. the playstation as a low cost cbe-based platform offers an efficient option to conventional hardware to solve computational problems in image processing and bioinformatics. the optimisations are based on partitioning, vectorisation, branch reducing and loop unrolling techniques with special attention to 32-bit multiplies and limited local storage on the computing units.
 solving bioinformatics tasks often requires extensive computational power. recent trends in processor architecture combine multiple cores into a single chip to improve overall performance. the cell broadband engine, a heterogeneous multi-core processor, provides power-efficient and cost-effective high-performance computing. one application area is image analysis and visualisation, in particular registration of 2d cross-sections into 3d image datasets. such techniques can be used to put different image modalities into spatial correspondence, for example, 2d images of histological cuts into morphological 3d frameworks.  we evaluate the cbe-driven playstation as a high performance, cost-effective computing platform by adapting a multimodal alignment procedure to several characteristic hardware properties. the optimisations are based on partitioning, vectorisation, branch reducing and loop unrolling techniques with special attention to 32-bit multiplies and limited local storage on the computing units. we show how a typical image analysis and visualisation problem, the multimodal registration of 2d cross-sections and 3d datasets, benefits from the multi-core based implementation of the alignment algorithm. we discuss several cbe-based optimisation methods and compare our results to standard solutions. more information and the source code are available from http://cbe.ipk-gatersleben.de.  the results demonstrate that the cbe processor in a playstation accelerates computational intensive multimodal registration, which is of great importance in biological/medical image processing. the playstation as a low cost cbe-based platform offers an efficient option to conventional hardware to solve computational problems in image processing and bioinformatics. 