Computer Organization (old course)

Initial values: $AR = 10001010$, $BR = 11100011$, $CR = 00001111$, $DR = 11111110$.

1. $AR \leftarrow AR + BR$

$10001010 + 11100011 = 1\,01101101$. The carry out is discarded, so $AR = 01101101$.

2. $CR \leftarrow CR \wedge DR,\ BR \leftarrow BR + 1$ (both happen in the same clock pulse)

$CR = 00001111 \wedge 11111110 = 00001110$

$BR = 11100011 + 1 = 11100100$

3. $AR \leftarrow AR - CR$

$01101101 - 00001110 = 01011111$ (that is, $109 - 14 = 95$).

Final values:

Initial: $A = 0010$, $B = 0111$, $C = 1000$, $D = 1111$.

1. $A \leftarrow A + C$: $0010 + 1000 = 1010$, so $A = 1010$.
2. $C \leftarrow C \wedge D$ and $D \leftarrow D + 1$ occur in the same clock, using the old values:
   • $C = 1000 \wedge 1111 = 1000$
   • $D = 1111 + 1 = 10000$, truncated to 4 bits, $D = 0000$ (carry lost).
3. $A \leftarrow A - B$: $1010 - 0111 = 0011$ (10 - 7 = 3), so $A = 0011$.

Final values:

An arithmetic right shift keeps the sign bit and shifts the other bits right.

$A = 10011100 \Rightarrow$ after ashr $A = 11001110$.

Assume the micro operations on separate lines execute one after another, and that those on the same line execute simultaneously (in the same clock pulse, using the old register values). Carries out of bit 8 are discarded.

Initial values: AR = 11110010, BR = 11111111, CR = 10111001, DR = 11101010.

Step 1: $AR \leftarrow AR + BR$

$11110010 + 11111111 = 1\,11110001$

so AR = 11110001 (carry discarded).

Step 2: $CR \leftarrow CR \vee DR,\; BR \leftarrow BR + 1$

$CR = 10111001 \vee 11101010 = 11111011$

$BR = 11111111 + 1 = 00000000$

Step 3: $AR \leftarrow AR + CR,\; DR \leftarrow DR + 1$

$AR = 11110001 + 11111011 = 1\,11101100 \Rightarrow 11101100$

$DR = 11101010 + 1 = 11101011$

Final values:

In an arithmetic right shift the sign bit is kept and copied into the next position, and the least significant bit is lost.

$A = 11011101 \to 11101110$

Arithmetic shift right keeps the sign bit and shifts the other bits right by one.

$A = 11101010 \;\Rightarrow\; A = 11110101$

The sign bit $1$ is replicated and the LSB $0$ is lost. (In decimal, $-22 \to -11$.)

Locality of reference is the tendency of a program to access, over a short time interval, only a small localized set of memory addresses repeatedly (temporal locality: recently used items are used again; spatial locality: nearby addresses are used soon). Cache memory exploits this property.

Associative memory (content addressable memory, CAM) is a memory accessed by the content of the data rather than by an address. The search key is compared with all stored words simultaneously and the matching word(s) are returned, which makes searching very fast.

The Input-Output Processor (IOP) is a processor with its own memory and instruction set that handles I/O transfers directly with memory (DMA) and communicates with peripherals. It relieves the CPU of I/O work, so the CPU is free for computation and the CPU and I/O devices work in parallel.

The microinstruction of the basic computer is 20 bits long, with these fields:

• F1, F2, F3: microoperation fields (each selects one of up to 7 microoperations).
• CD: condition field, which selects the status bit to be tested (U, I, S or Z).
• BR: branch field, which selects the type of branch (JMP, CALL, RET, MAP).
• AD: address field, which gives the branch address in the 128-word control memory.

Cache coherence is the requirement in a multiprocessor system that all the caches holding copies of the same memory block see the same (latest) value. When one processor changes its copy, the other copies and main memory must be updated or invalidated.

Signs. Multiplicand $B = -47$ has sign 1 and multiplier $Q = +102$ has sign 0, so the product sign is $1 \oplus 0 = 1$ (negative).

Magnitudes (7 bits). $B = 47 = 0101111$, $Q = 102 = 1100110$. $A$ and $E$ are cleared, and the sequence counter is $SC = 7$.

At each step, if $Q_0 = 1$ then $EA \leftarrow A + B$. Then $EAQ$ is shifted right and $SC$ is decremented.

The product magnitude is $A\,Q = 0100101\;0111010_2 = 4794$.

With the sign bit $As = 1$, the result is $-4794$, which agrees with $(-47)\times(+102) = -4794$.

Setup. Magnitudes: $19 = 10011$ (multiplicand B), $21 = 10101$ (multiplier Q). Signs: $B_s = 1$, $Q_s = 0$, so the product sign is $1 \oplus 0 = 1$ (negative). Registers: A = 00000, E = 0, SC = 5.

At each step, if $Q_0 = 1$ then $A \leftarrow A + B$; then shift right E, A, Q together.

The product magnitude is A Q = $01100\,01111_2 = 399$.

With the sign bit (1) attached, the result is $1\,0110001111_2 = -399$.

Check: $(-19)\times(+21) = -399$.

In programmed I/O the CPU keeps polling the device status flag, which wastes CPU time while it waits. In interrupt-initiated I/O the device signals the CPU only when it is ready, so the CPU runs other programs meanwhile and the system's efficiency is much higher.

Use Booth's algorithm for signed 2's complement numbers, with 7 bits per operand (6 bits for 37 plus the sign).

$BR = -37 = 1011011$ (multiplicand), $\overline{BR}+1 = 0100101 = +37$

$QR = +13 = 0001101$ (multiplier), $AC = 0000000$, $Q_{n+1} = 0$, $SC = 7$

Rule by $Q_n Q_{n+1}$: 10 gives $AC \leftarrow AC - BR$, 01 gives $AC \leftarrow AC + BR$, 00 or 11 gives no operation. Then arithmetic shift right AC, QR.

The product is $AC\,QR = 1111100\,0011111 = 11111000011111_2$.

It is negative. Its magnitude is the 2's complement $00000111100001_2 = 481$.

So $(-37)\times(+13) = -481$.

Signs differ (one operand negative, one positive), so the product sign bit is $1$ (negative). Signed-magnitude multiplication multiplies only the magnitudes by shift-and-add.

• Multiplicand $B = 121 = 1111001_2$ (magnitude), sign $0$
• Multiplier $Q = 19 = 10011_2$ (magnitude), sign $1$ (for $-19$)
• Sign of product: $1 \oplus 0 = 1$

Scan the multiplier bits from LSB to MSB: add the (shifted) multiplicand when the bit is 1, otherwise add nothing.

Magnitude of product $= 2299 = 100011111011_2$.

With the sign bit attached, the result is $1\,100011111011$ in signed-magnitude form, i.e. $-2299$.

Check: $19 \times 121 = 2299$, so $(-19)\times 121 = -2299$.

Multiplication is done by adding the multiplicand to a running sum as many times as the value of the multiplier.

#include <stdio.h>

int main(void) {
    int a, b, product = 0, i;
    printf("Enter two positive numbers: ");
    scanf("%d %d", &a, &b);

    for (i = 1; i <= b; i++) {
        product = product + a;   /* a added b times */
    }

    printf("%d x %d = %d\n", a, b, product);
    return 0;
}

For $a=5,\ b=4$: the loop gives $0+5=5$, $10$, $15$, $20$, so $5\times 4 = 5+5+5+5 = 20$.

In programmed I/O the CPU must keep polling the device status flag and wastes time waiting. In interrupt-initiated I/O the CPU carries on with useful work and the device interrupts it only when ready for a transfer, so CPU time is used efficiently and response to devices is faster.

Multiplication by repeated addition: the multiplicand is added to the product as many times as the multiplier.

#include <stdio.h>

int main(void) {
    int a, b, product = 0, i;        /* a = multiplicand, b = multiplier */

    printf("Enter two positive numbers: ");
    scanf("%d %d", &a, &b);          /* read both numbers */

    for (i = 1; i <= b; i++) {       /* repeat b times */
        product = product + a;       /* add a to the running sum */
    }

    printf("Product = %d\n", product);
    return 0;
}

Explanation of statements

• #include <stdio.h> includes the library for input/output.
• int a, b, product = 0, i; declares the operands, a loop counter, and the product initialised to 0 (the additive identity).
• scanf(...) reads the two numbers.
• for (i = 1; i <= b; i++) makes the loop run exactly b times.
• product = product + a; adds the multiplicand to the sum in every iteration.
• printf(...) prints the result.

Example: $5\times 4$ gives $0+5+5+5+5 = 20$.

The address field is at location 401 and has value $A = 500$; $R1 = 250$.

• (a) Direct: $EA = A = 500$.
• (b) Immediate: the operand is the address field itself, so there is no effective address in memory; the operand is 500 and lies at location 401.
• (c) Register indirect: $EA = [R1] = 250$.
• (d) Index with R1: $EA = A + R1 = 500 + 250 = 750$.

The instruction is at 500 and its address field at 501, so after fetching the instruction $PC = 502$. Address field $A = 800$, $R1 = 300$.

• (a) Direct: $EA = A = 800$.
• (b) Immediate: the operand is the address field itself, so $EA = 501$ (the operand value is 800).
• (c) Relative: $EA = PC + A = 502 + 800 = 1302$.
• (d) Register indirect: $EA = [R1] = 300$.

Yes. In strobe control, only one control line is used and the source (or destination) has no way to know whether the other side actually received (or supplied) the data. In handshaking, two control lines (e.g. data valid and data accepted) are used, so both units confirm each transfer. This makes handshaking more reliable and lets units of different speeds communicate correctly, although it needs an extra control line.

Gray code is a binary code in which two successive values differ in only one bit. For example, the 2-bit sequence is 00, 01, 11, 10. It is used in shaft encoders and Karnaugh maps to avoid errors during transitions.

A structural hazard occurs in a pipeline when two instructions need the same hardware resource (such as memory or the ALU) in the same clock cycle, so one of them must wait. It arises from insufficient hardware, e.g. a single memory used for both instruction fetch and data access.

16 flip-flops. The Data Register (DR) of the basic computer is a 16-bit register, and one flip-flop is needed for each bit.

Multiport memory: each memory module has several ports, one per processor, and the control, switching and priority logic is inside the memory module. It gives high transfer rate but needs expensive memory control logic and many cables; it suits small systems.

Crossbar switch: a matrix of switches between processors and memory modules, with the switching logic placed at the crosspoints outside the memory. Memory modules are simple, and several processors can access different modules at the same time, but the number of switches grows as $n \times m$, so the hardware becomes complex.

Intra-instruction level parallelism means exploiting parallelism inside the execution of a single instruction, by performing its different micro-operations or sub-steps (fetch, decode, operand access, execute) simultaneously on separate hardware units or in overlapping stages, as in pipelining.

An I/O interface is required because peripherals differ from the CPU in speed, data format, word length and signal levels. The interface converts data formats and signal levels, synchronises the timing of the slow device with the fast CPU, provides buffering and status information, and selects the device through address decoding and control signals.

A three-state (tri-state) gate is a digital circuit whose output can be in logic 0, logic 1, or a high-impedance (Hi-Z) state, which acts as an open circuit. An enable input controls it: when enabled it behaves as a normal buffer, otherwise the output is disconnected. It lets many devices share a common bus.

No single memory is at once very fast, very large and cheap, so a hierarchy (registers, cache, main memory, secondary storage) is maintained to get speed close to the fastest level and capacity and cost close to the slowest level. Programs show locality of reference, so most accesses are served by the small fast levels and only a few go to the slow, large ones.

The program uses basic computer assembly language. The multiplier is stored as a negative count in Y, so ISZ can count it up to zero. It adds X to the product P once per pass.

        ORG 100
LOP,    LDA P       / AC <- P
        ADD X       / AC <- P + X
        STA P       / P <- P + X
        ISZ Y       / Y <- Y + 1, skip if Y = 0
        BUN LOP     / repeat while Y != 0
        HLT
X,      DEC 7       / multiplicand
Y,      DEC -3      / -(multiplier), counts the additions
P,      DEC 0       / product, initially 0

For $7 \times 3$, the loop runs three times and $P$ becomes $7 \to 14 \to 21$. The result $P = 21$ is stored in memory.

Two 8-bit characters are read from the keyboard. The first is shifted left by 8 positions, and the second is added into the low byte. This gives one 16-bit word.

        ORG 100
        CLA
        CLE
FST,    SKI             / wait for the first character
        BUN FST
        INP             / AC(0-7) <- INPR
        STA CHR
        CLE
LP,     LDA CHR
        CIL             / rotate left through E
        STA CHR
        ISZ CTR         / repeat 8 times
        BUN LP
SND,    SKI             / wait for the second character
        BUN SND
        CLA
        INP             / AC(0-7) <- second character
        ADD CHR         / AC <- char2 + (char1 << 8)
        STA PCK         / packed word
        HLT
CTR,    DEC -8
CHR,    HEX 0
PCK,    HEX 0

E is 0 and the high bits of the character are 0, so 8 left rotations move the first character cleanly into bits 8-15. After ADD, the packed word PCK holds char1 in the high byte and char2 in the low byte.

Total accesses $= 120$, hits $= 85$, misses $= 120 - 85 = 35$.

$\text{Hit ratio} = \frac{85}{120} = 0.708 \;(70.8\%)$

$\text{Miss ratio} = \frac{35}{120} = 0.292 \;(29.2\%) = 1 - \text{hit ratio}$

Why an IOP is required.

• In programmed and interrupt-driven I/O, the CPU spends much of its time transferring data and checking device status. This wastes processor time.
• An Input-Output Processor (IOP) is a separate processor with its own instruction set that handles I/O. It supports DMA, fetches I/O programs (channel programs) from memory, and transfers blocks of data between devices and memory.
• The CPU only starts an I/O program and is interrupted when it ends. Meanwhile it runs other work, so CPU and I/O overlap and throughput rises.
• The IOP also converts data formats, detects errors and controls many slow and fast devices of different types.

What influences the design of instruction format.

An instruction format is the layout of bits in an instruction: opcode, addressing mode and operand fields. Its design depends on:

1. Number of instructions (operations). More operations need a longer opcode field.
2. Number of addressing modes. A mode field is needed and the address fields change.
3. Number of operands (address fields). Three-, two-, one- or zero-address formats, as in stack machines, affect program length and speed.
4. Number of registers. More registers need more bits in the register field.
5. Memory size and address range. Bigger memories need longer address fields.
6. Word length, and fixed or variable length instructions. Fixed length is simple to decode, while variable length saves space.
7. Ease of decoding and hardware cost. The control unit complexity, and compatibility with older machines, also matter.

No. Pipelining gives the ideal speedup of about $k$ (the number of stages) only when the pipeline is kept full and the stages are balanced. It can give little or no gain, or even a loss, in these cases:

1. Few tasks. The speedup is $S = \dfrac{n\,t_n}{(k+n-1)\,t_p}$. For a single task ($n=1$) with $k=5$ stages and $t_p = t_n/5$, the time is $5t_p = t_n$, so there is no gain. Extra latch (register) delay makes it slightly slower.
2. Hazards. Structural, data and control hazards cause stalls and flushes. For example, with $k=5$ and 20% branch instructions that each cost 3 stall cycles, the average CPI is $1 + 0.2\times 3 = 1.6$. The speedup is only $5/1.6 \approx 3.1$ instead of 5.
3. Unbalanced stages. The clock period is set by the slowest stage. If one stage takes 10 ns and the others 4 ns, every stage must run at 10 ns.
4. Pipeline register overhead adds to every stage.

Hence pipelining improves throughput for long, regular instruction streams, but it does not always give better performance.

Overflow occurs when two numbers of the same sign are added and the result has the opposite sign. In hardware it is detected by $V = C_{n-1} \oplus C_n$: the carry into the sign bit is XORed with the carry out of the sign bit. If they differ, overflow has occurred.

An operating system is system software that manages the hardware resources (CPU, memory, I/O devices and files). It provides a user interface and an environment in which application programs can run.

A crossbar switch is an interconnection network with a matrix of crosspoint switches that connect each processor to each memory module. Any processor can be connected to any free memory module, and several non-conflicting transfers can take place at the same time.

Daisy chaining connects the interrupting devices in a serial chain, with the highest-priority device first. The interrupt acknowledge signal passes along the chain, so the highest-priority requesting device gets service first. It is a hardware method to decide priority among devices on a common interrupt line.

Eight consecutive microinstructions per routine need 3 low-order bits for the position within the routine. The 5 opcode bits go in front of these, and the leftmost bit of the 9-bit address is 0:

$\text{Opcode } i_4 i_3 i_2 i_1 i_0 \;\longrightarrow\; 0\; i_4 i_3 i_2 i_1 i_0\; 0\,0\,0$

For example, opcode 10110 maps to 010110000. Routines start at address 0, 8, 16 and so on, which allows 32 routines of 8 microinstructions each.

The Control Address Register (CAR) holds the address of the next microinstruction to be read from the control memory. It is incremented, loaded with a branch address, or loaded by the mapping logic, so it sequences the microprogram.

A set of instructions is complete when it can be used to evaluate any computable function. In practice it needs instructions for arithmetic and logic, data transfer (load/store), program control (branch, jump, call) and input/output, so that any program can be written with it.

A bootstrap loader is a small program kept in ROM that runs when the computer is switched on. It loads the operating system from secondary storage into main memory and starts it.

Relative address mode. The effective address is $EA = PC + \text{address part of the instruction}$.

Microprogrammed control unit. It is a control unit whose control signals are generated by a stored program of microinstructions held in a control memory (ROM). Each machine instruction is executed as a sequence of microinstructions, called a microprogram. A control address register (CAR), the control data register and sequencing logic select the next microinstruction.

Advantage of floating point representation. It can represent a much wider range of numbers, very large and very small, with a given number of bits. It does this by storing a mantissa and an exponent, so the position of the radix point is not fixed. It also keeps good precision for scientific computation.

Pipelining. It is a technique of decomposing a sequential process into sub-operations (segments), each executed in a dedicated segment, so that several tasks or instructions overlap in execution. While one instruction is in one segment, other instructions are in other segments. This raises throughput.

Conflicts (hazards) in pipelining.

1. Resource (structural) conflicts. Two segments need the same resource, such as memory, at the same time.
2. Data dependency (data hazards). An instruction needs a result that a previous instruction has not yet produced.
3. Branch difficulties (control hazards). Branch and interrupt instructions change the program counter, so the instructions already fetched must be discarded.

The instruction cycle of the basic computer is repeated for every instruction. It has these phases:

1. Fetch the instruction from memory.
2. Decode the opcode.
3. Read the effective address from memory if the instruction has an indirect address.
4. Execute the instruction.

After execution, the cycle returns to step 1 for the next instruction, unless a HLT is executed.

Fetch and decode (timing signals $T_0$, $T_1$, $T_2$), when $R'=1$ (no interrupt):

$R'T_0:\; AR \leftarrow PC$ $R'T_1:\; IR \leftarrow M[AR],\; PC \leftarrow PC+1$ $R'T_2:\; D_0,\dots,D_7 \leftarrow \text{Decode } IR(12\text{-}14),\; AR \leftarrow IR(0\text{-}11),\; I \leftarrow IR(15)$

Indirect address. For a memory-reference instruction with $I=1$, at $T_3$: $AR \leftarrow M[AR]$. With $I=0$, nothing is done at $T_3$.

Execute. For memory-reference instructions this takes place from $T_4$ onwards, for example for ADD: $T_4: DR \leftarrow M[AR]$ and $T_5: AC \leftarrow AC + DR,\ E \leftarrow C_{out},\ SC \leftarrow 0$. Register-reference ($D_7 I'T_3$) and I/O-reference ($D_7 I T_3$) instructions execute at $T_3$.

At the end of execution the sequence counter is cleared ($SC \leftarrow 0$) and the next cycle starts. If an interrupt is pending ($R=1$), the interrupt cycle runs instead.

A MOD-4 up/down counter counts 00, 01, 10, 11 and back to 00 when the control input $X = 0$ (up). It counts 00, 11, 10, 01 and back to 00 when $X = 1$ (down). It uses two T flip-flops, $Q_1$ and $Q_0$, driven by a common clock.

State table

Flip-flop input equations

$T_0 = 1$

$T_1 = X'Q_0 + XQ_0' = X \oplus Q_0$

Circuit. The $Q_0$ flip-flop has $T=1$ and toggles at every clock pulse. The $Q_1$ flip-flop receives $T_1$ from an XOR gate with inputs $X$ and $Q_0$. All clock pins are connected together, so it is synchronous. When $X=0$, $T_1 = Q_0$ and the counter counts up. When $X=1$, $T_1 = Q_0'$ and it counts down.

Cache coherence. In a multiprocessor system each processor has its own cache, so the same memory block may be held in several caches. If one processor modifies its copy, the other caches and main memory hold stale values. Cache coherence is the requirement that all copies of shared data stay consistent. It is maintained by write-through or write-invalidate/update (snooping) protocols, directory-based schemes, or by not caching shared writable data.

Cache mapping techniques. Mapping decides where a main memory block may be placed in the cache.

1. Associative mapping. Any block can go in any cache line. The cache stores both the address and the data, and the CPU address is compared with all stored addresses at once. It is the most flexible and has the fewest conflicts, but needs costly associative (content-addressable) memory.
2. Direct mapping. The address is split into tag and index. A block can go in only one line, given by $\text{line} = \text{block number} \bmod \text{number of lines}$. It is cheap and simple, but blocks that map to the same line conflict and can cause thrashing.
3. Set-associative mapping. The cache is divided into sets of $k$ lines (k-way). A block maps to one set, given by $\text{block number} \bmod \text{number of sets}$, and can be in any line within that set. The tags in the set are compared. It is a compromise: the hit ratio is higher than direct mapping, with less hardware than fully associative mapping.

On a miss, a replacement algorithm (FIFO, LRU or random) chooses which block is replaced, in associative and set-associative caches.

a. Non-pipelined time for $n=100$ tasks: $n\,t_n = 100\times25 = 2500$ ns.

Pipelined time with $k=5$ segments and $t_p = 4$ ns: $(k+n-1)\,t_p = (5+100-1)\times4 = 416$ ns.

$\text{Speed-up } S = \frac{2500}{416} \approx 6.01$

b. Why addressing modes are used.

• They give programmers flexibility such as pointers, loop counters, indexing of arrays and relocation of programs.
• They reduce the number of bits in the address field and the number of instructions in a program.

Addressing modes available:

1. Implied mode: the operand is implied by the opcode, as with the accumulator.
2. Immediate mode: the operand is in the instruction itself.
3. Register mode: the operand is in a CPU register.
4. Register indirect mode: the register holds the address of the operand.
5. Autoincrement or autodecrement mode: register indirect, with the register incremented or decremented.
6. Direct address mode: the address field gives the operand's address.
7. Indirect address mode: the address field gives the location that holds the operand's address.
8. Relative address mode: $EA = PC + \text{address field}$.
9. Indexed addressing mode: $EA = \text{index register} + \text{address field}$.
10. Base register addressing mode: $EA = \text{base register} + \text{address field}$.

(a) Hardware for signed 2's complement addition/subtraction

Signed 2's complement numbers are added exactly like unsigned numbers, with the sign bit treated as an ordinary bit, so no separate sign logic is needed. The hardware consists of:

• Registers AC and BR (n bits each) holding the two operands, plus a flip-flop V for overflow.
• A parallel adder (chain of full adders) that adds AC and BR.
• An XOR (complementer) stage on the BR input. A mode control line $M$ is XORed with every BR bit and also fed to the carry-in $C_0$ of the adder.

Operation:

• $M = 0$ (addition): BR passes unchanged, $C_0 = 0$, so $AC \leftarrow AC + BR$.
• $M = 1$ (subtraction): BR is complemented and $C_0 = 1$, so $AC \leftarrow AC + \overline{BR} + 1 = AC - BR$ (2's complement of BR is added).

Overflow: it occurs when the carry into the sign position differs from the carry out of it, so $V = C_{n-1} \oplus C_n$. If $V = 1$ the result is invalid.

Algorithm: (1) Add (or subtract) the two numbers using the adder; (2) check $V$; if $V=0$ the sum in AC is the answer, if $V=1$ report overflow.

(b) Multiplication of $-23 \times 9$ (sign-magnitude)

Sign of multiplicand = 1 (negative), sign of multiplier = 0, so product sign $= 1 \oplus 0 = 1$ (negative).

Magnitudes: $23 = 10111_2$, $9 = 01001_2$ (5 bits each).

Shift-and-add: the multiplier bits (from LSB) are 1, 0, 0, 1, 0.

Magnitude of product $= 11001111_2 = 207$.

With the sign bit attached: $1\,11001111$, which is $-207$. Check: $-23 \times 9 = -207$.

Floating-point representation can represent a very wide range of numbers, from very small fractions to very large values, in a fixed number of bits, because the mantissa holds the precision and the exponent scales the value.

Resource (structural) conflicts are solved by duplicating hardware, for example separate instruction and data memories (or caches) so that instruction fetch and operand access can happen in the same clock cycle, and by adding more functional units or register ports. Where this is not possible, the pipeline is stalled (a bubble is inserted) until the resource is free.

The opcode (operation code) is the part of a machine instruction that specifies the operation to be performed, such as ADD, LOAD or STORE. The remaining fields give the operands or their addresses.

The basic computer has a 16-bit memory word, and the data register (DR) holds the operand read from memory (or to be written to it). Hence DR must be 16 bits wide to hold a complete word in one memory transfer. The same 16-bit width is used by AC, IR and the common bus.

Daisy chaining is required to decide priority among several devices sharing a single interrupt request line. The interrupt acknowledge signal passes serially from device to device, starting from the highest priority, so the first requesting device blocks it from reaching the lower ones and places its vector address on the bus. This resolves which device is served first.

In strobe control, a single control line (strobe) from either the source or the destination times the transfer, and the other unit gets no confirmation that data was received or sent. In handshaking, two control lines (e.g. data valid and data accepted) are used, so each unit acknowledges the other, which guarantees reliable transfer between units of different speeds.

A process is a program in execution. It includes the program code, its current activity (program counter and register contents), stack and data, and is the unit of work that the operating system schedules.

In a loosely coupled multiprocessor, each processor has its own local memory and I/O devices, and forms a computer module of its own. The processors communicate by message passing through a message-transfer system or communication network (e.g. a serial link or shared channel) rather than through a common memory. Interaction between processors is low, so it is suitable for tasks that can be divided into largely independent subtasks and is easily expandable.

A hardwired control unit generates control signals using fixed logic circuits (gates, decoders, counters) instead of a stored microprogram.

• Speed: It is faster, because signals are produced directly by logic gates with no control-memory fetch for each microinstruction.
• Lower overhead: There is no control memory and no microinstruction sequencing, so the delay per step is smaller. This suits RISC machines with simple instruction sets.
• Efficient with simple instruction sets: With few instructions the logic is small and economical.

Its drawback is that it is hard to modify or extend, whereas a micro-programmed unit can be changed by rewriting the microprogram.

In the basic computer, the registers and memory are connected through a common bus of 16 lines, so that information can be moved from one component to another using one shared set of wires instead of separate paths between every pair.

• The registers connected are AR, PC, DR, AC, IR, TR and memory (INPR feeds AC, OUTR is loaded from AC).
• A bus selector (multiplexer) with select lines $S_2S_1S_0$ chooses which one register or memory drives the bus: 001 = AR, 010 = PC, 011 = DR, 100 = AC, 101 = IR, 110 = TR, 111 = memory.
• AR, PC (12 bits) place their contents in the lower 12 bits of the bus (upper bits zero).
• The register that must receive data has its LD (load) input enabled; INR and CLR are also used for increment and clear.
• Only one register can drive the bus at a time. The adder and logic circuit takes input from AC and DR, and its output goes to AC (not through the bus).

Example: for $AR \leftarrow PC$ the selector chooses PC ($S_2S_1S_0=010$) and LD of AR is enabled.

Instruction pipelining is a technique in which the execution of an instruction is divided into several stages (segments), such as fetch, decode, operand fetch and execute, and several instructions are processed concurrently, each in a different stage. Like an assembly line, while one instruction is executing, the next is being decoded and the one after is being fetched.

With $k$ stages and clock period $t_p$, $n$ instructions need $(k + n - 1)t_p$ time instead of $n k t_p$, giving speedup

$S = \frac{n k}{k + n - 1} \to k \text{ as } n \to \infty.$

Pipelining raises throughput, but it can be disturbed by hazards: structural (resource), data and control (branch) hazards.

Cache mapping determines where a block of main memory may be placed in the cache. The three techniques are:

1. Direct mapping: Each main memory block maps to exactly one cache line, given by $i = j \bmod m$ (j = block number, m = number of cache lines). The address is divided into tag, index and word fields. It is simple and cheap, but two blocks with the same index keep replacing each other (conflict misses).
2. Associative (fully associative) mapping: A block can be placed in any cache line. The address is split into tag and word; the tag is compared with all stored tags in parallel using associative memory. It is flexible with the best hit ratio, but needs costly comparison hardware.
3. Set-associative mapping: The cache is divided into sets of $k$ lines; a block maps to one set (set $= j \bmod$ number of sets) and may occupy any line of that set. The address has tag, set and word fields. It is a compromise between the two, reducing conflict misses at moderate cost.

When the cache is full, a replacement policy (FIFO, LRU, random) selects the block to remove.

In a multiprocessor in which each processor has its own cache, the same memory block may be copied into several caches. If one processor writes to its copy, the other caches and main memory hold stale values, so the processors see inconsistent data. This is the cache coherence problem.

Coherence means that all processors always see the most recent value of a shared item. Solutions:

• Write-through / write-update: a write is also sent to memory and to the other caches so their copies are updated.
• Write-invalidate (snooping): each cache watches (snoops) the bus; when one processor writes, the copies in other caches are marked invalid.
• Directory-based protocols: a central directory tracks which caches hold each block.
• Non-cacheable shared data: shared writable data are kept only in main memory (not cached), or hardware/software marks them so.

Differences

Circuit diagrams

Combinational: half adder

 A ──┬──────────┐
     │        [XOR]──── Sum = A ⊕ B
 B ──┼──┬───────┘
     │  │
     └──┼──[AND]────── Carry = A·B
        └─────┘

Sequential: SR flip-flop with NOR gates (feedback gives memory)

 R ──[NOR]──┬──── Q
        ▲   │
        │   └───────┐
        └───────┐   │
 S ──[NOR]──┬───┘   │
        ▲   └────── Q'
        └───────────┘

Each NOR gate output is fed back to the input of the other, so the circuit holds its state; this feedback loop is what makes it sequential, while the half adder has no feedback.

The addressing mode specifies how the address field of an instruction is interpreted to find the operand (effective address). It gives flexibility, such as pointers, loop counters, indexing of arrays and program relocation, and reduces instruction length.

Common modes:

1. Implied mode: the operand is implied by the instruction, e.g. CMA complements AC.
2. Immediate mode: the operand is in the instruction itself, e.g. LDA #5. Fast, but the constant is fixed.
3. Register mode: the operand is in a register named in the instruction.
4. Register indirect mode: the register holds the address of the operand in memory; $EA = (R)$.
5. Autoincrement/autodecrement mode: like register indirect, but the register is incremented or decremented after/before access.
6. Direct address mode: the address field is the effective address, $EA = A$.
7. Indirect address mode: the address field gives the location that holds the operand's address, $EA = M[A]$.
8. Relative address mode: $EA = A + PC$; used for branches and relocatable code.
9. Indexed addressing mode: $EA = A + (XR)$; used for arrays.
10. Base register addressing mode: $EA = A + (BR)$; used for relocation.

Use 7-bit registers (40 needs 7 bits as a signed number).

Multiplicand $M = -13 = 1110011$, so $-M = +13 = 0001101$. Multiplier $QR = +40 = 0101000$. Initially $AC = 0000000$, $Q_{-1}=0$, SC = 7.

Rule: $Q_0Q_{-1} = 10$: $AC \leftarrow AC - M$; $01$: $AC \leftarrow AC + M$; $00$ or $11$: no operation. Then arithmetic shift right of AC, QR, $Q_{-1}$.

Result $AC\,QR = 1111011\ 1111000$ (14 bits). It is negative; its 2's complement is $00001000001000 = 520$.

$(-13)\times(+40) = -520$

A floating-point number is normalized when the most significant digit (bit) of the mantissa is non-zero, i.e. there are no leading zeros (e.g. mantissa $0.1xxx$ in binary). Un-normalized numbers are shifted left, with the exponent decreased accordingly, to obtain maximum precision.

The shift without loss of information is the circular shift (rotate) micro-operation. Circular shift right is $R \leftarrow cir\ R$ (shr with end-around), and circular shift left is $R \leftarrow cil\ R$. In these, the bit shifted out of one end is re-inserted at the other end.

In the basic computer, the I/O instruction is identified by opcode $= 111$ and the mode bit $I = 1$ (bit 15 of the instruction). The register-reference instructions have the same opcode 111 but $I = 0$. In an I/O instruction, bits 0-11 select the specific operation (INP, OUT, SKI, SKO, ION, IOF).

In a microprogrammed control unit, the microprogram sequencer (next-address generator) determines the address of the next microinstruction to be read from control memory. It is used to:

• increment the control address register (CAR) for the next sequential microinstruction;
• perform branches (conditional and unconditional) by loading an address from the microinstruction according to status bits;
• map the opcode of the instruction to the starting address of its microroutine;
• handle subroutine call and return of microroutines (using a register/stack).

In indexed addressing mode, the effective address is the sum of the address part of the instruction and the content of the index register:

$EA = A + (XR)$

where $A$ is the address field and $XR$ is the index register.

Solutions to control (branch) hazards:

• Pipeline stalling (inserting bubbles until the branch is resolved).
• Prefetching the branch target instruction (and the fall-through instruction), or using a branch target buffer.
• Branch prediction (static or dynamic).
• Delayed branch (rearranging instructions so useful ones fill the delay slots).
• Early branch resolution by adding hardware in the decode stage.

In programmed I/O the CPU must continuously poll the device status flag in a loop until the device is ready, so it is kept busy waiting and wastes CPU time, especially with slow devices. The CPU cannot do other useful work during the transfer.

A logical address is the address generated by the CPU (program) as seen in the program's own address space, which the memory management hardware maps to a physical address. A virtual address is an address in the virtual memory address space, which can be larger than the physical memory; it is mapped by the memory management unit (page or segment tables) to a physical address, with parts of it residing on secondary storage. In many systems the two terms are used almost interchangeably, but virtual address emphasises the extended space supported by paging or swapping.

Associative memory is a memory unit accessed by the content of the stored data rather than by a specific address (content addressable memory). A word is located by comparing the given argument with all stored words in parallel.

#include <stdio.h>

int main(void) {
    int a, b;

    printf("Enter two integers: ");
    scanf("%d %d", &a, &b);

    printf("First integer  = %d\n", a);
    printf("Second integer = %d\n", b);

    return 0;
}

The program reads two integers with scanf and prints them with printf. For example, input 7 12 prints First integer = 7 and Second integer = 12.

Given: non-pipelined task time $t_n = 45$ ns, number of segments $k = 5$, clock period (each sub-operation) $t_p = 10$ ns.

Speedup $S = \dfrac{n\,t_n}{(k + n - 1)\,t_p}$

For $n = 50$ tasks:

$S = \frac{50 \times 45}{(5 + 50 - 1)\times 10} = \frac{2250}{540} \approx 4.17$

For infinite tasks ($n \to \infty$):

$S = \frac{t_n}{t_p} = \frac{45}{10} = 4.5$

Memory: $M[250] = 511$, $M[325] = 255$, $M[511] = 432$; $R = 250$; $PC = 352$. Instruction: LDA 250 (address field = 250).

(a) Indirect: $EA = M[250] = 511$, operand $= M[511] = 432$. AC = 432.

(b) Register indirect: $EA = R = 250$, operand $= M[250] = 511$. AC = 511.

(c) Immediate: operand is the address field itself. AC = 250.

(d) Direct: $EA = 250$, operand $= M[250] = 511$. AC = 511.

Use 5-bit registers. Multiplicand $M = +15 = 01111$, so $-M = 10001$. Multiplier $QR = -5 = 11011$. Initially $AC = 00000$, $Q_{-1} = 0$, SC = 5.

Result $AC\,QR = 11101\ 10101$ (10 bits). Negative; 2's complement $= 0001001011 = 75$.

$(+15)\times(-5) = -75$

(a) Data transfer by handshaking

Handshaking uses two control lines between the source and destination units, so each transfer is acknowledged.

Source-initiated transfer:

1. The source places data on the data bus and enables data valid.
2. The destination accepts the data from the bus and enables data accepted.
3. The source sees data accepted, disables data valid and removes the data.
4. The destination disables data accepted, ready for the next transfer.

Destination-initiated transfer: the destination first activates ready for data; the source then places data on the bus and enables data valid; the destination accepts the data and disables ready for data; the source disables data valid and the cycle is ready to repeat.

This works for units of different speeds because each side proceeds only after the other's acknowledgement.

(b) Interrupt cycle of the basic computer

The interrupt flip-flop R is set (when IEN = 1 and an input or output flag FGI/FGO is 1). At the end of the execute phase, if $R = 1$ the computer goes to the interrupt cycle instead of fetching the next instruction:

1. $RT_0$: $AR \leftarrow 0,\ TR \leftarrow PC$ (save return address)
2. $RT_1$: $M[AR] \leftarrow TR,\ PC \leftarrow 0$ (store the return address at location 0)
3. $RT_2$: $PC \leftarrow PC + 1,\ IEN \leftarrow 0,\ R \leftarrow 0,\ SC \leftarrow 0$

So the return address is saved in memory location 0, control branches to location 1 (the interrupt service routine starts there), further interrupts are disabled, and the cycle is reset. The routine ends with ION and an indirect branch (BUN 0 I) back to the saved address.

(a) Interconnection structures for multiprocessors

1. Time-shared common bus: All processors, memory and I/O modules are connected to one shared bus. Only one transfer can take place at a time, so a bus arbitration mechanism is needed. It is simple, cheap and easy to expand, but the single bus limits throughput and a bus failure stops the system.
2. Crossbar switch: There is a switch at each crosspoint of a matrix with memory modules along one axis and processors along the other. Any processor can connect to any free memory module, and several transfers occur simultaneously, giving high bandwidth. Conflicts happen only if two processors want the same module. The disadvantage is the high hardware cost, which grows as $n \times m$.

Others include multiport memory, multistage switching network and hypercube.

(b) Cache mapping techniques

• Direct mapping: block $j$ goes to line $j \bmod m$; address = tag + index + word. Simple, but conflict misses.
• Fully associative mapping: a block can go to any line; address = tag + word; all tags are compared in parallel. Flexible and a high hit ratio, but expensive.
• Set-associative mapping: the cache is divided into sets; a block maps to a fixed set and can occupy any line in it; address = tag + set + word. A balance between cost and performance.

Replacement algorithms (FIFO, LRU) decide which block is replaced when the cache is full.

Complements simplify arithmetic in digital computers. Subtraction can be done by adding the complement of the subtrahend, so the same adder circuit performs both addition and subtraction, reducing hardware. Complements are also used for representing negative numbers (2's complement) and for logical operations.

The location counter (LC) keeps track of the address of the instruction or data currently being assembled. The assembler increments it as each line is processed, and uses its value to assign addresses to labels in the symbol table; it is set by the ORG pseudo-instruction.

$4096 = 2^{12}$ bytes, so 12 bits are required.

Dynamic microprogramming means the control memory is writable (RAM or other loadable memory), so the microprogram can be changed or reloaded at run time. This lets the same hardware emulate different instruction sets, unlike static microprogramming where the control memory is a fixed ROM.

In asynchronous data transfer, the strobe pulse is a control signal sent by one unit to tell the other unit when to transfer data. The source (or destination) activates it to indicate that valid data is on the bus, so the receiving unit knows the exact moment to accept the data.

The instruction pipeline deviates from normal operation because of three types of hazards.

• Resource (structural) conflicts: two segments need the same resource, such as memory, in the same clock cycle.
• Data dependency: an instruction needs the result of a previous instruction that is not yet available.
• Branch difficulties: branch and interrupt instructions change the program counter, so the instructions already fetched must be discarded.

Cache memory is based on the principle of locality of reference. Programs tend to access the same or nearby memory locations repeatedly (temporal and spatial locality), so keeping those active words in a small, fast memory makes the average access time close to that of the cache.

A critical section (the question's "critical selection") is the part of a program in which a process accesses a shared resource or shared data. Only one process may execute it at a time, so that concurrent access does not give inconsistent results.

There are $5FF - 500 + 1 = 100_{16} = 256$ locations, so the counter is initialised to $-256$. In the basic computer, a pointer location holds the address and indirect addressing (I) is used to reach the memory word.

        ORG 100
LOP,    CLA            / AC = 0
        STA PTR I      / store 0 at the address held in PTR
        ISZ PTR        / PTR = PTR + 1 (next location)
        ISZ CNT        / CNT = CNT + 1, skip next instruction when zero
        BUN LOP        / repeat until all 256 words are cleared
        HLT
PTR,    HEX 500        / pointer to the first location
CNT,    DEC -256       / counter for 256 locations

The loop runs 256 times. When CNT becomes 0, ISZ CNT skips BUN LOP and the computer halts, with locations 500 to 5FF all set to 0.

The instruction LDA 300 is stored at address $PC - 1 = 299$ (PC already points to the next instruction, 300), and its address field is 300. The effective address and the value loaded depend on the mode. Let $M[x]$ be the memory word at address $x$ in the figure.

i. Direct addressing: effective address EA = 300, so $AC = M[300]$.

ii. Immediate: the operand is the address field itself, so $AC = 300$.

iii. Indirect addressing: EA = $M[300]$ (the pointer stored at 300, which leads to location 450 in the figure), so $AC = M[M[300]] = M[450]$.

iv. Register indirect (LDA (R1)): R1 = 500 holds the address of the operand, so EA = 500 and $AC = M[500]$.

Direct needs one memory reference for the operand, indirect needs two, immediate needs none, and register indirect needs one.

Associative memory (content-addressable memory, CAM) is a memory that is accessed by the content of the data rather than by an address. A search word is compared with all stored words simultaneously, and the matching words are returned. It is very fast but costly, and it is used in cache tags and page tables.

Average access time. Given $t_c = 200$ ns, $t_m = 2000$ ns and hit ratio $h = 0.9$:

$t_{avg} = h\,t_c + (1-h)\,t_m = 0.9(200) + 0.1(2000) = 180 + 200 = 380 \text{ ns}$

(If main memory is accessed only after the cache lookup fails, $t_{avg} = t_c + (1-h)t_m = 200 + 200 = 400$ ns. The usual textbook formula above gives 380 ns.)

Common bus system. In a common bus system, a single set of lines is shared to transfer information between the registers, memory and other units. Selection circuitry (multiplexers or three-state buffers) chooses which register drives the bus, and the bus carries the data to the destination register whose load input is enabled.

Advantages:

• It needs far fewer wires and less hardware than separate paths between every pair of registers, so it is cheaper and simpler.
• It is easy to expand, since a new register or device is added by connecting it to the bus.
• Control is simple, because only the select and load signals decide the transfer.
• The only cost is that one transfer can take place at a time on the bus.

Diagram (registers feeding a bus through a multiplexer):

 AR   PC   DR   AC   IR   TR   Memory
  |    |    |    |    |    |     |
  +----+----+----+----+----+-----+
            |   COMMON BUS (16 lines)
  +----+----+----+----+----+-----+
  |    |    |    |    |    |     |
 LD   LD   LD   LD   LD   LD    Write
          (S2 S1 S0 select the source on the bus)

Vector processing. Vector processing is the execution of a single instruction on whole arrays (vectors) of data, with many elements processed using pipelined arithmetic units or several processing elements. It avoids the loop overhead of scalar processing, and it is used for scientific work such as matrix computation, weather forecasting and image processing, where the same operation is applied to a large set of data.

Interrupt priority. When several devices raise interrupts at the same time, priority decides which is served first. There are two ways.

1. Software (polling): one common branch address is used for all interrupts. The routine polls the devices in order, so the first device polled has the highest priority. It is simple, but slow, since many devices may be tested before the requester is found.

2. Hardware:

• Daisy chaining (serial priority): the devices are connected in series by a priority chain. The interrupt acknowledge signal passes through each device in turn, and the first device with a pending request blocks the signal and puts its vector address on the bus. The device nearest to the CPU has the highest priority.
• Parallel priority: each device has a bit in an interrupt register, with a mask register to enable or disable each source. A priority encoder gives the vector address of the highest-priority unmasked request.

Instruction set completeness. An instruction set is complete if it can be used to evaluate any computable function. It must contain instructions in these classes:

• arithmetic, logical and shift instructions for computation,
• data transfer instructions (move data between memory and registers),
• program control instructions (test, branch, call, return) for decisions and loops,
• input/output instructions for communication with the outside.

A normalized floating-point number has a non-zero leading digit in its fraction (mantissa). This uses the mantissa bits for the maximum precision and gives each number a unique representation, which also makes comparison and arithmetic simpler.

The control data register holds the microinstruction fetched from control memory while it is executed. The next microinstruction is read and the next address is computed at the same time as the present one executes. This overlapping of fetch and execute is pipelining, so the register is called the pipeline register.

Parallel processing is achieved by:

• Pipelining (overlapping the segments of an instruction or arithmetic operation),
• Vector (array) processing,
• Multiple functional units in the CPU,
• Multiprocessing (several CPUs sharing memory, such as multiprocessor systems),
• Multicomputers/distributed systems, and
• Overlapping CPU and I/O operations.

Peripherals differ from the CPU in speed, data format, word length and signal levels. An interface is placed between them to convert signals and formats, synchronise the different speeds, and provide the control and status information and the address decoding. Without it the CPU could not communicate correctly with the devices.

No single memory is at once fast, large and cheap. A hierarchy (registers, cache, main memory, secondary storage) combines a small, fast memory for the active data with larger, slower and cheaper memories. Because of locality of reference, the system gives an average access time close to the fastest level at a cost close to the cheapest level.

A vector processor has one (or a few) deeply pipelined functional units that process the elements of a vector one after another in a pipelined fashion, with the elements streamed from vector registers. An array processor has many identical processing elements (ALUs) that operate in parallel on different elements of the array at the same time under a single control unit (SIMD), so it needs more hardware.

Use 7 bits including the sign bit, so the range is $-64$ to $+63$.

Case 1: (+33) + (+48)

$+33 = 0100001$ and $+48 = 0110000$

  0100001
+ 0110000
---------
  1010001

The carry into the sign bit is 1 and the carry out of the sign bit is 0. These differ, so overflow occurs. Two positive numbers have given a negative-looking result (sign bit 1), and the true sum $+81$ is outside the range $-64$ to $+63$.

Case 2: (-33) + (-48)

$-33$ in 2's complement: $0100001 \to 1011110 + 1 = 1011111$

$-48$ in 2's complement: $0110000 \to 1001111 + 1 = 1010000$

  1011111
+ 1010000
---------
 10101111

Dropping the carry out gives $0101111$. The carry into the sign bit is 0 and the carry out of the sign bit is 1, which differ, so overflow occurs. Two negative numbers have given a positive-looking result (sign bit 0), and the true sum $-81$ is outside the range.

In both cases the sign of the result is wrong, which shows overflow.

Every instruction in the basic computer goes through an instruction cycle that is repeated until the computer halts. It has these phases:

1. Fetch the instruction from memory.
2. Decode the operation code.
3. Read the effective address from memory if the instruction has an indirect address.
4. Execute the instruction.

Fetch (timing signals T0, T1): $T_0: AR \leftarrow PC$ $T_1: IR \leftarrow M[AR],\; PC \leftarrow PC + 1$

Decode (T2): $T_2: D_0 \ldots D_7 \leftarrow \text{decode } IR(12\text{-}14),\; AR \leftarrow IR(0\text{-}11),\; I \leftarrow IR(15)$

After decoding, the type of instruction is found from $D_7$ and $I$:

• $D_7 = 1,\; I = 1$: input-output instruction, executed at once.
• $D_7 = 1,\; I = 0$: register-reference instruction, executed at once.
• $D_7 = 0,\; I = 1$: memory-reference instruction with indirect address, so $AR \leftarrow M[AR]$ at $T_3$.
• $D_7 = 0,\; I = 0$: memory-reference instruction with direct address, so nothing is done at $T_3$.

Then the memory-reference instruction is executed from $T_4$ onwards, and the sequence counter is cleared ($SC \leftarrow 0$) so that the next instruction is fetched at $T_0$.

Flow chart:

        Start, SC <- 0
              |
        T0: AR <- PC
              |
        T1: IR <- M[AR], PC <- PC + 1
              |
        T2: Decode IR(12-14), AR <- IR(0-11), I <- IR(15)
              |
          D7 = 1 ?
         /          \
      (no)          (yes)
  memory-ref        I = 1 ? --yes--> Input-output: execute at T3
       |               | no
    I = 1 ?        Register-ref: execute at T3
    /     \               |
 (yes)   (no)             |
T3: AR<-M[AR]  T3: nothing |
    \     /                |
  Execute memory-ref (T4...)|
         \                 /
          SC <- 0, next instruction

Pipeline clock period. The clock must be as long as the slowest segment plus the register delay: $t_p = \max(t_1,t_2,t_3,t_4) + d = 45 + 4 = 49 \text{ ns}$

Pipeline time for $n = 100$ tasks with $k = 4$ segments: $T_{pipe} = (k + n - 1)\,t_p = (4 + 100 - 1)(49) = 103 \times 49 = 5047 \text{ ns}$

Equivalent non-pipelined system: each task takes the sum of the segment delays, $t_n = 30 + 35 + 20 + 45 = 130$ ns, so $T_{non\text{-}pipe} = n\,t_n = 100 \times 130 = 13000 \text{ ns}$