Ti stai perdendo delle opportunità di trading:
- App di trading gratuite
- Oltre 8.000 segnali per il copy trading
- Notizie economiche per esplorare i mercati finanziari
Registrazione
Accedi
Accetti la politica del sito e le condizioni d’uso
Se non hai un account, registrati
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.