并行外部存储器

在计算机科学中，并行外部存储器（PEM）模型是一种具有高速缓存意识的外部存储器抽象机器。它是单处理器外部存储器（EM）模型的并行计算类比。类似地，它是并行随机存取机器（PRAM）的缓存感知类比。PEM模型由若干个处理器，以及它们各自的私有缓存和一个共享的主存储器组成。

PEM模型是EM模型和PRAM模型的结合。PEM模型是一个计算模型，由以下部分组成P{fnTahomafs10bord0shad01cH00FFFF}{displaystyleP}处理器和一个两级的存储器层次结构。这个存储器层次包括一个大的外部存储器（主存储器），大小为小型内部存储器（缓存）。这些处理器共享主存储器。每个高速缓存对单个处理器是独占的。一个处理器不能访问另一个处理器的高速缓存。缓存有一个大小处理器只能对其高速缓存中的数据进行操作。数据可以在主存储器和高速缓存之间以大小为B的块进行传输。

PEM模型的复杂度是I/O复杂度，它决定了主存储器和高速缓存之间平行块传输的数量。在一次平行块传输过程中，每个处理器可以传输一个块。因此，如果{displaystyleP}处理器平行加载一个大小为B的数据块{displaystyleB}的数据块平行加载到它们的缓存中。的数据块到它们的缓存中，这被认为是一个I/O复杂度为.PEM模型中的程序应该尽量减少主内存和缓存之间的数据传输，并尽可能地在缓存中的数据上操作。读/写冲突在PEM模型中，P处理器之间没有直接的通信网络。处理器必须通过主存储器间接地进行通信。如果多个处理器试图同时访问主存储器中的同一个块，就会发生读/写冲突。和PRAM模型一样，这个问题有三种不同的变化被考虑。并发读并发写（CRCW）。多个处理器可以同时读取和写入主存储器中的同一个块。

并发读独占写（CREW）。主内存中的同一个块可以被多个处理器同时读取。每次只有一个处理器可以对一个块进行写入。独占读独占写（EREW）。主存储器中的同一个块不能被多个处理器同时读或写。以下两种算法可以解决CREW和EREW问题，如果xxx种方法是将写操作序列化。只有一个处理器在另一个处理器之后向块写入。这就导致了总共有并行块传输和每个处理器的额外块。主要的想法是以二进制树的方式安排写操作，并逐渐将数据合并成一个块。在xxx轮中.这个过程一直持续到所有的数据被合并到一个区块中。