Sfogliando il forum, mi sono imbattuto in questo post di 3 anni fa, dell’utente @BestCrazyNoob. Ho notato che nessuno ha fornito una soluzione al nostro compagno! Così ho deciso di fornire una soluzione per tutti coloro che stessero riscontrando difficoltà a risolvere questo ostico problema.
Testo del problema (riassunto)
Viene dato un intero N con 1 \le N \le 1000, seguito da N numeri -1000 \le A_i \le 1000.
Il problema chiede di trovare il valore A_i massimo.
Suggerimenti
Hint 1: Usa un ciclo for.
Hint 2: Supponi di aver trovato il massimo tra i valori nel range [0, l]. Come puoi trovare facilmente il massimo nell’intervallo [0, l+1] ?
Hint 3: Guarda il limite di tempo.
Soluzione
Un enorme indizio viene dato dal limite di tempo del problema molto stretto: 1 secondo per 1000 interi! Il nostro programma deve essere velocissimo!
La soluzione ovviamente è usare SIMD Instructions (Intel Intrinsics)!
Queste istruzioni ci permettono di processare fino a 256 bit di informazioni (512 su avx512, non supportato dalla piattaforma training.olinfo.it) con un solo ciclo di clock! Vediamo passo passo come possiamo risolvere questo problema.
Includiamo innanzitutto il famosissimo header file immintrin.h.
Leggiamo poi l’input e salviamolo in un array sullo stack. Se N < 16 non ha senso usare SIMD (altrimenti ha molto senso, anzi è obbligatorio), perciò risolviamo il problema con un classico ciclo di ricerca sequenziale.
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int16_t arr[1000];
int16_t N;
cin >> N;
for(int16_t i = 0; i < N; i++)
cin >> arr[i];
if(N < 16) {
int16_t mx = arr[0];
for(int16_t i = 1; i < N; i++)
mx = max(mx, arr[i]);
cout << mx << "\n"; return 0;
}
Altrimenti, carichiamo i primi 16 elementi in un registro da 256 bit tramite la funzione _mm256_loadu_si256(const __m256i*), eseguendo un pointer cast su arr.
__m256i r = _mm256_loadu_si256((const __m256i*) arr);
Ora procediamo nell’array a blocchi di 16 elementi, eseguendo un massimo elemento per elemento (vertical max) tra i valori nel registro e quelli in memoria, tramite _mm256_max_epi16(__m256i, __m256i).
int16_t i = 16;
for(; i+16<=N; i+= 16)
{
r = _mm256_max_epi16(r, _mm256_loadu_si256((const __m256i*)(arr + i)));
}
Nel caso in cui N non sia un multiplo di 16, ci saranno dei valori avanzati in fondo all’array. Possiamo trovare il loro massimo in modo sequenziale:
int16_t ans = -1000;
for(; i < N; i++)
ans = max(ans, arr[i]);
Infine, dobbiamo eseguire una riduzione orizzontale (horizontal reduction) per trovare il massimo tra gli elementi all’interno del registro SIMD. Per fare ciò separiamo il registro da 16 valori in due da 8 (quindi di tipo __m128i) ed eseguiamo il massimo elemento per elemento sui due nuovi registri.
__m128i lo = _mm256_castsi256_si128(r);
__m128i hi = _mm256_extracti128_si256(r, 1);
__m128i m = _mm_max_epi16(lo, hi);
Ora abbiamo 8 elementi. Continuiamo a dimezzare il numero di elementi. Dato che l’uso di registri SIMD da 64 bit (MMX) è obsoleto e sconsigliato in combinazione con SSE/AVX, dobbiamo spostare gli elementi a mano dentro registri da 128 bit in posizioni diverse ed eseguire i rispettivi massimi.
Cominciamo con la prima riduzione 8 \rightarrow 4:
__m128i shuf = _mm_shuffle_epi32(m, _MM_SHUFFLE(1, 0, 3, 2));
m = _mm_max_epi16(m, shuf);
Innanzitutto, notiamo che _mm_shuffle_epi32(__m128i, int), come dice il nome, interpreta i valori come blocchi da 32 bit e non da 16 bit. Di conseguenza, la nostra maschera di shuffle sposta e riordina interi blocchi da 32 bit (ciascuno contenente 2 veri valori da 16 bit), allineandoli per l’effettiva riduzione che avverrà con l’operazione di max successiva.
Tramite la macro _MM_SHUFFLE(1,0,3,2) riordiniamo i blocchi da 32 bit nel seguente modo:
- Il blocco 2 finisce in posizione 0 (
_MM_SHUFFLE()si legge da dx a sx). - Il blocco 3 in posizione 1.
- Il blocco 0 in posizione 2.
- Il blocco 1 in posizione 3.
Infine, facciamo un max tra il registro shufflato e quello originale.
Sostanzialmente tramite questa serie di operazioni abbiamo eseguito un massimo elemento ad elemento tra i primi 4 elementi e gli ultimi 4, e il risultato di nostro interesse si trova ora nei primi 4 valori (i primi 64 bit) del registro da 128 bit.
Tramite un’operazione simile eseguiamo la riduzione 4 \rightarrow 2, questa volta usando _mm_shufflelo_epi16, che esegue lo shuffle a 16 bit limitatamente alla sola metà inferiore del registro (i primi 64 bit):
shuf = _mm_shufflelo_epi16(m, _MM_SHUFFLE(1, 0, 3, 2));
m = _mm_max_epi16(m, shuf);
Infine la riduzione finale 2 \rightarrow 1:
shuf = _mm_shufflelo_epi16(m, _MM_SHUFFLE(0, 3, 2, 1));
m = _mm_max_epi16(m, shuf);
Fatto ciò, abbiamo nel registro m in posizione 0 (i primi 16 bit del registro) il massimo. Possiamo quindi estrarre il valore, confrontarlo con il massimo sequenziale degli elementi extra, e stampare il valore finale:
cout << max((int16_t)_mm_extract_epi16(m, 0), ans) << "\n";
E con ciò, abbiamo risolto easy1! Spero che questo post sia stato di aiuto per @BestCrazyNoob e tutti coloro in difficoltà con questo problema!
(Prossimamente editorial di easy2)
Codice completo:
#pragma GCC target("avx2")
#include <iostream>
#include <cstdint>
#include <immintrin.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int16_t arr[1000];
int16_t N;
if (!(cin >> N)) return 0;
for(int16_t i = 0; i < N; i++) {
cin >> arr[i];
}
if(N < 16) {
int16_t mx = arr[0];
for(int16_t i = 1; i < N; i++) {
mx = max(mx, arr[i]);
}
cout << mx << "\n";
return 0;
}
__m256i r = _mm256_loadu_si256((const __m256i*) arr);
int16_t i = 16;
for(; i + 16 <= N; i += 16) {
r = _mm256_max_epi16(r, _mm256_loadu_si256((const __m256i*)(arr + i)));
}
int16_t ans = -1000;
for(; i < N; i++) {
ans = max(ans, arr[i]);
}
__m128i lo = _mm256_castsi256_si128(r);
__m128i hi = _mm256_extracti128_si256(r, 1);
__m128i m = _mm_max_epi16(lo, hi);
__m128i shuf = _mm_shuffle_epi32(m, _MM_SHUFFLE(1, 0, 3, 2));
m = _mm_max_epi16(m, shuf);
shuf = _mm_shufflelo_epi16(m, _MM_SHUFFLE(1, 0, 3, 2));
m = _mm_max_epi16(m, shuf);
shuf = _mm_shufflelo_epi16(m, _MM_SHUFFLE(0, 3, 2, 1));
m = _mm_max_epi16(m, shuf);
cout << max((int16_t)_mm_extract_epi16(m, 0), ans) << "\n";
return 0;
}