Eguaglianza tra sommatorie
Salve.
Ho due sommatorie che corrispondono al carico di lavoro di due thread. Come posso scegliere M per bilanciare il carico di lavoro.
E' evidente che il secondo thread ha un carico maggiore.
t1 = $\sum_{i=0}^M (i+1)t$
t2 = $\sum_{i=M}^(2M) (i+1)t$
dove $M = text{arr.length} / 2$
Se pongo t1 = t2 trovo che $M = 3M$.
Grazie anticipatamente.
Ho due sommatorie che corrispondono al carico di lavoro di due thread. Come posso scegliere M per bilanciare il carico di lavoro.
E' evidente che il secondo thread ha un carico maggiore.
t1 = $\sum_{i=0}^M (i+1)t$
t2 = $\sum_{i=M}^(2M) (i+1)t$
dove $M = text{arr.length} / 2$
Se pongo t1 = t2 trovo che $M = 3M$.
Grazie anticipatamente.
Risposte
Cos'è $t$?
Un parametro? Una costante?
Assumendo che $t$ sia una costante, tieni presente che:
\[
\begin{split}
t_2 &\stackrel{j=i-M}{=} \sum_{j=0}^M (j+1+M)t\\
&= \sum_{j=0}^M (j+1)t + Mt\\
&= \sum_{j=0}^M (j+1)t + \sum_{j=0}^M Mt\\
&= t_1 + M(M+1)t
\end{split}
\]
quindi difficilmente avrai $t_2=t_1$.
P.S.: È buona norma astenersi da scrivere "è evidente che" o "è banale che" se quello che segue è evidente o banale solo per chi scrive.
Un parametro? Una costante?
Assumendo che $t$ sia una costante, tieni presente che:
\[
\begin{split}
t_2 &\stackrel{j=i-M}{=} \sum_{j=0}^M (j+1+M)t\\
&= \sum_{j=0}^M (j+1)t + Mt\\
&= \sum_{j=0}^M (j+1)t + \sum_{j=0}^M Mt\\
&= t_1 + M(M+1)t
\end{split}
\]
quindi difficilmente avrai $t_2=t_1$.
P.S.: È buona norma astenersi da scrivere "è evidente che" o "è banale che" se quello che segue è evidente o banale solo per chi scrive.
Si hai perfettamente ragione e riformulo la domanda.
Ho una procedura:
Il metodo processValue ha però tempi di esecuzione diversi:
per ogni $i>=0$ richiede tempo $(i+1)t$.
Se la computazione dell'array viene divisa in due thread e ognuno prende in pasto come carico la metà dell'array, allora i tempi di esecuzione dei thread sono bilanciati e come si potrebbe distribuire meglio il carico??
Grazie
Ho una procedura:
algo run()
for i<-0 to array.length do
ans += processValue(array[i])
Il metodo processValue ha però tempi di esecuzione diversi:
per ogni $i>=0$ richiede tempo $(i+1)t$.
Se la computazione dell'array viene divisa in due thread e ognuno prende in pasto come carico la metà dell'array, allora i tempi di esecuzione dei thread sono bilanciati e come si potrebbe distribuire meglio il carico??
Grazie
ciao,
allora, tu hai:
$t_1 = sum_{i=0}^x (i+1)t$
$T = sum_{i=0}^{L-1} (i+1)t$
con $t_1$ il tempo del primo thread, $T$ il tempo totale del processo non parallelizzato, $t$ valore costante, $L$ lunghezza del vettore da processare, $x$ la nostra incognita, ovvero la "porzione" di vettore da far processare al primo thread per equilibrare il carico.
Affinchè il carico di lavoro sia equamente distribuito tra i due thread, dobbiamo avere $t_1 = T / 2$
Inoltre, risolvendo le sommatorie, abbiamo: $t_1 = t(x+1)(1+x/2)$ e $T=tL(1+{L-1}/2)$
sostituendo queste espressioni all'equazione precedente, si trova la soluzione univoca:
$x_{opt}={-3+sqrt(1+2L+2L^2)}/2$, notare inoltre che , per $L->+\infty$, \(x_{opt}(L) \sim L/\sqrt 2 > L/2\) proprio come ci aspettavamo
allora, tu hai:
$t_1 = sum_{i=0}^x (i+1)t$
$T = sum_{i=0}^{L-1} (i+1)t$
con $t_1$ il tempo del primo thread, $T$ il tempo totale del processo non parallelizzato, $t$ valore costante, $L$ lunghezza del vettore da processare, $x$ la nostra incognita, ovvero la "porzione" di vettore da far processare al primo thread per equilibrare il carico.
Affinchè il carico di lavoro sia equamente distribuito tra i due thread, dobbiamo avere $t_1 = T / 2$
Inoltre, risolvendo le sommatorie, abbiamo: $t_1 = t(x+1)(1+x/2)$ e $T=tL(1+{L-1}/2)$
sostituendo queste espressioni all'equazione precedente, si trova la soluzione univoca:
$x_{opt}={-3+sqrt(1+2L+2L^2)}/2$, notare inoltre che , per $L->+\infty$, \(x_{opt}(L) \sim L/\sqrt 2 > L/2\) proprio come ci aspettavamo
Scusa ma faccio fatica a capire. Quindi quel'è la percentuale di carico che dovrebbe avere il primo thread e quale il secondo?
No sarebbe più facile calcolare separatamente la quantità dell'uno e dell'altro e capirne dal rapporto la differenza??
No sarebbe più facile calcolare separatamente la quantità dell'uno e dell'altro e capirne dal rapporto la differenza??
La percentuale di carico si trova dividendo la lunghezza da processare nel primo thread (esplicitata dalla variabile $x_{opt}$, soluzione della sopracitata equazione) per la lunghezza totale del vettore.
Quindi la porzione relativa sarebbe:
$l_1 = {-3+sqrt(1+2L+2L^2)}/{2L}$ che, per $L->+\infty$ tende a $sqrt(2)/2$.
Quindi diciamo che, per vettori di proporzioni abbastanza grandi, la porzione percentuale per il carico del primo thread si avvicina al $71%$
Quindi la porzione relativa sarebbe:
$l_1 = {-3+sqrt(1+2L+2L^2)}/{2L}$ che, per $L->+\infty$ tende a $sqrt(2)/2$.
Quindi diciamo che, per vettori di proporzioni abbastanza grandi, la porzione percentuale per il carico del primo thread si avvicina al $71%$
Grazie mille 
E di consequenza il secondo thread dovrebbe processarne circa il $30%$ per far si che i due thread siano bilanciati, giusto?
E di consequenza il secondo thread dovrebbe processarne circa il $30%$ per far si che i due thread siano bilanciati, giusto?
Ma in $l1$ la divisione non dovrebbe essere solo per $2$ e non $2L$ ??!?! E' un refuso o da dove viene fuori?
Quello è il rapporto tra la lunghezza del vettore processato dal primo thread e la lunghezza totale del vettore:
$x_{opt}/L = {{-3+sqrt(1+2L+2L^2)}/2}/L ={-3+sqrt(1+2L+2L^2)}/{2L}$
$x_{opt}/L = {{-3+sqrt(1+2L+2L^2)}/2}/L ={-3+sqrt(1+2L+2L^2)}/{2L}$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo