آلة ذات برنامج مخزن ذي وصول عشوائي
في علم الحاسوب النظري، يعتبر نموذج آلة البرنامج المخزن ذو الوصول العشوائي (RASP) آلة مجردة تستخدم لأغراض تطوير الخوارزميات ونظرية تعقيد الخوارزميات .
إنّ RASP نموذجٌ لآلة الوصول العشوائي (RAM)، يختلف عن RAM بوجود برنامجه في "سجلاته" مع مدخلاته. هذه السجلات غير محدودة (سعتها لانهائية)؛ أما كونها محدودة فهو أمرٌ خاصٌ بكل نموذج. لذا، فإنّ RASP بالنسبة لـ RAM كآلة تورينج العالمية بالنسبة لآلة تورينج . يُعدّ RASP مثالًا على بنية فون نيومان ، بينما تُعدّ RAM مثالًا على بنية هارفارد .
يُعدّ نموذج RASP أقرب النماذج المجردة إلى المفهوم الشائع للحاسوب . ولكن على عكس الحواسيب الفعلية، يتميز نموذج RASP عادةً بمجموعة تعليمات بسيطة للغاية، مُختزلة بشكل كبير عن معالجات CISC وحتى RISC ، لتقتصر على أبسط العمليات الحسابية، ونقل البيانات بين المسجلات، وتعليمات الاختبار/القفز. تحتوي بعض النماذج على عدد قليل من المسجلات الإضافية، مثل المُراكم .
إلى جانب آلة التسجيل ، وذاكرة الوصول العشوائي، وآلة المؤشر ، تشكل RASP نماذج الآلات التسلسلية الأربعة الشائعة ، والتي تسمى بهذا الاسم لتمييزها عن النماذج "المتوازية" (مثل آلة الوصول العشوائي المتوازية ) [انظر فان إمدي بواس (1990)].
تعريف غير رسمي: نموذج البرنامج المخزن ذو الوصول العشوائي (RASP)
وصف موجز لجهاز RASP:
- إن جهاز RASP هو آلة تورينج عالمية (UTM) مبنية على هيكل ذاكرة الوصول العشوائي (RAM) الخاص بالآلة.
سيتذكر القارئ أن آلة تورينج العالمية (UTM) هي آلة تورينج مزودة بجدول تعليمات محدود الحالات "عالمي" قادر على تفسير أي "برنامج" سليم مكتوب على الشريط كسلسلة من خماسيات تورينج، ومن هنا تأتي عالميتها. بينما يتوقع نموذج UTM الكلاسيكي وجود خماسيات تورينج على شريطه، يمكن وضع أي مجموعة برامج يمكن تخيلها هناك، شريطة أن تتوقع آلة تورينج وجودها، شريطة أن يتمكن جدولها محدود الحالات من تفسيرها وتحويلها إلى الإجراء المطلوب. إلى جانب البرنامج، ستُطبع على الشريط بيانات/معاملات/أرقام الإدخال (عادةً إلى يمين البرنامج)، وفي النهاية بيانات/أرقام الإخراج (عادةً إلى يمين كليهما، أو مختلطة مع الإدخال، أو تحل محله). يجب على "المستخدم" وضع رأس آلة تورينج فوق التعليمات الأولى، ويجب وضع المدخلات في مكان وتنسيق محددين مناسبين لكل من البرنامج الموجود على الشريط وجدول تعليمات آلة الحالة المحدودة .
يحاكي برنامج RASP هذا التصميم: فهو يضع "البرنامج" و"البيانات" في الثقوب (السجلات). ولكن على عكس برنامج UTM، يقوم برنامج RASP بجلب تعليماته بشكل تسلسلي، إلا إذا أرسلها الاختبار الشرطي إلى مكان آخر.
نقطة لبس: مجموعتان من التعليمات : على عكس نموذج UTM، يحتوي نموذج RASP على مجموعتين من التعليمات - جدول تعليمات آلة الحالة (المترجم) و"البرنامج" الموجود في الثقوب. ولا يشترط أن تكون المجموعتان من نفس المصدر.
مثال على ذاكرة الوصول العشوائي (RAM) التي تعمل كوحدة معالجة الرسومات (RASP).
سيقوم المثال التالي لبرنامج بنقل محتويات السجل (الثقب) رقم 18 إلى السجل (الثقب) رقم 19، مع مسح محتويات رقم 18 في هذه العملية.
5:03 18 15 JZ 18 , 15 ؛ إذا كانت قيمة [18] تساوي صفرًا، انتقل إلى 15 لإنهاء البرنامج. 02 18 DEC 18 ؛ إنقاص قيمة [18]. 01 19 INC 19 ؛ زيادة قيمة [19]. 03 15 05 JZ 15 , 5 ؛ إذا كانت قيمة [15] تساوي صفرًا، انتقل إلى 5 لتكرار الحلقة (استخدم Halt لمحاكاة القفز غير المشروط). 15:00 H ؛ توقف.18: ن ؛ القيمة المصدر المراد نسخها 19:؛ وجهة النسخستكون تعليمات البرنامج المتوفرة في جهاز RASP هذا مجموعة بسيطة للحفاظ على المثال قصيرًا:
| تعليمات | ذاكري | إجراء على السجل "r" | الإجراء على سجل التعليمات الخاص بآلة الحالة المحدودة، IR |
|---|---|---|---|
| زيادة | شركة (ر) | [r] +1 → r | [IR] +1 → IR |
| تخفيض | DEC ( r ) | [r] -1 → r | [IR] +1 → IR |
| اقفز إذا كان الصفر | JZ ( r, z ) | لا أحد | إذا كان [r] = 0 فإن z → IR، وإلا فإن [IR] + 1 → IR |
| وقف | ح | لا أحد | [IR] → IR |
لتسهيل المثال، سنقوم بتزويد آلة الحالة الخاصة بـ RAM-as-RASP بالتعليمات الأولية المستمدة من نفس المجموعة، ولكن مع إضافة تعليمتين للنسخ غير المباشر:
- تعليمات آلة الحالة في ذاكرة الوصول العشوائي (RAM):
- { INC h; DEC h; JZ h,xxx; CPY ⟪ha a ⟫, ⟨ ha a ⟩ ; CPY ⟨ ha a ⟩ ,⟪ha a ⟫ }
أثناء قيام آلة الحالة في جهاز RASP بتفسير البرنامج الموجود في السجلات، ما الذي ستفعله آلة الحالة تحديدًا؟ سيسرد العمود الذي يحتوي على علامة التعجب ! إجراءات آلة الحالة بالتسلسل الزمني أثناء "تفسيرها" - أي تحويلها إلى إجراء - للبرنامج.
| جهاز كمبيوتر | الأشعة تحت الحمراء | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ثقب → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| البرنامج، المعلمات → | 5 | جيه زد | 18 | 15 | ديسمبر | 18 | شركة | 19 | جيه زد | 15 | 5 | ح | ن | ||||||
| البرنامج المشفر → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| تعليمات آلة الحالة ↓ | |||||||||||||||||||
| ! |
يقسم التقليد إجراءات آلة الحالة إلى مرحلتين رئيسيتين تُسميان الجلب والتنفيذ . وسنلاحظ لاحقًا وجود مراحل فرعية ضمن هاتين المرحلتين الرئيسيتين. لا يوجد اتفاق موحد؛ فكل نموذج يتطلب وصفًا دقيقًا خاصًا به.
مرحلة الجلب
تتمتع آلة الحالة بإمكانية الوصول إلى جميع السجلات، بشكل مباشر وغير مباشر. لذا فهي تعتمد السجل رقم 1 كعداد البرنامج (PC). يتمثل دور عداد البرنامج في "حفظ الموقع" في قائمة البرنامج؛ ولدى آلة الحالة سجل حالة خاص بها لاستخدامها الخاص.
عند بدء التشغيل، تتوقع آلة الحالة العثور على رقم في عداد البرنامج - أول "تعليمات البرنامج" في البرنامج (أي عند الرقم 5).
(بدون استخدام النسخ غير المباشر، تصبح مهمة إدخال تعليمة البرنامج المشار إليها في السجل رقم 2 شاقة بعض الشيء. ستقوم آلة الحالة بإنقاص قيمة السجل المشار إليه بشكل غير مباشر بينما تزيد قيمة السجل رقم 2 (الفارغ) بشكل مباشر. خلال مرحلة "التحليل"، ستستعيد محتويات السجل رقم 5 التي تم التضحية بها عن طريق التضحية بالعدد في السجل رقم 2.)
الهدف من الاستطراد المذكور أعلاه هو إظهار أن الحياة تصبح أسهل بكثير عندما يكون لدى آلة الحالة إمكانية الوصول إلى نوعين من النسخ غير المباشر:
- نسخ غير مباشر من i ومباشر إلى j: CPY ⟪h i ⟫, ⟨ h j ⟩
- نسخ مباشر من i وغير مباشر إلى j: CPY ⟨ h i ⟩ ,⟪h j ⟫
يوضح المثال التالي ما يحدث خلال مرحلة "جلب" البيانات في آلة الحالة. تُدرج عمليات آلة الحالة في العمود المسمى "تعليمات آلة الحالة ↓". لاحظ أنه في نهاية عملية الجلب، يحتوي السجل رقم 2 على القيمة العددية 3 لرمز العملية (" opcode ") للتعليمة الأولى JZ .
| جهاز كمبيوتر | PIR | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ثقب → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| البرنامج، المعلمات → | 5 | جيه زد | 18 | 15 | ديسمبر | 18 | شركة | 19 | جيه زد | 15 | 5 | ح | ن | ||||||||
| البرنامج المشفر → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||||
| خطوة | تعليمات آلة الحالة ↓ | ||||||||||||||||||||
| 1 | fetch_instr: | CPY ⟪1⟫, ⟨ 2 ⟩ | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن |
مرحلة التحليل
الآن بعد أن أصبح رقم تعليمات البرنامج (على سبيل المثال 3 = "JZ") موجودًا في السجل رقم 2 - وهو "سجل تعليمات البرنامج" PIR - تستمر آلة الحالة في إنقاص الرقم حتى يصبح سجل تعليمات البرنامج فارغًا:
إذا كان سجل التعليمات (IR) فارغًا قبل عملية الإنقاص، فإن تعليمة البرنامج ستكون 0 = HALT، وسينتقل الجهاز إلى روتين "HALT". بعد الإنقاص الأول، إذا كان السجل فارغًا، ستكون التعليمة INC، وسينتقل الجهاز إلى تعليمة "inc_routine". بعد الإنقاص الثاني، يمثل السجل الفارغ DEC، وسينتقل الجهاز إلى روتين "dec_routine". بعد الإنقاص الثالث، يكون السجل فارغًا بالفعل، مما يؤدي إلى الانتقال إلى روتين "JZ_routine". إذا كان هناك رقم غير متوقع لا يزال موجودًا في السجل، فسيكون الجهاز قد اكتشف خطأً ويمكنه التوقف (على سبيل المثال).
| جهاز كمبيوتر | الأشعة تحت الحمراء | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ثقب → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| البرنامج، المعلمات → | 5 | جيه زد | 18 | 15 | ديسمبر | 18 | شركة | 19 | جيه زد | 15 | 5 | ح | ن | ||||||||
| البرنامج المشفر → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||||
| تعليمات آلة الحالة ↓ | |||||||||||||||||||||
| CPY ⟪1⟫, ⟨ 2 ⟩ | 5 i | [3] | [3] | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||||
| JZ 2، توقف | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 19 | 5 | 0 | ن | |||||||
| 3 | 2 ديسمبر | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 4 | JZ 2,inc_routine: | 5 | 2 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 5 | 2 ديسمبر | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 6 | JZ 2,dec_routine | 5 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 7 | 2 ديسمبر | 5 | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 8 | JZ 2، روتين JZ | 5 | 0 ! | ||||||||||||||||||
| — | وقف: | وقف | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| — | inc_routine: | إلخ. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| — | dec_routine: | إلخ. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 9 | JZ_routine: | إلخ. | 5 | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن |
مرحلة التنفيذ، روتين JZ
الآن، تعرف آلة الحالة أي تعليمة برمجية يجب تنفيذها؛ بل إنها انتقلت إلى تسلسل تعليمات "JZ_routine". تحتوي تعليمة JZ على مُعاملين : (أ) رقم السجل المراد اختباره، و(ب) العنوان الذي يجب الانتقال إليه في حال نجاح الاختبار (أي إذا كان السجل فارغًا).
(أ) جلب المعامل - أي سجل يتم اختباره للتأكد من خلوه؟: على غرار مرحلة الجلب، تنقل آلة الحالة المحدودة محتويات السجل الذي يشير إليه عداد البرنامج (PC)، أي الفتحة رقم 6، إلى سجل البرنامج والتعليمات (PIR) رقم 2. ثم تستخدم محتويات السجل رقم 2 للإشارة إلى السجل المراد اختباره للتأكد من خلوه من الصفر، أي السجل رقم 18. تحتوي الفتحة رقم 18 على الرقم "n". لإجراء الاختبار، تستخدم آلة الحالة الآن محتويات سجل البرنامج والتعليمات (PIR) لنسخ محتويات السجل رقم 18 بشكل غير مباشر إلى سجل احتياطي، رقم 3. لذا، هناك احتمالان: (أ) السجل رقم 18 فارغ، (ب) السجل رقم 18 غير فارغ.
(ia): إذا كان السجل رقم 3 فارغًا، فإن آلة الحالة تقفز إلى (ii) جلب المعامل الثاني - جلب عنوان القفز.
(ب): إذا لم يكن السجل رقم 3 فارغًا، فيمكن لآلة الحالة تخطي (2) جلب المعامل الثاني. ببساطة، تقوم بزيادة عداد البرنامج بمقدار الضعف ثم تعود بشكل غير مشروط إلى مرحلة جلب التعليمات، حيث تجلب تعليمة البرنامج رقم 8 (DEC).
(ii) جلب المعامل - عنوان الانتقال . إذا كان السجل رقم 3 فارغًا، فإن آلة الحالة تستخدم عداد البرنامج (PC) لنسخ محتويات السجل الذي يشير إليه (رقم 8) بشكل غير مباشر إلى داخلها . الآن، يحمل عداد البرنامج عنوان الانتقال 15. ثم تعود آلة الحالة تلقائيًا إلى مرحلة جلب التعليمات، حيث تجلب تعليمة البرنامج رقم 15 (HALT).
| جهاز كمبيوتر | الأشعة تحت الحمراء | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ثقب → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| البرنامج، المعلمات → | 5 | جيه زد | 18 | 15 | ديسمبر | 18 | شركة | 19 | جيه زد | 15 | 5 | ح | ن | ||||||||
| البرنامج المشفر → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||||
| خطوة | تعليمات آلة الحالة ↓ | ||||||||||||||||||||
| 9 | روتين JZ | شركة 1 | [6] | 3 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 10 | CPY ⟪1⟫, ⟨ 2 ⟩ | 6 i | [18] | 3 | [18] | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||
| 11 | حفرة اختبار: | CPY ⟪2⟫, ⟨ 3 ⟩ | 6 | 18 i | [ن] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | [ن] | ||||
| 12 | حفرة اختبار: | JZ 3، قفزة | 6 | 18 i | [ن] | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| ن | ن | ||||||||||||||||||||
| 13 | no_jump: | شركة 1 | [7] | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 14 | شركة 1 | [8] | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 15 | J fetch_instr | 8 | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 1 | fetch_instr: | CPY ⟪1⟫, ⟨ 2 ⟩ | 8 i | [2] | ن | 3 | 18 | 15 | [2] | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 2 | تحليل: | إلخ. | |||||||||||||||||||
| 13 | القفز: | شركة 1 | [7] | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 14 | CPY ⟪1⟫, ⟨ 1 ⟩ | [15] | 18 | ن | 3 | 18 | [15] | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 15 | J fetch_instr | 15 | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 1 | fetch_instr: | CPY ⟪1⟫, ⟨ 2 ⟩ | 15 i | [0] | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | [0] | ن | ||||
| 2 | تحليل: | إلخ. |
تنفيذ المرحلة INC، DEC
يكمل ما يلي تفسير آلة الحالة لذاكرة الوصول العشوائي لتعليمات البرنامج، INC h و DEC h، وبالتالي يكمل عرض كيفية "انتحال" ذاكرة الوصول العشوائي لـ RASP:
- مجموعة تعليمات البرنامج المستهدف: { INC h; DEC h; JZ h,xxx, HALT }
بدون تعليمات آلة الحالة غير المباشرة INCi و DECi، لتنفيذ تعليمات برنامج INC و DEC ، يجب على آلة الحالة استخدام النسخ غير المباشر للحصول على محتويات السجل المشار إليه في السجل الاحتياطي رقم 3، ثم DEC أو INC فيه، ثم استخدام النسخ غير المباشر لإعادته إلى السجل المشار إليه.
| جهاز كمبيوتر | الأشعة تحت الحمراء | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ثقب → | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | ||
| البرنامج، المعلمات → | 5 | جيه زد | 18 | 15 | ديسمبر | 18 | شركة | 19 | جيه زد | 15 | 5 | ح | ن | ||||||||
| البرنامج المشفر → | 5 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||||||
| تعليمات آلة الحالة ↓ | |||||||||||||||||||||
| 15 | J fetch_instr | 8 | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 16 | fetch_instr: | CPY ⟪1⟫, ⟨ 2 ⟩ | 8 i | [2] | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 17 | تحليل: | JZ 2، توقف | 8 | 2 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 18 | 2 ديسمبر | 8 | [1] | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 19 | JZ 2، inc_routine: | 8 | 1 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 20 | 2 ديسمبر | 8 | [0] | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 21 | JZ 2، روتين فك الضغط: | 8 | 0 ! | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 22 | dec_routine: | شركة 1 | 9 | 0 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | ||||
| 23 | CPY ⟪1⟫, ⟨ 2 ⟩ | 9 i | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 24 | CPY ⟪2⟫, ⟨ 3 ⟩ | 9 | 18 i | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 25 | JZ 3,*+2 | 9 | 18 | ن | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 26 | 3 ديسمبر | 9 | 18 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن | |||||
| 27 | CPY ⟨ 3 ⟩ ,⟪2⟫ | 9 | 18 i | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 28 | شركة 1 | 10 | 18 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 29 | J fetch_instr | 10 | 18 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 30 | fetch_instr: | CPY ⟪1⟫, ⟨ 2 ⟩ | 10 i | 1 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | ||||
| 31 | تحليل: | JZ 2، توقف | 10 | 1 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | ||||
| 32 | 2 ديسمبر | 10 | 0 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 33 | JZ 2,inc_routine: | 10 | 0 ! | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 34 | inc_routine: | شركة 1 | 11 | 0 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | ||||
| 35 | CPY ⟪1⟫, ⟨ 2 ⟩ | 11 i | 19 | ن-1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | |||||
| 36 | CPY ⟪2⟫, ⟨ 3 ⟩ | 11 | 19 i | 0 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 0 | ||||
| 37 | شركة 3 | 11 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 0 | ||||
| 38 | CPY ⟨ 3 ⟩ ,⟪2⟫ | 11 | 19 i | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 1 | ||||
| 39 | شركة 1 | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 0 | ||||
| 40 | J fetch_instr | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 0 | ||||
| 41 | fetch_instr: | إلخ. | 12 | 19 | 1 | 3 | 18 | 15 | 2 | 18 | 1 | 19 | 3 | 15 | 5 | 0 | ن-1 | 0 |
تعليمات بديلة : على الرغم من أن العرض التوضيحي أسفر عن RASP بدائي مكون من أربع تعليمات فقط، إلا أنه يمكن للقارئ أن يتخيل كيف يمكن تنفيذ تعليمات إضافية مثل "ADD ⟨ h ⟩ " أو "MULT ⟨ h a ⟩ ,⟪h b >.
برامج RASP ذاتية التعديل
عندما تعمل ذاكرة الوصول العشوائي (RAM) كوحدة معالجة RASP، يتحقق شيء جديد: على عكس ذاكرة الوصول العشوائي، تتمتع وحدة المعالجة RASP بالقدرة على تعديل تعليمات برنامجها ذاتيًا (حيث تكون تعليمات آلة الحالة ثابتة وغير قابلة للتعديل من قِبل الآلة). وقد علّق كوك-ريكهاو (1971) (ص 75) على هذا في وصفهما لنموذج RASP، وكذلك فعل هارتمانيس (1971) (ص 239 وما بعدها).
يمكن العثور على وصف مبكر لهذا المفهوم في كتاب غولدستين-فون نيومان (1946):
- "نحن بحاجة إلى أمر [تعليمات] يمكنه استبدال رقم في أمر معين ... وبواسطة هذا الأمر، يمكن إدخال نتائج عملية حسابية في التعليمات التي تحكم تلك العملية الحسابية أو عملية حسابية مختلفة" (ص 93).
تتيح هذه القدرة ما يلي:
- الروتينات الفرعية - يقوم الروتين المُستدعي (أو ربما الروتين الفرعي) بتخزين عنوان الإرجاع "return_address" في الأمر الأخير للروتين الفرعي، أي "JMP return_address"
- ما يسمى بجداول القفز
- كود ذاتي التعديل
مجموعة تعليمات برنامج RASP من تأليف كوك وريكهاو (1973)
في ورقة بحثية مؤثرة، قام ستيفن أ. كوك وروبرت أ. ريكهاو بتعريف نسختهما من RASP:
- "إن آلة الوصول العشوائي للبرامج المخزنة (RASP) الموصوفة هنا تشبه آلة RASP التي وصفها هارتمانيس [1971]" (ص 74).
كان هدفهم مقارنة أوقات التنفيذ للنماذج المختلفة: RAM و RASP وآلة تورينج متعددة الأشرطة لاستخدامها في نظرية تحليل التعقيد .
السمة البارزة لنموذج RASP الخاص بهم هي عدم وجود أي بند يسمح بتعليمات البرنامج غير المباشرة (انظر مناقشتهم في الصفحة 75). ويتحقق ذلك من خلال إلزام البرنامج بتعديل نفسه: فإذا لزم الأمر، يمكن للتعليمات تعديل "المعامل" (مصطلحهم، أي "المُعامل") لتعليمات معينة. وقد صمموا نموذجهم بحيث تستخدم كل "تعليمات" سجلين متتاليين، أحدهما لرمز العملية (مصطلحهم) والآخر للمعامل "إما عنوان أو ثابت عددي".
سجلات وحدة المعالجة RASP الخاصة بهم غير محدودة السعة والعدد؛ وكذلك الحال بالنسبة للمراكم AC وعداد التعليمات IC. مجموعة التعليمات هي كالتالي:
| عملية | ذاكري | رمز العملية | وصف |
|---|---|---|---|
| ثابت الحمل | LOD، k | 1 | ضع قيمة ثابتة k في المُراكم |
| يضيف | أضف، ج | 2 | أضف محتويات السجل j إلى المُراكم |
| طرح | SUB, j | 3 | اطرح محتويات السجل j من المُراكم |
| محل | STO، j | 4 | انسخ محتويات المُراكم إلى السجل j |
| تفرع على المجمع الموجب | بي بي إيه، xxx | 5 | إذا كانت محتويات المُراكم أكبر من صفر، فانتقل إلى xxx، وإلا فانتقل إلى التعليمات التالية. |
| يقرأ | RD, j | 6 | المدخل التالي سجل c j |
| مطبعة | PRI, j | 7 | إخراج محتويات السجل j |
| وقف | HLT | أي عدد صحيح آخر - أو + | قف |
مراجع
غالبًا ما يتم عرض كل من آلات الوصول العشوائي (RAM) وآلات التسجيل (RASP) معًا في نفس المقالة. وقد تم نسخ هذه المعلومات من مقالة "آلة الوصول العشوائي" ؛ وباستثناءات قليلة، فإن هذه المراجع هي نفسها الموجودة في مقالة "آلة التسجيل" .
- جورج بولوس ، جون ب. بورغيس ، ريتشارد جيفري (2002)، الحوسبة والمنطق: الطبعة الرابعة ، مطبعة جامعة كامبريدج، كامبريدج، إنجلترا. خضع نص بولوس-جيفري الأصلي لمراجعة شاملة من قِبل بورغيس، وهو أكثر تقدماً من مجرد كتاب تمهيدي. تم تطوير نموذج "آلة المعداد" بشكل موسع في الفصل الخامس " حوسبة المعداد "؛ وهو أحد ثلاثة نماذج تمت معالجتها ومقارنتها بشكل موسع - آلة تورينج (لا تزال في شكل بولوس الأصلي المكون من 4 عناصر) ونموذجان للاستدعاء الذاتي.
- آرثر بيركس ، وهيرمان غولدستاين ، وجون فون نيومان (1946)، مناقشة تمهيدية للتصميم المنطقي لجهاز حاسوب إلكتروني ، أعيد طبعه في الصفحات 92 وما بعدها في كتاب غوردون بيل وآلان نيويل (1971)، هياكل الحاسوب: قراءات وأمثلة ، شركة ماكجرو هيل للنشر، نيويورك. ISBN 0-07-004357-4 .
- ستيفن أ. كوك وروبرت أ. ريكهاو (1972)، آلات الوصول العشوائي المحدودة زمنيا ، مجلة علوم أنظمة الحاسوب 7 (1973)، 354-375.
- مارتن ديفيس (1958)، قابلية الحساب وعدم قابلية الحل ، شركة ماكجرو هيل للنشر، نيويورك.
- كالفن إلجوت وأبراهام روبنسون (1964)، آلات البرامج المخزنة ذات الوصول العشوائي، نهج للغات البرمجة ، مجلة رابطة آلات الحوسبة، المجلد 11، العدد 4 (أكتوبر 1964)، ص 365-399.
- J. Hartmanis (1971), "التعقيد الحسابي لآلات البرامج المخزنة ذات الوصول العشوائي"، نظرية الأنظمة الرياضية 5، 3 (1971) ص 232-245.
- جون هوبكروفت ، جيفري أولمان (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة ، الطبعة الأولى، ريدينغ، ماساتشوستس: أديسون-ويسلي. ISBN 0-201-02988-Xكتاب صعب يتمحور حول قضايا التفسير الآلي لـ "اللغات"، واكتمال NP، وما إلى ذلك.
- ستيفن كلين (1952)، مقدمة في ما وراء الرياضيات ، دار نشر نورث هولاند، أمستردام، هولندا. رقم ISBN 0-7204-2103-9.
- دونالد كنوث (1968)، فن برمجة الحاسوب ، الطبعة الثانية 1973، أديسون-ويسلي، ريدينغ، ماساتشوستس. انظر الصفحات 462-463 حيث يُعرّف "نوعًا جديدًا من الآلات المجردة أو "الأوتوماتون" التي تتعامل مع الهياكل المرتبطة".
- يواكيم لامبيك (1961، تاريخ الاستلام 15 يونيو 1961)، كيفية برمجة عداد لانهائي ، النشرة الرياضية، المجلد 4، العدد 3، سبتمبر 1961، الصفحات 295-302. في الملحق الثاني، يقترح لامبيك "تعريفًا رسميًا لـ'البرنامج'". ويشير إلى ميلزاك (1961) وكلين (1952)، مقدمة في ما وراء الرياضيات .
- ز. أ. ميلزاك (1961، تاريخ الاستلام 15 مايو 1961)، مدخل حسابي غير رسمي للحوسبة والحساب ، النشرة الرياضية الكندية ، المجلد 4، العدد 3، سبتمبر 1961، الصفحات 279-293. لم يذكر ميلزاك أي مراجع، لكنه أقرّ بـ"فائدة المحادثات مع الدكاترة ر. هامينغ ، ود. ماكلروي ، وف . فيسوتسكي من مختبرات بيل للهواتف ، ومع الدكتور هـ. وانغ من جامعة أكسفورد" .
- مارفن مينسكي (1961). "عدم قابلية حل مسألة بوست المتعلقة بـ'الوسم' بشكل متكرر ومواضيع أخرى في نظرية آلات تورينج". حوليات الرياضيات . 74 (3): 437-455 . doi : 10.2307/1970290 . JSTOR 1970290 .
- مارفن مينسكي (1967). الحوسبة: الآلات المحدودة واللامحدودة ( الطبعة الأولى). إنجلوود كليفس، نيوجيرسي: برنتيس هول، إنك. ISBN 0-13-165449-7.انظر تحديدًا الفصل 11: نماذج مشابهة للحواسيب الرقمية ، والفصل 14: أسس بسيطة جدًا للحوسبة . في الفصل الأول، يُعرّف "آلات البرمجة"، وفي الفصل الثاني، يناقش "آلات البرمجة الشاملة ذات سجلين" و"...ذات سجل واحد"، إلخ.
- حصل جون سي. شيبردسون وإتش إي ستورجيس (1961) على جائزة في ديسمبر 1961 عن بحثهما المنشور في مجلة جمعية آلات الحوسبة (JACM) 10:217-255، 1963. يُعد هذا البحث مرجعًا قيّمًا للغاية. وفي الملحق (أ)، يستشهد المؤلفان بأربعة مراجع أخرى فيما يتعلق بـ "الحد الأدنى من التعليمات المستخدمة في 4.1: مقارنة مع أنظمة مماثلة".
- كافينجست، هاينز، Eine Abstrakte Programmgesteuerte Rechenmaschine' ، Zeitschrift fur mathematische Logik und Grundlagen der Mathematik: 5 (1959)، 366-379.
- إرشوف، أ.ب. حول خوارزميات المؤثرات ، (بالروسية) دوك. أكاد. ناوك 122 (1958)، 967-970. الترجمة الإنجليزية، أوتومات. إكسبريس 1 (1959)، 20-23.
- بيتر، مخطط الرسم البياني والوظائف المتكررة ، جدل 12 (1958)، 373.
- Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Math.-Phys. Semsterberichte (Göttingen) 4 (1954), 42-53.
- Arnold Schönhage (1980), Storage Modification Machines, Society for Industrial and Applied Mathematics, SIAM J. Comput. Vol. 9, No. 3, August 1980. Wherein Schōnhage shows the equivalence of his SMM with the "successor RAM" (Random Access Machine), etc. resp. Storage Modification Machines, in Theoretical Computer Science (1979), pp. 36–37
- Peter van Emde Boas, Machine Models and Simulations pp. 3–66, appearing in: Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (volume A). QA 76.H279 1990.
- van Emde Boas' treatment of SMMs appears on pp. 32-35. This treatment clarifies Schōnhage 1980 -- it closely follows but expands slightly the Schōnhage treatment. Both references may be needed for effective understanding.
- Hao Wang (1957), A Variant to Turing's Theory of Computing Machines, JACM (Journal of the Association for Computing Machinery) 4; 63–92. Presented at the meeting of the Association, June 23–25, 1954.
- Register machines