Compilation Techniques for Multimedia Processors

The huge processing power needed by multimedia applications has led to multimedia extensions in the instruction set of microprocessors which exploit subword parallelism. Examples of these extended instruction sets are the Visual Instruction Set of the UltraSPARC processor, the AltiVec instruction set of the PowerPC processor, the MMX and ISS extensions of the Pentium processors, and the MAX-2 instruction set of the HP PA-RISC processor. Currently, these extensions can only be used by programs written in assembly language, through system libraries or by calling specialized macros in a high-level language. Therefore, these instructions are not used by most applications. We propose two code generation techniques to produce native code using these multimedia extensions for programs written in a high-level language: classical vectorization and vectorization by unrolling. Vectorization by unrolling is simpler than classical vectorization since data dependence analysis is reduced to acyclic control flow graph analysis. Furthermore, we address the problem of unaligned memory accesses. This can be handled by both static analysis and dynamic runtime checking. Preliminary experimental results for a code generator for the UltraSPARC VIS instruction set show that speedups of up to a factor of 4.8 are possible, and that vectorization by unrolling is much simpler but as effective as classical vectorization.     

无线MMX技术在MPEG-4中的应用

无线MMX(Wireless MMX Technology)是用来提高移动多媒体计算性能的技术。针对无线视频通信的应用，研究了采用无线MMX来实现MPEG-4视频编解码的技术；通过对无线MMX体系结构和指令特点的分析，从指令优化和算法优化两方面给出了MPEG-4编解码器优化的关键策略。经过优化的编解码器可很好地满足无线视频通信要求。     

Optimizing mobile multimedia using SIMD techniques

Demand for mobile video applications is growing today in wireless handheld platforms. Optimizing instruction set architectures and employing SIMD techniques is a logical approach towards attaining higher performance in mobile multimedia applications. Intel® Wireless MMX? technology has been designed to accelerate mobile multimedia and applications processing in a power efficient manner. This paper provides an overview of Intel® Wireless MMX? technology, a 64-bit Single Instruction Multiple Data (SIMD) coprocessor for the Intel® XScale® microarchitecture, and the key features of the architecture that specifically enhance the multi-media performance. Tools and techniques for optimization are also described.     

Efficient multimedia coprocessor with enhanced SIMD engines for exploiting ILP and DLP

Multimedia applications have become increasingly important in daily computing. These applications are composed of heterogeneous regions of code mixed with data-level parallelism (DLP) and instruction-level parallelism (ILP). A standard solution for a multimedia coprocessor resembles of single-instruction multiple-data (SIMD) engines into architectures exploiting ILP at compile time, such as very long instruction word (VLIW) and transport triggered architecture (TTA). However, the ILP regions fail to scale with the increased vector length to achieve high performance in the DLP regions. Furthermore, the register-to-register nature of SIMD instructions causes current SIMD engines to have limitations in handling memory alignment, data reorganization, and control flow. Many supporting instructions such as data permutations, address generations, and loop branches, are required to aid in the execution of the real SIMD computation instructions. To mitigate these problems, we propose optimized SIMD engines that have the capabilities for combining VLIW or TTA processing with a unified scalar and long vector computations as well as efficient SIMD hardware for real computation. Our new architecture is based on TTA and is called multimedia coprocessor (MCP). This architecture includes following features: (1) a simple coprocessor structure with 8-way TTA, (2) cost-effective SIMD hardware capable of performing floating-point operations, (3) long vector capabilities built upon existing SIMD hardware and a single register file and processor data path for both scalar operands and vector elements, and (4) an optimized SIMD architecture that addresses the SIMD limitations. Our experimental evaluations show that MCP can outperform conventional SIMD techniques by an average of 39% and 12% in performance for multimedia kernels and applications, respectively.     

Architectural support for thread communications in multi-core processors

In the ongoing quest for greater computational power, efficiently exploiting parallelism is of paramount importance. Architectural trends have shifted from improving single-threaded application performance, often achieved through instruction level parallelism (ILP), to improving multithreaded application performance by supporting thread level parallelism (TLP). Thus, multi-core processors incorporating two or more cores on a single die have become ubiquitous. To achieve concurrent execution on multi-core processors, applications must be explicitly restructured to exploit parallelism, either by programmers or compilers. However, multithreaded parallel programming may introduce overhead due to communications among threads. Though some resources are shared among processor cores, current multi-core processors provide no explicit communications support for multithreaded applications that takes advantage of the proximity between cores. Currently, inter-core communications depend on cache coherence, resulting in demand-based cache line transfers with their inherent latency and overhead. In this paper, we explore two approaches to improve communications support for multithreaded applications. Prepushing is a software controlled data forwarding technique that sends data to destination’s cache before it is needed, eliminating cache misses in the destination’s cache as well as reducing the coherence traffic on the bus. Software Controlled Eviction (SCE) improves thread communications by placing shared data in shared caches so that it can be found in a much closer location than remote caches or main memory. Simulation results show significant performance improvement with the addition of these architecture optimizations to multi-core processors.     

A multi-streaming SIMD multimedia computing engine

Current multimedia extensions provide a mechanism for general-purpose processors to meet the growing performance demand of multimedia applications. However, the computing performance of these extensions is often limited for the design conceptions of the single data stream. This paper presents an architecture called “multi-streaming SIMD” that enables current multimedia extensions to simultaneously manipulate multiple data streams. To efficiently and flexibly realize the proposed architecture, an operation cell is designed by fusing the logic gates and the storage cells together. Multiple operation cells then are connected to compose a register file with the ability of performing SIMD operations called “Multimedia Operation Storage Unit (MOSU)”. Further, many MOSUs are used to compose a multi-streaming SIMD computing engine that can simultaneously manipulate multiple data streams and exploit the subword parallelisms of the elements in each data stream. This paper also designs three instruction modes (global, coupling, and isolated modes) for programmers to dynamically configure the multi-streaming SIMD computing engine at the instruction level to manipulate different amounts of data streams. Simulation results show that when the multi-streaming SIMD architecture has four 4-register MOSUs, it provides a factor of 3.3×–5.5× performance enhancement for traditional MMX extensions on 12 multimedia kernels.     

WMMX技术及应用

随着无线技术的发展进步,手持设备如PDA等有了更广泛的应用空间,要求在Wireless网络以及多媒体方面的性能必须有大幅度提高.在Intel 2004年4月发布的PXA 27x处理器中,新加入的WMMX技术是其降低能耗与提高媒体程序效率的关键技术,专门用于在无线网络环境以及多媒体应用场合下增强代码效率.在介绍了WMMX技术的要点、同MMX与SSE的兼容性、编程模型等之外,演示了如何将WMMX技术在2Dgraphics场合下进行应用以提高系统对Bitmap进行操作的性能.     

A multilevel computing architecture for embedded multimedia applications

We have designed a new architecture that simplifies integration of heterogeneous IP for multimedia and streaming applications. The multilevel computing architecture (MLCA) is a template architecture featuring multiple processing units. This template architecture for SOC systems uses superscalar techniques to exploit task-level parallelism among different processing units. It supports a natural programming model that relieves programmers from explicitly synchronizing tasks and communicating data. code transformations that improve application performance are easy to incorporate in compilers for this architecture.     

一种SIMD优化中的向量寄存器部分重用方法

SIMD架构用于多媒体加速,已经广泛应用于现代通用处理器中.SIMD架构的数据并行性可大大提高处理器的运算能力,但由于存储系统的速度远远不能与其匹配,使得应用程序的性能很难获得进一步的提高.因此,本文基于SIMD架构的访存特性,提出了一种向量寄存器部分重用的方法,以提高访存效率;并给出了相应的程序转换算法,通过数据相关性的分
分析,在应用程序向量化时,生成采用向量寄存器部分重用的优化代码.实验结果说明,该算法对多媒体应用程序的性能有显著的提高.     

Optimizing image processing on multi-core CPUs with Intel parallel programming technologies

The rapid advance of computer hardware and popularity of multimedia applications enable multi-core processors with sub-word parallelism instructions to become a dominant market trend in desk-top PCs as well as high end mobile devices. This paper presents an efficient parallel implementation of 2D convolution algorithm demanding high performance computing power in multi-core desktop PCs. It is a representative computation intensive algorithm, in image and signal processing applications, accompanied by heavy memory access; on the other hand, their computational complexities are relatively low. The purpose of this study is to explore the effectiveness of exploiting the streaming SIMD (Single Instruction Multiple Data) extension (SSE) technology and TBB (Threading Building Block) run-time library in Intel multi-core processors. By doing so, we can take advantage of all the hardware features of multi-core processor concurrently for data- and task-level parallelism. For the performance evaluation, we implemented a 3?×?3 kernel based convolution algorithm using SSE2 and TBB with different combinations and compared their processing speeds. The experimental results show that both technologies have a significant effect on the performance and the processing speed can be greatly improved when using two technologies at the same time; for example, 6.2, 6.1, and 1.4 times speedup compared with the implementation of either of them are suggested for 256?×?256, 512?×?512, and 1024?×?1024 data sets, respectively.     

一种基于代价子图的子字并行指令选择算法

子字并行能够充分利用多媒体算法的数据精度小、内部循环处理形式规则的特点,是加速多媒体处理的有效方式。然而,如何充分挖掘多媒体应用中的子字并行仍然是一个难题。本文说明传统的并行技术可以有效地开发循环中的子字并行性,同时提出一种基于代价子图的子字并行指令自动识别的方法。与其他方法相比,该方法利用代价模型对子子字并行指令选择进行定量评估。本文在TTA体系结构框架下实现了这一方法。实验结果表明,该方法可以充分地提取循环中的子字并行性。     

Challenges to combining general-purpose and multimedia processors

Multimedia processor media extensions to general purpose processors present new challenges to the compiler writer, language designer, and microarchitect. Multimedia workloads have always held an important role in embedded applications, such as video cards or set top boxes, but these workloads are becoming increasingly common in general purpose computing as well. Over the past three years the major vendors of general purpose processors (GPPs) have announced extensions to their instruction set architectures that supposedly enhance the performance of multimedia workloads. These include North Carolina MAX 2 extensions to Hewlett-Packard PA-RISC, MMX for Intel's x86, UltraSparc's VIS, and MDMX extensions to MIPS V. Merging these new multimedia instructions with existing GPPs poses several challenges. Also, some doubt remains as to whether multimedia extensions are a real development or just a competition induced fad in the GPP industry. If it is indeed a development, how must current processor microarchitectures change in reaction? And if they change, can GPPs and MMPs apply application specific integrated circuit (ASIC) solutions to the same problems?     

Avoiding Conversion and Rearrangement Overhead in SIMD Architectures

Single-Instruction Multiple-Data (SIMD) instructions provide an inexpensive way to exploit the Data-Level Parallelism in multimedia applications. However, the performance improvement obtained by employing SIMD instructions is often limited because frequently many overhead instructions are required to bring data in a form amenable to SIMD processing. In this paper, we employ two techniques to overcome this limitation. The first technique, extended subwords, uses four extra bits for every byte in a media register. This allows many SIMD operations to be performed without overflow and avoids packing/unpacking conversion overhead. The second technique, Matrix Register File (MRF), allows flexible row-wise as well as column-wise access to the register file. It is useful for many two-dimensional multimedia algorithms such as the (I) Discrete Cosine Transform, 2 × 2 Haar Transform, and pixel padding. In addition, we propose a few new media instructions. Experimental results obtained by extending the SimpleScalar toolset show that these techniques improve performance by up to a factor of 4.5 compared to a conventional SIMD instruction set extension.     

Embedded GPU and multicore processors for emotional-based mobile robotic agents

Control architectures based on emotions are becoming promising solutions for the implementation of future robotic systems. The basic controllers of this architecture are the emotional processes that decide which behaviors the robot must activate to fulfill the objectives. The number of emotional processes increases (hundreds of millions/s) with the complexity level of the application, limiting the processing capacity of a main processor to solve the complex problems. Fortunately, the potential parallelism of emotional processes permits their execution in parallel, hence enabling the computing power to tackle the complex dynamic problems. In this paper, Graphic Processing Unit (GPU), multicore processors and single instruction multiple data (SIMD) instructions are used to provide parallelism for the emotional processes. Different GPUs, multicore processors and SIMD instruction sets are evaluated and compared to analyze their suitability to cope with robotic applications. The applications are set-up taking into account different environmental conditions, robot dynamics and emotional states. Experimental results show that, despite the fact that GPUs have a bottleneck in the data transmission between the host and the device, the evaluated GTX 670 GPU provides a performance of more than one order of magnitude greater than the initial implementation of the architecture on a single core. Thus, all complex proposed application problems can be solved using the GPU technology in contrast to the first prototype where only 55% of them could be solved. Using AVX SIMD instructions, the performance of the architecture is increased in 3.25 times in relation to the first implementation. Thus, from the 27 proposed applications about 88.8% are solved. In the case of the SSE SIMD instructions, the performance is almost doubled and the robot could solve about 74% of the proposed application problems. The use of AVX and SSE SIMD instructions provides almost the same performance as a quad- and a dual-core, respectively, with the advantage that they do not add any additional hardware cost.     

AltiVec extension to PowerPC accelerates media processing

There is a clear trend in personal computing toward multimedia-rich applications. These applications will incorporate a wide variety of multimedia technologies, including audio and video compression, 2D image processing, 3D graphics, speech and handwriting recognition, media mining, and narrow/broadband signal processing for communication. In response to this demand, major microprocessor vendors have announced architectural extensions to their general-purpose processors in an effort to improve their multimedia performance. Intel extended IA-32 with MMX and SSE (alias KNI), Sun enhanced Sparc with VIS, Hewlett-Packard added MAX to its PA-RISC architecture, Silicon Graphics extended the MIPS architecture with MDMX, and Digital (now Compaq) added MVI to Alpha. This article describes the most recent, and what we believe to be the most comprehensive, addition to this list: PowerPC's AltiVec, AltiVec speeds not only media processing but also nearly any application in which data parallelism exists, as demonstrated by a cycle-accurate simulation of Motorola's MPC 7400, the heart of Apple G4 systems     

A high‐performance sorting algorithm for multicore single‐instruction multiple‐data processors

Many sorting algorithms have been studied in the past, but there are only a few algorithms that can effectively exploit both single‐instruction multiple‐data (SIMD) instructions and thread‐level parallelism. In this paper, we propose a new high‐performance sorting algorithm, called aligned‐access sort (AA‐sort), that exploits both the SIMD instructions and thread‐level parallelism available on today's multicore processors. Our algorithm consists of two phases, an in‐core sorting phase and an out‐of‐core merging phase. The in‐core sorting phase uses our new sorting algorithm that extends combsort to exploit SIMD instructions. The out‐of‐core algorithm is based on mergesort with our novel vectorized merging algorithm. Both phases can take advantage of SIMD instructions. The key to high performance is eliminating unaligned memory accesses that would reduce the effectiveness of SIMD instructions in both phases. We implemented and evaluated the AA‐sort on PowerPC 970MP and Cell Broadband Engine platforms. In summary, a sequential version of the AA‐sort using SIMD instructions outperformed IBM's optimized sequential sorting library by 1.8 times and bitonic mergesort using SIMD instructions by 3.3 times on PowerPC 970MP when sorting 32 million random 32‐bit integers. Also, a parallel version of AA‐sort demonstrated better scalability with increasing numbers of cores than a parallel version of bitonic mergesort on both platforms. Copyright © 2011 John Wiley & Sons, Ltd.     

H.264中变换和量化的SIMD优化

H.264是一个新的基于运动补偿+变换+量化+熵编码框架的视频编码国际标准。H.264中采用了大量的新技术,这些技术在提高编码效率的同时,也极大地增加了算法的复杂度。为此H.264在保证性能的前提下也做了一些优化,如变换和量化可以在16比特精度下完成,并且除了量化中需要少许乘法外,其余可以只用加法和移位实现。这些特点使得H.264中的变换和量化可以很好地使用支持单指令多数据(SIMD)的MMX技术进行进一步优化。该文首先介绍了H.264中变换和量化的实现过程和特点,接下来重点讨论了利用MMX指令对变换和量化中的关键部分进行优化的方法,最后给出了计算机仿真的结果,并对结果进行了分析。仿真结果表明:该文提出的方法可以使H.264的变换和量化模块的运算速度提高到原来的3.5～5.2倍,优化效果十分显著。     

多媒体处理器的SIMD代码生成

通用处理器的SIMD（Single Instruction Multiple Data）多媒体扩展，为提高多媒体应用的性能提供了新的体系结构支持。但目前编译技术对这类指令不能提供很好的支持。本文提出了一个新的SIMD指令生成算法，基于把编译器前端的程序分析和编译器后端的机器信息相结合的思想，采用扩展的treeparsing技术，有效识别程序中的并行操作以生成SIMD指令。基于SUIF（Stanford University Intermediate Format）编译器框架的实验表明，针对一组多媒体kernel，本文提出的算法可平均减少其非SIMD代码47％的cycles。     

Optimizing image spatial filtering on single CPU core

Nowadays, computing becomes a service on cloud computing resources. Users reserve virtual machines to execute their applications with minimum number of processing cores to save money. Optimizing user applications on the level of single core of a physical machine is highly desirable to users to reduce cost, as well as to cloud providers to reduce power consumption. In this paper, we showed how to exploit all the processing resources available in a single CPU physical core to optimize the performance of the 2D spatial filtering operation, a basic kernel in important image and multimedia applications such as image enhancement, edge detection, image segmentation, and image analysis. We proposed a novel computational procedure to restructure the conventional image filtering operation. Then, we demonstrated the merits of combining hand-optimized source-code restructuring, auto-optimized compiler techniques including vectorization, and hand-optimized threading to squeeze the performance of a single CPU core. Our intensive performance evaluations, using Sobel filters, on a variety of image sizes using the Linux Perf tool on a single core of the quad-core Intel Core i7 processor showed that our source-code restructurings with compiler auto-vectorization, using Intel AVX vector instructions, is 1.3X better than the non-restructured auto-vectorized version of the CImg library for computing the image gradient. Moreover, using OpenMP library directives we studied different image partitioning strategies to better exploit the two hardware threads inside a CPU core which boosted performance to 2.6X. Compared with the conventional CImg implementation, we obtained an average enhancement of 5.0X for image sizes ranging from 0.5 MPixel to 8 MPixel. However, comparing our best-optimized code to the conventional non-optimized serial code, without threading, resulted in a significant enhancement of 23X. The overall results showed how significant performance in important image processing applications can be obtained by applying source-code restructurings before employing any automatic compiler optimizations to exploit ILP, DLP and TLP parallelism degrees inside a single core of a multi-core CPU.     

Concurrent warp execution: improving performance of GPU-likely SIMD architecture by increasing resource utilization

Hardware parallelism should be exploited to improve the performance of computing systems. Single instruction multiple data (SIMD) architecture has been widely used to maximize the throughput of computing systems by exploiting hardware parallelism. Unfortunately, branch divergence due to branch instructions causes underutilization of computational resources, resulting in performance degradation of SIMD architecture. Graphics processing unit (GPU) is a representative parallel architecture based on SIMD architecture. In recent computing systems, GPUs can process general-purpose applications as well as graphics applications with the help of convenient APIs. However, contrary to graphics applications, general-purpose applications include many branch instructions, resulting in serious performance degradation of GPU due to branch divergence. In this paper, we propose concurrent warp execution (CWE) technique to reduce the performance degradation of GPU in executing general-purpose applications by increasing resource utilization. The proposed CWE enables selecting co-warps to activate more threads in the warp, leading to concurrent execution of combined warps. According to our simulation results, the proposed architecture provides a significant performance improvement (5.85 % over PDOM, 91 % over DWF) with little hardware overhead.