Parallel Computing Interview Questions & Answers

  1. Question 1. What Is Shared-memory Architecture?

    Answer :

    A single address space is visible to all execution threads.

  2. Question 2. What Is Numa Memory Architecture?

    Answer :

    NUMA stands for Non-Uniform memory access and is a special type of shared memory architecture where access times to different memory locations by a processor may vary as may also access times to the same memory location by different processors.

  3. C++ Interview Questions

  4. Question 3. Name Some Network Architectures Prevalent In Machines Supporting The Message Passing Paradigm?

    Answer :

    Ethernet, Infiniband, Tree.

  5. Question 4. What Is Data-parallel Computation?

    Answer :

    Data is partitioned across parallel execution threads, each of which perform some computation on its partition – usually independent of other threads.

  6. C++ Tutorial

  7. Question 5. What Is Task-parallel Computation?

    Answer :

    The parallelism manifests across functions. A set of functions need to compute, which may or may not have order constraints among them.

  8. C preprocessor Interview Questions

  9. Question 6. What Is Task-latency?

    Answer :

    The time taken for a task to complete since a request for it is made.

  10. Question 7. What Is Task-throughput?

    Answer :

    The number of tasks completed in a given time

  11. Parallel Algorithm Tutorial
    Basic C Interview Questions

  12. Question 8. What Is Speed-up?

    Answer :

    The ratio of some performance metric (like latency) obtained using a single processor with that obtained using a set of parallel processors.

  13. Question 9. What Is Parallel Efficiency?

    Answer :

    The Speed-up per processor

  14. IBM DataPower Interview Questions

  15. Question 10. What Is An Inherently Sequential Task?

    Answer :

    On whose maximum speed-up (using any number of processors) is 1.

  16. Parallel Computer Architecture Tutorial

  17. Question 11. What Is The Maximum Time Speed-up Possible According To Amdahl’s Law?

    Answer :

    1/f, where f is inherently sequential fraction of the time taken by the best sequential execution of the task.

  18. Base Sas Interview Questions

  19. Question 12. What Is Simd?

    Answer :

    A class belonging to Flynn’s taxonomy of parallel architectures, it stands for single instruction multiple data. In this architecture, different processing elements all execute the same instruction in a given clock cycle, with the respective data (e.g., in registers) being independent of each other.

  20. C++ Interview Questions

  21. Question 13. What Is Cache Coherence?

    Answer :

    Different processors may maintain their own local caches. This results in potentially multiple copies of the same data. Coherence implies that access to the local copies behave similarly to access from the local copy – apart from the time to access.

  22. Question 14. What Is A Hypercube Connection?

    Answer :

    A single node is a hypercube. An n node hypercube is made of two n/2 node hypercube, with their corresponding nodes connected to each other.

  23. Question 15. What Is The Diameter Of An N-node Hypercube?

    Answer :

    log n. The diameter is the minimum number of links required to reach two furthest nodes.

  24. Parallels Workstation for Windows and Linux Interview Questions

  25. Question 16. How Does Openmp Provide A Shared-memory Programming Environment.?

    Answer :

    OpenMP uses pragmas to control automatic creation of threads. Since the thread share the address space, they share memory. However, they are allowed a local view of the shared variables through “private” variables. The compiler allocates a variable-copy for each thread and optionally initializes them with the original variable. Within the thread the references to private variable are statically changed to the new variables.

  26. Question 17. What Is The Memory Consistency Model Supported By Openmp?

    Answer :

    There is no “guaranteed” sharing/consistency of shared variables until a flush is called. Flush sets that overlap are sequentially consistent and the writes of a variable become visible to every other thread at the point flush is serialized. This is slightly weaker than “weak consistency.”

  27. Ibm Websphere Process Server Interview Questions

  28. Question 18. How Are Threads Allocated To Processors When There Are More Threads Than The Number Of Processors?

    Answer :

    Once a thread is completed on a core, a new thread is run on it. The order can be controlled using the “Schedule” clause.

  29. C preprocessor Interview Questions

  30. Question 19. What Is Common Crcw Pram?

    Answer :

    Parallel Random Access Model of Computation in which the processors can write to a common memory address in the same step, as long as they are all writing the same value.

  31. Question 20. What Is The Impact Of Limiting Pram Model To A Fixed Number Of Processors Or A Fixed Memory Size?

    Answer :

    Prams with higher capacities can be simulated can be simulated (with linear slowdown).

  32. Embedded Processors Interview Questions

  33. Question 21. What Is The Impact Of Eliminating Shared Write From Pram?

    Answer :

    It can be simulated by crew pram with a log n factor in the time. However, the algorithms in this model can become a little complicated, as they must ensure conflict free writes.

  34. Question 22. What Is The Significance Of Work Complexity Analysis?

    Answer :

    Time complexity does not account for the size of the machine. Work complexity is more reflective of practical efficiency. Work-time scheduling principle describes the expected time for a p processor pram as work/p.

  35. Question 23. What Does Bulk Synchronous Model Add To Pram For Parallel Algorithm Analysis?

    Answer :

    Pram assumes constant time access to shared memory, which is unrealistic. Bsp counts time in “message communication” and in this model a step isn’t initiated until the input data has arrived.

  36. Parallel Computer Architecture Interview Questions

  37. Question 24. Is It True That All Nc Problems Parallelize Well?

    Answer :

    In general NC problems do parallelize well in terms of having a poly-log solution in pram model while it only has a super log solution in ram model. However, for problems with poly-log solution in ram models, there may not be an effective speed-up.

  38. Basic C Interview Questions

  39. Question 25. Is User Locking Required To Control The Order Of Access To Guarantee Sequential Consistency?

    Answer :

    Sequential consistency is independent of user locking but does require delaying of memory operations at the system level. Precise ordering of operations need not be pre-ordained by the program logic. There just must exist a global ordering which is consistent with the local view observed by each processor.

  40. Question 26. What Is The Difference Between Processor And Fifo Consistency?

    Answer :

    In FIFO consistency only writes from a single processor are visible in the order issued. In processor consistency, additionally there exists a global ordering of writes to any address x by different processes exists that is consistent with the local views.

  41. Back Office Interview Questions

  42. Question 27. What Is False Sharing?

    Answer :

    Sharing of a cache line by distinct variables. As a result, performance issues come into play. If such variables are not accessed together, the un-accessed variable is unnecessarily brought into cache along with the accessed variable.

  43. IBM DataPower Interview Questions

  44. Question 28. What Is A Task Dependency Graph?

    Answer :

    A directed graph with nodes representing tasks and edge from task a to b indicating that task b can only start after task a is completed.

  45. Question 29. When Can An Mpi Send Call Return?

    Answer :

    If it is a synchronous call, it can return only when the pairing call on another process is ready. For asynchronous versions, it can return as soon as the provided buffer is ready for re-use.

  46. Question 30. What Is A Collective Communication Call?

    Answer :

    It’s a call that must be made at all members of the communication group. No call can return until all calls have been at least been made.

  47. Question 31. How Cam Mpi Be Used For Shared Memory Style Programming?

    Answer :

    Each process registers its local memory and attaches it to a “window.” Accesses via this window get translated to send or fetch requests to the desired member of the group. The pairing communication is handled by the MPI system asynchronously.

  48. Question 32. What Is The Complexity Of Prefix Sum In Pram Model?

    Answer :

    Time O(log n) and work O(n)

  49. Question 33. What Is The Time Complexity Of Optimal Merge Algorithm (on Pram)?

    Answer :

    O(log log n) by first merging sub-sequences of the original lists of size n/(log log n) each. The remaining elements are inserted into the just computed sequence in the next step.

  50. Base Sas Interview Questions

  51. Question 34. What Is Accelerated Cascading?

    Answer :

    The accelerated cascading technique combines a fast but work-inefficient algorithm with a work optimal one. The problem is recursively divided into many smaller sub-problems, which are first solved solved using the optimal algorithm. The sub-results are then combined with the faster version of the algorithm.

  52. Question 35. Why Must Cuda Divide Computation Twice: Into Grids And Then Blocks?

    Answer :

    The hardware is based on maximizing throughput. This has been done by allowing a large number of running threads — all with a live context. This implies that only a fixed number of threads can fit in the hardware. This in turn means that these threads cannot communicate with or depend on other thread that could not be fit and hence must wait for the first set of threads to complete execution. Hence, a two level decomposition. Further, even the set of threads running together may execute at different SMs, and synchronization across SMs would be slow and onerous and hence not supported.

  53. Question 36. How Do Memory Operations In Gpus Differ From Those In Cpus?

    Answer :

    GPUs have a significantly smaller cache making average latency of memory operations much higher. This requires many concurrent threads to hid the latency. Also, the shared memory can be used as an opaque cache in direct control of the programmer — making it possible to utilize the cache better in some situations. Further, because of SIMD warp instructions, multiple memory accesses are made per instruction. These accesses can be coalesced into a smaller number of real accesses, if the address set is contiguous for global memory or strided for shared memory.

  54. Parallels Workstation for Windows and Linux Interview Questions

  55. Question 37. How Can Two Gpu Threads Communicate Through Shared Memory?

    Answer :

    If the threads belong to a non-divergent warp, writes before reads are visible to the read. Two threads in the same block must have an intervening sync for the write to affect the read. Two thread in different blocks within the same kernel cannot be guaranteed an order and the read must be moved to a later kernel for the write to become visible.

  56. Question 38. How Can Prefix Minima Be Found In O(1) Time?

    Answer :

    This can be computed by first finding all nearest smaller values first in O(1) and then checking in O(1) time for each element (using O(n) processor for that element), that largest index smaller than its own, whose element has no nearest smaller value on its left. The work complexity of O(n2) can be improved using accelerated cascading.

  57. Question 39. How Long Does Bitonic Sorting Require On Pram?

    Answer :

    O(log2n)

  58. Question 40. How Long Does Batcher’s Odd-even Merge Require?

    Answer :

    O(log n) time, O(n log n) work

  59. Ibm Websphere Process Server Interview Questions

  60. Question 41. In Order To Balance Load For Parallel Bucket Sort Of N Elements, Uniformly Spaced Splitters Need To Be Selected. This Can Be Done By First Dividing The List Into B Lists And Choosing B Equi-spaced Samples From Each. The Final B Splitters Are Chosen Uniformly Spaced From These Samples. How Balanced Are The Buckets If These Splitters Are Used?

    Answer :

    No bucket will contain more than 2n/B elements.

  61. Question 42. How Fast Can Two Sorted Lists Of Size N Each Be Merged Into One Using P Processors?

    Answer :

    O(n/p) time using optimal multi-way merge.

  62. Embedded Processors Interview Questions

  63. Question 43. How Fast Can A List Be Sorted Using N Processors Using Local Sorting Of N/p Elements Each Followed By Optimal Multi-way Merge?

    Answer :

    O(n/p log n)

  64. Question 44. When Stealing Load From A Random Loaded Processor, What Type Of Synchronization Is Needed?

    Answer :

    One needs to make sure that the queue being stolen from is operated in a synchronized fashion – either locked or edited in a lock-free manner.

  65. Question 45. How Can One Ensure Mutual Exclusion Without Locks?

    Answer :

    When references of two (or more) threads (or processes) may be serialized with respect to a variable, system primitives like compare and swap can help detect the conflict with another thread. Lock free implementations of a thread usually detect the conflict atomically (e.g., using compare and swap) and one succeeds while the other backs off and retries.

  66. Question 46. How Long Does The Parallel Version Of Prim’s Minimum Spanning Tree Finding Algorithm Require For A Graph With N Nodes Using P Processors?

    Answer :

    O(n2/p + n log p)