سوار

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
الموسوعة الحرة

تقنية SIMD داخل سجل ( SWAR )، والمعروفة أيضًا باسم "SPIMD المضغوط" [ 1 ]، هي تقنية لتنفيذ عمليات متوازية على البيانات الموجودة في سجل المعالج . SIMD اختصار لـ "تعليمات واحدة، بيانات متعددة" .

تتضمن العديد من معالجات الحواسيب الحديثة متعددة الأغراض بعض الإمكانيات لتقنية SIMD ، وذلك في شكل مجموعة من المسجلات والتعليمات اللازمة لاستخدامها. يشير مصطلح SWAR إلى استخدام هذه المسجلات والتعليمات، بدلاً من استخدام محركات معالجة متخصصة مصممة خصيصًا لأداء عمليات SIMD بكفاءة أعلى. كما يشير أيضًا إلى استخدام تقنية SIMD مع مسجلات وتعليمات متعددة الأغراض لم تكن مصممة لهذا الغرض في ذلك الوقت، وذلك من خلال حيل برمجية مبتكرة. [ 3 ]

معمارية SWAR

تُعرف بنية SWAR بأنها بنية تتضمن تعليمات مُصممة خصيصًا لتنفيذ عمليات متوازية على البيانات المخزنة في الكلمات الفرعية أو الحقول المستقلة في سجل. أما البنية القادرة على تنفيذ SWAR فهي بنية تتضمن مجموعة من التعليمات الكافية لمعالجة البيانات المخزنة في هذه الحقول بشكل مستقل، حتى وإن لم تتضمن البنية تعليمات مُصممة خصيصًا لهذا الغرض.

كان جهاز لينكولن لابوراتوري TX-2، الذي دخل حيز التشغيل عام 1958، أحد الأمثلة التاريخية الأولى، حيث كان يتمتع بذاكرة عرضها 36 بت، وتعليمات يمكن تنفيذها في وحدة الحساب والمنطق على كلمة فرعية واحدة بعرض 36 بت، أو على كلمتين فرعيتين بعرض 18 بت، أو على أربع كلمات فرعية بعرض 9 بت. ويسبق جهاز TX-2 اختراع مصطلح SIMD. [ 4 ]

كان معالج إنتل بنتيوم المزود بتقنية MMX مثالًا مبكرًا وشهيرًا على بنية SWAR ، حيث نفّذ مجموعة امتدادات MMX . وعلى النقيض من ذلك، لم يتضمن معالج إنتل بنتيوم مثل هذه التعليمات، ولكنه مع ذلك استطاع العمل كبنية SWAR من خلال البرمجة اليدوية الدقيقة أو تقنيات المُترجم.

تشمل معمارية SWAR المبكرة معالج DEC Alpha MVI ، ومعالج PA-RISC MAX من شركة Hewlett-Packard ، ومعالج MIPS MDMX من شركة Silicon Graphics Incorporated ، ومعالج SPARC V9 VIS من شركة Sun. ومثل معالج MMX، صُممت العديد من مجموعات تعليمات SWAR لترميز الفيديو بشكل أسرع. [ 5 ]

تاريخ نموذج برمجة SWAR

قدّم ويسلي أ. كلارك عمليات معالجة البيانات المجزأة للكلمات الفرعية في خمسينيات القرن العشرين . ويمكن اعتبار ذلك سلفًا مبكرًا جدًا لتقنية SWAR. وقدّم ليزلي لامبورت تقنيات SWAR في بحثه بعنوان "معالجة البايتات المتعددة باستخدام تعليمات الكلمات الكاملة" [ 6 ] عام 1975.

مع طرح امتدادات مجموعة تعليمات الوسائط المتعددة MMX من إنتل عام 1996، أصبحت معالجات سطح المكتب المزودة بإمكانيات المعالجة المتوازية SIMD شائعة. في البداية، كان استخدام هذه التعليمات مقتصراً على استخدام كود التجميع المكتوب يدوياً.

في خريف عام ١٩٩٦، كان البروفيسور هانك ديتز مُدرّسًا لمقرر بناء المترجمات لطلاب البكالوريوس في كلية الهندسة الكهربائية وهندسة الحاسوب بجامعة بيردو. في هذا المقرر، كلّف الطلاب بسلسلة من المشاريع لبناء مترجم بسيط يستهدف لغة MMX. وكانت لغة الإدخال لهجة فرعية من لغة MPL الخاصة بـ MasPar تُسمى NEMPL (ليست MPL تمامًا).

خلال الفصل الدراسي، اتضح لمساعد تدريس المقرر، راندال (راندي) فيشر، وجود عدد من المشكلات في لغة MMX التي ستُصعّب بناء الواجهة الخلفية لمترجم NEMPL. على سبيل المثال، تحتوي MMX على تعليمة لضرب بيانات 16 بت، لكنها لا تحتوي على تعليمة لضرب بيانات 8 بت. لم تُراعِ لغة NEMPL هذه المشكلة، مما سمح للمبرمج بكتابة برامج تتطلب عمليات ضرب بيانات 8 بت.

لم تكن بنية x86 من إنتل البنية الوحيدة التي تضمنت تعليمات متوازية شبيهة بـ SIMD. فقد أُضيفت مجموعات تعليمات الوسائط المتعددة الأخرى، مثل VIS من صن و MDMX من إس جي آي ، إلى بنى مجموعات التعليمات الحالية لدى مصنّعين آخرين لدعم ما يُسمى بتطبيقات الوسائط الجديدة . وقد اختلفت هذه الإضافات اختلافًا كبيرًا في دقة البيانات وأنواع التعليمات المدعومة.

بدأ ديتز وفيشر بتطوير فكرة نموذج برمجة متوازية مُحدد جيدًا يسمح للبرمجة باستهداف النموذج دون معرفة تفاصيل بنية النظام المستهدف. أصبح هذا النموذج أساس أطروحة فيشر. وقد صاغ ديتز وفيشر اختصار "SWAR" ذات يوم في مكتب هانك بمبنى قسم هندسة البرمجيات بجامعة بيردو. [ 7 ] ويشير هذا الاختصار إلى هذا النوع من المعالجة المتوازية، والبنى المصممة لأداء هذا النوع من المعالجة بشكل أصلي، ونموذج البرمجة العامة الذي تُعد أطروحة فيشر.

تمت مناقشة مشكلة التجميع لهذه البنى المتباينة على نطاق واسع في ورقة بحثية تم تقديمها في مؤتمر LCPC98. [ 5 ]

بعض تطبيقات SWAR

استُخدمت معالجة SWAR في معالجة الصور، [ 8 ] والاقترانات التشفيرية، [ 9 ] ومعالجة الصور النقطية، [ 10 ] وديناميكيات الموائع الحسابية، [ 11 ] والاتصالات. [ 12 ]

أمثلة

يمكن استخدام تقنيات SWAR حتى على الأنظمة التي لا تدعمها أجهزة خاصة. تعمل العمليات المنطقية على مستوى البت، أي أنها تُطبق على كل بت من السجل بشكل مستقل. يُعد استخدام الجمع والطرح أكثر صعوبة، ولكنه قد يكون مفيدًا إذا تم الحرص على تجنب انتقال الحمل غير المرغوب فيه بين المسارات. باستثناء انتقال الحمل هذا، فإن عملية جمع أو طرح واحدة لـ 64 بت تُعادل إجراء ثماني عمليات جمع أو طرح لـ 8 بت.

تم ضبط بتات العد

ربما يكون المثال النموذجي لتقنيات SWAR هو إيجاد عدد البتات المُفعّلة في سجل ما. يُعامل السجل تباعًا كسلسلة من الحقول المكونة من بت واحد، وبتين، وأربعة بتات، وهكذا.

بدايةً، لاحظ أن عدد عناصر حقل مكون من بت واحد هو ببساطة عدد عناصر الحقل نفسه. ولإيجاد عدد عناصر حقل مكون من بتين، اجمع عدد عناصر حقليه المكونين من بت واحد. ويمكن القيام بذلك بالتوازي لـ 32 حقلاً مكوناً من بتين في قيمة 64 بت x.

x2 := (x & 0x5555555555555555) + ((x >> 1) & 0x55555555555555555);

الثابت السداسي العشري0x5 هو 0101 2 بالنظام الثنائي ، وهو يعزل البتات ذات الأرقام الزوجية. لا يمكن أن يتجاوز مجموع كل حقل مكون من 2 بت الحد الأقصى، لأن أقصى مجموع ممكن هو 2.

يمكن تكرار هذه العملية لدمج الحقول المكونة من 2 بت في حقول مكونة من 4 بت. هنا، نستخدم قناعًا ثنائيًا 0011 2 ، أو سداسيًا عشريًا 0x3، لعزل أزواج البتات.

x4 := (x2 & 0x3333333333333333) + ((x2 >> 2) & 0x3333333333333333);

الآن، يحتوي كل حقل من 4 بتات على عدد من 0 إلى 4. ولأن حقل 4 بتات يمكن أن يحتوي على قيمة تصل إلى 15، فلا يمكن حدوث تجاوز عند جمع عددين من 4 بتات، مما يسمح بإجراء عملية الإخفاء بعد الجمع، بدلاً من مرة واحدة لكل عنصر مضاف:

x8 := (x4 + (x4 >> 4)) & 0x0f0f0f0f0f0f0f0f;

في هذه المرحلة، يمكن للحقول ذات 8 بت أن تحمل قيمًا تصل إلى 255، لذلك لا حاجة إلى مزيد من الإخفاء حتى النهاية:

x16 = x8 + (x8 >> 8)؛ x32 = x16 + (x16 >> 16)؛ x64 = x32 + (x32 >> 32)؛ عدد السكان = x64 & 0xff;

مزيد من التحسينات

توجد عدة صيغ معروفة لهذا. على وجه الخصوص، يمكن دمج خطوات الإزاحة والجمع الثلاث الأخيرة في

عدد السكان = (x8 * 0x0101010101010101) >> 56؛

تتطلب ثلاث مراحل من الإزاحة والجمع ست تعليمات، كل منها تعتمد على بيانات سابقتها، لذا تستغرق ست دورات ساعة على الأقل. عادةً ما يمكن تنفيذ عملية الضرب بشكل أسرع. عند التعامل مع كلمات 32 بت، يصبح الأمر أقل وضوحًا، حيث أن عملية الضرب التي تستغرق ثلاث دورات شائعة.

يتمثل البديل الثاني في تغيير الخطوة الأولى. فبدلاً من دمج البتّين b1 و b0 في كل حقل ثنائي البت عن طريق جمعهما، نعتبر القيمة الأولية للحقل الثنائي البت هي 2b1 + b0 . سيؤدي طرح b1 من هذه القيمة إلى الحصول على المجموع المطلوب، وذلك باستخدام عملية إخفاء واحدة فقط.

x2 := x − ((x >> 1) & 0x55555555555555555);

العثور على صفر بايت

من الشائع البحث عن حرف إنهاء السلسلة في سلسلة نصية . لكن القيام بذلك بايتًا واحدًا في كل مرة غير فعال، في حين أن المعالج ذو 64 بت يمكنه العمل على 8 بايتات في المرة الواحدة.

يمكن استخدام نفس الأسلوب للبحث عن فواصل مسار الاسم أو المحددات الأخرى، عن طريق إجراء عملية "أو" الحصرية مع قيمة البايت المستهدفة أولاً.

تتضمن بعض البنى تعليمات خاصة لإجراء مقارنات ثمانية بايتات دفعة واحدة. على سبيل المثال، احتوت بنية DEC AlphaCMPBGE على تعليمات لإجراء مقارنات ثمانية بايتات دفعة واحدة. مع ذلك، يمكن البحث عن بايت صفري دون أي دعم خاص.

إحدى الطرق هي دمج 8 بتات باستخدام عملية OR بطريقة مشابهة لمثال عد البتات أعلاه:

x2 = x | x<<1; ×4 = ×2 | x2<<2; x8 = x4 | x4<<4; byte_map = ~x8 & 0x8080808080808080;

ينتج عن ذلك byte_mapوجود بت واحد في البت الأكثر أهمية لأي بايت كان في الأصل صفرًا.

مع ذلك، يمكن إنجاز ذلك بسرعة أكبر بالاستفادة من خاصية نقل البيانات باستخدام العمليات الحسابية. إضافة 0x7f(01111111 2 بالنظام الثنائي ) إلى كل بايت تُسبب نقلًا إلى البت 7 إذا كانت البتات السبعة الأدنى غير صفرية. يكمن التحدي في ضمان توقف نقل البيانات عند البت 7 وعدم تأثيره على البايتات الأخرى. يمكن تحقيق ذلك بالعمل على البتات السبعة الأدنى والبت الأعلى لكل بايت على حدة. أولًا، استخرج البتات السبعة الأدنى من كل بايت باستخدام عملية AND0x7f قبل الإضافة 0x7f.

x7 = (x & 0x7f7f7f7f7f7f7f7f) + 0x7f7f7f7f7f7f7f7f؛

ثم اجمعها مع الأجزاء الأكثر أهمية:

x8 = x7 | x;

ستُضبط قيمة البت الأكثر أهمية (msbit) لكل حقل من حقول 8 بت على 1 إذا كانت قيمة هذا البايت غير صفرية. وأخيرًا:

byte_map = ~(x8 | 0x7f7f7f7f7f7f7f7f);

سيتم تعيين جميع البتات المنخفضة غير المرغوب فيها في كل بايت، ثم عكس كل شيء، بحيث لا يتبقى سوى بتات 1 في أي مكان يكون فيه بايت الإدخال المقابل صفرًا. (هذا مكافئ لـ ~x8 & 0x80...80، ولكنه يستخدم نفس القيمة الثابتة). إذا لم تكن هناك بتات 1، فيمكن مواصلة البحث مع الكلمة التالية. إذا كانت هناك أي بتات 1، فيمكن حساب طول السلسلة من مواقعها.

مزيد من التحسينات

إذا كان الهدف يقتصر على إيجاد أول بايت صفري على معالج little-endian ، فمن الممكن إيجاد أقل بايت صفري أهمية في عدد أقل من العمليات، باستخدام ثابتين مختلفين: [ 13 ]

x7 = x − 0x0101010101010101; byte_map = x7 & ~x & 0x8080808080808080;

لكل بايت b ، يتم تعيين msbit الخاص به byte_mapإذا تم تعيين msbit الخاص بـ b − 1 وكان msbit الخاص بـ b غير مفعل، وهو أمر يحدث فقط إذا كان b = 0.

العبارة السابقة صحيحة فقط إذا لم يكن هناك استعارة في ؛ إذا كان هناك استعارة، فسيكون الشرط صحيحًا أيضًا إذا كانت b = 1. ومع ذلك، لا يمكن توليد مثل هذه الاستعارة إلا بواسطة بايت صفري أقل أهمية، لذلك سيتم تحديد البايت الصفري الأقل أهمية بشكل صحيح، كما هو مطلوب.

لا يقتصر الأمر على توفير عملية ثنائية واحدة فحسب، بل إنها ليست جميعها مترابطة تسلسليًا، لذا يمكن تنفيذها في دورتين بافتراض وجود تعليمة "وليس" (مسح البت).

عمليات البحث في الجداول الصغيرة

كتعميم لخريطة البتات ، يُمكن تخزين جداول بحث صغيرة جدًا في سجل واحد. على سبيل المثال، يتراوح عدد أيام الشهر بين 28 و31 يومًا، أي ضمن نطاق 4 قيم. يُمكن تخزين هذا في 12 × 2 = 24 بت.

days_table = 0xeefbb3 + (is_leap_year << 2); days_in_month = 28 + (days_table >> 2*month & 3);

(هذا بافتراض أن رقم الشهر يبدأ من الصفر . يمكن استيعاب رقم الشهر الذي يبدأ من الواحد عن طريق تحريك الفاصلة days_table.)

إن حقيقة أن الجدول يتناسب بشكل أنيق مع سجل واحد تجعل من السهل تعديله للسنوات الكبيسة .

انظر أيضاً

مراجع

  1. ↑ مياوكا، ي.؛ تشوي، ج.؛ توغاوا، ن.؛ ياناغيساوا، م.؛ أوتسوكي، ت. (2002). خوارزمية لتوليد وحدات الأجهزة لتوليف نواة المعالج باستخدام تعليمات SIMD المعبأة . مؤتمر آسيا والمحيط الهادئ للدوائر والأنظمة. المجلد  1. الصفحات 171-176 . doi : 10.1109/APCCAS.2002.1114930 . hdl : 2065/10689 . 
  2. ↑ فلين، مايكل ج. (سبتمبر 1972). "بعض تنظيمات الحاسوب وفعاليتها" (ملف PDF) . معاملات IEEE في مجال الحواسيب . C-21 (9): 948-960 . doi : 10.1109/TC.1972.5009071 .
  3. ↑ فيشر، راندال جيه (2003). SIMD للأغراض العامة ضمن سجل: المعالجة المتوازية على المعالجات الدقيقة الاستهلاكية (PDF) (دكتوراه). جامعة بيردو.
  4. ↑ "نسخة مؤرشفة" (PDF) . مؤرشفة من النسخة الأصلية (PDF) بتاريخ 22-04-2021.{{cite web}}: CS1 maint: archived copy as title ( link )
  5. 1 2 فيشر، راندال جيه؛ هنري جي. ديتز (أغسطس 1998). إس. تشاتيرجي؛ جيه إف برينس؛ إل. كارتر؛ جيه. فيرانتي؛ زد. لي؛ دي. سيهر؛ بي.-سي. يو (محررون). "الترجمة البرمجية لتقنية SIMD ضمن سجل". وقائع ورشة العمل الدولية الحادية عشرة حول اللغات والمترجمات للحوسبة المتوازية .
  6. ↑ لامبورت، ليزلي (أغسطس 1975). "معالجة متعددة البايتات باستخدام تعليمات الكلمات الكاملة" . اتصالات رابطة آلات الحوسبة . 18 (8): 471-475 . doi : 10.1145/360933.360994 . S2CID 1593593 . 
  7. ↑ ديتز، هانك. "خوارزميات السحر التجميعي" .
  8. ^ بادوا، فلافيو إل سي؛ بيريرا ، جيلهيرم AS . نيتو، خوسيه بي دي كيروش؛ كامبوس، ماريو FM؛ فرنانديز ، أنطونيو أو. (يناير 2001). تحسين وقت معالجة الصور الكبيرة عن طريق التوازي على مستوى التعليمات (PDF) . أسبوع الحوسبة التشيلي، ورشة العمل الخامسة حول الأنظمة المتوازية والموزعة. بونتا اريناس. مؤرشفة من الأصلي (PDF) بتاريخ 25-02-2007 . تم الاسترجاع 2012/12/05 .
  9. ↑ غرابهر، فيليب؛ يوهان غروسشادل؛ دان بيج (2009). "حول التنفيذ المتوازي للبرمجيات لعمليات الاقتران التشفيري". مجالات مختارة في التشفير . سلسلة محاضرات في علوم الحاسوب. المجلد 5381. الصفحات 35-50 . doi : 10.1007/978-3-642-04159-4_3 . ISBN   978-3-642-04158-7.
  10. ↑ بيرسادا، أونيل نازرا؛ تييري غوبير (12-14 سبتمبر 2004). "تسريع معالجة الصور النقطية باستخدام التوازي الدقيق والخشن في GRASS". وقائع مؤتمر مستخدمي FOSS/GRASS لعام 2004 .
  11. ↑ هاوزر، توماس؛ تي آي ماتوكس؛ آر بي لوبو؛ إتش جي ديتز؛ بي جي هوانغ (أبريل 2003). "تحسينات برمجية للمعالجات الدقيقة المعقدة المطبقة على برامج ديناميكا الموائع الحسابية". مجلة SIAM للحوسبة العلمية . 25 (4): 1461-1477 . doi : 10.1137/S1064827502410530 . ISSN 1064-8275 . 
  12. ↑ سبراكلين، لورانس أ. (2001). أنظمة SWAR وتطبيقات الاتصالات (PDF) (دكتوراه). جامعة أبردين.
  13. ↑ فيشر، جيمس (24 يناير 2017). "التحقق السريع من وجود بايت صفري في لغة C باستخدام عمليات البت" . تم الاسترجاع في 21 ديسمبر 2024 .