JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III Year ADVANCED COMPUTER ARCHITECTURE Previous Question Paper (September - 2021 - R18)

Implicit parallelism refers to the ability of the compiler or the hardware architecture to automatically detect and exploit parallelism within a sequential program without requiring the programmer to explicitly specify it. The compiler performs dependency analysis to identify independent instructions that can be executed concurrently, often using techniques like instruction pipelining, superscalar execution, or out-of-order execution.

Explicit parallelism requires the programmer or the language construct to explicitly define parallel tasks, threads, or processes. The programmer uses specific parallel programming models or primitives, such as fork-join constructs, message passing interfaces (MPI), or shared memory directives (e.g., OpenMP), to manage synchronization, communication, and task distribution across multiple processors.

Granularity refers to the size of the computational tasks relative to the communication overhead. Fine-grain parallelism involves small tasks (e.g., individual instructions or loop iterations) with high communication frequency, while coarse-grain parallelism involves large tasks (e.g., entire subroutines or functions) with lower communication frequency.

Grain packing is the process of merging fine-grain nodes into larger coarse-grain nodes to reduce communication overhead and scheduling latency.

Before packing, a program graph consists of many small nodes (N1, N2, ..., Nn) connected by edges representing data dependencies. After grain packing, nodes that have high communication costs relative to their execution time are grouped into a single macro-node (e.g., M1 = {N1, N2}). The resulting graph has fewer nodes and edges, effectively increasing the granularity of the tasks and reducing the overhead associated with task management and synchronization.