Why is there a risk of data and control hazards in a pipelined processor? For modern RISC
Question:
Why is there a risk of data and control hazards in a pipelined processor?
For modern RISC instruction set architectures like RISC-V, why are control hazards not exposed in the programming model? [4 marks]
(a) (i) Describe the four classes in Flynn's taxonomy of computing systems.
(ii) Describe Amdahl's law and use it to calculate the maximum speedup achievable by running a program, P, on a multicore system, S, where 80% of P is parallel and S contains 16 cores.
(i) Describe how the processor can support branch divergence between the different lanes. [4 marks] (ii) With the aid of a diagram, show the utilisation of the SIMD lanes for each pseudo-code operation, hence calculate the code's efficiency (overall utilisation of the SIMD lanes). [6 marks] (iii) What architectural technique do GPUs employ to allow them to perform useful work even though the loads from X and Y often cause stalls?
Two objects are being retrieved from B by A using HTTP over a network where the TCP-style transport protocol has no maximum segment size and the network experiences no loss. Each object is 125 kByte (i.e., one Mbit) in size. We assume all connection setup packets and HTTP request packets are negligible in size; we ignore the connection tear-down. (a) Suppose the Round-Trip-Time (RTT) between A and B is 10 milliseconds and the bandwidth between the sites is 10 Mbit/s. Illustrate with a simple diagram in each case how long it takes for A to retrieve both files under the following circumstances: [2 marks each] (i) Sequential (one-at-a-time) requests with non-persistent connections. (ii) Concurrent requests with non-persistent connections. (iii) Sequential requests within a single persistent connection. (iv) Pipelined requests within a single persistent connection. (b) Suppose A is connected to a cache C by a link with 10 Gbit/s bandwidth and negligible RTT. C connects to B with the link originally specified in part (a): 10 Mbit/s and 10 millisecond RTT. The cache operates as follows: ? If the object is not in the cache, the request is forwarded to B which responds with the object, which the cache stores with an object timeout and then forwards to A. ? If the object is in the cache, and the cache entry has not timed out (i.e., the cache Time To Live (TTL) has not expired), the object is returned to the client. ? If the object is in the cache, but the cache entry has timed out, the cache issues a conditional GET to the original server, asking if the object has changed since this object was cached. If the original server responds that it has not, the cache returns the cached object, otherwise the original server responds with the updated object which the cache forwards to the client. Showing your working, how long does it take for A to retrieve one file under the following circumstances: [3 marks each] (i) The file is not in the cache (ii) The file is in the cache and the TTL has not expired (iii) The file is in the cache, the TTL has expired, but the file has not changed (iv) The file is in the cache, the TTL has expired, and the file has changed 5 (TURN OVER) CST.2016.5.6 5 Computer Networking (a) This question concerns IPv6 notation. [2 marks] (i) Rewrite the following IPv6 address in the most compact form. 3ffe:1944:0000:0000:0010:0000:0000:d00b (ii) In IPv6 notation, what do ::/0 and ::1/128 represent? (b) Describe five differences between IPv4 and IPv6. [5 marks] (c) Describe, giving reasons, how an Internet Service Provider (ISP) may use their allocated IPv6 addresses to provide address blocks to their (residential) customers. [3 marks] (d) What are the implications of IPv6 for the Network Address Translation (NAT) gateways and firewalls of residential customers? [4 marks] (e) Give one advantage and one disadvantage that Stateless Address Autoconfiguration (SLAAC) has compared to DHCPv4. [2 marks] (f ) Suggest two features that would be desirable extensions of IPv6. Justify your answer. [4 marks] 6 CST.2016.5.7 6 Computer Networking (a) Consider packet switching and circuit switching. In simple terms, packet switching may allow more users to use the network. We have N users sharing a 1 Mbit/s link. Each user consumes 100 kbit/s when transmitting but only transmits for 10% of the time, on average. (i) How many users would a circuit-switching system support? State your assumptions. [1 mark] (ii) For N = 40 users, the probability that more than 10 users are active at the same time is approximately 0.0015. Show how to compute this probability. You are not required to calculate the actual figures. [6 marks] (iii) State two assumptions that you made in Part (a)(ii) about the network users. In each case describe why the assumption may fail for current Internet traffic. [4 marks] (b) The formulae below are used in TCP implementations to compute a value for the retransmission time-out T. R is an estimate of the round-trip time (RTT), D is an estimate of variance, M is the most recently measured round-trip measurement, ? = 0.875 and h = 0.25. D ? D + h(|M ? R| ? D) R ? ?R + (1 ? ?)M T = R + 4D (i) Give an example of how the retransmission time-out T is used within TCP. [1 mark] (ii) Describe why the computation of the retransmission time-out T incorporates a correction for deviation in the estimate of the RTT. [2 marks] (iii) For each assumption you stated in Part (a)(iii), describe the impact on the estimate of the retransmission time-out T. [3 marks each] 7 (TURN OVER) CST.2016.5.8 7 Concurrent and Distributed Systems This question is with respect to an operating system that supports multi-threaded processes using the POSIX threads (pthreads) API. Assume that each call to printf prints its output atomically, that thread scheduling is non-deterministic, and that threads are allocated unique and sequential integer IDs starting with 0. (a) Some program state is per-process, and some is per-thread. How many instances of each of the following will a 2-thread process have: virtual address space, executable program, register file, scheduling state (e.g., RUN, SLEEP), and stack? [5 marks] (b) A programmer adds printfs to a concurrent program to debug a race condition, but the symptoms vanish. Explain why this might have happened. [2 marks] (c) thrprint accepts as arguments the current thread's unique ID and a debug message to print. If each thread calls thrprint exactly once on start, how many possible interleavings are there with n threads? [2 marks] void thrprint(int threadid, char *message) { printf("Thread %d: %s ", threadid, message);
(a) Show how a transparent D latch can be constructed using an RS latch and some combinational logic gates. Briefly describe the operation of such a transparent D latch. [4 marks] (b) A 3-bit synchronous counter has a mode control input X. If X = 0, the counter steps through the binary sequence 111, 110, 101, 100, 011, 010, 001, 000, and repeat, or if X = 1, the counter advances through the Grey code sequence 111, 101, 100, 000, 001, 011, 010, 110, and repeat. Draw the state diagram for the counter. [6 marks] (c) A machine has the state diagram shown below, where N and D are two inputs and N = D = 1 cannot occur. The state assignment is S0 = [00], S1 = [01], S2 = [10] and S3 = [11], where the machine starts in state S0 and finishes in state S3. Note that state = [Q1Q0] where Qn is the output of flip-flop n. S0 1 N N N+D D D D.N D.N D.N S1 S2 S3 (i) Write down the state transition table for this machine. [6 marks] (ii) Assuming the use of D-type flip-flops for the state registers, determine the minimised Boolean expressions for the next state functions. [4 marks] 2 CST.2012.2.3 2 Digital Electronics (a) With the aid of appropriate diagrams, show how the Source-Drain current that flows in a p-channel MOSFET is controlled by the applied Gate-Source voltage. [4 marks] (b) (i) Draw the circuit diagram of a NOT gate that comprises an n-channel
(c) For the NOT gate in (b), calculate the power dissipated by the entire gate and that by resistor R alone, when Vin = 12 V. [4 marks] (d) The stray capacitance present at the output of the NOT gate in (b) can be represented by a capacitor, C = 100 nF connected between the gate output and 0 V. Also assume that the MOSFET has an ON resistance Ron = 100 ?. The input signal, Vin, is a 1 kHz square wave with minimum and maximum amplitudes of 0 V and 12 V respectively. (i) Sketch the output signal waveform, Vout, of the NOT gate being sure to include indicative rise and fall times and voltage levels. [4 marks] (ii) How could the rise-time of Vout be reduced and what would be the impact of your proposed solution on the power dissipation of the circuit? [2 marks] 3 (TURN OVER) CST.2012.2.4 SECTION B 3 Operating Systems (a) To switch between processes, an operating system must save the context of the current executing process and restore the context of that being resumed. (i) By what mechanism is the point of execution of a process preserved and restored? [2 marks] (ii) Describe two methods by which the contents of a process address space are preserved and restored. [8 marks] (iii) Give two other elements of process context. [2 marks]
(i) A running process is interrupted by a timer. The timer interrupt service routine determines that the time slice given to the process has not yet expired. [2 marks] (ii) As in (b)(i) but the time slice given to the process has expired. [2 marks] (iii) A running process makes a system call which can be serviced immediately by the kernel. [2 marks] (iv) A running process makes a system call which requires an I/O operation to be initiated. [2 marks]
Expert Answer:
