CS5260 Exam 2 | Correct Questions and Answers
1. Describe an MIMD system. What does it consist of? What does it support?-
: MIMD System - Multiple instructions, multiple data systems. Supports multiple simultaneous instruction streams
operating on multiple data streams. Consists of a collection of fully independent processing units or cores, each of which
has its own control unit and its own data path. Supports asynchronous.
2. Describe a shared memory system. How do the processors communicate? Give two examples: Shared memory
system - Uses one or more multicore proces- sors, a multicore processor has multiple CPU's or cores on one chip. The
intercon- nect can either connect all processors to main memory known as UMA (Uniform Memory Access) or
processors can have a connection to a block of main memory and processors can access each others blocks through
special hardware built into the processors known as NUMA (Non Uniform Memory Access).
3. Describe a cluster. How do the nodes communicate?: Cluster - Most widely available distributed-memory
systems. Composed of commodity systems like PC's connected by a commodity interconnection network like Ethernet.
4. Describe a bus interconnect.: Bus - a collection of parallel communication wires together with some hardware that
controls access to the bus.
5. Define bandwidth: Bandwidth - The bandwidth of a link is the rate at which it can transmit data.
6. Define bisection width: Bisection width - a measure of the number of simulta- neous communications or
connectivity. How many simultaneous connections com- munications can take place across the divide between the two
halves of a parallel system.
7. Define bisection bandwidth: Bisection bandwidth - a measure of network quali- ty, similar to bisection width,
however instead of counting the number of links joining the halves, it sums the bandwidth of the links.
8. Define latency in regards to message passing: Latency - The time that elapses between a source begging to transmit
the data to the destination starting to receive the first byte.
9. Give a formula for message transmission time with latency l, bandwidth b, and message length n: message
transmission time = l + n/b
10.What is cache coherence?: Cache coherence - The synchronicity and consis- tency of data stored within a
multicore or multiprocessor system.
11.What is snooping cache coherence?: Snooping cache coherence - When the cores share a bus, any signal
transmitted on the bus can be "seen" by all cores connected to the bus. Thus when core 0 updates the copy of x stored in
its cache, if core 1 is snooping the bus, it will see that x has been updated, and it can mark its copy of x as invalid.
1/
7
, CS5260 Exam 2 | Correct Questions and Answers
12.What is directory based cache coherence?: Directory based cache coher- ence - Attempts to solve the problem
of cache coherence through the use of
a directory. A directory is a data structure that stores the status of each cache line. Typically this data structure is
distributed. Each core/memory pair could be responsible for storing
13.What is an SPMD program?: SPMD program - in a single program, multiple data program instead of running a
different program on each core, SPMD programs consist of a single executable that can behave as if it were multiple
different programs through the use of conditional branches.
14.Give three steps to write a parallel program.: 1. Divide the work among the processes/threads in such a way
that
a. each process/thread gets roughly the same amount of work, and
b. the amount of communication required is minimized.
2. Arrange for the processes/threads to synchronize.
3. Arrange for communication among the processes/threads.
15.What are dynamic threads?: Dynamic threads - the paradigm that there is often a master thread and at any given
time a (possibly empty) collection of worker threads. The master waits for work requests and forks over workers.
16.What are static threads?: Static threads - all threads are forked after the needed setup by the master thread and the
threads run until all work is completed.
17.Why are parallel programs considered "nondeterministic"?: A computation is nondeterministic if a given input
can result in different outputs. If multiple threads are executing independently, the relative rate at which they'll compute
statements varies from run to run, and hence the results of the program may be different run to run.
18.Give four possible causes of nondeterminism.:
19.What is busy-waiting? Give an example.: Busy-waiting - a thread enters a loop whose sole purpose is to test a
condition.
my_val = Compute_val(my_rank):
if (my_rank == 1)
while (!ok_for_1): /* Busy-wait loop */ x +=
my_val; /* Critical section */
2/
7
1. Describe an MIMD system. What does it consist of? What does it support?-
: MIMD System - Multiple instructions, multiple data systems. Supports multiple simultaneous instruction streams
operating on multiple data streams. Consists of a collection of fully independent processing units or cores, each of which
has its own control unit and its own data path. Supports asynchronous.
2. Describe a shared memory system. How do the processors communicate? Give two examples: Shared memory
system - Uses one or more multicore proces- sors, a multicore processor has multiple CPU's or cores on one chip. The
intercon- nect can either connect all processors to main memory known as UMA (Uniform Memory Access) or
processors can have a connection to a block of main memory and processors can access each others blocks through
special hardware built into the processors known as NUMA (Non Uniform Memory Access).
3. Describe a cluster. How do the nodes communicate?: Cluster - Most widely available distributed-memory
systems. Composed of commodity systems like PC's connected by a commodity interconnection network like Ethernet.
4. Describe a bus interconnect.: Bus - a collection of parallel communication wires together with some hardware that
controls access to the bus.
5. Define bandwidth: Bandwidth - The bandwidth of a link is the rate at which it can transmit data.
6. Define bisection width: Bisection width - a measure of the number of simulta- neous communications or
connectivity. How many simultaneous connections com- munications can take place across the divide between the two
halves of a parallel system.
7. Define bisection bandwidth: Bisection bandwidth - a measure of network quali- ty, similar to bisection width,
however instead of counting the number of links joining the halves, it sums the bandwidth of the links.
8. Define latency in regards to message passing: Latency - The time that elapses between a source begging to transmit
the data to the destination starting to receive the first byte.
9. Give a formula for message transmission time with latency l, bandwidth b, and message length n: message
transmission time = l + n/b
10.What is cache coherence?: Cache coherence - The synchronicity and consis- tency of data stored within a
multicore or multiprocessor system.
11.What is snooping cache coherence?: Snooping cache coherence - When the cores share a bus, any signal
transmitted on the bus can be "seen" by all cores connected to the bus. Thus when core 0 updates the copy of x stored in
its cache, if core 1 is snooping the bus, it will see that x has been updated, and it can mark its copy of x as invalid.
1/
7
, CS5260 Exam 2 | Correct Questions and Answers
12.What is directory based cache coherence?: Directory based cache coher- ence - Attempts to solve the problem
of cache coherence through the use of
a directory. A directory is a data structure that stores the status of each cache line. Typically this data structure is
distributed. Each core/memory pair could be responsible for storing
13.What is an SPMD program?: SPMD program - in a single program, multiple data program instead of running a
different program on each core, SPMD programs consist of a single executable that can behave as if it were multiple
different programs through the use of conditional branches.
14.Give three steps to write a parallel program.: 1. Divide the work among the processes/threads in such a way
that
a. each process/thread gets roughly the same amount of work, and
b. the amount of communication required is minimized.
2. Arrange for the processes/threads to synchronize.
3. Arrange for communication among the processes/threads.
15.What are dynamic threads?: Dynamic threads - the paradigm that there is often a master thread and at any given
time a (possibly empty) collection of worker threads. The master waits for work requests and forks over workers.
16.What are static threads?: Static threads - all threads are forked after the needed setup by the master thread and the
threads run until all work is completed.
17.Why are parallel programs considered "nondeterministic"?: A computation is nondeterministic if a given input
can result in different outputs. If multiple threads are executing independently, the relative rate at which they'll compute
statements varies from run to run, and hence the results of the program may be different run to run.
18.Give four possible causes of nondeterminism.:
19.What is busy-waiting? Give an example.: Busy-waiting - a thread enters a loop whose sole purpose is to test a
condition.
my_val = Compute_val(my_rank):
if (my_rank == 1)
while (!ok_for_1): /* Busy-wait loop */ x +=
my_val; /* Critical section */
2/
7
