Search code examples
algorithmoptimizationdesign-patternsparallel-processingopenmp

Examples where 4-step PCAM (Foster's Methodology) is applied to parallel algorithm design?

Foster's metholodogy has 4 steps to designing parallel algorithms

  • Partitioning

  • Communication

  • Agglomeration

  • Mapping

Many examples I'm coming across take a very mathematical approach. While I can understand that math is essential, I was wondering if there was an easier way of explanation the PCAM method to someone who isn't computer science oriented?

Solution

  • Let's suppose you are going to the supermarket for some grocery shopping and you have a partner with you, in that case your computer has two processors or two threads (you and your partner).

    First we partition the problem into tasks:

    • Create a shopping list
    • Drive to the supermarket
    • Get all the items in the list
    • Pay for the items
    • Drive back home
    • Store all the items
    • Park the car (let's assume the garage is far away from the house)

    Then you define the communication

    • To create the shopping list each processor will check the house for what is missing and will get together from time to time to consolidate the list
    • In the supermarket each processor will go get some goods and will get together at the cart to choose another item from the list so that no processor go looking for the same item at the same time
    • While one processor is storing the items the other goes park the car, when the processor is back it may help store the items that are still left

    Agglomeration of tasks (Unfortunately I already described them agglomerated)

    Mapping

    • You check some items, your partner the others
    • Any processor drives to the supermarket (but the other goes together)
    • You go get some item and your partner gets a different item until the list is complete
    • Any processor pays for the goods (hopefully, your partner)
    • Any processor drives back to leave a processor at home storing the items
    • The driver processor goes park the car
    • The non-driver processor starts storing the goods
    • The driver processor gets back and check what goods are still left and helps store the goods

    This is completely non-mathematical and was the best example that I could come up with, any non-computer science person that is willing to understand the method may grasp the idea (I hope).

    Cheers!