Two independent threads are run on different processors in a chip-multiprocessor

Subject:Computer SciencePrice:9.82 Bought3

Share With

Two independent threads are run on different processors in a chip-multiprocessor.
Each thread simply increments a private counter one million times. The two
counters are stored in consecutive memory locations. It is discovered that
running the threads sequentially is faster than running them in parallel. What
may cause this type of behaviour?
(b) Cache coherence protocols are classified as either invalidate or update protocols.
What are the potential advantages and disadvantages of adopting an update
rather than an invalidate protocol?
(c) Sequential consistency offers a simple and intuitive memory consistency model.
Why is sequential consistency rarely supported by modern chip-multiprocessor
designs?
(d) What information does the directory provide in a directory-based coherence
protocol?

 

 

address all questions

(a) In at most five sentences, describe the kd-tree data structure and its use in ray
tracing. [3 marks]
(b) Several formulae were discussed in the course for calculating the normal to a
discrete surface at a vertex.
(i) In at most five sentences, explain why all of these formulae are necessarily
approximations; and why a true answer is impossible. [3 marks]
(ii) Give the best (most nearly accurate) formula discussed in the course.
[1 mark]
(c) The angle deficit is a method for measuring discrete curvature. Give the formula
for the angle deficit of a vertex v. [1 mark]
(d) A simple closed discrete surface has 148 vertices, 248 edges and 80 faces. What
must its genus be, and why? [2 marks]
(e) An implicit surface system is described by the force function f(r) = 1/r2
, the
threshold t = 1.0, and a set of generating points.
(i) A surface is defined by two generating points at (−x, 0, 0) and (x, 0, 0).
What is the largest value of x such that the surface forms a single
component? [2 marks]
(ii) A surface is defined by three generating points, positioned in an equilateral
triangle at (−1, 0, 0), (1, 0, 0), and (0,
√
3, 0). Does the surface form a single
component of genus 0, a single component of genus 1, or three separated
components of genus 0? [1 mark]
(iii) If the set of generating points is described as v ∈ V we can write the
equation for the total value of the force F(x) at a point x in space as
F(x) = X
v∈V
1
|x − v|
2
Give an expression for F(x) if the surface were instead defined by infinite
generating lines of force, where each generating line, L, is expressed by two
points [A, B]. If your expression is correct, the implicit surface described
by a single line [A, B] will be an infinite cylinder of radius one centred on
the axis [A, B]. [3 marks]
(iv) Modify your definition to treat each generating line as a finite line segment
from A to B. A single generating line should describe a surface that is a
finite cylinder with spherical end caps. [2 marks]
 

Evil Robot hates kittens. He has invented the kitty-destroyer (KD) to rid the world of
their menace. To test it, he has a kitten (K) next to the KD on his laboratory bench
(B). He has to open the KD, place the kitten inside it, close it and press the start
button (SB). He has not however established that this sequence of events will lead to
his goal of a destroyed kitten. Evil Robot is equipped with a planning system based
on a solver for constraint satisfaction problems, and wants to use this to construct a
plan.
(a) Explain how this problem can be represented using the state-variable representation, including in your answer specific examples of a domain, a rigid relation,
a state variable and an action for the problem. [7 marks]
(b) Give one reason that a state-variable representation might be preferable to a
representation aimed at encoding to a satisfiability problem. [1 mark]
(c) Explain, giving a specific example for this problem, how the action taken at
some time t can be encoded as part of a constraint satisfaction problem.
[3 marks]
(d) Explain, giving a specific example for this problem, how a state-variable can be
encoded as part of a constraint satisfaction problem.

 

Consider the following class PrimeNumbers, which has three methods. The first, computePrimes() takes one integer input and calculates that many prime numbers. Iterator() returns an Iterator object that will iterate through the primes, and toString() returns a string representation.

public class PrimeNumbers implements Iterable<Integer>
{
private List<Integer> primes = new ArrayList<Integer>();
public void computePrimes (int n)
{
int count = 1; // count of primes
int number = 2; // number tested for primeness
boolean isPrime; // is this number a prime
while (count <= n)
{
isPrime = true;
for (int divisor = 2; divisor <= number / 2; divisor++)
{
if (number % divisor == 0)
{
isPrime = false;
break; // for loop
}
}
if (isPrime && (number % 10 != 9)) // FAULT
{
primes.add (number);
count++;
}
number++;
}
}

@Override public Iterator<Integer> iterator()
{
return primes.iterator();
}

2

@Override public String toString()
{
return primes.toString();
}
}

computePrimes() has a fault that causes it not to include prime numbers whose last digit is 9 (for example, it omits 19, 29, 59, 79, 89, 109, ...).

Normally, this problem is solved with the Sieve of Eratosthenes. The change in algorithm changes the consequences of the fault. Specifically, false positives are now possible in addition to false negatives.

(a) Reimplement the algorithm for calculating primes using the Sieve of Eratosthenes approach, but leave the fault in place.

(b) What is the first false positive and how many primes must a test case generate before encountering it?

(c)  A test must reach a location in a program that contains the fault (reachability). After the location is executed, the state of the program is incorrect (infected). The infected state must propagate through the execution and cause some output of the final state of the program to be incorrect (propagation). Finally, the tester must observe part of the incorrect portion of the final program state (revealability). (This all serves to illustrate that testing is actually really complicated!) What does this example illustrate about these four concepts?

 

j,this file is named HW3.Java can someone run it through a GNU compiler and please show me the outputs

the input arguements are

$ java HW3 p1 p1.txt 6

import java.io.FileWriter;
import java.io.IOException;
public class HW3 {
public static void main(String[] args) throws IOException {
// 0th argument contains the name of algorithm
String algo = args[0];
// 1st argument contains the name of file
// Make a new file
FileWriter fw = new FileWriter(args[1]);
if (algo.equals("p1")) {
// 2nd argument comes in the form of string.
// convert it to intger and run a loop
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
double[] x = new double[(int) Math.pow(10, i)];
// use start and end for recording time
long start = System.currentTimeMillis();
prefixAverage1(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("p2")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
double[] x = new double[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
prefixAverage2(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("e1")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
int[] x = new int[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
example1(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("e2")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
int[] x = new int[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
example2(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("e3")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
int[] x = new int[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
example3(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("e4")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
int[] x = new int[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
example4(x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
} else if (algo.equals("e5")) {
for (int i = 1; i <= Integer.parseInt(args[2]); i++) {
int[] x = new int[(int) Math.pow(10, i)];
long start = System.currentTimeMillis();
// You can take a new array here, I am just running it for x here
example5(x, x);
long end = System.currentTimeMillis();
double totalTime = Math.log10(end - start);
fw.write(String.valueOf(totalTime));
String newLine = System.getProperty("line.separator");
fw.write(newLine);
}
}
fw.close();
}
public static double[] prefixAverage1(double[] x) {
int n = x.length;
double[] a = new double[n];
for (int j = 0; j < n; j++) {
double total = 0;
for (int i = 0; i <= j; i++) {
total += x[i];
a[j] = total / (j + 1);
}
}
return a;
}
public static double[] prefixAverage2(double[] x) {
int n = x.length;
double[] a = new double[n];
double total = 0;
for (int j = 0; j < n; j++) {
total += x[j];
a[j] = total / (j + 1);
}
return a;
}
public static int example1(int[] arr) {
int n = arr.length, total = 0;
for (int j = 0; j < n; j++)
total += arr[j];
return total;
}
public static int example2(int[] arr) {
int n = arr.length, total = 0;
for (int j = 0; j < n; j += 2)
total += arr[j];
return total;
}
public static int example3(int[] arr) {
int n = arr.length, total = 0;
for (int j = 0; j < n; j++)
for (int k = 0; k <= j; k++)
total += arr[j];
return total;
}
public static int example4(int[] arr) {
int n = arr.length, prefix = 0, total = 0;
for (int j = 0; j < n; j++) {
prefix += arr[j];
total += prefix;
}
return total;
}
public static int example5(int[] first, int[] second) {
int n = first.length, count = 0;
for (int i = 0; i < n; i++) {
int total = 0;
for (int j = 0; j < n; j++)
for (int k = 0; k <= j; k++)
total += first[k];
if (second[i] == total) count++;
}
return count;
}
}

 

 

(a) A key/value store holds pairs of strings in a non-volatile memory (NVM). The
NVM is mapped as a memory region between two hardcoded virtual addresses,
NV START and NV END. This memory is all set to zero as manufactured and
can be freely read, but any write operations result in a logical ORing of the new
data with the old data at the addressed location. Bits can never be cleared.
Strings representing keys and values will be fewer than 250 characters long.
Eventually the memory will fill up, but sufficient is available for the intended
application.
The API provides the following two operations:
int store(char *key, char *value) // returns non-zero on error, and
char *lookup(char *key) // returns NULL if not found.
Provide a full C implementation of the store routine, explaining how the lookup
function and changes to values under a given key would work, if this is not
obvious from your code. Code efficiency is not important.
Hint: You can directly access the non-volatile store using a construct such as
((char *)NV_START)[offset]. [10 marks]
(b) The following text almost constitutes both a C++ and Java program:
class Foo { public: int x, y; };
class Test {
private: void f1(Foo p) { p.x = 1; }
private: void f2(Foo &q) { q.y = 2; } //[Java]: ignore '&'
public: void test() {
Foo p; //[Java]: replace with: 'Foo p = new Foo();'
p.x = p.y = 99;
f1(p);
Foo q = p;
p = q;
f2(q);
print("HERE");
}
};
(i) Explain the storage structure accessible from variables x and y when control
reaches print("HERE") following a call to test(), both in the Java and
the C++ interpretations. [3 marks]
(ii) For the C++ interpretation, show how adjustments only to the definition
of class Foo can cause (useful) debugging-style output to be produced at
as many places as possible during the execution of method test().

 

(a) Into what three cases can a linear program in standard form be classified?
[3 marks]
(b) Consider the (unweighted) vertex cover problem for the graph G = (V, E) with
V = {1, 2, 3} and E = {{1, 2}, {2, 3}, {1, 3}}.
(i) Write down the linear program relaxation for the vertex cover problem and
solve the linear program. [6 marks]
(ii) Based on the solution of the linear program in (b)(i), derive an integer
solution using the rounding approach described in the lecture. [2 marks]
(c) Consider the following randomised algorithm for the unweighted vertex cover
problem:
Initialize S to be the empty set
For all edges e=(u,v) do
If neither u nor v belongs to S
Randomly choose u or v with probability 1/2
and add the vertex to S
End If
End For
Return S
Derive an upper bound, as tight as possible, on the approximation ratio of the
algorithm.
Hint: Try to find an invariant that bounds from below the size of the intersection
of the current solution S = S(i) with the optimum solution, where S(i) denotes
the set S after the i-th iteration of the FOR loop.

 

You are a 22nd century historian researching the "FEE" (First Epidemic Era) of
2019-2025, for which records are patchy. You research which government policy was
in place in any given week during this historic phase. Policies, in order of severity,
are: No restrictions, Tier 1, Tier 2, Tier 3, and Lockdown.
(a) From other historic sources, you know the following about sequences of policy
levels: if you are in a given policy level, there is a 40% chance you will stay
there, a 20% chance that you will be upgraded to the next-highest (more
severe) level next week, and a 10% chance that you will be downgraded to
the next-lowest (less severe) policy level. The background lockdown probability
(which applies if nothing more informative is known about lockdown) is 10%. For
each observation sequence, there is also a 5% chance of the sequence ending at
any point. Transitions to any other policy level beyond those already described
are equally likely. Observation sequences begin with each policy level at equal
likelihood.
Using the information given above, construct the full transition probability table.

(b) You want to estimate which policy was in place for the first six weeks of 2025,
but unfortunately, the only information you have about this is a sequence of
Covid case numbers for these six weeks:
[0 − 99], [0 − 99], [> 200], [> 200], [> 200], [100 − 199].
You know that case loads are associated with policy levels as in the Table below.
Describe how you can calculate the sequence of most likely policy levels for these
6 weeks, giving numbers for at least three steps of the calculation. Assume that
all policies are equally likely in the week preceding the first week.

 

Write  program that will ask the user to enter your name and your class section
Write a c program to count the total number of commented characters and words in a c file taking both types of c file comments (single line and block) into account.

 Write  program to print all natural numbers in reverse (from n to 1). - using loop 
 

 

Given the following class: class Q2 { private int a; private int b; private int c; public void setAint a)this.a = a; } public void setB(int b{this.b = b;} public void setc(int c){this.C = } public int geta0{return a;) public int gets0freturn b;} public int getc0{return c} public int m1int a, int b){ return a + b; public boolean m2 (int x, int y)} return m1(x, y) +x + y < 10; What is the output of the following code segment: Q2 0bji = new Q20: y 10; What is the output of the following code segment? Q2 obj1 = new Q20; Q2 obj2 = new Q20; obji.setA(0); obj1.setB(e); obj1.setC(10); obj2.setA(4); obj2.setB (5); obj2.setc(-1), while(lobj1.m2(1, 3)) {obj2.setc(obj2.getc) + 10); System.out.println("obj2.c = "+ obj2.getc0); A. obj2.c = 10 B. obj2.c = 9 C. Infinite loop D. obj2.c = 1