Let's say that you have 16 processors. You are trying to solve the 0-1 knapsack problem for 40 items. Each item i has size S[i], and you need to find the subset of items which sums as close to T as possible without exceeding T.
Pick four of items. There are 16 possible combinations of those items: 0000 (none of those 4 items included) 0001 (only item #1 included) ... 1111 (all four items included) You will essentially ask each of the 16 processors to solve the knapsack problem for 36 items, starting with one of the 16 possible combiations of the 4 items. Processor 0 will start with none of the first 4 items. Processor 15 will start with all of them, and the other processors will start with a different subset of the items. It may seem like solving the problem for 36 items is not much different than 40, but it requires 1/16th of the work. When each processor is done, it knows the best solution including its assigned items from among the first 4 items. To find the overall best solution you just need to compare the 16 solutions and pick the one best. A possible improvement is to divide up the problem into more parts and farm them out to the processors as they become available. This would work better if you don't have a power of 2 number of processors. It also would reduce the tendancy for some processors to finish early and sit idle while one or two take longer to finish their portion of the work. Don On Mar 28, 9:51 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote: > @Don: I am not clear with your explanation. Please can you give me an > example? > > > > > > On Wed, Mar 28, 2012 at 6:19 AM, Don <dondod...@gmail.com> wrote: > > If you have n processors, start with the n possible ways to select > > from log2 n items. Assign each processor to find a solution based on > > the resulting subset of remaining items. Each processor should be able > > to work fairly independently, and when they are done, they can compare > > results and find the best one. > > Don > > > On Mar 27, 10:47 pm, Arun Vishwanathan <aaron.nar...@gmail.com> wrote: > > > Hi all, > > > > I am planning to implement a parallel version of the 0-1 knapsack > > problem. > > > I tried reading up a bit and there are few suggestions here and there. > > > However I would like to know if anyone has an idea or links that I cud > > > refer for this? The main problem in parallelizing a DP algorithm is the > > > dependencies due to recursion? Is there an effective strategy for this?? > > > Using shared memory or message passing approach? > > > > Arun > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily."- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
