موضوع مقاله: ماشین برنامه ذخیره‌شده با دسترسی تصادفی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # ماشین برنامه ذخیره‌شده با دسترسی تصادفی | مقدمه: در علوم نظری کامپیوتر، مدل ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (RASP) یک ماشین انتزاعی است که برای اهداف توسعهٔ الگوریتم و نظریهٔ پیچیدگی الگوریتم مورد استفاده قرار می‌گیرد. | ## بخش 1: ماشین برنامه ذخیره‌شده با دسترسی تصادفی | رجیسترها نامحدود (دارای ظرفیت بینهایت) هستند؛ محدود بودن تعداد رجیسترها، به مدل بستگی دارد؛ بنابراین نسبت RASP به RAM، مانند ماشین تورینگ جهانی به ماشین تورینگ است. RASP نمونه‌ای از معماری فون نویمان است، درحالیکه RAM نمونه‌ای از معماری هاروارد می‌باشد. اما برخلاف کامپیوترهای واقعی، مدل RASP معمولاً دارای مجموعهٔ ساختاری بسیار ساده‌ای است که تا حد زیادی از CISC و حتی پردازشگرهای RISC به صورت ساده‌ترین "حرکات" حسابی و رجیستر به رجیستر، و همچنین فرمان‌های "آزمون/جهش" ساده شده‌اند. برخی مدل‌ها، مانند یک انباشتگر، دارای رجیسترهای کمی بیشتر هستند.RASP به همراه ماشین رجیستر، RAM و ماشین اشاره‌گر، چهار مدل ماشین متوالی رایج را ایجاد می‌کند، که جهت تمایز آن‌ها از مدل‌های "موازی" (مثلاً، ماشین دسترسی تصادفی موازی) به این نام خوانده می‌شوند (van Emde Boas (1990 . خواننده به یاد خواهد آورد که UTM یک ماشینگ تورینگ با یک فهرست فرمان‌های "جهانی" حالت محدود است که می‌تواند هرگونه "برنامه"ی به خوبی شکل‌گرفته و نوشته شده بر روی یک نوار ضبط به عنوان یک رشته تورینگ ۵تایی، و از اینرو عمومیت آن، را تفسیر نماید. در حالیکه انتظار می‌رود تا مدل UTM، تورینگ ۵تایی را بر روی نوار خود بیابد، هر مجموعه برنامهٔ قابل تصور را، با توجه به اینکه ماشین تورینگ انتظار دارد که آن‌هارا بیابد، می‌توان در آنجا قرار داد، با توجه به اینکه فهرست حالت محدود آن می‌تواند آن مجموعه برنامه را تفسیر نموده و آن‌ها را به عمل دلخواه تبدیل نماید. در کنار برنامه، سایر موارد چاپ شده بر روی نوار، داده-ها/مولفه‌ها/اعداد ورودی (معمولاً در سمت راست برنامه)، و در نهایت داده‌ها/اعداد خروجی (معمولاً در سمت راست هر دوی آن‌ها، یا آمیخته با ورودی‌ها، یا جایگزین آن‌ها) خواهند بود. "کاربر" باید ابتدای ماشین تورینگ را بالاتر از اولین فرمان قرار دهد، و ورودی‌ها باید در یک محل خاص و قالبی مناسب هم برای برنامهٔ روی نوار و هم برای فهرست فرمان‌های ماشین حالت محدود جای دهد. RASP از این فرمان تقلید می‌کند: "برنامه" و "داده‌هاً را درون حفره‌ها (رجیسترها) جای می‌دهد. اما برخلاف UTM، RSAP اقدام به "واکشی" فرمان‌هایش به صورت ترتیبی می‌کند، مگر اینکه آزمون شرطی آن‌ها را به جای دیگری ارسال نماید. نکتهٔ تردید دو مجموعه فرمان: مدل RASP، بر خلاف UTM، دارای دو مجموعه فرمان است؛ فهرست فرمان‌های حالت ماشین ("مفسر") و "برنامه" درون حفره‌ها. مثالی از یک RAM به عنوان یک RASP نمونه برنامهٔ زیر مقادیر رجیستر (حفره) #۱۸ را به رجیستر (حفره) #۱۹ انتقال داده و مقادیر #۱۸ را در این فرایند پاک خواهد نمود. به‌طور مرسوم، اعمال ماشینِ حالت به دو "مرحله"ی اصلی به نام‌های واکشی و اجرا تقسیم می‌کند. | ## بخش 2: ماشین برنامه ذخیره‌شده با دسترسی تصادفی | مرحلهٔ واکشی ماشین حالت، هم مستقیم و هم غیرمستقیم، به تمام رجیسترها دسترسی دارد؛ بنابراین #۱ را به عنوان "شمارشگر برنامه" (PC) اتخاذ می‌کند. نقش شمارشگر برنامه "حفظ موقعیت" در فهرست برنامه خواهد بود؛ ماشین حالت، برای کاربرد اختصاصی‌اش، دارای رجیستر حالتِ منحصربفرد خود است. به محض شروع، ماشین حالت منتظر یافتن یک شماره درون PC می‌ماند، یعنی اولین "فرمان برنامه‌ای" درون برنامه (مثلاً در #۵). (بدون استفاده از کپی‌های غیرمستقیم، وظیفهٔ رساندن فرمان برنامه‌ایِ مورد اشاره به #۲ کمی دشوار است. ماشینِ حالت، رجیستر مورد اشاره را به‌طور غیرمستقیم کاهش خواهد داد، درحالیکه رجیستر (خالیِ) #۲ را افزایش می‌دهد. در طول مرحلهٔ "تجزیه"، مقادیر ارائه شدهٔ #۵ را بوسیلهٔ قربانی کردن شمارهٔ درون #۲، ترمیم خواهد نمود) هدف از نکتهٔ انحرافی بالا این است که نشان دهیم، زمانی‌که ماشین حالت به دو نوع کپی غیرمستقیم دسترسی دارد، کارها آسان‌تر خواهند بود: کپی غیرمستقیم از i و مستقیم به j: CPY <<hi>>,<hj> کپی مستقیم از i و غیرمستقیم به j: CPY <hi>,<<hj>> مثال بعدی نشان می‌دهد که در طی مرحلهٔ "واکشی" ماشینِ حالت، چه اتفاقی رخ می‌دهد. عملیات‌های ماشینِ حالت در زیر ستونی با عنوان "فرمان‌های ماشینِ حالت ↓ " فهرست شده‌اند. مشاهده کنید که در انتهای واکشی، رجیستر #۲ حاوی مقدار عددی ۳ از "کد عملیاتی" ("opcode") فرمان اول JZ است. فرمان JZ دارای دو عملوند است، (i) رقم رجیستر جهت آزمون، و (ii) آدرسی که در صورت موفقیت‌آمیز بودن آزمون (خالی بودن حفره) باید به آن مراجعه نمود. : مشابه مرحلهٔ واکشی، ماشینِ حالت محدود، مقادیر رجیستری را که توسط PC به آن اشاره شده، مثلاً حفرهٔ #۶، را به درون رجیستر فرمان برنامه‌ایِ #۲ منتقل می‌کند. سپس از مقادیر رجیستر #۲ برای اشاره به رجیستر جهت آزمایش شدن برای صفر، مثلاً رجیستر #۱۸، استفاده می‌کند. اکنون برای انجام آزمایش، ماشینِ حالت از مقادیر PIR جهت کپی غیرمستقیم رجیستر #۱۸ درون یک رجیستر یدکی، #۳، استفاده می‌کند؛ بنابراین دو احتمال وجود دارد، (ia) رجیستر #۱۸ خالی است، (ib) رجیستر #۱۸ خالی نیست. (ia) در صورتی‌که رجیستر #۳ خالی باشد، ماشینِ حالت به (ii) دومین واکشی عملوند، جهش می‌یابد (واکشی آدرس جهش به). | ## بخش 3: ماشین برنامه ذخیره‌شده با دسترسی تصادفی | (ib) در صورتی‌که رجیستر #۳ خالی نباشد، ماشین حالت می‌تواند (ii) دومین واکشی عملوند را نادیده بگیرد. این کار به سادگی PC را دو بار کاهش می‌دهد و سپس بدون قید و شرط به مرحلهٔ واکشیِ فرمان، یعنی جاییکه فرمان برنامه‌ای #۸ را واکشی می‌کند (DEC)، بازمی‌گردد. اگر رجیستر #۳ خالی باشد، ماشینِ حالت اقدام به استفاده از PC جهت کپی غیرمستقیم مقادیر رجیستری که به آن اشاره دارد (#۸) به درون خود، می‌کند. سپس ماشینِ حالت بدون قید و شرط به مرحلهٔ واکشی فرمان بازمی‌گردد، یعنی جاییکه فرمان برنامه‌ای #۱۵ را واکشی می‌نماید (HALT). ۱۲ ۱۹ ۱ ۳ ۱۸ ۱۵ ۲ ۱۸ ۱ ۱۹ ۳ ۱۵ ۵ ۰ n-1 ۰ فرمان‌های جایگزین: اگرچه این نمایش به یک RASP اولیه از تنها چهار فرمان منجر شد، خواننده باید حدس بزند که یک فرمان اضافی مانند "ADD <h>" یا "MULT <ha>,<<hb>"، چگونه ممکن است انجام شود. برنامه‌های RASP خود اصلاح زمانیکه یک RAM به عنوان یک RASP عمل می‌کند، مورد جدیدی به دست می‌آید: RASP، بر خلاف RAM، ظرفیت خود اصلاحی فرمان‌های برنامه‌ای خود را دارد (فرمان‌های ماشینِ حالت ثابت بوده و غیرقابل تعدیل توسط ماشین هستند). تعریفی اولیه از این مفهوم را می‌توان در گلدشتین-فون نویمان (Goldstine-von Neumann) (1946) یافت: "ما به دستوری (فرمانی) نیاز داریم که بتواند یک عدد را درون یک ردیف مشخص جایگزین نماید… با استفاده از چنین دستوری، نتایج یک محاسبه را می‌توان به صورت فرمان‌هایی نشان داد که این محاسبه یا یک محاسبهٔ دیگر را کنترل می‌کنند" (صفحه ۹۳). رکهو، تفسیر خود از یک RASP را در یک مقالهٔ مؤثر، چنین شرح می‌دهند: "ماشین برنامهٔ ذخیره شده با دسترسی تصادفی (RASP) شرح داده شده در اینجا، مشابه RASPهای شرح داده شده توسط هارتمانیس می‌باشد" (صفحه ۷۴). هدف آن‌ها، مقایسهٔ زمان‌های اجرایی مدل‌های مختلف از جمله RAM، RASP و ماشین تورینگ چند نواری، جهت استفاده در نظریهٔ تحلیل پیچیدگی بود. ویژگی چشمگیر مدل RASP آن‌ها، بی‌قیدی برای فرمان‌های برنامه‌ای غیرمستقیم است (به بحث آن-ها در صفحه ۷۵ رجوع شود). آن‌ها با ملزم نمودن یک برنامه جهت اصلاح خود، به این نتیجه رسیدند: در صورت لزوم، یک فرمان می‌تواند "مولفه"ی (به قول آن‌ها، مثلاً "عملوند") یک فرمان خاص را اصلاح نماید. آن‌ها مدل خود را به گونه‌ای طراحی کردند که هر "فرمان" از دو رجیستر متوالی استفاده نماید، یکی برای "کد عملیاتی" (به قول آن‌ها) و مؤلفهٔ "یک آدرس یا یک ثابت اینتجر". | ## جمع‌بندی | رجیسترهای RASP آن‌ها از لحاظ ظرفیت و از لحاظ تعداد، نامحدود هستند؛ به همین ترتیب، انباشتگر آن-ها یعنی AC، و شمارندهٔ فرمان، IC، نیز نامحدود هستند.