Please enable JavaScript.
Coggle requires JavaScript to display documents.
Memoria Esterna - Coggle Diagram
Memoria Esterna
Modello Computazionale
formato da
Modello architetturale
semplificazione sistema di calcolo
Modello di programmazione
insieme istruzioni offerte per
la specifica degli algoritmi
Modello di costo
funzioni che associano algoritmo
alla misura delle sue prestazioni
Modello RAM
cpu<-->ram
processore può accedere direttamente in ogni livello di memoria allo stesso tempo
operazioni elementari
PROBLEMI GRANDE DIMENSIONE
insieme dati input o output superiore alla memoria RAM a disposizione
come superarli
Memoria Virtuale
NON SI PUO' PIU' SUPPORRE COSTANTE IL TEMPO DI ACCESSO A TUTTI I DATI
Uso esplicito Memoria secondaria
per adattarla alle esigenze del proprio problema
prestazioni valutate in tempo e spazio
Modello Disco
cpu<->ram<->disk
operazioni elementari + operazioni di lettura su disco (I/O)
prestazioni valutate tramite due metriche temporali
WORK: operazioni elementari
TRANSFER: operazioni di I/O
incoraggia utilizzo località temporale e spaziale
Problemi Tipici
Batched Problems
si deve accedere a tutti i dati senza un preprocessing
On line Problems
forniscono risposte ad interrogazioni
pre organizzazione dei dati
dati statici o dinamici
OPERAZIONI
Notazione
N
dimensione del problema
n=N/B
M
dimensione della memoria interna
m=M/B
B
dimensione del blocco trasferito
Q
numero di interrogazioni
Z
dimensione della risposta
z=Z/B
operazioni fondamentali
Sort(N) : Ordinamento file N elementi
theta(n log_m n)
Search(N) : Ricerca insieme N dati ordinati
theta( log_B N)
con tecniche hash theta(1)
Scan(N) : lettura di un file di N elementi
theta(n)
Output(Z) : Restituzione di Z elementi in risposta a una query
theta(max{1,z})