Ph.D. Dissertation Defense: Adrian Sapio

Monday, October 21, 2019
10:00 a.m.
AVW2328
Maria Hoo
301 405 3681
mch@umd.edu

ANNOUNCEMENT: Ph.D. Dissertation Defense

Name: Adrian Sapio

Committee:
Professor Shuvra Bhattacharyya, Chair/Advisor

Professor Marilyn Wolf
Professor Rajeev Barua
Professor Richard La
Professor Balakumar Balachandran, Dean’s Representative

Date/time: Monday,  October 21, 2019 at 11am-1pm

Location:   AVW2328  

Title: Runtime Adaptation in Embedded Computing Systems using Markov Decision Processes


Abstract:

During the design and implementation of embedded computing systems (ECSs),
engineers must make assumptions on how the system will be used after being
built and deployed. These assumptions are typically used to balance multiple
conflicting performance objectives, and they have a significant effect on how
well the system ultimately performs in the deployed environment. Traditionally,
these important decisions were made at design time for a fleet of ECSs prior to
deployment. In contrast to this approach, this research explores and develops
techniques to enable adaptation of ECSs at runtime to the environments and
applications in which they operate. Adaptation is enabled such that the usage
assumptions and performance optimization decisions can be made autonomously at
runtime in the deployed system.

This thesis utilizes Markov Decision Processes (MDPs), a powerful and
well established mathematical framework used for decision making under
uncertainty, to control computing systems at runtime.
The resulting control is performed in ways that are
more dynamic, robust and adaptable than alternatives in many scenarios.

The techniques developed in this thesis are first applied to a
reconfigurable embedded digital signal processing system. In this
effort, several challenges are encountered and resolved using novel
approaches. These include the use of transition states to accurately
model a wide range of the processing system dynamics, a scalarization
approach to employ the MDP within a multiobjective optimization
framework, and the factorization of system states into internal and
external groupings for efficient representation and embedded
computation. Through extensive simulations and a prototype
implementation, the robustness of the adaptation is demonstrated in
comparison with the prior state-of-the-art.

The thesis continues by developing an efficient algorithm for conversion of MDP
models to actionable control policies --- a required step known as solving the
MDP. The solver algorithm is developed in the context of ECSs that contain
general purpose embedded GPUs (graphics processing units). Common examples of
these GPU-accelerated ECSs can be found in robotics, automobiles and
smartphones. The novel solver algorithm, Sparse Parallel Value Iteration
(SPVI), makes use of the parallel processing capabilities provided by such
GPUs, and also exploits the sparsity that typically exists in MDPs when used to
model and control ECSs. The result is a GPU algorithm that leverages sparse
linear algebra techniques to outperform the state-of-the-art in GPU-accelerated
solvers on several MDPs encountered. SPVI also lifts restrictions required by
other MDP solver approaches, making it more widely compatible with large
classes of adaptation problems.

To extend the applicability of the runtime adaptation techniques to
smaller and more strictly resource constrained ECSs, another solver ---
Sparse Value Iteration (SVI) is developed for use on microcontrollers.
The method is explored in a detailed case study involving a cellular
(LTE-M) connected sensor that adapts to varying communications profiles.
Such time-varying and installation-specific variations are an
unavoidable reality for Internet of Things (IoT) devices that must
contend with wireless networks that are congested during peak hours, as
well as installation locations that may have weak signal strength and
poor cellular coverage. The case study reveals that the proposed
adaptation framework outperforms a competing approach based on
Reinforcement Learning (RL) in terms of robustness and adaptation, while
consuming comparable resource requirements. Additionally, the aspects of
ECSs that make the proposed technique preferable over RL are quantified
and explored for the benefit of future ECS designers and engineering
practitioners.

Finally, the thesis concludes by analyzing the various logistical
challenges that exist when deploying MDPs on ECSs. In response to
these challenges, the thesis contributes an open source software package
to the engineering community. The software package is targeted to a
specific family of ECSs --- the NVIDIA Jetson platform, and is designed
for future retargetability to other platforms. The software package
contains several useful components that have been generated during the
multi-year effort of working with MDPs on resource constrained ECSs. The
package contains libraries of MDP solvers, parsers, datasets and
reference solutions, which provide a comprehensive infrastructure for
working with and understanding trade-offs among existing embedded MDP
techniques, and experimenting with novel approaches. 

 

 

Audience: Graduate  Faculty 

remind we with google calendar

 

March 2024

SU MO TU WE TH FR SA
25 26 27 28 29 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 1 2 3 4 5 6
Submit an Event