VLSI and Circuits, Embedded and Hardware Systems Commons^™

Accelerating Machine Learning Inference For Satellite Component Feature Extraction Using Fpgas., Andrew Ekblad

Theses and Dissertations

Running computer vision algorithms requires complex devices with lots of computing power, these types of devices are not well suited for space deployment. The harsh radiation environment and limited power budgets have hindered the ability of running advanced computer vision algorithms in space. This problem makes running an on-orbit servicing detection algorithm very difficult. This work proposes using a low powered FPGA to accelerate the computer vision algorithms that enable satellite component feature extraction. This work uses AMD/Xilinx’s Zynq SoC and DPU IP to run model inference. Experiments in this work centered around improving model post processing by creating implementations …

Qasm-To-Hls: A Framework For Accelerating Quantum Circuit Emulation On High-Performance Reconfigurable Computers, Anshul Maurya

Theses and Dissertations

High-performance reconfigurable computers (HPRCs) make use of Field-Programmable Gate Arrays (FPGAs) for efficient emulation of quantum algorithms. Generally, algorithm-specific architectures are implemented on the FPGAs and there is very little flexibility. Moreover, mapping a quantum algorithm onto its equivalent FPGA emulation architecture is challenging. In this work, we present an automation framework for converting quantum circuits to their equivalent FPGA emulation architectures. The framework processes quantum circuits represented in Quantum Assembly Language (QASM) and derives high-level descriptions of the hardware emulation architectures for High-Level Synthesis (HLS) on HPRCs. The framework generates the code for a heterogeneous architecture consisting of a …

Framework Of Hardware Trojan Detection Leveraging Structural Checking Tool, Rafael Dacanay Del Carmen

Graduate Theses and Dissertations

Since there is a significant demand for obtaining third-party soft Intellectual Property (IP) by first-party integrated circuit (IC) vendors, it is becoming easier for adversaries to insert malicious logic known as hardware Trojans into designs. Due to this, vendors need to find ways to screen the third-party IPs for possible security threats and then mitigate them. The development of the Structural Checking (SC) tool provides a solution to this issue. This tool analyzes the structure of an unknown soft IP design and creates a network of all the signals within the design and how they are connected to each other. …

Evaluation Of Robust Deep Learning Pipelines Targeting Low Swap Edge Deployment, David Carter Cornett

Masters Theses

The deep learning technique of convolutional neural networks (CNNs) has greatly advanced the state-of-the-art for computer vision tasks such as image classification and object detection. These solutions rely on large systems leveraging wattage-hungry GPUs to provide the computational power to achieve such performance. However, the size, weight and power (SWaP) requirements of these conventional GPU-based deep learning systems are not suitable when a solution requires deployment to so called "Edge" environments such as autonomous vehicles, unmanned aerial vehicles (UAVs) and smart security cameras.

The objective of this work is to benchmark FPGA-based alternatives to conventional GPU systems that have the …

Expanding Temperature Sensing For The Orion Bms 2, Samuel J. Parker

University Honors Theses

Formula SAE (FSAE) is an annual collegiate design competition that takes place across the globe. Portland State University’s team, Viking Motorsports, was committed to designing an Electric Vehicle (EV) for the 2021 FSAE competition. The team designed a completely custom lithium-ion cell battery that is managed by an Orion BMS 2 battery management system. The FSAE rulebook requires a robust temperature monitoring system for any EV power supply. The Orion BMS 2 can only directly collect data from eight temperature sensors, which is not enough to meet FSAE regulation. However, the BMS can be configured to monitor many more sensors …

Iot Garden Frost Alarm, Andrew James

Honors Theses

Home gardeners are faced with yearly challenges due to spring frosts harming young plants. This is frequently mitigated by covering crops with frost blankets, but only on nights when a frost is predicted. In areas with less predictable climate, an unexpected frost can kill vulnerable plants, reducing the amount of food produced. A system is proposed and designed here to use internet of things (IoT) technology to enable a small weather station in the home garden to report current climate data and predict frosts, then alert the gardener in time for them to cover their plants.

The system as designed …

Design Project: Smart Headband, John Michel, Jack Durkin, Noah Lewis

Williams Honors College, Honors Research Projects

Concussion in sports is a prevalent medical issue. It can be difficult for medical professionals to diagnose concussions. With the fast pace nature of many sports, and the damaging effects of concussions, it is important that any concussion risks are assessed immediately. There is a growing trend of wearable technology that collects data such as steps and provides the wearer with in-depth information regarding their performance. The Smart Headband project created a wearable that can record impact data and provide the wearer with a detailed analysis on their risk of sustaining a concussion. The Smart Headband uses accelerometers and gyroscopes …

Longitudinal Partitioning Waveform Relaxation Methods For The Analysis Of Transmission Line Circuits, Tarik Menkad

Electronic Thesis and Dissertation Repository

Three research projects are presented in this manuscript. Projects one and two describe two waveform relaxation algorithms (WR) with longitudinal partitioning for the time-domain analysis of transmission line circuits. Project three presents theoretical results about the convergence of WR for chains of general circuits.

The first WR algorithm uses a assignment-partition procedure that relies on inserting external series combinations of positive and negative resistances into the circuit to control the speed of convergence of the algorithm. The convergence of the subsequent WR method is examined, and fast convergence is cast as a generic optimization problem in the frequency-domain. An automatic …

Digital And Mixed Domain Hardware Reduction Algorithms And Implementations For Massive Mimo, Najath A. Mohomed

FIU Electronic Theses and Dissertations

Emerging 5G and 6G based wireless communications systems largely rely on multiple-input-multiple-output (MIMO) systems to reduce inherently extensive path losses, facilitate high data rates, and high spatial diversity. Massive MIMO systems used in mmWave and sub-THz applications consists of hundreds perhaps thousands of antenna elements at base stations. Digital beamforming techniques provide the highest flexibility and better degrees of freedom for phased antenna arrays as compared to its analog and hybrid alternatives but has the highest hardware complexity.

Conventional digital beamformers at the receiver require a dedicated analog to digital converter (ADC) for every antenna element, leading to ADCs for …

Investigating Single Precision Floating General Matrix Multiply In Heterogeneous Hardware, Steven Harris

McKelvey School of Engineering Theses & Dissertations

The fundamental operation of matrix multiplication is ubiquitous across a myriad of disciplines. Yet, the identification of new optimizations for matrix multiplication remains relevant for emerging hardware architectures and heterogeneous systems. Frameworks such as OpenCL enable computation orchestration on existing systems, and its availability using the Intel High Level Synthesis compiler allows users to architect new designs for reconfigurable hardware using C/C++. Using the HARPv2 as a vehicle for exploration, we investigate the utility of several of the most notable matrix multiplication optimizations to better understand the performance portability of OpenCL and the implications for such optimizations on this and …

Compound Effects Of Clock And Voltage Based Power Side-Channel Countermeasures, Jacqueline Lagasse

Masters Theses

The power side-channel attack, which allows an attacker to derive secret information from power traces, continues to be a major vulnerability in many critical systems. Numerous countermeasures have been proposed since its discovery as a serious vulnerability, including both hardware and software implementations. Each countermeasure has its own drawback, with some of the highly effective countermeasures incurring large overhead in area and power. In addition, many countermeasures are quite invasive to the design process, requiring modification of the design and therefore additional validation and testing to ensure its accuracy. Less invasive countermeasures that do not require directly modifying the system …

Hardware Ip Classification Through Weighted Characteristics, Brendan Mcgeehan

Graduate Theses and Dissertations

Today’s business model for hardware designs frequently incorporates third-party Intellectual Property (IP) due to the many benefits it can bring to a company. For instance, outsourcing certain components of an overall design can reduce time-to-market by allowing each party to specialize and perfect a specific part of the overall design. However, allowing third-party involvement also increases the possibility of malicious attacks, such as hardware Trojan insertion. Trojan insertion is a particularly dangerous security threat because testing the functionality of an IP can often leave the Trojan undetected. Therefore, this thesis work provides an improvement on a Trojan detection method known …

Model Development And Assessment Of The Gate Network In A High-Performance Sic Power Module, William Austin Curbow

Graduate Theses and Dissertations

The main objective of this effort is to determine points of weakness in the gate network of a high-performance SiC power module and to offer remedies to these issues to increase the overall performance, robustness, and reliability of the technology. In order to accomplish this goal, a highly accurate model of the gate network is developed through three methods of parameter extraction: calculation, simulation, and measurement. A SPICE model of the gate network is developed to analyze four electrical issues in a high-speed, SiC-based power module including the necessary internal gate resistance for damping under-voltage and over-voltage transients, the disparity …

Cmos Compatible Memristor Networks For Brain-Inspired Computing, Can Li

Doctoral Dissertations

In the past decades, the computing capability has shown an exponential growth trend, which is observed as Moore’s law. However, this growth speed is slowing down in recent years mostly because the down-scaled size of transistors is approaching their physical limit. On the other hand, recent advances in software, especially in big data analysis and artificial intelligence, call for a break-through in computing hardware. The memristor, or the resistive switching device, is believed to be a potential building block of the future generation of integrated circuits. The underlying mechanism of this device is different from that of complementary metal-oxide-semiconductor (CMOS) …

Low Latency Intrusion Detection In Smart Grids, Israel Zairi Akingeneye

Graduate Theses and Dissertations

The transformation of traditional power grids into smart grids has seen more new technologies such as communication networks and smart meters (sensors) being integrated into the physical infrastructure of the power grids. However, these technologies pose new vulnerabilities to the cybersecurity of power grids as malicious attacks can be launched by adversaries to attack the smart meters and modify the measurement data collected by these meters. If not timely detected and removed, these attacks may lead to inaccurate system state estimation, which is critical to the system operators for control decisions such as economic dispatch and other related functions.

This …

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Ronald Greenberg

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Ronald Greenberg

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

Ronald Greenberg

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

In this paper, we examine the wormhole routing problem in terms of the “congestion” c and “dilation” d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη+cLηlogP) time with high probability, where L is the number of flits in a packet, and η=min{d,L}; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log^3 A) …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Ronald Greenberg

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a …

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Ronald Greenberg

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Ronald Greenberg

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels …

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of …

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from Theta(n) to Omega(n^2), where n is the number of nets. But, if the number of columns c is O(n), one can solve the problem in time O(n^{1.5}lg n ), which improves upon a `naive' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Ronald Greenberg

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.