2507292
Speculative Updates of Local and Global Branch History: A Quantitative Analysis
In today’s wide-issue processors, even small branch-misprediction rates introduce substantial performance penalties. Worse yet, inadequate branch prediction creates a bottleneck at the fetch stage, restricting other opportunities for improving performance. The choice of how to predict conditional-branch outcomes is the primary lever on prediction accuracy. But the choice of whento update the predictor with branch outcomes is a second powerful lever, and the subject of this paper. In history-based predictors like g har , many mispredictions result from commit-time update of the history: typical pipelined processors predict branches in the fetch stage, but update the predictor in the commit stage, making the predictor’s state temporarily outof-date. As pipelines grow longer—in particular, when branches can spend many cycles in the instruction window waiting to issue—this problem becomes worse. Prior work on this subject has discussed the need for speculative update in a global-history-based predictor; this paper evaluates speculative history update for both global-history and local-history predictors of various configurations, using cycle-level simulation to show the effects of prediction accuracy and update time on overall performance. The results show the importance of speculative history update, but also that speculative update requires suitable fixup mechanisms for repairing state that has been corrupted by mispredictions. A number of such mechanisms are discussed.
7136114
Multipath execution: opportunities and limits
Even sophisticated branch-prediction techniques necessarily suffer some mispredictions, and even relatively small mispredict rates hurt performance substantially in current-generation processors. In this paper, we investigate schemes for improving performance in the face of imperfect branch predictors by having the processor simultaneously execute code from both the taken and not-taken outcomes of a branch. This paper presents data regarding the limits of multipath execution, considers fetch-bandwidth needs for multipath execution, and discusses various dynamic confidence-prediction schemes that gauge the likelihood of branch mispredictions. Our evaluations consider executing along several (Z-8) paths at once. Using 4 paths and a relatively simple confidence predictor, multipath execution garners speedups of up to 30% compared to the single-path case, with an average speedup of 14.4% for the SPECint suite. While associated increases in instruction-fetch-bandwidth requirements are not too surprising, a less expected result is the significance of having a separate return-address stack for each forked path. Overall, our results indicate that multipath execution offers significant improvements over single-path performance, and could be especially useful when combined with multithreading so that hardware costs can be amortized over both approaches.
6229316
Thread scheduling for out-of-core applications with memory server on multicomputers
Out-of-core applications perform poorly in paged virtual memory (VM) systems because demand paging involves slow disk I/O accesses. Much research has been done on reducing the I/O overhead in such applications by either reducing the number of I/Os or lowering the cost of each I/O operation. In this paper, we investigate a method that combines finegrained threading with a memory server model to improve the performance of out-of-core applications on multicomputers. The memory server model decreases the average cost of I/O operations by paging to remote memory, while the fine-grained thread scheduling reduces the number of I/O accesses by improving the data locality of applications. We have evaluated this method on an Intel Paragon with 7 applications. Our results show that the memory server system performs better than the VM disk paging by a factor of 5 for sequential applications and a factor of 1.5 to 2.2 for parallel applications. The fine-grained threading alone improves the VM disk paging performance by a factor of 10 and 1.2 to 3 respectively for sequential and parallel applications. Overall, the combination of these two techniques outperforms the VM disk paging by more than a factor of 12 for sequential applications and a factor of 3 to 6 for parallel applications.
1788137
A taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions
The need for accurate conditional-branch prediction is well known: mispredictions waste large numbers of cycles, inhibit out-of-order execution, and waste power on mis-speculated computation. Prior work on branch-predictor organization has focused mainly on how to reduce conflicts in the branch-predictor structures, while relatively little work has explored other causes of mispredictions. Some prior work has identified other categories of mispredictions, but this paper organizes these categories into a broad taxonomy of misprediction types. Using the taxonomy, this paper goes on to show that other categories- especially wrong history mispredictions-are often more important than conflicts. This is true even if just a very simple conflict-reduction technique is used. Based on these observations, this paper proposes alloying local and global history together in a two-level branch predictor structure. This simple technique, a generalization of the bi-mode predictor, attacks wrong-history mispredictions by making both global and local history simultaneously available. Unlike bi-mode prediction, however, alloying gives robust performance for branch-predictor hardware budgets ranging from very large to very small. Finally, this paper shows that individual branch references can also suffer wrong-history mispredictions as they alternate between using global and local history, a phenomenon that favors dynamic rather than static selection in hybrid predictors.
61690467
The performance impact of incomplete bypassing in processor pipelines
Pipelined processors employ hardware bypassing to eliminate certain pipeline hazards. By passing is logically simple but can be costly, especially in wide issue and deeply pipelined machines. In this paper bypassing is studied in detail, with an emphasis on designs in which the bypassing network is not complete. Cycle-level simulations of a model of integer and floating-point pipelines running some of the SPEC92 benchmarks show that at least half of the instructions executed used a bypassed register result from a previous instruction. Missing bypasses induce interlock stalls. The paper reports measurements of the performance impact of a number of pipeline configurations with incomplete bypassing networks. This impact ranges from a slowdown of just a few percent for a configuration with one late bypass missing to a slowdown of almost a factor of two for the integer pipe with no bypassing at all. Two types of code alterations reduce the new interlock stalls. A simple code transformation, the interchange of operands in instructions that perform commutative operations, cuts the performance loss from interlock stalls in certain configurations between about 20 and 50 percent. The second transformation is to reschedule code within basic blocks to avoid any missing bypasses. In five individual experiments with a small number of configurations and two benchmarks, this rescheduling saved 25 to 50 percent of the interlock stalls. In certain configurations both transformations can be applied.
10720036
Evaluating multi-port frame buffer designs for a mesh-connected multicomputer
Multicomputers can be effectively used for interactive graphics rendering only if there are mechanisms available to rapidly composite and transfer images to an external display device. One method for achieving the necessary bandwidth for this operation is to provide multiple high-bandwidth ports into a frame buffer. In this paper, we evaluate the design space of a multiport frame buffer design for the Intel Paragon mesh routing network. We use an instrumented rendering system to capture the graphics operations needed for rendering a number of three-dimensional scenes; we then use those workloads as input to test programs running on the Paragon to estimate the performance of our hardware. Our experiments consider three major design questions: how many network ports the frame buffer needs, whether Z-buffering should be done in hardware on the frame buffer or in software on the computing nodes, and whether the design alternatives are scalable.
19812651
A Lattice of Abstract Graphs
This paper concerns the abstract interpretation of Term Graph Rewriting systems. We introduce a new lattice of abstract graphs; this improves over previous work in that the ordering is defined directly on the graph structure rather than via unravelling into trees. We use the lattice in sketching the correctness of Nocker's abstract reduction algorithm; an efficient strictness analysis used in the Concurrent Clean system.
16641025
Quantified Interference for a While Language
We show how information theory can be used to give a quantitative definition of interference between variables in imperative programming languages. In this paper we focus on a particular case of this definition of interference: leakage of information from private variables to public ones in While language programs. The major result of the paper is a quantitative analysis for this language that employs a use-definition graph to calculate bounds on the leakage into each variable.
5895699
Addressing reality: an architectural response to real-world demands on the evolving Internet
A system as complex as the Internet can only be designed effectively if it is based on a core set of design principles, or tenets, that identify points in the architecture where there must be common understanding and agreement. The tenets of the original Internet architecture [6] arose as a response to the technical, governmental, and societal environment of internetworking's earliest days, but have remained central to the Internet as it has evolved. In light of the increasing integration of the Internet into the social, economic, and political aspects of our lives, it is worth revisiting the underlying tenets of what is becoming a central element of the world's infrastructure.This paper examines three key tenets that we believe should guide the evolution of the Internet in its next generation and beyond. They are: design for change, controlled transparency, and the centrality of the tussle space. [8] Our purpose is not to present these ideas as new, but rather to propose that they should be elevated to central tenets of the evolving architecture of the Internet, and explore the ramifications of doing so. The paper first examines the tenets somewhat abstractly, and then in more detail by studying their relation to several design choices needed for a complete architecture. We conclude with a discussion of the relationship between the network architecture and the applications it serves.
36796993
From Implicit Specifications to Explicit Designs in Reactive System Development
In this paper we describe how the RSDS method can be used as a bridge between implicit Z-style specifications of reactive systems, and explicit B AMN designs of these systems. We define the translation from RSDS to B and verify its correctness. We also define controller decomposition techniques, and a translation to SMV.
9494191
Visualization of height field data with physical models and texture photomapping
The paper discusses a unique way to visualize height field data-the use of solid fabricated parts with a photomapped texture to display scalar information. In this process, the data in a height field are turned into a 3D solid representation through solid freeform fabrication techniques, in this case laminated object manufacturing. Next, that object is used as a 3D "photographic plate" to allow a texture image representing scalar data to be permanently mapped onto it. The paper discusses this process and how it can be used in different visualization situations.