bluuebunny/crossref_metadata_2025 huggingface dataset:
Review of "Structural Mechanics Computer Programs" University Press of Virginia, Charlottesville, Virginia, 1105 pages.
Authors: Potts Jackie
Published: January 2007

In June, University Press of Virginia published Structural Mechanics Computer Programs, Surveys, Assessments, and Availability. The book contains most of the papers presented at the International Symposium on Structural Mechanics Computer Software which was held at the University of Maryland from 12 - 14 June.
Computer aided plant layout design
Authors: Ciaffi F.
Published: January 2007

Plant layout is of fundamental importance for the arrangement and allocation of internal plant-areas an essential and frequent operation for large industrial installations.
Optimising automatic tracking of multilayer boards
Authors: Adshead H. G.
Published: January 2007

The paper commences with a brief but critical appreciation of some known automatic tracking techniques for multilayer printed circuit boards, viz. Maze-Running, Line-Search and Channel-Allocation. The purpose here is to bring out their inherent similarity and to propound their specific superiority under different combinations of controlling criteria dictated by technological constraints. Consideration is given to the prohibitive core and time requirement for a real life environment involving an approximately 500 x 500 track matrix associated with the request for orthogonally connecting about 2500 pin-pairs, on each board. The paper then proceeds to discuss in detail the evolution of an effective algorithm and list-structure capable of successfully handling this problem. Finally several side issues of major significance are introduced. The efficient pre-sorting of the order in which wires are submitted to the main algorithm has been found to make a significant contribution to the efficiency of the entire system. Profile analysis is developed as a technique for comparing the relative merits of various topological placements of the logic network. The importance of the basic board layout and its relation to the algorithm employed is stressed.
A model of real time control system production
Authors: Matelan M. N.
Published: January 2007

Many facets of Computer Science and associated technologies may be profitably viewed as dedicated real time control activities. Production of systems to exercise such control has been difficult and costly. An abstract model of the process of producing these systems is presented. The model indicates three areas of the design problem amenable to automation: 1) the selection and configuration of hardware; 2) the production of software; and 3) the selection of a monitor to maintain real time integrity of the entire system. The concept of hardware binding is introduced and it is shown that delaying the point in the design cycle where hardware is functionally bound allows a new approach to machine independence.This paper comprises two chapters of a larger work which developes an implementation-independent application-specification language and techniques to automate control system design. Such an automation system is intended to produce a hardware configuration listing and software which together define a complete dedicated real time controller. Development of this system is based on the model presented here and is an on-going design automation project at Lawrence Livermore Laboratory.
Computer aided design and design automation in Europe
Authors: Magnuson Waldo G.
Published: January 2007

The development of CAD and DA in Italy and Germany compares closely with that in Britain. Germany, although lagging behind the US in computer utilization in engineering design, appeared to have better and more numerous contacts with US research in CAD and DA than either Italy or Britain has. Philips in Holland is taking a very aggressive approach to developing company coordination in CAD. Similarly, Siemens in Germany has a sizable group in CAD. Olivetti in Italy over the years, has developed extensive DA systems quite independent of other research. Among the universities, the University of Karlsruhe, Technische Hochschule Darmstadt and University of Bologna and have active and excellent research programs in CAD and DA.
Automatic PC board routing cleanup procedures
Authors: Smith R. J. , Castleton R. N. , Kaminsky W. J.
Published: January 2007

Automatic routing programs produce layouts which contain features that could be improved. This paper describes straightforward techniques for layout improvement that are routing algorithm independent.
Data management requirements for large scale design and production
Authors: Atkinson Malcolm , Wiseman Neil
Published: January 2007

The paper sets out to clarify and expose the differences and similarities between the data organisation requirements in two ranges of computer activity. These are computing in administration and computing in design. In both cases the man and machine synergy is supported by large bodies of data, so that we may expect the activities to be comparable.
Feasibility demonstration of an automated design system
Authors: Ross Alan A.
Published: January 2007

M. N. Matelan recently developed an abstract model for the control system design process (Matelan, 1976). Several features of this CSD model make it an attractive structure for an automated design system. These features include a method of stating the design problem independant of any realization technology and an approach which divides the design problem into a series of contingencies to be tested, related tasks to be performed as necessary, and a monitor strategy which controls the time sequencing of these contingency/task pairs. The concept of hardware binding is also introduced, which facilitates the simultaneous development of hardware and software.
A digital design automation course for logic designers
Authors: vanCleemput W. M.
Published: January 2007

This paper describes a course which is being offered to graduate students at Stanford University as well as to practicing logic designers from industry. The main purpose of this course is to familiarize logic designers with the current state-of-the-art of digital design automation.
Phoenix software development system overview
Authors: Rosene A. F.
Published: January 2007

The Eastern Division Automated Software Development System is a life-cycle software development methodology expedited and enforced by use of a collection of software tools which run on the DECsystem-20 engineering computing facility. These three items - methodology, tools, and computer - have been integrated into a system which appears to the user as (1) commands which can be used to create, modify, and display the data which comprises the project design, (2) standards which are implemented and enforced by the execution of the commands, and (3) reports for management visibility. The objective of this system is to improve the quality, increase the management control, and reduce the costs of software.
Phoenix architecture
Authors: Roder John
Published: January 2007

Multiprogramming and multitasking programming concepts are familiar to most of us. In a multiprogrammed arrangement several "user programs" can share the use of a single computer in a time sharing mode. An executive program provides the time slices to the "user programs" by activating and deactivating them according to some schedule. When multitasking is added to this arrangement, a "user program" may have several incarnations and the executive provides time slices to the incarnations of the user programs.
The design of a dense PCB using an interactive DA system
Authors: Rager David , Weiner Herb
Published: January 2007

Historically, there have been two approaches to the use of computers for the design of printed circuit boards: Computer Aided Design (CAD) wherein a designer carries out the design of the board and a computer, coupled with graphics hardware (usually a storage tube) and software is used to carry out graphic handling and bookkeeping tasks; and Design Automation (DA) wherein a sophisticated placement and routing program, usually installed on a large computer, is used in a batch process mode to carry out the design according to necessarily limited algorithms. When either of these approaches is used in conjunction with dense PCB designs, the results have been unsatisfactory: From CAD because of a feeling that "the computer should be able to help me more in solving this knotty problem"; and from DA because the results of the automated process are usually so poor as to approach being worthless: that is, the effort to complete the design approaches the level of difficulty of designing the card manually from the beginning. The use of a computer-based design system for the design of dense printed circuit boards (PCB's) has thus been an elusive goal.
An evaluation of random input test for the verification of circuit realizations
Authors: Wakimura Yoshiaki , Tohma Yoshihiro
Published: January 2007

This paper evaluates the capability of a random input test for the verification that a given circuit correctly realizes its specification.
Multilevel parallel processor for the data file application
Authors: Hoang Quang Hong , Vincent Ung
Published: January 2007

In the view of the difficulties encountered by the technics of associative memory processors, we propose a new hardware approach for the data file application.The proposed method is characterized by a parallel processing of the data provided sequently in a high velocity by a data source.
Some conclusions on a top-down functional specifications definition experiment
Authors: Lekkos Anthony A.
Published: January 2007

Functional Specifications are considered the foundation to the software development process. Fewer problems in software development are caused by design and implementation phase, and more by the specifications definition phase.This paper reports the results of an experiment undertaken by a small group of individuals to define the Functional Specifications in a top-down manner.
Design automation in creativity development
Authors: Ishikawa Akira , Mieno Hiroshi , Sakamoto Kazuo
Published: January 2007

Although the development of creativity and related issues have been studied for ages, we have as yet to reach a gratifying plateau, due partially to a slow progress in cerebral physiology and partially, on the part of studies on creativity process itself.
Cost effective data entry techniques for design automation
Authors: Harvel Jerry T.
Published: January 2007

A major problem in automating the design of printed circuit boards and hybrids is an effective method of converting data from engineering documentation into machine readable form. The process is time consuming and error-prone, often representing 30% or more of the total design effort.This paper addresses several methods for capturing data from a schematic or logic diagram, and data entry. Traditional mediums, such as cards and tape, are reviewed. Conventional techniques, such as key-to-disc and key-to-tape are examined, and advanced techniques, such as graphic and voice data entry are also explored. Data conversion from other sources, such as existing wire lists, is also reviewed. The methods, techniques and procedures are investigated in detail.
Open source search
Authors: Buntine Wray
Published: January 2007

Commercial search engines provide a quality service at no cost to consumers thanks to embedded targeted marketing. Despite this, I argue there are still reasons why an open source effort should be encouraged in the community: as part of broader open publishing initiatives, to allow quality subject specific search engines to develop, and "because we can," because search is one of the great grand challenge problems and we, the research community, cannot join in without an accessible, non-proprietary system. This talk outlines arguments and discusses some of the new technology that could go into such a system, as well as the infrastructure that would be required to make it work.
Report on the TREC 2004 genomics track
Authors: Hersh William R.
Published: January 2007

The goal of the TREC Genomics Track is to create test collections for evaluation of information retrieval (IR) and related tasks in the genomics domain. The Genomics Track differs from the other TREC tracks in that it is focused on retrieval in a specific domain. Initially the track has focused on modeling advanced users accessing the scientific literature. The advanced users include biomedical scientists and database curators or annotators. New advances in biotechnologies have changed the face of biological research, particularly "high-throughput" techniques such as gene microarrays (Mobasheri, Airley et al., 2004). These not only generate massive amounts of data but also have led to an explosion of new scientific knowledge. As a result, this domain is ripe for improved information access and management.
Relevance feedback at the INEX 2004 workshop
Authors: Crouch Carolyn
Published: January 2007

In 2004, the INitiative for the Evaluation of XML Retrieval (INEX), in its third year of investigations into various aspects of theoretical and applied structured retrieval, added a Relevance Feedback (RF) Track. The purpose of this Track is to explore issues related to the use of relevance feedback in a structured environment. Because the interim between the receipt of relevance assessments by Workshop participants and the due date of their papers was relatively short, the amount of time available for experiments was limited. However, three groups reported early experiments: Mass and Mandelbrod (Relevance Feedback for XML Retrieval); Mihajlovic, Ramirez, de Vries, Hiemstra, and Blok (TIJAH at INEX 2004 Modeling Phrases and Relevance Feedback); and Crouch, Majahan and Bellamkonda (Flexible Retrieval Based on the Vector Space Model).
Report on the INEX 2004 interactive track
Authors: Tombros Anastasios , Malik Saadia , Larsen Birger
Published: January 2007

As scientific data repositories, digital libraries and publishers increasingly use the eXtensible Markup Language (XML) for publication and storage interest has arisen in exploiting this formatting for retrieval purposes. XML is attractive because it defines the logical structure of the documents and has the potential to assist IR systems in providing more appropriate results to users, i.e., to return relevant document components (i.e. XML elements) rather than whole documents. In addition, the XML tags often have specific semantics that may be exploited purposefully in IR.
The NLP task at INEX 2004
Authors: Geva Shlomo , Sahama Tony
Published: January 2007

The INEX workshop is concerned with Evaluating the effectiveness of XML retrieval systems. In 2004 a natural language query task was added to the INEX Ad hoc track. Standard INEX Ad hoc topic titles are specified in NEXI -- a simplified and restricted subset of XPath, with a similar feel, and yet with a distinct IR flavour and interpretation. The syntax of NEXI is rigid and it imposes some limitations on the kind of information need that it can faithfully capture. At INEX 2004 the NLP question to be answered was simple -- is it practical to use a natural language query that is the equivalent of the formal NEXI title? The results of this experiment are reported and some information on the future direction of the NLP task is presented.
Verification of bibliometric methods' applicability for thesaurus construction
Authors: Schneider Jesper W.
Published: January 2007

The doctoral dissertation work concerns the development and exploration of a semi-automatic thesaurus construction approach based on bibliometric methods.
Fixed point analysis of single cell IEEE 802.11e WLANs
Authors: Ramaiyan Venkatesh , Kumar Anurag , Altman Eitan
Published: January 2007

We consider the vector fixed point equations arising out of the analysis of the saturation throughput of a single cell IEEE 802.11e wireless local area network with nodes that have different back-off parameters, including different Arbitration InterFrame Space (AIFS) values. We consider balanced and unbalanced solutions of the fixed point equations arising in homogeneous and nonhomogeneous networks. We are concerned, in particular, with (i) whether the fixed point is balanced within a class, and (ii) whether the fixed point is unique. Our simulations show that when multiple unbalanced fixed points exist in a homogeneous system then the time behaviour of the system demonstrates severe short term unfairness (or
multistability
). Implications for the use of the fixed point formulation for performance analysis are also discussed. We provide a condition for the fixed point solution to be balanced within a class, and also a condition for uniqueness. We then provide an extension of our general fixed point analysis to capture AIFS based differentiation; again a condition for uniqueness is established. An asymptotic analysis of the fixed point is provided for the case in which packets are never abandoned, and the number of nodes goes to ∞. Finally the fixed point equations are used to obtain insights into the throughput differentiation provided by different initial back-offs, persistence factors, and AIFS, for finite number of nodes, and for differentiation parameter values similar to those in the standard.
Empirical evaluation of multi-level buffer cache collaboration for storage systems
Authors: Chen Zhifeng , Zhang Yan , Zhou Yuanyuan , Scott Heidi , Schiefer Berni
Published: January 2007

To bridge the increasing processor-disk performance gap, buffer caches are used in both storage clients (e.g. database systems) and storage servers to reduce the number of slow disk accesses. These buffer caches need to be managed effectively to deliver the performance commensurate to the aggregate buffer cache size. To address this problem, two paradigms have been proposed recently to
collaboratively
manage these buffer caches together: the

hierarchy-aware caching

maintains the same
I/O
interface and is fully transparent to the storage client software, and the

aggressively-collaborative caching

trades off transparency for performance and requires changes to both the interface and the storage client software. Before storage industry starts to implement collaborative caching in real systems, it is crucial to find out whether sacrificing transparency is really worthwhile, i.e., how much can we gain by using the aggressively-collaborative caching instead of the hierarchy-aware caching? To accurately answer this question, it is required to consider all possible combinations of recently proposed local replacement algorithms and optimization techniques in both collaboration paradigms.Our study provides an empirical evaluation to address the above questions. Particularly, we have compared three aggressively-collaborative approaches with two hierarchy-aware approaches for four different types of database/file
I/O
workloads using traces collected from real commercial systems such as
IBM DB2
. More importantly, we separate the effects of collaborative caching from local replacement algorithms and optimizations, and uniformly apply several recently proposed local replacement algorithms and optimizations to all five collaboration approaches.When appropriate local optimizations and replacement algorithms are uniformly applied to both hierarchy-aware and aggressively-collaborative caching, the results indicate that hierarchy-aware caching can deliver similar performance as aggressively-collaborative caching. The results show that the aggressively-collaborative caching only provides less than 2.5% performance improvement on average in simulation and 1.0% in real system experiments over the hierarchy-aware caching for most workloads and cache configurations. Our sensitivity study indicates that the performance gain of aggressively-collaborative caching is also very small for various storage networks and different cache configurations. Therefore, considering its simplicity and generality, hierarchy-aware caching is more feasible than aggressively-collaborative caching.
The performance impact of kernel prefetching on buffer cache replacement algorithms
Authors: Butt Ali R. , Gniady Chris , Hu Y. Charlie
Published: January 2007

A fundamental challenge in improving the file system performance is to design effective block replacement algorithms to minimize buffer cache misses. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively without taking into account file system prefetching which exists in all modern operating systems. This paper shows that such kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. These results demonstrate the importance for buffer caching research to take file system prefetching into consideration.
Fast data-locality profiling of native execution
Authors: Berg Erik , Hagersten Erik
Published: January 2007

Performance tools based on hardware counters can efficiently profile the cache behavior of an application and help software developers improve its cache utilization. Simulator-based tools can potentially provide more insights and flexibility and model many different cache configurations, but have the drawback of large run-time overhead.We present StatCache, a performance tool based on a statistical cache model. It has a small run-time overhead while providing much of the flexibility of simulator-based tools. A monitor process running in the background collects sparse memory access statistics about the analyzed application running natively on a host computer. Generic locality information is derived and presented in a code-centric and/or data-centric view.We evaluate the accuracy and performance of the tool using ten SPEC CPU2000 benchmarks. We also exemplify how the flexibility of the tool can be used to better understand the characteristics of cache-related performance problems.
Automatic measurement of memory hierarchy parameters
Authors: Yotov Kamen , Pingali Keshav , Stodghill Paul
Published: January 2007

The running time of many applications is dominated by the cost of memory operations. To optimize such applications for a given platform, it is necessary to have a detailed knowledge of the memory hierarchy parameters of that platform. In practice, this information is poorly documented if at all. Moreover, there is growing interest in self-tuning, autonomic software systems that can optimize themselves for different platforms; these systems must determine memory hierarchy parameters automatically without human intervention.One solution is to use micro-benchmarks to determine the parameters of the memory hierarchy. In this paper, we argue that existing micro-benchmarks are inadequate, and present novel micro-benchmarks for determining parameters of all levels of the memory hierarchy, including registers, all data caches and the translation look-aside buffer. We have implemented these micro-benchmarks in a tool called X-Ray that can be ported easily to new platforms. We present experimental results that show that X-Ray successfully determines memory hierarchy parameters on current platforms, and compare its accuracy with that of existing tools.
Optimal insensitive routing and bandwidth sharing in simple data networks
Authors: Jonckheere M. , Virtamo J.
Published: January 2007

Many communication systems can be efficiently modelled using queueing networks with a stationary distribution that is insensitive to detailed traffic characteristics and depends on arrival rates and mean service requirements only. This robustness enables simple engineering rules and is thus of considerable practical interest. In this paper we extend previous results by relaxing the usual assumption of static routing and balanced service rates to account for both dynamic capacity allocation and dynamic load balancing. This relaxation is necessary to model systems like grid computing, for instance. Our results identify joint dynamic allocation and routing policies for single input reversible networks that are optimal for a wide range of performance metrics. A simple two-pass algorithm is presented for finding the optimal policy. The derived analytical results are applied in a number of simple numerical examples that illustrate their modelling potential.
Optimization model of internet protocols
Authors: Low Steven , Doyle J. , Li L. , Tang A. , Wang J.
Published: January 2007

Layered architecture is one of the most fundamental and influential structures of network design. Can we integrate the various protocol layers into a single coherent theory by regarding them as carrying out an asynchronous distributed primal-dual computation over the network to implicitly solve a global optimization problem? Different layers iterate on different subsets of the decision variables using local information to achieve individual optimalities, but taken together, these local algorithms attempt to achieve a global objective. Such a theory will expose the interconnection between protocol layers and can be used to study rigorously the performance tradeoff in protocol layering as different ways to distribute a centralized computation. In this talk, we describe some preliminary work towards this goal and discuss some of the difficulties of this approach.
An optimization based approach for cross-layer design in wireless communication networks
Authors: Shroff Ness , Lin Xiaojun
Published: January 2007

In this talk we study the issue of cross-layer design for rate control in multihop wireless networks. We have developed an optimal cross-layered rate control scheme that jointly computes both the rate allocation and the stabilizing schedule that controls the resources at the underlying layers. However, the scheduling component in this optimal cross-layered rate control scheme has to solve a complex global optimization problem at each time, and is hence too computationally expensive for online implementation. Thus, we study the impact on the performance of cross-layer rate control if the network can only use an imperfect (and potentially distributed) scheduling component that is easier to implement. We study scenarios with both fixed number of users as well as when the number of users change due to arrivals and departures in the system. In each case, we establish desirable results on the performance bounds of cross-layered rate control with imperfect scheduling. Our cross-layered approach provides provably better performance bounds when compared with a layered approach (that does not design rate control and scheduling together). The insights drawn from our analyses also enable us to design a fully distributed cross-layered rate control and scheduling algorithm under a restrictive interference model.
A network service curve approach for the stochastic analysis of networks
Authors: Ciucu Florin , Burchard Almut , Liebeherr Jörg
Published: January 2007

The stochastic network calculus is an evolving new methodology for backlog and delay analysis of networks that can account for statistical multiplexing gain. This paper advances the stochastic network calculus by deriving a network service curve, which expresses the service given to a flow by the network as a whole in terms of a probabilistic bound. The presented network service curve permits the calculation of statistical end-to-end delay and backlog bounds for broad classes of arrival and service distributions. The benefits of the derived service curve are illustrated for the exponentially bounded burstiness (EBB) traffic model. It is shown that end-to-end performance measures computed with a network service curve are bounded byO(HlogH), whereHis the number of nodes traversed by a flow. Using currently available techniques that compute end-to-end bounds by adding single node results, the corresponding performance measures are bounded byO(H3).
Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices
Authors: Zhao Qi (George) , Kumar Abhishek , Wang Jia , Xu Jun (Jim)
Published: January 2007

The traffic volume between origin/destination (OD) pairs in a network, known as traffic matrix, is essential for efficient network provisioning and traffic engineering. Existing approaches of estimating the traffic matrix, based on statistical inference and/or packet sampling, usually cannot achieve very high estimation accuracy. In this work, we take a brand new approach in attacking this problem. We propose a novel data streaming algorithm that can process traffic stream at very high speed (e.g., 40 Gbps) and produce traffic digests that are orders of magnitude smaller than the traffic stream. By correlating the digests collected at any OD pair using Bayesian statistics, the volume of traffic flowing between the OD pair can be accurately determined. We also establish principles and techniques for optimally combining this streaming method with sampling, when sampling is necessary due to stringent resource constraints. In addition, we propose another data streaming algorithm that estimates
flow matrix
, a finer-grained characterization than traffic matrix. Flow matrix is concerned with not only the total traffic between an OD pair (traffic matrix), but also how it splits into flows of various sizes. Through rigorous theoretical analysis and extensive synthetic experiments on real Internet traffic, we demonstrate that these two algorithms can produce very accurate estimation of traffic matrix and flow matrix respectively.
Troubleshooting multihop wireless networks
Authors: Qiu Lili , Bahl Paramvir , Rao Ananth , Zhou Lidong
Published: January 2007

Effective network troubleshooting is critical for maintaining efficient and reliable network operation. Troubleshooting is especially challenging in multihop wireless networks because the behavior of such networks depends on complicated interactions between many unpredictable factors such as RF noise, signal propagation, node interference, and traffic flows. In this paper we propose a new direction for research on fault diagnosis in wireless networks. Specifically, we present a diagnostic system that employs trace-driven simulations to detect faults and perform root cause analysis. We apply this approach to diagnose performance problems caused by packet dropping, link congestion, external noise, and MAC misbehavior. In a 25 node multihop wireless network, we are able to diagnose over 10 simultaneous faults of multiple types with more than 80% coverage. Our framework is general enough for a wide variety of wireless and wired networks.
Mobi_Causal
Authors: Benzaid Chafika , Badache Nadjib
Published: January 2007

This paper presents, Mobi_Causal, a new protocol to implement causal ordering in mobile computing systems. The implementation of causal ordering proposed in this paper uses the new timestamping mechanisms proposed by Prakash and Singhal for mobile environments; dependency sequences and hierarchical clocks. Our protocol, compared with previous proposals, is characterized by the elimination of unnecessary inhibition delay in delivering messages while maintaining low message overhead. Our protocol requires minimal resources on mobile hosts and wireless links. The proposed protocol is also scalable and can easily handle dynamic change in the number of participating mobile hosts in the system.
Achieving all the time, everywhere access in next-generation mobile networks
Authors: Cinque Marcello , Cotroneo Domenico , Russo Stefano
Published: January 2007

The anytime, anywhere access view of nomadic computing is evolving towards all the time, everywhere views of pervasive computing. The all the time access requires mobile devices to be always connected, even if connectivity may be compromised due to Access Point overload and to transient signal degradations. The everywhere access requires mobile devices to use heterogeneous Access Points (ranging from Bluetooth and 802.11 to 2.5G and 3G cellulars), leading to high variability of the connection status. A mobility management solution that leverages connection availability, while enabling applications to be aware of the connection status, is thus needed. This paper proposes a Last Second Soft Handoff scheme that leverages the availability of connection. The proposed scheme has been integrated in a mobility management architecture, which provides connection awareness via an API, named NCSOCKS. Implementation issues are discussed and experimental results are provided.
Performance analysis of a broadcast communications protocol
Authors: Melliar-Smith P. M. , Moser Louise E.
Published: January 2007

The Trans protocol is a communications protocol that exploits the broadcast capability of local area networks. Classical Markov models and queueing theory are used to analyze the performance of components of this protocol, but cannot be applied directly to determine the performance of the protocol as a whole. Instead, Laplace transforms of the distributions for the components are first derived and then combined into a transform for the entire protocol. This transform is evaluated by contour integration to yield the latency for the protocol.
An approach to detecting changes in the factors affecting the performance of computer systems
Authors: Berry Robert , Hellerstein Joseph
Published: January 2007

Resolving intermittent performance problems in computer systems is made easier by pinpointing when a change occurs in the system's perforrnance-determinin g factors (e.g., workload composition, configuration). Since we often lack direct measurements of performance factors, this paper presents a procedure for indirectly detecting such changes by analyzing performance characteristics (e.g., response times, queue lengths). Our procedure employs a widely used clustering algorithm to identify candidate change points (the times at which performance factors change), and a newly developed statistical test (based on an AR(1) time series model) to determine the signficance of candidate change points. We evaluate our procedure by using simulations of M/M/1, FCFS queueing systems and by applying our procedure to measurements of a mainframe computer system at a large telephone company. These evaluations suggest that our procedure is effective in practice, especially for larger sample sizes and smaller utilizations. We further conclude that indirectly detecting changes in performance factors appears to be inherently difficult in that the sensitivity of a detection procedure depends on the magnitude of the change in performance characteristics, which often has a nonlinear relationship with the change in performance factors. Thus, a change in performance factors (e.g., increased service times) may be more readily detected in some situations (e.g., very low or very high utilizations) than in others (e.g., moderate utilizations). A key insight here is that the sensitivity of the detection procedure can be improved by choosing appropriate measures of performance characteristics. For example, our experience and analysis suggest that queue lengths can be more sensitive than response times to changes in arrival rates.
A synthetic workload model for a distributed system file server
Authors: Bodnarchuk Robert , Bunt Richard
Published: January 2007

The accuracy of the results of any performance study depends largely on the quality of the workload model driving it. Not surprisingly then, workload modelling is an area of great interest to those involved in the study of computer system performance. While a significant amount of research has focussed on the modelling of workloads in a centralized computer system, little has been done in the context of distributed systems. The goal of this research was to model the workload of a distributed system file server in a UNIX/NFS environment. The resulting model is distribution-driven and generates workload components in real time. It runs externally to the system it drives, thus eliminating any interference at the server. The model was validated for different workload intensities to ensure that it provides the flexibility to vary the workload intensity without loss of accuracy.
A Markov chain approximation for the analysis of banyan networks
Authors: Merchant Arif
Published: January 2007

This paper analyzes the delay suffered by messages in a clocked, packet-switched, square Banyan network with
k
x
k
output-buffered switches by approximating the flow processes in the network with Markov chains. We recursively approximate the departure process of buffers of the n
th
stage in terms of thqt at the
n
-- l
st
stage. We show how to construct the transition matrix for the Markov chain at each stage of the network and how to solve for the stationary distribution of the delay in the queues of that stage. The analytical results are compared with simulation results for several cases. Finally, we give a method based on this approximation and the technique of
coupling
to compute upper bounds on the time for the system to approach steady state.
A model for estimating trace-sample miss ratios
Authors: Wood David A. , Hill Mark D. , Kessler R. E.
Published: January 2007

Unknown references, also known as cold-start misses, arise during trace-driven simulation of uniprocessor caches because of the unknown initial conditions. Accurately estimating the miss ratio of unknown references, denoted by μ, is particularly important when simulating large caches with short trace samples, since many references may be unknown.In this paper we make three contributions regarding μ. First, we provide empirical evidence that μ is much larger than the overall miss ratio (e.g., 0.40 vs. 0.02). Prior work suggests that they should be the same. Second, we develop a model that explains our empirical results for long trace samples. In our model, each block frame is either
live
, if its next reference will hit, or dead, if its next reference will miss. We model each block frame as an alternating renewal process, and use the renewal-reward theorem to show that μ is simply the fraction of time block frames are dead. Finally, we extend the model to handle short trace samples and use it to develop several estimators of μ. Trace-driven simulation results show these estimators lead to better estimates of overall miss ratios than do previous methods.
Performance analysis of Time Warp with homogeneous processors and exponential task times
Authors: Gupta Anurag , Akyildiz Ian , Fujimoto Richard M.
Published: January 2007

The behavior of n interacting processors synchronized by the "Time Warp" protocol is analyzed using a discrete state continuous time Markov chain model. The performance and dynamics of the processes are analyzed under the following assumptions: exponential task times and times-tamp increments on messages, each event message generates one new message that is sent to a randomly selected process, negligible rollback, state saving, and communication delay, unbounded message buffers, and homogeneous processors that are never idle. We determine the fraction of processed events that commit, speedup, rollback probability, expected length of rollback, the probability mass function for the number of uncommitted processed events, and the probability distribution function for the virtual time of a process. The analysis is approximate, so the results have been validated through performance measurements of a Time Warp testbed (PHOLD workload model) executing on a shared memory multiprocessor.
On subcube dependability in a hypercube
Authors: Kim Jong , Das Chita R.
Published: January 2007

In this paper, we present an analytical model for computing the dependability of hypercube systems. The model, referred to as task-based dependability (TBD), is developed under the assumption that a task needs at least an
m
-cube (
m
<
n
) in an n-cube for its execution. Two probabilistic terms are required for computing this dependability. The first is the probability of any
x
nodes working out of 2
n
nodes. The second term is a conditional probability that at least a connected m-cube exists among those
x
working nodes. This term is computed using a recursive expression. Two dependability measures, reliability and availability, are analyzed in this paper. A combinatorial enumeration is used in the reliability analysis, and a machine repairman model is used in the availability analysis to find the first probability. The machine repairman model is modified to capture imperfect coverage and imprecise repair. The TBD model is also extended to find multitask dependability. Numerical results are presented for n-cubes with different task requirements and are validated through extensive simulation. It is observed that an m-cube requirement is highly restrictive compared to the simple 2
m
-connected node requirement.
Analysis of task migration in shared-memory multiprocessor scheduling
Authors: Squillante Mark S. , Nelson Randolph D.
Published: January 2007

In shared-memory multiprocessor systems it may be more efficient to schedule a task on one processor than on mother. Due to the inevitability of idle processors in these environments, there exists an important tradeoff between keeping the workload balanced and scheduling tasks where they run most efficiently. The purpose of an adaptive task migration policy is to determine the appropriate balance between the extremes of this load sharing tradeoff.We make the observation that there are considerable differences between this load sharing problem in distributed and shared-memory multiprocessor systems, and we formulate a queueing theoretic model of task migration to study the problem. A detailed mathematical analysis of the model is developed, which includes the effects of increased contention for system resources induced by the task migration policy. Our objective is to provide a better understanding of task migration in shared-memory multiprocessor environments. In particular, we illustrate the potential for significant improvements in system performance, and we show that even when migration costs are large it may still be beneficial to migrate waiting tasks to idle processors. We further demonstrate the potential for unstable behavior under migratory scheduling policies, and we provide optimal policy thresholds that yield the best performance and avoid this form of processor thrashing.
Analytical modelling of a hierarchical buffer for a data sharing environment
Authors: Dan Asit , Dias Daniel M. , Yu Philip S.
Published: January 2007

In a data sharing environment, where a number of loosely coupled computing nodes share a common storage subsystem, the effectiveness of a private buffer at each node is limited due to the multi-system invalidation effect, particularly under a non-uniform data access pattern. A global shared buffer can be introduced to alleviate this problem either as a disk cache or shared memory. In this paper we developed an approximate analytic model to evaluate different shared buffer management policies (SBMPs) which differ in their choice of data granules to be put into the shared buffer. The analytic model can be used to study the trade-offs of different SBMPs and the impact of different buffer allocations between shared and private buffers. The effects of various parameters, such as, the probability of update, the number of nodes, the sizes of private and shared buffer, etc., on the performance of SBMPS are captured in the analytic model. A detailed simulation model is also developed to validate the analytic model. We show that dependency between the contents of the private and shared buffers can play an important role in determining the effectiveness of the shared buffer particularly for a small number of nodes.
Performance of a mirrored disk in a real-time transaction system
Authors: Chen Shenze , Towsley Don
Published: January 2007

Disk mirroring has found widespread use in computer systems as a method for providing fault tolerance. In addition to increasing reliability, a mirrored disk can also reduce I/O response time by supporting the execution of parallel I/O requests. The improvement in I/O efficiency is extremely important in a real-time system, where each computational entity carries a deadline. In this paper, we present two classes of real-time disk scheduling policies, RT-DMQ and RT-CMQ, for a mirrored disk I/O subsystem and examine their performance in an integrated real-time transaction system. The real-time transaction system model is validated on a real-time database testbed, called RT-CARAT. The performance results show that a mirrored disk I/O subsystem can decrease the fraction of transactions that miss their deadlines over a single disk system by 68%. Our results also reveal the importance of real-time scheduling policies, which can lead up to a 17% performance improvement over non-real-time policies in terms of minimizing the transaction loss ratio.
MTOOL
Authors: Goldberg Aaron , Hennessy John
Published: January 2007

This paper presents a new, relatively inexpensive method for detecting regions (e.g. loops and procedures) in a program where the memory hierarchy is performing poorly. By observing where actual measured execution time differs from the time predicted given a perfect memory system, we can isolate memory bottlenecks. MTOOL, an implementation of the approach aimed at applications programs running on MIPS-chip based workstations is described and results for some of the Perfect Club and SPEC benchmarks are summarized.
Performance analysis case study (abstract)
Authors: Newman Robb
Published: January 2007

A common requirement of computer vendor's competitive performance analysis departments is to measure and report on the performance characteristics of another vendor's system. In many cases the amount of prior knowledge concerning the competitor's systcm is limited to sales brochures and non-technical publications. Availability of the system for benchmarking is minimal; there is little choice concerning memory and I/O configurations; and time to complete the project is short. A project of this nature is not, however, unique to computer vendors. Many users of computer systems that want to better understand a system's performance characteristics before deciding on a purchase, are also faced with similar restrictions.
Measurements of the paging behavior of UNIX
Authors: Park Arvin , Becker Jeffrey C.
Published: January 2007

This paper analyzes measurements of paging activity from several different versions of UNIX. We set out to characterize paging activity by first taking measurements of it, and then writing programs to analyze it. In doing so, we were interested in answering several questions:1. What is the magnitude of paging traffic and how much of I/O system activity is paging related?2. What are the characteristics of paging activity, and how can paging system implementations be tuned to match them?3. How does paging activity vary across different machines, operating systems, and job mixes?4. How well does paging activity correlate with system load average and number of users?
A parallel branch-and-bound algorithm for MIN-based multiprocessors
Authors: Yang Myung K. , Das Chita R.
Published: January 2007

A parallel "Decomposite Best-First" search Branch-and-Bound algorithm (
pdbsbb
) for MIN-based multiprocessor systems is proposed in this paper. A conflict free mapping scheme, known as
step-by-step spread
, is used to map the algorithm efficiently on to a MIN-based system for reducing communication overhead. It is shown that the proposed algorithm provides better speed-up than other reported schemes when communication overhead is taken into consideration.
An overlay facility for LISP programs
Authors: Greenawalt E. M.
Published: January 2007

An overlay facility is described which enables large LISP programs such as are frequently encountered in symbolic algebraic manipulation to be used in a memory environment considerably smaller than required for the entire program. This facility has been implemented in the University of Texas LISP for CDC 6000 series machines, and has been so far applied to Joel Moses' integration package with good results.