Esiste una "soglia" che giustifichi il calcolo multithreading?

Question

Quindi, in pratica, avevo bisogno di ottimizzare questo pezzo di codice oggi. Si cerca di trovare la sequenza più lunga prodotta da qualche funzione per i primi numeri milioni partenza:

public static void main(String[] args) { 
    int mostLen = 0; 
    int mostInt = 0; 
    long currTime = System.currentTimeMillis(); 
    for(int j=2; j<=1000000; j++) { 
     long i = j; 
     int len = 0; 
     while((i=next(i)) != 1) { 
      len++; 
     } 
     if(len > mostLen) { 
      mostLen = len; 
      mostInt = j; 
     } 
    } 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 


static long next(long i) { 
    if(i%2==0) { 
     return i/2; 
    } else { 
     return i*3+1; 
    } 
} 

Il mio errore è stato quello di cercare di introdurre il multithreading:

void doSearch() throws ExecutionException, InterruptedException { 
    final int numProc = Runtime.getRuntime().availableProcessors(); 
    System.out.println("numProc = " + numProc); 
    ExecutorService executor = Executors.newFixedThreadPool(numProc); 
    long currTime = System.currentTimeMillis(); 
    List<Future<ValueBean>> list = new ArrayList<Future<ValueBean>>(); 
    for (int j = 2; j <= 1000000; j++) { 
     MyCallable<ValueBean> worker = new MyCallable<ValueBean>(); 
     worker.setBean(new ValueBean(j, 0)); 
     Future<ValueBean> f = executor.submit(worker); 
     list.add(f); 
    } 
    System.out.println(System.currentTimeMillis() - currTime); 

    int mostLen = 0; 
    int mostInt = 0; 
    for (Future<ValueBean> f : list) { 
     final int len = f.get().getLen(); 
     if (len > mostLen) { 
      mostLen = len; 
      mostInt = f.get().getNum(); 
     } 
    } 
    executor.shutdown(); 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 

public class MyCallable<T> implements Callable<ValueBean> { 
    public ValueBean bean; 

    public void setBean(ValueBean bean) { 
     this.bean = bean; 
    } 

    public ValueBean call() throws Exception { 
     long i = bean.getNum(); 
     int len = 0; 
     while ((i = next(i)) != 1) { 
      len++; 
     } 
     return new ValueBean(bean.getNum(), len); 
    } 
} 

public class ValueBean { 
    int num; 
    int len; 

    public ValueBean(int num, int len) { 
     this.num = num; 
     this.len = len; 
    } 

    public int getNum() { 
     return num; 
    } 

    public int getLen() { 
     return len; 
    } 
} 

long next(long i) { 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

Purtroppo, la versione multithreaded lavorato 5 volte più lento rispetto al single-threaded su 4 processori (core).

poi ho provato un po 'di più l'approccio grezzo:

static int mostLen = 0; 
static int mostInt = 0; 

synchronized static void updateIfMore(int len, int intgr) { 
    if (len > mostLen) { 
     mostLen = len; 
     mostInt = intgr; 
    } 
} 

public static void main(String[] args) throws InterruptedException { 
    long currTime = System.currentTimeMillis(); 
    final int numProc = Runtime.getRuntime().availableProcessors(); 
    System.out.println("numProc = " + numProc); 
    ExecutorService executor = Executors.newFixedThreadPool(numProc); 
    for (int i = 2; i <= 1000000; i++) { 
     final int j = i; 
     executor.execute(new Runnable() { 
      public void run() { 
       long l = j; 
       int len = 0; 
       while ((l = next(l)) != 1) { 
        len++; 
       } 
       updateIfMore(len, j); 
      } 
     }); 
    } 
    executor.shutdown(); 
    executor.awaitTermination(30, TimeUnit.SECONDS); 
    System.out.println(System.currentTimeMillis() - currTime); 
    System.out.println("Most len is " + mostLen + " for " + mostInt); 
} 


static long next(long i) { 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

e ha funzionato molto più veloce, ma comunque era più lento del metodo singolo thread.

Spero che non sia perché ho sbagliato il modo in cui sto facendo il multithreading, ma piuttosto questo particolare calcolo/algoritmo non è adatto per il calcolo parallelo. Se cambio calcolo per renderlo più intenso processore con il metodo next sostituendoli con:

long next(long i) { 
    Random r = new Random(); 
    for(int j=0; j<10; j++) { 
     r.nextLong(); 
    } 
    if (i % 2 == 0) { 
     return i/2; 
    } else { 
     return i * 3 + 1; 
    } 
} 

entrambe le versioni multithread cominciano ad eseguire più di due volte più veloce rispetto alla versione singlethreaded su una macchina 4 nucleo.

Così chiaramente ci deve essere una certa soglia, che è possibile utilizzare per determinare se vale la pena di introdurre il multithreading e la mia domanda è:

Qual è la regola di base che avrebbe aiutato a decidere se un determinato calcolo è abbastanza intensiva per essere ottimizzato eseguendolo in parallelo (senza spendere sforzi per implementarlo effettivamente?)

Answer 1

Penso che ci sia un altro componente in questo che non stai considerando. La parallelizzazione funziona meglio quando le unità di lavoro non dipendono l'una dall'altra. Eseguire un calcolo in parallelo è sub-ottimale quando i risultati del calcolo successivi dipendono da risultati di calcolo precedenti. La dipendenza potrebbe essere forte nel senso di "Ho bisogno del primo valore per calcolare il secondo valore". In tal caso, l'attività è completamente seriale e i valori successivi non possono essere calcolati senza attendere calcoli precedenti. Potrebbe anche esserci una dipendenza più debole nel senso di "Se avessi il primo valore potrei calcolare il secondo valore più velocemente". In tal caso, il costo della parallelizzazione è che alcuni lavori possono essere duplicati.

Questo problema si presta all'ottimizzazione senza multithreading perché alcuni dei valori successivi possono essere calcolati più velocemente se si hanno già i risultati precedenti. Prendi, ad esempio j == 4. Una volta attraverso il ciclo interno produce i == 2, ma hai appena calcolato il risultato per j == 2 due iterazioni fa, se hai salvato il valore di len puoi calcolarlo come len (4) = 1 + len (2).

Utilizzando una matrice per memorizzare i valori precedentemente calcolati di len e un po 'di rotazione nel metodo next, è possibile completare l'attività> 50 volte più velocemente.

Answer 2

"Il guadagno di prestazioni sarà maggiore del costo del cambio di contesto e della creazione di thread?"

Questo è un sistema operativo, linguaggio e hardware, costo dipendente; this question ha qualche discussione sul costo in Java, ma ha alcuni numeri e alcuni indicatori su come calcolare il costo.

Si desidera anche avere un thread per CPU, o meno, per il lavoro intensivo della CPU. Grazie a David Harkness per il puntatore to a thread on how to work out that number.

Answer 3

La chiave per implementare in modo efficiente il multithreading è assicurarsi che il costo non sia troppo alto. Non ci sono regole fisse in quanto dipendono fortemente dal tuo hardware.

L'avvio e l'arresto di thread hanno un costo elevato. Ovviamente hai già utilizzato il servizio executor che riduce considerevolmente questi costi perché utilizza una serie di thread di lavoro per eseguire i tuoi Runnables. Comunque ogni Runnable arriva ancora con qualche overhead. Ridurre il numero di runnables e aumentare la quantità di lavoro che ognuno deve fare migliorerà le prestazioni, ma si desidera comunque avere abbastanza runnables per il servizio executor per distribuirli in modo efficiente sui thread worker.

Hai scelto di creare una eseguibile per ogni valore iniziale in modo da terminare la creazione di 1000000 eseguibili. Probabilmente otterrai risultati molto migliori lasciando che ogni Runnable esegua un batch di almeno 1000 valori iniziali. Il che significa che hai bisogno solo di 1000 runnables che riducono notevolmente il sovraccarico.

Answer 4

Stima della quantità di lavoro che un thread può eseguire senza interazione con altri thread (direttamente o tramite dati comuni). Se quella parte di lavoro può essere completata in 1 microsecondo o meno, l'overhead è eccessivo e il multithreading non è di alcuna utilità. Se è 1 millisecondo o più, il multithreading dovrebbe funzionare bene. Se è nel mezzo, sono necessari test sperimentali.