(a) What is the critical path of a synchronous clock domain and how…
Question Answered step-by-step (a) What is the critical path of a synchronous clock domain and how… (a) What is the critical path of a synchronous clock domain and how does it affect performance? [2 marks] (b) Name two tools that can be used for locating the critical paths of a system on chip before fabrication. Which is faster or better and why? [4 marks] (c) Explain how pipelining can alter performance. What are its disadvantages? [4 marks] (d) How does pipelining alter the state encoding for a sub-system? [2 marks] (e) Name a tool that can be used to formally check whether a minor design change has altered the behaviour of a subsystem where the state encoding has not been changed. Name another tool for use when the state encoding may have been changed. [2 marks] (f ) Using any combination of diagrams, SystemC or RTL, sketch two implementations for a design of your choosing that use a different number of flip-flops to achieve the same functionality. Explain whether the reports from each of your two tools from part (e) might differ for your two implementations. [6 marks]Consider the following grammar: ce, cats} V ? {saw, grinned} (a) The grammar can be used to generate the following sentences: (i) Alice saw cats (ii) Cats Alice saw grinned Draw derivation trees for both of these sentences. [2 marks] (b) What is the longest sentence that can be generated by the grammar? Describe this sentence. [2 marks] (c) Is the language generated by the grammar a regular language? Provide a proof for your answer. [8 marks] (d) A psycho-linguistic experiment shows that, by the 2nd word in the sentence, Part (a)(ii) is harder to process than the sentence Part (a)(i). Yngve hypothesised that a speaker’s short-term memory functions as a stack. Explain how this hypothesis might account for the experimental results by drawing the stack arising from a top-down parse of the two sentences. [4 marks] (e) How might the sentence in Part (a)(ii) be altered so that it has the same meaning but is easier to process? Explain your reasoning.A Boolean satisfiability problem has four variab? x3) ? (x2 ? x3) ? (x1 ? x2 ? x4). (1) The aim is to find assignments to the variables such that f is true under the usual rules for Boolean operations. This question addresses the use of more general constraint satisfaction to solve this problem. (a) Give a general description of a constraint satisfaction problem (CSP). [3 marks] (b) Explain how a Boolean satisfiability problem in CNF form and with n variables can be converted to a CSP, also having n variables and having a suitable constraint for each clause. Illustrate your answer using the 4-variable formula f in (1). [3 marks] (c) Explain, again using a constraint corresponding to a clause from (1), how general constraints can be converted to binary constraints. Provide a graph illustrating the problem from (1) after it has been converted to a CSP with only binary constraints. [4 marks] (d) Explain, how forward checking works in the context of a general CSP. How does this benefit a CSP solver? [3 marks] (e) Using the CSP equivalent you developed for (1), with only binary constraints, demonstrate how forward checking works using the sequence of assignments x1 = F, x2 = F, x4 = T. [5 marks] (f ) How would you expect the solution obtained when applying forward checking to be affected if constraints were allowed to propagate more widely? [2 marks] A program is required to draw an arc from (0, 1) to (1, 0) of the circle centred t the origin with unit radius. (a) One approach would be to draw a segment of the cubic Overhauser curve defined by (?1, 0), (0, 1), (1, 0) and (0, ?1). (i) Explain how a segment of an Overhauser curve in general can be represented as an Hermite cubic and so as a B´ezier cubic. [4 marks] (ii) Derive the formula for the resulting B´ezier curve, P(t). [3 marks] (iii) Calculate the coordinates of P( 1 2 ). How large is the error? [Hint: ? 2 ? 1.414.] [3 marks] (b) Calculate revised control points for the B´ezier curve so that it models the circular arc more accurately. [4 marks] (c) Describe in outline an alternative way of efficiently drawing the arc by calculating the pixels that lie on it directly.(a) State what is meant by a directed graph and a strongly connected component.Illustrate your description by giving an example of such a graph with 8 verticesand 12 edges that has three strongly connected components. [5 marks](b) Describe, in detail, an algorithm to perform a depth-fifirst search over such agraph. Your algorithm should attach the discovery and fifinishing times to eachvertex and leave a representation of the depth-fifirst spanning tree embeddedwithin the graph. [5 marks](c) Describe an O(n) algorithm to discover all the strongly connected componentsof a given directed graph and explain why it is correct. You may fifind it usefulto use the concept of the forefather ?(v) of a vertex v which is the vertex, u,with highest fifinishing time for which there exists a (possibly zero length) pathfrom v to u. [10 marks]2 Computer Design(a) What is a data cache and what properties of data access does it exploit?[5 marks](b) What is a direct mapped cache and under what conditions will it exhibit poorperformance? [5 marks](c) Under what circumstances might a word of data in main memory besimultaneously held in two separate fifirst-level cache lines? [5 marks](d) A translation look aside buffffer is a specialised cache. What does it typicallystore and why is it often a factor of 1000 smaller than a data cache? [5 marks]2CST.2001.6.33 Digital Communication I(a) Defifine the terms circuit and packet in the context of communication systems.[5 marks](b) What sort of guarantee does circuit switching provide? [5 marks](c) What advantages does packet switching provide over circuit switching?[5 marks](d) Which of frequency division multiplexing, time division multiplexing and codedivision multiplexing lend themselves to circuit switching? Which to packetswitching? Explain why or why not in each case. [5 marks]4 Computer Graphics and Image Processing(a) Describe the z-buffffer polygon scan conversion algorithm. [10 marks](b) In ray tracing, once we have determined where a ray strikes an object, theillumination at the intersection point can be calculated using the formula: Explain what real effffect each of the three terms is trying to model and explainwhat each of the following symbols means, within the context of this formula:I, Ia, i, Ii , ka, kd, ks,Li, N, Ri, V, nImage transcription text10. (10pts) Recall the attributed grammar from question 8. Consider the following de- notational semantics:densem(
