distributed.net
(Answer) (Category) distributed.net Faq-O-Matic : (Category) Project: OGR (Optimal Golomb Rulers) : (Answer) Why are some stubs marked with an asterisk (*)? Why are they called combined? Why are they bigger than others?

Sometimes you can see a stub marked with an asterisk (*) on the end. This stub usually takes more time to process than its neighbors. Such stubs are called combined.

When the sum of all marks in the stub increases, the amount of work required to check this stub decreases dramatically; with a high initial sum, there will be fewer combinations to check. Without optimization, this will lead to hundreds of stubs where each one takes only a few seconds to process. To reduce load on the network and proxy servers and to reduce the amount of disk space required to store results on our master server, these tiny stubs are combined into a single packet.

For example, we have stubs from 27/1-2-60-8-4-1 to 27/1-2-60-8-4-99 to check. Even if the first stubs in the list have a reasonable length (we could complete them in 1 or 2 hours), the last ones are so small that they will require only a fraction of a second to complete. So the master server combines all of the tiny stubs, starting from some point, into a single packet - in our case it will be "27/1-2-60-8-4-19*". Now the master server will have to generate and track only 19 work units instead of 99.

When the client software processes the initial stub (27/1-2-60-8-4-19) and finds that the "combined" flag is set, instead of reporting its result back to the master server, it automatically increases the last mark (number) in the stub and processes the new stub, and so on, until it hits some known limit. In our example, the client will automatically process:

27/1-2-60-8-4-19
27/1-2-60-8-4-20
.... and so on until ....
27/1-2-60-8-4-99 -- let it be the limit for our example.

The sum of all of the results will be sent back in one reply.

Combined stubs are generated automatically by the master server when the sum of all marks in a stub exceeds a predefined threshold. Since this algorithm is quite simple and the size of each stub varies significantly along the tree, some very big work units can be generated. We're trying to use thresholds which will keep them within reasonable limits, but the exact sizes of combined stubs are almost unpredictable.


This document is: http://faq.distributed.net/?file=298
[Search] [Appearance] [Show Expert Edit Commands]
This is a Faq-O-Matic 2.721.test.

© Copyright distributed.net 1997-2013 - All rights reserved