Chip multi-threaded (CMT) processors provide support for many simultaneous hardware threads of execution in various ways, including simultaneous multithreading (SMT) and chip multiprocessing (CMP). CMT processors are especially suited to server workloads, which generally have high levels of thread-level parallelism (TLP). In this paper, we describe the evolution of CMT chips in industry and highlight the pervasiveness of CMT designs in upcoming general-purpose processors. The CMT design space accommodates a range of designs between the extremes represented by the SMT and CMP designs and a variety of attractive design options are currently unexplored. Though there has been extensive research on utilizing multiple hardware threads to speed up single-threaded applications via speculative parallelization, there are many challenges in designing CMT processors, even when sufficient TLP is present. This paper describes some of these challenges including, hot sets, hot banks, speculative prefetching strategies, request prioritization and off-chip bandwidth reduction.

In this paper, we study the instruction cache miss behavior of four modern commercial applications (a database workload, TPC-W, SPECjAppServer2002 and SPECweb99). These applications exhibit high instruction cache miss rates for both the L1 and L2 caches, and a sizable performance improvement can be achieved by eliminating these misses. We show that it is important, not only to address sequential misses, but also misses due to branches and function calls. As a result, we propose an efficient discontinuity prefetching scheme that can be effectively combined with traditional sequential prefetching to address all forms of instruction cache misses. Additionally, with the emergence of chip multiprocessors (CMPs), instruction prefetching schemes must take into account their effect on the shared L2 cache. Specifically aggressive instruction cache prefetching can result in an increase in the number of L2 cache data misses. As a solution, we propose a scheme that does not install prefetches into the L2 cache unless they are proven to be useful. Overall, we demonstrate that the combination of our proposed schemes is successful in reducing the instruction miss rate to only 10%-16% of the original miss rate and results in a 1.08X-1.37X performance improvement for the applications studied.

Computer architects utilize cycle simulators to evaluate microprocessor chip design tradeoffs and estimate performance metrics. Traditionally, cycle simulators are either trace-driven or execution-driven. In this paper, we describe ValueSim, a software layer that is interposed between a cycle simulators and either a functional simulator or a value-enhanced trace. By writing to the ValueSim API, the cycle simulator can run in either trace-driven mode or execution-driven mode, allowing it to exploit the advantages of both approaches. The ValueSim API allows a cycle simulator to accurately model a complete range of aggressive speculative mechanisms developed by computer architects, even in the trace-driven mode. Using ValueSim, we illustrate, for three key commercial applications, the significant underestimation of off-chip bandwidth, queuing delays and cache pollution when modern speculative mechanisms are not accurately modeled, highlighting the importance of accurately modeling these mechanisms in chip multiprocessor designs.

This paper studies the impact of off-chip store misses on processor performance for modern commercial applications. The performance impact of off-chip store misses is largely determined by the extent of their overlap with other off-chip cache misses. The epoch MLP model is used to explain and quantify how these overlaps are affected by various store handling optimizations and by the memory consistency model implemented by the processor. The extent of these overlaps is then translated to off-chip CPI. Experimental results show that store handling optimizations are crucial for mitigating the substantial performance impact of stores in commercial applications. While some previously proposed optimizations, such as store prefetching, are highly effective, they are unable to fully mitigate the performance impact of off-chip store misses and they also leave a performance gap between the stronger and weaker memory consistency models. New optimizations, such as the store miss accelerator, an optimization of hardware scout and a new application of speculative lock elision, are demonstrated to virtually eliminate the impact of off-chip store misses.

Data prefetching via helper threading has been extensively investigated on simultaneous multi-threading (SMT) or virtual multi-threading (VMT) architectures. Although reportedly large cache latency can be hidden by helper threads at runtime, most techniques rely on hardware support to reduce context switch overhead between the main thread and helper thread as well as rely on static profile feedback to construct the help thread code. This paper develops a new solution by exploiting helper threaded prefetching through dynamic optimization on the latest UltraSPARC chip-multiprocessing (CMP) processor. Our experiments show that by utilizing the otherwise idle processor core, a single user-level helper thread is sufficient to improve the runtime performance of the main thread without triggering multiple thread slices. Moreover, since the multiple cores are physically decoupled in the CMP, contention introduced by helper threading is minimal. This paper also discusses several key technical challenges of building a lightweight dynamic optimization/software scouting system on the UltraSPARC/Solaris platform.

With processor speeds continuing to outpace the memory subsystem, cache missing memory operations continue to become increasingly important to application performance. In response to this continuing trend, most modern processors now support hardware (HW) prefetchers, which act to reduce the missing loads observed by an application.This paper analyzes the behavior of cache-missing loads in SPEC CPU2000 and highlights the inability of unit and single non-unit stride prefetchers to correctly prefetch for some commonly occurring streams. In response to this analysis, a novel multi-stride prefetcher, that supports streams with up to four distinct strides, is proposed. Performance analysis for SPEC CPU2000 illustrates that the proposed multi-stride prefetcher can outperform current stride prefetchers on several benchmarks; most notably on mcf, lucas and facerec, where it achieves an additional performance gain of up to 57%. Performance of the strided HW prefetchers is also contrasted with another recently proposed prefetch scheme, runahead execution (RAE), and the synergy between the schemes is investigated.

The performance of memory-bound commercial applications such as databases is limited by increasing memory latencies. In this paper, we show that exploiting memory-level parallelism (MLP) is an effective approach for improving the performance of these applications and that microarchitecture has a profound impact on achievable MLP. Using the epoch model of MLP, we reason how traditional microarchitecture features such as out-of-order issue and state-of-the-art microarchitecture techniques such as runahead execution affect MLP. Simulation results show that a moderately aggressive out-of-order issue processor improves MLP over an in-order issue processor by 12-30%, and that aggressive handling of loads, branches and serializing instructions is needed to attain the full benefits of large out-of-order instruction windows. The results also show that a processor's issue window and reorder buffer should be decoupled to exploit MLP more efficiently. In addition, we demonstrate that runahead execution is highly effective in enhancing MLP, potentially improving the MLP of the database workload by 82% and its overall performance by 60%. Finally, our limit study shows that there is considerable headroom in improving MLP and overall performance by implementing effective instruction prefetching, more accurate branch prediction and better value prediction in addition to runahead execution.

The PICO-N system automatically synthesizes embedded nonprogrammable accelerators to be used as co-processors for functions expressed as loop nests in C. The output is synthesizable VHDL that defines the accelerator at the register transfer level (RTL). The system generates a synchronous array of customized VLIW (very-long instruction word) processors, their controller local memory, and interfaces. The system also modifies the user's application software to make use of the generated accelerator. The user indicates the throughput to be achieved by specifying the number of processors and their initiation interval. In experimental comparisons, PICO-N designs are slightly more costly than hand-designed accelerators with the same performance.

Automated design tools must understand and exploit the hierarchical structure of large design spaces.We have developed a general methodology for decomposing system design spaces into smaller component design spaces, followed by component-level evaluation, filtering, recomposition and system-level evaluation.This methodology greatly reduces the time and cost of design space exploration, since the typical number of system-level evaluations is greatly reduced.This paper describes the application of our decomposition methodology in the context of PICO.PICO is a design space exploration system that automatically generates embedded designs consisting of a stylized processor, hardware accelerator and a cache hierarchy, each customized to a benchmark.First, PICO splits the specified system design space into smaller design spaces, one for each of the components, viz.processor, accelerator and data/instruction/unified caches.PICO further partitions each component design space into predicated design spaces, so that all designs in a predicated design space satisfy a specified predicate.PICO uses component-level evaluations to identify the performance-cost optimal component-level Pareto designs in each predicated design space.PICO generates all compositions of Pareto designs from compatible predicated design spaces and uses a system-level evaluation to identify the Pareto designs at the system level.For reasonable design spaces, PICO reduces the design exploration time by over four orders of magnitude compared to an exhaustive approach.

Automation is the key to the design of future embedded systems as it permits application-specific customization while keeping design costs low. A key problem faced by automatic design systems is evaluating the performance of the vast number of alternative designs in a timely manner. For this paper, we focus on an embedded system consisting of the following components: a VLIW processor, instruction cache, data cache, and second-level unified cache. A hierarchical approach of partitioning the system into its constituent components and evaluating each component individually is utilized. The performance of each processor is evaluated independent of its memory hierarchy, and each of the caches is simulated using the traces from a single reference processor. Since the changes in the processor architecture do indeed affect the address traces and thus the performance of the memory hierarchy, the overall performance is inaccurate. To overcome this error, the changes in the processor architecture are modeled as a dilation of the reference processor's address trace, where each instruction block in the trace is conceptually stretched out by the dilation coefficient. This approach provides a projected cache performance that more accurately accounts for changes in the processor architecture. In order to understand the accuracy of the dilation model, we separate the possible errors that the model introduces and quantify these errors on a set of benchmarks. The results show that the dilation model is effective for most of the design space and facilitates efficient automatic design.

Meld scheduling melds the schedules of neighboring scheduling regions to respect latencies of operations issued in one region but completing after control transfers to the other. In contrast, conventional schedulers ignore latency constraints from other regions leading to potentially avoidable stalls in an interlocked (superscalar) machine or incorrect schedules for non-interlocked (VLIW) machines. Alternatively, schedulers that conservatively require all operations to complete before the branch rakes effect produce inefficient schedules. In this paper, we present general data structures for maintaining latency constraint information at region boundaries. We present a meld scheduling algorithm that generates latency constraints at the boundaries of scheduled regions and utilizes this information during the scheduling of other regions. We present a range of design options and describe the reasons behind our particular choices. We cover certain pitfalls and discuss how to develop an algorithm that addresses these issues. We evaluate the performance of meld scheduling on a range of noninterlocked machine models on a set of SPEC 92 and Unix benchmarks. We also investigate the sensitivity of the performance improvements due to changes in issue width and instruction latencies.

Modtdo schedulwsg is an eficient tech nzque for exploiting instruction level parallelism in a uaraety of ioopsl resulting in high performance code but increased register requirements.We present a combined approach that schedules the loop operations for the highest steady state throughput and minimum register requirements.Our method determines optimal register requirements for machines with jinite resources and for general dependence graphs.We compare the performance of this and other modulo schedulers for a benchmark of 6.29 loops from the Perfect Clubl SPEC-89, and the Livermore Fortran Kernels.Measurements demonstrate the potential of r-egister=sensittve modulo schedulers, wh~ch will be useful in evaluating the performance of register-sensitive modrslo scheduling heuristics.

Set-associative caches are widely used in CPU memory hierarchies, I/O subsystems, and file systems to reduce average access times. This article proposes an efficient simulation technique for simulating a group of set-associative caches in a single pass through the address trace, where all caches have the same line size but varying associativities and varying number of sets. The article also introduces a generalization of the ordinary binomial tree and presents a representation of caches in this class using the Generalized Binomial Tree (gbt). The tree representation permits efficient search and update of the caches. Theoretically, the new algorithm, GBF_LS, based on the gbt structure, always takes fewer comparisons than the two earlier algorithms for the same class of caches: all-associativity and generalized forest simulation. Experimentally, the new algorithm shows performance gains in the range of 1.2 to 3.8 over the earlier algorithms on address traces of the SPEC benchmarks. A related algorithm for simulating multiple alternative direct-mapped caches with fixed cache size, but varying line size, is also presented.

Applications with irregular data structures such as sparse matrices or finite element meshes account for a large fraction of engineering and scientific applications. Domain decomposition techniques are commonly used to partition these applications to reduce interprocessor communication on message passing parallel systems. Our work investigates the use of domain decomposition techniques on cache-coherent parallel systems.

Module scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present a combined approach that schedules the loop operations for minimum register requirements, given a module reservation table. Our method determines optimal register requirements for machines with finite resources and for general dependence graphs. This method demonstrates the potential of lifetime-sensitive module scheduling and is useful in evaluating the performance of lifetime-sensitive module scheduling heuristics.

We develop compile-time iteration partitioning techniques for private-cache shared-memory mulriprocessors. Our techniques assign loop iterations to a set of processors so that cache coherency traffic due io interprocessor communication is minimized and load balance is maintained. In contrast to most previous research that has examined uniformly-generated dependences, we develop methods for non-uniform dependences that are generated by stride conflicts. Furthermore, we consider the effects of a long cache line size and minimize false coherency traffic. Our methods can handle conflicts between any two integer strides. We have conducted experiments on a 32-processor KSR-1 from Kendall Square Research which show 2x performance improvement using our partitioning algorithm over standard contiguous partitioning techniques.

Communication has a dominant impact on the performance of massively parallel processors (MPPs). We propose a methodology to evaluate the internode communication performance of MPPs using a controlled set of synthetic workloads. By generating a range of sparse matrices and measuring the performance of a simple parallel algorithm that repeatedly multiplies a sparse matrix by a dense vector, we can determine the relative performance of different communication workloads. Specifiable communication parameters include the number of nodes, the average amount of communication per node, the degree of sharing among the nodes, and the computation-communication ratio. We describe a general procedure for constructing sparse matrices that have these desired communication and computation parameters, and apply a range of these synthetic workloads to evaluate the hierarchical ring interconnection and cache-only memory architecture (COMA) of the Kendall Square Research KSRI MPP. This analysis discusses the impact of the KSRI architecture on communication performance, highlighting the utility and impact of the automatic update feature. It also investigates the impact of system contention on the performance, particularly how it causes potential updates to be ignored.

Presents a model of coarse grain dataflow execution. The authors present one top down and two bottom up methods for generation of multithreaded code, and evaluate their effectiveness. The bottom up techniques start from a fine-grain dataflow graph and coalesce this into coarse-grain clusters. The top down technique generates clusters directly from the intermediate data dependence graph used for compiler optimizations. The authors discuss the relevant phases in the compilation process. They compare the effectiveness of the strategies by measuring the total number of clusters executed, the total number of instructions executed, cluster size, and number of matches per cluster. It turns out that the top down method generates more efficient code, and larger clusters. However the number of matches per cluster is larger for the top down method, which could incur higher cluster synchronization costs.>

Cache miss characterization models such as the three Cs model are useful in developing schemes to reduce cache misses and their penalty. In this paper we propose the OPT model that uses cache simulation under optimal (OPT) replacement to obtain a finer and more accurate characterization of misses than the three Cs model. However, current methods for optimal cache simulation are slow and difficult to use. We present three new techniques for optimal cache simulation. First, we propose a limited lookahead strategy with error fixing, which allows one pass simulation of multiple optimal caches. Second, we propose a scheme to group entries in the OPT stack, which allows efficient tree based fully-associative cache simulation under OPT. Third, we propose a scheme for exploiting partial inclusion in set-associative cache simulation under OPT. Simulators based on these algorithms were used to obtain cache miss characterizations using the OPT model for nine SPEC benchmarks. The results indicate that miss ratios under OPT are substantially lower than those under LRU replacement, by up to 70% in fully-associative caches, and up to 32% in two-way set-associative caches.

A performance bounding methodology that explains the performance of loop-dominated scientific applications on particular systems is presented. The throughput of key hardware units that are common bottlenecks in concurrent machines is modeled. A workload characterization is proposed, and upper bounds on the performance of specific machine-workload pairs are derived. Comparing delivered performance with bounds focuses attention on areas for improvement and indicates how much improvement might be attainable. A detailed analysis and performance improvement effort for the IBM RS/6000 produced an average lower bound of 1.27 clocks per floating-point operation (CPF), whereas machine peak performance is 0.5 CPF and the V2.01 Fortran compiler attains only 2.43 CPF. Code improvements in this study have achieved 1.36 CPF, increasing the harmonic mean steady-state inner loop performance to 97.6% of the MFLOPS bound. Subsequently, the V2.02 compiler achieved 1.75 CPF, and 1.60 with carefully chosen preprocessing.>

The notion of optimality of a parallel algorithm is closely tied to the characteristics of the parallel machine. A parallel implementation of radiosity solution is chosen for studying relationship between algorithms and parallel architectures. The radiosity method determines a view independent solution to scene illumination. This approach is computationally intensive and can benefit from parallelism. An algorithm for solving the radiosity equation was previously developed for Intel iPSC/2, a tightly coupled message passing multiprocessor. This algorithm when directly ported to IBM RS6000 LAN performed worse than a serial algorithm due to the high message latency of a LAN. Network parameters on the LAN multicomputer were measured. A new algorithm that minimizes the number of messages by increasing task granularity is proposed. The results obtained using this algorithm indicated expected performance improvements.>

To enable concurrent instruction execution, scientific computers generally rely on pipelining, which combines with faster system clocks to achieve greater throughput. Each concurrently executing instruction requires buffer space, usually implemented as a register, to receive its result. This paper focuses on the issue of how many registers are required to achieve optimal performance in pipelined scientific computers. Four machine models are considered: single, double, and triple issue scalar machines, and vector machines with various register lengths. A model is presented that accurately relates the register requirements for optimum performance cyclically scheduled loops with tree-dependence graphs to the degree of function unit pipelining, the instruction issue bandwidth, and code properties. A method for finding upper and lower bounds on the minimum register requirements is also presented.The result of this work is a theory for assessing register requirements that can be used to reveal fundamental differences among machines within a space of architectural and implementation design choices. Some experimental data is also provided to support the theory.

article Vector register design for polycyclic vector scheduling Share on Authors: William Mangione-Smith Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Santosh G. Abraham Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Edward S. Davidson Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile Authors Info & Claims ACM SIGOPS Operating Systems ReviewVolume 25Issue Special IssueApr. 1991 pp 154–163https://doi.org/10.1145/106974.328664Published:01 April 1991 8citation339DownloadsMetricsTotal Citations8Total Downloads339Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Iterative parallel algorithms account for many important supercomputer applications.on such algorithms, the communication of partial results stresses the memory system performance.In an earlier paper, we developed loop partitioning strategies that minimize the number of data points exchanged between processors.In this paper, we develop data placement schemes that minimize communication time.Under a given loop $bal da~a into four classes for artition our compile-time algorlthm partitions each processor.Eac rocessor may move its ezclu- !V sive read-write set (ER ), into the highest level of its hierarchy.The processor must maintain consistency on the shared read-excluszve write set (SREW) and shared read-no wlit e set (SRN W).A processor does not access the no read-wrate set (NRW).Assignment of SRNW sets to the local memory of each processor and caching of the ERW sets leads to a factor of five improvement over the default data assignment in the BBN TC2000.Features in current generation pipelined processors with multiple functional units permit the overlap of memory accesses with computation.Our experiments on the BBN TC2000 show that the degree of overlap is limited by architectural parameters, such as the number of CPU registers.We show that software redundancy in data assignments achieves 1? rester overla thus reducing communication over-: ead even furt er.

Adaptive data partitioning (ADP) which reduces the execution time of parallel programs by reducing interprocessor communication for iterative parallel loops is discussed. It is shown that ADP can be integrated into a communication-reducing back end for existing parallelizing compilers or as part of a machine-specific partitioner for parallel programs. A multiprocessor model to analyze program execution factors that lead to interprocessor communication and a model for the iterative parallel loop to quantify communication patterns within a program are defined. A vector notation is chosen to quantify communication across a global data set. Communication parameters are computed by examining the indexes of array accesses and are adjusted to reflect the underlying system architecture by compensating for cache line sizes. These values are used to generate rectangular and hexagonal partitions that reduce interprocessor communication.>

This paper uses bottom-up, static program partitioning to minimize the execution time of parallel programs by reducing interprocessor communication. Program partitioning is applied to a parallel programming construct known as a sequentially iterated parallel loop. This paper develops and evaluates compiler techniques to automatically generate data partitions for sequentially iterated parallel loops that minimize interprocessor communication. These techniques could be included as a communication-reducing back end for existing parallelizing compilers.