@article {2023, title = {Efficient Unmanned Aerial Systems Navigation With Collision Avoidance in Dense Urban Environments}, journal = {IEEE Transactions on Intelligent Transportation Systems (T-ITS)}, volume = {24}, year = {2023}, month = {August}, abstract = {

Unmanned Aerial Systems (UAS) are an emerging type of airborne traffic under active research expected to carry cargo and passengers in the future over dense population centers. One challenge is identifying algorithms which can compactly represent and navigate the available airspace while avoiding conflict with buildings and other UAS. In this paper, we explore a decentralized method coupling a medial axis graph for global navigation through the city with local collision avoidance of buildings and other UAS to obtain collision-free efficient navigation through an urban environment. We study trade-offs of using Optimal Reciprocal Collision Avoidance (ORCA), Rapidly-exploring Random Trees (RRT and RRT*), and Fast Markov Decision Process (FastMDP) as the collision avoidance algorithms. We examine low-altitude UAS navigating through a portion of New York City dense with skyscrapers to study the effectiveness of the algorithms in a challenging environment. We show that ORCA, RRT, RRT*, and FastMDP all are fairly efficient for 2D problems, but as the problem becomes more realistic (3D, constrained motion, aware of other UAS), FastMDP provides the best overall performance among the four algorithms studied.

}, author = {Joshua Bertram and Joseph Zambreno and Peng Wei} } @conference {2023, title = {An FPGA Implementation of SipHash}, booktitle = {Proceedings of the Reconfigurable Architectures Workshop (RAW)}, year = {2023}, month = {May}, abstract = {

Cryptographic hash functions play a critical role in ensuring the security and veracity of network transactions; for example, they constitute the backbone of hash-based message authentication codes (HMACs), distributed hash tables (DHTs), and blockchain. However, cryptographic hashing can incur significant CPU overhead, especially for applications that commonly process large inputs exceeding 1 MB. This can make it infeasible to implement HMACs, DHTs, etc. in resource-constrained embedded systems or servers with strict response time requirements.\  As a solution, we present an FPGA architecture to accelerate SipHash, a promising cryptographic hash function.\  Our design constitutes the first SipHash implementation that targets maximum performance on an FPGA. The proposed architecture\&$\#$39;s throughput and acceleration vs. software were measured on Xilinx\&$\#$39;s Zynq-7000 and Ultrascale+ SoCs for a wide range of input sizes.\  These results show one core can provide single-threaded throughput of up to 13.7 Gbps on a modern FPGA fabric, and multiple parallel cores can exceed 100 Gbps, allowing applications like blockchain and peer-to-peer file sharing to scale with emerging high-bandwidth networks.\  A single core can keep pace with 10 Gigabit Ethernet, and further parallelization can empower FPGA designs to fully utilize higher network bandwidths.

}, author = {Benjamin Welte and Joseph Zambreno} } @article {2021, title = {A Fast Markov Decision Process based Algorithm for Collision Avoidance in Urban Air Mobility}, journal = {IEEE Transactions on Intelligent Transportation Systems (T-ITS)}, volume = {23}, year = {2022}, month = {September}, abstract = {
Multiple aircraft collision avoidance is a challenging problem due to a stochastic environment and uncertainty in the intent of other aircraft. Traditionally a layered approach to collision avoidance has been employed using a centralized air traffic control system, established rules of the road, separation assurance, and last minute pairwise collision avoidance. With the advent of Urban Air Mobility (air taxis), the expected increase in traffic density in urban environments, short time scales, and small distances between aircraft favor decentralized decision making on-board the aircraft. In this paper, we present a Markov Decision Process (MDP) based method, named FastMDP, which can solve a certain subclass of MDPs quickly, and demonstrate using the algorithm online to safely maintain separation and avoid collisions with multiple aircraft (1-on-n) while remaining computationally efficient. We compare the FastMDP algorithm\’s performance against two online collision avoidance algorithms that have been shown to be both efficient and scale to large numbers of aircraft: Optimal Reciprocal Collision Avoidance (ORCA) and Monte Carlo Tree Search (MCTS). Our simulation results show that under the assumption that aircraft do not have perfect knowledge of other aircraft intent FastMDP outperforms ORCA and MCTS in collision avoidance behavior in terms of loss of separation and near mid-air collisions while being more computationally efficient. We further show that in our simulation FastMDP behaves nearly as well as MCTS with perfect knowledge of other aircraft intent. Our results show that FastMDP is a promising algorithm for collision avoidance that is also computationally efficient.
}, author = {Joshua Bertram and Peng Wei and Joseph Zambreno} } @conference {BerZam21A, title = {Scalable FastMDP for Pre-departure Airspace Reservation and Strategic De-conflict}, booktitle = {Proceedings of the AIAA SciTech Forum}, year = {2021}, month = {January}, abstract = {

Pre-departure flight plan scheduling for Urban Air Mobility (UAM) and cargo delivery drones will require on-demand scheduling of large numbers of aircraft. We demonstrate an algorithm known as FastMDP-GPU that performs first-come-first-served pre-departure flight plan scheduling where conflict free flight plans are generated on demand. We demonstrate a parallelized implementation of the algorithm on a Graphics Processor Unit (GPU) and show the level of performance and scaling that can be achieved. Our results show that on commodity GPU hardware we can perform flight plan scheduling against 2000-3000 known flight plans and with server-class hardware the performance can be higher. Our results show promise for implementing a large scale UAM scheduler capable of performing on-demand flight scheduling that would be suitable for both centralized or distributed flight planning systems.

}, author = {Joshua Bertram and Joseph Zambreno and Peng Wei} } @conference {ZhuWer18A, title = {Improving First Level Cache Efficiency for GPUs Using Dynamic Line Protection}, booktitle = {Proceedings of the International Conference on Parallel Processing (ICPP)}, year = {2018}, month = {August}, abstract = { A modern Graphics Processing Unit (GPU) utilizes L1 Data (L1D) caches to reduce memory bandwidth requirements and latencies. However, the L1D cache can easily be overwhelmed by many memory requests from GPU function units, which can bottleneck GPU performance. It has been shown that the performance of L1D caches is greatly reduced for many GPU applications as a large amount of L1D cache lines are replaced before they are re-referenced. By examining the cache access patterns of these applications, we observe L1D caches with low associativity have difficulty capturing data locality for GPU applications with diverse reuse patterns. These patterns result in frequent line replacements and low data re-usage. To improve the efficiency of L1D caches, we design a Dynamic Line Protection scheme (DLP) that can both preserve valuable cache lines and increase cache line utilization. DLP collects data reuse information from the L1D cache. This information is used to predict protection distances for each memory instruction at runtime, which helps maintain a balance between exploitation of data locality and over-protection of cache lines with long reuse distances. When all cache lines are protected in a set, redundant cache misses are bypassed to reduce the contention for the set. The evaluation result shows that our proposed solution improves cache hits while reducing cache traffic for cache-insufficient applications, achieving up to 137\% and an average of 43\% IPC improvement over the baseline.}, author = {Xian Zhu and Robert Wernsman and Joseph Zambreno} } @conference {WanZam16A, title = {Parallelizing Latent Semantic Indexing Using an FPGA-based Architecture}, booktitle = {Proceedings of the International Conference on Computer Design (ICCD)}, year = {2016}, month = {October}, abstract = {Latent Semantic Indexing (LSI) has played a significant role in discovering patterns on the relationships between query terms and unstructured documents. However, the inherent characteristics of complex matrix factorization in LSI make it difficult to meet stringent performance requirements. In this paper, we present a deeply pipelined reconfigurable architecture for LSI, which parallelizes the matrix factorization and dimensionality reduction, computation of cosine similarity between vectors, and the ranking of documents. Our architecture implements the reduced Singular Value Decomposition with Hestenes-Jacobi algorithm, in which both singular values and orthogonal vectors are collected, and its components can be reconfigured to update query vector coordinate and calculate query-document similarity. In addition, an ordered tree structure is used to reduce the matrix dimension and rank the documents. Analysis of our design indicates the potential to achieve a performance of 8.9 GFLOPS with dimension-dependent speedups over an optimized software implementation that range from 3.8x to 10.1x in terms of computation time.}, author = {Xinying Wang and Joseph Zambreno} } @conference {WanJon15A, title = {A Configurable Architecture for Sparse LU Decomposition on Matrices with Arbitrary Patterns}, booktitle = {Proceedings of the International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies (HEART)}, year = {2015}, month = {June}, abstract = {Sparse LU decomposition has been widely used to solve sparse linear systems of equations found in many scientific and engineering applications, such as circuit simulation, power system modeling and computer vision. However, it is considered a computationally expensive factorization tool. While parallel implementations have been explored to accelerate sparse LU decomposition, irregular sparsity patterns often limit their performance gains. Prior FPGA-based accelerators have been customized to domain-specific sparsity patterns of pre-ordered symmetric matrices. In this paper, we present an efficient architecture for sparse LU decomposition that supports both symmetric and asymmetric sparse matrices with arbitrary sparsity patterns. The control structure of our architecture parallelizes computation and pivoting operations. Also, on-chip resource utilization is configured based on properties of the matrices being processed. Our experimental results show a 1.6 to 14x speedup over an optimized software implementation for benchmarks containing a wide range of sparsity patterns.}, author = {Xinying Wang and Phillip Jones and Joseph Zambreno} } @article {WanJon16A, title = {A Configurable Architecture for Sparse LU Decomposition on Matrices with Arbitrary Patterns}, journal = {ACM Computer Architecture News (CAN)}, volume = {43}, year = {2015}, month = {September}, abstract = {Sparse LU decomposition has been widely used to solve sparse linear systems of equations found in many scientific and engineering applications, such as circuit simulation, power system modeling and computer vision. However, it is considered a computationally expensive factorization tool. While parallel implementations have been explored to accelerate sparse LU decomposition, irregular sparsity patterns often limit their performance gains. Prior FPGA-based accelerators have been customized to domain-specific sparsity patterns of pre-ordered symmetric matrices. In this paper, we present an efficient architecture for sparse LU decomposition that supports both symmetric and asymmetric sparse matrices with arbitrary sparsity patterns. The control structure of our architecture parallelizes computation and pivoting operations. Also, on-chip resource utilization is configured based on properties of the matrices being processed. Our experimental results show a 1.6 to 14x speedup over an optimized software implementation for benchmarks containing a wide range of sparsity patterns.}, author = {Xinying Wang and Phillip Jones and Joseph Zambreno} } @conference {WanZam14B, title = {An Efficient Architecture for Floating-Point Eigenvalue Decomposition}, booktitle = {Proceedings of the International Symposium on Field-Programmable Custom Computing Machines (FCCM)}, year = {2014}, month = {May}, abstract = {Eigenvalue decomposition (EVD) is a widely-used factorization tool to perform principal component analysis, and has been employed for dimensionality reduction and pattern recognition in many scientific and engineering applications, such as image processing, text mining and wireless communications. EVD is considered computationally expensive, and as software implementations have not been able to meet the performance requirements of many real-time applications, the use of reconfigurable computing technology has shown promise in accelerating this type of computation. In this paper, we present an efficient FPGA-based double-precision floating-point architecture for EVD, which can efficiently analyze large-scale matrices. Our experimental results using an FPGA-based hybrid acceleration system indicate the efficiency of our novel array architecture, with dimension-dependent speedups over an optimized software implementation that range from 1.5x to 15.45x in terms of computation time.}, author = {Xinying Wang and Joseph Zambreno} } @conference {WanZam14A, title = {An FPGA Implementation of the Hestenes-Jacobi Algorithm for Singular Value Decomposition}, booktitle = {Proceedings of the Reconfigurable Architectures Workshop (RAW)}, year = {2014}, month = {May}, abstract = {As a useful tool for dimensionality reduction, Singular Value Decomposition (SVD) plays an increasingly significant role in many scientific and engineering applications. The high computational complexity of SVD poses challenges for efficient signal processing and data analysis systems, especially for time-sensitive applications with large data sets. While the emergence of FPGAs provides a flexible and low-cost opportunity to pursue high-performance SVD designs, the classical two-sided Jacobi rotation-based SVD architectures are restricted in terms of scalability and input matrix representation. The Hestenes-Jacobi algorithm offers a more parallelizable solution to analyze arbitrary rectangular matrices; however, to date both FPGA and GPU-based implementations have not lived up to the algorithm{\textquoteright}s potential. In this paper, we introduce a floating-point Hestenes-Jacobi architecture for SVD, which is capable of analyzing arbitrary sized matrices. Our implementation on an FPGA-based hybrid acceleration system demonstrates improved efficiency of our architecture compared to an optimized software-based SVD solution for matrices with small to medium column dimensions, even with comparably large row dimensions. The dimensional speedups can be achieved range from 3.8x to 43.6x for matrices with column dimensions from 128 to 256 and row sizes from 128 to 2048. Additionally, we also evaluate the accuracy of our SVD process through convergence analysis.}, author = {Xinying Wang and Joseph Zambreno} } @conference {WanZam14C, title = {A Reconfigurable Architecture for QR Decomposition Using A Hybrid Approach}, booktitle = {Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI)}, year = {2014}, month = {July}, abstract = {QR decomposition has been widely used in many signal processing applications to solve linear inverse problems. However, QR decomposition is considered a computationally expensive process, and its sequential implementations fail to meet the requirements of many time-sensitive applications. The Householder transformation and the Givens rotation are the most popular techniques to conduct QR decomposition. Each of these approaches have their own strengths and weakness. The Householder transformation lends itself to efficient sequential implementation, however its inherent data dependencies complicate parallelization. On the other hand, the structure of Givens rotation provides many opportunities for concurrency, but is typically limited by the availability of computing resources. We propose a deeply pipelined reconfigurable architecture that can be dynamically configured to perform either approach in a manner that takes advantage of the strengths of each. At runtime, the input matrix is first partitioned into numerous submatrices. Our architecture then performs parallel Householder transformations on the sub-matrices in the same column block, which is followed by parallel Givens rotations to annihilate the remaining unneeded individual off-diagonals. Analysis of our design indicates the potential to achieve a performance of 10.5 GFLOPS with speedups of up to 1.46x, 1.15x and 13.75x compared to the MKL implementation, a recent FPGA design and a Matlab solution, respectively.}, author = {Xinying Wang and Phillip Jones and Joseph Zambreno} } @conference {RilGra11A, title = {Circumventing a Ring Oscillator Approach to FPGA-Based Hardware Trojan Detection}, booktitle = {Proceedings of the International Conference on Computer Design (ICCD)}, year = {2011}, month = {October}, abstract = {Ring oscillators are commonly used as a locking mechanism that binds a hardware design to a specific area of silicon within an integrated circuit (IC). This locking mechanism can be used to detect malicious modifications to the hardware design, also known as a hardware Trojan, in situations where such modifications result in a change to the physical placement of the design on the IC. However, careful consideration is needed when designing ring oscillators for such a scenario to guarantee the integrity of the locking mechanism. This paper presents a case study in which flaws discovered in a ring oscillator-based Trojan detection scheme allowed for the circumvention of the security mechanism and the implementation of a large and diverse set of hardware Trojans, limited only by hardware resources.}, author = {Justin Rilling and David Graziano and Jamin Hitchcock and Timothy Meyer and Xinying Wang and Phillip Jones and Joseph Zambreno} }