QS/NFS crossover points - Page 5

bsquared · 2022-02-13, 19:11

Saw ~10% improvement on the c95. I didn't really watch the first one with default params, but this one had to extend the sieve range 5 or 6 times before filtering/LA.

VBCurtis · 2022-02-13, 19:26

That makes sense, if you're running single-threaded. CADO siever clients continue to run during filtering, so on a normal job that's using an entire machine the server thread is filtering while the other threads keep sieving- filtering usually fails the first time, asking for more relations, but by the time it does the client threads have supplied enough relations for filtering to work the second time. CADO is smart enough to not repeat duplicate removal- running filtering twice leads to a shorter job than running it once, at least on 6+ core machines.

This is a spot where running single-threaded is a handicap against CADO.

Edit: your single-thread experience makes clear that I should add a note to the file to add 10% to target relations if running 4-threaded or fewer.

bsquared · 2022-02-13, 22:28

Quote:

Originally Posted by VBCurtis

That makes sense, if you're running single-threaded. CADO siever clients continue to run during filtering, so on a normal job that's using an entire machine the server thread is filtering while the other threads keep sieving- filtering usually fails the first time, asking for more relations, but by the time it does the client threads have supplied enough relations for filtering to work the second time. CADO is smart enough to not repeat duplicate removal- running filtering twice leads to a shorter job than running it once, at least on 6+ core machines.

This is a spot where running single-threaded is a handicap against CADO.

Yeah that makes sense too. Maybe I can also run a few points with multiple threads.

The C100 was about 30% faster with the new params, very nice! That brings the crossover somewhere between 95 and 100 digits, maybe 97.

bsquared · 2022-02-15, 04:11

Quote:

Originally Posted by bsquared

QS packages tested:
* yafu (2.08)

NFS packages tested:
* yafu-nfs-2.08 (msieve/ggnfs64)
* cado-nfs-3.0.0

Run on: Intel(R) Core(TM) i7-7800X CPU @ 3.50GHz (wsl2); all tests single threaded. Yafu-qs and cado are both using AVX-512.

Here is the total time data:

Code:

input digits	yafu-2.08 qs (t4)      yafu-2.08-nfs	cado-nfs-3.0.0 (t4)     cado-3.0-mf-params (t4)
60	           1.1 (0.35)		                      54.3 (37.1)
65	           3.3 (0.97)		                      74.9 (42.3)
70	           6.7 (2.3)		                      106 (56.4)
75	           22.5 (6.6)		                      208 (96)
80	           45.5 (14.1)	                              351 (124)
85	           132 (39.6)	                 	      652 (224)
90	           514 (143)	                 	      1377 (442)          892 (309)
95	           1550 (408)	                              2365                2126 (658)
100	           3413 (909)                                 3950	          2697 (958)
105	           11984	                              7405
110

Still gathering data. It looks like the crossover between yafu and cado is slightly over 100 digits with default params, and maybe around 97 digits with VBCurtis's improved params.

Added some 4-thread data (on a 6-core, 12-thread machine). With 4 threads the crossover is slightly over 100 digits again.

factorn · 2022-02-17, 14:46

Quote:

Originally Posted by bsquared

Added some 4-thread data (on a 6-core, 12-thread machine). With 4 threads the crossover is slightly over 100 digits again.

Thanks for the report! I am eager to see what all the final numbers will be.

Question: Could you tell me how to build GGNFS from source? I have tried a lot and cannot get it to compile for my CPU. I tried Ed's "How do I..." set of guides and the build would crash on factoring some numbers but not on other, the SVN repo is from 2006 and hasn't been update since then. I tried several patches for the repo to try to get it to install and they get pass some issues but not others, mostly I get assembly errors and a modulo32 function duplication error from the compiler.

Any instructions on how to compile GGNFS and its sievers from source using GCC-11 for Linux would be greatly appreciated. I notice you wrote GGNFS64, do you have a 64-bit assembly version that runs on modern machines? As oppose to what was available back in 2006?

EdH · 2022-02-17, 14:53

Quote:

Originally Posted by factorn

. . . I tried Ed's "How do I..." set of guides and the build would crash on factoring some numbers but not on other, . . .

Could you post a couple numbers that fail in the referenced thread?

charybdis · 2022-02-17, 14:57

I don't think there's much to be gained from compiling your own copies of the GGNFS sievers rather than using precompiled binaries. Did bsquared's binaries from EdH's guide not work on your system?

The GGNFS sievers are no longer in development. You couldn't find a version for modern machines because there isn't one; the asm code hasn't been updated since the core-2 era. But it still runs on modern machines.

bsquared · 2022-02-17, 15:24

I just now re-uploaded linux ggnfs executables here. It's a zip file dated 2011, which is probably when I last built the things and I've been using ever since.

I have numbers now for yafu-nfs but they are on my home pc; I'll try to remember to add them later today. The upshot is that yafu-nfs is competitive but slightly slower than cado-3.0 with default params. With VBCurtis's new params cado-3.0 beats it handily.

[edit]
Also, yafu-qs with three large primes is about 10% faster on the c105, but that's not enough to change anything. cado or yafu's nfs is better still.

bsquared · 2022-02-17, 16:25

Quote:

Originally Posted by factorn

Question: Could you tell me how to build GGNFS from source?

You only need the sievers. No one has used any of the rest of it in a decade or more, to my knowledge.

To build those I think this works:

Quote:

Originally Posted by lasieve4_64 INSTALL file

follow these steps to build the binaries on a 64-bit machine.
These should build and run on Athlon64, or Core2 cpus.

******************************
NOTE for Phenom/K8 users: replace in athlon64/ls-defs.asm
define(l1_bits,15)dnl
=>
define(l1_bits,16)dnl

and in athlon64/siever-config.h
#define L1_BITS 15
=>
#define L1_BITS 16

This may add 5-10% speed to your sieving speed.
But try it both ways and decide for yourself. Caveat emptor!
******************************

Prerequisites: gmp.h libgmp

cd src/experimental/lasieve4_64/athlon64
make liblasieve.a
make liblasieveI11.a
make liblasieveI12.a
make liblasieveI13.a
make liblasieveI14.a
make liblasieveI15.a
make liblasieveI16.a
cp *.a ..
cd ..
ln -s athlon64 asm
make

factorn · 2022-02-19, 05:22

Quote:

Originally Posted by bsquared

You only need the sievers. No one has used any of the rest of it in a decade or more, to my knowledge.

To build those I think this works:

I tried doing that, I ran all those commands exactly in that order from that directory but I get:

Quote:

make: *** No rule to make target 'liblasieve.a', needed by 'gnfs-lasieve4I11e'. Stop.

The Makefile I have in ggnfs/src/experimental/lasieve4_64 is below. Indeed, there is no target to build liblasieve.a

Code:

# Copyright (C) 2001,2002 Jens Franke
# This file is part of gnfs4linux, distributed under the terms of the
# GNU General Public Licence and WITHOUT ANY WARRANTY.

# You should have received a copy of the GNU General Public License along
# with this program; see the file COPYING.  If not, write to the Free
# Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
# 02111-1307, USA.
#
# 6/13/04: Hacked up for use in GGNFS by Chris Monico.

INC=-I. -I./asm
LIBFLAGS=-L.
#CFLAGS=-Os -march=amdfam10 -mtune=amdfam10 -funroll-loops
CFLAGS=-O3 -march=k8 -mtune=k8 -funroll-loops

.SUFFIXES:

.SECONDARY: *.c *.o

.PHONY: all clean

SRCFILES=fbgen.c gnfs-lasieve4e.c input-poly.c mpz-ull.c mpqs.c \
         real-poly-aux.c redu2.c gmp-aux.c if.c lasieve-prepn.c \
     primgen32.c recurrence6.c asm/siever-config.c asm/siever-config.h

OBJS=if.o input-poly.o redu2.o recurrence6.o fbgen.o \
     real-poly-aux.o primgen32.o lasieve-prepn.o mpqs.o

LIBS=-lgmp-aux -lgmp -lm


all : gnfs-lasieve4I11e gnfs-lasieve4I12e gnfs-lasieve4I13e \
      gnfs-lasieve4I14e gnfs-lasieve4I15e gnfs-lasieve4I16e


%.o: %.c asm/siever-config.h
    $(CC) $(CFLAGS) $(INC) -c -o $@ $<

%.o: %.s
    $(CC) $(INC) -c $^

libgmp-aux.a: gmp-aux.o mpz-ull.o
    $(AR) rcs $@ $^

gnfs-lasieve4eI%.o: gnfs-lasieve4e.c
    $(CC) $(CFLAGS) $(INC) -c -DI_bits=$* -o $@ $<

gnfs-lasieve4I11e: gnfs-lasieve4eI11.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI11.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static
gnfs-lasieve4I12e: gnfs-lasieve4eI12.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI12.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static
gnfs-lasieve4I13e: gnfs-lasieve4eI13.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI13.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static
gnfs-lasieve4I14e: gnfs-lasieve4eI14.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI14.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static
gnfs-lasieve4I15e: gnfs-lasieve4eI15.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI15.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static
gnfs-lasieve4I16e: gnfs-lasieve4eI16.o $(OBJS) libgmp-aux.a \
                             liblasieve.a liblasieveI16.a
    $(CC) $(CFLAGS) $(INC) $(LIBFLAGS) -o $@ $^ $(LIBS) -static


clean:
ifeq ($(OS),Windows_NT)
    -rm -f *.o *.a $(BINDIR)/gnfs-lasieve4I1?e.exe
else
    -rm -f *.o *.a $(BINDIR)/gnfs-lasieve4I1?e
endif
     (test -d asm && $(MAKE) -C asm clean) || exit 0

EDIT: Now that I look closer there are a tonne or assembly error messages:

Quote:

mpqs_td.s: Assembler messages:
mpqs_td.s:249: Error: incorrect register `%r9' used with `w' suffix
mpqs_td.s:280: Error: incorrect register `%r9' used with `w' suffix
mpqs_td.s:283: Error: incorrect register `%rsi' used with `w' suffix
mpqs_td.s:313: Error: incorrect register `%r9' used with `w' suffix
make: *** [Makefile:56: mpqs_td.o] Error 1

Quote:

tdslinieI11.s: Assembler messages:
tdslinieI11.s:2297: Error: incorrect register `%r10' used with `w' suffix

Quote:

tdslinieI12.s: Assembler messages:
tdslinieI12.s:1161: Error: incorrect register `%r10' used with `w' suffix

And similar for files *13-16.s

VBCurtis · 2022-02-19, 08:56

There's a reason nobody tries to guild GGNFS anymore. It's unsupported, and a pain to compile, and really really out of date. Even when it was the best we had, it was a pain to compile (I never succeeded, but I'm no programmer so debugging compiler errors is not my skillset).

If the binaries floating around don't suit you, get used to CADO.

2022-02-13, 19:26	#46
VBCurtis "Curtis" Feb 2005 Riverside, CA 14D4₁₆ Posts	That makes sense, if you're running single-threaded. CADO siever clients continue to run during filtering, so on a normal job that's using an entire machine the server thread is filtering while the other threads keep sieving- filtering usually fails the first time, asking for more relations, but by the time it does the client threads have supplied enough relations for filtering to work the second time. CADO is smart enough to not repeat duplicate removal- running filtering twice leads to a shorter job than running it once, at least on 6+ core machines. This is a spot where running single-threaded is a handicap against CADO. Edit: your single-thread experience makes clear that I should add a note to the file to add 10% to target relations if running 4-threaded or fewer. Last fiddled with by VBCurtis on 2022-02-14 at 05:30

2022-02-17, 15:24	#52
bsquared "Ben" Feb 2007 7·11·47 Posts	I just now re-uploaded linux ggnfs executables here. It's a zip file dated 2011, which is probably when I last built the things and I've been using ever since. I have numbers now for yafu-nfs but they are on my home pc; I'll try to remember to add them later today. The upshot is that yafu-nfs is competitive but slightly slower than cado-3.0 with default params. With VBCurtis's new params cado-3.0 beats it handily. [edit] Also, yafu-qs with three large primes is about 10% faster on the c105, but that's not enough to change anything. cado or yafu's nfs is better still. Last fiddled with by bsquared on 2022-02-17 at 15:26

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
29 to 30 bit large prime SNFS crossover	VBCurtis	Factoring	11	2015-03-09 07:01
32/33 and 15e/16e crossover point	fivemack	Factoring	7	2009-04-21 07:59
More points for PRP?	Mystwalker	Prime Sierpinski Project	6	2006-01-03 23:32
any body play with the soft fft crossover yes?	crash893	Software	9	2002-09-18 20:45
Can I move an exponent near a FFT crossover to my P III?	svempasnake	Software	2	2002-09-09 21:32

2022-02-13, 19:11	#45
bsquared "Ben" Feb 2007 7·11·47 Posts	Saw ~10% improvement on the c95. I didn't really watch the first one with default params, but this one had to extend the sieve range 5 or 6 times before filtering/LA.

2022-02-17, 14:57	#51
charybdis Apr 2020 7×107 Posts	I don't think there's much to be gained from compiling your own copies of the GGNFS sievers rather than using precompiled binaries. Did bsquared's binaries from EdH's guide not work on your system? The GGNFS sievers are no longer in development. You couldn't find a version for modern machines because there isn't one; the asm code hasn't been updated since the core-2 era. But it still runs on modern machines.

2022-02-19, 08:56	#55
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²·31·43 Posts	There's a reason nobody tries to guild GGNFS anymore. It's unsupported, and a pain to compile, and really really out of date. Even when it was the best we had, it was a pain to compile (I never succeeded, but I'm no programmer so debugging compiler errors is not my skillset). If the binaries floating around don't suit you, get used to CADO.