# Prime Time Tactics--Sieve Tweaks and Boosters
## 3 Parallel Sieving Strategies
### Generic Considerations
If the primes need to be generated in order, a multi-threaded approach introduces some complications, but the overall performance can still be improved with the use of extra threads. The method described here alternates between sieving and counting. However, these two tasks differ significantly in how they utilize CPU pipelines and their data access patterns. Therefore, overlapping them may lead to better utilization of CPU resources. By concurrently performing sieving and counting, the CPU can be more efficiently exploited, as it can handle the distinct demands of each task in parallel, potentially reducing idle times and improving overall performance. Such a strategy is exemplified in [24], using a so-called tic-toc mechanism which involves two distinct sieving buffers that are processed alternately by the working threads; while one buffer is being sieved, the other buffer is being counted (tic), then the buffers are switched (toc). Here is the gist of the main loop in such an implementation:
```
tpPrimeWindow_start_1=0: tpPrimeWindow_start_2=WINDOW_SIZE; unsignedexpected_state_1=0; unsignedexpected_state_2=0; //boolticot=true; do{ //if(titocot){ticotoc=false; if(window_start_1>=limit)break; //waitforcountingtofinsish sync_1.WaitTurnAndAcquire(expected_state_1); expected_state_1+=2; //sieve
```
Siieve(sieve_1); window_start_1+=2+WINDOW_SIZE; //releaseforcounting sync_1.Release(); ////else{ticotoc=true; if(Window_start_2>=limit)break; sync_2.WaitTurnAndAcquire(expected_state_2); expected_state_2+=2; Siewe(sieve_2); window_start_2+=2+WINDOW_SIZE; sync_2.Release(); //// } while(true);
```The counting loop is practically identical, except its states are initialized with 1. Overlapping the two working patterns and fine-tuning the number of sieving and counting threads may result in a better utilization of CPU pipelines. To conclude the process, the final task is to collect and organize the many lists of primes (one for each segment), which are not necessarily produced in order. This problem is essentially identical to the one encountered within an individual segment if parallel counting is employed. Given that we may need to address the same issue here, it is straightforward to use the same solution in both places. One effective solution is to have an additional parallel thread that waits for segments/chunks to produce their results and then processes them in the correct order as they become available. This approach ensures that the primes are gathered and ordered efficiently, leveraging parallel processing to maintain performance. Finally, for testing or benchmarking, there arises the question of how to handle each generated prime. The task must be lightweight enough to avoid skewing the performance metrics, yet substantial enough to ensure the compiler actually computes the prime and passes it to a designated location. Here is our solution of choice for this problem; it works without congestion in a multi-threaded execution, the index does not require any limit check (255 + 1 = 0), and it allows visibility of the last 256 primes generated and facilitates prime validation when single-threaded:

```
inlineuint8_tidx_last_primes=0; inlinestd::array<uint64_t,256>last_primes; inlinevoidAddPrime(uint64_tprime){
#_fdef_D256_
#staticCheckerckr; assert(ckr.check_next_prime(prime));
#endif//-D256
#last_primes[idx_last_primes++]=prime; } inlinethread_localuint8_tidx_last_primes_t=0; inlinethread_localstd::array<uint64_t,256>last_primes_t; inlinevoidAddPrimeThread(uint64_tprime){ last_primes_t[idx_last_primes++]=prime; }
```

### Massive Parallel Sieving

A highly effective strategy for managing the immense computational demands of sieving is to employ a GPGPU paradigm, leveraging the substantial throughput capabilities of GPU devices. To achieve this, it is essential to utilize a framework or SDK that abstracts the complexities and diversity of specific GPUs, providing a generic API.