ذاكرة خارجية متوازية

يُعد نموذج PEM ^{[ 1 ]} مزيجًا من نموذج EM ونموذج PRAM. وهو نموذج حسابي يتكون من${\displaystyle P}$معالجات وهيكل ذاكرة ثنائي المستوى . يتكون هيكل الذاكرة هذا من ذاكرة خارجية كبيرة (ذاكرة رئيسية) بحجم${\displaystyle N}$و${\displaystyle P}$ذاكرة داخلية صغيرة (ذاكرة تخزين مؤقتة) . تتشارك المعالجات الذاكرة الرئيسية. كل ذاكرة تخزين مؤقتة خاصة بمعالج واحد فقط. لا يمكن لمعالج الوصول إلى ذاكرة تخزين مؤقتة لمعالج آخر. تتميز ذاكرات التخزين المؤقتة بحجم محدد.${\displaystyle M}$والتي يتم تقسيمها إلى كتل بحجم${\displaystyle B}$لا تستطيع المعالجات إجراء عمليات إلا على البيانات الموجودة في ذاكرتها المؤقتة (الذاكرة المخبئية). ويمكن نقل البيانات بين الذاكرة الرئيسية والذاكرة المؤقتة على شكل كتل بحجم معين.${\displaystyle B}$.

مقياس تعقيد نموذج PEM هو تعقيد الإدخال/الإخراج، ^{[ 1 ]} والذي يحدد عدد عمليات نقل الكتل المتوازية بين الذاكرة الرئيسية وذاكرة التخزين المؤقت. خلال عملية نقل كتلة متوازية، يمكن لكل معالج نقل كتلة واحدة. لذا، إذا${\displaystyle P}$تقوم المعالجات بتحميل كتلة بيانات بحجم معين بالتوازي${\displaystyle B}$تحويل الذاكرة الرئيسية إلى ذاكرات تخزين مؤقتة، يُعتبر ذلك تعقيدًا في عمليات الإدخال/الإخراج.${\displaystyle O(1)}$لا${\displaystyle O(P)}$ينبغي للبرنامج في نموذج PEM أن يقلل من نقل البيانات بين الذاكرة الرئيسية وذاكرة التخزين المؤقت وأن يعمل قدر الإمكان على البيانات الموجودة في ذاكرة التخزين المؤقت.

في نموذج 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}$وتستمر هذه العملية حتى يتم دمج جميع البيانات في كتلة واحدة.

يترك${\displaystyle M=\{m_{1},...,m_{d-1}\}}$ليكن متجهًا من d-1 محاور مرتبة ترتيبًا تصاعديًا. ولتكن A مجموعة غير مرتبة من N عنصرًا. التقسيم d-way ^{[ 1 ]} لـ A هو مجموعة${\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}}$يُطلق عليه اسم الحاوية رقم i. عدد العناصر في${\displaystyle A_{i}}$أكبر من${\displaystyle m_{i-1}}$وأصغر من${\displaystyle m_{i}^{2}}$في الخوارزمية التالية ^{[ 1 ]} ، يتم تقسيم المدخلات إلى أجزاء متجاورة بحجم N/P${\displaystyle S_{1},...,S_{P}}$في الذاكرة الرئيسية. يعمل المعالج i بشكل أساسي على القطاع${\displaystyle S_{i}}$تستخدم خوارزمية التقسيم متعدد الاتجاهات ( PEM_DIST_SORT^{[ 1 ]} ) خوارزمية مجموع البادئة PEM ^{[ 1 ]} لحساب مجموع البادئة الأمثل${\displaystyle O\left({\frac {N}{PB}}+\log P\right)}$تعقيد الإدخال/الإخراج. تحاكي هذه الخوارزمية خوارزمية مجموع البادئة PRAM المثلى.

// حساب تقسيم ثنائي الاتجاه على أجزاء البيانات بالتوازي${\displaystyle S_{i}}$لكل معالج i بالتوازي، اقرأ متجه المحاور M في الذاكرة المؤقتة. تقسيم${\displaystyle S_{i}}$في d دلاء ودع المتجه${\displaystyle M_{i}=\{j_{1}^{i},...,j_{d}^{i}\}}$ليكن عدد العناصر في كل دلو. نهاية الحلقة قم بتطبيق مجموع البادئة PEM على مجموعة المتجهات${\displaystyle \{M_{1},...,M_{P}\}}$معًا. // استخدم متجه المجموع البادئ لحساب التقسيم النهائي لكل معالج i بالتوازي، اكتب العناصر${\displaystyle S_{i}}$في مواقع الذاكرة مع إزاحة مناسبة بواسطة${\displaystyle M_{i-1}}$و${\displaystyle M_{i}}$. نهاية لـ باستخدام مجموعات البادئات المخزنة في${\displaystyle M_{P}}$يقوم المعالج الأخير P بحساب المتجه B لأحجام الحاويات وإعادته.

إذا كان متجه${\displaystyle d=O\left({\frac {M}{B}}\right)}$إذا كانت المحاور M ومجموعة المدخلات A موجودة في ذاكرة متجاورة، فيمكن حل مشكلة التقسيم متعدد الاتجاهات في نموذج PEM باستخدام${\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]}$نهاية الشرط // أوجد الوسيط لكل${\displaystyle S_{i}}$لكل معالج 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فإن تعقيد الإدخال/الإخراج هو:

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

تقوم خوارزمية فرز التوزيع بتقسيم قائمة الإدخال A ذات الحجم N إلى d مجموعات منفصلة ذات أحجام متقاربة. ثم يتم فرز كل مجموعة بشكل متكرر، وتُدمج النتائج في قائمة مرتبة بالكامل.

لو${\displaystyle P=1}$يتم تفويض المهمة إلى خوارزمية فرز أحادية المعالج ذات ذاكرة تخزين مؤقت مثالية.

وإلا يتم استخدام الخوارزمية التالية ^{[ 1 ] :}

// عينة${\displaystyle {\tfrac {4N}{\sqrt {d}}}}$لكل معالج i بالتوازي، قم بتنفيذ العناصر من A إذا${\displaystyle M<|S_{i}|}$ثم${\displaystyle d=M/B}$ حمولة${\displaystyle S_{i}}$في صفحات بحجم M ، وفرز الصفحات بشكل فردي، وإلا${\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}}}$نهاية التكرار // يجد${\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}}}$ // قسّم المجموعة أ حول المحاور إلى مجموعات فرعية${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {B}}={\texttt {PEMMULTIPARTITION}}(A[1:N],{\mathcal {M}},{\sqrt {d}},P)}$ // فرز المجموعات بشكل متكرر ل${\displaystyle j=1}$ل${\displaystyle {\sqrt {d}}+1}$بالتوازي، قم باستدعاء متكرر${\displaystyle {\texttt {PEMDISTSORT}}}$على دلو j بحجم${\displaystyle {\mathcal {B}}[j]}$ استخدام${\displaystyle O\left(\left\lceil {\tfrac {{\mathcal {B}}[j]}{N/P}}\right\rceil \right)}$المعالجات المسؤولة عن العناصر في نهاية المجموعة j لـ

تعقيد الإدخال/الإخراج 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)}$

إذا تم اختيار عدد المعالجات الذي${\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)}}$
إيجاد شجرة الامتداد الأدنى [ 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)}}$

أين${\displaystyle {\textrm {sort}}_{P}(N)}$هو الوقت الذي يستغرقه فرز N عنصرًا باستخدام P معالجًا في نموذج PEM.