Apprendimento automatico e Reti Neurali - pagina 30

Nuovo commento
 

Lezione 10. Misurazione e tempistica



Lezione 10. Misurazione e tempistica

In questo video, i relatori discutono vari aspetti della misurazione e della tempistica nel calcolo, inclusi i fattori esterni che possono influire sulla precisione. Sottolineano la necessità di modelli e una chiara comprensione dei dati, riducendo la varianza per compensare gli errori e utilizzando appropriate chiamate temporali per garantire l'affidabilità. Discutono anche delle sfide nella misurazione accurata delle prestazioni del software, come la legge di potenza e i fattori non deterministici, mettendo in evidenza strumenti come la modellazione delle prestazioni, le chiamate di temporizzazione, i contatori hardware e i simulatori. Infine, mettono in guardia dal fare affidamento su un unico strumento, raccomandando la triangolazione e l'adattamento come tecniche per garantire risultati accurati.

Il relatore spiega l'importanza di una misurazione affidabile delle prestazioni nell'ingegneria del software delle prestazioni. Raccomanda l'uso delle statistiche per misurare con precisione le prestazioni e discute vari tipi di statistiche riassuntive come la media, che possono fornire utili misure delle prestazioni in diversi contesti. Sottolinea che prendere la media aritmetica dei rapporti non è un approccio valido e suggerisce invece di utilizzare la media geometrica. Il relatore sottolinea l'importanza di scegliere il modo corretto per aggregare i dati quando si confrontano i programmi e suggerisce di prendere la statistica di ordine basso, come il minimo o il 10%, da più esecuzioni per confrontare più accuratamente le prestazioni. Il relatore discute anche diverse metodologie per misurare e confrontare le prestazioni, incluso il confronto testa a testa e l'adattamento di un modello per ricavare statistiche, ma mette in guardia sul problema dell'overfitting nella modellazione. Nel complesso, il video sottolinea l'importanza di una misurazione affidabile delle prestazioni per migliorare le prestazioni del programma.

  • 00:00:00 In questa sezione, il relatore discute uno studio sul codice di ordinamento che è stato fatto da uno dei suoi ex studenti. Il codice utilizza il file di intestazione time.h per ottenere l'accesso alla routine di clock get time per le misurazioni di temporizzazione. Viene calcolata una routine di ordinamento e il tempo trascorso viene calcolato e stampato. Il grafico dei tempi di esecuzione misurati mostra che la routine di ordinamento segue per lo più una crescita N log N, ma i tempi misurati sono lenti anche per gli array più grandi.

  • 00:05:00 In questa sezione, un professore discute l'importanza di avere un modello per i dati osservati. Presenta un esempio in cui i dati misurati deviano significativamente da quanto previsto e chiede agli studenti di suggerire possibili ipotesi per questa deviazione. Mentre alcuni pensavano che potesse trattarsi di un problema con la cache o con la precisione dei tempi, il professore sottolinea che potrebbero esserci processi non correlati in esecuzione sulla macchina che stanno causando la deviazione. In questo caso, il problema riguarda la multi-tenancy, in cui la macchina viene utilizzata da più di un processo contemporaneamente. Il professore sottolinea la necessità di misurazioni di qualità e di avere una chiara comprensione del significato dei dati.

  • 00:10:00 In questa sezione, i relatori discutono di misurazione e temporizzazione nell'informatica e di come i fattori esterni possono influenzare l'accuratezza delle misurazioni. Si concentrano in particolare su come possono verificarsi variazioni della frequenza di clock a causa della temperatura del sistema e delle tecniche di risparmio energetico, che possono influire in modo significativo sui risultati delle misurazioni. Gli altoparlanti introducono il concetto di frequenza dinamica e ridimensionamento della tensione, che è una tecnica per ridurre la potenza regolando la frequenza di clock e la tensione ai transistor. Sottolineano che è fondamentale considerare i fattori esterni quando si effettuano misurazioni per evitare risultati imprecisi.

  • 00:15:00 In questa sezione, il relatore discute le sfide della misurazione delle prestazioni del software a causa della legge di potenza utilizzata dagli ingegneri elettrici. La legge sulla potenza afferma che la potenza è uguale a CV al quadrato di F, dove C è la capacità dinamica, V è la tensione di alimentazione e F è la frequenza di clock. Per ridurre la potenza e il calore, è possibile ridurre la frequenza e la tensione, con conseguente riduzione cubica della potenza. Ciò rappresenta una sfida per misurare le prestazioni del software in modo affidabile e l'oratore suggerisce di mettere in pausa i sistemi eliminando parte del rumore per effettuare misurazioni accurate. Discutono anche degli strumenti per misurare le prestazioni del software, come la modellazione delle prestazioni.

  • 00:20:00 In questa sezione, il relatore discute l'importanza di ridurre la varianza quando si tratta di misurazione e tempistica, specialmente nel contesto dell'ingegneria delle prestazioni. Riducendo la variabilità, è possibile compensare errori di misurazione sistematici e casuali e richiedere meno prove per confrontare i programmi. L'oratore sottolinea inoltre varie fonti di variabilità nei sistemi informatici, inclusi lavori in background, interruzioni e posizionamento di thread, tra gli altri. Infine, sottolinea l'importanza di concentrarsi sulla riduzione della varianza prima di tentare di apportare modifiche al sistema, poiché la misurazione durante un'elevata varianza può portare a risultati inaffidabili.

  • 00:25:00 In questa sezione, il relatore parla del concetto di hyper-threading nei processori e di come può portare a misurazioni imprecise nei sistemi cloud. L'hyper-threading esegue due flussi di istruzioni attraverso un'unità funzionale, che appare come due processori, ma in realtà fornisce solo un aumento della velocità del 20% anziché due processori separati. Il relatore discute anche di altre tecniche come il turbo boost e la disattivazione di un sistema, che possono influenzare in modo significativo i risultati della misurazione. Disattivando l'hyper-threading e il turbo boost e disattivando tutti i demoni, l'oratore e il suo gruppo sono stati in grado di ottenere misurazioni notevolmente affidabili che erano meno dell'1% più lente del tempo di esecuzione minimo.

  • 00:30:00 In questa sezione, l'oratore parla di vari fattori che possono influenzare il determinismo di un programma in esecuzione su hardware moderno. Mentre ci sono alcune misure che si possono prendere per rendere il programma più deterministico, è impossibile eliminare completamente i fattori non deterministici. La maggior parte dei fattori non deterministici che possono sorgere durante l'esecuzione del programma, come la memorizzazione nella cache, gli interrupt, il threading e la predizione dei rami, sono processi deterministici. Tuttavia, la casualità nell'hardware è al di fuori del controllo dell'utente e può causare un errore di memoria. L'oratore suggerisce che l'allineamento del codice può fare la differenza nel determinismo del programma e qualsiasi modifica apportata al codice può causare uno spostamento nell'allineamento della cache, influenzando il determinismo del programma.

  • 00:35:00 In questa sezione, il relatore spiega come piccoli cambiamenti possono avere un grande impatto sulle prestazioni di un programma. Ad esempio, l'inserimento di un byte può causare un impatto lineare su tutto ciò che segue e la modifica dell'ordine in cui i file punto o appaiono sulla riga di comando del linker può avere un effetto maggiore rispetto al passaggio tra -OH- e -O3. Per affrontare questi problemi, i compilatori stanno riconoscendo il problema e facendo più allineamento. LLVM ha interruttori che possono allineare tutte le funzioni e i blocchi in una funzione, ma l'allineamento può rallentare il programma. Inoltre, il nome del programma può influire sulla sua velocità poiché il nome dell'eseguibile finisce in una variabile di ambiente che finisce nello stack di chiamate.

  • 00:40:00 In questa sezione, il relatore discute vari strumenti e metodi per misurare le prestazioni del software, inclusa la misurazione esterna del programma con il comando time, l'inserimento di chiamate di temporizzazione nel programma utilizzando clock get time o altri metodi, l'interruzione del programma con gdb per identificare quale routine sta impiegando più tempo, sfruttando il supporto hardware e del sistema operativo come quelli utilizzati nel set di strumenti perf o simulando il programma per ottenere una comprensione più profonda ma a una velocità inferiore. L'oratore spiega la differenza tra il tempo trascorso, l'ora dell'utente e l'ora del sistema quando si utilizza il comando time e come potrebbero non sommarsi al tempo totale a causa dell'allocazione del processore.

  • 00:45:00 In questa sezione, il relatore discute i diversi tipi di temporizzazione e misurazione, incluso il tempo dell'orologio, il tempo del processore trascorso in modalità utente e il tempo trascorso nel kernel. La chiamata di temporizzazione consigliata per l'uso è clock get time con l'opzione clock monotonic che garantisce di non tornare mai indietro. Sebbene l'esecuzione possa richiedere una quantità di tempo non deterministica, è più affidabile di altri timer come RTIDTSC che possono fornire risposte diverse su core diversi e possono essere eseguiti all'indietro. L'oratore mette in guardia contro l'uso di ottenere l'ora del giorno.

  • 00:50:00 In questa sezione, il relatore discute vari modi per misurare e cronometrare gli eventi nella programmazione, incluso l'uso di clock_gettime e la misurazione con il comando time. Avvertono che nel tempo le tecniche potrebbero cambiare e gli ingegneri potrebbero dover adattarsi. L'oratore suggerisce anche di interrompere il codice in momenti casuali come semplice tecnica di profilazione e menziona che grandi aziende come Facebook utilizzano questo metodo. Inoltre, il relatore introduce l'idea dei contatori hardware e della libreria livepFM4, che consente l'accesso a questi contatori in base al processo. Sottolineano che un ingegnere potrebbe non aver sempre bisogno di strumenti chirurgicamente precisi e che a volte uno strumento semplice può essere sufficiente per il lavoro.

  • 00:55:00 In questa sezione, il relatore discute i diversi modi di raccogliere misurazioni, inclusi contatori hardware e simulatori. Avvertono che molti contatori hardware sono scarsamente documentati e che alcuni strumenti condividono la larghezza di banda se vengono utilizzati più di quattro o cinque contatori. I simulatori sono elogiati per la loro ripetibilità, ma potrebbero non modellare tutto nella cache. L'oratore consiglia la triangolazione e l'utilizzo di almeno due misurazioni per garantire la precisione. Sottolineano inoltre l'importanza di disporre di un modello di performance per guidare l'interpretazione dei dati.

  • 01:00:00 In questa sezione, il relatore spiega il processo di ingegneria del software delle prestazioni, che implica prendere un programma, apportarvi modifiche e misurarne le prestazioni per produrre un programma più veloce. Tuttavia, una misurazione affidabile delle prestazioni è fondamentale per apportare piccole modifiche che si sommano e trarre conclusioni accurate. Pertanto, l'oratore consiglia di utilizzare le statistiche per ottenere un quadro accurato di ciò che sta accadendo. Offre anche un enigma che coinvolge la misurazione delle prestazioni grezze di un programma deterministico e conclude che l'utilizzo del minimo è il modo migliore per rifiutare il rumore e determinare le prestazioni hardware sottostanti del programma.

  • 01:05:00 In questa sezione vengono discussi vari tipi di statistiche riassuntive, inclusa la media, che possono fornire misure utili delle prestazioni in diversi contesti. Quando si valutano i server Web, l'utilizzo della CPU e il tempo totale di completamento dell'attività possono essere misurati utilizzando la media aritmetica, mentre il tempo reale e il comportamento percentile possono essere più rilevanti per ottimizzare la soddisfazione delle richieste. Tuttavia, quando si riassumono i rapporti, ad esempio confrontando le prestazioni dei programmi A e B, prendere la media aritmetica non è un approccio valido, anche se è comunemente usato in modo improprio. Questo perché la media dei rapporti non è la stessa del rapporto stesso, come illustrato nell'esempio riportato nel video.

  • 01:10:00 In questa sezione, il relatore discute i problemi relativi al confronto di rapporti e medie durante la misurazione delle prestazioni. Dimostrano che prendere la media aritmetica dei rapporti può portare a risultati sospetti, ed è meglio usare la media geometrica. Inoltre, notano che quando si confrontano i tassi, la media armonica è spesso utile. Viene sottolineata l'importanza di scegliere il modo corretto per aggregare i dati quando si confrontano i programmi e il relatore suggerisce di prendere la statistica di ordine basso, come il minimo o il 10%, da più esecuzioni per confrontare più accuratamente le prestazioni.

  • 01:15:00 In questa sezione, il relatore discute diverse metodologie per misurare e confrontare le prestazioni. Un approccio consiste nel confrontare le opzioni più economiche del 10% e fare la riduzione del rumore per confrontare i mezzi, anche se potrebbe non fornire prove conclusive. In alternativa, è possibile condurre un confronto testa a testa tra A e B per vedere quale vince più frequentemente. Attraverso questo, l'ipotesi nulla può essere verificata e il valore p può essere calcolato per determinare se la deviazione è significativa. Questo metodo è comunemente usato nelle scienze sociali e può essere utile in ambienti rumorosi. Infine, il relatore accenna brevemente all'idea di adattare un modello per derivare statistiche e discute l'uso dell'approssimazione dei minimi quadrati.

  • 01:20:00 In questa sezione, il relatore discute il problema dell'overfitting nella modellazione e come l'aggiunta di più funzioni di base può migliorare l'adattamento dei dati ma anche portare all'overfitting. La soluzione è rimuovere una funzione di base e verificare se influisce sulla qualità del modello. L'oratore cita anche Lord Kelvin, noto come il Guru della misurazione, il quale affermava che misurare è conoscere e se non si può misurare non si può migliorare. Il video si conclude con l'oratore che augura buona fortuna a un quiz martedì.
 

Lezione 11. Allocazione della memoria



Lezione 11. Allocazione della memoria

Il docente discute l'allocazione dello spazio di archiviazione in questo video, coprendo sia l'allocazione che la liberazione della memoria. Vengono affrontati diversi tipi di archiviazione, inclusi lo stack e l'heap, nonché schemi di allocazione di dimensioni fisse e variabili. Viene discussa anche la frammentazione esterna causata dalla diffusione di blocchi di memoria, con soluzioni come liste libere o bitmap per pagina del disco. Viene inoltre introdotto il concetto di Garbage Collection, incluso il conteggio dei riferimenti e le limitazioni di questo algoritmo. Vengono inoltre spiegate le procedure di garbage collection "mark and sweep" e "stop and copy", con particolare attenzione a come quest'ultima affronta la frammentazione e il possibile problema di correttezza creato dagli aggiornamenti dei puntatori. Il video si conclude con note sulla complessità temporale e spaziale dell'algoritmo stop and copy e la sua eliminazione della frammentazione esterna.

Questo video copre vari argomenti relativi all'allocazione dinamica dello storage, tra cui il sistema Buddy, le procedure di mark and sweep, le ottimizzazioni, la garbage collection generazionale e in tempo reale, l'allocazione dello storage multi-thread e la garbage collection parallela. Il docente spiega che la garbage collection generazionale si basa sull'idea che gli oggetti più giovani vengono scansionati più frequentemente, mentre la garbage collection in tempo reale viene eseguita in background durante l'esecuzione del programma, ma può portare a problemi di correttezza se l'oggetto e il grafico del puntatore continuano a cambiare. Infine, la lezione riassume i diversi tipi di allocazione della memoria, inclusi stack e heap, e diversi metodi di raccolta dei rifiuti, come il conteggio dei riferimenti, mark-and-sweep e stop-and-copy. Il docente afferma che gli studenti potranno provare alcuni di questi metodi nei loro prossimi compiti a casa.

  • 00:00:00 In questa sezione, il docente discute l'allocazione della memoria, che include sia l'allocazione che la liberazione della memoria. La forma più semplice di archiviazione è uno stack, in cui la memoria viene allocata incrementando il puntatore dello stack e liberata decrementando il puntatore dello stack. Tuttavia, lo stack ha un'applicabilità limitata perché può liberare solo l'ultima cosa che è stata allocata e non può liberare nulla al centro dell'area utilizzata. Il docente osserva inoltre che, per motivi di efficienza, l'overflow dello stack non viene solitamente controllato dai compilatori.

  • 00:05:00 In questa sezione, il docente parla di due tipi di archiviazione: lo stack e l'heap. Lo stack è uno spazio di archiviazione di dimensioni fisse che è efficiente ma non può essere utilizzato per tutto, mentre l'heap è più generale ma difficile da organizzare e utilizzare in modo efficiente. Per l'allocazione dell'heap, è possibile utilizzare le funzioni malloc e C gratuite, ma poiché C e C++ non forniscono un Garbage Collector, i programmatori devono gestire la memoria da soli, il che può portare a perdite di memoria, puntatori penzolanti e doppia liberazione. Il docente suggerisce di utilizzare i correttori di memoria come il disinfettante per indirizzi e Valgrind per ridurre il numero di bug di memoria nel programma.

  • 00:10:00 In questa sezione, l'oratore discute i diversi modi di allocare lo spazio di archiviazione, a partire dall'allocazione di dimensioni fisse, in cui ogni pezzo di spazio di archiviazione ha le stesse dimensioni e alcuni blocchi vengono utilizzati mentre altri sono inutilizzati. I blocchi inutilizzati sono conservati in un elenco chiamato elenco libero e ogni blocco nell'elenco libero ha un puntatore al blocco successivo nell'elenco. Per allocare un oggetto dall'elenco libero, il programma imposta il puntatore come libero e quindi imposta il puntatore libero in modo che punti alla cosa successiva nell'elenco libero, restituendo il puntatore al primo oggetto nell'elenco libero. Per deallocare, basta impostare il prossimo puntatore dell'oggetto su free e impostare free uguale all'oggetto da liberare. Con l'elenco libero, l'allocazione e la liberazione richiedono un tempo costante e si ottiene anche una buona località temporale.

  • 00:15:00 In questa sezione viene introdotto il concetto di frammentazione esterna, che si verifica quando blocchi di memoria utilizzata sono distribuiti nello spazio di tutta la memoria. Ciò può portare a una tabella delle pagine più grande, che può causare il thrashing del disco e rendere meno efficiente la ricerca delle traduzioni. Per mitigare la frammentazione esterna, è possibile utilizzare un elenco libero o una bitmap per pagina del disco e si può eseguire l'allocazione dalla pagina più completa, liberare blocchi di storie e sfogliare le pagine vuote. L'allocazione dell'heap a dimensione fissa può essere utile anche per ridurre la frammentazione esterna. Infine, l'allocazione dell'heap di dimensione variabile può essere utilizzata con elenchi liberi di bin, che sfruttano l'efficienza degli elenchi liberi per diverse dimensioni di memoria allocata.

  • 00:20:00 In questa sezione viene presentato uno schema per memorizzare blocchi di memoria di varie dimensioni in un sistema di allocazione della memoria. Lo schema prevede la divisione dei blocchi in contenitori in base alla loro dimensione, con ciascun contenitore che contiene blocchi di una dimensione specificata che sono potenze di due. Quando si alloca la memoria, viene selezionato il contenitore appropriato in base alla dimensione richiesta e, se è vuoto, un contenitore non vuoto più grande viene suddiviso in blocchi più piccoli per ottenere la dimensione desiderata. Tuttavia, questo schema può comportare una frammentazione interna della memoria, che è uno spreco, quindi il numero di contenitori utilizzati è limitato e piccoli blocchi vengono raggruppati in pagine per ridurre il sovraccarico. Il sistema operativo può essere utilizzato per fornire più memoria, se necessario, e sono disponibili chiamate di sistema per questo scopo.

  • 00:25:00 In questa sezione, il video discute come funziona l'allocazione della memoria e osserva che le implementazioni standard di 'malloc' si basano su comandi come 'break' per ottenere memoria dal sistema operativo. Il sistema operativo offre una grossa fetta di memoria e spetta al sistema di allocazione dello storage suddividerla in blocchi più piccoli. Questa sezione copre anche le varianti dell'allocatore di memoria, inclusi diversi schemi per la memorizzazione delle dimensioni dei blocchi e il modo in cui lo spazio degli indirizzi della memoria virtuale è strutturato in un programma. Rileva che lo stack e l'heap crescono l'uno verso l'altro ma non si intersecano mai. Infine, si dice che il pre-calcolo di grandi tabelle di costanti in un programma può aumentare il tempo di caricamento in quanto richiede la lettura dal segmento di dati.

  • 00:30:00 In questa sezione viene discusso il problema della frammentazione con la memoria virtuale, che può portare a frammentazione esterna, prestazioni degradate della tabella delle pagine, thrashing del disco e basse percentuali di hit TLB se la memoria è distribuita. L'obiettivo dell'allocazione dello storage è utilizzare la minor quantità possibile di memoria virtuale mantenendo compatte le parti utilizzate della memoria. Viene analizzato lo schema di allocazione dell'elenco libero di bin, con un teorema che afferma che la quantità di memoria virtuale consumata dall'archiviazione dell'heap è limitata in alto da M log M. L'unione di blocchi più piccoli in blocchi più grandi può migliorare lo schema dell'elenco libero di bin, ma l'overhead di questo metodo può essere elevato rispetto all'algoritmo standard della lista libera dei contenitori, che è solo un fattore costante peggiore dell'allocatore ottimale, secondo un articolo di Charles Leiserson.

  • 00:35:00 In questa sezione, il relatore spiega il concetto di allocazione dello storage e come può ridurre la frammentazione quando si ha a che fare con l'heap storage. Discute anche l'idea della raccolta dei rifiuti, che libera il programmatore dal dover liberare manualmente gli oggetti. Il relatore spiega i tre tipi di oggetti della memoria - radici, oggetti vivi e oggetti morti - e come la raccolta dei rifiuti può riciclare questi ultimi. Infine, descrive il conteggio dei riferimenti, una semplice forma di raccolta dei rifiuti che conta il numero di puntatori che fanno riferimento a un oggetto per determinare se può essere liberato.

  • 00:40:00 In questa sezione, il relatore introduce il concetto di conteggio dei riferimenti come schema di raccolta dei rifiuti e spiega come funziona l'algoritmo del conteggio dei riferimenti. Si segnala però una limitazione dell'algoritmo, dove non è possibile raccogliere i cicli nel grafo di riferimento. Il relatore discute quindi l'uso di puntatori forti e deboli in alcuni linguaggi di programmazione per evitare questa limitazione. Infine, il relatore presenta in anteprima altri due schemi di garbage collection, "mark-and-sweep" e "stop and copy", che evitano la limitazione del conteggio dei riferimenti quando si tratta di cicli nel grafico di riferimento.

  • 00:45:00 In questa sezione, il relatore discute l'uso di un algoritmo di ricerca in ampiezza per trovare tutti gli oggetti vivi nella memoria. Viene utilizzato un array con due puntatori per rappresentare una coda FIFO per la ricerca e l'algoritmo contrassegna ogni oggetto attivo raggiungibile dalle radici. Al termine della ricerca, gli oggetti non contrassegnati sono disponibili per il Garbage Collection. La procedura mark-and-sweep prevede due fasi: la fase contrassegnata, che coinvolge l'algoritmo di ricerca in ampiezza, e la fase di scansione, che comporta la scansione della memoria per liberare oggetti non contrassegnati. Tuttavia, ci sono limitazioni a questo schema, come la necessità di scansionare tutta la memoria e il sovraccarico associato alla ricerca di oggetti senza riferimenti.

  • 00:50:00 In questa sezione, il video introduce la procedura di garbage collection "stop and copy" che si occupa della frammentazione. Questa procedura è simile all'algoritmo mark and sweep ma adotta un approccio diverso per garantire che gli oggetti live siano contigui nella memoria. La procedura utilizza due spazi di memoria separati, lo spazio from e lo spazio to, e alloca e libera gli oggetti dallo spazio from finché non si riempie. Quindi, viene eseguito l'algoritmo di Garbage Collection e lo spazio due viene utilizzato come coda per la ricerca in ampiezza per identificare gli oggetti attivi, che verranno inseriti in modo contiguo nella memoria nello spazio due. Tuttavia, l'utilizzo di questo algoritmo può portare a un possibile problema di correttezza in cui i puntatori che puntano a oggetti nello spazio from potrebbero non essere più corretti. Per risolvere questo problema, la procedura memorizza un puntatore di inoltro nell'oggetto corrispondente nello spazio from e aggiorna tutti i puntatori seguendo questi puntatori di inoltro durante la rimozione di un oggetto dalla coda nella ricerca in ampiezza.

  • 00:55:00 In questa sezione, il relatore discute l'algoritmo di Garbage Collection stop and copy, la sua complessità temporale e come gestisce la frammentazione esterna. L'algoritmo stop and copy comporta la copia di oggetti dallo spazio from allo spazio to e quindi l'aggiornamento dei puntatori di questi oggetti nello spazio to. Questo algoritmo è lineare nel tempo e nello spazio, il che lo rende un modo più efficiente ed efficace di raccolta dei rifiuti. Quando lo spazio from diventa pieno, l'utente può richiedere un nuovo spazio heap e raddoppiare la dimensione dello spazio from. Lo spazio di memoria virtuale richiesto da questo schema è costante volte ottimale e questo algoritmo elimina la frammentazione esterna.

  • 01:00:00 In questa sezione, il relatore discute più argomenti relativi all'allocazione dinamica dello storage come il sistema Buddy per fare coalescing, varianti della procedura mark and sweep, ottimizzazioni per migliorare le prestazioni, garbage collection generazionale, garbage collection in tempo reale , allocazione di archiviazione multi-thread e Garbage Collection parallela. La garbage collection generazionale si basa sull'idea che molti oggetti hanno vita breve, quindi solo gli oggetti più giovani vengono scansionati per la maggior parte del tempo. La raccolta dei rifiuti in tempo reale funziona in background mentre il programma è in esecuzione, ma potrebbe portare a problemi di correttezza se il grafico di oggetti e puntatori sta cambiando. L'allocazione di archiviazione multi-thread e la garbage collection parallela hanno più thread in esecuzione, il che rende gli algoritmi più complicati da gestire con le corse e altri problemi di correttezza. L'oratore riassume anche i diversi tipi di allocazione della memoria, inclusi lo stack e l'heap, e diversi modi per eseguire la raccolta dei rifiuti, come il conteggio dei riferimenti, mark-and-sweep e stop-and-copy.

  • 01:05:00 In questa sezione, l'istruttore ha affermato che approfondiranno ulteriormente gli schemi di allocazione dello spazio di archiviazione e che gli studenti avranno l'opportunità di provarne alcuni nei loro prossimi compiti a casa. L'istruttore ha quindi concluso la lezione e ha aperto la parola per ulteriori domande.
 

Lezione 12. Parallel Storage Allocation



Lezione 12. Parallel Storage Allocation

Il video discute varie strategie di allocazione della memoria e i loro compromessi. Viene spiegato l'uso di malloc e dell'allocazione allineata, nonché l'importanza di una corretta deallocazione della memoria con free. Viene trattato anche l'uso di Mmap per l'allocazione della memoria virtuale, insieme ai problemi della frammentazione esterna e del rallentamento delle prestazioni. Viene esplorato il concetto di stack nella programmazione C e C++, con enfasi posta su un approccio di stack di cactus basato su heap per l'allocazione di frame di stack, che può portare a migliori dimostrazioni spaziali e limiti superiori. Viene discusso anche l'uso di un pool di stack lineari, insieme all'importanza dell'ottimizzazione per piccoli blocchi per ridurre al minimo la frammentazione. Il video si conclude con una discussione sugli approcci heap globali e locali e sui loro potenziali problemi, insieme ad approcci come elenchi liberi di bin e ribilanciamento periodico della memoria per risolvere questi problemi.

Il video illustra anche le soluzioni per l'allocazione di storage in parallelo e introduce l'allocatore Hoard come soluzione. L'allocatore Hoard utilizza una combinazione di heap locali e globali e grandi super blocchi che possono essere spostati tra gli heap per ridurre la falsa condivisione, migliorare la scalabilità e ridurre la frammentazione esterna. Lo spazio di archiviazione massimo allocato nell'heap globale è al massimo lo spazio di archiviazione massimo allocato negli heap locali e il footprint è limitato in alto dal footprint dell'utente più lo spazio di archiviazione allocato ma inutilizzato negli heap locali. Il video discute anche brevemente di altri allocatori come Je malloc e Super malloc, con risultati di benchmark che indicano che Super malloc ha ottenuto risultati migliori di Je malloc e Hoard. La discussione si conclude con un riferimento alle diapositive online per i dettagli della raccolta dei rifiuti.

  • 00:00:00 In questa sezione, il docente passa in rassegna le primitive di allocazione della memoria, tra cui malloc e allocazione allineata. L'allocazione allineata può essere utilizzata per allineare la memoria alle righe della cache in modo che l'accesso a un oggetto all'interno di una riga della cache richieda solo un accesso alla cache, riducendo il numero di cache miss. Il docente discute anche l'importanza di deallocare correttamente la memoria con la funzione libera ed evitare perdite di memoria e doppia liberazione. Infine, il docente introduce la chiamata di sistema Mmap, che può essere utilizzata per allocare memoria virtuale senza un file di supporto.

  • 00:05:00 In questa sezione, l'oratore spiega il processo di allocazione della memoria utilizzando M map, che è una chiamata di sistema che trova una regione contigua inutilizzata nello spazio degli indirizzi dell'applicazione abbastanza grande da contenere la dimensione della memoria richiesta e aggiorna il tabella delle pagine per contenere una voce per le pagine allocate. A differenza di malloc, che è una chiamata di libreria e parte del codice di gestione dell'heap della libreria C, M map non alloca immediatamente memoria fisica per la memoria richiesta ma popola la tabella delle pagine con voci che puntano a una speciale pagina zero che viene modificata e tradotto in memoria fisica solo quando l'utente vi scrive per la prima volta. Inoltre, M map è responsabile dell'ottenimento della memoria dal sistema operativo, mentre malloc è responsabile del riutilizzo della memoria allocata in precedenza per ridurre la frammentazione e migliorare la località temporale.

  • 00:10:00 In questa sezione, il video discute le differenze tra l'utilizzo di MMAP e MALLOC per l'allocazione dello spazio di archiviazione, sottolineando che MMAP è relativamente pesante e alloca intere pagine anche per piccole allocazioni, portando a frammentazione esterna e prestazioni lente. Il video esamina anche il processo di traduzione degli indirizzi, in cui l'indirizzo virtuale viene utilizzato per accedere alla memoria e l'hardware cerca l'indirizzo fisico appropriato nella tabella delle pagine. Il video spiega come funzionano i TLB memorizzando nella cache le ricerche recenti nella tabella delle pagine e osserva che i programmi con località spaziale o temporale avranno molti accessi recenti memorizzati nel TLB, portando a prestazioni più veloci.

  • 00:15:00 In questa sezione, il relatore discute di come funziona la traduzione degli indirizzi nelle macchine moderne e approfondisce anche il concetto di stack nella programmazione C e C++. Gli stack vengono utilizzati per tenere traccia delle chiamate di funzione e delle variabili locali e seguono un ordine lineare. L'oratore sottolinea una regola dei puntatori negli stack lineari tradizionali: un genitore può passare i puntatori alle sue variabili di stack fino ai suoi figli, ma non viceversa, per evitare di sovrascrivere le variabili. L'oratore suggerisce anche opzioni, come l'allocazione della memoria sull'heap o sullo stack del genitore, per passare la memoria da una funzione figlia al genitore.

  • 00:20:00 l'allocazione dell'heap parallelo è corretta, il potenziale problema con l'utilizzo di uno stack di cactus basato su heap è la frammentazione della memoria, dove potrebbe non esserci abbastanza memoria contigua rimasta per allocazioni future, portando allo spazio sprecato e potenzialmente all'esaurimento di memoria o mandare in crash il programma. Sebbene i primi sistemi per la programmazione parallela utilizzassero questa strategia, è importante ottimizzare il codice per ridurre al minimo l'impatto sulle prestazioni e considerare le conseguenze della frammentazione della memoria.

  • 00:25:00 In questa sezione, il video discute l'uso di un approccio stack cactus basato su heap per l'allocazione di stack frame senza porre un limite superiore alla profondità massima. Tuttavia, l'interoperabilità è un problema quando si tenta di utilizzare il codice stack lineare tradizionale con questo stack cactus basato su heap. Questo problema può essere risolto utilizzando un approccio chiamato mappatura della memoria locale del thread, ma questo approccio richiede modifiche al sistema operativo. Nonostante ciò, l'approccio dello stack di cactus basato su heap è ancora valido nella pratica e può essere utilizzato per dimostrare uno spazio limitato di un programma Silk che lo utilizza. Questo limite di spazio mostra che lo spazio dello stack di un'esecuzione di P worker che utilizza uno stack cactus basato su heap è limitato in alto da P per s1, dove s1 è lo spazio dello stack richiesto da un'esecuzione seriale del programma Silk. Questa è una bella caratteristica dell'approccio stack di cactus basato su heap.

  • 00:30:00 In questa sezione, viene analizzato il codice di moltiplicazione della matrice divide et impera per capire come può essere applicato al Teorema del compromesso spazio-tempo. Il codice effettua otto chiamate ricorsive, ciascuna di dimensione N/2, e prima di ogni chiamata esegue un malloc per ottenere uno spazio temporaneo di ordine di dimensione N al quadrato, che viene quindi liberato subito prima che la funzione ritorni. Poiché le allocazioni seguono una disciplina dello stack, anche quando si esegue l'allocazione dall'heap, lo spazio limitato dalla diapositiva precedente può essere utilizzato per il limite superiore dello spazio di lavoro P. Il lavoro è N al cubo e lo span è l'ordine log al quadrato di N. La ricorrenza per lo spazio è s di N/2 + theta di N al quadrato, che si risolve in N al quadrato. Pertanto, la proprietà delle foglie occupate e il teorema per lo spazio limitato mostrano che su P processori lo spazio è limitato da P per N al quadrato.

  • 00:35:00 In questa sezione, l'oratore guida il pubblico attraverso come dimostrare un limite di spazio più forte per l'algoritmo discusso nella sezione precedente. Analizzando la struttura dell'algoritmo e concentrandosi sulla ramificazione il più possibile vicino alla parte superiore dell'albero di ricorsione, il relatore è in grado di dimostrare uno spazio limitato di P a un terzo di N al quadrato, che è migliore dei precedenti limiti superiori . Il relatore osserva che l'analisi della struttura di un algoritmo può portare a dimostrazioni legate allo spazio più forti rispetto alla semplice applicazione di un teorema generale. La sezione si conclude discutendo di come le funzioni parallele non riescono a interagire con binari seriali legacy e di terze parti.

  • 00:40:00 In questa sezione, il relatore discute l'uso di un pool di stack lineari nell'allocazione dello storage, che può essere utilizzato per mantenere un pool di stack per il codice legacy. Il numero di stack nel pool deve essere costante moltiplicato per il numero di processori in modo da preservare lo spazio limitato. Tuttavia, questa strategia può influire sul limite di tempo dell'algoritmo di furto del lavoro perché il lavoratore potrebbe non essere in grado di rubare se non ci sono più pile disponibili. Il relatore parla quindi delle proprietà di base degli allocatori di memoria heap, tra cui la velocità dell'allocatore e l'impronta dell'utente, sottolineando l'importanza dell'ottimizzazione per piccoli blocchi a causa del potenziale di frammentazione e del sovraccarico nell'allocazione. La frammentazione è definita come l'impronta dell'allocatore divisa per l'impronta dell'utente.

  • 00:45:00 In questa sezione del video, il relatore discute su come mantenere il footprint allocato il più vicino possibile al footprint dell'utente per ridurre al minimo il rapporto tra i due. Una soluzione è usare qualcosa chiamato M advise, che dice al sistema operativo che una certa pagina di memoria non è più necessaria ma dovrebbe essere conservata nella memoria virtuale. Il relatore cita anche il teorema della lezione precedente secondo cui la frammentazione per le liste libere di contenitori è il log dell'ordine in base due di U, dove U è la quantità totale di memoria allocata, e spiega le differenze tra sovraccarico di spazio, frammentazione interna e frammentazione esterna. Infine, il relatore osserva che i moderni processori a 64 bit forniscono da 2 a 48 byte di spazio di indirizzi virtuali, che è sufficiente per la maggior parte dei programmi ma comunque più della memoria fisica su una macchina tipica.

  • 00:50:00 In questa sezione, il video esplora una strategia di allocazione heap parallela utilizzando un heap globale con protezione mutex, che è il modo in cui funziona l'allocatore C++ predefinito. L'esplosione di questa strategia è una, in quanto non richiede spazio aggiuntivo rispetto a un allocatore seriale. Tuttavia, il potenziale problema con questo approccio è il calo delle prestazioni, poiché l'acquisizione del blocco per ogni allocazione e deallocazione è lenta e peggiora con l'aumento dei processori. La contesa dei blocchi è la ragione principale della scarsa scalabilità, che è più problematica per le piccole allocazioni a causa dei tassi di richiesta più elevati e le allocazioni di blocchi di grandi dimensioni richiedono più lavoro.

  • 00:55:00 In questa sezione, il video discute il potenziale problema con l'utilizzo di un approccio heap locale, che è che può portare alla deriva della memoria e all'esplosione illimitata. In sostanza, se si alloca tutta la memoria in un thread ma la si libera in un altro, potrebbe esserci memoria inutilizzata nel sistema che l'allocatore non è abbastanza intelligente da riutilizzare. Di conseguenza, il tuo programma in esecuzione su più processori potrebbe eventualmente esaurire la memoria, ma non accadrà se viene eseguito solo su un singolo core. Il video suggerisce di utilizzare un approccio all'elenco bin free per risolvere questo problema, che prevede l'impostazione di puntatori nella struttura dei dati dell'elenco bin free in modo che il blocco liberato possa essere visualizzato in uno degli elenchi collegati. Un'altra strategia consiste nel riequilibrare periodicamente la memoria, ma viene discusso anche un approccio più semplice.

  • 01:00:00 In questa sezione, il video illustra come modificare l'allocatore di memoria per ottenere il comportamento desiderato di avere ogni thread che accede al proprio heap senza la necessità di un heap globale. Un approccio consiste nell'etichettare ogni oggetto con un proprietario e restituirlo all'heap del proprietario quando viene liberato. In questo modo, gli oggetti locali ottengono un'allocazione e una liberazione rapide, mentre gli oggetti remoti richiedono una certa sincronizzazione, ma non tanto quanto con un heap globale. La quantità massima di memoria che può essere allocata è limitata da X, la quantità utilizzata dal programma sequenziale, e il rapporto di espansione è limitato superiore da P, il numero di heap. Questo approccio ha anche resilienza alla falsa condivisione, che si verifica quando più processori accedono a diverse posizioni di memoria ma sulla stessa linea di cache.

  • 01:05:00 In questa sezione, l'oratore discute di come l'allocazione di heap parallela possa portare a false condivisioni e introduce l'allocatore di hoard come soluzione. L'allocatore di hoard utilizza una combinazione di heap locali e globali, organizzando la memoria in grandi super blocchi che possono essere spostati tra gli heap. Questo approccio è veloce, scalabile e resiliente alla falsa condivisione. Quando viene effettuata un'allocazione, l'allocatore cerca un oggetto libero nell'heap locale e lo ottiene se ne esiste uno. In caso contrario, passa all'heap globale per ottenere più memoria.

  • 01:10:00 In questa sezione, l'oratore spiega come l'allocatore Orda riduca la frammentazione esterna allocando un oggetto libero dal super blocco non completo più completo per densificare il movimento dei super blocchi. Se l'oggetto non viene trovato nell'heap locale, controlla l'heap globale e, se l'heap globale è vuoto, chiama un nuovo superblocco dal sistema operativo. L'allocatore Horde mantiene un invariante in cui l'heap è al massimo utilizzato per metà e, se rileva che l'heap è sottoutilizzato, sposta un superblocco semivuoto nell'heap globale. L'oratore presenta quindi un lemma affermando che la memoria massima allocata nell'heap globale è al massimo la memoria massima allocata negli heap locali. Infine, l'oratore dimostra il teorema secondo cui l'impronta dell'allocatore Horde è superiore all'ordine u più SP, dove u è l'impronta dell'utente per il programma e SP è la memoria allocata ma inutilizzata negli heap locali. L'esplosione viene quindi calcolata come uno più l'ordine SP diviso per u.

  • 01:15:00 In questa sezione, l'oratore discute diversi allocatori tra cui Je malloc e Super malloc. Je malloc ha blocchi globali separati per diverse dimensioni di allocazione e rilascia pagine vuote utilizzando la consulenza em che lo rende robusto per diverse tracce di allocazione. D'altra parte, Super malloc ha pochissime righe di codice e si sta sviluppando molto velocemente. L'oratore condivide i risultati del benchmark in cui Super malloc ha funzionato meglio di J malloc, che ha funzionato meglio di Horde, mentre l'allocatore predefinito ha avuto prestazioni scadenti. Il discorso si estende anche alla raccolta dei rifiuti, ma il relatore rimanda i dettagli di questo alle slide online.
 

Lezione 13. Il sistema Cilk Runtime



Lezione 13. Il sistema Cilk Runtime

Il sistema di runtime Cilk è responsabile della pianificazione e del bilanciamento del carico dei calcoli sui processori paralleli, utilizzando uno scheduler di furto di lavoro casuale per mappare i calcoli sui processori in fase di esecuzione. Il sistema è progettato per ottimizzare l'esecuzione seriale del programma anche a discapito di costi aggiuntivi ai furti. Il lavoratore mantiene una struttura di dati del mazzo separata che contiene i puntatori ai frame dello stack e utilizza i puntatori di testa e coda. I frame disponibili per il furto hanno una struttura locale aggiuntiva che contiene le informazioni necessarie affinché il furto avvenga mentre il mazzo è esterno allo stack di chiamate. La sezione spiega come il sistema consente ai processori di iniziare l'esecuzione dal mezzo di una funzione in esecuzione e come la sincronizzazione tra processori diventa complicata quando si raggiunge un'istruzione di sincronizzazione che non può essere eseguita oltre il punto perché processori specifici stanno ancora aspettando il completamento dei calcoli. Inoltre, il relatore affronta le prestazioni del sistema, le considerazioni sulla progettazione e le strutture dei dati e il modo in cui il sistema ottimizza l'esecuzione utilizzando il protocollo THC, coinvolgendo due serie di protocolli, uno per il lavoratore che esegue il lavoro e uno per il ladro.

Il Cilk Runtime System utilizza un protocollo di salto in serie e salto in lungo per gestire il furto di calcoli dai mazzi di esecuzione dei processi vittima. L'astrazione Cactus Stack consente al processo del ladro di avere il proprio stack di chiamate per impedire la corruzione degli stack della vittima. Il protocollo di sincronizzazione del sistema utilizza un albero di calcoli e un Cactus Stack per garantire che la sincronizzazione avvenga solo tra calcoli nidificati all'interno di una funzione. L'albero Full Frame mantiene le relazioni padre-figlio tra i calcoli con i sotto-calcoli in sospeso per semplificare il processo di sincronizzazione. Inoltre, il sistema di runtime ottimizza il caso comune in cui la funzione corrente non ha calcoli figlio in sospeso e tutti i lavoratori sono occupati. Altre funzionalità supportate includono eccezioni C++, hyper object riduttore e alberi genealogici.

  • 00:00:00 In questa sezione, Tibi spiega il sistema di runtime Cilk, che è responsabile della pianificazione e dei calcoli di bilanciamento del carico sui processori paralleli. Il sistema di runtime utilizza uno scheduler di furto di lavoro randomizzato per mappare i calcoli sui processori in fase di runtime, garantendo un'esecuzione efficiente. Tibi osserva che il sistema di runtime Cilk è un software complesso, ma la sua magia sottostante è implementata attraverso la collaborazione del compilatore Cilk e della libreria di runtime. Inoltre, mostra lo pseudocodice per un semplice programma Cilk dopo la compilazione, che evidenzia il complesso processo alla base del sistema di runtime di Cilk.

  • 00:05:00 In questa sezione, il relatore spiega le funzionalità richieste per il sistema di runtime Cilk, oltre a considerazioni sulle prestazioni. Usa un esempio di routine Fibonacci parallelizzata per illustrare come il programma Cilk esegue un dag di calcolo, che si svolge dinamicamente mentre il programma viene eseguito su un processore. Tuttavia, quando si incontra l'istruzione silk spawn, viene creato un nuovo frame per fib di 3 e un altro filamento è disponibile per l'esecuzione in parallelo. Il processore inizia quindi a eseguire fib di 3 come se si trattasse di una normale chiamata di funzione. Il processo si ripete quando il puntatore dell'istruzione ritorna all'inizio della routine fib.

  • 00:10:00 In questa sezione, vediamo come più processori eseguono una routine fib in parallelo con l'aiuto del sistema di runtime Cilk. Ogni processore salta nel mezzo di una funzione in esecuzione e inizia a eseguirla, nonostante abbia registri indipendenti, il che solleva la questione di come il sistema Silk consenta ai processori di iniziare l'esecuzione dal mezzo di una funzione in esecuzione. Inoltre, la sincronizzazione tra i processori diventa complicata quando si raggiunge un'istruzione di sincronizzazione che non può essere eseguita oltre il punto perché processori specifici sono ancora in attesa del completamento dei calcoli, il che richiede una sincronizzazione a grana fine all'interno del modello annidato.

  • 00:15:00 In questa sezione, il relatore discute le considerazioni sull'implementazione del sistema di runtime Cilk. Citano tre considerazioni principali: un singolo lavoratore in grado di eseguire il programma, la capacità di saltare nel mezzo dell'esecuzione delle funzioni e riprendere da dove altri processori si erano interrotti e la sincronizzazione. Inoltre, Silk ha un'idea di una pila di cactus, che deve essere implementata correttamente per rendere disponibili e coerenti tutte le viste della pila. Infine, il sistema deve consentire il furto di lavoro consentendo ai processori di rubare i frame gli uni dagli altri.

  • 00:20:00 In questa sezione, il relatore discute le funzionalità richieste per Cilk Runtime System, che include l'esecuzione seriale, i ladri che saltano nel mezzo delle funzioni in esecuzione, sincronizzazioni per la sincronizzazione in modo granulare nidificato, uno stack di cactus per tutti i lavoratori da vedere e gestire combinazioni di frame di spawn e frame chiamati che potrebbero essere disponibili quando rubano il calcolo. La sezione passa quindi ad affrontare le prestazioni del sistema, dove abbiamo bisogno di un ampio parallelismo, T1 su T infinito dovrebbe essere molto più grande di P e vogliamo un'accelerazione lineare quando si aumenta il numero di processori per eseguire il programma. La sezione copre anche il tempo di esecuzione previsto dei processori TCP su P, che è proporzionale al lavoro del calcolo diviso per il numero di processori più qualcosa nell'ordine dell'intervallo del calcolo.

  • 00:25:00 In questa sezione, impariamo a conoscere il Cilk Runtime System e il suo scopo di mantenere un'elevata efficienza di lavoro in programmi con sufficiente parallelismo. Il Silk Runtime System si attiene al principio work first ottimizzando l'esecuzione seriale del programma anche a scapito di qualche costo aggiuntivo per gli acciai. La libreria di sistema di runtime gestisce i problemi con l'esecuzione parallela e gestisce percorsi di esecuzione più lenti quando si verificano acciai. Il lavoratore mantiene una struttura di dati del mazzo separata che contiene i puntatori ai frame dello stack e utilizza i puntatori di testa e coda. I frame disponibili per il furto hanno una struttura locale aggiuntiva che contiene le informazioni necessarie affinché il furto avvenga mentre il mazzo è esterno allo stack di chiamate.

  • 00:30:00 In questa sezione, apprendiamo la progettazione del Cilk Runtime System e le sue strutture dati di base. Il sistema genera una funzione di spawn helper per ogni calcolo, che mantiene rispettivamente una struttura worker e una struttura Silk stack frame per ciascuna istanza di una funzione di spawning e di un spawn helper. Il frame dello stack Silk RTS contiene campi come un buffer e un numero intero di flag per riepilogare lo stato del frame dello stack Silk e un puntatore a un frame dello stack Silk padre nello stack delle chiamate. La struttura worker mantiene un mazzo e un puntatore all'attuale stack frame di Silk RTS. Queste strutture di dati sono gli elementi essenziali del Cilk Runtime System su cui elabora il sistema di runtime Intel so+.

  • 00:35:00 In questa sezione, il video esplora il codice per la funzione spawn "foo" e la funzione spawn helper. Il codice per "foo" include una chiamata per inizializzare lo stack frame, impostato per uno spawn con la routine set jump, una chiamata alla funzione helper spawn "spawn bar", un blocco di codice condizionale per un sink nel Silk RTS, e chiama i frame pop e leaf per la pulizia. Il codice per lo spawn helper include una chiamata per inizializzare lo stack frame e una chiamata per staccare Silk RTS con funzioni di pulizia aggiuntive per la struttura dello stack. La routine di set up è descritta come una funzione che consente ai ladri di rubare la continuazione della funzione, prendendo come argomento un buffer per memorizzare le informazioni necessarie per riprendere la posizione della funzione.

  • 00:40:00 In questa sezione, l'oratore discute come restringere il set di registri e salvarli in un set predeterminato per una chiamata di funzione. La responsabilità del salvataggio dei registri ricade sulla funzione, ma il puntatore all'istruzione e i puntatori allo stack vengono salvati nel buffer. La sezione prosegue discutendo una funzione di spawn helper e come aggiorna le strutture dei lavoratori e gli stack frame correnti. Infine, la sezione spiega come la routine veloce di immissione del frame stabilisce un puntatore padre nello stack di chiamate e aggiorna il frame dello stack corrente del lavoratore in modo che punti in basso.

  • 00:45:00 In questa sezione, la trascrizione del video di YouTube intitolato "The Cilk Runtime System" spiega come la funzione di distacco di Silk RTS consenta il furto del calcolo, dove una volta terminata l'esecuzione di Silk Artistic, un ladro potrebbe venire a rubare la continuazione della progenie della seta. Il pop frame è responsabile della pulizia della struttura dello stack frame e dell'aggiornamento dell'attuale stack frame in modo che punti al genitore. Questa chiamata di funzione può restituire o meno e quale di questi due casi è più importante per l'ottimizzazione del sistema di runtime è il caso di successo, basato sui due principi che funzionano per primi.

  • 00:50:00 In questa sezione, l'oratore discute l'ottimizzazione del sistema di runtime Cilk sull'esecuzione dei lavoratori nel caso uno, in cui si presume che i lavoratori eseguano regolarmente l'esecuzione seriale. Spiegano anche come funziona il furto dei lavoratori, con il ladro che prende di mira la parte superiore del mazzo della vittima, rimuovendo l'oggetto dalla coda e aggiornando l'intestazione del mazzo e l'attuale puntatore dello stack frame. Il risultato della funzione generata viene restituito allo stack frame padre nel codice SIL originale.

  • 00:55:00 In questa sezione, il relatore spiega l'approccio del Cilk Runtime System nella gestione degli accessi simultanei che coinvolgono più processori utilizzando un protocollo chiamato protocollo THC. Il protocollo prevede due serie di protocolli, uno per il lavoratore che esegue il lavoro e uno per il ladro. Il protocollo del lavoratore è ottimizzato cercando di far saltare qualcosa dal fondo del mazzo, e solo in caso di fallimento acquisisce un lucchetto sul mazzo, mentre il ladro afferra sempre un lucchetto prima di eseguire qualsiasi operazione sul mazzo. Il ladro quindi riprende magicamente una continuazione rubata chiamando la funzione di salto in lungo, passando il buffer del frame dello stack recuperato dalla funzione di salto impostato e impostando il suo stato di registro in modo che sia quello della continuazione rubata.

  • 01:00:00 In questa sezione, il relatore discute l'interazione tra le chiamate di salto in serie e salto in lungo all'interno del sistema di runtime Cilk. Spiegano come, quando viene chiamata una routine di salto in lungo, essa ritorna effettivamente dal salto impostato una seconda volta, questa volta con un valore diverso specificato nel secondo argomento. Usando il buffer appropriato e il secondo argomento, il ladro può eseguire un salto in lungo per saltare un certo calcolo nel codice della vittima. Il relatore osserva che è possibile calcolare staticamente la distanza necessaria per superare una chiamata e utilizzare un approccio diverso, ma il protocollo di salto impostato e salto in lungo funge da metodo più flessibile per il sistema di runtime Cilk. Nel complesso, il relatore evidenzia le varie tecniche disponibili per il ladro per rubare i calcoli dal mazzo della vittima usando Cilk.

  • 01:05:00 In questa sezione viene discussa la necessità di un'astrazione dello stack cactus per il sistema di runtime Cilk. Viene spiegato che l'utilizzo dello stack della vittima può portare alla corruzione dello stack della vittima e causare problemi con il mantenimento della coerenza tra tutti i lavoratori. Pertanto, è necessario uno stack di chiamate separato per il ladro. L'implementazione dello stack cactus prevede che il ladro rubi la continuazione e imposti il puntatore dello stack sul proprio stack pur essendo ancora in grado di accedere allo stato della funzione sullo stack della vittima tramite offset da RB p.

  • 01:10:00 In questa sezione, il relatore spiega come il sistema di runtime SIL gestisce la sincronizzazione del calcolo su diversi processori. Il sistema utilizza lo stack di cactus e un albero di calcoli per garantire che la sincronizzazione avvenga solo tra sottocalcoli nidificati in una funzione, non nel programma in generale. Quando un lavoratore raggiunge un'istruzione di sincronizzazione della seta prima che vengano restituiti tutti i calcoli secondari, diventa un ladro e continua a lavorare sullo stack frame di un calcolo rubato. Ciò consente al sistema di evitare lo spreco di lavoratori e di garantire che i calcoli nidificati siano sincronizzati correttamente. Il sistema indica specificamente al compilatore di non utilizzare un'ottimizzazione che potrebbe entrare in conflitto con questo approccio.

  • 01:15:00 In questa sezione, il Cilk Runtime System è descritto come mantenere un albero di stati chiamato frame completi, che tiene traccia di quali calcoli sono in attesa su quali altri calcoli finiscono. Questo sistema utilizza un albero di frame completo per tenere traccia di un sacco di informazioni per l'esecuzione parallela, inclusi i puntatori ai frame principali, potenzialmente ai frame secondari e al modo in cui i calcoli secondari in sospeso si relazionano tra loro. Quando un lavoratore incontra una sincronizzazione, se ha un calcolo figlio in sospeso, non può sincronizzarsi e deve sospendere l'intero frame fino a quando non può diventare un ladro per rubare altro lavoro. Questo sistema consente a un programma di avere un ampio parallelismo e semplifica i protocolli di sincronizzazione.

  • 01:20:00 In questa sezione, il relatore discute di come Cilk Runtime System ottimizzi il caso comune in cui la funzione di esecuzione non ha figli in sospeso e tutti i lavoratori sul sistema sono impegnati con le proprie attività. Il sistema di runtime utilizza i bit dal campo flag di un frame dello stack associato per valutare se la sincronizzazione è necessaria per una sincronizzazione di seta. L'oratore cita anche molte altre funzionalità supportate dal sistema di runtime, incluse eccezioni C++, oggetti hyper riduttore e pedigree.
 

Lezione 14. Caching e algoritmi Cache-Efficient



Lezione 14. Caching e algoritmi Cache-Efficient

Nel video sulla memorizzazione nella cache e sugli algoritmi efficienti nella cache, l'istruttore spiega la gerarchia della cache delle macchine moderne, le differenze tra cache completamente associative e cache mappate dirette e i vantaggi e gli svantaggi delle cache set associative. Il video introduce anche il modello di cache ideale e il concetto di algoritmi efficienti per la cache. L'oratore discute il lemma cache miss, il presupposto della cache alta e il lemma della cache sub-matrice. Analizzano anche i cache miss verificatisi durante la lettura di una sottomatrice e durante la moltiplicazione di matrici. Il video si conclude introducendo il concetto di moltiplicazione di matrici affiancate e come può migliorare significativamente le prestazioni, ma rileva anche che non è portabile e può essere costoso da ottimizzare per più livelli di cache.

La lezione copre la memorizzazione nella cache e gli algoritmi efficienti nella cache, utilizzando come esempio la moltiplicazione ricorsiva di matrici. Il relatore sottolinea l'importanza di analizzare separatamente sia il lavoro che i cache miss e osserva che gli algoritmi che riconoscono la cache potrebbero non essere ottimali per tutte le macchine a causa delle diverse dimensioni della cache. L'oratore discute anche degli algoritmi che ignorano la cache che si sintonizzano automaticamente per qualsiasi dimensione della cache e menziona gli sviluppi nel codice parallelo che ignora la cache. Infine, l'obiettivo è progettare algoritmi che siano o cache-aware o cache-oblio, e la discussione sulla progettazione di algoritmi cache-oblio continuerà nella lezione seguente.

  • 00:00:00 In questa sezione sulla memorizzazione nella cache e sugli algoritmi efficienti nella cache, l'istruttore discute la gerarchia della cache delle macchine moderne, che include cache di dati e istruzioni L1 private per ciascun processore, una cache L2 privata e una cache di ultimo livello che è condiviso tra tutti i processori. Le dimensioni di queste cache aumentano man mano che si sale nella gerarchia della memoria, con la DRAM che è la più lenta e la più grande. Anche l'associatività della cache e la latenza aumentano man mano che si sale nella gerarchia della memoria, con la cache L1 che è la più veloce e la più associativa. L'istruttore menziona anche l'importanza dei protocolli di coerenza della cache per garantire la coerenza negli accessi agli indirizzi di memoria per l'elaborazione parallela. Capire come sfruttare la località nei programmi può aiutare a fare un uso efficiente delle cache di memoria più veloci.

  • 00:05:00 In questa sezione vengono discusse le differenze tra le cache completamente associative e quelle mappate direttamente. Una cache completamente associativa richiede la ricerca nell'intera cache per trovare un blocco che può essere lento e inefficiente poiché la ricerca di un blocco può richiedere l'accesso a più righe. La cache mappata diretta, d'altra parte, ha solo una posizione possibile per ogni blocco, il che rende l'accesso ai blocchi molto più veloce, con meno conflitti. I tre componenti dello spazio degli indirizzi, l'offset, il set e il tag vengono spiegati anche quando si divide l'indirizzo della memoria virtuale per determinare la posizione del blocco della cache. Il tag identifica a quale blocco di memoria corrisponde il blocco della cache e l'insieme determina in quale posizione nella cache va il blocco, con uno spazio di indirizzi totale di W bit.

  • 00:10:00 In questa sezione, il video discute i vantaggi e gli svantaggi delle cache mappate dirette, che sono veloci perché è necessario cercare solo una posizione nella cache, ma sono soggette a conflitti mancanti in cui i blocchi della cache continuano a sfrattare l'un l'altro, riducendo le prestazioni. Il video introduce quindi le cache associative di set, una soluzione ibrida in cui ogni set contiene più righe, consentendo più di una possibile posizione nella cache per ogni blocco di cache. Il video menziona anche una tassonomia di diversi tipi di cache miss, inclusi i cold miss che si verificano la prima volta che si accede a un blocco della cache e che non possono essere evitati.

  • 00:15:00 In questa sezione, il video discute diversi tipi di errori nella cache, inclusi errori di capacità, errori di conflitto e errori di condivisione. I problemi di capacità si verificano quando la cache è piena e non può contenere tutti i blocchi della cache a cui è necessario accedere, mentre i problemi di conflitto si verificano nelle cache associative impostate quando troppi blocchi dallo stesso set mappano alla cache. Infine, gli errori di condivisione si verificano in un contesto parallelo quando più processori accedono alla stessa linea di cache e almeno uno di loro sta scrivendo su di essa. Il video fornisce anche un esempio di un cattivo caso di conflitti mancati quando si accede a una sottomatrice all'interno di una matrice più grande memorizzata nell'ordine maggiore di riga.

  • 00:20:00 In questa sezione, il relatore discute la memorizzazione nella cache e gli algoritmi efficienti nella cache. Usano un esempio di accesso a una sottomatrice all'interno di una matrice più grande e di come possono verificarsi conflitti mancanti quando la cache è solo associativa a 4 vie. L'oratore suggerisce di aggiungere una quantità costante di spazio alla fine di ogni riga nella matrice, quindi ogni riga è più lunga di 2 ^ 15 byte, il che può aiutare a ridurre i conflitti mancati.

  • 00:25:00 In questa sezione, il relatore discute il modello di cache ideale che è un modello utilizzato per analizzare le prestazioni della cache degli algoritmi. Questo modello presuppone una gerarchia di cache a due livelli, una cache completamente associativa e una politica di sostituzione Nishant ottimale. Il relatore spiega che le due misure di performance che contano sono l'ordine di N e il numero di cache miss, dove lo scenario ideale è avere un basso numero di cache miss senza aumentare il lavoro del tradizionale algoritmo standard. Viene anche menzionato il lemma LRU, dimostrato nel 1985, che afferma che un algoritmo che incorre in Q cache miss su una cache ideale di dimensione M incorrerà in 2 Q cache miss su una cache completamente associativa di dimensione 2M che utilizza la politica LRU.

  • 00:30:00 In questa sezione, il relatore introduce il concetto di algoritmi efficienti per la cache e come possono migliorare le prestazioni del programma riducendo al minimo il numero di cache miss. Spiega la politica di sostituzione meno utilizzata di recente (LRU), che afferma che una cache completamente associativa di dimensioni doppie rispetto alla cache ideale che utilizza LRU non incorrerà in più del doppio del numero di cache miss. Ciò consente un'analisi più semplice dei cache miss durante l'esecuzione dell'analisi asintotica. Il relatore presenta anche un lemma cache miss, affermando che se un programma legge un insieme di segmenti di dati la cui dimensione è inferiore a un terzo della dimensione della cache e la cui dimensione media è almeno la dimensione di una riga della cache, allora il numero di cache miss per leggerli tutti è al massimo tre volte la dimensione totale dei segmenti divisa per la dimensione di una riga della cache.

  • 00:35:00 In questa sezione, il video discute due presupposti relativi al caching: il lemma cache miss e il presupposto tall cache. Il lemma cache miss afferma che se la lunghezza media dei segmenti di dati è maggiore della dimensione del blocco della cache, aumenta il numero di cache miss solo di un fattore costante. Il presupposto della cache alta presuppone che la cache sia più alta che larga e di solito è soddisfatta nella pratica. Il video spiega anche il lemma della cache della sottomatrice, che discute il problema con le cache corte nell'adattare le sottomatrici nelle righe della cache e perché l'ipotesi della cache alta è utile per risolvere questo problema.

  • 00:40:00 In questa sezione, il relatore discute la memorizzazione nella cache e gli algoritmi efficienti nella cache. Analizzano il numero di cache miss verificatisi durante la lettura di una sottomatrice quadrata nella cache e utilizzano il lemma cache miss per mostrare che il numero di cache miss richiesti per leggere tutti gli elementi della matrice nella cache è al massimo 3n^2/B . Quindi analizzano il numero di mancanze nella cache sostenute nell'algoritmo di moltiplicazione della matrice di lavoro cubico standard, assumendo che la matrice sia in ordine maggiore di riga e soddisfino l'ipotesi di cache alta. Considerano tre casi e assumono LRU per il secondo e il terzo caso, dimostrando infine l'importanza dell'ottimizzazione della cache nella progettazione dell'algoritmo.

  • 00:45:00 In questa sezione, il relatore discute la memorizzazione nella cache e gli algoritmi efficienti nella cache. Analizzano due casi per la moltiplicazione di matrici, dove n è maggiore di M su B e quando n è minore di C moltiplicato M su B. Usano una politica di sostituzione LRU e calcolano il numero di cache miss verificatesi durante l'accesso alla matrice B. Nel primo caso, scoprono di aver bisogno di theta di n cache miss al cubo, il che non comporta alcun vantaggio dall'avere località nell'algoritmo. Nel secondo caso, possono sfruttare la località spaziale e ridurre il numero di cache miss di un fattore B, risultando in theta di n al cubo rispetto a B cache miss, che è più efficiente.

  • 00:50:00 In questa sezione del video, l'oratore discute di cache e algoritmi efficienti per la cache. Prima analizzano il caso in cui l'intera matrice si inserisce nella cache, risultando in un numero totale di cache miss di theta di n^2 su B. Quindi discutono un'ottimizzazione scambiando l'ordine dei due loop interni per beneficiare della località spaziale e ridurre il numero totale di cache miss a theta di n al cubo su B. Tuttavia, notano che è possibile fare di meglio utilizzando un'ottimizzazione chiamata tiling, in cui vengono utilizzati sei cicli for per eseguire il loop su tile e il calcolo viene eseguito per ogni sottotitolo -matrix prima di passare alla successiva. Il lavoro per una sottomatrice di dimensione s per s è quindi s cubo.

  • 00:55:00 In questa sezione viene introdotto e discusso in dettaglio il concetto di moltiplicazione di matrici affiancate. L'obiettivo di questo algoritmo è inserire le sottomatrici nella cache in modo che tutti i calcoli possano essere eseguiti nella cache senza più cache miss. Viene analizzato il numero di cache miss e si scopre che il numero di cache miss è n/s^3 volte s^2 /B, per un totale di n^3/B * sqrt(M) cache miss. Questo numero è molto significativo nel migliorare le prestazioni del codice di moltiplicazione di matrici. Tuttavia, sorge un problema con l'algoritmo: non è portabile in quanto dipende fortemente dalla dimensione della cache della macchina su cui viene eseguito. Inoltre, l'ottimizzazione dell'ottimizzazione multidimensionale diventa molto più costosa e il codice diventa più disordinato durante l'ottimizzazione per più livelli di cache.

  • 01:00:00 In questa sezione, la lezione esplora la memorizzazione nella cache e gli algoritmi efficienti nella cache. Il relatore discute le sfide della messa a punto dei parametri per un algoritmo efficiente nella cache e dell'ottimizzazione per una particolare macchina. Introducono un algoritmo di moltiplicazione di matrici ricorsive in cui le matrici di input sono divise in quattro sottomatrici o quadranti. Per ogni quadrante della matrice di output, si verifica ricorsivamente una somma di due moltiplicazioni di matrice. Infine, il relatore analizza il lavoro di questo algoritmo e conclude che si tratta di un design più semplice che mantiene comunque buone prestazioni della cache.

  • 01:05:00 In questa sezione, il relatore discute la memorizzazione nella cache e gli algoritmi efficienti nella cache e utilizza l'esempio della moltiplicazione di matrici per spiegare la differenza tra l'analisi del lavoro e gli errori nella cache. Il relatore disegna un albero di ricorsione per visualizzare il problema della dimensione e dei sottoproblemi di ramificazione, e osserva che il numero di livelli fino alle foglie è logaritmico in base 2 di n. Il numero di foglie è calcolato come otto per logaritmo in base 2 di n, che è uguale a n cubo. La quantità di lavoro è semplicemente theta n al cubo e i cache miss vengono analizzati con un caso base diverso, in cui la sottomatrice si adatta alla cache e viene utilizzato il theta di N al quadrato sui cache miss. Il relatore sottolinea che il numero di livelli non è solo logaritmo in base 2 di n, ma dipende anche dalla dimensione della cache, risultando in un numero diverso di foglie, theta di n cubo su m alle tre metà.

  • 01:10:00 In questa sezione, il relatore spiega come analizzare il numero di cache miss in un algoritmo cache-efficient usando l'esempio di un codice di moltiplicazione di matrice ricorsivo. Il codice è ignaro della cache, il che significa che non ha alcuna conoscenza esplicita delle cache e si auto-sintonizza passivamente per la particolare dimensione della cache della macchina su cui è in esecuzione. L'oratore menziona anche che i migliori codici ignari della cache oggi funzionano su matrici rettangolari arbitrarie ed eseguono la divisione binaria invece della divisione a otto vie. Il relatore discute il contesto parallelo e spiega come analizzare il numero di cache miss in un calcolo di cella deterministico eseguito su più processori con cache private.

  • 01:15:00 In questa sezione, il relatore discute il caching e gli algoritmi efficienti per la cache. Riducendo al minimo i cache miss nell'illusione seriale, possiamo essenzialmente minimizzarli nell'esecuzione parallela per algoritmi a bassa portata. L'oratore fornisce un cache miss bound per un algoritmo di moltiplicazione di matrici ricorsive parallele, che è lo stesso dell'esecuzione seriale. L'obiettivo è progettare algoritmi che abbiano una conoscenza esplicita della cache o ne siano ignari. Il relatore fornisce esempi di entrambi e menziona che ci sarà un'ulteriore discussione sulla progettazione di algoritmi ignari della cache nella lezione seguente.
 

Lezione 15. Cache-Oblivious Algorithms



Lezione 15. Cache-Oblivious Algorithms

Il video discute gli algoritmi che ignorano la cache, che possono ottimizzare automaticamente le dimensioni della cache su una macchina, ottenere una buona efficienza della cache e non richiedere la conoscenza dei parametri della cache della macchina. Il video mostra come scrivere codice per simulare la diffusione del calore attraverso equazioni differenziali utilizzando il metodo stencil su una matrice 2D. Il codice ha entrambe le versioni in loop e trapezoidale, con quest'ultima più efficiente nella cache ma non significativamente più veloce in una simulazione 2D a causa della prevedibilità del modello di accesso del codice in loop. Il video discute anche l'interazione tra memorizzazione nella cache e parallelismo e la diagnosi di potenziali colli di bottiglia nell'accelerazione parallela. Infine, il relatore spiega i calcoli dello stencil e come ogni punto in un array viene aggiornato utilizzando uno schema fisso chiamato stencil, che può soffrire di cache miss e ha requisiti di archiviazione che possono essere ridotti utilizzando algoritmi efficienti che sfruttano la località temporale e spaziale.

La seconda parte del video discute gli algoritmi che ignorano la cache per l'ordinamento e l'unione. Nello specifico, il video illustra la complessità della cache del merge sort, introduce il concetto di unione a più vie e spiega la complessità della cache dell'algoritmo di unione a più vie. Il video discute anche dell'algoritmo di ordinamento dell'imbuto, che è un algoritmo di ordinamento ignaro della cache che può unire elementi K quadrati e elenchi ordinati K. L'algoritmo di ordinamento dell'imbuto è ottimale e costruito in modo ricorsivo con la radice quadrata di K imbuti. Il video spiega che esistono molti altri algoritmi e strutture di dati ignari della cache, come b-tree, manutenzione ordinata dei file e code di priorità. Nel complesso, il video fornisce un'introduzione agli algoritmi che ignorano la cache per coloro che sono interessati a saperne di più sull'argomento.

  • 00:00:00 In questa sezione, il video discute gli algoritmi cache-oblio, che sono un algoritmo che ottimizza automaticamente le dimensioni della cache su una macchina e raggiunge una buona efficienza della cache, senza che il codice debba conoscere i parametri della cache di la macchina. Il video utilizza l'esempio della simulazione della diffusione del calore attraverso equazioni differenziali per mostrare come il calcolo scientifico si basi spesso su equazioni differenziali per descrivere i processi fisici e quindi debba scrivere un codice efficiente per simulare il processo. Il video mostra come scrivere codice basato sul metodo di approssimazione alle differenze finite per simulare l'equazione del calore 1D.

  • 00:05:00 In questa sezione, il relatore illustra come scrivere codice per un'equazione di simulazione che consente l'approssimazione alle differenze finite utilizzando il metodo stencil. L'equazione utilizza le derivate parziali di U rispetto a T e X, e il relatore mostra come ottenere queste derivate parziali utilizzando metodi di approssimazione. Lo spazio 2D è rappresentato utilizzando una matrice con i valori X e T rappresentati rispettivamente orizzontalmente e verticalmente. L'oratore spiega i limiti della matrice e calcola U utilizzando l'equazione.

  • 00:10:00 In questa sezione, il presentatore spiega i calcoli con stencil, un metodo ampiamente utilizzato nel calcolo scientifico per vari scopi. In questo metodo, ogni punto in un array viene aggiornato utilizzando uno schema fisso chiamato stencil. Il calcolo dipende da altri tre valori, e questo è noto come posizione a tre punti. Sebbene i calcoli dello stencil possano essere utilizzati per valori X elevati, le prestazioni potrebbero risentirne in merito alla memorizzazione nella cache, con conseguenti errori nella cache. Inoltre, la memoria richiesta per memorizzare i dati può essere ridotta memorizzando solo due righe, quella corrente e quella precedente, per aggiornare i valori dei punti.

  • 00:15:00 funziona: in ogni fase temporale, aggiorniamo solo i valori di X per una riga specifica utilizzando i valori della riga precedente. Quindi, possiamo alternare quale riga stiamo aggiornando e quale riga stiamo usando come riga precedente, e dobbiamo solo mantenere una riga extra di valori. Tuttavia, questo codice non è molto efficiente nella cache e possiamo renderlo ancora più efficiente utilizzando algoritmi di tiling o cache ignari. Il modello di cache ideale presuppone una cache completamente associativa con una politica di sostituzione ottimale o LRU e acquisisce mancanze di capacità ma non mancate di conflitto in un'esecuzione seriale. Tuttavia, è ancora utile per progettare algoritmi efficienti che sfruttano la località temporale e spaziale.

  • 00:20:00 In questa sezione, il relatore spiega come utilizzare un algoritmo cache-oblio per calcolare i punti all'interno di uno spazio trapezoidale in una matrice 2D senza guardare al di fuori di esso. Il calcolo implica una funzione del kernel che porta un puntatore a UT mod su X e restituisce W di 0 più alfa volte W di negativo 1 meno 2 volte W di 0 più W di 1. Il comportamento della memorizzazione nella cache viene analizzato assumendo la politica di sostituzione LRU e il il numero di cache miss è Theta di NT su B per ogni riga. Tuttavia, il relatore osserva che è possibile ottenere prestazioni migliori con l'affiancamento, ma procedono con la discussione della versione ignara della cache. Il trapezio ha una base superiore in T1 e una base inferiore in T0. L'algoritmo calcola tutti i punti all'interno del trapezio utilizzando condizioni di disuguaglianza che coinvolgono T, t0, t1, X, x0, x1, DX0, DX1, dove DX0 e DX1 sono -1, 0 o 1 che rappresentano le pendenze.

  • 00:25:00 In questa sezione, il relatore descrive un approccio divide et impera per l'algoritmo della regola del trapezio. L'approccio ha un caso base in cui l'altezza del trapezio è 1 e un ciclo calcola tutti i valori in base all'ordine di calcolo. L'algoritmo ha due casi ricorsivi, vale a dire il taglio spaziale e il taglio temporale, che dipendono rispettivamente dalla larghezza e dall'altezza del trapezio. Quando il trapezio è troppo largo, viene applicato un taglio spaziale in cui il trapezio viene tagliato verticalmente con una linea con pendenza uno negativo che attraversa il centro del trapezio. Al contrario, un taglio temporale viene applicato quando il trapezio è troppo alto e viene tagliato con una linea orizzontale che attraversa il centro. L'algoritmo ricorsivo effettua due chiamate che attraversano rispettivamente i lati sinistro e destro e inferiore e superiore del trapezio, in un ordine specifico per impedire l'interdipendenza tra i punti.

  • 00:30:00 In questa sezione, il relatore discute la complessità della cache degli algoritmi cache-oblio. Analizzano l'approccio dell'albero di ricorsione e scoprono che l'algoritmo si divide in due sottoproblemi a ciascun livello fino a raggiungere il caso base, che rappresenta il theta dei punti HW dove H è Theta di W. Il numero di cache miss per foglia è theta W su B, e il numero di foglie è Theta di NT su HW. I nodi interni non contribuiscono sostanzialmente alla complessità della cache. La complessità della cache si generalizza a più di una dimensione e, se d è uno, risulta in NT su MB.

  • 00:35:00 In questa sezione, l'oratore spiega la differenza tra il codice looping e il codice trapezoidale, che ha una complessità della cache molto migliore salvando un fattore M dove M è il numero di righe della cache. La simulazione dimostra che il codice trapezoidale incorre in meno cache miss rispetto al codice in loop, terminando così il calcolo molto più velocemente. Tuttavia, il relatore nota che questa simulazione era solo per una dimensione e prosegue mostrando una demo di ciò che accade in due dimensioni.

  • 00:40:00 In questa sezione, il presentatore dimostra una simulazione in tempo reale della diffusione del calore in uno spazio 2D, dove i colori sullo schermo corrispondono alle temperature. Il presentatore confronta le prestazioni del codice in loop e del codice trapezoidale e rivela che, sebbene il codice trapezoidale subisca molti meno cache miss, è solo marginalmente più veloce del codice in loop. Si suggerisce che ciò potrebbe essere dovuto al precaricamento hardware che aiuta il codice in loop, poiché il suo modello di accesso è regolare e facile da prevedere.

  • 00:45:00 In questa sezione, l'oratore discute l'interazione tra cache e parallelismo. Spiegano un teorema che afferma che minimizzare i cache miss nell'esecuzione seriale può essenzialmente minimizzarli nell'esecuzione parallela assumendo un algoritmo a bassa portata. Quindi dimostrano come l'algoritmo trapezoidale può funzionare in parallelo utilizzando un taglio a V, in cui due trapezi indipendenti vengono eseguiti in parallelo e il trapezio grigio viene eseguito successivamente. Menzionano anche il taglio a V rovesciato utilizzato per i trapezi rovesciati.

  • 00:50:00 In questa sezione, l'oratore discute le prestazioni del codice a looping parallelo e del codice trapezoidale parallelo rispetto alle loro controparti seriali. Il codice di looping parallelo raggiunge meno della metà della potenziale accelerazione nonostante abbia un potenziale parallelismo maggiore rispetto al codice trapezoidale. Questo perché, nel caso parallelo, c'è un collo di bottiglia della larghezza di banda della memoria, che impedisce al precaricamento di aiutare il codice del looping parallelo, rispetto al caso seriale in cui c'è molta larghezza di banda della memoria. Al contrario, il codice trapezoidale raggiunge una velocità quasi lineare, il che è coerente con il fatto che l'efficienza della cache gioca un ruolo molto più importante in dimensioni di input maggiori in cui la cache è così piccola rispetto alla dimensione dell'input.

  • 00:55:00 In questa sezione, il relatore discute come diagnosticare un collo di bottiglia di accelerazione parallela e identifica diverse cose che potrebbero causarlo, come parallelismo insufficiente, sovraccarico di pianificazione, mancanza di larghezza di banda della memoria e contesa. Suggeriscono diversi modi per diagnosticare questi problemi, incluso l'utilizzo di Silk Scale per misurare il parallelismo nel codice e l'esecuzione di contatori hardware per misurare la larghezza di banda della memoria. Tuttavia, la diagnosi della contesa è particolarmente impegnativa e l'oratore consiglia di esaminare le prime tre potenziali cause prima di valutare se la contesa è il problema. Infine, l'oratore passa a discutere il calcolo dello stencil.

  • 01:00:00 In questa sezione, il relatore discute l'analisi della complessità della cache di merge sort analizzando prima la complessità dell'unione di due array di input ordinati. Il tempo necessario per eseguire questa operazione è proporzionale alla somma delle dimensioni degli array di input. Il numero di mancati riscontri nella cache durante l'unione di n elementi è theta n su B, dove B è il numero di byte in una riga della cache. Merge sort ha due chiamate ricorsive su input di dimensioni dimezzate e unisce gli output ordinati delle sue chiamate ricorsive. Il lavoro complessivo di merge sort è theta di n log n, che viene analizzato utilizzando il metodo dell'albero di ricorsione. Viene anche discussa la complessità della cache di Merge Sort e viene mostrato che il numero di cache miss è proporzionale al numero di blocchi di cache necessari per memorizzare i dati, che è theta n su B log M, dove M è la dimensione massima a il sottoblocco può avere.

  • 01:05:00 In questa sezione, l'oratore spiega la ricorrenza della complessità della cache del merge sort. Il caso base si verifica quando la dimensione del problema rientra nella cache, incorrendo in Θ(n/B) cache miss. Altrimenti, l'algoritmo ha due chiamate ricorsive di dimensione n/2 e Θ(n/B) cache miss per unire i risultati. L'analisi coinvolge il numero di livelli di un albero di ricorsione, che è logaritmo in base 2 di n/CM, dove CM è una costante. Il numero di cache miss per foglia è Θ(M/B * n/CM), fornendo un numero complessivo di cache miss di Θ(n/B * log (n/CM)), risparmiando un fattore di B nel primo termine . Tuttavia, per problemi di dimensioni maggiori, risparmiamo solo un fattore B rispetto al lavoro, mentre risparmiamo un fattore B log n per problemi di dimensioni ridotte. L'oratore chiede se esiste una soluzione migliore e la risposta è sempre sì.

  • 01:10:00 In questa sezione, il relatore spiega come utilizzare l'unione a più vie per unire sottoarray ordinati e introduce l'idea di un albero del torneo per determinare gli elementi minimi dei sottoarray. Spiegano anche il lavoro e le complessità della cache di questo approccio, che viene utilizzato negli algoritmi ignari della cache per l'ordinamento. La complessità del lavoro del multi-way merge è la stessa del binary merge sort, mentre la complessità della cache è determinata dal numero di cache miss richiesti per riempire l'albero del torneo e accedere agli array di input, che possono essere ottimizzati se R è minore di C*M/B per una piccola costante C.

  • 01:15:00 In questa sezione, il relatore discute la complessità della cache dell'algoritmo di Merge Sort a più vie e lo confronta con l'algoritmo di Merge Sort binario. L'algoritmo multi-way merge sort prevede la divisione del problema in sottoproblemi di dimensione n/R e il pagamento di n/B cache miss per unirli. Il numero di livelli dell'albero di ricorsione è log in base R di n/cm e la dimensione della foglia è cm. L'oratore imposta R uguale a theta di M/B, rendendolo il più grande possibile, e analizza la complessità della cache, che risulta essere theta n log n diviso per B log M. Rispetto all'algoritmo di unione binaria, il multi -way merge sort l'algoritmo salva un fattore di log M nei cache miss. Tuttavia, l'algoritmo non è ignaro della cache e il valore di R deve essere ottimizzato per una particolare macchina, il che può essere un problema se sono in esecuzione altri lavori che competono per la cache.

  • 01:20:00 In questa sezione, l'oratore discute l'algoritmo di ordinamento a imbuto, che è un algoritmo di ordinamento che non tiene conto della cache e che può unire K quadrati di elementi e K elenchi ordinati. Il costo di questa unione risulta essere lo stesso dell'algoritmo di ordinamento di unione a più vie, ma l'algoritmo di ordinamento a imbuto ignora la cache e il suo limite è ottimale. Il relatore presenta un'immagine di come appare un imbuto K e spiega che l'algoritmo è costruito in modo ricorsivo con la radice quadrata di imbuti K che alimentano gli elementi ai buffer, che, a loro volta, alimentano gli elementi alla radice quadrata di output finale dell'imbuto K, producendo l'output per l'imbuto K. L'oratore menziona anche che ci sono molti altri algoritmi e strutture di dati ignari della cache, come b-tree, manutenzione ordinata dei file e code prioritarie, e invita gli spettatori a saperne di più online.
 

Lezione 16. Programmazione parallela non deterministica



Lezione 16. Programmazione parallela non deterministica

Questo video discute vari concetti relativi alla programmazione parallela deterministica e non deterministica. Il relatore sottolinea l'importanza di evitare il non determinismo in quanto può portare a comportamenti anomali e difficoltà di debug. Le strategie per la gestione del non determinismo includono l'utilizzo di valori fissi, riproduzione di record, strumenti di analisi, incapsulamento e unit test. L'uso dei mutex viene esplorato in dettaglio, tra cui la rotazione rispetto al rendimento, il rientro rispetto al non rientro e l'equità rispetto all'ingiusto. Il relatore tocca anche il concetto di cambio di contesto e il "problema del noleggio sci" nel contesto della programmazione parallela. Il segmento si conclude discutendo i principi di base dell'ingegneria delle prestazioni nei processori multi-core.

La seconda parte del video copre il problema del deadlock nella programmazione parallela e offre soluzioni per evitarlo, come l'ordinamento lineare dei mutex che garantisce l'assenza di cicli di attesa. Inoltre, il relatore introduce il concetto di memoria transazionale, che garantisce l'atomicità rappresentando una regione critica come una transazione che esegue il commit di tutti gli aggiornamenti contemporaneamente. Il video presenta quindi un algoritmo che utilizza un approccio basato su lock con un array di proprietà finito e un metodo release sort require per prevenire deadlock e starvation senza bisogno di un blocco globale. Infine, viene spiegato l'algoritmo release sort and reacquire, che impedisce a più blocchi di tentare di acquisire un blocco contemporaneamente, evitando problemi di prestazioni.

  • 00:00:00 In questa sezione, il docente introduce il concetto di determinismo nella programmazione e come si collega al calcolo parallelo. Un programma è deterministico se ogni locazione di memoria viene aggiornata con la stessa sequenza di valori in ogni esecuzione e il programma si comporta sempre allo stesso modo. I programmi deterministici hanno il vantaggio di essere ripetibili, rendendoli più facili da eseguire il debug. Il docente sottolinea l'importanza di non scrivere mai programmi paralleli non deterministici in quanto possono presentare comportamenti anomali difficili da eseguire il debug. Tuttavia, in pratica, può essere difficile evitare il non determinismo nel calcolo parallelo.

  • 00:05:00 In questa sezione, il relatore discute la programmazione parallela non deterministica e il fatto che a volte può portare a prestazioni migliori, ma dovrebbe comunque essere evitata a meno che non sia necessario. L'oratore consiglia di ideare una strategia di test per gestire il non determinismo se è necessario scrivere un programma in questo modo. Esempi di strategie includono la disattivazione del non determinismo, l'utilizzo dello stesso seme per numeri casuali o la fornitura di valori fissi per input di programma che potrebbero altrimenti cambiare in modo casuale. Il relatore sottolinea l'importanza di avere un modo per gestire i bug nel programma causati dal non determinismo.

  • 00:10:00 In questa sezione, il relatore parla delle strategie per gestire la programmazione non deterministica, come la riproduzione di record, l'incapsulamento del non determinismo, la sostituzione di un'alternativa deterministica, l'utilizzo di strumenti di analisi e unit test. L'oratore sottolinea l'importanza di controllare il non determinismo per migliorare le possibilità di rilevare bug nel codice. Il relatore fornisce anche un esempio di utilizzo dell'esclusione reciproca e dell'atomicità in una tabella hash per illustrare come gestire la programmazione non deterministica.

  • 00:15:00 In questa sezione, l'oratore discute di come le istruzioni parallele che accedono alla stessa posizione possono portare a race bug e distruggere l'integrità del sistema. La soluzione standard è rendere alcune istruzioni atomiche, nel senso che sono viste come completamente eseguite o non eseguite affatto dal resto del sistema. Per ottenere ciò, viene utilizzato un blocco di mutua esclusione o un blocco mutex, che è un oggetto con funzioni membro di blocco e sblocco. Ogni slot è trasformato in una struttura con un blocco mutex e un puntatore al contesto dello slot, consentendo l'utilizzo delle funzioni di blocco e sblocco prima di accedere all'elenco, garantendo così la correttezza del sistema.

  • 00:20:00 In questa sezione, il video esplora l'uso dei mutex per implementare l'atomicità e come si collega alle gare di determinazione. I blocchi mutex possono garantire che le sezioni critiche siano atomiche, ma il codice risultante non è deterministico a causa di una gara di determinazione che in alcuni casi potrebbe essere ciò che si desidera. Il video sottolinea l'importanza di comprendere la differenza tra corse di dati e gare di determinazione e osserva che la semplice eliminazione di corse di dati non significa necessariamente che non ci siano bug presenti nel codice. È importante avere un modo per rilevare il non determinismo al fine di evitare falsi positivi o errori di razza mancanti nel codice.

  • 00:25:00 In questa sezione, l'oratore spiega che non avere corse di dati non significa necessariamente che il codice non abbia bug. Sebbene nessuna corsa ai dati sia un aspetto positivo del codice, l'esempio del blocco per fornire l'atomicità può portare a una violazione dell'atomicità. Inoltre, possono verificarsi gare benigne, ad esempio quando due processi paralleli accedono allo stesso valore, il che può comportare lo stesso risultato, ma potrebbe anche portare a valori errati su alcune architetture. L'oratore sostiene che mentre alcune persone considerano innocue le razze benigne, è comunque essenziale identificarle ed evitarle.

  • 00:30:00 In questa sezione, l'oratore spiega i pericoli della programmazione non deterministica, in particolare a causa delle race condition che possono verificarsi quando più processi tentano di impostare valori nella stessa posizione. L'oratore introduce il concetto di "Silks", che consente gare intenzionali ma può essere pericoloso se non usato correttamente. La complessità delle corse può anche rendere difficile il debug e confondere gli strumenti intesi ad aiutare a rilevare il codice corretto. L'oratore discute anche di come l'implementazione dei mutex e dei loro parametri può influenzare il loro comportamento, ad esempio se stanno cedendo o ruotando.

  • 00:35:00 In questa sezione, il video spiega tre proprietà di base dei mutex nella programmazione parallela: spinning vs. yielding, reentrant vs. non-reentrant e fair vs. unfair. Il concetto di rotazione vs resa è l'idea che un thread non resterà inattivo e controllerà continuamente l'accesso a un blocco, ma piuttosto cederà il controllo al sistema operativo per un'esecuzione più efficiente. Il mutex rientrante consente a un thread che è già in possesso di un blocco di acquisirlo di nuovo mentre i blocchi non rientranti andranno in stallo se il thread tenta di riacquisire un mutex che già possiede. Infine, fair mutex assicura che il thread che ha atteso più a lungo ottenga il blocco per primo per prevenire la possibilità di un problema di fame. Il video fornisce anche un'implementazione di un semplice mutex rotante in linguaggio assembly.

  • 00:40:00 In questa sezione, il video discute l'uso del mutex nella programmazione parallela e perché viene utilizzata l'istruzione di scambio invece di ottenere solo il mutex. Si spiega che l'operazione di cambio è assimilabile ad un diritto, e per esercitare un diritto, la linea di cassa su cui si trova deve essere invalidata sulle altre e tenuta in uno stato modificato o esclusivo. Questo crea traffico sulla rete di memoria e rallenta il processo. D'altra parte, utilizzando l'istruzione di scambio, le linee della cache vengono messe in uno stato condiviso, mantenendo così il processo più veloce e generando meno traffico.

  • 00:45:00 In questa sezione, l'oratore discute la differenza tra un mutex rotante e un mutex cedevole. In uno spinning mutex, il programma continua a verificare che il mutex sia sbloccato, mentre in un yielding mutex, il programma cede il controllo al sistema operativo, che gli consente di programmare qualcos'altro. L'oratore osserva che esiste anche un altro tipo di mutex chiamato mutex competitivo, che raggiunge entrambi gli obiettivi di un mutex rotante e di un mutex cedevole. L'oratore esplora anche l'uso del passaggio di messaggi o delle interruzioni per informare i thread in attesa, ma osserva che la soluzione più semplice sarebbe quella di utilizzare un meccanismo di esclusione reciproca.

  • 00:50:00 In questa sezione, l'oratore spiega il concetto di cambio di contesto, ovvero la frequenza con cui il sistema operativo passa da un thread all'altro sui processori disponibili. In genere, il sistema esegue il cambio di contesto circa 100 volte al secondo, il che significa che ogni passaggio richiede circa 10 millisecondi. Tuttavia, questo è più di un ordine di grandezza maggiore del tempo di esecuzione di una semplice istruzione, il che significa che ci sono molte istruzioni che possono essere eseguite prima che il thread abbia la possibilità di rientrare e afferrare un blocco. Questo problema può essere risolto utilizzando una combinazione di filatura e cedimento. L'oratore chiama questo il "problema del noleggio sci" nella letteratura teorica.

  • 00:55:00 In questa sezione, il video illustra il processo per decidere se acquistare o noleggiare l'attrezzatura per una particolare attività, utilizzando l'esempio dell'acquisto o del noleggio di attrezzature sportive. L'oratore incoraggia gli spettatori a considerare i costi dell'affitto rispetto all'acquisto e suggerisce di affittare fino a quando il costo non è uguale a quello dell'acquisto, quindi effettuare l'acquisto. Il video esplora anche il concetto di tempo di cambio di contesto, tempo di accesso al disco e il problema del deadlock quando si mantengono più blocchi contemporaneamente. Nel complesso, questo segmento copre i principi di base dell'ingegneria delle prestazioni nei processori multi-core.

  • 01:00:00 In questa sezione, l'oratore spiega il deadlock, ovvero quando due thread contengono risorse che sono entrambe richieste dall'altro thread, portando a una perdita di prestazioni. Esistono tre condizioni di base per il deadlock: mutua esclusione (controllo esclusivo sulle risorse), non prelazione (risorse mantenute fino al completamento) e attesa circolare (un ciclo di thread in attesa di risorse mantenute dal successivo). La rimozione di uno qualsiasi di questi vincoli può risolvere il problema del deadlock. L'oratore utilizza "Dining Philosophers", una storia raccontata da Tony Hoare basata su una domanda d'esame di Edsger Dijkstra, per illustrare il problema con lo stallo. La storia coinvolge filosofi seduti attorno a un tavolo, che mangiano noodles con le bacchette dove ogni piatto di noodles è situato tra due bacchette e hanno bisogno di due bacchette per mangiare i noodles. I filosofi afferrano le bacchette a sinistra ea destra per mangiare i loro noodles. Tuttavia, se tutti raccolgono la bacchetta sinistra alla loro sinistra, finiranno per morire di fame.

  • 01:05:00 In questa sezione, il relatore discute il problema del deadlock nella programmazione parallela e offre una soluzione che garantisce la non prelazione evitando il deadlock: l'ordinamento lineare dei mutex. Numerando ogni mutex e bloccandoli strategicamente in base al loro ordine numerico, i programmatori possono garantire che non possa verificarsi un ciclo di attesa (la condizione necessaria per il deadlock). Tuttavia, avverte i programmatori di essere consapevoli dell'incapsulamento dei blocchi del sistema di runtime in Silk, poiché l'introduzione di ulteriore non determinismo attraverso questi blocchi può causare problemi. Condivide un esempio in cui può verificarsi un deadlock con un solo blocco, sottolineando l'importanza di un'attenta considerazione durante la progettazione di programmi paralleli.

  • 01:10:00 In questa sezione, il relatore approfondisce l'argomento della memoria transazionale, una recente tecnica a livello di ricerca che prevede transazioni di database in cui l'atomicità avviene implicitamente, senza la necessità di specificare i blocchi. Il relatore fornisce un esempio di come la memoria transazionale sia utile nel calcolo simultaneo di grafi, vale a dire l'eliminazione gaussiana, in cui l'eliminazione simultanea di due nodi provoca violazioni dell'atomicità. L'idea alla base della memoria transazionale è quella di rappresentare l'area critica come una transazione e, al momento del commit, tutti gli aggiornamenti della memoria nell'area critica appaiono come se fossero avvenuti contemporaneamente.

  • 01:15:00 n questa sezione, il relatore discute la risoluzione dei conflitti, la risoluzione dei conflitti, l'avanzamento e il throughput nella memoria transazionale. Introducono un algoritmo che utilizza un approccio basato su lock con un array di proprietà finito e un metodo release sort require per prevenire deadlock e fame senza bisogno di un blocco globale. L'algoritmo registra le letture e le scritture per consentire il rollback o il commit atomico quando una transazione viene interrotta. L'array di blocco viene utilizzato per bloccare una posizione a cui mappa una funzione hash, consentendo un'acquisizione equa dei blocchi. Questo algoritmo consente transazioni simultanee senza sacrificare le prestazioni o causare deadlock.

  • 01:20:00 In questa sezione, l'oratore discute un algoritmo chiamato release sort and reacquire. L'algoritmo funziona tentando avidamente di acquisire un blocco di una posizione di memoria e, se si verifica un conflitto, la transazione esegue il rollback senza rilasciare i blocchi che detiene. Successivamente, l'algoritmo rilascia tutti i blocchi con indici maggiori dell'indice della posizione a cui sta tentando di accedere. Acquisisce quindi il blocco desiderato e infine acquisisce i blocchi rilasciati in ordine ordinato. Questo processo viene ripetuto finché la transazione non va a buon fine. L'algoritmo è progettato per impedire a più blocchi di tentare di acquisire un blocco contemporaneamente, il che può causare problemi di prestazioni.
 

Lezione 17. Sincronizzazione senza blocchi



Lezione 17. Sincronizzazione senza blocchi

Charles Leiserson esplora il concetto di sincronizzazione senza blocchi in un video di YouTube. Fornisce un esempio che dimostra la necessità di un ordine lineare globale di istruzioni per garantire l'esecuzione sequenziale e discute come è possibile ottenere l'esclusione reciproca attraverso la coerenza sequenziale, evitando le difficoltà ei potenziali problemi dell'utilizzo dei blocchi. Leiserson presenta l'algoritmo di Peterson come una soluzione che utilizza solo operazioni di caricamento e archiviazione per accedere a sezioni critiche senza interferenze da parte di processi concorrenti. Il video copre anche le sfide della sincronizzazione attraverso la memoria dovute al riordino dell'hardware e il concetto di recinti di memoria per mantenere l'ordine relativo con altre istruzioni. Leiserson sostiene che il supporto della coerenza sequenziale per macchine parallele è vantaggioso ma difficile da ottenere per i progettisti hardware.

La seconda parte del video discute l'uso dei recinti di memoria e delle istruzioni di sincronizzazione per prevenire errori nei programmi paralleli. Il relatore esplora diversi modi di implementare recinti di memoria, implicitamente o esplicitamente, e l'importanza di un'attenta progettazione e coordinamento tra diversi team che lavorano su diversi aspetti di un processore. Inoltre, il docente discute l'uso delle istruzioni CAS come parte dell'algoritmo lock-free nello standard del linguaggio C11 per implementare mutex di algoritmi di mutua esclusione senza deadlock n-thread utilizzando solo uno spazio costante. Charles Leiserson spiega il problema dell'utilizzo dei blocchi in un sistema multi-thread e la soluzione dell'utilizzo di CAS invece, poiché un thread che mantiene il blocco per lungo tempo può potenzialmente bloccare altri thread in attesa di accedere alla stessa risorsa. Inoltre, il video evidenzia il potenziale problema del problema ABA con il confronto e lo scambio e incoraggia coloro che sono interessati all'argomento a saperne di più sugli algoritmi senza blocco.

  • 00:00:00 e le loro istruzioni sono interfogliate per produrre un ordine lineare globale di tutte le istruzioni. Questa è l'idea alla base del modello di memoria di coerenza sequenziale, che è il modello di memoria più importante da un punto di vista teorico. È importante comprendere i modelli di memoria perché, in assenza di blocchi, il comportamento dei programmi paralleli dipende dal modello di memoria. Un esempio presentato nella lezione illustra questo punto chiedendosi se sia possibile che due processori abbiano entrambi il valore 0 dopo aver eseguito il loro codice in parallelo, che dipende dal modello di memoria utilizzato.

  • 00:05:00 In questa sezione, Charles Leiserson discute il concetto di sincronizzazione senza blocchi in cui i carichi e gli archivi devono sembrare obbedire a un ordine lineare globale affinché l'esecuzione sia sequenziale. Usa l'esempio dell'interlacciamento di vari valori per dimostrare diversi percorsi di esecuzione che possono verificarsi e come l'hardware può fare quello che vuole. Spiega inoltre che anche se possono esserci molti modi diversi per intercalare i valori, affinché l'esecuzione sia coerente, deve sembrare che i carichi e gli archivi seguano un ordine lineare. In definitiva, Leiserson conclude che non esiste alcuna esecuzione che termini con entrambi i valori pari a zero, ed è interessante notare che nessuno dei computer moderni fornisce coerenza sequenziale.

  • 00:10:00 In questa sezione viene discusso il concetto di coerenza sequenziale, che implica la comprensione della relazione "accade prima" tra le istruzioni e il loro ordine, la relazione lineare tra la connessione della freccia destra, l'ordine del processore e la sequenza delle istruzioni. Inoltre, l'esclusione reciproca può essere ottenuta senza utilizzare istruzioni o blocchi pesanti, pensando alla coerenza sequenziale e implementando la struttura dei dati condivisi attraverso l'uso di carichi e archivi. Le dispense descrivono metodi che utilizzano operazioni specializzate come testare e impostare o confrontare e scambiare, ma la soluzione presentata evita la creazione di deadlock o altre cose brutte che si verificano quando si utilizzano i blocchi.

  • 00:15:00 In questa sezione, Charles Leiserson spiega l'algoritmo di Peterson per ottenere l'esclusione reciproca in un programma concorrente utilizzando solo le operazioni di caricamento e archiviazione. L'algoritmo consente a due processi simultanei, Alice e Bob, di eseguire il codice senza interferire l'uno con l'altro utilizzando un insieme di variabili e un meccanismo di alternanza. Il codice garantisce che solo un processo alla volta possa entrare in una sezione critica e modificare una risorsa condivisa. A differenza dei blocchi, l'algoritmo di Peterson non si basa sull'acquisizione o il rilascio di un blocco e utilizza invece carichi e negozi per ottenere l'esclusione reciproca.

  • 00:20:00 In questa sezione, il relatore discute l'algoritmo di Peterson per ottenere l'esclusione reciproca nella sezione critica senza utilizzare i blocchi. Spiega che solo una persona alla volta può entrare nella sezione critica e l'algoritmo garantisce che qualcuno che vuole entrare nella sezione critica possa farlo se è l'unico che vuole andare. L'oratore presenta quindi una dimostrazione dell'algoritmo, che prevede l'assunzione che sia Alice che Bob si trovino insieme nella sezione critica e ne derivi una contraddizione. La dimostrazione si basa sulla relazione "accade prima" e sull'ordine di programma delle istruzioni eseguite.

  • 00:25:00 In questa sezione, l'oratore spiega il processo di sincronizzazione senza blocchi. Stabiliscono catene di istruzioni e assicurano che si verifichino nell'ordine corretto per evitare errori di sincronizzazione. Usano l'esempio di Bob e Alice che vogliono accedere a una risorsa condivisa come dimostrazione. Spiegano che durante la sincronizzazione, gli ingegneri devono stare attenti e rivedere "accade prima delle cose" per assicurarsi che avvengano nell'ordine corretto.

  • 00:30:00 In questa sezione, Charles Leiserson discute il concetto di verifica del modello e il suo utilizzo nell'analisi dei protocolli di rete, sicurezza e cache. Quindi passa a spiegare le proprietà dell'algoritmo di Peterson, che garantisce la libertà di starvation ma non funziona con più di due processi. Leiserson esplora anche le sfide della sincronizzazione attraverso la memoria e la mancanza di coerenza sequenziale nei processori moderni, che porta a una coerenza della memoria rilassata e alla difficoltà di ottenere una sincronizzazione corretta.

  • 00:35:00 è sicuro riordinare le istruzioni senza causare problemi con la latenza del carico? Il secondo vincolo è quando non c'è dipendenza dai dati tra le istruzioni, il che significa che le istruzioni non condividono i dati o utilizzano la stessa posizione in memoria. Il riordino delle istruzioni in questo caso può migliorare le prestazioni e coprire la latenza del sovraccarico, poiché il caricamento può essere eseguito prima e altre operazioni possono essere eseguite in attesa del risultato. Comprendere questi concetti a livello di hardware può aiutare a ragionare sul software e ottimizzare le prestazioni.

  • 00:40:00 In questa sezione, Charles Leiserson spiega il concetto di riordino in sincronizzazione senza blocchi. Chiarisce che il riordino è sicuro da eseguire fintanto che non c'è concorrenza, specialmente quando il processore è in funzione o ci sono bolle nel flusso di istruzioni. Questo perché, nei processori moderni, l'hardware memorizza i dati in un buffer e bypassa i carichi andando direttamente al sistema di memoria. Tuttavia, questo bypass può portare a problemi di correttezza se uno degli archivi è l'oggetto che viene caricato.

  • 00:45:00 In questa sezione, Charles Leiserson spiega come avviene il riordino dell'hardware e perché non soddisfa la consistenza sequenziale, e come x86 ha un modello di consistenza della memoria chiamato total store order, che è più debole della consistenza sequenziale. Le regole per l'ordine totale del negozio includono il non riordino mai dei carichi con i carichi, i carichi visualizzati nello stesso ordine da elaboratori esterni, i negozi che non vengono mai riordinati con i negozi e i carichi che vengono riordinati solo con i negozi precedenti in una posizione diversa, ma non con i carichi precedenti da la stessa posizione. Le istruzioni di blocco e l'ordinamento della memoria rispettano un ordine totale.

  • 00:50:00 In questa sezione, l'oratore discute di come il riordino delle istruzioni può violare la coerenza sequenziale e portare a valori errati. Il riordino può verificarsi sia nell'hardware che nel compilatore ed è importante sapere che le istruzioni di blocco non verranno spostate prima di altre istruzioni. L'oratore osserva inoltre che i carichi possono andare prima dei negozi se si trovano a un indirizzo diverso. Il pericolo del riordino è dimostrato nell'algoritmo di Peterson, che potrebbe essere completamente rovinato se si verificano determinati riordini. Pertanto, è importante scrivere codice deterministico per evitare questi problemi durante la sincronizzazione tramite memoria.

  • 00:55:00 In questa sezione, Charles Leiserson discute il problema del riordino durante la scrittura di codice parallelo e simultaneo, in cui è importante evitare che un carico particolare si verifichi prima di un negozio. Per gestire tali scenari, gli ingegneri introducono recinti di memoria, che mantengono l'ordine relativo con altre istruzioni, ma a costo di una maggiore complessità e potenziali bug. Leiserson sostiene inoltre che è vantaggioso per le macchine parallele supportare la coerenza sequenziale, ma è una sfida da realizzare per i progettisti hardware.

  • 01:00:00 In questa sezione, il relatore discute l'importanza dei recinti di memoria e delle istruzioni di sincronizzazione per evitare che i programmi paralleli incontrino errori. L'oratore descrive diversi modi in cui è possibile implementare i recinti di memoria, ad esempio esplicitamente come istruzione o implicitamente attraverso altre istruzioni di sincronizzazione come il blocco e lo scambio. Tuttavia, ci sono casi in cui un recinto di memoria può effettivamente rallentare un programma, dimostrando l'importanza di un'attenta progettazione e coordinamento tra diversi team che lavorano su diversi aspetti di un processore. Inoltre, l'oratore consiglia di utilizzare variabili volatili e recinti del compilatore per impedire al compilatore di ottimizzare le variabili e causare errori nel codice parallelo.

  • 01:05:00 In questa sezione, il docente discute la sincronizzazione senza blocchi nello standard del linguaggio C11. Lo standard definisce un modello di memoria debole, che consente di dichiarare le cose come atomiche, richiedendo l'uso di operazioni costose come il recinto di memoria o un confronto e scambio atomico per un algoritmo di esclusione reciproca privo di deadlock. Qui, l'istruzione CAS (Compare-and-Swap) viene esplorata come parte dell'algoritmo lock-free. L'istruzione controlla se il valore in memoria è lo stesso del vecchio valore prima di scambiarlo con il nuovo valore, tutto fatto in modo atomico. L'uso di CAS consente di implementare mutex di algoritmi di mutua esclusione senza deadlock n-thread utilizzando solo uno spazio costante. Un'istruzione di blocco, che gira finché non ottiene il valore vero, viene utilizzata per scambiare in vero affermando che qualcuno detiene il blocco.

  • 01:10:00 In questa sezione, il professor Charles Leiserson spiega come utilizzare il confronto e lo scambio (CAS) per risolvere i problemi di sincronizzazione. Dimostra come utilizzare CAS come blocco e corregge un bug nel codice presentato da uno studente. Quindi presenta un codice errato utilizzato per calcolare la somma dei valori in un array, che porta a una race condition. Introduce i blocchi mutex come una soluzione tipica e spiega il potenziale problema di un thread che viene scambiato dopo aver acquisito il blocco, portando altri thread in attesa del blocco, ostacolando così il progresso.

  • 01:15:00 In questa sezione, Charles Leiserson spiega il problema dell'utilizzo dei blocchi in un sistema multi-thread e la soluzione dell'utilizzo di CAS invece. Con i lock, un thread può potenzialmente mantenere il lock per molto tempo, bloccando altri thread in attesa di accedere alla stessa risorsa. Tuttavia, con CAS, un caricamento di x è seguito da un archivio di x dopo aver calcolato una temperatura pur avendo anche le variabili vecchio e nuovo per memorizzare il vecchio risultato e aggiungere il risultato temporaneo a quel vecchio valore per produrre un nuovo valore che può essere scambiato se il vecchio valore non è cambiato. Charles menziona anche il problema ABA con il confronto e lo scambio e incoraggia coloro che sono interessati all'argomento a saperne di più sugli algoritmi senza blocco.
 

Lezione 18. Linguaggi specifici del dominio e autotuning



Lezione 18. Linguaggi specifici del dominio e autotuning

In questo video, il professor Saman Amarasignhe del dipartimento EECS del MIT discute i vantaggi dell'utilizzo di linguaggi specifici del dominio (DSL) e dell'autotuning nell'ingegneria delle prestazioni. Sottolinea l'importanza dei DSL, che catturano domini specifici di un'area che sono difficili da descrivere in linguaggi generici, consentendo ai programmatori di sfruttare la conoscenza degli esperti di dominio per prestazioni migliori. Singh discute l'ottimizzazione dei processi di grafi utilizzando i DSL, incluso il partizionamento dei grafi e l'importanza della forma del grafo nel calcolo. Introduce DSL Halide per l'elaborazione delle immagini, che consente una rapida ottimizzazione del codice e la portabilità tra le macchine. Discute l'uso di Halide in vari settori come Google e Adobe. In definitiva, sottolinea l'importanza di sperimentare approcci diversi nell'ottimizzazione del codice concentrandosi su parallelismo, località e lavoro ridondante.

Il video parla anche delle sfide dell'ingegneria delle prestazioni e della ricerca dei parametri ottimali affinché un programma funzioni in modo efficiente. L'oratore suggerisce che l'autotuning può risolvere questo problema cercando automaticamente l'ampio spazio dei parametri per trovare i valori ottimali. Osserva che la ricerca esaustiva può essere poco pratica e che le soluzioni basate sull'euristica potrebbero non essere ottimali. L'autotuning, che definisce uno spazio di valori accettabili e itera in base ai risultati delle prestazioni, può accelerare il processo di ricerca di soluzioni ottimali. Il relatore discute anche l'applicazione dell'autotuning nella generazione di pianificazioni per Try, che è stato in grado di produrre pianificazioni in modo più efficiente ed efficace rispetto alla ricerca esaustiva.

  • 00:00:00 In questa sezione, il professor Saman Amarasignhe, professore presso il dipartimento EECS del MIT, parla di linguaggi specifici del dominio e auto-tuning. Spiega che questi linguaggi hanno vantaggi ingegneristici perché catturano domini specifici di un'area specifica che sono difficili da descrivere in un linguaggio generico. I linguaggi specifici del dominio sono molto più facili da capire e mantenere e consentono al programmatore di sfruttare la conoscenza degli esperti del dominio per ottenere prestazioni davvero buone. Inoltre, se costruito correttamente, un linguaggio specifico del dominio può lasciare la decisione di livello inferiore al compilatore, rendendo il processo di ottimizzazione molto più semplice.

  • 00:05:00 In questa sezione, il relatore discute l'uso dei linguaggi specifici del dominio (DSL) nell'ingegneria delle prestazioni. Incoraggiano a lasciare le prestazioni al compilatore quando possibile e introducono tre diversi linguaggi/framework di programmazione per l'elaborazione dei grafici: Graffiti, Halide e OpenTuner. Sottolineano che i grafici sono ovunque, dalle ricerche su Google ai motori di raccomandazione, e approfondiscono l'algoritmo PageRank utilizzato da Google per classificare le pagine web. L'algoritmo PageRank esamina i vicini di una pagina web e calcola un nuovo rango in base alla loro influenza, mostrando l'importanza dell'elaborazione dei grafici nell'ingegneria delle prestazioni.

  • 00:10:00 In questa sezione, il relatore discute gli algoritmi grafici, che possono comportare l'elaborazione di enormi quantità di dati e l'iterazione dei calcoli per l'intero grafico. Per ottimizzare il codice per le prestazioni, è possibile utilizzare un DSL. Il tipo di algoritmi utilizzati per l'elaborazione del grafico include algoritmi basati sulla topologia, in cui l'intero grafico partecipa al calcolo, e algoritmi basati sui dati, in cui l'elaborazione viene eseguita su una piccola regione o parte del grafico. Esistono anche diversi modi per eseguire le inversioni del grafico e ogni modo ha un diverso insieme di risultati.

  • 00:15:00 In questa sezione viene discusso l'argomento del partizionamento del grafico, in cui un grafico di grandi dimensioni viene suddiviso in parti più piccole. Il vantaggio del partizionamento di un grafico è che consente il parallelismo e fornisce anche una buona località, il che significa che i nodi su cui si lavora sono abbastanza piccoli da stare nella cache. Il partizionamento dei grafici ha anche un impatto sui grafici dei social network in quanto hanno una relazione di legge di potenza. Ciò significa che alcuni nodi hanno più connessioni o un impatto maggiore di altri e, durante l'elaborazione di questi grafici, è necessario prestare maggiore attenzione a determinate connessioni e nodi data la loro importanza.

  • 00:20:00 In questa sezione, il relatore discute l'importanza della forma di un grafico nel calcolo, in particolare come la dimensione e la località di un grafico possono influenzare l'efficienza degli algoritmi di parallelismo. Fattori come il parallelismo, la località e il lavoro extra necessario devono essere attentamente bilanciati per ottenere le migliori prestazioni per un dato algoritmo e il metodo giusto deve essere selezionato in base al tipo di grafico, al tipo di algoritmo e all'hardware utilizzato. È stato sviluppato un linguaggio specifico del dominio per separare l'algoritmo costante dai metodi di elaborazione per ottimizzare al meglio questi fattori.

  • 00:25:00 in questa sezione, il relatore discute su come utilizzare i linguaggi specifici del dominio (DSL) per scrivere codice a un livello superiore, rendendolo più semplice ed elegante. Forniscono esempi di diversi algoritmi e di come i DSL forniscono un modo semplice per calcolarli. Inoltre, il relatore spiega come ottimizzare la programmazione dei DSL per ottenere la migliore velocità possibile, consentendo anche l'elaborazione parallela. Il codice può essere variato in base ai cambiamenti nel grafico o nella macchina, ma l'algoritmo rimane lo stesso. L'oratore sottolinea l'importanza dei DSL che forniscono semplicità nella programmazione pur essendo abbastanza potenti da generare pianificazioni ottimizzate.

  • 00:30:00 In questa sezione, il relatore discute un altro linguaggio specifico del dominio, Halide, che si concentra sull'elaborazione delle immagini con strutture regolari dense. Halide aiuta a ridurre la quantità di programmazione necessaria per ottenere prestazioni ottimizzate e aumenta la portabilità del programma su macchine diverse. L'oratore fornisce un esempio di sfocatura tre per tre per dimostrare come funziona Halide. Halide ha un modello simile al linguaggio grafico discusso in precedenza in termini di ottimizzazione delle prestazioni attraverso diverse combinazioni di varie tecniche.

  • 00:35:00 In questa sezione, il relatore discute l'uso di linguaggi specifici del dominio (DSL) e l'autotuning per ottimizzare le prestazioni del codice. Fornisce un esempio di un filtro immagine che funziona più velocemente utilizzando un DSL chiamato Halide, rispetto a un codice C valido. Halide consente il disaccoppiamento dell'algoritmo dalla pianificazione, che consente una semplice ottimizzazione della pipeline di funzioni pure in esecuzione. Infine, il relatore sottolinea la necessità di un compromesso tra località, parallelismo e lavoro ridondante per ottenere le migliori prestazioni dalle risorse di calcolo disponibili.

  • 00:40:00 In questa sezione, il relatore discute l'importanza della località quando si tratta di elaborazione delle immagini. Quando si elabora un'immagine di grandi dimensioni, non è efficiente applicare filtri che operano sull'intera immagine in una sola volta perché non entrerà nella cache. Invece, il relatore suggerisce di scomporre l'immagine in sezioni più piccole e di applicare filtri a ciascuna sezione, concentrandosi sulla località e sul parallelismo. Ciò può essere ottenuto utilizzando un framework di pianificazione e ottimizzando la larghezza di banda di calcolo e la granularità dello storage. Potrebbe anche richiedere un lavoro ridondante per ottenere una migliore località e parallelismo.

  • 00:45:00 In questa sezione, il relatore discute i linguaggi specifici del dominio e l'autotuning, concentrandosi sull'uso di Halide. Halide può fondere insieme le funzioni di libreria, il che è più veloce rispetto alla chiamata di librerie perché c'è più località. Il relatore mostra come Halide può ottimizzare i processi computazionali come il calcolo del filtro bilaterale e gli algoritmi di segmentazione. In un esempio, un algoritmo di segmentazione scritto in MATLAB, che chiamava librerie ottimizzate a mano, era 70 volte più veloce quando scritto in Halide. Halide è una parte importante di Google ed è stato integrato nei telefoni Android ed è stato utilizzato in Google Glass.

  • 00:50:00 In questa sezione, il relatore discute l'efficacia dell'utilizzo di Halide per l'elaborazione front-end e come sta diventando ampiamente utilizzato in diversi settori. Halide vanta un aumento della velocità del 4-5% rispetto alle versioni precedenti, il che è significativo per Google considerando il numero di video scaricati. Adobe ha anche annunciato che interi filtri di Photoshop sono scritti in Halide. Anche il processore di immagini Snapdragon e Intel stanno iniziando a utilizzare Halide. Il relatore discute anche di come Halide e Graph condividano somiglianze in termini di capacità di automatizzare l'ottimizzazione, semplificando il lavoro dell'ingegnere delle prestazioni. Tuttavia, quando si tratta di ottimizzazione algoritmica, si tratta di un cambiamento di livello superiore che richiede conoscenze contestuali specifiche, rendendo difficile l'automazione. Tuttavia, strumenti come i linguaggi pianificati offrono agli utenti la possibilità di provare approcci diversi e ottenere prestazioni migliori.

  • 00:55:00 In questa sezione, il relatore discute la complessità dei moderni sistemi informatici e come non esiste un modo giusto per ottimizzare il codice. Sottolineano l'importanza di provare approcci diversi e il significato di cache, località e parallelismo. Discutono anche di come le persone in vari domini, come la biologia e la fisica, trascorrano molto tempo a ottimizzare il codice piuttosto che perseguire la ricerca perché non sono in grado di scrivere programmi abbastanza velocemente a causa della complessità del codice. L'oratore suggerisce che trovare domini in cui le persone trascorrono la maggior parte del loro tempo hackerando e inventando l'astrazione può essere un'area interessante da esplorare per la ricerca. Nel complesso, lo spazio su cui operare per ottimizzare i programmi include parallelismo, località e lavoro ridondante, e giocare in questo spazio è fondamentale per gli ingegneri delle prestazioni.

  • 01:00:00 In questa sezione, il relatore discute le sfide dell'ingegneria delle prestazioni, che comporta la ricerca dei parametri giusti affinché un programma funzioni in modo ottimale. Spiega che ci sono numerosi parametri che possono essere regolati, come l'allocazione della memoria e la dimensione del blocco, ma che può essere difficile determinare i valori corretti per ogni parametro per ogni programma. Tuttavia, l'oratore suggerisce che l'autotuning può risolvere questo problema, cercando automaticamente l'ampio spazio dei parametri per trovare i valori ottimali. Spiega che le soluzioni basate sull'euristica, che implicano regole di hard-coding per determinate situazioni, possono funzionare la maggior parte del tempo ma potrebbero non essere sempre ottimali. Il relatore osserva inoltre che la costruzione di modelli del sistema può essere problematica in quanto il modello non tiene conto di tutti i fattori importanti, il che può portare a risultati non ottimali.

  • 01:05:00 In questa sezione, il relatore discute le sfide legate alla ricerca di soluzioni ottimali di fronte al cambiamento della tecnologia o all'evoluzione dei requisiti. Nota che esiste una varietà di "euristica" che i programmatori utilizzano per guidare le loro soluzioni, spesso basate su linee guida o regole empiriche che potrebbero non essere più applicabili. Un'opzione è la ricerca esaustiva, ma questo può essere poco pratico dato l'enorme numero di possibili permutazioni. Per risolvere questo problema, il relatore raccomanda l'uso dell'autotuning come un modo per sfoltire lo spazio di ricerca e trovare soluzioni ottimali più velocemente. L'autotuning comporta la definizione di uno spazio di valori accettabili, la scelta casuale di un valore da testare e quindi l'iterazione in base ai risultati delle prestazioni. OpenTuner è un esempio di un framework che utilizza un insieme di tecniche, come hill climber e ricerca casuale, per accelerare questo processo iterativo.

  • 01:10:00 In questa sezione, il relatore discute il concetto di ottimizzazione automatica e come può essere applicato nella generazione di pianificazioni per Try. Comprendendo i grafici e il ritmo coinvolti, l'autotuning può essere utilizzato per generare un programma in modo più efficiente ed efficace rispetto alla ricerca esaustiva. Questo metodo è stato in grado di produrre programmi in meno di due ore e, in alcuni casi, anche meglio di quello che inizialmente si pensava fosse il miglior programma possibile.
 

Lezione 19. Leiserchess Codewalk



Lezione 19. Leiserchess Codewalk

In questo video di YouTube intitolato "19. Leiserchess Codewalk", Helen Xu spiega le regole di Lesierchess, un gioco giocato da due squadre con l'obiettivo di sparare al re della squadra avversaria o far sparare al tuo re. Il gioco ha due tipi di mosse, mosse base e mosse schiacciate, e una regola Ko che rende una mossa illegale se annulla la mossa più recente dell'avversario. Xu si tuffa in vari aspetti del gioco, tra cui il metodo di controllo del tempo di Fisher, la notazione Forsythe-Edwards, l'autotester del cloud e l'organizzazione del progetto, valutando e confrontando i bot utilizzando valutazioni Elo, generazione di mosse, valutazione statica e algoritmi di ricerca come alfa-beta, variazione di principio, potatura sottoalbero e tabelle di trasposizione. Discute anche dell'importanza dell'infrastruttura di test per l'ottimizzazione del programma e del file eval.c, che contiene l'euristica che valuta ogni casella del tabellone in base al tipo di pezzo e al suo colore.

L'oratore approfondisce anche l'aspetto della copertura laser del gioco, spiegando il complicato sistema di generazione di tutte le possibili mosse per una posizione basata sul colore del giocatore usando un'affermazione while-true. Spiegano anche l'importanza della correttezza nel codice e come testarla, suggerendo la conversione della rappresentazione per garantire la correttezza prima dell'ottimizzazione per le prestazioni. Il relatore discute anche della grande flessibilità fornita dall'interfaccia UCI di Leiserchess, che consente agli utenti di modificare tabelle e comandi a proprio piacimento, e rassicura gli spettatori che il codice morto verrà ripulito e qualsiasi altro bug dovrebbe essere segnalato per essere corretto.

  • 00:00:00 In questa sezione, Helen illustra le regole del gioco Lesierchess e come si gioca. Il gioco è giocato da due squadre, arancione e lavanda, ciascuna delle quali ha sette pedoni e un re. L'obiettivo del gioco è sparare al re della squadra avversaria o far sparare al tuo re. Il gioco ha due tipi di mosse, mosse base e mosse swat. Il gioco ha inoltre una regola Ko che rende una mossa illegale se annulla la mossa più recente dell'avversario semplicemente tornando al punto in cui si trovava la squadra avversaria. Si verifica un pareggio se ci sono state 50 mosse di ciascuna squadra senza che un pedone sia stato colpito, la stessa posizione si ripete o le due squadre concordano sul pareggio.

  • 00:05:00 In questa sezione, il relatore spiega il metodo di controllo del tempo di Fisher utilizzato in leiserchess. Ogni giocatore inizia con un budget di tempo iniziale e un incremento di tempo. Nell'esempio utilizzato, ogni giocatore inizia con 60 secondi e quando termina la propria mossa ottiene 0,5 secondi in più. Ma il limite di tempo effettivo può essere qualsiasi cosa. L'oratore mostra quindi come giocare a leiserchess chiedendo al pubblico di suggerire mosse per il mandarino per colpire il pedone in F5 evitando i contrattacchi. Tuttavia, l'oratore avverte delle sottigliezze del gioco, come uccidere ingenuamente tutti i pezzi, poiché potrebbe aprire l'avversario.

  • 00:10:00 In questa sezione, Helen Xu discute la notazione Forsythe-Edwards come uno strumento per rappresentare una posizione degli scacchi utilizzando una stringa, che è utile per scopi di debug, consentendo di tornare facilmente a una posizione specifica. Spiega anche come leggere i registri delle partite di scacchi, dove scompone ogni mossa e le annotazioni corrispondenti. Inoltre, dimostra come utilizzare il server di scrimmage per testare i bot con altre squadre della classe, nonché come sfidare altre squadre e visualizzare le partite giocate.

  • 00:15:00 In questa sezione, Helen Xu parla dell'autotester Cloud e dell'organizzazione del progetto per Lesierchess. Mentre il server di scrimmage consente solo un gioco alla volta, l'autotester Cloud può eseguire più giochi e binari su un controllo temporale che può essere personalizzato in base alle preferenze di ciascun utente. L'organizzazione del progetto nel repository include le directory doc, auto tester, pgnstates, tests, player e webgui. L'auto tester è un auto tester locale Java utilizzato per testare le modifiche in locale, mentre nella directory tests è possibile specificare le configurazioni per il test automatico. Helen Xu introduce anche l'interfaccia toracica universale (UCI), un protocollo di comunicazione utilizzato da Lesierchess per interfacciarsi con il tester automatico.

  • 00:20:00 In questa sezione, il relatore discute di come i bot verranno misurati e confrontati utilizzando le valutazioni Elo, che è un sistema di valutazione basato sul livello di abilità relativo nei giochi a somma zero. Il rating Elo non si basa esclusivamente sul tempo, ma anche sui nodi al secondo ricercati utilizzando l'UCI. L'oratore si tuffa quindi in maggiori dettagli sul gioco, come la generazione di mosse, la rappresentazione del tabellone e la struttura utilizzata per memorizzare la posizione. Inoltre, la mossa è rappresentata utilizzando 28 bit, che includono il tipo di pezzo, l'orientamento, da quadrato, quadrato intermedio e due quadrati. L'impianto di riferimento genera tutte le mosse a seconda di chi è il turno iterando attraverso il tabellone e generando tutte le mosse da quel particolare pezzo. L'oratore menziona l'uso della funzione di debug perft per garantire che la generazione di mosse modificata restituisca le stesse mosse da ogni posizione.

  • 00:25:00 In questa sezione, l'oratore discute su come determinare se una mossa è buona attraverso una valutazione statica, che genera un punteggio basato su una posizione utilizzando l'euristica. Le euristiche includono quelle incentrate sul re, i pedoni e la distanza e possono aiutare a determinare se una posizione è buona o meno. L'oratore parla anche di come i programmi di gioco utilizzano gli alberi di ricerca per giocare e scegliere la mossa migliore in base alla valutazione. Per ridurre il numero di nodi, il relatore entra nei dettagli sulla ricerca di quiescenza e sulla ricerca min-max, che possono migliorare la quantità di nodi valutati e portare a prestazioni migliori.

  • 00:30:00 In questa sezione, l'oratore discute l'algoritmo chiamato alpha beta, che viene utilizzato durante una ricerca da un nodo con una finestra alpha beta. Se il valore della ricerca scende al di sotto dell'alfa, la mossa non è abbastanza buona e continui a cercare. Beta significa essenzialmente che una parte sta cercando di massimizzare e l'altra sta cercando di minimizzare. Pertanto, se il valore scende al di sopra di beta, generi un limite di beta, perché l'avversario non ti lascerebbe fare quella mossa, perché sarebbe troppo buona. L'oratore spiega quindi il principio della ricerca della variazione, che presuppone che la prima mossa sia la migliore, e si esegue la ricerca scout, che è anche chiamata ricerca a finestra zero, sulle mosse rimanenti per verificare che siano peggiori. Questo modo di ricerca è una variazione dell'algoritmo alfa-beta.

  • 00:35:00 In questa sezione viene discusso il concetto di potatura di sottoalberi negli algoritmi di ricerca minimax. L'idea alla base della potatura dei sottoalberi è rimuovere i sottoalberi con punteggi inferiori al miglior punteggio trovato finora. Ciò riduce il numero di nodi valutati e velocizza il processo di ricerca. L'avversario cerca anche la mossa migliore e cerca di minimizzare i punteggi del giocatore. L'equilibrio tra massimizzare il punteggio del giocatore e minimizzare il punteggio dell'avversario è cruciale, e l'obiettivo è trovare una mossa che sia buona per il giocatore e anche qualcosa che l'avversario permetta.

  • 00:40:00 In questa sezione, Helen Xu spiega il concetto di potatura delle variazioni principali in cui si assume che il sottoalbero più a sinistra sia il percorso migliore e si prendono le prime uscite se il presupposto è vero. Se il presupposto è falso, è necessario eseguire la ricerca nell'intero sottoalbero. La ricerca scout viene utilizzata per applicare questo in modo ricorsivo ai sottoalberi inferiori, con passaggi iniziali per verificare le ipotesi. Questo metodo migliora la potatura ed elabora la maggior parte dell'albero del gioco senza ricerche di finestre.

  • 00:45:00 In questa sezione, apprendiamo le ottimizzazioni della ricerca per il programma Leiserchess. Una delle ottimizzazioni più importanti è l'uso di una tabella di trasposizione per memorizzare le posizioni incontrate in precedenza, che consente di risparmiare tempo evitando ricerche non necessarie. Altre ottimizzazioni includono l'uso dell'hashing di Zobrist per generare hash univoci per ogni posizione, la tabella delle mosse killer per memorizzare le mosse valide in modo che non debbano essere ricalcolate e la potatura della futilità per saltare l'esplorazione delle mosse che non aumenterebbero il punteggio alfa. Si consiglia inoltre l'implementazione di un miglior libro di apertura per memorizzare le posizioni precalcolate all'inizio del gioco e risparmiare tempo nella ricerca.

  • 00:50:00 In questa sezione, il relatore discute alcuni strumenti utili per l'ottimizzazione di un programma di scacchi, inclusi libri di apertura e database di fine gioco che possono essere precalcolati. È importante testare e disporre di una buona infrastruttura per i test per poter innovare e fare progressi senza problemi di debug. L'uso delle tabelle di trasposizione nella programmazione parallela rende importante poterle disattivare a scopo di test e si consiglia di eseguire ricerche a profondità fissa durante il test. Nel complesso, disporre di una buona infrastruttura di test è fondamentale per fare progressi ed evitare significativi problemi di debug.

  • 00:55:00 In questa sezione, il relatore discute il file eval.c nel progetto Leiserchess e come possa sembrare travolgente a prima vista a causa delle sue dimensioni e complessità. Tuttavia, man mano che gli utenti acquisiscono maggiore familiarità con esso, acquisiranno sicurezza nella gestione di un pezzo di codice di dimensioni adeguate. Il file eval.c contiene euristiche come p between, p central, k face e k aggressive che valutano ogni casella sulla scacchiera in base al tipo di pezzo e al suo colore. La p tra l'euristica determina se un pedone si trova tra i due re, mentre la p centrale dà un bonus basato su quanto è vicino il pedone al centro della scacchiera. L'euristica k faccia e k aggressiva fornisce bonus basati sull'orientamento del re e sulla sua distanza dall'avversario e dai bordi del tabellone.

  • 01:00:00 In questa sezione, l'oratore spiega la copertura laser, che è un aspetto complicato del gioco. La copertura laser genera tutte le possibili mosse di una particolare posizione a seconda del colore del giocatore. Quindi fornisce un elenco di mosse e l'oratore elabora il modo in cui questa mappa svolge la sua funzione con un'affermazione while-true. Il percorso laser rimbalza su alcune pedine mentre disegna il percorso e aumenta la distanza per ogni casella. Dopo aver generato la mappa, il processo viene ripetuto e la distanza viene divisa per la distanza effettiva dal laser. Questo complicato sistema ottimizza le iterazioni richieste nel metodo di valutazione per trovare ogni pezzo sulla scacchiera, il che rallenta il processo, e l'oratore aggiunge che rappresentare la scacchiera in modo diverso e affermare che entrambe le funzioni di conversione producono lo stesso risultato è un buon modo per fare decisioni di ottimizzazione.

  • 01:05:00 In questa sezione del video, i relatori discutono dell'importanza di mantenere la correttezza del codice e di come testarla. Spiegano che la conversione da una rappresentazione all'altra può rallentare il processo ma è necessaria per garantire la correttezza prima di ottimizzare le prestazioni. Un modo per verificare la correttezza è tenere traccia dei conteggi dei nodi e assicurarsi che rimangano gli stessi dopo aver apportato modifiche. Dimostrano anche come eseguire il codice e mostrano l'interfaccia UCI in Lesierchess.c, che consente di impostare valori per varie cose senza dover ricompilare il binario ogni volta. Infine, esaminano una tabella di euristiche e spiegano come specificare i valori per il tester automatico.

  • 01:10:00 In questa sezione, il relatore discute la grande flessibilità che il gioco Leiserchess offre per la modifica di tabelle e comandi attraverso l'interfaccia UCI. Ciò consente agli utenti di accedere e implementare tutti i comandi che desiderano, incluse nuove euristiche, e avere il controllo sull'analisi e l'implementazione. Sebbene esista del codice morto, il professore rassicura gli spettatori che verrà ripulito e che qualsiasi altro bug dovrebbe essere segnalato per essere corretto. Infine, afferma che sebbene il progetto possa non essere divertente ogni minuto, nel complesso offre molto divertimento.
1...232425262728293031323334353637...74
Nuovo commento
Motivazione: