Multithreaded constraint programming and applications.
Item
-
Title
-
Multithreaded constraint programming and applications.
-
Identifier
-
AAI9924858
-
identifier
-
9924858
-
Creator
-
Zabatta, Fabian.
-
Contributor
-
Adviser: Kenneth McAloon
-
Date
-
1999
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
Constraint programming is a powerful and robust software technology for modeling and solving difficult combinatorial problems. However, as problems grow larger in scale and complexity, they become increasingly difficult to solve and their execution times can exhibit inordinate growth. One solution is multithreaded parallelization. Multithreaded parallelization can greatly improve performance, not only increasing the size of solvable problems but also improving solutions that were previously limited by time.;This thesis addresses the fundamental issues concerning the problem of application-based multithreaded constraint programming. The focus of the thesis is on methods for achieving application-based parallelism in constraint programming using threads. Included are the presentations of algorithms such as Dynamic Thread Creation, a new dynamic load balancing scheme specific to multithreading and the Multithreaded Least Discrepancy Search and the Multithreaded Best-First With Backtracking Search, two new parallel search strategies that break away from the classic backtracking schemes normally associated with constraint programming. These new algorithms are applied to benchmark problems with data from the literature and empirical results are reported.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
