![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
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.
