Pisike protsessor: Little Man Computer

Programm asub samas sajas postkastis kui arvud, millega ta töötab. Sammhaaval käivitades näed käsutsükli iga etappi: loetav postkast muutub siniseks, kirjutatav merevaigukollaseks ja järgmise käsu ümber ilmub lilla raam.

Näidisarvutus — Pisike protsessor: Little Man Computer

Täidetud käske	65
F: käsu toomisi, igaüks ühe lugemisega	65
R: operandi lugemisi käskudega LDA, ADD ja SUB	30
W: kirjutamisi käsuga STA	16
Postkastide poole pöördumisi kokku	111
Käskude toomise osakaal	58,6%
Väljund	42
Käivituse lõpp	käsul HLT

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Pisike protsessor: Little Man Computer

Käsu toomise, dekodeerimise ja täitmise tsükkel kordub protsessoris iga käsu puhul. Toomisel kopeeritakse PC väärtus MAR-i, loetakse vastava postkasti sisu MDR-i, kopeeritakse see CIR-i ja liidetakse PC väärtusele 1. Dekodeerimisel eraldatakse käsust operatsioon, mille määrab sajaliste kohal olev number, ja aadress, mille annavad kaks viimast numbrit. Erandiks on 901, 902 ja 000: need on käskude INP, OUT ja HLT terviklikud koodid ega sisalda postkasti aadressi. Täitmisel sooritatakse käsk. Selleks võidakse MAR-i ja MDR-i kaudu veel üht postkasti lugeda või sinna kirjutada.

Mida iga sümbol tähendab

PC: käsuloendur: järgmise mälust toodava käsu aadress
MAR: mäluaadressiregister: selle postkasti aadress, millest hakatakse lugema või kuhu kirjutama
MDR: mäluandmeregister: äsja loetud või kirjutamiseks valmis väärtus
CIR: käsuregister: parajasti täidetav käsk
ACC: akumulaator: siia paigutavad oma tulemuse ADD, SUB ja LDA

Eeldab: Stuart Madnicki Little Man Computer (MIT, 1965) ei määra, mis juhtub, kui SUB annab negatiivse tulemuse või ADD tulemus ületab 999. Selle simulaatori akumulaator mahutab väärtusi −999 kuni 999, seega kontrollib BRP väärtuse märki. Väljapoole seda vahemikku jääv tulemus peatab käivituse ületäitumise tõttu, selle asemel et liikuda ringiga vahemiku teise otsa. Õppesimulaatorid käsitlevad seda erinevalt. Programm, mille akumulaatori väärtus püsib vahemikus 0 kuni 999, töötab kõigis ühtemoodi.

Masin ei erista arvu käsust 🖖

Vajuta Andmed käskudena. Programm koosneb käskudest LDA n ja OUT ning peaks väljastama 105 ühe korra. Autor unustas HLT. PC liigub seetõttu edasi postkasti 02, kuhu on salvestatud 105, ja masin loeb selle järgmise käsuna. 105 tähendab ADD 05 ning postkastis 05 on 20. Järgmisel DAT-real on 902 ehk OUT, nii et väljastatakse 125. Selle järel tuleb 0 ehk HLT. Postkasti sisu juures pole mingit märget, kas see on käsk või arv. Kui PC osutab postkastile, käsitletakse selle sisu käsuna; kui sellele viitab LDA, ADD või SUB, on sisu andmed. Esimene käsk luges sedasama 105 arvuna, kolmas täitis selle käsuna. Nii toimib salvestatud programm, mis esimest korda käivitati Manchester Baby arvutis juunis 1948.

Loendi järgmise elemendi lugemiseks kirjutab programm end ümber 🖖

Vajuta Liida loendi arvud ja jälgi postkasti 00. Alguses on seal 517 ehk LDA 17, mis laadib loendi esimese arvu. LMC käsus on aadress kirjas käsu enda osana. Masinal pole registrit, millest käsk saaks operandi aadressi võtta, seega ei saa öelda „loe postkastist, mis järgneb äsja loetule“. Käsud LDA 17, ADD 18, ADD 19 ja nii edasi sobivad selle loendi jaoks, kuid pikema jaoks neist ei piisa. Et liita arvud ühe tsükliga olenemata nende arvust, loeb programm oma esimese käsu arvuna, liidab sellele 1 ja salvestab tagasi. 517 muutub väärtuseks 518 ehk käsuks LDA 18. Viie tsüklikäiguga kirjutatakse postkast 00 viis korda ümber. Viimast versiooni, LDA 22, ei täideta, sest loendur jõuab enne nulli. Päris protsessorid saavad just selleks aadressi registrist lugeda: nii saab loendi läbida programmi ennast muutmata.

Suurem osa masina loetust on tema enda programm 🖖

Iga käsk vajab enne täitmist üht postkasti lugemist: nii tuuakse käsk mälust. LDA, ADD ja SUB loevad veel ühe postkasti, STA kirjutab ühte. Hüppekäsud, INP ja OUT täitmise ajal postkastide poole ei pöördu. Näites Korruta liites nõuab 6 × 7 seega 65 käsu toomist, 30 operandi lugemist ja 16 kirjutamist. Kogu protsessori ja mälu vahelisest liiklusest kulub 58,6 % masina enda käskude toomisele. Kõigi sisendipaaride puhul, mille korrutis on kõige rohkem 999, jääb see osakaal vahemikku 57,2 % kuni 69,2 %. Programm ja andmed liiguvad sama teed mööda samasse mällu, ükshaaval. John Backus nimetas selle ühenduse von Neumanni pudelikaelaks oma 1977. aasta Turingi auhinna loengus.

Ülesanne täielikult lahendatud

Miks 2 × 99 vajab 801 käsku ja 99 × 2 vaid 25 4 sammu
Vajuta nuppu 2 × 99 aeglaselt ja muuda seejärel sisenditeks 99 ja 2. Mõlemal juhul väljastab programm 198. Loenda kummalgi käivitusel täidetud käsud, leia valem ja ütle, kui palju käske kulub sisendite ebasoodsama järjestuse korral, kui korrutis mahub ühte postkasti.

Ava see ülesanne tööriistas
1. Enne tsüklit täidetakse kaks INP- ja kaks STA-käsku: kokku 4 käsku. Tsükli kehas on LDA b, BRZ, SUB one, STA b, LDA total, ADD a, STA total, BRA loop: 8 käsku, mida korratakse b korda.
  
  $INP, STA, INP, STA : 4 LDA, BRZ, SUB, STA, LDA, ADD, STA, BRA : 8$
2. Kui b jõuab nulli, täidetakse tsüklist ainult LDA b ja BRZ. Seejärel lõpetavad programmi LDA total, OUT ja HLT: veel 5 käsku. Üks käivitus nõuab seega 4 + 8b + 5 = 8b + 9 käsku. Arv a selles avaldises ei esine.
  
  $LDA, BRZ, LDA, OUT, HLT : 5 C (b) = 4 + 8 b + 5 = 8 b + 9$
3. Kui b = 99, on käskude arv 8 × 99 + 9 = 801; kui b = 2, on see 25. Tulemuste tabel näitab esimese järjekorra puhul 801 ja teise puhul 25.
  
  $C (99) = 8 \times 99 + 9 = 801 C (2) = 8 \times 2 + 9 = 25$
4. Suurim postkasti mahtuv korrutis on 999. Sisenditega 1, 999 läbitakse tsükkel 999 korda: kokku 8 001 käsku. Sisenditega 999, 1 läbitakse see ühe korra: 17 käsku.
  
  $C (999) = 8001 C (1) = 173 1^{2} = 961 \leq 999 < 1024 = 3 2^{2}$
Vastus

8b + 9 käsku, kus b on teine sisend. Sama korrutise 999 leidmiseks kulub ühes järjekorras 8 001 käsku ja teises 17, ligikaudu 470 korda rohkem. Kui programm võrdleks kõigepealt sisendeid ja kordaks tsüklit väiksema arvu järgi, kuluks kõige rohkem 8 × 31 + 9 käsku ning lisaks võrdlemiseks vajalikud käsud: kuni 999 ulatuva korrutise väiksem tegur on kõige rohkem 31.

$C = 8 b + 9, min (a, b) \leq 31 \Rightarrow C \leq 8 \times 31 + 9 = 257$

Õpitee

Kuidas arvuti programmi täidab

Allikad (4)

Where the third insight's phrase comes from: the connecting tube between CPU and store, named the von Neumann bottleneck, and the remark that much of its traffic is not data but the names of data: John Backus, "Can programming be liberated from the von Neumann style? A functional style and its algebra of programs." Communications of the ACM 21(8), 613–641, August 1978. The 1977 ACM Turing Award Lecture.
The date the first insight gives for the stored-program idea first running: The University of Manchester, "How a 70-year-old 'Baby' changed the face of modern computing." News, 21 June 2018.
The machine itself: Madnick's 1965 design, the instruction codes, and the fact the page's assumes rests on, that a negative or over-999 result is left undefined: "Little man computer." Wikipedia, read 14 October 2026.
A school simulator's instruction table, with BRP described as branching when the accumulator is zero or positive, the sign convention this page follows: 101computing.net, "LMC Simulator."

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.