Recovering from OS crashes has traditionally been done using reboot or checkpoint-restart mechanisms. Such techniques either fail to preserve the state before the crash happens or require modifications to applications. To eliminate these problems, we present a novel OS-hyper visor infrastructure for automated OS crash diagnosis and recovery in virtual servers. Our approach uses a small hidden OS-repair-image that is dynamically created from the healthy running OS instance. Upon an OS crash, the hyper visor automatically loads this repair-image to perform diagnosis and repair. The offending process is then quarantined, and the fixed OS automatically resumes running without a reboot. Our experimental evaluations demonstrated that it takes less than 3 seconds to recover from an OS crash. This approach can significantly reduce the downtime and maintenance costs in data centers. This is the first design and implementation of an OS-hyper visor combo capable of automatically resurrecting a crashed commercial server-OS.

Trace visualization is a way to understand the behavior of an application on computer systems. In this paper we describe the design and implementation of a Gantt Chart visualization tool for visualizing multi-dimensional trace files, particularly traces from Message Passing Interface (MPI) programs and Apache servers. An MPI tracing library is developed for MPI programs, and an Apache server plug-in is developed to generate Web traces. Since the amount of trace data may be large, utilities are provided to convert and merge multiple event trace files into one scalable, self-defining interval file for visualization. The interval format facilitates the development of multiple time-space diagrams for visualization tools. For MPI traces, each record also includes an instruction address for source code association, which provides a way to display the source code and pin-point the line that generates the event.

In this paper we describe a trace analysis framework, from trace generation to visualization. It includes a unified tracing facility on IBMâ SPä systems, a self-defining interval file format, an API for framework extensions, utilities for merging and statistics generation, and a visualization tool with preview and multiple time-space diagrams. The trace environment is extremely scalable, and combines MPI events with system activities in the same set of trace files, one for each SMP node. Since the amount of trace data may be very large, utilities are developed to convert and merge individual trace files into a self-defining interval trace file with multiple frame directories. The interval format allows the development of multiple time-space diagrams, such as thread-activity view, processor-activity view, etc., from the same interval file. A visualization tool, Jumpshot, is modified to visualize these views. A statistics utility is developed using the API, along with its graphics viewer.

A fundamental trend for servers in network-centric computing environments is to evolve from traditional database and transaction servers to information distribution and handling systems. In addition to documents written in the HyperText Markup Language (HTML), data stored in other forms can be retrieved through the Common Gateway Interface (CGI). A significant performance bottleneck is the initialization and setup phase for a CGI process to gain access to a backend server. In this paper, we describe the design and implementation of distributed Web server for CGI processes to acquire services efficiently. A Connection Manager Daemon (CMD) is developed to provide a number of cliettes, which are connected to backend servers to eliminate initialization costs for incoming requests. A Cache Manager is implemented to speedup response time in case of repeated requests. We also trace and monitor the Connection Manager Daemon as well as its clients using extended UTE (Unified Trace Environment) tools, and present its performance analysis and visualization. The platforms where we conduct this study include a single-node workstation, a cluster of workstations, and an IBM Scalable Parallel (SP) system.

In essence, the World Wide Web is a worldwide string of computer databases using a common information retrieval architecture. With the increasing popularity of the World Wide Web, more and more functions have been added to retrieve not only documents written in HTML (Hypertext Markup Language), but also those in other forms through the Common Gateway Interface (CGI), by constructing HTML documents dynamically. Dynamic construction of HTML documents for handling information such as digital libraries is slow and requires much more computer power. A significant performance bottleneck is the initialization and setup phase for a CGI process to gain access to the system containing the data. In this paper we describe the design and implementation of a Connection Manager Interface on IBM SP systems. The Connection Manager provides cliette processes to serve CGI requests and eliminates such bottlenecks. An IBM SP system is used for this emerging area to show that our design and implementation is flexible enough to take advantage of the High-Performance Switch in an IBM SP system. We trace and monitor this scalable Web services using UTE (Unified Trace Environment) tools, and present its performance analysis and visualization.

In this paper we discuss an implementation of the message passing interface standard (MPI) for the IBM Scalable Power PARALLEL 1 and 2 (SP1, SP2). Key to a reliable and efficient implementation of a message passing library on these machines is the careful design of a UNIX-Socket like layer in the user space with controlled access to the communication adapters and with adequate recovery and flow control. The performance of this implementation is at the same level as the IBM-proprietary message passing library (MPL). We also show that in the IBM SP1 and SP2 we achieve integrated tracing ability, where both system events, such as context switches and page fault etc., and MPI related activities are traced, with minimal overhead to the application program, thus presenting application programmers the trace of all the events that ultimately affect efficiency of a parallel program.

Stack simulation is a powerful cache analysis approach to generate the number of misses and write backs for various cache configurations in a single run. Unfortunately, none of the previous work on stack simulation has efficient stack algorithm for virtual address caches with real tags (VIR-type caches). In this paper, we devise an efficient stack simulation algorithm for analyzing VIR-type caches. Using markers with a valid range for synonym lines, our algorithm is able to keep track of stack distances for different cache configurations. In addition to cache miss ratios and write back ratios, our approach generates pseudonym frequency for all cache configurations under investigation.>

We present an integrated approach to deal with timestamp consistency, and trace based performance analysis techniques for distributed parallel applications. Our trace generation facility captures message passing and system events such as process dispatch with minimal trace overhead. Trace driven analysis tools are developed for post execution analysis, reporting information such as the time stolen by other processes in each node, and the observed message passing time and local wait time for each message. We then present our techniques to reduce total elapsed times based on observed message passing times and local wait times.

We propose efficient stack simulation algorithms for shared memory multiprocessor (MP) caches. A stack simulation algorithm for write-updated MP caches is first presented. It produces the number of write-updates as well as misses for all cache configurations in a single run. We then devise a new stack simulation algorithm for writeinvalidate MP caches. Our algorithm takes into account cross-invalidation among processors, and generates the number of invalidations as well as misses for all cache configurations in a single run. A cache simulator based on our algorithms for MP caches is developed and the results on sample traces are reported. Our results show that effi cient stack simulation is a powerful technique for multi processor cache analysis.

Parallel accesses to the table lookaside buffer (TLB) and cache array are crucial for high-performance computer systems, and the choice of cache types is one of the most important factors affecting cache performance. The authors classify caches according to both index and tag. Since both index and tag could be either virtual (V) or real (R), their classification results in four combinations or cache types. The real address caches with virtual tags for high-performance computer systems in this study are prediction-based, since index bins are generated from a small array and predictions could be false. As a result, they also discuss and evaluate real address MRU caches with real tags, and propose virtually indexed MRU caches with real tags. Each of the four cache types and MRU caches are discussed and evaluated using trace-driven simulation. The results show that a virtually indexed MRU cache with real tags is a good choice for high-performance computer systems.>

The architecture, design, and performance of a hybrid number system processor are described. The processor performs multiplication, division, square root, and square in the logarithmic number system (LNS) domain. However, the input, output, addition, and subtraction are all executed in the 32-b IEEE standard floating-point number system. With the LNS multiplier and pipelined architecture, the processor is able to perform the geometric and complex arithmetic very effectively. The processor is also shown to compare well to an existing 32-b floating-point DSP (digital signal processor) chip. For the same level of CMOS technology, the performance ratios between the hybrid number system and the floating-point processor are shown to be 6.4:1 and 8:1 for division and square root, respectively; for the complex FFT (fast Fourier transform) algorithm, the ratio is around 2:1.>

A potential system software bottleneck is demonstrated in designing an efficient process scheduling method for multiprocessor systems with shared-memory communication mechanism. The process scheduling overhead is considered. The main contribution of this work is to find the design tradeoffs between monitor bottleneck due to scheduling overhead and low process utilization due to load imbalancing. Choosing an optimum number of scheduling monitors is the key to resolve the bottlenecks. Because of the excessive number of memory requests generated by the dynamic monitor selection method, the use of the fixed monitor selection method is recommended. An analytic estimation provides a lower bound in determining the optimum number of monitors. Hill-climbing simulation is then used to find the optimum number of monitors.>

A novel rule-based circuit representation is proposed to describe the connectivities of CMOS circuits at the transistor level. The unique feature of the rule-based representation is its ability to automate CMOS circuit design and verification. A precise symbolic description of the functionality of a transistor-level circuit can be derived based on a set of production rules in linear time. Automated synthesis and verification of CMOS logic circuits are demonstrated.