Through geometry, program visualization can yield performance properties. We derive all possible synchronization sequences and durations of blocking and concurrent execution for two process programs from a visualization mapping processes, synchronization, and program execution to Cartesian graph axes, line segments, and paths, respectively. Relationships to Petri nets are drawn.

World-Wide Web proxy servers that cache documents can potentially reduce three quantities: the number of requests that reach popular servers, the volume of network traffic resulting from document requests, and the latency that an end-user experiences in retrieving a document. This paper examines the first two using the measures of cache hit rate and weighted hit rate (or fraction of client-requested bytes returned by the proxy). A client request for an uncached document may cause the removal of one or more cached documents. Variable document sizes and types allow a rich variety of policies to select a document for removal, in contrast to policies for CPU caches or demand paging, that manage homogeneous objects. We present a taxonomy of removal policies. Through trace-driven simulation, we determine the maximum possible hit rate and weighted hit rate that a cache could ever achieve, and the removal policy that maximizes hit rate and weighted hit rate. The experiments use five traces of 37 to 185 days of client URL requests. Surprisingly, the criteria used by several proxy-server removal policies (LRU, Hyper-G, and a proposal by Pitkow and Recker) are among the worst performing criteria in our simulation; instead, replacing documents based on size maximizes hit rate in each of the studied workloads.

We describe how to investigate collections of trace data representing network delivery of multimedia information with CHITRA95, a tool that allows a user to visualize, query, statistically analyze and test, transform, and model collections of trace data. CHITRA95 is applied to characterize World Wide Web (WWW) traffic from three workloads: students in a classroom of network-connected workstations, graduate students browsing the Web, undergraduates browsing educational and other materials, as well as traffic on a courseware repository server. We explore the inter-access time of files on a server (i.e., recency), the hit rate from a proxy server cache, and the distributions of file sizes and media types requested. The traffic study also yields statistics on the effectiveness of caching to improve transfer rates. In contrast to past WWW traffic studies, we analyze client as well as server traffic; we compare three workloads rather than drawing conclusions from one workload; and we analyze tcpdump logs to calculate the performance improvement in throughput that an end user sees due to caching.

Abstract Performance visualization tools of the past decade have yielded new insights into the behavior of sequential, parallel and distributed programs. However, they have three inherent limitations: (1) they only display what happened in one execution of a program (this is dangerous when analyzing concurrent applications, which are prone to non‐deterministic behavior); (2) a human uses one or more bandwidth‐limited senses with a visualization tool (this limits the scalability of a visualization tool); (3) the relationship of ‘interesting’ program events is often separated in time by other events; thus discerning time‐dependent behavior often hinges on finding the ‘right’ visualization—a possibly time‐consuming activity. CHITRA93 complements visualization systems, while alleviating these limitations, and analyzes a set (or ensemble) of traces by combining the visualization of a few traces with a statistical analysis of the entire ensemble (overcoming (1)). It reduces the ensemble to empirical models that capture the time‐dependent relationships of ‘interesting’ program events through application, programming language and computer architecture independent analysis techniques (addressing (2) and (3)). It also incorporates the following transforms, such as aggregation, that simplify the ensemble and reduce the state‐space size of the models generated; a user interface that allows certain transforms to be selected by editing the visualization with a mouse; homogeneity tests that allow partitioning of an ensemble; an efficient semi‐Markov model generation algorithm whose computation time is linear in the sum of the lengths of the traces comprising the ensemble; and a CHAID‐based model that can fathom non‐Markovian relationships among transitions in the traces. The use of CHITRA93 is demonstrated by partitioning ten parallel database traces with nearly 8,000 states into two homogeneous subsets, each modeled by an irreducible, periodic and hierarchical stochastic process with as few as four states.

Can a discrete event simulation model be executed in parallel? Fujimoto's article presents the challenges from the perspective of a parallel discrete event simulation (PDES) researcher. A somewhat different answer arises by reexamining the question from the viewpoint of simulation modelers that study complex systems. A simulationist in any simulation study faces the central concern of how to define a model. Often the choice of what to include versus exclude from a model is a significant intellectual accomplishment. Indeed, success in selecting a model maximizes the model's ability to meet the objectives of a simulation study, but minimizes the computation required, to the point that it may obviate the need for parallel simulation! The model is cast into a specification, and the specification is implemented as a program. The issues of verification—whether we are building the model right—and validation—whether we are building the right model—become paramount. An added complexity is designing a model that is maintainable over a lifetime of many years, during which the model may be adapted to new simulation study objectives, run on new hardware configurations or even a new computer architecture, and run on new system software releases. Therefore, conducting a successful simulation study using sequential simulation is already a taxing activity. What additional work must be done to use PDES? Fundamentally, for the PDES programmer, the chief intellectual problem is algorithm design—to devise an operational view of model execution that can be partitioned into an efficient program for the target computer architecture. The efficiency of the algorithm chosen and its match to the target architecture are overriding decisions. In selecting the parallel simulation algorithm used for execution, the PDES programmer will assess whether assumptions required by different algorithms are met by the model. This raises the question of whether a model can be modified to allow use of a more efficient PDES algorithm. In particular, the modeler may have made arbitrary design decisions which do not affect the validity of the model but do affect the ability to parallelize the model. Therefore, model definition and PDES algorithm design are not independent processes. Simulation model definition and parallel algorithm design are very different activities. Therefore success in a large PDES study implies a need for a team combining individuals with “hard-core” simulation modeling knowledge as well as individuals with PDES algorithm knowledge. Such a team could determine if an efficiency problem should be solved by model redefinition, by changing the PDES algorithm, or both. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Chitra analyzes a program execution sequence (PES) collected during execution of a program and produces a homogeneous, semi-Markov chain model fitting the PES. The PES represents the evolution of a program state vector in time. Therefore Chitra analyzes the time-dependent behavior of a program. The authors describe a set of transforms that map a PES to a simplified PES. Because the transforms are program-independent. Chitra can be used with any program. Chitra provides a visualization of PESs and transforms, to allow a user to visually guide transform selection in an effort to generate a simple yet accurate semi-Markov chain model. The resultant chain can predict performance at program parameters different than those used in the input PES, and the chain structure can diagnose performance problems.>