Exercise Solution) 3

Role # ___________________ Section ____________

COMPTER ARCHITECTURE AND ORGANIZATION MIDTERM 2 (WEDNESSDAY, MAY 3, 2006) ASSIGNMENT-SOLUTION Question 1 (25): CPU R0 R1 R2 R3

I/O Channel Block 0

Block 1

Block 2

Block 3

P(0-3)

Block 4

Block 5

Block 6

Block 7

P(4-7)

Block 8

Block 9

Block 10

Block 11

P(8-11)

Block 12

Block 13

Block 14

Block 15

P(12-15)

The above diagram shows the organization of a personal computer: a. What does this arrangement of hard disks is called and what level of configuration (2) RAID – LEVEL 4 b. Following 4 Binary floating numbers : A= -1.1101001011 21010 B= -011110111.10 20010 C= 1110.1010011 20001 D= 111111111110000 2-0100 are to be read from the hard disks by the CPU into 4 registers. How will you save these numbers across the disks to achieve the best I/O time for the retrieve operation and why? (2) SPREAD THEM ACROSS DISKS I.E. BLOCK 0 WILL HAVE A, BLOCK 1 WILL HAVE B AND SO ON

Page 1 of 10

Role # ___________________ Section ____________ c. You will need to calculate the arithmetic operation ((B-D)/(C+A))*D for these 4 numbers, Please show how will you perform the arithmetic operation using the following Booth algorithm for multiplication and successive subtraction for the division algorithm (9+9) A= -1.1101001011 21010 B= -011110111.10 20010 C= 1110.1010011 20001 D= 111111111110000 2-0100 PLEASE NOTE THAT THESE ARE NOT IN SIGNED NUMBER FORM. ALSO NOTE:  B-D = -(B+D)  C+A WILL BE NEGATIVE THEREFOR SET X = B+D AND Y = C+A, THEN –X/Y WILL BE POSITIVE FOR B+D WE NEED TO ALIGN THE POWERS ON 2: -B = 011110111.10 20010 = -111101.1110 20100 D= 111111111110000 2-0100 = 1111111.11110000 20100 X = B+D

= (111101.1110 + 1111111.11110000) 20100 = 10111101.1101 20100 A= -1.1101001011 21010 = -1110100.1011 20100 C = 1110.1010011 20001 = 1.1101010011 20100 Y = A+C = (APPROX) =

-1110111.00 20100 WE NEED TO EVALUATE -X/Y * D = X/-Y*D = (X*D)/-Y X*D WILL BE EVALUATE USING THE BOOTH ALGORITHM. BUR FIRST MOVE THE REDIX POINT SUCH THAT THERE IS NO POINT IN X ,Y OR D: X = 10111101.1101 20100 = 101111011101 -Y = 1110111 20100 D = 111111111110000 2-0100  Z= X*D = (11111111111 * 101111011101) 1000 2-0100 SO THE BOOTH ALGORITHM WILL DO 11111111111* 101111011101 PLEASE NOTE THAT IF WE USE SET Q = 11111111111) THEN ONLY IN THE FIRST STEP (WHEN Q0 AND Q-1 ARE 00) WE NEED TO DO A=A-M, ALL THE OTHER 10 IETERATIONS IT WILL ONLY DO AN ARITHMATIC SHIFT RIGHT. (PLEASE GIVE FULL MARKS IF SOMEONE HAS REACHED THIS POINT, EVEN IF THEY DO THE BOOTH ALGORITHM WRONG) NOW WE WILL DO THE DIVISION (Z/-Y) USING SUCCESSIVE SUBTRACTION. WE WILL ONLY DO ONE TIME SUBSTRACTION AS THIS WILL BE AN APPROXIMATE RESULT (PLEASE GIVE FULL MARKS FOR ONE TIME SUBTRACTION): d. Can you change the DISKS configuration to achieve a better data protection? If yes then which level of configuration will you use(3) LEVEL 6 WILL PROVIDE THE BEST PROTECTTION. OTHERS ARE VALID ALSO IF GIVEN EXPLAINATION

Page 2 of 10

Role # ___________________ Section ____________

BOOTH ALGORITHM START

A 0, Q-1  0 M  Multiplicand Q  Multiplier Count  n

= 10

A  A-M

Q0, Q-1

= 11 = 00

= 01

A  A+M

Arithmetic shift right: A,Q,Q-1 Count  Count-1

NO

YES Count = 0 ?

END

Page 3 of 10

Role # ___________________ Section ____________

Question 2 (20): A Microprocessor will need to perform the arithmetic calculation, Y = ((C*(A+D)/(C-B))/A, on the 4 binary numbers of question 1. You will design an Instruction Set for a microprocessor that can perform this arithmetic: a. Show how this arithmetic operation will be performed by the CPU using 2 addresses(5) Load Y, A ADD Y, D MPY Y,C Store Temp, Y Load Y, C Sub Y,B Div Y, Temp Mpy Y,A You can do the multiplication and division the same way as in Question 1. Now answer the following: b. What types of operands will you choose for your Instruction Set design (2) NUMBERS, LOGICAL DATA c. What types of operations will you choose for your Instruction Set design (3) ARITHMATIC, LOGICAL, TRANSFER OF CONTROL d. How will you implement the Booth’s algorithm using conditional branching? Only show relevant portions where you will use conditional branching (5+5) i. FOR TESTING BITS Q0, Q-1 WE WILL LOGICAL “AND” A WITH NUMBERS THAT CAN TELL IF THE BITS ARE 00, 01, 10 OR 11: 0000 AND A, 00 0001 BRZ 1001 0002 AND A, 01 0003 BRZ 2000 0004 AND A, 10 0005 BRZ 1000 0006AND A, 11 0007 BRZ 1001 1000 SUB A,M 1001 ASR A,Q.Q-1 2000 ADD A,M 2001 JUMP 1002 ii. FOR TESTING COUNT = = 0 : 0000 MOV A, COUNT 0001 DECREMENT A

Page 4 of 10

Role # ___________________ Section ____________ 0002 BRNZ (START OF THE MULTIPLICATION LOOP) 0003 END

Page 5 of 10

Role # ___________________ Section ____________

Question 3 (25): Consider the following code for main program, Subroutine A and B. a. Write sequence of execution cycle for the main program.(7) THEY NEED TO DO IT FOR THE MAIN PROGRAM ONLY (NOT THE SUBROUTINES) EXAMPLE (REST IS THE SAME WAY) : PC = F000 - FETCH INSTRUCTION POINTED TO BY PC(IR  LOAD A100) - DECODE THAT THIS IS A LOAD INTRUCTION - RESOLVE ADDRESS FOR OPERAND (A100) - FETCH DATA THAT IS STORED AT A100 - PC = PC+1 b. How many address references will needs to be resolved?(3) 30 c. Show how the Stack will be used for execution of the main program (5) STACK POINTER (SP) = FFFF (BASE OF THE STACK = TOP OF THE STACK)

MAIN PROGRAM: Address F000 F001 F002 F003 F004 F005

Instruction LOAD A100 ADD B100 CALL 1001 SUB C100 CALL 1001 MPY D100

Operation AC  AC + (A100) AC  AC + (B100) CALL SUB A AC  AC-(C100) CALL SUB A AC  AC*(D100)

Instruction ADD B100 CALL 5001 SUB C100 CALL 5001 MPY D100 RET

Operation AC  AC + (B100) CALL SUB B AC  AC-(C100) CALL SUB B AC  AC*(D100)

Instruction ADD B100 DIV C100

Operation AC  AC + (B100) AC  AC / (C100)

SP = FFFF SP = FFFF SP = FFFE, FFFE = F003 SP = FFFF SP = FFFE, FFFE = F005 SP = FFFF

SUB A: Address 1001 1002 1003 1004 1005 1006

SP = FFFE SP = FFFD, FFFD = 1003 SP = FFFE, FFFE = F003 SP = FFFD, FFFD = 1005 SP = FFFE, FFFE = F003 SP = FFFF, PC = F003 (FFFE POPED INTO PC)

SUB B: Address 5001 5002

SP = FFFD, FFFD = 1003 SP = FFFD, FFFD = 1003

Page 6 of 10

Role # ___________________ Section ____________ 5003 5004 5005 5006

SUB C100 ADD B100 MPY D100 RET

AC  AC-(C100) AC  AC + (B100) AC  AC*(D100)

SP = FFFD, FFFD = 1003 SP = FFFD, FFFD = 1003 SP = FFFE, FFFE = F003, PC = 1003 (POP SP INTO PC)

d. If we replace the code in SUB A at location 5006 with the following lines in SUB B then show how the Stack will be used (5+5) Address 5006 5007

Instruction CALL 1001 RET

Operation CALL SUB A

THIS IS SIMILAR TO PARTC FOR STACK (THEY NEEDS TO SHOW ONE SUBROUTINE CALL CYCLE(5)). THEY WILL ALSO NEED TO IDENTIFY THAT THIS IS AN INFINITE RECURSIVE LOOP (5).

Page 7 of 10

Role # ___________________ Section ____________

Question 4 (30): PLEASE BE VERY GENERAOUS WITH THIS QUESTION. ACCEPT ANY PROPER EXPLAINATION OR ASSUMPTIONS. FOLLOWING IS ONE SET OF ANSWERS Consider the following code in Table A for a microprocessor. The values (in Hex) for each step are also shown: Initially AC = 00000000; R1 = 00000100; A100 = 00000002; A102 = 00000003; A200 = 00000002; 00000100 = 0000A100; 0000102 = 00000200; PC = 0000; 0000103 = 00000005; 0000002 = 00000100; (All value are in Hex; AC is accumulator, R1 is register, PC is program counter, “A100 = 00000002” means memory address A100 contains value = 00000002) ADDRESS INSTRUCTION EXECUTION ADDRESSING Number of Effective RESULT MODE? Address address references? 00000000 MOV R1,A100 AC=00000002 PRE-INDEXING 2 (0100 + A100 = A200 00000001 ADD 0003 AC = 00000005 IMMEDIATE 0 NA 00000002 SUB A100 AC=00000003 DIRECT 1 A100 00000003 MPY R1 AC=00000200 REGISTER 1 R (THERE IS AN ERROR AC SHOULD BE 300) 00000004 DIV A200,R1 AC = 00000001 AUTO3 200 = INDEXING (A200) + 100 00000005 STORE R1 AC=00000001 REGISTER 2 (100) INDIRECT 00000006 ADD A100,R1 AC=00000006 POST-INDEXING 3 103 = (A100) + R1 00000007 SUB 0100 AC = ERROR (DO NOT ERROR ERROR FFFF5F06 GRADE) 00000008 ADD R, A000 AC = ERROR (DO NOT ERROR ERROR FFFF5F08 GRADE) 00000009 SUB A00,R AC ERROR (DO NOT ERROR ERROR =FFFF5F0B GRADE) R1 = 00000101 TABLE A a. Please fill in the above TABLE A addressing modes for each instruction that will produce the results of the second column?(10) Also fill in the column for number of address references and effective address? (5)

Page 8 of 10

Role # ___________________ Section ____________ b. For the following program in table B, please fill the missing values indicated by a question mark (10)? Also fill in the column for number of address references and effective address? (5) Initially AC = 00000000; R = 00000002, C100 = 00000D100; C102 = 000002;D102 = 00000002; E000 = 0000F000; PC = F000; F100 = 00000008; 00000002 = 00000004; 00000004 = 00000004; STACK POINTER = FFFFFFFE; FFFFFFFE=0000A000; 0018000 = 000F100 ADDRESS INSTRUCTION EXECUTION ADDRESSING Number of Effective RESULT MODE Address Address references? EA? F0000000 MOV 0100 AC = 8 Relative 1 F100 addressing F0000001 ADD C100,R AC = A Pre-indexing 3 D102 = addressing (C100) + R F0000002 MPY R AC = 28 Register indirect 1 002 = (R) addressing F0000003 DIV 0002 R = 02, AC = 05 Indirect addressing 2 0004 = (0002) F0000004 SUB R AC = 3 Register 1 R addressing F0000005 ADD C100,R AC = 5 Post-indexing 2 C102=C100 addressing + (R) F0000006 DIV 0001 AC = 5 Immediate 0 NA addressing F0000007 STORE R,E000 AC = 5 Base register 2 (R) + E000 addressing F0000008 LOAD R AC = 5 Stack addressing 1 FFFFFFFE R = A000 F0000009 ADD E000,R AC = 000F100 Pre-indexing 2 (R) + addressing (E000) = 0018000 TABLE B (EA is effective address)

Page 9 of 10

Role # ___________________ Section ____________

Page 10 of 10