Problem partitioning in parallel processor simulation systems

✍ Scribed by E.Pearse O'Grady

• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 774 KB
• Volume: 28
• Category: Article
• ISSN: 0378-4754
• DOI: 10.1016/0378-4754(86)90108-4

✦ Synopsis

Problem partitioning

to solve ordinary differential equations on a parallel processor system using classical numerical integration methods involves defining and ordering computation tasks and scheduling the tasks for execution. In defining tasks there is a tradeoff between decomposing a computation into a large number of primitive tasks to expose all potential parallelism and decomposing it into a smaller number of tasks to simplify scheduling. Scheduling is an intractable problem; heuristic scheduling algorithms reduce the effort required to schedule tasks but cannot guarantee that the parallel solution will execute in minimum time. An example illustrates difficulties encountered in scheduling tasks for parallel computation and use of a dependency graph as a tool in problem partitioning. The need for an efficient mechanism for asynchronous data exchanges among processors is demonstrated.