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.
Model
Definition
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
{\displaystyle P}
processors and a two-level memory hierarchy. This memory hierarchy consists of a large external memory (main memory) of size
N
{\displaystyle N}
and
P
{\displaystyle 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
M
{\displaystyle M}
which is partitioned in blocks of size
B
{\displaystyle B}
. The processors can only perform operations on data which are in their cache. The data can be transferred between the main memory and the cache in blocks of size
B
{\displaystyle B}
.
I/O complexity
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
P
{\displaystyle P}
processors load parallelly a data block of size
B
{\displaystyle B}
form the main memory into their caches, it is considered as an I/O complexity of
O
(
1
)
{\displaystyle O(1)}
not
O
(
P
)
{\displaystyle O(P)}
. A program in the PEM model should minimize the data transfer between main memory and caches and operate as much as possible on the data in the caches.
Read/write conflicts
In the PEM model, there is no direct communication network between the P processors. The processors have to communicate indirectly over the main memory. If multiple processors try to access the same block in main memory concurrently read/write conflicts occur. Like in the PRAM model, three different variations of this problem are considered:
Concurrent Read Concurrent Write (CRCW): The same block in main memory can be read and written by multiple processors concurrently.
Concurrent Read Exclusive Write (CREW): The same block in main memory can be read by multiple processors concurrently. Only one processor can write to a block at a time.
Exclusive Read Exclusive Write (EREW): The same block in main memory cannot be read or written by multiple processors concurrently. Only one processor can access a block at a time.
The following two algorithms solve the CREW and EREW problem if
P
≤
B
{\displaystyle P\leq B}
processors write to the same block simultaneously.
A first approach is to serialize the write operations. Only one processor after the other writes to the block. This results in a total of
P
{\displaystyle P}
parallel block transfers. A second approach needs
O
(
log
(
P
)
)
{\displaystyle O(\log(P))}
parallel block transfers and an additional block for each processor. The main idea is to schedule the write operations in a binary tree fashion and gradually combine the data into a single block. In the first round
P
{\displaystyle P}
processors combine their blocks into
P
/
2
{\displaystyle P/2}
blocks. Then
P
/
2
{\displaystyle P/2}
processors combine the
P
/
2
{\displaystyle P/2}
blocks into
P
/
4
{\displaystyle P/4}
. This procedure is continued until all the data is combined in one block.
Comparison to other models
Examples
{\displaystyle A_{i}\cap A_{j}=\emptyset }
for
1
≤
i
<
j
≤
d
{\displaystyle 1\leq i<j\leq d}
.
A
i
{\displaystyle A_{i}}
is called the i-th bucket. The number of elements in
A
i
{\displaystyle A_{i}}
is greater than
m
i
−
1
{\displaystyle m_{i-1}}
and smaller than
m
i
2
{\displaystyle m_{i}^{2}}
. In the following algorithm the input is partitioned into N/P-sized contiguous segments
S
1
,
.
.
.
,
S
P
{\displaystyle S_{1},...,S_{P}}
in main memory. The processor i primarily works on the segment
S
i
{\displaystyle S_{i}}
. The multiway partitioning algorithm (PEM_DIST_SORT) uses a PEM prefix sum algorithm to calculate the prefix sum with the optimal
O
(
N
P
B
+
log
P
)
{\displaystyle 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
{\displaystyle S_{i}}
for each processor i in parallel do
Read the vector of pivots M into the cache.
Partition
S
i
{\displaystyle S_{i}}
into d buckets and let vector
M
i
=
{
j
1
i
,
.
.
.
,
j
d
i
}
{\displaystyle 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
}
{\displaystyle \{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
{\displaystyle S_{i}}
into memory locations offset appropriately by
M
i
−
1
{\displaystyle M_{i-1}}
and
M
i
{\displaystyle M_{i}}
.
end for
Using the prefix sums stored in
M
P
{\displaystyle M_{P}}
the last processor P calculates the vector B of bucket sizes and returns it.
If the vector of
d
=
O
(
M
B
)
{\displaystyle 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
(
N
P
B
+
⌈
d
B
⌉
>
log
(
P
)
+
d
log
(
B
)
)
{\displaystyle 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.
Selection
The selection problem is about finding the k-th smallest item in an unordered list A of size N.
The following code makes use of PRAMSORT which is a PRAM optimal sorting algorithm which runs in
O
(
log
N
)
{\displaystyle O(\log N)}
, and SELECT, which is a cache optimal single-processor selection algorithm.
if
N
≤
P
{\displaystyle N\leq P}
then
PRAMSORT
(
A
,
P
)
{\displaystyle {\texttt {PRAMSORT}}(A,P)}
return
A
[
k
]
{\displaystyle A[k]}
end if
//Find median of each
S
i
{\displaystyle S_{i}}
for each processor i in parallel do
m
i
=
SELECT
(
S
i
,
N
2
P
)
{\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}
end for
// Sort medians
PRAMSORT
(
{
m
1
,
…
,
m
2
}
,
P
)
{\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}
// Partition around median of medians
t
=
PEMPARTITION
(
A
,
m
P
/
2
,
P
)
{\displaystyle t={\texttt {PEMPARTITION}}(A,m_{P/2},P)}
if
k
≤
t
{\displaystyle k\leq t}
then
return
PEMSELECT
(
A
[
1
:
t
]
,
P
,
k
)
{\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}
else
return
PEMSELECT
(
A
[
t
+
1
:
N
]
,
P
,
k
−
t
)
{\displaystyle {\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:
log
(
N
P
)
)
{\displaystyle O\left({\frac {N}{PB}}+\log(PB)\cdot \log({\frac {N}{P}})\right)}
Distribution sort
Distribution sort partitions an input list A of size N into d disjoint buckets of similar size. Every bucket is then sorted recursively and the results are combined into a fully sorted list.
If
P
=
1
{\displaystyle P=1}
the task is delegated to a cache-optimal single-processor sorting algorithm.
Otherwise the following algorithm is used:
// Sample
4
N
d
{\displaystyle {\tfrac {4N}{\sqrt {d}}}}
elements from A
for each processor i in parallel do
if
M
<
|
S
i
|
{\displaystyle M<|S_{i}|}
then
d
=
M
/
B
{\displaystyle d=M/B}
Load
S
i
{\displaystyle S_{i}}
in M-sized pages and sort pages individually
else
d
=
|
S
i
|
{\displaystyle d=|S_{i}|}
Load and sort
S
i
{\displaystyle S_{i}}
as single page
end if
Pick every
d
/
4
{\displaystyle {\sqrt {d}}/4}
'th element from each sorted memory page into contiguous vector
R
i
{\displaystyle R^{i}}
of samples
end for
in parallel do
Combine vectors
R
1
…
R
P
{\displaystyle R^{1}\dots R^{P}}
into a single contiguous vector
R
{\displaystyle {\mathcal {R}}}
Make
d
{\displaystyle {\sqrt {d}}}
copies of
R
{\displaystyle {\mathcal {R}}}
:
R
1
…
R
d
{\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}
end do
// Find
d
{\displaystyle {\sqrt {d}}}
pivots
M
[
j
]
{\displaystyle {\mathcal {M}}[j]}
4
N
d
)
{\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}}_{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}
end for
Pack pivots in contiguous array
M
{\displaystyle {\mathcal {M}}}
// Partition Aaround pivots into buckets
B
{\displaystyle {\mathcal {B}}}
B
=
PEMMULTIPARTITION
(
A
[
1
:
N
]
,
M
,
d
,
P
)
{\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}
// Recursively sort buckets
for
j
=
1
{\displaystyle j=1}
to
d
+
1
{\displaystyle {\sqrt {d}}+1}
in parallel do
recursively call
PEMDISTSORT
{\displaystyle {\texttt {PEMDISTSORT}}}
on bucket jof size
B
[
j
]
{\displaystyle {\mathcal {B}}[j]}
using
O
(
⌈
B
[
j
]
N
/
P
⌉
)
{\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}
processors responsible for elements in bucket j
end for
The I/O complexity of PEMDISTSORT is:
log
d
P
)
{\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)}
where
f
(
N
,
P
,
d
)
=
O
(
log
P
B
d
log
N
P
+
⌈
d
B
log
P
+
d
log
B
⌉
)
{\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)}
If the number of processors is chosen that
f
(
N
,
P
,
d
)
=
O
(
⌈
N
P
B
⌉
)
{\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}
and
M
<
B
O
(
1
)
{\displaystyle M<B^{O(1)}}
the I/O complexity is then:
O
(
N
P
B
log
M
/
B
N
B
)
{\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}
Other PEM algorithms
Where
sort
P
(
N
)
{\displaystyle {\textrm {sort}}_{P}(N)}
is the time it takes to sort N items with P processors in the PEM model.
See also
Parallel random-access machine (PRAM)
Random-access machine (RAM)
External memory (EM)
References
