Nagging: A scalable fault-tolerant paradigm for distributed search. (English) Zbl 0999.68048
Summary: This paper describes nagging, a technique for parallelizing search in a heterogeneous distributed computing environment. Nagging exploits the speedup anomaly often observed when parallelizing problems by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is both fault tolerant and robust to long message latencies. In this paper, we show how nagging can be used to parallelize several different algorithms drawn from the artificial intelligence literature, and describe how nagging can be combined with partitioning, the more traditional search parallelization strategy. We present a theoretical analysis of the advantage of nagging with respect to partitioning, and give empirical results obtained on a cluster of 64 processors that demonstrate nagging’s effectiveness and scalability as applied to \(A^{*}\) search, \(\alpha \beta\) minimax game tree search, and the Davis–Putnam algorithm.
Keywords:
parallel/distributed search algorithms; search pruning; game tree search; branch and bound; Boolean satisfiabilityReferences:
| [1] | D. Applegate, R. Bixby, W. Cook, and V. Chvátal, On the solution of traveling salesman problems, Technical Report 98744, Center for Research on Parallel Computation, Rice University, Houston, TX, July 1998; D. Applegate, R. Bixby, W. Cook, and V. Chvátal, On the solution of traveling salesman problems, Technical Report 98744, Center for Research on Parallel Computation, Rice University, Houston, TX, July 1998 · Zbl 0904.90165 |
| [2] | Beguelin, A.; Dongarra, J.; Jiang, W.; Manchek, R.; Sunderam, V., PVM Users Guide and Reference Manual (1994), Oak Ridge National Laboratory: Oak Ridge National Laboratory Oak Ridge, TN |
| [3] | Brockington, M.; Schaeffer, J., APHID: Asynchronous parallel game-tree search, J. Parallel Distributed Comput., 60, 2, 247-273 (2000) · Zbl 0954.68064 |
| [4] | Cook, D.; Varnell, R. C., Adaptive parallel iterative deepening search, J. Artificial Intelligence Res., 9, 139-166 (1998) · Zbl 0910.68059 |
| [5] | Cook, S., The complexity of theorem-proving procedures, (Proc. 3rd Annual ACM Symposium on the Theory of Computing (1971)), 151-158 · Zbl 0253.68020 |
| [6] | Davis, M.; Logemann, G.; Loveland, D., A machine program for theorem-proving, Comm. ACM, 5, 7, 394-397 (1962) · Zbl 0217.54002 |
| [7] | W. Ertel, Performance analysis of competitive or-parallel theorem proving, Technische Universität München, FKI-162-91, 1992; W. Ertel, Performance analysis of competitive or-parallel theorem proving, Technische Universität München, FKI-162-91, 1992 |
| [8] | Feldmann, R.; Mysliwietz, P.; Monien, B., Game tree search on a massively parallel system, (van den Herik, H.; Herschberg, I.; Uiterwijk, J., Advances in Computer Chess VII (1994), University of Limburg: University of Limburg Maastricht, the Netherlands), 203-218 |
| [9] | Ferguson, C.; Korf, R. E., Distributed tree search and its application to alpha-beta pruning, (Proc. AAAI-88, St. Paul, MN (1988)), 128-132 |
| [10] | S.L. Forman, Torsion angle selection and emergent non-local secondary structure in protein structure prediction, Ph.D. Thesis, Department of Mathematics, The University of Iowa, Iowa City, IA, August 2001; S.L. Forman, Torsion angle selection and emergent non-local secondary structure in protein structure prediction, Ph.D. Thesis, Department of Mathematics, The University of Iowa, Iowa City, IA, August 2001 |
| [11] | Foster, I.; Kesselman, C., Globus: A metacomputing infrastructure toolkit, Internat. J. Supercomput. Appl. High Performance Comput., 11, 2, 115-128 (1997) |
| [12] | Gomes, C.; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. Automat. Reasoning, 24, 1-2, 67-100 (2000) · Zbl 0967.68145 |
| [13] | Grama, A.; Kumar, V., Parallel search algorithms for discrete optimization problems, ORSA J. Comput., 7, 4, 365-385 (1995) · Zbl 0843.90098 |
| [14] | Grama, A.; Kumar, V., State of the art in parallel search techniques for discrete optimization problems, IEEE Trans. Knowledge Data Engrg., 11, 1, 28-35 (1999) |
| [15] | Gropp, W.; Lusk, E.; Doss, N.; Skjellum, A., A high-performance, portable implementation of the MPI message-passing interface standard, Parallel Comput., 22, 6, 789-828 (1996) · Zbl 0875.68206 |
| [16] | Gu, J.; Purdom, P. W.; Franco, J.; Wah, B. W., Algorithms for the satisfiability (SAT) problem: A survey, (Satisfiability Problem: Theory and Applications. Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1997), American Mathematical Society: American Mathematical Society Providence, RI), 19-151 · Zbl 0945.03040 |
| [17] | Joerg, C.; Kuszmaul, B., Massively parallel chess, (Proc. Third DIMACS Parallel Implementation Challenge, Rutgers University, Rutgers, NJ (1994)) · Zbl 0881.68059 |
| [18] | Knuth, D. E.; Moore, R. W., An analysis of alpha-beta pruning, Artificial Intelligence, 6, 4, 293-326 (1975) · Zbl 0358.68143 |
| [19] | Lai, T. H.; Sahni, S., Anomalies in parallel branch-and-bound algorithms, Comm. ACM, 27, 4, 594-602 (1984) · Zbl 0587.68032 |
| [20] | Lawler, E.; Wood, D., Branch and bound methods: A survey, Oper. Res., 14, 4, 699-719 (1966) · Zbl 0143.42501 |
| [21] | Lee, E., Statistical Methods for Survival Data Analysis (1992), Wiley: Wiley New York |
| [22] | Litzkow, M.; Livny, M.; Mutka, M., Condor: A hunter of idle workstations, (Proc. Eighth Conference on Distributed Computing Systems, San Jose, CA (1988)) |
| [23] | Mahanti, A.; Daniels, C. J., A SIMD approach to parallel heuristic search, Artificial Intelligence, 60, 2, 243-282 (1993) |
| [24] | Mann, N.; Schafer, R.; Singpurwalla, N., Methods for Statistical Analysis of Reliability and Life Data (1974), Wiley: Wiley New York · Zbl 0339.62070 |
| [25] | Meeker, W.; Escobar, L., Statistical Methods for Reliability Data (1998), Wiley: Wiley New York · Zbl 0949.62086 |
| [26] | Mitchell, D.; Selman, B.; Levesque, H., Hard and easy distributions of SAT problems, (Proc. AAAI-92, San Jose, CA (1992)), 459-465 |
| [27] | Newell, A.; Shaw, J.; Simon, H., Chess playing programs and the problem of complexity, IBM J. Res. Development, 2, 320-335 (1958) |
| [28] | Nilsson, N., Problem-Solving Methods in Artificial Intelligence (1971), McGraw Hill: McGraw Hill New York |
| [29] | Norvig, P., Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA |
| [30] | Paarsch, H. J.; Segre, A. M., Extending the computational horizon: Effective distributed resource-bounded computation for intractable problems, (Proc. Fifth International Conference of the Society for Computational Economics (1999)) |
| [31] | Powley, C.; Ferguson, C.; Korf, R. E., Depth-first heuristic search on a SIMD machine, Artificial Intelligence, 60, 2, 199-242 (1993) |
| [32] | Reinefeld, A.; Schnecke, V., Work-load balancing in highly parallel depth-first search, (Proc. 1994 Scalable High-Performance Computing Conference (1994)), 773-780 |
| [33] | Reinelt, G., The Traveling Salesman: Computational Solutions for TSP Applications (1994), Springer: Springer Berlin · Zbl 0825.90720 |
| [34] | Segre, A. M.; Elkan, C. P.; Russell, A., A critical look at experimental evaluations of EBL, Machine Learning, 6, 2, 183-196 (1991) |
| [35] | Segre, A. M.; Sturgill, D. B., Using hundreds of workstations to solve first-order logic problems, (Proc. AAAI-94, Seattle, WA (1994)), 187-192 |
| [36] | Selman, B.; Levesque, H.; Mitchell, D., A new method for solving hard satisfiability problems, (Proc. AAAI-92, San Jose, CA (1992)), 440-446 |
| [37] | Selman, B.; Mitchell, D.; Levesque, H., Generating hard satisfiability problems, Artificial Intelligence, 81, 17-29 (1996) · Zbl 1508.68347 |
| [38] | Stephens, M. A., EDF statistics for goodness of fit and some comparisons, J. Amer. Statist. Soc., 69, 720-727 (1974) |
| [39] | Sturgill, D. B.; Segre, A. M., Nagging: A distributed adversarial search-pruning technique applied to first-order logic, J. Automat. Reasoning, 19, 3, 347-376 (1997) · Zbl 0884.68116 |
| [40] | Sturgill, D. B.; Segre, A. M., A novel asynchronous parallelization scheme for first-order logic, (Proc. Twelfth Conference on Automated Deduction (1994)), 484-498 · Zbl 1433.68568 |
| [41] | C. Whittinghill, Social choice and resource allocation in a professional sports league, Ph.D. Thesis, Department of Economics, The University of Iowa, Iowa City, IA, 1999; C. Whittinghill, Social choice and resource allocation in a professional sports league, Ph.D. Thesis, Department of Economics, The University of Iowa, Iowa City, IA, 1999 |
| [42] | Wilcoxon, F., Individual comparisons by ranking methods, Biometrics, 1, 80-83 (1945) |
| [43] | Zhang, W., State-Space Search: Algorithms, Complexity, Extensions, and Applications (1999), Springer: Springer Berlin · Zbl 0942.90001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
