Computer Organization and Architecture 2021-22 question paper

The structure of a computer has four main components.

• Central processing unit (CPU): it controls the computer and does the data processing. It has the control unit, the ALU and the registers.
• Main memory: it stores the programs and data that the CPU is working on.
• Input/output (I/O): it moves data between the computer and the outside world, such as a keyboard, a disk or a display.
• System interconnection (system bus): it is the path that carries data, addresses and control signals between the CPU, the memory and the I/O.

In horizontal microprogramming each control signal has its own bit in the microinstruction. In vertical microprogramming the signals are grouped into fields and coded, and a decoder gives the signals.

The statement has two conditions, so it gives two register transfers. The first one occurs when $P = 1$. The second occurs when $P = 0$ and $Q = 1$, because the "else if" is checked only when the first condition fails.

$$P:\ R1 \leftarrow R2$$

$$P'Q:\ R1 \leftarrow R3$$

Here $P'$ means the complement (NOT) of $P$. The part before the colon is the control function. It must be 1 for the transfer to take place at the next clock pulse. If both $P = 0$ and $Q = 0$, no transfer happens and R1 keeps its old value.

A 4-bit incrementer adds 1 to a 4-bit number $A_3A_2A_1A_0$. We use four full adders in a ripple chain. The second input $B$ of every adder is tied to 0. The carry input of the first adder is tied to 1, and this 1 is what gets added.

 A3     A2     A1     A0
  |      |      |      |
[FA3]<-[FA2]<-[FA1]<-[FA0]<-- C0 = 1   (B inputs = 0)
  |      |      |      |
 S3     S2     S1     S0

The first adder gives $S_0 = \overline{A_0}$ and carry $A_0$, and the carry moves up the chain. The output is $A + 1$. The last carry shows that $A$ was $1111$.

In daisy chaining, the devices are connected in series on one grant line. The bus grant signal passes from the first device to the next. A device that has requested the bus stops the signal and takes the bus. So the priority depends on the position in the chain, and the closest device has the highest priority. It needs few wires but is slow.

In centralized parallel arbitration, each device has its own separate request and grant lines to a central arbiter. The arbiter looks at all the requests together and grants one. It is faster and more flexible in priority, but needs more lines and a more complex arbiter.

The transfer rate of a tape is the number of bits passing the read head per second. It equals the recording density times the tape speed.

$$\text{Transfer rate} = \text{density} \times \text{speed} = 1600 \times 120$$

$$\text{Transfer rate} = 192{,}000 \text{ bytes per second}$$

The eight tracks are read in parallel, so one bit from each track forms one byte at every position. Therefore the transfer rate is 192,000 bytes per second (about 1.54 million bits per second).

The register holds $A = 10011101$. The leftmost bit is the sign bit.

Arithmetic shift right. Every bit moves one place right, the sign bit is kept, and the lowest bit is lost. Therefore:

$$10011101 \rightarrow 11001110$$

This is the value $-99$ halved to $-50$.

Arithmetic shift left. Every bit moves one place left and a 0 enters at the right:

$$10011101 \rightarrow 00111010$$

The sign bit has changed from 1 to 0. This is an overflow, because the true result $-198$ does not fit in 8 bits. The overflow flag is set whenever the sign bit before the shift and the bit that replaces it are different.

An associative memory is also called content addressable memory (CAM). A word is found by its content, not by an address. The search key is compared with all stored words at the same time, and the matching word is returned.

Advantages: the search is very fast, because all words are checked in parallel, and no address is needed. It is useful for cache tags and page tables.

Disadvantages: every cell needs its own comparison logic, so it is costly, takes more space, and is built only in small sizes.

SRAM and DRAM are both volatile semiconductor memories, but they differ as follows.

The instruction format depends on the number of address fields. The types are:

• Three-address: ADD R1, R2, R3. Two sources and one destination.
• Two-address: ADD R1, R2. The result replaces the first operand.
• One-address: ADD X. The other operand and the result are in the accumulator.
• Zero-address: ADD. Operands are on the stack, as in a stack machine.

Each format holds an opcode and zero to three operand fields. More addresses make the program short, but each instruction long.

In a multiplexer bus, there is one multiplexer for each bit of the bus. All the registers feed their bits into these multiplexers, and a common set of select lines decides which register is put on the bus. The question gives 8 registers of 16 bits each.

I. Select inputs in each multiplexer

A multiplexer must be able to choose any one of the 8 registers. The number of select lines $k$ must satisfy $2^k \geq 8$.

$$2^k = 8 \Rightarrow k = \log_2 8 = 3$$

Therefore each multiplexer has 3 select inputs. The same 3 lines are connected to all multiplexers, so the 3-bit code selects the same register in every bit position.

II. Size of the multiplexers

Each multiplexer takes one bit from each of the 8 registers, so it has 8 data inputs and one output. The size of each multiplexer is 8 to 1, which is written as $8 \times 1$. It is also called an 8-to-1 line multiplexer.

III. Number of multiplexers

The bus carries 16 bits, because each register has 16 bits. We need one multiplexer for each bit.

$$\text{number of multiplexers} = 16$$

Multiplexer 0 takes bit 0 of all 8 registers, multiplexer 1 takes bit 1 of all registers, and so on up to multiplexer 15.

 R0..R7 (16 bits each)
  bit15 of R0..R7 --> [MUX 15 8x1] --+
  ...                                |--> 16-bit bus
  bit 0 of R0..R7 --> [MUX  0 8x1] --+
        S2 S1 S0 (common select lines)

Check of the totals

The total number of data inputs to all the multiplexers is $16 \times 8 = 128$. This is the same as the total number of register bits, $8 \times 16 = 128$. So every register bit is connected to exactly one multiplexer input.

Working of the bus

Suppose the select code is $S_2S_1S_0 = 101$. This chooses register R5. All 16 bits of R5 appear on the bus at the same time. If the load input of register R2 is also enabled, then at the next clock pulse the transfer $R2 \leftarrow R5$ takes place.

Select lines and their register:

Only one register can drive the bus at any moment, so there is no conflict. This is the main advantage of the multiplexer bus. Its disadvantage is the large number of gates. Here we need 16 multiplexers of size 8 to 1.

Therefore the bus needs 3 select inputs per multiplexer, 8-to-1 multiplexers, and 16 multiplexers in all.

In asynchronous data transfer, the source and the destination units have independent clocks. They must therefore use control signals to agree on when data is valid and when it has been taken. Handshaking uses two control lines, one in each direction. In destination-initiated transfer, the destination starts the exchange by saying that it is ready to receive data.

Control lines

• Ready for data: this line goes from the destination to the source. It tells the source that the destination is ready to take a word.
• Data valid: this line goes from the source to the destination. It tells the destination that the data on the bus is valid.

        data bus (8 or 16 lines)
  +--------+ ===================> +-------------+
  | Source |   data valid  ------> | Destination |
  |  unit  | <------ ready for data|    unit     |
  +--------+                       +-------------+

Sequence of events

The destination first activates "ready for data". This shows that it wants a word and has room for it.

When the source sees ready for data, it places the data word on the data bus. After the data has settled, it activates "data valid".

The destination sees data valid and knows that the bus holds a good word. It latches the word into its register.

After latching the data, the destination removes "ready for data". This tells the source that the word has been taken.

The source sees ready for data go low. It removes the data from the bus and also disables "data valid".

The system is now back in the starting state. The destination can raise ready for data again to ask for the next word.

Timing diagram

 Ready for data  __|‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾|________
 Data valid      ______|‾‾‾‾‾‾‾‾‾‾|________
 Data bus        ______<==valid====>________
                  1     2    3     4    5

Here 1 is where the destination asks, 2 is where the source puts data and data valid, 3 is where the destination latches the data, 4 is where ready for data is removed, and 5 is where the source removes data valid and data.

Why this is reliable

Each signal change is a reply to the other unit's signal change. The source does not drop the data until the destination says it has taken it. The destination does not take the data until the source says it is valid. So no word is lost or read twice, whatever the speeds of the two units.

Compared with the source-initiated method

In source-initiated handshaking the source starts with data valid, and the destination answers with data accepted. In the destination-initiated method, the receiver controls the pace. The source cannot send before it is asked. This is useful when the receiver, such as a slow printer, is the one that knows when it can accept data.

Use

Parallel interfaces such as Centronics printer ports, and many bus protocols, use this style of handshake. A time-out circuit can be added to signal an error if the other unit never replies.

An array multiplier forms all partial products at the same time with AND gates, and then adds them with an array of adders. Let the multiplicand be $A = a_1a_0$ and the multiplier be $B = b_1b_0$. The product $P = p_3p_2p_1p_0$ has 4 bits.

Each partial product bit is one AND gate: $a_0b_0$, $a_1b_0$, $a_0b_1$ and $a_1b_1$. They are arranged like paper multiplication:

Column $2^0$ has one bit, so $p_0 = a_0b_0$. Column $2^1$ has two bits, which a half adder (HA1) adds: the sum is $p_1$ and the carry $c_1$ goes to the next column. Column $2^2$ has $a_1b_1$ and $c_1$, which a second half adder (HA2) adds: the sum is $p_2$ and the carry is $p_3$.

$$p_0 = a_0b_0 \qquad p_1 = a_1b_0 \oplus a_0b_1$$

$$p_2 = a_1b_1 \oplus (a_1b_0 \cdot a_0b_1) \qquad p_3 = a_1b_1 \cdot a_1b_0 \cdot a_0b_1$$

 a1b0 a0b1        a0b0 ----------------------> p0
   \   /
   [HA1] --sum-----------------------------> p1
     | c1
 a1b1 +--> [HA2] --sum----------------------> p2
              \--carry---------------------> p3

The circuit needs 4 AND gates and 2 half adders. For $A = 11$ and $B = 11$ (that is $3 \times 3$), the four AND outputs are all 1. Then $p_0 = 1$, $p_1 = 0$ with $c_1 = 1$, $p_2 = 1 \oplus 1 = 0$ and $p_3 = 1$. The product is $1001 = 9$.

Flowchart for division of signed magnitude numbers. The sign and the magnitude are handled separately. The dividend is in $A$ and $Q$ joined, the divisor is in $B$, and the sign bits are $A_s$, $B_s$ and $Q_s$.

 START
   |
 Qs = As xor Bs ; SC = n-1
   |
 EA = A + (not B) + 1       (try A - B)
   |
 E = 1 ?--yes--> DIVIDE OVERFLOW (stop)
   | no
 shift left AQ ; EA = A + (not B) + 1
   |
 E = 1 ? --yes--> Qn = 1 ; A = EA
   | no
 Qn = 0   (A stays, so no restore needed)
   |
 SC = SC - 1 ; SC = 0 ? --no--> back to shift
   | yes
 END : Q = quotient, A = remainder

The first subtraction checks that the quotient fits in $n$ bits. If $A \ge B$ already, the divide overflows. After that, each cycle shifts left, subtracts $B$ by adding its 2's complement, and checks the carry $E$. A carry of 1 means the subtraction succeeded, so the quotient bit is 1 and $A$ takes the new value. A carry of 0 means it failed, so the quotient bit is 0 and $A$ keeps its old value. After $n-1$ cycles $Q$ holds the quotient and $A$ the remainder. The quotient sign is $A_s \oplus B_s$, and the remainder takes the sign of the dividend.

Main memory is $64\text{K} \times 16$. Since $64\text{K} = 2^{16}$, the memory address has 16 bits and each word is 16 bits wide. The cache has 1K words, so it has $1\text{K} = 2^{10}$ words. A block holds 4 words.

In direct mapping, the address is split into a tag, an index and a word field. The index selects the cache location. The tag is stored with the data and is compared to find a hit.

I. Address fields

The word field selects one of 4 words in a block, so it has $\log_2 4 = 2$ bits. The cache has $1024 / 4 = 256$ blocks, so the block field has $\log_2 256 = 8$ bits. Together the word and block fields form the index of 10 bits, as the cache has 1K words. The tag takes the remaining bits:

$$\text{tag} = 16 - 10 = 6 \text{ bits}$$

So the address format is

The total is $6 + 8 + 2 = 16$ bits.

II. Bits in each cache word

Each cache word stores the 16-bit data, the 6-bit tag of the block it belongs to, and 1 valid bit. The valid bit tells whether the word holds real data or is still empty after power on. So

$$16 + 6 + 1 = 23 \text{ bits}$$

The 16 bits are the data, 6 bits are the tag used for the hit check, and 1 bit is the valid flag. The whole cache is therefore $1\text{K} \times 23$ bits.

III. Number of blocks

$$\text{blocks} = \frac{1024 \text{ words}}{4 \text{ words per block}} = 256$$

The cache can hold 256 blocks. Main memory has $65536 / 4 = 16384$ blocks, so every cache block is shared by $16384/256 = 64$ memory blocks. These 64 blocks differ only in their tag value.

The tag is stored along with the data so that the cache can tell which of the 64 memory blocks is now present at an index. Without the tag, two different memory blocks with the same index could not be told apart. A new block replaces the old one directly, because direct mapping gives only one possible place.

Working example

Take the address $\text{0x1234}$. Its upper 6 bits give tag $= 4$. The next 8 bits give block number $= 141$, and the last 2 bits give word $= 0$. The cache looks at index $564$ (block 141, word 0). If the valid bit is 1 and the stored tag is 4, it is a hit and the word is sent to the CPU. Otherwise it is a miss. The whole 4-word block is then read from main memory, and the tag is updated to 4.

In a microprogrammed control unit, the control memory holds the microinstructions. The control address register (CAR) gives the address to read. The address selection circuit, also called the sequencer, decides what goes into CAR next, so that the microinstructions run in the right order.

Parts of the circuit

• Multiplexer (MUX): it selects one of four possible next addresses.
• Incrementer: gives CAR plus one.
• Branch logic: tests the status bits chosen by the microinstruction and decides whether a branch is taken.
• Mapping logic: converts the opcode from the instruction register into a starting address.
• Subroutine register (SBR): stores the return address of a micro-subroutine.
• Control memory: a ROM that holds the microinstructions. It is read at the address in CAR.

How the next address is selected

The select lines of the multiplexer come from the branch logic. It gives four ways to choose the address.

1. Increment: CAR becomes $CAR + 1$. This is the normal flow, when the condition is false or no branch is wanted.
2. Branch: the address field of the microinstruction is loaded into CAR when the tested status bit is true. It is either a conditional or an unconditional jump.
3. External mapping: after the fetch routine, the opcode bits of the instruction are mapped to the first address of the routine that executes it. This is the way a machine instruction starts its microprogram.
4. Subroutine call and return: on a call, the return address is saved in SBR and the branch address is loaded in CAR. On a return, SBR is copied back into CAR.

Mapping example. Let the opcode be 4 bits and let each routine be allowed 4 microinstructions. Then the address is formed as 0, then the opcode, then 00. For opcode 1010 the address is 0101000, that is 40. If the opcode changes by one, the starting address changes by four, so the routines do not overlap. A 7 bit CAR can address $2^7 = 128$ words.

Working in sequence. The microinstruction read from the control memory has a condition field, a branch field and an address field. The condition field selects one status bit. The branch field tells the MUX what to choose when that bit is true. If the bit is false, the incrementer path is taken. At the next clock pulse the chosen address is stored in CAR, and the next microinstruction is read.

This arrangement lets the microprogram do loops, tests and calls, so complex instructions can be built from simple micro-steps without extra hardware for each.

Why this design is used. The same small circuit supports straight-line flow, loops, tests and shared micro-subroutines. For example, the routine that finds an indirect operand address is written once, and many instruction routines call it. This saves control memory. The cost is only a few extra gates and one register, so address selection stays cheap and fast.

(I) Biased representation of exponents

A 7-bit exponent field holds $2^7 = 128$ values, from 0 to 127. With bias 64, the stored value is the true exponent plus 64:

$$E = e + 64$$

The true exponents $-64$ to $+63$ are therefore stored as 0 to 127. The list runs in order, so each exponent has the 7-bit binary form of $e + 64$. Some key values:

All the other exponents follow the same rule. Negative exponents begin with 0 and non-negative exponents begin with 1.

(II) Addition of exponents

Let the two true exponents be $e_1$ and $e_2$. Their biased forms are $E_1 = e_1 + 64$ and $E_2 = e_2 + 64$. Adding the stored values gives:

$$E_1 + E_2 = e_1 + e_2 + 128$$

The correct biased sum of the exponents must be $(e_1 + e_2) + 64$. The result above is 64 too large. So we subtract 64:

$$E_1 + E_2 - 64 = e_1 + e_2 + 64$$

This is the biased form of $e_1 + e_2$. This is the exponent step in floating point multiplication.

(III) Subtraction of exponents

Subtracting the stored values gives:

$$E_1 - E_2 = (e_1 + 64) - (e_2 + 64) = e_1 - e_2$$

The bias has cancelled out. But the biased form of $e_1 - e_2$ must be $(e_1 - e_2) + 64$. The result is 64 too small, so we add 64:

$$E_1 - E_2 + 64 = (e_1 - e_2) + 64$$

This is the exponent step in floating point division.

Check with numbers. Take $e_1 = 5$ and $e_2 = -3$. Then $E_1 = 69$ and $E_2 = 61$. The sum is $69 + 61 - 64 = 66 = 2 + 64$, which is the biased form of $5 + (-3) = 2$. The difference is $69 - 61 + 64 = 72 = 8 + 64$, which is the biased form of $5 - (-3) = 8$. Both agree. The result is valid only if the true result stays between $-64$ and $+63$. Otherwise there is exponent overflow or underflow.

This is why a biased exponent is useful. All stored exponents are plain positive numbers, so the sign of the exponent never needs special handling. The only extra work is the single correction of 64 after each addition or subtraction, which is a cheap operation for the hardware.

We need 5-bit registers, because $-15$ needs 5 bits in 2's complement. The numbers are:

$$M = +13 = 01101 \qquad -M = 10011 \qquad Q = -15 = 10001$$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In each cycle, we look at $Q_0$ and $Q_{-1}$. The pair $10$ means $A = A - M$ (we add $-M$). The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. Then $A$, $Q$ and $Q_{-1}$ shift one place right as a whole, and the sign bit of $A$ is copied (arithmetic shift right, ASR). There are 5 cycles, one for each multiplier bit.

The product is in $AQ$ joined:

$$AQ = 1100111101$$

The leading bit is 1, so the result is negative. Take the 2's complement to find its size:

$$\overline{1100111101} + 1 = 0011000010 + 1 = 0011000011 = 195$$

Therefore $(+13) \times (-15) = -195$.

We can also read $AQ$ directly as a 10-bit signed number, where the leftmost bit has the weight $-512$:

$$-512 + 256 + 32 + 16 + 8 + 4 + 1 = -195$$

The shift is an arithmetic shift, so the sign of the partial product is never lost. When $A - M$ makes $A$ negative, the copied sign bit keeps it negative after the shift.

The method works because the pairs of bits turn the multiplier into signed digits. Here $Q = 10001$ becomes the digits $-1$ at bit 0, $+1$ at bit 1 and $-1$ at bit 4, so its value is:

$$-16 + 2 - 1 = -15$$

In the table, cycle 1 subtracts $M$ (digit $-1$), cycle 2 adds $M$ (digit $+1$), and cycle 5 subtracts $M$ again, but now it counts $16$ times as much because of the shifts. The cycles 3 and 4 only shift. Adding these shifted copies of $M$ gives $13 \times (-15)$.

The check is $13 \times 15 = 195$ and the signs differ, so the sign is negative. The result agrees.

A three-state buffer is a gate that has three output states: logic 0, logic 1, and high impedance. In the high-impedance state the output is disconnected, as if the gate were not there. A control input decides this. When the control input is 1, the buffer passes its input to the output. When the control input is 0, the output is in high impedance.

Because a disabled buffer does not affect the line, the outputs of many buffers can be joined to one wire. We only need to make sure that one buffer is enabled at a time. That is how a common bus is formed without multiplexers.

Bus with four registers

Take four registers A, B, C and D of 4 bits each. For every register there is a group of four 3-state buffers, one for each bit. The outputs of the four buffers of the same bit position are tied together to make that bit of the bus. A 2-to-4 decoder produces the enable signals. Its two inputs $S_1S_0$ select the register, and each of its four outputs enables the group of buffers of one register.

 S1 S0 --> [ 2-to-4 DECODER ]
            |   |   |   |
           E_A E_B E_C E_D   (enable of each buffer group)
            |   |   |   |
          [buf][buf][buf][buf]   4 buffers per register
            ^   ^   ^   ^
            A   B   C   D        (registers)
            |   |   |   |
            +---+---+---+--->  4-bit common bus

Working

The decoder makes exactly one of its outputs 1 for each value of $S_1S_0$.

Suppose $S_1S_0 = 01$. Only the buffers of B are enabled. Their outputs show the bit values of B on the bus. The buffers of A, C and D are in high impedance, so they do not affect the bus. The data on the bus can then be loaded into any register whose load input is enabled at the clock pulse.

Care is needed in the design. If two groups of buffers were enabled together, two different values would try to drive the same wire. This is a bus conflict, and it can damage the circuit. The decoder prevents it, because it never enables more than one output at a time.

Comparison with the multiplexer bus

A multiplexer bus needs one multiplexer for every bit. A three-state bus replaces the set of multiplexers by buffers and a single decoder. For 8 registers of 16 bits, the multiplexer method needs sixteen 8-to-1 multiplexers. The buffer method needs 128 buffers and one 3-to-8 decoder.

The three-state method also has an important advantage: the bus can be extended simply by connecting one more set of buffers. It is easy to build in integrated circuits, and it can carry data in both directions. Real computer buses use this idea.

In a single bus system, all the units share one bus, so only one transfer can take place in a clock cycle. This makes it slow. In a multiple bus organization, the CPU has two or three internal buses, so that more than one transfer can take place at the same time.

Three-bus organization of the CPU

The common design has bus A, bus B and bus C. The registers are in a register file with two read ports and one write port. Bus A and bus B carry the two source operands from the register file to the two inputs of the ALU. Bus C carries the ALU result back to the register file.

  +--------------------------------+
  |        Register file R0..Rn    |
  +--+--------------+----------^---+
     |A bus         | B bus    | C bus
     v              v          |
   +---------------------+     |
   |         ALU         |-----+
   +---------------------+

The program counter, the instruction register, the memory address register and the memory data register also connect to these buses, as needed.

Working

In one clock cycle, two registers are read onto bus A and bus B, the ALU adds them, and the result is written to a third register through bus C. For example, ADD R4, R1, R2 with $R4 \leftarrow R1 + R2$ needs only one clock step. In a single bus system, the same instruction needs three steps. First R1 is moved to a temporary register, then R2 is put on the bus and added, and then the result is moved to R4.

Advantages

• Fewer clock cycles per instruction, so the program runs faster.
• Two operands can be read at the same time.
• No temporary registers such as the Y register are needed for ALU inputs.
• It supports pipelining more easily.

Disadvantages

• More wires and more control signals are needed.
• The hardware and the cost are higher.
• The control unit becomes more complex.

Example of the saving

Take the three instructions ADD R4, R1, R2, SUB R5, R4, R3 and MUL R6, R5, R1. On a three-bus CPU each of them needs one data-path step, so three steps in all. On a single bus CPU, each needs about three steps, so nine steps in all. The three-bus design is therefore about three times faster for this short program, although the real gain depends on the program and the instruction mix.

Other multiple bus use

At the system level, there may be separate buses for memory and for I/O, or separate address, data and control buses. Some systems also have a fast local bus for the CPU and the cache, and a slower expansion bus for devices, joined by a bridge. The slow devices then do not delay the fast ones.

So multiple bus organization improves the performance of the processor by allowing parallel transfers, at the price of a higher cost and more complex control.

This is a segmented-paged system. The logical address is divided into a segment number, a page number and a word number. The physical address is divided into a block number and a word number.

Logical address format

There are 128 segments, so the segment field needs $\log_2 128 = 7$ bits. Each segment has up to 32 pages, so the page field needs $\log_2 32 = 5$ bits. Each page has 4K words, so the word field needs $\log_2 4096 = 12$ bits. The logical address is

$$7 + 5 + 12 = 24 \text{ bits}$$

Physical address format

Physical memory has 4K blocks, so the block field needs $\log_2 4096 = 12$ bits. Each block has 4K words, so the word field needs 12 bits. The physical address is

$$12 + 12 = 24 \text{ bits}$$

Check of sizes

The logical space is $128 \times 32 \times 4096 = 2^{24}$ words. The physical memory is $4096 \times 4096 = 2^{24}$ words. Both are 16M words.

The two sizes can also be seen as counts. The logical space has $128 \times 32 = 4096$ pages in total, and the physical memory has 4096 blocks. So each logical page can in the best case have its own block, but a program uses far fewer pages than this at one time.

How the mapping works

The page size and the block size are both 4K words, so the 12 word bits are copied unchanged from the logical address to the physical address. Only the segment and page numbers must be translated into a block number.

The segment number selects an entry in the segment table. That entry gives the address of the page table of that segment. Each segment has its own page table with 32 entries. The page number selects an entry in this page table, and the entry holds a 12-bit block number. This block number is joined with the 12-bit word to give the physical address.

 Logical: [ Segment 7 ][ Page 5 ][ Word 12 ]
              |            |          |
        Segment table   Page table    |
              |------->  (32 entries) |
                          |           |
 Physical:           [ Block 12 ][ Word 12 ]

The mapping needs two table reads, one in the segment table and one in the page table, so it is slower than plain paging. A TLB is used to keep the recent translations and avoid these reads. Protection bits in the segment table also allow each segment to be marked read only or executable.

For example, if the entry of page 3 in the page table of segment 5 holds block 100, then the logical address (segment 5, page 3, word 20) maps to physical block 100 with word 20.

(a) Mapping of a virtual address to a physical address

A virtual (logical) address is the address made by the program. It must be changed to a physical address in main memory. This is done by the memory management unit (MMU) with the help of a page table. The virtual address is divided into a page number and an offset. The page table is stored in main memory. It has one entry for each page, and the entry holds the frame (block) number and a valid bit.

The page number is used as an index into the page table. If the valid bit is 1, the frame number is read from the entry. This frame number is joined with the offset to make the physical address. The offset is copied unchanged, because pages and frames have the same size. If the valid bit is 0, a page fault occurs and the operating system loads the page from disk.

A page table lookup costs one more memory access. So a small and fast memory called the translation lookaside buffer (TLB) holds the recent page-to-frame translations. The MMU looks at the TLB first. A TLB hit gives the frame number at once, and only a TLB miss needs the page table.

 Virtual address [ page no. | offset ]
                      |          |
                    TLB / page table
                      |          |
 Physical address [ frame no. | offset ]

(b) Methods of writing into cache

When the CPU writes, the cache and the main memory can become different. Two main policies solve this.

Write-through. Every write goes to the cache and to main memory at the same time. Main memory always holds the latest data, so it is simple and safe for I/O devices and multiple processors. The disadvantage is that every write is slow because it uses the main memory, and it creates a lot of bus traffic. A write buffer is often used to hide this delay.

If a program changes the same variable 100 times, write-through sends 100 writes to main memory. The next policy sends just one.

Write-back (copy-back). A write goes only to the cache, and the block is marked dirty with a modified bit. Main memory is updated only when the dirty block is removed from the cache. This gives fewer memory writes and faster operation: the 100 changes above cost only one write, made when the block is replaced. The disadvantage is that main memory may hold old data for some time, so it is more complex to keep consistent.

When a write misses, there are two choices. In write-allocate, the block is first brought into the cache, and then written. In no-write-allocate, the data is written straight to main memory. Write-back is usually used with write-allocate, and write-through with no-write-allocate.

(a) Communication of the buses with memory and I/O

A computer has three buses: the address bus, the data bus and the control bus. The CPU uses them to talk to both memory and I/O devices. There are two ways to connect I/O devices to the buses.

In the first way, there is one common set of buses for both memory and I/O, with separate read and write lines for I/O. This is isolated I/O. The CPU puts an address on the address bus. A control signal tells whether this address is for memory or for an I/O port. Memory and the interfaces both listen to the address, but only the selected one answers.

In the second way, memory and I/O share the same address space and the same read and write lines. This is memory mapped I/O. An address decoder decides whether the address belongs to memory or to an I/O register.

In both cases, the CPU does the following for a write. It places the address on the address bus and the data on the data bus. Then it activates the write signal on the control bus. The selected memory cell or I/O register latches the data. In a read, the selected unit puts its data on the data bus after the read signal.

Each I/O interface has an address decoder, data and control registers, and logic that connects it to the buses. In this way, the same buses serve both memory and I/O.

(b) CPU and IOP communication

An Input Output Processor (IOP) is a small processor with its own instruction set, made only for I/O work. It takes over the I/O job from the CPU and communicates with the memory by DMA.

        +-----+      +--------+
        | CPU |      | Memory |
        +--+--+      +---+----+
           |             |
  ==========+=============+=========== Memory bus
                 |
             +---+---+
             |  IOP  |
             +---+---+
   ====+=======+=======+=======+==== I/O bus
       |       |       |       |
    +--+--+ +--+--+ +--+--+ +--+--+
    | PD1 | | PD2 | | PD3 | | PD4 |
    +-----+ +-----+ +-----+ +-----+

The CPU does not start the I/O itself. The sequence is as follows.

The CPU first sends an instruction to the IOP to test the status of the IOP. If the IOP is free, the CPU sends a start instruction. This instruction tells the IOP where the I/O program is in memory.

The IOP then fetches its own program (made of commands that say which device, which operation, how many words and where in memory). It runs these commands, and moves data between the devices and memory by cycle stealing.

When the IOP finishes, it sends an interrupt to the CPU. The CPU then reads the status word of the IOP, which tells whether the operation was completed without error. Based on this, the CPU decides what to do next.

The CPU is free for the full time between starting the IOP and receiving the interrupt, so it can work on other programs. This arrangement is used in large mainframes, where many fast devices are active together.

When two units such as the CPU and an I/O interface do not share a common clock, they exchange data by asynchronous transfer. The sender must show when the data is valid, and the receiver must show that it has accepted it. For this purpose, two methods are used: strobe control and handshaking.

Method 1: Strobe control

A single control line, called the strobe, times the transfer. It is driven by one of the two units.

Source-initiated strobe. The source puts the data on the bus. After a short delay, it activates the strobe. The destination latches the data on the strobe. Then the source disables the strobe and later removes the data. For example, the CPU writes to a port in this way.

Destination-initiated strobe. The destination activates the strobe to request data. The source puts the data on the bus in reply. The destination latches the data and removes the strobe. The source then removes the data. For example, the CPU reads from a port in this way.

The weak point is that there is no reply. In the source-initiated case, the source cannot know whether the destination took the data. In the destination-initiated case, the destination cannot know whether the source has put valid data.

Source-initiated        Destination-initiated
 Data   =<valid>=        Data   ====<valid>=
 Strobe __|‾‾|___        Strobe __|‾‾‾‾‾|___
 (source -> dest)        (dest -> source)

Method 2: Handshaking

Handshaking adds a second control line so that each unit acknowledges the action of the other. Both signals change in a fixed order, so there is no doubt.

Source-initiated handshaking. Lines are "data valid" (source to destination) and "data accepted" (destination to source). The source puts data on the bus and enables data valid. The destination accepts the data and enables data accepted. The source sees this, disables data valid and removes the data. The destination then disables data accepted.

Destination-initiated handshaking. Lines are "ready for data" (destination to source) and "data valid" (source to destination). The destination enables ready for data. The source puts the data and enables data valid. The destination latches the data and disables ready for data. The source then disables data valid.

Time-out

If one unit fails, the other waits forever. A time-out circuit is added, which sets an error flag when a reply does not arrive within a set time.

Comparison of the methods

In short, strobe is simple but blind, while handshaking is a little more costly but safe for any pair of units. Most practical interfaces use handshaking.

In a stack organized computer with zero-address instructions, the arithmetic instructions have no address field. They take their operands from the top two items of the stack and push the result back. Only PUSH and POP name a memory address. So we first write the expression in reverse Polish notation (RPN), where each operator comes after its operands.

The expression is $X = (A-B) * (((C - D * E) / F) / G)$. We convert it by taking the innermost bracket first.

$$A - B \rightarrow AB-$$

$$D * E \rightarrow DE*$$

$$C - DE \rightarrow CDE-$$

$$(C-DE)/F \rightarrow CDE-F/$$

$$((C-DE)/F)/G \rightarrow CDE-F/G/$$

The last operation is the product of the two big brackets.

$$AB-;CDE*-F/G/;*$$

I checked this RPN with a small program. Each letter of the string becomes a PUSH, and each operator becomes one instruction. The program is:

PUSH A      ; stack: A
PUSH B      ; stack: A, B
SUB         ; stack: (A-B)
PUSH C      ; stack: (A-B), C
PUSH D      ; stack: (A-B), C, D
PUSH E      ; stack: (A-B), C, D, E
MUL         ; stack: (A-B), C, (D*E)
SUB         ; stack: (A-B), (C-D*E)
PUSH F      ; stack: (A-B), (C-D*E), F
DIV         ; stack: (A-B), ((C-D*E)/F)
PUSH G      ; stack: (A-B), ((C-D*E)/F), G
DIV         ; stack: (A-B), (((C-D*E)/F)/G)
MUL         ; stack: (A-B)*(((C-D*E)/F)/G)
POP X       ; X <- result

Each SUB, DIV and MUL takes the top item as the second operand and the item below it as the first operand. For example, at the first SUB the top is $DE$ and below it is $C$, so the result is $C - DE$ and not the reverse.

Why the order matters

The operands of a subtraction or a division must be pushed in the right order. The first operand goes in first, so that it lies below the second operand. If $F$ were pushed before the bracket $C - DE$ is complete, the division would give $F/(C-DE)$ instead of the intended one. The RPN form takes care of this automatically.

Check with numbers

Let $A=10, B=4, C=20, D=2, E=3, F=7, G=2$. The stack program works as follows.

$$A-B = 10-4 = 6$$

$$DE = 6,\quad C-DE = 20-6 = 14$$

$$14/F = 14/7 = 2,\quad 2/G = 2/2 = 1$$

$$6 \times 1 = 6$$

The direct calculation of $(10-4)(((20-23)/7)/2)$ also gives 6, so the program is right.

The program has 14 instructions, of which 7 are PUSH, one is POP and 6 are arithmetic. The arithmetic instructions are short because they need no address. The stack never holds more than 4 items at once. This is how a stack computer runs an expression without using any general registers.

Therefore the required program is the 14 instruction sequence given above, ending with POP X. Reading it again from the top, the first three lines compute the value of $(A-B)$, the next nine lines compute the big bracket on the right, and the last MUL joins them.

Hardwired versus microprogrammed control

Control steps for R1 <- R2 * (R3) on a single bus

The instruction means: take the number stored in memory at the address held in R3, multiply it by R2, and put the product in R1. On a single bus architecture, only one register can put data on the bus at a time. So the ALU keeps one input in the temporary register Y, takes the other from the bus, and stores the result in register Z. The control steps are as follows.

1. $PC_{out}$, $MAR_{in}$, Read, Select 4, Add, $Z_{in}$. This starts the fetch. The address of the instruction goes to the memory address register, and PC plus 4 goes into Z.
2. $Z_{out}$, $PC_{in}$, $Y_{in}$, WMFC. PC is updated, and the CPU waits for the memory function to complete.
3. $MDR_{out}$, $IR_{in}$. The fetched instruction is moved from the memory data register to the instruction register. Now the instruction is decoded.
4. $R3_{out}$, $MAR_{in}$, Read. The address of the operand, held in R3, goes to MAR and a memory read is started.
5. $R2_{out}$, $Y_{in}$, WMFC. R2 is placed in Y, and the CPU waits until the operand arrives in MDR.
6. $MDR_{out}$, Select Y, Multiply, $Z_{in}$. The ALU multiplies Y with the operand from the bus, and the product is saved in Z.
7. $Z_{out}$, $R1_{in}$, End. The product is moved into R1, and the instruction is complete.

Steps 1 to 3 are the fetch part, which is the same for every instruction. Steps 4 to 7 are the execute part. In a hardwired unit, these signals are produced by gates driven by the step counter, while in a microprogrammed unit each step is one microinstruction.

Using the sequence. Seven control steps mean seven clock cycles for this one instruction. If the memory is slow, the two WMFC steps (wait for memory function complete) make the CPU stall until the data is ready. On a multi-bus architecture, some of these steps could be joined, so fewer cycles are needed. That is why single bus designs are simple and cheap but slower.

Short note on the choice. The table shows that hardwired control suits fast and simple machines, while microprogrammed control suits machines with many complex instructions. Many processors use both.