![[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 about 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, remove 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 removing 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.
