Older adult care technologies are increasingly explored to support the independent living of older adults by monitoring their abnormal activities and informing caregivers to provide intervention if necessary. However, the adoption of these technologies remains challenging due to several factors (e.g. lack of usability). In this work, we present a human-centered, intelligent system for older adult care. Our proposed designs of the system were created based on the findings from a focus group session with caregivers. This system monitors the abnormal activities of an older adult using wireless motion sensors and machine learning models. In addition, unlike previous work that only notifies an outcome of activity recognition and abnormal detection models to a caregiver, the system supports interactive dialogue responses to explain the abnormal activities of an older adult to a caregiver and allow the caregiver to elicit additional information about the older adult and the older adult to proactively share his/her status with the caregiver for an adequate intervention.

Artificial intelligence (AI) and machine learning (ML) algorithms are increasingly being explored to support various decision-making tasks in health (e.g. rehabilitation assessment). However, the development of such AI/ML-based decision support systems is challenging due to the expensive process to collect an annotated dataset. In this paper, we describe the development process of a human-AI collaborative, clinical decision support system that augments an ML model with a rule-based (RB) model from domain experts. We conducted its empirical evaluation in the context of assessing physical stroke rehabilitation with the dataset of three exercises from 15 post-stroke survivors and therapists. Our results bring new insights on the efficient development and annotations of a decision support system: when an annotated dataset is not available initially, the RB model can be used to assess post-stroke survivor’s quality of motion and identify samples with low confidence scores to support efficient annotations for training an ML model. Specifically, our system requires only 22 - 33% of annotations from therapists to train an ML model that achieves equally good performance with an ML model with all annotations from a therapist. Our work discusses the values of a human-AI collaborative approach for effectively collecting an annotated dataset and supporting a complex decision-making task.

Advances in artificial intelligence (AI) have made it increasingly applicable to supplement expert’s decision-making in the form of a decision support system on various tasks. For instance, an AI-based system can provide therapists quantitative analysis on patient’s status to improve practices of rehabilitation assessment. However, there is limited knowledge on the potential of these systems. In this paper, we present the development and evaluation of an interactive AI-based system that supports collaborative decision making with therapists for rehabilitation assessment. This system automatically identifies salient features of assessment to generate patient-specific analysis for therapists, and tunes with their feedback. In two evaluations with therapists, we found that our system supports therapists significantly higher agreement on assessment (0.71 average F1-score) than a traditional system without analysis (0.66 average F1-score, p < 0.05). After tuning with therapist’s feedback, our system significantly improves its performance from 0.8377 to 0.9116 average F1-scores (p < 0.01). This work discusses the potential of a human-AI collaborative system to support more accurate decision making while learning from each other’s strengths.

A robotic exercise coaching system requires the capability of automatically assessing a patient's exercise to interact with a patient and generate corrective feedback. However, even if patients have various physical conditions, most prior work on robotic exercise coaching systems has utilized generic, pre-defined feedback.This paper presents an interactive approach that combines machine learning and rule-based models to automatically assess a patient's rehabilitation exercise and tunes with patient's data to generate personalized corrective feedback. To generate feedback when an erroneous motion occurs, our approach applies an ensemble voting method that leverages predictions from multiple frames for frame-level assessment. According to the evaluation with the dataset of three stroke rehabilitation exercises from 15 post-stroke subjects, our interactive approach with an ensemble voting method supports more accurate frame-level assessment (p <; 0.01), but also can be tuned with held-out user's unaffected motions to significantly improve the performance of assessment from 0.7447 to 0.8235 average F1-scores over all exercises (p <; 0.01). This paper discusses the value of an interactive approach with an ensemble voting method for personalized interaction of a robotic exercise coaching system.

Technology-assisted systems to monitor and assess rehabilitation exercises have an opportunity of enhancing rehabilitation practices by automatically collecting patient's quantitative performance data. However, even if a complex algorithm (e.g. Neural Network) is applied, it is still challenging to develop such a system due to patients with various physical conditions. The system with a complex algorithm is limited to be a black-box system that cannot provide explanations on its predictions. To address these challenges, this paper presents a hybrid model that integrates a machine learning (ML) model with a rule-based (RB) model as an explainable artificial intelligence (AI) technique for quantitative assessment of stroke rehabilitation exercises. For evaluation, we collected therapist's knowledge on assessment as 15 rules from interviews with therapists and the dataset of three upper-limb stroke rehabilitation exercises from 15 post-stroke and 11 healthy subjects using a Kinect sensor. Experimental results show that a hybrid model can achieve comparable performance with a ML model using Neural Network, but also provide explanations on a model prediction with a RB model. The results indicate the potential of a hybrid model as an explainable AI technique to support the interpretation of a model and fine-tune a model with user-specific rules for personalization.

Clinical decision support systems have the potential to improve work flows of experts in practice (e.g. therapist's evidence-based rehabilitation assessment). However, the adoption of these systems is challenging, and the gains of these systems have not fully demonstrated yet. In this paper, we identified the needs of therapists to assess patient's functional abilities (e.g. alternative perspectives with quantitative information on patient's exercise motions). As a result, we co-designed and developed an intelligent decision support system that automatically identifies salient features of assessment using reinforcement learning to assess the quality of motion and generate patient-specific analysis. We evaluated this system with seven therapists using the dataset from 15 patients performing three exercises. The results show that therapists have higher usage intent on our system than a traditional system without patient-specific analysis ($p < 0.05$). While presenting richer information ($p < 0.10$), our system significantly reduces therapists' effort on assessment ($p < 0.10$) and improves their agreement on assessment from 0.66 to 0.71 F1-scores ($p < 0.01$). This work discusses the importance of human centered design and development of a machine learning-based decision support system that presents contextually relevant information and salient explanations on its prediction for better adoption in practice.

Due to the limited number of therapists, task-oriented exercises are often prescribed for post-stroke survivors as in-home rehabilitation. During in-home rehabilitation, a patient may become unmotivated or confused to comply prescriptions without the feedback of a therapist. To address this challenge, this paper proposes an automated method that can achieve not only qualitative, but also quantitative assessment of stroke rehabilitation exercises. Specifically, we explored a threshold model that utilizes the outputs of binary classifiers to quantify the correctness of a movements into a performance score. We collected movements of 11 healthy subjects and 15 post-stroke survivors using a Kinect sensor and ground truth scores from primary and secondary therapists. The proposed method achieves the following agreement with the primary therapist: 0.8436, 0.8264, and 0.7976 F1-scores on three task-oriented exercises. Experimental results show that our approach performs equally well or better than multi-class classification, regression, or the evaluation of the secondary therapist. Furthermore, we found a strong correlation (R2 = 0.95) between the sum of computed exercise scores and the Fugl-Meyer Assessment scores, clinically validated motor impairment index of post-stroke survivors. Our results demonstrate a feasibility of automatically assessing stroke rehabilitation exercises with the decent agreement levels and clinical relevance.

Accurate real-time depth camera-based tracking of limbs, fingers and faces would be of great use to the field of Sign Language Recognition (SLR). While aspects of depth-based tracking have been applied to SLR, technological limitations have previously forced trade-offs between the resolution necessary to track finger positions and the field of view necessary to track the signer's body. Only recently, with improvements in cameras and computing power, have algorithms been developed which boast the capability of maintaining accurate finger tracking over an appropriately sized volume of space. In this paper, we employ the publicly available Sphere-Mesh [1] hand tracking algorithm to collect and recognize ASL handshapes. In doing so, we demonstrate recognition rates comparable to other state of the art handshape classifiers using simple naíve Bayesian classifiers that can run in real-time.

Though tactile maps have been shown to be useful tools for visually impaired individuals, their availability has been limited by manufacturing and design costs. In this paper, we present a system that uses 3D printing to (1) make tactile maps more affordable to produce, (2) allow visually impaired individuals to independently design and customize maps, and (3) provide interactivity using widely available mobile devices. Our system consists of three parts: a web interface, a modeling algorithm, and an interactive touchscreen application. Our web interface, hosted at www.tactilemaps.net, allows visually impaired individuals to create maps of any location on the globe while specifying (1) what features to map, (2) how the features should be represented by textures, and (3) where to place markers and labels. Our modeling algorithm accommodates user specifications to create map models with (1) multiple layers of continuously varying textures and (2) markers of various geometric shapes or braille characters. Our interactive application uses a novel approach to 3D printing tactile maps using conductive filament to provide touchscreen overlays that allow users to dynamically interact with the maps on a wide range of mobile devices. This paper details the implementation of our system. We also present findings from a user study validating the usability of our mapping interface and the utility of the maps produced. Finally, we discuss the limitations of our current implementation and the plans we have to improve our system based on feedback from our user study and additional interviews.

It is well established that delays in system response time negatively impact productivity, error rates and user satisfaction. What is less clear is the degree to which these effects deter users from engaging with a system. Usability guidelines provide rough response time targets for minimizing these effects across various types of interactions. However, developers faced with technical limitations or cost constraints that prevent them from meeting such targets are given no data with which to estimate the impact that system response delays will have on user engagement. In this work, we demonstrate a methodology for using crowd sourcing platforms to examine (1) the relative impacts of different delay types and (2) the effects of marginal changes in system response times. We compare two common network delay types, those caused by limited bandwidth (increased download times) and those caused by network latency (lag in responsiveness), and present how these delays reduce engagement in the context of a crowd sourced image classification task. Furthermore, we model how financial incentives interact with system response delays to impact user engagement. Finally, we show how such models can be used to optimize the cost of system design choices.

This paper presents a method for filtering sinusoidal noise with a variable bandwidth filter that is capable of tracking a sinusoid's drifting frequency. The method, which is based on the adaptive noise canceling (ANC) technique, will be referred to here as the adaptive sinusoid canceler (ASC). The ASC eliminates sinusoidal contamination by tracking its frequency and achieving a narrower bandwidth than typical notch filters. The detected frequency is used to digitally generate an internal reference instead of relying on an external one as ANC filters typically do. The filter's bandwidth adjusts to achieve faster and more accurate convergence. In this paper, the focus of the discussion and the data is physiological signals, specifically electrocorticographic (ECoG) neural data contaminated with power line noise, but the presented technique could be applicable to other recordings as well. On simulated data, the ASC was able to reliably track the noise's frequency, properly adjust its bandwidth, and outperform comparative methods including standard notch filters and an adaptive line enhancer. These results were reinforced by visual results obtained from real ECoG data. The ASC showed that it could be an effective method for increasing signal to noise ratio in the presence of drifting sinusoidal noise, which is of significant interest for biomedical applications.

Tactile maps are useful, but not commonly available, tools for providing visually impaired individuals with knowledge about their environment. We have developed a web tool to allow visually impaired users to specify locations and customize 3D map models for production with 3D printers. Our tool uses available online map data and encodes features such as roads and waterways into 3D-printable tactile features. We present a preliminary overview of our web interface and tactile map-generating software with a focus on the design choices that were informed by our pilot studies. We will also discuss additional findings from our focus group interviews and future plans for this work.

In mobile computing, varying access to resources makes it difficult for developers to ensure that satisfactory system response times will be maintained at all times. Wearable physiological sensors offer a way to dynamically detect user frustration in response to increased system delays. However, most prior efforts have focused on binary classifiers designed to detect the presence or absence of a task-specific stimulus. In this paper, we make two contributions. Our first contribution is in identifying the use of variable length system response delays, a universal and task-independent feature of computing, as a stimulus for driving different levels of frustration. By doing so, we are able to make our second and primary contribution, which is the development of models that predict multiple levels of user frustration from psycho-physiological responses caused by system response delays. We investigate how incorporating different sensor features, application settings, and timing constraints impact the performance of our models. We demonstrate that our models of physiological responses can be used to classify five levels of frustration in near real-time with over 80% accuracy, which is comparable to the accuracy of binary classifiers.

The proliferation of wearable sensor platforms (Jawbone, Fit Bit, Smart Watches) and sensor rich Smart Phones have produced a torrent of real time sensed signals that is interpreted to produce data (e.g. Sleep quality, step count). Often the volume of this data overwhelms users. Visualization is an effective way to summarize data and observe trends. This is especially valuable when someone, such as a doctor, has to monitor a large number of people. When a human expert is not available, a Virtual Coach can provide feedback and guidance. Virtual coaches can recognize actions, correct errors, recognize emotions, and provide motivation. We will illustrate how these two technologies can effectively convert data into action in dozens of real applications. Examples include monitoring physiological parameters, identifying trends, providing guidance, correcting errors, and motivating. We will conclude with a projection of future Virtual Coaches.

Physical therapists could make better treatment decisions if they had accurate patient home exercise data but today this information is only available from patient self-report. A more accurate source of data could be gained from wearable computing designed for physical therapy exercise support. Existing systems have been tested in the lab but we have little information about issues they may face in home settings. We designed a technology probe, SenseCap, and deployed it for seven days in ten physical therapy patients' homes. SenseCap is a wearable physical therapy support system that gathers patient exercise compliance and performance data and summarizes the data in charts on an iPad Dashboard for physical therapists to view when patients return to the clinic. In this paper, we present the results of our deployment, show in-home patient exercise data gathered by the probe, and make design recommendations based on patient and physical therapist responses.

The paper presents an audio-based emotion recognition system that is able to classify emotions as anger, fear, happy, neutral, sadness or disgust in real time. We use the virtual coach as an application example of how emotion recognition can be used to modulate intelligent systems' behavior. A novel minimum-error feature removal mechanism to reduce bandwidth and increase accuracy of our emotion recognition system has been introduced. A two-stage hierarchical classification approach along with a One-Against-All (OAA) framework are used. We obtained an average accuracy of 82.07% using the OAA approach, and 87.70% with a two-stage hierarchical approach, by pruning the feature set and using Support Vector Machines (SVMs) for classification.

We compared two privacy configuration styles for specifying rules for social sharing one's past locations. Our findings suggest that location-sharing applications (LSAs) which support varying levels of location granularities are associated with sharing rules that are less convoluted, are less likely to be negatively phrased, and can lead to more open sharing; users are also more comfortable with these rules. These findings can help inform LSA privacy designs.

The combination of sensors, perception algorithms, and mobile computing enables situationally aware systems that provide proactive assistance. This paper outlines the basic components of a virtual coach with illustrations in five applications ranging from reminders to advice to opportunities for personal reflection.

With over 13.3 million children living below poverty line in the United States, there is a pressing need for engaging HCI research with children at the socio-economic margins. Drawing from design studio culture and art therapy literature, we explore wearable computing as a creative and tangible medium (similar to markers, paints, clays, etc.) for motivating 'at-risk' children in hands-on making and expressive instantiation of ideas. Working with a local outreach organization for 'at-risk' middle school girls, we conducted five weekly workshops during which participants ideated, designed and implemented personal wearable computing projects. These sessions inspired participants (age 10-12) who tend to be uninterested and uncooperative in educational activities to complete interactive projects and engage with workshop volunteers as mentors and peers. We present the challenges, merits and outcomes of our approach, proposing wearable computing as a healing outlet and a mentoring strategy for at-risk children.

While past work has looked extensively at how to design privacy configuration UIs for sharing current location, there has not yet been work done to examine how visual representations of historical locations can influence end-user privacy. We present results for a study examining three visualization types (text-, map-, and time-based) for social sharing of past locations. Our results reveal that there are important design implications for location sharing applications, as certain visual elements led to more privacy concerns and inaccurate perceptions of privacy control.

The popularity of micro-blogging has made general-purpose information sharing a pervasive phenomenon. This trend is now impacting location sharing applications (LSAs) such that users are sharing their location data with a much wider and more diverse audience. In this paper, we describe this as social-driven sharing, distinguishing it from past examples of what we refer to as purpose-driven location sharing. We explore the differences between these two types of sharing by conducting a comparative two-week study with nine participants. We found significant differences in terms of users' decisions about what location information to share, their privacy concerns, and how privacy-preserving their disclosures were. Based on these results, we provide design implications for future LSAs.

RADAR is a multiagent system with a mixed-initiative user interface designed to help office workers cope with email overload. RADAR agents observe experts to learn models of their strategies and then use the models to assist other people who are working on similar tasks. The agents' assistance helps a person to transition from the normal email-centric workflow to a more efficient task-centric workflow. The Email Classifier learns to identify tasks contained within emails and then inspects new emails for similar tasks. A novel task-management user interface displays the found tasks in a to-do list, which has integrated support for performing the tasks. The Multitask Coordination Assistant learns a model of the order in which experts perform tasks and then suggests a schedule to other people who are working on similar tasks. A novel Progress Bar displays the suggested schedule of incomplete tasks as well as the completed tasks. A large evaluation demonstrated that novice users confronted with an email overload test performed significantly better (a 37% better overall score with a factor of four fewer errors) when assisted by the RADAR agents.

Context-aware computing describes the situation where a wearable/mobile computer is aware of its user's state and surroundings and modifies its behavior based on this information. We designed, implemented, and evaluated a wearable system which can learn context-dependent personal preferences by identifying individual user states and observing how the user interacts with the system in these states. This learning occurs online and does not require external supervision. The system relies on techniques from machine learning and statistical analysis. A case study integrates the approach in a context-aware mobile phone. The results indicate that the method is able to create a meaningful user context model while only requiring data from comfortable wearable sensor devices.

We present an incentive compatible mechanism for negotiated power management in mobile ad hoc networks. Using power measurements of real wireless interfaces, we show that a cost model for this environment must account for energy complementarity between overlapping traffic flows. We introduce the combinatorial exchange, a generalization of the route selection method already implemented in source routing networks, as a model which accounts for overlap. No previous mechanism for networks is incentive compatible in the power managing environment. We have developed a distributed procedure for exchange-based route selection, which we evaluate using realistic simulation. Our results show significant improvements in energy consumption variability, route setup latency, and application message delivery latency.

Embedded systems encompass a wide range of applications, technologies, and disciplines, necessitating a broad approach to education. We describe embedded system coursework during the first 4 years of university education (the U.S. undergraduate level). Embedded application curriculum areas include: small and single-microcontroller applications, control systems, distributed embedded control, system-on-chip, networking, embedded PCs, critical systems, robotics, computer peripherals, wireless data systems, signal processing, and command and control. Additional cross-cutting skills that are important to embedded system designers include: security, dependability, energy-aware computing, software/systems engineering, real-time computing, and human--computer interaction. We describe lessons learned from teaching courses in many of these areas, as well as general skills taught and approaches used, including a heavy emphasis on course projects to teach system skills.

Experimental research in dependability has evolved over the past 30 years accompanied by dramatic changes in the computing industry. To understand the magnitude and nature of this evolution, this paper analyzes industrial trends, namely: 1) shifting error sources, 2) explosive complexity, and 3) global volume. Under each-of these trends, the paper explores research technologies that are applicable either to the finished product or artifact, and the processes that are used to produce products. The study gives a framework to not only reflect on the research of the past, but also project the needs of the future.

This paper describes a design process for custom wearable systems produced in an academic setting. A set of 245 wearable design defects from two distinct periods separated by six years in time is presented. These data identify aspects of the process which require significant developer effort. We show this effort using several views of the data, including time spent, design region affected, and distribution under an Orthogonal Defect Classification scheme. A comparison of defect attribute distributions across the two separate design periods is given. The results show that growing interoperability requirements are increasing design complexity, and inducing greater debugging effort. In addition, the combination of increasing pin counts and decreasing physical dimensions produce a higher rate of critical defects (i.e., those that require major physical modifications before debugging can continue). Finally, although the nature of the defects themselves has changed with time, the mechanisms used to discover defects have remained relatively constant.

This paper describes nonideal properties of batteries and how these properties may impact power-performance trade offs in wearable computing. The first part of the paper details the characteristics of an ideal battery and how these characteristics are used in sizing batteries and estimating discharge times. Typical nonideal characteristics and the regions of operation where they occur are described. The paper then presents results from a first-principles, variable-load battery model, showing likely areas for exploiting battery behavior in mobile computing. The major result is that, when battery behavior is nonideal, lowering the average power or the energy per operation may not increase the amount of computation that can be completed in a battery life.

This paper introduces a systematic approach to power awareness in mobile, handheld computers. It describes experimental evaluations of several techniques for improving the energy efficiency of a system, ranging from the network level down to the physical level of the battery. At the network level, a new routing method based upon the power consumed by the network subsystem is shown to improve power consumption by 15% on average and to reduce latency by 75% over methods that consider only the transmitted power. At the boundary between the network and the processor levels, the paper presents the problem of local versus remote processing and derives a figure of merit for determining whether a computation should be completed locally or remotely, one that involves the relative performance of the local and remote system, the transmission bandwidth and power consumption, and the network congestion. At the processor level, the main memory bandwidth is shown to have a significant effect on the relationship between performance and CPU frequency, which in turn determines the energy savings of dynamic CPU speed-setting. The results show that accounting for the main memory bandwidth using Amdahl's law permits the performance speed-up and peak power versus the CPU frequency to be estimated to within 5%. The paper concludes with a technique for mitigating the loss of battery energy capacity with large peak currents, showing an improvement of up to 10% in battery life, albeit at some cost to the size and weight of the system.

Summary form only given. Rapid advances in mobile computing and wireless communication present an opportunity for fundamental changes in engineering education, particularly for team based courses in which collaborative learning is the dominant learning mode. Through an iterative, bootstrapping approach, we study how students use computer-based collaboration tools to design a next generation of collaboration tools. Our suite of collaboration tools is called Handy Andy, which is based on the Andrew wireless network at Carnegie Mellon. Our goal is to facilitate computer-based collaborative learning in project-based design courses by developing collaboration tools for mobile computers.

This paper focuses on the design and implementation of a companion contextual car driver interface that proactively assists the driver in managing information and communication. The prototype combines a smart car environment and driver state monitoring, incorporating a wide range of input-output modalities and a display hierarchy. Intelligent agents link information from many contexts, such as location and schedule, and transparently learn from the driver, interacting with the driver only when it is necessary.

Before using CORBA (Common Object Request Broker Architecture) applications in mission-critical scenarios, it is important to understand the robustness of the Object Request Broker (ORB) being used, which forms the platform for CORBA applications. We have extended the Ballista software testing technique to test the exception-handling robustness of C++ ORB client-side application interfaces, and have tested two major versions of three ORB implementations on two operating systems, yielding robustness failure rates ranging from 26% to 42%. To improve ORB robustness, we also propose a probing method to harden object and pseudo-object related data types against exceptional inputs. Using these probes on omniORB 2.8 has proven to be effective in eliminating some cases of robustness failures found during testing. These results suggest that CORBA implementations currently have significant robustness vulnerabilities, but that some important classes of problems can be overcome with better exception-handling approaches.

This paper explores the system-level power-performance tradeoffs of dynamically varying CPU speed. Previous work in CPU speed-setting considered only the power of the CPU and only CPUs that vary supply voltage with frequency. This work takes a broader approach, considering total system power, battery capacity, and main memory bandwidth. The results, which are up to a factor of four less than ideal, show that all three must be considered when setting the CPU speed.

The purpose of this paper is to report the power and performance of an application on a real system as the CPU frequency varies.Previous work in CPU speed-setting considered only the power of the CPU and only CPU's that vary supply voltage with frequency.This work takes a broader approach, considering total system power, battery capacity and main memory bandwidth.The results, which are up to a factor of four less than ideal, show that all three must be considered when setting the CPU speed, whether the speed is fixed at a single value or varied dynamically during operation.

The problem of maximizing system utility by allocating a single finite resource to satisfy discrete Quality of Service (QoS) requirements of multiple applications along multiple QoS dimensions was studied previously. In this paper we consider the more complex problem of apportioning multiple finite resources to satisfy the QoS needs of multiple applications along multiple QoS dimensions. In other words, each application, such as video-conferencing, needs multiple resources to satisfy its QoS requirements. We evaluate and compare three strategies to solve this provably NP-hard problem. We show that dynamic programming and mixed integer programming compute optimal solutions to this problem but exhibit very long running times. We then adapt the mixed integer programming problem to yield near-optimal results with smaller running times. Finally, we present an approximation algorithm based on a local search technique that is less than 5% away from the optimal solution but which is more than two orders of magnitude faster. Perhaps more significantly, the local search technique turns out to be very scalable and robust as the number of resources required by each application increases.

The QoS based Resource Allocation Model (Q-RAM) proposed by R. Rajkumar et al. (1998) presented an analytical approach for satisfying multiple quality of service dimensions in a resource constrained environment. Using this model, available system resources can be apportioned across multiple applications such that the net utility that accrues to the end users of those applications is maximized. We present several practical solutions to allocation problems that were beyond the limited scope of Q-RAM. We show that the Q-RAM problem of finding the optimal resource allocation to satisfy multiple QoS dimensions is NP hard. We then present a polynomial solution for this resource allocation problem which yields a solution within a provably fixed and short distance from the optimal allocation. Secondly, Q-RAM dealt mainly with the problem of apportioning a single resource to satisfy multiple QoS dimensions. We study the converse problem of apportioning multiple resources to satisfy a single QoS dimension. In practice, this problem becomes complicated, since a single QoS dimension perceived by the user can be satisfied using different combinations of available resources. We show that this problem can be formulated as a mixed integer programming problem that can be solved efficiently to yield an optimal resource allocation. We also present the run times of these optimizations to illustrate how these solutions can be applied in practice. A good understanding of these solutions will yield insights into the general problem of apportioning multiple resources to satisfy simultaneously multiple QoS dimensions of multiple concurrent applications.

This paper considers the problem of automatically configuring multicomputers for use in embedded applications. The configuration problem is decomposed into two subproblems: (1) specification of the hardware components and (2) assignment of the software tasks to the hardware. An automated technique is introduced to solve these subproblems concurrently. The technique is described and then verified on a set of real and synthetic test cases. The paper concludes with a discussion and summary of the results.

The design process used to produce an innovative computer system is presented.The computer system that resulted from the process uses a circular motif both for the user interface and the input device.The input device is a dial and the user interface is visually organized around the concept of a circle.The design process itself proceeded in the presence of a great many constraints and we discuss these constraints and how an innovative design was achieved in spite of the constraints.

The Wearable Computer Project is a testbed integratingresearch on rapid design and prototyping. Based onrepresentative examples from six generations of wearablecomputers, the paper focuses on the differences in rapidprototyping using custom design versus off-the-shelfcomponents. The attributes characterizing these two designstyles are defined and illustrated by experimentalmeasurements. The off-the-shelf approach required ten timesthe overhead, 30% more cost, fifty times the storage resources,20% more effort, five times more power, but 30% less effort toport software than the embedded approach.

Quality of service (QoS) has been receiving wide attention in many research communities including networking, multimedia systems, real-time systems and distributed systems. In large distributed systems such as those used in defense systems, on-demand service and inter-networked systems, applications contending for system resources must satisfy timing, reliability and security constraints as well as application-specific quality requirements. Allocating sufficient resources to different applications in order to satisfy various requirements is a fundamental problem in these situations. A basic yet flexible model for performance-driven resource allocations can therefore be useful in making appropriate tradeoffs. We present an analytical model for QoS management in systems which must satisfy application needs along multiple dimensions such as timeliness, reliable delivery schemes, cryptographic security and data quality. We refer to this model as Q-RAM (QoS-based Resource Allocation Model). The model assumes a system with multiple concurrent applications, each of which can operate at different levels of quality based on the system resources available to it. The goal of the model is to be able to allocate resources to the various applications such that the overall system utility is maximized under the constraint that each application can meet its minimum needs. We identify resource profiles of applications which allow such decisions to be made efficiently and in real-time. We also identify application utility functions along different dimensions which are composable to form unique application requirement profiles. We use a video-conferencing system to illustrate the model.

When creating mission-critical distributed systems using off-the-shelf components, it is important to assess the dependability of not only the hardware, but the software as well. This paper proposes a way to test operating system dependability. The concept of response regions is presented as a way to visualize erroneous system behavior and gain insight into failure mechanisms. A 5-point "CRASH" (catastrophic, restart, abort, silent, hindering) scale is defined for grading the severity of robustness vulnerabilities encountered. Test results from five operating systems are analyzed for robustness vulnerabilities, and exhibit a range of dependability. Robustness benchmarking comparisons of this type may provide important information to both users and designers of off-the-shelf software for dependable systems.

Inability to identify weaknesses or to quantify advancements in software system robustness frequently hinders the development of robust software systems. Efforts have been made to develop benchmarks of software robustness to address this problem, but they all suffer from significant shortcomings. The paper presents the various features that are desirable in a benchmark of system robustness, and evaluates some existing benchmarks according to these features. A new hierarchically structured approach to building robustness benchmarks, which overcomes many deficiencies of past efforts, is also presented. This approach has been applied to building a hierarchically structured benchmark that tests part of the Unix file and virtual memory systems. The resultant benchmark has successfully been used to identify new response class structures that were not detected in a similar situation by other less organized techniques.

This paper considers the design problems of processor specification and task allocation for embedded computer systems. A graph partitioning-based representation is proposed that allows these problems to be solved concurrently. A custom design automation algorithm bared on this representation is then presented. This algorithm, named CP*-2, was benchmarked against two baseline algorithms on a combination of real and synthetic test cases with respect to two figures of merit: hardware cost and run-time. The real test cases are based on commercially developed automotive applications and the benchmark algorithms consist of heuristic and simulated annealing approaches. On average, CP*-2 was found to generate solutions with quality comparable to simulated annealing with up to an order of magnitude improvement in run-time.

The advent of mobile computing has made power consumption a critical design factor. There has been little systematic consideration of the power sources for mobile computing systems. This paper presents a class of system-level metrics intended to make a systematic study more feasible and to more accurately reflect the trade-off between battery life and performance. An example involving the clock frequency of a CPU shows the possible impact of the nonlinearity, an impact not predicted by existing metrics. Results of an initial attempt to verify the example are presented and explained. The paper concludes with drawbacks of the metric and possible extensions to overcome these drawbacks.

Ultra-dependable computing demands verification of fault-tolerant mechanisms in the hardware. The most popular class of verification methodologies, fault-injection, is fraught with a host of limitations. Methods which are rapid enough to be feasible are not based on actual hardware faults. On the other hand, methods which are based on gate-level faults require enormous time resources. This research tries to bridge that gap by developing a new fault-injection methodology for processors based on a register-transfer-language (RTL) fault model. The fault model is developed by abstracting the effects of low-level faults to the RTL level. This process attempts to be independent of implementation details without sacrificing coverage, the proportion of errors generated by gate-level faults that are successfully reproduced by the RTL fault model. A prototype tool, ASPHALT, is described which automates the process of generating the error patterns. The IBM RISC-Oriented Micro-Processor (ROMP) is used as a basis for experimentation. Over 1.5 million transient faults are injected using a gate-level model. Over 97% of these are reproduced with the RTL model at a speedup factor of over 500:1. These results show that the RTL fault model may be used to greatly accelerate fault-injection experiments without sacrificing accuracy.

The paper describes the evolution of an Interdisciplinary Concurrent Design Methodology (ICDM) and the metrics used to compare four generations of wearable computer artifacts produced by the methodology at each stage of ICDM's growth.The product cycle is defined, its phases, and the design information representation for each phase.Six generic axes of design activity are defined, and the concept of benchmarking a complete design methodology using these axes is introduced.In addition an approach for measuring design complexity is proposed.When applied to the four generations of the CMU wearable computers, the ICDM has demonstrated two orders of magnitude increase in design and efficiency. A. Conceptual Product.During the conceptualization stage, the multidisciplinary design team establishes a common vision of the end product.This vision provides a consistent set of design goals for all disciplines to maintain

Complex systems such as computers, aerospace systems, etc., are often tested by using a sequence of tests to exercise the functionality of the system. If the system fails a test, an error message is generated, initiating the test selection (TS) phase. The troubleshooter must decide whether or not to run more tests. Should the troubleshooter decide to conduct more tests, a test must be chosen as it may no longer be useful to conform to the predefined sequence. While in the TS phase, the troubleshooter will repeatedly make these decisions until he is done. The authors present a domain-independent framework to automate TS that is based on two computational models, TI and TP. Both models are needed for the authors show there are applications for which one model performs well, while the other model performs poorly. The use of the appropriate model for automating TS is indicated by certain characteristics of the testing sequence and the system under test.>

A methodology is proposed for performance prediction of an application in a multi-computer architecture. The methodology introduces a two-step approach. In the first step the application (Sphinx I) is considered as a benchmark and its performance in uniprocessor systems is predicted from other standard benchmarks. In the second step the predicted performance values for the compositive modules of the application are used in a partition model to predict the performance of the entire application in a multi-computer architecture. The approach is validated by measuring the actual performance of the application on different two-processor configurations and comparing the results to the predictions made. The methodology for predicting application performance in a multi-computer architecture provides a relatively inexpensive approach to design. Rather than porting the application to the target architecture to measure its performance, the performance can be estimated from standard benchmarks, such as Dhrystone and Linpack. Results from Dhrystone and Linpack benchmarks are readily available, even for new systems, since the results are typically published in advertising literature.>

Abstract – Timing verification ascertains whether timing checks on components in a circuit are satisfied given component delay models. This paper addresses timing verification of microprocessor-based designs for which previous approaches are shown to be inadequate. It introduces the concept of sequential path tracing – tracing paths through both space and time – that forms the basis of the mtv tool. mtv has the following novel features: unlike previous approaches, it considers sequential behavior together with timing and handles sequential sensitizability and multi-cycle paths automatically; it does not require a predefined clock schedule and can handle circuits with conditional or gated clocks, multiple unrelated clocks, asynchronous set/reset, and power-up initialization; it generates symbolic constraints between timing attributes of components that can be efficiently re-used for small circuit changes or by a synthesis/optimization tool; symbolic constraints also enable common ambiguity removal. Experimental results demonstrate that mtv takes only a few CPU minutes to generate symbolic constraints for each of several microprocessor-based designs. I.

Products of the future will be technologically more sophisticated, highly customized, produced in small batches, and brought to market quickly. These products will require an approach which integrates the application, the artifact, the CAD environment, and the physical prototyping. The EDRC is developing a comprehensive program to integrate these four activities.>

In an Ethernet network, a common type of failure is the temporary of extended loss of bandwidth, or soft failure as it is referred to in the literature. Though the causes of soft failures vary, to the network user such failures are perceived as noticeably degraded or anomalous performance.This work uses anomaly detection as a means to signal performance degradations that are indicative of network soft failures. Detection is done via a signature matching mechanism, call a fault feature vector, which will detect the occurrence of a fault by looking for anomaly conditions particular to the fault. In a two-year study of the Carnegie Mellon University Computer Science Network the fault feature vector mechanism proved effective in detecting faults and discriminating between faults types. This mechanism was also effective at abstracting large amounts of network data to only those events which warranted operator attention; in this two-year study, over 32 million monitored data points were reduced to under a two hundred event matchings.

The Engineering Design Research Center (EDRC) promotes the establishment and dissemination of a scientific basis for design based on an interdisciplinary approach to researrh and education. The Center's vision is that a scientific framework for design can exploit rapid advances in computer and communications technologies to serve the competitive need for reduced product development cycles, improved quality and reliability, and lower cost. Basic notions of the product cycle underlie the Center's strategic plan, a framework of researrh thrusts leading from barriers in design science to goals and vision. As an NSF Engineering Research Center, EDRC conducts cross-educational and industrial programs in parallel with research

A hierarchical select-and-interconnect methodology for system-level design is described. It extends the flexibility of previous approaches by allowing dynamic subproblem ordering, which is essential for this domain. The design model of M1, a knowledge-based system that implements this approach for small computer systems, is presented. M1's design space covers five microprocessor families, and it has generated hundreds of designs, three of which were built. A set of experiments showing that M1 can be used successfully to design in this complex domain and provides a substantial increase in designer productivity is described.>

Performance benchmarks are used to help decide the question: 'which system is faster?' With the increased use of computers in critical systems, there are more and more applications of resources to improve system quality. However, there are no benchmarks that can be used to compare the dependability and robustness of systems in order to answer the question: 'which system is more reliable?' The authors present an attempt at the development of a benchmark to gauge a system's robustness as measured by its ability to tolerate errors. The initial effort produced four primitive benchmark programs. They include file management system, memory access, user application, and C library functions. Each primitive benchmark targets a system functionality and measures its behavior, given erroneous inputs. The authors present the motivation and experimental results for one of these primitive benchmarks in detail followed by an analysis of the results. A methodology is presented to combine the primitive benchmarks to form an overall robustness figure.>

Vuman is a wearable portable computer used for navigation through electronic blueprints. Thirty working units of Vuman were designed and manufactured from system concept using a concurrent engineering design environment. The authors describe the steps in prototyping Vuman, using the suite of synthesis and analysis tools in the electronic and mechanical domains which comprise the concurrent engineering design environment. Some unforeseen problems and their proposed solutions are discussed.>

The authors describe a methodology for modeling fault effects on system behavior and evaluate the methodology through an experimental fault injection, study. The methodology characterizes a workload under faulted conditions, and then uses workload attributes such as instruction usage to infer the fault behavior of other workloads. A model of workload attributes required to predict faulty behavior, is presented and evaluated.>

A tool capable of extracting structure from a logical design was implemented, and the effect of structure on placement was studied. Results demonstrate that structure can reduce the problem complexity of a traditional placement tool when the structured portion of a design is clustered and/or seeded, thereby giving the traditional placement tool fewer cells to place. The reduction in complexity depends on the amount of structure in the logic design. In addition, placing structure may lead to better circuit performance by reducing bit-slice length, the distance a signal must travel as it traverses the combinational logic of a bit slice. The number of layer changes for clock lines and control signals can be reduced by aligning the modules connected by these signals. By strategically placing the drivers of key control signals, the lengths of their longest stubs can be reduced, thereby improving clock speed. Experiments demonstrate that structurally directed placement can reduce bit-slice length by up to 96% and clock stub length by up to 67% with negligible impact on traditional routing metrics, such as track count and wirelength.>

The results of cache-simulation experiments with an abstract machine for reducing combinator graphs are presented. The abstract machine, called TIGRE, exhibits reduction rates that, for similar kinds of combinator graphs on similar kinds of hardware, compare favorably with previously reported techniques. Furthermore, TIGRE maps easily and efficiently onto standard computer architectures, particularly those that allow a restricted form of self-modifying code. This provides some indication that the conventional "stored program" organization of computer systems is not necessarily an inappropriate one for functional programming language implementations. This is not to say, however, that present day computer systems are well equipped to reduce combinator graphs. In particular, the behavior of the cache memory has a significant effect on performance. In order to study and quantify this effect, trace-driven cache simulations of a TIGRE graph reducer running on a reduced instruction-set computer are conducted. The results of these simulations are presented with the following hardware-cache parameters varied: cache size, block size, associativity, memory update policy, and write-allocation policy. To begin with, the cache organization of a commercially available system is used and then the performance sensitivity with respect to variations of each parameter are measured. From the results of the simulation study, a conclusion is made that combinator-graph reduction using TIGRE runs most efficiently when using a cache memory with an allocate-on-write-miss strategy, moderately large block size (preferably with subblock placement), and copy-back memory updates.

The input/otrtput (1/0) subsystem is often the bottleneck in high performance computer systems where the CPU/Memory technology has been pushed to the limit.But recent microprocessor and workstation speeds ae beginning to shift the system balance to the point that 1/0 is becoming the bottleneck even in mid-range and low-end systems.In this work the 1/0 subsystem's impact on system performartce is shown by modeling the relative performance of VAX uniprocessors with and without enhancement in the 1/0 subsystem.Tradhional system performance models were enhanced to include the effect of the I/O subsystem.The parameters modeling the I/O subsystem's effect were identified as D[,O (the number of I/O bytes transferred per instruction executed by the CPU), trl,O (the &ansfer time per I/O byte), and Wq (the waiting time in the I/O subsystem).These parameters were measured on a VAX1 1/780 system by using special purpose hardware and were used to calibrate the enhanced system performance model.It is interesting to note that these measurements indicate that contemporary systems require a factor of eight increase over the I/O bandwidth requirement stated by the Amdhal-Case rule.

The author surveys the approaches and techniques used to improve system reliability. Over the past 40 years computing systems have experienced over three orders of magnitude improvement in average time to failure and over six orders of magnitude improvement in work accomplished between outages. A three-dimensional design space for comparing fault-tolerant systems is proposed and populated by over two dozen actual systems. A detailed description is provided for a dozen systems evenly distributed throughout the design space. The author concludes by observing trends in the design space and projecting future developments.>

Design for dependability has long been an important issue for computer systems. While several dependability analysis tools have been produced, no effort has been made to automate the design for dependability. This paper describes ASSURE, an automated design for dependability advisor, which is part of the MICON system for rapid prototyping of small computer systems. A design for dependability methodology and a formal interface between synthesis and dependability analysis are presented. ASSURE's operation includes dependability analysis, evaluation of dependability enhancement techniques using predictive estimation, and selection of a technique. Different kinds of knowledge used in designing for dependability are identified, including an algorithmic approach for dependability analysis and a knowledge-based approach for suggesting dependability enhancement techniques. Examples of designs produced using ASSURE as a dependability advisor are provided and show an order of magnitude dependability improvement.

The results of several experiments conducted using the fault-injection-based automated testing (FIAT) system are presented. FIAT is capable of emulating a variety of distributed system architectures, and it provides the capabilities to monitor system behavior and inject faults for the purpose of experimental characterization and validation of a system's dependability. The experiments consists of exhaustively injecting three separate fault types into various locations, encompassing both the code and data portions of memory images, of two distinct applications executed with several different data values and sizes. Fault types are variations of memory bit faults. The results show that there are a limited number of system-level fault manifestations. These manifestations follow a normal distribution for each fault type. Error detection latencies are found to be normally distributed. The methodology can be used to predict the system-level fault responses during the system design stage.>

Probe selection (PS) in machine diagnosis is viewed as a collection of models that apply under specific conditions. This makes it possible for three polynomial-time optimal algorithms to be developed for simplified PS models that allow different probes to have different costs. The work is compared with previous research, wherein H.A. Simon and J.B. Kadane (1975) review and develop a collection of models for optimal problem-solving search. The relationship between these models and the three newly developed algorithms for PS is explored. Two of the algorithms are unlike the ones discussed by Simon and Kadane. The third cannot be related to the problem-solving models.>

The MICON system is an integrated collection of programs which automatically synthesizes small computer systems from high level specifications. The system addresses multiple levels of design, from logical through physical, providing a rapid prototyping capability. Two programs form MICON's nucleus: a knowledge-based synthesis tool called M1; and, an automated knowledge acquisition tool named CGEN which is used to teach M1 how to design. Other tools in the MICON system are an integrated database and associated data management tools. The system is fully functional, having been used to generate designs that have been fabricated. This paper describes the architecture and operation of the MICON system.

Knowledge-based systems are becoming pervasive in the computer-aided design area. For these systems to achieve satisfactory levels of performance large amounts of knowledge are necessary; however, the acquisition of knowledge is a difficult task. Automated knowledge-acquisition tools (AKAT) provide capabilities for quickly building and maintaining knowledge-bases. This paper describes CGEN, a tool which allows hardware designers, unfamiliar with artificial intelligence, to deposit their expertise into a knowledge-base. A set of experiments which tested CGEN's capabilities are presented. The experiments demonstrate hardware designers can produce high quality knowledge-bases using CGEN.

An algorithm for extracting structure from a logical design is presented. It uses a data structure which explicitly represents not only connectivity, but also a variety of information that is generated during logical design. The algorithm is applied to a small design and used to determine the layout. Work is in progress to increase the number of functional cluster types that can be extracted and to develop additional heuristics for automatically mapping the structure onto the chip.>

A simple and effective parallel algorithm to color the nodes of a graph is presented. The algorithm is useful in its own right. It also provides a vehicle to demonstrate the tradeoffs between performance and speed implicit in many parallel algorithms. The algorithm is used when the parallel machine has at least as many processors as there are nodes to color.>

A model for predicting multiprocessor performance on iterative algorithms is developed. Each iteration consists of some amount of access to global data and some amount of local processing. The iterations may be synchronous or asynchronous, and the processors may or may not incur waiting time, depending on the relationship between the access time and processing time. The effect on performance of the speed of the processor, memory, and the interconnection network is studied. The model also illustrates the significant impact on performance of decomposing an algorithm into parallel processes. The model's predictions are calibrated with experimental measurements.>

This paper presents a unifying procedure, called Facet, for the automated synthesis of data paths at the register-transfer level. The procedure minimizes the number of storage elements, data operators, and interconnection units. A design generator named Emerald, based on Facet, was developed and implemented to facilitate extensive experiments with the methodology. The input to the design generator is a behavioral description which is viewed as a code sequence. Emerald provides mechanisms for interactively manipulating the code sequence. Different forms of the code sequence are mapped into data paths of different cost and speed. Data paths for the behavioral descriptions of the AM2910, the AM2901, and the IBM System/370 were produced and analyzed. Designs for the AM2910 and the AM2901 are compared with commercial designs. Overall, the total number of gates required for Emerald's designs is about 15 percent more than the commercial designs. The design space spanned by the behavioral specification of the AM2901 is extensively explored.

In this paper we describe WEAVER, a channel/switch-box knowledge-based routing program. WEAVER considers all the important routing metrics such as 100% routability, minimum routing area, minimum wire length, and minimum number of vias simultaneously. It allows pre-routed nets, and user interaction throughout the entire routing process. It also relaxes unnecessary constraint of assigning different layers to different directions, the constraint imposed by all of the current channel and switch-box routers. WEAVER is a grid-based router that utilizes two interconnection layers and can be easily expanded to route any shape routing area such as 'T' or '+'. Implemented in OPS5, a production system language, WEAVER routinely produces routings requiring less area than routers that focus on a single routing metric.

article The influence of parallel decomposition strategies on the performance of multiprocessor systems Share on Authors: Dalibor Vrsalovic Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Edward F. Gehringer Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Zary Z. Segall Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile , Daniel P. Siewiorek Department of Computer Science Carnegie-Mellon University Department of Computer Science Carnegie-Mellon UniversityView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 396–405https://doi.org/10.1145/327070.327372Online:01 June 1985Publication History 26citation241DownloadsMetricsTotal Citations26Total Downloads241Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper introduces the concept of an integrated instrumentation environment (IIE) for multiprocessors. The primary objective of such an environment is to assist the user in the process of experimentation. The emphasis in an IIE is on experiment management (including stimulus generation, monitoring, data collection and analysis), rather than on techniques for program development as in conventional programming environments. We believe the functionality of the two environments should eventually be provided in one comprehensive environment.

In this paper a new modeling methodology to characterize failure processes in digital computers due to hardware transients is presented. The basic assumption made is that system sensitivity to hardware transient errors is a function of critical resources usage. The failure rate of a given resource is approximated by a deterministic function of time, depending on the average workload of that resource, plus a Gaussian process. The probability density function of the time to failure obtained under this assumption has a decreasing hazard function, explaining why decreasing hazard function densities such as the Weibull fit experimental data so well. Data on transient errors obtained from several systems are analyzed. Statistical tests confirm the good fit between decreasing hazard distributions and actual data. Finally, models of common fault-tolerant redundant structures are developed using decreasing hazard function distributions. The analysis indicates significant differences between reliability predictions based on the exponential distribution and those based on decreasing hazard function distributions. Reliability differences of 0.2 and factors greater than 2 in Mission Time Improvement are seen in model results. System designers should be aware of these differences.

Calculation of the reliability of computer system architectures with built-in redundancy, such as multiprocessors, is gaining in importance. The task of computing the reliability function for arbitrary Processor-Memory-Switch (PMS) interconnection structures, however, is tedious and prone to human error. Existing reliability computation programs make one of two assumptions: • That the case analysis of success states of the system has been carried out. Such analysis must be done manually. In this instance, input to the program is usually in the form of an intermediate representation (e.g., fault tree, reliability graph). • That the interconnection structure is a member of, or can be partitioned into, some limited class of structures for which a parametric family of equations exists (e.g., N-modular redundant systems, hybrid redundant systems).

This is an elaboration of the paper `Synchronization and matching in redundant systems' by Davies and Wakerly (ibid., vol.27, p.531-9, 1978). The design of voters for synchronization is strongly dependent on the signaling convention used. This correspondence presents voter designs for three different signaling conventions (transition, level, and pulse). The issue of improved voter performance is also addressed.

This correspondence proposes a model using microcycle and memory read pause times to account for variation in performance between members of a computer family. Wben applied to the DEC PDP-11 and IBM S/360-S/370 families, the model explains over 90 percent of the variation. This model is useful for initial family planning, as well as design of individual family members.

Design automation at the register transfer level of design is still in its infancy, and it is not yet completely understood what the appropriate measures used in direction the automated design process should be. To establish these measures, results of these design automation systems must be compared with some near optimal designs. A set of statistically based experiments is developed to estimate near optimal designs. A method is demonstrated for gathering data on designer performance, specifically at the different levels of systems design, and in general for calibration of other design automation systems where the intuitive designer still performs more capably than the present design algorithms. An analysis of variance is used to indicate the relative importance of various decisions in a system design. It is shown that the algorithm to be implemented and the hardware design style account for 90 percent of the variation in the results. Thus, selecting the design style (e.g., distributed, microprocessor, pipelined, etc.) is the most important parameter for a design automation system.

With the exponential explosion in chip complexity there is a growing need for high level design aids. A preliminary experiment was conducted in mating a hierarchical, top-down DA system for data paths with an existing IC placement and router. Nine designs ranging in complexity from 7 to 150 register transfers were synthesized. Strong correlations were observed between high level, abstract measures and final placed and routed chip area. It was observed that use of logic primitives of a moderate level abstraction yielded a 50% savings in placed and routed chip area.

A brief survey of memory chip failure modes shows that partial chip failures are the dominant failure mode. A single error-correcting (SEC) code memory model is developed based on the results of the survey. The effect of memory support circuitry, often ignored, is included. Examples illustrate that the support circuitry dominates the memory system reliability for wide ranges of memory system parameters.

Various switch designs for the hybrid redundancy scheme are studied. A reliability model for the switch is developed and the switch is shown to be a significant factor in the overall system reliability. A hybrid redundancy scheme with a triple-modular redundant (TMR) core may have a maximum attainable reliability for only a spare or two. Adding spares complicates the switch enough to cause the system reliability to actually decrease. There exist conditions under which the switch becomes so complex that simple TMR would yield a better solution. Models for fault-tolerant switch designs are also obtained. Finally, various designs are compared via their reliability models.

The classical reliability model for N-modular redundancy (NMR) assumes the network to be failed when a majority of modules which drive the same voter fail. It has long been known that this model is pessimistic since there are instances, termed compensating module failures, where a majority of the modules fail but the network is nonfailed. A different module reliability model based on lead reliability is proposed which has the classical NMR reliability model as a special case. Recent results from the area of test generation are employed to simplify the module reliability calculation under the lead reliability model. First a fault equivalent technique, based on functional equivalence of faults, is developed to determine the effect of compensating module failures on system reliability. This technique can increase the predicted mission time (the time the system is to operate at or above a given reliability) by at least 40 percent over the classical model prediction for simple networks. Since the fault equivalent technique is too complex for modeling of large circuits a second, computational simpler technique, based on fault dominance, is derived. It is then shown to yield results comparable to the fault equivalent technique. A more complex example circuit analyzed by the fault dominance model shows at least a 75 percent improvement in mission time due to modeling compensating module failures. A commercialy available 31 gate integrated circuit chip is also modeled to demonstrate the applicability of the technique to large circuits.

A distinguishing feature of modular design from ad hoc design is the establishment of an intermodule protocol to which all modules adhere. The problem of representing and analyzing intermodule protocol for the control portion of register transfer level systems is outlined. An introduction to two existing graph models of computation indicates that existing register transfer level module sets are representable by various "token flow" models. A single model that is capable of representing the token flow models and some of its analytical properties are illustrated by example. Finally, three examples of deadlocks in existing modules sets are presented. These deadlocks were uncovered by the analytic properties of the new model. One example is due to incorrect interconnection of modules at the user level. The other two illustrate incorrect signaling conventions between modules necessitating a redesign of some modules.

There are several instances where the classical method of triple-modular redundancy (TMR) reliability modeling may provide predictions which are inadequate. It is shown that for even simple networks such as those exhibiting fan-in and fan-out, classical methods may predict a reliability that is higher than or lower than the actual reliability. Furthermore, the classical method gives no hint as to whether the predicted number is high or low. As a solution to this problem, a method of partitioning an arbitrary network into cells such that faults in a cell are independent of faults in other cells is proposed. An algorithm is then given to calculate the reliability of any such cell, by considering only the structure of the interconnections within the cells. The value of the reliability found is exact if TMR is assumed to be a coherent system. An approximation to the algorithm is also described; this can be used to find a lower bound to the reliability without extensive calculation.

Some comments on a recent contribution on multiple fault detection using test sets for single fault detection are presented. A counter example that shows some defects in generalizing from a tree to an arbitrary network are also included.

This book is an introduction to the design of digital systems. It is intended as a one semester course for electrical engineering or computer science students and assumes only a minimal background in programming, binary numbers, and Boolean algebra. The intended level of the course is never mentioned. The major goal of the book is to "....involve the student in the design process...". The vehicle for this involvement is a register transfer (RT) language. Statements in the language are shown to be readily translated into hardware. Thus once the RT language description is formulated the hardware design is essentially complete. Also, as a matter of course specific systems are designed in the RT language before generalizations are made. Unfortunately the RT language and the specific to general approach (both of which the reviewer views as good techniques) lead to the major weaknesses of the book.

A Design Automation System for the RT level of design is described. The System explores the design space by finding alternative implementations for a user given behavioral specification. The alternative solutions are obtained by transformations on a graph model. These transformations effect trade-offs between the cost of the hardware and the speed of the algorithm. Heuristic routines are used to reduce the design space by exploring only those alternatives whose characteristics approach a user given set of goals.

This paper describes the architecture of Computer Modules, or CMs. They are large digital modules of about minicomputer complexity that are specifically designed to take advantage of the rapidly advancing semiconductor technology. These modules are intended to be interconnected into systems that implement a wide range of computational structures. The main features of a CM include a small processor as the primary control element and memory distributed among the CMs in the system rather than centralized into memory modules as in current multiprocessors. CMs are interconnected into a network via buses that each have their own virtual address space to facilitate efficient inter-module memory sharing. This paper includes an ISP description of the address translation mechanisms as well as a discussion of several important implementation issues such as the avoidance of deadlocks in CM networks and the width of the inter-CM buses.

The combination of N-modular redundancy (NMR) and standby sparing has resulted in a promising redundancy technique for protecting those portions of a fault-tolerant system whose continuous real-time operation is essential. This technique, known as hybrid redundancy, uses N + Sp identical modules. N of these are connected to a majority voter to form an NMR core. The remaining Sp are used as standby spares. Disagreement detectors instruct a switch to replace with a standby spare any of the N modules that disagrees with the majority consensus. Since the switch and disagreement detector, as well as the modules, must function properly for the system to perform its designed task, the overall system reliability depends on the disagreement detector, switch, and hybrid reliabilities. Hence the overall reliability is a function of switch reliability. A highly reliable, thus simple, switch is desirable. First, strategies where every spare can be switched into every voter position (totally assigned) are considered. An optimal strategy is developed where the number of states in the switch is the criterion used for optimality. Formulas for the switch state count for the various strategies are derived and the strategies compared. Next, partially assigned switching strategies, strategies where every spare need not be capable of occupying every voter position, are examined. It is shown that designs where all spares are assigned to the same t + 2 of the 2t + 1 voter positions have as good reliability as the more complex totally assigned switching strategy.

A marriage of N-modular redundancy (NMR) and standby sparing has resulted in a promising redundancy technique for protecting those portions of a fault-tolerant system whose continuous real-time operation is essential. This technique, known as hybrid redundancy, consists of N identical modules connected to a majority voter to form an NMR core. Disagreement detectors instruct a switch to replace any of the N modules that disagree with the majority consensus by a standby spare. The switch is essential to the operation of the hybrid redundancy scheme. The system reliability is a product of the reliabilities of the switch and the hybrid redundancy scheme assuming a perfect switch. To realize the demonstrated potential of the latter a highly reliable, thus simple, switch is required. An iterative cell switch is proposed and demonstrated to save at least 25 percent, and more than 80 percent in some instances, of the complexity of a switch design presented elsewhere in the literature. The use of threshold, rather than majority, voters is considered and shown to yield a simpler design in some cases. Three techniques for decreasing the propagation delay through the iterative cell switch are presented as well as a scheme to implement retry of failed modules. Finally, five different switch designs are compared on a cost and complexity basis.