Msieve and OpenMP

[frmky]

Originally Posted by charybdis

Getting errors during compilation with gcc 9.4.0:[/code]

I've not seen that before. But there's no reason payload needs to be a bitfield since it now uses 32 bits of a 64-bit integer. Just make it uint32. And might as well get rid of the bitfield entirely.

diff --git a/common/filter/filter_priv.h b/common/filter/filter_priv.h
index 2e2722a..8358bd7 100644
--- a/common/filter/filter_priv.h
+++ b/common/filter/filter_priv.h
@@ -39,12 +39,12 @@ typedef struct {
    linked list of relations that use that ideal */

 typedef struct {
-       uint64 payload : 32;    /* offset in list of ideal_relation_t
+       uint32 payload; /* offset in list of ideal_relation_t
                                   structures where the linked list of
                                   ideal_relation_t's for this ideal starts */
-       uint64 clique : 1;      /* nonzero if this ideal can participate in
+       uint8 clique;      /* nonzero if this ideal can participate in
                                   a clique */
-       uint64 connected : 1;   /* nonzero if this ideal has already been
+       uint8 connected;   /* nonzero if this ideal has already been
                                   added to a clique under construction */
 } ideal_map_t;

*Code has not been tested.

[charybdis]

Originally Posted by frmky

I've not seen that before. But there's no reason payload needs to be a bitfield since it now uses 32 bits of a 64-bit integer. Just make it uint32. And might as well get rid of the bitfield entirely.

...

*Code has not been tested.

Thank you! Filtering runs smoothly on the data from the benchmark thread. It's nice to see the relations being read so much faster at the start

[jasonp]

I think this was a side effect of the changes to fix the large dataset bug; the original structure had a 30-bit entry for the first bitfield and large clique removal problems were overflowing 30 bits.

[frmky]

Exactly. I changed it to use 32 bits for payload but just left it as a bitfield at the time.

BTW I just ran into a problem with duplicate removal on a large data set (> 3.5 billion relations). I'll attempt to track it down later today...

Msieve v. 1.54 (SVN Unversioned directory)
Wed Jan  4 21:07:40 2023
random seeds: 8843eb30 0eaf6dcd
MPI process 0 of 1
Using 32 OpenMP threads
factoring 4253349343727251941236877330119054101365914162453902893114846114910830524926133972442672109384930997010015571127515364573577614552367729063797097718571593825921640272454441835184315923713781601800465188651975108402186204817922305008709852043792965744682561465375915998120986746272975079603698798568632913 (304 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (304-digit input)
R0: -12259964326927110866866776217202473468949912977468817408
R1: 1
A0: 2
A1: 0
A2: 0
A3: -2
A4: 0
A5: 0
A6: 1
skew 1.54, size 3.668e-16, alpha 2.178, combined = 2.345e-16 rroots = 0

commencing relation filtering
setting target matrix density to 130.0
estimated available RAM is 257753.8 MB
commencing duplicate removal, pass 1
skipped 4902752 relations with b > 2^32
skipped 4 relations with composite factors
skipped 22985 malformed relations
found 1242193459 hash collisions in 3517393380 relations
added 1218925 free relations
commencing duplicate removal, pass 2
[kepler-0-1:11718] *** Process received signal ***
[kepler-0-1:11718] Signal: Segmentation fault (11)
[kepler-0-1:11718] Signal code: Address not mapped (1)
[kepler-0-1:11718] Failing at address: 0x7f706418be3c
[kepler-0-1:11718] [ 0] /lib64/libpthread.so.0(+0xf5e0)[0x7f7b769c75e0]
[kepler-0-1:11718] [ 1] ./msieve[0x44dac7]
[kepler-0-1:11718] [ 2] ./msieve[0x462da4]
[kepler-0-1:11718] [ 3] ./msieve[0x428675]
[kepler-0-1:11718] [ 4] ./msieve[0x4162ad]
[kepler-0-1:11718] [ 5] ./msieve[0x4061d0]
[kepler-0-1:11718] [ 6] ./msieve[0x404b7d]
[kepler-0-1:11718] [ 7] ./msieve[0x404730]
[kepler-0-1:11718] [ 8] /lib64/libc.so.6(__libc_start_main+0xf5)[0x7f7b760f3c05]
[kepler-0-1:11718] [ 9] ./msieve[0x4047ca]
[kepler-0-1:11718] *** End of error message ***

[frmky]

Originally Posted by frmky

found 1242193459 hash collisions in 3517393380 relations

I haven't had a chance to dig into the code yet, but my first suspicion is that the problem is related to 1242193459*sizeof(uint32) > 2^32.

[jasonp]

There are going to be more and more of these failures as problems approach 4 billion relations. Maybe there would be a bigger payoff investing in making msieve postprocessing interoperable with CADO postprocessing :)

In this case the hashtable code that is used should have a linked list of hashtable offsets and not byte offsets for resolving collisions, but nobody should rely on my memory from 2007.

[frmky]

Yes, it looks like hashtable.c needs a bit of a rewrite. But fundamentally this crash is just a symptom. The real (and easier to patch) problem is that the pass 1 hashtable is too small, which leads to far too many collisions. I'm testing changes now.

As Jason's comment in the source suggests, a better fix would be to replace it with a Bloom filter. And I would argue for sizing the filter a bit larger, discarding the second pass, and just throwing away relations that collide. It wouldn't be difficult to adjust the filter to get negligible collisions.

CADO polyselect and filtering + msieve GPU BL and sqrt would definitely be the best of both worlds. The very different architecture for keeping track of relations suggests this might be difficult to implement, but I do think it would be worth the effort.

[jasonp]

A different idea was explored in another corner of the svn repo, using Berekeley DB. This is straightforward for the duplicate removal, using BDB to implement an out-of-core sort on relation coordinates. Similar techniques apply to the first pass of the singleton removal but gaining a speedup over using a hashtable is much harder.

[frmky]

Originally Posted by frmky

Yes, it looks like hashtable.c needs a bit of a rewrite. But fundamentally this crash is just a symptom. The real (and easier to patch) problem is that the pass 1 hashtable is too small, which leads to far too many collisions. I'm testing changes now.

Increasing the pass 1 hashtable in duplicate removal circumvented the crash in pass 2, but it just reappeared in singleton removal initial pass. So, in the short term, hashtable.c does need to be fixed. For now, though, I've just done duplicate removal and a couple rounds of singleton removal to reduce the dataset before starting msieve.

I'll look into the msieve-db code soon, but I'm afraid I also have little time these days for tool development.

[frmky]

Originally Posted by frmky

BTW I just ran into a problem with duplicate removal on a large data set (> 3.5 billion relations). I'll attempt to track it down later today...

I finally had time to look at this yesterday. Simple overflow in the hashtable match array reallocation size. Easy fix, and it only affects runs with more than 3,276,800,000 relations.
https://github.com/gchilders/msieve_...833d28370a2948

[jasonp]

Originally Posted by frmky

I finally had time to look at this yesterday. Simple overflow in the hashtable match array reallocation size. Easy fix, and it only affects runs with more than 3,276,800,000 relations.
https://github.com/gchilders/msieve_...833d28370a2948

Thanks! Does this mean the duplicate removal is limited to 3.2 billion unique relations?