The main topic of this dissertation involves cluster-based computing, specifically relating to computations performed on Beowulf clusters. I have developed a light-weight library for dynamic interoperable message passing, called the InterCluster Interface (ICI). This library not only supports computations performed over multiple clusters that are running different Message Passing Interface (MPI) implementations, but also can be used independently of MPI. In addition I developed the Backtracking Framework (BkFr) that simplifies implementations of the parallel backtracking paradigm in the single cluster environment, and supports the extension of computations over multiple clusters. BkFr uses MPI for the intra-cluster communication and ICI for the inter-cluster communication. I have also developed a template-based library of programming modules that facilitate the introduction of the rapidly emerging message passing parallel computing paradigm in upper-division undergraduate courses.
An important application of ICI and the backtracking framework discussed in this dissertation is the computation of Van der Waerden numbers, which involve the existence of arithmetic progressions in arbitrary partitions of {1, 2, …, n} for sufficiently large n. The computations of these numbers utilized a special SAT solver that I developed. For example, I almost doubled the previously known lower bound for the Van der Waerden number W(2, 6), and I am running a calculation whether the lower bound is actually the exact value. Among other reductions, I was able to drastically reduce the search for potential solutions with the aid of a tunneling technique based on an aggressive addition of uninferred constraints. The tunneling technique has the likely potential to be used in a number of other satisfiability settings. I also developed an FPGA version of my SAT solver for Van der Waerden numbers that improved the search speed up to 230 times or more compared to its sequential equivalent. Utilizing this special SAT solver has resulted in significant progress in the search to determine bounds or exact values for Van der Waerden numbers and, more generally, for Van der Waerden subnumbers. I have found the exact values for several of these subnumbers, specifically W(2; 5,6)=206, W(2; 4,8)=146, W(2; 3,16)=238 and W(3; 2,4,7)=119.