Stats about missed crossings

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 06/24/2021 at 23:590 Comments

I investigate more the phenomenon of the "missed crossings" in my dual-thread algo because I can't just try "solutions" if I don't identify the cause correctly.

So I run a script to gather some statistics, mainly about how many crossings are missed:

{ N=0
  for i in $(seq 1 1000) ; do
    ./orbit16  | grep EUREKA && N=$((N+1))
  echo RESULT=$N
} | tee 1000.txt

Of the 1000 runs, 378 (more than 1/3) have missed. It seems random, with no discernible clustering.

Even more interesting is the ratio : 489 crossings are detected by backwards (close to 50%, fine) while only 133 are detected by the forward code. Is there a flaw with the forward code ? Or is this a mechanical consequence of higher speed ? Is it a hint for the actual cause ?

Inspection of the code does not reveal any difference between the two directions and the mystery gets even weirder. Anyway, a further script run shows that ALL the misses are due to the forward code, in a consistent ratio. Which is only a confirmation that the forward code always executes faster and finishes first in case of a miss.

Similarly, the higher number of crosses detected by the backwards code indicates/confirms that it is slower: mechanically the forward code crosses more 0s than the backwards code in a given period, hence more forward finds are stacked in the FIFO in average.

Just to be sure, I reorganised the data to prevent the FIFO pointers from residing on the same cache line :

struct cross FIFO_array[FIFOLENGTH];
volatile int FIFO_tail, FIFO_head;
struct cross FOFI_array[FIFOLENGTH];
pthread_t thread_f, thread_b;
volatile int FOFI_tail, FOFI_head;

 But I still get a 37% miss.