![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
Title: Optimizing Two-Dimensional Continuous Dynamic Programming for Cell Broadband Engine Processors.
Authors: Shin-ya Iwazaki, Yuichi Okuyama, Ken-ichi Kuroda, and other
1. Introduction
A Two-Dimensional Continuous Dynamic Programming (2DCDP) is a specialized DP matching method for an image recognition. There are 2 advantages of a 2DCDP. A 2DCDP is tolerant of skew and misalignment matching because of non-linear enlargement or reduction of one image. In addition, a 2DCDP automatically segments an object which are matched with an image. One of the expectations by a 2DCDP is an object tracking in a movie. However, a movie per second consists of 30 image frames, and it means that an image matching for each image frame must be done within 0.03 seconds if we consider a real-time object tracking. Modern computers which have a general purpose processors can not achieve in real-time.
A Cell Broadband Engine processor (Cell processor) is a heterogeneous multi-core processor developed by STI, an alliance of SONY, TOSHIBA, and IBM. A Cell processor has a potential of the performance for not only multimedia processing but also scientific computing. In addition, a Cell processor is included in a SONY PLAYSTATION3 (PS3) and the linux OS and the software development kit which runs on a PS3 is opened to the public. Therefore, we can obtain the high-performance computer in the lower price than other computers whose performance are same to PS3.
In this paper, we present our approach to optimizing a 2DCDP to achieve a real-time object tracking in a movie. We choose a PS3 which includes a Cell processor as a platform and optimize a 2DCDP problem for a PS3.
This paper is organized as follows;
2 2DCDP
3 Cell processor
3.1 An overview of a Cell processor
The first generation Cell processor consists of a Power Processor Element (PPE) and eight Synergistic Processor Elements (SPEs). A PPE and an SPE are different types of an architecture. Although the performance of each processor element is not higher than recent general processor because each processor element does not have an out-of-order execution unit and a dynamic branch predictor, it is possible to get the high performance by vectorizing a program using SIMD instructions and parallelizing to all of SPEs. Each processing element and I/O devices are connected by a four-ring structured Element Interconnect Bus (EIB).
3.2 PPE
A PPE is based on 64-bit multi-threaded Power Architecture. A PPE runs an OS and organizes whole execution in SPEs.
3.3 SPE
An SPE consists of a Synergistic Processor Unit (SPU) and a Memory Follow Controller (MFC) and it is a different architecture from a PPE. An SPU contains 128 elements of 128-bit registers, and it can execute a vectorized program by using SIMD instructions. In addition, an SPU can issue a pair of an odd and even instructions at once. An SPU holds 256KB scratchpad memory called as a Local Store (LS) instead of a cache. Each SPU holds its own local address space and can not access to the main memory directly. An MFC provides a DMA transfer to send/receive the data between the main memory and the LS. An MFC also provides a mailbox and signal-notification for a communication between a PPE and an SPE or an SPE and another SPE.
3.4 I/O
The main memory adopts 
R DRAM and its bandwidth is 25.6GB/sec. The main memory is connected to Memory Interface Controller (MIC), and the MIC and other devices are connected with EIB.
3.5 An advantage and disadvantage of a Cell processor
Optimizing a program for a Cell processor is necessary to get a high-performance of a Cell processor. First, an original program is parallelized to SPEs, and it is vectorized by using SIMD instructions. On the other hands, an SPE does not have out-of-order execution unit and a dynamic branch predictor. With lack of these units in mind, we need to optimize a program; for example, eliminating a branch instruction and replace to compare and select instructions, etc.
3.6 PLAYSTATION3
PS3 is a video game machine which includes a Cell processor, but we can get some Linux operating systems which are designed for PS3 (Fedora, Yellow Dog, etc), and the software development kit is also opened to the public. A Cell processor in a PS3 consists of a PPE and eight SPEs, but the user can use a PPE and six SPEs.
4 Optimizing 2DCDP for a Cell processor
4.1 An overview of the optimization
We adopt a PS3 to optimize 2DCDP. A PS3 includes a Cell processor and 256MB main memory. The current implementation keeps all of the local distance and accumulative distance which are calculated in the column-direction CDP and row-direction CDP. However, the size of an LS in each SPE is limited to 256KB. In addition, the main memory in a PS3 is 256MB, but we can use about 180MB because the OS and other application use about 70MB of the main memory. Therefore, the size of all data must be kept below 180MB because the swap will be occured if the size is over the size of main memory.
Optimizing 2DCDP for a Cell processor, we divide 2DCDP into three modules. The first module is a role of a column-direction CDP, the second module is a role of row-direction CDP, and the third module is a role of backtrace. First, a module of a column-direction CDP runs on five SPEs and a module of row-direction CDP runs on an SPE, and these are executed in parallel. After the most right row is decided in row-direction CDP, backtrace module is executed with six SPEs. In the implementation by Iwasa et al., double type is used for calculation of the luminance. However, an SPE can execute for only two of double data because an SPE execute for 128bytes data by SIMD instructions. Therefore, we convert all of double data to float data, and we can calculate for four data at once. In addition, the current implementation of 2DCDP includes many branches. We replace the branch instructions with the compare and select instructions. By eliminating the branch instructions, we can avoid the penalty caused by branch miss stall.
4.2 Column-direction CDP module
4.2.1 Optimizing consumption of the memory
4.2.2 Vectorizing by SIMD instructions
Column-direction CDP calculates the luminance of local paths, and determines the accumulative path from 7 local paths. The first part of column-direction CDP calculates di(j,k,l), di(j,k,l+1),di(j,k,l+2),di(j,k,l+3) at once by using SIMD instructions. The next part select the optimal local path path from 7 local paths as an accumulative path. To select the optimal local path, compare and select instructions are used except of branch instruction to avoid the branch miss penalty.
4.2.3 Parallelizing with multiple SPEs
The order of column-direction CDP is O(IxJxKxL) and it is the maximum execution time of three modules. Column-direction CDP is parallelized with five SPEs because another SPE will be used by row-direction CDP at the same time. The program is parallelized in loop i level because there is a data dependence between loop j and loop j-1. By the parallelization, the order of column-direction CDP per each SPE will decrease O(I/5xJxKxL)
4.3 Row-direction CDP module
4.3.1 Optimizing consumption of the memory
Row-direction CDP module calculates its accumulative path by using its local paths calculated in column-direction CDP. The result of column-direction CDP module (Di(J,k,l) to Di+4(J,k,l)) will be the local path(dd(i,k,l) to dd(i+4,k,l)) in row-direction CDP. Therefore, row-direction CDP module assigns four lines of dd. In addition, row-direction CDP is required to save all of the accumulative paths and its spot points which correspond to the most right row. Accumulative paths are recorded in RPath and the spot points are recorded in RSpot as same as CPath in column-direction CDP.
4.3.2 Vectorizing by SIMD instructions
In row-direction CDP module, the local paths are not required to calculate because the local paths depend on the accumulative paths in column-direction CDP. Therefore, row-direction CDP calculates the accumulative paths by using SIMD instructions.
4.3.3 Parallelizing with multiple SPEs
Row-direction CDP runs with column-direction CDP in parallel. Column-direction CDP runs on five SPEs, therefore, row-direction CDP runs on an SPE. During row-direction CDP calculates DD(i,k,l) to DD(i+4,k,l), column-direction CDP calculates Di+5(j,k,l) to Di+9(j,k,l).
4.4 Backtrace module
4.4.1 Optimizing consumption of the memory
Backtrace module calculates the correspond of a reference image to an input image. Using RPath and RSpot recorded in row-direction CDP and CPath recorded in column-direction CDP, backtrace module records the column-direction spots which corresponds to the reference image. The points of the spot are recorded in CSpot as same as RSpot.
4.4.2 Parallelizing with multiple SPEs.
Backtrace module is executed after column-direction CDP and row-direction CDP. Therefore, backtrace module can use all of six SPEs. Backtrace module is parallelized in loop i because there is a data dependence between loop j and loop j-1 as same as column-direction CDP. The order of the computation will be O(JxI/6) from O(JxI).
5. Evaluation
5.1 An overview of the evaluation
To evaluate the optimized 2DCDP for a Cell processor, we compare with the original implementation running on an Intel Pentium4 processor. We adopts the reference image and input image from Video Database for Evaluating Video Processing. The size of the reference image is 82x84 pixels and the size of the input image is 136x200 pixels. Therefore, I=84, J=82, K=136, and L=200.
6. Conclusion
In this paper, we optimized a 2DCDP which has been proposed as a simultaneous processing algorithm of seqmentation and recognition for a Cell processor. There are 2 main problems of a 2DCDP; one is a huge order of the computation and a huge amount of the memory consumption. For the huge order of the computation, we optimized by vectorizing by SIMD instructions, parallelizing with multiple SPEs, loop unrolling, eliminating branch instructions, double buffering of DMA transfers, etc. For the huge amount of the memory consumption, we optimized by reduction of recorded data and contriving the data structure.
An amount of char-type arrays which record accumulative paths is decreased from 187MB to 94MB by assign the information of 2 paths per one element. By this optimization, the total consumption of the memory is decreased from 200MB to 110MB. To calculate the local paths and accumulative paths in column-direction and row-direction CDP, we vectorized by SIMD instructions. We assigned five SPEs for a column-direction CDP module and an SPE for a row-direction CDP module, and they are executed in parallel. After column-direction and row-direction CDP modules, a backtrace module is executed in parallel with six SPEs. These optimization shown above decreases the execution time from 44.45 seconds to 1.97 seconds and 22.6 times faster than the original implementation.
