Open Access. Powered by Scholars. Published by Universities.^{®}

- Discipline

- Publication Year

- Publication

- Publication Type

Articles **1** - **29** of ** 29**

## Full-Text Articles in Engineering

Sparse Coding On Stereo Video For Object Detection, Sheng Y. Lundquist, Melanie Mitchell, Garrett T. Kenyon

#### Sparse Coding On Stereo Video For Object Detection, Sheng Y. Lundquist, Melanie Mitchell, Garrett T. Kenyon

*Computer Science Faculty Publications and Presentations*

Deep Convolutional Neural Networks (DCNN) require millions of labeled training examples for image classification and object detection tasks, which restrict these models to domains where such a dataset is available. We explore the use of unsupervised sparse coding applied to stereo-video data to help alleviate the need for large amounts of labeled data. In this paper, we show that unsupervised sparse coding is able to learn disparity and motion sensitive basis functions when exposed to unlabeled stereo-video data. Additionally, we show that a DCNN that incorporates unsupervised learning exhibits better performance than fully supervised networks. Furthermore, finding a sparse representation ...

A Theory Of Name Resolution, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

#### A Theory Of Name Resolution, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

*Computer Science Faculty Publications and Presentations*

We describe a language-independent theory for name binding and resolution, suitable for programming languages with complex scoping rules including both lexical scoping and modules. We formulate name resolution as a two-stage problem. First a language-independent scope graph is constructed using language-specific rules from an abstract syntax tree. Then references in the scope graph are resolved to corresponding declarations using a language-independent resolution process. We introduce a resolution calculus as a concise, declarative, and language- independent specification of name resolution. We develop a resolution algorithm that is sound and complete with respect to the calculus. Based on the resolution calculus we ...

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

#### Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

*Computer Science Faculty Publications and Presentations*

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent ...

Application Of Cuda In The Boolean Domain For The Unate Covering Problem, Eric Paul, Bernd Steinbach, Marek Perkowski

#### Application Of Cuda In The Boolean Domain For The Unate Covering Problem, Eric Paul, Bernd Steinbach, Marek Perkowski

*Electrical and Computer Engineering Faculty Publications and Presentations*

NVIDIA’s Compute Unified Device Architecture (CUDA) is a relatively-recent development that allows to realize very fast algorithms for several Constraint Satisfaction and Computer Aided Design tasks. In this paper we present an approach to use Graphics Processing Units (GPU) and CUDA for solving Unate Covering Problem, a practical problem related to SAT. In particular we present a CUDA-enabled Petrick Function Minimizer. We compare the performance of a pipeline-processor (CPU) and a parallel processor (GPU) implementation of the matrix-multiplication method for solving unate covering problems.

Ternary Quantum Logic, Normen Giesecke

#### Ternary Quantum Logic, Normen Giesecke

*Dissertations and Theses*

The application of Moore's Law would not be feasible by using the computing systems fabrication principles that are prevalent today. Fundamental changes in the field of computing are needed to keep Moore's Law operational. Different quantum technologies are available to take the advancement of computing into the future. Logic in quantum technology uses gates that are very different from those used in contemporary technology. Limiting itself to reversible operations, this thesis presents different methods to realize these logic gates. Two methods using Generalized Ternary Gates and Muthukrishnan Stroud Gates are presented for synthesis of ternary logic gates. Realizations ...

Logic Synthesis For Layout Regularity Using Decision Diagrams, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jinsong Zhang, Marek Perkowski

#### Logic Synthesis For Layout Regularity Using Decision Diagrams, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Jinsong Zhang, Marek Perkowski

*Electrical and Computer Engineering Faculty Publications and Presentations*

This paper presents a methodology for logic synthesis of Boolean functions in the form of regular structures that can be mapped into standard cells or programmable devices. Regularity offers an elegant solution to hard problems arising in layout and test generation, at no extra cost or at the cost of increasing the number of gates, which does not always translate into the increase of circuit area. Previous attempts to synthesize logic into regular structures using decision diagrams suffered from an increase in the number of logic levels due to multiple repetitions of control variables. This paper proposes new techniques, which ...

Function-Driven Linearly Independent Expansions Of Boolean Functions And Their Application To Synthesis Of Reversible Circuits, Pawel Kerntopf, Marek Perkowski

#### Function-Driven Linearly Independent Expansions Of Boolean Functions And Their Application To Synthesis Of Reversible Circuits, Pawel Kerntopf, Marek Perkowski

*Electrical and Computer Engineering Faculty Publications and Presentations*

The paper presents a family of new expansions of Boolean functions called Function-driven Linearly Independent (fLI) expansions. On the basis of this expansion a new kind of a canonical representation of Boolean functions is constructed: Function-driven Linearly Independent Binary Decision Diagrams (fLIBDDs). They generalize both Function-driven Shannon Binary Decision Diagrams (fShBDDs) and Linearly Independent Binary Decision Diagram (LIBDDs). The diagrams introduced in the paper, can provide significantly smaller representations of Boolean functions than standard Ordered Binary Decision Diagrams (OBDDs), Ordered Functional Decision Diagrams (OFDDs) and Ordered (Pseudo-) Kronecker Functional Decision Diagrams (OKFDDs) and can be applied to synthesis of reversible ...

Logic Synthesis For Regular Layout Using Satisfiability, Marek Perkowski, Alan Mishchenko

#### Logic Synthesis For Regular Layout Using Satisfiability, Marek Perkowski, Alan Mishchenko

*Electrical and Computer Engineering Faculty Publications and Presentations*

In this paper, we propose a regular layout geometry called 3×3 lattice. The main difference of this geometry compared to the known 2×2 regular layout geometry is that it allows the cofactors on a level to propagate to three rather than two nodes on the lower level. This gives additional freedom to synthesize compact functional representations. We propose a SAT-based algorithm, which exploits this freedom to synthesize 3×3 lattice representations of completely specified Boolean functions. The experimental results show that the algorithm generates compact layouts in reasonable time.

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

#### 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 ...

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

#### 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.

Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

#### Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole

*Computer Science Faculty Publications and Presentations*

This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.

Jitter And Wander Reduction For A Sonet Ds3 Desynchronizer Using Predictive Fuzzy Control, Kevin Blythe Stanton

#### Jitter And Wander Reduction For A Sonet Ds3 Desynchronizer Using Predictive Fuzzy Control, Kevin Blythe Stanton

*Dissertations and Theses*

Excessive high-frequency jitter or low-frequency wander can create problems within synchronous transmission systems and must be kept within limits to ensure reliable network operation. The emerging Synchronous Optical NETwork (SONET) introduces additional challenges for jitter and wander attenuation equipment (called desynchronizers) when used to carry payloads from the existing Plesiochronous Digital Hierarchy (PDH), such as the DS3. The difficulty is primarily due to the large phase transients resulting from the pointer-based justification technique employed by SONET (called Pointer Justification Events or PJEs). While some previous desynchronization techniques consider the buffer level in their control actions, none has explicitly considered wander ...

Minimization Of Sum-Of-Conditional-Decoders Structures With Applications In Finite Machine Epld Design And Machine Learning, Sanof Mohamedsadakathulla

#### Minimization Of Sum-Of-Conditional-Decoders Structures With Applications In Finite Machine Epld Design And Machine Learning, Sanof Mohamedsadakathulla

*Dissertations and Theses*

In order to achieve superior speed in sequencer designs over competing PLD devices, Cypress brought to market an innovative architecture, CY7C361. This architecture introduced a new kind of universal logic gate, the CONDITION DECODER (CDEC). Because there are only 32 macrocells in the chip, saving only one CDEC gate can be quite important (the well-known "fit/no-fit problem"). A problem that is related to the fitting problem of the Cypress CY7C361 chip is the SOC Minimization. Due to the limited low number of macrocells in CY7C361, a high quality logic minimization to reduce the number of macrocells is very important ...

High Level Preprocessor Of A Vhdl-Based Design System, Karthikeyan Palanisamy

#### High Level Preprocessor Of A Vhdl-Based Design System, Karthikeyan Palanisamy

*Dissertations and Theses*

This thesis presents the work done on a design automation system in which high-level synthesis is integrated with logic synthesis. DIADESfa design automation system developed at PSU, starts the synthesis process from a language called ADL. The major part of this thesis deals with transforming the ADL -based DIADES system into a VHDL -based DIADES system. In this thesis I have upgraded and modified the existing DIADES system so that it becomes a preprocessor to a comprehensive VHDL -based design system from Mentor Graphics. The high-level synthesis in the DIADES system includes two stages: data path synthesis and control unit ...

An Analysis Of Approaches To Efficient Hardware Realization Of Image Compression Algorithms, Kamran Iravani

#### An Analysis Of Approaches To Efficient Hardware Realization Of Image Compression Algorithms, Kamran Iravani

*Dissertations and Theses*

In this thesis an attempt has been made to develop a fast algorithm to compress images. The Reed-Muller compression algorithm which was introduced by Reddy & Pai [3] is fast, but the compression factor is too low when compared to the other methods. In this thesis first research has been done to improve this method by generalizing the Reed-Muller transform to the fixed polarity Reed-Muller form. This thesis shows that the Fixed Polarity Reed-Muller transform does not improve the compression factor enough to warrant its use as an image compression method. The paper, by Reddy & Pai [3], on Reed-Muller image compression ...

Minimization Of Generalized Reed-Muller Expansion And Its Sub-Class, Xiaoqiang Zeng

#### Minimization Of Generalized Reed-Muller Expansion And Its Sub-Class, Xiaoqiang Zeng

*Dissertations and Theses*

Several classes of AND-EXOR circuit expressions have been defined and their relationship have been shown. A new class of AND-EXOR circuit, the Partially Mixed Polarity Reed-Muller Expression(PMPRM), which is a subclass of the Generalized Reed-Muller expression, is created, along with an efficient minimization algorithm. This new AND/EXOR circuit form has the following features: • Since this sub-family of ESOP (with a total of n2n-I22n-i - (n-1)2n forms which includes the 2n Fixed-Polarity Reed-Muller forms) is much larger than the Kronecker Reed-Muller(KRM) expansion(with 3n forms), generally the minimal form of this expansion will be much closer to the ...

#### Investigation Of Solution Space Of Trees And Dags For Realization Of Combinational Logic In At 6000 Series Fpgas, Philip Ho

*Dissertations and Theses*

Various tree and Directed Acyclic Graph structures have been used for representation and manipulation of switching functions. Among these structures the Binary Decision DiagramJilave been the most widely used in logic synthesis. A BDD is a binary tree graph that represents the recursive execution of Shannon's expansion. A FDD is a directed function graph that represents the recursive execution of Reed Muller expansion. A family of decision diagrams for representation of Boolean function is introduced in this thesis. This family of Kronecker Functional Decision Diagrams (KFDD) includes the Binary Decision Diagrams (BDD) and Functional Decision Diagrams (FDD) as subsets ...

Vertex Ordering For A Partitioning-Based Fitting Algorithm For An Epld Device, Tongjun Gao

#### Vertex Ordering For A Partitioning-Based Fitting Algorithm For An Epld Device, Tongjun Gao

*Dissertations and Theses*

As the Application-Specific Integrated Circuit(ASIC) technology develops to the trend of high density and modulization, the ASIC device market has been dominated gradually by the more complex Erasable Programmable Logic Devices (EPLDs) and the Field Programmable Gate Array(FPGAs) instead of the ordinally Programmable Logic Devices(PLDs). Meanwhile, the design automation system for such programmable devices has also moved from schematic entry design to high level hardware description language entry design. Usually, the whole design automation process consists of three phrases, the high level hardware description language compiler, the logic synthesis stage and the layout synthesis stage. Though the ...

Quasi-Static Deflection Compensation Control Of Flexible Manipulator, Jingbin Feng

#### Quasi-Static Deflection Compensation Control Of Flexible Manipulator, Jingbin Feng

*Dissertations and Theses*

The growing need in industrial applications of high-performance robots has led to designs of lightweight robot arms. However the light-weight robot arm introduces accuracy and vibration problems. The classical robot design and control method based on the rigid body assumption is no longer satisfactory for the light-weight manipulators. The effects of flexibility of light-weight manipulators have been an active research area in recent years. A new approach to correct the quasi-static position and orientation error of the end-effector of a manipulator with flexible links is studied in this project. In this approach, strain gages are used to monitor the elastic ...

A Robust High Precision Algorithm For Sinewave Parameter Estimation, Kendall Ann Rydell

#### A Robust High Precision Algorithm For Sinewave Parameter Estimation, Kendall Ann Rydell

*Dissertations and Theses*

The estimation of sinewave parameters has many practical applications in test and data processing systems. Measuring the effective bits of an analog-to-digital converter and linear circuit identification are some typical examples. If a sinew ave's frequency is known, there is an established linear method to estimate the other parameters. But when none of the parameters are known (which is usually the case in practical situations), the estimation problem becomes more difficult. Traditional approaches to this task applied an iterative, sinewave curve-fit algorithm. Two problems with this technique are that convergence is often slow and not always guaranteed and the ...

#### Minimization Of Permuted Reed-Muller Trees And Reed-Muller Trees For Cellular Logic Programmable Gate Arrays, Lifei Wu

*Dissertations and Theses*

The new family of Field Programmable Gate Arrays, CLI 6000 from Concurrent Logic Inc realizes truly Cellular Logic. It has been mainly designed for the realization of data path architectures. However, the realizable logic functions provided by its macrocells and their limited connectivity call also for new general-purpose logic synthesis methods. The basic cell of CLi 6000 can be programmed to realize a two-input multiplexer ( A*B + C*B ), an AND/EXOR cell ( A*B Ea C ), or the basic 2-input AND, OR and EXOR gate. This suggests to using these cells for tree-like expansions. These "cellular logic" devices require ...

#### Minimization Of Exclusive Sum Of Products Expressions For Multiple-Valued Input Incompletely Specified Functions, Ning Song

*Dissertations and Theses*

In recent years, there is an increased interest in the design of logic circuits which use EXOR gates. Particular interest is in the minimization of arbitrary Exclusive Sums Of Products (ESOPs). Functions realized by such circuits can have fewer gates, fewer connections, and take up less area in VLSI and especially, FPGA realizations. They are also easily testable. So far, the ESOPs are not as popular as their Sum of Products (SOP) counterparts. One of the main reasons it that the problem of the minimization of ESOP circuits was traditionally an extremely difficult one. Since exact solutions can be practically ...

Mapping Programs To Parallel Architectures In The Real World, Dezheng Tang

#### Mapping Programs To Parallel Architectures In The Real World, Dezheng Tang

*Dissertations and Theses*

Mapping an application program to a parallel architecture can be described as a multidimensional optimization problem. To simplify the problem, we divide the overall mapping process into three sequential substeps: partitioning, allocating, and scheduling, with each step using a few details of the program and architecture description. Due to the difficulty in accurately describing the program and architecture and the fact that each substep uses incomplete information, inaccuracy is pervasive in the real-world mapping process. We hypothesize that the inaccuracy and the use of suboptimal, heuristic mapping methods may greatly affect the mapping or submapping performance and lead to a ...

A Partitioning-Based Approach To The Fitting Problem In Special Architecture Eplds, Steffan Goller

#### A Partitioning-Based Approach To The Fitting Problem In Special Architecture Eplds, Steffan Goller

*Dissertations and Theses*

In this thesis, we describe an architecture-driven fitting algorithm for an Application-Specific EPLD, the CY7C361, from Cypress Semiconductor. Traditional placement and routing tools for PLDs perform placement and routing separately. Several placement possibilities are created and the router tries to realize the connections between the physical locations of the cells on the chip. The Cypress CY7C361 has a very unique chip architecture with a highly limited connectivity between the physical cells. Therefore, it is necessary to consider the mutability when the placement of cells is performed. The combination of the two stages is called fitting. The specific architecture-dependent constraints, imposed ...

Improved I/O Pad Positions Assignment Algorithm For Sea-Of-Gates Placement, Shyang-Kuen Her

#### Improved I/O Pad Positions Assignment Algorithm For Sea-Of-Gates Placement, Shyang-Kuen Her

*Dissertations and Theses*

A new heuristic method to improve the I/O pad assignment for the sea-of-gates placement algorithm "PROUD" is proposed. In PROUD, the preplaced I/O pads are used as the boundary conditions in solving sparse linear equations to obtain the optimal module placement. Due to the total wire length determined by the module positions is the strong function of the preplaced I/O pad positions, the optimization of the I/O pad circular order and their assignment to the physical locations on the chip are attempted in the thesis. The proposed I/O pad assignment program is used as a ...

Effectiveness Of Additive Correction Multigrid In Numerical Heat Transfer Analysis When Implemented On An Intel Ipsc2, James D. Padgett

#### Effectiveness Of Additive Correction Multigrid In Numerical Heat Transfer Analysis When Implemented On An Intel Ipsc2, James D. Padgett

*Dissertations and Theses*

The effectiveness of the Additive Correction Multigrid (ACM) algorithm, a line-byline Tri-diagonal Matrix Algorithm (TDMA), and simple Gauss-Seidel (GS) iteration in numerical heat transfer analysis is investigated on a conventional single processor computer and on a distributed memory parallel computer. The performance of these methods is studied by solving a two-dimensional, steady heat conduction problem. The execution time of ACM on a single processor is proportional to the number of unknowns to the 1.5 power. This is in contrast to the execution time of the TDMA for which the execution time is proportional to the number of unknowns to ...

Ignoring Interprocessor Communication During Scheduling, Chintamani M. Patwardhan

#### Ignoring Interprocessor Communication During Scheduling, Chintamani M. Patwardhan

*Dissertations and Theses*

The goal of parallel processing is to achieve high speed computing by partitioning a program into concurrent parts, assigning them in an efficient way to the available processors, scheduling the program and then executing the concurrent parts simultaneously. In the past researchers have combined the allocation of tasks in a program and scheduling of those tasks into one operation. We define scheduling as a process of efficiently assigning priorities to the already allocated tasks in a program. Assignment of priorities is important in cases when more than one task at a processor is ready for execution. Most heuristics for scheduling ...

A Practical Parallel Algorithm For The Minimization Of KröNecker Reed-Muller Expansions, Paul John Gilliam

#### A Practical Parallel Algorithm For The Minimization Of KröNecker Reed-Muller Expansions, Paul John Gilliam

*Dissertations and Theses*

A number of recent developments has increased the desirability of using exclusive OR (XOR) gates in the synthesis of switching functions. This has, in turn, led naturally to an increased interest in algorithms for the minimization of Exclusive-Or Sum of Products (ESOP) forms. Although this is an active area of research, it is not nearly as developed as the traditional Sum of Products forms. Computer programs to find minimum ESOPs are not readily available and those that do exist are impractical to use as investigative tools because they are too slow and/or require too much memory. A practical tool ...

Parplum : A System For Evaluating Parallel Program Optimization Methods, Jingsong Fu

#### Parplum : A System For Evaluating Parallel Program Optimization Methods, Jingsong Fu

*Dissertations and Theses*

The diversity of application programs and parallel architectures makes the mapping problem complicated and hard to evaluate. The quality of mapping is machine and application dependent and varies due to inaccurate values of application and architecture characteristics.

A system for developing, applying and evaluating mappings must have four characteristics: (1) Simplicity: A mapping procedure can be evaluated by separately evaluating its submapping, so the complicated problem can be simplified. (2) Generality: A wide range of application programs and architectures can be easily represented and all mapping algorithms can be easily implemented. (3) Multifunctionality: all the mapping steps, application programs, target ...