To compete performance-wise, modern VLIW processors must have fast clock rates and high instruction-level parallelism (ILP). Partitioning resources (functional units and registers) into clusters allows the processor to be clocked faster, but operand transfers across clusters can easily become a bottleneck. Increasing the number of functional units increases the potential ILP, but only helps if the functional units can be kept busy.To support these features, optimizations such as loop unrolling must be applied to expose ILP, and instructions must be explicitly assigned to clusters to minimize cross-cluster transfers. In an architecture with homogeneous clusters, the number of functional units of a given type is typically a multiple of the number of clusters. Thus, it is common to unroll a loop so that the number of copies of the loop body is a multiple of the number of clusters. The result is that there is a natural mapping of instructions to clusters, which is often the best mapping. While this mapping can be obvious by inspection, we have found that existing cluster assignment algorithms often miss this natural split. The consequence is an excessive number of inter-cluster transfers, which slows down the loop.Because we were unable to find an existing cluster-assignment algorithm that performed well for unrolled loops, we developed our own. Our Affinity-Based Clustering (ABC) algorithm has been implemented in a production compiler for the Texas Instruments TMS320C6000, a two-cluster VLIW architecture. It is tailored for exploiting the patterns that result from either manual or compiler-based unrolling. As demonstrated experimentally, it performs well, even when post-unrolling optimizations partially obscure the natural split.

In large-scale multiprocessors, whether loosely or tightly coupled, some memory is cheaper to access than other memory. Because direct management of memory on these machines is quite burdensome to the programmer, much research effort has been directed toward providing a shared virtual memory (SVM) interface. Clearly, the success of this endeavor depends heavily on the efficiency of page management strategies. To date, this has been primarily the responsibility of the operating system, and secondarily that of the hardware. Unfortunately, delaying page management decisions entirely until run time can lead to an unacceptable loss of efficiency, due to poor data layout and memory reference patterns that are fixed by the end of compile time. For this reason, programmer assistance has been occasionally solicited. However, this disrupts the SVM abstraction. Moreover, many of these problems may be addressable at the compiler level instead. This is especially promising for array-based languages where compiler-based, analytical technology is most mature. Surprisingly, this possibility is largely unexplored. In this paper, we discuss the issue of compiler involvement in areas ranging from loop transformations and scheduling issues, to data layout strategies, page placement decisions, access pattern analysis, and use of run time system directives.

To reduce conflict misses, this technique, the data layout in a cache is adjusted by copying array files into temporary arrays that exhibit better cache behavior. This approach incurs a cost proportional to the amount of data being copied. To date, there has been no discussion regarding either this tradeoff or the problem of determining what and when to copy. The authors present a compile-time technique for making this determination and present a selective copying strategy based on this methodology. Preliminary experimental results demonstrate that, because of the sensitivity of cache conflicts to small changes in problem size and base addresses, selective copying can lead to better overall performance than either no copying, complete copying, or copying based on manually applied heuristics.

Alleviating memory access delays is crucial to harnessing the potential of hierarchical-memory, highperformance systems, especially vector and paral!el systems.In typica!numerics!applications, a significant portion of global memory data -lrafic arises from accesses to blocks of array elements or regions.Memory access delays due to such trafic can be reduced by using compile-time information to detect when iocal data can be reused, thereby eliminating redundant global memory accesses.In this paper, we present a compile-time algorithm that applies combined flow and dependence analysis to programs with vector and paraL lel constructs to detect such redundancies across loops nests, and in the presence of conditionals.We also show how this information can be used to eliminate redundancies.

Memory hierarchies are used by multiprocessor systems to reduce large memory access times. It is necessary to automatically manage such a hierarchy, to obtain effective memory utilization. In this paper, we discuss the various issues involved in obtaining an optimal memory management strategy for a memory hierarchy. We present an algorithm for finding the earliest point in a program that a block of data can be prefetched. This determination is based on the control and data dependencies in the program. Such a method is an integral part of more general memory management algorithms. We demonstrate our method's potential by using static analysis to estimate the performance improvement afforded by our prefetching strategy and to analyze the reference patterns in a set of Fortran benchmarks. We also study the effectiveness of prefetching in a realistic shared-memory system using an RTL-level simulator and real codes. This differs from previous studies by considering prefetching benefits in the presence of network contention.