Che cos'è il "margine di prestazione del ninja?"

Un approccio ingenuo che finisca molte attività potrebbe essere quello di avviare un'attività, attendere che finisca e solo successivamente avviare l'attività successiva. Supponiamo di voler recuperare molte risorse di rete. L'approccio ingenuo sarebbe quello di inviare una richiesta per la prima risorsa, attendere che la richiesta venga completata, quindi inviare la successiva.

Se un buon programmatore è esperto in concorrenza, tale programmatore potrebbe scrivere un programma che esegue molte azioni in una sola volta usando tutte le risorse del computer su cui viene eseguito (processori, memoria di sistema, ecc.). Utilizzando l'esempio di risorsa di rete sopra, l'approccio ottimale sarebbe quello di tentare di ottenere molte risorse allo stesso tempo.

Il divario tra l'approccio ingenuo e l'approccio più ottimale è quello che questi autori (e apparentemente altri) chiamano il "gap delle prestazioni dei ninja".

Queste parole sono state scelte bene?

Probabilmente sono stati scelti per il valore promozionale e di novità. Poiché il fenomeno sembra essere un problema molto reale, avrei preferito un termine incentrato sul problema rispetto agli attori su un lato del gap.

Forse "gap di concorrenza ottimizzato" sarebbe stata una scelta migliore a parole.

Perché è così grande?

L'approccio ingenuo alla risoluzione di molti problemi con i computer può essere piuttosto inefficiente rispetto a miglioramenti noti.

La mia esperienza con Project Euler me lo ha dimostrato, con alcune soluzioni che non si completavano in un ragionevole lasso di tempo (minuti, ore), ma altre soluzioni allo stesso problema si sono rivelate incredibilmente veloci (in pochi secondi).

L'ordinamento a bolle è noto per essere piuttosto inefficiente rispetto ad altri algoritmi di ordinamento.

Mettiamo in dubbio la sua dimensione?

Sulla base delle conoscenze di cui sopra, non metto in dubbio le dimensioni come indicato.

Come può essere superato?

La soluzione ingenua sarebbe che il programmatore studiasse il threading e tutte le abilità rilevanti per colmare questa lacuna. Chiudere il gap in questo modo richiederebbe molto tempo e impegno, sia per acquisire le competenze che per scrivere i programmi.

Come impariamo a superarlo? Dovremmo imparare concurrency abile o imparare algoritmi?

L'abstract della carta afferma che l'utilizzo di algoritmi migliori combinati con migliori compilatori può ridurre il gap con il minimo sforzo richiesto. Sono propenso, senza conoscenza diretta, a crederli.

Tieni presente che la differenza è tra "codice scritto e parallelamente inconsapevole codice " e codice ottimizzato. La conclusione che c'è una differenza di qualità tra gli sviluppatori responsabili è completamente ingiustificata. Il codice inconsapevolmente scritto e parallelamente inconsapevole è molto più facile ed economico da scrivere, ed è molto più facile ed economico renderlo affidabile.

Ad un certo punto (e prima di iniziare a ottimizzare) occorre prendere una decisione sull'ottimizzazione dell'ottimizzazione. Il codice può essere eseguito 10 volte più velocemente, ma in questo modo si ottiene un valore uguale o superiore al costo dell'ottimizzazione? Non a tutti, ma a quelli che pagano per l'ottimizzazione? Quella decisione sarà spesso che l'ottimizzazione non sta dando i suoi frutti. In molti luoghi, il costo di esecuzione di un software non ottimizzato è molto inferiore al costo di ottimizzazione.

A casa, vado spesso in "modalità Ninja" perché è divertente. Migliorare la velocità del codice che ho scritto da un fattore 10 di solito non è un grosso problema. È successo che ho preso il codice assembler SIMD scritto a mano e l'ho migliorato di un fattore 10 con il codice C. Tuttavia, negli ultimi anni non ho riscontrato una situazione nella programmazione commerciale in cui vi fosse alcuna necessità. (C'era la necessità occasionale di sostituire codice stupido con codice ingenuo, che lo rendeva dieci volte più veloce o più).

Per la maggior parte delle situazioni, non è necessario ottimizzare. Non è assolutamente necessario che tutti siano in grado di scrivere codice ottimizzato.

Se inserisci il titolo del documento in Google Scholar otterrai un link al punto in cui IBM ospita il documento: link

Oppure puoi utilizzare direttamente Google e ottenere un link dove una delle istituzioni ospitanti dell'autore ha una versione completa del documento: link

La risposta breve è che devi leggere gli algoritmi progettati per il parallelismo (il documento elenca un numero di essi e le relative tecniche), ma in poche parole non esiste una pallottola d'argento disponibile. Le tecniche più comunemente utilizzate nella programmazione di oggi (metodi di ordinamento predefiniti, schemi di accesso, ecc.) Non sono in grado di trarre vantaggio dalla maggior parte dei miglioramenti delle prestazioni possibili con il calcolo parallelo. Per trarre vantaggio da più processori è necessario apprendere nuove tecniche, adattare gli strumenti esistenti e utilizzare il benchmark per vedere se ciò che si sta facendo funziona come ci si aspetta.

Il documento si riferisce all'ottimizzazione delle prestazioni sia dal parallelismo SIMD che multicore, insieme ad altre tecniche come lo srotolamento del ciclo e le prestazioni della cache. Quindi non è solo il parallelismo da solo.

"Ninja" si riferisce ai programmatori esperti. In altre parole, il "divario Ninja" è la differenza di prestazioni tra un capolavoro e il lavoro di un apprendista.

Il documento continua a spiegare come trasformare (riscrivere) in modo incrementale il lavoro di un apprendista in un capolavoro.

Citato dall'abstract (enfasi mia):

We show how a set of well-known algorithmic changes coupled with advancements in modern compiler technology can bring down the Ninja gap to an average of just 1.3X.

In altre parole, non si tratta di usare algoritmi ben noti ; si tratta di applicare tecniche di refactoring algoritmo ben note per i guadagni in termini di prestazioni.

Alcune delle tecniche di refactoring degli algoritmi citate nel documento sono:
(Il documento menziona solo i termini senza spiegazione, le mie spiegazioni potrebbero essere errate.)

• Blocco della cache (quando un algoritmo scorre attraverso una o più dimensioni, introdurre loop intermedi nell'iterazione per massimizzare la localizzazione della cache (località spaziale e temporale) e quindi i tassi di hit della cache)
• Modifica dei layout di memoria dei dati per migliorare la larghezza di banda e le prestazioni SIMD. In particolare, passaggio tra AOS e SOA (array di strutture e strutture di array), allineamento dei dati a cachelines e / o requisiti di allineamento SIMD, ecc.
• Passare ad algoritmi alternativi che danno risultati equivalenti ma sono più SIMD friendly.

Si noti che la carta non attribuisce tutti i vantaggi in termini di prestazioni all'uso di queste tecniche. Gli autori hanno anche sperimentato molte caratteristiche del compilatore come l'auto-vettorizzazione (nella generazione del codice SIMD), l'auto-parallelizzazione (su più core) e lo srotolamento del ciclo.