ذاكرة الوصول العشوائي المتوازية

الموسوعة الحرة

في علوم الحاسوب ، تُعرف آلة الوصول العشوائي المتوازية ( PRAM ) بأنها آلة مجردة ذات ذاكرة مشتركة . وكما يشير اسمها، فإن PRAM تُعتبر نظيرًا للحوسبة المتوازية لآلة الوصول العشوائي (RAM) ( مع التنويه إلى عدم الخلط بينها وبين ذاكرة الوصول العشوائي ). [ 1 ] وكما يستخدم مصممو الخوارزميات التسلسلية ذاكرة الوصول العشوائي (RAM) لنمذجة أداء الخوارزمية (مثل التعقيد الزمني)، يستخدم مصممو الخوارزميات المتوازية PRAM لنمذجة أداء الخوارزميات المتوازية (مثل التعقيد الزمني، حيث يُذكر عادةً عدد المعالجات المفترض). وعلى غرار تجاهل نموذج ذاكرة الوصول العشوائي (RAM) للمسائل العملية، مثل زمن الوصول إلى ذاكرة التخزين المؤقت مقابل الذاكرة الرئيسية، يتجاهل نموذج PRAM مسائل مثل التزامن والاتصال ، ولكنه يوفر أي عدد من المعالجات (يعتمد على حجم المسألة). فعلى سبيل المثال، تُقدّر تكلفة الخوارزمية باستخدام معيارين : O(الزمن) و O(الزمن × عدد المعالجات).

تعارضات القراءة/الكتابة

يتم حل تعارضات القراءة/الكتابة، والتي تسمى عادةً بالتداخل في الوصول إلى نفس موقع الذاكرة المشتركة في وقت واحد، من خلال إحدى الاستراتيجيات التالية:

  1. القراءة والكتابة الحصريتان (EREW) - يمكن قراءة أو كتابة كل خلية ذاكرة بواسطة معالج واحد فقط في كل مرة
  2. القراءة والكتابة الحصرية المتزامنة (CREW) - يمكن لعدة معالجات قراءة خلية ذاكرة، ولكن لا يمكن إلا لمعالج واحد الكتابة في كل مرة
  3. الكتابة المتزامنة للقراءة الحصرية (ERCW) - لم يتم النظر فيها في الغالب لأنها لا تضيف المزيد من القوة [ 2 ]
  4. القراءة والكتابة المتزامنة (CRCW) - يمكن لمعالجات متعددة القراءة والكتابة. يُطلق على ذاكرة الوصول العشوائي المتزامنة (PRAM) من نوع CRCW أحيانًا اسم آلة الوصول العشوائي المتزامنة . [ 3 ]

هنا، يرمز الحرفان E و C إلى "حصري" و "متزامن" على التوالي. لا تُسبب عملية القراءة أي اختلافات، بينما تُعرَّف عملية الكتابة المتزامنة على النحو التالي:

شائع — تكتب جميع المعالجات نفس القيمة؛ وإلا فهو غير قانوني
عشوائي - محاولة عشوائية واحدة فقط تنجح، أما البقية فتنسحب.
الأولوية - رتبة المعالج تشير إلى من يحق له الكتابة
نوع آخر من عمليات اختزال المصفوفات مثل SUM أو المنطق AND أو MAX.

تُعتمد عدة افتراضات تبسيطية عند دراسة تطوير خوارزميات PRAM، وهي:

  1. لا يوجد حد لعدد المعالجات في الجهاز.
  2. يمكن الوصول إلى أي موقع في الذاكرة بشكل موحد من أي معالج.
  3. لا يوجد حد لمقدار الذاكرة المشتركة في النظام.
  4. لا يوجد تنازع على الموارد .
  5. البرامج المكتوبة على هذه الأجهزة هي، بشكل عام، من نوع SIMD .

تُعدّ هذه الأنواع من الخوارزميات مفيدةً لفهم استغلال التزامن، وذلك بتقسيم المشكلة الأصلية إلى مشاكل فرعية متشابهة وحلّها بالتوازي. وقد هدف تقديم نموذج "P-RAM" الرسمي في أطروحة ويلي عام 1979 [ 4 ] إلى قياس تحليل الخوارزميات المتوازية بطريقة مماثلة لآلة تورينج . ركّز التحليل على نموذج برمجة MIMD باستخدام نموذج CREW، ولكنه أظهر إمكانية وجود العديد من المتغيرات، بما في ذلك تطبيق نموذج CRCW والتنفيذ على آلة SIMD، مع تكلفة إضافية ثابتة فقط.

تطبيق

لا يمكن موازاة خوارزميات PRAM باستخدام مزيج من وحدة المعالجة المركزية وذاكرة الوصول العشوائي الديناميكية (DRAM) لأن ذاكرة الوصول العشوائي الديناميكية لا تسمح بالوصول المتزامن إلى بنك واحد (ولا حتى عناوين مختلفة في البنك)؛ ولكن يمكن تنفيذها في الأجهزة أو القراءة/الكتابة إلى كتل ذاكرة الوصول العشوائي الثابتة الداخلية (SRAM) لمصفوفة البوابات القابلة للبرمجة الميدانية (FPGA)، ويمكن القيام بذلك باستخدام خوارزمية CRCW.

مع ذلك، يعتمد اختبار الجدوى العملية لخوارزميات PRAM (أو RAM) على ما إذا كان نموذج التكلفة الخاص بها يوفر تجريدًا فعالًا لحاسوب ما؛ إذ قد يختلف هيكل هذا الحاسوب اختلافًا كبيرًا عن النموذج المجرد. إن معرفة طبقات البرمجيات والأجهزة اللازمة لإدراجها تتجاوز نطاق هذه المقالة. لكن مقالات مثل فيشكين (2011) توضح كيف يمكن دعم تجريد شبيه بـ PRAM بواسطة نموذج تعدد الخيوط الصريح (XMT)، ومقالات مثل كاراجيا وفيشكين (2011) توضح أن خوارزمية PRAM لمسألة التدفق الأقصى يمكن أن توفر تسارعًا كبيرًا مقارنةً بأسرع برنامج تسلسلي لنفس المسألة. وقد أوضحت مقالة غانم وفيشكين وباروا (2018) أن خوارزميات PRAM بصيغتها الحالية يمكنها تحقيق أداء تنافسي حتى بدون أي جهد إضافي لتحويلها إلى برامج متعددة الخيوط على XMT.

مثال على التعليمات البرمجية

هذا مثال على كود SystemVerilog الذي يجد القيمة القصوى في المصفوفة خلال دورتي ساعة فقط. يقارن الكود جميع تركيبات عناصر المصفوفة في الدورة الأولى، ثم يدمج النتائج في الدورة الثانية. يستخدم الكود ذاكرة CRCW، m[i] <= 1وتُكتب maxNo <= data[i]القيم في وقت واحد. لا يُسبب التزامن أي تعارضات لأن الخوارزمية تضمن كتابة القيمة نفسها في الذاكرة نفسها. يمكن تشغيل هذا الكود على أجهزة FPGA .

وحدة FindMax #( معامل int len ​​= 8 ) ( بت الإدخال clock ، resetN ، بت الإدخال [ 7 : 0 ] data [ len ]، بت الإخراج [ 7 : 0 ] maxNo )؛ typedef enum bit [ 1 : 0 ] { COMPARE ، MERGE ، DONE } الحالة ؛ الحالة state ؛ بت m [ len ]؛ int i ، j ؛ always_ff @( حافة صاعدة clock ، حافة هابطة resetN ) ابدأ إذا ( ! resetN ) ابدأ من أجل ( i = 0 ؛ i < len ؛ i ++ ) m [ i ] <= 0 ؛ الحالة <= COMPARE ؛ نهاية else ابدأ حالة ( الحالة ) COMPARE: ابدأ من أجل ( i = 0 ؛ i < len ؛ i ++ ) ابدأ من أجل ( j = 0 ؛ j < len ؛ j ++ ) ابدأ إذا ( data [ i ] < data [ j ]) m [ i ] <= 1 ؛ نهاية نهاية الحالة <= دمج ؛ نهاية الدمج: بداية لـ ( i = 0 ؛ i < الطول ؛ i ++ ) بداية إذا ( m [ i ] == 0 ) الحد الأقصى للرقم <= البيانات[ i ]; نهاية الحالة <= تم ؛ نهاية نهاية الحالة نهاية نهاية نهاية الوحدة

انظر أيضاً

مراجع

  1. ↑ فورتشن، ستيفن؛ ويلي، جيمس (1978-05-01). "التوازي في آلات الوصول العشوائي" . وقائع الندوة السنوية العاشرة لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '78 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 114-118 . doi : 10.1145/800133.804339 . hdl : 1813/7454 . ISBN  978-1-4503-7437-8.
  2. ↑ ماكنزي، فيليب د.؛ راماتشاندران، فيجايا (6 أبريل 1998). "ذاكرة الوصول العشوائي ذات السعة المتغيرة ERCW والاتصالات الضوئية" . علوم الحاسوب النظرية . 196 (1): 153-180 . doi : 10.1016/S0304-3975(97)00199-0 . ISSN 0304-3975 . 
  3. ↑ نيل إيمرمان، قابلية التعبير والتعقيد المتوازي . مجلة SIAM للحوسبة، المجلد 18، العدد 3، الصفحات 625-638، 1989.
  4. ↑ ويلي، جيمس سي. تعقيد الحسابات المتوازية ، أطروحة دكتوراه، قسم علوم الحاسوب، جامعة كورنيل
  • إبستين، ديفيد؛ جاليل، تسفي (1988)، "تقنيات الخوارزميات المتوازية للحساب التوافقي"، المجلة السنوية لعلوم الحاسوب ، 3 : 233-283 ، doi : 10.1146/annurev.cs.03.060188.001313
  • جاجا، جوزيف (1992)، مقدمة في الخوارزميات المتوازية ، أديسون-ويسلي، رقم ISBN 0-201-54856-9
  • كارب، ريتشارد م.؛ راماتشاندران، فيجايا (1988)، مسح للخوارزميات المتوازية لآلات الذاكرة المشتركة ، جامعة كاليفورنيا، بيركلي، قسم الهندسة الكهربائية وعلوم الحاسوب، تقرير فني UCB/CSD-88-408
  • كيلر، يورغ. كريستوف كيسلر؛ يسبر تراف (2001). برمجة PRAM العملية . جون وايلي وأولاده. رقم ISBN 0-471-35351-5.
  • فيشكين، أوزي (2009)، التفكير بالتوازي: بعض الخوارزميات والتقنيات الأساسية للتوازي في البيانات، 104 صفحات (ملف PDF) ، ملاحظات صفية لمقررات دراسية حول الخوارزميات المتوازية تُدرَّس منذ عام 1992 في جامعة ميريلاند، كوليدج بارك، وجامعة تل أبيب، ومعهد التخنيون.
  • فيشكين، أوزي (2011)، "استخدام التجريد البسيط لإعادة ابتكار الحوسبة من أجل التوازي"، اتصالات ACM ، 54 : 75-85 ، doi : 10.1145/1866739.1866757
  • كاراجيا، جورج كونستانتين؛ فيشكين، أوزي (2011)، "إعلان موجز: تحسينات في سرعة التدفق الأقصى المتوازي"، وقائع الندوة الثالثة والعشرين لجمعية الحوسبة الآلية حول التوازي في الخوارزميات والهياكل - SPAA '11 ، ص  131، doi : 10.1145/1989493.1989511 ، ISBN 9781450307437، S2CID 5511743 
  • غانم، فادي؛ فيشكين، أوزي؛ باروا، راجيف (2018)، "برمجة متوازية عالية الأداء سهلة تعتمد على PRAM باستخدام ICE"، معاملات IEEE في الأنظمة المتوازية والموزعة ، 29 (2): 377-390 ، doi : 10.1109/TPDS.2017.2754376 ، hdl : 1903/18521