Parallel external memory

PEM Model

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.

The PEM model is a combination of the EM model and the PRAM model. The PEM model is a computation model which consists of P small internal memories (caches). The processors share the main memory. Each cache is exclusive to a single processor. A processor can't access another’s cache. The caches have a size B.

The complexity measure of the PEM model is the I/O complexity, which determines the number of parallel blocks transfers between the main memory and the cache. During a parallel block transfer each processor can transfer a block. So if O(1) not P parallel block transfers. A second approach needs P/2 blocks. Then P/4. This procedure is continued until all the data is combined in one block.

Model	Multi-core	Cache-aware
Random-access machine (RAM)	No	No
Parallel random-access machine (PRAM)	Yes	No
External memory (EM)	No	Yes
Parallel external memory (PEM)	Yes	Yes

Let Π={A1,...,Ad} , where 1≤i<j≤d. mi−1 and smaller than Si. The multiway partitioning algorithm (PEM_DIST_SORT) uses a PEM prefix sum algorithm to calculate the prefix sum with the optimal M into the cache. Partition {M1,...,MP} simultaneously. // Use the prefix sum vector to compute the final partition for each processor i in parallel do Write elements Mi. end for Using the prefix sums stored in d=O(MB) 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 \\log(P)+d\\log(B)\\right)"}}'>O(NPB+⌈dB⌉>log⁡(P)+dlog⁡(B)) I/O complexity. The content of the final buckets have to be located in contiguous memory.

The selection problem is about finding the k-th smallest item in an unordered list O(log⁡N), and SELECT, which is a cache optimal single-processor selection algorithm.

if A[k] end if //Find median of each mi=𝚂𝙴𝙻𝙴𝙲𝚃(Si,N2P) end for // Sort medians k≤t then return O(NPB+log⁡(PB)⋅log⁡(NP))

Distribution sort partitions an input list d disjoint buckets of similar size. Every bucket is then sorted recursively and the results are combined into a fully sorted list.

If A for each processor d=M/B Load d=|Si| Load and sort ℛ Make ℛ1…ℛd end do // Find j=1 to ℳ // Partition ℬ=𝙿𝙴𝙼𝙼𝚄𝙻𝚃𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽(A[1:N],ℳ,d,P) // Recursively sort buckets for 𝙿𝙴𝙼𝙳𝙸𝚂𝚃𝚂𝙾𝚁𝚃 on bucket O(⌈ℬ[j]N/P⌉) processors responsible for elements in bucket f(N,P,d)=O(log⁡PBdlog⁡NP+⌈dBlog⁡P+dlog⁡B⌉)

If the number of processors is chosen that O(NPBlogM/BNB)

PEM Algorithm	I/O complexity	Constraints
Mergesort	O(sortP(N))	P≤NB2,M=BO(1)
Expression tree evaluation	O(sortP(|V|)+sortP(|E|)log⁡|V|pB)	N items with Arge, Lars; Goodrich, Michael T.; Sitchinava, Nodari (2010). "Parallel external memory graph algorithms". 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS). IEEE. pp. 1–11. doi:10.1109/ipdps.2010.5470440. ISBN 9781424464425. S2CID 587572. Parallel computing
General	Distributed computing Parallel computing Parallel algorithm Massively parallel Cloud computing High-performance computing Multiprocessing Manycore processor GPGPU Computer network Systolic array
Levels	Bit Instruction Thread Task Data Memory Loop Pipeline
Multithreading	Temporal Simultaneous (SMT) Simultaneous and heterogenous Speculative (SpMT) Preemptive Cooperative Clustered multi-thread (CMT) Hardware scout
Theory	PRAM model PEM model Analysis of parallel algorithms Amdahl's law Gustafson's law Cost efficiency Karp–Flatt metric Slowdown Speedup
Elements	Process Thread Fiber Instruction window Array
Coordination	Multiprocessing Memory coherence Cache coherence Cache invalidation Barrier Synchronization Application checkpointing
Programming	Stream processing Dataflow programming Models Implicit parallelism Explicit parallelism Concurrency Non-blocking algorithm
Hardware	Flynn's taxonomy SISD SIMD Array processing (SIMT) Pipelined processing Associative processing MISD MIMD Dataflow architecture Pipelined processor Superscalar processor Vector processor Multiprocessor symmetric asymmetric Memory shared distributed distributed shared UMA NUMA COMA Massively parallel computer Computer cluster Beowulf cluster Grid computer Hardware acceleration
APIs	Ateji PX Boost Chapel HPX Charm++ Cilk Coarray Fortran CUDA Dryad C++ AMP Global Arrays GPUOpen MPI OpenMP OpenCL OpenHMPP OpenACC Parallel Extensions PVM pthreads RaftLib ROCm UPC TBB ZPL
Problems	Automatic parallelization Cache stampede Deadlock Deterministic algorithm Embarrassingly parallel Parallel slowdown Race condition Software lockout Scalability Starvation
View original on Wikipedia | Back | FazBrowse Home