Digital Commons Network^™

Improving Circuit Testability By Clock Control, Kent L. Einspahr, Sharad C. Seth, Vishwani D. Agrawal

School of Computing: Conference and Workshop Papers

The testability of a sequential circuit can be improved by controlling the clocks of individual storage elements during testing. We propose several clock control strategies derived from an analysis of the circuit, its S-graph structure, and its function. Through examples we show how the number of clocks affects the circuit’s testability. It is shown that if certain flip-flops (FFs) are scanned (or otherwise initialized), the remaining FFs can be controlled and initialized to any arbitrary state using the clock control. We derive a controllability graph and use it to assign clocks to FFs and to schedule the clocks to set …

A User Interface For The Visualization And Manipulation Of Arrays, Jennifer Leopold, A. Ambler

Computer Science Faculty Research & Creative Works

The success of spreadsheets has shown that a visual representation of a 2D array greatly facilitates solving certain problems. However, spreadsheets are not general-purpose programming environments and are not suited to many problems that might naturally be solved using multi-dimensional arrays. Furthermore, spreadsheets employ a textual notation for cell references in formulas. This notation, which adds to the programmer''s burden by distinguishing between relative and absolute addressing, can be difficult to understand and is error-prone even for the most experienced users. In this paper, we present a user interface for multi-dimensional arrays within Formulate, a form-based visual programming language. This …

Compositional Reasoning Is Not Possible In Determining The Solvability Of Consensus, Prasad Jayanti

Computer Science Technical Reports

Consensus, which requires processes with different input values to eventually agree on one of these values, is a fundamental problem in fault-tolerant computing. We study this problem in the context of asynchronous shared-memory systems. In our model, shared-memory consists of a sequence of cells and supports a specific set of operations. Prior research on consensus focussed on its solvability in shared-memories supporting specific operations. In this paper, we investigate the following general question: Let OP1 and OP2 be any two sets of operations such that each set includes read and write operations. Suppose there is no consensus protocol for N …

Control Uniqueness In Reconstructability Analysis, Martin Zwick

Complex Systems Faculty Publications and Presentations

When the reconstructability analysis of a directed system yields a structure in which a generated variable appears in more than one subsystem, information from all of the subsystems can be used in modeling the relationship between generating and generated variables. The conceptualization and procedure proposed here is discussed in relation to Klir's concept of control uniqueness.

Introduction To Multiprocessor I/O Architecture, David Kotz

Dartmouth Scholarship

The computational performance of multiprocessors continues to improve by leaps and bounds, fueled in part by rapid improvements in processor and interconnection technology. I/O performance thus becomes ever more critical, to avoid becoming the bottleneck of system performance. In this paper we provide an introduction to I/O architectural issues in multiprocessors, with a focus on disk subsystems. While we discuss examples from actual architectures and provide pointers to interesting research in the literature, we do not attempt to provide a comprehensive survey. We concentrate on a study of the architectural design issues, and the effects of different design alternatives.

Analogy-Making: A Connectionist Exploration, Doug Blank

Computer Science Faculty Research and Scholarship

No abstract provided.

Behavior-Based Analogy-Making, Doug Blank

Computer Science Faculty Research and Scholarship

No abstract provided.

Information Systems In Non-Profit Organizations: Enhancing Performance Through Online Help, Robert H. Lane

CCAC Theses and Dissertations

The purpose of this dissertation is to focus attention on the problems which non-profit organizations face in dealing with employee dissatisfaction and turnover among clerical staff whose principal responsibility is data entry. To address the problem, a presentation on the background, a discussion of the managerial and information systems implications, and an end-user needs assessment culminated in the development of an online help system for an IDM AS/400-based membership management package.

The system enables the data entry staff to easily locate the answers to most of their commonly asked questions without leaving their workstation, thus reducing the need for as …

An Assessment Of Asynchronous Transfer Mode (Atm) Training For Educators, Dan A. Niswander

CCAC Theses and Dissertations

The purpose of this dissertation was to develop and evaluate a hypertext-based training tutorial/guide on asynchronous transfer mode (ATM) technology for use by school district educators and technology planners. A review of literature indicated training needs on new broadband technologies were not being adequately met from the point of view of an educational environment. An interactive hypertext solution was proposed, designed, and developed based on the needs of adult learners. An analysis of these needs indicated adults prefer flexibility in navigating between training topics as well as in the pace of material presentation, that is, whether to proceed at a …

Low Cost Video For Distance Education, Michael J. Simpson

CCAC Theses and Dissertations

A distance education system has been designed for Nova Southeastern University (NSU) . The design was based on emerging low cost video technology. The report presented the design and summarizes existing distance education efforts and technologies.

The design supported multimedia electronic classrooms, and enabled students to participate in multimedia classes using standard telephone networks. Results were presented in three areas: management, courseware, and, systems.

In the area of management, the report recommended that the University separately establish, fund, and staff the distance education project. Supporting rationale was included.

In the area of courseware, the importance of quality courseware was highlighted. …

Improved Data Migration And Processing For Projecting The Financial Aid Budget, Jeffery L. Olson '96

Honors Projects

Last fall, I again resumed work on the budget projection model that encompassed five spreadsheets. Four of these sheets generated a set of statistical averages for each class. Each one consisted of 101 columns containing data for the four-to five-hundred students(rows) in each class. In addition, a fifth sheet used these averages to generate a highly accurate prediction for expenditures in the upcoming year. However, there were two main areas of improvement that became readily apparent: importing data and the sheets themselves.

Analysis Of Mpeg Compressed Video Traffic, Jerome R. Cox Jr., O. Matthew Beal

All Computer Science and Engineering Research

This paper outlines a study of MPEG compressed video sequences and simulation of multiplexed video traffic in the ATM environment. A number of statistical characteristics including autocorrelation and variance of MPEG-1 compressed video sequences are used to characterize the 16 sample traces used in this study. From these measurements, a preliminary model is developed which utilizes basic measurements of the individual component video sequences to predict bandwidth requirements and cell loss of the multiplexed video traffic.

Design And Implementation Of A Practical Security-Conscious Electronic Polling System, Lorrie Faith Cranor, Ron K. Cytron

All Computer Science and Engineering Research

We present the design and implementation of Sensus, a practical, secure and private system for conducting surveys and elections over computer networks. Expanding on the work of Fujioka, Okamoto, and Ohta, Sensus uses blind signatures to ensure that only registered voters can vote and that each registered voter only votes once, while at the same time maintaining voters' privacy. Sensus allows voters to verify independently that their votes were counted correctly, and anonymously challenge the results should their votes be miscounted. We outline seven desirable properties of voting systems and show that Sensus satisfied these properties well, in some cases …

Design Of Nonblocking Atm Networks, J. Andrew Fingerhut, Rob Jackson, Subhash Suri, Jonathan S. Turner

All Computer Science and Engineering Research

This paper considers the problem of designing ATM networks that are nonblocking with respect to virtual circuit requests, subject to specified constraints on the traffic. In this paper, we focus on global traffic constraints that simply limit the total entering and exiting traffic at each switching system. After reviewing prior results for linear link costs, we introduce a more realistic link cost model, and develop a number of results using it. We also describe a technique for converting tree-structured networks to nonblocking hierarchical networks satisfying limits on the capacity of any single switch.

Bringing Real-Time Scheduling Theory And Practice Closer For Multimedia Computing, R. Gopalakrishnan, Guru M. Parulkar

All Computer Science and Engineering Research

This paper seeks to bridge the gap between theory and practice of real-time scheduling in the domain of multimedia computer systems. We show that scheduling algorithms that are good in theory, often have practical limitations. However when these algorithms are modified based on practical considerations, existing theoretical results cannot be used as they are. In this paper we motivate the need for new scheduling schemes for multimedia protocol processing, and demonstrate their real-time performance in our prototype implementation. We then explain the observed results by analysis and measurement. More specifically, we show that using strict preemption can introduce overheads in …

Mobile Unity: Reasoning And Specification In Mobile Computing, Gruia-Catalin Roman, Peter J. Mccann

All Computer Science and Engineering Research

Mobile computing represents a major point of departure from the traditional distributed computing paradigm. The potentially very large number of independent computing units, a decoupled computing style, frequent disconnections, continuous position changes, and the location-dependent nature of the behavior and communication patterns present designers with unprecedented challenges in the areas of modularity and dependability. So far, the literature on mobile computing is dominated by concerns having to do with the development of protocols and services. This paper complements this perspective by considering the nature of the underlying formal models that will enable us to specify and reason about such computations. …

On The Performance Of Early Packet Discard, Maurizio Casoni, Jonathan S. Turner

All Computer Science and Engineering Research

In a previous paper [3], one of the authors, gave a worst-case analysis for the Early Packet Discard (EPD) technique for maintaining packet integrity during overload in ATM switches. This analysis showed that to ensure 100% goodput during overload under worst-case conditions, requires a buffer with enough storage for one maximum length packet from every active virtual circuit. This paper refines that analysis, using assumptions that are closer to what we expect to see in practice and examines how EPD performs when the buffer is not large enough to achieve 100% goodput. We show that 100% goodput can be achieved …

Extending Atm Networks For Efficient Reliable Multicast, Jonathan S. Turner

All Computer Science and Engineering Research

One of the important features of ATM networks is their ability to support multicast communications. This facilitates the efficient distribution of multimedia information streams (such as audio and video) to large groups of receivers (potentially millions). Because ATM networks do not provide reliable delivery mechanisms, it is up to end systems to provide end-to-end reliability where it is needed. While this is straightforward for point-to-point virtual circuits, it is more difficult for one-to many and many-to-mamy virtual circuits. In this report, we propose some minimal extensions to the hardware of ATM switches that enables end systems to implement reliable multicast …

A Pilot Study Of Speech And Pen User Interface For Graphical Editing, Karl E. Schmidt

All Computer Science and Engineering Research

As computer size continues to decrease and new user interface technologies become more ubiquitous, the conventional keyboard and mouse input interfaces are becoming harder to design into newer machines and less practical for use in some applications. The pen is one input technology more suited for the upcoming generation of smaller computers using direct manipulation interfaces. However, a pen-only user interface relies on continuous gesture and handwriting tecognizers that are often slow, inaccurate, and error prone for command and text entry. Speech recognition is an input modality that can input commands quickly and potentially be a fast text entry mechanism, …

Vaudeville: A High Performance, Voice-Activated Teleconferencing Application, Jyoti K. Parwatikar, T. Paul Mccartney, John D. Dehart, Maynard Engebretson, Kenneth J. Goldman

All Computer Science and Engineering Research

We present a voice-activated, hands-off, ATM-based video conferencing application. The application, called Vaudeville, features high quality NTSC video, voice-activated audio transmission, audio bridging of two audio streams, and voice-activated video switching. It supports multiple simultaneous multi-party conferences using a scalable multicast mechanism. We describe how Vaudeville was built using a component-based distributed programming environment. We also describe the algorithms used to contorl the audio and video of the applciation. Audio and video are encoded in hardware using an ATM hardware multimedia interface.

Supporting Dis Applications Using Atm Multipoint Connection Caching, Anshul Kantawala, Guru Parulkar, John Dehart, Ted Marz

All Computer Science and Engineering Research

This report describes an ATM Multipoint Connection Caching strategy (AMCC) to control the explosive growth of traffic within the network and at an endpoint in a large Distributed Interactive Simulation (DIS) application such as a battlefield simulation. For very large DIS applications with 100,000 entities, the current method of broadcasting information among entities will no longer be feasible due to computational and network bandwidth limitations. Our scheme divides the simulation space into grids and each grid square or a set of grid squares forms a multicast group. Entities join the groups within their perception range and thus, they receive state …

Negotiation As A Resource Allocation Process, Fernando Tohme

All Computer Science and Engineering Research

The main economic-theoretic approcahes to the problem of resource allocation make little if any reference to negotiation processes. These processes are fundamentally linguistic, based on the exchange of messages among agents. Communication being so fundamental in the characterization of negotiation processes, the analysis of negotiation must emphasize on the structure of the language in which the negotiations take place. Computer science and particularly Artificial Intelligence have provided interesting insights about that linguistic structure. In the first part of this work we present a brief survey of the literature on resource allocation processes in which communication among agents plays a relevant …

New Results On Generalized Caching, Saied Hosseini-Khayat

All Computer Science and Engineering Research

We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains …

Alchourron's Defeasible Conditionals And Defeasible Reasoning, Fernando Tohme, Ronald P. Loui

All Computer Science and Engineering Research

No abstract provided.

Building Distributed Applications With Design Patterns, Gruia-Catalin Roman, James C. Hu

All Computer Science and Engineering Research

Design patterns are a topic of great current interest within the object-oriented programming community. The motivation is both economical and intellectual. On one hand, there is the hope of establishing a common culture and language that fosters communicatino and growth in the software engineering field. While a community dominated by empiricism is seeking to achieve higher levels of formality by capturing its experiences in the form of catalogs of design patterns, another community, deeply rooted in formal thinking, is seeking to make its mark on the every day workings of the software engineering process. Distributed algorithms and the heuristics used …

Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner

All Computer Science and Engineering Research

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network desings that, subject to specified traffic constraints, are nonblocking for point-to-point and multicast virtual circuits. Within this model we give various conditions under which star networks are optimal or near-optimal. These conditions are approximately satisfied in many common situations making the results of practical significance. An important consequence of these results is that, where they apply, there is no added cost for nonblocking multicast communication, relative to networks that are nonblocking for point-to-point traffic …

Design Of A Gigabit Atm Switch, Tom Chaney, Andrew Fingerhut, Margaret Flucke, Jonathan S. Turner

All Computer Science and Engineering Research

This report describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 1- Tb.s. The system design supports many-to-one and many-to-many forms of multicast, in addition to the usual one-to-many. It also provides multicast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that can achieve 100% link efficiencies, without large buffers.

Reconsidering Fragmentation And Reassembly, Girish P. Chandranmenon, George Varghese

All Computer Science and Engineering Research

We reconsider several issues related to fragmentation and reassembly in IP. We first reconsider reassembly. We describe a simple expected case optimization that improves reassembly performance to 38 instructions per fragment if the fragments arrive in FIFO order (the same assumption made in header prediction) which has been implemented in the NetBSD kernel. Next, we introduce the new idea of Graceful Intermediate Reassembly (GIR), which is a generalization of the existing IP mechanisms of destination and hop-by-hop reassembly. In GIR, we coalesce the fragments at an intermediate router in order to use the largest sized packets on its outgoing interface. …

Leap Forward Virtual Clock: An O(Loglogn) Fair Queuing Scheme With Guaranteed Delays And Throughput Fairness, Subhash Suri, George Varghese, Girish P. Chandranmenon

All Computer Science and Engineering Research

We describe an efficient fair queuing scheme, Leap Forward Virtual Clock, that provides end-to-end delay bounds almost identical to that of PGPS fair queuing, along with throughput fairness. Our scheme can be implemented with a worst-case time O(loglogN) per packet guaranteed delay and throughput fairness. As its name suggests, our scheme is based on Zhang's virtual clock. While the original virtual clock scheme does not achieve throughput fairness, we can modify it with a simple leap forward mechanism that keeps the server clock from lagging too far behind the packet tags. We prove that our scheme guarantees a fair share …

Efficient User Space Protocol Implementations With Qos Guarantees Using Real-Time Upcalls, R. Gopalakrishnan, Guru M. Parulkar

All Computer Science and Engineering Research

Real-time upcalls (RTUs) are an operating systems mechanism to provide quality-of-service (QoS) guarantees to network applications, and to efficiently implement protocols in user space with (QoS) guarantees. Traditionally, threads (and real-time extensions to threads) have been used to structure concurrent activities in user space protocol implementations. However, preemptive scheduling required for real-time threads leads to excessive context switching, and introduces the need for expensive concurrency control mechanisms such as locking. The RTU mechanism exploits the iterative nature of protocol processing to eliminate the need for locking, and reduce asynchronous preemption, while ensuring real-time operation. In addition to efficiency, eliminating the …