Boots – shoes – and leggings
Patent
1991-12-30
1992-09-08
Fleming, Michael R.
Boots, shoes, and leggings
395 51, 364134, G06F 1518
Patent
active
051465400
ABSTRACT:
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.
REFERENCES:
Janakiram et al., "A Randomized Parallel Backtracking Algorithm", IEEE Trans. on Computers, 37, 12, Dec. 1988, pp. 1665-1676.
Polychronopoulos et al., "Processor Allocation for Horizontal and Vertical Parallelism and Related Speed Up Bounds," IEEE Trans. on Computers, C-36, 4, Apr. 1987, pp. 410-420.
Bokhari, S. H., "Partitioning Problems in Parallel, Pipelined, and Distributed Computing," IEEE Trans. on Computers, 37, 1, Jan. 1988, pp. 48-57.
Wah et al., "MANIP-A Multicomputer Architecture for Solving Combinatorial Extremum-Search Problems," IEEE Trans. Computers, C-33, 5, May 1984, pp. 377-390.
Sahni, S., "Scheduling Multipipeline and Multiprocessor Computers," IEEE Trans. on Computers, C-33, 7, Jul. 1984, pp. 637-645.
"Parallel Lookahead Technique for Constraint Satisfaction" IBM Technical Disclosure Bulletin, vol. 31, No. 10 Mar. 1989.
"Estimating the Size of a Backtrack Search During the Search Operation" IBM Technical Disclosure Bulletin, vol. 30, No. 8 Jan. 1988.
D. E. Knuth, "Estimating the Efficiency of Backtrack Programs", Mathematics of Computation, vol. 29, 1975, pp. 121-136.
Downs Robert W.
Fleming Michael R.
International Business Machines Corp.
LandOfFree
Processor allocation method and apparatus for multiprocessor exe does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processor allocation method and apparatus for multiprocessor exe, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processor allocation method and apparatus for multiprocessor exe will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-140483