Exam cards

Question 1

State Moore’s Law

Answer 1

The number of transistors in a dense integrated circuit doubles about every two years. OR: Computer power doubles every 19-24 months while the cost effectiveness keeps pace.

Question 2

Explain cost-effectiveness of hardware

Answer 2

Cost-effectiveness is the ratio between the performance and cost of hardware

Question 3

Explain the killer-micro effect

Answer 3

Additional hardware resources generated by the rapid increase in transistor density were utilized to increase the speed/frequency of single CPU-systems resulting in complex designs of muscled single processors relying on out-of-order dataflow execution model.

Question 4

What are the two main capabilities of the out-of-order (data-flow) execution, model?

Answer 4

1. storing in their pipeline thousands of instruction. 2. executing hundreds of instructions per cycle.

Question 5

Explain the divergence between academic interest in parallel architectures, and industries focus on muscled single processor systems

Answer 5

Muscling single CPU systems was seen as the path of least resistance as it required no rewriting of code while converting to parallel architectures requires significant rewriting which is tedious and non-trivial.

Question 6

What was the tectonic shift towards multiprocessor design?

Answer 6

In 2004 Intel cancelled the design of the Pentium 4 GHz and switches to multicore design

Question 7

What is the power wall?

Answer 7

Dynamic power is proportional to the cube of frequency

Question 8

What is the memory wall?

Answer 8

The seemingly exponentially-increasing performance gap between processor and memory

Question 9

Commodity parallel architectures such as GPUs provide thousands of cores and tens of thousands of threads. What is the main barrier to utilizing this power?

Answer 9

The lack of high-level programming models and compiler optimizations that would allow commodity software to harness the power.

Question 10

What are a program and a process/thread?

Answer 10

A program is a set of statements for performing computational tasks while a process/thread embeds the execution of the computation. A program is to the process/thread what a
the recipe is for cooking

Question 11

What is a processor/core and what is a multithreaded core?

Answer 11

The hardware entity capable of sequencing and executing a process/threads instructions. Multithreaded cores support multiple hardware threads, each running in its own hardware context.

Question 12

What is a multiprocessor?

Answer 12

A multiprocessor is a set of processors connected to execute a workload. Each multiprocessor consists of several cores - potentially with hardware multithreaded support and several levels of cache.

Question 13

Name the three main improvement types in processor design

Answer 13

1. Deeper piplines (10-20 stages) - more stages = less complex single stages = less gates per stage, i.e each stage is quicker hence larger clock rate.
2. Aggressively exploiting instruction level parallelism (ILP) for example by out-of-order execution, speculative execution which combine techniques such as register renaming, reordering
   buffers, branch predication, lockup-free caches, speculative memory disambiguation.
3. improvements in circuit design

Question 14

Why is it unsustainable to carry on improving the clockrate?

Answer 14

• First, it is unfeasible to build deeper pipelines because it is difficult to imagine useful stages
that can be built from less than 10 gates (we have already reached that point).
• Second, the impact of technology scaling will be blunted in the future due to wire delays,
which do not scale, because the speed of wire transmission grows much slower than the
switching speed.
• Finally, and perhaps most importantly, circuits clocked at higher rates consume more power,
and we have already reached the limits of power consumption in single-chip microprocessors.

Question 15

Which hardware optimizations can we do other than increasing clock rate?

Answer 15

Reduction of feature size and increasing the number of transistors.

Question 16

How can we utilize an increased number of transistors?

Answer 16

We can
1. Enhance the parallelism of the memory system.
2. Fetch and decode multiple instructions per clock.
3 Run concurrently multiple hardware threads per core, for example in order to hide the high latency of the memory system
4 Support thousands of cores that run threads in parallel on different corres.

Question 17

How much does DRAM density increase every third year (historically)?

Answer 17

4 x

Question 18

How much does DRAM speed increase each year (historically)?

Answer 18

7%

Question 19

The memory wall has been replaced by what?

Answer 19

A bandwidth wall. This is because nowadays, the memory subsystem
needs to efficiently feed cores that execute threads in parallel, which means that the memory system
has to be capable of delivering multiple data in the same time, which is measured by bandwidth.

Question 20

Name the four technological limits in architectural design

Answer 20

Power, wire delays, reliability and complexity of design

Question 21

Explain what the power constraint is and why it favours parallel processing over an increase in the clock rate.

Answer 21

The power constraint is that the power consumed by a processor is given by the sum of dynamic and static power and is not limitless. The dynamic power is consumed by gate switching. Dynamic power is roughly proportional to the cubic power of the frequency. Hence increasing the frequency requires much more power than replicating a uniprocessor.

Question 22

What is leakage power and how is it related to dynamic power?

Answer 22

Leakage power is the same as static power and is dissipated in all circuits at all times independent of frequency and switching. It is dominated by cache leakage. the leakage power increases exponentially as the voltage at which a transistor switches off is reduced. Smaller feature sizes and lower threshold voltage means that leakage power has overtaken dynamic power as the major source of dissipation.

Question 23

What are the three classifications of hardware failures

Answer 23

Transient failures (Soft error): due to voltage reduction in every process generation bits are more and more prone to flip. The device is operational but data may be partly corrupted.
Intermittent/Temporary failures: Result of environmental variations on the chip such as hot spots. In order for device to return to correct behavior the issue must be fixed (turn off and cool down).
Permanent failures: can not be fixed.

Question 24

Why do multiproccesors promote more reliablility than uniprocessor systems?

Answer 24

Threads can be used to redundantly perform the same computation and compare results. Faulty cores can be detected and disabled while the system remains functional.

Question 25

The propagation delay on a wire is proportional to what?

Answer 25

the product between its resistance and capacitance.

Question 26

The resistance of a wire is proportional to what?

Answer 26

the ratio between the cross-section area and the length of the wire.

Question 27

What happens to the length of wires at each process generation? Is this good or bad for resistance?

Answer 27

It shrinks. Good!

Question 28

What happens to the cross-section area of wires at each process generation? Is this good or bad for resistance?

Answer 28

It shrinks. Bad!

Question 29

Why is the impact of wire delay lower for multiprocessors?

Answer 29

Communication traffic is hierarchical:

most communication is local, while inter-core communication only happens occasionally.

Question 30

Why does the cost of design verification favour mulitprocessors?

Answer 30

It is much easier to replicate the same

structure multiple times than it is to design a large and complex system

Question 31

How is feature size defined?

Answer 31

half the distance between two metal wires.

Question 32

What is the definition of a monoid?

Answer 32

Definition 1 (Monoid).
Assume a set S and a binary operator ⊙ : S × S →S.
(S, ⊙) is called a monoid if it satisfies the following two axioms:
(1) Associativity: ∀x,y, z ∈ S we have (x ⊙ y) ⊙ z ≡ x ⊙ (y ⊙ z) and
(2) Identity Element: ∃e ∈ S such that ∀a ∈ S, e ⊙ a ≡ a ⊙ e ≡ a.

Question 33

What is the definition of a group?

Answer 33

Definition 2 (Group).
(S, ⊙) is called a group if it is a monoid satisfying the additional property that any element is invertible:
∀a, ∃a−1 such that a ⊙ a−1 ≡ a−1 ⊙ a ≡ e.

Question 34

State whether (Z, +), (N, +), (Z, ×) are monoids and groups

Answer 34

(Z, +): monoid and group, (N,+): monoid but not group, (Z, ×): monoid not group

Question 35

Give the definition of a monoid homomorphism

Answer 35

A monoid homomorphism from monoid (S, ⊕) to monoid (T, ⊙) is a function h : S →T such that
∀u,v ∈ S, h(u ⊕ v) ≡ h(u) ⊙ h(v).

Question 36

Give the definition of a list homomorphic function

Answer 36

A LHF function h is a (mathematical) function that can be implemented as:
h( [ ] ) = e
h( [x] ) = f(x)
h( x ++ y) = h(x) ⊙ h(y)

Question 37

A list homomorphic function is a mathematical homomorphism from ____ to ____? What does this mean?

Answer 37

(LT , ++) to (Img(h), ⊙).
In particular (Img(h), ⊙) must be a monoid with neutral element e, which also means that ⊙ must be
associative.
The reverse also (trivially) holds: if h is a homomorphism between (LT , ++) and some monoid (M, ⊙)
then it accepts a LHI (as above).

Question 38

Give examples of 3 list homomorphic programs

Answer 38

1. computing the length of a list, i.e., len : [α] → Int.
   len [ ] = 0
   len [x] = one x – where one x = 1
   len (x ++ y) = (len x) + (len y)
2. allp that checks whether some predicate p
   : α → Bool satisfies (holds on) all elements of an input list:
   allp [ ] = true
   allp [x] = p x
   allp (x ++ y) = (allp x) && (allp y)
3. summing up the (numerical) elements of a list. This can be accomplished with the following LHI:
   sum [ ] = 0
   sum [x] = id x – where id x = x
   sum (x ++ y) = (sum x) + (sum y)
4. The function that adds two to every (numeric) element of a list and then multiplies the results.
   fld [ ] = 1
   fld [x] = plus2 x – where plus2 x = x + 2
   fld (x ++ y) = (fld x) * (fld y)

Question 39

What is the first basic block of data parallel programming?

Answer 39

the map second-order operator, which takes
as argument an unary function and a list of elements, and produces a list of the same length as the
original one by applying the function argument to each element of the input list. The type and
semantics of map are presented below:
map : (α → β) → [α] → [β]
map f [x1, . . .xn ] = [f x1,. . ., f xn ]

Question 40

Explain why map has implicitly parallel semantics.

Answer 40

The computation corresponding to some element x_i of the array is completely independent of all other elements of the array.

Question 41

What is the second basic block of data parallel programming?

Answer 41

The reduce second-order operator,
which takes as arguments an associative binary operator, the neutral element corresponding to the
monoid defined by the binary operator, and a list of elements. The result of reduce is obtained
by successively applying the operator to all the elements of the array. The type and semantics of
reduce are presented below:
reduce : (α →α →α) → α → [α] →α
reduce ⊙ e [x1, . . .xn ] = e ⊙ x1 ⊙ . . . ⊙ xn

Question 42

What is important to rememeber about the operator in reduce so that it has parallel semantics?

Answer 42

It must be associative.

Question 43

What is the first list homomorphism theorem?

Answer 43

A list-homomorphic implementation defined as:
h( [ ] ) = e
h( [x] ) = f(x)
h( x ++ y) = h(x) ⊙ h(y)
is semantically equivalent with (reduce ⊙ e) ◦ (map f), or in complete code:
h z ≡ reduce ⊙ e ( map f z)

Question 44

Write the map-reduce implementations of the list homomorphic programs for finding the length of a list: len, whether all items of a list satifies some propertyr: allp, the sum of elements in a list: sum.

Answer 44

• len z ≡ reduce (+) 0 (map one z)
• allp z ≡ reduce (&&) true (map p z)
• sum z ≡ reduce (+) 0 (map id z) ≡ reduce (+) 0 z

Question 45

State the list homomorphism lemmas

Answer 45

1. ( map f) ◦ ( map g) ≡ map (f ◦ g)
2. ( map f) ◦ ( reduce (++) []) ≡ ( reduce (++) []) ◦ ( map ( map f))
3. ( reduce (⊙) e⊙) ◦ ( reduce (++) []) ≡
   ( reduce (⊙) e⊙) ◦ (map ( reduce (⊙) e⊙ ))

Question 46

The first identity in the list homomorphism lemma is known as ___ and is useful for what?

Answer 46

It is known as the map fusion/fission rule. Fusion corresponds to applying the transformation in the forward direction and is useful for reducing the number of accesses to global memory which is slow compared to registers. Fission corresponds to applying the transformation in the backwards direction and is useful for enhancing the degree of parallelism that is statically mapped to the hardware in the context of a nested parallel program.

Question 47

How can the second and third identities of the list homomorphism lemmas be used?

Answer 47

In the forward direction they can be used to efficiently sequentialize the parallelism in excess of what the hardware can support and in the backward direction to enhance load balancing and the programs degree of parallelism that can be statically mapped to the hardware.

Question 48

What is an often used optimization for the scheduling of map-reduce computations?

Answer 48

Map-reduce composition can be
re-written into a semantically equivalent program that:
• splits the input list into p sublists of roughly equal length,
• applies the original computation to each sublist, such the computation of a sublist is performed
sequentially on a core, but different sublists are processed in parallel on different cores,
• applies the original reduction to the per-core results.
The benefit of such an execution is not only given by spawning a number of threads equal to the
numbers of cores, thus reducing scheduling and switching-contexts overheads, but also optimizing
the reduction depth. Originally, the reduction was applied to a list of n elements, and would require
log(n) sequential steps (see reduction tree in fig. 4). In the transformed program the final (parallel)
reduction is performed on a list of p elements, requiring only log(p) sequential steps.

Question 49

What is the optimized map-reduce lemma?

Answer 49

Theorem 4 (Optimized Map-Reduce Lemma). Assume splitp :: [α] → [[α]] distributes a list
into p sublists, each containing about the same number of elements. Also assume ⊙ a binary associative
operator with neutral element e⊙ and f a unary function. The following identity always holds:
redomap (⊙) f e⊙ ≡
( reduce (⊙) e⊙) ◦ (map ( redomap (⊙) f e⊙ )) ◦ splitp
where redomap is defined as redomap ⊙ f e⊙ ≡ (reduce ⊙ e⊙) ◦ (map f).

Question 50

Give an example of a near homomorphic program and the transformation into a homomophic program.

Answer 50

The maximum segment sum problem is an example. It can be transformed by computing extra baggage of information - (maximum segment sum, maximum intial sum, maximum concluding sum, total sum) and then implementing i three main steps: each input element is lifted to before mentioned quadruple of info. The result is reduced using an associative operator for computing mentioned info. Then we project, i.e select the element in the quadruple that is the result (the mss in the quadruple).
Longest satisfying segment is another similar example.

Question 51

Write the three formulas that provide the basis for Amdahls law.

Answer 51

Let E be the enhancement providing speedup, F the fraction of the program that benefits and 1-F the fraction that does not. Then
Speedup(E) = T(without E)/T(with E) = 1/((1-F)+F/S)
Speedup(E) <= 1/(1-F)
lim S -> inf Speedup(E) = 1/(1-F)

Question 52

Provide an interpretation of Amdahls law by diminishing returns

Answer 52

In essence, Amdahl’s law shows that no matter how big the improvement is, the overall application
speedup is limited by the 1 − F fraction that does not benefit from the improvement.

Question 53

Write the formula fr Amdahls law in the particular case of parallelism

Answer 53

Let T1 be the time execution take on one processor and TP be the time on P processors. F is the fraction run in parallel. Speedup(P) = T1/TP = P/(F+P(1−F )) < 1/(1−F). Ideally P cores results in a Px speedup.

Question 54

What is the moral of Amdahls law for parallel parallelizing code?

Answer 54

Never leave sequential any part of the program that can possibly be
parallelized. In other words, when developing parallel code, we must reason as if the hardware has an
unlimited/infinity number of cores.

Question 55

What does PRAM stand for?

Answer 55

Parallel random access machine.

Question 56

What are the 5 assumptions on a PRAM?

Answer 56

1. There are P processors connected to shared memory
2. Each processsor han an unique identifier/index 0 <=i < P
3. The execution happens in single instruction multiple data fashion, i.e all cores execute in lock step
4. each parallel instruction takes unit time
5. each processor has a flag that controls whether it is active in the execution of an instruction

Question 57

What does SIMD stand for and what does it mean?

Answer 57

ingle instruction multiple data which means all cores execute in lock step i.e. a core can not start the next instruction until all cores have finished the current instruction.

Question 58

What effect does executing in lock step have when branching.

Answer 58

In the case of an if-then-else,
the processors that did not take the then branch must wait until all the other processors has
finished executing the then branch, before starting to execute the else branch, and similar
for the else branch.

Question 59

What is the work complexity?

Answer 59

The total number of operations performed to execute a program.

Question 60

What is the depth complexity?

Answer 60

The number of sequential steps needed to execute a program.

Question 61

When is a parallel implementation work efficient?

Answer 61

If the work complexity is asymptotically equal to that of the best sequential implementation of the same program.

Question 62

State Brentt’s theorem

Answer 62

A parallel implementation that has depth D(n) and work W(n) can be simulated on a P-processor
PRAM in time complexity T such that:
W(n)/P ≤ T ≤ W(n)/P + D(n)

Question 63

What does SOAC stand for

Answer 63

Second order array operator

Question 64

Explain the implementation of scan

Answer 64

The implementation is
organized in two parallel steps:
(1) The first step is called “Up-Sweep” and is similar with a reduction, except that the accumulation
of all elements is computed in the last element of the array, rather than the first.
• After the up-sweep pass, value 0 is placed in the position of the last element.

(2) The second step is called “Down-Sweep”, and it propagates updates to the array’s elements
in the reverse order of the up-sweep pass (i.e., reverse the arrows and the traversal of the up
sweep). Each propagation requires two substeps:
2.1. the left child sends its value to its parent and updates its value to that of the parent.
2.2. the right-child value is obtained by applying the binary operator of the scan to the leftchild
value and to the (old) value of parent. Please notice that the right child is in fact the
parent—an in-place algorithm.

Question 65

What’ss the ddepth and work of scan and reduce?

Answer 65

Lg(n) and n

Question 66

What is a Warp?

Answer 66

The unit of parallel execution in CUDA which consists of 32 parallel threads.

Question 67

How do the threads in a warp execute?

Answer 67

In SIMD fashion

Question 68

Make a data-parallel represetation of the array [[1 , 3, 5], [7, 8], [9, 11, 14, 15]]

Answer 68

shapeArray = [ 3, 2, 4 ]
flagArray = [ 1, 0, 0, 1, 0, 1, 0, 0, 0 ]
valueArray = [ 1, 3, 5, 7, 8, 9, 11, 14, 15 ]

Question 69

What is the work and depth of Segmented Scan

Answer 69

Lg n and n -> since essentially a segmented scan can be implemented in terms of a scan and the work and depth of scan is lg n and n.