Processor Architectures and Boolean Algebra: Computer Science 9618 (Cambridge International AS & A Level)

A graphics processor applies the same brightness-adjustment instruction to every pixel of a photograph at the same time. Hundreds of separate processing units are used, each one applying that identical instruction to a different pixel's colour data simultaneously, all under the control of a single instruction stream.

Which of the four basic computer architectures does this describe?

A hardware company is designing two new processors.

Processor X has a small, fixed set of simple instructions, almost all of which complete in exactly one clock cycle. It relies on a large bank of general-purpose registers, and it only accesses main memory using dedicated load and store instructions.

Processor Y has a much larger and more varied set of instructions. Some of these instructions operate directly on data held in main memory (not just in registers), and completing them can take several clock cycles rather than one.

(a) State, giving a reason for each, which processor is RISC and which is CISC. [3]

(b) Processor X uses a three-stage pipeline (Fetch, Decode, Execute) to overlap the execution of successive instructions. The table below shows which pipeline stage three instructions, I1, I2 and I3, occupy in each clock cycle, assuming no stalls occur.

(i) Complete the table to show which stage I3 occupies in cycles 3, 4 and 5. [1]

(ii) State the total number of clock cycles taken to complete all three instructions using this pipeline, and the total number of clock cycles that would instead be needed if the three instructions were executed one at a time with no overlap at all. [1]

(c) Explain why the maximum time between an interrupt occurring and Processor X (RISC) beginning to service it is more predictable than the equivalent maximum time for Processor Y (CISC). [2]

A university research group needs to run several different operating systems on one physical server, and separately, needs so much raw computing power that it plans to link together thousands of individual processors to model climate change.

(a) Explain what is meant by a virtual machine, and describe how one could be used to meet the university's need to run several different operating systems on a single physical server. [2]

(b) State one benefit and one limitation of running an operating system inside a virtual machine, rather than directly on physical hardware. [2]

(c) The climate-modelling system the group plans to build is described as a massively parallel computer. State two characteristics of a massively parallel computer that distinguish it from a general-purpose computer containing only two or three processor cores. [2]

A digital electronics student is building simple circuits from logic gates, and separately, storing single bits of data using flip-flops.

(a) The student first builds a half adder, with inputs A and B, and outputs Sum and Carry. Complete the truth table for the half adder, and state the Boolean expression for Sum in terms of A and B. [2]

(b) The student then builds a full adder, with inputs A, B and Cin (carry-in), and outputs Sum and Cout (carry-out). Complete the truth table for the full adder, and state the Boolean expression for Cout in terms of A, B and Cin. [3]

(c) Starting with output Q = 0, an SR flip-flop receives these three successive sets of inputs.

(i) State the value of Q after each of steps 1, 2 and 3. [2]

(ii) A fourth step is then applied, with S = 1 and R = 1. State why this input combination is not allowed on an SR flip-flop. [1]

(d) Starting again with output Q = 0, a JK flip-flop receives these three successive sets of inputs.

State the value of Q after each of steps 1, 2 and 3, explaining how the flip-flop behaves differently from an SR flip-flop when J = K = 1. [2]

(a) Apply De Morgan's laws to write an equivalent expression for

NOT(A.B) + NOT(A+C)

that contains no NOT applied to a bracketed term, and simplify your answer as far as possible, naming any further law you use. [2]

(b) A logic circuit implements the Boolean expression

X = A.B.C + A.B.NOT C + A.NOT B.C

Simplify this expression algebraically to a minimal sum-of-products form, showing each step and naming the Boolean law used at each step. [3]

(c) The truth table for X (as defined in part (b)) is given below.

(i) Complete the Karnaugh map below for X, using rows for A and columns for BC. [1]

(ii) Draw loop(s) around the appropriate group(s) of 1s in your Karnaugh map, and hence write the minimal sum-of-products expression for X. Confirm that it matches your answer to part (b). [2]

A small company runs three separate physical servers in its server room. One server continuously runs email software and processes incoming email messages. A second server independently runs database software and processes queries against its own stored records. A third server runs web server software and processes visitors' page requests. Each server executes its own distinct program on its own separate data, entirely independently of the other two, all at the same time.

Which of the four basic computer architectures does this describe?

A processor manufacturer is comparing a RISC design and a CISC design for the same task, and is also studying how pipelining affects instruction execution on the RISC processor.

(a) A short routine that adds a value held in memory to a value held in another memory location, and stores the result back in memory, is written separately in RISC assembly language and in CISC assembly language for two otherwise equivalent processors. State, with a reason, which version of the routine is likely to contain more individual instructions. [2]

(b) State, with a reason, which processor's compiler. The RISC processor's or the CISC processor's, needs to carry out more work to produce efficient code. [2]

(c) The RISC processor uses a 4-stage pipeline (Fetch, Decode, Execute, Write-back). Explain why pipelining increases the processor's overall instruction throughput, but does NOT reduce the time taken for any single individual instruction to pass through all four stages. [2]

A logic circuit implements the Boolean expression Y = A.B + NOT A.C, where A, B and C are single-bit inputs.

(a) Complete the truth table for Y, for all eight combinations of A, B and C. [3]

(b) State the number of rows in your completed table for which Y = 1. [1]

(c) List the individual logic gates needed to build a circuit that implements Y directly from the expression above, without first simplifying it, stating how many of each gate are required. [2]

A logic circuit implements the Boolean expression Z = A.B + A.NOT B + NOT A.B, where A and B are single-bit inputs.

(a) Simplify Z algebraically as far as possible, showing each step and naming the Boolean law used at each step. [3]

(b) Complete a truth table showing the value of the original expression Z, and the value of your simplified expression from part (a), for all four combinations of A and B. Confirm that the two columns are identical in every row. [3]

The exclusive-OR (XOR) of two single-bit inputs A and B can be written as the Boolean expression A XOR B = A.NOT B + NOT A.B.

(a) Starting from NOT(A XOR B) = NOT(A.NOT B + NOT A.B), apply De Morgan's laws to remove the NOT from outside each bracket, so that no NOT is applied to a bracketed term. Show each application of the law. [2]

(b) Continue simplifying your answer to part (a), using the distributive law and the complement law, to show that NOT(A XOR B) = A.B + NOT A.NOT B. Show each step and name the law used at each step. [3]

(c) Complete a truth table showing A XOR B and NOT(A XOR B) for all four combinations of A and B, and confirm that your simplified expression from part (b) gives the same values as the NOT(A XOR B) column in every row. [3]