Ordine di micro-ottimizzazione SSE

Question

Ho notato che a volte MSVC 2010 non riordina affatto le istruzioni SSE. Ho pensato che non dovevo preoccuparmi dell'ordine delle istruzioni all'interno del mio ciclo, dal momento che il compilatore gestisce meglio, il che non sembra essere il caso.

Come dovrei pensare a questo? Cosa determina il miglior ordine di istruzioni? So che alcune istruzioni hanno una latenza maggiore di altre e che alcune istruzioni possono essere eseguite in parallelo/asincrono a livello di CPU. Quali metriche sono rilevanti nel contesto? Dove posso trovarli?

So che avrei potuto evitare questa domanda per profilatura, tuttavia tali profiler sono costosi (VTune XE) e mi piacerebbe conoscere la teoria dietro di esso, non solo i risultati empirica.

Inoltre, dovrei preoccuparmi del precaricamento del software (_mm_prefetch) o posso presumere che la cpu farà un lavoro migliore di me?

Diciamo che ho la seguente funzione. Devo interlacciare alcune delle istruzioni? Devo fare i negozi prima dei flussi, fare tutti i carichi in ordine e poi fare i calcoli, ecc ...? Devo considerare USWC vs non USWC, e temporale vs non temporale?

  auto cur128  = reinterpret_cast<__m128i*>(cur); 
      auto prev128 = reinterpret_cast<const __m128i*>(prev); 
      auto dest128 = reinterpret_cast<__m128i*>(dest; 
      auto end  = cur128 + count/16; 

      while(cur128 != end)    
      { 
       auto xmm0 = _mm_add_epi8(_mm_load_si128(cur128+0), _mm_load_si128(prev128+0)); 
       auto xmm1 = _mm_add_epi8(_mm_load_si128(cur128+1), _mm_load_si128(prev128+1)); 
       auto xmm2 = _mm_add_epi8(_mm_load_si128(cur128+2), _mm_load_si128(prev128+2)); 
       auto xmm3 = _mm_add_epi8(_mm_load_si128(cur128+3), _mm_load_si128(prev128+3)); 

            // dest128 is USWC memory 
       _mm_stream_si128(dest128+0, xmm0); 
       _mm_stream_si128(dest128+1, xmm1); 
       _mm_stream_si128(dest128+2, xmm2);; 
       _mm_stream_si128(dest128+3, xmm3); 

            // cur128 is temporal, and will be used next time, which is why I choose store over stream 
       _mm_store_si128 (cur128+0, xmm0);    
       _mm_store_si128 (cur128+1, xmm1);     
       _mm_store_si128 (cur128+2, xmm2);     
       _mm_store_si128 (cur128+3, xmm3); 

       cur128 += 4; 
       dest128 += 4; 
       prev128 += 4; 
      } 

      std::swap(cur, prev); 

Answer 1

Sono d'accordo con tutti sul fatto che testare e perfezionare sia l'approccio migliore. Ma ci sono alcuni trucchi per aiutarlo.

Prima di tutto, MSVC fa riordinare l'istruzione SSE. Il tuo esempio è probabilmente troppo semplice o già ottimale.

In generale, se si dispone di un numero sufficiente di registri per farlo, l'interleaving completo tende a fornire i migliori risultati. Per fare un ulteriore passo avanti, srotoli i tuoi loop abbastanza da usare tutti i registri, ma non troppo da versare. Nel tuo esempio, il loop è completamente vincolato dagli accessi alla memoria, quindi non c'è molto spazio per fare di meglio.

Nella maggior parte dei casi, non è necessario ottenere l'ordine delle istruzioni perfetto per ottenere prestazioni ottimali. Finché è "abbastanza vicino", il compilatore o l'esecuzione fuori dall'hardware dell'hardware lo correggeranno automaticamente.

Il metodo che utilizzo per determinare se il mio codice è ottimale è l'analisi del percorso critico e del collo di bottiglia. Dopo aver scritto il ciclo, cerco quali istruzioni usano quali risorse. Usando queste informazioni, posso calcolare il limite superiore delle prestazioni, che poi confronta con i risultati effettivi per vedere quanto vicino/lontano sono ottimale.

Ad esempio, supponiamo di avere un ciclo con 100 aggiunte e 50 moltiplicazioni. Sia su Intel che su AMD (pre-Bulldozer), ciascun core può supportare un SSE/AVX add e un multiplo SSE/AVX per ciclo. Poiché il mio ciclo ha 100 aggiunte, so che non posso fare meglio di 100 cicli. Sì, il moltiplicatore sarà inattivo metà del tempo, ma il sommatore è il collo di bottiglia.

Ora vado e tempo il mio ciclo e ottengo 105 cicli per iterazione. Ciò significa che sono abbastanza vicino a quello ottimale e non c'è molto altro da guadagnare. Ma se ottengo 250 cicli, significa che c'è qualcosa di sbagliato nel ciclo e vale la pena armeggiare di più.

L'analisi del percorso critico segue la stessa idea. Cerca le latenze per tutte le istruzioni e trova il tempo di ciclo del percorso critico del loop. Se la tua performance reale è molto vicina ad essa, sei già ottimale.

Agner Fog ha un grande riferimento per i dettagli interni dei processori attuali: http://www.agner.org/optimize/microarchitecture.pdf

Answer 2

Ho appena costruita usando il compilatore VS2010 32bit e ottengo il seguente:

void F (void *cur, const void *prev, void *dest, int count) 
{ 
00901000 push  ebp 
00901001 mov   ebp,esp 
00901003 and   esp,0FFFFFFF8h 
    __m128i *cur128  = reinterpret_cast<__m128i*>(cur); 
00901006 mov   eax,220h 
0090100B jmp   F+10h (901010h) 
0090100D lea   ecx,[ecx] 
    const __m128i *prev128 = reinterpret_cast<const __m128i*>(prev); 
    __m128i *dest128 = reinterpret_cast<__m128i*>(dest); 
    __m128i *end  = cur128 + count/16; 

    while(cur128 != end)    
    { 
    auto xmm0 = _mm_add_epi8(_mm_load_si128(cur128+0), _mm_load_si128(prev128+0)); 
00901010 movdqa  xmm0,xmmword ptr [eax-220h] 
    auto xmm1 = _mm_add_epi8(_mm_load_si128(cur128+1), _mm_load_si128(prev128+1)); 
00901018 movdqa  xmm1,xmmword ptr [eax-210h] 
    auto xmm2 = _mm_add_epi8(_mm_load_si128(cur128+2), _mm_load_si128(prev128+2)); 
00901020 movdqa  xmm2,xmmword ptr [eax-200h] 
    auto xmm3 = _mm_add_epi8(_mm_load_si128(cur128+3), _mm_load_si128(prev128+3)); 
00901028 movdqa  xmm3,xmmword ptr [eax-1F0h] 
00901030 paddb  xmm0,xmmword ptr [eax-120h] 
00901038 paddb  xmm1,xmmword ptr [eax-110h] 
00901040 paddb  xmm2,xmmword ptr [eax-100h] 
00901048 paddb  xmm3,xmmword ptr [eax-0F0h] 

    // dest128 is USWC memory 
    _mm_stream_si128(dest128+0, xmm0); 
00901050 movntdq  xmmword ptr [eax-20h],xmm0 
    _mm_stream_si128(dest128+1, xmm1); 
00901055 movntdq  xmmword ptr [eax-10h],xmm1 
    _mm_stream_si128(dest128+2, xmm2);; 
0090105A movntdq  xmmword ptr [eax],xmm2 
    _mm_stream_si128(dest128+3, xmm3); 
0090105E movntdq  xmmword ptr [eax+10h],xmm3 

    // cur128 is temporal, and will be used next time, which is why I choose store over stream 
    _mm_store_si128 (cur128+0, xmm0);    
00901063 movdqa  xmmword ptr [eax-220h],xmm0 
    _mm_store_si128 (cur128+1, xmm1);     
0090106B movdqa  xmmword ptr [eax-210h],xmm1 
    _mm_store_si128 (cur128+2, xmm2);     
00901073 movdqa  xmmword ptr [eax-200h],xmm2 
    _mm_store_si128 (cur128+3, xmm3); 
0090107B movdqa  xmmword ptr [eax-1F0h],xmm3 

    cur128 += 4; 
00901083 add   eax,40h 
00901086 lea   ecx,[eax-220h] 
0090108C cmp   ecx,10h 
0090108F jne   F+10h (901010h) 
    dest128 += 4; 
    prev128 += 4; 
    } 
} 

il che dimostra che il compilatore riordino delle istruzioni, seguendo la regola generale di "non utilizzare un registro subito dopo aver scritto al registro ". Ha anche trasformato due carichi e un add in un singolo carico e un aggiunto dalla memoria. Non c'è motivo per cui non si possa scrivere il codice come questo e utilizzare tutti i registri SIMD invece dei quattro che si stanno utilizzando attualmente. È possibile che si desideri confrontare il numero totale di byte caricati con le dimensioni di una riga della cache. Questo darà al prefetching dell'hardware la possibilità di riempire la prossima linea della cache prima che ne abbiate bisogno.

Inoltre, il prefetch, specialmente nel codice che legge in modo sequenziale la memoria, spesso non è necessario. La MMU può precaricare fino a quattro flussi alla volta.

Answer 3

è possibile trovare i capitoli dal 5 al 7 del Intel Architectures Optimization Reference Manual molto interessanti, dettaglia il modo in cui Intel pensa che si dovrebbe andare a scrivere codice SSE ottimale, e descrive molte delle domande che si stanno facendo.

Answer 4

Voglio anche raccomandare l'architettura Intel® Code Analyzer:

https://software.intel.com/en-us/articles/intel-architecture-code-analyzer

Si tratta di una statica analizzatore di codice che aiuta a capire/ottimizzare percorsi critici, latenze e velocità effettiva. Funziona con Windows, Linux e MacO (l'ho provato solo su Linux). La documentazione ha un esempio medio-semplice su come usarlo (ad esempio, come evitare le latenze riordinando le istruzioni).