Final Review A

CUDA and OpenCL both exist to provide an interface for writing programs that will execute directly on the graphics processing unit (GPU). A GPU can provide additional processing power, particularly for computational problems that are amenable to parallelization.

• A GPU has several computation units (“thread processors”) that are all driven with the same instructions, though each has its own register set.

• A GPU distinguishes between three types of memory: “private” memory available to just one computation unit, “local” memory that is available to one group of computation units (all driven by the same instruction stream), and “global” memory that is available across the processor. By contrast, a CPU has only registers (anologous to a GPU's private memory) and memory (analogous to a GPU's global memory).

• A GPU includes aggressive multithreading, with 96 threads per multiprocessor being typical. By contrast, a CPU handles fewer threads at any one time, but it works more aggressively to discover instruction-level parallelism so that each individual thread can be completed more quickly.

A symmetric multiprocessor relies on a single, shared memory bus shared among all processors for communication with the single shared memory. Beyond eight processors, the amount of traffic on this bus and the amount of traffic with the main memory becomes a bottleneck impeding the system's speed. A distributed system allows direct communication between processors along a switching network.

All four possibilities could occur. It is easy to come up with cases that lead to (a.), (c.), and (d.): We could execute all of B before A, or execute the first instruction of each before the second instruction of each, or we could execute all of A before B. However, (b.) is sequentially inconsistent, so there's no such sequence. However, if A and B occur at virtually the same time, the definition of coherence could permit a to eventually become 1 while b would eventually become 12.

In the write invalidate protocol, whenever a processor wishes to write to a memory location, the cache first broadcasts onto the bus that other caches should invalidate their copies. From then on, the cache considers itself to have an exclusive copy of that data, so that subsequent writes to that memory location can reside purely in the cache. When another processor requests the memory location, or when the processor decides that it is time to use the cache location for another purpose, then the processor sends the actual value written onto the bus.

Write invalidate's primary advantage is that it requires less traffic for multiple writes to the same cache line: With write broadcast, every write to a cache line must be broadcast onto the bus, but with write invalidate, only the first write needs a broadcast on the bus. (Of course, the value must be broadcast later when the cache decides no longer to include that memory location, or when another cache needs to read from that memory location.)

In a directory system, there is a central location for each line of memory that tracks which processors' caches hold a copy of that line. Having a central location allows processors to determine the status of how a line is shared. This is particularly relevant for a DSM system, since messages are not broadcast to all other procesors (across a bus) and so needs to know which other processors to communicate with.

a. n / 2, since for any node the furthest node is halfway around the ring.

b. n / 4, since for any node there is one node that is 0 way, one that is n / 2 away, and two nodes for each integer distance between 0 and n / 2.

c. n.