Three-dimensional memory vectorization for high bandwidth media memory systems

Three-Dimensional Memory Vectorization for High Bandwidth Media Memory Systems Jesus Corbal, Roger Espasa and Mateo Valero Departament díArquitectura de Computadors, Universitat Polit`ecnica de CatalunyañBarcelona, Spain  e-mail: f jcorbal,roger,mateo g @ac.upc.es Abstract Vector processors have good performance, cost and adaptability when targeting multimedia applications. However, for a significant number of media programs, conventional memory configurationsfail to deliver enoughmemory references per cycle to feed the SIMD functional units. This paper addresses the problem of the memory bandwidth. We propose a novel mechanism suitable for 2dimensional vector architectures and targeted at providing high effective bandwidth for SIMD memory instructions. The basis of this mechanism is the extension of the scope of vectorization at the memory level, so that 3-dimensional memory patterns can be fetched into a second-level register file. By fetching long blocks of data and by reusing 2dimensional memory streams at this second-level register file, we obtain a significant increase in the effective memory bandwidth. As side benefits, the new 3-dimensional load instructions provide a high robustness to memory latency and a significant reduction of the cache activity, thus reducing power and energy requirements. At the investment of a 50% more area than a regular SIMD register file, we have measured and average speed-up of 13% and the potential for power savings in the L2 cache of a 30%. 1 Introduction Multimedia applications have become one of the most important types of workloads in current microprocessor design [1]. Most new general purpose and embedded processors include SIMD ISA extensions to increase the performanceoffuturemedia protocolsand killerapplicationssuch as MPEG-4 [2]. These new instruction extensions focus on exploitingdata-level parallelism over small data-types (thus sometimes called  -SIMD parallelism) inside a single register (64-128bits typically). Examples of these new ISA extensions are INTELís MMX [3] and SSE[4], SUNís VIS[5],  This work has been supported by the Ministry of Science and Technology of Spain under contract TIC-2001-0995 and by the CEPBA AMDís 3DNow! [6], MIPSís MDMX [7] and Motorolaís AltiVec [8]. Ranganathan et.al. [9] presented an in-depth study of the characteristics of  -SIMD enhanced applications. They showed that after including software prefetching, most media applications were compute bound. Performance was, then, ultimately limited by fetch and issue bandwidth. In order to address this problem, several authors have proposed 2-dimensional vector architectures [10, 11, 12]. These architectures adapt to typical multimedia memory patterns by extending the scope of vectorization to two dimensions (or parallel loops). The main advantage of these 2-dimensional vector architectures is that they are able to signiÝcantly increase the numberof operations per instruction,thus, breaking the fetch/issue barrier of most media programs. In this paper, we study the behavior of several media applications using one of these 2D media extensions. We will show that several applications experience a signiÝcant performance degradationdue to the the memory system. While datacachesshowan extremelyhighhitrate (asalreadyhighlighted by Slingerlandet.al. [13]), they are, however, unable to deliver enough memory bandwidth for the vector functional units. The design of high bandwidth cache memory systems is not trivial due to the complex memory layouts typically found in most media applications. In order to address this problem, we came to the observation that high amounts of spatial and temporal locality exist at extra dimensions of the memorypatternlayout,eventhoughthere arecomputational dependences that do not allow straight-forward vectorization. This locality, if properly exploited, may enable high memory bandwidth with a feasible cache hierarchy based on widening the cache memory ports. We propose a new extension to a 2D vector architecture targeted at implementing high bandwidth vector memory systems. The basis of this mechanism is a second-level vector register Ýle where 3-dimensional memory patterns can be fetched from the memory thanks to a new 3D vector load instruction. By doing this, we take advantage of higher amounts of spatial and temporal locality that translate into higher effective bandwidth and register reuse. Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6 a 0,7 64 bits dimension i: 8 elements x 8 bits a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6 a 0,7 a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,7 a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,7 a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6 a 3,7 a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6 a 4,7 a 5,0 a 5,1 a 5,2 a 5,3 a 5,4 a 5,5 a 5,6 a 5,7 a 6,0 a 6,1 a 6,2 a 6,3 a 6,4 a 6,5 a 6,6 a 6,7 a 7,0 a 7,1 a 7,2 a 7,3 a 7,4 a 7,5 a 7,6 a 7,7 64 bits dimension i: 8 elements x 8 bits dimension j: 8 elements x 64-bit (MMX) 8 MOM MMX int fullsearch(blk1, blk2, length, i0, j0, int win) unsigned char *blk, *blk2; int length, i0, j0, win; { int l, d, i, j, k, min, pos; unsigned char *a,*b; ... ... for (k=0; k<l; k++) { a = blk1 + k; b = blk2; d = 0; for(j=0; j<8; j++) { for(i=0; i<8; i++) { d += abs(a[i]-b[i]); } a += length; b += length; } if (d<dmin) { min=d; pos = k; ; } } ... ... } Figure 1. Comparison between (a) a conventional MMX-like  -SIMD instruction and (b) a Matrix (MOMlike) 2D SIMD instruction. We will show that our proposed mechanism is able to provide high performance gains for those applications where memory bandwidth is the main bottleneck. Even for therestofthe benchmarks,ourproposalprovidestwosignificant side beneÝts: a sensible reduction of the cache activity and a prefetching effect. The former translates into lower power/energyconsumptioninthememorysub-systemwhile the latter provides high robustness to the latency when the memory is far away. 2 A brief overview of a 2D vector ISA In this paper, we are goingto use MOM [10] as our baseline 2DvectorISA. MOM stands forMatrix Oriented Multimedia extensionand is a hybrid between a traditional vector anda  -SIMD ISA. MOM is able to exploitup to two different dimensions of parallelism by using a different paradigm (either vector or  -SIMD ) to vectorize one of two available parallel nested loops. MOM can be viewed as a conventionalvector ISA where each of its computation operations are  -SIMD MMX-like instructions. The execution of a MOM instruction is dictated by two different parameters. The Vector Length determines how many 64-bit elements of the MOM register are operated (out of 16). The Vector Stride determines the distance between two consecutive MOM vectorelements when performing memory operations. In order to help understand the differences between a conventional  -SIMD approach and a 2D approach such as MOM, Ýgure 1 shows a simpliÝed fragment of code extracted from a MPEG-2 encoder. The algorithm shown is doing the motion estimation stage of the encoding, which detects movement of objects along different video frames. In order to do so, it searches across the reference image for the image block which matches better with the block being compressed. This is accomplished by Ýnding the minimal sum of absolute differences between the pixels of the two blocks. This search is performed, in the code, over several matrices laid out on the image x-axis. Note that length may be arbitrarily long, as it stands for the horizontal size of the frame. Analyzing the code shown in the Ýgure we can see that there are up to two different dimensions of data-level parallelism to be exploited: nested loops i and j . The calculation of the sum of absolute differences between pairs of pixels ( i j ) can be done in parallel fairly easily. Note, however, that loop k does not show the same property, as we have data and control dependencies in the if clause (clause that determines if we have found a local minimum) which avoid vectorization. As shown in Ýgure 1, MOM is able to take advantage of the parallelism implicit in both loops i and j . First, it generates a MMX-like instruction for loop i , and then extends an additional vectorization of this instruction, replicating it across loop j . As a result, each pattern a and b are loaded into a single MOM register. In other words, each MOM register element (a 64-bit  -SIMD register) corresponds to a row of a matrix. Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE Processor Core Processor Core bank 0 bank 1 bank n-1 Shift & Mask Interchange Initial Address Final Address Processor Core Processor Core (b)(a) ... Crossbar ... ... 11 1 x B 11 B 1 B x 1 Figure 2. Cache designs for SIMD memory ports: (a) Multi-banking, (b) Port Widening. 3 Rationale for 3-dimensional vectorization In this section we will show that 2D SIMD media programs can experience severe performance degradations due to the bandwidth constraints of realistic cache implementations. In order to address the problem, we will introduce two new instructions to perform 3D memory accesses and will discuss why they allow exploiting a higher amount of temporal and spatial locality. 3.1 The problem of the bandwidth A traditionalproblemof SIMDarchitecturesis thedesign of a memory system able to provide enough memory references per cycle to keep the SIMD functional units busy. As shown by Toni Juan et. al. [14], true multi-ported caches are not feasible due to their high cost. Alternative cache designs to true multi-ported caches are several, each with its drawbacks: time-multiplexing(as in the Alpha 21264 [15]), multi-banking, port widening, etc. Multi-bankingconsistsofimplementing B memoryports connected with a set of cache memory banks by means of a crossbar (see Ýgure 2-a). A vector memory instruction can distribute its different memory references among all available memory ports. While this conÝguration presents the advantage of performing well for different strides, scalability is compromised because of bank contention and implementation issues of the crossbar for an elevated number of memory ports. Port widening is a more restrictive (but cheaper) alternative, based on increasing the granularity of the memory accesses. Given a vector memory instruction whose elements are consecutively arranged in memory, we can fetch several elements in a single access provided that they are located jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode 1.0 1.2 1.4 1.6 Performance slowdown MOM multi-banked cache MOM vector cache Figure 3. Performance slowdown for realistic memory system configurations. in the same cache line. The vector cache [16] is a straightforward implementation of this concept. As shown in Ýgure 2-b, the vector cache is based on loading two whole cache lines (one per interleaved bank) instead of individually loading each vector element. Additional logic (an interchange switch, a shifter and a mask logic)allows selecting a chunk of up to B consecutive words, being the upper bound of B the size of a single cache line. Its main drawbacks are: Ýrst, it may add extra latency due to the shift&mask logic, and second, it is not able to providemore than one reference per cycle when the vector stride in different than one. In order to evaluate the efÝciency of the two different cache designs, we have measured the performancedegradation of a 8-way issue processor able to execute MOM instructions, for a set of benchmarks from Mediabench [17]. Figure 3 shows the processor performance slowdown for two differentcache designs: (a) a 4-port multi-bankedcache (with 8 memory banks), and (b) a vector cache with one single port of width 4  64 bits. Performance degradation is given relative to performance of an idealistic memory system (perfect cache, 1-cycle of latency, unbounded bandwidth). Details about the architecture conÝguration can be found in section 5.3. Results show that some of the benchmarks have significant performance degradations when taking into account a realistic memory implementation (ranging from 8% to 58%). As the cache hit rates are relatively high (from 90% to 99%), the reason that explains such decreases in performance is no other than the effective bandwidth provided by the memory ports. Results also show that the vector cache obtains slowdowns reasonably similar to those of the multibanked conÝguration, while being much easier to implement. 3.2 Identifying the potential of a third dimension As seen in the previous subsection, some media benchmarks have severe performance shortcomings due to the Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE k i j l MMX memory pattern MOM (2D) memory pattern 3D memory pattern i i j int fullsearch(blk1, blk2, length, i0, j0, int win) unsigned char *blk, *blk2; int length, i0, j0, win; { int l, d, i, j, k, min, pos; unsigned char *a,*b; ... ... for (k=0; k<l; k++) { a = blk1 + k; b = blk2; d = 0; for(j=0; j<8; j++) { for(i=0; i<8; i++) { d += abs(a[i]-b[i]); } a += length; b += length; } if (d<dmin) { min = d; pos = k; } } ... ... } Figure 4. N-dimensional memory patterns in a MPEG2 kernel. inability of any of the proposed vector memory systems to provide the required bandwidth. A way to identify the sources of the problem may come from a closer observation of MOM 2-dimensional memory pattern characteristics. If we turn back at the exampleshown if Ýgure 1, we realize that there is a long distance between consecutive MOM elements (as the stride between two different MOM register elements corresponds to the horizontal size of the image). Therefore, a vector memory system such as the vector cache is unable to fetch more than one MOM register element per cycle, as two consecutive elements are placed in non-consecutivecache lines Indeed, as already shown in [10, 11], strided matrices are a very common data structure in multimedia. These matrices are laid out in memory in such a way that, while the elements in a single row of one matrix are consecutively arranged in memory, elements beyond the Ýrst dimension are distributed across far away cache lines. From the set of benchmarks, only jpeg decode and gsm encode own memory patterns characterized for wide blocks of consecutive data along a single dimension. To solve this problem, some authors propose simply rearranging the data to Ýt a better layout. We have found that most of the times is either not possible (due to the way the benchmarks are written) or counterproductive (since it may produce even worse memory behavior in other stages of the applications). Our claim is that the solution for this problem may reside in the exploitation of more dimensions of the media memory layout than those already exploited by 2D vectors ISAs. More dimensions bring more opportunities to Ýnd longer sets of data consecutively arranged in memory, and hence, more opportunities to fully exploit the peak bandwidth of a wider memory port. If we look further intothe n-dimensionalstructure of media data, we can realize that a set of MOM 2-dimensional streams as a whole shows a higher level of spatial and temporal locality than every stream in isolation. If we reorder the way we access the streams, we can take advantage of the existence of longer chunks of data and from the redundancyintrinsic to the overlappingof different 2-dimensional streams. In the previous example (see Ýgure 4), the row elements of matrices a and b are extremely sparse. Therefore, if we use a vector cache, we are only able to gather the eight 8-bit elements of one row with a single access. Nevertheless, when looking at the third dimension of the algorithm (corresponding to loop k ), we can observe a 3-dimensional memory pattern composed of a set of 2dimensional matrices. These 2D matrices are laid out on the x-axis of the image (the loop i ) with an address offset (or stride) of one single byte. The overall structure is a rectangular matrix of length (8 + l ; 1)  8 . The interesting point of this structure is that it exposes several elements consecutively arranged in memory and that it determines a high amount of potential MOM 2D memory streams inside, as there is a high amount of overlapping between them. The main point is that, even though k loop cannot be fully vectorized,we can vectorizethe memory access to this 3-dimensional memory pattern, as there are no memory dependences betweenthe matrices of every instance of loop k . Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE By doing so, we are able to increase the effective memory bandwidth (as we are exposing longer chunks of data), and we are able to reduce the memory trafÝc (as we can avoid fetching repeatedly redundant data when streams overlap). 4 3D memory vectorization We propose a novel vector memory access technique based on implementing a new set of 3D vector registers. These 3D vector registers will be used as temporal storage for 3D memory streams fetched from memory. By doing sequential accesses to these second-level registers, we will be able to conveniently rearrange the 3D memory pattern to accommodate 2D MOM memory accesses. A 3D vector register is basically a widened version of a common MOM register. A 3D vector load instruction allows to transfer multiple cache lines inside the different elements of a single 3D vector register. Afterwards, the data in the 3D register Ýle can be transferred to the MOM register Ýle using a 3D vector move instruction. In the same vein that the MOM register Ýle, the 3D register Ýle is organized in lanes (or clusters). This organization enables very high bandwidth transfers with low hardware complexity. It is very important to note that from a compiler/programmer point of view, 3D memory instructions can be used even if the third outer loop is not strictly vectorizable. We are using these instructions to strictly fetch data from memory and to rearrange the data later on. Therefore, those computational dependences not related to read/write conÐicts between the 2D memory streams can be ignored. Our proposed 3-dimensional memory vectorization technique provides three signiÝcant advantages:  longer chunks of data accessed every cycle  reduction of cache trafÝc by means of register reuse  more elements packed per vector memory instruction In this paper, we will quantify how well the 3D memory instructions do improve the length of the chunks of data to be accessed, reduce the cache trafÝc and increase the number of elements packed per memory instruction. Finally, we will evaluate the impact of these factor over performance, power and robustness to the latency. 4.1 Semantics of the 3D memory instructions We haveused the MOMInstructionSet Architecture [18] as a representative example of a 2D media vector ISA. Our objective is to evaluate the potential of extending a 2D instruction repertoire with 3D memory instructions. The MOM Instruction Set Architecture contains 121 instructions and 16 logical 2D vector registers. Each 2D vector register is composed of 16 MMX-like elements of 64-bit each. The ISA includes a Vector Length register that keeps track of the number of MOM elements to be operated. Additionally, MOM memoryinstructions includean extraÝeld containing the Vector Stride to control the load and store of 2D memory patterns. We have made two modiÝcations to the basic MOM architecture: the set of logical registers has been expanded with the inclusion of two 3D vector registers, and the instruction repertoire includes two new instructions designed to transfer data to/from these new registers. A3D vector register is a widened version of a regular MOM register (see Ýgure 5 for a comparison of both kinds of registers). Instead of 16 elements of 8 bytes, a 3D vector register contains 16 elements of 128 bytes (16 x 64 bits), enough to Ýt a typical L2 cache line. Every 3D vector register has also a 7-bit pointer register, which maintains the current offset within the 3D vector register. This offset determines which slice of data is going to be transferred to a 2D MOM vector register. The two new instructions have the following syntax and semantics: 3D Vector Load. This instruction has the form Dvload 3 DR i < = R j , R k ,W,b. 3 DR i is one of the two 3D logical vectorregisters. R j is the base addresswhere the loadstarts. R k is the vectorstride. W is an 4-bitimmediate value which indicates the width of each 3D-register element. Finally, b is a Ðag that indicates the initial value of the 3D-register pointer. The semantics of the instruction are as follows (see Ýgure 5-a): starting at address R j , loada block of W  64 ; bit into the Ýrst position of 3D register i . Repeat the process, adding the stride register R k to the current base address, for the next VL ; 1 elements of the 3D register (being VL the contents of the Vector Length register). The value of the register pointer is either the beginningor the end of the register, accordingto the value ofthe Ðag b (this allows to move along the two ways of the third dimension). 3D Vector Move. This instruction allows to move one subset of the 3D logical vector register into a 2D MOM register and has the form 3dvmov MR i < =3 DR j , P s . MR i stands for the MOM destination register. 3 DR j is the 3D logical vector register from where the data is going to be transferred. P s is the pointer stride. The semantics of the instruction are as follows (see Ýgure 5-b): starting at offset ( offset being the contents, in bytes, of the pointer register associated with 3 DR j ), move a 64-bit sub-block from 3D-register j to the MOM register Ýle i . This process is repeated VL times ( VL being the contents of the Vector Length register). Finally, update the current value of the 3D register pointer by adding P s . 5 Evaluation background In this section we present the methodology we have followed to evaluate the beneÝts of the 3D memory vector extensions to the MOM ISA, and we quantify the improveProceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE ... ... 16 16 x 64 bits (a) byte byte ... ... 3D pointer Shift & Mask W VL 64 bits 64 bits (b) 16 16 x 64 bits byte 64 bits VL 3D register W 13D register 2D (MOM) register VL 16 Figure 5. 3D vector memory instructions (a) 3D vector load (from the vector cache to one 3D register) (b) 3D vector move (from one 3D register to one MOM register). ments of the new 3D memory instructions compared with the original 2D memory instructions. 5.1 Benchmarks and Code Generation We have used the set of modiÝed benchmarks described in [10]. From the Mediabench suite [17], the authors rewrote a set of representative examples of video, image and audio applications, using two versions of media ISA extensions: a 1D  -SIMD ISA (similar to MMX) and MOM. We have selected those with the highest vectorization percentage: mpeg2 encode,mpeg2 decode, jpeg encode,jpeg decode and gsm encode. The benchmarks show a wide selection of types of media memory streams, thus beingsuitable for evaluatingthe generality of our 3D memory instructions. We have modiÝed the emulation libraries and traces obtained using ATOM [19], so that we are able to include 3D memory instructions to the MOM versions of the benchmarks. The 3D memory instructions were added to those loops that fulÝlled either of the following conditions: (a) there was potential to fetch more that one MOM stream by loading a whole cache line, and (b) there was potential for reuse at the 3D register Ýle level due to overlapping between two or more MOM memory streams. From the set of benchmarks, only jpeg decode did not have suitable 3dimensional memory patterns to be exploited with our technique. For ourinitial evaluation, the 3Denhancedcode has been hand-written after a careful study of the algorithms. We believe,however,thatthecompilersupportneededforgenerating such instructions is relativelyfeasible to implement, due to the nature of the analysis. Since we are only vectorizing memory references, we do not need to check dependences beyond those related to conÐicting reading and writing 2D memory streams. As media kernels usually have lots of 2D loads and no 2D stores, the analysis is commonlytrivial (detecting the stride between the 2D load instructions to pack them together into a single 3D load and replacing the original 2D load instructions with 3D vector moves). 5.2 Characteristics of the new instructions In the previous section, we claimed that the performance beneÝts from the new 3D memory instructions would come from three main factors. In this section we will brieÐy quantify them and discuss their beneÝcial impact over the architecture. A. Longer data chunks accessed per cycle. Our 3D memory instructions focus on fetching wider blocks of data to capture slices from different MOM memory streams. As a result, they exhibit the potential to obtain more effective Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode 0 2 4 6 effective bandwidth (words/access) MOM multi-banked cache MOM vector cache MOM+3D vector cache Figure 6. Effective memory bandwidth (in words transferred per access) for the different memory systems and ISA enhancements. bandwidth from a vector cache conÝguration,that is able to access as many elements as the width of a cache line. To show this property, Ýgure 6 shows the effective bandwidth of different cache implementations with and without 3D instructions. We consider the effective bandwidth to be the average number of words that can be obtained with a single access to the cache (or to several banks concurrently in the case of the multi-banked cache). As shown in the Ýgure, 3D memory vectorization makes very good use of the simple vector cache implementation, increasing the effective memory bandwidth for several benchmarksand being even better than the expensivemultibanked conÝguration. Having longer consecutive sets of data to access each cycle will translate into two main beneÝts. First, we will increase the effective bandwidth of the vector memory system, thus reducingperformanceslowdown. Second, we will gather more data every time we access the cache, thus reducing the cache activity (and as a direct consequence, the power consumption). B. Reduction of the cache traffic. As we have a secondlevelregister Ýle thatis aware ofthe behavior ofthe memory references at the third dimension, we have opportunities to reducethe trafÝc to the cache bymeans ofreusing (totallyor partially) streams at the 3D register Ýle level. For instance, we may have 2D streams with data overlapping (as in the example of section 2), or sets of 2D streams that become invariant at the third dimension of the nested loops. In order to realize the impact of register reuse overtrafÝc reduction, we may look at Ýgure 7. In the Ýgure, we present the vector cache trafÝc reduction when including a 3D vector register Ýle, measured as the reduction of 64-bit words transferred from or to the vector cache sub-system. Reusing data at the register Ýle level has a clear impact on the power consumption of the system (as the accesses to the 3D register Ýle are cheaper, in energy terms, than the accesses to the cache banks). Additionally, the latency of jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode 0 20 40 60 80 100 Cache traffic reduction (%) Figure 7. Vector cache traffic reduction when using 3D vectorization (in 64-bit words transferred). MOM MOM + 3D 1st 2nd 3rd 1st 2nd 3rd (max) mpeg2encode 7.2 10.1 ñ 7.2 9.3 1.5 (5) mpeg2decode 4.2 7.4 ñ 4.2 6.2 1.7 (3) jpeg encode 4.1 8.2 ñ 4.1 7.8 1.9 (16) jpeg decode 5.5 15.9 ñ 5.5 15.9 ñ gsm 4.0 10.0 ñ 4.0 10.0 7.7 (16) Table 1. Memory instruction vector length for each of the three dimensions. the 3D register Ýle is much shorter than the cache, thus providing a way to alleviate the processor-memory speed gap impact. C. Longer vector memory instructions. It is widely known that the longerthe vectorsof a givenarchitecture, the better the ability to tolerate memory latency. Our 3D memory architecture extension provides two main beneÝts that have the potential to better tolerate increases in the latency of the memory instructions. First, we are actually doing a sort of software prefetching, as a 3D memory instruction triggers the fetching of streams of data several cycles before they will be really needed. Second, we pack more elements per memory instruction, thus taking advantage of the relation between the vector length and the tolerance to memory latency. Table 1 presents the average vector length along each dimension in every memory instruction (two dimensions for plain MOM memory instructions, three dimensions when including 3D memory instructions). Taking into account that the 3D memory instructions are typically less predominant than the 2D memory instructions (as they are around 4 times longer, and hence, fewer 3D loads are required when taking advantage of the 3D register reuse), we may realize how the third dimension is contributing to the amount of data read by each instruction. Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE MMX MOM Fetch rate 8 8 graduation window 128 128 Load/Store queue 32 32 INTEGER issue 4 4 INTEGER FUs 4 4 SIMD issue 4 1 SIMD FUs 4 1x4 memory issue 4 2 L1 memory ports 4 2 L2 vector memory ports n/a 1x4 Table 2. Processor configurations. 5.3 Modeled architecture We have used the Jinks simulator [10] to model an aggressive 8-way out-of-ordersuperscalar processor. The processor is enhanced with its own independent multimedia pipeline and SIMD register Ýle. We have two versions of the same model, able to executeeither MMX-style or MOM instructions. Architectural parameters are summarized in table 2. As seen, the MMX conÝguration is aggressive in number of registers and functional units to avoid an unfair comparison with MOM. Note that the MOM processor has one SIMD functional unit with four lanes or clusters. Every cluster is able to perform one MOM operation/cycle from the same MOM instruction, thus providing overall the same FU bandwidth than the MMX processor (Ýgure 8-b illustrates the MOM lane conÝguration). In order to implement the combined 2D/3D memory mechanism in the MOM architecture, we need to include two new register Ýles: the3D Vector Register File, that contains 4 physical 3D vector registers and the 3D Pointer Register File which keeps the coherent values of the pointers for each logical 3D vector register. Note that the renaming process of the 3D physical vector registers and the physical pointer registers is not the same. For instance, a 3dvmov operation (which moves a slice from a 3D vector register to a MOM register) causes the pointer register to be renamed, as its value is updated using the pointer stride. Table 3 summarizes the different register Ýle conÝgurations. We have assumed 3 cycles of latency for the 3D vector register Ýle (but 1 cycle per transfer). We have estimated the area cost of the different register Ýles using the models described in [20]. Estimated register Ýle areas (in square wire tracks) and overall normalized areas (relative to the MMX-like processor) are included in table 3. Figure 8 shows the vector memory sub-system implementation. Our basic cache hierarchy model is similar to the Alpha 21364 [21] one, where both L1 and L2 caches are located on-chip. The L1 cache is a 64 KB, 2-way set associative, write-through cache with 32-byte lines. The L2 cache is a 2MB, 4-way set associative, write-back cache MMX MOM MOM+3D MMX/MOM Register File register size 64 b 16x64b 16x64b logical/physical registers 32/80 16/36 16/36 read ports (per lane) 12 3 3 write ports (per lane) 8 2 2 max memory bandwidth 4 4 4 estimated area ( wt 2 ) 2,826,240 2,654,208 2,654,208 cache buses ( wt 2 ) 262,144 262,144 n/a Accumulator Register File register size n/a 192b 192b logical/physical registers n/a 2/4 2/4 read ports n/a 1 1 write ports n/a 1 1 estimated area ( wt 2 ) n/a 23,040 23,040 3D Vector Register File register size n/a n/a 16x16x64b logical/physical registers n/a n/a 2/4 read ports (per lane) n/a n/a 1 write ports (per lane) n/a n/a 1 max memory bandwidth n/a n/a 16 estimated area ( wt 2 ) n/a n/a 1,966,080 3D Pointer Register File register size n/a n/a 7b logical/physical registers n/a n/a 2/8 read ports n/a n/a 2 write ports n/a n/a 2 estimated area ( wt 2 ) n/a n/a 3,136 Estimated RF area 3,088,384 2,939,392 4,646,464 Overall normalized area 1.00 0.95 1.50 Table 3. Multimedia register file configurations. with 128-byte lines. L1 data cache latency is 1 cycle while L2 cache latency is 20 cycles. The instruction cache has not been simulated given the extremely low instruction miss rates measured. We have decided to adopt the same cache hierarchy conÝguration proposed for the original MOM architecture [16, 22]. In this architecture, the MOM memory accesses bypass the L1 cache and go straight to the L2 cache. As interference between vector and scalar data might occur, a simplecoherence protocol, based on an exclusive-bit policy, was proposed. Several reasons explain why is worth paying the extra latency and implementing the vector memory sub-system over the second level of cache. First, we avoid jeopardizing the L1 cycle time and latency, thus not compromising scalar performance,which is paramount for the target architecture. Second, the L2cache has longercache lines than theL1 data cache, hence increasing the potential performanceof the already cost-efÝcient vector cache implementation. Looking at Ýgure 8-a and 8-b , we can compare the implementation of a 4-port multi-banked cache and a vector cache for the original MOM architecture. The interconnection logic of the vector cache is signiÝcantly simpler than its multi-bankedcounterpart. Note, however, that the vector cache peak bandwidth is limited by the number of lanes of the MOM pipeline (4 for our conÝguration). Even though Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE Shift & Mask Interchange Initial Address Final Address VRF0 VRF1 VRF2 VRF3 (a) Shift & Mask Interchange Initial Address Final Address 3D VRF 0 3D VRF 1 (c) 3D VRF 2 3D VRF 3 VRF0 VRF1 VRF2 VRF3 VRF0 VRF1 VRF2 VRF3 bank 0 bank 1 bank 2 bank 3 bank 4 bank 5 bank 6 bank 7 X (b) 64 64 64 64 64 64 64 64 64 64 64 64 64 64 16x64 64 64 64 64 64 64 64 64 64 64 Figure 8. Vector memory sub-system implementations: (a) multi-banked cache, (b) vector cache, and (c) vector cache and secondlevel 3D vector register file. the 4x8 crossbar required for the multi-banked cache is not simple, we have not considered any extra latency to the cache access pipeline. Figure 8-cshowsthe vectormemorysystem implementation, but this time for the MOM architecture with 3D memory instructions. Note that the 3D vector register Ýle is distributed over as many lanes as the MOM register Ýle. The different widened elements of the 3D physical vector registers are distributed within these lanes. All the different 3D vector lanes are connected to the same array of bitlines. So, every cycle, a chunk of up to 128 bytes of data can be fetchedfrom the L2 cacheand can be directlywritten in parallel to one of the 3D vector register Ýle lanes. Therefore, the effective memory bandwidth may be as large as the size jpeg encode jpeg decode mpeg2 decode mpeg2 encode gsm encode 1.0 1.2 1.4 1.6 Performance slowdown MMX-like multi-banked cache MMX-like ideal memory MOM multi-banked cache MOM vector cache MOM+3D vector cache Figure 9. Performance slowdown for the different ISA and memory sub-system configurations. of a whole L2 cache line. While large chunks of data are written in one of the 3D vector lanes, one 64-bit element can be read from each of these lanes. As a result, we have a peak transfer rate of four 64 bits elements per cycle between the 3D vector register Ýle and the MOM register Ýle. Note that the 3D register Ýle allows byte-aligned accesses. From the point of view of implementation, we would typically require a mechanism that fetches two consecutive quadwordaligned elements and that is able to use a shift&mask logic block to extract the required 64-bit element. 6 Performance and power benefits of 3D memory vectorization In this section we will evaluate the beneÝts provided by 3D memory vectorization in terms of performance slowdown relative to an idealistic memory system and will analyze the impact of increasing the cachelatency. Finally, we will roughly estimate the power savings leveraged by the reduction of the cache activity. 6.1 Performance slowdown with realistic memory Figure 9 shows the performance slowdown of different ISA and memory sub-system conÝgurations, relative to the performance of a MOM processor with an idealistic memory system (single cycle of latency, effective bandwidth equal to the peak bandwidth). The Ýgure allows us to determine how well a given memory system performs over a speciÝc ISA style. First, Ýgure 9 allows us to see the effect of a realistic memory implementation over the performance of the MMX-like conÝguration processor. As seen in the Ýgure, software prefetchingcombinedwith a way of avoiding bank collisionswouldapproximatetheperformanceoftheMMXlike system to the one of an idealistic memory system, but it would still be far from the performance of the idealistic MOMsystem (1.31Xofperformanceslowdowninaverage). The reason is that the MMX-style processoris limited by issue bandwidth and not by memory bandwidth. Proceedings of the 35 th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-35) 1072-4451/02 $17.00 © 2002 IEEE