locked
some alogrithem could not run parallel ?? RRS feed

  • Question

  • Dear All

     I have question,   is it  true that some alogrithem could not run  parallel ?(inherently sequential )  , if  yes  , please give me an Example

    Thursday, June 17, 2010 12:34 PM

Answers

  • Its easy to construct trivial examples like:

    while (some_condition()) { do_something(); }

    Assuming that some_condition() and do_something() are an external library and we don't have control over it, you cannot parallelize this loop.

    Constructing non-trivial cases is harder.  Generally, you can't parallelize the iterations of while loops where the condition is external and/or has side-effects, like reading from a TCP connection.  But even those cases tend to have some pipeline parallelism downstream, i.e. you can separate the while-loop-based reader/producer thread from a separate consumer thread. 

    Its also worth noting that even the most intractably sequential algorithms do get some parallelism at the CPU instruction level, where multiple instructions can be scheduled in parallel, but that's not really what you're talking about.


    John Lilley CTO DataLever Corporation
    • Proposed as answer by Dana Groff Thursday, June 24, 2010 4:53 PM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Friday, June 18, 2010 1:42 PM
  • Hi,

    First of all it depends of what kind of parallel. Math requires a multi-core CPU. Data scanning requires parallel memory. Searching in a file requires multiple hard drives.

    There are types of algorithms that cannot be fully parallel or only some part can be parallel. For example X[n] = X[n-1] + 12. You have to go according to the dependency between iterations. Partial dependency for example:

    X[n] = X[n-1] + 12;

    Y[n] = X * 12;

    You can run the second part in parallel.

    Regards,

    Asaf


    Asaf Shelly [Microsoft MVP]
    • Proposed as answer by Dana Groff Thursday, June 24, 2010 4:53 PM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Sunday, June 20, 2010 11:50 AM
  • Asaf,

    Just to clarify, you seem to be assuming a loop over n around the two statements above. That's implicit in your comment about iterations, but possibly unclear to someone less familiar with parallelizing loops. (Besides, not all parallelism involves loops.)

    Also, perhaps you meant:

        ...

        Y[n] = X[n] + 12;

    The example in Y that you gave is also parallelizable, but this way the Y expression is closer to the X expression; hence the crucial difference (inter-iteration dependence) is more apparent.

     

    --Ed Segall

     

    • Proposed as answer by Amare1982 Tuesday, July 13, 2010 6:44 AM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Thursday, June 24, 2010 10:20 PM
  • Hi Ed,

    You are correct. This should have been Y = X[n].

    I have actually explained this with more details as part of a solution to this pattern here:

    http://software.intel.com/en-us/blogs/2010/07/01/automatic-parallelization-design-pattern/

    How does that sound?

    Regards,

    Asaf


    Asaf Shelly [Microsoft MVP]
    • Proposed as answer by Amare1982 Thursday, July 15, 2010 12:48 AM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:34 PM
    Tuesday, July 13, 2010 8:45 AM

All replies

  • Its easy to construct trivial examples like:

    while (some_condition()) { do_something(); }

    Assuming that some_condition() and do_something() are an external library and we don't have control over it, you cannot parallelize this loop.

    Constructing non-trivial cases is harder.  Generally, you can't parallelize the iterations of while loops where the condition is external and/or has side-effects, like reading from a TCP connection.  But even those cases tend to have some pipeline parallelism downstream, i.e. you can separate the while-loop-based reader/producer thread from a separate consumer thread. 

    Its also worth noting that even the most intractably sequential algorithms do get some parallelism at the CPU instruction level, where multiple instructions can be scheduled in parallel, but that's not really what you're talking about.


    John Lilley CTO DataLever Corporation
    • Proposed as answer by Dana Groff Thursday, June 24, 2010 4:53 PM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Friday, June 18, 2010 1:42 PM
  • Hi,

    First of all it depends of what kind of parallel. Math requires a multi-core CPU. Data scanning requires parallel memory. Searching in a file requires multiple hard drives.

    There are types of algorithms that cannot be fully parallel or only some part can be parallel. For example X[n] = X[n-1] + 12. You have to go according to the dependency between iterations. Partial dependency for example:

    X[n] = X[n-1] + 12;

    Y[n] = X * 12;

    You can run the second part in parallel.

    Regards,

    Asaf


    Asaf Shelly [Microsoft MVP]
    • Proposed as answer by Dana Groff Thursday, June 24, 2010 4:53 PM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Sunday, June 20, 2010 11:50 AM
  • Asaf,

    Just to clarify, you seem to be assuming a loop over n around the two statements above. That's implicit in your comment about iterations, but possibly unclear to someone less familiar with parallelizing loops. (Besides, not all parallelism involves loops.)

    Also, perhaps you meant:

        ...

        Y[n] = X[n] + 12;

    The example in Y that you gave is also parallelizable, but this way the Y expression is closer to the X expression; hence the crucial difference (inter-iteration dependence) is more apparent.

     

    --Ed Segall

     

    • Proposed as answer by Amare1982 Tuesday, July 13, 2010 6:44 AM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:33 PM
    Thursday, June 24, 2010 10:20 PM
  • Hi Ed,

    You are correct. This should have been Y = X[n].

    I have actually explained this with more details as part of a solution to this pattern here:

    http://software.intel.com/en-us/blogs/2010/07/01/automatic-parallelization-design-pattern/

    How does that sound?

    Regards,

    Asaf


    Asaf Shelly [Microsoft MVP]
    • Proposed as answer by Amare1982 Thursday, July 15, 2010 12:48 AM
    • Marked as answer by Dana Groff Monday, July 19, 2010 5:34 PM
    Tuesday, July 13, 2010 8:45 AM
  • Tahani,

    Your question has generated a great discussion, thank you.   Do you have any follow up information required?  I have indicated a few of these replies are good answers to your question. 

    If I don't see any follow up by 7/16, I will mark this thead as "answered". 

    -Dana

    • Proposed as answer by Amare1982 Thursday, July 15, 2010 12:47 AM
    Wednesday, July 14, 2010 10:51 PM