Search

This article reports that the Cypak company has developed a disposable paper computer that can collect, process, encrypt, and store up to 32 kilobytes of data. The Cypak's system contains printable sensors and a small multipurpose application-specific integrated circuit with a radio-frequency identification interface. It detects events or accepts input via graphite-ink circuits. Thus, if a user breaks a seal to remove a product or presses a surface to answer a question, the system recognizes whether the circuit is opened or closed and records the information.

Computer communication systems are complex systems in which both computing power and communications capabilities play a key role. Examples of such systems range from worldwide data and voice communications networks to local area networks, and even encompass the more recent multiprocessor computer systems. In the past, the design and development of such systems has been done in a fairly ad hoc manner. However, it is increasingly apparent that in order to understand and develop sucy systems, it is necessary to have a more systematic approach to designing and studying such systems.

The interpretations of logical expressions found in most introductory textbooks are not suitable for use in software engineering applications because they do not deal with partial functions. More advanced papers and texts deal with partial functions in a variety of complex ways. This paper proposes a very simple change to the classic interpretation of predicate expressions, one that defines their value for all values of all variables, yet is almost identical to the standard definitions. It then illustrates the application of this interpretation in software documentation. [ABSTRACT FROM AUTHOR]

The idea of proxying network connectivity has been proposed as an efficient mechanism to maintain network presence on behalf of idle devices, so that they can “sleep.” The concept has been around for many years; alternative architectural solutions have been proposed to implement it, which lead to different considerations about capability, effectiveness and energy efficiency. However, there is neither a clear understanding of the potential for energy saving nor a detailed performance comparison among the different proxy architectures. In this paper, we estimate the potential energy saving achievable by different architectural solutions for proxying network connectivity. Our work considers the tradeoff between the saving achievable by putting idle devices to sleep and the additional power consumption to run the proxy. Our analysis encompasses a broad range of alternatives, taking into consideration both implementations already available in the market and prototypes built for research purposes. We remark that the main value of our work is the estimation under realistic conditions, taking into consideration power measurements, usage profiles, and proxying capabilities. [ABSTRACT FROM AUTHOR]

Information about upcoming events of interest to Computer Society members. [ABSTRACT FROM PUBLISHER]

Many pervasive computing courses don't require a textbook. Instead, a variety of papers are given as assigned reading. Although there are advantages to using papers for reading assignments, there are disadvantages as well. With each course, instructors must curate their own list of important papers, and students don't have the benefit of a well-planned book, which ties together topics systematically. In light of this, Andrew Kun reviews nine books that might be a good match for pervasive computing courses. [ABSTRACT FROM PUBLISHER]

Microelectronic circuits exhibit increasing variations in performance, power consumption, and reliability parameters across the manufactured parts and across use of these parts over time in the field. These variations have led to increasing use of overdesign and guardbands in design and test to ensure yield and reliability with respect to a rigid set of datasheet specifications. This paper explores the possibility of constructing computing machines that purposely expose hardware variations to various layers of the system stack including software. This leads to the vision of underdesigned hardware that utilizes a software stack that opportunistically adapts to a sensed or modeled hardware. The envisioned underdesigned and opportunistic computing (UnO) machines face a number of challenges related to the sensing infrastructure and software interfaces that can effectively utilize the sensory data. In this paper, we outline specific sensing mechanisms that we have developed and their potential use in building UnO machines. [ABSTRACT FROM AUTHOR]

The Symposium on Foundations in Software Engineering is an annual conference sponsored by Association for Computing Machinery, a computer portal and dedicated to the presentation of innovative research results contributing to an engineering discipline for software systems. This special section of the July 1998 issue of the journal IEEE Transactions on Software Engineering features three of the best papers from the fourth symposium, held in October 1996 in San Francisco, California. During its first half-decade, research results presented at this conference have covered engineering research topics. However, a number of distinguishing properties tend to characterize the best of the papers and have helped set the standards for high-quality software engineering research. The three papers in this special section illustrate these properties. One of the critical challenges for software engineering research is to find practical tools that help system builder restructure existing systems. Mark Moriconi was general chair for the symposium and deserves considerable credit for its success.

This paper proposes general software optimization techniques for embedded systems based on processors, which mainly include general optimization methods in high language and software & hardware co-optimization in assembly language. Then these techniques are applied to optimize our MP3 decoder, which is based on RISC32, a RISC core compatible with MIPSI instruction set The last optimization decoder requires 48 MIPS and 49Kbytes memory space to decode 128Kbps, 44.1KHz joint stereo MP3 in real time with CPI 1.15, and we have achieved performance increase of 46.7% and memory space decrease of 38.8% over the original decoding software. [ABSTRACT FROM AUTHOR]

Experimental research in computer science is a relatively new, yet fast developing area. It is encouraging to that there is substantial research going on in this important area. A study on experimental evaluation of a reusability-oriented parallel programming environment is given. There is a significant amount of experimental research in the area of computer dependability.

Information about upcoming events of interest to Computer Society members. [ABSTRACT FROM PUBLISHER]

We have been seeing use of word “smart” before almost anything that we can think of in our day-to-day life: smart phone, smart TV, and smart appliance. At a bigger scale smart cities, smart villages, smart healthcare, and smart agriculture, are used to describe new generation of these physical entities. So, an obvious question: What is smart? From dictionary, smart means: “(of a person) clean, tidy, and well dressed” and “(of a device) programmed so as to be capable of some independent action.” Thus, smart and intelligence is the “ability to take decisions based on the data, circumstances, situations.” [ABSTRACT FROM AUTHOR]

DIRECT is a multiprocessor database machine designed and implemented at the University of Wisconsin. This paper describes our experiences with the implementation of DIRECT. We start with a brief overview of the original machine proposal and how it differs from what was actually implemented. We then describe the structure of the DIRECT software. This includes software on host computers that interfaces with the database machine; software on the back-end controller of DIRECT; and software executed by the query processors. In addition to describing the structure of the software we will attempt to motivate and justify its design and implementation. We also discuss a number of implementation issues (e.g., debugging of the code across several machines). We conclude the paper with a list of the "lessons" we have learned from this experience. [ABSTRACT FROM AUTHOR]

This paper presents a Mahalanobis distance (MD) based diagnostic approach that employs a probabilistic approach to establish thresholds to classify a product as being healthy or unhealthy. A technique for detecting trends and biasness in system health is presented by constructing a control chart for the MD value. The performance parameters' residuals, which are the differences between the estimated values (from an empirical model) and the observed values (from health monitoring), are used to isolate parameters that exhibit faults. To aid in the qualification of a product against a specific known fault, we suggest that a fault-specific threshold MD value be defined by minimizing an error function. A case study on notebook computers is presented to demonstrate the applicability of this proposed diagnostic approach. [ABSTRACT FROM AUTHOR]

Currently, the problem size that can be solved in reasonable time using the Method of Moments is limited by the amount of memory installed in the computer. This paper offers a new development that not only breaks this memory constraint, but also maintains the efficiency of running the problem in-core. In this paper, highly efficient parallel matrix-filling schemes are presented for parallel in-core and parallel out-of-core integral-equation solvers with subdomain RWG basis functions. The parallel methodology for matrix filling is quite different when using a subdomain basis as opposed to using a higher-order basis. The parallel in-core solver uses memory, which is often expensive and limited in size. The parallel out-of-core solver is introduced to extend the capability of MoM to solve larger problems that can be as large as the amount of storage on the hard disk. Numerical results on several typical computer platforms show that the parallel matrix-filling schemes and matrix-equation solvers introduced here are highly efficient and achieve theoretical predictions. The implementation of these advancements with the widely used RWG basis functions creates a powerful tool for efficient computational electromagnetics solution of complex real-world problems. [ABSTRACT FROM AUTHOR]

This paper presents an embedded digital system for incremental encoders allowing for high dynamic performance and accuracy speed measurement in all the operating conditions for the application in digital servo drives. The idea aims at embedding processing capabilities inside traditional position transducers in order to develop a smart measuring system. The base processing algorithm employs a novel mixed time and frequency measurement technique of the encoder signals. The iterative formulation of the algorithm and the limited hardware requirements allows its implementation by means of a standard microcontroller (e.g., TMS32OF24x) or by dedicated hardware. Communication between the smart sensor and the servo drive is preliminarily realized via high-speed serial peripheral interface. [ABSTRACT FROM AUTHOR]

Computers offer valuable opportunities to people with physical disabilities. For example, a computer can allow someone with severe speech and motor-impairment to engage more fully with the world. This paper describes the design of a communication aid for motor-impaired users, who literally use computers as their communication partners. Currently, a low cost interface suitable for different types of motor-impaired users is hardly available. Additionally, the target audience of existing such systems is very much limited. The present work solved these problems by its adaptation mechanism. The adaptation mechanism provides an appropriate interface from an interface bank for each user before start of an interaction. The adaptation mechanism is continued during as well as after the end of interactions to make the system personalized to individual user. [ABSTRACT FROM AUTHOR]

Deeds is a simulation environment for e-learning in digital electronics. The simulators cover combinational and sequential logic networks, finite state-machine design, and microcomputer interfacing and programming. They are integrated together, and therefore allow the design and test of embedded digital systems. The environment guides students' activities by delivering learning materials through specialized browsers. An extensive collection of learning materials is available. This paper includes an example of activity on a problem assignment. [ABSTRACT FROM AUTHOR]

Speed and position sensing in servo drives is an issue that is still not completely understood. Expressions like "accuracy" and "resolution" still get mixed up when engineers talk about encoders. These words, however, do describe different characteristics and should not be confused. The introduction of digital control has made this issue much more important for servo drive applications than before. This paper presents some general explanations of speed and motion sensing as well as different encoder technologies available today and their characteristics, particularly with respect to digitally controlled servo drives. [ABSTRACT FROM AUTHOR]

AVS-P7 is the recent mobile video coding standard of China. Currently, ARM cores are widely used in mobile applications because of their low power consumption. In this paper a scheme of the AVS-P7decoder real-time implementation on 32 bit MCU RISC processor ARM920T (S3C2440) is presented. The algorithm, redundancy, structure and memorp optimization methods to implement AVS-P7 real-time are discussed in detail. The experiment results demonstrate the success of our optimization techniques and the real-time implementation. The ADS, MCPS, PSNR and simulation results show that the proposed AVS-P7 decoder can decode the QVGA image sequence in real-time with high image quality and has low complexity and less memory requirement. AVS conformance test result confirms the proposed AVS-P7 decoder full compliance with AVS. The proposed AVS-P 7 decoder can be applied in many real-time applications like Mobile phone and IPTV in the third generation communication. [ABSTRACT FROM AUTHOR]

Effectiveness of previous SRAM leakage reduction techniques vary significantly as the leakage variation gets worse with process and temperature fluctuation. This paper proposes a simple circuit technique that adaptively trades off overhead energy for maximum leakage savings under severe leakage variations. The proposed run-time leakage reduction technique for on-die SRAM caches considers architectural access behavior to determine how often the SRAM blocks should enter a sleep mode. A self-decay circuit generates a periodic sleep pulse with an adaptive pulse period, which puts the SRAM array into a sleep mode more frequently at high leakage conditions (fast process, high temperature) and vice versa. An 0.18-μm 1.8-V 16-kbyte SRAM testchip shows 94.2% reduction in SRAM cell leakage at a performance penalty less than 2%. Measurement results also indicate that our proposed memory cell improves SRAM static noise margin by 25%. [ABSTRACT FROM AUTHOR]

In this paper, we study diagnosabilities of multiprocessor systems under two diagnosis models: the PMC model and the comparison model. In each model, we further consider two different diagnosis strategies: the precise diagnosis strategy proposed by Preparata et al. [28] and the pessimistic diagnosis strategy proposed by Friedman [18]. The main result of this paper is to determine diagnosabilities of regular networks with certain conditions, which include several widely used multiprocessor systems such as variants of hypercubes and many others. [ABSTRACT FROM AUTHOR]

The growing complexity of customizable single-chip multiprocessors is requiring communication resources that can only be provided by a highly-scalable communication infrastructure. This trend is exemplified by the growing number of Network-on-Chip (NoC) architectures that have been proposed recently for System-on-Chip (SoC) integration. Developing NoC-based systems tailored to a particular application domain is crucial for achieving high-performance, energy-efficient customized solutions. The effectiveness of this approach largely depends on the availability of an ad hoc design methodology that, starting from a high-level application specification, derives an optimized NoC configuration with respect to different design objectives and instantiates the selected application specific on-chip micronetwork. Automatic execution of these design steps is highly desirable to increase SoC design productivity. This paper illustrates a complete synthesis flow, called NetChip, for customized NoC architectures, that partitions the development work into major steps (topology mapping, selection, and generation) and provides proper tools for their automatic execution (SUNMAP, xpipescompiler). The entire flow leverages the flexibility of a fully reusable and scalable network components library called xpipes, consisting of highly-parameterizable network building blocks (network interlace, switches, switch-to-switch links) that are design-time tunable and composable to achieve arbitrary topologies and customized domain-specific NoC architectures. Several experimental case studies are presented in the paper, showing the powerful design space exploration capabilities of the proposed methodology and tools. [ABSTRACT FROM AUTHOR]

This paper presents a low-power encoding framework for embedded processor instruction buses. The encoder is capable of adjusting its encoding not only to suit applications but furthermore to suit different aspects of particular program execution. It achieves this by exploiting application-specific knowledge regarding program hot-spots, and thus identifies efficient instruction transformations so as to minimize the bit transitions on the instruction bus lines. Not only is the switching activity on the individual bus lines considered but so is the coupling activity across adjacent bus lines, a foremost contributor to the total power dissipation in the case of nanometer technologies. Low-power codes are utilized in a reprogrammable application specific manner. The restriction to two well-selected classes of simply computable, functional transformations delivers significant storage benefits and ease of reprogrammability, in the process obtaining significant power savings. The microarchitectural support enables reprogrammability of the encoding transformations in order to track code particularities effectively. Such reprogrammability is achieved by utilizing small tables that store relevant application information. The few transformations that result in optimal power reductions for each application hot-spot are selected by utilizing short indices stored into a table, which is accessed only once at the beginning of the transformed bit sequence. Extensive experimental results show significant power reductions ranging up to 80% for switching activity on bus lines and up to 70% when bus coupling effects are also considered. [ABSTRACT FROM AUTHOR]

In this paper, we present a methodology for the design of high-performance system-on-chip communication architectures. The approach is based on the addition of a layer of circuitry called the communication architecture tuner (CAT) layer around an existing communication architecture topology. The added layer provides a system with the capability of adapting to runtime variability in the communication needs of its constituent components. For example, more critical data may be handled differently, leading to lower communication latencies. The CAT associated with each component monitors its internal state, analyzes the communication transactions it generates, and "predicts" the relative importance of the transactions in terms of their impact on system-level performance metrics. It then configures the protocol parameters of the underlying communication architecture (e.g., priorities, burst modes, etc.) to best suit the system's changing communication needs. We illustrate the issues and tradeoffs involved in the design of CAT-based communication architectures, and present algorithms that automate the key steps. Experiments with example systems indicate that performance metrics (e.g., number of missed deadlines, average processing time) for systems with CAT-based communication architectures are significantly (sometimes over an order of magnitude) better than those with conventional communication architectures. [ABSTRACT FROM AUTHOR]

Computational grids are promising next-generation computing platforms for large-scale problems in science and engineering. Grids are large-scale computing systems composed of geographically distributed resources (computers, storage etc.) owned by self interested agents or organizations. These agents may manipulate the resource allocation algorithm in their own benefit, and their selfish behavior may lead to severe performance degradation and poor efficiency. In this paper, we investigate the problem of designing protocols for resource allocation involving selfish agents. Solving this kind of problems is the object of mechanism design theory. Using this theory, we design a truthful mechanism for solving the static load balancing problem in heterogeneous distributed systems. We prove that using the optimal allocation algorithm the output function admits a truthful payment scheme satisfying voluntary participation. We derive a protocol that implements our mechanism and present experiments to show its effectiveness. [ABSTRACT FROM AUTHOR]

Scheduling theory holds gnat promise as a means to a priori validate timing correctness of real-time applications. However, there currently exists a wide gap between scheduling theory and its implementation in operating system kernels running on specific hardware platforms. The implementation of any particular scheduling algorithm introduces overhead and blocking components which must be accounted for in the timing correctness validation process. This paper presents a methodology for incorporating the costs of scheduler implementation within the context of fixed priority scheduling algorithms. Both event-driven and timer-driven scheduling implementations are analyzed. We show that for the timer-driven scheduling implementations the selection of the timer interrupt rate can dramatically affect the schedulability of a task set, and we present a method for determining the optimal timer rate. We analyzed both randomly generated and two well-defined task sets and found that their schedulability can be significantly degraded by the implementation costs. Task sets that have ideal breakdown utilization over 90% may not even be schedulable when the implementation costs are considered. This work provides a first step toward bridging the gap between real-time scheduling theory and implementation realities. This gap must be bridged for any meaningful validation of timing correctness properties of real- time applications. [ABSTRACT FROM AUTHOR]

Scheduling and dispatching tools for high-performance computing (HPC) machines have the key role of mapping jobs to the available resources, trying to maximize performance and quality-of-service (QoS). Allocation and Scheduling in the general case are well-known NP-hard problems, forcing commercial schedulers to adopt greedy approaches to improve performance and QoS. Search-based approaches featuring the exploration of the solution space have seldom been employed in this setting, but mostly applied in off-line scenarios. In this paper, we present the first search-based approach to job allocation and scheduling for HPC machines, working in a production environment. The scheduler is based on Constraint Programming, an effective programming technique for optimization problems. The resulting scheduler is flexible, as it can be easily customized for dealing with heterogeneous resources, user-defined constraints and different metrics. We evaluate our solution both on virtual machines using synthetic workloads, and on the Eurora HPC with production workloads. Tests on a wide range of operating conditions show significant improvements in waitings and QoS in mid-tier HPC machines w.r.t state-of-the-art commercial rule-based dispatchers. Furthermore, we analyze the conditions under which our approach outperforms commercial approaches, to create a portfolio of scheduling algorithms that ensures robustness, flexibility and scalability. [ABSTRACT FROM AUTHOR]

This paper presents the hardware-in-the-loop (HIL) simulation of power electronic systems using a unique adaptive discretization technique based on the input of the system, where the coefficient matrices and system equations are changed while the simulation is running. The voltage-sourceconverter (VSC)-based HVDC system is used as a case study. Two z-transform-based discretization techniques, known as the step-invariant transformation (SIT) and the ramp-invariant transformation, and one of their derivative time-shifted SIT are applied for simulating the VSC-HVDC system. Discrete switching synchronization algorithms are used to accommodate the asynchronous events that take place in between two discrete simulation points. The HIL simulation is implemented using an off-the-shelf PC cluster interfaced with a digital controller. The simulator and the controller are connected through I/O ports, which facilitate the exchange of analog and digital signals. A 4-kW VSC-HVDC experimental setup is used to validate the simulation results, using the same digital controller as that in the HIL simulation to supply the necessary gate pulses for the experimental VSCs. A comparative study of the results obtained through offline, HIL simulation, and the experiment is presented. [ABSTRACT FROM AUTHOR]

Large-scale full-wave simulations are performed to investigate radar wave propagation inside buildings. In principle, a radar system combined with sophisticated numerical methods for inverse problems can be used to determine the internal structure of a building. The composition of the walls (cinder block, rebar) may effect the propagation of the radar waves in a complicated manner. In order to provide a benchmark solution of radar propagation in buildings, including the effects of cinder block and rebar, we performed large-scale full-wave simulations using a finite-element time domain (FETD) method. This particular FETD implementation is tuned for the special case of an orthogonal Cartesian mesh and hence resembles finite-difference time domain (FDTD) in accuracy and efficiency. The method was implemented on a general-purpose massively parallel computer. In this paper we briefly describe the radar propagation problem, the FETD implementation, and we present results of simulations that used over 10-billion elements. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present a design methodology that can be employed to develop computerized radiation monitoring systems for technology insertion into non-computerized human-machine systems. The methodology seeks to hybridize and exploit the benefits of several diverse disciplines including nuclear engineering, computer science, health physics, real-time system design, human-machine interaction, computer-human interface, and software engineering, in the realization of a Performance Support System (PSS). The focus for combining these disciplines is on the implementation of a specific application: The Iodine Monitoring and Advising System (IMAS), a computerized embedded system for the MNR (McMaster Nuclear Reactor) I125 production facility. IMAS uses radiation monitoring techniques and human factor concepts to provide nuclear reactor operators with a computerized monitoring alarm facility. The migration from a crude and inflexible spill detector to an intelligent performance support system is documented. [ABSTRACT FROM AUTHOR]

This paper describes an architecture model for data acquisition systems based on compact PCI platforms. The aim is to increase real-time data processing capabilities in experimental environments such as nuclear fusion devices (e.g., ITER). The model has these features: 1) Real-time data acquisition: the system has been provided with real-time capabilities, developing specific data acquisition kernel modules under Linux and RTAI, using COMEDI project drivers; 2) Multiprocessor PCI eXtensions for Instrumentation (PXI) Architecture: the model makes possible to add one or more processing cards (in nonsystem slots) to each standard PXI chassis. Several real-time software modules have been developed to allow the communication between the PXI controller and the processing cards. This way the system performance is not restricted to the PXI controller's own performance. This model provides scalability to the system, adding or removing processing cards; 3) Real-time acquired data distribution: with this model it is possible to define how to distribute, in real-time, the data from all acquired signals in the system among the processing cards and the PXI controller; and 4) Dynamic Data Processing: a software platform has been developed to allow users to dynamically manage their own data processing algorithms in the system. This means that users can start, stop, modify, and replace their data processing algorithms without disrupting the data acquisition process or the rest of the data processing algorithms. [ABSTRACT FROM AUTHOR]

The integral nonlinearity (INL) of analog-to-digital converters (ADCs) can be described by a behavioral error model expressed as one-dimensional image in the code domain. This image consists of low and high code frequency components which allow describing the ADC performance with a small number of parameters. This paper presents new methods for low code frequency and high code frequency testing. The identification of the low code frequency components is performed by multiharmonic sine fitting in the time domain. The high code frequency components are estimated in the statistical domain by a narrow band histogram test using a triangular stimulus signal. The performance of the proposed method is assessed for various ADC devices. [ABSTRACT FROM AUTHOR]

The growing demand of computer usage requires efficient ways of managing network traffic in order to avoid or at least limit the level of congestion in cases where increases in bandwidth are not desirable or possible. In this paper we developed and analyzed a generic Integrated Dynamic Congestion Control (IDCC) scheme for controlling traffic using information on the status of each queue in the network. The IDCC scheme is designed using nonlinear control theory based on a nonlinear model of the network that is generated using fluid flow considerations. The methodology used is general and independent of technology, as for example TCP/IP or ATM. We assume a differentiated-services network framework and formulate our control strategy in the same spirit as IP DiffServ for three types of services: Premium Service, Ordinary Service, and Best Effort Service. The three differentiated classes of traffic operate at each output port of a router/switch. An IDCC scheme is designed for each output port, and a simple to implement nonlinear controller, with proven performance, is designed and analyzed. Using analysis performance bounds are derived for provable controlled network behavior, as dictated by reference values of the desired or acceptable length of the associated queues. By tightly controlling each output port, the overall network performance is also expected to be tightly controlled. The IDCC methodology has been applied to an ATM network. We use OPNET simulations to demonstrate that the proposed control methodology achieves the desired behavior of the network, and possesses important attributes, as e.g., stable and robust behavior, high utilization with bounded delay and loss, together with good steady-state and transient behavior. [ABSTRACT FROM AUTHOR]

The scope of the Formal System Design (ForSyDe) methodology is high-level modeling and refinement of systems-on-a-chip and embedded systems. Starting with a formal specification model, that captures the functionality of the system at a high abstraction level, it provides formal design-transformation methods for a transparent refinement process of the system model into an implementation model that is optimized for synthesis. The main contribution of this paper is the ForSyDe modeling technique and the formal treatment of transformational design refinement We introduce process constructors, that cleanly separate the computation part of a process from the synchronization and communication part. We develop the characteristic function for each process type and use it to define semantic preserving and design decision transformations. These transformations are characterized by name, the format of the original process network, the transformed process network, and a design implication. The implication expresses the relation between original and transformed process network by means of the characteristic function. The objective of the refinement process is a model that can be implemented cost efficiently. To this end, process constructors and processes have a hardware and software interpretation which shall facilitate accurate performance and cost estimations. In a study of a digital equalizer example, we illustrate the modeling and refinement process and focus in particular on refinement of the clock domain, communication refinement, and resource sharing. [ABSTRACT FROM AUTHOR]

A number of software design methodologies (SDM's) have been developed and compared over the past two decades. An accurate comparison would aid in codifying and integrating these SDM's. However, existing comparisons are often based largely upon the experiences of practitioners and the intuitive understandings of the authors. Consequently, they tend to be subjective and affected by application domains. In this paper, we introduce a systematic and defined process (called CDM) for objectively comparing SDM's. We believe that using CDM will lead to detailed, traceable, and objective comparisons. CDM uses process modeling techniques to model SDM's, classify their components (e.g., guidelines and notations), and analyze their procedural aspects. Modeling the SDM's entails decomposing their methods into components and analyzing the structure and functioning of the components. The classification of the components illustrates which components address similar design issues and/or have similar structures. Similar components then may be further modeled to aid in understanding more precisely their similarities and differences. The models of the SDM's are also used as the bases for conjectures and analyses about the differences between the SDM's. This paper describes three experiments that we carried out in evaluating CDM. The first uses CDM to compare JSD and Booch's Object Oriented Design (BOOD). The second uses CDM to compare two other pairs of SDM's. The last compares some of our comparisons with other comparisons done in the past using different approaches. The results of these experiments demonstrate that process modeling is valuable as a powerful tool in analysis of software development approaches. [ABSTRACT FROM AUTHOR]

In this paper we examine a system structure and protocols to improve the performance of a distributed transaction processing system when there is some regional locality of data reference. Several transaction processing applications such as reservation systems, insurance, and banking belong to this category. While maintaining a distributed computer system at each region, a central computer system is introduced with a replication of all databases at the distributed sites. It can provide the advantage of distributed systems for transactions that refer principally to local data, and also can, provide the advantage of centralized systems for transactions accessing nonlocal data. Specialized protocols can be designed to keep the copies at the distributed and centralized systems consistent without incurring the overhead and delay of generalized protocols for fully replicated databases. In this paper we study the advantage achievable through this system structure and the trade-offs between protocols for concurrency and coherency control of the duplicate copies of the databases. An approximate analytic model is employed to estimate the system performance. It is found that the performance is indeed sensitive to the protocol and substantial performance improvement can be obtained as compared with distributed systems. The protocol design factors considered include the approach for intersite concurrency control (optimistic versus pessimistic), resolution of aborts due to intersite conflict, and choice of the master/primary site of the dual copies (distributed site versus central site). Among the protocols considered, the most robust one uses an optimistic protocol for intersite control with the distributed site as the master site, allows a locally running transaction to commit without any communication with the central site, and balances transaction aborts between transactions running at the central site and distributed sites. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of modeling a system's reliability and availability with respect to the various classes of faults (physical and design, internal and external) which may affect the service delivered to its users. Hardware and software models are currently exceptions in spite of the users' requirements; these requirements are expressed in terms of failures independently of their sources; i.e. the various classes of faults. The causes of this situation are analyzed; it is shown that there is no theoretical impediment to deriving such models, and that the classical reliability theory can be generalized in order to cover both hardware and software viewpoints that are X-Ware. After the introduction, which summarizes the current state of the art with regard to the dependability requirements from the users' viewpoint, the body of the paper is composed of two sections. Section H is devoted to system behavior up to failure; it focuses on failure rate and reliability, considering in turn atomic (or single component) systems and systems made out of components. Section III deals with the sequence of failures when considering restoration actions consecutive to maintenance; failure intensity, reliability, and availability are derived for various forms of maintenance. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient incremental LL(1) parsing algorithm for use in language-based editors that use the structure recognition approach. It is designed to parse user input at intervals of very small granularity and to limit the amount of incremental parsing needed when changes are made internal to the editing buffer. The algorithm uses the editing focus as a guide in restricting parsing. It has been implemented in the Fred language-based editor. [ABSTRACT FROM AUTHOR]

We have noticed two problems with viewing a process as a sequence of events: The first problem is the complete loss of information about potential intra-process concurrency for both sequential and distributed computations, and partial loss of information about potential inter-process concurrency for distributed computations. The second problem is that the resulting reasoning framework does not lend itself to refinement (from sequential computing or a given set of distributed processes) to a preferable set of distributed processes. We argue that it is more natural to view a computation, either distributed or sequential, as a partially ordered set of events. Doing so leads to a view, called passive-space and time view, which we propose in this paper. In the proposed view, a point in space is a passive entity which does not order events that occur at it, and the order is determined by the interaction among the events. We define a relation, "Affects", between pairs of events, which captures the partial order on events. To aid users of the relation "Affects" in developing algorithms, we define vector clocks, that are global logical clocks, so that the relation "Affects", and hence all potential concurrency, between events can be identified from their timestamps assigned. Since this research is motivated by the need to solve practical problems, we define passive-space and time view such that a user has control, in two ways, over the costs involved. First, a process designer may choose any granularity of events and choose any mechanism for determining partial order among events on the process. Second, a user may choose a vector clock such that the extent of potential intra-process concurrency identified depends on the costs associated with the identification. We give vector clocks which trade cost incurred and concurrency identification. We compare the proposed view with the space and time view. Finally, we give a scheme for reducing the cost of communicating timestamps. [ABSTRACT FROM AUTHOR]

The Xerox Star (8010) is an integrated office workstation. Its software is written in an object-oriented style. Often, different applications will impose slightly different requirements on nominally similar objects which they use. Customization of object definitions for different applications is achieved by attaching modifiers called traits to pre-existing object definitions. This paper describes the approach and recounts our experience with traits. [ABSTRACT FROM AUTHOR]

This article presents a study regarding the increasing complexity of computer networks calls for developing new models for their simulation. It examines a system for modeling and simulation of computer networks based on cellular automata. It discusses that system reliability evaluation, algorithms for connectivity evaluation, and shortest path computation in a computer network have been implemented. The system was developed and designed as an interactive tool that offers automated modeling with the assistance of a dynamic and user-friendly graphical environment.

This paper describes the first algorithm that calculates accurate interprocedural defuse associations in C software systems. Our algorithm accounts for program-point-specific pointer-induced aliases, though it is currently limited to programs using a single level of indirection. We prove the NP-hardness of the interprocedural reaching definitions problem and describe the approximations made by our polynomial-time algorithm. Initial empirical results are also presented. [ABSTRACT FROM AUTHOR]

This paper presents a modeling approach based on stochastic Petri nets to estimate the reliability and availability of programs in a distributed computing system environment. In this environment, successful execution of programs is conditioned on the successful access of related files distributed throughout the system. The use of stochastic Petri nets is demonstrated by extending a basic reliability model to account for repair actions when faults occur. To this end, two possible models are discussed: the global repair model, which assumes a centralized repair team that restores the system to its original status when a failure state is reached, and the local repair model, which assumes that repairs are localized to the node where they occur. The former model is useful in evaluating the availability of programs (or the availability of the hardware support) subject to hardware faults that are repaired globally; therefore, the programs of interest can be interrupted. On the other hand, the latter model can be used to evaluate program reliability in the presence of hardware faults subject to repair, without interrupting the normal operation of the system. [ABSTRACT FROM AUTHOR]

Mutation testing is a fault-based technique for unit-level software testing. Weak mutation was proposed as a way to reduce the expense of mutation testing. Unfortunately, weak mutation is also expected to provide a weaker test of the software than mutation testing does. This paper presents results from an implementation of weak mutation, which we used to evaluate the effectiveness versus the efficiency of weak mutation. Additionally, we examined several options in an attempt to find the most appropriate way to implement weak mutation. Our results indicate that weak mutation can be applied in a manner that is almost as effective as mutation testing, and with significant computational savings. [ABSTRACT FROM AUTHOR]

Petri nets have been proposed as a promising tool for modeling and analyzing concurrent-software systems such as Ada programs and communication protocol software. Among analysis techniques available for Petri nets, the most general approach is to generate all possible states (markings) of the system in a form of a so-called reachability graph. This conventional reachability graph approach is inefficient or intractable, however, even for a bounded Petri net, due to state explosion in many practical applications. To cope with this problem, this paper proposes a method for constructing a hierarchically organized state space called the hierarchical reachabilty graph (HRG). Using the HRG, we obtain necessary and sufficient conditions for reachability and deadlock, as well as algorithms to test whether a given state or marking is reachable from the initial state and whether there is a deadlock state (a state with no successor states). [ABSTRACT FROM AUTHOR]

This paper presents a family of strategies for automatically generating test data for any implementation intended to satisfy a given specification that is a Boolean formula. The fault detection effectiveness of these strategies is investigated both analytically and empirically, and the costs, assessed in terms of test set size, are compared. [ABSTRACT FROM AUTHOR]

Remote procedure call (RPC) is the most popular paradigm used today to build distributed systems and applications. As a consequence, the term "RPC" has grown to include a range of vastly different protocols above the transport layer. A resulting problem is that programs often use different RPC protocols, cannot be interconnected directly, and building a solution for each case in a large heterogeneous environment is prohibitively expensive. In this paper, we describe the design of a system that can synthesize programs (RPC agents) to accommodate RPC heterogeneities. Because of its synthesis capability, our system also facilitates the design and implementation of new RPC protocols through rapid prototyping. We have built a prototype system to validate the design and to estimate the agent development costs and cross-RPC performance. Our evaluation shows that our synthesis approach provides a more general solution than existing approaches do, and with lower software development and maintenance costs, while maintaining reasonable cross-RPC performance. [ABSTRACT FROM AUTHOR]

Measurement of software development productivity is needed in order to control software costs, but it is discouragingly labor-intensive and expensive. Computer-aided software engineering (CASE) technologies-especially repository-based, integrated CASE-have the potential to support the automation of this measurement. In this paper, we discuss the conceptual basis for the development of automated analyzers for function point and software reuse measurement for object-based CASE. Both analyzers take advantage of the existence of a representation of the application system that is stored within an object repository, and that contains the necessary information about the application system. We also discuss metrics for software reuse measurement, including reuse leverage, reuse value, and reuse classification that are motivated by managerial requirements and the efforts, within industry and the IEEE, to standardize measurement. The functionality and the analytical capabilities of state-of-the-art automated software metrics analyzers are illustrated in the context of an investment banking industry application that is similar to systems deployed at the New York City-based investment bank where these tools were developed and tested. [ABSTRACT FROM AUTHOR]

Measurement of software reliability by life testing involves executing the software on large numbers of test cases and recording the results. The number of failures observed is used to bound the failure probability even if the number of failures observed is zero. Typical analyses assume that all failures that occur are observed, but, in practice, failures occur without being observed. In this paper, we examine the effect of imperfect error detection, i.e., the situation in which a failure of the software may not be observed. If a conventional analysis associated with life testing is used, the confidence in the bound on the failure probability is optimistic. Our results show that imperfect error detection does not necessarily limit the ability of life testing to bound the probability of failure to the very low values required in critical systems. However, we show that the confidence level associated with a bound on failure probability cannot necessarily be made as high as desired, unless very strong assumptions are made about the error detection mechanism. Such assumptions are unlikely to be met in practice, and so life testing is likely to be useful only for situations in which very high confidence levels are not required. [ABSTRACT FROM AUTHOR]