Browsing by Author "Vazirani, Devendra"

Now showing 1 - 2 of 2
  • CHITRA94: A Tool to Dynamically Charaterize Ensembles of Traces for Input Data Modeling and Output Analsis
    Abrams, Marc; Batongbacal, Alan; Ribler, Randy; Vazirani, Devendra (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-06-01)
    CHITRA94 is the third generation of a comprehensive system to visualize, transform, statistically analyze, and model ensembles of trace data and validate the resultant models. The tool is useful for deriving input data models from trace data as well as for analysis of trace data output by a simulation. The tool uses an stochastic (possibly no-Markovian) process as its fundamental modeling component. The tool is unique in several respects. First, it focuses on the dynamic characterization of systems. Consequently it includes tests for homogeneity of ensembles, stationarity of individual traces, and the ability to partition ensembles into transient and stationary pieces. Second, CHITRA94 is a scalable performance tool: its methods are designed to work with an arbitrary number of traces in an ensemble so that a user can examine the variability of system behaviors across different traces (representing different observation periods, different system configurations, etc.). To analyze multiple traces, the user can either (1) map the traces to a model that characterizes the dynamic behavior or (2) use a novel visualization, the mass evolution graph, that shows the probability mass distribution evolution of one or more traces. A mass evolution graph is easily constructed from trace data, and the derivative of the paths it contains yield an estimate of probability mass as a function of time. Third, it analyzes categorical, not just numerical, time series data. Categorical data arises naturally in many computer and communication system modeling problems. Fourth, it includes a library of transforms that reduce the state space of the stochastic process generated. Fifth, CHITRA94 is implemented as a user extensible collection of small programs, organized as a library, which allows the user to write new library modules that use existing modules to automate analysis procedures. Instead, CHITRA94 may be invoked from command line, under a GUI, or integrated with another tool (e.g., a simulation model development or CASE tool). The use of CHITRA94 is illustrated on a variety of trace data, and the extensibility is illustrated on the problem of partitioning an ensemble of 60 traces of compressed entertainment video into mutually exclusive, exhaustive, and homogeneous subsets from which a hierarchical workload model is derived.
  • Queue Layouts and Staircase Covers of Matrices
    Abrams, Marc; Batongbacal, Alan; Ribler, Randy; Vazirani, Devendra; Heath, Lenwood S.; Pemmaraju, Sriram V. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-06-01)
    A connection between a queue layout of an undirected graph and a staircase cover of its adjacency matrix is established. The connection is exploited to establish a number of combinatorial results relating the number of vertices, the number of edges, and the queue number of a queue layout. The staircase notion is generalized to that of an (h,w)- staircase, and an efficient algorithm to optimally cover a matrix with (h,w)- staircases is presented. The algorithm is applied to problems of monotonic subsequences and to the maxdominance problem of Atallah and Kosaraju.