Memoria externa paralela

El modelo PEM ^{[ 1 ]} es una combinación del modelo EM y el modelo PRAM. El modelo PEM es un modelo de cálculo que consta de${\displaystyle P}$procesadores y una jerarquía de memoria de dos niveles . Esta jerarquía de memoria consta de una gran memoria externa (memoria principal) de tamaño${\displaystyle N}$y${\displaystyle P}$pequeñas memorias internas (cachés) . Los procesadores comparten la memoria principal. Cada caché es exclusiva de un solo procesador. Un procesador no puede acceder a la caché de otro. Las cachés tienen un tamaño${\displaystyle M}$que se divide en bloques de tamaño${\displaystyle B}$Los procesadores solo pueden realizar operaciones en los datos que se encuentran en su caché. Los datos se pueden transferir entre la memoria principal y la caché en bloques de tamaño${\displaystyle B}$.

La medida de complejidad del modelo PEM es la complejidad de E/S, ^{[ 1 ]} que determina el número de transferencias de bloques paralelos entre la memoria principal y la caché. Durante una transferencia de bloque paralela, cada procesador puede transferir un bloque. Por lo tanto, si${\displaystyle P}$Los procesadores cargan en paralelo un bloque de datos de tamaño${\displaystyle B}$desde la memoria principal a sus cachés, se considera como una complejidad de E/S de${\displaystyle O(1)}$no${\displaystyle O(P)}$Un programa en el modelo PEM debe minimizar la transferencia de datos entre la memoria principal y las cachés, y operar en la medida de lo posible con los datos almacenados en las cachés.

En el modelo PEM, no existe una red de comunicación directa entre los procesadores P. Los procesadores deben comunicarse indirectamente a través de la memoria principal. Si varios procesadores intentan acceder al mismo bloque en la memoria principal simultáneamente, se producen conflictos de lectura/escritura ^{[ 1 ]} . Al igual que en el modelo PRAM, se consideran tres variaciones diferentes de este problema:

• Lectura y escritura concurrentes (CRCW): El mismo bloque en la memoria principal puede ser leído y escrito por varios procesadores simultáneamente.
• Lectura y escritura exclusivas concurrentes (CREW): Varios procesadores pueden leer simultáneamente el mismo bloque de memoria principal. Solo un procesador puede escribir en un bloque a la vez.
• Lectura y escritura exclusivas (EREW): El mismo bloque en la memoria principal no puede ser leído ni escrito por varios procesadores simultáneamente. Solo un procesador puede acceder a un bloque a la vez.

Los siguientes dos algoritmos ^{[ 1 ]} resuelven el problema CREW y EREW si${\displaystyle P\leq B}$Los procesadores escriben en el mismo bloque simultáneamente. Un primer enfoque es serializar las operaciones de escritura. Solo un procesador después del otro escribe en el bloque. Esto da como resultado un total de${\displaystyle P}$transferencias de bloques en paralelo. Se necesita un segundo enfoque${\displaystyle O(\log(P))}$transferencias de bloques en paralelo y un bloque adicional para cada procesador. La idea principal es programar las operaciones de escritura en forma de árbol binario y combinar gradualmente los datos en un solo bloque. En la primera ronda${\displaystyle P}$Los procesadores combinan sus bloques en${\displaystyle P/2}$bloques. Entonces${\displaystyle P/2}$Los procesadores combinan los${\displaystyle P/2}$bloques en${\displaystyle P/4}$Este procedimiento se continúa hasta que todos los datos se combinen en un solo bloque.

Dejar${\displaystyle M=\{m_{1},...,m_{d-1}\}}$Sea A un vector de d-1 pivotes ordenados en orden creciente. Sea A un conjunto no ordenado de N elementos. Una partición de d vías ^{[ 1 ]} de A es un conjunto${\displaystyle \Pi =\{A_{1},...,A_{d}\}}$, dónde${\displaystyle \cup _{i=1}^{d}A_{i}=A}$y${\displaystyle A_{i}\cap A_{j}=\emptyset }$para${\displaystyle 1\leq i<j\leq d}$.${\displaystyle A_{i}}$se llama el i-ésimo cubo. El número de elementos en${\displaystyle A_{i}}$es mayor que${\displaystyle m_{i-1}}$y más pequeño que${\displaystyle m_{i}^{2}}$. En el siguiente algoritmo ^{[ 1 ]} la entrada se divide en segmentos contiguos de tamaño N/P${\displaystyle S_{1},...,S_{P}}$en la memoria principal. El procesador i trabaja principalmente en el segmento${\displaystyle S_{i}}$El algoritmo de partición multiway ( PEM_DIST_SORT^{[ 1 ]} ) utiliza un algoritmo de suma de prefijos PEM ^{[ 1 ]} para calcular la suma de prefijos con el óptimo${\displaystyle O\left({\frac {N}{PB}}+\log P\right)}$Complejidad de E/S. Este algoritmo simula un algoritmo óptimo de suma de prefijos PRAM.

// Calcula en paralelo una partición de d vías en los segmentos de datos.${\displaystyle S_{i}}$Para cada procesador i en paralelo, lea el vector de pivotes M en la caché. Dividir${\displaystyle S_{i}}$en d cubos y deje que vector${\displaystyle M_{i}=\{j_{1}^{i},...,j_{d}^{i}\}}$sea ​​el número de artículos en cada cubo. fin para Ejecutar la suma de prefijos PEM en el conjunto de vectores${\displaystyle \{M_{1},...,M_{P}\}}$simultáneamente. // Utilizar el vector de suma de prefijos para calcular la partición final. para cada procesador i en paralelo hacer Escribir elementos${\displaystyle S_{i}}$en ubicaciones de memoria desplazadas adecuadamente por${\displaystyle M_{i-1}}$y${\displaystyle M_{i}}$. fin para Utilizando las sumas de prefijo almacenadas en${\displaystyle M_{P}}$El último procesador, P, calcula el vector B de tamaños de cubetas y lo devuelve.

Si el vector de${\displaystyle d=O\left({\frac {M}{B}}\right)}$Los pivotes M y el conjunto de entrada A se encuentran en memoria contigua, entonces el problema de partición de d vías se puede resolver en el modelo PEM con${\displaystyle O\left({\frac {N}{PB}}+\left\lceil {\frac {d}{B}}\right\rceil >\log(P)+d\log(B)\right)}$Complejidad de E/S. El contenido de los cubos finales debe ubicarse en memoria contigua.

El problema de selección consiste en encontrar el k-ésimo elemento más pequeño en una lista no ordenada A de tamaño N. El siguiente código ^{[ 1 ]} utiliza PRAMSORTun algoritmo de ordenación óptima PRAM que se ejecuta en${\displaystyle O(\log N)}$y SELECT, que es un algoritmo de selección de procesador único óptimo para la caché.

si${\displaystyle N\leq P}$entonces${\displaystyle {\texttt {PRAMSORT}}(A,P)}$devolver${\displaystyle A[k]}$fin si //Calcular la mediana de cada${\displaystyle S_{i}}$para cada procesador i en paralelo hacer${\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}$fin para // Ordenar medianas ${\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}$ // Partición en torno a la mediana de las medianas ${\displaystyle t={\texttt {PEMPARTICIÓN}}(A,m_{P/2},P)}$si${\displaystyle k\leq t}$luego regresar${\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}$de lo contrario, regresa${\displaystyle {\texttt {PEMSELECT}}(A[t+1:N],P,kt)}$fin si

Bajo el supuesto de que la entrada se almacena en memoria contigua, PEMSELECTtiene una complejidad de E/S de:

${\displaystyle O\left({\frac {N}{PB}}+\log(PB)\cdot \log({\frac {N}{P}})\right)}$

El algoritmo de ordenación por distribución divide una lista de entrada A de tamaño N en d grupos disjuntos de tamaño similar. Cada grupo se ordena recursivamente y los resultados se combinan en una lista completamente ordenada.

Si${\displaystyle P=1}$La tarea se delega a un algoritmo de ordenación de un solo procesador que optimiza el uso de la caché.

En caso contrario, se utiliza el siguiente algoritmo ^{[ 1 ] :}

// Muestra${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$elementos de A para cada procesador i en paralelo hacer si${\displaystyle M<|S_{i}|}$entonces${\displaystyle d=M/B}$ Carga${\displaystyle S_{i}}$en páginas de tamaño M y ordenar las páginas individualmente en caso contrario${\displaystyle d=|S_{i}|}$ Cargar y ordenar${\displaystyle S_{i}}$como final de una sola página si elige cada${\displaystyle {\sqrt {d}}/4}$El elemento 'enésimo de cada página de memoria ordenada en un vector contiguo${\displaystyle R^{i}}$de muestras finalizan paraen paralelo hacer Combinar vectores${\displaystyle R^{1}\dots R^{P}}$en un único vector contiguo${\displaystyle {\mathcal {R}}}$ Hacer${\displaystyle {\sqrt {d}}}$copias de${\displaystyle {\mathcal {R}}}$:${\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}$fin hacer // Encontrar${\displaystyle {\sqrt {d}}}$pivotes${\displaystyle {\mathcal {M}}[j]}$para${\displaystyle j=1}$a${\displaystyle {\sqrt {d}}}$en paralelo hacer${\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}}_{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}$fin para Empaqueta los pivotes en una matriz contigua${\displaystyle {\mathcal {M}}}$ // La partición A se divide en cubos alrededor de los pivotes.${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$ // Ordenar recursivamente los cubos para${\displaystyle j=1}$a${\displaystyle {\sqrt {d}}+1}$en paralelo, realizar llamadas recursivas${\displaystyle {\texttt {PEMDISTSORT}}}$en el cubo j de tamaño${\displaystyle {\mathcal {B}}[j]}$ usando${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$procesadores responsables de los elementos en el cubo j fin para

La complejidad de E/S PEMDISTSORTes:

${\displaystyle O\left(\left\lceil {\frac {N}{PB}}\right\rceil \left(\log _{d}P+\log _{M/B}{\frac {N}{PB}}\right)+f(N,P,d)\cdot \log _{d}P\right)}$

dónde

${\displaystyle f(N,P,d)=O\left(\log {\frac {PB}{\sqrt {d}}}\log {\frac {N}{P}}+\left\lceil {\frac {\sqrt {d}}{B}}\log P+{\sqrt {d}}\log B\right\rceil \right)}$

Si se elige el número de procesadores que${\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}$y${\displaystyle M<B^{O(1)}}$La complejidad de E/S es entonces:

${\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}$

Dónde${\displaystyle {\textrm {sort}}_{P}(N)}$es el tiempo que se tarda en clasificar N elementos con P procesadores en el modelo PEM.