Distribute one disjunction from the formula over a conjunction or fail if no such disjunction exists: A (B C) ' (A B) (A C) [6 marks] (iv) Repeatedly apply the distribution step until no more distribution can be done [4 marks] Ensure that your predicates behave appropriately with backtracking, avoid over-use of cut, and are commented appropriately. Minor syntactic errors will not be penalised. 9 (TURN OVER) CST.2013.3.10 9 Software Engineering Google have spent several years developing self-driving cars which rely on a range of sensors and stored data and are now claimed to have covered hundreds of thousands of miles with a good safety record. A Google executive has now asked to meet the Transport Secretary, who has in turn asked your company for advice. What sort of safety case should the government demand from vendors and service providers if autonomous vehicles are to be allowed on Britain's roads? [20 ma

a) What is the difference between production test and functional test? [2 marks] (b) What is path sensitisation for production test? Provide an example. [4 marks] (c) Below is the circuit for a JTAG scan flip-flop. How are the signals TI, TO, TE and CLK used to undertake production test? [6 marks] (d) In SystemVerilog, what is the purpose of an "initial" block and how is timing specified? [4 marks] (e) What is static timing analysis and why is it important for a design to pass timing if it is to be functionally correct? [4 marks] 2 CST.2013.5.3 2 Computer Design The version of Thacker's Tiny Computer 3 (TTC3) that was used in the 2012 ECAD Laboratory sessions (instruction set summary is below) has the following pipeline stages: fetch decode/register fetch execute/memory access write-back Currently the implementation only supports one instruction in the pipeline at a time, i.e. the next instruction is only fetched when the current one finishes in the write-back stage. If the implementation were to attempt to fetch a new instruction every clock cycle, explain the following microarchitectural issues: (a) What data hazards would exist and how can they be resolved whilst preserving the programmer's sequential model? [5 marks] (b) What are control hazards and how can we avoid exposing them to the programmer? [5 marks] (c) When are branch target addresses computed on the TTC3 and how many bubbles will be introduced when taking a jump? Assume that such a tiny computer would not have a branch predictor. [5 marks] (d) On the TTC3, every instruction (except jump) can conditionally skip the next instruction. How might skip be implemented and how many pipeline bubbles need to be introduced? [5 marks] TTC3 Instruction Set Summary 31 2425 17 10 57 03 Rw Ra LC Rb Func Shift Skip Opcode Function: 0: A+B 1: A-B 2: B+1 3: B-1 4: A & B 5: A | B 6: A ^ B 7: reserved Shift (rotates right): 0: no shift 1: RCY 1 2: RCY 8 3: RCY16 Skip: 0: never 1: ALU<0 2: alu=0 3: inrdy opcode: 0: normal: rw=F(Ra,Fb), skip if condition 1: storedm: dm[rb]=Ra, storeim: im[rb] =Ra, out: outstrobe, 4: loaddm: 5: in: 6: jump: pc =F(Ra,Rb), no 7: reserved lc=load constant (bits 23:0 of the instruction), counter where function is specified by func bits f(ra,rb) =rotate(Shift, alu), rotation shift 3 (turn over) cst.2013.5.4 computer design (a) moore's law an observation gordon moore in 1960s that trends electronic manufacturing technology would result transistor density doubling every 18 to 24 months. (i) explain how can be applied processor speed and hard disk density. [5 marks] (ii) today scaling favours transistors over wires thermal densities limit performance. why this resulting commercial chips having many cores rather than one high-performance core? (b) pci, used connect i o boards a pc, has been replaced with pcie. transition resulted parallel communication being bundles serial channels. what difference between communication? are multiple channels now preferred link? might latency single load register on pcie device take longer pci? 4 cst.2013.5.5 networking spy elects use self-synchronizing scrambler encode his secret message. will not give him any privacy self-synchronisingapproach better communications engineer. assistance annotated diagrams csma cd ca. your explanation, note physical constraints packets networks these approaches impose. [10 (c) consider network buffer sizing formula b =2T c formula. [2 discuss architecture traffic assumptions made [3 5 cst.2013.5.6 here four options for improving web page option http caching forward proxy cdn using dns anycast based rewriting html urls you have asked help reduce costs university. university pays its service provider networks'r'us, bandwidth it uses; dominated students downloading external pages. which, any, above usage? choice. [4 delivery online courses become tremendous success - but led significant increase must select minimize servers. compare operation each justify selection provides finest granularity control content-servers serve customer from closest server. [12 looked up ip address favourite searchengine noticed answerdifferent given friend when he did lookup newfoundland, canada. above, indicate might, or not, improve 6 cst.2013.5.7 considering either tcp udp ip, write description server-port, client-port, source-port destination-port relate other. may wish examples as appropriate. routing-loop? include diagram answer. describe mechanism prevents routing-loops ethernet networks. (d) and, aid example, illustrate time-to-live (ttl) minimising impact routing-loops. assuming, part (d)(i), perfect implementation, disadvantage including symptoms experienced subject disadvantage, test identify problem. (e) technical architectural argument behind decision ipv6 retain header ttl checksum. (f ) there ambiguity about handling values 1 practical solution. 7 cst.2013.5.8 concurrent distributed systems deadlock classic problem systems. necessary conditions deadlock? often explained dining philosopher's pseudo-code, fork represented lock: lock forks[] =new lock[5];>

Consider IEEE single-precision arithmetic. How are the 32 bits arranged in terms of sign, exponent and significand? How is the exponent stored? Explain the terms normalized number, denormal number. What is the hidden bit and how is it used? How are negative numbers stored? What does NaN stand for? Give an example of an operation that yields a NaN value.

What is meant by saying that a model for computation offers unlimited data storage but is restricted to finite logic? How would you record the configuration during computation within such a model? Illustrate your ann a k-symbol Turing machine having searching states. Show how to represent the transition from the configuration at time t to the configuration at time t + 1 by a system of arithmetic equations. Hence show that any Turing machine computation may be simulated by a register machine having a suitable program

answer all

Discuss capability-based access control under the headings protection of capabilities control of transfer of capabilities between principals delegation of rights revocation of capabilities Your answer should mention the differences between the management of capabilities in distributed as opposed to centralised systems. You should consider alternative designs of capabilities.

What is a leaky bucket algorithm? How can it be used to police traffic? How can it be used to shape traffic? [5 marks] You are required to provide a flow admission controller for a router. RSVP is used to request resources for flows with leaky bucket parameters. Outline how you would design the controller, bearing in mind the soft state nature of RSVP. [15 marks]

An M/M/m queue has an arrival process with mean rate , and processes customers at a mean rate of . (a) What are the distributions and parameters of the inter-arrival and service times of customers? [3 marks] (b) Sketch an outline proof showing that the distribution of the departure process from the queue is the same as that of the arrivals process. [10 marks] Briefly contrast analytical queueing analysis and discrete event simulation with regard to their fields of applicability and other important considerations for the systems modeller. [7 marks] 4 VLSI Write short notes on two of the following: (a) the fundamental limits which may slow down progress in semiconductor technology; (b) designing VLSI systems for low-power applications; (c) problems which can prevent an apparently properly designed chip from working to specification.

You are assigned the role of UK sales and marketing manager for a new kind of low-cost computer, primarily aimed at the educational market. Whilst not directly PC compatible, the computer includes web access, PC-compatible word processing, other PC-compatible productivity tools, and a suite of educational programs. How would you approach this task? Draw up an outline business plan as follows. (a) Show what communication and distribution channels you propose. [5 marks] (b) Propose a selling price, and estimate the number of units you might sell at this price. [5 marks] (c) Estimate a 3-year budget for the sales and marketing activity. [5 marks] (d) State how you would refine your estimates, and what monitoring you would put in place. [5 marks] Background information: There are about 32,000 schools in the UK. The UK government has recently published a consultative document The National Grid for Learning with a proposal to spend 100M on provision of internet access in schools over the next 5 years. This sum includes infrastructure provision, content development and teacher training, as well as a contribution to provision of computers in schools. The average school IT spend is projected to be 18,000 each year. Additional funding may be available from government and parents for specific projects. The unit manufacturing cost is 200, delivered.

Describe the structure of an ordinary heap, and document the costs associated with the following operations. (a) Create heap from n items where the items are all available at once but are initially in a random order. (b) Remove the top (i.e. smallest) value stored in the heap. (c) Given a pointer to an arbitrary item in the heap, re-instate the heap property after the key associated with that single item is decreased in value. (d) Form a new heap whose elements are all those that are present in two other heaps (which may be destroyed in the combining process if that helps). You are not expected to give detailed accounts of the algorithms involved. [6 marks] Now explain the structure of a Binomial Heap and compare, with some explanation of your claims, the costs incurred in the same set of operations if Binomial rather than ordinary heaps were to be used. [14 marks]

Consider the programming language with terms e having abstract syntax: e ::= x | c | x.e | e1e2 | let x = e1 in e2 where x ranges over a set of identifiers and c over a set of integer constants. For the rest of the question, your answers can be illustrated by reference to the program p: z.let id = x.x in id id 7 State how to label terms in p uniquely so that a subterm occurring repeatedly in a term has different labels. [4 marks] Show how such terms may be seen as a family of flowgraphs, one for each (you may find it useful to consider the above labelling as providing a unique function name for anonymous -abstractions). [4 marks] Define the call graph of such a family of flowgraphs, stating clearly how indirect calls are treated. [4 marks] Describe how to associate a flow-variable with each labelled node of a term such as p and to derive equations which can improve the above treatment of indirect calls to get a better approximation of the edges in the call graph. [8 marks] [Hint: you may find it useful to recall the shorthand of ( 7 ) as representing the compound constraint that whenever (xj .ek ) i we have j k where r is the flow variable associated with the node labelled r.]

When using a feed-forward network to solve a classification problem we can interpret the network's outputs as posterior probabilities of class membership, and then subsequently use these probabilities to make classification decisions. Alternatively, we can treat the network as a discriminant function which is used to make the classification decision directly. Discuss the relative merits of these two approaches. [7 marks] Explain the concept of a likelihood function, and the principle of maximum likelihood. [3 marks] Consider a feed-forward network which implements a function y(x, w) in which y is the output variable, x is the vector of input variables, and w is the vector of weight parameters. We wish to use this network to solve a classification problem involving two classes A and B. The value of y, when the network is presented with an input vector x, is to be interpreted as the posterior probability P(t = 1|x) in which t = 1 denotes class A and t = 0 denotes class B. Write down the probability distribution of t given y. Use the principle of maximum likelihood to derive an expression for the corresponding error function defined over a set of training data comprising input vectors xn and targets tn, where n = 1, . . . , N. Write down a suitable form for the output unit activation function y = g(a). Hence evaluate the derivative of ln P(t|y) with respect to a. Describe those provisions of the following Acts of Parliament that are relevant to computer security: The Civil Evidence Act of 1968 The Police and Criminal Evidence Act of 1984 The Data Protection Act of 1984 The Computer Misuse Act of 1990

A software house incorporates a time-lock which causes their product to stop working if it is not supplied with a suitable password every 6 months. What risks are they running? [4 marks] A hospital de-identifies patient records by removing names and addresses, leaving only the patient's postcode and date of birth as an identifier. These records are then sold to researchers and drug companies. What risk is the hospital running?