14927180
Improving prediction for procedure returns with return-address-stack repair mechanisms
This paper evaluates several mechanisms for repairing the return-address stack after branch mispredictions. The return-address stack is a small but important structure for achieving better control-flow prediction accuracy and therefore better performance. But wrong-path execution after mispredictions frequently corrupts the return-address stack, making repair mechanisms necessary. If the processor implements multipath execution-simultaneously executing both sides of a branch-the contention among different paths makes the problem more severe. For conventional, single-path processors, this paper proposes saving both the top-of-stack pointer and the top-of-stack contents for later restoration in case of a misprediction. This simple technique achieves nearly 100% hit rates and improves performance by up to 8.7% compared to a stack with no repair mechanism. For multipath processors, providing each path with its own return-address stack completely eliminates contention, improving performance by over 25%.
5170042
Building and Using A Scalable Display Wall System
Princeton's scalable display wall project explores building and using a large-format display with commodity components. The prototype system has been operational since March 1998. Our goal is to construct a collaborative space that fully exploits a large-format display system with immersive sound and natural user interfaces. Our prototype system is built with low-cost commodity components: a cluster of PCs, PC graphics accelerators, consumer video and sound equipment, and portable presentation projectors. This approach has the advantages of low cost and of tracking technology well, as high-volume commodity components typically have better price-performance ratios and improve at faster rates than special-purpose hardware. We report our early experiences in building and using the display wall system. In particular, we describe our approach to research challenges in several specific research areas, including seamless tiling, parallel rendering, parallel data visualization, parallel MPEG decoding, layered multiresolution video input, multichannel immersive sound, user interfaces, application tools, and content creation.
8350048
Monitoring shared virtual memory performance on a Myrinet-based PC cluster
Network-connected clusters of PCs or workstations are becoming a widespread parallel computing platform. Performance methodologies that use either simulation or high-level software instrumentation cannot adequately measure the detailed behavior of such systems. The availability of new network technologies based on programmable network interfaces opens a new avenue of research in analyzing and improving the performance of software shared memory protocols. We have developed monitoring firmware embedded in the programmable network interfaces of a Myrinet-based PC cluster. Timestamps on network packets facilitate the collection of low-level statistics on, e.g., network latencies, interrupt handler times and inter-node synchronization. This paper describes our use of the low-level software performance monitor to measure and understand the performance of a Shared Virtual Memory (SVM) system implemented on a Myrinetbased cluster, running the SPLASH-2 benchmarks. We measured time spent in various communication stages during the main protocol operations: remote page fetch, remote lock synchronization, and barriers. These data show that remote request contention in the network interface and hosts can serialize their handling and artificially increase the page miss time. This increase then dilates the critical section within which it occurs, increasing lock contention and causing lock serialization. Furthermore, lock serialization is reflected in the waiting time at barriers. These results of our study sharpen and deepen similar but higher-level speculations in previous simulation-based SVM performance research. Moreover, the insights about different layers, including communication architecture, SVM protocol, and applications, on real systems provide guidelines for better designs in those layers.
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.
18220788
An adaptive globally-synchronizing clock algorithm and its implementation on a Myrinet-based PC cluster
Fast commodity network-connected PC or workstation clusters are becoming more and more popular. This popularity can be attributed to their ability to provide high-performance parallel computing on a relatively inexpensive platform. An accurate global clock is invaluable for these systems, both for measuring network perfor? mance and coordinating distributed applications. ‘Qpically, however, these systems do not include dedicated clock synchronization support. Previous clock synchronization methods are not fully suitable to them, either due to their non-commodity hardware requirements or due to insufficient synchronized clock accuracy. In this paper we present and evaluate an adaptive clock synchronization algorithm. We have implemented and tested the algorithm on a Myrinet-based PC cluster. The algorithm has several important features. First, it does not require any extra hardware support. Second, we show that this algorithm places very low intrusion on the system and has a microsecond-level accuracy. Finally, our results indicate that adding the ability to adaptively adjust the clock’s re-synchronization period causes almost no extra overhead while achieving a much better global clock accuracy.
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.
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.
29540594
Evaluating Communication Protocols for WebComputing
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.
15573543
Invariant-Based Synthesis of Fault-Tolerant Systems
Statecharts are a very widely used formalism for reactive system development, however there are problems in using them as a fully formal specification notation because of the conflicting variants of statechart semantics which exist. In this paper a modular subset of statechart notation is defined which has a simple semantics, and permits compositional development and verification. Techniques for decomposing specifications in this notation, design strategies for incorporating fault tolerance, and translation to the B formal language, are also described, and illustrated with extracts from a case study of a fault tolerant system.
12745557
Safety of Strictness Analysis via Term Graph Rewriting
A safe abstraction is presented for a restricted form of term graph rewriting. This abstraction can be seen as a formalisation of the rewrite system employed by the strictness analyser in the Concurrent Clean compiler. Programs written in a core functional language are interpreted as graph rewriting systems using a form of equational term graph rewriting due to Ariola and Arvind. Abstract graphs are defined by extending the signature of ordinary graphs and it is shown how to extend a rewriting system on ordinary graphs to one on abstract graphs. An abstraction relation between abstract graphs is used to define a notion of safety with respect to a variant of Ariola and Arvind’s direct approximation semantics, and this notion of safety is shown to be adequate for strictness analysis. Abstract reduction is defined as the union of the extended rewrite system with additional ‘heuristic’ reductions and shown to be safe.