ในวิทยาการคอมพิวเตอร์โมเดลหน่วยความจำภายนอกแบบขนาน (PEM)เป็นเครื่องจักรนามธรรมหน่วยความจำภายนอกที่รับรู้แคช^{[ 1 ]}เป็นการเปรียบเทียบการประมวลผลแบบขนานกับ โมเดล หน่วยความจำภายนอกแบบ โปรเซสเซอร์เดี่ยว (EM) ในทำนองเดียวกัน เป็นการเปรียบเทียบที่รับรู้แคชกับเครื่องจักรเข้าถึงแบบสุ่มแบบขนาน (PRAM) โมเดล PEM ประกอบด้วยโปรเซสเซอร์จำนวนหนึ่ง พร้อมด้วยแคชส่วนตัวของแต่ละตัว และหน่วยความจำหลักที่ใช้ร่วมกัน

แบบจำลอง PEM ^{[ 1 ]}เป็นการผสมผสานระหว่างแบบจำลอง EM และแบบจำลอง PRAM แบบจำลอง PEM เป็นแบบจำลองการคำนวณที่ประกอบด้วย โปรเซสเซอร์และ ลำดับชั้นหน่วยความจำสองระดับลำดับชั้นหน่วยความจำนี้ประกอบด้วยหน่วยความจำภายนอก ขนาดใหญ่ (หน่วยความจำหลัก) ที่มีขนาดและ หน่วยความจำภายใน ขนาดเล็ก(แคช)โปรเซสเซอร์ใช้หน่วยความจำหลักร่วมกัน แคชแต่ละอันเป็นของโปรเซสเซอร์ตัวเดียวเท่านั้น โปรเซสเซอร์ไม่สามารถเข้าถึงแคชของโปรเซสเซอร์อื่นได้ แคชมีขนาดซึ่งถูกแบ่งออกเป็นบล็อกที่มีขนาดโปรเซสเซอร์สามารถดำเนินการกับข้อมูลที่อยู่ในแคชของตนเท่านั้น ข้อมูลสามารถถ่ายโอนระหว่างหน่วยความจำหลักและแคชได้ในบล็อกที่มีขนาด ${\displaystyle P}$${\displaystyle N}$${\displaystyle P}$${\displaystyle M}$${\displaystyle B}$${\displaystyle B}$

การวัดความซับซ้อนของโมเดล PEM คือความซับซ้อนของ I/O ^{[ 1 ]}ซึ่งกำหนดจำนวนการถ่ายโอนบล็อกแบบขนานระหว่างหน่วยความจำหลักและแคช ในระหว่างการถ่ายโอนบล็อกแบบขนาน โปรเซสเซอร์แต่ละตัวสามารถถ่ายโอนบล็อกได้ ดังนั้น หากโปรเซสเซอร์โหลดบล็อกข้อมูลขนาดจากหน่วยความจำหลักไปยังแคชแบบขนานจะถือว่ามีความซับซ้อนของ I/O เท่ากับโปรแกรมในโมเดล PEM ควรลดการถ่ายโอนข้อมูลระหว่างหน่วยความจำหลักและแคชให้น้อยที่สุด และดำเนินการกับข้อมูลในแคชให้มากที่สุดเท่าที่จะเป็นไปได้ ${\displaystyle P}$${\displaystyle B}$${\displaystyle O(1)}$${\displaystyle O(P)}$

ในโมเดล PEM ไม่มีเครือข่ายการสื่อสารโดยตรงระหว่างโปรเซสเซอร์ P โปรเซสเซอร์ต้องสื่อสารกันทางอ้อมผ่านหน่วยความจำหลัก หากโปรเซสเซอร์หลายตัวพยายามเข้าถึงบล็อกเดียวกันในหน่วยความจำหลักพร้อมกัน จะเกิดความขัดแย้งในการอ่าน/เขียน^{[ 1 ]}เช่นเดียวกับในโมเดล PRAM มีการพิจารณาปัญหาที่แตกต่างกันสามแบบดังนี้:

• การอ่านและการเขียนพร้อมกัน (CRCW): บล็อกเดียวกันในหน่วยความจำหลักสามารถอ่านและเขียนได้โดยโปรเซสเซอร์หลายตัวพร้อมกัน
• การอ่านพร้อมกันและการเขียนแบบพิเศษ (CREW): โปรเซสเซอร์หลายตัวสามารถอ่านบล็อกเดียวกันในหน่วยความจำหลักได้พร้อมกัน มีเพียงโปรเซสเซอร์เดียวเท่านั้นที่สามารถเขียนลงในบล็อกได้ในแต่ละครั้ง
• การอ่านและการเขียนแบบผูกขาด (EREW): บล็อกเดียวกันในหน่วยความจำหลักไม่สามารถถูกอ่านหรือเขียนโดยโปรเซสเซอร์หลายตัวพร้อมกันได้ มีเพียงโปรเซสเซอร์เดียวเท่านั้นที่สามารถเข้าถึงบล็อกได้ในแต่ละครั้ง

อัลกอริทึมสองแบบต่อไปนี้^{[ 1 ]}แก้ปัญหา CREW และ EREW ได้หากโปรเซสเซอร์เขียนไปยังบล็อกเดียวกันพร้อมกัน วิธีแรกคือการเรียงลำดับการดำเนินการเขียน โปรเซสเซอร์จะเขียนไปยังบล็อกทีละตัวเท่านั้น ซึ่งส่งผลให้มีการถ่ายโอนบล็อกแบบขนานทั้งหมด วิธีที่สองต้องการการถ่ายโอนบล็อกแบบขนานและบล็อกเพิ่มเติมสำหรับแต่ละโปรเซสเซอร์ แนวคิดหลักคือการกำหนดตารางการดำเนินการเขียนในลักษณะต้นไม้ไบนารี และค่อยๆ รวมข้อมูลเข้าเป็นบล็อกเดียว ในรอบแรก โปรเซสเซอร์จะรวมบล็อกของตนเข้าเป็นบล็อก จากนั้นโปรเซสเซอร์จะรวมบล็อกเข้าเป็น ขั้นตอนนี้จะดำเนินต่อไปจนกว่าข้อมูลทั้งหมดจะถูกรวมเข้าเป็นบล็อกเดียว ${\displaystyle P\leq B}$${\displaystyle P}$${\displaystyle O(\log(P))}$${\displaystyle P}$${\displaystyle P/2}$${\displaystyle P/2}$${\displaystyle P/2}$${\displaystyle P/4}$

ให้เป็นเวกเตอร์ของตัวหมุน d-1 ที่เรียงลำดับจากน้อยไปมาก ให้Aเป็นเซตที่ไม่มีลำดับขององค์ประกอบ N ตัว การแบ่งพาร์ติชัน d ทาง^{[ 1 ]}ของAคือเซตโดยที่และสำหรับ เรียกว่าบัคเก็ต ที่i จำนวนองค์ประกอบในมากกว่าและน้อยกว่าในอัลกอริทึมต่อไปนี้^{[ 1 ]}อินพุตจะถูกแบ่งพาร์ติชันออกเป็นส่วนย่อยต่อเนื่องขนาด N/P ในหน่วยความจำหลัก โปรเซสเซอร์ i ทำงานหลักๆ กับส่วนย่อยอัลกอริทึมการแบ่งพาร์ติชันแบบหลายทาง ( ^{[ 1 ]} ) ใช้อัลกอริทึมผลรวมคำนำหน้า PEM ^{[ 1 ]}เพื่อคำนวณผลรวมคำนำหน้าด้วยความซับซ้อน I/O ที่เหมาะสมที่สุด อัลกอริทึมนี้จำลองอัลกอริทึมผลรวมคำนำหน้า PRAM ที่เหมาะสมที่สุด ${\displaystyle M=\{m_{1},...,m_{d-1}\}}$${\displaystyle \Pi =\{A_{1},...,A_{d}\}}$${\displaystyle \cup _{i=1}^{d}A_{i}=A}$${\displaystyle A_{i}\cap A_{j}=\emptyset }$${\displaystyle 1\leq i<j\leq d}$${\displaystyle A_{i}}$${\displaystyle A_{i}}$${\displaystyle m_{i-1}}$${\displaystyle m_{i}^{2}}$${\displaystyle S_{1},...,S_{P}}$${\displaystyle S_{i}}$PEM_DIST_SORT${\displaystyle O\left({\frac {N}{PB}}+\log P\right)}$

// คำนวณพาร์ติชั่นแบบ d ทางบนเซ็กเมนต์ข้อมูลสำหรับแต่ละโปรเซสเซอร์ i แบบขนาน อ่านเวกเตอร์ของตัวแบ่งMลงในแคช${\displaystyle S_{i}}$ แบ่งข้อมูลออกเป็น d กลุ่ม และให้เวกเตอร์แทนจำนวนรายการในแต่ละกลุ่ม จบสำหรับ${\displaystyle S_{i}}$${\displaystyle M_{i}=\{j_{1}^{i},...,j_{d}^{i}\}}$ เรียกใช้ฟังก์ชัน PEM prefix sum กับชุดเวกเตอร์พร้อมกัน${\displaystyle \{M_{1},...,M_{P}\}}$ // ใช้เวกเตอร์ผลรวมคำนำหน้าเพื่อคำนวณพาร์ติชันสุดท้าย สำหรับโปรเซสเซอร์ i แต่ละ ตัวแบบขนาน ให้ เขียนองค์ประกอบลงในตำแหน่งหน่วยความจำโดยมีการชดเชยอย่างเหมาะสมด้วยและ. จบสำหรับ${\displaystyle S_{i}}$${\displaystyle M_{i-1}}$${\displaystyle M_{i}}$ โดยใช้ผลรวมนำหน้าที่จัดเก็บไว้ในตัวประมวลผลสุดท้าย P จะคำนวณเวกเตอร์Bของขนาดบัคเก็ตและส่งคืนค่าดังกล่าว ${\displaystyle M_{P}}$

ถ้าเวกเตอร์ของจุดหมุน M และชุดข้อมูลนำเข้า A อยู่ในหน่วยความจำที่ต่อเนื่องกัน ปัญหาการแบ่งพาร์ติชันแบบ d ทางสามารถแก้ไขได้ในแบบจำลอง PEM ด้วยความซับซ้อนของ I/O โดยที่เนื้อหาของบัคเก็ตสุดท้ายจะต้องอยู่ในหน่วยความจำที่ต่อเนื่องกันด้วย ${\displaystyle d=O\left({\frac {M}{B}}\right)}$${\displaystyle O\left({\frac {N}{PB}}+\left\lceil {\frac {d}{B}}\right\rceil >\log(P)+d\log(B)\right)}$

ปัญหาการเลือกคือการค้นหารายการที่เล็กที่สุดลำดับที่ k ในรายการที่ไม่มีลำดับAที่มีขนาดNรหัสต่อไปนี้^{[ 1 ]}ใช้ประโยชน์จากPRAMSORTอัลกอริทึมการเรียงลำดับที่เหมาะสมที่สุดของ PRAM ซึ่งทำงานในและซึ่งเป็นอัลกอริทึมการเลือกแบบโปรเซสเซอร์เดี่ยวที่เหมาะสมที่สุดของแคช ${\displaystyle O(\log N)}$SELECT

ถ้าเช่นนั้นให้ส่งคืนค่าสิ้นสุดของเงื่อนไข${\displaystyle N\leq P}$${\displaystyle {\texttt {PRAMSORT}}(A,P)}$${\displaystyle A[k]}$ //หาค่ามัธยฐานของแต่ละโปรเซสเซอร์i ในแบบขนาน ทำซ้ำจนครบ${\displaystyle S_{i}}$${\displaystyle m_{i}={\texttt {SELECT}}(S_{i},{\frac {N}{2P}})}$ // เรียงลำดับค่ามัธยฐาน ${\displaystyle {\texttt {PRAMSORT}}(\lbrace m_{1},\dots ,m_{2}\rbrace ,P)}$ // การแบ่งกลุ่มตามค่ามัธยฐานของค่ามัธยฐาน ${\displaystyle t={\texttt {PEMPARTITION}}(A,m_{P/2},P)}$ถ้าเป็นเช่นนั้นให้ส่งคืนมิฉะนั้นให้ส่งคืนสิ้นสุดเงื่อนไข${\displaystyle k\leq t}$${\displaystyle {\texttt {PEMSELECT}}(A[1:t],P,k)}$${\displaystyle {\texttt {PEMSELECT}}(A[t+1:N],P,kt)}$

ภายใต้สมมติฐานว่าข้อมูลนำเข้าถูกจัดเก็บไว้ในหน่วยความจำแบบต่อเนื่องPEMSELECTจะมีความซับซ้อนในการรับส่งข้อมูล (I/O complexity) ดังนี้:

${\displaystyle O\left({\frac {N}{PB}}+\log(PB)\cdot \log({\frac {N}{P}})\right)}$

การเรียงลำดับ แบบกระจาย (Distribution sort)แบ่งรายการข้อมูลนำเข้าAที่มีขนาดNออกเป็นdกลุ่มย่อยที่ไม่ซ้ำกัน โดยแต่ละกลุ่มย่อยจะมีขนาดใกล้เคียงกัน จากนั้นแต่ละกลุ่มย่อยจะถูกเรียงลำดับแบบเรียกซ้ำ และผลลัพธ์จะถูกรวมเข้าด้วยกันเป็นรายการที่เรียงลำดับอย่างสมบูรณ์

หากมอบหมายงานให้กับอัลกอริทึมการเรียงลำดับแบบโปรเซสเซอร์เดี่ยวที่เหมาะสมกับแคช ${\displaystyle P=1}$

มิเช่นนั้น จะใช้ อัลกอริทึมต่อไปนี้^{[ 1 ] :}

// สุ่มตัวอย่างองค์ประกอบจากA สำหรับแต่ละโปรเซสเซอร์i ในแบบขนาน ทำซ้ำถ้าเป็นเช่นนั้น ให้โหลดลงในหน้าขนาด M และเรียงลำดับแต่ละหน้า มิฉะนั้น ให้โหลดและเรียงลำดับเป็นหน้าเดียว จบเงื่อนไข เลือกองค์ประกอบที่ 'th จากแต่ละหน้าหน่วยความจำที่เรียงลำดับแล้วลงในเวกเตอร์ตัวอย่าง ที่ต่อเนื่องกัน จบเงื่อนไข${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$${\displaystyle M<|S_{i}|}$${\displaystyle d=M/B}$${\displaystyle S_{i}}$${\displaystyle d=|S_{i}|}$${\displaystyle S_{i}}$${\displaystyle {\sqrt {d}}/4}$${\displaystyle R^{i}}$ทำแบบขนาน รวมเวกเตอร์เข้าเป็นเวกเตอร์เดียวที่ต่อเนื่องกัน สร้างสำเนาของ: จบการ ทำ${\displaystyle R^{1}\dots R^{P}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\sqrt {d}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {R}}_{1}\dots {\mathcal {R}}_{\sqrt {d}}}$ // ค้นหาจุดหมุนสำหรับ to ใน parallel do end for${\displaystyle {\sqrt {d}}}$${\displaystyle {\mathcal {M}}[j]}$${\displaystyle j=1}$${\displaystyle {\sqrt {d}}}$${\displaystyle {\mathcal {M}}[j]={\texttt {PEMSELECT}}({\mathcal {R}__{i},{\tfrac {P}{\sqrt {d}}},{\tfrac {j\cdot 4N}{d}})}$ จุดหมุนของแพ็คในอาร์เรย์ต่อเนื่อง${\displaystyle {\mathcal {M}}}$ // แบ่งพาร์ติชันAรอบจุดหมุนออกเป็นกลุ่มๆ${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$ // เรียงลำดับบัคเก็ตแบบเรียกซ้ำ เพื่อ ดำเนินการแบบขนาน โดยเรียกซ้ำบนบัคเก็ตjที่มีขนาด โดยใช้โปรเซสเซอร์ที่รับผิดชอบองค์ประกอบในบัคเก็ตj สิ้นสุดสำหรับ${\displaystyle j=1}$${\displaystyle {\sqrt {d}}+1}$${\displaystyle {\texttt {PEMDISTSORT}}}$${\displaystyle {\mathcal {B}}[j]}$${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$

ความซับซ้อนของการรับส่งข้อมูล (I/O complexity) PEMDISTSORTคือ:

${\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)}$

ที่ไหน

${\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)}$

ถ้าเลือกจำนวนโปรเซสเซอร์แล้วและความซับซ้อนของการรับส่งข้อมูล (I/O complexity) เป็นดังนี้: ${\displaystyle f(N,P,d)=O\left(\left\lceil {\tfrac {N}{PB}}\right\rceil \right)}$${\displaystyle M<B^{O(1)}}$

${\displaystyle O\left({\frac {N}{PB}}\log _{M/B}{\frac {N}{B}}\right)}$

อัลกอริทึม PEM	ความซับซ้อนของอินพุต/เอาต์พุต	ข้อจำกัด
เมอร์จซอร์ต[ 1 ]	${\displaystyle O\left({\frac {N}{PB}}\log _{\frac {M}{B}}{\frac {N}{B}}\right)={\textrm {sort}}_{P}(N)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
การจัดอันดับรายการ[ 2 ]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N/B^{2}}{\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
ทัวร์ออยเลอร์[ 2 ]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}}},M=B^{O(1)}}$
การประเมินแผนผังการแสดงออก[ 2 ]	${\displaystyle O\left({\textrm {sort}}_{P}(N)\right)}$	${\displaystyle P\leq {\frac {N}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$
การค้นหาMST [ 2 ]	${\displaystyle O\left({\textrm {sort}}_{P}(|V|)+{\textrm {sort}}_{P}(|E|)\log {\tfrac {|V|}{pB}}\right)}$	${\displaystyle p\leq {\frac {|V|+|E|}{B^{2}\log B\cdot \log ^{O(1)}N}},M=B^{O(1)}}$

ในแบบจำลอง PEM การจัดเรียงสิ่งของ Nชิ้นด้วย โปรเซสเซอร์ P ตัวใช้เวลานานเท่าใด${\displaystyle {\textrm {sort}}_{P}(N)}$

• หน่วยความจำเข้าถึงแบบสุ่มขนาน (PRAM)
• หน่วยความจำเข้าถึงแบบสุ่ม (RAM)
• หน่วยความจำภายนอก (EM)