![[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
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 Column-direction CDP loads a line of a reference image and calculates di(j,k,l). di(j-1,k,l) is required to calculate di(j,k,l), but other local paths are not required. Therefore, we holds the area for di(j,k,l) and di(j-1,k,l) in the LS. After calculating di(j,k,l), Di(j,k,l) is calculated. Only Di(j-1,k,l) is required to calculate Di(j,k,l) and other accumulative paths are not required to hold. In the case of 82x84 reference image and 136x200 input image, memory consumption for local paths and accumulative paths are reduced from 9MB to 0.22MB and it can be stored in the 256KB LS.
