Tasodifiy kirish uchun saqlanadigan dastur mashinasi - Random-access stored-program machine

Ushbu maqola umumiy ro'yxatini o'z ichiga oladi ma'lumotnomalar, lekin bu asosan tasdiqlanmagan bo'lib qolmoqda, chunki unga mos keladigan etishmayapti satrda keltirilgan. Iltimos yordam bering takomillashtirish tomonidan ushbu maqola tanishtirish aniqroq iqtiboslar. (Noyabr 2018) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Yilda nazariy informatika The tasodifiy kirish uchun saqlangan dastur (RASP) mashina modeli an mavhum mashina maqsadlari uchun ishlatiladi algoritm rivojlanish va algoritm murakkabligi nazariyasi.

RASP a tasodifiy kirish mashinasi (RAM), RAMdan farqli o'laroq, unga ega dastur uning "registrlarida" kiritilishi bilan birga. Registrlar cheksizdir (imkoniyatlari bo'yicha cheksiz); registrlar soni cheklangan bo'ladimi, modelga xosdir. Shunday qilib, RASP RAMga sifatida Universal Turing mashinasi ga Turing mashinasi. RASP ga misol fon Neyman me'morchiligi RAM esa .ning misoli Garvard me'morchiligi.

RASP barcha mavhum modellardan umumiy tushunchaga eng yaqinidir kompyuter. Ammo haqiqiy kompyuterlardan farqli o'laroq, RASP modeli odatda juda oddiy ko'rsatmalar to'plamiga ega bo'lib, ularnikidan ancha kamaygan CISC va hatto RISC protsessorlar eng oddiy arifmetik, ro'yxatdan o'tish uchun "harakatlanish" va "sinov / sakrash" ko'rsatmalariga. Ba'zi modellarda an kabi bir nechta qo'shimcha registrlar mavjud akkumulyator.

Bilan birga ro'yxatdan o'tish mashinasi, RAM va ko'rsatkich mashinasi RASP to'rtta umumiy narsani tashkil qiladi ketma-ket mashina modellari, ularni "parallel" modellardan ajratish uchun chaqirdi (masalan.) parallel tasodifiy kirish mashinasi ) [qarang van Emde Boas (1990)].

Norasmiy ta'rif: tasodifiy kirish uchun saqlangan dastur modeli (RASP)

RASP ning qisqacha tavsifi:

RASP a universal Turing mashinasi (UTM) a ga asoslangan tasodifiy kirish mashinasi RAM shassisi.

O'quvchi UTM ning a ekanligini eslaydi Turing mashinasi lentada yozilgan har qanday yaxshi shakllangan "dastur" ni Turing 5-karra qatori sifatida izohlashi mumkin bo'lgan ko'rsatmalarning "universal" cheklangan holat jadvali bilan, shuning uchun uning universalligi. Klassik UTM modeli o'z lentasida Turing 5-tupleni topishni kutayotgan bo'lsa-da, Turing mashinasi ularni topishni kutayotganligini hisobga olib, har qanday dasturiy ta'minotni tasavvur qilish mumkin, chunki uning cheklangan holat jadvali ularni sharhlashi va o'zgartirishi mumkin. kerakli harakat. Dastur bilan bir qatorda lentada chop etilgan ma'lumotlar / parametrlar / raqamlar (odatda dasturning o'ng tomonida) va natijada chiqadigan ma'lumotlar / raqamlar (odatda ikkalasining o'ng tomonida yoki kirish bilan aralashtiriladi yoki uni almashtiradi) bo'ladi. ). "Foydalanuvchi" Tyuring mashinasining boshini birinchi ko'rsatma ustiga qo'yishi kerak va kirish belgilangan joyda va formatdagi lentada ham, cheklangan holatdagi mashinaning ko'rsatmalar jadvalida ham joylashtirilgan bo'lishi kerak.

RASP ushbu qurilishni taqlid qiladi: u "dastur" va "ma'lumotlarni" teshiklarga (registrlarga) joylashtiradi. Ammo UTM dan farqli o'laroq, RASP o'z ko'rsatmalarini ketma-ket ravishda "olib kelishga" kirishadi, agar shartli test boshqa joyga yubormasa.

Chalkashlik nuqtasi: ikkita ko'rsatma to'plami: UTM dan farqli o'laroq, RASP modeli ikkita ko'rsatmalar to'plamiga ega - ko'rsatmalarning davlat mashina jadvali ("tarjimon") va teshiklarda "dastur". Ikkala to'plamni bir xil to'plamdan olish shart emas.

RASP sifatida ishlaydigan RAMga misol

Quyidagi dastur namunasi # 18 registr tarkibini # teshik (# teshik) # 19 ga ko'chiradi va bu jarayonda # 18 tarkibini o'chirib tashlaydi.

    5: 03 18 15    JZ 18,15       ; agar [18] nolga teng bo'lsa, dasturni tugatish uchun 15 ga sakrab chiqing       02 18       DEK 18         ; Kamaytirish [18]       01 19       INC 19         ; O'sish [19]       03 15 05    JZ 15, 5       ; Agar [15] nol bo'lsa, tsiklni takrorlash uchun 5 ga sakrab o'ting (so'zsiz sakrashni simulyatsiya qilish uchun Halt dan foydalaning)   15: 00          H              ; Salom   18:  n                         ; Nusxalash uchun manba qiymati   19:                            ; Nusxalash uchun mo'ljallangan joy

The dastur- ushbu RASP mashinasida mavjud bo'lgan ko'rsatmalar qisqa misolni saqlash uchun oddiy to'plam bo'ladi:

Misolni engillashtirish uchun biz jihozlaymiz davlat mashinasi RAM-as-RASP ning bir xil to'plamdan olingan ibtidoiy ko'rsatmalar bilan, lekin ikkita bilvosita nusxa olish ko'rsatmalari bilan to'ldirilgan:

RAM holatidagi mashinaning ko'rsatmalari:

{INC h; Soat dek; JZ h, xxx; CPY << h_a>>, a>; CPY a>, << h_a>> }

RASP mashinasining holat mashinasi registrlardagi dasturni talqin qilar ekan, davlat mashinasi aniq nima qiladi? Undov belgisini o'z ichiga olgan ustun! davlat mashinasining harakatlarini vaqt ketma-ketligi bilan ro'yxatlaydi, chunki u "sharhlaydi" - harakatga aylantiradi - dastur:

An'ana davlat-mashina harakatlarini ikkita asosiy "faza" ga ajratadi Qabul qiling va Ijro eting. Quyida biz ushbu ikki asosiy bosqichda "kichik fazalar" mavjudligini kuzatamiz. Kelishilgan konventsiya yo'q; har bir model o'zining aniq tavsifini talab qiladi.

Fetch bosqichi

Davlat mashinasi to'g'ridan-to'g'ri va bilvosita barcha registrlarga kirish huquqiga ega. Shunday qilib, u №1-ni "dastur hisoblagichi" sifatida qabul qiladi shaxsiy kompyuter. Ning roli dastur hisoblagich dastur ro'yxatidagi "joyni saqlab qolish"; davlat mashinasi shaxsiy foydalanish uchun o'z davlat reestriga ega.

Ishga tushgandan so'ng, davlat mashinasi kompyuterda raqamni topishni kutadi - dasturdagi birinchi "Dastur-yo'riq" (ya'ni # 5 da).

(Bevosita COPY-lardan foydalanmasdan, yo'naltirilgan dastur-yo'riqnomani # 2-ga kiritish vazifasi juda qiyin. Davlat mashinasi bilvosita to'g'ridan-to'g'ri (bo'sh) registrni ko'paytirganda, ishora qilingan registrni kamaytiradi. "ayrıştırma" bosqichi, # 2-sonli sonni qurbon qilish orqali # 5 ning qurbon qilingan tarkibini tiklaydi.)

Yuqoridagi aylanib o'tishning maqsadi shundan iboratki, davlat mashinasi ikki xil bilvosita nusxaga ega bo'lganda hayot ancha osonlashadi:

• bilvosita i dan nusxa ko'chiring va to'g'ridan-to'g'ri j: CPY << h_men>>, j>
• to'g'ridan-to'g'ri i dan bilvosita j ga ko'chiring: CPY men>, << h_j>>

Quyidagi misol davlat-mashinaning "olish" bosqichida nima bo'lishini ko'rsatadi. Davlat-mashinaning operatsiyalari "Davlat mashinalariga ko'rsatma ↓" ustunida keltirilgan. Yuklab olish oxirida # 2 registrda birinchi ko'rsatmaning "operatsion kodi" ("opcode") ning 3-qiymati borligini kuzating. JZ:

Sinov bosqichi

Endi dastur ko'rsatmasining raqami (masalan, 3 = "JZ") # 2 registrda - "Dastur-yo'riq reestri" PIRda - davlat mashinasi IQ bo'shatilgunga qadar sonni kamaytiradi:

Agar IQ kamayishdan oldin bo'sh bo'lsa, unda dastur ko'rsatmasi 0 = HALT bo'ladi va mashina "HALT" tartibiga o'tib ketadi. Birinchi pasayishdan so'ng, teshik bo'sh bo'lsa, ko'rsatma INC bo'ladi va mashina "inc_routine" buyrug'iga o'tib ketadi. Ikkinchi pasayishdan so'ng, bo'sh IR DEC ni ifodalaydi va mashina "dec_routine" ga o'tib ketadi. Uchinchi pasayishdan so'ng, IR haqiqatan ham bo'sh va bu "JZ_routine" tartibiga o'tishga olib keladi. Agar kutilmagan raqam hali ham IQda bo'lsa, unda mashina xatolikni aniqlagan bo'lar edi va HALT (masalan).

JZ_routine bosqichini bajaring

Endi davlat mashinasi qanday dastur-ko'rsatmani bajarilishini biladi; chindan ham u "JZ_routine" ko'rsatmalar ketma-ketligiga o'tdi. JZ yo'riqnomasida 2 ta operand mavjud - (i) sinov uchun registrning raqami va (ii) agar test muvaffaqiyatli bo'lsa (teshik bo'sh bo'lsa) boradigan manzil.

(i) Operandni olish - bo'shni tekshirish uchun qaysi ro'yxatdan o'tish?: Fetch bosqichiga o'xshash, cheklangan holat mashinasi kompyuter tomonidan ko'rsatilgan registr tarkibini, ya'ni №6 teshikni PIR № 2 dastur-yo'riq registriga ko'chiradi. Keyin u # 2 registrining tarkibidan foydalanib, nolga, ya'ni # 18 registrga tekshiriladigan registrga ishora qiladi. # 18 teshik "n" raqamini o'z ichiga oladi. Sinovni amalga oshirish uchun endi davlat mashinasi PIR tarkibini bilvosita ravishda # 18 registr tarkibini # 3 zaxira registriga ko'chirish uchun ishlatadi. Shunday qilib, ikkita voqea mavjud (ia), registr # 18 bo'sh, (ib) registr # 18 bo'sh emas.

(ia): №3 registr bo'sh bo'lsa, davlat mashinasi (ii) Second operand fetch - sakrash manzilini olib keladi.

(ib): Agar №3 registr bo'sh bo'lmasa, davlat mashinasi (ii) Ikkinchi operandni olib o'tishni o'tkazib yuborishi mumkin. U shunchaki kompyuterni ikki baravar ko'paytiradi va keyin so'zsiz buyruqni olish bosqichiga o'tib, u erda # 8 dastur buyrug'ini oladi (DEC).

(ii) Operandni olish - manzilga o'tish. Agar №3 registr bo'sh bo'lsa, davlat mashinasi kompyuterni bilvosita (# 8) ko'rsatgan registr tarkibini nusxalash uchun ishlatadi. o'zi. Endi kompyuter 15-sonli o'tish manzilini ushlab turibdi. Keyin davlat mashinasi so'zsiz buyruqni qabul qilish bosqichiga qaytadi, u erda №15 dastur-ko'rsatmasi olinadi (HALT).

INC, DEC bosqichini bajaring

Quyidagilar RAMning INC h, DEC h dasturiy ko'rsatmalarini davlat-mashinada talqin qilishini yakunlaydi va shu bilan operativ xotira qanday qilib RASP-ni "taqlid qilishi" mumkinligini namoyish etadi:

Maqsadli dastur ko'rsatmalari to'plami: {INC h; Soat dek; JZ h, xxx, HALT}

INCi va DECi davlat-mashinalarining bilvosita ko'rsatmalarisiz INC va DECni bajarish dastur- yo'riqnomada davlat mashinasi bilvosita nusxasini ishlatib, ro'yxatdan o'tish uchun tarkibini №3, DEC yoki INC zaxira reestriga kiritishi kerak, so'ngra bilvosita nusxasini uni ko'rsatgichga qaytarib yuborish uchun ishlatishi kerak.

Muqobil ko'rsatmalar: Namoyish natijasida faqat to'rtta yo'riqnomadan iborat ibtidoiy RASP paydo bo'lgan bo'lsa ham, o'quvchi "ADD " yoki "MULT a>, << h_b> amalga oshirilishi mumkin.

O'z-o'zini o'zgartirish RASP dasturlari

Operativ xotira RASP vazifasini bajarayotganda, yangi narsa paydo bo'ldi: RAMdan farqli o'laroq, RASP o'z-o'zini o'zgartirish qobiliyatiga ega dastur- ko'rsatmalar (davlat-mashina ko'rsatmalari muzlatilgan, mashina tomonidan o'zgartirilishi mumkin emas). Kuk-Rekxou (1971) (75-bet) bu haqda o'zlarining RASP modellarini tavsiflashlarida, Hartmanis (1971) kabi (239ff-bet)

Ushbu tushunchaning dastlabki tavsifini Goldstine-von Neumann (1946) da topish mumkin:

"Bizga raqamni berilgan tartib bilan almashtiradigan buyruq [ko'rsatma] kerak bo'ladi ... Bunday tartib yordamida hisoblash natijalarini u yoki boshqa hisobni tartibga soluvchi ko'rsatmalarga kiritish mumkin" (93-bet).

Bunday qobiliyat quyidagi imkoniyatlarni beradi:

• subroutines - qo'ng'iroq qilish tartibi (yoki ehtimol subroutine) qaytish manzili pastki dasturning oxirgi buyrug'idagi "return_address", ya'ni "JMP return_address"
• deb nomlangan JUMP-jadvallar
• o'z-o'zini o'zgartiradigan kod

Cook and Reckhow dasturining RASP dasturiy to'plami (1973)

Ta'sirli qog'ozda Stiven A. Kuk va Robert A. Reckhow o'zlarining RASP versiyasini aniqlaydilar:

"Bu erda tasvirlangan tasodifiy kirish uchun saqlanadigan dastur mashinasi (RASP) Xartmanis [1971] tasvirlangan RASP-ga o'xshaydi" (74-bet).

Ularning maqsadi turli xil modellarning ishlash vaqtlarini taqqoslash edi: RAM, RASP va ko'p tarmoqli Turing mashinasi nazariyasida foydalanish uchun murakkablikni tahlil qilish.

Ularning RASP modelining ajralib turadigan xususiyati bilvosita dastur-ko'rsatmalar uchun shart emas (ularning muhokamasi 75-bet). Bunga ular dasturdan o'zini o'zgartirishni talab qilish orqali erishadilar: agar kerak bo'lsa, ko'rsatma ma'lum bir ko'rsatmaning "parametrini" (ularning so'zlari, ya'ni "operand") o'zgartirishi mumkin. Ular o'zlarining modellarini ishlab chiqdilar, shuning uchun har bir "ko'rsatma" ketma-ket ikkita registrdan foydalanadi, bittasi "operatsion kodi" (ularning so'zi) va "yoki manzil yoki butun son doimiy" parametrlari uchun.

Ularning RASP registrlari cheklangan va soni bo'yicha cheklanmagan; shuningdek, ularning akkumulyatori AC va ko'rsatmalar hisoblagichi IC cheksizdir. Ko'rsatmalar to'plami quyidagilar:

Adabiyotlar

Ko'pincha ikkala RAM va RASP mashinalari bir xil maqolada keltirilgan. Ular nusxa ko'chirilgan Tasodifiy kirish mashinasi; ba'zi bir istisnolardan tashqari, ushbu ma'lumotnomalar xuddi shu bilan mos keladi Ro'yxatdan o'tish mashinasi.

• Jorj Boolos, Jon P. Burgess, Richard Jeffri (2002), Hisoblash va mantiq: to'rtinchi nashr, Kembrij universiteti matbuoti, Kembrij, Angliya. Boolos-Jeffri asl matni Burgess tomonidan keng ko'lamda qayta ko'rib chiqilgan: kirish darsligidan ancha rivojlangan. "Abakus mashinasi" modeli 5-bobda keng ishlab chiqilgan Abakusni hisoblash; bu keng qamrovli ishlov berilgan va taqqoslangan uchta modeldan biri - Turing mashinasi (hanuzgacha Boolosning dastlabki 4 karra shaklida) va qolgan ikkitasini rekursiya qilish.
• Artur Burks, Herman Goldstine, Jon fon Neyman (1946), Elektron hisoblash vositasining mantiqiy dizaynini oldindan muhokama qilish, qayta bosilgan pp. 92ff Gordon Bell va Allen Newell (1971), Kompyuter tuzilmalari: o'qishlar va misollar, mcGraw-Hill Book Company, Nyu-York. ISBN  0-07-004357-4 .
• Stiven A. Kuk va Robert A. Reckhow (1972), Vaqt chegaralangan tasodifiy kirish mashinalari, Journal of Computer Systems Science 7 (1973), 354-375.
• Martin Devis (1958), Hisoblash va echib bo'lmaydiganlik, McGraw-Hill Book Company, Inc Nyu-York.
• Kalvin Elgot va Ibrohim Robinson (1964), Dasturiy ta'minot uchun tasodifiy kirish mashinalari, dasturlash tillariga yondashuv, Hisoblash mashinalari assotsiatsiyasi jurnali, jild. 11, № 4 (1964 yil oktyabr), 365-399 betlar.
• J. Xartmanis (1971), "Tasodifiy kirishda saqlanadigan dastur mashinalarining hisoblash murakkabligi", Matematik tizimlar nazariyasi 5, 3 (1971) 232-245 betlar.
• Jon Xopkroft, Jeffri Ullman (1979). Avtomatika nazariyasi, tillar va hisoblash bilan tanishish, 1-nashr, O'qish massasi: Addison-Uesli. ISBN  0-201-02988-X. "Tillarni" kompyuterda talqin qilish, NP-To'liqlik va h.k.lar atrofida joylashgan qiyin kitob.
• Stiven Klayn (1952), Metamatematikaga kirish, North-Holland nashriyot kompaniyasi, Amsterdam, Niderlandiya. ISBN  0-7204-2103-9.
• Donald Knuth (1968), Kompyuter dasturlash san'ati, 1973 yil ikkinchi nashr, Addison-Uesli, Reading, Massachusets. Cf 462-463 sahifalarda u "bog'langan tuzilmalar bilan shug'ullanadigan mavhum mashina yoki" avtomat "ning yangi turini" belgilaydi.
• Yoaxim Lambek (1961 yil, 15 iyun 1961 yil qabul qilingan), Cheksiz abakusni qanday dasturlash mumkin, Matematik byulleten, vol. 4, yo'q. 3. 1961 yil sentyabr 295-302 betlar. Lambek o'zining II ilovasida "dastur" ning rasmiy ta'rifini taklif qiladi. U Melzak (1961) va Kleen (1952) ga murojaat qiladi. Metamatematikaga kirish.
• Z. A. Melzak (1961, 15 may 1961 yil qabul qilingan), Hisoblash va hisoblash uchun norasmiy arifmetik yondashuv, Kanada matematik byulleteni, jild. 4, yo'q. 3. 1961 yil sentyabr 279-293 betlar. Melzak hech qanday ma'lumotnomani taklif qilmaydi, ammo "Bell telefon laboratoriyalari doktorlari R. Xamming, D. Makilroy va V. Visots bilan hamda Oksford universiteti doktori X. Vang bilan suhbatlarning foydasi" ni tan oladi.
• Marvin Minskiy (1961 yil, 15 avgust 1960 yil qabul qilingan). "Turing mashinalari nazariyasining" Tag "muammosi va boshqa mavzularining rekursiv echimsizligi". Matematika yilnomalari. Matematika yilnomalari. 74 (3): 437–455. doi:10.2307/1970290. JSTOR  1970290. Sana qiymatlarini tekshiring: | sana = (Yordam bering)
• Marvin Minskiy (1967). Hisoblash: chekli va cheksiz mashinalar (1-nashr). Englewood Cliffs, N. J.: Prentice-Hall, Inc. ISBN  0-13-165449-7. Xususan, 11-bobga qarang: Raqamli kompyuterlarga o'xshash modellar va 14-bob: Hisoblash uchun juda oddiy asoslar. Avvalgi bobda u "Dastur mashinalari" ni ta'riflagan bo'lsa, keyingi bobda "Ikki registrli universal dastur mashinalari" va "... bitta registr bilan" va boshqalarni muhokama qiladi.
• Jon C. Shepherdson va H. E. Sturgis (1961) 1961 yil dekabrni qabul qildi Rekursiv funktsiyalarning hisoblanishi, Hisoblash texnikasi assotsiatsiyasi jurnali (JACM) 10: 217-255, 1963. Juda qimmatli ma'lumotnoma. A qo'shimchasida mualliflar "4.1-da ishlatiladigan ko'rsatmalarning minimalligi: o'xshash tizimlar bilan taqqoslash" ga ishora qilib yana 4 kishini keltirishgan.

• Kefengst, Xaynts, Eine Abstrakte dasturi "Rechenmaschine", Zeitschrift fur matematik Logik und Grundlagen der Mathematik:5 (1959), 366-379.
• Ershov, A. P. Operator algoritmlari to'g'risida, (Ruscha) Dok. Akad. Nauk 122 (1958), 967-970. Ingliz tiliga tarjima, Avtomat. Express 1 (1959), 20-23.
• Peter, Rozsa Graphschemata und rekursive Funktionen, Dialectica 12 (1958), 373.
• Germes, Xans Die Universalität programmgesteuerter Rechenmaschinen dasturida. Matematika-fiz. Semsterberichte (Göttingen) 4 (1954), 42-53.

• Arnold Sönhage (1980), Saqlashni o'zgartirish mashinalari, Sanoat va amaliy matematika jamiyati, SIAM J. Comput. Vol. 9, № 3, 1980 yil avgust. Bu erda Shnhage o'zining SMM-ning "voris RAM" (Random Access Machine) va boshqalar bilan tengligini ko'rsatadi. Saqlashni o'zgartirish mashinalari, yilda Nazariy kompyuter fanlari (1979), 36-37 betlar
• Piter van Emde Boas, Mashina modellari va simulyatsiyalar 3-6 bet, quyidagi ko'rinishda: Yan van Leyven, tahrir. "Nazariy informatika qo'llanmasi. A jild: Algoritmlar va murakkablik, MIT PRESS / Elsevier, 1990 yil. ISBN  0-444-88071-2 (A jild). QA 76.H279 1990 yil.

van Emde Boasning SMMlarni davolashi 32-35 betlarda paydo bo'ladi. Ushbu davolash usuli Schōnhage 1980-ga oydinlik kiritadi - u Schnhage davolanishini diqqat bilan kuzatib boradi, ammo biroz kengaytiradi. Ikkala ma'lumot ham samarali tushunish uchun kerak bo'lishi mumkin.

• Xao Vang (1957), Turingning hisoblash mashinalari nazariyasining varianti, JACM (hisoblash mashinalari assotsiatsiyasi jurnali) 4; 63-92. 1954 yil 23-25 ​​iyun kunlari Assotsiatsiya yig'ilishida taqdim etilgan.