Possibili metodi per accedere alla cache L1 e specificare thread / core

Question

Possibili metodi per accedere alla cache L1 e specificare thread / core

#1 da (2 voti)
#2 da (1 voti)

-2

Un generatore di numeri primi più rapido con hyperthreading e cache L1

Circa cinque anni fa ho scritto un semplice widget VB per generare il primo milione di numeri primi e quindi portarli nel suo singolo listBox VB. Ci sono volute circa quattro ore su un Athlon 1.4 GHz con 1GB di DDR per PC-3200. Mi chiedevo alcuni suggerimenti e trucchi per accelerare notevolmente questo processo con l'ottimizzazione dell'hardware a basso livello e la gestione della memoria in C.

Più tardi mi è venuto in mente che tutti i numeri primi oltre i dieci terminano in 1, 3, 7 o 9 quindi perché non impostare un algoritmo da eseguire in ciascun core di un processore quad-core e, se possibile, specificarlo l'algoritmo viene eseguito all'interno della cache L1.

Che cosa succede se saliamo a 100.000.000, quindi ogni ramo di questa app valuterà 10.000.000 di candidati primi e restituirà circa 1.000.000 di risultati

 ser[1]=new Array(1000000);
 ser[3]=new Array(1000000);
 ser[7]=new Array(1000000);   
 ser[9]=new Array(1000000);

 void run_array_loader(seed)
 {
     for(n=seed+10;n<100000000;n+=10)
     {
         for(x=3;x<sqrt(n);x+=2)
         {
             n%x==0?break;:continue;
         }
         ser[seed][]=n;
     }
 }
 run_array_loader(1); //in core[0]       
 run_array_loader(3); //in core[1]       
 run_array_loader(7); //in core[2]     
 run_array_loader(9); //in core[3]

Quali metodi utilizzeremmo per accelerare e per specificare l'allocazione di base e l'utilizzo della cache?

20 ottobre: ecco una ripartizione dei risultati in C ++

Riepilogo
33:46 per eseguire 31.209 miliardi di calcoli, identificando 5.762.681 numeri primi

c multithreading caching multi-core visual-basic

posta Brett Bergan 19.10.2016 - 11:04

fonte

2 risposte

Leggi altre domande sui tag c multithreading caching multi-core visual-basic

Perché la sintassi per la creazione di un nuovo oggetto è un po 'lunga in java? [duplicare] In che modo tipizzare un array è diverso dal typecasting di un singolo elemento?

score 2 · Answer 1

Quando si ha a che fare con numeri così grandi, scegliere un algoritmo più veloce ti fornirà risultati più veloci indipendentemente da qualsiasi ottimizzazione di basso livello.

Il tuo ciclo incorre in 100.000.000 / 10 * sqrt (100.000.000) / 2 = 50.000.000.000 operazioni / thread.

Al contrario, utilizzando setaccio di Eratostene ti occorrerebbero solo 100.000.000 * log (log (100.000.000)) ~~ 400.000.000 di operazioni. Questo è 125 volte più veloce su un thread rispetto all'implementazione su 4 thread.

Come hai anche menzionato una casella di elenco VB, tieni presente che l'aggiunta di un numero elevato di valori può essere piuttosto lenta.

Modifica successiva : un aggiornamento dopo aver pubblicato un benchmark.

Riassumendo il numero di numeri primi che il tuo codice ha scoperto produce 5.762.693. Questo sito tuttavia elenca 5.761.455 numeri primi sotto 100.000.000. Quindi il tuo codice considera 1.238 numeri primi quando non lo sono.

Ecco un codice di esempio che utilizza un algoritmo diverso:

#include <bitset>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <memory>
#include <vector>

template <int UpTo, typename OutputIt>
void populate_prime_numbers(OutputIt output)
{
    //stores 0 if the number is still considered a prime or 1 if certainly not
    auto valuesPtr = std::make_unique<std::bitset<UpTo>>();
    auto& values = *valuesPtr;
    for (int64_t divider = 3; ; divider += 2)
    {
        auto dividerSquare = divider * divider;
        if (dividerSquare >= UpTo) break;

        if (values[divider])
        {
            continue;
        }
        auto multiple = dividerSquare;
        while (multiple < UpTo)
        {
            values[multiple] = 1;
            multiple += divider;
        }
    }

    *output = 2;
    ++*output;

    for (int i = 3; i < UpTo; i += 2)
    {
        if (0 == values[i])
        {
            *output = i;
            ++*output;
        }
    }
}

int main()
{
    std::vector<int> results;

    populate_prime_numbers<100000000>(back_inserter(results));

    std::cout << results.size() << " prime numbers < 100,000,000";
}

Emette 5761455 prime numbers < 100,000,000 in solo 1 secondo sotto x64. Codice a thread singolo, nessuna ottimizzazione a basso livello.

score 1 · Answer 2

Il caching diventa importante solo dopo aver implementato correttamente un setaccio. "Decente" significa che utilizza una memoria minima, nessun lavoro non necessario e un'implementazione efficiente. (Mi aspetterei che per esempio non memorizzare affatto numeri pari e non rimuovere i multipli di 3, 5, 7, 11 dal setaccio ma non averli nel setaccio in primo luogo quando il setaccio è inizializzato) .

Per ottimizzare l'uso della cache L1, non si limita a filtrare un array di grandi dimensioni, ma si esegue l'intera operazione di setacciamento su piccoli blocchi di dati che si adattano alla cache L1, ovvero rimuovere i multipli di 13, 17, 19 ecc. in un blocco di dati con cache L1, quindi rimuoverli nel blocco successivo e così via. Non sono necessari trucchi hardware.