Scribd Logo
Upload

Welcome to Scribd!

  • 282 views

    Parallel Algorithm Models

    Uploaded by

    ZESTY
    The document describes several parallel algorithm models: 1. The data parallel model divides data among processes that perform the same operations in parallel. 2. The task graph model expresses parallelism through a graph of dependent tasks. 3. The work pool model dynamically maps tasks to processes for load balancing without pre-mapping. 4. The master-slave model has master processes generate and allocate tasks to slave processes. 5. The pipeline model passes a data stream through a series of processes that each perform operations. 6. Hybrid models combine multiple models, such as using different models at different levels or phases.

    Copyright:

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

    Parallel Algorithm Models

    Uploaded by

    ZESTY
    282 views21 pages
    The document describes several parallel algorithm models: 1. The data parallel model divides data among processes that perform the same operations in parallel. 2. The task graph model expresses parallelism through a graph of dependent tasks. 3. The work pool model dynamically maps tasks to processes for load balancing without pre-mapping. 4. The master-slave model has master processes generate and allocate tasks to slave processes. 5. The pipeline model passes a data stream through a series of processes that each perform operations. 6. Hybrid models combine multiple models, such as using different models at different levels or phases.

    Original Description:

    PARALLEL ALGORITHM MODELLS

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes several parallel algorithm models: 1. The data parallel model divides data among processes that perform the same operations in parallel. 2. The task graph model expresses parallelism through a graph of dependent tasks. 3. The work pool model dynamically maps tasks to processes for load balancing without pre-mapping. 4. The master-slave model has master processes generate and allocate tasks to slave processes. 5. The pipeline model passes a data stream through a series of processes that each perform operations. 6. Hybrid models combine multiple models, such as using different models at different levels or phases.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    282 views21 pages

    Parallel Algorithm Models

    Uploaded by

    ZESTY
    The document describes several parallel algorithm models: 1. The data parallel model divides data among processes that perform the same operations in parallel. 2. The task graph model expresses parallelism through a graph of dependent tasks. 3. The work pool model dynamically maps tasks to processes for load balancing without pre-mapping. 4. The master-slave model has master processes generate and allocate tasks to slave processes. 5. The pipeline model passes a data stream through a series of processes that each perform operations. 6. Hybrid models combine multiple models, such as using different models at different levels or phases.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    You are on page 1of 21

    Parallel Algorithm Models

    By:
    Adnan Akhtar
    Fatima Shahid
    Mishal Shafiq
    Sidra Nazir
    Hafsa Owais
    Ume Habiba
    The model of a parallel algorithm is
    developed by considering a strategy for
    dividing the data and processing
    method and applying a suitable strategy
    to reduce interactions. We will present
    the following Parallel Algorithm
    Models:
    1. Data parallel model
    2. Task graph model
    3. Work pool model
    4. Master slave model
    5. Producer consumer or pipeline model
    6. Hybrid model
    Data Parallel Model
    The data-parallel model is one of the simplest
    algorithm models.

    Tasks are assigned to processes and each task


    performs similar types of operations on different
    data.

    Data Parallel This type of parallelism that is a result of identical


    operations being applied concurrently on different
    Model data items is called data parallelism.
    Data parallelism is a consequence of single
    operations that is being applied on multiple data
    items.
    The work may be done in phases and the data
    operated upon in different phases may be different
    Data Parallel Model

    • Data-parallel model can be


    applied on shared-address
    spaces and message-passing
    paradigms.
    • A key characteristic of data-
    parallel problems is that the
    degree of data parallelism
    increases with the size of
    the problem.
    • Making it possible to use
    more processes to
    effectively solve larger
    problems.
    • Example
    The Task Graph Model
    In the task graph model, parallelism is expressed
    by a task graph.

    The correlation among the tasks are utilized to


    promote minimum interaction costs.

    The Task
    Graph Model This model is enforced to solve problems in which
    the quantity of data associated with the tasks is
    huge compared to the number of computation
    associated with them.

    The tasks are assigned to help improve the cost of


    data movement among the tasks.
    The Task Graph Model
    • Each task is an independent unit of job that has
    dependencies on one or more antecedent task.

    • After the completion of a task, the output of an


    antecedent task is passed to the dependent task.

    • A task with antecedent task starts execution only


    when its entire antecedent task is completed.

    • The final output of the graph is received when


    the last dependent task is completed (Task 6 in
    the figure).

    • Example: parallel quicksort


    Work Pool Model
    • The work pool or the task pool model.
    • Dynamic mapping of tasks onto processes for load balancing.
    • No desired Pre mapping
    • Mapping may be centralized or decentralized
    • The work may be statically available in the beginning, or could be
    dynamically generated; i.e., the processes may generate work and
    add it to the global (possibly distributed) work pool.
    • If Work is generated dynamically and a decentralized mapping is used,
    then a termination detection algorithm would be required.
    • In the message-passing
    paradigm, the work
    pool model is typically
    used when the amount
    of data associated with
    tasks is relatively small
    compared to the
    computation associated
    with the tasks.
    • Examples
    1) Parallelization of loops
    by chunk scheduling in
    centralized mapping
    2) Parallel tree search
    The Master-Slave Model
    The Master-Slave Model
    In the master-slave model, one or more master processes generate
    task and allocate it to slave processes. The tasks may be allocated a
    priori if -
     the master can estimate the volume of the tasks, or
     a random assigning can do a satisfactory job of balancing load

    In another scenario, workers are assigned smaller pieces of work at


    different times.
    This model is generally equally suitable to shared-address-
    space or message-passing paradigms, since the interaction is naturally
    two ways.
    The master-slave
    model can be
    generalized
    to hierarchical or m
    ulti-level master-
    slave model in
    which the top level
    master feeds the
    large portion of
    tasks to the second-
    level master.
    Care should be taken to assure that the master does not become a congestion point. It
    may happen if the tasks are too small or the workers are comparatively fast.

    The granularity of tasks should be chosen such that the cost of doing work dominates
    the cost of transferring work and the cost of synchronization.

    Asynchronous interaction may help overlap interaction and the computation


    associated with work generation by the master.
    The Pipeline Model
    • It is also known as the producer-consumer
    model
    • In this model, a stream of data is passed on
    through a series of processes, each of which
    performs some task on it
    • This simultaneous execution of different programs on a
    data stream is called stream parallelism.
    • The processes could form such pipelines in the
    form of arrays, trees, or general graphs etc
    Example −
    Parallel LU
    factorization
    algorithm.
    Hybrid Models
    Hybrid Models

    • A hybrid algorithm model is required when more than one


    model may be needed to solve a problem.
    • Possible to use multiple models
    • Hierarchical
    • Different models at different levels
    • Sequentially
    • Different models in different phases
    • An algorithm formulation may have characteristics more
    than one algorithm model
    • Major computations
    use task graph
    model
    • Each node of graph
    may use a data
    parallelism or
    pipelined model
    • Example : parallel
    quick short

    You might also like