Yafu

[bsquared]

Originally Posted by jasonp

Smaller problems don't have N times the range to be divided up, especially for e.g. degree 5 jobs near 110 digits, or degree 4 jobs below ~95 digits. Degree 4 jobs around 100-110 digits will definitely benefit from splitting the A4 range, and possibly from splitting a single A4. The other thing to note is that is that you have to get over 140 digits before a single A5 has enough blocks of work to do that you can assign them randomly to threads and expect not to duplicate any work. In a perfect world you could assign both the special-q range and the A4/5/6 range to the library.

I guess I wasn't completely aware of some of these alternatives. Right now I just split things up using the leading coefficient. I give each of N threads a smallish chunk of A4/5 to work on and loop until "deadline/N" seconds have elapsed. Or, I could loop until "deadline" seconds have elapsed, which will cover N times the coefficient space. I hadn't thought about assigning each thread the *same* range of coefficients, and relying on internal randomness within each coefficient range. And as far as I know, there's no way to assign special_q from the top level (i.e., at the msieve_obj level).

Its an easy enough change to just make an optional parameter (something to put in yafu.ini, for example) to choose betweeen fast (/N), broad (*N), or thorough (same range).

[bsquared]

Originally Posted by Karl M Johnson

My opinion - true parallelization is doing the same task(s), only in parallel.
Ideally, this is N times faster than single-threaded variant.
When this cant be done(or hard to do, or inefficient), an alternative way is to launch N threads, each doing its own job on its own range.

I appreciate your thoughts. I'm somewhat limited here by the interface to the code - splitting things up by range is really all I can do. So the question becomes which ranges make the overall task most efficient?

Parallelization in general is usually an interesting problem. Often times the lowest level nuts & bolts type code doesn't scale very well - data dependencies, memory access latencies and the like can hamper parallelization. The trick is to find ways to divide up a problem into separate independent tasks and that only touch each other rarely, if at all.

[Karl M Johnson]

Originally Posted by bsquared

So the question becomes which ranges make the overall task most efficient?

Oh, I'm not the guy to ask, but it would be nice if the user(optionally, using a flag or something like that) could specify the range, on which to perform the polynomial selection, like in Msieve. Since YAFU will use Msieve, it should be possible, yes ?

I did this little research on Msieve's stage1 polyselect, and 1M-1.01M and 100M-100.01M quickly generated candidates. However, it is not enough information to build a decision upon.



Oh, and what I ment to say, the "true" variant would split a certain specified(or built-in) range(say, 1,10000) by N.
If the CPU has 4 cores, then it would be something like 1,2.5k ; 2.5k,5k ; 5k,7.5k ; 7.5k,10k.
This way, it's up to N times(in average) faster.

The second way is to assign independent ranges to N cores.
It's similar to the "true" way, yet it's just with less control, somewhat.

[chris2be8]

Originally Posted by bsquared

I've just about finished with a fairly major overhaul of NFS within yafu. One of the changes is parallelizing the poly searching (using msieve still, of course). A question I have is, is it better to divide the time deadline by N, or multiply the space searched by N? In other words, would you rather get done with the poly search N times faster over approximately the same coefficient range, or search N times the coefficient range in the same amount of time as a serial task would take?

I vote for dividing the time by N. So upgrading from cores to 4 cores would do nearly everything twice as fast and finish in half the time.

Chris K

[bsquared]

Originally Posted by chris2be8

I vote for dividing the time by N. So upgrading from cores to 4 cores would do nearly everything twice as fast and finish in half the time.

Chris K

I've made it so that 'fast' searching is what it does by default. There will also be a new option to specify 'wide' or 'deep' searching for searching N times more leading coefficients or for searching each leading coefficient with N threads.

So far everything is working nicely, but it needs more testing before I release the new version. There are many new command line or .ini file options, and I want to be sure they play nicely together and that I haven't created opprotunities to stomp on data files, for instance.

On that note, if anyone wants to beta test - the source code is up to date in sourceforge if you can build your own executable. Or contact me if you want me to provide you with an executable to test....

[bsquared]

In the usual place.

The major addition with this version is automated multi-threadable poly selection (using msieve) for GNFS jobs. Specifying -t N will now do NFS using N threads for all major phases except filtering and sqrt.

In general, NFS within YAFU underwent a pretty significant overhaul. There are a number of new options which allow jobs to be tailored for those who like to run things more manually or for large/community efforts (where manual interaction is pretty much required).

The last couple bugs discussed here have been fixed as well.

Happy factoring!

[Karl M Johnson]

Good job, Ben.

Some quick comments so far:
1. Now it requires cat. No big deal, grabbed it from coreutils(or was it gnuutils?)
2. -ggnfsT parameter. Does it work ? I tried launching yafu agains a c93 I generated with that parameter in the batch file, in the yafu.ini file, and without it, and the polyselection always lasts the exact same time. Did I miss something ? Ofc, this can be roughly overridden by specifying a range for the polyselection(-np X,Z).
3. If I try to launch yafu with a -np 1,25000 parameter, it crashes with BEX64 error. Uhm ?

[Andi_HB]

Is it possible to print the used Poly with murphy e-score before the sieving is working?

[bsquared]

Originally Posted by Karl M Johnson

Good job, Ben.

Some quick comments so far:
1. Now it requires cat. No big deal, grabbed it from coreutils(or was it gnuutils?)
2. -ggnfsT parameter. Does it work ? I tried launching yafu agains a c93 I generated with that parameter in the batch file, in the yafu.ini file, and without it, and the polyselection always lasts the exact same time. Did I miss something ? Ofc, this can be roughly overridden by specifying a range for the polyselection(-np X,Z).
3. If I try to launch yafu with a -np 1,25000 parameter, it crashes with BEX64 error. Uhm ?

'cat' should still be optional... you may see messages printed to the effect that 'cat' was not found, but if that happens YAFU will use a backup method. cat is faster though, so getting it via gnuutils is generally a good idea.

-ggnfsT does work, but it is only enforced at 'phase boundaries', i.e., after poly selection or a round of sieving finishes. As you observed, if you make a phase shorter (-np [X,Y]), then the -ggnfsT cutoff is checked sooner and the elapsed time will be closer to the specified cutoff. This isn't an ideal implementation, I know, but I don't know of a better way to enforce the time limit other than adding timers and checkpoints everywhere in the code and that gets tiresome and ugly.

-np X,Y does indeed seem to be broken. Which is annoying because I know I tested that. I'll get a patch out soon.


Thanks for the feedback!

[bsquared]

Originally Posted by bsquared

-np X,Y does indeed seem to be broken. Which is annoying because I know I tested that. I'll get a patch out soon.

Ok, I fixed it and updated the sourceforge download.

The problem was that I tried to make gcc happy at the last minute by initializing a pointer variable to NULL without checking to see that the behavior of a function (strtoul) changes if passed a NULL pointer. Sorry for the hiccup.

- ben.

[Karl M Johnson]

Well, actually, with -np working, I dont need any timers

Thanks for the fast bugfix.