Parallel Processing and Multiprocessors Questions and Answers

Answer: C

The routine not in the minimal set is MPI_Sendrecv.

A complete MPI program can be written with six routines: MPI_Init and MPI_Finalize to start and end MPI, MPI_Comm_size and MPI_Comm_rank (printed 'MPI_Comm_Size') to find the number of processes and each process's rank, and MPI_Send and MPI_Recv for point-to-point messages.

MPI_Sendrecv combines a send and a receive in one call to avoid deadlock in exchanges. It is convenient but can be built from MPI_Send and MPI_Recv, so it is not part of the minimal set.

Answer: D

All four are characteristics, so the answer is (i), (ii), (iii) and (iv).

M. Morris Mano describes a multiprocessor as two or more CPUs interconnected with shared main memory and I/O equipment (i). Because a failure of one processor need not stop the system, reliability improves (ii). Throughput improves because the system can either run multiple independent jobs in parallel (iii) or split a single job into parts that execute in parallel (iv).

Each of the other options omits at least one of these.

Answer: A

The protocol is the Snoopy protocol.

Snoopy protocols distribute the responsibility for cache coherence among all the cache controllers. Each controller watches (snoops) the shared bus, recognises when a line it holds is shared, and invalidates or updates its copy when another processor writes.

Directory protocols do the opposite: a central directory records which caches hold each line, and a central controller enforces coherence. Write-back and write-through are policies for when main memory is updated, not ways of sharing the coherence work.

Answer: C

The parallel time is \(O(\log_2 n)\).

The algorithm finds the maximum of the \(n = 2^{m}\) values stored in a complete binary tree, level by level from the bottom. In each iteration of the outer loop, all nodes on level k compute the maximum of their two children in parallel, using one comparison, so each iteration takes constant time.

The outer loop runs once per level, m times, and \(m = \log_2 n\), so the parallel time is \(O(\log_2 n)\). O(n) or worse would be the sequential cost of scanning the values.

Answer: C

The key's answer is Control structures.

The standard textbook account (Morris Mano) says vector processing eliminates the overhead of fetching and executing the instructions in the program loop. A loop that adds two arrays element by element, for example, repeats its fetch, index update and branch instructions for every element; a single vector instruction does the whole operation. A loop is a control structure, which is the option the key takes.

Vector processing does not remove the instructions of a whole program, and functions and sub-routines are not what it targets, so those options are wrong.

Answer: C

The statement that is not a characteristic of NUMA machines is (iii), access to remote memory is faster than access to local memory.

NUMA (non-uniform memory access) multiprocessors have three key characteristics: a single address space visible to all CPUs (i); access to remote memory through ordinary LOAD and STORE instructions (ii); and access to remote memory that is slower than access to local memory (iv). The non-uniformity is precisely that local memory is faster.

Statement (iii) contradicts (iv) and the very idea of NUMA, so it is the odd one out; the other three are true.

Answer: A

All four are application areas of vector processing: (i), (ii), (iii) & (iv).

Vector processors apply one operation to long arrays of data, so they suit problems built on large matrix and array computations. Standard computer architecture texts (Mano among them) list long-range weather forecasting, petroleum explorations, seismic data analysis, medical diagnosis, aerodynamics and space flight simulations, artificial intelligence and expert systems, mapping the human genome and image processing.

Seismic data analysis, petroleum exploration, medical diagnosis and AI and expert systems are all on this list, so options naming only some of them, or none, are wrong.

Answer: D

Processing several programs at the same time is MIMD.

In Flynn's classification, Multiple Instruction stream, Multiple Data stream machines have several processors, each executing its own instruction stream on its own data. That is what running several programs simultaneously requires; multiprocessors and multicomputers are MIMD.

SISD is a single conventional processor, SIMD applies one instruction to many data items (vector and array processors), and MISD, many instructions on one data stream, is rarely built.

Answer: B

This is SIMD, Single Instruction Stream, Multiple Data Stream.

In Flynn's classification, an SIMD machine has many processing elements under the supervision of one common control unit. The control unit broadcasts a single instruction, and all the processing units execute it at once on different data, as in array processors and vector units.

SISD has one processing unit, the ordinary uniprocessor. MISD applies several instruction streams to one data stream, and MIMD has several processors each with its own control unit and instruction stream, so neither has a single common control unit.