Partitioning is the first step in Foster’s methodology for designing concurrent systems. It breaks a problem into small tasks that can run independently, revealing opportunities for parallel execution. section 13.2 section 13.4
Two complementary ways to divide work are:
- Data decomposition splits a large dataset into parts that can be processed independently. section 13.4
- Task decomposition divides calculations by their function. A design can combine both approaches. section 13.4
Planning a road trip
Route planning, booking accommodation, and researching places to visit are separate tasks that friends can take on concurrently. The analogy makes independent work easier to spot before considering how to coordinate it. section 13.2
At this stage, look for as many small tasks as possible without accounting for processor count or machine type. The guidance is to find at least an order of magnitude more tasks than processors. Some algorithms cannot be decomposed; vertical scaling may help, but has physical limits. section 13.4 section 13.4
