Alcuni risultati con LazySMP


Questa pagina ha una gerarchia - Pagina madre:Programmazione

Home Forum Programmazione Alcuni risultati con LazySMP

Questo argomento contiene 33 risposte, ha 8 partecipanti, ed è stato aggiornato da  sasachess 1 anno, 2 mesi fa.

Stai vedendo 15 articoli - dal 1 a 15 (di 34 totali)
  • Autore
    Articoli
  • #9638
    Andrea
    Andrea
    Membro

    Ho rimosso tutto il codice riguardante lo YBWC da Chiron e implementato il LazySMP per provarlo. Come sapete, il LazySMP non prevede lo splitting dell’albero di ricerca tra i vari thread ma semplicemente si tratta di lanciare N thread di ricerca alla radice nel loop dell’iterative deepening con la stessa finestra alpha-beta ma con depth diverse. Lo schema di Daniel Homan prevede di assegnare ai thread pari la profondità dell’attuale iterazione mentre a quelli dispari depth+1. I thread comunicano esclusivamente tramite le varie hash table mentre history heuristic, killer move, ecc sono per thread.

    L’hardware usato è stato un dual Opteron 6176, 24 core in totale e 4 nodi NUMA perchè ogni cpu è composta da due die. Attualmente non ho implementato nessuna ottimizzazione per il NUMA.

    Gli nps scalano quasi linearmente fino a 16 thread poi salgono molto poco. Ottimizzando per il NUMA e riducendo l’utilizzo dell’hash table nella quiescenza quando ci sono molti thread (rendendola per esempio locale) la situazione dovrebbe migliorare.

    Ho fatto dei test da 2500 partite a 20″+0.03″ e a 60″+0.1″: 2thread vs 1thread, 4t vs 1t e 8t vs 1t.

    Ho voluto testare prima questi incrementi per la profondità: 0, 1, 1, 2, 2, 3, 3, 4. Adesso sto testando il classico 0, 1, 0, 1, ecc e aggiungerò i risultati in seguito.

    Per calcolare i rating ho utilizzato Ordo.

    60"+0.1"
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron8T      :  149.7    1752.0    2500   70.1%
       2 Chiron1T      :    0.0     748.0    2500   29.9%
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron4T      :  114.0    1641.5    2500   65.7%
       2 Chiron1T      :    0.0     858.5    2500   34.3%
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron2T      :   56.0    1447.5    2500   57.9%
       2 Chiron1T      :    0.0    1052.5    2500   42.1%
    
    
    
    20"+0.03"
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron8T      :  174.4    1554.5    2131   72.9%
       2 Chiron1T      :    0.0     576.5    2131   27.1%
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron4T      :  134.9    1707.0    2500   68.3%
       2 Chiron1T      :    0.0     793.0    2500   31.7%
    
       # PLAYER        : RATING    POINTS  PLAYED    (%)
       1 Chiron2T      :   71.0    1499.5    2500   60.0%
       2 Chiron1T      :    0.0    1000.5    2500   40.0%
    

    Come si vede, il LazySMP da dei risultati molto interessanti, soprattutto considerando il poco tempo necessario ad implementarlo rispetto allo YBW. Al raddoppiare del tc, però, ogni versione ha perso circa 20 punti, bisogna quindi vedere come si comporterà nelle varie rating list con tempi maggiori. Dubito, però, che vada sotto agli 84 punti di Chiron 2 4T vs 1T nella CEGT 40/4.

    #9639

    marco belli
    Membro

    l’implementazione del lazy smp di vajolet è molto simile alla tua e a quella di Daniel Homan. thread pari depth n, thread dispari depth n+1.
    la versione 2.1 di vajolet è la prima ad implementare un algoritmo smp e questi sono i risultati molto provvisori che ci sono nella lista ccrl 40/40

    Vajolet2 2.1 64-bit 4CPU 3015
    Vajolet2 2.1 64-bit 2900

    un aumento di 115 punti elo. Visto il rating degli avversari e l poche partite effettuate dai 2 engine credo che alla fine sia più credibile un delta di solo 90 punti.

    #9640
    stegemma
    stegemma
    Moderatore

    Credo che sia normale che SMP scali bene solo fino a circa 16 core: siccome viene attivato alla root, le mosse che ha senso esaminare sono circa la metà di quelle disponibili (forse anche meno); gli altri core sono di fatto “sprecati”. Questo lo scrivo solo ad intuito, non avendo ancora approfondito nulla, sull’implementazione SMP o multi-threading in generale. Se è veramente così, dovrebbe scalare ancor peggio per posizioni iniziali in cui le mosse decenti sono poche.

    #9644
    Andrea
    Andrea
    Membro

    No, col LazySMP non c’è nessuno splitting, neanche alla radice, quindi ogni thread analizza tutte le mosse alla root. Si tratta di lanciare N thread che eseguono la SearchRoot() con profondità diverse.

    Per quanto riguarda lo scaling, mi riferivo, in quella parte, agli nps che, in teoria, non essendoci l’overhead dovuto allo splitting, tutti i thread sono sempre occupati, ecc dovrebbero scalare quasi linearmente visto che ogni thread analizza il suo albero indipendentemente dagli altri.

    Per esempio, Cheng di Martin Sedlak si comporta molto bene: nella posizione iniziale dopo un minuto fa 958K nps con un thread, 13.65M con 16 e 20.72M con 24.

    #9645

    sasachess
    Partecipante

    Ciao Andrea,
    grazie per la condivisione. Mi sta venendo voglia di implementare il lazySMP anche in gogobello!
    Leggevo in chat che sarebbe meglio progettare il motore per il multithreading già dall’inizio, a partire dalle strutture dati.
    Dato che ho in mente un rifacimento completo per gogobello, al fine di uniformare la convenzione sui nomi, lo stile di programmazione, eliminare il codice che non serve, etc. potrei anche ripensarlo in quest’ottica. Ma quali strutture dati sono più sensibili a questo tema? E’ sufficiente rimuovere l’utilizzo delle variabili globali, oppure c’è dell’altro a cui prestare attenzione?

    Grazie.
    Salvatore

    #9646
    stegemma
    stegemma
    Moderatore

    La prima cosa da fare è incapsulare tutti i dati in classi, limitando appunto quelli globali; per questi ultimi è meglio definire un oggetto globale che li incapsula, piuttosto che tenerli “sparsi” nel codice (salvo che siano “read-only”). Tutto Satana è incapsulato in una classe derivata da una clsEngine ed anche la TT viene allocata dall’oggetto stesso, che ne tiene un puntatore.

    Questa struttura scala in modo naturale verso un multi-thread perché è nata pensando a quello. Ci sarà da vedere come condividere la TT, il modo più semplice sarebbe la condivisione del puntatore ma, per ragioni di “pulizia” questo andrebbe spostato in un oggetto “a monte”, che uso per gestire i vari clsEngine, passando ad ognuno lo stesso puntatore. Di nuovo, questo implica la possibilità a costo zero, se necessario, di avere TT diverse per gruppi di engine.

    Altro vantaggio di questo approccio: se hai più strutture comuni le puoi incapsulare in un oggetto unico, da cui l’oggetto principale deriva (o lo tiene come membro) e ne passa il puntatore ai vari thread-engine.

    Un approccio ancor più pulito sarebbe quello di nominare l’oggetto principale come “arbitro” anche dell’oggetto globale da condividere, così che i singoli thread chiedano ad esso l’accesso, così che il punto di protezione sia unico. bisogna anche tener conto delle prestazioni… perché più “strati” di classi aggiungi e più potresti perdere (ma è da verificare).

    Se non s’è capito nulla va bene lo stesso, perché ho scritto più per chiarirmi le idee che altro! 😉

    #9647
    Andrea
    Andrea
    Membro

    Ciao Andrea,
    grazie per la condivisione. Mi sta venendo voglia di implementare il lazySMP anche in gogobello!

    Ciao Salvatore. L’ho scritto apposta il messaggio 🙂

    Ma quali strutture dati sono più sensibili a questo tema? E’ sufficiente rimuovere l’utilizzo delle variabili globali, oppure c’è dell’altro a cui prestare attenzione?

    Si, per utilizzare i thread è sostanzialmente sufficiente rimuovere tutte le variabili globali non costanti utilizzate da ricerca e valutazione, eccetto le hash table ovviamente. Io ho tutto in una struct e le varie funzioni si passano il puntatore alla struct associata al proprio thread.

    Utilizzando i processi non ci sarebbe neanche bisogno di rimuovere le variabili globali ma sinceramente preferisco i thread, come ormai tutti.

    In un sistema NUMA poi converrebbe probabilmente rendere l’hash table principale interleaved e tutte le altre locali per thread o nodo, ma è inutile pensare a questo all’inizio.

    #9648

    sasachess
    Partecipante

    In un sistema NUMA poi converrebbe probabilmente rendere l’hash table principale interleaved e tutte le altre locali per thread o nodo, ma è inutile pensare a questo all’inizio.

    Grazie a entrambi per le risposte.

    @Stefano, in gogobello non ho classi. Uso il C, non il C++.

    @andrea, cosa intendi per hash table principale e hash locali? Non ti seguo su questo punto.

    #9649
    Andrea
    Andrea
    Membro

    @Andrea, cosa intendi per hash table principale e hash locali? Non ti seguo su questo punto.

    Quella principale è quella utilizzata dalla ricerca. Le altre possono essere essere quella pedonale, per la valutazione, per il materiale, ecc

    #9650
    stegemma
    stegemma
    Moderatore

    @Stefano, in gogobello non ho classi. Uso il C, non il C++.

    Si può programmare ad oggetti anche in C…

    #9651

    ciao a tutti,
    anche io (dietro un suggerimento di Andrea di qualche mese fa) sto implementando il lazySMP nel mio Cinnamon. Ho praticamente riscritto tutta l’architettura per renderlo multithread e scritto un thread pool generico per la gestione dei thread.

    Ho incapsulato dentro la classe Search tutta la logica per effettuare una ricerca e tutte le strutture e variabili di appoggio, questa classe inoltre estende la classe Thread.

    Una classe SearchManager crea un thread pool dentro il quale pool creo N istanze di Search che gestisco facilmente grazie ai metodi del thread pool stesso.

    L’hash table è banalmente una classe singleton in questo modo ogni classe Search ha nel proprio costruttore il puntatore Hash *hash = &Hash::getInstance().

    I sorgenti del thread pool sono qui https://github.com/gekomad/ThreadPool

    i sorgenti di cinnamon (ancora in alpha) sono qui https://github.com/gekomad/Cinnamon/tree/v1.2c-smp.x-lazysmp

    #9652
    stegemma
    stegemma
    Moderatore

    Sembra tutto molto ben scritto. Ho visto in particolare la tua classe Mutex; io uso i mutex di pthread, dove disponibili, altrimenti sotto Windows uso l’API WaitForSingleObject. Questa è la versione che uso col vecchio C++Builder: (scusa se si è persa un po’ la formattazione)

    
    class clsMutex
    {
    	protected:
    		HANDLE mtx;
    	public:
    		clsMutex();
    		virtual ~clsMutex();
    		bool Lock();
    		bool TryLock();
    		bool UnLock();
    };
    
      clsMutex::clsMutex(): mtx(NULL)
      {
        try
        {
        	mtx = CreateMutex(NULL, FALSE, NULL);
        }catch(...){}
      }
    
      clsMutex::~clsMutex()
      {
        try
        {
        	UnLock();
          if(mtx) CloseHandle(mtx);
        } catch(...){}
      }
    
    	bool clsMutex::Lock()
      {
        if(mtx) try
        {
          DWORD dwWaitResult = WaitForSingleObject(mtx, INFINITE);
          switch (dwWaitResult)
          {
              case WAIT_OBJECT_0:  return true;
              case WAIT_ABANDONED: return false;
          }
        }catch(...){}
      	return false;
      }
    
    	bool clsMutex::TryLock()
      {
        if(mtx) try
        {
          DWORD dwWaitResult = WaitForSingleObject(mtx, 0);
          switch (dwWaitResult)
          {
              case WAIT_OBJECT_0:  return true;
              case WAIT_ABANDONED:
              case WAIT_TIMEOUT:
              case WAIT_FAILED:    return false;
          }
        }catch(...) { }
      	return false;
      }
    
    	bool clsMutex::UnLock()
      {
        if(mtx) try
        {
    ReleaseMutex(mtx);
          return true;
        }catch(...) { }
      	return true;
      }
    
    #9653

    Ho letto da qualche parte che i Mutex sotto windows sono molto pesanti perchè richiamano delle API in kernel mode è quindi preferibile utilizzare le critical_section inoltre nei casi di lock/unlock per tempi bassissimi (ad esempio quando si scrive un valore in un hash table) è preferibile usare gli Spinlock anche in questo caso ho verificato grandi miglioramenti

    #9654
    stegemma
    stegemma
    Moderatore

    Le critical_section richiamano comunque le API… tutto chiama le API, in Windows!

    Sotto Windows i mutex sono sicuramente troppo pesanti, non so come funzionino in Linux/OS X ma suppongo che sia più o meno lo stesso. Lo scopo dei mutex è controllare punti critici del codice, richiamati da funzioni che comunque sono già pesanti per conto loro; per funzioni ultra-brevi come quelle di un engine, ovviamente anche solo poche decine di istruzioni diventano inaccettabili.

    #9794

    Ciao a tutti,

    visto che è un argomento caldo per molti, ho qualche dubbio che magari qualcuno può chiarirmi.
    Prima di tutto vorrei capire cosa fate quando uno dei thread ha finito la sua iterazione a depth X: aspettate gli altri thread? Abortite gli altri thread? La PV viene scelta e stampata solo dal thread master o anche i thread di supporto possono dire la loro?
    Io avevo letto un post dell’autore di Cheng in cui lui sosteneva di lanciare tutti i thread e quando il primo finisce stoppa gli altri e passa all’iterazione successiva, senza differenza sia il thread master o meno, è anche vero, se ricordo bene, che lui lanciava tutti i thread con la medesima depth e non alternando depth e depth+1.

    Grazie a chi vorrà rispondermi
    Marco

Stai vedendo 15 articoli - dal 1 a 15 (di 34 totali)

Devi essere loggato per rispondere a questa discussione.

© 2017 G 6 Tutti i diritti riservati - Buon divertimento!

By continuing to use the site, you agree to the use of cookies. more information

Questo sito utilizza i cookie per fonire la migliore esperienza di navigazione possibile. Continuando a utilizzare questo sito senza modificare le impostazioni dei cookie o clicchi su "Accetta" permetti al loro utilizzo.

Chiudi