This research addresses a high-speed computation method for the Kleene star of the weighted adjacency matrix in a max-plus algebraic system. We focus on systems whose precedence constraints are represented by a directed acyclic graph and implement it on a Cell Broadband EngineTM (CBE) processor. Since the resulting matrix gives the longest travel times between two adjacent nodes, it is often utilized in scheduling problem solvers for a class of discrete event systems. This research, in particular, attempts to achieve a speedup by using two approaches: parallelization and SIMDization (Single Instruction, Multiple Data), both of which can be accomplished by a CBE processor. The former refers to a parallel computation using multiple cores, while the latter is a method whereby multiple elements are computed by a single instruction. Using the implementation on a Sony PlayStation 3TM equipped with a CBE processor, we found that the SIMDization is effective regardless of the system's size and the number of processor cores used. We also found that the scalability of using multiple cores is remarkable especially for systems with a large number of nodes. In a numerical experiment where the number of nodes is 2000, we achieved a speedup of 20 times compared with the method without the above techniques.

Existing multimedia processors having millions of transistors are not suitable for portable multimedia services and existing fixed-point DSP chips having fixed data formats are not appropriate for multimedia applications. This paper proposes a multimedia fixed-point DSP (MDSP) chip for portable multimedia services and its chip implementation. MDSP employs parallel processing techniques, such as SIMD, vector processing, and DSP techniques. MDSP can handle 8-, 16-, 32- or 40-bit data and can perform two MAC operations in parallel. In addition, MDSP can complete two vector operations with two data movements in a cycle. With these features, MDSP can handle both 2-D video signal processing and 1-D signal processing. The prototype MDSP chip has 68,831 gates, has been fabricated, and is running at 30 MHz.