Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 30 of 41
Full-Text Articles in Engineering
Efficiently Computing {Phi}-Nodes On-The-Fly, Ron K. Cytron, Jeanne Ferrante
Efficiently Computing {Phi}-Nodes On-The-Fly, Ron K. Cytron, Jeanne Ferrante
All Computer Science and Engineering Research
Recently, Static Single Assignment Form and Sparse Evaluation Graphs have been advanced for the efficient solution of program optimization problems. Each method is provided with an initial set of flow graph nodes that inherently affect a problem's solution. Other relevant nodes are those where potentially disparate solutions must combine. Previously, these so-called {phi}-nodes were found by computing the iterated dominance frontiers of the initial set of nodes, a process that could take worst case quadratic time with respect to the input flow graph. In this paper we present an almost-linear algorithm for detemining exactly the same set of {phi}-nodes.
Dynamic Reconfiguration With I/O Abstraction, Bala Swaminathan, Kenneth J. Goldman
Dynamic Reconfiguration With I/O Abstraction, Bala Swaminathan, Kenneth J. Goldman
All Computer Science and Engineering Research
Dynamic reconfiguration is explored in the context of I/O abstraction, a new programming model that defines the communication structure of a system in terms of connections among well-defined data interfaces for the modules in the system. The properties of I/O abstraction, particularly the clear separation of computation from communication and the availability of a module's state information, help simplify the reconfiguration strategy. Both logical and physical reconfiguration are discussed, with an emphasis on a new module migration mechanism that (1) takes advantage of the underlying I/O abstraction model, (2) avoids the expense and complication of state extraction techniques, (3) minimizes …
Approximation Algorithms For Configuring Hierarchical Nonblocking Communication Networks, J. Andrew Fingerhut
Approximation Algorithms For Configuring Hierarchical Nonblocking Communication Networks, J. Andrew Fingerhut
All Computer Science and Engineering Research
A framework is given for specifying nonblocking traffic limits in a connection-oriented communications network. In this framework, connections may be point-to-point or mutlipoint, and the data rates may vary from one connection to another. The traffic limits may be "flat", or they may also be hierarchical, representing communities of interest within the network that have higher traffic among themselves than with the rest of the network. The communication networks are constructed from switches (or nodes) and trunks, which connect pairs of switches. This framework is intended to model Asynchronous Transfer Mode (ATM) networks and traffic. We present a way of …
Segmentation/Recognition Of Hand-Written Numeral Characters, Khalid Sherdil
Segmentation/Recognition Of Hand-Written Numeral Characters, Khalid Sherdil
All Computer Science and Engineering Research
This thesis describes a number of techniques for segmenting non-cursive handwritten digits into individual characters. It strongly emphasizes on a recognition-segmentation algorithm, which uses the linear regression method to recognize those strokes which consist of one or more straight-lined parts. A new method of sampling the pen data according to the pen speed, hence giving a more uniform points concentratino distribution, is also introduced. It is shown how several of our segmenting techniques, such as relative stroke lengths, relative stroke positions, order of stroke entry, stroke direction, stroke intersection, etc. can be combined to yield success results of about 95%.
Symphony: A Hardware, Operating System, And Protocol Processing Architecture For Distributed Multimedia Applications, Andreas D. Bovopoulos, R. Gopalakrishnan, Saied Hosseini
Symphony: A Hardware, Operating System, And Protocol Processing Architecture For Distributed Multimedia Applications, Andreas D. Bovopoulos, R. Gopalakrishnan, Saied Hosseini
All Computer Science and Engineering Research
This paper explores the architectural requirements for computers to be able to process multimedia data streams such as video and audio. The I/O subsystem is shown to be a bottleneck, and a network backplane approach is suggested to alleviate this. The need to provide end-to-end performance guarantees requires predictable performance of intra-machine communication, and a schedulable bus with reservation is proposed to achieve this. In addition this requires operating system (OS) mechanisms to negotiate and enforce QoS requirements of applications. A real-time microkernel executive is proposed for each autonomous unit. Requirements for real-time microkernel exeutive is proposed for each autonomous …
Clothespins On Timelines: Utilities And The Interval Representation Of Time, R. P. Loui, Jersey Chen
Clothespins On Timelines: Utilities And The Interval Representation Of Time, R. P. Loui, Jersey Chen
All Computer Science and Engineering Research
We discuss the problem of representing utility in planning systems that are based on Allen's [83] popular ontology for planning, which represents actions and events as time intervals. We identify a small number of primitive functions on time intervals which may be helpful in representing preference and also in eliminating dominated actions. Assuming that utility can be decomposed to take advantage of these primitives, these functions provide one solution to the problem of specifying utility in such expressive planning languages. We identify a restricted class of utility expressions that generate linear programming problems. The contribution is not deep, but is …
Learning Unions Of Boxes With Membership And Equivalence Queries, Paul W. Goldberg, Sally A. Goldman, H. David Matthias
Learning Unions Of Boxes With Membership And Equivalence Queries, Paul W. Goldberg, Sally A. Goldman, H. David Matthias
All Computer Science and Engineering Research
We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. The first algorithm receives at most s*d counterexamples and uses time and membership queries polynomial in s and logn for d any constant. Further, all equivalence queries made can be formulated as the union of O(s*d*log(s)) axis-parallel boxes. Next, we introduce a new complexity measure that better captures the complexity of a union of boxes than simply the number of boxes and dimensions. …
Real-Time Admission Control Algorithms With Delay And Loss Guarantees In Atm Networks, Apostolos Dailianas, Andreas D. Bovopoulos
Real-Time Admission Control Algorithms With Delay And Loss Guarantees In Atm Networks, Apostolos Dailianas, Andreas D. Bovopoulos
All Computer Science and Engineering Research
A multimedia ATM network is shared by media streams with different performance requirements. For media streams such as file transfers, the preservation of bursts and the provision of guarantees for loss probability at the burst level is of primary importance, while, for media streams such as voice, loss guarantees at the cell level are sufficient. Continuous media have stringent delay jitter requirements. Finally, some applications require loss-free transmission. In this paper, the first complete traffic management scheme for multimedia ATM networks is introduced. The traffic management scheme supports four different classes of traffic, each of which has different performance requirements …
An Optimal Nonblocking Multicast Virtual Circuit Switch, Jonathan S. Turner
An Optimal Nonblocking Multicast Virtual Circuit Switch, Jonathan S. Turner
All Computer Science and Engineering Research
This paper describes an architecture for a multicast virtual circuit switch using cell recycling. This is the first nonblocking switch architecture that is optimal in both the switching network complexity and the amount of memory required for multicast address translation. Furthermore, it is optimal in the amount of effort required for multicast connection modification. This architecture makes it both technically and economically feasible to construct the large switching systems that will ultimately be needed for wide scale deployment of Broadband ISDN to residential users. In particular, we estimate that systems with tens of thousands of 620 Mb/s ports can be …
The Dim System: Turn-Taking In Dyadic Telephone Dialogues, Umesh Berry, Anne Johnstone
The Dim System: Turn-Taking In Dyadic Telephone Dialogues, Umesh Berry, Anne Johnstone
All Computer Science and Engineering Research
The analysis of human conversations has revealed that the design of interfaces using spoken dialogue must differ radically from those using written communication. Such characteristics as prosody, confirmations, echoes, and other speech phenomena must be considered. This work is a step in that direction. Prosodic, syntactic and semantic information from actual human dialogues has been used to build a turn-taking model empirically for dydadic telephone dialogues. The ability to predict completion of turns has been the biggest motivating factor in the development of this model. The design and evaluation of the model are presented in this report.
Distributed Computing Systems And Checkpointing, Ken Wong, Mark Franklin
Distributed Computing Systems And Checkpointing, Ken Wong, Mark Franklin
All Computer Science and Engineering Research
This paper examines the performance of synchronous checkpointing in a distributed computing environment with and without load redistribution. Performance models are developed, and optimum checkpoint intervals are determined. The analysis extends earlier work by allowing for multiple nodes, state dependent checkpoint intervals, and a performance metric which is coupled with failure-free performance and the speedup functions associated with implementation of parallel algorithms. Expressions for the optimum checkpoint intervals for synchronous checkpointing with and without load redistribution are derived and the results are then used to determine when load redistribution is advantageous.
Effective Loss Of Multiplexed Atm Cell Streams, Seyyed M-R Mahdavian, Andreas D. Bovopoulos
Effective Loss Of Multiplexed Atm Cell Streams, Seyyed M-R Mahdavian, Andreas D. Bovopoulos
All Computer Science and Engineering Research
Cell loss is an inherent problem of ATM networks. The magnitude of the service degeneration caused by cell loss depends on the application and loss distribution. This paper introduces a new performance criterion, called effective loss, which can quantitatively measure this degradation. Effective loss is particularly suitable for block-oriented transmissions, such as file transfer applications, but can also be applied to a broad range of other applications. In this paper the effective loss measure is applied to the study of the effectiveness of bandwidth reservation mechanisms in an ATM multiplexer. Numerical results demonstrate circumstances under which bandwidth reservation improves performance …
Representing And Learning Propositional Logic In Symmetric Connectionist Networks, Gadi Pinkas
Representing And Learning Propositional Logic In Symmetric Connectionist Networks, Gadi Pinkas
All Computer Science and Engineering Research
The chapter presents methods for efficiently representing logic formulas in connectionist networks that perform energy minimization. Algorithms are given for transforming any formula into a network in linear time and space and for learning representations of unknown formulas by observing examples of satisfying truth assignments. The relaxation process that underlies networks of energy minimization reveals an efficient hill climbing algorithm for satisfiability problems. Experimental results indicate that the parallel implementation of the algorithm with give extremely good average-case performance, even for large-scale, hard satisfiability problems (randomly generated).
Clocked And Asynchronous Instruction Pipelines, Mark A. Franklin, Tienyo Pan
Clocked And Asynchronous Instruction Pipelines, Mark A. Franklin, Tienyo Pan
All Computer Science and Engineering Research
Clocked (synchronous) and self-timed (asynchronous) represent the two prinicipal methodologies associated with timing control and synchronization of digital systems. In this paper, clocked and the asynchronous instruction pipelines are modeled and compared. The approach which yields the best performance is dependent on technology parameters, operating range and pipeline algorithm characteristics. Design curves are presented which permit selection of the best approach for a given application and technology environment.
The Dim System: Woz Simulation Results - Phase Ii, Anne Johnstone, Umesh Berry, Tina Nguyen
The Dim System: Woz Simulation Results - Phase Ii, Anne Johnstone, Umesh Berry, Tina Nguyen
All Computer Science and Engineering Research
We report an experiment designed to compare human-human spoken dialogues with human-computer spoken dialogue. Our primary purpose was to collect data on the kinds of protocols that were used to control the interaction. Three groups of 12 subjects each were asked to complete tasks over the phone. These tasks involved the use of custom-calling features such as call-forwarding and speed-dialing. The experimental procedure was a new variation on the Wizard of Oz (WOZ) technique that allowed much clearer comparisons to be made between human-human and human-computer interactions. Subjects in the Operator Group were told they were talking to a human …
The N-Body Problem: Distributed System Load Balancing And Performance Evaluation, Vasudha Govindan, Mark A. Franklin
The N-Body Problem: Distributed System Load Balancing And Performance Evaluation, Vasudha Govindan, Mark A. Franklin
All Computer Science and Engineering Research
In this paper, the N-body simulation problem is considered, its parallel implementation described, its execution time performance is modeled and compared with measured results, and two alternative load balancing algorithms for enhancing performance investigated. Parallel N-body techniques are widely applied in various fields and possess characteristics that challenge the computation and communication capabilities of parallel computing systems and are therefore good candidates for use as parallel benchmarks. Performance models may be used to estimate the performance of an algorithm on a given system, identify performance bottlenecks and study the performance implications of several algorithm are system enhancements. In this paper, …
Clinical Decision-Support Systems In Radiation Therapy, Nilesh L. Jain, Michael G. Kahn
Clinical Decision-Support Systems In Radiation Therapy, Nilesh L. Jain, Michael G. Kahn
All Computer Science and Engineering Research
Computers have been used in radiation therapy since the early 1960s to perform dose calculations. In the last decade, researchers have developed computer-based clinical decision-support systems for assisting in different decision-making tasks in radiation therapy. This paper reviews eleven prototype systems developed for target volume delineation, treatment planning, treatment plan evaluation, and treatment machine diagnosis. The advent of three-dimensional (3D) conformal radiation therapy (CRT) provides radiation oncologists with the opportunity to consider innovative beam arrangements which were not possible in two-dimensional class solutions. The difficulty of manually generating the thousands of clinically plausible 3D treatment plans calls for the use …
The Study Of Computer Science Concepts Through Game Play, Benjamin M. Weber
The Study Of Computer Science Concepts Through Game Play, Benjamin M. Weber
All Computer Science and Engineering Research
No abstract provided.
The Programmers' Playground: I/O Abstraction For Heterogeneous Distributed Systems, Kenneth J. Goldman, Michael D. Anderson, Bala Swaminathan
The Programmers' Playground: I/O Abstraction For Heterogeneous Distributed Systems, Kenneth J. Goldman, Michael D. Anderson, Bala Swaminathan
All Computer Science and Engineering Research
I/O abstraction is offered as a new high-level approach to interprocess communication. Functional components of a concurrent system are written as encapsulated modules that act upon local data structures, some of which may be published for external use. Relationships among modules are specified by logical connections among their published data structures. Whenever a module updates published data, I/O takes place implicitly according to the configuration of logical connections. The Programmer's Playground, a software library and run-time system supporting I/O abstraction, is described. Design goals include high-level communication among programs written in multiple programming languages and the uniform treatment of discrete …
A Unified Model For Shared-Memory And Message-Passing Systems, Kenneth Goldman, Katherine Yelick
A Unified Model For Shared-Memory And Message-Passing Systems, Kenneth Goldman, Katherine Yelick
All Computer Science and Engineering Research
A unified model of distributed systems that accomodates both shared-memory and message-passing communication is proposed. An extension of the I/O automaton model of Lynch and Tuttle, the model provides a full range of types of atomic accesses to shared memory, from basic reads and writes to read-modify-write. In addition to supporting the specification and verification of shared memory algorithms, the unified model is particularly helpful for proving correspondences between atomic shared objects and invocation-response systems and for proving the correctness of systems that contain both message passing and shared memory (such as a network of shared-memory multiprocessors or a distributed …
Human And Machine Cognition Workshop Papers 1989, 1991, 1993, R. P. Loui
Human And Machine Cognition Workshop Papers 1989, 1991, 1993, R. P. Loui
All Computer Science and Engineering Research
No abstract provided.
A Design For Reasoning With Policies, Prrecedents And Rationales, Ronald P. Loui, Jeff Norman, Jon Olson, Andrew Merrill
A Design For Reasoning With Policies, Prrecedents And Rationales, Ronald P. Loui, Jeff Norman, Jon Olson, Andrew Merrill
All Computer Science and Engineering Research
No abstract provided.
Reasoning About Synchrony Illustrated On Three Models Of Concurrency, Gruia-Catalin Roman, Jerome Plun
Reasoning About Synchrony Illustrated On Three Models Of Concurrency, Gruia-Catalin Roman, Jerome Plun
All Computer Science and Engineering Research
This paper presents a model of concurrency (Dynamic Synchrony) whose distinctive feature is a novel formal treatment of synchronization. Synchrony is defined as the coordinated execution of two or more actions. The dynamic aspect comes from the fact that the definition of which actions must be executed synchronously can change freely during the execution of the program. This unique modeling capability comes with a UNITY-stype assertional logic that can be applied to program verification and derivation. This paper shows that the proposed proof logic can be used to verify programs expressed using other models of foncurrency without having to translate …
The Washington University Multimedia System, William D. Richard, Jerome R. Cox Jr., Brian Gottlieb, Ken Krieger
The Washington University Multimedia System, William D. Richard, Jerome R. Cox Jr., Brian Gottlieb, Ken Krieger
All Computer Science and Engineering Research
The Washington University Multimedia System (MMS) is a complete multimedia system capable of transmitting and receiving video, audio, and radiological images, in addition to normal network traffic, over the Washingon University broadband ATM network. The MMS consists of an ATMizer and three multimedia subsystems. The ATMizer implements the host interface, the interface to the ATM network, and the interface to the three multimedia subsystems. The video sybsystem encodes and decodes JPEG compressed video using two hardware compression engines. The audio subsystem encodes and decodes CD-quality stereo audio. The high-speed radiological image subsystem reformats radiological image data transmitted by a dedicated …
A Fault Tolerant Connectionist Architecture For Construction Of Logic Proofs, Gadi Pinkas
A Fault Tolerant Connectionist Architecture For Construction Of Logic Proofs, Gadi Pinkas
All Computer Science and Engineering Research
This chapter considers the problems of expressing logic and constructing proofs in fault tolerant connectionist networks that are based on energy minimalism. Given a first-order-logic knowledge base and a bound k, a symmetric network is constructed (like a Boltzman machine or a Hopfield network) that searches for a proof for a given query. If a resolution-based proof of length no longer than k exists, then the global minima of the energy function that is associated with the network represent such proofs. If no proof exist then the global minima indicate the lack of a proof. The network that is generated …
Research Proposal: Preference Acquisition Through Reconciliation Of Inconsistencies, Nilesh L. Jain
Research Proposal: Preference Acquisition Through Reconciliation Of Inconsistencies, Nilesh L. Jain
All Computer Science and Engineering Research
The quality of performance of a decision-support system (or an expert system) is determined to a large extent by its underlying preference model (or knowledge base). The difficulties in preference and knowledge acquisition make them a major focus of current research in decision-support and expert systems. Researchers have used various concepts to develop promising acquisition techniques. One of the concepts used is knowledge maintenence where the knowledge base is changed in response to incorrect or inadequate performance by the expert system. This dissertation investigates a preference acquisition technique based on the reconciliation of inconsistencies between the preference model and the …
Objective Evaluation Of Radiation Treatment Plans, Nilesh L. Jain, Michael G. Kahn
Objective Evaluation Of Radiation Treatment Plans, Nilesh L. Jain, Michael G. Kahn
All Computer Science and Engineering Research
The evaluation of radiation treatment plans involves making trade-offs among doses delivered to the tumor volumes and nearby normal tissues. Evaluating state-of-the-art three-dimensional (3D) plans is a difficult task because of the huge amount of planning data that needs to be deciphered. Multiattribute utility theory provides a methodology for specifying trade-offs and selecting the optimal plan from many competing lans. Using multiattribute utility theory, we are developing a clinically meaningful objective plan-evaluation model for 3D radiation treatment plans. Our model incorporates three of the factors involved in radiation treatment evaluation - treatment preferences of the radiation oncologist, clinical condition of …
Supervised Competitive Learning With Backpropagation Network And Fuzzy Logic, Takayuki Dan Kimura, Thomas H. Fuller Jr., Ce Wang
Supervised Competitive Learning With Backpropagation Network And Fuzzy Logic, Takayuki Dan Kimura, Thomas H. Fuller Jr., Ce Wang
All Computer Science and Engineering Research
SCL assembles a set of learning modules into a supervised learning system to address the stability-plasticity dilemma. Each learning module acts as a similarity detector for a prototype, and includes prototype resetting (akin to that of ART) to respond to new prototypes. Here (Part I) we report SCL results using back-propagation networks as the learning modules. We used two feature extractors: about 30 energy-based features, and a combination of energy-based and graphical features (about 60). ACL recognized 96% (energy) and 99% (energy/graphical) of test digits, and 91% (energy) and 96% (energy/graphical) of test letters. In the accompanying paper (Part II), …
Teaching A Smarter Learner, Sally A. Goldman, H. David Mathias
Teaching A Smarter Learner, Sally A. Goldman, H. David Mathias
All Computer Science and Engineering Research
We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the non-intuitive aspects of otehr models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we present other general results relating this model of teaching to …
Improving The Speed Of A Distributed Checkpointing Algorithm, Sachin Garg, Kenneth F. Wong
Improving The Speed Of A Distributed Checkpointing Algorithm, Sachin Garg, Kenneth F. Wong
All Computer Science and Engineering Research
This paper shows how Koo and Toueg's distributed checkpointing algorithm can be modified so as to substantially reduce the average message volume. It attempts to avoid O(n{squared}) messages by using dependency knowledge to reduce the number of checkpoint request messages. Lemmas on consistency and termination are also included.