Engineering Commons^™

Logic Synthesis Of Reversible Wave Cascades, Alan Mishchenko, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A circuit is reversible if it maps each input vector into a unique output vector, and vice versa. Reversible circuits lead to power-efficient CMOS implementations. Reversible logic synthesis may be applicable to optical and quantum computing. Minimizing garbage bits is the main challenge in reversible logic synthesis. This paper introduces an algorithm to generate the cascade of reversible complex Maitra terms (called here reversible wave cascade) implementing incompletely specified Boolean functions. The remarkable property of the presented method compared to other reversible synthesis methods is that it creates at most one constant input and no additional garbage outputs. Preliminary estimation …

On The Intrinsic Evolution Of Material Inhomogeneities, Marek Elźanowski, Marcelo Epstein

Mathematics and Statistics Faculty Publications and Presentations

The evolution of a distribution of material inhomogeneities (defects, dislo-cations, etc.) is investigated. Adopting our recently developed model of the anelastic evolution law of a defective solid crystal body and using the classical methods of the theory of hyperbolic waves we analyze such phenomena as the long-term relaxation of defects and the dislocation pile-up.

Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Wu-Chang Feng, Francis Chang, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper describes the results of a 500 million packet trace of a popular on-line, multi-player, game server. The results show that the traffic behavior of this heavily loaded game server is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link. Specifically, in order to maximize the interactivity of the game itself and to provide relatively uniform experiences between players playing over different network speeds, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While …

Supporting Low-Latency Tcp-Based Media Streams, Ashvin Goel, Charles Krasic, Kang Li, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The dominance of the TCP protocol on the Internet and its success in maintaining Internet stability has led to several TCP-based stored media-streaming approaches. The success of these approaches raises the question whether TCP can be used for low-latency streaming. Low latency streaming allows responsive control operations for media streaming and can make interactive applications feasible. We examined adapting the TCP send buffer size based on TCP's congestion window to reduce application perceived network latency. Our results show that this simple idea significantly improves the number of packets that can be delivered within 200 ms and 500 ms thresholds.

Poster: Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Francis Chang, Wu-Chang Feng, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

A poster that illustrates the client/server model employed by an multiplayer online game, focusing on bandwidth usage.

Le Bio Wall : Un Tissue Informatique Pour Le Prototypage De Systèmes Bio-Inspirés, Andre Stauffer, Daniel Mange, Gianluca Tempesti, Christof Teuscher

Electrical and Computer Engineering Faculty Publications and Presentations

Dans cet article, nous décrivons le BioWall, un tissu informatique reconfigurable géant développé dans le but d’y implémenter des machines mettant en oeuvre les principes de notre projet Embryonique. Bien que ses dimensions et ses caractéristiques en font d’abord un objet de démonstration publique, le BioWall constitue également un outil de recherche précieux, du fait que sa faculté de reprogrammation et sa structure cellulaire s’adaptent parfaitement à l’implémentation de toutes sortes de systèmes bioinspirés. Pour illustrer ces capacités, nous décrivons un ensemble d’applications qui reflètent différentes sources d’inspiration biologique allant des systèmes biologiques ontogénétiques aux dispositifs évolutifs phylogénétiques, en passant …

Infopipes: An Abstraction For Multimedia Streaming, Andrew P. Black, Huang Jie, Rainer Koster, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

To simplify the task of building distributed streaming applications, we propose a new abstraction for information flow – Infopipes. Infopipes make information flow primary, not an auxiliary mechanism that is hidden away. Systems are built by connecting predefined component Infopipes such as sources, sinks, buffers, filters, broadcasting pipes, and multiplexing pipes. The goal of Infopipes is not to hide communication, like an RPC system, but to reify it: to represent communication explicitly as objects that the program can interrogate and manipulate. Moreover, these objects represent communication in application-level terms, not in terms of network or process implementation.

Forces On Permeable Conductors In Magnetic Fields, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

It is often implied that the force density formula dF/dV = JXB is all that is required to calculate the force that would be experienced by any stationary current-carrying medium in a region of space containing a magnetic field. However, representations of this formula are not all compatible, and the methods of applying such formulas when the conductor or surrounding medium have permeabilities different from vacuum are not widely known. The simplest case that one might consider is that of a current-carrying wire in an otherwise uniform field. It appears that the experimental measurements corresponding to such a situation have …

A Review Of Systems: New Paradigms For The Human Sciences, Martin Zwick

Complex Systems Faculty Publications and Presentations

This essay is a selective review of Systems: New Paradigms for the Human Sciences, edited by Gabriel Altmann and Walter A. Koch (Berlin: Walter de Gryter, 1998). It is selective because it is impossible to engage such a varied collection of systems-theoretic essays in a review of reasonable length. To invoke a relevant dialectical idea: the characteristic strength of any system is often also its characteristic weakness. One strength and weakness of the systems field is its great diversity, and this diversity is reflected in this volume by the range of subjects addressed in its 27 articles. I will not …

Thread Transparency In Information Flow Middleware, Rainer Koster, Andrew P. Black, Jie Huang, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

Existing middleware is based on control-flow centric interaction models such as remote method invocations, poorly matching the structure of applications that process continuous information flows. Difficulties cultiesin building this kind of application on conventional platforms include flow-specific concurrency and timing requirements, necessitating explicit management of threads, synchronization, and timing by the application programmer. We propose Infopipes as a high-level abstraction for information flows, and we are developing a middleware framework that supports this abstraction. Infopipes transparently handle complexities associated with control flow and multi-threading. From high-level configuration descriptions the platform determines what parts of a pipeline require separate threads or …

High Definition Manufacturing Cell Model, Wayne Wakeland, Leupold & Stevens, Inc.

Complex Systems Faculty Publications and Presentations

The purpose was to study the capacity, staffing requirements and alternative equipment configurations. This presentation provides a preview of the results.

Querying Geographically Dispersed, Heterogeneous Data Stores: The Pperfxchange Approach, Matthew Edward Colgrove

Dissertations and Theses

This thesis details PPerfXchange’s approach for querying geographically dispersed heterogeneous data stores. While elements of PPerfXchange’s method have been implemented for other application areas, PPerfXchange shows how these elements can be applied to parallel performance analysis. The accomplishments of this thesis are:

• The design of an architecture for PPerfXchange, giving a uniform method to query heterogeneous data stores;
• A proof of concept prototype implementation of PPerfXchange including a partial implementation of an XQuery processor and a relational database virtual XML document; and
• Evaluation of PPerfXchange using example parallel performance analysis data.

Efficient Algorithms For Creation Of Linearly-Independent Decision Diagrams And Their Mapping To Regular Layouts, Marek Perkowski, Bogdan Jaroslaw Falkowski, Malgorzata Chrzanowska-Jeske, Rolf Dreschler

Electrical and Computer Engineering Faculty Publications and Presentations

A new kind of a decision diagrams are presented: its nodes correspond to all types of nonsingular expansions for groups of input variables, in particular pairs. The diagrams are called the Linearly Independent (LI) Decision Diagrams (LI DDs). There are 840 nonsigular expansions for a pair of variables, thus 840 different types of nodes in the tree. Therefore, the number of nodes in such (exact) diagrams is usually much smaller than the number of nodes in the well-known Kronecker diagrams (which have only single-variable Shannon, Positive Davio, and Negative Davio expansions in nodes). It is usually much smaller than 1/3 …

Term Trees In Application To An Effective And Efficient Atpg For And–Exor And And–Or Circuits, Lech Jozwiak, Aleksander Ślusarczyk, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A compact data representation, in which the typically required operations are performed rapidly, and effective and efficient algorithms that work on these representations are the essential elements of a successful CAD tool. The objective of this paper is to present a new data representation—term trees (TTs)—and to discuss its application for an effective and efficient structural automatic test-pattern generation (ATPG). Term trees are decision diagrams similar to BDDs that are particularly suitable for structure representation of AND–OR and AND–EXOR circuits. In the paper, a flexible algorithm for minimum term-tree construction is discussed and an effective and efficient algorithm for ATPG …

Multiple-Valued Quantum Logic Synthesis, Marek Perkowski, Anas Al-Rabadi, Pawel Kerttopf

Electrical and Computer Engineering Faculty Publications and Presentations

This paper asks the question: is logic synthesis for quantum computers a practical research subject?

We would like to assume that any two quantum wires can interact, but we are limited by the realization constraints. Structure of atomic bonds in the molecule determines neighborhoods in the circuit. This is similar to restricted routing in FPGA layout - link between logic and layout synthesis known from CMOS design now appears in quantum. Below we are interested only in the so-called “permutation circuits” - their unitary quantum matrices are permutation matrices.

Generalized Inclusive Forms — New Canonical Reed-Muller Forms Including Minimum Esops, Marek Perkowski, Alan Mishchenko, Malgorzata Chzanowka-Jeske

Electrical and Computer Engineering Faculty Publications and Presentations

Reed-Muller (AND/EXOR) expansions play an important role in logic synthesis and circuit design by producing economical and highly-testable implementations of Boolean functions [3–6]. The range of Reed-Muller expansions include canonical forms, i.e. expansions that create unique representations of a Boolean function. Several large families of canonical forms: fixed polarity Reed-Muller forms (FPRMs), generalized Reed-Muller forms (GRMs), Kronecker forms (KROs), and pseudo- Kronecker forms (PKROs), referred to as the Green/Sasao hierarchy, have been described [7–9]. (See Fig. 1 for a settheoretic relationship between these families.)

Upper Spokane River Model: Model Calibration, 1991 And 2000, Chris Berger, Robert Leslie Annear, Scott A. Wells

Civil and Environmental Engineering Faculty Publications and Presentations

The Washington Department of Ecology is interested in a water quality model for the Upper Spokane River system for use in developing Total Maximum Daily Loads (TMDLs). The goals of this modeling effort are to:

• Gather data to construct a computer simulation model of the Spokane River system including Long Lake Reservoir and the pools behind Nine Mile dam, Upper Falls dam and Upriver dam. • Ensure that the model accurately represents the system hydrodynamics and water quality (flow, temperature, dissolved oxygen and nutrient dynamics)

This report evaluates the model calibration and discusses issues relative to that calibration effort. …

Lower Willamette River Model: Model Calibration, Chris Berger, Robert Leslie Annear, Scott A. Wells

Civil and Environmental Engineering Faculty Publications and Presentations

Water Environment Services of Clackamas County is in the process of planning upgrades on several of its wastewater treatment plants (WWTPs) which discharge into the Lower Willamette River. The goals of the modeling effort were to:

• Gather data to construct a computer simulation model of the Lower Willamette River system in order to evaluate the impact of the WWTP discharges on water quality

• Ensure that the model accurately represents the system physics and chemistry (flow, temperature, dissolved oxygen and nutrient dynamics) by model calibration

• Use the model to evaluate how to meet various future discharge scenarios for …

Capillary Flow In Interior Corners: The Infinite Column, Mark M. Weislogel

Mechanical and Materials Engineering Faculty Publications and Presentations

Capillary flow of a sinusoidally perturbed liquid column in an interior corner of infinite extent is solved using lubrication theory. Due primarily to the length scales selected to nondimensionalize the momentum equation, an analytic time scale governing the settling of the perturbation is determined. The time scale, which is shown to be independent of a steady base state flow, proves useful in rapidly predicting transients for surface settling in certain liquid-bearing tanks of spacecraft employing interior corners for fluids management purposes. The asymptotic analysis is extended to address flows along interior corners whose faces are slightly nonplanar. The generalized formulation …

Upper Spokane River Model: Boundary Conditions And Model Setup, 1991 And 2000, Robert Leslie Annear, Chris Berger, Scott A. Wells

Civil and Environmental Engineering Faculty Publications and Presentations

The Washington Department of Ecology is interested in a water quality model for the Upper Spokane River system for use in developing Total Maximum Daily Loads (TMDLs). The goals of this modeling effort are to:

• Gather data to construct a computer simulation model of the Spokane River system including Long Lake Reservoir and the pools behind Nine Mile dam, Upper Falls dam and Upriver dam

• Ensure that the model accurately represents the system hydrodynamics and water quality (flow, temperature, dissolved oxygen and nutrient dynamics)

A hydrodynamic and water quality model, CE-QUAL-W2 Version 3 (Wells, 1997), is being applied …

Lower Willamette River Model: Boundary Conditions And Model Setup, Herman G. Rodriguez, Robert Leslie Annear, Scott A. Wells, Chris Berger

Civil and Environmental Engineering Faculty Publications and Presentations

Water Environment Services of Clackamas County is in the process of planning upgrades on several of its sewage treatment plants which discharge into the Lower Willamette River. The goals of the modeling effort are to:

• Gather data to construct a computer simulation model of the Lower Willamette River system including part of the Lower Columbia River and the Willamette River above the Oregon City Falls; Because of the tidal influence in the Lower Willamette River, portions of the Columbia River that might affect the Lower Willamette River water quality were also modeled. Also, a section of the Willamette River …

Reifying Communication At The Application Level, Andrew P. Black, Jie Huang, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Middleware, from the earliest RPC systems to recent Object-Oriented Remote Message Sending (RMS) systems such as Java RMI and CORBA, claims transparency as one of its main attributes. Coulouris et al. define transparency as “the concealment from the … application programmer of the separation of components in a distributed system.” They go on to identify eight different kinds of transparency.

We considered titling this paper “Transparency Considered Harmful”, but that title is misleading because it implies that all kinds of transparency are bad. This is not our view. Rather, we believe that the choice of which transparencies should be offered …

Freightliner Llc Manufacturing Optimization, Jerry Compton, Ryan Jefferis, Hasnah Mat-Amin, Felix Ngoussou

Engineering and Technology Management Student Projects

Freightliner LLC has been producing innovative products since 1942 for the trucking industry. Following a 1981 acquisition by Daimler-Benz AG, Freightliner has steadily gained market share through acquisition and fleet sales. Following record production in 1999 at maximum yield levels, year 2000 hit the heavy truck market especially hard. High diesel fuel prices, low used truck values, and a slowing economy were just a few reasons for reduced truck sales.

Through Ql of 2001, heavy vehicle production was down 54% compared to 2000 in attempts of lowering inventory amounts. In this new market, capacity is no longer the overall manufacturing …

Gaussian Beams In Hollow Metal Waveguides: Experiment, Marius Ghita, Lee W. Casperson

Electrical and Computer Engineering Faculty Publications and Presentations

Gaussian beams have been widely used for propagating electromagnetic waves in free space and in certain other optical systems. It has been suggested that recurring forms of such beams might also be useful for propagation in planar or rectangular metal waveguides. Experimental verification of the recurrence of the Gaussian field distribution in metal waveguides is reported here.

Implicit Algorithms For Multi-Valued Input Support Manipulation, Alan Mishchenko, Craig Files, Marek Perkowski, Bernd Steinbach, Christina Dorotska

Electrical and Computer Engineering Faculty Publications and Presentations

We present an implicit approach to solve problems arising in decomposition of incompletely specified multi-valued functions and relations. We introduce a new representation based on binaryencoded multi-valued decision diagrams (BEMDDs). This representation shares desirable properties of MDDs, in particular, compactness, and is applicable to weakly-specified relations with a large number of output values. This makes our decomposition approach particularly useful for data mining and machine learning. Using BEMDDs to represent multi-valued relations we have developed two complementary input support minimization algorithms. The first algorithm is efficient when the resulting support contains almost all initial variables; the second is efficient when …

A General Decomposition For Reversible Logic, Marek Perkowski, Lech Jozwiak, Pawel Kerntopf, Alan Mishchenko, Anas Al-Rabadi, Alan Coppola, Andrzej Buller, Xiaoyu Song, Svetlana Yanushkevich, Vlad P. Shmerko, Malgorzata Chrzanowska-Jeske, Mozammel Huq Azad Khan

Electrical and Computer Engineering Faculty Publications and Presentations

Logic synthesis for reversible logic differs considerably from standard logic synthesis. The gates are multi-output and the unutilized outputs from these gates are called “garbage”. One of the synthesis tasks is to reduce the number of garbage signals. Previous approaches to reversible logic synthesis minimized either only the garbage or (predominantly) the number of gates. Here we present for the first time a method that minimizes concurrently the number of gates, their total delay and the total garbage. Our method adopts for reversible logic many ideas developed previously for standard logic synthesis (such as Ashenhurst/Curtis Decomposition, Dietmeyer’s Composition, non-linear preprocessing …

Fast Heuristic Minimization Of Exclusive-Sums-Of-Products, Alan Mishchenko, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

Exclusive-Sums-Of-Products (ESOPs) play an important role in logic synthesis and design-for-test. This paper presents an improved version of the heuristic ESOP minimization procedure proposed in [1,2]. The improvements concern three aspects of the procedure: (1) computation of the starting ESOP cover; (2) increase of the search space for solutions by applying a larger set of cube transformations; (3) development of specialized datastructures for robust manipulation of ESOP covers. Comparison of the new heuristic ESOP minimizer EXORCISM-4 with other minimizers (EXMIN2 [3], MINT [4], EXORCISM-2 [1] and EXORCISM3 [2]) show that, in most cases, EXORCISM-4 produces results of comparable or better …

Infopipes—An Abstraction For Information Flow, Jie Huang, Andrew P. Black, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

Building Object-Oriented Distributed Systems has been facilitated by Remote Message Sending (RMS) systems like Java RMI and implementations of CORBA. However, RMS systems are designed to support request/response interactions. Streaming applications, in contrast, are characterized by high-bandwidth, long-duration communication with stringent performance requirements. Examples of streaming applications include video-on-demand, teleconferencing, on-line education, and environmental observation. These applications transfer huge amounts of data and focus on distributed information flow rather than request/response.

To simplify the task of building distributed streaming applications, we propose a new abstraction for information flow—Infopipes. Using Infopipes, information flow becomes the heart of the system, not an …

Globally Convergent Approximate Dynamic Programming Applied To An Autolander, J.J. Murray, Richard Saeks, C.J. Cox, George G. Lendaris

Complex Systems Faculty Publications and Presentations

A globally convergent nonlinear Approximate Dynamic Programming algorithm is described, and an implementation of the algorithm in the linear case is developed. The resultant linear Approximate Dynamic Programming algorithm is illustrated via the design of an autolander for the NASA X-43 research aircraft, without a priori knowledge of the X-43's flight dynamics.

Bi-Decomposition Of Multi-Valued Relations, Alan Mishchenko, Marek Perkowski, Bernd Steinbach

Electrical and Computer Engineering Faculty Publications and Presentations

This presentation discusses an approach to decomposition of multivalued functions and relations into networks of two-input gates implementing multi-valued MIN and MAX operations. The algorithm exploits both the incompleteness of the initial specification and the flexibilities generated in the process of decomposition. Experimental results over a set of multi-valued benchmarks show that this approach outperforms other approaches in the quality of final results and CPU time.