Distributed data cache designs for clustered VLIW processors

Distributed Data Cache Designs for Clustered VLIW Processors Enric Gibert, Jesu ´sSa ´nchez, Member,IEEE, and Antonio Gonza ´lez, Member,IEEE Abstract—Wire delays are a major concern for current and forthcoming processors. One approach to deal with this problem is to divide the processor into semi-independent units referred to as clusters. A cluster usually consists of a local register file and a subset of the functional units, while the L1 data cache typically remains centralized in what we call partially distributed architectures. However, as technology evolves, the relative latency of such a centralized cache will increase, leading to an important impact on performance. In this paper, we propose partitioning the L1 data cache among clusters for clustered VLIW processors. We refer to this kind of design as fully distributed processors. In particular, we propose and evaluate three different configurations: a snoop-based cache coherence scheme, a word-interleaved cache, and flexible L0 buffers managed by the compiler. For each alternative, instruction scheduling techniques targeted to cyclic code are developed. Results for the Mediabench suite show that the performance of such fully distributed architectures is always better than the performance of a partially distributed one with the same amount of resources. In addition, the key aspects of each fully distributed configuration are explored. Index Terms—Single data stream architectures, design styles. æ 1INTRODUCTION ASfeature sizes shrink, wire delays become slower relative to gate delays [32], [1]. For example, in the Pentium4 processor [20], some stages of the pipeline are mainly dedicated to propagating signals along the chip. One solution to this problem is to divide the processor into semi-independent units referred to as clusters. A cluster often consists of a local register file and a subset of the functional units while other processor resources remain centralized. We refer to this kind of architecture as a partially distributed architecture. Local communications (communications inside a cluster) are fast, while global communications (intercluster communications) are slow. Intercluster communications are used to propagate register values when the producer and the consumer of a value are assigned to different clusters. Hence, instructions should be assigned or steered to clusters so that global communications are minimized while workload balance among clusters is maximized. A typical cluster configuration can be seen in the left part of Fig. 1. Clustering not only solves the wire delay problem, but it also helps reduce power consumption since some of the power-hungry processor structures, such as the issue queue, the bypass network, and the register file, are partitioned. The use of an integer and a floating-point cluster is common in commercial out-of-order superscalar microprocessors. Such processors differentiate between the integer pipeline and the floating-point pipeline in order to reduce the complexity of the issue queue, the bandwidth of the broadcast network, and the access bandwidth to the integer and floating-point register files. More recent designs, such as the Alpha 21264, partition the integer pipeline into two clusters [19]. However, the use of clustering is even more noticeable in the embedded/DSP market in which clustered VLIW organizations are common [18], [41], [13], [12]. As wire delays increase relative to gate delays, having a centralized L1 data cache that can be quickly accessed by all clusters is becoming unfeasible. The cache could be close to one or a few clusters but not to all of them. Besides, the access time to the cache grows with its capacity. Hence, the distribution of the data cache among clusters will be a key performance issue in future microprocessors whose performance will be dominated by wire delays. In order to do that, the L1 data cache can be partitioned into different smaller cache modules and one cache module can be assigned to each cluster, as shown in the right part of Fig. 1. Memory accesses to the local cache module are fast, while memory accesses to remote cache modules or to the centralized next level cache are slow. The distribution of the data cache among clusters poses new challenges. First, there are multiple alternatives on how the L1 data cache can be partitioned into different cache modules and how data is mapped to these modules. And, second, a new cache coherence problem arises and mechanisms must be introduced in order to guarantee data consistency. We will refer to this kind of architecture as fully distributed architecture. Few research works have dealt with the distribution of the data cache among clusters so far ([43], [46], [34]) and fully distributed architectures have not been implemented in any commercially available processor yet. Most of these research works are targeted at out-of-order superscalar processors. In such proposals, instructions are assigned to clusters at runtime by using several hardware tables and prediction techniques. Performance results demonstrate that the distribution of the data cache among clusters is a viable solution to overcome the wire delay problem in the memory hierarchy. In this work, we focus on statically IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 10, OCTOBER 2005 1227 .The authors are with Intel Labs Barcelona-Universitat Polite `cnica de Catalunya, c/ Jordi Girona, 29, Edifici Nexus II, 3a planta, 08034 Barcelona, Spain. E-mail: {enricx.gibert.codina, f.jesus.sanchez, antonio.gonzalez}@intel.com. Manuscript received 19 Apr. 2004; revised 23 Dec. 2004; accepted 5 Apr. 2005; published online 16 Aug. 2005. For information on obtaining reprints of this article, please send e-mail to: [email protected], and reference IEEECS Log Number TCSI-0134-0404. 0018-9340/05/$20.00 ß2005 IEEE Published by the IEEE Computer Society scheduled processors (e.g., VLIW) instead of out-of-order superscalar processors. In statically scheduled processors, performance is very much related to the ability of the compiler to generate effective code. Thus, an additional challenge for clustered VLIW processors with a distributed data cache is to develop instruction scheduling techniques in order to exploit the underlying architecture efficiently. Such instruction scheduling techniques must include techniques to increase the percentage of local memory accesses since they are executed faster than memory accesses satisfied by remote cache modules or by the centralized next level cache. Our baseline partially distributed architecture consists of four clusters, where each one has a subset of the functional units and a local register file. For the sake of simplicity, all clusters are assumed to be homogeneous. All other resources (including the memory hierarchy) are global to all clusters. Each cluster executes a fixed part of the VLIW instruction and all clusters execute in lock-step mode: If a cluster stalls when the consumer of a load instruction is executed but data is not ready yet, all other clusters are stalled as well. We assume that intercluster communications are realized through a set of global buses referred to as register-to- register communication buses or register buses for short. These buses are controlled by the compiler, which is responsible for adding and scheduling an explicit copy operation whenever it assigns two register-flow dependent instructions to different clusters. This paper presents a comparative study of different architecture/compilation techniques that we have recently proposed for fully distributed clustered VLIW processors ([38], [15], [17]). For each proposed architecture, efficient instruction scheduling techniques are developed, which are strongly tied to the architectural configuration in order to exploit its particularities. Such scheduling techniques are targeted to cyclic code and perform modulo scheduling of inner loops, which account for most of the benchmarks’ execution time. The rest of this paper is organized as follows: In Section 2, a brief introduction to modulo scheduling is performed since the proposed algorithms are built on top of it. The compilation and simulation infrastructure is described in Section 3, along with the benchmarks that have been used. Next, each architecture/scheduling algorithm pair is presented in a different section. For each architecture configuration, the three main challenges for distributing the data cache are discussed: the architecture itself, the scheduling algorithm targeted to it, and memory coherence. In addition, each configuration is evaluated individually. First, the MultiVLIW is introduced in Section 4. Next, a wordinterleaved cache clustered VLIW processor is presented in Section 5, while Flexible Compiler-Managed L0 Buffers are explained in Section 6. The proposed architectural schemes/compiler techniques are then compared in Section 7. Finally, some related work is outlined in Section 8 and conclusions are drawn in Section 9. 2MODULO SCHEDULING AND SWING MODULO SCHEDULING Modulo scheduling is an effective technique to extract instruction-level parallelism (ILP) from loops by overlapping the execution of successive iterations of the original loop without the need to unroll it [8], [35]. It is a wellunderstood technique used by many current compilers. The parameters that most affect the performance of a modulo scheduled loop are the Initiation Interval (II) and the Stage Count (SC). The II is the number of cycles between the initiation of consecutive iterations. For loops with a high trip count, the execution time is almost proportional to the II. Modulo scheduling algorithms begin by computing a Minimum II (MII) for a given loop. The MII is bounded by resource usage and recurrences in the Data Dependence Graph. After that, modulo scheduling algorithms start an iterative process trying to find a valid schedule with the lowest possible value of the II starting with the MII. On the other hand, the Stage Count (SC) specifies the number of overlapped iterations. Swing Modulo Scheduling (SMS) is one of the most effective modulo scheduling techniques [27], [11]. It is basically a heuristic to sort the instructions of the Data Dependence Graph (DDG) so that a valid schedule is found with the MII most of the time, combined with a bidirectional scheduler. SMS gives priority to instructions in recurrences according to the constraints they impose on the II. It has been demonstrated that giving priority to critical instructions is good to achieve tight schedules. In particular, recurrences are sorted from most to least restrictive in terms of II. Within each recurrence, nodes are sorted so that most of them (all except one per recurrence) have only predecessors or successors placed prior to them in the ordered list. 1 This is beneficial for reducing register pressure [21], [10]. 1228 IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 10, OCTOBER 2005 1. Nodes that belong to more than one recurrence are listed with the most restrictive one. Fig. 1. A typical clustered processor (left) and a clustered processor with a distributed L1 data cache (right). In both cases, a four cluster configuration is assumed. In this work, we develop instruction scheduling techniques for cyclic code. In particular, we propose a modulo scheduling algorithm for each of the proposed distributed cache architectures. 3TOOLS AND CONFIGURATIONS The IMPACT compiler [7] has been used as the main infrastructure to compile the benchmarks, optimize them, and build hyperblocks [28]. The benchmarks we have used are the Mediabench suite [26] since they represent workloads that can be found in embedded processors such as DSPs. The benchmarks and their inputs are summarized in Table 1. We evaluate the performance of the three proposed architectures that are explained in the following sections: the MultiVLIW, a word-interleaved cache clustered VLIW processor and a clustered VLIW processor with Flexible Compiler-Managed L0 Buffers. They are compared with a partially distributed processor (a clustered architecture with a unified L1 data cache). In all configurations, we have assumed a 4-cluster architecture in which all clusters are homogeneous and each one has one integer, one memory, and one FP functional unit. The architectural parameters used in our simulations are summarized in Table 2. We have assumed that the latency of a centralized L1 data cache is the same as the access time to a remote cache module when the cache is distributed. In addition, we use the same bandwidth for all cache configurations. In case of a unified 8KB cache, four read/write ports to the cache have been assumed, whereas one read/write port cache module has been used when the cache is partitioned. For each architecture configuration, we have used the proposed scheduling algorithm in order to perform modulo scheduling of inner loops, which account for approximately 80 percent of the total execution time. 4THE MULTIVLIW 4.1 Architecture Sa ´nchez and Gonza ´lez [38] proposed partitioning the L1 data cache into different cache modules and attaching a cache module to each cluster. A snoop-based cache coherence protocol such as MSI (used in multiprocessor architectures [42]) is used to guarantee coherence among the different cache modules. A memory access that is satisfied by the local cache module has short latency, while memory accesses requesting data that is mapped remotely or coherence transactions, such as invalidation messages, take longer. Although all clusters work in lock-step mode, the use of a cache coherence protocol found in multiprocessor systems led the authors to use the term Multi- VLIW to refer to this architecture. The main advantage of the MultiVLIW is that data is replicated/moved dynamically to the clusters that make use of it based on the access pattern of the instructions. However, data replication may limit the effective capacity of the cache. In addition, a hardware cache coherence protocol may have a high cost, especially in the embedded/ DSP domain. 4.2 Instruction Scheduling Algorithm The instruction scheduling algorithm proposed for this architecture is explained in this section. The core of the algorithm will also be used for the following architecture configurations, so it is exposed here in deeper detail. A graphical view of the algorithm is shown in Fig. 2. Since data is already moved dynamically to the clusters that make use of it in the MultiVLIW, no additional techniques to increase local accesses are used. Given a Data Dependence Graph (DDG) representing a loop, the algorithm starts by sorting its nodes using the GIBERT ET AL.: DISTRIBUTED DATA CACHE DESIGNS FOR CLUSTERED VLIW PROCESSORS 1229 TABLE 1 Benchmarks and Inputs Used in Simulations along with the Relevant Command Line Arguments Used to Run the Programs The main data type is listed in the last column, along with the amount of dynamic memory accesses to this data type. SMS heuristic explained in Section 2. Once the nodes are ordered, the algorithm proceeds by scheduling one instruction at a time. For each instruction, the set of possible clusters where it can be scheduled is computed. This set contains the clusters with enough free resources to execute the instruction. If the instruction cannot be scheduled in any cluster, the II is increased and the whole scheduling process starts again. On the other hand, if the set of possible clusters is not empty, it is ordered so that clusters where global communications are minimized are selected first. In addition, clusters that incur the same overhead in terms of global communications are again ordered by giving priority to clusters with fewer instructions already assigned to them. The idea is to minimize global communications and maximize the workload balance among clusters at the same time. Finally, the instruction is scheduled in the first cluster of the set where a valid slot is found. If the schedule is not possible, the II is increased and thewhole process starts again. 5AWORD-INTERLEAVED CACHE CLUSTERED VLIW PROCESSOR 5.1 Architecture Another way to partition the L1 data cache is to distribute a cache line among clusters in a word-interleaved manner [15]. In such a configuration, each cache module will hold some words of each memory block, depending on the data address and the interleaving factor of the architecture. We use the term subblock to identify words of the same memory block that are mapped into the same cache module. For example, assuming a 4-cluster architecture, 8-word cache lines, and an interleaving factor of 1 word, words 0 and 4 of a given cache line form a subblock that will always be mapped to cluster 1, as can be seen in Fig. 3. Note that each piece of data is mapped in a single cache module, so there is no data replication, as opposed to the MultiVLIW in which the same piece of data may be present in different cache modules at the same time. A memory access in a word-interleaved cache clustered VLIW processor can be satisfied with four different latencies (assuming a perfect L2 data cache or main memory): .Local hit: If the memory access references a local subblock and it is present in the local cache module. .Remote hit: If the memory access references a remote subblock and it is present in the corresponding remote cache module. .Local miss: If the memory access references a local subblock and it misses in the local cache module. .Remote miss: If the memory access references a remote subblock and it misses in the corresponding remote cache module. With such a static binding between addresses and clusters, compiler techniques are key to increasing the ratio 1230 IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 10, OCTOBER 2005 TABLE 2 Architectural Parameters for Each Configuration Fig. 2. Modulo scheduling algorithm for the multiVLIW. This algorithm is later refined to generate efficient code for the other architectural configurations. of memory accesses that are satisfied locally. Although the proposed techniques increase the proportion of local accesses by 27 percent on average, small buffers in each cluster are an effective hardware technique to hold remotely mapped data and further increase the ratio [14]. The idea is to amortize a costly remote access. When a cluster accesses a remote subblock, the whole remote subblock is returned to the cluster and cached in its local buffer. These buffers are handled as a regular cache structure and the next access to a cached remote subblock will be satisfied locally if it has not been replaced from the buffer. These buffers are referred to as Attraction Buffers since data is attracted to the cluster that accesses it. An example of Attraction Buffers is shown in Fig. 4, where data mapped in cluster 4 is attracted to cluster 1. Techniques to keep cache modules and Attraction Buffers coherent are explained in Section 5.3. 5.2 Instruction Scheduling Algorithm We have adapted the proposed scheduling algorithm explained in Section 4.2 in order to generate code for a word-interleaved cache clustered VLIW processor. The algorithm has been divided into several steps, which are covered in deeper detail next. These steps are: 1. Profiling and variable alignment: Gathering information of memory accesses. 2. Loop unrolling: In order to increase local accesses. 3. Latency assignment: To schedule each memory instruction with its “appropriate” latency. 4. Sorting the nodes of the Data Dependence Graph (DDG). 5. Cluster assignment and scheduling. 5.2.1 Profiling and Variable Alignment Due to the static binding between addresses and clusters in a word-interleaved cache clustered VLIW processor, it is very important to develop techniques to increase the number of local accesses. Such techniques rely on information for each memory instruction that is gathered through profiling. We will refer to the amount of times an instruction is expected to access each cluster as the access pattern of the instruction. Such information may be different when a different input set is used. For example, if a memory instruction I accesses a heap variable V and has an access pattern of {100, 0, 0, 0} (meaning that it accessed elements of V mapped in cluster 1 100 times, while it never accessed elements mapped in other clusters), it is reasonable to GIBERT ET AL.: DISTRIBUTED DATA CACHE DESIGNS FOR CLUSTERED VLIW PROCESSORS 1231 Fig. 3. A 4-cluster word-interleaved cache clustered VLIW processor. L1 blocks are split into subblocks which are statically assigned to clusters based on their addresses and the interleaving factor. Fig. 4. Attraction Buffers are a complexity-effective hardware mechanism to increase local accesses. In this example, the interleaving factor is equal to the size of array a’s elements. schedule I in cluster 1, which is its preferred cluster or its most accessed cluster during profiling. However, V may be aligned differently when another input is used and I’s preferred cluster may not be cluster 1 anymore. In order to mitigate alignment differences among input sets, variable alignment is enforced. In particular, stack frames are aligned so that their first word is always mapped in cluster 1. On the other hand, heap variables are aligned in the same way by forcing malloc-type routines to return pointers aligned to the first cluster. Finally, global variables are not aligned in any special way since they are always mapped in the same addresses, regardless of the input data. 5.2.2 Loop Unrolling Before scheduling, the compiler performs loop unrolling. Loop unrolling helps improve the performance of modulo scheduled loops for unified and clustered architectures [37]. For a word-interleaved configuration, unrolling has an additional advantage: It can help increase local accesses. For example, imagine the following piece of code: for (i=0; i<MAX; i++) { load a[i] perform computations store b[i] } where array elements are 4-bytes long and a 4-byte interleaving factor is used to distribute data among clusters. Given a 4-cluster architecture, three out of four memory accesses will be remote, no matter where memory instructions are scheduled. However, if the loop is unrolled four times, each memory instruction will access data mapped in a single cluster. If the compiler is able to assign each memory instruction to its appropriate cluster, all memory accesses will be satisfied locally. In order to compute the Optimum Unrolling Factor 2 (OUF) for each loop, the compiler takes into account the stride of eachmemory instruction in the loop, the number of clusters, and the interleaving factor. The stride of memory instructions is computed statically by the compiler. Memory instructions without a stride are not considered when computing the OUF of each loop since it is difficult to predict their access pattern. Although unrolling may be beneficial, the compiler may be applying excessive unrolling if every loop is unrolled by its OUF, leading to code explosion. For example, the OUF of a loop that has memory instructions with a 1-byte stride is 16, assuming a 4 cluster architecture with an interleaving factor of 4 bytes. Memory accesses with 1-byte and 2-byte strides are common in the evaluated benchmarks. In addition, excessive unrolling may generate loops that iterate few times, making them not suitable for modulo scheduling. These two drawbacks, together with the use of small Attraction Buffers in each cluster in order to increase local accesses by hardware, advocates for the use of a more selective unrolling process. In particular, the compiler chooses among three different unrolling factors instead of always using OUF and chooses the best one for each loop in terms of less expected compute time. The three factors are: 1 (no unroll), N(unroll by N,Nbeing the number of clusters), and OUF. The compute time of a loop L is estimated by the compiler using the following formula: TcompL¼ðavg num iterationsLþSCL1ÞIIL: 5.2.3 Latency Assignment Memory instructions do not have a deterministic latency. Hence, they can be scheduled with different latencies, such as the hit latency or the miss latency, based on profiling information or some other heuristics. Scheduling memory instructions with small latencies (hit latency) reduces compute time since tighter schedules are achieved. However, if instructions miss in the cache, stall time is increased. On the other hand, if memory instructions are scheduled with large latencies (miss latency), compute time is increased, but stall time is reduced. It has been shown that a hybrid mechanism in which memory instructions are selectively scheduled with one or another latency based on a locality analysis is a good trade-off between compute time and stall time and performance is improved [36]. This is done in this step of the algorithm. Since a memory instruction can be classified into four different groups in a word-interleaved cache clustered VLIW processor (local hit, remote hit, local miss, remote miss), each memory instruction may be scheduled with four different latencies. Given a loop, the compiler will first assign the largest latency (remote miss) to all memory instructions. However, execution time may be greatly increased with this initial assignment compared to that achieved if all memory instructions were assigned and scheduled with the smallest latency (local hit). Thus, an iterative process reassigns smaller latencies to some selectively chosen instructions in order to achieve an execution time similar to the latter. The idea is to assign smaller latencies to memory instructions that will probably be satisfied with latency. For instance, assume the following loop that has not been unrolled and assume that all instructions have a 100 percent hit rate: for (i=0; i<MAX; i++) { load a[i] load b[4*i] compute store a[i] } load b½4iaccesses the same cluster for all iterations and will be transformed into local accesses if scheduled properly. Hence, its latency is reduced before the latency of load a½ithat will access a remote cluster most of the time. A benefit function B is computed for each instruction in the loop. This benefit function describes how good would be to reduce the latency of an instruction Ifrom Lto L0(L0 always being smaller than L). The benefit function is the following: BðI; L; L0Þ¼rExecution Time Stall T ime : This function corresponds to the ratio between the expected decrease in execution time if the latency reduction was performed for that particular instruction divided by the expected increase in stall time. In order to compute the expected increase in stall time, profiling information 1232 IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 10, OCTOBER 2005 2. The unrolling factor that guarantees that all memory instructions in the loop with a known strike will access data mapped in a single cluster for all iterations. gathered in Step 1 is used. For example, the ratio of local accesses versus remote accesses is used to account for the times the instruction will be executed with a local or a remote latency and this information is derived from the access pattern of the instruction. In addition, the hit rate is used to estimate the ratio of local or remote hits and local or remote misses. On the other hand, the impact of the instruction on the II is used to estimate the decrease in execution time if its latency is reduced. The compiler reassigns the latency of the instruction with highest benefit and iterates by recomputing the benefit function for the rest of the instructions and by changing the latency of one instruction at a time. This iterative process finishes when the expected execution time of the loop is the same as if all memory instructions were scheduled with the smallest latency. 5.2.4 Sort the Nodes of the DDG After the latency of all instructions has been assigned, the algorithm sorts them using the Swing Modulo Scheduling (SMS) ordering phase, as was done in the previous algorithm. 5.2.5 Cluster Assignment and Scheduling Finally, the algorithm starts the scheduling process itself. For each node or instruction, the algorithm computes the set of possible clusters where it can be scheduled. As explained before, this set contains the clusters with enough free resources to execute the instruction. If the instruction cannot be scheduled in any cluster, the II is increased and the whole process starts again as was done in the previous algorithm. If the set of possible clusters is not empty, it is then sorted. For memory instructions, priority is given to each instruction’s preferred cluster (the cluster it accessed most during profiling), which is placed at the beginning of the set. The rest of the clusters are ordered by giving priority to clusters that minimize global communications and maximize workload balance. Finally, the instruction is scheduled in the first cluster of the set where a valid slot is found. 5.3 Memory Coherence Memory instructions must be scheduled carefully in order to guarantee memory coherence [16]. Coherence may be corrupted if memory requests accessing the same memory address are not satisfied in the original program order. For instance, if a load instruction scheduled in cluster 1 at cycle i accesses variable Xthat is mapped in cluster 3 and a store instruction to the same variable is scheduled in cluster 4 one cycle later, coherence is corrupted if the store instruction updates Xbefore it is read. This scenario is shown in Fig. 5. Although the compiler has scheduled the store one cycle after the load, this situation can still occur due to the nondeterministic latency to reach a remote cluster. When the remote request derived from the load instruction is issued, the memory bus may be busy due to other remote accesses, invalidation requests, replacements, etc., that can lead to a situation in which the store request reaches cluster 2 before the load request. In addition, coherence must be kept among Attraction Buffers, which may cache different copies of the same data. The solution to this problem is to restrict, to some extent, the assignment of memory instructions to clusters. In particular, the scheduling algorithm forces memory dependent instructions to be scheduled in the same cluster since the serialization of memory accesses is guaranteed within a cluster but not among clusters. Hence, the compiler builds memory dependent sets and assigns and schedules memory instructions belonging to the same set to the same cluster. In the example of Fig. 5, either the load should be scheduled in cluster 4 or the store in cluster 1. Memory dependent sets are constructed after applying some kind of high-level memory disambiguation analysis [9]. It should be pointed out that the compiler always stays on the conservative side when performing such a type of analysis: Whenever it cannot determine whether two memory instructions will access the same data, it will add a memory dependence between them. In order to reduce theimpactofsuchassignmentconstraints,memory dependent sets are built for each loop independently. Thus, these constraints are only applied on a loop basis. In order to guarantee coherence between loops, the execution of a loop does not proceed until all memory accesses of the previous loop have reached their home cluster, the home cluster being the one where the data is statically mapped. Note that this solution also guarantees coherence among Attraction Buffers since memory instructions accessing the same piece of data are assigned and scheduled into the GIBERT ET AL.: DISTRIBUTED DATA CACHE DESIGNS FOR CLUSTERED VLIW PROCESSORS 1233 Fig. 5. The latency of a memory bus is not deterministic. Hence, memory instructions may proceed in an order different from the original program order if the scheduling algorithm does not restrict the assignment of memory instructions to clusters. This is known as the memory coherence problem. same cluster and will use a single Attraction Buffer. 3 Once a loop exits, the contents of all Attraction Buffers are flushed. 5.4 Evaluation In this section, some of the proposed mechanisms and techniques for a word-interleaved cache clustered VLIW processor are evaluated. We should point out that an interleaving factor of 4 bytes has been used since 4-bytes are one of the most common data types in the simulated benchmarks, as shown in the last column of Table 1. The impact of the proposed scheduling techniques on the local ratio (the proportion of local versus remote accesses) is studied first. In Fig. 6, memory accesses have been classified into local hits, remote hits, local misses, remote misses, and combined accesses. Combined accesses are accesses to subblocks that have already been requested and are still pending and, hence, the second request is not issued. These combined accesses can result in hits or misses and they have just been counted as a separate group. The y-axis represents the ratio of all memory accesses. For each benchmark, four bars are drawn. From left to right, these bars represent the results of the proposed scheduling algorithm with 1. no unrolling with variable alignment, 2. OUF unrolling without variable alignment, 3. OUF unrolling with variable alignment, and 4. OUF unrolling with variable alignment and no memory dependent sets, where memory instructions are freely scheduled in their preferred cluster. Note that this last column is shown for comparison purposes since coherence is not guaranteed (memory accesses may reach memory out of program order, although coherence is guaranteed by hand in our simulator in order to maintain correct execution). As can be seen, loop unrolling and variable alignment help increase the percentage of local hits. In particular, the local hit ratio is increased by 20 percent on average when variable alignment is used for OUF unrolling (comparing the second and the third columns), while it is increased by 27 percent on average between no unrolling and OUF unrolling, both with variable alignment (comparing the first and the third columns). This indicates that the proposed strategies are successful in increasing the proportion of memory accesses that are satisfied locally. Furthermore, variable alignment increases the size of the benchmarks’ working sets by only 6 percent on average. This increase is concentrated in the programs with the smallest working sets (g721dec and g721enc) and it translates into a negligible impact on the hit rate and performance. Although the percentage of local accesses is large for some benchmarks, remote accesses are still important in some applications. Remote accesses are due to: .Double precision accesses in which memory instructions access data elements bigger than the interleaving factor. These accesses require at least one remotely mapped word. This type of access accounts for 50 percent of all accesses in mpeg2dec. .Indirect accesses of the form a½b½i. This type of access is very common in jpegdec, jpegenc, pegwitdec, and pegwitenc. .Memory accesses with an ”unclear” preferred cluster. These include indirect accesses that have been introduced before and accesses such as the following two examples: for (i=0; i<N; i++) { for (j=i; j<N; j=j+4) { load a[j] ... } } for (i=0; i<N; i++) { p++; q=p; /* p & q are pointers */ for (j=0; j<N; j=j+4) { load *q q=q+4 ... } } whereweassumethatinnerloopshavebeen unrolled OUF times and, in both load instructions, access the same cluster once the inner loop is entered. This type of access is common in jpegdec and jpegenc. .Memory dependent sets. Memory instructions in a memory dependent set are not scheduled in their preferred cluster but on the average preferred 1234 IEEE TRANSACTIONS ON COMPUTERS, VOL. 54, NO. 10, OCTOBER 2005 Fig. 6. Each bar from left to right represents the classification of memory accesses using: 1) no unrolling with variable alignment, 2) OUF unrolling without variable alignment, 3) OUF unrolling with variable alignment, and 4) OUF unrolling with variable alignment and no memory dependent sets (memory instructions are freely assigned to their preferred cluster). 3. Memory instructions accessing the same data may be assigned and scheduled into different clusters as long as all memory instructions accessing this data are load instructions. In this case, there is no coherence problem since data that may be replicated in more than one Attraction Buffer is only read. cluster of the set. These kind of remote accesses are important in epicdec, pgpdec, pgpenc, and rasta, as can be seen when comparing the third and fourth columns in Fig. 6. In these cases, the memory alias analysis applied by the compiler cannot disambiguate memory references in some important loops and memory dependent sets are relatively big. A more aggressive alias analysis may reduce this kind of remote access. However, we have used a more selective unrolling heuristic than OUF unrolling, as explained in Section 5.2. In this case, Attraction Buffers are important to increase local accesses by hardware and reduce stall time. Stall time is mainly due to memory instructions that have been scheduled too close to their consumers. Remote accesses and, especially, remote hits are the biggest source of stall time, as can be seen in Fig. 7. For each benchmark (except for g721dec and g721enc, where stall time is negligible), two bars are shown using selective unrolling which correspond to: 1) stall time generated without Attraction Buffers and 2) stall time generated with 16-entry 2-way set-associative Attraction Buffers. Results are normalized to the first bar. Stall time has been divided into stall time generated by remote hits, local misses, and remote misses (local hits never cause stalls). As can be observed, stall time is mainly due to remote hits that account for 72 percent of the stall time, on average, without Attraction Buffers. In addition, Attraction Buffers are an effective way to reduce stall time, which is reduced by 36 percent on average. A previous partial study [14] showed that 8-entry and 16-entry Attraction Buffers are enough to capture most of the remote accesses and are cost-effective solutions in terms of buffer size and stall time reduction. 6FLEXIBLE COMPILER-MANAGED L0 BUFFERS FOR A CLUSTERED VLIW PROCESSOR 6.1 Architecture The last distributed cache configuration we have proposed for clustered VLIW processors consists of a slow centralized L1 data cache and a small and fast L0 buffer per cluster [17]. Due to the small capacity of these buffers, flexible mechanisms can be used to map data to the buffers and manage them. In addition, the compiler is responsible for marking which instructions make use of the buffers and which do not. Hence, it is important to map critical data in the buffers without overflowing their capacity. We refer to these buffers as Flexible Compiler-Managed L0 Buffers, or L0 buffers for short, and an example is shown in Fig. 8. We consider that an entry in an L0 buffer has the size of a cache line divided by the number of clusters. The term subblock is again used to identify bytes of an L1 block that are mapped in the same entry of a given L0 buffer. The proposed buffers are flexible since data from the slow centralized L1 data cache can be mapped to the buffers in different ways. First, there is no static binding between addresses and clusters, so any piece of data can be present in any cluster. In addition, data can be mapped in the buffer in a linear manner or in an interleaved manner. With linear mapping, consecutive bytes of a cache line form one subblock that is mapped in the buffer of the cluster that requested the data. On the other hand, with interleaved mapping, an L1 block is split into Nsubblocks (Nbeing the number of clusters) and subblocks are mapped in consecutive clusters. Subblocks are formed by interleaving bytes of the cache line using the access granularity as the interleaving factor. For example, in case of a load_2_bytes instruction, subblocks will be formed by using an interleaving factor of 2 bytes. An example of both mapping schemes is shown in Fig. 9. The use of a dynamic interleaving factor is better explained with an example. Assume that a loop has been unrolled Ntimes, Nbeing the number of clusters, and has derived in the following code: for (i=0; i<MAX; i+=4) { a[i] = b[i] + C; /* load_1 accesses b[0],b[4],b[8], ... */ a[i+1] = b[i+1] + C; /* load_2 accesses b[1],b[5],b[9], ... */ a[i+2] = b[i+2] + C; /* load_3 accesses b[2],b[6],b[10], ... */ a[i+3] = b[i+3] + C; /* load_4 accesses b[3],b[7],b[11], ... */ } It seems reasonable to schedule each load instruction in a consecutive cluster and map data accordingly. If arrays aand bare 2-byte element arrays, data can be split into subblocks with a 2-byte interleaving factor so that elements b½0,b½4,b½8, etc., are mapped in the same cluster. The disadvantage of using a dynamic interleaving factor is that data must be GIBERT ET AL.: DISTRIBUTED DATA CACHE DESIGNS FOR CLUSTERED VLIW PROCESSORS 1235 Fig. 7. Stall time due to different memory access types. The first bar represents stall time when no Attraction Bufferes are used, while the second shows stall time when 16-entry 2-way set-associative Attraction Buffers are used. Values are normalized to the first bar.