Valutiamo ora la complessit`a computazionale del nostro algoritmo, ricorrendo ad un’analisi asintotica al caso pessimo. Per semplificare la notazione, all’interno dello pseudo-codice indicheremo i parametri di un ciclo riportando solo il numero di iterazioni da esso compiute:
for (i = 0; i < N ; i++) do for (N ) do
. . . ≡ . . .
end for end for
Ci concentriamo innanzitutto sulla funzioneoptimal_scheduler, che implementa l’algo-ritmo DP. Non riportiamo tutte le varie operazioni elementari, che danno un contributo costante in termini di complessit`a e sono quindi trascurabili. Non riportiamo inoltre cicli con un numero di iterazioni pari a N (a meno che non siano annidati), cio`e il numero delle appliance controlla-bili: si assume ragionevolmente che N sia sempre piuttosto basso (tipicamente non superiore a 4 o 5 nell’arco di 24 ore), quindi anche questi cicli sono trascurabili.
Indichiamo con R il numero di stati di {r} e {eR}, con W la durata della procedura DP (che al caso pessimo coincide appunto con la durata massima della finestra di previsione) e con M il massimo numero di stati che il controllo ukpu`o assumere. Ricordiamo che lo stato complessivo (xk, yk) del nostro modello `e determinato da {rk}, {eRk}, uk−1 e sAT Tk(par. 2.5.1), pertanto, al caso peggiore, il numero totale di stati da considerare nel procedimento di minimizzazione del costo sar`a sempre R2M .
optimal scheduler: for (R2M ) do
inizializza vettore costi; end for for (R2M ) do for (N ) do inizializza sAT T0 W; end for end for for (W ) do / / ciclo I for (R2M ) do
inizializza contatore deadline mancate; end for
for (W ) do
conta slot low cost; end for
for (R2M ) do / / ciclo II for (R) do
for (R) do
calcola pij dei macrostati per ogni j; end for
end for
for (2N) do / / ciclo III for (R2) do
calcola J (j) per ogni j; end for
for (R2) do
end for end for end for for (R2M ) do
for (N ) do
controlla se hai gi`a completato tutte le attivit`a; end for
end for end for
Si osserva che il contributo pi`u consistente, in termini di complessit`a, `e dato dall’anni-damento dei cicli denominati I, II e III. Il ciclo I determina lo spostamento a ritroso di uno slot alla volta; il ciclo II, all’inizio del generico slot k, permette di valutare tutti gli stati (xk, yk) possibili per il calcolo del costo atteso; il ciclo III consente di valutare tutte le azioni di controllo uk, per individuare quella di costo minimo. Per quest’ultimo ciclo contiamo 2N iterazioni (tutti i possibili valori del vettore binario b), con all’interno R2+ R2 operazioni, quindi in totale 2R22N operazioni.
Per il ciclo II contiamo R2M iterazioni, con all’interno il contributo appena determinato, pi`u R2operazioni, quindi:
R2M (2R22N+ R2) = R4M (2 · 2N + 1).
Per il ciclo I abbiamo W iterazioni, con all’interno il contributo calcolato sopra, pi`u R2M + W operazioni: W R2M + W + R4M (2 · 2N + 1) .
Il termine introdotto dal ciclo II `e approssimabile con O R4M 2N, pertanto il termine R2M + W `e trascurabile nell’analisi asintotica. La complessit`a dei tre cicli annidati risulta quindi O W R4M 2N. A questo vanno aggiunte le R2M e R2M N iterazioni dei cicli iniziali della funzione, che per`o divengono anch’esse trascurabili. Possiamo allora concludere che la complessit`a dioptimal_scheduler `e O W R4M 2N.
N 1 2 3 4 5 6 7 8 9 10
2N 2 4 8 16 32 64 128 256 512 1024
N2 1 4 9 16 25 36 49 64 81 100
N3 1 8 27 64 125 216 343 512 729 1000
Tabella 3.2: Confronto tra le funzioni 2N, N2, N3per N ≤ 10
Generalmente, complessit`a asintotiche dipendenti da funzioni esponenziali sono indice di algoritmi molto poco efficienti. Tuttavia, dato che ci si aspetta un numero di appliance controllabili, come osservato in precedenza, tipicamente non superiore a 4 o 5, la funzione 2N nel nostro caso non grava eccessivamente sulla complessit`a. Essa `e anzi abbondantemente sovra-dominata dalla funzione cubica fino a N = 9, e l’andamento si avvicina molto a quello della funzione quadratica fino a N = 5, come si pu`o osservare nella Tabella 3.2.
Analizziamo ora la complessit`a computazionale del main, riportandone lo pseudo-codice semplificato secondo le stesse considerazioni fatte per la funzione optimal_scheduler . Tralasciamo per il momento le istruzioni eseguite dalla funzionepower_calcper il calcolo della potenza o damarkov_evolper l’evoluzione delle MC (nel caso si utilizzi la versione per le simulazioni), che danno comunque un contributo trascurabile nella complessit`a totale, come vedremo in seguito.
Indichiamo con S la durata massima (in slot) di una qualunque attivit`a schedulabile. Al caso pessimo tutte le N attivit`a avranno ovviamente durata pari a S. Non teniamo conto del tempo di attesa forzato tra due chiamate successive aoptimal_scheduler(30 minuti), nel caso si utilizzi la versione normale, che non riguarda l’efficienza dell’algoritmo.
Main:
for (R2W ) do
carica matrici di transizione di r; end for
for (R2W ) do
carica matrici di transizione di eR; end for
controlla correttezza matrici di r; controlla correttezza matrici di eR; end for for (N ) do for (N ) do ordina deadline; end for end for for (N ) do for (S) do
inizializza a 0 matrice dei prof ili energetici; end for
end for for (N ) do
for (S) do
riempi matrice dei prof ili energetici; end for end for while do / / ciclo IV eseguioptimal_scheduler; for (N ) do for (S) do aggiorna variabili; end for end for end while
La parte iniziale del main comprende 3R2W iterazioni per il caricamento e il controllo delle matrici di transizione dei processi {r} e {eR}. Seguono le istruzioni per ordinare le appliance
in base alle rispettive dead-line e riempire la matrice N × S che ne raccoglie i profili energetici, aggiungendo cos`ı N2+ 2N S iterazioni.
Il ciclo IV comporta, nel caso peggiore, W esecuzioni dioptimal_schedulere aggior-namenti vari (trascurabili rispetto al contributo di queste ultime). Si deve per`o osservare che, ad ogni esecuzione, la finestra su cui agisce l’algoritmo DP diminuisce di uno slot, quindi in realt`a la complessit`a dioptimal_schedulernon `e fissa: se indichiamo con I il numero delle iterazioni compiute prima della sua chiamata, essa `e pari a O (W − I)R4M 2N. Ci`o significa che, alla prima iterazione del while l’algoritmo DP richieder`a un tempo O W2R4M 2N, mentre diverr`a sempre pi`u veloce nelle iterazioni successive, finch´e all’ultima richieder`a un tempo W volte inferiore, cio`e O W R4M 2N.
La complessit`a introdotta dalla parte iniziale diventa ovviamente trascurabile, pertanto la complessit`a totale del main, dopo un numero generico I di iterazioni, risulta O W (W − I)R4M 2N.
Analizziamo molto rapidamente le complessit`a dipower_calcemarkov_evol, dimo-strando che esse sono effettivamente trascurabili.
Inpower_calc(par.3.3.2), ci`o che “appesantisce” la complessit`a `e il calcolo della DFFT per i segnali di tensione e corrente. Se indichiamo con F il numero di campioni in cui `e discretizzato il dominio della Trasformata (che deve essere una potenza di 2), la complessit`a di tale calcolo `e O F log2F [10]. Attualmente si utilizza un numero di campioni pari a F = 512, pertanto O F log2F < O W (W − I)R4M 2N.
Per quanto riguardamarkov_evol, il contributo maggiore nel tempo di esecuzione `e dato dal calcolo dei sotto-intervalli in [0, 1] (par.3.5.1) mediante una somma di probabilit`a che richiede ogni volta un numero di accessi a una determinata riga della matrice di transizione pari a: R X i=1 i = R(R + 1) 2 = R2 2 + R 2 .
Questo avviene sia per il processo {r} sia per {eR}, e viene ripetuto per tutti i W slot della finestra di previsione. Il numero di iterazioni risulta quindi W 2R2, da cui la complessit`a O(W R2).