answer the question clearly

(a) Why is a shared second-level (L2) cache typically divided into multiple banks (banked) in a chip multiprocessor? [3 marks] (b) In what situation might a shared second-level cache offer a performance advantage over a memory hierarchy for a chip multiprocessor with private L2 caches? [4 marks] (c) A cache controller in a chip multiprocessor snoops the bus and observes a transaction that refers to a block that its cache contains. The block is held in State M (Modified). The bus transaction has been generated by a processor wishing to read the block. Assuming a MSI (write-back invalidate) cache coherence protocol, what actions will be taken by the cache controller? [6 marks] (d) How does adopting an inclusion policy simplify the implementation of a cache coherence mechanism in a chip multi

(a) Write brief notes on top-down merge sort, contrasting it with insertion sort. State its worst-case and average-case complexity, with brief justification. (There is no need to present ML code.) [5 marks] (b) Write brief notes on preorder, inorder and postorder tree traversal. Present efficient code for one of them and state, with justification, its worst-case complexity. [5 marks] (c) The binary search tree t1 is superseded by t2 provided every (key, value) entry in t1 is also present in t2. Code an ML function to determine whether one binary search tree is superseded by another. Express its cost in terms of n1 and n2, the numbers of entries in t1 and t2, respectively. For full credit, the worst-case cost should be no worse than O(n1 + n2). [10 marks] All code must be explained clearly. You may assume that any necessary ML data structures or functions are available.(a) Give one difference and one similarity between the programming languages: (i) Algol and SIMULA [2 marks] (ii) LISP and Smalltalk [2 marks] (b) What is the type of the expression fn f => fn x => f(f(x)) inferred by the SML interpreter? Explain your answer. [6 marks] (c) Give an example in the SML Modules language of two distinct signatures, say IN and OUT, and of a functor that takes structures matching IN to produce structures matching OUT. [6 marks] (d) Comment on the mechanism for parameter-passing in the programming language Scala. [4 marks] You may wish to consider the following two code samples. def whileLoop( cond: => Boolean )( comm: => Unit ) { if( cond ) comm; whileLoop( cond )( comm ) } def qsort[T]( xs: Array[T] )( implicit o: Ord[T] ): Array[T] = if( xs.length <= 1 ) xs else { val pivot = xs( xs.length/2 ) Array.concat ( qsort( xs filter (x => x.lt(x,pivot)) ) , xs filter (x => x == pivot ) , qsort( xs filter (x => x.lt(pivot,x)) ) ) }The ML data type BOOL, defined below, is to be used to represent boolean expressions. datatype BOOL = VAR of string | NOT of BOOL | AND of BOOL*BOOL | OR of BOOL*BOOL; The constructor VAR is used to represent named boolean variables, and NOT, AND and OR are used to represent the corresponding boolean operators. Define a function that will return a list of the distinct names used in a given boolean expression. [4 marks] A context is represented by a list of strings corresponding to the boolean variables that are set to true. All other variables are deemed to be set to false. Define a function that will evaluate a given boolean expression in a given context. [3 marks] Incorporate your two functions into a program that will determine whether a given boolean expression is true for all possible settings of its variableYou are a computer architect working on the design of your company's new instruction set architecture for the 21st Century. Analysis of the latest implementation of the current architecture indicates that removal of logic to perform 8- and 16-bit loads and stores could result in a 20% reduction in processor cycle time. You have been assigned to assess the overall performance implications of removing sub-word memory accesses from the current architecture in order to determine whether they will be omitted from the new architecture. First, you need to consider what sequence of instructions will be required to emulate sub-word loads and stores in software using standard instructions. Show the instruction sequences that will be required to load and store a signed byte value given an arbitrary byte address stored in a register. Be sure to state any assumptions you make. [10 marks] Here is a summary of some dynamic instruction mix data that have been collected from the company's current processor executing an important integer benchmark: Instruction Percentage Instruction Percentage load 20% add 18% branch 16% compare 13% store 9% or 8% shift 7% other 9% Of the loads and stores, 94% are 32-bit, 0% are 16-bit, and 6% are 8-bit. Assuming that your instruction sequences are used to replace all the 8-bit memory accesses, estimate the overall performance of the new implementation relative to the one with hardware support for such accesses. [4 marks] In practice, shorter instruction sequences can be used to replace most sub-word accesses on processors without such hardware support. What extra instruction set features or compiler optimisations might be used to reduce the overhead of sub-word memory accesses?Here horizontal and vertical bars indicate walls. One can step from a position to an adjacent position if there is no wall obstructing the move. For example, one can move in one step from position (1,1) to position (2,1), but not to (1,0). Diagonal steps are not allowed. (a) Carefully explain a convenient way of representing such labyrinths in ML. Then define a function, call it next, which takes two arguments, a position (x,y) and a labyrinth, and returns a list of all positions that can be reached in one step from position (x,y). [Hint: Consider representing labyrinths as functions with a type of the form int * int -> something.] [8 marks] (b) Use next to code, in ML, a space-efficient function that checks whether it is possible to move from a position (x1,y1) to another position (x2,y2) in a given labyrinth. For full marks, make sure your function always terminates. [6 marks] (c) Explain, not necessarily using ML code, how one can code a function that returns the shortest path between two given positions. Here path means a list of all the positions one would visit en route to the destination. The solution must be space efficient and practical even for large labyrinths. Briefly explain why your solution is space efficientA puzzle, or one-person game, can be represented in ML by two functions: a next-state function, which maps a state to a list of possible next states, and a wins function, which returns true if the given state counts as a win. A simple example is a puzzle that has states consisting of positive integers, a nextstate function that maps n to [n+ 2, n+ 5], and a "wins" function that returns true if n = 10. We can win if we start from n = 2 but not from n = 7. (a) Code a polymorphic datatype 'a puzzle, to represent a puzzle by the pair of a next-state function and a wins function. [2 marks] (b) Briefly contrast depth-first search, breadth-first search and iterative deepening as techniques for solving such puzzles. [6 marks] (c) Write a function depth that accepts a puzzle, a state and a depth limit. It should use depth-first search to determine whether the puzzle can be solved from the given state within the given depth limit. [6 marks] (d) Write a function breadth that accepts a puzzle and a state. It should use breadth-first search to determine whether the puzzle can be solved from the given state. [6 marks] All code must be explained clearly. You may assume that any necessary ML data structuresNot everything is working as they hoped; for example, sometimes IoT devices can't connect to the Internet to update and your colleague can not connect to their front-door camera when at work. Explain what sort of problems your colleague may face along with methods by which they could verify the root cause. [6 marks] (iii) Explain to your colleague why you might not be able to lend them one of your /64 allocations, even though the /64 blocks (provided to you by your ISP) are each globally routable addresses. [2 marks] (b) A local area network may carry several different LANs simultaneously; such a network would be designated for known sets of HomePlug devices. Describe a physical line coding approach for the HomePlug devices that: allows two or more simultaneous virtual local area networks to fairly share the same physical channel, but does not permit trivial interception of network traffic. Outline your approach along with its benefits and drawbacks, comparing it with the simplest use of VLAN tags in EthernetThe network illustrated above represents an Ethernet Layer-2 network that uses spanning-tree to compute forwarding tables. Assume all links have a link-weight of one. [Note: Tie-breaking/leader-elections use the switch identifier from this diagram.] (a) Compute the steady state routing/forwarding table for Switch 3. [4 marks] (b) Noting which switches recompute a solution, enumerate the changed forwarding tables in switches of this network resulting from the complete failure and removal of link D. [9 marks] (c) Following the removal of Link D, a new link H is added between Switch 1 and 4; however, this link fails frequently. Denied access to monitor the network-traffic, outline a diagnostic strategy to identify the faulty Link H, making clear how the network-operator might use interrogation of network switch forwarding tables. [4 marks] (d) Now suppose the switches do not permit interrogation of switch forwarding