Recent ics_tr items

Steps Toward an Artificially Intelligent CAI System: An Interim Report on Research in Progress

Wed, 9 Mar 2022 00:00:00 +0000

Steps Toward an Artificially Intelligent CAI System: An Interim Report on Research in Progress

A System for Testing Student Programs

Wed, 9 Mar 2022 00:00:00 +0000

A System for Testing Student Programs

Material and Ideas to Teach an Introductory Programming Course Using Logo

Wed, 9 Mar 2022 00:00:00 +0000

Material and Ideas to Teach an Introductory Programming Course Using Logo

Abstract description of pointer data structures : an approach for improving the analysis and optimization of imperative programs

Wed, 9 Mar 2022 00:00:00 +0000

Even though impressive progress has been made in the area of optimizing and parallelizing array-based programs, the application of similar techniques to programs using pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties, pointers can be used to implement a wide variety of structures which exhibit a much larger set of properties. The diversity of these structures implies that programs with pointer data structures cannot be effectively analyzed by traditional optimizing and parallelizing compilers.

In this paper we present a new approach that leads to the improved analysis and transformation of programs with recursively-defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS). ADDS is a simple extension to existing imperative languages (such as C) that allows the programmer to explicitly describe the important properties of a large class of...

Distributed Computer Operating System: Programming Guide Version 3

Wed, 9 Mar 2022 00:00:00 +0000

Distributed Computer Operating System: Programming Guide Version 3

A Language and Data Structure for Fact Retrieval

Wed, 9 Mar 2022 00:00:00 +0000

A computer system that results in a useful and quite natural vehicle in which fact retrieval systems can be constructed quite easily is presented and analyzed. The system, called TRAMP, consists of a simulated associative machine providing the storage structure, and a relational language for that associative storage structure providing a question-oriented data structure. The TRAMP system is a computer language with applicability to a class of problems that are best represented as associations between objects, or by a relational data structure. In particular, the language contains potent fact retrieval capabilities in the sense that it automatically deduces implications of facts resident in its store.

We use the term "fact retrieval" here to mean the extraction of facts from a data store regardless of whether or not the information explicitly resides in the store. Thus, fact retrieval includes "document" retrieval--simply locating and extracting a data item from memory...

Nonhierarchical Process Structure in a Decentralized Computing Environment

Wed, 9 Mar 2022 00:00:00 +0000

This paper describes a process organization designed to be used in a decentralized hardware environment where reliability is a major goal. The process organization proposed here is designed to reflect such a hardware organization and to be consistent with the goal of reliability.

The proposed process structure is a nonhierarchical one, designed to allow structured but unhindered communication, selective access to critical information, and control not solely a function of process creation history. Communication is, in general, accomplished by the sending of messages. Messages may be sent by a process to any other process whose name it knows. Access to critical information is controlled; only special kinds of processes may access it. Access to shared information is also regulated.

Some new terminology is introduced to make explicit the features of this process structure. The special processes which can access critical, or state, information are called state changers....

L6 Manual

Wed, 9 Mar 2022 00:00:00 +0000

L6 Manual

Exploiting ultra-fine grain parallelism for machines with parallel pipelined datapaths

Wed, 9 Mar 2022 00:00:00 +0000

This report examines ultra-fine grain machine parallelism determined by various hardware styles and constraints. Two major components are incorporated in our system: (1) A generalized parameterized architecture model which characterizes different design styles and constraints based on parallel pipelined machines. (2) A retargetable compiler which maps instruction parallelism to ultra-fine grain machine parallelism for target architectures. Basically the generalized parameterized model is used to specify different target machines, and the retargetable compiler compiles and schedules applications, codes written in high-level language, into control codes for given target machines. The resulting control codes are run through a simulator, after which dynamic statistics of the execution are recorded and the ultra-fine grain parallelism of target machines is assessed. A set of studies has been conducted to demonstrate how ultra-fine grain machine parallelism is affected by various...

Sofa3 -- A Program for the Three-dimensional Sofa Problem

Wed, 9 Mar 2022 00:00:00 +0000

Sofa3 -- A Program for the Three-dimensional Sofa Problem

Methodology for the Generation of Program Test Data (Revised)

Wed, 9 Mar 2022 00:00:00 +0000

A methodology for generating program test data is described. The methodology is a model of the test data generation process and can be used to characterize the basic problems of test data generation. It is well defined and can be used to build an automatic test data generation system.

The methodology decomposes a program into a finite set of classes of paths in such a way that an intuitively complete set of test cases would cause the execution of one path in each class. The test data generation problem is theoretically unsolvable: there is no algorithm which, given any class of paths, will generate a test case that causes sore path in that class to be followed. The methodology attempts to generate test data for as many of the classes of paths as possible. It operates by constructing descriptions of the input data subsets which cause the classes of paths to be followed. It transforms these descriptions into systems of predicates which it attempts to solve.

A Semantic Formalism and Associated Semantic Process for the Specification and Translation of Programming Languages

Wed, 9 Mar 2022 00:00:00 +0000

Definitions of the semantics of programming languages are often incomplete and ambiguous. In particular, it may be difficult to determine what action is intended by a particular construct in some language. As a consequence, different implementations of that language may produce different results.

To help eliminate those differences which result from incomplete and ambiguous language definitions, a formalism for semantic specification and a semantic process are introduced. A semantic specification for a programming language can be viewed as a set of state transformations. The semantic process applies these state transformations to a program represented as a tree indicating the program structure and produces a computation tree representing the meaning of the program.

The semantic process can be viewed as part of a generalized table-driven translator for programming languages. Although such a translator may not be particularly efficient, its use produces translations...

Progress Report on the Distributed Computing System

Wed, 9 Mar 2022 00:00:00 +0000

Progress Report on the Distributed Computing System

The SpeC language reference manual

Wed, 9 Mar 2022 00:00:00 +0000

This Language Reference Manual defines the syntax and semantics of the SpecC language. For each SpecC construct the syntax, purpose, and semantics are defined and an explaining example is given. Also the full SpecC grammar is included using a formal notation in lex and yacc style.

Computerized Thematic Content Analysis

Wed, 9 Mar 2022 00:00:00 +0000

Computerized Thematic Content Analysis

Parallel interpretation of logic programs (revised)

Wed, 9 Mar 2022 00:00:00 +0000

Logic programs offer many opportunities for parallelism. We present an abstract model that exploits the parallelism due to nondeterministic choices in a logic program. A working interpreter based on this model is described, along with variants of the basic model that are capable of exploiting other sources of parallelism. We conclude with a discussion of our plans for experimenting with the various models, plans which we hope will lead eventually to a multi-processor machine.

Views of Artificial Intelligence

Wed, 9 Mar 2022 00:00:00 +0000

As time passed, more powerful software tools and bigger and faster computers were used by computer scientists to produce artificial intelligence programs which perform tasks which are similar to tasks that increasingly younger human beings can perform.

A Note on Response Time and Saturation

Wed, 9 Mar 2022 00:00:00 +0000

A Note on Response Time and Saturation

Modelling Structures Formalism

Wed, 9 Mar 2022 00:00:00 +0000

Modelling Structures Formalism

General Problem Solving Structure and the Logic Theory Machine

Wed, 9 Mar 2022 00:00:00 +0000

General Problem Solving Structure and the Logic Theory Machine

Automating Software Design

Wed, 9 Mar 2022 00:00:00 +0000

Automating Software Design

Analysis of a protocol using a token flow model

Wed, 9 Mar 2022 00:00:00 +0000

Analysis of a protocol using a token flow model

A Decision Tree Language

Wed, 9 Mar 2022 00:00:00 +0000

A Decision Tree Language

A Question-answering System Based on the Kay Parsing Algorithm

Wed, 9 Mar 2022 00:00:00 +0000

A Question-answering System Based on the Kay Parsing Algorithm

Representation Plans and Problem Solving

Wed, 9 Mar 2022 00:00:00 +0000

Problem solving processes in which 'general solution ideas' are constructed as part of the solution process are studied. In particular, the design of interactive systems in which the user controls and guides the solution process is considered. A formal approach to the structure of problem-solving systems is presented and studied. The approach is based on the idea of a problem grammar. Problem grammars are models of structure of solution representations constructed problem solvers. The approach can be used to clearly define the position of a user in an interactive problem-solving system. The formalism is used to design and implement one interactive problem-solving system and to sketch the design of a second. It is also used to describe the structure of several well-known automatic problem solvers. The terminology of the formalism can be used to characterize those structural deficiencies of automatic problem solving systems which can be overcome in an interactive system.

An Intercampus Data Network for the University of California

Wed, 9 Mar 2022 00:00:00 +0000

An Intercampus Data Network for the University of California

Plans and Problem Solving Structure

Wed, 9 Mar 2022 00:00:00 +0000

Plans and Problem Solving Structure

A Symbiotic Theory Formation System

Wed, 9 Mar 2022 00:00:00 +0000

A Symbiotic Theory Formation System

Steps Toward Automatic Theory Formation

Wed, 9 Mar 2022 00:00:00 +0000

This paper describes a theory formation system which can discover a partial axiomization of a data base represented as extensionally defined binary relations. The system first discovers all possible intensional definitions of each binary relation in terms of the others. It then determines a minimal set of these relations from which the others can be defined. It then attempts to discover all the ways the relations of this minimal set can interact with each other, thus generating a set of inference rules. Although the system was originally designed to explore automatic techniques for theory construction for question-answering systems, it is currently being expanded to function as a symbiotic system to help social scientists explore certain kinds of data bases.

A Model-Driven Question Answering System for Mixed Initiative CAI

Wed, 9 Mar 2022 00:00:00 +0000

A Model-Driven Question Answering System for Mixed Initiative CAI

EXTRAC: Initial Report and User's Manual

Wed, 9 Mar 2022 00:00:00 +0000

EXTRAC: Initial Report and User's Manual

Computer System Protection: An Inventory

Wed, 9 Mar 2022 00:00:00 +0000

Computer System Protection: An Inventory

Functional Programming, Testing and Machine Aids

Wed, 9 Mar 2022 00:00:00 +0000

The main ideas of functional (structured or top-down) programming are briefly reviewed and examined for implications for testing. It is pointed out that functional programming provides an opportunity for explicitly tracking functional specifications of an evolving design. The relevance of an integrated programming environment to this methodology is observed and two particular features it should have are examined: effective top-level execution control by the programmer himself and a continuous context that preserves the effects of individual tests. Two mechanisms, a type system and an extendible interpreter, are suggested as a basis for an implementation.

A Controller for a Braille Terminal

Wed, 9 Mar 2022 00:00:00 +0000

A controller for the braille terminal described by Anderson and Rogers permits the braille terminal to communicate with a host computer on a teletype-compatible line without special provisions in the host machine. The controller translates characters and buffers output messages. A complete braille representation of the standard teletype character set is given.

Design Rationalization of Three BASIC Systems

Wed, 9 Mar 2022 00:00:00 +0000

Work on software design processes (e.g., automatic programming, programming methodology) demands that we have available more explicit information about design problems and their possible solutions than is now available. We are developing and exploring the use of a method – design rationalization -- intended to aid in the discovery and codification of such information. The method is described, illustrated, and discussed in this paper. The results of applying it to three largo pieces of software are reported.

Irreducible Flowcharts

Wed, 9 Mar 2022 00:00:00 +0000

A schema is defined for characterising flowchart programs. This schema is used to construct a procedure for generating the set of flowcharts which contain n branching tests but which are irreducible; i.e., have no embedded flowcharts. The sets of such flowcharts for n ≤ 4 are enumerated here. Some examples from these sets are discussed. Suggestions are made concerning the utility of these flowcharts in the analysis of goto-less programming and in gaining insight into potential programming language constructs. A proof of the procedure for generating irreducible flowcharts is given.

Performance of a dataflow computer (revised)

Wed, 9 Mar 2022 00:00:00 +0000

Our goal is to devise a computer comprising large numbers of cooperating processors (LSI). In doing so we reject the sequential and memory cell semantics of the von Neumann model, and instead adopt the asynchronous and functional semantics of dataflow. We briefly describe the high-level dataflow programming language Id, as well as an initial design for a dataflow machine and the results of detailed, deterministic simulation experiments on a part of that machine. For example, we show that a dataflow machine can automatically unfold the nested loops of n-by-n matrix multiply to reduce its time complexity from O(n^3) to 0(n) so long as sufficient processors and communication capacity is available. Similarly, quicksort executes with average 0(n) time demanding 0(n) processors. Also discussed are the use of processor and communication time complexity analysis and "flow analysis", as aids in understanding the behavior of the machine.

Job Dominance and Minimal Idle Factor in the Flow Shop Problem

Wed, 9 Mar 2022 00:00:00 +0000

Job Dominance and Minimal Idle Factor in the Flow Shop Problem

Recoverability of Processes

Wed, 9 Mar 2022 00:00:00 +0000

Recoverability of Processes

Software Methods for Achieving Fail-soft Behavior in the Distributed Computing System

Wed, 9 Mar 2022 00:00:00 +0000

Software Methods for Achieving Fail-soft Behavior in the Distributed Computing System

Storage Structures Formalism

Wed, 9 Mar 2022 00:00:00 +0000

A storage structures formalism is described which can be used as a precise symbolic representation of low-level storage organizations and also as a description of storage requirements to a storage allocation mechanism. The formalism is based on three forms of memory management (sequential, linked, and associative) and associated referencing mechanisms (indexing, pointing, and hashing). Several examples of the formalism are presented. The meaning, or interpretation, of a storage structure as used to implement a modelling structure is discussed. Examples of alternative implementation structures (storage structures and their interpretations) for a particular modelling structure are presented.

Recursive Functional Programming for Students in the Humanities and Social Sciences

Wed, 9 Mar 2022 00:00:00 +0000

Recursive Functional Programming for Students in the Humanities and Social Sciences

LOGO for the Xerox Sigma 7: Internal Specifications and System Maintenance Manual

Wed, 9 Mar 2022 00:00:00 +0000

This is the internal specifications and system maintenance manual for Logo on the Sigma 7 at the University of California, Irvine.

On a Distance Function for Ordered Lists

Wed, 9 Mar 2022 00:00:00 +0000

Given two ordered lists of the same elements, we define their distance as the sum for each element of the absolute value of the difference of each element's position in the two lists. Various properties of this distance function are exhibited. In particular, a given list is "far", on the average, from a random list of the same elements.

A Study of the Recoverability of Computing Systems

Wed, 9 Mar 2022 00:00:00 +0000

A Study of the Recoverability of Computing Systems

A Note on the Expected Number of Singleton Cycles in a Permutation of 1, 2, ..., N.

Wed, 9 Mar 2022 00:00:00 +0000

A Note on the Expected Number of Singleton Cycles in a Permutation of 1, 2, ..., N.

The (preliminary) Id report: an asynchronous programming language and computing machine (revised)

Wed, 9 Mar 2022 00:00:00 +0000

The (preliminary) Id report: an asynchronous programming language and computing machine (revised)

A Parallel Mechanism for Detecting Curves in Pictures

Wed, 9 Mar 2022 00:00:00 +0000

HOUGH has proposed a procedure for detecting lines in pictures. DUDA-HART extended the method for a more general curve fitting. This paper shows how this method can be used to detect any given curve. The procedure presented here can be easily implemented and is more efficient in a parallel machine.

The Distributed BASIC Interpreter System

Wed, 9 Mar 2022 00:00:00 +0000

This paper presents a design for a translator system to be used in a distributed computing environment. The concept of a language service for such an environment is discussed and the distribution of the system's processes is examined. A technique for moving interrupted interactive computations among processors is presented. Detailed design specifications are provided for the translator system processes.

Syntax and semantics of the SpecC+ language

Fri, 17 Dec 2021 00:00:00 +0000

In this paper, we describe the goals for the development of an executable modeling language in the context of a homogeneous codesign methodology featuring the synthesis, reuse and validation flow. A C based language called SpecC+ is proposed as an attempt to achieve these goals. The syntax and semantics of the language is presented and compared with existing HDLs and we conclude it is conceptually more abstract, syntactically simpler, and semantically richer.

Maximum likelihood estimation of mixture densities for binned and truncated multivariate data

Fri, 17 Dec 2021 00:00:00 +0000

Binning and truncation of data is common in data analysis and machine learning. This paper addresses the problem of fitting mixture densities to multivariate binned and truncated data. The EM approach proposed by McLachlan and Jones (1988) for the univariate case is generalized to multivariate measurements. The multivariate solution requires the evaluation of multidimensional integrals over each bin at each iteration of the EM procedure. Naive implementation of the procedure can lead to computationally inefficient results. To reduce the computational cost a number of straightforward numerical techniques are proposed. Results on simulated data indicate that the proposed methods can achieve significant computational gains with no loss in the accuracy of the final parameter estimates. Furthermore, experimental results suggest that with a sufficient number of bins and data points it is possible to estimate the true underlying density almost as well as if the data had not been binned....

Communication synthesis for reuse

Fri, 17 Dec 2021 00:00:00 +0000

In this report we discuss a set of techniques needed to generate and synthesize communication interfaces in a System Design context. Given a behavioral specification, we present the transformations necessary for generating a communication model containing channels and protocol. This work is being conducted in conjunction with codesign tools being developed in the CADLAB at the University of California, Irvine.

Line size adaptivity analysis of parameterized loop nests for direct mapped data cache

Fri, 17 Dec 2021 00:00:00 +0000

Caches are an important part of architectural and compiler high performance and low-power strategies by reducing memory accesses and energy per access. In this paper, we examine efficient utilization of data caches in an adaptive memory hierarchy. We focus on the optimization of data reuse through the static analysis of line size adaptivity. We present a framework that enables the quantification of data misses with respect to cache line size at compile-time using (parametric) equations modeling interference. The framework considers both expressiveness and practicability of the analysis. Part of this analysis is implemented in a software package STAMINA. Experimental results demonstrate effectiveness and accuracy of the analytical results compared to alternative simulation based methods.

Project transPROse : reconciling mobile-code security with execution efficiency

Fri, 17 Dec 2021 00:00:00 +0000

transPROSE is a comprehensive research project investigating techniques for transporting programs securely over potentially insecure channels. The central focus of this project is the development of a blueprint for a next-generation mobile-code distribution format. A problem of previous approaches to mobile-code security has been that the additional provisions for security lead to a loss of efficiency, often to the extent of making an otherwise virtuous security scheme unusable for all but trivial programs. Project transPROSE strives to deviate from the common approach of studying security in isolation and instead focuses simultaneously on multiple aspects of mobile-code quality. Besides security, such aspects include encoding density, speed of dynamic code generation, and the eventual execution peiformance. This paper gives a high-level overview of project transPROSE and presents initial results.

A unified approach to concept learning

Fri, 17 Dec 2021 00:00:00 +0000

This dissertation proposes a unification of two leading approaches to concept learning: rule induction and instance-based learning.

Current rule induction algorithms based on the "separate and conquer" paradigm suffer from the fragmentation of the training set produced as induction progresses, and from high error rates in rules covering few examples (the "small disjuncts problem"). Current instance-based learners are unable to select different attributes in different regions of the instance space. The limitations of either approach can be addressed by bringing in elements of the other.

In this dissertation, the two paradigms are unified by noting the relationship between the representations they use, and introducing a new algorithm to learn concept descriptions in the unified representation. Instances and rules are unified syntactically by viewing instances as maximally specific rules, and semantically by allowing rules to match examples approximately. The RISE...

Decomposition of timed decision tables and its use in presynthesis optimizations

Fri, 17 Dec 2021 00:00:00 +0000

In this paper we introduce the decomposition of Timed Decision Tables (TDT), a tabular model of system behavior. The decomposition can be used in system partitioning or in HDL code restructuring to improve synthesis results. The TDT decomposition is based on the kernel extraction algorithm. By experimenting using named benchmarks, we demonstrate how TDT decomposition can be used in presynthesis optimizations. Presynthesis optimizations transform a behavioral HDL description into optimized HDL description that results in improved synthesized circuits.

A generic binding model for concurrently optimizing interconnection and functional units

Fri, 17 Dec 2021 00:00:00 +0000

A generic binding model which can provide complete information for binding task is presented in this paper. With information provided by this model, people can do interconnection optimization concurrently with operation and variable binding, as well as find better combination of FUs. Our method is not only much faster but also can obtain better or competitive binding than complex previous works.

FastMesh : efficient view-dependent meshing

Fri, 17 Dec 2021 00:00:00 +0000

In this paper we present an optimized view-dependent meshing framework for adaptive and continuous level-of-detail (LOD) rendering in real-time. Multiresolution triangle mesh representations are an important tool for adapting triangle mesh complexity in real-time rendering environments. Ideally for interactive visualization, a triangle mesh is simplified to the maximal tolerated perceptual error, and thus mesh simplification is view-dependent. This paper introduces an efficient hierarchical multiresolution triangulation framework based on a half-edge triangle mesh data structure, and presents an optimized computation of several view-dependent error metrics within that framework providing conservative error bounds. The presented approach called FastMesh, is highly efficient both in space and time cost, and it spends only a fraction of the time required for rendering to perform the error calculations and dynamic mesh updates.

Probabilistic analysis for scheduling with conflicts

Fri, 17 Dec 2021 00:00:00 +0000

In this paper, we consider the scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graphs so that all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our goal is to bound the maximum response time of any job in the system. It has been previously shown [13] that the best competitive ratio achievable by any online algorithm for the maximum response time on interval or bipartite graphs is [omega](n), where n is the number of nodes in the conflict graph. As a result, we study scheduling with conflicts under probabilistic assumptions about the input. Each node i has a value pi such that a job arrives at node i in any given time...

A systematic approach to branch speculation

Fri, 17 Dec 2021 00:00:00 +0000

A general theoretical framework is developed for the study of branch speculation. The framework yields a systematic way to select the schedule in a given set that, for any (estimated) bias of the branch, minimizes the expected execution time. Among other things, it is shown that in some cases the optimal schedule is neither of those resulting from aggressively speculating on any given outcome of the conditional. Our results can be useful in either static or dynamic approaches. We propose a simple run-time estimator for the bias and discuss how to combine it with schedule selection. A number of examples motivate and illustrate the techniques, and show that our approach yields better performance in the case of highly unpredictable branches.

System modeling and presynthesis using timed decision tables

Fri, 17 Dec 2021 00:00:00 +0000

In this paper, we present a tabular model of system behavior called Timed Decision Table (TDT). The TDT model is useful for identifying control-data interaction and in performing control-oriented optimizations. TDTs provide an ideal vehicle to implement source-level optimizations on a given behavioral description in a procedural hardware description language (HDL). These optimizations are used to produce improved synthesis results by simplifying the HDL models using Don't Cares or assertions in particular.

TDT also provides a convenient data structure for extracting information that can be used in further synthesis subtasks to obtain improved synthesis results. One example of this is the information on mutual exclusiveness between a pair of operations, which can be used to optimize operation scheduling.

Source-level control-flow optimization and analysis which extracts useful information from input HDL source for optimization in synthesis process are collectively...

Scheduling with conflicts

Fri, 17 Dec 2021 00:00:00 +0000

In this paper, we consider the scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For the specific graph which arises in the traffic...

Hierarchical models for screening of iron deficiency anemia

Fri, 17 Dec 2021 00:00:00 +0000

We investigate the problem of classifying individuals based on estimated density functions for each individual. Given labelled histograms characterizing red blood cells (RBCs) for different individuals, the learning problem is to build a classifier which can classify new unlabelled histograms into normal and iron deficient classes. Thus, the problem is similar to conventional classification in that there is labelled training data, but different in that the underlying measurements are not feature vectors but histograms or density estimates. We describe a general framework based on probabilistic hierarchical models for modelling such data and illustrate how the model lends itself to classification. We contrast this approach with two other alternatives: (1) directly defining distance between densities using a cross-entropy distance measure, and (2) using parameters of the estimated densities as feature vectors for a standard discriminative classification framework. We evaluate...

ATM modeling example for SpecGen evaluation

Fri, 17 Dec 2021 00:00:00 +0000

In this report we discuss the specification of an ATM cell filter. A behavioral model of the filter is supplied using two specification languages, VHDL, and SpecC, a new language under development by the CADLAB at the University of California, Irvine. A description of the functionality of the filter model is supplied in addition to language features and problems encountered during the specification process. This model to be used as an example for the evaluation of the SpecGen system, a simulation and synthesis environment also under development at the CADLAB.

Probabilistic clustering using hierarchical models

Fri, 17 Dec 2021 00:00:00 +0000

This paper addresses the problem of clustering data when the available data measurements are not multivariate vectors of fixed dimensionality. For example, one might have data from a set of medical patients, where for each patient there are time series, image, text, and multivariate data. We propose a general probabilistic clustering framework for clustering heterogeneous data types of this form. We focus on two-level probabilistic hierarchical models, consisting of a high-level mixture model on parameters and a low-level model for observations. This general framework permits probabilistic clustering of "objects" (sequences, histograms, images, etc) using an extension of the expectation-maximization (EM) algorithm which we derive. We further show that earlier (intuitive) clustering algorithms can be viewed as special cases (approximations) of the framework proposed here. The paper includes several illustrations of the method, including an application to a problem in clustering...

Architecture description language driven verification of in-order execution in pipelined processors

Fri, 17 Dec 2021 00:00:00 +0000

As embedded systems continue to face increasingly higher performance requirements, deeply pipelined processor architectures are being employed to meet desired system performance. System architects critically need modeling techniques that allow exploration, evaluation, customization and validation of different processor pipeline configurations, tuned for a specific application domain. We propose a novel FSM-based modeling of pipelined processors and define a set of properties that can be used to verify the correctness of in-order execution in the pipeline. Our approach leverages the system architect's knowledge about the behavior of the pipelined processor (through our ADL constructs) and thus allows a powerful top-down approach to pipeline verification.

Analysis of high-level address code transformations for programmable processors

Fri, 17 Dec 2021 00:00:00 +0000

Memory intensive applications require considerable arithmetic for the computation and selection of the different memory access pointers. These memory address calculations often involve complex (non)linear arithmetic expressions which have to be calculated during program execution under tight timing constraints, thus becoming a crucial bottleneck in the overall system performance. This paper explores applicability and effectiveness of sourcelevel optimisations (as opposed to instruction-level) for address computations in the context of multimedia. We propose and evaluate two processor-target independent source-level optimisation techniques, namely, global scope operation cost minimisation complemented with loop-invariant code hoisting, and non-linear operator strength reduction. The transformations attempt to achieve minimal code execution within loops and reduced operator strengths. The effectiveness of the transformations is demonstrated with two real-life multimedia application...

An evaluation of linearly combining density estimators via stacking

Fri, 17 Dec 2021 00:00:00 +0000

This paper presents experimental results with both real and artificial data on using the technique of stacking to combine unsupervised learning algorithms. Specifically, stacking is used to form a linear combination of finite mixture model and kernel density estimators for non-parametric multivariate density estimation. The method is found to outperform other strategies such as choosing the single best model based on cross-validation, combining with uniform weights, and even using the single best model chosen by "cheating" and examining the test set. We also investigate in detail how the utility of stacking changes when one of the models being combined generated the data; how the stacking coefficients of the models compare to the relative frequencies with which cross-validation chooses among the models; how stacking performs using L1 and L2 performance measures (for which one must know the true density) rather than log-likelihood; visualization of combined "effective" kernels;...

On the role of connectors in modeling and implementing software architectures

Fri, 17 Dec 2021 00:00:00 +0000

Software architectures are software system models that represent the design of a system at a high level of abstraction. A software architecture typically focuses on the coarse-grained organization of functionality into components and on the explicit representation and specification of inter-component communication. A notable feature of many architectural models (and the languages used to express them) is their representation of communication concerns in explicit model elements, which are typically called connectors. However, there is little consensus yet in the software engineering community on the role of connectors in an architectural model, or even on the necessity of making them first-class model elements. In this paper we demonstrate the utility of explicit connectors in architectural models through a presentation and analysis of an architecture for a meeting scheduler system. We show how the functional abstraction provided by connectors contributes to the mobility, distribution...

Network Border Patrol

Fri, 17 Dec 2021 00:00:00 +0000

The end-to-end nature of Internet congestion control is an important factor in its scalability and robustness. However, end-to-end congestion control algorithms alone are incapable of preventing the congestion collapse and unfair bandwidth allocations created by applications which are unresponsive to network congestion. In this paper, we propose and investigate a new congestion avoidance mechanism called Network Border Patrol (NBP). NBP relies on the exchange of feedback between routers at the borders of a network in order to detect and restrict unresponsive traffic flows before they enter the network. The NBP mechanism is compliant with the Internet philosophy of pushing complexity toward the edges of the network whenever possible. Simulation results show that NBP network whenever possible. Simulation results show that NBP effectively eliminates congestion collapse, and that, when combined with fair queueing, NBP achieves approximately max-min fair bandwidth allocations for...

An approach to large-scale collection of application usage data over the Internet

Fri, 17 Dec 2021 00:00:00 +0000

Empirical evaluation of software systems in actual usage situations is critical in software engineering. Prototyping, beta testing, and usability testing are widely used to refine system requirements, detect anomalous or unexpected system and user behavior, and to evaluate software usefulness and usability. The World Wide Web enables cheap, rapid, and large-scale distribution of software for evaluation purposes. However, current techniques for collecting usage data have not kept pace with the opportunities presented by Web-based deployment. This paper presents an approach and prototype system that makes large-scale collection of usage data over the Internet a practical possibility. A general framework for comparing software monitoring systems is presented and used to compare the proposed approach to existing techniques.

Compiler-directed cache assist adaptivity

Fri, 17 Dec 2021 00:00:00 +0000

The performance of a traditional cache memory hierarchy can be improved by utilizing mechanisms such as a victim cache or a stream buffer (cache assists). The amount of on-chip memory for cache assist is typically limited for technological reasons. In addition, the cache assist size is limited in order to maintain a fast access time. Performance gains from using a buffer or a victim cache, or a combination of the two, varies from program to program as well as within a program. Therefore, given a limited amount of cache assist memory, there is a need and a potential for "adaptivity" of the cache assists i.e., an ability to vary their relative size within the bounds of the cache assist organization and its effect on system performance. Several adaptivity mechanisms are proposed and investigated. The results show that a cache assist that is adaptive at loop level clearly improves the cache memory performance, has low overhead, and can be easily implemented.

Trouble management in DRAM fabrication

Fri, 17 Dec 2021 00:00:00 +0000

This paper probes the fabrication process critical to DRAM (Dynamic Random Access Memory) chip productivity (the product yield), describes the technical structure and technical issues of the fabrication process, and explores the practice of DRAM trouble management dealing with the issues in situ. Analysis of the processes of DRAM trouble management indicates that the push for micro-miniaturization with extremely small physical tolerances creates a tension between two technical requirements: smaller chip size and higher chip robustness. The tension disturbs the balance among heterogeneous objectives of engineering groups. This suggests that the tension leads to a socio-technical resolution of engineering problems in DRAM fabrication. The study also questions existing assumptions about the control of engineering problem solving practice.

Perpetual adaptation of software to hardware : an extensible architecture for providing code optimization as a central system service

Fri, 17 Dec 2021 00:00:00 +0000

Much of the software in everyday operation is not making optimal use of the hardware on which it actually runs, but has been optimized for earlier and often outdated processor versions. This is because users upgrade hardware independently from, and often more frequently than, application software. Moreover, software vendors are generally unable or unwilling to provide multiple versions of the same program that differ only in the processor model specifically targeted during compilation.

The obvious solution to matching a piece of softWcU'e with the actual capabilities of the hardware on which it is about to be executed is to delay code generation until load time. This is the earliest point at which the software can be fine-tuned to specific hardware characteristics such as the latencies of individual instructions and the sizes of the instruction and data caches. An even better match can be achieved by replacing the already executing software at regular intervals by new...

Design of a JBIG encoder using SpecC methodology

Fri, 17 Dec 2021 00:00:00 +0000

This report describes the design of a JBIG encoder, based on the ITU-T Recommendation T.82, using the SpecC system level design methodology being developed at CAD Lab, UC Irvine. We begin with an executable specification in SpecC, and explore design alternatives for the system architecture, and refine the specification into a final communication model where the communication protocols between the system components are defined. In this report, we document the different design stages undergone, and also the results in the process.

VISTA--a visual interface for software reuse in TROMLAB environment

Fri, 17 Dec 2021 00:00:00 +0000

This paper introduces an automatic tool facilitating software reuse. Reusable software components have the potential to increase productivity and reduce development costs. Several research and industrial experience reports show that practicing and achieving high levels of software reuse post technical and managerial challenges. Researchers advocate using component repository technologies and object-oriented development methods within computer-aided software engineering (CASE) environments to address these challenges. Yet additional research is needed to solve them.

Our approach promotes reuse at the specification level rather than merely at the code level. This paper presents our research in elevating reuse capabilities within TROMLAB, a rigorous development environment for real-time reactive systems. We have developed VISTA (Visual Interface for Software Reuse in TROMLAB Applications), which supports automatic search and retrieval of TROMLAB components. VISTA is a visual...

Using critics to support software architects

Fri, 17 Dec 2021 00:00:00 +0000

Software architectures evolve as the result of numerous, interrelated design decisions. Existing approaches to analysis, however, tend to provide feedback only after numerous design decisions have been made. As a result, theydo not directly support the evolutionary nature of the architecture design process or the software architect's decision-making process. In this paper we present an approach to architectural analysis stemming from previous work in domain oriented design environments that is based on critics and criticism control mechanisms. This approach more closely supports evolution and the needs of architects by providing feedback as individual design decisions are beingconsidered. We discuss the theoretical motivations for the critic-based approach, the implementation and management of critics, support for diverse and extensible groups of critics, and the combined use of critics and existing analysis techniques.

Superboundary exchange : a technique for reducing communication in distributed implementations of iterative computations

Fri, 17 Dec 2021 00:00:00 +0000

We introduce a technique for lowering the communication cost in a certain type of distributed application, in which processors perform computation in each time step and must obtain boundary data from their neighbors before they can perform the next time step. A typical example of such an application is solving differential equations using the finite difference method. Our method, which we call SuperBoundary Exchange, consists of sending a larger boundary less often. This results in less frequent data exchange, trading off against larger messages and some redundant computation. We present experimental data showing that our method consistently results in significant speedup in communication-intensive applications, under varying assumption about the balance of computation load among the processors.

Design critiquing systems

Fri, 17 Dec 2021 00:00:00 +0000

Design critiquing systems are a type of intelligent user interface used to support human designers in decision making. This paper places design critics in the larger context of intelligent user interface approaches and surveys several critiquing systems. Each approach and system is evaluated with respect to a five-phase design improvement process. This paper concludes with a summary of the state of the art in critiquing systems and recommendations for future research directions.

Fair queueing with feedback-based policing

Fri, 17 Dec 2021 00:00:00 +0000

End-to-end congestion control is an important reason why the Internet is robust, scalable and simple to use. Unfortunately, purely end-to-end congestion control algorithms are incapable of preventing the unfair bandwidth allocations and congestion collapse caused by unresponsive applications, which are becoming increasingly prevalent in the Internet. In this paper, we propose a new mechanism called Fair Queueing with Feedback-based Policing (FQFP) to address unfair bandwidth allocation and congestion collapse in the Internet. We demonstrate the promise of FQFP through simluations and suggest ways in which FQFP may leverage the mechanisms currently being developed in the context of differentiated services. The FQFP mechanism is compliant with the Internet philosophy of keeping router implementations simple and pushing complexity toward the edges of the network.

Supporting ongoing user involvement in development via expectation-driven event monitoring

Fri, 17 Dec 2021 00:00:00 +0000

Involving end users in the development of interactive systems increases the likelihood those systems will be useful and usable. User involvement, however, is both time and resource intensive. Intemet-and World-Wide-Web-based software release models have magnified these problems. At the same time, these practices have begun to blur the distinction between development and use and, in so doing, have provided developers with unprecedented, and currently underutilized, opportunities for increasing user involvement. We propose an approach — based on expectation-driven event monitoring and expectation agents — that leverages these opportunities to support ongoing user involvement in the software development process.

Design visualization and entry using structural and functional entities

Fri, 17 Dec 2021 00:00:00 +0000

Visualization of design is an important part of the system design process. In practice, systems are often visualized using a combination of structural and functional entities. In this technical report, we describe YAML (Yet Another UML front end) that enables the system designer to enter designs "schematically" using predefined structural and functional objects conforming to UML notation. YAML provides support for modeling objects and a range of object relationships that are crucial to real-life embedded system designs. A YAML design entry can then be automatically translated into a C++ or synthesizable C++ code for simulation and hardware synthesis.

LDFS : a fault-tolerant local disk-based file system for mobile agents

Fri, 17 Dec 2021 00:00:00 +0000

A local disk-based file system, LDFS, is an attractive way to speed up distributed applications. Local file access is much faster than accessing data on remote file servers through the network. LDFS is also scalable, as it does not rely on centralized file servers, and it exploits already existing resources (local disks) to provide storage. However, since individual workstations are less reliable and less available than file servers, LDFS must be made fault tolerant. We present an approach that integrates the LDFS with the distributed application. This is particularly suitable for mobile agent systems, because they can easily migrate to access remote files. LDFS avoids logging of individual file accesses, which are regenerated automatically from application messages. Our experiments show that the overhead of checkpointing with LDFS is generally smaller that with NFS, while access time to files decreases dramatically.

Design of a JPEG encoding system

Fri, 17 Dec 2021 00:00:00 +0000

This report describes the design of a JPEG encoder. The project is a result of a course "System Tools" at Information and Computer Science Department, UC Irvine. The abstract executable specification SpecC is first developed based on a public domain C implementation. Software and hardware estimation is then performed based on which a datapath architecture is selected and RTL code is implemented. Finally, to explore the method of implementing a gate level model, part of the JPEG encoder is refined to the gate level.

SpecC profiler : specification-level exploration tool

Fri, 17 Dec 2021 00:00:00 +0000

SpecC methodology of the system design consists of four major hierarchical levels: specification, architecture, communication, and implementation. The SpecC Profiler is a high-level process within the SpecC methodology, which analyzes system design at the specification level. To achieve fast profiling with satisfactory accuracy, the SpecC Profiler relies on simulation and front-end compiler tools. Each subpart of the specification-level design is associated with the profiling information, targeting computational complexity, storage requirements, and communication complexity of the specification design. In addition, SpecC Profiler predicts the performance, such as number of instructions or execution time.

This report describes the profiler architecture and implementation. The accuracy of the profiler is asserted by comparing the performance predicted by the profiler with the results of simulated execution of different applications, like JPEG and Vocoder.

TestTalk language reference (version 0.1)

Fri, 17 Dec 2021 00:00:00 +0000

TestTalk language reference (version 0.1)

Collecting usage data and user feedback on a large scale to inform software development

Fri, 17 Dec 2021 00:00:00 +0000

The two most commonly used techniques for evaluating the fit between application design and use - namely, usability testing and beta testing with user feedback - suffer from a number of limitations that restrict evaluation scale (in the case of usability tests) and data quality (in the case of beta tests). They also fail to provide developers with an adequate basis for: (1) assessing the impact of suspected problems (and proposed solutions) on users at large, and (2) deciding where to focus scarce development and evaluation resources to maximize the benefit for users at large. This article describes an approach to usage data and user feedback collection that addresses these limitations to provide developers with a complementary source of usage - and usability-related information. This research has been subjected to a number of evaluative activities including: (1) the development of three research prototypes at NYNEX Corporation, the University of Colorado, and the University...

AMRM prototype board design and implementation

Fri, 17 Dec 2021 00:00:00 +0000

AMRM prototype board design and implementation

Architecture and compiler for an ANSI C-targeting reduced instruction set core for embedded systems (ANTARES)

Fri, 17 Dec 2021 00:00:00 +0000

In this document the architecture and instruction set of a RISC-Core is designed in a top down fashion so ANSI-C-programs are easily processed on the core giving optimal performance with a minimum of architectural features. Severe constraints have to be obeyed concerning register size, instruction-coding and addressing, limitation resulting from the goal of a small area of the core and easy memory interfacing. Compiler design and architecture engineering is done concurrently, influencing each other and showing strong interdependence of instruction set, architecture and compiler. The LCC- retargetable compiler is used as a basis and the machine description file is elaborated. A retargetable assembler is taken from an existing design with a new instruction description file. The core is simulated with an existing, retargetable C- based simulator.

Agents for collecting application usage data over the Internet

Fri, 17 Dec 2021 00:00:00 +0000

Empirical evaluation of software systems in actual use is critical in software engineering. Prototyping, beta testing, and usability testing are widely employed to refine system requirements, to detect anomalous or unexpected system and user behavior, and to evaluate software usefulness and usability. The World Wide Web enables cheap, rapid, and large-scale distribution of software for evaluation purposes. However, current techniques for collecting usage data have not kept pace with the opportunities presented by Web-based deployment. This paper presents an agent-based approach and prototype system that makes large-scale collection of usage data over the Internet a practical possibility.

ADLscope : an automated specification-based unit testing tool

Fri, 17 Dec 2021 00:00:00 +0000

Specification-based testing is important because it relates directly to what the program is supposed to do and can detect certain errors that are often not detected by traditional codebased testing techniques such as branch coverage and statement coverage. We have developed an automated testing tool, called ADLscope, that utilizes the formal specification of a program unit as the basis for test coverage measurement. A tester uses ADLscope to test Application Programmatic Interfaces (APIs) written inthe C programming language. The API must be formally specified in the Assertion Definition Language (ADL), a language developed at Sun Microsystems Laboratories. The tester uses ADLscope to generate coverage conditions from a program's ADL specifications. When the API is tested, ADL scope automatically measures how many of the coverage conditions have been covered by the tests. An uncovered condition usually means that certain aspects ofthe specification have not been thoroughly...

Stand-alone messages : a step towards component-oriented programming languages

Fri, 17 Dec 2021 00:00:00 +0000

We are concerned with the design of programming languages that support the paradigm of component-oriented programming. Languages based on the accepted idea of combining modular and object-oriented concepts fail to provide adequate support. We argue that messages should be separated from methods to address this shortcoming. We introduce the concept of stand-alone messages, give examples for its utility, and compare it to related approaches and language constructs. Besides leading to interesting insights on the interaction of modular and object-oriented concepts, we believe that stand-alone messages also provide a useful basis for further research on component-oriented programming· languages.

Interface synthesis at behavioral RTL

Fri, 17 Dec 2021 00:00:00 +0000

This report describes the interface synthesis methodology at behavioral RTL, based on handshaking protocol using the the SpecC system level design language, which has been developed at CAD Lab., UC Irvine. We use the parity encoder with two communicating behaviors as example. To synchronize two communicating behaviors, we show the methodology to generate the handshaking protocol and transducer.

System-level timing-constrained scheduling

Fri, 17 Dec 2021 00:00:00 +0000

HLS scheduling algorithms can not be applied on system-level synthesis due to the following problems:

- The control-step is not available at system-level.

- Mixed concurrent and exclusive execution flows

- Synchronization among objects scheduled

- Execution time of objects scheduled may not be determined until run-time.

In this paper, we present a data-structure to specify the Input for system-level scheduling, and a system-level timing-constrained scheduling algorithm. Static scheduling, which has no OS overhead and better system WCET, is used. The algorithm presented can obtain near-optimal solutions within acceptable and predictable CPU time.

Enabling logical structure support in the dynamic distributed environment

Fri, 17 Dec 2021 00:00:00 +0000

Coordination protocols are an essential part of every distributed system. In general, centralized protocols are simpler and more efficient than distributed ones. However, as a distributed system gets large, the bottleneck of the central coordinator renders protocols relying on centralized coordination inefficient. To solve this problem, hierarchical coordination can be used. This solves the scalability problem of the algorithms relying on centralized coordinations, since the performance of hierarchical coordination degrades logarithmically with the number of participating processes.

In this paper we present a mechanism that automatically organizes processes in a hierarchy and maintains the hierarchy in the presence of node failures, and addition and removal of processes in the system. The proposed scheme is simple and general, and can concurrently support multiple logical structures, such as a ring, a hypercube, or a mesh.

A study of out-of-order completion for the MIPS R10K superscalar processor

Fri, 17 Dec 2021 00:00:00 +0000

Instruction level parallelism (ILP) improves performance for VLIW, EPIC, and Superscalar processors. Out-of-order execution improves performance further. The advantage of out-of-order execution is not fully utilized due to in-order completion. In this report we study the performance loss due to in-order completion for MIPS R10000 processor.

The SpecC methodology

Fri, 17 Dec 2021 00:00:00 +0000

This report describes the SpecC methodology for system-level embedded system design. The methodology consists of a set of well-defined tasks and design models which allow the easy insertion and reuse of intellectual property. Starting from the abstract executable specification written in SpecC different design alternatives concerning the system architecture (components and communication) can be explored and the specification is gradually refined and mapped to a final HW/SW implementation such that the constraints are satisfied optimally. The final hand-off for manufacturing includes software code compiled for the processors and the RTL descriptions for hardware synthesis.

Design of a JPEG encoder using SpecC methodology

Fri, 17 Dec 2021 00:00:00 +0000

This report describes the design of a JPEG encoder, using the SpecC system level design methodology developed at CAD lab, UC Irvine. We first begin with an executable specification model in SpecC, and then refine the specification model into a architecture model which accurately reflects the system architecture. Based on the architecture model, a communication model where the communication protocols between the system components are defined are developed. Finally, we refine the communication model of the DCT block into the implementation model, which is the lowest level of abstraction in the SpecC methodology. This Project is a result of a course "System Tools" at Information and Computer Science Department, UC Irvine.

The SpecC+ language

Fri, 17 Dec 2021 00:00:00 +0000

In this report, we discuss the characteristics necessary for specifying embedded hardware-software systems. We describe the constructs needed to capture these characteristics and propose a new C based specification language to describe heterogeneous embedded systems.

SpecC for beginners : the example of a sounding dice

Fri, 17 Dec 2021 00:00:00 +0000

In this document the SpecC-language is demonstrated in a low complexity example with main features of the laguage explained and evaluated. Purpose of this document is to give beginners a first feeling for the language constructs and its usage in actual modelling. Allthough the language was not developed for these small tasks in general, it is well suited to cover all kind of modelling tasks with the existing semantic. The example consist of several finite state maschines connected and communicating with each other. The sounding dice example is taken from an existing design out of the authors course, normal used for student education in the VHDL-dasses of the University of Applied Science, Offenburg, Germany.