PESIT SOUTHCAMPUS 10CS46: COMPUTER ORGANIZATION
QUESTION BANK
BASIC STRUCTURES OF COMPUTERS
OBJECTIVE: Computer performs the function of storing and processing the information. It has various functional units, and has evolved to the present day form after generations. In this chapter we learn and understand basic operational concepts of a computer, its performance, and about the evolution of computer from 1st generation to 4th.
1.
List the steps needed to execute the machine instruction Add LOC, R0 in terms of transfers 08 between memory and processor and some simple control commands. Assume that the instruction itself is stored in the memory at location INSTR and that this address is initially in register PC.
2.
Give a short sequence of machine instructions for the task: “Add the contents of memory 08 location A to those of location B, and place the answer in location C.” Instructions Load LOC, Ri and
Store Ri, LOC
are the only instructions available to transfer data between the memory and general purpose register Ri. Do not destroy the contents of either location A or B.
3.
Suppose that Move and Add instructions are available with the format 08 Move / Add Location 1, Location 2 These instructions move or add a copy of the operand at first location to the second location, overwriting the original operand at the second location. Location can be in either the memory or the processor register set. Is it possible to use fewer instructions to accomplish the task in question 2? If Yes, give the sequence.
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS
4.
5.
Explain different functional units of a digital computer. Mention the functions of different 08* processor registers a)IR b)MAR c)PC List and explain the developments made during different generations of a computer. 08*
6.
What is a bus? Explain single bus structure in architecture.
06*
7.
Explain how will you measure the performance of a computer.
06
8.
Explain the methods to improve the performance of a computer.
06
9.
Explain the function of processor registers with a block diagram.
08*
10.
With a neat diagram explain the connections between the different processor register and the memory.
06
11.
What is a bus? Explain single bus and multiple bus structure used to interconnect functional units.
04
12.
List three important differences between how the stacks and queues organized in memory.
04
MACHINE INSTRUCTIONS & PROGRAMS OBJECTIVE: Computer executes programs, i.e. a set of instructions along with some operands. These instructions and operands are stored generally in memory. In this chapter we study how these instructions and operands are brought from memory to the processor and executed. At the end of the chapter one will know about machine instructions and program execution, number representation, addressing modes, operations on stack, queue, list, linked-list and array data structures. 13. Represent the decimal values 5, -2, 14, -10, 26, -19, 51 and –43, as signed, 7- bit 10 numbers in the following binary formats: a) Sign-and-magnitude b) 1’s complement c) 2’s complement 14. (a) Convert the following pairs of decimal numbers to 5-bit, signed, 2’s- complement 10 binary numbers and add them. State whether or not overflow occurs in each case. a) 5 and 10 b) 7 and 13 c) –14 and 11 d) –5 and 7 e) –3 and –8 PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS (b) Repeat Part a for the subtract operation, where the second number of each pair is to be subtracted from the first number. State whether or not overflow occurs in each case. 15. Given a binary pattern in some memory location, is it possible to tell whether this 04 pattern represents a machine instruction or a number? 16. A memory byte location contains the pattern 00101100. What does this pattern 04 represent when interpreted as a binary number? What does it represent as an ASCII code? 17. Consider a computer that has a byte-addressable memory organized in 32-bit words 06 according to the big-endian scheme. A program reads ASCII characters entered at a keyboard and stores them in successive byte locations, starting at location 1000. Show the contents of the two memory words at locations 1000 and 1004 after the name “Johnson” has been entered. 18. A program reads ASCII characters representing the digits of a decimal number as 06 they are entered at a keyboard and stores the characters in successive memory bytes. Examine the ASCII code and indicate what operation is needed to convert each character into an equivalent binary number. 19. Write a program that can evaluate the expression
06
A*B+C*D In a single-accumulator processor. Assume that the processor has Load, Store, Multiply, and Add instructions and that all values fit in the accumulator. 20.
a)
LOOP
08 Move
#AVEC, R1
Move
#BVEC, R2
Move
N, R3
Clear
R0
Move
(R1)+, R4
Multiply
(R2)+, R4
Add
R4, R0
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS Decrement
R3
Branch>0
LOOP
Move
R0, DOTPROD
Rewrite the dot product program above for an instruction set in which the arithmetic and logic operators can only be applied to operands in processor registers. The two instructions Load and Store are used to transfer operands between registers and the memory. b) Calculate the values of the constants k1 and k2 in the expression k1+k2n, which represents the number of memory accesses required to execute your program for Part a, including instruction word fetches. Assume that each instruction occupies a single word. 21. “Having a large number of processor registers makes it possible to reduce the 05 number of memory accesses needed to perform complex tasks.” Devise a simple computational task to show the validity of this statement for a processor that has four registers compared to another that has only two registers. 22. Registers R1 and R2 of a computer contains the decimal values 1200 and 4600. What 06 is the effective address of the memory operand in each of the following instructions? (a) load 20I, R5 (e) add -(R2), R5
b) move
#3000,R5
c) store
d) add R5,30(R1,R2)
f) subtract (R1)+,R5
23. Consider an array of numbers A (I, j), where i=0 through n – 1 is the row index, and 06 j=0 through m-1 is the column index. The array will be stored in the memory of a computer one row after another, with elements of elements of each row occupying m successive word locations. Assume that the memory is byte-addressable and that the word length is 32 bits. Write a subroutine for adding column x to column y, element by element, leaving the sum elements in column y. The indices x and y are passed to the subroutine in registers R1 and R2. The parameters n and m are passed to the subroutine in registers R3 and R4, and the address of element A (0,0) is passed in register R0. Any of the addressing modes in table 1 can be used. At most, one operand of an instruction can be in memory. 24. Both of the following statements cause the value 300 to be stored in location 1000, but at different times.
PESIT-BSC-Education for the real world
05
PESIT SOUTHCAMPUS ORIGIN DATAWORD
1000 300
and move
#300, 1000
Explain the difference. 25. Register R5 is used in a program to point to the top of a stack. Write a sequence of instructions using the Index, Autoincrement, and Autodecrement addressing modes to perform each of the following tasks:
06
(a) Pop the top two items off the stack, and them, and then push the result onto the stack. (b) Copy the fifth item from the top into register R3. (c) Remove the top ten items from the stack. 26. A FIFO queue of bites is to be implemented in the memory, occupying a fixed region 08 of k bytes. You need two pointers, an IN pointer and an OUT pointer. The IN pointer keeps track of the location where the next byte is to be appended to the queue and the OUT pointer keeps track of the location containing the next byte to be removed from the queue. a) As data items are added to the queue, they are added at successively higher addresses until the end of the memory region is reached. What happens next, when a new item is to be added to the queue? b) Choose a suitable definition for the IN and OUT pointers, indicating what they point to in the data structure. Use a simple diagram to illustrate your answer. c) Show that if the state of the queue is described only by the two pointers, the situations when the queue is completely full and completely empty are indistinguishable. d) What condition would you add to solve the problem in part c? e) Propose a procedure for manipulating the two pointers IN and OUT to append and remove items from the queue. 27. Consider the queue structure described in the above problem. Write APPEND and 06 REMOVE routines that transfer data between a processor register and the queue. Be careful to inspect and update the state of the queue and the pointers each time an operation is attempted and performed. 28. Consider the following possibilities for saving the return address of a subroutine: a) In a processor register. b) In a memory location associated with the call, so that a different location is used when the subroutine is called from different places. PESIT-BSC-Education for the real world
04
PESIT SOUTHCAMPUS c) On a stack. Which of these possibilities supports subroutine nesting and which supports subroutine recursion (that is, a subroutine that calls itself)? 29. The subroutine call instruction of a computer saves the return address in a processor 05 register called the link register, RL. What would you do to allow subroutine nesting? Would your scheme allow the subroutine to call itself? 30. Assume you want to organize subroutine calls on a computer as follows: When 06 routine Main wishes to call subroutine SUB1, it calls an intermediate routine, CALLSUB, and passes to it the address of SUB1 as a parameter in register R1. CALLSUB saves the return address on a stack, making sure that the upper limit of the stack is not exceeded. Then it branches to SUB1. To return to the calling program, subroutine SUB1 calls another intermediate routine, RETRN. This routine checks that the stack is not empty and then uses the top element to return to the original calling program. Write routine CALLSUB and RETRN, assuming that the subroutine call instruction saves the return address in a link register, RL. The upper and lower limits of the stack are recorded in memory locations UPPERLIMIT and LOWERLIMIT, respectively. 31. Explain various forms of representation of numerical data. Justify which is better 06 method with examples. 32. Explain Big-Endian, Little-Endian assignment and byte addressability.
06*
33. What is arithmetic overflow.Explain how it can be detected with an illustration.
08*
34. Explain the Instruction Sequencing and its complete execution.
05
35. What is an Instruction? Explain its functionalities.
06
36. Mention the four types of operations to be performed by an instruction in a 06* computer.What are the basic types of instruction formats. Give examples? 37. Write the complete execution of Straight Line Sequencing with an example.
05
38. Write a note on Branching Instruction with reference to the PC.
05
39. What is Addressing Mode? Explain various methods with examples.
08*
40. Write notes on:
06
a) Register transfer notation. B) Assembly language Notation. C) Assembler PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS Directives. 41. Explain SUBROUTINE LINKAGE with example.
04
42. Mention various parameter-passing techniques with examples.
06
43. What is Stack? Write the line of code to implement the same.
04
44. What is a Queue? Write the line of code for its implementation.
04
45. Write a brief note on Input and output operations with a neat diagram.
06
46. What do you understand by stack frame? Discuss their use in sub-routines.
10*
47. Write a note on RISC and CISC machines.
06
48. What are the instructions to manipulate bit wise data? Explain.
06
49. Write the use of ROTATE & SHIFT Instructions with examples.
06
50. Write a piece of code in ALP to implement the student record and compute average.
08
51. Consider the memory system of a computer storing the following data:
20*
Address in Hex
Data stored (binary)
2000 00111000 2001 00110100 2002 00110010 2003 00111001 Interpret the storage as numbers in the manner indicated below and find their decimal values in each case. i) Big-endian storage of 2 hex words of 4-digits each ii) Big-endian storage of 2 BCD words of 4-digits each iii) Little-endian storage, in ASCII, of a 4-digit signed hex word iv) Little-endian storage, in ASCII, of a 4-digit BCD word. (b) Give reasons to justify using, generally, i) ii) iii)
Single address instructions in 8-bit CPU’s Double address instruction in 16-bit CPU’s Three address instructions in RISC systems
In each of these systems give assembly language programs for performing the operation: Data at mem A + Data at mem B -> mem C.
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS 52. Write an assembly program to multiply 2 memory arrays and store their result in a third memory array:
10*
a(i) * b(i) = c(i) for i=0 to n-1. Consider load/store and 3-address system. 53. What are assembler directive? Explain any two directives.
06*
54. Explain Logical, Shift and Rotate instructions with examples.
06*
55. Write an assembly language program to solve an expression ax2 + bx + c = 0 using two addressing modes.
06*
56. Register RI and R2 of computer contain the decimal value 1200 and 4600. What is the
05*
effective address of the source operand in each of the following instructions? i) Load 20(Rl), R5 ii) Hove # 3000, R5 iii) Store R5, 30(Rl, R2) iv) Add -(R2), R5 v) Subtract (RI)+, R5 57. Mention four types of operations required to be performed by
6
instructions in a computer. Show how the operation C= A+B can be implemented using : i.Three address instruction ii.Two address instruction iii.One address instruction
58. Explain branching with a neat diagram.
04
59. What is an addressing mode ? List the different types of addressing modes . Explain index addressing mode with example program.
08
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS 60. List few condition codes.
04
61. What is subroutine linkage? Explain with an example using link register.
06
62. For a simple example of I/O operations involving a keyboard and a display device , write a ALP that reads one line from the keyboard, stores it in memory buffer and echoes it back to the display.
06
63. Explain the following instructions with example
06
a) Logical b) Rotate - (RLC,RL)
INPUT / OUTPUT ORGANIZATION
OBJECTIVE: One of the basic features of a computer is its ability to exchange data with other devices. It means computer performs various input/output operations. In this chapter we will learn in detail about how these operations are performed. We will know about programcontrolled I/O using polling, interrupts, direct memory access, data transfer over synchronous and asynchronous buses, and about PCI, SCSI and USB buses.
64.
What is Program Controlled I/O? Explain.
05
65.
Differentiate memory mapped I/O and I/O mapped I/O
04
66.
Explain with a neat diagram the single bus organization.
05
67.
What is Interrupt driven I/O? Explain how an I/O is serviced?
06
68.
What is an ISR? Write how interrupts are enabled or disabled.
08
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS 69.
Explain any two methods of handling multiple I/O devices.
06*
70.
What are Vectored Interrupts? Explain.
06
71.
What are Priority Interrupts? Explain.
05
72.
What is DMA? Explain.
06
73.
Why does DMA have priority over the CPU when both request a memory transfer?
04
74.
What is bus arbitration? Explain how it is resolved when requested for service by both processor and memory.
06
75.
Explain different types of arbitration.
04
76.
What is I/O BUS? Explain.
04
77.
Explain different types of data Transfer methods.
06
78.
What is Synchronous Bus Transfer? Explain with a timing diagram.
08
79.
What is Asynchronous Bus Transfer? Explain with a timing diagram.
08
80.
What is an Interface? Write a note on its types.
06
81.
Write a note on Serial Interface.
04
82.
Write a note on Parallel Interface.
04
83.
Write a note on Standard Interfaces.
04
84.
Write a note on Peripheral Component Interconnect (PCI) Bus.
04
85.
Explain data transfer using PCI Bus.
04
86.
Write a note on SCSI bus signals.
06
87.
Explain SCSI, USB and PCI Bus.
05
88.
Differentiate all the three buses.
04
89.
Write a note on USB protocols.
04
90.
Explain how a read operation is performed using PCI Bus.
04
91.
Explain the USB architecture with a neat diagram.
06
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS 92.
Explain how USB operates using split-traffic mode. How can it be connected to two fast and one slow device.
10
93.
Write a note on addressing scheme used in USB.
04
94.
a) Explain how interrupt request from several I/O devices can be communicated to a processor through a single INTR line.
10*
b) Which type of I/O devices is interfaced through DMA? c) Explain the bus-arbitration process used for DMA. 95.
Explain the general features of interfacing a parallel I/O port to a processor.
96.
Consider the daisy chain arrangement shown in figure 3 (available at the end of the Q-bank) in 10* which the bus request signal from the I/O is directly fed back as grant signal. Assume device I/O3 requests the bus and begins using it. When the device is finished, it deactivates BR3. Assume the delay from BGi to BGi+1 in any device is d. Show that a spurious bus-grant pulse will travel down stream from device 3. Estimate the width of this pulse.
97.
Why is bus arbitration required? Explain with block diagram bus arbitration using daisy chain.
08*
With a block diagram, explain how a keyboard is connected to a processor.
06*
98.
A CPU with a 20-MHz clock is connected to a memory unit whose access time is 40 ns. Formulate a read and write timing diagrams using a READ strobe and a WRITE strobe. Include the address in the timing diagram.
08
99.
Obtain the truth table of an 8x3 priority encoder. Assume that the three outputs xyz from the priority encoder are used to provide a vector address of the form 101xyz00. List the eight vector addresses starting from the one with the highest priority.
10
10*
100. What programming steps are required to check when a source interrupts the computer while it is still being serviced by a previous interrupt request from the same source?
08
101. Why are the read and write control lines in a DMA controller bi-directional? Under what condition and for what purpose are they used as inputs? Under what condition and for what purpose are they used as outputs?
06
102. What is the basic advantage of using interrupt-initiated data transfer over transfer under program control without an interrupt?
04
103. The address of a terminal connected to a data communication processor consists of two letters
04
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS of the alphabet or a letter followed by one of the 10 numerals. How many different addresses can be formulated? 104. How can the processor obtain the starting address of different interrupt-service routines
04
using vectored interrupts? 105. Explain the followings with respect to USB.
08
i) USB architecture ii) USB addressing iii) USB protocols 106. Describe the split bus operation. How can it be connected to two fast devices and one slow device?
08
107. How can the processor obtain the starting address of different interrupt-service routines using vectored interrupts?
04
108. List out the functions of an I/O interface with the help of a diagram.
06
109. What are Interrupt nesting? Briefly bring out the methods involved in the processor attending to simultaneous requesting.
06
THE MEMORY SYSTEM OBJECTIVE: Programs and the data operated on are stored in the memory of a computer. The execution speed of programs is highly dependent on the speed with which instructions and data can be transferred between the processor and the memory. In this chapter you will learn about basic memory circuits, organization of the main memory, cache memory, virtual memory mechanism, magnetic disks, optical disks and magnetic tapes.
110. Explain the memory operations Read and Write.
08
111. Mention the various memory performance parameters.
08
112. Explain the following:
08
a) Primary memory
b) Secondary memory
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS c) Tertiary memory
d) Block transfer in menu hierarchy.
113. What is refreshing? Explain the concept of refreshing in dynamic memory.
05
114. Explain the static RAM cell design.
05
115. Explain the dynamic RAM.
05
116. Explain the following:
08
a) PROM b) EPROM c) Flash e) EEPROM 117. Explain the general properties of a 2 level hierarchy.
05
118. Explain the following:
04
a) Hit ratio b) Miss ratio 119. Given a hit ratio of 0.92 and cache access time of 40 ns and main memory access time of 300 ns .calculate the average access time.
04
120. Differentiate between Miss penalty and hit rate.
05
121. With a suitable block diagram explain the cache swapping function.
08
122. Write a note on virtual memory and give the advantages.
08
123. Explain the following:
08
a) Effective address b) Logical address c) Virtual address d) Physical address 124. Explain memory management using segmentation and paging.
10
125. Differentiate between internal fragmentation and external fragmentation.
05
126. Explain the following:
08
a) Multiprogramming b) Page placement 127. Explain the structure and operation of translation look- aside buffer.
08
128. Explain the operation of memory hierarchy with block diagram.
08
129. Explain the Read/Write operation of an SRAM cell designed using CMOS, with the help of a neat diagram.
06
130. Discuss the organization of 1K x 1 memory cell.
06
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS 131. Describe the operation of 2M x 8 asynchronous DRAM chip.
06
132. Discuss the main features of SDRAM with a neat diagram.
06
133. Write a note on memory expansion. Show how a 8K x 8 memory can be obtained using 2K x 8 chips.
06
134. Write a block diagram of 256K x 8 memory using 256K x 1 chips.
06
135. Design a 4M x 32 module using 512K x 8 memory chips. Show the address lines and control signals required.
08
136. Write briefly about Read only memories.
04
137. Describe the terms latency, bandwidth, locality of reference, mapping function and replacement algorithm, with reference to cache memory.
08
138. Discuss how read and write operations are carried out in a cache memory.
06
139. Consider a system having 512K main memory organized as 16K blocks of 32 words each and a cache memory of 16K arranged as 512 blocks of 32 words each. Show how the mapping is done using direct mapping.
08
140. A set-associative cache consists of 128 blocks divided into 4 block / set. The main memory has 8192 blocks each consists of 128 words.
06
a. How many address bits are required to access a main memory location? b. What are the number of bits in TAG, SET and WORD fields? 141. A computer has L1 and L2 caches. The cache block consists of a 8 words. The hit rate is 0.95 for both caches. The time required to access an 8-word block in L1 cache is 1 cycle and in L2 cache is 10 cycles. Time needed to access L1 cache is 1 cycle, L2 cache is 10 cycles and main memory is 50 cycles. Calculate the average access time experienced by the processor. 142. Consider a disk unit having 24 surfaces and 14000 cylinders. There are 400 sectors per track with each sector having 512 bytes of data. c. What is the total capacity of the disk in bytes? d. What is the data transfer rate in bytes per second at a rotational speed of 6000 rpm? 143. Describe SDRAM and DDR SDRAM operations for data transfer between main memory and cache memory systems. 144. Consider a processor running a program. 30% of the instructions of which require a memory read or write operation if the cache bit ratio is 0.95 for instructions and 0.9 for data. When a cache bit occurs for instruction or for data, only one clock is needed while the cache miss penalty is 17 clocks to read/write on the main memory. Work out the time saved by using the PESIT-BSC-Education for the real world
05
04
10* 10*
PESIT SOUTHCAMPUS cache, given the total number of instructions executed is 1 million. 145. How read and write operation takes place in 1KX 1 memory chip? Explain.
06*
146. Explain any two cache mapping functions.
08*
147. What are the key factors that affect the performance and cost of a computer with respect to memory? Explain briefly.
06*
148. Explain the working principles of magnetic disk.
08*
149. A magnetic disk system has the following parameters:
04
Ts = average time to position the magnetic head over a track R = rotation speed of disk in revolutions per second Nt = number of bits per track Ns = number of bits per sector Calculate the average time Ta that it will take to read one sector. 150. An 8-bit computer has a 16-bit address bus. The first 15 lines of the address are used to select a 06 bank of 32K bytes of memory. The high-order bit of the address is used to select a register which receives the contents of the data bus. Explain how this configuration can be used to extend the memory capacity of the system to eight banks of 32K bytes each, for a total of 256K bytes of memory. 151. A digital computer has a memory unit of 64K x 16 and a cache memory of 1K words. The 08 cache uses direct mapping with a block size of four words. a. How many bits are there in the tag, index, block and word fields of the address format? b. How many bits are there in each word of cache, and how are they divided into functions? Include a valid bit. c. How many blocks can the cache accommodate?
152. A two-way set associative cache memory uses blocks of four words. The cache can 06 accommodate a total of 2048 words from main memory. The main memory size is 128Kx32. e. Formulate all pertinent information required to construct the cache memory. f. What is the size of the cache memory? 153. A virtual memory has a page size of 1K words. There are eight pages and four blocks. The PESIT-BSC-Education for the real world
06
PESIT SOUTHCAMPUS associative memory page table contains the following entries: Page Block a. 3 b. 1 a. 2 a. 0 Make a list of all virtual addresses (in decimal) that will cause a page fault if used by the CPU. 154. The logical address space in a computer system consists of 128 segments. Each segment can have upto 32 pages of 4K words in each. Physical memory consists of 4K blocks of 4K words in each. Formulate the logical and physical address formats.
06
155. a. What is the memory layout of the 16-bit value, ABCDH in a big-endian 16-bit machine, and a little-endian 16-bit machine?
05
b. What would the layouts be in 32-bit machines? 156. What would the layout of the following data structure be in little-endian and big-endian machines?
04
char d[7]; /* ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’ byte array */ 157. Explain different mapping functions used in cache memory
10
158. What do you mean by memory interleaving? Explain
04
159. Explain the working of a single-transistor dynamic memory cell.
07
160. Explain with block diagram how TLB is used in implementing virtual memory?
08
161. Mention any two difference between static and dynamic RAM’s. Explain the internal organization of a memory chip consisting of 16 words of 8 bit each.
08
162. Why bus arbitration is required ? Explain with block diagram distributed bus arbitration.
06
163. Define exceptions . Explain two kinds of exceptions
04
164. Describe a ROM cell. Explain the various types of ROM
05
165. Draw neat timing diagrams and explain :
08
i. Multi-cycle synchronous bus transfer for a read transfer
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS ii. Asynchronous bus transfer for a read transfer 166. Bring out the difference between Memory Mapped I/O and Isolated I/O.
06
167. Explain how an address generated by the processor gets translated into main memory address
10
ARITHMETIC UNIT OBJECTIVE: A basic operation in all digital computers is the addition or subtraction of two numbers. Arithmetic operations occur at the machine instruction level. They are implemented along with basic logic functions. In this chapter we learn about design of arithmetic and logic unit viz., Adders, Multiplications, etc., booth’s algorithm, representation of Floating point numbers in IEEE standards and its implementation.
168. Explain 2’s complement Adder/ Subtracter with a suitable block diagram.
08
169. Differentiate restoring and non restoring division
04
170. Write the algorithm for binary division using restoring division method.
04
171. Give the Pseudocode for multiplying 2 m-digit unsigned integers.
05
172. Explain 2’s complement multiplier with suitable block diagram.
08
173. Write the procedure for integer division for dividing (101101)2 (45)10 by (000110)2 (6)10.
05
174. Explain floating-point addition and subtraction with a suitable example and also give the h/w structure for that. 175. Give the procedure for floating-point multiplication and division.
08
176. Perform addition and subtraction on the following pairs of numbers represented in 2’scomplement format. In each case, verify whether overflow has occurred or not. The numbers are represented using 7-bits including the sign bit. a) +25 and +38 b) +33 and +51 c) –24 and +63 d) –23 and – 57 e) –12 and –40 f) –62 and +18
06
177. Show how to implement a full adder using half-adders and external logic gates.
08
178. Design a BCD adder for adding 2 decimal digits using 4-bit binary adder and external logic gates. The inputs are A = A3 A2A1A0 and B = B3B2B1B0 and a carry-in, cin bit. The range of A and B is from 0 to 9.
06
PESIT-BSC-Education for the real world
05
PESIT SOUTHCAMPUS 179. Work out the multi level look-ahead carry scheme for doing a 32-bit number addition. How many gate delays are required to do the complete addition in this method? 180. Design a 16-bit adder using 4-bit ripple-carry adder blocks. Calculate the time required to generate the sum and output carry assuming a CUP frequency of 100 MHz. 181. Design a 16-bit adder using 4-bit carry-lookahead adder blocks. Calculate the time required to generate the sum and output carry assuming a CUP frequency of 100 MHz. Is there any improvement in performance?
10*
182. Write a note on IEEE standard for floating-point numbers.
08*
183. Write the complete logic diagram of 4-bit carry-lookahead adder. How many logic gates are required? 184. Using longhand methods, perform the operations AxB and A÷B on the given set of 5-bit unsigned numbers a) A = 10101, B = 00101 b) A = 11001, B = 01000
08
185. Multiply each of the following pairs of signed 2’s – complement numbers using Booth Algorithm. A is the multiplicand and B is the multiplier. What is your observation in each case?
08
a) A = 010111, B = 110110
b) A = 111000, B = 011111
c) A = 001110, B = 001110
d) A = 001101, B = 010101
186. Multiply each of the following pairs of signed 2’s – complement numbers using bit-paring of the multipliers. A is the multiplicand and B is the multiplier. What is your observation in each case? a) A = 010111, B = 110110
188. Show the sequential multiplication process for each of the following pairs of numbers. X is the multiplier and Y is the multiplicand.
06
10
08 06
b) X = 1110, Y = 0111
189. Perform the operation of division using a) restoring and b) non-restoring method on the following pairs of numbers. X is the divisor and Y is the dividend. a) X = 0101, Y = 11111
10
b) A = 111000, B = 011111
c) A = 001110, B = 001110 d) A = 001101, B = 010101 187. Using Booths multiplication algorithm multiply -13 and +107
a) X = 0101, Y = 1101
08
08
b) X = 1001, Y = 10010
190. Represent the following decimal numbers using IEEE standard floating point notation. PESIT-BSC-Education for the real world
08
PESIT SOUTHCAMPUS a) +1.725
b) –25.125
c) –0.08125
d) +45
191. The hexadecimal value of ∏ is 3.243F6A8885A308D3… Work out the IEEE standard representation (IEEE standard 754-1985) of ∏ in single and double precision formats.
10*
192. Give Booth’s algorithm to multiply two binary numbers. Explain the working of the algorithm taking an example. 193. Explain sequential binary multiplier with the help of a neat diagram
12*
194. Draw a circuit diagram for binary division and explain its operation
08
195. Perform the arithmetic operations below with binary numbers and with negative numbers in signed-2’s complement representation. Use seven bits to accommodate each number together with its sign. In each case, determine if there is an overflow by checking the carries into and out of the sign bit position. g. (+35) + (+40) h. (-35) + (-40) i. (-35) – (+40) 196. Prove that the multiplication of two n-digit numbers in base r gives a product no more than 2n digits in length. Show that this statement implies that no overflow can occur in the multiplication operation. 197. What decimal value does the binary word 1010 1111 0101 0100 have when it represents an a. unsigned integer b. 1’s complement integer c. 2’s complement integer d. sign-magnitude integer 198. Design a 3-bit carry lookahead adder and determine the maximum number of gates between any input and each of the four outputs (3 sum bits and a carry) 199. How many gate delays are there in the longest path from some input to some output of a 64-bit adder using 4-bit carry lookahead groups and a multiple level structure? Compare with the longest path for a 64-bit ripple carry adder. 200. List the rules for addition, subtraction, multiplication and division of floating point numbers.
06
201. Explain the IEEE standard for floating point number representation
08
202. Explain with diagram the design and working of a 4-bit look ahead carry adder circuit
10
BASIC PROCESSING UNIT
OBJECTIVE: A typical computing task consists of a series of steps specified by a sequence of machine instructions that constitute a program. In this chapter we focus on the processing unit, which executes machine instructions and coordinates the activities of other units. In this chapter we learn about the processor’s internal structure and how it performs the tasks of fetching, decoding, and executing instructions of a program, fundamental concepts- register transfer, PESIT-BSC-Education for the real world
06*
06
04
08 08
06
PESIT SOUTHCAMPUS execution of instruction, control unit–design of hardwired & microprogram sequencing, microinstruction with next–address field.
203. Why is the Wait-for-memory-function-completed step needed for reading from or writing to the main memory? 204. Assume that a memory read or write operation takes the same time as one internal processor step and that both the processor and the memory are controlled by the same clock. Estimate the execution time of this sequence. 205. Assume that propagation delays along the bus and through the ALU of figure 1 are 0.3 and 2 ns, respectively. The set up time for the registers is 0.2 ns and the hold time is 0. What is the minimum clock period needed? 206. Write the sequence of control steps required for the bus structure in figure 1 in each of the following instructions:
04 04
04
06
a) Add the immediate number NUM to register R1. b) Add the contents of memory location NUM to register R1. c) Add the contents of the memory location whose address is at memory location NUM to register R1. Assume that each instruction consists of two words. The first word specifies the operation and the addressing mode, and the second word contains the number NUM.
207.
Step 1
Action PCout , MARin , READ , Select4, Add, Zin 2
Zout , PCin ,Yin ,WMFC
3
MDRout , IRin
4
R3out , MARin , Read
5
R1out , Yin , WMFC
6
MDRout ,Select Y, Add, Zin
7
Zout , R1in , End
Consider the add instruction that has the control sequence given above. The processor is driven by a continuously running clock, such that each control step is 2 ns in duration how long will the processor have to wait in steps 2 and 5, assuming that a memory read operation takes 16 ns to complete? What percentage of time is the processor idle during execution of this PESIT-BSC-Education for the real world
06
PESIT SOUTHCAMPUS instruction? 208. Show the control steps for the Branch on Negative instruction for a processor with three-bus organization of the data path. (Refer figure 4) 209. The multiplexer and feed back connection in figure 2 eliminates the need for gating the clock input as a means of enabling and disabling register input. Using a timing diagram, explain the problems that may arise if clock gating were used. 210. Write a microroutine, such as the one shown below, for the instruction MOV
X (Rsrc), Rdst
when the source and destination operands are specified in index and register addressing modes respectively. Address
Microinstruction for Add (Rsrc)+, Rdst
(octal) 000
PCout , MARin , Read, Select4, Add, Zin
001
Zout , PCin , Yin , WMFC
002
MDRout , IRin
003
µBranch {µPC<--101 (from instruction decoder); µPC5,4
121
[IR10,9 ]; µPC3
[IR10 ] · [IR9 ] · [IR8]}
Rsrcout ,MARin, Read, Select4, Add, Zin
122
Zout , Rsrcin
123
µBranch {µPC
170
MDRout , MARin , Read, WMFC
171
MDRout ,Yin
172
Rdstout , SelectY, Add, Zin
173
Zout , Rdstin , End
PESIT-BSC-Education for the real world
170;µPC0
[IR8]}, WMFC
06 08
06
PESIT SOUTHCAMPUS 211. A BGT (Branch if>0) machine instruction has the expression Z+(N +V)=0 as its branch 08 condition, where Z, N and V are the zero, negative and overflow condition flags respectively. Write a microroutine that can implement this instruction. Show the circuitry needed to test the condition codes. 212. What are the advantages and disadvantages of hardwired and microprogrammed control?
06
213. Show the basic organization of a CPU in terms of registers and other units for a single bus data 08 path CPU. In such a CPU, show the complete action of the CPU in fetching and executing the instruction. 214. Explain single bus organization of the processor.
06
215. Discuss the internal and external operations performed in a computer system.
04
216. Discuss the need for gating signals with an example.
06
217. With the help of a neat sketch, explain three-bus organization of the processor.
06
218. Discuss how unconditional branching is taken into account in a control sequence.
04
219. Write the sequence of control steps required to perform the following operations in a single 06 bus structure. j. Add the contents of memory location NUM to register R1 and storing the result in NUM. k. Add an immediate number VALUE to register R1 and storing the result in R1. l. Add the contents of a memory location whose address is at memory location NUM to register R1. 220. Write the control sequence for the operation Sub R2, R3, R4 of the three-bus organization of a 04 processor. 221. Discuss the organization of hardwired control unit. 08 222. Describe the organization of microprogrammed control unit. Define the following terms: 10 microinstruction, microoperation, microroutine, control word and control store. 223. Describe how field encoding of microinstructions is implemented?
06
224. Discuss two types of microinstructions.
04
225. Write a microroutine for the instruction MOV X (Rsrc), Rdst.
06
226. Show the basic organization of a CPU in terms of registers and other units for a single bus data 10* path CPU. In such a CPU, show the complete action of CPU in fetching and executing the instruction.
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS Load R1 from memory data at A, where A is a memory address. Assume the instruction is in one process or word. Indicate the control signals to be used at each stage of execution. 227. Explain the basic concepts of micro programmed control.
10*
228. Show the control sequences for execution of Add (R3), R1 and explain.
06*
229. A computer has 32-bit instructions and 12-bit addresses. If there are 250 two-address 04 instructions, how many one-address instructions can be formulated? 230. A two-word instruction is stored in memory at an address designated by the symbol W. The 06 address field of the instruction (stored at W+1) is designated by the symbol Y. The operand used during the execution of the instruction is stored at an address symbolized by Z. An index register contains the value X. State how Z is calculated from the other addresses if the addressing mode of the instruction is m. Direct n. Indirect o. Relative p. Indexed 231. Perform the logic AND, OR and XOR with the two binary strings 10011100 and 10101010.
04
232. Write and explain the control sequences for execution of following instruction.
06
Add (R3), R1 233. With neat diagram, explain three bus organisation and write control sequence for the instruction
08
Add R1, R2, R3 234. What are the modifications required in the basic organization of a microprogrammed control unit to support conditional branching in the microprogram
04
235. Write the control sequences for execution of the following instructions.
10
i)Add (R3),R1. ii) unconditional branch instruction 236. With a diagram explain hard wired control, which shows separation of the decoding and encoding function.
10
237. Draw the diagram of floating point addition-subtraction unit and explain how to add or
10
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS subtract floating point numbers
238. Write. and explain the control sequences for execution of an unconditional
05
branch instruction. 239. Explain with block diagram the basic organization of a microprogrammed control unit.
10
240. What are the modifications required in the basic organization of a microprogrammed control 06 unit to support conditional branching in the microprogram.
Marks
No. of Questions
04
43
05
25
06
82
08
62
10
26
12
01
20
01
Total
240
PESIT-BSC-Education for the real world
PESIT SOUTHCAMPUS
PESIT-BSC-Education for the real world
