Scribd Logo
Upload

Welcome to Scribd!

  • 40 views

    CS416 - Parallel and Distributed Computing: Lecture # 6 (19-03-2021) Spring 2021 FAST - NUCES, Faisalabad Campus

    Uploaded by

    Rao Usama
    This document discusses key concepts in parallel algorithm design including: - Decomposing a problem into tasks that can be executed concurrently - Mapping tasks to processes and analyzing task dependencies, granularity, and interaction - Metrics for evaluating parallelism like maximum/average degree of concurrency and critical path length - Representing task dependencies, interactions, and mappings using graphs

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CS416 - Parallel and Distributed Computing: Lecture # 6 (19-03-2021) Spring 2021 FAST - NUCES, Faisalabad Campus

    Uploaded by

    Rao Usama
    40 views31 pages
    This document discusses key concepts in parallel algorithm design including: - Decomposing a problem into tasks that can be executed concurrently - Mapping tasks to processes and analyzing task dependencies, granularity, and interaction - Metrics for evaluating parallelism like maximum/average degree of concurrency and critical path length - Representing task dependencies, interactions, and mappings using graphs

    Original Title

    Week_03_Lec_02(lecture#6)--19-03-2021

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses key concepts in parallel algorithm design including: - Decomposing a problem into tasks that can be executed concurrently - Mapping tasks to processes and analyzing task dependencies, granularity, and interaction - Metrics for evaluating parallelism like maximum/average degree of concurrency and critical path length - Representing task dependencies, interactions, and mappings using graphs

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    40 views31 pages

    CS416 - Parallel and Distributed Computing: Lecture # 6 (19-03-2021) Spring 2021 FAST - NUCES, Faisalabad Campus

    Uploaded by

    Rao Usama
    This document discusses key concepts in parallel algorithm design including: - Decomposing a problem into tasks that can be executed concurrently - Mapping tasks to processes and analyzing task dependencies, granularity, and interaction - Metrics for evaluating parallelism like maximum/average degree of concurrency and critical path length - Representing task dependencies, interactions, and mappings using graphs

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 31

    CS416 – Parallel

    and Distributed
    Computing
    Lecture # 6 (19-03-2021)
    Spring 2021
    FAST – NUCES, Faisalabad Campus
    Agenda
    2

     A Quick Review
     Parallel Algorithm Design Life Cycle
     Tasks, Decomposition, and Task-dependency graphs
     Granularity
     Fine-grained
     Coarse-grained
     Concurrency
     Max-degree of concurrency
     Critical path length
     Average-degree of concurrency
     Task-interaction Diagrams
     Processes and mapping
    CS416 - Spring 2021
    Quick Review to the Previous Lecture
    3

     Static vs Dynamic Interconnections


     Network Topologies
     Linear array
     Star
     Mesh
     Tree
     Fully-connected
     Hypercube
     Evaluating Static interconnections
     Cost
     Diameter
     Bisection-width
     Arc-connectivity

    CS416 - Spring 2021


    Evaluating Static Interconnections
    4

    CS416 - Spring 2021


    Principles of Parallel
    Algorithm Design
    5

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    6

    Steps in Parallel Algorithm Design


    1. Identification: Identifying portions of the work that
    can be performed concurrently.
     The work-units are also known as tasks
     E.g., Initializing two mega-arrays are two tasks and can be
    performed in parallel
    2. Mapping: The process of mapping concurrent
    pieces of the work or tasks onto multiple processes
    running in parallel.
     Multiple processes can be physically mapped on a single
    processor.

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    7

    Steps in Parallel Algorithm Design


    3. Data Partitioning: Distributing the input, output, and
    intermediate data associated with the program.
     One way is to copy whole data at each processing node
     Memory challenges for huge-size problems
     Other way is to give fragments of data to each processing
    node
     Communication overheads
    4. Defining Access Protocol: Managing accesses to
    data shared by multiple processors (i.e., managing
    communication).
    5. Synchronizing the processes at various stages of the
    parallel program execution.

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    8

     Decomposition:
     The process of dividing a computation into smaller parts,
    some or all of which may potentially be executed in parallel.
     Tasks
     Programmer-defined units of computation into which the
    main computation is subdivided by means of decomposition
     Tasks can be of arbitrary size, but once defined, they are
    regarded as indivisible units of computation.
     The tasks into which a problem is decomposed may not all
    be of the same size
     Concurrent execution of multiple tasks is the key to reducing
    the time required to solve the entire problem.

    CS416 - Spring 2021


    CS416 - Spring 2021 9
    CS416 - Spring 2021 10
    Principals of Parallel Algorithm Design
    11

    Task-Dependency Graph
     The tasks in the previous examples are independent and
    can be performed in any sequence.
     In most of the problems, there exist some sort of
    dependencies between the tasks.
     An abstraction used to express such dependencies
    among tasks and their relative order of execution is known
    as a task-dependency graph
     It is a directed acyclic graph in which node are tasks and
    the directed edges indicate the dependencies between
    them
     The task corresponding to a node can be executed only
    when all the predecessor [parent] tasks complete their
    execution.

    CS416 - Spring 2021


    CS416 - Spring 2021 12
    CS416 - Spring 2021 13
    CS416 - Spring 2021 14
    Principals of Parallel Algorithm Design
    15

    Granularity
     The number and sizes of tasks into which a problem is
    decomposed determines the granularity of the
    decomposition
     A decomposition into a large number of small tasks is called
    fine-grained
     A decomposition into a small number of large tasks is called
    coarse-grained
     For matrix-vector multiplication Figure 3.1 would
    usually be considered fine-grained
     Figure 3.4 shows a coarse-grained decomposition as
    each task computes n/4 entries of the output vector
    of length n
    CS416 - Spring 2021
    Principals of Parallel Algorithm Design
    16

    Maximum Degree of Concurrency


     The maximum number of tasks that can be executed
    concurrently in a parallel program at any given time
    is known as its maximum degree of concurrency
     Usually, it is normally less than total number of tasks due to
    dependencies.
     E.g., max-degree of concurrency in the task-graphs of
    Figures 3.2 and 3.3 is 4.
     Rule of thumb: For task-dependency graphs that are
    trees, the maximum degree of concurrency is always
    equal to the number of leaves in the tree

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    17

    Determine Maximum Degree of Concurrency?

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    18

    Average Degree of Concurrency


     A relatively better measure for the performance of a
    parallel program
     The average number of tasks that can run
    concurrently over the entire duration of execution of
    the program
     The ratio of the total amount of work to the critical-
    path length
     So, what is the critical path in the graph?

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    19

    Average Degree of Concurrency


     Critical Path: The longest directed path between any
    pair of start and finish nodes is known as the critical
    path.
     Critical Path Length: The sum of the weights of nodes
    along this path
     the weight of a node is the size, or the amount of work
    associated with the corresponding task.
     A shorter critical path favors a higher average-
    degree of concurrency.
     Both, maximum and average degree of concurrency
    increases as tasks become smaller(finer)
    CS416 - Spring 2021
    Principals of Parallel Algorithm Design
    20

    Average Degree of Concurrency

    Critical path lengths: 27 and 34


    Total amount of work: 63 and 64
    Average degree of concurrency: 2.33 and 1.88
    CS416 - Spring 2021
    Principals of Parallel Algorithm Design
    21

    Determine critical path length and average-


    concurrency?

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    22

    Task Interact Graph


     Depicts pattern of interaction between the tasks
     Dependency graphs only show that how output of
    first task becomes input to the next level task.
     But how the tasks interact with each other to access
    distributed data is only depicted by task interaction
    graphs
     The nodes in a task-interaction graph represent tasks
     The edges connect tasks that interact with each
    other

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    23

    Task Interact Graph


     The edges in a task interaction graph are usually
    undirected
     but directed edges can be used to indicate the direction of
    flow of data, if it is unidirectional.
     The edge-set of a task-interaction graph is usually a
    superset of the edge-set of the task-dependency
    graph
     In database query processing example, the task-
    interaction graph is the same as the task-
    dependency graph.

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    24

    Task Interact Graph (Sparse-matrix multiplication)

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    25

    Processes and Mapping


     Logical processing or computing agent that performs
    tasks is called process.
     The process of assigning tasks to logical computing
    agents (i.e., processes) is called mapping.

     Multiple tasks can be mapped on a single process


     However, Independent task should be mapped onto
    different processes
     Map tasks with high mutual-interactions onto a single
    process

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    26

    Processes and Mapping

    CS416 - Spring 2021


    Principals of Parallel Algorithm Design
    27

    Processes and Processors


     Processes are logical computing agents that perform
    tasks
     Processors are the hardware units that physically
    perform computations
     Depending on the problem, multiple processes can
    be mapped on a single processor
     But, in most of the cases, there is one-to-one
    correspondence between processors and processes
     So, we assume that there are as many processes as the
    number of physical CPUs on the parallel computer

    CS416 - Spring 2021


    Questions
    28

    CS416 - Spring 2021


    References
    29
    1. Kumar, V., Grama, A., Gupta, A., & Karypis, G. (1994). Introduction to parallel computing (Vol. 110). Redwood City,
    CA: Benjamin/Cummings.
    2. Quinn, M. J. Parallel Programming in C with MPI and OpenMP,(2003).

    CS416 - Spring 2021

    You might also like