Department of Computer Science

Permanent URI for this community

https://hdl.handle.net/10919/19035

The Department of Computer Science has an accredited undergraduate program that offers specialized ‘tracks’ of study in key areas. Undergraduates are prepared by graduation for pursuing a computing career or for graduate study. Our active corporate partners program offers internships and permanent employment to our students. Students are encouraged to participate in research experiences during their studies. Capstone courses provide significant team project experiences. The graduate program offers M.S. and Ph.D. degrees, emphasizing thesis work both at the main campus in Blacksburg and at the Northern Virginia Center. About two-thirds of the graduate students are pursuing the Ph.D. degree. The faculty, among whom there are 12 NSF or DOE CAREER Award winners, are active researchers who are visible contributors to the profession and have achieved significant honors.

Browse

Now showing 1 - 20 of 42

Adapting Protocols to Massively Interconnected Systems
Kafura, Dennis G.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1991-05-01)
This paper describes ongoing research focused on two critical problems posed by the interconnection of a massive number of computer systems. The interconnection may be achieved through wide area or local area networks. The two problems considered in this research are as follows: (1) performance analysis of the protocols used in an internetwork connecting thousands to millions of nodes, and (2) application development in a massively distributed, heterogeneous environment where components implemented in different programming languages must be integrated and/or reused. The performance analysis problem is addressed by employing large-scale parallel simulation, extended finite state machines and objected-oriented simulation techniques. The approach to solving the application development problem is based on an environment which exploits the synergism between object-oriented programming and layered communication protocols (specifically, OSI).
Analysis of Bottlenecks in International Internet Links
Ahsan Habib, Md; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1998-12-01)
We report on preliminary results of analysis into the sources of congestion in international Internet routes from the United States to several countries: Brazil and South Africa. Using the pathchar and traceroute tools, we identified which links in a variety of routes are a bottleneck. The measures used were throughput, round trip delay, and router queueing delays. Measurements with ping were used to validate the round trip times obtained with pathchar.
Approximate Time-Parallel Simulation of Queueing Systems with Losses
Wang, Jain J.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
This paper presents a guideline of a partial state matching approach for time-parallel simulation. Two algorithms using this approach to simulate FCFS G/G/1/K and G/D/1/K queues in which arriving customers that find the queue full are lost are proposed. Experiments with M/M/1/K and M/D/1/K models show that the performance of the algorithms in terms of convergence speed and accuracy is good in general cases. The worst performance of the algorithms occurs when traffic intensity approaches one. An argument is made to explain this phenomenon.
Beyond Software Performance Visualization
Abrams, Marc; Lee, Timothy; Cadiz, Horacio; Ganugapati, Krishna (Department of Computer Science, Virginia Polytechnic Institute & State University, 1994-02-01)
Performance visualization tools of the last decade have yielded new insights into the new 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 are often separated in time by other events; thus discerning time dependent behavior often hinges on finding the "right" visualization - a possibly time-comsuming activity. CHITRA93 complements visualization systems, while alleviating these limitations. CHITRA93 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)); and 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 tools (addressing (2) and (3)). CHITRA93 incorporates: transforms, such as aggregation, that simplify the ensemble and reduce the state space size of the models generated; a user interface that allows some 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 a 20 state irreducible, periodic (non-Markovian) stochastic process.
Caching Proxies: Limitations and Potentials
Abrams, Marc; Standridge, Charles R.; Abdulla, Ghaleb; Williams, Stephen; Fox, Edward A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1995-07-01)
As the number of World-Wide Web users grow, so does the number of connections made to servers. This increases both network load and server load. Caching can reduce both loads by migrating copies of server files closer to the clients that use those files. Caching can either be done at a client or in the network (by a proxy server or gateway). We assess the potential of proxy servers to cache documents retrieved with the HTTP protocol. We monitored traffic corresponding to three types of educational workloads over a one semester period, and used this as input to a cache simulation. Our main findings are (1) that with our workloads a proxy has a 30-50% maximum possible hit rate no matter how it is designed; (2) that when the cache is full and a document is replaced, least recently used (LRU) is a poor policy, but simple variations can dramatically improve hit rate and reduce cache size; (3) that a proxy server really functions as a second level cache, and its hit rate may tend to decline with time after initial loading given a more or less constant set of users; and (4) that certain tuning configuration parameters for a cache may have little benefit.
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.
Chitra: Visual Analysis of Parallel and Distributed Programs in the Time, Event, and Frequency Domains
Abrams, Marc; Doraswamy, Naganand; Mathur, Anup (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
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 paper describes 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 PES's and transforms, to allow a user visually to 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.
Computational Geometric Performance Analysis of Limit Cycles in Timed Transition Systems
Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993-09-01)
Certain parallel software performance evaluation problems are equivalent to computational geometric problems. Consider a timed transition system representing a parallel program: a set of variables, a set of states, an initial state, a transition function mapping a set to a set of successor states, and a description of the time between transitions. Given a timed transition system, the paper solves four problems: (1) state the necessary and sufficient conditions for a TES to contain a LCES; (2) given the initial starting time of each process, find a representation of the set of all possible TESs; (3) determine if any initial process starting times exist that lead to a LCES in which no process ever blocks; and (4) find the set of all possible LCESs.
The Cost of Terminating Optimistic Parallel Discrete-Event Simulations
Sanjeevan, Vasant; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
In a previous paper, we proposed seven algorithms for mechanically adding an arbitrary termination condition to a conservative-synchronous, non-terminating parallel simulation. Informal arguments about the performance of each algorithm were made, and the arguments were confirmed through measurement for four of these algorithms. The benchmark used was the simulation of a Torus network using the Bounded Lag protocol on a shared memory multiprocessor. In this paper, we report on the performance of the simulation of the same Torus network benchmark with the same four termination conditions using an optimistic protocol on a message-passing multiprocessor. We also report on the performance of a colliding pucks simulation with three additional termination conditions.
Design Issues in General Purpose, Parallel Simulation Languages
Abrams, Marc; Lomow, Greg (Department of Computer Science, Virginia Polytechnic Institute & State University, 1989)
This paper addresses the topic of designing general purpose, parallel simulation languages. We discuss how parallel simulation languages differ from general purpose programming languages. Our thesis is that the issues of distribution, performance, unusual implementation mechanism, and the desire for determinism are the dominant considerations in designing a simulation language today. We then discuss the separate roles that special and general purpose simulation languages play. Next we use the two languages, Sim++ and CPS, to illustrate these issues. Then we discuss eight design considerations: process versus event oriented-view, basic program structure, I/O, making implementation cost explicit to the programmer, providing dynamic facilities, memory management, the semantics of false messages in time warp, and program development methodology considerations. A number of conclusions are drawn from our experiences in language design.
Determining Initial States for Time-Parallel Simulations
Wang, Jain J.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
In this paper, we propose a time-parallel simulation method which uses a pre-simulation to identify recurrent states. Also, an approximation technique is suggested for approximate Markovian modeling for queueing networks to extend the class of simulation models which can be simulated efficiently using our time-parallel simulation. A central server system and a virtual circuit of a packet-switched data communication network modeled by closed queueing networks are experimented with the proposed time-parallel simulation. Experiment results suggest that the proposed approach can exploit massive parallelism while yielding accurate results.
The Effectiveness of Cache Coherence Implemented on the Web
Doswell, Felicia; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 2000-08-01)
The popularity of the World Wide Web (Web) has generated so much network traffic that it has increased concerns as to how the Internet will scale to meet future demand. The increased population of users and the large size of files being transmitted have resulted in concerns for different types of Internet users. Server administrators want a manageable load on their servers. Network administrators need to eliminate unnecessary traffic, thereby allowing more bandwidth for useful information. End users desire faster document retrieval. Proxy caches decrease the number of messages that enter the network by satisfying requests before they reach the server. However, the use of proxies introduces a concern with how to maintain consistency among cached document versions. Existing consistency protocols used in the Web are proving to be insufficient to meet the growing needs of the World Wide Web population. For example, too many messages are due to caches guessing when their copy is inconsistent. One option is to apply the cache coherence strategies already in use for many other distributed systems, such as parallel computers. However, these methods are not satisfactory for the World Wide Web due to its larger size and range of users. This paper provides insight into the characteristics of document popularity and how often these popular documents change. The frequency of proxy accesses to documents is also studied to test the feasibility of providing coherence at the server. The main goal is to determine whether server invalidation is the most effective protocol to use on the Web today. We make recommendations based on how frequently documents change and are accessed.
Formally Reasoning About and Automatically Generating Sequential and Parallel Simulations
Abrams, Marc; Page, Ernest H. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
This paper proposes a methodology to automate the construction of simulation programs within the context of a simulation support environment. The methodology starts with a simulation model specification in the form of a set of coupled state transition systems. The paper provides a mechanical method of mapping the transition systems first into a set of formal assertions, permitting formal verification of the transition systems, and second into an executable program. UNITY, a computational model and proof system suitable for development of parallel and distributed programs through step-wise refinement of specifications, is used as the specification and program notation. The methodology provides a means to independently verify the correctness of the transition systems: one can specify properties formally that the model should obey and prove them as theorems using the formal specification.
Geometric Performance Analysis of Mutual Exclusion: The Model
Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
This paper is motivated by the need to better understand parallel program run-time behavior. The paper first formally describes a general model of program execution based on Djkstra's progress graphs. The paper then defines a special case of the model representing two cyclic processes sharing mutually exclusive, reusable resources. Processes synchronize through semaphore operations that are not embedded in conditionally executed code segments. Model parameters are the times at which each semaphore operation completes and the independently derived, constant execution time required by each process between points of completion of semaphore operations.
Geometric Performance Analysis of Mutual Exclusion: The Model Solution
Abrams, Marc; Agrawala, Ashok (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
This paper presents an analytic solution to progress graphs used for performance analysis. It derives the exact sequence of blocking and running times experienced by two processes sharing mutually exclusive, reusable resources. A novel application of Dijkstra's progress graphs yields the complex relationship between the waiting times at each synchronization point. The problem of solving progress graphs is formulated in terms of finding the minimum solution of each of a set of Diophantine equations. An algorithm is presented to find all steady state behaviors involving blocking that emerge from any initial condition.
Geometric Performance Analysis of Semaphore Programs
Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993-08-01)
A key problem in designing parallel programs that achieve a desired performance goal is the ability to analyze exactly program performance, given a specification of the process syncronization structure and the execution timings of all code segments. The problem solved in this paper is to derive, for all possible process starting times, the set of all possible limit cycle execution sequences in which a process blocks. This paper makes two contributions. First, it employs a novel analysis method that derives timed execution sequences from a geometric model of program execution, called timed progress graphs. Second, it solves the timed progress graph not by a computational geometric algorithm, as employed by most solutions in the literature to untimed progress graphs, but by an analytic solution.
The Impact of Lookahead on Conservative Simulation
Wang, Jain J.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1995-02-01)
This paper studies the impact on the performance of conservative simulation for both open and closed models. For open models, we derive an upper bound on the performance improvement due to the lookahead. We show that the benefit of lookahead diminishes as the simulation length increases. For closed models, on the other hand, the performance improvement converges to a constant as the simulation length increases.
Implementing a Global Termination Condition and Collecting Output Measures in Parallel Simulation
Abrams, Marc; Richardson, Debra S. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
This paper investigates how to implement arbitrary global termination conditions and collect statistics in a parallel simulation. The problem is first discussed using Chandy and Sherman's space-time framework. Then termination conditions are categorized, and termination algorithms are given for several categories. The chief problem is that if one evaluates the termination condition asynchronously with respect to the simulation, when termination is detected the simulator has already modified old attribute values needed to compute output measures. The major conclusion is that minor modification of time warp permits use any termination condition. In contrast, conservative protocols permit limitied termination conditions unless they are modified to incorporate mechanisms present in optimistic protocols.
Implications of Using the Event Scheduling World View for Parallel Simulation
Richardson, Debra S.; Abrams, Marc (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
Use of a particular world view, or conceptual framework, makes the programming of many simulations easier. Parallel simulation implementations generally have not been based on a particular world view. An open question is what impact a world view has on the execution of a simulation in parallel.
An Introduction to Visualizing Program Execution Dynamics with Chitra
Abrams, Marc; Doraswamy, Naganand (Department of Computer Science, Virginia Polytechnic Institute & State University, 1992)
We describe a tool called Chitra, which serves two purposes. First, Chitra visualizes program execution sequences (PES's) collected by monitoring parallel and distributed program execution in the time, event, and frequency domains. Second, Chitra produces an empirical model of a PES. A case study applies Chitra to predict and evaluate the efficiency and fairness of a resource sharing algorithm at a range of parameter values, given observations of a few parameter values. Inefficient behavior is explained by examining the states that constitute the stochastic process model constructed by Chitra.

Browse

Browsing Department of Computer Science by Author "Abrams, Marc"

Results Per Page

Sort Options