Algoritmos paralelos y distribuidos [2010-11-09 Tue]--[2010-11-18 Thu]
Jérémy Barbay 9 Nov 201009/11/10 at 11:332010-11-09 11:33:09
Algoritmos paralelos y distribuidos (2 semanas = 4 charlas)
===========================================================
[2010-11-09 Tue]--[2010-11-18 Thu]
- Medidas de complejidad
- Técnicas de diseño
REFERENCIA: Chap 12 of "Introduction to Algorithms, A Creative Approach",
Udi Manber, p. 375
REFERENCIA: [www.catonmat.net/ ... ithms-part-thirteen/]
Table of Contents
=================
1 Modelos de paralelismo
2 Modelo PRAM
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
4 PROBLEMA: Calcular Max(A[1,...,N])
5 LEMA de Brent
6 DEFINICIÓN "Trabajo"
7 COROLARIO
8 EJEMPLO
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
10 PROBLEMA: Ranking en listas
1 Modelos de paralelismo
~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Instrucciones
- SIMD: Single Instrucción, Múltiple Data
- MIMD: Múltiple Instrucción, Múltiple Data
* Memoria
- compartida
- distribuida
* 2*2 combinaciones posibles:
Memoria compartida Memoria distribuida
------+--------------------+-----------------------------------------------------
SIMD PRAM redes de interconexión (weak computer units)
(hipercubos, meshes, etc...)
------+--------------------+-----------------------------------------------------
MIMD Threads procesamiento distribuido (strong computer units),
Bulk Synchronous Process, etc...
* En este curso consideramos en particular el modelo PRAM
2 Modelo PRAM
~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Mucha unidad de CPU, una sola memoria RAM
cada procesador tiene un identificador único, y puede utilizarlo
en el programa
* Ejemplo:
+ if p mod 2 = 0 then
+ A[p] += A[p-1]
+ else
+ A[p] += A[p+1]
+ b <- A[p];
+ A[p]<- b;
* Problema: el resultado no es bien definido, puede tener
*conflictos* si los procesadores están asinchronos. Las soluciones a
este problemas dan varios submodelos del modelo PRAM:
1. EREW Exclusive Read. Exclusive Write
2. CREW Concurrent Read, Exclusive Write
3. CRCW Concurrent Read, Concurent Write
En este caso hay variantes también:
- todos deben escribir lo mismo
- arbitrario resultado
- priorizado
- alguna f() de lo que se escribe
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* DEFINICIÓN:
- $T^*(n)$ es el *Tiempo secuencial* del mejor algoritmo no
paralelo en una entrada de tamaño $n$ (i.e. usando $1$
procesador).
- $T_A(n,p)$ es el *Tiempo paralelo* del algoritmo paralelo
$A$ en una entrada de tamaño $n$ usando $p$ procesadores.
- El *Speedup* del algoritmo $A$ es definido por
$S_A(n,p) = \frac{ T^*(n) }{ T_A(n,p) } \leq p$
Un algoritmo es mas efectivo cuando $S(p)=p$, que se llama
*speedup perfecto*.
- La *Eficiencia* del algoritmo $A$ es definida por
$E_A(n,p) = \frac{ S_A(n,p) }{ p }=\frac{T^*(n)}{pT_A(n,p)}$
El caso óptima es cuando $E_A(n,p)=1$, cuando el algoritmo
paralelo hace la misma cantidad de trabajo que el algoritmo
secuencial. El objetivo es de *maximizar la eficiencia*.
(Nota estas definiciones en la pisara, vamos a usarlas después.)
4 PROBLEMA: Calcular Max(A[1,...,N])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
1. Solucion Secuencial
* Algoritmo:
- $m \leftarrow 1$
- for $i\leftarrow 2$ to $n$
- if $A[i]>A[m]$ then $m\leftarrow i$
- return $A[m]$
* Se puede ver como un arbol de evaluación con una sola rama
de largo $n$ y $n$ hojas.
* Complejidad:
- tiempo $O(n)$, con $1$ procesador, entonces:
- $T^*(n)=n$.
2. Solucion Parallela con $n$ procesadores
* Algoritmo:
- $M[p] \leftarrow A[p]$
- for $l\leftarrow 0$ to $\lceil \lg p \rceil -1$
- if $p \mod 2^{l+1}=0$ y $ p+2^l
Si un algoritmo consigue un tiempo T(n,p)=C,
entonces consigue tiempo T(n,p/s)= sC \forall s>1
(bajo algunas condiciones)
6 DEFINICIÓN "Trabajo"
~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Usando el Lema de Brent, podemos exprimir el rendimiento de
los algoritmos paralelos con dos medidas:
- $T(n)$, el tiempo del algoritmo paralelo usando cualquier
cantidad de procesadores que quiere.
Nota la diferencia con
+ $T^*(n)$, el tiempo del mejor algoritmo secuencial, y
+ $T_A(n,n)$, el tiempo del algoritmo con $n$ procesadores.
- $W(n)$, la suma del total trabajo ejecutado por todo los
procesadores.
7 COROLARIO
~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Con el lema de Brent podemos obtener:
- $$T(n,p) = T(n) + \frac{ W(n) }{ p }$$
- $$E(n,p) = \frac{ T^*(n) }{ pT(n) + W(n) }$$
8 EJEMPLO
~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
* Para el calculo del máximo:
- $T(n) = \lg n$
- $W(n) = n$
* Entonces
- se puede obtener
- $T_B(n,p) = \lg n + {n \over p}$
- $$E(n,p) = \frac{ n }{ p\lg n + n }$$
* (Nota que eso es solamente una cota superior, nuestro
algoritmo da un mejor tiempo.)
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
* DEFINICIÓN: Problema "Prefijo en Paralelo"
Dado $x_1,\ldots, x_n$ y un operador asociativo \times
calcular
- $y_1 = x_1$
- $y_2 = x_1\times x_2$
- $y_2 = x_1\times x_2 \times x_3$
- ...
- $y_n = x_1\times \ldots \times x_n$
* Solucion Secuencial
Hay una solucionó obvio en tiempo O(n).
* Solucion paralela 1
* Concepto:
- Hipótesis: sabemos solucionarlo con $n/2$ elementos
- Caso de base: $n=1$ es simple.
- Inducción:
1. recursivamente calculamos en paralelo:
- todos los prefijos de $\{x_1,\ldots,x_{n/2}\}$ con
$n/2$ procesadores.
- todos los prefijos de $\{x_{n/2},\ldots,x_n\}$ con
$n/2$ procesadores.
2. en paralelo agregamos $x_{n/2}$ a los prefijos de
$\{x_{n/2},\ldots,x_n\}$
* ParallelPrefix1(i,j)
- if $i_p=j_p$
- return x_{i_p}
- $m_p \leftarrow \lfloor \frac{i_p + j_p}{2} \rfloor$;
- if $p\leq m$ then
- algo( i_p, m_p )
- else
- algo(m+1, j_p)
- y_p \leftarrow y_m . y_p
* Otra forma del algoritmo (de p. 384 de "Introduction to
Algorithms, A Creative Approach", Udi Manber):
+ ParallelPrefix1(left,right)
- if (right-left) = 1
- x[right] <- x[left] . x[right]
- else
- middle <- (left+right-1)/2
- do in paralel
- ParallelPrefix1(left,middle) {assigned to {P_1 to P_{n/2}}}
- ParallelPrefix1(middle+1,right) {assigned to {P_{n/2+1} to P_n}}
- for i <- middle+1 to right do in paralel
- x[i] <- x[middle] . x[i]
* Notas:
- este solucion *no* es EREW (Exclusive Read&Write), porque
los procesadores pueden leer $y_m$ al mismo tiempo.
- este solucionó es CREW (Concurrent Read, Exclusive Write).
- Complejidad:
- $T_{A_1}(n,n) = 1+ T(n/2,n/2) = \lg n$
(El mejor tiempo en paralelo con cualquier cantidad de
procesadores.)
- $W_{A_1}(n) = n + 2 W_{A_1}(n/2) - n\lg n$
- $T_{A_1}(n,p) = T(n) + W_{A_1}(n)/p = \lg n + (n\lg n)/p$
- Calculamos $p^*$, la cantidad óptima de procesadores
para minimizar el tiempo:
- $T(n) = W_{A_1}(n) /p^*$
- $p^* = \frac{ W(n) }{ T(n) } = n$
- Calculamos la eficiencia
- $E_{A_1}(n,p^*)
= \frac{ T^*(n) }{ p^* T(n)+W(n) }
= \frac{ n }{ n\lg n }
= {1 \over \lg n}$
- es poco eficiente =(
- PodrÃ-amos tener un algoritmo con
- la eficiencia del algoritmo secuencial
- el tiempo del algoritmo paralelo?
* Solucion paralela 2: mismo tiempo, mejor eficiencia
- Idea:
El concepto es de dividir de manera diferente: par y impar
(en vez de largo o pequeño).
- Concepto:
1. Calcular en paralelo $x_{2i-1}.x_{2i}$ en $x_{2i}$
para $\forall i, 1\leq i \leq n/2$.
2. Recursivamente, calcular todos los prefijos de
$E=\{ x_2,x_4,\ldots, x_{2i},\ldots, x_n \}$
3. Calcular en paralelo los prefijos en posiciones impares,
multiplicando los prefijos de $E$ por una sola valor.
- algo2(i,j)
- for $d\leftarrow 1$ to $(\lg n)-1$
- if $p=0 \mod 2^{d+1}$
- if $p+2^d0$
- $x_{p-2^d} \leftarrow x_{p-2^d}.x_p$
- visualización
0.
1. [0,1]
2.
3. [2,3] [0,3]
4.
5. [4,5]
6.
7. [6,7] [4,7] [0,7]
8.
9. [8,9]
10.
11. [10,11] [8,11]
12.
13. [12,13]
14.
15. [14,15] [12,15] [8,15] [0,15]
- Notas:
- Este algoritmo es EREW
- Análisis
- $T_2(n) = 2\lg n$
- $W(n) = n + W(n.2) = n$
- $T_2(n,p) = T(n) + W(n)/p = 2\lg n + \frac{n}{p}$
- Calculamos la cantidad óptima de procesadores para obtener
el tiempo óptima:
- $T_2(n) = W(n) / p^*$ entonces
- $p^* = {W(n) \over T(n)} = {n\over\lg n}$
- $E_2(n,p^*) = { T^*(n) \over p^* T(n)+ W(n)} = n/n \in O(1)$
10 PROBLEMA: Ranking en listas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
1. DEFINICIÓN
- dado una lista, calcula el rango para cada elemento.
- En el caso de una lista tradicional, no se puede hacer
mucho mejor que lineal.
- Consideramos una lista en un arreglo $A$,
- donde cada elemento $A[i]$ tiene un puntero al siguiente
elemento, $N[i]$, y
- calculamos su rango $R[i]$ en un arreglo $R$.
2. DoublingRank()
- $R[p] \leftarrow 0$
- if $N[p] = null$
- R[p] \leftarrow 1
- for $d\leftarrow 1$ to $\lceil\lg n\rceil$
- if $N[p]\neq NULL$
- if $R[N[p]]>0$
- $R[p] \leftarrow R[N[p]]+2^d$
- $N[p] \leftarrow N[N[p]]$
3. Análisis
- T(n) = \lg n
- W(n) = n + W(n/2) = O(n)
- T(n,p) = T(n) + W(n)/p = \lg n + n/p
- p^*
T(n) = W(n) / p^*
p n/\lg n
- E(n,p^*) = \frac{T^*(n)}{ p^* T(n) + W(n) }
= \frac{ n }{ n/\lg n \lg n +n}
= \Theta(1)
4. El algoritmo es EREW o CREW?
- es EREW si los procesadores están sincronizados, com en RAM
aquÃ-.
===========================================================
[2010-11-09 Tue]--[2010-11-18 Thu]
- Medidas de complejidad
- Técnicas de diseño
REFERENCIA: Chap 12 of "Introduction to Algorithms, A Creative Approach",
Udi Manber, p. 375
REFERENCIA: [www.catonmat.net/ ... ithms-part-thirteen/]
Table of Contents
=================
1 Modelos de paralelismo
2 Modelo PRAM
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
4 PROBLEMA: Calcular Max(A[1,...,N])
5 LEMA de Brent
6 DEFINICIÓN "Trabajo"
7 COROLARIO
8 EJEMPLO
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
10 PROBLEMA: Ranking en listas
1 Modelos de paralelismo
~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Instrucciones
- SIMD: Single Instrucción, Múltiple Data
- MIMD: Múltiple Instrucción, Múltiple Data
* Memoria
- compartida
- distribuida
* 2*2 combinaciones posibles:
Memoria compartida Memoria distribuida
------+--------------------+-----------------------------------------------------
SIMD PRAM redes de interconexión (weak computer units)
(hipercubos, meshes, etc...)
------+--------------------+-----------------------------------------------------
MIMD Threads procesamiento distribuido (strong computer units),
Bulk Synchronous Process, etc...
* En este curso consideramos en particular el modelo PRAM
2 Modelo PRAM
~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* Mucha unidad de CPU, una sola memoria RAM
cada procesador tiene un identificador único, y puede utilizarlo
en el programa
* Ejemplo:
+ if p mod 2 = 0 then
+ A[p] += A[p-1]
+ else
+ A[p] += A[p+1]
+ b <- A[p];
+ A[p]<- b;
* Problema: el resultado no es bien definido, puede tener
*conflictos* si los procesadores están asinchronos. Las soluciones a
este problemas dan varios submodelos del modelo PRAM:
1. EREW Exclusive Read. Exclusive Write
2. CREW Concurrent Read, Exclusive Write
3. CRCW Concurrent Read, Concurent Write
En este caso hay variantes también:
- todos deben escribir lo mismo
- arbitrario resultado
- priorizado
- alguna f() de lo que se escribe
3 Como medir el "trade-off" entre recursos (cantidad de procesadores) y tiempo?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
* DEFINICIÓN:
- $T^*(n)$ es el *Tiempo secuencial* del mejor algoritmo no
paralelo en una entrada de tamaño $n$ (i.e. usando $1$
procesador).
- $T_A(n,p)$ es el *Tiempo paralelo* del algoritmo paralelo
$A$ en una entrada de tamaño $n$ usando $p$ procesadores.
- El *Speedup* del algoritmo $A$ es definido por
$S_A(n,p) = \frac{ T^*(n) }{ T_A(n,p) } \leq p$
Un algoritmo es mas efectivo cuando $S(p)=p$, que se llama
*speedup perfecto*.
- La *Eficiencia* del algoritmo $A$ es definida por
$E_A(n,p) = \frac{ S_A(n,p) }{ p }=\frac{T^*(n)}{pT_A(n,p)}$
El caso óptima es cuando $E_A(n,p)=1$, cuando el algoritmo
paralelo hace la misma cantidad de trabajo que el algoritmo
secuencial. El objetivo es de *maximizar la eficiencia*.
(Nota estas definiciones en la pisara, vamos a usarlas después.)
4 PROBLEMA: Calcular Max(A[1,...,N])
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-09 Tue 12:00-13:30>
1. Solucion Secuencial
* Algoritmo:
- $m \leftarrow 1$
- for $i\leftarrow 2$ to $n$
- if $A[i]>A[m]$ then $m\leftarrow i$
- return $A[m]$
* Se puede ver como un arbol de evaluación con una sola rama
de largo $n$ y $n$ hojas.
* Complejidad:
- tiempo $O(n)$, con $1$ procesador, entonces:
- $T^*(n)=n$.
2. Solucion Parallela con $n$ procesadores
* Algoritmo:
- $M[p] \leftarrow A[p]$
- for $l\leftarrow 0$ to $\lceil \lg p \rceil -1$
- if $p \mod 2^{l+1}=0$ y $ p+2^l
Si un algoritmo consigue un tiempo T(n,p)=C,
entonces consigue tiempo T(n,p/s)= sC \forall s>1
(bajo algunas condiciones)
6 DEFINICIÓN "Trabajo"
~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Usando el Lema de Brent, podemos exprimir el rendimiento de
los algoritmos paralelos con dos medidas:
- $T(n)$, el tiempo del algoritmo paralelo usando cualquier
cantidad de procesadores que quiere.
Nota la diferencia con
+ $T^*(n)$, el tiempo del mejor algoritmo secuencial, y
+ $T_A(n,n)$, el tiempo del algoritmo con $n$ procesadores.
- $W(n)$, la suma del total trabajo ejecutado por todo los
procesadores.
7 COROLARIO
~~~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
- Con el lema de Brent podemos obtener:
- $$T(n,p) = T(n) + \frac{ W(n) }{ p }$$
- $$E(n,p) = \frac{ T^*(n) }{ pT(n) + W(n) }$$
8 EJEMPLO
~~~~~~~~~~
SCHEDULED: <2010-11-11 Thu 12:00-13:30>
* Para el calculo del máximo:
- $T(n) = \lg n$
- $W(n) = n$
* Entonces
- se puede obtener
- $T_B(n,p) = \lg n + {n \over p}$
- $$E(n,p) = \frac{ n }{ p\lg n + n }$$
* (Nota que eso es solamente una cota superior, nuestro
algoritmo da un mejor tiempo.)
9 PROBLEMA: Prefijos en paralelo ("Parallel Prefix")
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
* DEFINICIÓN: Problema "Prefijo en Paralelo"
Dado $x_1,\ldots, x_n$ y un operador asociativo \times
calcular
- $y_1 = x_1$
- $y_2 = x_1\times x_2$
- $y_2 = x_1\times x_2 \times x_3$
- ...
- $y_n = x_1\times \ldots \times x_n$
* Solucion Secuencial
Hay una solucionó obvio en tiempo O(n).
* Solucion paralela 1
* Concepto:
- Hipótesis: sabemos solucionarlo con $n/2$ elementos
- Caso de base: $n=1$ es simple.
- Inducción:
1. recursivamente calculamos en paralelo:
- todos los prefijos de $\{x_1,\ldots,x_{n/2}\}$ con
$n/2$ procesadores.
- todos los prefijos de $\{x_{n/2},\ldots,x_n\}$ con
$n/2$ procesadores.
2. en paralelo agregamos $x_{n/2}$ a los prefijos de
$\{x_{n/2},\ldots,x_n\}$
* ParallelPrefix1(i,j)
- if $i_p=j_p$
- return x_{i_p}
- $m_p \leftarrow \lfloor \frac{i_p + j_p}{2} \rfloor$;
- if $p\leq m$ then
- algo( i_p, m_p )
- else
- algo(m+1, j_p)
- y_p \leftarrow y_m . y_p
* Otra forma del algoritmo (de p. 384 de "Introduction to
Algorithms, A Creative Approach", Udi Manber):
+ ParallelPrefix1(left,right)
- if (right-left) = 1
- x[right] <- x[left] . x[right]
- else
- middle <- (left+right-1)/2
- do in paralel
- ParallelPrefix1(left,middle) {assigned to {P_1 to P_{n/2}}}
- ParallelPrefix1(middle+1,right) {assigned to {P_{n/2+1} to P_n}}
- for i <- middle+1 to right do in paralel
- x[i] <- x[middle] . x[i]
* Notas:
- este solucion *no* es EREW (Exclusive Read&Write), porque
los procesadores pueden leer $y_m$ al mismo tiempo.
- este solucionó es CREW (Concurrent Read, Exclusive Write).
- Complejidad:
- $T_{A_1}(n,n) = 1+ T(n/2,n/2) = \lg n$
(El mejor tiempo en paralelo con cualquier cantidad de
procesadores.)
- $W_{A_1}(n) = n + 2 W_{A_1}(n/2) - n\lg n$
- $T_{A_1}(n,p) = T(n) + W_{A_1}(n)/p = \lg n + (n\lg n)/p$
- Calculamos $p^*$, la cantidad óptima de procesadores
para minimizar el tiempo:
- $T(n) = W_{A_1}(n) /p^*$
- $p^* = \frac{ W(n) }{ T(n) } = n$
- Calculamos la eficiencia
- $E_{A_1}(n,p^*)
= \frac{ T^*(n) }{ p^* T(n)+W(n) }
= \frac{ n }{ n\lg n }
= {1 \over \lg n}$
- es poco eficiente =(
- PodrÃ-amos tener un algoritmo con
- la eficiencia del algoritmo secuencial
- el tiempo del algoritmo paralelo?
* Solucion paralela 2: mismo tiempo, mejor eficiencia
- Idea:
El concepto es de dividir de manera diferente: par y impar
(en vez de largo o pequeño).
- Concepto:
1. Calcular en paralelo $x_{2i-1}.x_{2i}$ en $x_{2i}$
para $\forall i, 1\leq i \leq n/2$.
2. Recursivamente, calcular todos los prefijos de
$E=\{ x_2,x_4,\ldots, x_{2i},\ldots, x_n \}$
3. Calcular en paralelo los prefijos en posiciones impares,
multiplicando los prefijos de $E$ por una sola valor.
- algo2(i,j)
- for $d\leftarrow 1$ to $(\lg n)-1$
- if $p=0 \mod 2^{d+1}$
- if $p+2^d0$
- $x_{p-2^d} \leftarrow x_{p-2^d}.x_p$
- visualización
0.
1. [0,1]
2.
3. [2,3] [0,3]
4.
5. [4,5]
6.
7. [6,7] [4,7] [0,7]
8.
9. [8,9]
10.
11. [10,11] [8,11]
12.
13. [12,13]
14.
15. [14,15] [12,15] [8,15] [0,15]
- Notas:
- Este algoritmo es EREW
- Análisis
- $T_2(n) = 2\lg n$
- $W(n) = n + W(n.2) = n$
- $T_2(n,p) = T(n) + W(n)/p = 2\lg n + \frac{n}{p}$
- Calculamos la cantidad óptima de procesadores para obtener
el tiempo óptima:
- $T_2(n) = W(n) / p^*$ entonces
- $p^* = {W(n) \over T(n)} = {n\over\lg n}$
- $E_2(n,p^*) = { T^*(n) \over p^* T(n)+ W(n)} = n/n \in O(1)$
10 PROBLEMA: Ranking en listas
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SCHEDULED: <2010-11-16 Tue 12:00-13:30>
1. DEFINICIÓN
- dado una lista, calcula el rango para cada elemento.
- En el caso de una lista tradicional, no se puede hacer
mucho mejor que lineal.
- Consideramos una lista en un arreglo $A$,
- donde cada elemento $A[i]$ tiene un puntero al siguiente
elemento, $N[i]$, y
- calculamos su rango $R[i]$ en un arreglo $R$.
2. DoublingRank()
- $R[p] \leftarrow 0$
- if $N[p] = null$
- R[p] \leftarrow 1
- for $d\leftarrow 1$ to $\lceil\lg n\rceil$
- if $N[p]\neq NULL$
- if $R[N[p]]>0$
- $R[p] \leftarrow R[N[p]]+2^d$
- $N[p] \leftarrow N[N[p]]$
3. Análisis
- T(n) = \lg n
- W(n) = n + W(n/2) = O(n)
- T(n,p) = T(n) + W(n)/p = \lg n + n/p
- p^*
T(n) = W(n) / p^*
p n/\lg n
- E(n,p^*) = \frac{T^*(n)}{ p^* T(n) + W(n) }
= \frac{ n }{ n/\lg n \lg n +n}
= \Theta(1)
4. El algoritmo es EREW o CREW?
- es EREW si los procesadores están sincronizados, com en RAM
aquÃ-.
| Last Edit | 9 Nov 201009/11/10 at 11:332010-11-09 11:33:09 |
|---|---|
| Unique Views | 0 |
| Compartir |
