首页>
外国专利>
Processor allocation method and apparatus for multiprocessor execution of a constraint satisfaction search
Processor allocation method and apparatus for multiprocessor execution of a constraint satisfaction search
展开▼
机译：用于多处理器执行约束满足搜索的处理器分配方法和装置
展开▼
页面导航
摘要
著录项
相似文献
摘要
Apparatus and method for minimizing, in a multiprocessor system, a variance in a search effort along different subtrees of a backtrack search tree employed for solving an instance of a constraint- satisfaction problem. A method includes the steps of (a) estimating an amount of search effort required for different subtrees of the search tree, (b) allocating an appropriate number of processors to each of the different subtrees of the search tree based upon the estimated amount of search effort, the number of processor allocated to each of the subtrees being selected to minimize a variance in search processing time along the different subtrees, and (c) executing the search with the allocated processors in parallel along the different subtrees of the search tree. The step of allocating an appropriate number of processors includes the steps of (a) dividing the search tree into N( M) subspaces and (b) assigning the M processors to the subspaces in proportion to the estimated effort involved in searching the subspaces.
展开▼
