الحساب العكسي

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

الحوسبة العكسية هي تطبيق برمجي لمفهوم الحوسبة العكسية .

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

يُعدّ مفهوم الحوسبة العكسية أبسط نوعًا ما من الحوسبة العكسية، إذ تقتصر الحاجة إلى الحوسبة العكسية على استعادة الحالة المكافئة لتطبيق برمجي، بدلًا من دعم عكسية مجموعة جميع التعليمات الممكنة. وقد طُبّقت مفاهيم الحوسبة العكسية بنجاح كحوسبة عكسية في مجالات تطبيقات البرمجيات، مثل تصميم قواعد البيانات [ 5 ] ، ونقاط التحقق وتصحيح الأخطاء [ 6 ] ، وتفاضل التعليمات البرمجية [ 7 ] [ 8 ] .

الحساب العكسي لمحاكاة الأحداث المنفصلة المتوازية

قائمة العمليات التي يمكن حسابها عكسياً وتكاليفها.

استنادًا إلى التطبيق الناجح لمفاهيم الحساب العكسي في مجالات برمجية أخرى، يقترح كريس كاروثرز وكاليان بيرومالا وريتشارد فوجيموتو [ 9 ] تطبيق الحساب العكسي لتقليل تكاليف حفظ الحالة في محاكاة الأحداث المنفصلة المتوازية (PDES). ويُعرّفون منهجًا قائمًا على رموز الأحداث العكسية (التي يمكن إنشاؤها تلقائيًا)، ويُبيّنون مزايا أداء هذا المنهج مقارنةً بحفظ الحالة التقليدي للتطبيقات الدقيقة (تلك التي تتضمن قدرًا ضئيلًا من العمليات الحسابية لكل حدث). وتكمن الخاصية الأساسية التي يستغلها الحساب العكسي في أن غالبية العمليات التي تُعدّل متغيرات الحالة هي عمليات "بنائية" بطبيعتها. أي أن عملية التراجع عن هذه العمليات لا تتطلب سجلًا تاريخيًا، بل يكفي فقط معرفة أحدث قيم المتغيرات للتراجع عن العملية. على سبيل المثال، تنتمي عوامل التشغيل مثل ++ و-- و+= و-= و*= و/= إلى هذه الفئة. تجدر الإشارة إلى أن عاملي التشغيل *= و/= يتطلبان معالجة خاصة في حالة الضرب أو القسمة على صفر، وفي حالات تجاوز السعة/نقص السعة. كما أن العمليات الأكثر تعقيدًا مثل الإزاحة الدائرية (التبديل حالة خاصة)، وبعض فئات توليد الأرقام العشوائية تنتمي إلى هنا أيضًا.

تُسمى العمليات التي تأخذ الصيغة a = b، أو عمليات حساب باقي القسمة ، أو العمليات الحسابية على مستوى البتات ، والتي تؤدي إلى فقدان البيانات، بالعمليات التخريبية. وعادةً ما لا يمكن استعادة هذه العمليات إلا باستخدام تقنيات حفظ الحالة التقليدية. ومع ذلك، نلاحظ أن العديد من هذه العمليات التخريبية هي نتيجة لوصول بيانات موجودة ضمن الحدث قيد المعالجة. على سبيل المثال، في دراسة ياون وكاروذرز وآخرين، باستخدام محاكاة TCP واسعة النطاق، [ 10 ] يسجل وقت الإرسال الأخير الطابع الزمني لآخر حزمة تم توجيهها في عملية منطقية لجهاز التوجيه. وتجعل عملية التبديل هذه العملية قابلة للعكس.

تاريخ الحساب العكسي وتطبيقه على محاكاة الأحداث المنفصلة المتوازية

تصنيف المحاكاة الرقمية.

في عام 1985، قدم جيفرسون بروتوكول التزامن التفاؤلي، الذي تم استخدامه في عمليات محاكاة الأحداث المنفصلة المتوازية، والمعروف باسم Time Warp. [ 11 ] وحتى الآن، لم يتم تطبيق التقنية المعروفة باسم الحساب العكسي إلا في البرامج لمحاكاة الأحداث المنفصلة المتوازية المتزامنة تفاؤلياً.

في ديسمبر 1999، تخرج مايكل فرانك من جامعة فلوريدا . ركزت أطروحته للدكتوراه على الحساب العكسي على مستوى الأجهزة، ولكنها تضمنت وصفًا لكل من بنية مجموعة التعليمات ولغة برمجة عالية المستوى (R) لمعالج يعتمد على الحساب العكسي. [ 12 ] [ ملاحظات 1 ]

في عام ١٩٩٨، نشر كاروثرز وبيرومالا ورقة بحثية في ورشة عمل "مبادئ المحاكاة المتقدمة والموزعة" [ ١٣ ] كجزء من دراساتهما العليا تحت إشراف ريتشارد فوجيموتو، حيث قدّما تقنية الحوسبة العكسية كآلية تراجع بديلة في محاكاة الأحداث المنفصلة المتوازية المتزامنة تفاؤلياً (تقنية Time Warp). في العام نفسه، أصبح كاروثرز أستاذاً مشاركاً في معهد رينسيلار للفنون التطبيقية . وبالتعاون مع طالبي الدراسات العليا ديفيد باور وشون بيرس، دمج كاروثرز تصميم تقنية Time Warp من معهد جورجيا للتكنولوجيا في نظام المحاكاة التفاؤلية (ROSS) التابع لمعهد رينسيلار، والذي كان يدعم الحوسبة العكسية فقط كآلية تراجع. كما قام كاروثرز ببناء نماذج الحوسبة العكسية لبروتوكول BitTorrent في شركة جنرال إلكتريك، بالإضافة إلى العديد من بروتوكولات الشبكات مع الطلاب ( BGP4 ، وTCP Tahoe، و Multicast ). أنشأ كاروثرز دورة تدريبية حول المحاكاة المتوازية والموزعة، حيث طُلب من الطلاب بناء نماذج الحوسبة العكسية في نظام ROSS.

في نفس الفترة تقريبًا، تخرج بيرومالا من معهد جورجيا للتكنولوجيا والتحق بالعمل في مختبر أوك ريدج الوطني (ORNL). هناك، قام بتطوير محاكي uSik، وهو عبارة عن بروتوكول PDES يجمع بين التفاؤل والتحفظ. كان النظام قادرًا على تحديد أفضل بروتوكول للبرمجة الخطية ديناميكيًا وإعادة تعيينها أثناء التنفيذ استجابةً لتغيرات النموذج. في عام 2007، اختبر بيرومالا uSik على نظام Blue Gene/L ، ووجد أنه بينما تقتصر قابلية التوسع على 8000 معالج لتنفيذ Time Warp الخالص، فإن التنفيذ المتحفظ يتوسع إلى 16000 معالج متاح. تجدر الإشارة إلى أن عملية قياس الأداء أُجريت باستخدام PHOLD مع معدل أحداث بعيد مقيد بنسبة 10%، حيث تم تحديد الطابع الزمني للأحداث بواسطة توزيع أسي بمتوسط ​​1.0، مع إضافة فترة استباقية إضافية قدرها 1.0 لكل حدث. كان هذا أول تطبيق لبروتوكول PDES على نظام Blue Gene باستخدام الحساب العكسي.

من عام ١٩٩٨ إلى عام ٢٠٠٥، أجرى باور دراسات عليا في معهد رينسيلار للفنون التطبيقية (RPI) تحت إشراف كاروثرز، مركزًا بشكل كامل على الحوسبة العكسية. وقد طور أول نظام PDES قائم كليًا على الحوسبة العكسية، أطلق عليه اسم نظام رينسيلار للمحاكاة التفاؤلية (ROSS) [ ١٤ ] ، وذلك لأنظمة الذاكرة المشتركة والموزعة المدمجة . من عام ٢٠٠٦ إلى عام ٢٠٠٩، عمل باور تحت إشراف إي إتش بيج في شركة MITRE ، وبالتعاون مع كاروثرز وبيرس، قام بتطوير محاكي ROSS ليعمل على معالج Blue Gene/P (Intrepid) ذي ١٣١,٠٧٢. وقد تميز هذا التطبيق بالاستقرار عند معدلات أحداث بعيدة تصل إلى ١٠٠٪ (إرسال كل حدث عبر الشبكة). خلال فترة عمله في معهد رينسيلار للفنون التطبيقية وشركة MITRE، طور باور نظام محاكاة الشبكة ROSS.Net [ ١٥ ] الذي يدعم تصميم التجارب شبه الآلي لتحسين نماذج بروتوكولات الشبكة التي يتم تنفيذها في ROSS. وكان الهدف الرئيسي للنظام هو تحسين نماذج بروتوكولات الشبكة المتعددة لتنفيذها في ROSS. على سبيل المثال، يُحسّن إنشاء بنية طبقات LP لإزالة الأحداث التي يتم تمريرها بين طبقات بروتوكول الشبكة LP على نفس الجهاز المُحاكى، من محاكاة عُقد شبكة TCP/IP عن طريق إزالة الطوابع الزمنية ذات الإزاحة الصفرية بين بروتوكولي TCP وIP. كما قام باور ببناء نماذج RC قائمة على الوكلاء لشبكات الاتصال الاجتماعي لدراسة آثار الأمراض المعدية ، ولا سيما الإنفلونزا الوبائية، والتي يمكن توسيع نطاقها لتشمل مئات الملايين من الوكلاء؛ بالإضافة إلى نماذج RC لشبكات الجوال المخصصة التي تُنفذ وظائف التنقل (كشف التقارب) وانتشار الموجات الكهرومغناطيسية في الطبقة الفيزيائية بدقة عالية (نموذج مصفوفة خط النقل). [ 16 ]

شهدت الفترة الأخيرة توجهاً متزايداً من مجتمع PDES نحو مجال المحاكاة المستمرة . فعلى سبيل المثال، قام فوجيموتو وبيرومالا، بالتعاون مع تانغ وآخرون [ 17 ] ، بتطبيق نموذج RC للجسيمات في الخلية، وأظهرا تسارعاً ملحوظاً مقارنةً بالمحاكاة المستمرة لنماذج الضوء كجسيم. كما أظهر باور وبيج تسارعاً ملحوظاً لنموذج مصفوفة خط النقل RC (بي بي جونز، 1971)، الذي ينمذج الضوء كموجة بترددات الميكروويف. وقد ابتكر باور أيضاً نسخة RC من نموذج SEIR تُحقق تحسناً هائلاً مقارنةً بالنماذج المستمرة في مجال انتشار الأمراض المعدية. إضافةً إلى ذلك، يتميز نموذج RC SEIR بقدرته على نمذجة أمراض متعددة بكفاءة، بينما يتضاعف النموذج المستمر بشكل كبير مع ازدياد عدد تركيبات الأمراض الممكنة بين السكان.

الفعاليات

ملحوظات

  1. ↑ يحتفظ الدكتور فرانك بموقعين إلكترونيين لمنشوراته حول الحساب العكسي حتى عام 2004 وما بعده .

مراجع

  1. ↑ لانداور، رولف (يوليو 1961). "عدم الانعكاسية وتوليد الحرارة في عملية الحوسبة". مجلة آي بي إم للبحوث والتطوير . 5 (3): 183-191 . CiteSeerX 10.1.1.68.7646 . doi : 10.1147/rd.53.0183 . 
  2. ↑ فون نيومان، جون (1966). نظرية الأوتوماتا ذاتية التكاثر . مطبعة جامعة إلينوي. ص 388. تم الاطلاع عليه بتاريخ 2009-04-06 . 
  3. ↑ بينيت، تشارلز هـ. (1982). "الديناميكا الحرارية للحوسبة - مراجعة" (ملف PDF) . المجلة الدولية للفيزياء النظرية . 21 (12): 905-940 . Bibcode : 1982IJTP...21..905B . CiteSeerX 10.1.1.655.5610 . doi : 10.1007/BF02084158 . S2CID 17471991. تاريخ الاسترجاع: 2009-04-06 .  
  4. ↑ فرانك، مايكل ب. (يونيو 1999). قابلية الانعكاس للحوسبة الفعالة، أطروحة دكتوراه (PDF) . معهد ماساتشوستس للتكنولوجيا، قسم الهندسة الكهربائية وعلوم الحاسوب . تاريخ الاسترجاع: 6 أبريل 2009 .
  5. ↑ ليمان الابن، جورج ب. (1986). "نهج رسمي لعمليات التراجع في لغات البرمجة" . معاملات ACM في لغات البرمجة والأنظمة . 8 (1): 50-87 . doi : 10.1145/5001.5005 .
  6. ↑ بيسواس، بيتان؛ مال، ر. (1999). "التنفيذ العكسي للبرامج" . إشعارات ACM SIGPLAN . 34 (4): 61-69 . doi : 10.1145/312009.312079 . S2CID 11685971 . 
  7. ↑ غريوانك، أندرياس؛ جوديس، ديفيد؛ أوتكه، جان (1996). "الخوارزمية 755: أدولك: حزمة للتفاضل التلقائي للخوارزميات المكتوبة بلغة سي/سي++" . معاملات ACM في البرمجيات الرياضية . 22 (2): 131-167 . doi : 10.1145/229473.229474 . S2CID 7339428 . 
  8. ↑ غريم، ج؛ بوتييه، ل؛ روستينغ-شميدت، ن. (1996). "الوقت الأمثل والحد الأدنى لحاصل ضرب المساحة والزمن لعكس فئة معينة من البرامج" (ملف PDF) . تقرير فني .
  9. ↑ كاروثرز، كريستوفر د.؛ بيرومالا، كاليان س.؛ فوجيموتو، ريتشارد م. (1999). "محاكاة متوازية تفاؤلية فعالة باستخدام الحساب العكسي" (ملف PDF) . معاملات ACM في النمذجة والمحاكاة الحاسوبية . 9 (3): 224-253 . CiteSeerX 10.1.1.113.1702 . doi : 10.1145/347823.347828 . S2CID 969021. مؤرشف من الأصل (ملف PDF) بتاريخ 17 يوليو 2011. تم الاسترجاع بتاريخ 6 أبريل 2009 .  
  10. ↑ ياون، غاريت؛ كاروثرز، كريستوفر د.؛ كاليانارامان، شيفكومار (2003). "نماذج TCP واسعة النطاق باستخدام المحاكاة المتوازية التفاؤلية". ورشة العمل السابعة عشرة حول المحاكاة المتوازية والموزعة، 2003. (PADS 2003). وقائع المؤتمر . الصفحات 153-162 . CiteSeerX 10.1.1.115.1320 . doi : 10.1109/PADS.2003.1207431 . ISBN   978-0-7695-1970-8. S2CID 6196101 . 
  11. ↑ جيفرسون، ديفيد ر. (1985). "الزمن الافتراضي" (ملف PDF) . معاملات ACM في لغات البرمجة والأنظمة . 7 (3): 404-425 . doi : 10.1145/3916.3988 . S2CID 2654080. تاريخ الاسترجاع: 2009-04-06 . 
  12. ↑ فييري، سي.؛ أمير، إم جيه.؛ فرانك، إم.؛ مارغولوس، إن .؛ نايت، تي. (يونيو 1998). "معالج دقيق قابل للعكس تمامًا ذو طاقة صفرية تقاربًا" (ملف PDF) . ورشة عمل هندسة المعالجات الدقيقة المدفوعة بالطاقة : 138-142 .
  13. ↑ ورشة عمل مبادئ المحاكاة المتقدمة والموزعة، والتي أصبحت الآن مؤتمر ACM SIGSIM حول مبادئ المحاكاة المنفصلة المتقدمة (PADS)
  14. ↑ كاروثرز، كريستوفر د.؛ باور، د. و.؛ بيرس، شون أ. (2002). "روس: نظام تايم وورب معياري عالي الأداء ومنخفض الذاكرة". مجلة الحوسبة المتوازية والموزعة . 62 (11): 1648-1669 . CiteSeerX 10.1.1.78.3105 . doi : 10.1016/S0743-7315(02)00004-7 . 
  15. ↑ باور، ديفيد دبليو؛ ياون، غاريت؛ كاروثرز، كريستوفر دي؛ يوكسيل، مراد؛ كاليانارامان، شيفكومار (2003). "ROSS.Net: إطار محاكاة متوازي متفائل لنماذج الإنترنت واسعة النطاق". وقائع المؤتمر الدولي لعام 2003 حول التعلم الآلي وعلم التحكم الآلي (IEEE Cat. No.03EX693) . المجلد 1. الصفحات 703-711 . doi : 10.1109/WSC.2003.1261486 . ​​ISBN   978-0-7803-8131-5. S2CID 2735827 . 
  16. ↑ باور الابن، ديفيد دبليو؛ بيج، إرنست إتش (2007). "محاكاة الأحداث المنفصلة المتوازية المتفائلة لطريقة مصفوفة خط النقل القائمة على الأحداث". وقائع المؤتمر التاسع والثلاثين حول محاكاة الشتاء: 40 عامًا! الأفضل لم يأتِ بعد : 676-684 . CiteSeerX 10.1.1.132.307 . 
  17. ↑ تانغ، واي.؛ بيرومالا، كيه إس؛ فوجيموتو، آر إم؛ كريمابادي، إتش.؛ دريسكول، جيه.؛ أوميلتشينكو، واي. (2005). "محاكاة الأحداث المنفصلة المتوازية المتفائلة للأنظمة الفيزيائية باستخدام الحساب العكسي". ورشة عمل حول مبادئ المحاكاة المتقدمة والموزعة (PADS'05) (ملف PDF) . الصفحات 26-35 . CiteSeerX 10.1.1.110.5893 . doi : 10.1109/PADS.2005.16 . ISBN   978-0-7695-2383-5. S2CID 802601 . تم الاسترجاع بتاريخ 2009-04-06 .