Appunti lezioni di Informatica B

La scelta di codifica delle istruzioni determina l'Instructure Set Architecture (ISA)

La scelta di codifica delle istruzioni determina l'Instructure Set Architecture (ISA), cioè il modo in cui sono codificate le istruzioni del processore. CISC e RISC sono due famiglie di ISA. La scelta dell'ISA è influenzata da motivi commerciali e dalle tipologie di applicazioni da eseguire. La codifica delle istruzioni è chiamata linguaggio macchina. Per esprimere un programma nel modo più semplice è attraverso l'utilizzo di linguaggi di alto livello. Il compilatore svolge un lavoro di traduzione dal linguaggio ad alto livello al linguaggio macchina costruito da byte. È possibile scrivere un programma direttamente in linguaggio macchina. La creazione del codice in linguaggio macchina è delegata al compilatore.

Velocità del processore

La velocità del processore è determinata dalla frequenza del clock. Il processore compie un progresso ogni ciclo di clock. La velocità di un processore è

Il processore è il componente principale di un computer ed è responsabile dell'esecuzione delle istruzioni. La sua velocità di esecuzione è proporzionale alla frequenza del clock. La sua frequenza si misura in hertz (Hz).

Il numero di cicli di clock necessari per eseguire un'istruzione varia a seconda di diversi fattori:

• Il tipo di istruzione. Alcune operazioni sono intrinsecamente più complesse da svolgere di altre.
• La tipologia di ISA. Una singola operazione richiede mediamente un numero minore di cicli di clock su architettura RISC rispetto a CISC.
• La disponibilità di operandi. Istruzioni che operano su dati presenti nei registri sono più veloci rispetto alle stesse che operano su operandi in memoria, perché l'accesso alla memoria è più lento dell'accesso ai registri.

Il numero di cicli per singola istruzione varia da 2 a 20 su macchine CISC e da 1 a 4 su macchine RISC.

Cache memory

Il processore potrebbe eseguire istruzioni anche ogni nanosecondo, ma la memoria ha un tempo di accesso di circa 50 nanosecondi. Di conseguenza, tutte le istruzioni

che richiedono un accesso in memoria sono rallentate. La memoria costituisce un collo di bottiglia. L'utilizzo della memoria cache (= nascondiglio) permette di ridurre la perdita di prestazioni dovuta alla maggiore lentezza degli accessi in memoria rispetto agli accessi ai registri. La cache memory è una memoria più veloce ma più piccola, è collocata fra il processore e il bus di comunicazione. Il suo scopo è quello di contenere dati e istruzioni che vengono usati più frequentemente. In questo modo si eviteranno tempi lunghi della memoria principale per l'accesso ai dati/istruzioni di uso frequente. Per stimare la frequenza di utilizzo dei dati vengono sfruttati 2 principi:

• La località temporale. Il fatto che se una determinata locazione di memoria è stata acceduta, è molto probabile che essa venga acceduta anche nell'immediato futuro.
• La località spaziale. Se una certa localizzazione di memoria

è stat acceduta, alloraanche locazione di memoria con indirizzi vicini saranno probabilmente acceduteprossimamente.

Nelle architetture di calcolatori moderni possono esistere livelli diversi di cache inbase alla vicinanza al processore. Si parla di cache L1, L2, L3. Al crescere dell’indice12del livello della cache, le cache memory diventano sempre più grandi, lontani dalla CPUe lente. La cache di livello L1 è la più vicina e veloce, ma anche la più piccola.

Se il processore trova all’interno della cache i dati cercati avviene una cache hit el’accesso al dato avviene in modo più rapido. Mentre, se i dati richiesti dal processorenon si trovano nella cache avviene un cache miss e i dati devono essere prelevati dallamemoria. L’accesso ai dati è più veloce se avviene un cache hit rispetto al temporichiesto nel caso di un cache miss.

Gerarchia di memoria

Il principio di cache viene applicato estensivamente a vari

livelli dal più basso al piùalto. Per descrivere questa organizzazione viene utilizzato il termine di gerarchia di memoria. Ecco alcuni valori tipici delle memorie coinvolte nel calcolo.

I registri, i dischi e la capacità di memorizzazione offerta dai data center si possono considerare come forme di memoria. I tempi di accesso aumentano all’aumentare della distanza dal processore. Avere memorie molto grandi e molto vicine al processore non è tecnologicamente fattibile. Anche avere memorie piccole e con tempi di accesso grandi è inutile. Il costo di ogni singolo byte di memoria diminuisce all’aumentare della distanza dal processore. Importante sono anche:

• Il tempo di vita di una memoria. Indica infatti per quanto tempo i dati possono rimanere memorizzati.
• L’affidabilità. Indica il grado di errore che si può incontrare nel rileggere dalla memoria un dato scritto e la capacità di mantenere l’informazione.

immagazzinare e recuperare i dati in modo efficiente, viene utilizzata una gerarchia di memoria. La cache è una memoria molto veloce e di piccole dimensioni che si trova direttamente sul processore. Viene utilizzata per memorizzare temporaneamente i dati e le istruzioni più frequentemente utilizzati, in modo da ridurre i tempi di accesso alla memoria principale. La memoria principale, o RAM, è una memoria più grande ma più lenta rispetto alla cache. Contiene tutti i dati e le istruzioni necessari per l'esecuzione dei programmi. La RAM è organizzata in celle di memoria, ognuna delle quali può contenere un byte di dati. Oltre alla RAM, esistono anche altre forme di memoria, come ad esempio la memoria di massa, utilizzata per memorizzare permanentemente i dati anche quando il computer è spento. Esempi di memoria di massa sono gli hard disk e le unità a stato solido. La gerarchia di memoria è organizzata in modo tale che le memorie più veloci e costose si trovino più vicine al processore, mentre le memorie più lente e meno costose si trovino più lontane. In questo modo, i dati e le istruzioni più frequentemente utilizzati vengono memorizzati nelle memorie più veloci, riducendo i tempi di accesso complessivi. Le architetture multi-processore sono sistemi che utilizzano più di un processore per eseguire i programmi. Questo permette di aumentare la potenza di calcolo complessiva del sistema e di eseguire più programmi contemporaneamente. I processori possono essere collegati tra loro tramite una rete di comunicazione, che permette loro di scambiarsi dati e coordinare le operazioni. Le architetture multi-processore possono essere utilizzate in diversi contesti, come ad esempio nei server, nei supercomputer o nei sistemi embedded.

eseguire le istruzioni il processore ha bisogno di prelevare dalla memoria sia la loro codifica che gli operandi necessari per la loro esecuzione e copiarli all'interno dei propri registri dove può modificare i dati. Queste operazioni si chiamano accessi in memoria. Gli accessi alla memoria avvengono attraverso il bus di comunicazione. Le operazioni in memoria e sui registri avvengono con velocità diverse.

Il processore è in grado di elaborare dati ad una velocità di circa un miliardo di byte al secondo. La memoria riesce a fornire soltanto 20 milioni di byte in un secondo.

Un'istruzione che richiede un accesso in memoria è circa 50 volte più lenta di un'altra operazione che non richiede tale accesso. Un'istruzione i cui operandi siano già presenti nei registri del processore riesce a eseguire a velocità massima. Invece quando gli operandi vengono scritti o letti nella memoria, l'istruzione impiega circa

50 volte in più. Per migliorare il problema di rallentamento della CPU sono state introdotte le memorie cache. La cache è una memoria più piccola della memoria principale ma più veloce. Il processore è in grado di accedere a circa 100 milioni di byte al secondo della memoria cache. La memoria cache è posizionata fra il processore e la memoria principale, serve a contenere dati che saranno utilizzati frequentemente in futuro. Quando il processore ha necessità di alcuni dati dalla memoria, vengono prelevati sia i dati richiesti che altri dati presenti in celle di memoria limitrofe. Tutti i dati prelevati dalla memoria vengono copiati nella cache. I dati necessari per svolgere l'istruzione vengono copiati nei registri interni e l'istruzione viene normalmente eseguita. I benefici della cache si manifestano durante l'esecuzione delle istruzioni. Permette un accesso a tali dati circa 5 volte più veloce rispetto al loro accesso.

dalla memoria. Il principio che permette alla cache di migliorare le prestazioni della CPU si chiama principio di località, cioè quando vengono presi dei dati dalla memoria con alta probabilità verranno presi anche dati presenti in locazioni di memoria limitrofe.

ALGORITMICA

Problemi e algoritmi

Nella vita quotidiana si sente spesso parlare di algoritmi. In contesti positivi: la ricerca rapida di informazioni in una grande mole di dati o il riconoscimento e la manipolazione di suoni ed immagini con strumenti alla portata di tutti. In contesti negativi: ci sentiamo osservati per i nostri comportamenti su internet o sui social network.

L'algoritmo viene associato a un calcolo, a un programma per computer oppure un'app, in sistema informatico. L'algoritmo serve per passare dai dati in ingresso o input al risultato finale, cioè l'uscita o output.

Definizione algoritmo: "un algoritmo è un insieme di istruzioni ordinate, non ambigue ed

effettivamente eseguibili, seguendo le quali per ogni ingresso di tipo appropriato siottiene un'uscita in un numero finito di passi.

Elementi importanti:

• L'ingresso deve essere finito e possedere una struttura completa e non ambigua delle informazioni. Fissato il modo con cui i dati vengono rappresentati.
• Le istruzioni non devono essere ambigue ed effettivamente seguibili. Fare riferimento ad un insieme finito e prefissato di operazioni di base eseguibili. Le operazioni di base formano il modello di calcolo.
• La codifica dell'algoritmo, la descrizione precisa che venendo eseguita da un computer utilizzerà uno dei tanti linguaggi di programmazione.
• La terminazione, la richiesta che per ogni ingresso appropriato l'esecuzione termini in un numero finito di passi.

Un algoritmo non è una qualunque procedura, ma è una strategia per risolvere un problema ben definito. Diciamo che un problema computazionale è ben

definito quando sono specificati: - L'insieme degli input (ingressi ammissibili). - L'insieme degli output (risultati corretti in funzione degli input). Un problema algoritmo è una specifica di input ed output. L'istanza del problema è un caso particolare di input. Un algoritmo risolve un problema algoritmo se produce un'uscita corretta per ogni istanza ammissibile. Per illustrare il concetto menzioniamo alcuni problemi algoritmici: - Ordinamento (sorting). Si chiede di ordinare una lista di elementi secondo un criterio. - Torre di Hanoi. Si chiede di spostare una torre di dischi secondo certe regole. - Ciclo di Hamilton. Esiste un percorso nella rete che attraversa i nodi esattamente una volta. - Ricoprimento o tassellata di una superficie con piastrelle (tailing problem). Dato un problema algoritmo se esiste una soluzione che lo risolve, allora ne esisteranno infinite altre. Tuttavia spesso esistono soluzioni diverse dello stesso problema.

stessoproblema.

Il problema di ordinare una lista di parole.