Transputer网络上分布式组合搜索的效率  

Efficiency of Distributed Combinatorial Search on Transputer Network

作　　者：孙凝晖[1] 李国杰[1] 

机构地区：[1]国家智能计算机研究开发中心

出　　处：《中国科学院研究生院学报》1994年第1期104-111,共8页Journal of the Graduate School of the Chinese Academy of Sciences

摘　　要：Ｔｒａｎｓｐｕｔｅｒ网络是一种典型的消息传送型多处理机系统，无论是传统的数值计算，还是人工智能的动态非确定搜索问题，都可以得到加速处理。本文研究如何在Ｔｒａｎｓｐｕｔｅｒ网络上高效地实现分布式组合搜索。针对搜索的动态非确定性，我们提出一种异步通讯模式，以及Ｔｒａｎｓｐｕｔｅｒ上并行搜索的负载平衡算法。我们实现了最佳优先和启发式导向的深度优先两种策略的分布式分枝限界算法（Ｂｒａｎｃｈ－ａｎｄ－Ｂｏｕｎｄ），应用于求解旅行推销员问题（ＴＳＰ），在１６个Ｔｒａｎｓｐｕｔｅｒ上获得了较好的并行效率。Transputer network is a typical multiprocessor system based on message passing, on which either computing in digital valuc field or dynamical nonderminative search in AI can be speeded up. In the paper implemcntation efficiency of distributed combinatorial search on Transputer network is studied.Based on dynamical non-dermination of combinatorial search, one kind of asynchronous communication model and load balance algorithm of parallel search on Transputer are proposed. Best-first and guided depth-first method of distributed branch-and-bound algorithm are implemented. When they are applied to TSP problems, better efficiency is gained on 16 nodes Transputer network.

关 键 词：TRANSPUTER 分布式 组合搜索算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]