Apprendimento automatico e Reti Neurali - pagina 29

[MetaQuotes]

Conferenza 36: Alan Edelman e Julia Language

Conferenza 36: Alan Edelman e Julia Language

In questo video, Alan Edelman discute il potere dei linguaggi di programmazione per l'apprendimento automatico e la loro importanza in matematica. Sottolinea il recente sviluppo del linguaggio Julia, come riconosciuto da Google, per i suoi meriti tecnici e l'usabilità nell'apprendimento automatico. Edelman spiega come funziona la differenziazione automatica in Julia e fornisce un esempio di calcolo della radice quadrata di x senza utilizzare differenze numeriche finite attraverso l'algoritmo babilonese. Discute anche l'uso dei tipi in Julia per un calcolo efficiente e per semplificare il processo di backpropagation con matrici a blocchi. Nel complesso, Edelman sottolinea l'importanza dell'algebra lineare per i calcoli matematici e il suo ruolo nella comprensione di fenomeni complessi.

• 00:00:00 In questa sezione, Alan Edelman discute una dimostrazione del professor Strang su rango di riga uguale a rango di colonna e come questo concetto si applica alla matrice zero. Poi parla dei recenti sviluppi in Julia, un linguaggio di programmazione che sta guadagnando terreno nell'apprendimento automatico, e di come Google abbia riconosciuto il suo potere in questo campo. Google ha recentemente pubblicato un post sul blog affermando che ci sono solo due lingue abbastanza potenti per l'apprendimento automatico e Julia è una di queste. Edelman fornisce esempi per illustrare questo punto e incoraggia gli studenti a controllare il post sul blog per ulteriori informazioni.
  
  
• 00:05:00 In questa sezione, Alan Edelman discute l'importanza dei linguaggi di programmazione in senso matematico e la loro capacità di fare molto di più che implementare algoritmi. Spiega che Julia, Swift, C++ e Rust sono i quattro linguaggi di programmazione ritenuti appropriati per l'apprendimento automatico in base ai loro meriti tecnici e all'usabilità. Edelman sottolinea l'importanza dell'algebra lineare come base per tutti i corsi di ingegneria e il suo sfortunato ritardo nella storia. Quindi approfondisce la differenziazione automatica e il modo in cui si relaziona al calcolo, il suo iniziale scetticismo nei suoi confronti e i dettagli tecnici che ha esplorato nel suo taccuino sulla differenziazione automatica in modalità diretta.
  
  
• 00:10:00 In questa sezione, Alan Edelman discute i suoi pensieri iniziali sulla differenziazione automatica e come pensava che fosse proprio come il calcolo che aveva imparato a scuola, ma con un computer. Tuttavia, si rese presto conto che esisteva un terzo metodo che non era né le differenze finite né la regola della catena, che lo affascinava. Condivide quindi un esempio di come ha calcolato la radice quadrata di x utilizzando l'algoritmo babilonese in Julia e di come è stato in grado di ottenere la derivata della radice quadrata senza digitare esplicitamente la formula della derivata, grazie alla funzione di differenziazione automatica di Julia.
  
  
• 00:15:00 In questa sezione, l'oratore descrive l'utilizzo del codice Julia per calcolare la radice quadrata di un numero senza utilizzare calcoli alle differenze finite. Il codice crea un tipo di variabile chiamato "dual number" che è una coppia di float che rappresenta una funzione numerica e la sua derivata. L'oratore quindi sovraccarica le operazioni più e dividi per implementare la regola del quoziente, consentendo il calcolo della radice quadrata utilizzando l'algoritmo babilonese. Il codice funziona senza l'uso di differenze numeriche finite e il relatore osserva che Julia consente il riutilizzo del codice esistente in nuovi contesti per eseguire "magie".
  
  
• 00:20:00 In questa sezione, Alan Edelman spiega come il linguaggio di programmazione Julia può calcolare in modo efficiente la derivata utilizzando l'algoritmo babilonese su un numero duale nel codice assembler. Dimostra come lo stesso codice eseguito nel pacchetto di calcolo simbolico di Python fornisce un calcolo simbolico con grandi coefficienti, che è molto inefficiente. Poi rivela l'SVD, un altro algoritmo che lo ha convinto di come funziona l'algoritmo babilonese. Prendendo la derivata di ogni riga del codice, l'algoritmo può convergere alla radice quadrata e alla derivata delle radici quadrate. La derivata risultante non è simbolica o numerica ma utilizza la regola del quoziente e la regola dell'addizione in ogni passaggio per ottenere la risposta.
  
  
• 00:25:00 In questa sezione, Alan Edelman, il creatore della lingua Julia, discute di come funziona la differenziazione automatica nella lingua. Invece di prendere manualmente i derivati di ogni riga, Edelman suggerisce che il software può farlo automaticamente lasciando che il compilatore JIT lo gestisca. Ciò elimina la necessità di scrivere un traduttore o scrivere a mano, rendendo la codifica molto più snella. Edelman osserva che l'apprendimento automatico fa molto affidamento sui problemi di ottimizzazione, che riguardano l'assunzione di derivati, rendendo la differenziazione automatica una componente essenziale del processo. Infine, spiega come l'utilizzo dei tipi può semplificare la creazione di matrici strutturate per archiviare i dati.
  
  
• 00:30:00 In questa sezione, Alan Edelman discute l'uso dei tipi in Julia per archiviare in modo efficiente solo ciò che è necessario durante l'esecuzione di calcoli, il che lo distingue da linguaggi come Python e MATLAB che hanno più sovraccarico. Quindi tocca brevemente l'idea della differenziazione in modalità immersa nelle reti neurali, partendo da un esempio scalare e generalizzando a matrici e vettori. Scrive l'algebra lineare coinvolta in questo processo, ma finisce il tempo prima che possa spiegarlo completamente.
  
  
• 00:35:00 In questa sezione, Edelman spiega come utilizzare le matrici di blocchi in Julia per eseguire la retropropagazione senza dover calcolare manualmente le derivate. Mostra come l'uso di una matrice diagonale e di una matrice triangolare inferiore può semplificare il processo di retropropagazione e utilizzare le funzioni integrate di Julia. Usando l'algebra lineare, dimostra come una barra rovesciata può risolvere la matrice triangolare inferiore, rendendo molto più facile il calcolo delle derivate. Edelman sottolinea che l'algebra lineare è essenziale per molti calcoli matematici ed è il segreto per comprendere molti fenomeni complessi.

[MetaQuotes]

MIT 6.172 Performance Engineering of Software Systems, autunno 2018 - 1. Introduzione e moltiplicazione di matrici

1. Introduzione e moltiplicazione di matrici

In questo video di YouTube intitolato "1. Introduzione e moltiplicazione di matrici", il docente discute l'importanza dell'ingegneria delle prestazioni e di come si è evoluta nel tempo. Usando l'esempio della moltiplicazione di matrici, il relatore mostra come le tecniche di codifica e le specifiche della macchina possono avere un grande impatto sulle prestazioni. La discussione copre argomenti come l'ordine dei cicli, l'utilizzo della cache e la programmazione parallela. Il relatore esplora anche modi per ottimizzare il codice per diversi processori e calcoli aritmetici. Nel complesso, il video fornisce preziose informazioni sul mondo dell'ingegneria delle prestazioni e sulle sue applicazioni pratiche nei moderni sistemi informatici.

• 00:00:00 In questa sezione, il docente discute l'importanza dell'ingegneria delle prestazioni e il motivo per cui viene studiata. Le prestazioni non sono sempre la massima priorità quando si tratta di sviluppo software. Tuttavia, è la valuta dell'informatica e viene utilizzata per acquistare altre proprietà desiderate come facilità di programmazione, sicurezza e correttezza. Il degrado delle prestazioni può causare software inutilizzabile e la principale lamentela delle persone sui sistemi informatici è che sono troppo lenti. Pertanto, sebbene le prestazioni possano non avere un valore intrinseco, contribuiscono alle cose a cui tengono gli sviluppatori.
  
  
• 00:05:00 In questa sezione, il relatore discute la storia dell'ingegneria delle prestazioni nell'informatica e il passaggio dai primi giorni di intensa ingegneria delle prestazioni a causa delle risorse limitate della macchina, all'era della Legge di Moore in cui le densità dei chip raddoppiavano ogni due anni e attendevano per l'hardware recuperare il ritardo era più vantaggioso dell'ottimizzazione del software. Tuttavia, il relatore osserva che il ridimensionamento di Dennard, che consentiva di aumentare la velocità di clock riducendo la potenza, è terminato nel 2004 e quindi la necessità di ingegneria delle prestazioni è più importante che mai. L'oratore include citazioni degli scienziati informatici Donald Knuth, Bill Wolfe e Michael Jackson sull'importanza del codice leggibile e sull'avvertimento contro l'ottimizzazione prematura.
  
  
• 00:10:00 In questa sezione, il relatore discute i limiti sulle velocità di clock che sono stati raggiunti nei primi anni 2000 a causa della densità di potenza, con conseguente sviluppo di processori multi-core per scalare le prestazioni. Tuttavia, ciò significava che le prestazioni non erano più gratuite e richiedevano una programmazione parallela, cosa che l'industria non aveva mai fatto prima. Da quel momento in poi, il software ha dovuto adattarsi alle nuove configurazioni hardware per essere efficace e, di conseguenza, c'è stata una maggiore attenzione alle prestazioni nei lavori di sviluppo software.
  
  
• 00:15:00 In questa sezione, il relatore inizia spiegando l'importanza pratica e teorica di imparare a scrivere software che utilizza in modo efficiente l'hardware moderno. Forniscono quindi un esempio di ingegneria delle prestazioni utilizzando il problema ben studiato della moltiplicazione di matrici, discutendo la macchina che utilizzeranno, comprese le sue specifiche e capacità come elaborazione parallela, dimensione della cache e capacità di memoria, e concludendo con una spiegazione di il codice di base per Python per la moltiplicazione di matrici. L'oratore sottolinea la potenza della macchina e il potenziale per progetti divertenti che ne sfruttano le capacità.
  
  
• 00:20:00 In questa sezione, il docente discute le prestazioni di Python, Java e C++ nel contesto della moltiplicazione di matrici. La conferenza dimostra che Python è troppo lento per la moltiplicazione di matrici di grandi dimensioni, con un tempo di esecuzione di circa 21.000 secondi, Java è più veloce e produce una velocità quasi nove volte maggiore rispetto a Python e C++ è il più veloce con un tempo di esecuzione di circa 1.100 secondi , che è due volte più veloce di Java e 18 volte più veloce di Python.
  
  
• 00:25:00 In questa sezione, l'oratore discute le differenze nelle prestazioni tra linguaggi interpretati come Python, linguaggi compilati come C e linguaggi come Java che vengono compilati in bytecode e poi interpretati. Gli interpreti come Python sono versatili ma lenti, mentre i compilatori come C sfruttano l'hardware e le istruzioni della macchina per ottimizzare le prestazioni. I compilatori JIT, come quelli utilizzati in Java, recuperano alcune prestazioni compilando solo i pezzi di codice eseguiti più frequentemente. Il relatore osserva che il modello di prestazioni di Python è difficile da comprendere, motivo per cui useranno C per i confronti delle prestazioni durante il corso. Tuttavia, ci sarà una conferenza ospite in cui discuteranno dell'ingegneria delle prestazioni in linguaggi gestiti come Python.
  
  
• 00:30:00 In questa sezione viene discussa l'importanza dell'ordine dei cicli per le prestazioni nella moltiplicazione di matrici. L'ordine dei loop influisce sulla località della cache che influisce sul tempo di esecuzione. Le matrici sono disposte in memoria in ordine di riga maggiore in C e in ordine di colonna maggiore in Fortran. Il modello di accesso per l'ordine ijk ha una buona località spaziale per C ma una scarsa località spaziale per B. Lo strumento "cachegrind" è utile per determinare i tassi di errore per il codice e anche semplici modifiche come la regolazione dei flag del compilatore possono migliorare le prestazioni.
  
  
• 00:35:00 In questa sezione, il relatore discute su come ottimizzare il codice per ottenere prestazioni migliori da una macchina. È importante scegliere un buon flag di ottimizzazione, come -O2 o -O3, ma a volte un flag di ottimizzazione inferiore può effettivamente ottimizzare meglio a seconda del codice. Inoltre, i processori multi-core possono essere utilizzati con loop paralleli utilizzando l'infrastruttura di seta, ottenendo un'accelerazione di quasi 18 volte su 18 core. L'oratore sottolinea che la parallelizzazione dei loop esterni è più efficace della parallelizzazione dei loop interni, che possono effettivamente rallentare il programma. Tuttavia, ci sono ancora fonti di opportunità per l'ottimizzazione, come i cache miss e il non utilizzo efficace delle istruzioni vettorializzate.
  
  
• 00:40:00 In questa sezione, il relatore discute su come gestire meglio i cache miss ristrutturando il calcolo per riutilizzare i dati nella cache il più possibile. Utilizzando uno schema di piastrellatura, le matrici vengono suddivise in sottomatrici più piccole e moltiplicate in blocchi per ridurre il numero di accessi alla memoria necessari. Il relatore spiega che è necessario un parametro di sintonia per determinare la dimensione delle sottomatrici e suggerisce che la sperimentazione è il modo migliore per trovare il valore ottimale. Attraverso questo approccio, il relatore dimostra che è possibile ridurre significativamente il numero di accessi alla memoria necessari per calcolare l'impronta della stessa dimensione, rendendo il calcolo più efficiente.
  
  
• 00:45:00 In questa sezione, il relatore discute i vantaggi dell'utilizzo del blocco, o piastrellatura, durante l'esecuzione della moltiplicazione di matrici, come un migliore utilizzo della cache e tempi di esecuzione più rapidi. Spiegano i diversi livelli di cache dei chip e come i programmatori possono utilizzare i parametri di ottimizzazione per ottimizzare il loro codice per ogni livello di cache. Tuttavia, il processo di messa a punto diventa più complesso con ogni livello di cache e il codice può diventare difficile da leggere e comprendere. Il relatore suggerisce un approccio divide et impera che utilizza la programmazione parallela per risolvere in modo ricorsivo sottoproblemi più piccoli. Sebbene questo metodo migliori l'utilizzo della cache, l'overhead delle chiamate di funzione rallenta il calcolo, evidenziando la necessità di un'ingegneria delle prestazioni intelligente.
  
  
• 00:50:00 In questa sezione, il relatore discute l'ottimizzazione della moltiplicazione di matrici utilizzando la tecnica divide et impera e la regolazione della soglia per l'utilizzo dell'algoritmo. Viene impostato un caso base per quando la soglia è al di sotto di un certo numero e l'algoritmo utilizza la normale moltiplicazione di matrici. Il valore migliore per il caso base è risultato essere 32, con un tempo di esecuzione di 1,3 secondi e il 12% delle prestazioni di picco. Inoltre, il relatore introduce il concetto di vettorizzazione utilizzando l'hardware vettoriale, che elabora i dati in un'unica istruzione, in più formati di dati. Il relatore delinea diversi modi per ottimizzare la vettorizzazione, incluso l'utilizzo di report di vettorizzazione, flag per architetture specifiche e il flag matematico veloce, che consente al compilatore di riordinare le associazioni. L'uso della matematica veloce e nativa dell'architettura si traduce in prestazioni raddoppiate quando si utilizza qualsiasi vettorizzatore del compilatore.
  
  
• 00:55:00 In questa sezione del video, l'oratore discute le varie dimensioni di bit utilizzate per i calcoli aritmetici, con 64 bit che è il più comune per i calcoli di algebra lineare. Menzionano anche che l'aritmetica di precisione inferiore può essere utilizzata per le applicazioni AI per migliorare le prestazioni. L'oratore prosegue parlando dell'utilizzo delle istruzioni vettoriali e degli intrinseci AVX, che forniscono prestazioni di picco fino al 41% e un'accelerazione di circa 50.000. Avvertono che miglioramenti delle prestazioni simili a quelli ottenuti nella moltiplicazione di matrici potrebbero non essere visti in altre aree, ma questo corso insegnerà agli studenti come ottenere miglioramenti sostanziali delle prestazioni da soli. Inoltre, il corso si concentrerà sull'elaborazione multi-core piuttosto che sulle GPU o su altre aree.

[MetaQuotes]

Lezione 2. Regole di Bentley per l'ottimizzazione del lavoro

2. Regole Bentley per l'ottimizzazione del lavoro

Questo video di YouTube discute varie tecniche di ottimizzazione per i programmi per computer. Vengono introdotte le regole Bentley per l'ottimizzazione del lavoro e le ottimizzazioni vengono raggruppate in strutture dati, cicli, logica e funzioni. Vengono discusse diverse tecniche come la codifica dei valori, l'aumento della struttura dei dati, il pre-calcolo, la memorizzazione nella cache e l'utilizzo di matrici sparse. Il relatore tocca anche i vantaggi dell'utilizzo di una rappresentazione a matrice sparsa per i grafici, l'ottimizzazione logica e l'ottimizzazione del rilevamento delle collisioni nei programmi di grafica. L'implementazione di queste tecniche di ottimizzazione aiuta a ridurre il tempo di esecuzione dei programmi, rendendoli più efficienti.

La seconda parte del video copre diverse categorie di tecniche di ottimizzazione, tra cui loop hoisting, l'uso di sentinelle nei loop, loop unrolling e fusion e function inlining. Il relatore sconsiglia l'ottimizzazione prematura e sottolinea l'importanza di mantenere la correttezza e utilizzare test di regressione. Il video delinea anche le Regole Bentley per l'ottimizzazione del lavoro, una guida in sei fasi per aumentare la produttività e raggiungere gli obiettivi in modo efficiente. Queste regole includono la definizione di obiettivi chiari, la suddivisione delle attività, la pianificazione e l'organizzazione, la definizione delle priorità delle attività, la riduzione al minimo delle distrazioni e la revisione e l'adeguamento regolari del proprio approccio.

• 00:00:00 In questa sezione, il docente introduce il concetto di ottimizzazione del lavoro nei programmi per computer e spiega come ridurre il lavoro di un programma può migliorarne le prestazioni. Parla anche delle regole Bentley per l'ottimizzazione del lavoro, dal nome di John Lewis Bentley, che ha scritto un libro sulla scrittura di programmi efficienti. Le ottimizzazioni sono raggruppate in quattro categorie: strutture dati, cicli, logica e funzioni, e il docente prevede di coprire tutte le 22 regole in una serie di mini lezioni durante il corso. Mentre ridurre il lavoro di un programma è una buona euristica per migliorarne il tempo di esecuzione, la natura complessa dell'hardware del computer significa che non sempre si traduce in una riduzione del tempo di esecuzione, quindi il docente tratterà anche delle ottimizzazioni specifiche dell'architettura più avanti nel corso.
  
  
• 00:05:00 In questa sezione del video, l'oratore discute il concetto di comprimere e codificare strutture di dati per memorizzare più di un valore di dati in una parola macchina e convertire i valori di dati in una rappresentazione che richiede meno bit. Riducendo il numero di cose da spostare in memoria, diventa una buona euristica per diminuire il tempo di esecuzione di un programma. L'oratore fornisce un esempio di codifica delle date per memorizzarle utilizzando meno bit per facilitare il recupero del mese, dell'anno o del giorno per una data specifica. Il relatore suggerisce di utilizzare le strutture dei campi di bit in C per memorizzare i dati strutturati, rendendoli più accessibili. Questa rappresentazione richiede un po' più di bit ma è molto più efficiente nell'accedere a valori di dati specifici all'interno della struttura.
  
  
• 00:10:00 In questa sezione, il video illustra tre tecniche di ottimizzazione. La prima tecnica consiste nel decidere se codificare i valori come numeri interi sequenziali o decomprimerli per un accesso più rapido. La seconda tecnica è l'aumento della struttura dati, in cui l'aggiunta di informazioni a una struttura dati può ottimizzare le operazioni comuni. Un esempio è l'aggiunta di un puntatore di coda a un elenco collegato singolarmente per rendere più efficiente l'aggiunta di due elenchi. La terza tecnica è il pre-calcolo, che consiste nell'eseguire i calcoli in anticipo per evitare di eseguire i calcoli in momenti mission-critical. Un esempio è l'utilizzo del triangolo di Pascal per precalcolare i coefficienti binomiali per velocizzare il programma che li utilizza.
  
  
• 00:15:00 In questa sezione, il relatore discute come pre-calcolare il triangolo di Pascal usando una formula ricorsiva e codice C. Spiegano che la formula ricorsiva comporta la chiamata della funzione di scelta e come pre-calcolare la tabella in fase di esecuzione utilizzando un ciclo. Inoltre, discutono su come inizializzare la tabella in fase di compilazione inserendo i valori della tabella nel codice sorgente, il che consente di risparmiare tempo durante l'esecuzione del programma. Infine, forniscono una tabella di esempio dei coefficienti binomiali fino a 10 a cui è possibile accedere durante l'esecuzione del programma.
  
  
• 00:20:00 In questa sezione, il relatore introduce il concetto di metaprogrammazione come un modo per evitare di digitare manualmente grandi tabelle di valori costanti in un programma. Scrivendo un programma che generi il codice necessario, il noioso compito può essere svolto automaticamente. L'oratore fornisce un frammento di codice Python come esempio. Viene inoltre introdotto l'argomento della memorizzazione nella cache, come tecnica per evitare la ripetizione di calcoli costosi memorizzando i risultati a cui si è avuto accesso di recente in una cache. L'esempio fornito calcola l'ipotenusa di un triangolo rettangolo utilizzando l'operatore radice quadrata, dove la cache pre-memorizza le ipotenuse precedenti, insieme ai valori di a e b. La funzione ipotenusa controlla innanzitutto se i valori di input corrispondono a quelli nella cache e, in tal caso, restituisce il valore memorizzato nella cache senza dover ricalcolare la radice quadrata.
  
  
• 00:25:00 In questa sezione, il relatore discute il concetto di memorizzazione nella cache per ottimizzare il lavoro in un programma. Memorizzando i valori comunemente calcolati in una cache, i programmi possono risparmiare tempo non dovendo calcolare ripetutamente gli stessi valori. Mentre l'hardware esegue anche la memorizzazione nella cache, anche il software può farlo, con una cache di dimensione 1.000 che memorizza i 1.000 valori calcolati più di recente come esempio. L'ottimizzazione può accelerare un programma di circa il 30% se gli stessi valori vengono calcolati ripetutamente. Il relatore introduce quindi l'idea di sfruttare la scarsità in un input per evitare di calcolare su elementi zero di quell'input, risparmiando così tempo di calcolo. Lo dimostrano con un esempio di moltiplicazione del vettore di matrici e introducono la struttura dei dati CSR (Compressed Sparse Row) che può accelerare la moltiplicazione delle matrici.
  
  
• 00:30:00 In questa sezione, il relatore discute come ottimizzare l'archiviazione e l'efficienza computazionale delle matrici sparse utilizzando il formato Compressed Sparse Row (CSR). Il formato CSR memorizza gli elementi diversi da zero di una matrice in tre array: l'array dei valori, l'array delle colonne e l'array delle righe. Il relatore spiega come calcolare la lunghezza di una riga e come eseguire la moltiplicazione matrice-vettore utilizzando il formato CSR. Il formato CSR può essere più efficiente in termini di spazio rispetto alla rappresentazione a matrice densa se il numero di elementi diversi da zero è significativamente inferiore a N^2. Tuttavia, per matrici relativamente dense, la rappresentazione della matrice densa potrebbe occupare meno spazio. L'oratore fornisce un esempio di codice per eseguire la moltiplicazione matrice-vettore utilizzando il formato CSR.
  
  
• 00:35:00 In questa sezione, l'istruttore discute i vantaggi dell'utilizzo di una matrice sparsa per rappresentare un grafico e come può essere utilizzata per eseguire algoritmi grafici classici come la ricerca in ampiezza e il PageRank in modo più efficiente. La rappresentazione del grafico sparso è costituita da due array: offset e spigoli, in cui i gradi di ciascun vertice possono essere ottenuti prendendo la differenza tra offset consecutivi. Il peso degli spigoli può anche essere memorizzato in un array separato o intercalato con gli spigoli per migliorare la località della cache. La sezione termina con una breve introduzione alle ottimizzazioni logiche, in particolare piegatura e propagazione costanti, che valuta le espressioni costanti durante la compilazione per ridurre il tempo di esecuzione.
  
  
• 00:40:00 In questa sezione del video, il relatore discute diverse tecniche di ottimizzazione per il codice, tra cui la piegatura e la propagazione costanti, l'eliminazione di sottoespressioni comuni e lo sfruttamento delle identità algebriche. Definendo le costanti in fase di compilazione, il compilatore può valutarle e risparmiare tempo durante il runtime. L'eliminazione comune delle sottoespressioni consente di evitare di calcolare più volte la stessa espressione memorizzando il risultato per un uso futuro. Lo sfruttamento delle identità algebriche implica la sostituzione di espressioni più costose con alternative più economiche. L'oratore sottolinea che mentre il compilatore è generalmente bravo a implementare queste ottimizzazioni, è comunque importante conoscerle per situazioni in cui il compilatore non lo fa automaticamente.
  
  
• 00:45:00 In questa sezione del video, il relatore discute due tecniche di ottimizzazione. Il primo è ridurre l'uso dell'operatore radice quadrata, che è computazionalmente costoso, utilizzando identità algebriche per evitare radici quadrate. La seconda tecnica di ottimizzazione è il cortocircuito, che comporta l'interruzione di una serie di test non appena il risultato è noto, nel caso in cui un array contenga numeri interi non negativi e la somma dei valori nell'array debba essere confrontata con un limite. L'ottimizzazione può eliminare la necessità di esaminare tutti gli elementi dell'array e può accelerare l'esecuzione del programma, ma dovrebbe essere usata con giudizio in base alla frequenza con cui il test può essere interrotto.
  
  
• 00:50:00 In questa sezione, il video discute il concetto di cortocircuito degli operatori logici e la loro utilità nell'ottimizzazione del codice. La doppia e commerciale e la doppia barra verticale sono operatori logici di cortocircuito che possono far risparmiare tempo e risorse valutando solo un lato dell'argomento. Inoltre, il video suggerisce di ordinare i test in base alla loro frequenza di successo e al costo di esecuzione. Questo approccio può trarre vantaggio dal cortocircuito per saltare test costosi se quelli meno costosi già falliscono. Infine, il video introduce l'idea di creare un percorso rapido utilizzando i controlli per uscire anticipatamente da un programma se un risultato è già noto. Un esempio di ciò è controllare se i riquadri di delimitazione di due palline si intersecano prima di controllare altre condizioni di collisione.
  
  
• 00:55:00 In questa sezione, Bentley illustra i modi per ottimizzare i test per il rilevamento delle collisioni nei programmi di grafica. Suggerisce un test del percorso rapido per determinare se i riquadri di delimitazione si intersecano prima di eseguire il test più costoso per la collisione. Questo test consiste nel controllare il valore assoluto della differenza su ciascuna coordinata e verificare se è maggiore della somma dei due raggi. Bentley osserva inoltre che la combinazione di test tramite un'unica istruzione switch o persino ricerche di tabelle può migliorare notevolmente le prestazioni. Nel complesso, queste ottimizzazioni possono essere vantaggiose per molte applicazioni e programmi di grafica.
  
  
• 01:00:00 In questa sezione, il video copre la terza categoria di ottimizzazioni, quella relativa ai loop. La prima ottimizzazione del ciclo discussa è il sollevamento, che comporta l'evitare di ricalcolare il codice invariante del ciclo ogni volta attraverso il corpo di un ciclo. Calcolando un'espressione una volta e memorizzandola in una variabile, anziché ricalcolarla a ogni iterazione, è possibile risparmiare tempo di esecuzione. La seconda ottimizzazione del ciclo è l'uso di sentinelle, speciali valori fittizi inseriti nelle strutture dati per semplificare la gestione delle condizioni al contorno e la logica di gestione dei test di uscita dal ciclo. Modificando il programma per utilizzare due voci aggiuntive nell'array, è possibile utilizzare una sentinella per eseguire solo un controllo in ogni iterazione del ciclo.
  
  
• 01:05:00 In questa sezione, il relatore discute due tecniche per l'ottimizzazione del codice: condizioni al contorno e loop unrolling. Per le condizioni al contorno, mostra come modificare un ciclo per gestire in modo efficiente il caso speciale in cui tutti gli elementi dell'array di input sono zero. Aggiungendo un elemento fittizio alla fine dell'array e verificando la presenza di un overflow, il codice può rilevare quando dovrebbe interrompersi. Per lo srotolamento del loop, ne spiega due tipi: completo e parziale. Mentre lo srotolamento completo del ciclo è raro a causa delle dimensioni del ciclo maggiori, lo srotolamento parziale del ciclo riduce il numero di iterazioni di un ciclo combinandone diverse in una, il che può migliorare le prestazioni riducendo il numero di istruzioni del flusso di controllo eseguite.
  
  
• 01:10:00 In questa sezione, l'istruttore discute lo srotolamento del ciclo e le ottimizzazioni della fusione del ciclo. Lo srotolamento del ciclo implica la combinazione di più iterazioni di un ciclo in una singola iterazione, riducendo così l'overhead del controllo del ciclo e consentendo più ottimizzazioni del compilatore. Tuttavia, lo srotolamento eccessivo può influire negativamente sulle prestazioni inquinando la cache delle istruzioni. La fusione di loop, d'altra parte, combina più loop sullo stesso intervallo di indici in un singolo loop, riducendo l'overhead di controllo del loop e migliorando la località della cache. L'istruttore discute anche dell'eliminazione delle iterazioni sprecate modificando i limiti del ciclo per evitare l'esecuzione di iterazioni del ciclo su corpi di ciclo vuoti.
  
  
• 01:15:00 In questa sezione, Bentley discute le ottimizzazioni delle funzioni, in particolare il concetto di inlining per evitare il sovraccarico di una chiamata di funzione. Dichiarando una funzione come static inline, il compilatore tenterà di sostituire una chiamata alla funzione con il corpo della funzione stessa, eliminando la necessità di una chiamata di funzione separata. Anche se le macro possono farlo, le funzioni inline sono più strutturate e valutano tutti i loro argomenti, evitando il rischio che una macro incolli un'espressione costosa più volte nel codice. Bentley sconsiglia l'ottimizzazione prematura e incoraggia gli sviluppatori a verificare innanzitutto che il loro programma sia corretto ea utilizzare i test di regressione per mantenerne la correttezza. Infine, sottolinea che molti livelli di ottimizzazione possono essere automatizzati dal compilatore e il controllo del codice assembly può rivelare tali ottimizzazioni.
  
  
• 01:20:00 In questa sezione, le regole Bentley per l'ottimizzazione del lavoro sono delineate in una serie di sei fasi. Queste regole consistono nello stabilire obiettivi chiari, suddividere le attività in parti più piccole, prendersi del tempo per pianificare e organizzare, dare priorità alle attività, ridurre al minimo le distrazioni e rivedere e adattare regolarmente il proprio approccio. Seguendo queste linee guida, puoi aumentare la tua produttività e raggiungere i tuoi obiettivi in modo più efficiente. Inoltre, incorporare queste strategie nella tua routine quotidiana può aiutarti a mantenere una forte etica del lavoro e rimanere concentrato sui tuoi obiettivi.

[MetaQuotes]

Lezione 3. Bit Hack

3. Bit hack

Questo video di YouTube copre una varietà di argomenti sulla manipolazione dei bit, tra cui la rappresentazione binaria, il complemento a due, gli operatori bit per bit, lo scambio di variabili senza una variabile temporanea e l'ottimizzazione del codice. Il video mostra vari trucchi come trovare il minimo di due numeri interi senza utilizzare istruzioni if-else e come scambiare due numeri interi senza utilizzare una variabile temporanea. L'oratore discute i rami imprevedibili e introduce un trucco di bit minimo senza ramo per quando i rami prevedibili non sono disponibili e mostra come i bit hack possono ottimizzare il codice sostituendo operazioni costose come la divisione con semplici operazioni bit a bit. Il video discute anche la sequenza di de Bruijn e la sua applicazione nella risoluzione di problemi come il problema N Queens.

La seconda parte discute la risoluzione del problema N Queens utilizzando vettori di bit e contando in modo efficiente il numero di bit 1 in una parola binaria. Il backtracking viene utilizzato per implementare il problema N Queens e i vettori di bit vengono utilizzati per rappresentare in modo efficiente il tabellone. Vengono descritti tre controlli per posizionare in modo sicuro una regina nel problema N Queens e viene presentato un metodo per contare il numero di bit 1 in una parola eliminando ricorsivamente il bit 1 meno significativo. Inoltre, viene discusso l'uso della ricerca nella tabella e della manipolazione del registro per contare il numero di 1 bit. Il video si conclude con una dimostrazione di un approccio divide et impera al conteggio di 1 bit che ha una performance proporzionale alla base logaritmica due della lunghezza della parola. Vengono inoltre fornite risorse per ulteriori apprendimenti.

• 00:00:00 In questa sezione impareremo la rappresentazione binaria delle parole e come calcolare i valori interi da esse. Impariamo anche la rappresentazione in complemento a due per i numeri interi con segno ei casi speciali della parola tutti zeri e tutti uno. Inoltre, vediamo un'identità importante per il complemento a 1 di X e la sua relazione con il negativo di X nella rappresentazione in complemento a due.
  
  
• 00:05:00 In questa sezione, il presentatore spiega il complemento a uno e come ottenere il negativo di un numero aggiungendo 1 al complemento a uno. Esamina anche l'uso dei numeri esadecimali per rappresentare grandi costanti binarie e fornisce una tabella per la conversione tra esadecimale e binario. Il video esamina quindi gli operatori bit per bit in C++ e mostra esempi di come usarli per operazioni logiche e, logiche o, esclusive o e di spostamento a sinistra ea destra.
  
  
• 00:10:00 In questa sezione, il video discute vari idiomi comuni che possono essere implementati utilizzando operatori bit a bit in C. Un esempio è l'impostazione o la cancellazione del bit case in una parola X utilizzando uno shift seguito da OR o NOT e un E, rispettivamente. Un altro esempio è l'estrazione di un campo di bit da una parola X generando una maschera con uno nelle posizioni dei bit desiderati e zeri altrove, quindi l'operazione AND della maschera con X e lo spostamento a destra dei bit estratti. Il video menziona anche che l'utilizzo di questi trucchi può essere particolarmente utile quando si lavora con dati compressi o codificati.
  
  
• 00:15:00 In questa sezione, il video illustra come scambiare due numeri interi senza utilizzare una variabile temporanea utilizzando alcuni trucchi. Il codice comporta l'impostazione di X uguale a X XOR Y, quindi Y uguale a X XOR Y e infine X uguale a X XOR Y. Funziona perché XOR è il proprio inverso e la prima riga genera una maschera con quelli in cui i bit in X e Y differiscono, che viene quindi utilizzato per capovolgere i bit in Y che sono diversi da X. Ciò consente lo scambio senza l'uso di una variabile temporanea. Il video sottolinea anche l'importanza del mascheramento per garantire la sicurezza quando si lavora con questi trucchi.
  
  
• 00:20:00 In questa sezione, l'oratore discute due hack. Il primo hack è un metodo per scambiare due variabili senza usare una variabile temporanea. L'hacking prevede l'uso di XOR e di una maschera per invertire i bit che differiscono tra le due variabili. Sebbene questo hack sia interessante, non è il modo più efficiente per scambiare variabili a causa dello scarso parallelismo del livello di istruzione. Il secondo hack è un modo per trovare il minimo di due numeri interi senza utilizzare istruzioni if-else, che possono causare problemi di prestazioni a causa di una previsione errata del ramo. Invece, il relatore mostra come utilizzare le operazioni bit a bit per confrontare gli interi e calcolare il minimo senza ramificazione.
  
  
• 00:25:00 In questa sezione, l'oratore discute l'ottimizzazione del codice e l'uso della parola chiave "restrict" in una subroutine che unisce due array ordinati. Il processo viene spiegato attraverso un esempio in cui due array verdi vengono uniti in un array blu. Viene anche discussa la prevedibilità di ciascun ramo nel codice, con il primo ramo prevedibile mentre il secondo è imprevedibile.
  
  
• 00:30:00 In questa sezione, il video discute i rami prevedibili e imprevedibili nella programmazione e introduce un trucco di bit minimo senza ramo come soluzione al problema del ramo imprevedibile. Il trucco consiste nell'usare una variabile chiamata "comp" per memorizzare il risultato del confronto tra il primo elemento di aeb e ottenere il minimo di aeb usando un trucco di bit. Quindi, il valore minimo viene inserito in C e il valore di A o B viene incrementato o decrementato in base al valore di "comp." Il video rileva che mentre il trucco potrebbe non funzionare in alcuni casi, è utile capire cosa sta facendo il compilatore e che molti bit hack per le parole possono estendersi a bit e word hack per i vettori, rendendo utile conoscere questi trucchi.
  
  
• 00:35:00 In questa sezione, il video discute i bit hack e la loro utilità nella programmazione. L'esempio fornito è un piccolo trucco per l'addizione modulare che consente operazioni più rapide senza utilizzare la divisione. Impostando Z alla somma di X e Y, e quindi controllando se è minore o maggiore di N, il programma può restituire Z se è all'interno dell'intervallo o il risultato di Z meno N per riportarlo nell'intervallo. Il programma utilizza una logica simile al minimo e ha un ramo imprevedibile che può provocare una previsione errata del ramo. Un altro esempio fornito è un modo per arrotondare un valore alla potenza di due più vicina utilizzando la manipolazione dei bit decrementando N, eseguendo bit a bit o operazioni con N spostato a destra di valori diversi e quindi incrementando alla fine.
  
  
• 00:40:00 In questa sezione del video, l'oratore discute i problemi di manipolazione di due bit. Il primo problema consiste nel trovare la più piccola potenza di due maggiore di un dato valore n. L'oratore spiega come ottenere ciò utilizzando la manipolazione dei bit e decrementando n se è già una potenza di due per garantire che sia impostato il logaritmo di n meno un bit. Il secondo problema riguarda il calcolo della maschera del meno significativo in una parola X, e l'oratore spiega come ottenere ciò impostando il risultato su X e utilizzando l'operazione bit per bit e con X negativo. L'oratore presenta anche il codice per trovare l'indice del bit moltiplicando X per una costante e cercando il risultato in una tabella. La sezione si conclude con l'oratore che esegue un trucco magico matematico che coinvolge la manipolazione dei bit.
  
  
• 00:45:00 In questa sezione, un video di YouTube mostra un gruppo che esegue un trucco magico con carte e campanello. L'esecutore afferma di leggere nella mente del pubblico e chiede loro di tagliare il mazzo di carte prima di distribuirle. L'esecutore predice il seme e il numero della carta di ogni persona e apparentemente ha successo. Attribuiscono le loro abilità all'indossare una "fantastica tutina" e un cappello magico, oltre a liberare l'aria con un campanello.
  
  
• 00:50:00 In questa sezione, apprendiamo la sequenza di de Bruyne e la sua correlazione con il calcolo del logaritmo in base 2 di una potenza di 2. La sequenza di de Bruyne è una sequenza di bit ciclica in cui ogni possibile stringa di bit di lunghezza K si verifica esattamente once come sottostringa nella sequenza. Usando una tabella di conversione, possiamo moltiplicare la costante di sequenza di de Bruyne per una potenza di 2 ed estrarre la sottostringa che appare all'inizio della sequenza per calcolare il logaritmo in base 2 della potenza di 2. Spostando a sinistra la sequenza e guardando sopra la posizione iniziale della sottostringa nella tabella di conversione, possiamo determinare il logaritmo in base 2 dell'intero con cui abbiamo iniziato, che risolve il trucco con le carte precedentemente dimostrato.
  
  
• 00:55:00 In questa sezione, l'oratore discute la sequenza di de Bruijn, che è una sequenza ciclica di un alfabeto binario che contiene ogni possibile stringa di n bit esattamente una volta. La sequenza può essere utilizzata per risolvere problemi come il problema N Queens e può essere generata utilizzando un trucco magico. L'oratore spiega anche come funziona il trucco del bit per determinare la posizione di una sottostringa di una sequenza di de Bruijn dopo uno spostamento a sinistra. Le prestazioni di questo trucco di bit sono limitate dalle prestazioni della moltiplicazione e della ricerca nella tabella, ma ora esiste un'istruzione hardware per calcolarlo.
  
  
• 01:00:00 In questa sezione, l'oratore discute il problema delle N regine, che consiste nel posizionare N regine su una scacchiera NxN in modo che non ci siano due regine che si minaccino a vicenda. Il problema viene spesso implementato utilizzando il backtracking, in cui le regine vengono posizionate riga per riga e il programma torna indietro quando non è possibile trovare una posizione valida. Vengono anche discusse diverse rappresentazioni della scheda, con la più compatta che è un insieme di tre vettori di bit. Il vettore down memorizza la presenza di regine in ogni colonna, il vettore diagonale sinistro memorizza la presenza di regine su ciascuna diagonale sinistra e il vettore diagonale destro memorizza la presenza di regine su ciascuna diagonale destra. L'utilizzo di vettori di bit consente un'implementazione più efficiente dell'algoritmo.
  
  
• 01:05:00 In questa sezione viene descritto il processo per verificare se una posizione è sicura per piazzare una regina in un problema con n-regine usando i vettori di bit. I tre controlli consistono nel controllare se c'è già una regina nella stessa riga, nella stessa colonna e nella stessa diagonale della posizione. Questo metodo è efficiente e garantisce che una regina possa essere posizionata in sicurezza se supera tutti e tre i controlli. Un altro problema discusso è il conteggio della popolazione, che comporta il conteggio del numero di bit 1 in una parola X. Il metodo presentato elimina ripetutamente il bit 1 meno significativo in X finché non diventa zero, e il numero di iterazioni richieste è proporzionale al numero di 1 bit in X.
  
  
• 01:10:00 In questa sezione, l'oratore discute l'uso della ricerca nella tabella per contare in modo efficiente il numero di 1 bit in una parola binaria. Il metodo di ricerca nella tabella comporta la creazione di una tabella di dimensione 256 che memorizza il numero di uno in ogni parola a 8 bit e quindi cerca il conteggio per ogni sottostringa a 8 bit nella parola binaria. Il relatore osserva che le prestazioni di questo metodo sono ostacolate dalle operazioni di memoria necessarie per accedere alla tabella. L'oratore prosegue presentando un terzo modo per contare il numero di bit 1 utilizzando i registri, dove creano maschere ed eseguono istruzioni specifiche che consentono loro di contare il numero di uno in una parola binaria senza accedere alla memoria. Il presentatore passa attraverso un esempio per spiegare come funziona questo metodo.
  
  
• 01:15:00 In questa sezione, l'oratore dimostra come contare il numero di 1 in una parola di input utilizzando un metodo parallelo divide et impera, in cui la performance è proporzionale alla base logaritmica due della lunghezza della parola, W. È ha sottolineato che la maggior parte delle macchine moderne ha un'istruzione di conteggio dei pop intrinseca che è più veloce di qualsiasi cosa possa essere codificata, accessibile tramite intrinseche del compilatore. Tuttavia, questo può rendere il codice meno portabile su macchine diverse. L'oratore fornisce alcune risorse per saperne di più sui trucchi, tra cui un sito Web, un libro di testo, un sito Web di programmazione degli scacchi e un libro intitolato Hacker's Delight.

[MetaQuotes]

Lezione 4. Linguaggio Assembly e Architettura del Computer

Lezione 4. Linguaggio Assembly e Architettura del Computer

Questo video fornisce una panoramica completa del linguaggio assembly e dell'architettura del computer. Il linguaggio assembly è un'interfaccia importante per l'ottimizzazione delle prestazioni del codice e la comprensione dell'architettura del computer è essenziale per padroneggiare il linguaggio assembly. Il relatore spiega la storia dell'architettura x86 64 e il suo sviluppo, i suoi registri chiave, i tipi di dati, le modalità di indirizzamento della memoria e l'architettura del set di istruzioni, inclusi stack, logica intera e binaria, logica booleana e subroutine. Discutono anche estensioni come estensione zero e segno e varie modalità di indirizzamento in linguaggio assembly. Inoltre, il video illustra i tipi di virgola mobile, i vettori e le unità vettoriali, le istruzioni tradizionali e SSE e le funzionalità di progettazione dell'architettura del computer come l'elaborazione superscalare, l'esecuzione fuori ordine e la previsione del ramo.

Il video copre anche diversi argomenti relativi al linguaggio assembly e all'architettura del computer. Uno dei temi centrali è il parallelismo a livello di istruzione (ILP) e gli stalli della pipeline, che sono causati da pericoli come le dipendenze dei dati. Il relatore discute le dipendenze dei dati veri, anti e di output e come i processori superscalari possono sfruttare più parallelismo nell'hardware per eseguire più istruzioni alla volta. Tuttavia, per evitare pericoli, gli architetti hanno implementato strategie come la ridenominazione e il riordino, nonché l'esecuzione speculativa per indovinare l'esito di un ramo ed eseguirlo in anticipo. Il relatore incoraggia il pubblico a comprendere questi metodi per comprendere meglio le ottimizzazioni del software.

• 00:00:00 In questa sezione, l'istruttore parla del linguaggio assembly e dell'architettura del computer, che spesso non sono trattati nei moderni corsi di software. La comprensione di questi concetti è necessaria per ottimizzare le prestazioni del codice e il linguaggio assembly è l'interfaccia migliore per farlo. Il processo di compilazione del codice prevede diverse fasi, tra cui la pre-elaborazione, la compilazione, l'assemblaggio e il collegamento. Il linguaggio assembly è una struttura mnemonica del codice macchina che lo rende più leggibile dall'uomo e l'eseguibile finale viene prodotto attraverso una fase di collegamento utilizzando il comando LD.
  
  
• 00:05:00 In questa sezione, l'oratore spiega che l'assembly e il codice macchina sono molto simili nella struttura, con i codici OP nell'assembly corrispondenti a specifici schemi di bit nel codice macchina. L'oratore introduce il programma ABS, che può produrre un disassemblaggio del codice macchina, rivelando il codice assembly mnemonico e leggibile dall'uomo. L'oratore discute quindi diversi motivi per cui qualcuno potrebbe voler esaminare il codice assembly, inclusa la rivelazione di ciò che il compilatore ha fatto e non ha fatto, il debug degli errori del compilatore e il reverse engineering di un programma senza accesso alla sua fonte.
  
  
• 00:10:00 In questa sezione, il relatore spiega le aspettative per la classe, che includono la comprensione di come un compilatore implementa i costrutti linguistici con istruzioni x86, la capacità di leggere il linguaggio assembly x86 e la comprensione delle implicazioni prestazionali dei modelli di assembly comuni. Gli studenti dovrebbero anche essere in grado di scrivere codice da zero, se necessario, e acquisire padronanza a un livello in cui ciò sia fattibile. L'oratore si tuffa quindi nell'architettura del set di istruzioni x86 64, inclusi registri, istruzioni, tipi di dati e modalità di indirizzamento della memoria. I registri chiave includono i registri di uso generale e il registro dei flag, che tiene traccia delle operazioni aritmetiche e dei riporti. Il puntatore all'istruzione guida l'hardware attraverso la sequenza di istruzioni in un programma in linguaggio assembly.
  
  
• 00:15:00 In questa sezione, il relatore discute la storia dell'architettura x86 64 e il suo sviluppo da word machine a 16 bit con memoria limitata a parole più ampie per l'indicizzazione man mano che si rende disponibile più memoria. Il relatore spiega anche l'aggiunta di registri vettoriali come i registri xmm e AVX per la vettorizzazione e come vengono utilizzati. Toccano anche l'argomento dei registri di uso generale e come i loro scopi funzionali sono cambiati in modo significativo nel tempo, ma i loro nomi sono rimasti per ragioni storiche. Inoltre, l'oratore spiega come alcuni registri sono aliasati alla stessa cosa per la metà inferiore e superiore della parola breve, delle parole a 32 bit o a 64 bit.
  
  
• 00:20:00 In questa sezione, il relatore spiega le basi del linguaggio assembly x86 64 e come funziona. I registri hanno nomi diversi a seconda della parte del registro a cui si accede e alcuni hanno scopi specifici come RSP utilizzato come puntatore dello stack. Il formato di un codice istruzione x86 64 deve avere un codice operativo e un elenco di operandi, solitamente con 0-3 operandi che possono essere origini o destinazioni. L'oratore spiega la differenza tra la sintassi AT&T e la sintassi Intel per fare riferimento alle operazioni e fornisce un elenco di codici operativi comuni come "mossa" e "mossa condizionale". Inoltre, il relatore spiega l'importanza di estendere il segno quando si passa da un registro di valore a 32 bit a un registro a 64 bit.
  
  
• 00:25:00 In questa sezione, il relatore discute i vari tipi di istruzioni in linguaggio assembly, comprese le istruzioni per stack, l'aritmetica dei numeri interi, la logica binaria, la logica booleana, i salti e le subroutine. I codici operativi possono essere aumentati con un suffisso che descrive il tipo di dati dell'operazione o un codice di condizione. Ad esempio, uno spostamento con un "cue" indica che i dati spostati sono una quad word, composta da 8 byte o 64 bit. Vengono inoltre discussi i tipi di dati x86 64 ei relativi suffissi di assemblaggio e vengono forniti esempi per illustrare come funziona l'estensione del segno. La presenza o l'assenza di determinati codici operativi e mnemonici nel linguaggio assembly può creare confusione, ma il compilatore deve comprendere queste istruzioni per eseguire correttamente il programma.
  
  
• 00:30:00 In questa sezione, l'oratore discute le estensioni come l'estensione zero e l'estensione del segno che si verificano quando si spostano operazioni a 32 bit in operazioni a 64 bit. Menzionano anche come il set di istruzioni Intel possa diventare più complicato con l'aggiunta di nuove istruzioni. L'oratore prosegue spiegando i diversi codici di condizione utilizzati nei salti condizionati e nei movimenti condizionati e i flag che vengono utilizzati con essi, come il flag zero e il flag overflow. Viene anche discusso il motivo per cui alcuni codici di condizione controllano il flag zero.
  
  
• 00:35:00 In questa sezione, il relatore discute le diverse modalità di indirizzamento diretto e indiretto nel linguaggio assembly. Le modalità di indirizzamento diretto includono l'immediato, la memoria diretta e l'utilizzo di un registro. Le modalità di indirizzamento indiretto del registro e indicizzato del registro consentono di accedere alla memoria fornendo l'indirizzo in un registro o compensando l'indirizzo. Il relatore osserva che l'accesso alla memoria può essere lento e costoso, quindi è importante memorizzare i valori nei registri quando possibile per accelerare il processo. Menzionano anche l'importanza della memorizzazione nella cache nell'ottimizzazione dell'accesso alla memoria.
  
  
• 00:40:00 In questa sezione, il video discute l'uso dell'indicizzazione relativa del puntatore, in cui il puntatore dell'istruzione viene utilizzato per indicizzare i dati piuttosto che un registro generico. Viene inoltre introdotto il metodo di indirizzamento dello spostamento della scala dell'indice di base, che è un'istruzione complicata che supporta l'indicizzazione delicata da un puntatore di base. Il video fornisce una panoramica di alcuni idiomi del linguaggio assembly, incluso il codice operativo XOR, che viene utilizzato per azzerare i registri, e il codice operativo di test, che calcola il bit per bit e di due valori e conserva i flag di registro. Infine, il video tocca le istruzioni di salto e le etichette, che consentono il flusso di controllo nel codice.
  
  
• 00:45:00 In questa sezione, il video discute il linguaggio assembly e l'architettura del computer, inclusi vari set di istruzioni e la storia della virgola mobile. I set di istruzioni x86, inclusi x87 e SSE, supportano l'aritmetica in virgola mobile scalare a precisione singola e doppia e le istruzioni vettoriali. Le istruzioni SSE sono generalmente preferite dai compilatori rispetto a x87 per la loro semplicità di compilazione e ottimizzazione. Viene inoltre spiegato lo scopo dell'utilizzo delle istruzioni no operation (nop) nell'assieme, come l'ottimizzazione dell'allineamento.
  
  
• 00:50:00 In questa sezione, il relatore discute i tipi di virgola mobile, i vettori e le unità vettoriali utilizzate nell'architettura dei computer. L'oratore spiega che il modo in cui funzionano le unità vettoriali è che il processore invia istruzioni a tutte le unità vettoriali, ciascuna delle quali è chiamata corsia. Le corsie contengono l'aritmetica dei numeri interi o in virgola mobile e operano tutte in blocco, nel senso che fanno tutte la stessa cosa. Possono eseguire più operazioni contemporaneamente e tutto ciò può essere fatto con una singola istruzione. L'oratore spiega che alcune architetture richiedono l'allineamento degli operandi vettoriali, mentre altre possono spostare i vettori in memoria, il che si traduce in una differenza di prestazioni tra i due. Inoltre, ci sono architetture che supportano operazioni cross-lane, come permuting, shuffling e scatter-gather.
  
  
• 00:55:00 In questa sezione, il relatore discute le differenze tra le istruzioni tradizionali e SSE e come possono essere utilizzate. Menzionano anche il trucco dell'aliasing in cui ymm registra i registri alias xmm e li estende a 512 bit con avx-512. Passano quindi a una discussione sull'architettura del computer, in particolare sulla differenza tra una pipeline a cinque stadi e un processore moderno con da 14 a 19 stadi della pipeline. Le funzionalità di progettazione che discutono includono il vettore o l'hardware I, l'elaborazione superscalare, l'esecuzione fuori ordine e la previsione del ramo, ma menzionano che non approfondiranno l'esecuzione fuori ordine a causa di vincoli di tempo.
  
  
• 01:00:00 In questa sezione del video, l'istruttore discute il parallelismo a livello di istruzione (ILP) e gli stalli della pipeline. ILP implica la ricerca di opportunità per eseguire più istruzioni contemporaneamente al fine di migliorare il throughput. Tuttavia, gli stalli della pipeline possono verificarsi quando un'istruzione non può essere eseguita a causa di un pericolo, come un pericolo strutturale, un pericolo per i dati o un pericolo per il controllo, con i rischi per i dati che sono i più comuni. Una vera dipendenza si verifica quando un'istruzione legge dopo una dipendenza da scrittura, mentre un'antidipendenza si verifica quando un'istruzione desidera scrivere in una posizione ma deve attendere che l'istruzione precedente abbia letto il valore. Il compilatore tenta di ridurre gli stalli della pipeline ottimizzando il codice per evitare pericoli.
  
  
• 01:05:00 In questa sezione viene discusso il concetto di dipendenze dei dati nel linguaggio assembly. Esistono tre tipi di dipendenze dei dati: true, anti e output. Le operazioni aritmetiche, specialmente quelle complesse come l'aritmetica in virgola mobile, hanno una latenza più lunga e richiedono unità funzionali separate nel processore, a volte con registri separati. Per aumentare il parallelismo a livello di istruzione, gli architetti hanno implementato tecniche come l'emissione di più istruzioni per ciclo per sfruttare più parallelismo nell'hardware.
  
  
• 01:10:00 In questa sezione, il video spiega come i processori superscalari possono eseguire più istruzioni alla volta, usando l'esempio di Haswell che suddivide le istruzioni in operazioni più semplici chiamate micro operazioni ed emette fino a quattro micro operazioni per ciclo. Il video descrive quindi le strategie per liberare i processori dall'esecuzione delle istruzioni in ordine, incluso il bypass e la ridenominazione dei registri, che consentono l'esecuzione fuori ordine delle istruzioni non dipendenti, con tempi di elaborazione più rapidi. Queste strategie richiedono di tenere traccia delle dipendenze e di eseguire il codice in modo da evitare pericoli come le dipendenze dei dati.
  
  
• 01:15:00 In questa sezione, il relatore discute la ridenominazione e il riordino, che sono due metodi importanti utilizzati nei processori moderni per evitare rischi per i dati. L'oratore parla anche dell'esecuzione speculativa, che viene utilizzata nella previsione del ramo per indovinare l'esito di un ramo ed eseguirlo in anticipo, per evitare lo stallo. Tuttavia, se l'ipotesi è sbagliata, l'annullamento del calcolo costerà dai 15 ai 20 cicli. L'oratore menziona brevemente come funzionano i predittori di ramo, ma sottolinea che è complicato e richiede ulteriori studi. Nonostante la fine affrettata, l'oratore incoraggia il pubblico a comprendere i vari metodi, che aiuteranno a capire perché certe ottimizzazioni del software funzionano e non funzionano.

[MetaQuotes]

Lezione 5. C all'Assemblea

Lezione 5. C all'Assemblea

In questa parte del video viene discussa l'importanza di comprendere il linguaggio C in assembly, insieme a come il codice C viene implementato nel linguaggio assembly utilizzando un compilatore. L'attenzione si concentra in particolare su come LLVM IR viene tradotto in assembly nella convenzione di chiamata Linux x86 64. Il relatore spiega i componenti di base di LLVM IR e come i costrutti nel linguaggio di programmazione C vengono tradotti in LLVM IR. Il video copre anche il layout della memoria virtuale, il problema del coordinamento delle chiamate di funzione tra più funzioni e l'uso di due puntatori, BP e SP, da parte della convenzione di chiamata Linux x86 64 per gestire tutti i frame dello stack.

Il video spiega anche le strategie per mantenere gli stati dei registri nella programmazione da C a Assembly, come il salvataggio dei registri come salvataggio del chiamante o salvataggio del chiamato e in che modo la convenzione di chiamata x86 evita lo spreco di lavoro. Copre il modo in cui le chiamate di funzione funzionano in C e in assembly, discutendo il processo di salvataggio di argomenti e variabili locali nello stack, nonché l'ottimizzazione comune dell'utilizzo del puntatore dello stack invece del puntatore di base. Il video mostra anche il processo di compilazione di LV miR fino al codice assembly, discutendo il prologo della funzione, il salvataggio dei registri, le condizioni di gestione e la conversione del codice C in codice assembly utilizzando un grafico del flusso di controllo. Infine, parla della funzione epilogo utilizzata per ripristinare i registri prima di restituire i risultati.

• 00:00:00 In questa sezione del video, TB Shuttle discute l'importanza della comprensione del linguaggio C per l'assembly. Osserva che il linguaggio assembly fornisce una precisione maggiore rispetto al codice C e può rivelare dettagli su un programma che non sono ovvi dal codice C. Osservare l'assembly può anche consentire agli sviluppatori di determinare cosa ha fatto o non ha fatto il compilatore durante l'ottimizzazione di un programma. Inoltre, possono verificarsi bug che creerebbero solo comportamenti imprevisti durante l'ottimizzazione del codice a determinati livelli, rendendo difficile individuare questi bug. Infine, la comprensione dell'assembly può consentire agli sviluppatori di modificare manualmente il codice assembly o di decodificare il codice.
  
  
• 00:05:00 In questa sezione, il video discute come il codice C viene implementato in linguaggio assembly attraverso l'uso di un compilatore che deve prendere decisioni complesse riguardo a quali istruzioni assembly usare, come implementare condizionali e cicli C e come coordinare le chiamate di funzioni. Per comprendere il processo di traduzione, il video introduce LVM IR, che è un assembly semplificato che il compilatore utilizza per ragionare sul programma. Il video spiega quindi come i costrutti nel linguaggio di programmazione C, come funzioni, condizionali e cicli, vengono tradotti in LVM IR. La sezione termina con una breve menzione degli attributi IR di LVM.
  
  
• 00:10:00 In questa sezione, l'attenzione è rivolta al processo di traduzione di LLVM ir in assembly, in particolare nella convenzione di chiamata Linux x86 64. Il relatore fornisce una breve introduzione su LLVM ir, spiegando i suoi componenti di base di funzioni, istruzioni e registri, che assomigliano a una versione più semplice dell'assembly. I registri ir LLVM sono simili alle variabili c e si distinguono per i loro nomi, e ogni funzione ha i propri nomi di registro locale. Il presentatore evidenzia i registri in un frammento di codice di esempio e osserva che la sintassi per i registri viene dirottata quando si fa riferimento a diversi blocchi di base in LLVM. Il discorso si conclude con un caso di studio su come funziona questo processo per un semplice codice per calcolare i numeri di Fibonacci.
  
  
• 00:15:00 In questa sezione, l'oratore spiega la sintassi delle istruzioni LV Mir, che comprende un nome di registro, un simbolo di uguale, un codice operativo e un elenco di operandi. Mentre alcune istruzioni restituiscono un valore che viene memorizzato in un registro locale, altre no. Il set di istruzioni LV Mir è più piccolo di quello di x86 poiché contiene solo poche istruzioni per movimenti di dati, operazioni aritmetiche e logiche e flusso di controllo. In LV Mir, tutto è esposto come tipi, che includono numeri interi (con un numero definito di bit), tipi a virgola mobile, tipi di puntatori, tipi di vettori e tipi di etichette per i blocchi di base. L'oratore menziona anche che le operazioni vettoriali LV Mir non sembrano SSE o AVX, ma piuttosto come operazioni ordinarie che funzionano su un tipo vettoriale.
  
  
• 00:20:00 In questa sezione, il video illustra come le sequenze di operazioni nel codice C vengono tradotte in LLVM IR e le regole empiriche per interpretare il codice in IR. L'estratto spiega anche come LLVM IR gestisce i tipi primitivi e aggregati, come array e struct, e mostra esempi di come l'accesso agli elementi in un array implica il calcolo degli indirizzi in memoria. Inoltre, il video spiega come le funzioni C vengono tradotte in LLVM IR, con le istruzioni return corrispondenti in entrambe le lingue.
  
  
• 00:25:00 In questa sezione, il video spiega come funzioni e parametri in C si traducono in LV Mir. Le funzioni in LV Mir sono simili alle funzioni in C, ma i parametri C diventano liste di parametri in LV Mir. Tuttavia, la lettura di LV Mir può essere impegnativa poiché i registri non sono ben denominati, il che rende difficile la decifrazione. Il video discute anche i blocchi di base in LV Mir, che sono blocchi di codice partizionati in base alle istruzioni del flusso di controllo. Le connessioni tra i blocchi di base si basano su archi indotti da istruzioni di diramazione. Infine, il video tocca i condizionali in LV Mir, dove le istruzioni if-then-else diventano istruzioni di salto condizionale che inducono blocchi di base e controllano i bordi del flusso.
  
  
• 00:30:00 In questa sezione, il video spiega come funzionano le operazioni condizionali e le diramazioni in LLVM IR. Il processo inizia con un confronto tra un valore letterale e un valore memorizzato in un registro, che crea un numero intero a un bit o un risultato booleano. Questo risultato viene quindi passato a un'azione di ramo condizionale insieme a due etichette di blocchi di base che indicano dove andare se il predicato è vero o falso. Se è presente un salto incondizionato con un operando, il risultato è un salto diretto a un determinato blocco base. Il video mostra anche come creare una forma a rombo nel grafico del flusso di controllo ogni volta che è presente un'istruzione condizionale e fornisce un esempio di ciclo scritto in codice C.
  
  
• 00:35:00 In questa sezione, il video discute i componenti di un loop C, che includono il corpo del loop e il controllo del loop. Il corpo del ciclo viene eseguito a ogni iterazione, mentre il controllo del ciclo gestisce tutte le iterazioni del ciclo. AC loop produce un modello di looping nel grafico del flusso di controllo, che a sua volta crea una struttura ad anello in LLVM ir. Il video quindi analizza il codice ir LLVM per il controllo del loop, dove c'è una strana istruzione fie che si presenta comunemente quando si ha a che fare con i loop. L'istruzione fie cerca di risolvere un problema con la rappresentazione LLVM del codice, dove I è rappresentato da un intero gruppo di registri diversi, rendendo poco chiaro dove sono effettivamente andato.
  
  
• 00:40:00 In questa sezione, il video discute la mappatura della variabile di induzione in un ciclo in varie posizioni in LLVM, cosa che fa a causa dei valori variabili della variabile attraverso le iterazioni del ciclo. Ciò porta all'invariante di "assegnazione singola statica" in LLVM secondo cui ogni istruzione definisce il valore di un registro solo una volta, il che pone un problema per le variabili di induzione. L'istruzione "phi" risolve questo problema definendo un valore di registro che dipende da come il flusso di controllo si unisce al punto di ingresso di un loop. Il video illustra anche gli attributi in LLVM e come possono fornire informazioni aggiuntive per i costrutti LLVM, come l'attributo NSW allegato all'istruzione "add".
  
  
• 00:45:00 In questa sezione del video, l'attenzione si concentra su LLVM IR, che è simile all'assemblaggio ma più semplice in molti modi, poiché tutti i valori calcolati sono memorizzati in registri che sono come normali variabili C. LLVM IR utilizza il paradigma di assegnazione singola statica in cui ogni variabile è scritta da al massimo un'istruzione. Il video descrive come tradurre il codice C in LLVM IR e quindi in assembly, con alcune complessità aggiuntive nel processo. Il compilatore seleziona le effettive istruzioni di assemblaggio necessarie per le operazioni IR LLVM, decide quali registri generici vengono utilizzati e coordina le chiamate di funzione tra diversi file sorgente e librerie binarie. La discussione passa quindi alla convenzione di chiamata Linux x86 64.
  
  
• 00:50:00 In questa sezione viene discusso il layout della memoria virtuale per un programma. La memoria virtuale è divisa in segmenti, come i segmenti stack e heap, che sono organizzati con l'uso di direttive assembler nel codice assembly. Inoltre, vengono discussi diversi tipi di direttive di archiviazione, come la direttiva space e il segmento lungo, che allocano memoria e archiviano valori. L'attenzione viene quindi rivolta al segmento dello stack in cui vengono archiviati i dati per gestire le chiamate e i ritorni di funzione, che include la memorizzazione di variabili locali, argomenti della funzione, l'indirizzo di ritorno e possibilmente risultati intermedi.
  
  
• 00:55:00 In questa sezione del video, il relatore discute il problema del coordinamento delle chiamate di funzione tra più funzioni, alcune delle quali possono provenire da diversi file o librerie. Per garantire che tutte le funzioni funzionino bene insieme, è stata stabilita una convenzione di chiamata a cui tutte le funzioni devono obbedire. La convenzione di chiamata Linux x86 64 utilizza due puntatori, BP e SP, per gestire tutti i frame dello stack per ogni istanza di funzione. Quando viene eseguita un'istruzione di chiamata, il valore corrente dell'IP viene inserito nello stack come indirizzo di ritorno e l'istruzione di chiamata salta all'indirizzo di una funzione nella memoria del programma. L'istruzione return annulla le operazioni dell'istruzione call ed estrae l'indirizzo di ritorno dallo stack per tornare all'esecuzione del chiamante. Per gestire il problema di più funzioni che desiderano utilizzare lo stesso
  registers, la convenzione di chiamata dettaglia le regole per quali registri ogni funzione può usare e come devono preservare quei registri attraverso le chiamate di funzione.
  
  
• 01:00:00 In questa sezione, il video illustra le strategie per mantenere gli stati dei registri quando si opera con diverse funzioni nella programmazione da C a Assembly. Menziona i due metodi che possono essere utilizzati, uno in cui il chiamante salva lo stato del registro prima di richiamare una chiamata e l'altro in cui il chiamato salva tutto lo stato del registro. La convenzione di chiamata x86 coinvolge entrambi, specificando alcuni registri come callee-save e altri come caller-save per evitare sprechi di lavoro. Il video esplora anche come è organizzata la memoria dello stack e lo stack si riduce. Infine, discute il coordinamento del modo in cui le funzioni utilizzeranno parti sovrapposte della memoria dello stack.
  
  
• 01:05:00 In questa sezione, il video illustra come funziona una chiamata di funzione in C e assembly. Prima di chiamare la funzione C, la funzione B inserisce argomenti non di registro per la funzione C su un blocco di collegamento riservato nella propria memoria stack sotto le variabili locali. Accederà a quegli argomenti con offset negativi. Quando la funzione C si avvia, esegue un prologo di funzione che salva il puntatore di base per lo stack frame di B e imposta BP uguale a SP perché sta entrando in un nuovo frame. Quindi alloca lo spazio nello stack per le proprie variabili locali e lo spazio che B utilizzerà per tutti i blocchi di collegamento che crea per i suoi chiamanti o per le cose che chiama. Il video menziona anche un'ottimizzazione comune in cui il compilatore potrebbe sbarazzarsi di BP ed eseguire tutta l'indicizzazione in base al puntatore dello stack RSP per ottenere un registro più generico.
  
  
• 01:10:00 In questa sezione, l'istruttore guida il pubblico attraverso il processo di compilazione di LV miR fino al codice assembly. Il primo passaggio prevede la definizione della funzione "fib" come funzione accessibile a livello globale utilizzando alcune direttive dell'assembler come la direttiva fib globale e l'allineamento. Quindi, il prologo della funzione viene salvato con una coda push di var BP e una coda mob di RSP rbp. Il codice assembly inserisce anche un paio di registri nello stack, che sono registri Kali-save, prima di spostare l'argomento nella funzione, RTI, e lo sposta nel registro RBX. Infine, viene valutata un'istruzione di confronto per verificare se il valore di N è minore di due e, in tal caso, restituisce il valore di input. Altrimenti, passa attraverso un codice lineare per calcolare fib di n meno uno e fib di n meno due, sommarli e restituire quel risultato.
  
  
• 01:15:00 In questa sezione, il video discute i salti condizionali e i vari comportamenti che si verificano successivamente nel codice a seconda dei risultati del confronto. L'istruzione JGE passa all'etichetta per il lato falso dell'operazione di ramo LLVM quando n è maggiore o uguale a 2, mentre le operazioni corrispondono al lato vero dell'operazione quando n è minore di 2. L'istruzione LEA è utilizzata per calcolo dell'indirizzo, mentre l'operazione di spostamento salva il risultato della chiamata di funzione in R14. Il prossimo set di istruzioni calcola il valore di n-2, lo nasconde in RDI e quindi chiama fib su n-2, restituendo il risultato nella nostra AX. Infine, l'operazione aggiunge R14 al nostro AX.
  
  
• 01:20:00 In questa sezione, il video discute la conversione dal codice C al codice assembly. Il relatore spiega che il processo utilizza un grafico del flusso di controllo, composto da blocchi di base collegati da bordi del flusso di controllo, per rappresentare il codice. Menzionano anche la complessità della gestione delle convenzioni di chiamata nel codice assembly. La funzione epilogue viene utilizzata per ripristinare i registri prima di qualsiasi cosa nello stack frame, prima di restituire il risultato. Il video si conclude riassumendo i principali argomenti trattati in tutta la sezione.

[MetaQuotes]

Lezione 6. Programmazione multicore

Lezione 6. Programmazione multicore

Questa lezione video discute la programmazione multi-core e l'emergere di processori multi-core a causa della legge di Moore e della fine del ridimensionamento delle frequenze di clock. Il relatore spiega il problema della densità di potenza affrontato dai processori e come ha portato all'aggiunta di più core ai chip per stare al passo con la legge di Moore. La lezione copre anche le basi dei protocolli di coerenza della cache nell'hardware della memoria condivisa e piattaforme di concorrenza come Pthreads, TBB, OpenMP e Silk che forniscono astrazioni per la programmazione parallela. I pro ei contro di ogni piattaforma sono discussi e dimostrati con esempi di implementazione di programmi Fibonacci. Il video offre una panoramica completa della programmazione multi-core e delle sfide e delle soluzioni affrontate dai programmatori.

Il video copre anche vari aspetti di Silk, uno strumento di astrazione per gestire l'elaborazione parallela. Il relatore discute argomenti come la seta nidificata per i loop, la generazione di codice assembly, la riduzione mediante riduttori, lo scheduler e l'ottimizzazione delle prestazioni. Forniscono inoltre una panoramica dell'ecosistema Silk e degli strumenti correlati come Silk Sanitizer e Silk Scale rispettivamente per il debug e l'analisi della scalabilità. La conclusione principale è che scrivere programmi paralleli per processori multicore può essere impegnativo, ma Silk semplifica il processo gestendo attività complesse in modo efficiente, offrendo ai programmatori un maggiore controllo sull'esecuzione del loro codice.

• 00:00:00 In questa sezione, l'istruttore discute la programmazione multi-core e le ragioni dell'emergere di processori multi-core. Con l'avvento della legge di Moore, che afferma che il numero di transistor che possono stare su un chip raddoppia ogni due anni, e la fine del ridimensionamento delle frequenze di clock tra il 2004 e il 2005, i fornitori di semiconduttori hanno iniziato a produrre chip con più core del processore. Ciò era dovuto al fatto che non era più possibile aumentare la frequenza dei singoli core su un chip, rendendo necessario il passaggio a un modello di progettazione che consentisse l'elaborazione parallela. L'istruttore chiarisce anche la relazione tra il numero di transistor su un chip e la frequenza massima del processore.
  
  
• 00:05:00 In questa sezione, il relatore discute il problema della densità di potenza affrontato dai processori, dove l'aumento della frequenza di clock provoca un aumento esponenziale della densità di potenza. Ciò ha portato all'aggiunta di più core ai chip per tenere il passo con la legge di Moore e non superare i limiti di densità di potenza. Il relatore introduce quindi l'architettura multi-core astratta, nota come chip multiprocessore, e delinea le lezioni sulle sfide hardware e sulle soluzioni software per programmare programmi paralleli su macchine multi-core utilizzando diverse piattaforme di concorrenza come thread P, thread winAPI, threading Intel elementi costitutivi, openmp e così via.
  
  
• 00:10:00 In questa sezione, il relatore spiega come funzionano le cache nella programmazione multicore. Quando un processore carica un valore nella sua cache dalla memoria principale, manterrà tale valore nella cache nel caso in cui debba accedervi nuovamente in futuro. Se un altro processore vuole caricare lo stesso valore, può anche farlo passare attraverso la cache del primo processore invece di andare fino alla memoria principale. Tuttavia, si verifica un problema quando un processore aggiorna il valore nella propria cache, rendendo obsoleto il valore nella cache di un altro processore. Il protocollo MSI è una soluzione di base a questo problema, che etichetta le righe della cache con tre possibili stati (M, S e I) per garantire la coerenza tra le cache.
  
  
• 00:15:00 In questa sezione, la conferenza discute le basi dei protocolli di coerenza della cache nell'hardware della memoria condivisa, in particolare come le modifiche a una riga della cache nella cache di un processore possono invalidare le copie della stessa riga nelle altre cache. La conferenza introduce un protocollo semplice e spiega come esistono nella pratica altri protocolli più complessi. L'hardware è responsabile della gestione dei conflitti quando più processori modificano la stessa riga della cache, ma ciò può provocare una "tempesta di invalidazioni" e rallentare le prestazioni. La conferenza rileva inoltre che le piattaforme di concorrenza possono astrarre queste complessità e aiutare con la sincronizzazione e la comunicazione nella programmazione parallela.
  
  
• 00:20:00 In questa sezione, il relatore discute diverse piattaforme di concorrenza utilizzando l'esempio dei numeri di Fibonacci. Il programma Fibonacci è implementato utilizzando un algoritmo ricorsivo che calcola i numeri di Fibonacci più volte, rendendolo un algoritmo scadente. Le due chiamate ricorsive possono essere parallelizzate in quanto sono calcoli completamente indipendenti. Pthreads, un'API standard per il threading, può essere utilizzata per implementare questa parallelizzazione.
  
  
• 00:25:00 In questa sezione, il relatore discute Pthreads, una libreria di funzioni che abilitano la concorrenza nella programmazione. Pthreads fornisce una piattaforma di concorrenza fai-da-te, in quanto consente di specificare la concorrenza nel codice utilizzando una libreria di funzioni con una semantica speciale. Ogni thread in Pthreads implementa un'astrazione di un processore ed è multiplexato sulle effettive risorse della macchina. Pthreads fornisce anche maschere che semplificano i protocolli coinvolti nel coordinamento dei thread interni. La libreria Pthreads ha funzioni chiave come pthread_create, che memorizza e identifica il nuovo thread creato da pthread, e pthread_join, che attende che il thread finisca prima di continuare nel codice. Il relatore dimostra come implementare una serie di Fibonacci usando Pthreads.
  
  
• 00:30:00 In questa sezione, il relatore discute l'implementazione del codice Pthreads per eseguire la sequenza di Fibonacci in parallelo. Spiegano che se la dimensione dell'input è abbastanza piccola, è meglio eseguire il programma in sequenza a causa del costo della creazione di thread in parallelo. Il codice esegue il marshalling dell'argomento di input nel thread e lo memorizza nella struttura arguments. Il relatore discute Pthread create, Pthread join e alcuni dei suoi svantaggi, come diventare molto più complicato se il codice deve creare thread in modo ricorsivo. Dicono anche che questo codice crea solo un thread, quindi la velocità massima possibile è due se eseguita su quattro processori.
  
  
• 00:35:00 In questa sezione del video vengono discussi i problemi con i Pthread e il codice per la sequenza di Fibonacci. L'elevato sovraccarico per la creazione di un thread si traduce in una concorrenza a grana grossa e il problema di scalabilità è che i due core non eseguono la stessa quantità di lavoro. Il codice manca anche di modularità, poiché la logica di Fibonacci non è ben incapsulata all'interno di una funzione, rendendone difficile la manutenzione e la modifica. Il codice diventa complicato anche a causa del marshalling degli argomenti, che è simile alla necessità di scrivere codice in assembly. Il video introduce quindi Threading Building Blocks (TBB), una libreria sviluppata da Intel per fornire una soluzione a questi problemi.
  
  
• 00:40:00 In questa sezione, il video illustra l'uso della libreria Intel Thread Building Blocks (TBB), una libreria C++ progettata per consentire ai programmatori di utilizzare thread nativi e un algoritmo di furto di lavoro senza dover gestire direttamente i thread. Specificando le attività, il carico TBB le bilancia tra i thread, rendendo il codice più semplice da scrivere e con prestazioni migliori rispetto all'utilizzo dei thread POSIX. Il video mostra un esempio di implementazione di un programma Fibonacci utilizzando TBB, dimostrando come crea in modo ricorsivo attività figlio, consentendo più parallelismo e scalabilità su più processori. TBB fornisce anche modelli per il parallelismo dei loop, l'aggregazione dei dati e il pipelining del software, oltre a classi container simultanee per un accesso simultaneo sicuro ai dati condivisi.
  
  
• 00:45:00 In questa sezione, il relatore introduce due soluzioni linguistiche al problema della concorrenza: OpenMP e Silk. OpenMP è una specifica che fornisce estensioni linguistiche a C e C++, oltre a Fortran, utilizzando i pragma del compilatore per specificare quali parti di codice devono essere eseguite in parallelo. Supporta il parallelismo del ciclo, il parallelismo delle attività e il parallelismo della pipeline e ha molte direttive di pianificazione e condivisione dei dati, nonché costrutti di sincronizzazione. L'oratore fornisce un esempio di implementazione di Fibonacci in OpenMP, che è più semplice e offre prestazioni migliori rispetto all'utilizzo di Pthreads o TBB. OpenMP è una soluzione popolare per scrivere programmi paralleli in quanto fornisce molte funzionalità e semplifica il codice.
  
  
• 00:50:00 In questa sezione, il relatore discute la piattaforma di programmazione Silk, che supporta il parallelismo articolare e vettoriale e include uno schedulatore di furto di lavoro dimostrabilmente efficiente. Il programma dispone anche di una libreria di iperoggetti per parallelizzare il codice con variabili globali e viene fornito con strumenti di programmazione come un rilevatore di razza serigrafica e un analizzatore di scalabilità chiamato Silk View. Il relatore nota anche che mentre non useranno silk plus nella classe, useranno un compilatore migliore noto come taper LLVM, che produce un codice migliore rispetto al suo compilatore di base rispetto a tutte le altre implementazioni di silk là fuori.
  
  
• 00:55:00 In questa sezione, l'uso delle istruzioni silk spawn e silk sync per abilitare l'esecuzione parallela viene discusso attraverso esempi. Il primo esempio è il rivestimento di sale per Fibonacci, che include istruzioni silk spawn e silk sync per suggerire che fib di n-1 può essere eseguito in parallelo con la funzione che lo chiama mentre viene eseguito fib di n-2. Tuttavia, il sistema di runtime decide se eseguire o meno queste attività in parallelo. Un altro esempio discusso è il parallelismo del ciclo, in cui l'istruzione silk for viene utilizzata per eseguire un ciclo for in parallelo con il compilatore che divide in modo ricorsivo lo spazio di iterazione a metà e utilizza le istruzioni silk spawn e silk sync fino a quando l'intervallo diventa troppo piccolo per essere eseguito in parallelo. È importante garantire che le iterazioni siano indipendenti per ottenere risultati corretti e l'utilizzo di silk per aggiunge ulteriori spese generali.
  
  
• 01:00:00 In questa sezione, il video discute l'utilizzo di cicli silk for nidificati e i dettagli della generazione di codice assembly utilizzando un flag nel compilatore clang. Il codice di esempio per una sommatoria di valori che utilizza un ciclo silk for solleva il problema della gara di determinazione quando più processori scrivono nella stessa posizione di memoria. Silk affronta questo problema attraverso l'uso di riduttori, che sono iperoggetti che gestiscono la funzione di addizione per una data variabile, registrando e annullando la registrazione delle macro riduttore. Questo è un modo per affrontare il problema della riduzione, che può presentarsi nella programmazione multicore, con molti altri operatori di riduzione disponibili per l'uso.
  
  
• 01:05:00 In questa sezione, il relatore discute i riduttori in Silk - strutture algebriche che hanno un'operazione binaria associativa e un elemento di identità. Silk ha diversi riduttori predefiniti, tra cui addizione, moltiplicazione, minimo, massimo e XOR, e puoi definire il tuo riduttore. Uno dei vantaggi di Silk è che esiste sempre un'interpretazione seriale valida del programma, semplificando il debug e dispone di uno scheduler di runtime che monitora e mappa il programma sui core del processore disponibili, utilizzando un algoritmo di pianificazione che ruba lavoro per bilanciare le attività uniformemente. A differenza di altre piattaforme di concorrenza, lo scheduler di Silk è teoricamente efficiente.
  
  
• 01:10:00 In questa sezione, il relatore fornisce una panoramica di alto livello dell'ecosistema Silk per la programmazione multicore, incluso come compilare il codice sorgente di Silk, confrontare le prestazioni parallele e seriali e risolvere i problemi utilizzando strumenti come Silk Sanitizer e Silk scala. Sottolineano inoltre l'importanza di ottimizzare il programma seriale per le prestazioni e come lo scheduler di Silk può gestire diverse attività durante l'esecuzione del programma. Inoltre, il relatore spiega come la scala della seta può determinare il numero massimo di processori di cui un codice può trarre vantaggio, rendendolo uno strumento utile per analizzare la scalabilità.
  
  
• 01:15:00 In questa sezione, il relatore riassume i punti salienti della lezione sulla programmazione multicore. Spiegano che la maggior parte dei processori moderni ha più core, rendendo necessario scrivere programmi paralleli per prestazioni elevate. Tuttavia, la scrittura di tali programmi può essere difficile, ed è qui che entra in gioco Silk. Questo strumento astrae i core del processore dal programmatore e gestisce la sincronizzazione, i protocolli di comunicazione e il bilanciamento del carico. Il relatore menziona anche un progetto futuro in cui gli studenti implementeranno il proprio salvaschermo parallelo utilizzando Silk.

[MetaQuotes]

Lezione 7. Razze e parallelismo

Lezione 7. Razze e parallelismo

Il video copre una serie di argomenti relativi a razze, parallelismo e dati di calcolo nella programmazione Silk. Alcuni concetti chiave trattati includono le dichiarazioni di spawn e sync per l'esecuzione simultanea, l'importanza di evitare le race condition e l'utilizzo del race detector di Silk per identificarle. Il video copre anche la legge di Amdahl, la legge sul lavoro e la legge sulla portata come modi per quantificare la quantità di parallelismo in un programma, insieme a modi per analizzare il lavoro e la durata dei calcoli. Vengono discussi anche il potenziale aumento di velocità e parallelismo degli algoritmi di ordinamento parallelo e il concetto di teoria della schedulazione, con particolare attenzione al teorema dello schedulatore avido. Nel complesso, il video fornisce preziose informazioni sulla comprensione e l'ottimizzazione delle prestazioni del programma nella programmazione Silk.

Il video spiega i corollari del greedy scheduler bound, che essenzialmente afferma che qualsiasi greedy scheduler raggiunge un'accelerazione lineare quasi perfetta fintanto che T1/Tinfinity è maggiore o uguale a P^2. Lo scheduler Silk, che utilizza uno scheduler che ruba lavoro, può ottenere un'accelerazione lineare quasi perfetta fintanto che il numero di processori è molto inferiore a T1/Tinfinity. Il sistema di runtime della seta funziona mantenendo un mazzo di lavoro di fili pronti e manipola il fondo del mazzo come una pila. Il video discute anche del Cactus Stack, che consente più visualizzazioni di stack in parallelo e rende possibili chiamate di funzioni parallele. Il limite superiore dello spazio dello stack richiesto dall'esecuzione del processore P è spesso molto più ampio della quantità effettiva necessaria poiché ogni processore potrebbe non aver bisogno di scendere fino in fondo al grafico di calcolo ogni volta che ruba lavoro.

• 00:00:00 In questa sezione, l'istruttore introduce l'argomento delle corse e del parallelismo in Silk, che sarà importante per l'imminente compito e progetto a casa. Vengono esaminate le basi delle istruzioni spawn e sync di Silk, che consentono l'esecuzione simultanea di funzioni padre e figlio. L'istruttore sottolinea inoltre l'importanza di incontrare i membri della politica del MIT ed evitare condizioni di competizione nel codice, che possono portare a conseguenze disastrose come visto con esempi passati. I race bug più difficili da trovare sono quelli che hanno causato eventi catastrofici e i test convenzionali spesso non sono efficaci. Silk offre uno strumento per aiutare a identificare potenziali bug di razza nel codice.
  
  
• 00:05:00 In questa sezione, il video spiega come le corse siano uno dei bug più difficili da trovare per gli sviluppatori perché può verificarsi solo in rari eventi quando codici logicamente paralleli accedono alla stessa posizione di memoria e almeno uno registra una scrittura ad esso. Ad esempio, il video mostra un semplice codice che utilizza un grafico delle dipendenze per mostrare come il race bug condiviso tra due percorsi paralleli non si verifica sempre. La gara si verifica quando entrambi gli archivi scrivono nella stessa posizione di memoria, il che potrebbe comportare output diversi a seconda di quale percorso di esecuzione viene eseguito interamente per primo.
  
  
• 00:10:00 In questa sezione, l'oratore spiega il concetto di gare di determinazione, che si verificano quando due istruzioni accedono alla stessa posizione di memoria e almeno una delle istruzioni è un'operazione di scrittura, con conseguente comportamento non deterministico nel programma. Il relatore fornisce suggerimenti su come evitare le corse, come garantire che le iterazioni di un ciclo for di Silk siano indipendenti e assicurarsi che anche il codice tra un'istruzione di spawn di Silk e la corrispondente istruzione di sincronizzazione di Silk sia indipendente. L'oratore osserva inoltre che la dimensione della parola della macchina è importante e che è necessario prestare attenzione durante la lettura e la scrittura di strutture di dati compressi che utilizzano tipi non standard.
  
  
• 00:15:00 In questa sezione, il video discute il "rilevatore di razza" della piattaforma Silk, che può aiutare a identificare potenziali condizioni di gara in un programma. Utilizzando il flag '-f sanitized equal to silk' per generare un programma strumentato, Silk può segnalare e localizzare le razze offensive, il che aiuta a eseguire il debug del codice. Il video spiega anche il concetto di parallelismo e come il modello di esecuzione di Silk utilizza i grafici di calcolo per illustrare lo sviluppo del calcolo durante l'esecuzione. Questi concetti sono importanti da comprendere quando si tenta di ottimizzare e migliorare le prestazioni del programma.
  
  
• 00:20:00 tipi di vertici nel calcolo dag: filamento iniziale, filamenti di continuazione, filamenti di chiamata di funzione e filamenti finali. Il filamento iniziale contiene la prima istruzione da eseguire e il filamento finale contiene l'ultima istruzione eseguita nel programma. I filamenti di continuazione rappresentano la continuazione di un'operazione di spawn, mentre i filamenti di chiamata di funzione rappresentano l'esecuzione di una chiamata di funzione. È importante notare che il dag di calcolo si svolge dinamicamente durante l'esecuzione ed è ignaro del processore, il che significa che il sistema di runtime capisce come mappare le attività ai processori in fase di esecuzione. In sintesi, il dag di calcolo è un potente strumento per comprendere il parallelismo e la concorrenza di un programma.
  
  
• 00:25:00 In questa sezione, apprendiamo i dati di calcolo e come possono essere utilizzati per analizzare il parallelismo in un programma. Il dag di calcolo rappresenta le dipendenze tra diverse parti del programma e ha diversi tipi di bordi, inclusi bordi di spawn, bordi di chiamata, bordi di ritorno e bordi continui. È possibile utilizzare i dati di calcolo per analizzare la quantità di parallelismo presente in un programma e utilizzare la legge di Amdahl per quantificare la quantità di parallelismo. Nell'esempio fornito, ci sono meno di sette nodi che devono essere eseguiti in sequenza, indicando che c'è un certo grado di parallelismo nel calcolo.
  
  
• 00:30:00 In questa sezione, viene introdotto il concetto di legge di Amdahl come un modo per determinare la massima velocità possibile nell'elaborazione parallela. Viene determinato che la frazione seriale del programma è 3/18, risultando in un'accelerazione massima di 6. Sebbene la legge di Amdahl fornisca un limite superiore al parallelismo, spesso è troppo ampia nei casi pratici. La legge di lavoro e la legge di span vengono introdotte come definizioni alternative di parallelismo, con la legge di lavoro che afferma che il tempo di esecuzione su P processori è maggiore o uguale al lavoro del programma diviso per P, e la legge di span che afferma che il tempo di esecuzione su P processori è almeno il tempo di esecuzione su un numero infinito di processori. Queste leggi forniscono in molti casi limiti superiori migliori rispetto alla legge di Amdahl sull'accelerazione massima.
  
  
• 00:35:00 In questa sezione, il relatore discute come comporre il lavoro e misurare le quantità di diversi calcoli. Spiegano che quando si eseguono due calcoli paralleli, il lavoro è ancora la somma del lavoro dei singoli calcoli e l'intervallo è il massimo dell'intervallo dei singoli calcoli. Il relatore definisce anche l'accelerazione sui processori P e discute l'accelerazione sublineare, lineare e superlineare. Notano che la massima accelerazione possibile è uguale al parallelismo del calcolo, che è uguale alla quantità media di lavoro per passo lungo il calcolo. Nel complesso, questa sezione fornisce informazioni sulla composizione dei calcoli e su come misurarne il parallelismo.
  
  
• 00:40:00 In questa sezione, il relatore discute come analizzare il lavoro e l'intervallo dei calcoli per calcolare il parallelismo massimo, utilizzando esempi come un DAG di calcolo e un algoritmo di Quicksort parallelo. Il relatore introduce l'analizzatore di scalabilità Silk Scale, che utilizza la strumentazione del compilatore per analizzare l'esecuzione seriale di un programma e ricavare limiti superiori sull'accelerazione parallela del programma. L'oratore menziona anche che l'analisi manuale del parallelismo di grandi calcoli può essere noiosa, ma Silk Scale può aiutare in questo.
  
  
• 00:45:00 In questa sezione, il video discute i risultati dell'esecuzione di un calcolo parallelo e della generazione di un grafico che mostra l'accelerazione osservata, nonché i limiti delle leggi dello span e del lavoro. Il grafico mostra che l'accelerazione massima è di circa 5, indicando che il parallelismo nel programma è basso. L'analisi rivela che il collo di bottiglia del parallelismo è l'esecuzione sequenziale della funzione di partizione e che il lavoro e l'intervallo previsti della versione parallela di quicksort sono dell'ordine di n log n. Il massimo parallelismo che si può ottenere è dell'ordine di log log n, che non è molto elevato. Per aumentare il parallelismo, la funzione di partizione deve essere parallelizzata.
  
  
• 00:50:00 In questa sezione, il relatore discute l'importanza di implementare il parallelismo negli algoritmi di partizione e merge sort al fine di ottenere una significativa accelerazione. Le versioni parallele di questi algoritmi hanno un intervallo complessivo limitato con log al quadrato n e un elevato parallelismo di n su log n. Inoltre, ci sono molti altri pratici algoritmi paralleli là fuori che hanno un alto parallelismo e un work bound asintoticamente uguale a quello del corrispondente algoritmo sequenziale. Il relatore introduce anche il concetto di teoria della pianificazione, spiegando che uno scheduler centralizzato può mappare i DAG di calcolo sui processori disponibili in fase di esecuzione, mentre uno scheduler distribuito viene utilizzato nella programmazione Silk. Viene utilizzato come esempio uno scheduler avido, che fa il più possibile in ogni fase del calcolo.
  
  
• 00:55:00 In questa sezione viene introdotto il concetto di avido programmatore, che esegue quanto più lavoro possibile nella fase temporale corrente senza pensare al futuro. Sono definite una fase completa, in cui sono pronti almeno P filamenti, e una fase incompleta, in cui sono pronti meno di P filamenti. Il famoso teorema, mostrato per la prima volta da Ron Graham nel 1968, afferma che il limite di tempo raggiunto da uno scheduler greedy è minore o uguale a T1/P + T infinito, dove T1 è il lavoro e T infinito è lo span. Viene fornita la dimostrazione di questo teorema, ed è dimostrato che qualsiasi schedulatore avido raggiunge entro un fattore due il tempo di esecuzione ottimale.
  
  
• 01:00:00 In questa sezione, il video spiega i corollari del greedy scheduler bound, che raggiunge entro un fattore due lo scheduler ottimale. Il corollario afferma che qualsiasi programmatore avido raggiunge un'accelerazione lineare quasi perfetta quando T1/Tinfinity è maggiore o uguale a P^2, dove T1/P moltiplicato per T infinito misura la quantità di parallelismo nel calcolo rispetto al numero di processori disponibile. Lo schedulatore di seta utilizza uno schedulatore che ruba lavoro, che ha un tempo di esecuzione previsto di TP pari a T1/P più l'ordine T infinito, con una grande O davanti a T infinito per tenere conto dei costi generali della pianificazione e può raggiungere quasi- accelerazione lineare perfetta fintanto che il numero di processori è molto inferiore a T1/Tinfinity. Il sistema di runtime della seta funziona mantenendo un mazzo di lavoro di fili pronti e manipola il fondo del mazzo come una pila. La strumentazione in Silk Scale consente di misurare i termini di lavoro e campata per determinare il parallelismo nel programma.
  
  
• 01:05:00 In questa sezione, il relatore discute il concetto di generazione e parallelismo nei processori. Spiegano che quando un processore chiama una funzione, posiziona il frame di quella funzione in fondo al suo stack e può generare frame in fondo allo stack. Più processi possono verificarsi in parallelo e i ritorni possono essere effettuati da spawn e chiamate. Quando i lavoratori finiscono il lavoro da fare, rubano dalla cima del mazzo di un altro processore. Il famoso teorema afferma che i lavoratori rubano molto raramente, dando un'accelerazione quasi lineare. L'oratore osserva inoltre che Silk supporta le regole di C per i puntatori, in cui un puntatore a uno spazio di stack può essere passato da un genitore a un figlio, ma non da un figlio a un genitore.
  
  
• 01:10:00 In questa sezione del video, l'oratore discute il Cactus Stack, che è lo stack che può essere visto da un'attività nel grafico di calcolo dell'antenato del programma Silk. Questo stack consente più visualizzazioni di stack in parallelo, il che rende possibili chiamate di funzioni parallele. Il relatore spiega che lo spazio di stack richiesto da un programma Silk può essere trovato prendendo lo spazio di stack richiesto da un'esecuzione seriale del programma (S sub 1) e moltiplicandolo per il numero di processori (P) che verranno utilizzati (S sub 1) sub P ≤ P x S sub 1). Il relatore fornisce una prova di alto livello di questo concetto e osserva che il limite superiore dello spazio dello stack richiesto dall'esecuzione del processore P è spesso molto più flessibile della quantità effettiva necessaria poiché ogni processore potrebbe non aver bisogno di scendere fino in fondo al grafico di calcolo ogni tempo ruba lavoro.

[MetaQuotes]

Lezione 8. Analisi di algoritmi multithread

Lezione 8. Analisi di algoritmi multithread

Questo video illustra il metodo principale per analizzare le ricorrenze divide et impera e lo applica agli algoritmi multithread confrontando la base logaritmica B di n con la base logaritmica B di A con F di N per determinare la loro crescita in n e il lavoro richiesto. Il video presenta un cheat sheet con soluzioni per algoritmi multithread di base e copre argomenti come l'analisi del lavoro e dello span, l'efficienza del lavoro e il superamento dei costi generali attraverso l'ottimizzazione della dimensione dei grani. Viene sottolineata l'importanza dell'empatia quando si comunicano argomenti tecnici e viene introdotto il concetto di DAG come mezzo per bilanciare lavoro e intervallo per aumentare il parallelismo e ridurre il tempo di esecuzione.

Il video illustra anche l'analisi degli algoritmi multithread, concentrandosi su lavoro e intervallo e su come massimizzare il parallelismo riducendo al minimo l'intervallo per ottenere un'accelerazione lineare quasi perfetta. L'oratore suggerisce un approccio divide et impera agli algoritmi multi-thread, in cui il numero di attività assegnate ai thread è sufficientemente grande e mette in guardia contro la generazione di numerose piccole attività a causa di spese generali di pianificazione. Il codice di esempio presentato include uno efficiente e uno scadente. Il relatore discute anche su come rappresentare le sottomatrici nella codifica e nell'indicizzazione bidimensionali e sottolinea l'uso di "restrict" nel codice di moltiplicazione delle matrici divide et impera per migliorare le prestazioni.

• 00:00:00 In questa sezione, l'istruttore inizia ricordando agli studenti le ricorrenze del divide et impera e il metodo generale per risolverle chiamato metodo principale. Il metodo tratta le ricorrenze e la loro forma T(n) = a*T(n/B) + F(n), dove a è una costante, B è il fattore di divisione e F(n) è la quantità totale di lavoro dividere il problema in sottoproblemi di dimensione n/B. Agli studenti viene ricordato l'albero di ricorsione e come ogni livello si suddivide in sottoproblemi di dimensione n/B, sommano il tempo di esecuzione attraverso le righe, calcolano l'altezza dell'albero e la moltiplicano per il numero di sottoproblemi a ciascun livello (un ^k). Infine, gli studenti calcolano che n^log base B di A è il tempo di esecuzione totale dell'algoritmo.
  
  
• 00:05:00 In questa sezione, il relatore spiega come determinare la crescita in n e il lavoro richiesto durante la valutazione di algoritmi multithread. La chiave è confrontare la base logaritmica B di n con la base logaritmica B di A con F di N. L'oratore copre tre possibili casi, il primo dei quali è quando la base logaritmica B n è molto più grande di F di n. In questo caso, la frazione costante del peso è nelle foglie, portando alla risposta n al logaritmo in base B di A. Il secondo caso è quando logaritmo in base B n è approssimativamente uguale a F di n. Per questo, aggiungi un logaritmo extra e la risposta è n al logaritmo in base B di un logaritmo alla k più 1 di n. Infine, il terzo caso è quando an to log base B è molto minore di F di N, il che significa che F deve soddisfare una condizione di regolarità, che è soddisfatta da tutte le funzioni che guarderanno come polinomi e logaritmi.
  
  
• 00:10:00 In questa sezione, il relatore presenta un cheat sheet con le soluzioni di base degli algoritmi multithread comunemente usati in informatica. Il primo algoritmo, T(n) = T(n/2) + n, ha una soluzione di Θ(n^2) poiché rientra nel primo caso. Il secondo algoritmo, T(n) = T(n/2) + n^2logn, ha una soluzione di Θ(n^2logn) poiché rientra nel caso due con k = 0. Per il terzo algoritmo, T(n) = T(n/2) + n^2, la soluzione è Θ(n^2) in quanto rientra nel primo caso. Il quarto algoritmo, T(n) = 2T(n/2) - n, è complicato in quanto non rientra in nessun caso del metodo principale e ha una soluzione di Θ(n^2loglogn).
  
  
• 00:15:00 In questa sezione, il relatore discute il metodo Aqua Bazi e come sia più complicato del metodo master, che è sufficiente per analizzare la maggior parte dei programmi. Forniscono quindi un esempio di ciclo parallelo con codice di trasposizione della matrice sul posto in cui il ciclo esterno è parallelizzato. Il relatore sottolinea l'importanza di definire correttamente lo spazio di iterazione e il bilanciamento del carico per un'elaborazione parallela efficiente. Spiegano anche come i loop vengono implementati dal compilatore di seta aperto e dal sistema di runtime.
  
  
• 00:20:00 In questa sezione, l'oratore descrive un programma ricorsivo per un ciclo che utilizza divide et impera per dividere il ciclo in due parti e chiamare se stesso in modo ricorsivo su ciascun lato fino a raggiungere un'iterazione di un elemento. Il lavoro di questo calcolo viene analizzato in termini di lavoro e intervallo, con il lavoro foglia di ordine n al quadrato e la parte superiore theta n perché ogni livello dalle foglie alla radice ha solo n nodi. Il sistema open silk runtime non ha un ciclo primitivo, quindi i cicli vengono effettivamente tradotti in questo approccio di divisione e conquista in parallelo.
  
  
• 00:25:00 In questa sezione, il relatore discute il lavoro e l'analisi di span di un algoritmo multithread. Spiega che il lavoro totale è Θ(n²) perché viene svolto un lavoro costante per ciascuna delle n foglie dell'albero binario completo. L'intervallo del controllo del ciclo è log(n), il che significa che un numero infinito di processori potrebbe completare l'attività in tempo logaritmico. Tuttavia, poiché esiste una componente lineare nel calcolo (n), l'intervallo totale è Θ(n). Pertanto, il parallelismo è Θ(n), che è una buona quantità per la maggior parte dei sistemi pratici. L'oratore esplora quindi lo scenario in cui anche il ciclo interno è parallelizzato e discute la quantità di lavoro risultante.
  
  
• 00:30:00 In questa sezione del video, il professore discute il concetto di efficienza del lavoro in algoritmi paralleli. La parallelizzazione degli algoritmi non cambia il lavoro, ma si spera che dovrebbe ridurre l'intervallo del calcolo per ottenere un grande parallelismo. Tuttavia, a volte la parallelizzazione può comportare l'aggiunta di più lavoro, il che può essere problematico perché rallenta il programma rispetto all'algoritmo originale. Gli algoritmi paralleli efficienti in termini di lavoro sono ciò che il professore è interessato a insegnare, poiché sono in grado di ridurre l'intervallo per ottenere un grande parallelismo senza aggiungere altro lavoro. Il professore sottolinea l'importanza di porre domande e commettere errori nel processo di apprendimento, in quanto può aiutare altri che potrebbero avere le stesse domande ma hanno paura di fare. Incoraggia gli studenti a partecipare e impegnarsi nel processo di apprendimento, anche se non sono nel 10% dei migliori.
  
  
• 00:35:00 In questa sezione viene sottolineata l'importanza dell'empatia nella comunicazione quando si tratta di argomenti tecnici. Il professore incoraggia gli studenti a essere pazienti con gli altri nella classe che potrebbero non avere familiarità con il materiale trattato. Passando all'analisi degli algoritmi multithread, viene presentato un algoritmo divide et impera per l'addizione di vettori e il parallelismo risulta essere n su log n. Viene discussa la relazione tra parallelismo e numero di processori, con il professore che sottolinea che mentre un maggiore parallelismo può sembrare migliore, è vantaggioso solo fino a una certa soglia.
  
  
• 00:40:00 In questa sezione, l'oratore discute l'ottimizzazione di parte dell'overhead in un algoritmo multithread, in particolare l'overhead della chiamata di subroutine. Introducono il concetto di "dimensione della grana", che suggerisce al compilatore che ci sono fino a G elementi per blocco alla fine del processo di divisione e conquista. Ciò consente di ammortizzare l'overhead della subroutine tra le iterazioni G anziché solo una, con conseguenti prestazioni migliori. Se la dimensione della grana non è specificata, il sistema fa la sua ipotesi migliore per ridurre al minimo l'overhead. Il relatore suddivide le variabili I, G e s per analizzare il lavoro in questo contesto e lo confronta con il lavoro nel codice originale senza il materiale di controllo parallelo.
  
  
• 00:45:00 In questa sezione, il relatore parla dell'analisi degli algoritmi multithread e di come il controllo del loop sia economico su un moderno processore fuori servizio. Esaminano l'intervallo, che è il tempo necessario per eseguire l'algoritmo con un numero infinito di processori, e discutono il costo generale rispetto al costo delle iterazioni. L'oratore suddivide l'intervallo in termini di numero di foglie e di operazioni colorate, denominate "s", che devono essere eseguite su ciascuna di esse. Rispondono anche a domande sul numero di nodi interni in un albero binario completo e sui percorsi seguiti per calcolare lo span.
  
  
• 00:50:00 In questa sezione, il relatore discute l'analisi degli algoritmi multithread, in particolare il concetto di DAG (grafico aciclico diretto) e come influisce sul percorso dell'algoritmo. Sottolineano la necessità di indipendenza tra i diversi sottoalberi del DAG per consentire l'elaborazione parallela. L'obiettivo è bilanciare il lavoro e l'intervallo dell'algoritmo, poiché questi due fattori funzionano in direzioni opposte. La chiave è che G (la quantità di parallelismo) sia molto maggiore di s su I (la parte sequenziale dell'algoritmo), che consente un sovraccarico minore e un'elaborazione più rapida. L'oratore menziona anche un'implementazione di questo concetto, ma osserva che sarà discusso più avanti nella serie di conferenze.
  
  
• 00:55:00 In questa sezione, il relatore presenta un'implementazione di algoritmi multithread utilizzando un ciclo for per sommare due vettori. Il ciclo utilizza un operatore chiamato V add per eseguire l'addizione di vettori seriali e il ciclo genera addizioni in gruppi di G utilizzando un vettore di dimensione G. Supponendo che G sia uguale a uno, il lavoro dei cicli è di ordine n e anche lo span è ordinanza n. Il parallelismo viene misurato prendendo il rapporto tra work e span, che è n diviso n, che semplifica a 1. Il relatore sottolinea che l'obiettivo dell'analisi degli algoritmi multithreading è aumentare il parallelismo e diminuire lo span per ridurre al minimo il tempo di esecuzione, e mette in evidenza la tecnica chiamato strip mining, in cui un ciclo di lunghezza N viene sostituito da un doppio ciclo annidato per parallelizzare i calcoli, come un modo per migliorare gli algoritmi multithread.
  
  
• 01:00:00 In questa sezione il relatore analizza le prestazioni degli algoritmi multithread in termini di work e span. Discutono su come ridurre al minimo lo span per massimizzare il parallelismo, poiché lo span è nel denominatore. La chiave è generare un parallelismo dieci volte maggiore rispetto ai processori se si desidera una velocità lineare quasi perfetta. L'oratore suggerisce anche di scambiare un po' di parallelismo per ridurre l'overhead di lavoro, se necessario. Incoraggiano a giocherellare con la dimensione del grano per farlo, purché venga mantenuto un parallelismo sufficiente.
  
  
• 01:05:00 In questa sezione, il relatore discute l'uso delle strategie divide et impera negli algoritmi multi-thread, sconsigliando di generare numerose piccole attività una dopo l'altra, a meno che non siano suddivise in poche attività, nel qual caso l'overhead è ok. In generale, dovrebbe esserci un approccio divide et impera, in cui il numero di compiti assegnati ai thread è sufficientemente grande. L'oratore avverte di fare attenzione alla pianificazione delle spese generali e suggerisce di parallelizzare il ciclo esterno anziché i cicli interni, che hanno più spese generali. I codici di esempio qui presentati ne mostrano uno efficiente, in cui la pianificazione si verifica solo una volta, e uno scadente, in cui l'overhead si verifica n volte. La moltiplicazione di matrici viene utilizzata come esempio di un algoritmo multi-thread che utilizza una strategia di divisione e conquista per moltiplicare le matrici n per n eseguendo 8 moltiplicazioni di n su 2 per n su 2 matrici e quindi aggiungendo due matrici n per n.
  
  
• 01:10:00 In questa sezione, il relatore discute su come rappresentare le sottomatrici nella codifica bidimensionale e nell'indicizzazione, in particolare nell'ordine di riga maggiore e di colonna maggiore per linguaggi come C e Fortran. L'idea è che ogni matrice bidimensionale può essere indicizzata come matrice unidimensionale e, quando si tratta di sottomatrici, è necessario aggiungere il numero di righe e la lunghezza della matrice lunga per sapere dove si trova l'elemento IJ. Inoltre, quando si implementa il divide et impera, è fondamentale conoscere gli angoli di partenza di ciascuna delle quattro sottomatrici. In definitiva, l'oratore sottolinea l'uso di "restrict" nel codice di moltiplicazione della matrice divide et impera per dire al compilatore quali elementi possono o meno essere aliasati.
  
  
• 01:15:00 In questa sezione, il relatore discute un algoritmo multithread per la moltiplicazione di matrici. L'algoritmo si basa sulla suddivisione ricorsiva delle matrici in sottomatrici più piccole, con ciascuna sottomatrice moltiplicata ricorsivamente per ottenere il risultato finale. Il relatore evidenzia un piccolo trucco per determinare rapidamente se n è una potenza di due e utilizza una macro per semplificare l'indicizzazione delle matrici. L'algoritmo presenta un parallelismo elevato, che può essere ridotto per migliorare le prestazioni. Vengono menzionati anche altri algoritmi simili.

[MetaQuotes]

Lezione 9. Cosa possono e non possono fare i compilatori

Lezione 9. Cosa possono e non possono fare i compilatori

Questo video illustra come i compilatori possono ottimizzare il codice, utilizzando vari esempi. Spiega come i compilatori possono eliminare l'archiviazione e i riferimenti di memoria non necessari e come possono ottimizzare i loop per migliorare le prestazioni.

Questo video spiega anche il concetto di passaggi di ottimizzazione del compilatore e come possono essere usati per migliorare le prestazioni del codice. Discute anche i limiti dei compilatori, in particolare per quanto riguarda la vettorizzazione. I compilatori possono vettorizzare il codice solo se possono determinare che i puntatori nel codice non creeranno alias. Se i puntatori fanno alias, il compilatore non sarà in grado di vettorizzare il codice. Come programmatore, puoi aiutare il compilatore annotando i tuoi puntatori per fornire maggiori informazioni sul loro utilizzo.

• 00:00:00 In questa conferenza, Tao Schardl discute cosa possono e non possono fare i compilatori. Spiega che lo studio delle ottimizzazioni del compilatore può aiutare gli sviluppatori a capire come scrivere codice che sfrutta le ottimizzazioni e come evitare di ottimizzare manualmente il codice che il compilatore può già ottimizzare.
  
  
• 00:05:00 Il compilatore è un grosso pezzo di software e può assolutamente aiutare per il debug quando il compilatore stesso ha bug. Aiuta a capire dove il compilatore potrebbe aver commesso un errore o dove il compilatore semplicemente non ha fatto quello che pensavi fosse in grado di fare.
  
  
• 00:10:00 Il compilatore può fare molte ottimizzazioni, ma ci sono alcune cose che non può fare. Ad esempio, non può sempre creare un percorso rapido o ottimizzare i loop.
  
  
• 00:15:00 Il compilatore può fare molto per ottimizzare il codice, ma ci sono alcune cose che non può fare bene. Un esempio sono le strutture dati: il compilatore non è intelligente su di esse nello stesso modo in cui lo è sulle funzioni. Un altro sono i loop: il compilatore può eseguire alcune ottimizzazioni su di essi, ma ci sono delle restrizioni.
  
  
• 00:20:00 Questo video di YouTube spiega come i compilatori possono utilizzare semplici operazioni per sostituire quelle più complesse. Ad esempio, per sostituire un'operazione di divisione, un compilatore può moltiplicare per un numero magico e quindi spostare il risultato. Questo video spiega anche come funziona il calcolatore di indirizzi.
  
  
• 00:25:00 Il video illustra come i compilatori possono ottimizzare il codice, utilizzando come esempio una semplice funzione "vex scale". Il codice viene prima mostrato senza ottimizzazioni e quindi con varie ottimizzazioni applicate. Le ottimizzazioni mostrate includono la riduzione del numero di istruzioni, l'uso di istruzioni vettoriali e l'uso di numeri magici.
  
  
• 00:30:00 Questo video illustra come i compilatori possono ottimizzare il codice eliminando le operazioni di memoria non necessarie. In particolare, mostra come un compilatore può ottimizzare una funzione che moltiplica due valori scalari eliminando la necessità di memorizzare i valori in memoria. Infine, mostra come un compilatore può ottimizzare una funzione che opera su una struttura eliminando la necessità di memorizzare la struttura in memoria.
  
  
• 00:35:00 In questo video di YouTube, il relatore spiega come i compilatori possono ottimizzare il codice eliminando l'archiviazione e i riferimenti di memoria non necessari. Usa l'esempio di una struttura con più campi e dimostra come il compilatore può ottimizzare il codice analizzando attentamente la matematica coinvolta nei calcoli dell'indirizzo. Comprendendo cosa fa ciascuna istruzione, il compilatore può ottimizzare il codice e rimuovere le operazioni non necessarie.
  
  
• 00:40:00 Il compilatore lavora duramente per trasformare strutture di dati e valori scalari per archiviare quanto più possibile esclusivamente all'interno dei registri ed evitare di utilizzare qualsiasi memoria locale, se possibile. Per le chiamate di funzione, il compilatore vede l'istruzione di chiamata e il codice per la funzione chiamata. Quindi cerca di rendere la funzione nel codice sopra ancora più veloce.
  
  
• 00:45:00 Il compilatore può incorporare il codice per evitare il sovraccarico delle chiamate di funzione e può anche ottimizzare il codice rimuovendo le operazioni non necessarie.
  
  
• 00:50:00 In questo video di YouTube, l'oratore spiega che ci sono tre motivi principali per cui un compilatore potrebbe non incorporare una funzione: se la funzione è ricorsiva, se la funzione si trova in un'unità di compilazione diversa o se la funzione potrebbe aumentare dimensione del codice e prestazioni negative. L'oratore fornisce anche alcuni suggerimenti per il controllo della funzione incorporata nei propri programmi.
  
  
• 00:55:00 Questo video mostra come i compilatori possono ottimizzare i loop per velocizzare l'esecuzione dei programmi. Il sollevamento del codice, o movimento del codice invariante del ciclo, è un'ottimizzazione che può essere utilizzata per migliorare le prestazioni.
  
  
• 01:00:00 Il compilatore può ottimizzare il codice eseguendo una sequenza di passaggi di trasformazione. Questi passaggi sono progettati per trovare proprietà come calcoli di indirizzi identici e sostituirli con un codice più efficiente.
  
  
• 01:05:00 Il compilatore è in grado di vettorizzare questo ciclo, nonostante non sappia se gli indirizzi di 'x' e 'y' si sovrappongono. Questo perché la struttura del codice compilato è più complicata della funzione a due righe fornita come input.
  
  
• 01:10:00 Questo video di YouTube spiega cosa possono e non possono fare i compilatori. I compilatori possono vettorizzare il codice se il codice non contiene alcun loop. Tuttavia, se il codice contiene cicli, il compilatore può vettorizzare il codice solo se il ciclo è pieno di operazioni vettoriali. Se il ciclo non è pieno di operazioni vettoriali, il compilatore non sarà in grado di vettorializzare il codice.
  
  
• 01:15:00 La questione se un compilatore possa vettorizzare o meno il codice è difficile, poiché dipende da una serie di fattori. In particolare, il compilatore deve essere in grado di determinare se due puntatori saranno o meno alias, il che può essere un compito difficile. Come programmatore, puoi aiutare il compilatore annotando i tuoi puntatori per fornire maggiori informazioni sul loro utilizzo.