Back to search

Hosted by Utah State University Libraries

A Field Programmable Gate Array Based Finite-Domain Constraint Solver

Abstract

dc:description.abstract

Constraint satisfaction and optimization techniques are commonly employed in scheduling, industrial manufacturing, and automation processes where concepts from Operations Research (OR) and Artificial Intelligence (AI) are applied. In embedded systems, Constraint Satisfaction Problem (CSP) finds use in design, synthesis, and optimization. However, most application areas of CSP employ offline solving techniques where design requirements and constraints are captured before the system is deployed online. There is a significant amount of pre-planning and human intervention required. In embedded systems, online constraint solving techniques are primarily used as onboard control software in order to enable a system that can dynamically adapt to a changing environment (e.g., autonomous mission planning). This is possible because by using constraint-solving techniques, the constraint model is inherently separated from the underlying algorithms employed for solving the constraints. Due to this separation of concerns, a variety of problems can be solved. The domain of dynamic scheduling is considered in this thesis and can be considered a part of onboard control software for embedded systems. Scheduling problems in particular are amenable to CSP techniques since the discrete start times that govern the execution of various tasks can be formulated as the output of several constraints. In its primitive form, the definition of a schedule includes temporal dependency constraints and resource constraints. Many dynamic schedulers, however, are also required to take configuration constraints of the system into account. Using CSP techniques for scheduling algorithms provides intelligent scheduling and enables the embedded system to be more adaptable to dynamic changes in the environment. This thesis discusses the development of a parallel finite-domain constraint solver in order to perform online constraint satisfaction for embedded systems. By modeling the scheduling problem as a CSP problem, the embedded system becomes flexible and adaptable to dynamic changes in the environment since it can accommodate a range of constraints apart from precedence and resource constraints. The features of this solver are that it is implemented in a platform with multiple soft-core processors with distributed memory architecture. The constraints for the application problem are captured from a Data Flow Graph (DFG) and solved on this platform. A tool is also developed that automates the partitioning of the given application and also configures the underlying framework for executionof the CSP problem.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
Hosted by Utah State University Libraries

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Subramanian, Prasad
Contributors dc:contributor
  • Brandon Eames
  • Aravind Dasu
  • Jacob Gunther

Subjects

dc:subject × 1

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Utah State University
Base URL
digitalcommons.usu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Subramanian, Prasad. A Field Programmable Gate Array Based Finite-Domain Constraint Solver. Thesis thesis, Hosted by Utah State University Libraries, https://digitalcommons.usu.edu/etd/99