My dream CPU |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
V. Примерни програмиЧаст 2. Примерни програми с по-висока степен на сложност. СортиранеТази част съдържа по-сложни програми. Демонстрира писането и използването на процедури. Предаване на параметри на процедурите през регистър или стека. Ще видим сортиране, двоично дърво, обхождане на дървото. Сортиране по метода на мехурчето. BubleSortТази програма демонстрира сортиране по метода на мехурчето, използвайки sortAB инструкцията. Данните за програмата са разположени от адрес 1000. След изпълнението на програмата те ще са сортирани. На адрес 950 е размера на масива. Програмата се разполага от адрес 100, така е инициализиран IP. Листинг на програмата: Init: IP: 100 SP: 1024 Memory size: 2k 0 A: rBs1 <-- #1000 2 A: rX1 <-- #0 4 A: rMaxX <-- M950 6 A: IfMaxX rX1 >= rMaxX ;#22 8 I: rA <-- M[rBs1,rX1]0 10 I: rB <-- M[rBs1, rX1]1 12 I: SortAB < ; IfNoExch #18 14 I: rA --> M[rBs1,rX1]0 16 I: rB --> M[rBs1,rX1]1 18 A: IncX rX1 #1 20 A: rIP <-- #6 22 A: rX1 <-- #0 24 I: rA <-- M950 26 I: rB <-- #1 28 I: AmnsB --> M950 30 I: rA <-- M950 32 I: rB <-- #0 34 I: if ( A > B ) jump #4 36 ENDPRG Data part; Start address: 0
Край Описание на програмата:
Инструкцията на адрес 0 зарежда rBs1 с 1000. Това е началото на масива с данни. Адрес 4 - rMaxX се зарежда от адрес 950. Там е размерът на масива 19 Адрес 6 - Проверява се rX1 >= rMaxX, ако е вярно се извършва преход на адрес 22 Адрес 8 - rA на целочисленият модул се зарежда от адрес [rBs1, rX1]0. Прочита елемент от масива. Адрес 10 - rB се зарежда от адрес [rBs1, rX1]1. Прочита следващият елемент от масива. Адрес 12 - Извършва се сортиране на rA и rB като A < B. Ако не е била извършена размяна на регистрите се извършва преход на адрес 18. Тоест ако A < B не е била извършвана рамяна на съдържанието на rA и rB. Няма смисъл от записване обратно в паметта и следващите 2 инструкции се презкачат. Адрес 14 - Записва rA на адрес [rBs1, rX1]0 Адрес 16 - Записва rB на адрес [rBs1, rX1]1 Адрес 18 - rX1 се инкрементира с 1 Адрес 20 - на rIP се присвоява стойност 6. Това е jump на адрес 6. Адрес 22 - rX1 се нулира Адрес 24 - В rA се зарежда размерът на масива. Този адрес от паметта се използва и за брояч. Адрес 26 - rB = 1 Адрес 28 - rA - rB се записва на адрес 950. Адрес 30 - rA се зарежда от адрес 950. Адрес 32 - rB се нулира Адрес 34 - Ако A > B се извършва преход към адрес 4 Адрес 36 - Край на програмата Методът на мехурчето се реализира с 2 цикъла вписани един в друг. В случаят вътрешният цикъл е между адреси 6 и адрес 20. Между адрес 22 и адрес 32 се намалява с 1 водещата променлива на външният цикъл, тя е в адрес 950 от паметта. На адрес 34 се извършва проверка за край на външният цикъл. Между адрес 22 и адрес 32 могат да се използват инструкции от типа регистър-регистър, но към датата на писането на тази програма още не бяха реализирани в самия процесор. Например намаляването на променливата с 1 може да се извърши с RR операция и в последствие да се запише на адрес 950. Втори вариант на програмата е показан на следният листинг: 0 A: rBs1 <-- #1000 2 A: rBs2 <-- #1001 4 A: rX1 <-- #0 6 A: rMaxX <-- M950 8 A: IfMaxX rX1 >= rMaxX ; #24 10 I: rA <-- M[rBs1,rX1]0 12 I: rB <-- M[rBs2,rX1]0 14 I: SortAB < ;IfNoExch #20 16 I: rA --> M[rBs1,rX1]0 18 I: rB --> M[rBs2,rX1]0 20 A: IncX rX1 #1 22 A: rIP <-- #8 24 A: rX1 <-- #0 26 I: rA <-- M950 28 I: rB <-- #1 30 I: AmnsB --> M950 32 I: rA <-- M950 34 I: rB <-- #0 36 I: if ( A > B ) jump #6 38 ENDPRG При този вариант е добавен адрес 2 в който rBs2 се инициализира със адреса на вторият елемент от масива. В следствие на което е променен адрес 12 където rB се зарежда M[rBs2, rX1]0 на база rBs2 и отместване 0. Също е променен и адрес 18 където rB се записва в M[rBs2, rX1]0. Тоест записът на rB също е по rBs2 и отместване 0. Спестява се изчисляването на адрес с отместване 1. Вариант 3. Същият е като вариант 2, но се използват компресирани инструкции: 0 A: rBs1 <-- #1000 2 A: rBs2 <-- #1001 4 A: rX1 <-- #0 6 A: rMaxX <-- M950 8 A: IfMaxX rX1 >= rMaxX ; #22 10 I: rA <-- M[rBs1,rX1] ||| I: rB <-- M[rBs2, rX1] 0|||0 13 I: SortAB < ;IfNoExch #18 15 I: rA --> M[rBs1,rX1] ||| I: rB --> M[rBs2, rX1] 0|||0 18 A: IncX rX1 #1 20 A: rIP <-- #8 22 A: rX1 <-- #0 24 I: rA <-- M950 26 I: rB <-- #1 28 I: AmnsB --> M950 30 I: rA <-- M950 32 I: rB <-- #0 34 I: if ( A > B ) jump #6 36 ENDPRG Компресирани са само инструкциите на адрес 10 и адрес 15. Това са инструкциите за четене преди sortAB и инструкциите за запис след нея. Инструкцията sortAB е изключително простичка и ефективна. При почти всички алгоритми за сортиране се прави сравнение и евентуална размяна на сортираните елементи. Това прави тази инструкция изключително полезна. |