ASU Electronic Theses and Dissertations
This collection includes most of the ASU Theses and Dissertations from 2011 to present. ASU Theses and Dissertations are available in downloadable PDF format; however, a small percentage of items are under embargo. Information about the dissertations/theses includes degree information, committee members, an abstract, supporting data or media.
In addition to the electronic theses found in the ASU Digital Repository, ASU Theses and Dissertations can be found in the ASU Library Catalog.
Dissertations and Theses granted by Arizona State University are archived and made available through a joint effort of the ASU Graduate College and the ASU Libraries. For more information or questions about this collection contact or visit the Digital Repository ETD Library Guide or contact the ASU Graduate College at gradformat@asu.edu.
Displaying 31 - 39 of 39
Description
Many companies face pressure to deploy flexible compute infrastructures to manage their operations. However, the current developments in cloud and edge computing have created a data processing asymmetry challenge. On the edge, workloads frequently require low-latency responses, contend with connectivity and bandwidth instabilities, may require privacy guarantees, and may perform under limited or high-variance compute resources. In the cloud, workloads tolerate longer latency, expect highly available infrastructure, access high-performance compute resources, and have more power available, but may be further from where the processing results are needed. This compute asymmetry challenge requires a new computational paradigm. In this work, I advance a new computing architecture model, called the Continuum Computing Architecture (CCA), and validate this model with a candidate architecture. CCA is a unifying edge-fog-cloud computing model that provides the following capabilities: (i) a continuum of compute that spans from network-connected edge devices to the cloud – with very low power consumption to high-performance compute; (ii) same architecture with different micro-architectures along this compute continuum – a single RISC-V instruction set architecture with reconfigurable processing units; (iii) portability across all scales – the same program can be run across the continuum with different latencies and power utilizations; and (iv) secure shared memory features are fully-supported – physical memories along the continuum are abstracted to allow edge and cloud to share data in a transparent fashion. The validating architecture has three micro-architectures. The edge micro-architecture, Parmenides, targets accelerator-based edge processing system-on-chips (SoCs). Parmenides includes security features to protect the SoC in uncontrolled environments while adapting its power usage and processing to ambient events. The fog and cloud micro-architectures, Melissus and Zeno, must support application data distribution across the memory of many compute nodes to achieve the desired scale and performance. As a solution, I introduce the Eleatic Memory Model (EMM): a global shared memory architecture with hardware-supported global memory access permissions. All memory accesses are made with a Namespace-based capability scheme that supports improved scalability and memory security. The CCA model addresses several memory-centric security challenges including the misuse of resources, risk to application and data integrity, as well as concerns over authorization and confidentiality.
ContributorsEhret, Alan (Author) / Kinsy, Michel A (Thesis advisor) / Vrudhula, Sarma (Committee member) / Shrivastava, Aviral (Committee member) / Rudd, Kevin (Committee member) / Gettings, Karen (Committee member) / Arizona State University (Publisher)
Created2022
Description
Data-intensive systems such as big data and large machine learning (ML) systems experience serious scalability challenges due to the ever-increasing data demand from ML and analytics applications and the resource fragmentation caused by conventional monolithic server architecture. Memory and storage disaggregation emerges as a pivotal technology to address these challenges by decoupling memory and storage resources from individual servers and managing and provisioning them to applications as a shared resource pool. This dissertation investigates several important aspects of memory and storage disaggregation and proposes novel solutions to support data-intensive applications.First, caching is a fundamental way to utilize disaggregated storage, but building a large disaggregated cache is challenging because the commonly-used fix-sized cache block allocation scheme is unable to provide good cache performance with low memory overhead for diverse cloud workloads with vastly different I/O patterns. The dissertation proposes a novel adaptive cache block allocation approach that dynamically adjusts cache block sizes based on changing I/O patterns. This approach significantly improves I/O performance while reducing memory usage, outperforming traditional fixed-size cache systems in diverse cloud workloads. Evaluation shows that it improves read latency by 20% and write latency by 9%. It also reduces the amount of I/O traffic to cloud block storage by up to 74% while achieving up to 41% memory savings with only 2 ms.
Second, large ML applications such as large language model (LLM) inference are memory demanding, but to support them using disaggregated memory brings challenges to memory management since disaggregated memory has higher memory access latency compared to local memory. The dissertation proposes latency-aware memory aggregation which cautiously distributes memory accesses to minimize the latency gap between local and disaggregated memory. It also proposes NUMA-aligned tensor parallelism to further improve the computing efficiency. With these optimizations, LLM inference achieves substantial speedups. For example, first token latency improves by 61%, and end-to-end latency improves by 43% for a LLM inference task which uses a model of 66 billion parameters when the batch size is 8.
Finally, to address the cost, power consumption, and volatility of DRAM, the dissertation proposes to incorporate flash memory into memory pools within the disaggregation framework. By establishing a tiered memory architecture which combines fast-tier local DRAM with slow-tier DRAM and flash memory in the memory pool and effectively migrates data based on hotness across memory tiers, this approach not only reduces expenses but also maintains the overall performance and scalability of data-intensive systems. For example, with 50% saving in memory cost, the performance degradation of training ResNet50 on ImageNet dataset is only 2.68%.
Together, these contributions systematically optimize the use of memory and storage disaggregation to deliver more efficient, scalable, and cost-effective systems for supporting the data explosion in today’s and future computing systems.
ContributorsYang, Qirui (Author) / Zhao, Ming (Thesis advisor) / Shrivastava, Aviral (Committee member) / Ren, Fengbo (Committee member) / Zou, Jia (Committee member) / Arizona State University (Publisher)
Created2024
Description
There has been exciting progress in the area of Unmanned Aerial Vehicles (UAV) in the last decade, especially for quadrotors due to their nature of easy manipulation and simple structure. A lot of research has been done on achieving autonomous and robust control for quadrotors. Recently researchers have been utilizing linear temporal logic as mission specification language for robot motion planning due to its expressiveness and scalability. Several algorithms have been proposed to achieve autonomous temporal logic planning. Also, several frameworks are designed to compose those discrete planners and continuous controllers to make sure the actual trajectory also satisfies the mission specification. However, most of these works use first-order kinematic models which are not accurate when quadrotors fly at high speed and cannot fully utilize the potential of quadrotors.
This thesis work describes a new design for a hierarchical hybrid controller that is based on a dynamic model and seeks to achieve better performance in terms of speed and accuracy compared with some previous works. Furthermore, the proposed hierarchical controller is making progress towards guaranteed satisfaction of mission specification expressed in Linear Temporal Logic for dynamic systems. An event-driven receding horizon planner is also utilized that aims at distributed and decentralized planning for large-scale navigation scenarios. The benefits of this approach will be demonstrated using simulations results.
This thesis work describes a new design for a hierarchical hybrid controller that is based on a dynamic model and seeks to achieve better performance in terms of speed and accuracy compared with some previous works. Furthermore, the proposed hierarchical controller is making progress towards guaranteed satisfaction of mission specification expressed in Linear Temporal Logic for dynamic systems. An event-driven receding horizon planner is also utilized that aims at distributed and decentralized planning for large-scale navigation scenarios. The benefits of this approach will be demonstrated using simulations results.
ContributorsZhang, Xiaotong (Author) / Fainekos, Georgios (Thesis advisor) / Ben Amor, Heni (Committee member) / Shrivastava, Aviral (Committee member) / Arizona State University (Publisher)
Created2016
Description
Graphs are one of the key data structures for many real-world computing applica-
tions such as machine learning, social networks, genomics etc. The main challenges of
graph processing include diculty in parallelizing the workload that results in work-
load imbalance, poor memory locality and very large number of memory accesses.
This causes large-scale graph processing to be very expensive.
This thesis presents implementation of a select set of graph kernels on a multi-core
architecture, Transmuter. The kernels are Breadth-First Search (BFS), Page Rank
(PR), and Single Source Shortest Path (SSSP). Transmuter is a multi-tiled architec-
ture with 4 tiles and 16 general processing elements (GPE) per tile that supports a
two level cache hierarchy. All graph processing kernels have been implemented on
Transmuter using Gem5 architectural simulator.
The key pre-processing steps in improving the performance are static partition-
ing by destination and balancing the workload among the processing cores. Results
obtained by processing graphs that are partitioned against un-partitioned graphs
show almost 3x improvement in performance. Choice of data structure also plays an
important role in the amount of storage space consumed and the amount of synchro-
nization required in a parallel implementation. Here the compressed sparse column
data format was used. BFS and SSSP are frontier-based algorithms where a frontier
represents a subset of vertices that are active during the current iteration. They
were implemented using the Boolean frontier array data structure. PR is an iterative
algorithm where all vertices are active at all times.
The performance of the dierent Transmuter implementations for the 14nm node
were evaluated based on metrics such as power consumption (Watt), Giga Operations
Per Second(GOPS), GOPS/Watt and L1/L2 cache misses. GOPS/W numbers for
graphs with 10k nodes and 10k edges is 33 for BFS, 477 for PR and 10 for SSSP.
i
Frontier-based algorithms have much lower GOPS/W compared to iterative algo-
rithms such as PR. This is because all nodes in Page Rank are active at all points
in time. For all three kernel implementations, the L1 cache miss rates are quite low
while the L2 cache hit rates are high.
tions such as machine learning, social networks, genomics etc. The main challenges of
graph processing include diculty in parallelizing the workload that results in work-
load imbalance, poor memory locality and very large number of memory accesses.
This causes large-scale graph processing to be very expensive.
This thesis presents implementation of a select set of graph kernels on a multi-core
architecture, Transmuter. The kernels are Breadth-First Search (BFS), Page Rank
(PR), and Single Source Shortest Path (SSSP). Transmuter is a multi-tiled architec-
ture with 4 tiles and 16 general processing elements (GPE) per tile that supports a
two level cache hierarchy. All graph processing kernels have been implemented on
Transmuter using Gem5 architectural simulator.
The key pre-processing steps in improving the performance are static partition-
ing by destination and balancing the workload among the processing cores. Results
obtained by processing graphs that are partitioned against un-partitioned graphs
show almost 3x improvement in performance. Choice of data structure also plays an
important role in the amount of storage space consumed and the amount of synchro-
nization required in a parallel implementation. Here the compressed sparse column
data format was used. BFS and SSSP are frontier-based algorithms where a frontier
represents a subset of vertices that are active during the current iteration. They
were implemented using the Boolean frontier array data structure. PR is an iterative
algorithm where all vertices are active at all times.
The performance of the dierent Transmuter implementations for the 14nm node
were evaluated based on metrics such as power consumption (Watt), Giga Operations
Per Second(GOPS), GOPS/Watt and L1/L2 cache misses. GOPS/W numbers for
graphs with 10k nodes and 10k edges is 33 for BFS, 477 for PR and 10 for SSSP.
i
Frontier-based algorithms have much lower GOPS/W compared to iterative algo-
rithms such as PR. This is because all nodes in Page Rank are active at all points
in time. For all three kernel implementations, the L1 cache miss rates are quite low
while the L2 cache hit rates are high.
ContributorsRENGANATHAN, SRINIDHI (Author) / Chakrabarti, Chaitali (Thesis advisor) / Shrivastava, Aviral (Committee member) / Mudge, Trevor (Committee member) / Arizona State University (Publisher)
Created2019
Description
Many core modern multiprocessor systems-on-chip offers tremendous power and performance
optimization opportunities by tuning thousands of potential voltage, frequency
and core configurations. Applications running on these architectures are becoming increasingly
complex. As the basic building blocks, which make up the application, change during
runtime, different configurations may become optimal with respect to power, performance
or other metrics. Identifying the optimal configuration at runtime is a daunting task due
to a large number of workloads and configurations. Therefore, there is a strong need to
evaluate the metrics of interest as a function of the supported configurations.
This thesis focuses on two different types of modern multiprocessor systems-on-chip
(SoC): Mobile heterogeneous systems and tile based Intel Xeon Phi architecture.
For mobile heterogeneous systems, this thesis presents a novel methodology that can
accurately instrument different types of applications with specific performance monitoring
calls. These calls provide a rich set of performance statistics at a basic block level while the
application runs on the target platform. The target architecture used for this work (Odroid
XU3) is capable of running at 4940 different frequency and core combinations. With the
help of instrumented application vast amount of characterization data is collected that provides
details about performance, power and CPU state at every instrumented basic block
across 19 different types of applications. The vast amount of data collected has enabled
two runtime schemes. The first work provides a methodology to find optimal configurations
in heterogeneous architecture using classifiers and demonstrates an average increase
of 93%, 81% and 6% in performance per watt compared to the interactive, ondemand and
powersave governors, respectively. The second work using same data shows a novel imitation
learning framework for dynamically controlling the type, number, and the frequencies
of active cores to achieve an average of 109% PPW improvement compared to the default
governors.
This work also presents how to accurately profile tile based Intel Xeon Phi architecture
while training different types of neural networks using open image dataset on deep learning
framework. The data collected allows deep exploratory analysis. It also showcases how
different hardware parameters affect performance of Xeon Phi.
optimization opportunities by tuning thousands of potential voltage, frequency
and core configurations. Applications running on these architectures are becoming increasingly
complex. As the basic building blocks, which make up the application, change during
runtime, different configurations may become optimal with respect to power, performance
or other metrics. Identifying the optimal configuration at runtime is a daunting task due
to a large number of workloads and configurations. Therefore, there is a strong need to
evaluate the metrics of interest as a function of the supported configurations.
This thesis focuses on two different types of modern multiprocessor systems-on-chip
(SoC): Mobile heterogeneous systems and tile based Intel Xeon Phi architecture.
For mobile heterogeneous systems, this thesis presents a novel methodology that can
accurately instrument different types of applications with specific performance monitoring
calls. These calls provide a rich set of performance statistics at a basic block level while the
application runs on the target platform. The target architecture used for this work (Odroid
XU3) is capable of running at 4940 different frequency and core combinations. With the
help of instrumented application vast amount of characterization data is collected that provides
details about performance, power and CPU state at every instrumented basic block
across 19 different types of applications. The vast amount of data collected has enabled
two runtime schemes. The first work provides a methodology to find optimal configurations
in heterogeneous architecture using classifiers and demonstrates an average increase
of 93%, 81% and 6% in performance per watt compared to the interactive, ondemand and
powersave governors, respectively. The second work using same data shows a novel imitation
learning framework for dynamically controlling the type, number, and the frequencies
of active cores to achieve an average of 109% PPW improvement compared to the default
governors.
This work also presents how to accurately profile tile based Intel Xeon Phi architecture
while training different types of neural networks using open image dataset on deep learning
framework. The data collected allows deep exploratory analysis. It also showcases how
different hardware parameters affect performance of Xeon Phi.
ContributorsPatil, Chetan Arvind (Author) / Ogras, Umit Y. (Thesis advisor) / Chakrabarti, Chaitali (Committee member) / Shrivastava, Aviral (Committee member) / Arizona State University (Publisher)
Created2019
Description
As device and voltage scaling cease, ever-increasing performance targets can only be achieved through the design of parallel, heterogeneous architectures. The workloads targeted by these domain-specific architectures must be designed to leverage the strengths of the platform: a task that has proven to be extremely difficult and expensive.
Machine learning has the potential to automate this process by understanding the features of computation that optimize device utilization and throughput.
Unfortunately, applications of this technique have utilized small data-sets and specific feature extraction, limiting the impact of their contributions.
To address this problem I present Dash-Database; a repository of C and C++ programs for software-defined radio applications and its neighboring fields; a methodology for structuring the features of computation using kernels, and a set of evaluation metrics to standardize computation data sets. Dash-Database contributes a general data set that supports machine understanding of computation and standardizes the input corpus utilized for machine learning of computation; currently only a small set of benchmarks and features are being used.
I present an evaluation of Dash-Database using three novel metrics: breadth, depth and richness; and compare its results to a data set largely representative of those used in prior work, indicating a 5x increase in breadth, 40x increase in depth, and a rich set of sample features.
Using Dash-Database, the broader community can work toward a general machine understanding of computation that can automate the design of workloads for domain-specific computation.
Machine learning has the potential to automate this process by understanding the features of computation that optimize device utilization and throughput.
Unfortunately, applications of this technique have utilized small data-sets and specific feature extraction, limiting the impact of their contributions.
To address this problem I present Dash-Database; a repository of C and C++ programs for software-defined radio applications and its neighboring fields; a methodology for structuring the features of computation using kernels, and a set of evaluation metrics to standardize computation data sets. Dash-Database contributes a general data set that supports machine understanding of computation and standardizes the input corpus utilized for machine learning of computation; currently only a small set of benchmarks and features are being used.
I present an evaluation of Dash-Database using three novel metrics: breadth, depth and richness; and compare its results to a data set largely representative of those used in prior work, indicating a 5x increase in breadth, 40x increase in depth, and a rich set of sample features.
Using Dash-Database, the broader community can work toward a general machine understanding of computation that can automate the design of workloads for domain-specific computation.
ContributorsWillis, Benjamin Roy (Author) / Brunhaver, John S (Thesis advisor) / Chakrabarti, Chaitali (Committee member) / Shrivastava, Aviral (Committee member) / Arizona State University (Publisher)
Created2020
Description
Autonomous Vehicles (AV) are inevitable entities in future mobility systems thatdemand safety and adaptability as two critical factors in replacing/assisting human
drivers. Safety arises in defining, standardizing, quantifying, and monitoring requirements
for all autonomous components. Adaptability, on the other hand, involves
efficient handling of uncertainty and inconsistencies in models and data. First, I address
safety by presenting a search-based test-case generation framework that can be
used in training and testing deep-learning components of AV. Next, to address adaptability,
I propose a framework based on multi-valued linear temporal logic syntax and
semantics that allows autonomous agents to perform model-checking on systems with
uncertainties. The search-based test-case generation framework provides safety assurance
guarantees through formalizing and monitoring Responsibility Sensitive Safety
(RSS) rules. I use the RSS rules in signal temporal logic as qualification specifications
for monitoring and screening the quality of generated test-drive scenarios. Furthermore,
to extend the existing temporal-based formal languages’ expressivity, I propose
a new spatio-temporal perception logic that enables formalizing qualification specifications
for perception systems. All-in-one, my test-generation framework can be
used for reasoning about the quality of perception, prediction, and decision-making
components in AV. Finally, my efforts resulted in publicly available software. One
is an offline monitoring algorithm based on the proposed logic to reason about the
quality of perception systems. The other is an optimal planner (model checker) that
accepts mission specifications and model descriptions in the form of multi-valued logic
and multi-valued sets, respectively. My monitoring framework is distributed with the
publicly available S-TaLiRo and Sim-ATAV tools.
ContributorsHekmatnejad, Mohammad (Author) / Fainekos, Georgios (Thesis advisor) / Deshmukh, Jyotirmoy V (Committee member) / Karam, Lina (Committee member) / Pedrielli, Giulia (Committee member) / Shrivastava, Aviral (Committee member) / Yang, Yezhou (Committee member) / Arizona State University (Publisher)
Created2021
Description
The holy grail of computer hardware across all market segments has been to sustain performance improvement at the same pace as silicon technology scales. As the technology scales and the size of transistors shrinks, the power consumption and energy usage per transistor decrease. On the other hand, the transistor density increases significantly by technology scaling. Due to technology factors, the reduction in power consumption per transistor is not sufficient to offset the increase in power consumption per unit area. Therefore, to improve performance, increasing energy-efficiency must be addressed at all design levels from circuit level to application and algorithm levels.
At architectural level, one promising approach is to populate the system with hardware accelerators each optimized for a specific task. One drawback of hardware accelerators is that they are not programmable. Therefore, their utilization can be low as they perform one specific function. Using software programmable accelerators is an alternative approach to achieve high energy-efficiency and programmability. Due to intrinsic characteristics of software accelerators, they can exploit both instruction level parallelism and data level parallelism.
Coarse-Grained Reconfigurable Architecture (CGRA) is a software programmable accelerator consists of a number of word-level functional units. Motivated by promising characteristics of software programmable accelerators, the potentials of CGRAs in future computing platforms is studied and an end-to-end CGRA research framework is developed. This framework consists of three different aspects: CGRA architectural design, integration in a computing system, and CGRA compiler. First, the design and implementation of a CGRA and its instruction set is presented. This design is then modeled in a cycle accurate system simulator. The simulation platform enables us to investigate several problems associated with a CGRA when it is deployed as an accelerator in a computing system. Next, the problem of mapping a compute intensive region of a program to CGRAs is formulated. From this formulation, several efficient algorithms are developed which effectively utilize CGRA scarce resources very well to minimize the running time of input applications. Finally, these mapping algorithms are integrated in a compiler framework to construct a compiler for CGRA
At architectural level, one promising approach is to populate the system with hardware accelerators each optimized for a specific task. One drawback of hardware accelerators is that they are not programmable. Therefore, their utilization can be low as they perform one specific function. Using software programmable accelerators is an alternative approach to achieve high energy-efficiency and programmability. Due to intrinsic characteristics of software accelerators, they can exploit both instruction level parallelism and data level parallelism.
Coarse-Grained Reconfigurable Architecture (CGRA) is a software programmable accelerator consists of a number of word-level functional units. Motivated by promising characteristics of software programmable accelerators, the potentials of CGRAs in future computing platforms is studied and an end-to-end CGRA research framework is developed. This framework consists of three different aspects: CGRA architectural design, integration in a computing system, and CGRA compiler. First, the design and implementation of a CGRA and its instruction set is presented. This design is then modeled in a cycle accurate system simulator. The simulation platform enables us to investigate several problems associated with a CGRA when it is deployed as an accelerator in a computing system. Next, the problem of mapping a compute intensive region of a program to CGRAs is formulated. From this formulation, several efficient algorithms are developed which effectively utilize CGRA scarce resources very well to minimize the running time of input applications. Finally, these mapping algorithms are integrated in a compiler framework to construct a compiler for CGRA
ContributorsHamzeh, Mahdi (Author) / Vrudhula, Sarma (Thesis advisor) / Gopalakrishnan, Kailash (Committee member) / Shrivastava, Aviral (Committee member) / Wu, Carole-Jean (Committee member) / Arizona State University (Publisher)
Created2015
Description
The rapid growth of data generated from Internet of Things (IoTs) such as smart phones and smart home devices presents new challenges to cloud computing in transferring, storing, and processing the data. With increasingly more powerful edge devices, edge computing, on the other hand, has the potential to better responsiveness, privacy, and cost efficiency. However, resources across the cloud and edge are highly distributed and highly diverse. To address these challenges, this paper proposes EdgeFaaS, a Function-as-a-Service (FaaS) based computing framework that supports the flexible, convenient, and optimized use of distributed and heterogeneous resources across IoT, edge, and cloud systems. EdgeFaaS allows cluster resources and individual devices to be managed under the same framework and provide computational and storage resources for functions. It provides virtual function and virtual storage interfaces for consistent function management and storage management across heterogeneous compute and storage resources. It automatically optimizes the scheduling of functions and placement of data according to their performance and privacy requirements. EdgeFaaS is evaluated based on two edge workflows: video analytics workflow and federated learning workflow, both of which are representative edge applications and involve large amounts of input data generated from edge devices.
ContributorsJin, Runyu (Author) / Zhao, Ming (Thesis advisor) / Shrivastava, Aviral (Committee member) / Sarwat Abdelghany Aly Elsayed, Mohamed (Committee member) / Arizona State University (Publisher)
Created2021