6-ma’ruza. Buyruqlar tizimi arxitekturalarini tasniflash

Stekli arxitektura. Stek deb HM ning asosiy xotirasidan tizimli tashkil etilishi bilan farq qiluvchi xotiraga aytiladi. Stek xotirasini yaratish tamoyillari keyinroq batafsil ko'rib chiqiladi, ammo bu yerda biz faqat stekga asoslangan BTA xususiyatlarini tushuntirish uchun zarur bo'lgan jihatlarni ta'kidlaymiz.
Stek "oxirgi kirgan, birinchi chiqadi" (LIFO, Last In First Out) tamoyili bo'yicha o'zaro ta'sir qiluvchi mantiqiy o'zaro bog'langan yacheykalar to'plamini tashkil qiladi (6.4-rasm).

6.4-rasm. Stekli xotira ishlash printsipi
Yuqori katak stekning cho’qqisi deb ataladi. Stekda ikkita operatsiya mavjud: push (ma'lumotlarni stekga surish) va pop (ma'lumotlarni stekdan chiqarish). Yozish faqat stekning yuqori katakchasiga mumkin, shu bilan birga stekda saqlangan barcha ma'lumotlar avvaliga bir pozitsiya pastga suriladi. O'qishga faqat stekning yuqori qismidan ruxsat beriladi. Qabul qilingan ma'lumotlar stekdan chiqariladi va qolgan tarkib yuqoriga suriladi. Stekga asoslangan BTA amalga oshiriladigan kompyuterlarda (ular odatda stek deb ataladi), operandlar qayta ishlashdan oldin stek xotirasining eng yuqori ikkita joyiga joylashtiriladi. Amallar natijasi stekga suriladi. (a + b) * (c + d ) − e ifodani hisoblash misolida stek mashinasining ishlash prinsipini tushuntiramiz.
Stack yordamida hisob-kitoblarni tavsiflashda, odatda, polyak matematigi J. Lukashevich tomonidan taklif qilingan teskari Polsha yozuvi deb nomlanuvchi matematik ifodalarni yozishning boshqa shakli qo'llaniladi. Uning o'ziga xosligi shundaki, ifodada qavslar yo'q va amal belgisi operandlar orasida joylashmaydi, balki ulardan keyin keladi (postfiks shakli).
Yordamchi stek yordamida ifodaning an'anaviy yozuvini postfiksga aylantirish qulay. Kompyuter stegi bilan adashtirmaslik uchun uni operatsiyalar ketma-ketligi deb ataymiz. Operatsiyalar ketma-ketligi bilan ishlash uchun original (an'anaviy) ifoda yordamida operatsiyalarining ustuvorliklarini belgilaymiz (2.2-jadval). 2.2-jadvalda nol minimalni, to'rt esa maksimal ustuvorlikni bildiradi.
2.2-jadval. Operatsiyalar ketma-ketligi bilan ishlashda operatsiyalarining ustuvor yo'nalishlari

An'anaviy satr skanerlanganda, operatsiyalar ketma-ketligida duch kelgan operatsiya belgilarini o'z ichiga oladi, ular keyinchalik (ma'lum qoidalarga muvofiq) postfiks qatoriga o'tkaziladi. Teskari polyak yozuvidagi ifoda bilan qatorni shakllantirish quyidagi algoritmga muvofiq amalga oshiriladi:
1. Ifoda bilan an'anaviy (kirish) qator chapdan o'ngga skanerlanadi.
2. Agar kirish qatorining keyingi belgisi operand bo'lsa, u darhol postfiks qatoriga qayta yoziladi.
3. Chap qavs, shuningdek, operatsiyalar ketma-ketligi bo'sh bo'lgan taqdirda matematik operatsiya belgisi har doim operatsiyalar ketma-ketligiga kiritiladi.
4. Qidiruv paytida o'ng qavsga duch kelganda, operatsiyalar ketma-ketligining yuqori qismidagi belgi operatsiyalar ketma-ketligidan chiqariladi va postfiks qatoriga qo'yiladi. operatsiyalar ketma-ketligi tepasida chap qavs paydo bo'lguncha protsedura takrorlanadi. Bu sodir bo'lganda, ikkala qavs bir-birini bekor qiladi va chap qavs STR dan olib tashlanadi.
5. Agar operatsiyalar ketma-ketligi bo'sh bo'lsa yoki kirish satridagi operatsiya belgisi operatsiyalar ketma-ketligining yuqori qismidagi belgidan yuqoriroq ustunlikka ega bo'lsa, kirish satridagi operatsiya belgisi operatsiyalar ketma-ketligiga suriladi.
6. Agar kirish satridagi belgining ustuvorligi operatsiyalar ketma-ketligining yuqori qismidagi belgining ustuvorligiga teng yoki undan past bo‘lsa, operatsiyalar ketma-ketligi tepasidagi belgi postfiks qatoriga suriladi. Operatsiyalar ketma-ketligitepasida yoki chap qavsda pastroq ustuvorlikka ega belgi paydo bo'lguncha yoki operatsiyalar ketma-ketligi bo'sh bo'lguncha protsedura takrorlanadi. Shundan so'ng, kirish qatoridagi belgi operandlar ketma-ketligiga kiritiladi.
7. Kirish satrining oxirgi belgisiga erishilganda, operatsiyalar ketma-ketligi satrning mazmuni postfiks qatoriga ketma-ket suriladi.
(a + b) * (c + d) - e ifodasi uchun teskari polyak yozuvini olish jarayoni 6.3-jadvalda keltirilgan.
6.3-jadval. (a + b) * (c + d) − e ifodasi uchun teskari polyak yozuvini shakllantirish

Shunday qilib, polyak yozuvidagi yuqoridagi ifoda: ab + cd +*e – ko’rinishga ega bo’ladi. Belgilanishning bu shakli operandlar va operatsiyalarni stekga yuklash tartibini yagona tarzda belgilaydi (6.5-rasm).

6.5-rasm. Stek arxitekturali kompyuterda ab+cd+*e− ifodasini hisoblash ketma-ketligi
BTA stekiga asoslangan HM ning mumkin bo'lgan variantlaridan birining asosiy tugunlari va axborot yo'llari 6.6-rasmda ko'rsatilgan.

6.6-rasm. Stakka asoslangan kompyuter arxitekturasi