4,580 Posts served

11,094 Conversations started

It's a Pattern! It's an Algorithm! It's a Dessert Topping!

By Clay Breshears (Intel) (196 posts) on January 16, 2009 at 3:36 pm

I was asked about what the difference was between a (parallel) programming pattern and an algorithm.  If you've read Patterns for Parallel Programming and Introduction to Algorithms (aka CLRS), you know the answer.  I'd be willing to bet that anyone even merely interested in object-oriented programming has at least heard of Design Patterns, and they probably know the difference, too.  For the rest of you, let me see if I can clear up any confusion you might have on the topics.  A prior manager of mine had a knack for creating analogies for situations that got to the heart of the matter, so I'll try an analogy here. 

A recipe to bake a cake is an algorithm.  This is a set of steps to accomplish a complex task.  An algorithm can be designed to give instructions on how to perform just about any job.  One of the favorite teaching exercises I've heard used on beginning programming students is to have them give the algorithm to do some everyday task, like put on a raincoat.  The professor plays the executor of the instructions and does everything without an assumptions.  When things go wrong it demonstrates the care needed in computer programs to specify exactly the right set of instructions.

Measuring out the dry ingredients for the cake would be a pattern.  Patterns are small and simple tasks that can typically be applied to a wide range of objects.  While the size of the device may change, how you measure and add flour is probably the same way you measure out and add the sugar is the same way you would measure and add salt.  Plus, it's the same pattern if you're baking cookies or pies.  Measuring liquid ingredients for the cake would be a different pattern as would separating the whites and yolks of eggs.

In terms of computation, you have sorting and searching algorithms and algorithms to find spanning trees of graphs or find the convex hull of a set of points.  There are patterns for iterating through a sequence of indexed items (a loop on an array) and for executing one of two separate code blocks based on the outcome of a conditional expression (if-then-else).  You can use patterns in the implementation of an algorithm.  For example, a comparison-based sort algorithm will need to cycle through the data items to be sorted and, at times, swap the order of two items if one should precede the other in the sorted sequence. 

Not really rocket science, is it?  (I'm getting hungry for a piece of cake, though.)

Parallel patterns are just those small tasks that can execute concurrently.  For example, concurrently execute the bodies of loop iterations that are independent.  The Berkeley Motifs (aka Dwarfs) scale the idea of parallel patterns to applications that have similar computations and, therefore, should be implemented with similar (and well-defined) parallel algorithms employing lower-level parallel patterns.

Categories: Academic, Parallel Programming, Software Tools

For more complete information about compiler optimizations, see our Optimization Notice.

Comments (4)

January 16, 2009 2:47 PM PST Aaron Tersteeg (Intel) Total Points: 20,165 Community Manager

Thanks Clay. You make is sound as easy as pie! Or as in your example cake.

January 18, 2009 11:24 AM PST Adrian Offerman

Thanks. Maybe you could make a connection to objects, libraries and functions when talking about patterns?

January 19, 2009 6:18 AM PST Clay Breshears (Intel) Total Points: 30,566 Black Belt

Adrian - I think that this was done in Design Patterns, at least as far as objects goes (or using objects within patterns). I've not read the book (or any of the myriad books that are written about patterns in various programming languages), so that might be the better place to start.

January 19, 2009 6:57 AM PST Tonya

It is all becoming clearer now! So, if we no want to decorate the cake - that's another algorithm, correct?

Trackbacks (1)

• Parallel Programming Talk #47 – Software Development for N-core Processing
  September 16, 2009 3:01 PM PDT

Leave a comment