Calcolo parallelo/calcolatori II @unipd

[BeBrA]

Salve!

Sto preparando l'esame di calcolatori II e mi sono abbattuto in questo esercizio:
(Se c'e' qualcuno dell'università di padova che sta seguendo il corso, l'esercizio è a pagina 7 della dispensa.)
Ecco il testo.

PREFIX COMPUTATION:
Sia N2^n e sia x=(x0,...xN-1) una sequenza di elementi di un semigruppo. Sia P2^d, con P<=N.

a) Si descriva un algoritmo per calcolare i prefissi y=(y0,..yN-1) delal sequenza x su linear array di P nodi, assumendo che (per j=0,1,...P-1) il nodo j contenga inizialmente gli elementi xjN/P+k con k0,1,....,N/P-1.

b) Si analizzi il tempo T(N,P) dell'algoritmo proposto e si determini il valore di P che minimizza tale tmpo pr un dato valore di N.

c) Si dimostri che, comunque si scelga P, T=Omega(radice(N)) per qualsiasi algoritmo. (Considerare le distanze tra i dati ed il numero di operazioni da svolgere).

Grazie!

[EnricoMic]

Ciao,
anch'io sto' preparando CP e arriverò fra un paio di giorni a fare quel tema.
Se vuoi ci possiamo dare una mano l'un l'altro.

Andando in ordine nella dispensa io ho già avuto problemi a risolvere i punti b e c del secondo esercizio del tema datato 13 settembre 2004. Tu come li hai risolti?

A risentirci

[FreeMan]

spero per lui che dal 2004 ad oggi l'esame l'abbia dato e l'abbia passato

e cmq era OT allora, lo è adesso e qui non si fanno esercizi altrui.


e ti sei pure iscritto apposta

CLOSED!!

>bYeZ<