An evaluation of different DLP alternatives for the embedded media domain

An Evaluation of Different DLP Alternatives for the Embedded Media Domain Esther Salam´ı, Jes´us Corbal, Mateo Valero  Departament d’Arquitectura de Computadors, UPC. Universitat Polit`ecnica de Catalunya–Barcelona,Spain e-mail: f esalami,jcorbal,mateo g @ac.upc.es Roger Espasa Compaq Computer Corp., Shrewsbury, MA e-mail: [email protected] Abstract The importanceof mediaprocessing hasproduced a revolution in the design of embedded processors. In order to face the high computational and technological demands of near future media applications, new embedded processors are including features that were commonly restricted to the general purpose and the supercomputing domains. In this paper we have evaluated the performance of various DLP (Data Level Parallelism) oriented embedded architectures and analyzed quantitative data in order to determine the highlights and disadvantages of each approach. Additionally we have analyzed the differences between the explicit parallelversions ofcode (oftenbased on the standard algorithms) and the high-tuned, non-vectorizable versions usually found in real multimedia programs. We will show that sub-word SIMD architectures (like MMX) are a very costeffective solution, and that, while long vector architectures provide few improvements at a very high cost, a smart combinationbetween vector and SIMD-like architectures is the alternativethat leverages best performance at a reasonable cost. We will also show that the memory latency tolerance, typical of vector architectures, is partially compensated by theworsespatiallocalityfoundwhenexecutingvector code. 1 Introduction The significance that media processing has been taking on duringthe last years have not been limitedto the general purpose domain. On the contrary, the embedded domain has experimented a revolutionbased on new and harder demands. Near future applications such as personal mobile computing,WebTV devices, DVD players oreven nextgeneration of game consoles [1] are just a few examples.  This work has been supported by Direccio General de Recerca de la Generalitat under grant 1998FI-00260, by the Ministry of Education of Spain under contract CICYT TIC98-05110C02-01and by the CEPBA. The 32-bit embedded processors have already narrowed thegapbetweenembeddedanddesktopsystems[2]andDSP processorsincludecurrentlyfeaturesthatwere restrictednot far ago to just the general purpose domain. Realizing the computational demands, together with the cost and power consumption requirements of these new applications, it can be easily predicted that even more aggressive approaches are going to be implemented in future embedded processors. Inthispaper we willtrytoevaluate several of thevarious DLPorientedapproaches designedtoboosttheperformance of multimedia and DSP applications for the embedded domain: (a) sub-word level SIMD multimedia architectures, (b) conventional short/longvector architectures and (c) matrix SIMD multimedia architectures. In order to understand the performance benefits of each alternative we willpresent quantitativedata suchas thenumberandtypeofinstructions executed, the overall number of operations or the memory behavior. As a side matter of study, this paper focuses also on studying the difference between scalar optimized code and explicit DLP code, which is a generally overlooked issue in mostmultimediapapers. Wewillshowwhatarethemainoptimizations made over the standard vectorizable algorithms and we will analyze both optimized and vectorizable versions. 2 The embedded domain evolution towards media processing Media processing has motivated strong changes in the focus and design of mid 90s processors. In the general purpose domain, these changes have been very straightforward withtheinclusionofSIMD-likemultimediaextensionssuch as MMX [3], VIS [4] or MDMX [5]. These extensions have become the most important change to the basic ISA since the inclusion of the FP units inside the processor core. On the other hand, the changes in the embedded design have been stronglyinfluenced by different domains such as the general purpose or the supercomputing domain. From the general purpose domain, two main DSP architectures have evolved: superscalar DSPs with SIMD instructions (such as TriCore [6]) and VLIW DSPs, either with special SIMD instructions (Philips TriMedia [7], TigerSHARC [8]) or without (Texas Instruments TMS320C6201 [9]). Fromthesupercomputingdomain,thevectorandsystolic paradigmshaveinfluencednewDSPprocessors. Therehave been several papers dealingwiththe designofcost-effective vectormicroprocessors [10, 11]. Examples ofvector microprocessor designs are the Torrent T0 [12] or the V-IRAM project [13]. Additionally, there are current projects using streaming SIMD architectures to address 3D graphics processingsuchasImagine[14]. Finally,asasideresearch line, there have been papers dealing with the inclusion to a basic superscalarcore ofa conventionalvectorISAextension[15] and a matrix ISA extension [16]. While all these new architectures are able to take benefit from the abundant Data Level Parallelism available in common media codes, there has notbeen any workcomparingtheirpotentialperformanceandcharacteristics, specially in the embedded domain. When dealing with restricted resources, different factors such as the code density, the explicit parallelism or the memory behavior can affect performance in different ways than more aggressive general purpose architectures. These three factors will be the basis of the performance analysis in this paper. 3 Evaluation Background In this section we will discuss the selection of benchmarks for our set of evaluations, the impact of the scalar optimized code compared to explicitly parallel codes, and we will briefly describe all the modeled architectures and the approach used for simulate them. 3.1 Benchmarks The difficulty to capture all of the essential elements of modern embedded multimedia and communications systems is reflected on the lack of any standardized benchmark suite. For our study we focus on three representative programs of image and video workloads: cjpeg (a JPEG image encoder), djpeg (a JPEG image decoder) and mpeg2encode (a MPEG2 video encoder), all from the UCLA Mediabench suite [17]. We have chosen entire applications instead of representative kernels in order to compare the real effectiveness of current architectures. Note that the improvement obtained in some parts of the code can be overridden by the degradationproducedonthe remainingpart. The selected programs are representativeenoughas faras compilationmethodsand vectorization percentage is concerned. JPEG is a compression standard for either grayscale and color digital images based on the DCT-method [18]. The codification is performed in three stages: color space conversionanddownsample,forwardDCTtransformandquantization,andentropycoding. Incolorspaceconversion,each pixel from the source image in converted from the RGB to its YUV representation and then the chrominance components( U and V )are downsampledbya factoroftwoonboth spatial dimensions. The forward DCT processing step lays the foundation for achieving data compression by concentrating most of the signal in the lower spatial frequencies. Source images samples are grouped into 8x8 blocks and input to the DCT. The output is another block of 64 coefficients with the property that most of them have zero or near-zero amplitude and need not be encoded. Afterwards, each coefficient is quantized with the purpose to achieve further compression by representing the coefficients with no greater precision than is necessary to achieve the desired image quality. Finally, all the quantized coefficients are ordered into a "zig-zag" sequence, so that they can be encodedmorecompactlybasedontheirstatisticalcharacteristics (Huffmann coding). Djpeg just performs the inverse operations in the reverse order. MPEG-2 video compression standard was developed by the Motion Picture Experts Group [19]. Video sequences usuallycontainstatisticalredundanciesinbothtemporaland spatial direction. Spatial correlation is exploited for each frame in the same way as JPEG, and motion compensated prediction techniques are used to reduce temporal redundancies between frames. Motionestimationsearches which block of the previous image matches better with the block being compressed (this becomes the most computationalintensivepartoftheprocess), andtheresultingdisplacement between thetwoblocksiscalled themotionvector. Usually, the block size is 16x16 pixels for the luminance component ( Y ) and 8x8 for the chrominance components ( U and V ). A motion compensated difference block is then formed by subtractingthe pixel values of the predicted block from that ofthecurrentblock. Thedifferentblockisthentransformed, quantized and entropy coded. 3.2 Explicit DLP Vs Optimized Scalar Code Mostofthealgorithmsusedinthestandardsabovehave a vector nature. Nevertheless, due totheintrinsicsignificance of most multimediaalgorithms,there has been a great effort focusing on reducing the overall number of required operations. Unfortunately, this effort has been oriented towards scalar architectures, hiding in most cases the data parallel nature of the original algorithm. We can find the most representative example in the DCT algorithm. This transformation can be represented as a matrix operation using a 8x8 transform matrix A to obtain the 8x8 transform coefficients matrix C based on a bilinear transformation: C = A  B  A T , where B is the inputblock and A T denotes the transpose of A . This would involve 1024 multiplications for each input block. Nevertheless, various fast algorithms have been introduced in the literature for reducing the number of multiplicationsinvolved in thetransform[20]. ThealgorithmusedintheJPEGstandard onlyneeds toperform192productstoproduceoneresultant block;butbecause ofthisoptimization,thenewcode cannot be vectorized. The use of memory tables to replace multiplications or otheroperations groupsis quitefrequent too. Incolor space conversion, the equations to be implemented for each pixel are: Y = C 1  R + C 2  G + C 3  B U = C 4  R + C 5  G + C 6  B + 128 V = C 6  R + C 7  G + C 8  B + 128 where C 1to C 8 are constants and R , G and B are the pixel color components. To avoid floating-point/fixed-point conversions, fractional numbers are represented as integers scaledupby216. Moreover, inordertoavoiddoingmultiplicationsintheinnerloop,theseproductsareprecalculatedfor all possible values of R , G and B . This would involve 256 entries of 32 bits per table; as two multiplication constants are identical, only eight tables are needed. These small tables are grouped into one unique table of 8 Kbytes, which can be held in cache. Taking into account that offsets and rounding factors are included in the tables, the real change is 9 loads and 6 adds in opposite to 9 mults and 9 adds. Something similar is done to perform saturation in djpeg. Several decompression processes need to rangelimit values between 0 and 255. On most machines a table lookupis faster than the explicit test: if(x < 0)x=0; else if (x > 255) x = 255; So, two conditional branches and an assignment above are replaced by one single memory access. Finally, another typical scalar optimization which can prevent a code fragment from being vectorized is a break condition inside a loop. We can look at the distance functionin mpeg2encode for a sample. In motion estimation, the distance between two blocks is computed as the sum of absolute differences between the pixels of both blocks. In fact, the object of the search is finding the block with minimal distance, so it is not worthto calculate the full distance when the sum accumulated for some columns exceeds the current minimum, and the resulting code is something similar to this: for(i=0;i<h;i++) f for(j=0;j<w;j++) s += abs(b1[i][j]-b2[i][j]); if (s >= distlim) break; g We cannot vectorize this code over loop i because of the conditional break, but this line of code could be removed without affecting the program output but rather the overall number of operations executed. Note that the improvement obtained with this kind of optimizations is strongly architecture dependent. We have looked for the main optimizations which are present in the three benchmarks and handwritten the standard (without optimizations)associated code, so thatwe can generate vector/SIMD code. In section 4 we will evaluate the impact of the optimized code over performance. The optimizationswe have taken into account are: a) For cjpeg: tables used for color space conversion have beenchangedforthelinealcombinationoftheinputsshowed above. The DCT is implemented as matrix per matrixproducts. b) For djpeg: besides the optimizationsdescribed for cjpeg, saturation is performed as a comparison instead of just accessingatable. Intheoptimizedcode, theyavoidcomputing the IDCT for those blocks whose elements are all zero. Initialevaluationsshowed usthateliminatingthisoptimization wouldprovide us diminishingreturns. Therefore, the IDCT has not been modified for any vector code (except for the basic non-optimizedreference code). c) For mpeg2encode: as in the previous benchmarks, the IDCT is implemented as twomatrix per matrix products. In motion estimation, we have removed the break conditionin distancecomputationwhengeneratingmatrix-orientedcode (see subsection 3.3) since would not allow us to vectorize thewholematrix,andalsowhengeneratingMMX-likecode as it would not allow us to generate optimal scheduling. 3.3 Modeled Architectures In this paper, we are going to evaluate five different SIMD/vector architectures:  2-way basic superscalar DSP  2-way superscalar DSP + SIMD extensions  2-way DSP + long vector instructions(128)  2-way DSP + short vector instructions(16)  2-way DSP + Matrix SIMD extensions 0.4 GB/s 0.4 GB/s MEM UNIT UNIT 2 CACHE I 2x32b RAMBUS DATA CACHE 32b @ DATA CACHE UNIT 32b @ 2 CACHE I 2x32b RAMBUS (a) (b) FETCH FETCH DECODE DECODE MEM UNIT INT ALU INT ALU INT REG INT REG Figure 1. The basic superscalar DSP reference architecture: (a) in-order, (b) out-oforder. The basic characteristics of all the architectures (such as theissue rate, the latencies, thepipelineor thecache configurations) have been chosen based on those of the Siemens TriCoreTC10. Notethatitisverydifficulttoprovidearather perfectly fair comparison between architectures, since factors such as the characteristics of the specific ISA or the election of the number of the functional units may affect overall performance. This paper is an attempt to determine trends and characteristics rather than identifying the best alternative. 3.3.1 Reference superscalar DSP ThebasicreferenceDSPisa100MHz,2-wayissue,RISC load/store architecture with 32 general purpose registers. The engine is able to fetch and decode up to two different instructions per cycle. There are two different pipelines: one for integer and branch instructionsand one for memory instructions. The integer operation latencies are 1 single cycle, except for multiply operations (3 cycles) and divide operations (7 cycles). The processor has a 16KB, 2-wayset associative instructioncache that provides 16-byte cache lines into an instruction buffer that decouples the fetch and the decode stages. The data cache is a 16KB, write-back, 4-wayset associative cache with 32-byte cache lines able to provide one 32-bit data access per cycle. The processor is coupled to a pseudo DirectRambusmemorysystemwithabi-directional,128-bit wide, 25MHz main bus, able to deliver up to 0.4 GB/s. The in-order execution version has a very simple controllogicthat stallsthe pipelinewhenever we encounter any kindof data dependence or resource constraint. The out-oforder version of the DSP (see figure 1.b) provides register renaming (40 physical registers) and includes one reservation station (of 8 slots) per pipeline. Instructions between pipelines can be executed out-of-order, but instructions inside the same reservation stationmust be executed in-order. In order to evaluate the performance of the architecture UNIT FETCH SIMD ALU DECODE 2 INT ALU 0.4 GB/s DATA CACHE @ CACHE I 2x32b RAMBUS 32/64 b 32/64 b MEM UNIT REG INT REG SIMD Figure 2. The in-order superscalar DSP + SIMD instructions architecture. we have used ATOM [21] to provide Alpha code traces to our Jinks simulator [15]. In order to approximate the effect of 0-cycle resolution branches typical of several DSPs, we have takenanoptimisticapproach andhave assumed perfect branch prediction. 3.3.2 Superscalar DSP + SIMD extensions We have enhanced the basic model with a SIMD register file together with an additional pipeline able to execute 64bitsub-wordlevelSIMDinstructions(seefigure2). Wehave used the emulation libraries described in [16] to hand-write the same applications with a SIMD ISA extension fairly similar to INTEL’s SSE [22] integer opcodes. This SIMD extensionprovides67opcodesand3264-bitSIMDregisters able to operate on up to eight 8-bit items in parallel. The data path of the data cache has been enlarged to allow one fullbyte-wise64-bitaccess percycle. Formoreinformation about the emulation and simulation details the reader may refer to [16, 23]. 3.3.3 DSP + vector instructions We have enhanced the basic model witha vector register file and a real single vector unit. The in-order execution model is similar to that proposed in [11], while the out-oforder version is based on the architecture proposed in [15]. Boththe register file and the vector functionalunitare clusterizedin4independent32-bitvectorpipes(orlanes) where the different vector elements are interleaved (see figure 3). Therefore, up to 4 operations from the same vector instruction can be performed per cycle (in the same vein that the SSE sub-word level parallelism). We have used the CONVEX C4000 compiler to generate vector code and we have generated traces tofeed Jinks. The CONVEX ISA provides 16 32-bit logical vector registers, and 52 address and scalar registers. The out-of-order version of the architecture performs register renaming with 24 physical vector registers 2x32b 32/64 b Vector Register File DECODE 0.4 GB/s MEM UNIT I 32/64 b CACHE RAMBUS INT ALU DATA CACHE @ UNIT FETCH LANE LANELANE LANE VS reg VL reg 2031 INT REG Figure 3. The in-order vector microprocessor DSP reference architecture. UNIT FETCH MEM UNIT MATRIX ALU DECODE 32/64 b 2 INT ALU DATA CACHE @ CACHE I 2x32b RAMBUS 0.4 GB/s 32/64 b VL reg MATRIXINT REG REG ACCUMULATORS Figure 4. The in-order superscalar DSP + Matrix instructions architecture. and 64 scalar/address registers. Inordertostudythedesigntrade-offs,we have generated code for two different vector lengths: 16 and 128. For the 16-lengthversion, we have used strip-miningtechniques on all those vectorizable loops it was required. For the full vector length version (128), whenever possible, we used loop-unrollingplus loop-interchange techniques so that we could achieve the longest effective vector length possible. SIMD-like extensions such as MMX are able to provide upto8elements withasingle64-bitmemoryaccess. We assume thatthe vector microprocessor memory system is able to provide the same bandwidth when the vector elements are consecutively arranged in memory (up to 8 elements of 8 bits, or up to 4 elements of 16 bits) and that the logic to distributethe elements among the vector lanes does not add additionalcycles of latency. 3.3.4 DSP + matrix SIMD extensions In [16] we proposed a matrix ISA that is basically an hybridbetween conventionalvector ISAsandSIMD MMXlikeISAs. ThisISAisabletoexploitDLPfromtwodifferent dimensions (parallel loops). We used emulation libraries to SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 100 200 300 cjpeg control vector arithmetic vector memory scalar arithmetic scalar memory SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 100 200 300 400 djpeg SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 500 1000 1500 2000 2500 instr. x 10^6 mpeg2encode Figure 5. Dynamic instruction breakdown. hand-writethecodeusingtheproposedmodelandJinkswas modified to be able to detect the emulation functions calls while gatheringthe SIMD traces. We have modified the DSP+vector model in order to allow the execution of thiskind of instructions. The ISA provides16logicalmatrixregisters(with1664-bitwordseach) and 2 logical 192-bitpacked accumulators (similar to those proposedintheMDMXmultimediaextension[5]). Wehave anindependentmatrixregisterfileandanindependentaccumulator file. In sharp contrast with the conventional vector version, we have not implemented parallel lanes since: a) we already have the MMX-like sub-word execution capabilities, and b) the accumulators complicate the design of fully independent lanes. The out-of-order version provides register renaming with 20 physical matrix registers and 4 SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 100 200 300 400 operations x 10^6 cjpeg vector operations scalar operations SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 100 200 300 400 djpeg SS - not optimized SS SS + SIMD SS + short Vect SS + long Vect SS + Matrix 0 500 1000 1500 2000 2500 operations x 10^6 mpeg2encode Figure 6. Dynamic operation count. physical multimedia accumulators. 4 QuantitativeAnalysis In this section we will provide quantitative data in order to identifythe main characteristics of every architecture under study. We will show the instruction and operation breakdownsandan analysisoftheperformance results. Additionally,wewillstudytheimpactofout-of-orderexecution over each architecture. Finally, we will analyze the data locality and the memory latency to explain the impact of a realistic memory over performance. 4.1 Instruction Breakdown Figure 5 shows the dynamic instruction breakdown for the benchmarks under study. The instruction types have been classified into the following five categories: scalar memory,scalararithmetic,vectormemory,vectorarithmetic and branches (control). From the results, we can clearly observe that the explicit vectorparallelversionsofcodehave ahugeinstructionoverhead. The optimizations described in section 3.2 are able to reduce between 35% and 70% of the overall number of instructions. Notespeciallythehighdegradationintroduced in the non-optimized code for djpeg, mainly produced by the zero condition removal mentioned in subsection 3.2, since almost 3/4 parts of the input blocks have zero AC coefficients. Because of the lack of resources in typical embedded architectures, the increases in performance are almost proSS + SIMD SS + SV SS + LV SS + Matrix mpeg2encode 6.60 15.19 16.47 50.82 djpeg 4.71 15.99 127.66 75.10 cjpeg 3.56 11.27 14.53 11.48 Table 1. Average vector length of the instructions for all the SIMD architectures. portionaltothereductionofthenumberofinstructions(considering the same ISA). Therefore, we may expect that the optimized version of code is going to execute about twice faster than the vectorizable version of code. Taking into account that all the SIMD/vector versions of code are based on the non-optimized vectorizable version, it might seem that the overall number of instructions could be higher than in the optimized original version. Nevertheless, as seen inthe figure, the MMX-likeSIMD architecture executes about 35% fewer instructions than the optimized code, and the vector oriented architectures (short, long and matrix) an average of 60% fewer instructions. The reason is that, as already pointed out in [24], the SIMD/vector architectures can pack several scalar memory and arithmetic instructions into a single vector/SIMD instruction. Moreover, due to the fact that multiple instances of a loop are replaced with equivalent SIMD/vector instructions, there is an additional reduction of the number of instructions involved in the loop-related control (that is, loop indexes and address variables). Finally, there is another factor of reduction related to the specific characteristics of every ISA. For instance,theMMX-likeandthematrixSIMDISAshavesaturationarithmetic that avoids having toperform the process described in section 3.2 and the matrix SIMD ISA allow to perform multiply&accumulate instructions. 4.2 Operation Breakdown The overall instruction reduction is strongly dependent on three factors: the average vector length (say, the average number of operations per vector instruction),the vectorization percentage of the program and the overall number of operations to execute. Figure 6 shows the dynamic operation count and table 1 shows the average vector length for all the benchmarks under study. Analyzing the average vector length for every architecture we can see that the short vector architecture is able to leverage a vector length very close to the maximum (16). The SIMD architecture is also able to provide convincing vector lengths (packing only 3 times less elements than the short vector architecture with a vector register file 16 times smaller). On the other hand, the average vector length of the long vector architecture is rather disappointing, since onlyfor djpeg is able to almost reach its maximum vector length, and for the other benchmarks is barely able to leverage longer lengths than the short vector alternative. This is duetothefactthatmostmultimediakernelsarecharacterized by having several nested loops with very small loop counts (between 8 and 16). The number of cases where longer loopsorloopinterchangecanbeusedisverysmall. Insharp contrast with the conventional vector architectures, the matrix ISA, due to its capability to vectorize two inner loops, leverages verylongvectors lengthsfor mpeg2encode and djpeg and a fair vector length for cjpeg. The overall number of operations is a way to determine the semantic richness of every ISA and is a strong indicator ofthefinal performance. From theresultsinfigure6 we can identify three different cases. In mpeg2encode both the MMX-like SIMD and the matrix architecture performs less operations than the conventional vector architectures. This is explained by the fact that they have very powerful instructionsto perform the motionestimationalgorithm, such as the vector average or the sum of absolute differences instructions. Furthermore, the matrix architecture only needs to execute almost half the number of operations than the SIMD architecture thanks to the advantages of the matrix accumulators [16]. Additionally, the vectorization percentageoftheoverallprogramissimilar,sincejustthisalgorithm represents almost a 80% of the entire program. Unfortunately,thesimilarityinthevectorizationpercentageisnotfoundintheothertwobenchmarks. TheCONVEX compiler is able to vectorize much more instructions than simply identifyingsome kernels and hand-write them (as is the case in the SIMD and matrix versions). This causes that the conventional vector architectures execute fewer scalar instructions than the others. Moreover, the number of vector operations is also smaller. This is produced by the large overhead involved in packing/unpacking operations (usually found in MMX-like ISAs) to perform typical transformations such as data promotion,matrix transpose or sign conversion. This logic overhead may represent almost the 50% of the overall number of operations. As we will see later, in some cases (such as djpeg) this overhead may cause less performance but, interesting enough, for some other cases (cjpeg) it may end up being beneficial. 4.3 Performance results Figure 7 shows the performance results for the three benchmarks with realistic cache simulation. The speed-up performance is related to the execution time of the reference superscalar DSP architecture. From the performance results, we can see that, as expected, the optimized version ofcodeperformstwicefasterthanthevectorizablecode. On theotherhand, we can alsosee thatthe longvector architectureisnotcosteffective, asitishardlyabletooutperformthe short vector architecture (except for djpeg which exhibits 0.0 0.5 1.0 1.5 Speed-up cjpeg SS - not optimized SS SS + SIMD SS + short vectors SS + long vectors SS + Matrix 0 1 2 Speed-up djpeg 0 1 2 3 4 Speed-up mpeg2encode Figure 7. Performance results. a 10% of performance improvement). In mpeg2encode, the SIMD architecture outperforms both vector architectures leveraging a 25% of additional performance while the matrix architecture provides a huge performance boostof2.2X.Tworeasons explainthisperformance gains: (a) the smaller number of overall operations to execute, and (b) the higher parallelism (for instance, the SIMDversionexecutes6.6vectoroperationspercyclewhile the vector architectures execute only up to 4 vector operations per cycle). Neither of the two previous reasons can explain why the SIMD and the matrix architectures slightly outperform the conventional vector architectures (15% and 20% respectively) in cjpeg. As we will see in section 4.5, the pack/unpack overhead in those architectures (basically, to perform matrix transpose and RGB color restructuring) allow to make full 64-bit vector memory accesses. On the contrary, the conventional vector architecture find the vector elements not consecutively arranged in memory thus leveraging very poor data bandwidth. Ontheotherhand,theproblemofthedata rearrangement is not encountered in djpeg, since the IDCT is not vectorized at all, and the inverse color conversion algorithm has the color dimensions adequately rearranged. Moreover, the matrix architecture cannot take benefit from the multimedia accumulators in the upsample algorithm (thus needing costly data promotion transformations). As a result, due to the difference in the number of operations to execute, the conventional vector architectures provides a performance benefit over theSIMD andmatrixarchitectures ofa 50%for the short vector architecture and a 66% for the long vector architecture. Speed-up SS SIMD SV LV Matrix mpeg2encode 24.2 % 31.1 % 63.3 % 59.5 % 32.6 % djpeg 29.1 % 30.5 % 43.6 % 37.4 % 27.2 % cjpeg 50.4 % 37.2 % 51.0 % 45.6 % 33.3 % Table 2. Impact of out-of-order execution. 4.4 The impact of out-of-order execution Historically, out-of-order execution has been considered not an option for the embedded domain. Theoretically, if the performance gains were not higher than the obvious increase in power consumption, an out-of-order execution engine would not be worth. Table 2 shows some speedups when using a very limited form of out-of-order rather than the baseline architecture. Note that the Speed-ups are relative to the correspondent in-order architecture. From the results, we can see that out-of-order execution provides a considerable performance boost for all the architectures (between 30% and 60%). Nevertheless, it still remains to beseen whetherthese performance gainsare higherthanthe increase in power consumption. Contraryto ourexpectations, the architectures that benefit the most from an aggressive dynamic scheduling are the conventional vector architectures. From the architectural pointof view, the streaming nature of the vector instruction should leverage a convincing throughput even for in-order execution. However, looking carefully at the behavior of the pipeline for in-order and out-of-order execution we can easilyfigureoutwhatproducessuchaperformancedegradation in the basic in-order approach. Our vector architecture model does not allow memory chaining (that is, a vector arithmetic operation does need to wait until a dependent vector load has executed totally). This design decision was duetothefact that,whilememory chainingisworthforsystems with fixed memory latency, having a cache hierarchy (andthus,unpredictablelatencies)complicatestoomuchthe control logic of the in-order processor. As a consequence, when we encounter a load-arithmetic dependence, the processor stalls many cycles waiting for an entire long stream of data. The lack of memory chaining is not much of a problem if we consider a careful static scheduling. By exploiting at compile time the available ILP so that we can separate the further possible a vector load from a dependent vector arithmetic instruction, we can perform statically what outof-orderexecutiondoes. Unfortunately,theCONVEXcompilerdoes notconsiderthese issuesand tendstoputtogether dependent load-arithmetic instructions. In sharp contrast with this poorly scheduled code, the MMX-like SIMD and thematrixarchitectureswerecarefullytunedexploitingmost of the potential ILP at the static scheduling level, so taking littlebenefit from a more aggressive dynamic execution. Slow-down SS SIMD SV LV Matrix mpeg2encode -5 % -16 % -14 % -18 % -18 % djpeg -15 % -13 % -13 % -10 % -12 % cjpeg -23 % -6 % -19 % -21 % -12 % Table 3. Memory performance degradation. Hit rate SS SIMD SV LV Matrix mpeg2encode 98.3 % 95.5 % 97.3 % 94.4 % 94.6 % djpeg 96.6 % 95.2 % 92.8 % 89.4 % 92.4 % cjpeg 93.7 % 97.6 % 93.3 % 93.0 % 93.5 % Table 4. Data cache hit rate. 4.5 Memory behavior Table3showstheperformancedegradationwhenweconsidera realisticmemory system (relative tothe performance with a perfect cache). The effect of the instruction cache over performance has demonstrated to be very small, as all programs fit perfectly in cache. Therefore, we are going to focus on the impact of the data cache. From the results on table 3 we can see three interesting facts. First, even with high hit-ratios (see table 4), considerable performance losses around 15% are produced when considering a realistic memory system. This is due to the fact that we do not have a L2 cache, and for all the accesses that miss in the first level we must pay all the full latency of theexternalmemory sub-system. Anotherinterestingfact is that the MMX-like SIMD architecture seems to be the most robust alternative to the impact of the memory system. Additionally, we can observe that the vector architectures (short, long and matrix) exhibit the highest performance degradations when considering a realistic memory system. This fact may seem counterintuitive, since vector architectures are very well known for theircapability to tolerate memory latency alonglong streams of data. However, this advantage is fully compensated by the fact that as we have longer vectors the data locality degrades (as it can be seen in table 4, where we show the data cache hit rates). The reason resides intheway thatthe differentarchitectures execute a loop. A non-vector architecture executes all the instructionsofaloopiterationinasequentialway,exploiting temporal locality. If there is spatial locality, a miss access produces an effect of ’prefetching’ that loads the elements of the following iterations. This effect produces a natural way of exploiting spatial locality. On the other hand, vector architectures execute several loop instances of the same instruction sequentially, thus not being able to exploit this advantage and finding less elements in the cache. As a matter of fact, the higherthevector lengththe lower the hit rate. On the other hand, the higher the vector length the higher the tolerance to memory latency. Therefore, this two effects compensate together. For instance, the long Latency SS SIMD SV LV Matrix mpeg2encode 1.61 2.64 2.46 2.85 3.26 djpeg 2.14 2.33 2.07 1.83 2.05 cjpeg 3.36 1.48 2.78 2.86 1.91 Table 5. Average memory latency. vector architecture leverages very high vector lengths for djpeg, and despite the fact that the hit-ratio is very low (a 89.4%), the performance loss (only a 10%) and the average memory latencyare thelowestforallthearchitectures. This effectisnotencounteredinthebasicsuperscalararchitecture and, as a result, low hit-ratios or even moderate latencies often translate into a high performance degradation, as it can be seen in table 5 for the cjpeg benchmark. The average memory latency is not only dependent on the data locality. For instance, for cjpeg, the conventional vector architectures have higher latencies than the matrix architecture having, though, the same data locality. This is explained by the fact that in cjpeg we find a high percentageofvectoraccesses whoseelements arenotconsecutively arranged inmemory (forexample, whenaccessing the color dimension we find stride 3, or when traversing columns in the IDCT we find stride 8). As a result, the memory system isforced toaccess the elements individually,leveraging very poor effective bandwidth (which ends up affecting the overall latency of the vector access). This explains why the conventional vector architectures do not outperform the SIMD architecture, even though they execute fewer operations. The SIMD and matrix architectures do not face this problem as they use logic operations to rearrange the data conveniently. 5 Architectural complexity comparison Table 6 compares the register file configuration and the overall size for all the architectures under study. Note that due to the simplicity of the basic processor core (same fetch/decode/issue rate, fixed number of register file and cache ports), the only parameters that influence the final area cost are the number and wide of the functional units andthesizeoftheregisterfiles. Sincethenumberofregister file portsis fixed, the area cost isproportionaltothe register file size. Therefore, from the point of view of performance/cost ratio, we can see that the in-order SIMD architecture is the most cost effective approach. The SIMD architecture outperformstheconventionalvectorarchitecturesfortwoofthe benchmarks, despitehavingonesingle64-bitfunctionalunit (instead of 4 32-bit functional units) and a overall register file size between 3 and 22 times smaller. On the other hand, the matrix architecture could be a good alternative when int vector accum. Total SS 32 x 32b 0x1x64b 0 x 192b 0.125 KB SS (ooo) 40 x 32b 0x1x64b 0 x 192b 0.156 KB SS + SIMD 32 x 32b 32 x 1 x 64b 0 x 192b 0.375 KB SS + SIMD (ooo) 40x 32b 40 x 1 x64b 0 x 192b 0.469 KB SS + SV 52 x 32b 16 x 16 x 32b 0 x 192b 1.203 KB SS + SV (ooo) 64 x 32b 24 x 16 x 32b 0 x 192b 1.750 KB SS+LV 52 x 32b 16 x 128 x 32b 0 x 192b 8.203 KB SS + LV (ooo) 64 x 32b 24 x 128 x 32b 0 x 192b 12.25 KB SS + matrix 32 x 32b 16 x 16 x 64b 2 x 192b 2.172 KB SS + matrix (ooo) 40 x 32b 20 x 16 x 64b 4 x 192b 2.750 KB Table 6. Overall register file sizes. lookingforhighperformance, since it providesthebest performance at a reasonable area cost (about6 times larger that the MMX-like SIMD architecture register file size). On the other hand, the long vector architecture does not arise as a good option, since requires a register file size of the same order of the data and instruction caches while is hardly able to provide performance gains when comparing with the short vector architecture. 6 Summary The focus of this paper has been to provide some quantitative data in order to understand the performance/cost trade-offs of different DSP exploitation alternatives for the embedded domain. We have selected three entire benchmarks from the Mediabench suite and we have evaluated them with different SIMD/vector architectures. We have also analyzed the differences between the explicit parallel versions of code, based on the standard algorithms, and the high-tunednon-vectorizable original versions of code, demonstratingthat the optimized version can execute up to two times faster that the non-optimizedone. From the performed quantitative analysis, we conclude that the SIMD-like architecture arises as the more costeffective option, as it can provide convincing performance (with gains over the reference DSP ranging from 1.2x to 2.6x) with only 32 64-bit registers in front of the nearly six times larger register file needed by the matrix architecture. Nevertheless, if we are looking for maximum performance, the latter can be considered, since it outperforms all the other architectures at a reasonable cost. As far as vector architectures are concerned, it has been demonstrated that a long vector processor is not worth at all for the embedded domain, as it does not achieve enough performance gains (only a 10% over short vectors for one of the benchmarks) to justify the enormous cost increase. However, short vectorscould be a good optionfor some media codes (withfew reduction operations and conveniently arranged data) if the cost of out-of-orderexecution is acceptable.