DIB—a distributed implementation of backtracking

ABSTRACT

DIB is a general-purpose package that allows a wide range of applications such as recursive backtrack, branch and bound, and alpha-beta search to be implemented on a multicomputer. It is very easy to use. The application program needs to specify only the root of the recursion tree, the computation to be performed at each node, and how to generate children at each node. In addition, the application program may optionally specify how to synthesize values of tree nodes from their children's values and how to disseminate information (such as bounds) either globally or locally in the tree. DIB uses a distributed algorithm, transparent to the application programmer, that divides the problem into subproblems and dynamically allocates them to any number of (potentially nonhomogeneous) machines. This algorithm requires only minimal support from the distributed operating system. DIB can recover from failures of machines even if they are not detected. DIB currently runs on the Crystal multicomputer at the University of Wisconsin-Madison. Many applications have been implemented quite easily, including exhaustive traversal (N queens, knight's tour, negamax tree evaluation), branch and bound (traveling salesman) and alpha-beta search (the game of NIM). Speedup is excellent for exhaustive traversal and quite good for branch and bound.

REFERENCES

• 1: AKL, S. G., BARNARD, D. T., AND DORAN, R.J. Simulation and analysis in deriving time and storage requirements for a parallel alpha-beta algorithm. In Proceedings of the 1980 International Con{erence on Parallel Processing (Columbus, Oh., Aug. 1980). IEEE, New York, 1980, pp. 231-234.
• 2: BAUDET, G. M. The design and analysis of algorithms for asynchronous multiprocessors. Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pa., (Apr. 1978).
• 3: BURTON, F. W. Controlling speculative computation in a parallel functional programming language. In Proceedings o{ the 5th International Con{erence on Distributed Computing Systems (Denver, Colo., May 1985), IEEE, New York, 1985, pp. 453-458.
• 4: COOK, R., FINKEL, R., DEWITT, D., LANDWEBER, L., AND VIROILIO, T. The Crystal nugget: Part I of the first report on the Crystal project. Tech. Rep. 499. Computer Sciences Department, University of Wisconsin, Madison, Wisc., Apr. 1983.
• 5: D. J. DeWitt , R. Finkel , M. Solomon, The crystal multicomputer: design and implementation experience, IEEE Transactions on Software Engineering, v.13 n.8, p.953-966, Aug. 1987 [doi>10.1109/TSE.1987.233513]
• 6: FINKEL, R. A., AND FISHBURN, J. P. Parallelism in alpha-beta search. Arti{. InteU. 19, 1 (Sept. 1982).
• 7: FINKEL, R. A., AND FISHBURN, J.P. Improved speedup bounds for parallel alpha-beta search. IEEE Trans. Pattern Analysis and Machine Intelligence PAMI-5, 1 (Jan. 1983).
• 8: FISHBURN, J. A., AND FINKEL, R. A. Quotient networks. IEEE Trans. Cornput. C-31, 4 (Apr. 1982), 288-295.
• 9: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 10: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 11: Robert H. Halstead, Jr., MULTILISP: a language for concurrent symbolic computation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.4, p.501-538, Oct. 1985 [doi>10.1145/4472.4478]
• 12: IMAI, M., FUKUMURA, T., AND YOSHIDA, Y. A parallelized branch-and-bound algorithm: Implementation and efficiency. Syst. Comput. Control 10, 3 (1979).
• 13: KASAHARA, H., AND NARITA, S. Parallel processing of robot-arm control computation on a multiprocessor system. IEEE J. Robotics and Automation RA-1 (June 1985), 104-113.
• 14: KNWrH, D. E., AND MOORE, R.W. An analysis of alpha-beta pruning. Arti{. lntelL 6, 4 (Winter 1975), 293-326.
• 15: Ten-Hwang Lai , Sartaj Sahni, Anomalies in parallel branch-and-bound algorithms, Communications of the ACM, v.27 n.6, p.594-602, June 1984 [doi>10.1145/358080.358103]
• 16: LAI, T.-H. AND SPRAGUE, A. Performance of branch-and-bound algorithms. IEEE Trans. Comput. C-34 (Oct. 1985), 962-964.
• 17: LAWLER, E. L., AND WOOD, D. Branch and bound methods: A survey. Oper. Res. 14, 4 (1966), 699-719.
• 18: LI, G.-J., AND WAH, B.W. Computational efficiency of parallel approximate branch-and-bound algorithms. In Proceedings o{ the 1984 International Con/erence on Parallel Processing (Columbus, Oh., Aug. 1984), IEEE, New York, 1984.
• 19: LIVNY, M., AND MANBER, U. Distributed computation via active messages. IEEE Trans. Comput. C-34, 12 (Dec. 1985), 1185-1190.
• 20: Udi Manber, On maintaining dynamic information in a concurrent environment, SIAM Journal on Computing, v.15 n.4, p.1130-1142, Nov. 1986 [doi>10.1137/0215082]
• 21: MOHAN, J. Experience with two parallel programs solving the traveling salesman problem. In Proceedings o{ the International Conference in Parallel Processing (Columbus, Oh., Aug. 1983), IEEE, New York, 1983, pp. 191-193.
• 22: MOLLER-NIELSEN, P., AND STAUNSTRUP, J. Experiments with a multiprocessor. Tech. Rep. PB-185. Computer Science Department, Aarhus University, Aarhus, Denmark (Nov. 1984).
• 23: Michael Lee Scott, Design and implementation of a distributed systems language (crystal, charlotte, lynx, soda), 1985
• 24: TAMURA, N., AND KANEDA, Y. Implementing parallel prolog on a multi-processor machine. In IEEE 1984 International Symposium on Logic Programming (Atlantic City, N.J., Feb. 1984), IEEE, New York, 1984, pp. 42-48.
• 25: VORNBERGER, O. Graph problems solved on a parallel system. Workshop on Graph Theoretic Concepts in Computer Science, Schloss Schwanberg, West Germany (1985).
• 26: WIRTH, N. Modula: A language for modular multiprogramming. Softw. Prac. Exper. 7, 1 (1977), 3-35.

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking; Concurrency
      D.4.5 Reliability
          Subjects: Fault-tolerance
      D.4.7 Organization and Design
          Subjects: Distributed systems

General Terms:
Algorithms, Design, Reliability