{
  "id": "enwiki-001180384636",
  "slug": "parallel-external-memory",
  "title": "Parallel external memory",
  "qid": "",
  "lead": "In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine. It is the parallel-computing analogy to the single-processor external memory (EM) model. In a similar way, it is the cache-aware analogy to the parallel random-access machine (PRAM). The PEM model consists of a number of processors, together with their respective private caches and a shared main memory. __TOC__",
  "body": "In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine. It is the parallel-computing analogy to the single-processor external memory (EM) model. In a similar way, it is the cache-aware analogy to the parallel random-access machine (PRAM). The PEM model consists of a number of processors, together with their respective private caches and a shared main memory. __TOC__ Let M=\\{m_1,...,m_{d-1}\\} be a vector of d-1 pivots sorted in increasing order. Let be an unordered set of N elements. A d-way partition of is a set \\Pi=\\{A_1,...,A_d\\} , where \\cup_{i=1}^d A_i = A and A_i\\cap A_j=\\emptyset for 1\\leq i . A_i is called the i-th bucket. The number of elements in A_i is greater than m_{i-1} and smaller than m_{i}^2 . In the following algorithm the input is partitioned into N/P-sized contiguous segments S_1,...,S_P in main memory. The processor i primarily works on the segment S_i . The multiway partitioning algorithm ( PEM_DIST_SORT ) uses a PEM prefix sum algorithm to calculate the prefix sum with the optimal O\\left(\\frac{N}{PB} + \\log P\\right) I/O complexity. This algorithm simulates an optimal PRAM prefix sum algorithm. // Compute parallelly a d-way partition on the data segments S_i for each processor i in parallel do Read the vector of pivots into the cache. Partition S_i into d buckets and let vector M_i=\\{j_1^i,...,j_d^i\\} be the number of items in each bucket. end for Run PEM prefix sum on the set of vectors \\{M_1,...,M_P\\} simultaneously. // Use the prefix sum vector to compute the final partition for each processor i in parallel do Write elements S_i into memory locations offset appropriately by M_{i-1} and M_{i} . end for Using the prefix sums stored in M_P the last processor P calculates the vector of bucket sizes and returns it. If the vector of d=O\\left(\\frac{M}{B}\\right) pivots M and the input set A are located in contiguous memory, then the d-way partitioning problem can be solved in the PEM model with O\\left(\\frac{N}{PB} + \\left\\lceil \\frac{d}{B} \\right\\rceil>\\log(P)+d\\log(B)\\right) I/O complexity. The content of the final buckets have to be located in contiguous memory. m_i = \\texttt{SELECT}(S_i, \\frac{N}{2P}) end for // Sort medians \\texttt{PRAMSORT}(\\lbrace m_1, \\dots, m_2 \\rbrace, P) // Partition around median of medians t = \\texttt{PEMPARTITION}(A, m_{P/2},P) if k \\leq t then return \\texttt{PEMSELECT}(A[1:t], P, k) else return \\texttt{PEMSELECT}(A[t+1:N], P, k-t) end if Under the assumption that the input is stored in contiguous memory, PEMSELECT has an I/O complexity of: O\\left(\\frac{N}{PB} + \\log (PB) \\cdot \\log(\\frac{N}{P})\\right) If P = 1 the task is delegated to a cache-optimal single-processor sorting algorithm. Otherwise the following algorithm is used: // Sample \\tfrac{4N}{\\sqrt{d}} elements from for each processor in parallel do if M then d = M/B Load S_i in -sized pages and sort pages individually else d = |S_i| Load and sort S_i as single page end if Pick every \\sqrt{d}/4 'th element from each sorted memory page into contiguous vector R^i of samples end for in parallel do Combine vectors R^1 \\dots R^P into a single contiguous vector \\mathcal{R} Make \\sqrt{d} copies of \\mathcal{R} : \\mathcal{R}_1 \\dots \\mathcal{R}_{\\sqrt{d}} end do // Find \\sqrt{d} pivots \\mathcal{M}[j] for j = 1 to \\sqrt{d} in parallel do \\mathcal{M}[j] = \\texttt{PEMSELECT}(\\mathcal{R}_i, \\tfrac{P}{\\sqrt{d}}, \\tfrac{j \\cdot 4N}{d}) end for Pack pivots in contiguous array \\mathcal{M} // Partition around pivots into buckets \\mathcal{B} \\mathcal{B} = \\texttt{PEMMULTIPARTITION}(A[1:N],\\mathcal{M},\\sqrt{d},P) // Recursively sort buckets for j = 1 to \\sqrt{d} + 1 in parallel do recursively call \\texttt{PEMDISTSORT} on bucket of size \\mathcal{B}[j] using O \\left( \\left \\lceil \\tfrac{\\mathcal{B}[j]}{N / P} \\right \\rceil \\right) processors responsible for elements in bucket end for The I/O complexity of PEMDISTSORT is: 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) where 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 ) If the number of processors is chosen that f(N,P,d) = O\\left ( \\left \\lceil \\tfrac{N}{PB} \\right \\rceil \\right ) and M the I/O complexity is then: O \\left ( \\frac{N}{PB} \\log_{M/B} \\frac{N}{B} \\right ) | p \\leq \\frac {B^2 \\log B \\cdot \\log^{O(1)} N}, M = B^{O(1)} |} Where \\textrm{sort}_P(N) is the time it takes to sort items with processors in the PEM model. ==References==",
  "categories": [
    "109399431",
    "20476448",
    "24866447",
    "29265121",
    "67977044"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1180384636",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1697438950.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001180384636",
    "type": "webpage",
    "title": "Parallel external memory",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/parallel-external-memory",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001180384636",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1180384636",
    "note": "Immutable snapshot enwiki-001180384636"
  }
}