Parallel and Distributed Computing

Part of: Computer Systems & Networks

Doing Work at the Same Time Most early programs ran sequentially : one step finished before the next began. Modern systems often run work in parallel to go faster. - Parallel computing uses multiple processors (or cores) on a single machine, each handling part of a problem at the same time. - Distributed computing spreads work across many separate computers connected by a network , such as a data center or a worldwide research project. Modeling Parallel Time When tasks run on several workers at once, the job is not finished until the busiest worker is done. So: - Sequential time = the sum of all task durations (one worker does everything). - Parallel time = the load of the most loaded worker. Balancing the Load If tasks are unevenly assigned, one worker can be overloaded while others sit idle. A common heuristic is to assign each task (largest first) to the currently least-loaded worker: Here one worker gets the size-5 task and the other gets 2 + 1 = 3, so the job finishes in 5, not 8. Costs of Parallelism - Coordination overhead : splitting work and combining results takes time. - Communication : distributed workers must send data over a network, which adds latency. - Imbalance :

Challenge: Compute Sequential vs Parallel Time