PDP 2026 exam

Critical section definition

A section of code that may only be executed by one process at any one time.

Mutual Exclusion definition

A property, the requirement that one thread of execution never enter its critical section at the same time that another concurrent thread of execution enters its own critical section.

Starvation definition

The problem encountered in concurrent computing where a process / thread is perpetually denied necessary resources to process its work.

Deadlock definition

A program state in which each member of a group is waiting for some other member to take action.

Race condition definition

Any situation where the outcome depends on the relative ordering of execution of operations on two or more threads.

Data race definition

Happens when there are two memory accesses in a program where both

• target the same location

• are performed concurrently by two threads

• are not reads

  • are not synchronization operations

A future definition?

A future implements an (asynchronous) one-off event

• waiting for the occurrence of the event is possible

• the event is typically the completion of an asynchronous task with return value

Atomic operation definition?

A set of operations that appears to the rest of the system to occur at once without being interrupted (uninterruptible).

Test-and-set instruction definition?

• Set value to true

• Return value tells if prior value was true or false

• Both done as a single atomic operation

Test-and-set lock?

1. Test the lock: if free, it atomically sets it to locked and enters critical section

2. If lock already taken, keep testing (spin)

3. Release the lock: when finished, it sets lock back to unlocked

LoadLoad program reordering?

Load ins reordered before/after another.

LoadStore program reordering?

Store ins reordered before load ins

StoreLoad reordering?

Load ins reordered before store ins

StoreStore program reordering?

Store ins reordered before/after another.

A multiprocessor is sequentially consistent if

• the result of any execution is the same as if the operations of all the processors were executed in some sequential order,

• and the operations of each individual processor appear in this sequence in the order specified by its program

• StoreLoad reordering not allowed

Total Store Order (TSO) memory model?

• More relaxed but weaker

• StoreLoad reordering allowed in threads

How to avoid StoreLoad reordering in TSO explicitly?

With memory fence: instruction inserted in source code that explicitly enforces a memory ordering

Memory fence what is it?

Instruction inserted in source code that explicitly enforces a memory ordering.

Different kind of memory fences?

• Full memory fence = all operations before the fence are finished before all other operations after the fence

• StoreLoad fence = all store operations before fence are finished all load operations after fence

• LoadLoad, StoreStore, LoadStore

Software memory model?

Putting another memory on top of a (weaker) hardware memory model.

Categories of atomic operations supported in Cpp with different memory ordering semantics?

• Load = atomically read from var

• Store = atomically write to var

• Read-Mofidy-Write = automatically read and write

Coarse-grained synchronization for a linked list?

Protect whole linked list with a single lock.

• Congestion if many threads wanna access.

Fine-grained synchronization (for linked list)?

• Split object into independently-synchronized components

• Lock while traversing the list, no validation

• Disadvantages: long chain of acquire/release + inefficient (because of traversal locking)

Optimistic synchronization (for linked lists)?

• In general: traverse without locks, then lock, validate and possibly restart

• Validation via scanning again to make sure nodes still adjacent

Lazy synchronization for linked lists for example?

• Traverse without locks, lock, validate, mark/remove, but contains() never locks (thanks to markers even though if the elements still exists)

• Validation done locally using the locked nodes → no second traversal

1. Logical deletion (marked = true)

2. Physical deletion (update pointers)

Linked list synchronization patterns?

• Coarse-grained

• Fine-grained

• Optimistic

• Lazy

• Lock-free

Lock-free synchronization for linked lists?

• Rely on atomic operations

1. Thread reads current pointer

2. Prepare new node

3. Atomically perform Compare-and-Swap (CAS)

   1. If pointer unchanged, update

   2. If another thread changed it first, the CAS fails & retry

C++ execution policies?

• std::execution::par_unseq → multi-threaded, vectorization (fastest)

• std::execution::par → multi-threaded, no vectorization

• std::execution::par → single thread

Parallel execution policy what to take into consideration?

Make sure that there are no data races or deadlocks.

Power consumption of a processor?

P~V²f

Power consumption of processor rule of thumb?

Reduction of 1% voltage and 1% reduces the power consumption by 3& and the performance by0.66%.

Vectorization definition?

• Single instruction defines n operations (instruction-level parallelism).

Features of GPU threads?

• Light-weight, little creation overhead, fast context switching

  • Up to 32 per core

Why do GPUs have good performance watt ratio?

• Many low frequency cores (watt usage), no control logic

• More transistors for computation (peak performance)

GPU architecture abstracted?

GPU → Device → GPU Processing Cluster (GPC) → Streaming Multiprocessor (SM) → Processing Element (PE) / “Core”

SIMD / Vector?

Single thread executes a single instruction stream, but the hardware has wide vector registers and ALUs that apply that instruction across multiple data elements simultaneously.

→ programmer packs data into vector registers and issues one vector instruction

→ x86 SSE/AVX

SIMT (Single Instruction, Multiple Threads)?

System presents the architecture as multiple scalar threds, but hardware groups them into bunches (“warp” of 32 threads) that execute in lockstep using a shared PC.

→ write code as each thread is independent with their own IDs but the GPU hardware executes the same instructions across all active threads

→ diverging with if/else

→ FPU

MIMD/SPMD

Multiple truly independent threads cores, each having its own hardware PC, cache and execution pipeline.

→ multicore CPU

Pool of warps what does it mean?

A streaming multiprocessor maintains a pool of active warps residing concurrently in hardware registers.

Warp scheduler?

Selects eligible warps and issues their instructions to the execution pipelines with zero context-switch overhead.

Thread blocks?

Multiple warps grouped into thread blocks.

Threads inside a block are scheduled on the same …

… multiprocessor!

How large should a thread block be?

Around 512.

Each thread is executed by a …

… core

Each thread block is executed on a …

streaming multiprocessor (SM).

Multiple thread blocks are grouped into

thread block clusters.

Thread block clusters are executed on a

GPC.

Kernel is executed as a

grid of clusters of blocks of threads on a device.

GPU programming design cycle?

1. Assess (find hotspots with profile)

2. Parallelize (replace serial hotspot via library calls, low-level code)

3. Optimize (iteratively)

4. Deploy (and verify)

Different techniques to do GPGPU programming higher level to lower level?

• Libraries (cuSPARSE)

• Directives (OpenMP)

• Programming Languages (CUDA)

How to calculate t_compute?

arithmetic operations [FLOP] / Pmax

How to calculate t_memory?

data transfers (LOAD, STORE) [words] / bs

How to calculate t_kernel?

max(t_compute, t_memory)

How to calculate the total execution time t_GPU?

t_GPU = t_H2D + t_kernel + t_D2H

How to calculate t_H2D or t_D2H?

t_H2D = alpha + LOADs / b_PCI

where alpha is latency, and STOREs for other way respectively

Occupancy per SM how to calculate?

Occupancy = active warps / max supported active warps

Kernel code built-in variables?

• gridDim: dimensions of gird (dim3)

• blockDim: dimensions of block (dim3)

• blockIdx: block index within grid (uint)

• threadIdx: thread index within block (uint)

• global index: gIdx = blockIdx.x * blockDim.x + threadIdx.x

Kernel usage with execution configuration?

kernel_func<<<dimGrid, dimBlock>>>(a, b, c)

How to allocate memory in device?

• cudaMalloc(pointerToGPUMem, size)

How to free memory pointer from device?

cudaFree(pointerToGPUMem)

How to transfer memory from pointer to pointer for device or the other ways?

cudaMemcpy(dest, src, size, direction)?

• direction: cudaMemcpyHostToDevice, —-DeviceToHost, —DeviceToDevice, —Default

Ways to optimize CUDA applications in high level?

• Data access patterns

• Memory coalescing

• Branching

• Synchronization

• Heterogeneous computing

Array of Structures vs Structure of Arrays (SoA)?

1. Stores complete Pt objects contiguously in memory, which leads to strides, non-coalesced memory accesses when single fields accesses

2. Group all identical fields contiguously into separate arrays → better when accessing single elements

Branch efficiency?

The ratio of executed flow control decisions over all executed conditionals.

What does heterogeneous computing mean in terms of GPUs?

• CPU & GPU both fully utilized

• Challenge in load balancing

What are the most common deep learning operations?

• Fully connected (MLP, CNN, Transformer)

• Convolution (CNN)

• Attention (Transformer)

What is meant by tile quantization in tensor cores?

• Tensor cores operate on fixed-size matrix fragments (tiles), e.g. 10 × 10

• If matrix not dividable by 10, e.g. 40 × 31, we still need 4×4 tiles.

• We have to do work of 40 × 40 but only need 40 × 31.

• WASTED WORK INSIDE A TILE.

What is meant by wave quantization in tensor cores?

• e.g. 20 even tiles to process

• GPU has 16 SMs

• First wave → 16 tiles, 16 SMs

• Second wave → 4 SMs, 12 SMs idle

  • Tail wave = the 75% idle SMs

Parallel data architectures in bulk-synchronous parallelism?

1. Shared memory (single memory for all Ps)

2. Distributed memory (data exchange via message passing in network)

Ways to pass messages in distributed memory machines?

• Classical/explicit approach: MPI (p-2-p, collective)

• Abstract/implicit approach: BSP (bulk-synchronous parallel)

Elements of BSP algorithm?

• Series of supersteps

  • Computation phase

  • Communication phase

  • Barrier

How does block distribution and and cyclic distribution look like?

How to characterize BSP computer as a 4-tuple?

• p: number of processors

• g: communication cost per data word [s/word]

• l: latency [s]

• r: computation rate per processor [FLOP/s]

Work metric of computation cost calculations?

$w_{i}^{\left(s\right)}$ , where number of floating-point operations (FLOPs) perfomed by processor s during superstep i

Time until all processors have finished in the BSP computation phase?

\frac{1}{r}\cdot\max_{0\le s<p}w_{i}^{\left(s\right)}\left\lbrack s\right\rbrack

What is h-relation in cost of communication phase?

\max_{0\le s<p}\max\left\lbrace r_{i}^{\left(s\right)},t_{i}^{\left(s\right)}\right\rbrace [words]

→ maximum number of words transmitted/received by any process in superset i

Time until all other processors have finished communication phase?

$gh_{i}$ , where g is communication cost per data word

Cost of superset (computation phase and communication phase together)?

T_{i}=\frac{1}{r}\cdot\max_{0\le s<p}w_{i}^{\left(s\right)}+gh_{i}+l\left\lbrack s\right\rbrack

→ computation + communication + latency l

BSP library interface?

• Environment → object representing physical system

• SPMD Block → execute identical code across all available processors

• World → enables communication & synchronization between processors