Parallel external memory explained

In computer science, a parallel external memory (PEM) model is a cache-aware, external-memory abstract machine.^[1] 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__

Model

Definition

The PEM model^[2] is a combination of the EM model and the PRAM model. The PEM model is a computation model which consists of

P processors and a two-level memory hierarchy. This memory hierarchy consists of a large external memory (main memory) of size N and 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 which is partitioned in blocks of size 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 .

I/O complexity

The complexity measure of the PEM model is the I/O complexity,^[3] 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 processors load parallelly a data block of size B form the main memory into their caches, it is considered as an I/O complexity of O( 1 ) not 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^[4] 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^[5] solve the CREW and EREW problem if

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 parallel block transfers. A second approach needs 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 processors combine their blocks into P/ 2 blocks. Then P/ 2 processors combine the P/ 2 blocks into P/ 4 . This procedure is continued until all the data is combined in one block.

Comparison to other models

!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

Examples

Multiway partitioning

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^[6] of is a set \Pi = \{A _{1,...,A} _{d\}} , where \cup ^{d} _{i =1} A _{i} = A and A _{i\cap} A _{j=\emptyset} for 1 \leq i<j\leq d . 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 ^{2} _{i} . In the following algorithm^[7] 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^[8]) uses a PEM prefix sum algorithm^[9] to calculate the prefix sum with the optimal O\left( (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} ^{i\}} ^{d} 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( (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( (N)/(PB) + \left\lceil (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 of size .The following code makes use of PRAMSORT which is a PRAM optimal sorting algorithm which runs in

O( log N) , and SELECT, which is a cache optimal single-processor selection algorithm. if N \leq P then tt{PRAMSORT}(A,P) return A[k] end if //Find median of each S _{i} for each processor in parallel do m _{i} = tt{SELECT}(S _{i,} (N)/(2 P) ) end for // Sort medians tt{PRAMSORT}(\lbrace m _{1,} ... , m _{2} \rbrace, P) // Partition around median of medians t = tt{PEMPARTITION}(A, m _{P/2} ,P) if k \leq t then return tt{PEMSELECT}(A[1:t], P, k) else return tt{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( (N)/(PB) + log (PB) ⋅ log ( (N)/(P) )\right)

Distribution sort

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

If

P = 1 the task is delegated to a cache-optimal single-processor sorting algorithm.

Otherwise the following algorithm is used: // Sample

\tfrac{ 4 N}{\sqrt{d}} elements from for each processor in parallel do if M < |S _{i|} 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} ... R ^{P} into a single contiguous vector l{R} Make \sqrt{d} copies of l{R} : l{R} _{1} ... l{R} _{\sqrt{d} } end do // Find \sqrt{d} pivots l{M}[j] for j = 1 to \sqrt{d} in parallel do l{M}[j] = tt{PEMSELECT}( l{R} _{i,} \tfrac{P}{\sqrt{d}}, \tfrac{j ⋅ 4 N}{d}) end for Pack pivots in contiguous array l{M} // Partition around pivots into buckets l{B} l{B} = tt{PEMMULTIPARTITION}(A[1:N], l{M},\sqrt{d},P) // Recursively sort buckets for j = 1 to \sqrt{d} + 1 in parallel do recursively call tt{PEMDISTSORT} on bucket of size l{B}[j] using O \left( \left \lceil \tfrac{ l{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 (N)/(PB) \right \rceil \left ( log _{d} P + log _{M/B} (N)/(PB) \right ) + f(N,P,d) ⋅ log _{d} P \right)

where

f(N,P,d) = O \left ( log (PB)/(\sqrt{d) } \log \frac + \left \lceil \frac \log P + \sqrt \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 < B ^{O(1)} the I/O complexity is then:O \left ( (N)/(PB) log _{M/B} (N)/(B) \right )

Other PEM algorithms

!PEM Algorithm!I/O complexity!Constraints

Mergesort	O\left( (N)/(PB) log _{(M)/(B)} (N)/(B) \right) = rm{sort} _{P(N)}	P \leq (N)/(B ^{2}) , M = B ^{O(1)}
List ranking^[10]	O \left ( rm{sort} _{P(N)} \right )	P \leq (N/B ^{2})/(log B ⋅ log ^{O(1)} N) , M = B ^{O(1)}
Euler tour	O \left ( rm{sort} _{P(N)} \right )	P \leq (N)/(B ^{2}) , M = B ^{O(1)}
Expression tree evaluation	O \left ( rm{sort} _{P(N)} \right )	P \leq (N)/(B ^{2} log B ⋅ log ^{O(1)} N) , M = B ^{O(1)}
Finding a MST	O \left( rm{sort} _{P(}	V	) + \textrm_P(	E	) \log \tfrac \right)	p \leq (|V| + |E|)/(B ^{2} log B ⋅ log ^{O(1)} N) , M = B ^{O(1)}

Where rm{sort} _{P(N)} is the time it takes to sort items with processors in the PEM model.

See also

• Parallel random-access machine (PRAM)
• Random-access machine (RAM)
• External memory (EM)

Notes and References

1. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
2. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
3. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
4. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
5. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
6. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
7. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
8. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
9. Book: Arge. Lars. Goodrich. Michael T.. Nelson. Michael. Sitchinava. Nodari. Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures . Fundamental parallel algorithms for private-cache chip multiprocessors . 2008. 197–206. New York, New York, USA. ACM Press. 10.1145/1378533.1378573. 9781595939739. 11067041 .
10. Book: Arge. Lars. Goodrich. Michael T.. Sitchinava. Nodari. 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) . Parallel external memory graph algorithms . 2010. 1–11. IEEE. 10.1109/ipdps.2010.5470440. 9781424464425. 587572 .