Engineering Commons^™

Ternary Logic Design In Topological Quantum Computing, Muhammad Ilyas, Shawn Cui, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

A quantum computer can perform exponentially faster than its classical counterpart. It works on the principle of superposition. But due to the decoherence effect, the superposition of a quantum state gets destroyed by the interaction with the environment. It is a real challenge to completely isolate a quantum system to make it free of decoherence. This problem can be circumvented by the use of topological quantum phases of matter. These phases have quasiparticles excitations called anyons. The anyons are charge-flux composites and show exotic fractional statistics. When the order of exchange matters, then the anyons are called non-Abelian anyons. Majorana …

Development Of A Configurable Real-Time Event Detection Framework For Power Systems Using Swarm Intelligence Optimization, Umar Farooq

Dissertations and Theses

Modern power systems characterized by complex topologies require accurate situational awareness to maintain an adequate level of reliability. Since they are large and spread over wide geographical areas, occurrence of failures is inevitable in power systems. Various generation and transmission disturbances give rise to a mismatch between generation and demand, which manifest as frequency events. These events can take the form of negligible frequency deviations or more severe emergencies that can precipitate cascading outages, depending on the severity of the disturbance and efficacy of remedial action schema. The impacts of such events have become more critical with recent decline in …

Methodologies For Quantum Circuit And Algorithm Design At Low And High Levels, Edison Tsai

Dissertations and Theses

Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research.

Any viable computing system requires both hardware and …

Quantum Grover's Oracles With Symmetry Boolean Functions, Peng Gao

Dissertations and Theses

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm.

In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized …

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

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

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

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.

Classical Search And Quantum Search Algorithms For Synthesis Of Quantum Circuits And Optimization Of Quantum Oracles, Sazzad Hossain

Dissertations and Theses

We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which …

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 of well-known …

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

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

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

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

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.

Design And Evaluation Of A Specialized Computer Architecture For Manipulating Binary Decision Diagrams, Robert K. Hatt

Dissertations and Theses

Binary Decision Diagrams (BDDs) are an extremely important data structure used in many logic design, synthesis and verification applications. Symbolic problem representations make BDDs a feasible data structure for use on many problems that have discrete representations. Efficient implementations of BOD algorithms on general purpose computers has made manipulating large binary decision diagrams possible. Much research has gone into making BOD algorithms more efficient on general purpose computers. Despite amazing increases in performance and capacity of such computers over the last decade, they may not be the best way to solve large, specialized problems. A computer architecture designed specifically to …

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

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

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. The …

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 …

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 …

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 minimal ESOP than …

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. Due …

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 layout synthesis stage …

Designing And Simulating A Multistage Sampling Rate Conversion System Using A Set Of Pc Programs, David Joseph Hagerty

Dissertations and Theses

The thesis covers a series of PC programs that we have written that will enable users to easily design FIR linear phase lowpass digital filters and multistage sampling rate conversion systems. The first program is a rewrite of the McClellan-Parks computer program with some slight modifications. The second program uses an algorithm proposed by Rabiner that determines the length of a lowpass digital filter. Rabiner used a formula proposed by Herrmann et al. to initially estimate the filter length in his algorithm. The formula, however, assumes unity gain. We present a modification to the formula so that the gain of …

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

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 results …

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 …

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 …

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 the …