index(4).html

Pthread lib库完整说明文档

<P>
    This problem is able to be solved in parallel. Each of the 
    molecular conformations is independently determinable.
    The calculation of the minimum energy conformation is also a
    parallelizable problem. 
<P>
<LI>Example of a Non-parallelizable Problem: 
<P>
<TABLE BORDER=1 CELLPADDING=5 CELLSPACING=0 WIDTH=75%>
<TR><TD>
    Calculation of the Fibonacci series (1,1,2,3,5,8,13,21,...) by use of 
    the formula: 
    <PRE>
    F(k + 2) = F(k + 1) + F(k)     </PRE>
</TABLE>
<P> This is a non-parallelizable problem because the calculation of the 
    Fibonacci sequence as shown would entail
    dependent calculations rather than independent ones. 
    The calculation of the k + 2 value uses those of
    both k + 1 and k.  These three terms cannot be calculated
    independently and therefore, not in parallel.
</UL> 
<P>
<LI>Identify the program's <I><B>hotspots</B></I>:
    <UL>
    <LI>Know where most of the real work is being done.  
        The majority of scientific and technical programs usually 
        accomplish most of their work in a few places. 
    <LI>Profilers and performance analysis tools can help here
    <LI>Focus on parallelizing the hotspots and ignore those sections
        of the program that account for little CPU usage. 
    </UL>
<P>
<LI>Identify <I><B>bottlenecks</B></I> in the program
    <UL>
    <LI>Are there areas that are disproportionately slow, or cause 
        parallelizable work to halt or be deferred?
        For example, I/O is usually something that slows a program down.
    <LI>May be possible to restructure the program or use a different
        algorithm to reduce or eliminate unnecessary slow areas
    </UL>
<P>
<LI>Identify inhibitors to parallelism.  One common class of inhibitor
    is <I>data dependence</I>, as demonstrated by the Fibonacci sequence
    above.  
<P>
<LI>Investigate other algorithms if possible.  This may be the single most
    important consideration when designing a parallel application.
</UL>


<!--========================================================================-->
<P>
<A NAME=DesignPartitioning> <BR><BR> </A>
<TABLE BORDER=1 CELLPADDING=5 CELLSPACING=0 WIDTH=100%>
<TR><TD BGCOLOR=#98ABCE>
<SPAN class=heading1>Designing Parallel Programs</SPAN></TD>
</TD></TR></TABLE>
<H2>Partitioning</H2>

<UL>
<P>
<LI>One of the first steps in designing a parallel program is to break the
    problem into discrete "chunks" of work that can be distributed to
    multiple tasks.  This is known as decomposition or partitioning.
<P>
<LI>There are two basic ways to partition computational work among parallel 
    tasks: <B><I>domain decomposition</I></B> and 
    <B><I>functional decomposition</I></B>. 
</UL>
<P>

<IMG SRC=../images/arrowBullet.gif ALIGN=top HSPACE=3>
<SPAN CLASS=heading3>Domain Decomposition:</SPAN>
    <UL>
    <P>
    <LI>In this type of partitioning, the data associated with a problem
        is decomposed.  Each parallel task then works on a portion of
        of the data.
    <P><IMG SRC=images/domain_decomp.gif WIDTH=388 HEIGHT=216 BORDER=0
       <ALT='Domain Decomposition'>
    <P>
<A NAME=distributions> </A>
    <LI>There are different ways to partition data:
    <P><IMG SRC=images/distributions.gif WIDTH=432 HEIGHT=332 BORDER=0
       <ALT='Different types of domain decomposition'>
    </UL>
<P>

<IMG SRC=../images/arrowBullet.gif ALIGN=top HSPACE=3>
<SPAN CLASS=heading3>Functional Decomposition:</SPAN>
    <UL>
    <P>
    <LI>In this approach, the focus is on the computation that is to be      
        performed rather than on the data manipulated by the computation.
        The problem is decomposed according to the work that must be done.
        Each task then performs a portion of the overall work.
    <P><IMG SRC=images/functional_decomp.gif WIDTH=400 HEIGHT=250 BORDER=0
       <ALT='Functional Decomposition'>
    <P>
    <LI>Functional decomposition lends itself well to problems that can be
        split into different tasks.  For example:
        <DL>
        <P>
        <DT><B>Ecosystem Modeling</B>
        <DD>Each program calculates the population
            of a given group, where each group's growth depends on that of its
            neighbors. As time progresses, each process calculates
            its current state, then exchanges information with the neighbor  
            populations. All tasks then progress to calculate the state at the
            next time step.
        <P>
        <IMG SRC=images/functional_ex1.gif WIDTH=567 HEIGHT=221 BORDER=0
        ALT='Functional decomposition example'>
        <P>
        <DT><B>Signal Processing</B>
        <DD>An audio signal data set is passed
            through four distinct computational filters. Each filter is a 
            separate process. The first segment of data must pass through the
            first filter before progressing to the second. When it does, the
            second segment of data passes through the first filter. By the time
            the fourth segment of data is in the first filter, all four
            tasks are busy.
        <P>
        <IMG SRC=images/functional_ex2.gif WIDTH=703 HEIGHT=272 BORDER=0
        ALT='Functional decomposition example'>
        <P>
        <DT><B>Climate Modeling</B>
        <DD>Each model component can be thought of as a separate task.
            Arrows represent exchanges of data between components during
            computation: the atmosphere model generates wind velocity data 
            that are used by the ocean model, the ocean model generates sea
            surface temperature data that are used by the atmosphere model, 
            and so on.
        <P>
        <IMG SRC=images/functional_ex3.gif WIDTH=372 HEIGHT=257 BORDER=0
        ALT='Functional decomposition example'>
        </DL>
<P>
<LI>Combining these two types of problem decomposition is common and natural.
<P>
</UL>


<!--========================================================================-->
<P>
<A NAME=DesignCommunications> <BR><BR> </A>
<TABLE BORDER=1 CELLPADDING=5 CELLSPACING=0 WIDTH=100%>
<TR><TD BGCOLOR=#98ABCE>
<SPAN class=heading1>Designing Parallel Programs</SPAN></TD>
</TD></TR></TABLE>
<H2>Communications</H2>

<IMG SRC=../images/arrowBullet.gif ALIGN=top HSPACE=3>
<SPAN CLASS=heading3>Who Needs Communications?</SPAN>
<UL>
<P>The need for communications between tasks depends upon your problem:
<P>
<LI><B>You DON'T need communications</B>
    <UL>
    <LI>Some types of problems can be decomposed and executed in parallel
    with virtually no need for tasks to share data.  For example, imagine an
    image processing operation where every pixel in a black and white image
    needs to have its color reversed.   The image data can easily be 
    distributed to multiple tasks that then act independently of each other
    to do their portion of the work.  
    <LI>These types of problems are often called <B><I>embarrassingly
    parallel</I></B>
    because they are so straight-forward.  Very little inter-task communication
    is required.
    </UL>
<P>
<LI><B>You DO need communications</B>
    <UL>
    <LI>Most parallel applications are not quite so simple, and do require 
    tasks to 
    share data with each other.  For example, a 3-D heat diffusion problem
    requires a task to know the temperatures calculated by the tasks that have
    neighboring data.  Changes to neighboring data has a direct effect on that
    task's data.
    </UL>
</UL>
<P>

<IMG SRC=../images/arrowBullet.gif ALIGN=top HSPACE=3>
<SPAN CLASS=heading3>Factors to Consider:</SPAN>
<UL>
<P>
There are a number of important factors to consider when designing your
program's inter-task communications:
<P>
<LI><B>Cost of communications</B>
    <UL>
    <LI>Inter-task communication virtually always implies overhead.
    <LI>Machine cycles and resources that could be used for computation
        are instead used to package and transmit data.
    <LI>Communications frequently require some type of synchronization
        between tasks, which can result in tasks spending time "waiting"
        instead of doing work.
    <LI>Competing communication traffic can saturate the available network
        bandwidth, further aggravating performance problems.
    </UL>
<P>
<LI><B>Latency vs. Bandwidth</B>
    <UL>
    <LI><B><I>latency</I></B> is the time it takes to send a minimal (0 byte)
        message from point A to point B.  Commonly expressed as microseconds.
    <LI><B><I>bandwidth</I></B> is the amount of data that can be communicated
        per unit of time.  Commonly expressed as megabytes/sec.
    <LI>Sending many small messages can cause latency to dominate communication
        overheads.  Often it is more efficient to package small messages into a
        larger message, thus increasing the effective communications bandwidth.
    </UL>
<P>
<LI><B>Visibility of communications</B>
    <UL>
    <LI>With the Message Passing Model, communications are explicit and
        generally quite visible and under the control of the programmer.  
    <LI>With the Data Parallel Model, communications often occur
        transparently to the programmer, particularly on distributed 
        memory architectures.  The programmer may not even be able to
        know exactly how inter-task communications are being accomplished.
    </UL>
<P>
<LI><B>Synchronous vs. asynchronous communications</B>
    <UL>
    <LI>Synchronous communications require some type of "handshaking"
        between tasks that are sharing data.  This can be explicitly
        structured in code by the programmer, or it may happen at a
        lower level unknown to the programmer.
    <LI>Synchronous communications are often referred to as
        <B><I>blocking</I></B> communications since other work must
        wait until the communications have completed.
    <LI>Asynchronous communications allow tasks to transfer data independently
        from one another. For example, task 1 can prepare and send a
        message to task 2, and then immediately begin doing other work.
        When task 2 actually receives the data doesn't matter. 
    <LI>Asynchronous communications are often referred to as
        <B><I>non-blocking</I></B> communications since other work can
        be done while the communications are taking place.
    <LI>Interleaving computation with communication is the single greatest
        benefit for using asynchronous communications.
    </UL>
<P>
<LI><B>Scope of communications</B>
    <UL>
    <LI>Knowing which tasks must communicate with each other is critical during
        the design stage of a parallel code. Both of the two scopings 
        described below can be implemented synchronously or asynchronously.
    <LI><B><I>Point-to-point</I></B> - involves two tasks with one task
        acting as the sender/producer of data, and the other acting as 
        the receiver/consumer.
    <LI><B><I>Collective</I></B> - involves data sharing between more than
        two tasks, which are often specified as being members in a common 
        group, or collective. Some common variations (there are more):
    <P>
    <IMG SRC=images/collective_comm.gif WIDTH=400 HEIGHT=317 BORDER=0
    ALT='Collective communications examples'> 
    </UL>
<P>
<LI><B>Efficiency of communications</B>
    <UL>
    <LI>Very often, the programmer will have a choice with regard to
        factors that can affect communications performance.  Only a
        few are mentioned here.        
    <LI>Which implementation for a given model should be used?  Using
        the Message Passing Model as an
        example, one MPI implementation may be faster on a given
        hardware platform than another.
    <LI>What type of communication operations should be used?  As
        mentioned previously, asynchronous communication operations
        can improve overall program performance.
    <LI>Network media - some platforms may offer more than one network
        for communications.  Which one is best?
    </UL>
<P>
<P>
<LI><B>Overhead and Complexity</B>
<P>    
    <IMG SRC=images/helloWorldParallelCallgraph.gif WIDTH=914 HEIGHT=497 
    BORDER=0 ALT='Callgraph of parallel hello world program'>
<P>
<LI>Finally, realize that this is only a partial list of things to consider!!!
</UL>


<!--========================================================================-->
<P>
<A NAME=DesignSynchronization> <BR><BR> </A>
<TABLE BORDER=1 CELLPADDING=5 CELLSPACING=0 WIDTH=100%>
<TR><TD BGCOLOR=#98ABCE>
<SPAN class=heading1>Designing Parallel Programs</SPAN></TD>
</TD></TR></TABLE>
<H2>Synchronization</H2>

<IMG SRC=../images/arrowBullet.gif ALIGN=top HSPACE=3>
<SPAN CLASS=heading3>Types of Synchronization:</SPAN>
<UL>
<P>
<LI><B>Barrier</B>
    <UL>
    <LI>Usually implies that all tasks are involved
    <LI>Each task performs its work until it reaches the barrier.  It then
        stops, or "blocks".        
    <LI>When the last task reaches the barrier, all tasks are synchronized.
    <LI>What happens from here varies.  Often, a serial section of work must
        be done.  In other cases, the tasks are automatically released to
        continue their work.  
    </UL>
<P>
<LI><B>Lock / semaphore</B>
    <UL>
    <LI>Can involve any number of tasks
    <LI>Typically used to serialize (protect) access to global data
        or a section of code. Only one task at a time may use (own) the 
        lock / semaphore / flag.
    <LI>The first task to acquire the lock "sets" it.  This task can then
        safely (serially) access the protected data or code.
    <LI>Other tasks can attempt to acquire the lock but must wait until the
        task that owns the lock releases it.
    <LI>Can be blocking or non-blocking
    </UL>
<P>
<LI><B>Synchronous communication operations</B>
    <UL>
    <LI>Involves only those tasks executing a communication operation
    <LI>When a task performs a communication operation, some form of
        coordination is required with the other task(s) participating in
        the communication.  For example, before a task can perform a
        send operation, i