عامل تخفيض السرعة

تمثل هذه الخوارزمية طريقة شائعة الاستخدام للتعامل مع المدخلات حيث${\displaystyle p}$هو قوة للعدد اثنين. غالبًا ما تُستخدم العملية العكسية لبث العناصر. ^{[ 6 ] [ 7 ] [ 8 ]}

ل${\displaystyle k\gets 0}$ل${\displaystyle \lceil \log _{2}p\rceil -1}$يفعل

ل${\displaystyle i\gets 0}$ل${\displaystyle p-1}$قم بذلك بالتوازي

لو${\displaystyle p_{i}}$إذا كان نشطًا

إذا بت${\displaystyle k}$ل${\displaystyle i}$يتم ضبطه بعد ذلك

تعيين${\displaystyle p_{i}}$إلى غير نشط

وإلا إذا${\displaystyle i+2^{k}<p}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

يُعرَّف المؤثر الثنائي للمتجهات عنصرًا بعنصر بحيث$${\displaystyle {\begin{pmatrix}e_{i}^{0}\\\vdots \\e_{i}^{m-1}\end{pmatrix}}\oplus ^{\star }{\begin{pmatrix}e_{j}^{0}\\\vdots \\e_{j}^{m-1}\end{pmatrix}}={\begin{pmatrix}e_{i}^{0}\oplus e_{j}^{0}\\\vdots \\e_{i}^{m-1}\oplus e_{j}^{m-1}\end{pmatrix}}.}$$

وتفترض الخوارزمية كذلك أنه في البداية${\displaystyle x_{i}=v_{i}}$للجميع${\displaystyle i}$و${\displaystyle p}$هو قوة للعدد اثنين ويستخدم وحدات المعالجة${\displaystyle p_{0},p_{1},\dots p_{n-1}}$في كل تكرار، يصبح نصف وحدات المعالجة غير نشط ولا يساهم في العمليات الحسابية اللاحقة. يوضح الشكل تمثيلًا مرئيًا للخوارزمية باستخدام الجمع كعامل. تمثل الخطوط الرأسية وحدات المعالجة التي تُجرى فيها حسابات العناصر الموجودة على ذلك الخط. تقع عناصر الإدخال الثمانية في الأسفل، وتتوافق كل خطوة من خطوات الرسوم المتحركة مع خطوة متوازية واحدة في تنفيذ الخوارزمية. معالج نشط${\displaystyle p_{i}}$يقوم بتقييم العامل المحدد على العنصر${\displaystyle x_{i}}$وهي تحتفظ حالياً بـ${\displaystyle x_{j}}$أين${\displaystyle j}$هل الفهرس الأدنى يحقق${\displaystyle j>i}$، لهذا السبب${\displaystyle p_{j}}$يصبح معالجًا غير نشط في الخطوة الحالية.${\displaystyle x_{i}}$و${\displaystyle x_{j}}$ليست بالضرورة عناصر من مجموعة المدخلات${\displaystyle X}$حيث يتم استبدال الحقول وإعادة استخدامها للتعبيرات التي تم تقييمها مسبقًا. ولتنسيق أدوار وحدات المعالجة في كل خطوة دون التسبب في اتصال إضافي بينها، يتم فهرسة وحدات المعالجة بأرقام من${\displaystyle 0}$ل${\displaystyle p-1}$يتم استخدامه. ينظر كل معالج إلى${\displaystyle k}$- البت الأقل أهمية ويحدد ما إذا كان سيتم تعطيله أو حساب المعامل على العنصر نفسه والعنصر ذي الفهرس حيث${\displaystyle k}$البت رقم -th غير مُفعّل. نمط الاتصال الأساسي للخوارزمية هو شجرة ذات الحدين، ومن هنا جاء اسم الخوارزمية.

فقط ${\displaystyle p_{0}}$يحتفظ بالنتيجة في النهاية، ولذلك فهو المعالج الرئيسي. في عملية Allreduce، يجب توزيع النتيجة، ويمكن القيام بذلك عن طريق إضافة بث من${\displaystyle p_{0}}$علاوة على ذلك، العدد${\displaystyle p}$يقتصر عدد المعالجات على أن يكون قوة للعدد اثنين. ويمكن تجاوز هذا القيد بزيادة عدد المعالجات إلى القوة التالية للعدد اثنين. كما توجد خوارزميات مصممة خصيصًا لهذه الحالة. ^{[ 9 ]}

على عكس خوارزمية PRAM، في نموذج الذاكرة الموزعة ، لا تتم مشاركة الذاكرة بين وحدات المعالجة، ويجب تبادل البيانات بشكل صريح بينها. لذا، يجب تبادل البيانات بشكل صريح بين الوحدات، كما هو موضح في الخوارزمية التالية.

ل${\displaystyle k\gets 0}$ل${\displaystyle \lceil \log _{2}p\rceil -1}$يفعل

ل${\displaystyle i\gets 0}$ل${\displaystyle p-1}$قم بذلك بالتوازي

لو${\displaystyle p_{i}}$إذا كان نشطًا

إذا بت${\displaystyle k}$ل${\displaystyle i}$يتم ضبطه بعد ذلك

يرسل${\displaystyle x_{i}}$ل${\displaystyle p_{i-2^{k}}}$

تعيين${\displaystyle p_{k}}$إلى غير نشط

وإلا إذا${\displaystyle i+2^{k}<p}$

يستلم${\displaystyle x_{i+2^{k}}}$

${\displaystyle x_{i}\gets x_{i}\oplus ^{\star }x_{i+2^{k}}}$

الفرق الوحيد بين الخوارزمية الموزعة وإصدار PRAM هو تضمين بدائيات الاتصال الصريحة، ويبقى مبدأ التشغيل كما هو.

عدد الخطوات في التنفيذ المتوازي هو${\displaystyle p+m-2}$، فإنه يأخذ${\displaystyle p-1}$خطوات حتى تتلقى وحدة المعالجة الأخيرة عنصرها الأول وعناصر إضافية${\displaystyle m-1}$حتى يتم استلام جميع العناصر. لذلك، فإن وقت التشغيل في نموذج BSP هو${\textstyle T(n,p,m)=\left(T_{\text{start}}+{\frac {n}{m}}\cdot T_{\text{byte}}\right)(p+m-2)}$بافتراض أن${\displaystyle n}$يمثل الحجم الإجمالي للبايتات للمتجه.

بالرغم من${\displaystyle m}$إذا كانت لها قيمة ثابتة، فمن الممكن تجميع عناصر المتجه معًا منطقيًا وتقليلها${\displaystyle m}$على سبيل المثال، يمكن معالجة مسألة تتضمن متجهات بحجم أربعة عن طريق تقسيم المتجهات إلى أول عنصرين وآخر عنصرين، واللذين يتم إرسالهما وحسابهما معًا دائمًا. في هذه الحالة، يتم إرسال ضعف الحجم في كل خطوة، ولكن عدد الخطوات ينخفض ​​إلى النصف تقريبًا. هذا يعني أن المعامل${\displaystyle m}$يتم تخفيض حجمه إلى النصف، بينما يتم تقليل الحجم الإجمالي بالبايت${\displaystyle n}$يبقى كما هو. وقت التشغيل${\displaystyle T(p)}$يعتمد هذا النهج على قيمة${\displaystyle m}$والتي يمكن تحسينها إذا${\displaystyle T_{\text{start}}}$و${\textstyle T_{\text{byte}}}$معروفة. إنها الأمثل لـ${\textstyle m={\sqrt {\frac {n\cdot (p-2)\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$بافتراض أن هذا يؤدي إلى حجم أصغر${\displaystyle m}$الذي يقسم الأصل.