Traditionally, programs are made with sequential computing in mind. That's when program instructions are processed one at a time.
However, as the demand for computers to become faster increased, sequential processing wasn't able to keep up. This is in part because you can only make a single processor so fast before the amount of heat it's generating literally causes it to melt.
This problem led to the creation of new models of computing known as parallel and distributed computing.
Parallel and Distributed Computing Definitions
Parallel computing is where a program is broken into smaller sequential computing operations. Some of these operations are done at the same time using multiple processors. Most modern computers use parallel computing systems, with anywhere from 4 to 24 cores (or processors) running at the same time.
There are several advantages to parallel computing.
- Performing tasks at the same time helps to save a lot of time, and money as well.
- Parallel computing solutions are also able to scale more effectively than sequential solutions. This means if there's a change in scale (ex: more instructions to process than before), these solutions will handle the change better than sequential computing models would.
Distributed computing, on the other hand, is where multiple devices are used to run a program. These devices can be in different locations around the world, communicating by sending messages to each other. 🌎
With a distributed computing model, two "heads" are better than one. You get the power of two (or more) computers working on the same problem. Using distributed computing allows people to solve problems that they wouldn't be able to otherwise, due to a lack of storage or needing too much processing time otherwise. Modern search engines, applications that store data somewhere separate from the user's computer like Gmail and Google Docs, and sigh cryptocurrency mining all use distributed computing.
Due to their increased capacities, a parallel or distributed computing model can process large data sets or solve complex problems faster than a sequential computing model can. They come with the added perk of not melting your computer while they're doing it.
Execution Time, Efficiency, and Speedup Calculations
The AP CSP test will have conceptual questions about parallel and distributed computing, but they'll also have some calculation questions, too. The test may ask you to calculate the execution time of a sequential or a parallel computing solution. They may also ask you to compare the efficiency of two solutions. Finally, the test may ask you to calculate the speedup of a certain parallel solution.
Calculating Execution Time
Sequential Solutions
A sequential solution takes as long as the sum of all steps in the program. For example, if your program has three steps that take 40, 50, and 80 seconds respectively, the sequential solution would take 170 seconds to complete.
Parallel Computing Solutions
The speed of a parallel computing solution, on the other hand, depends on the number of cores involved. The more cores, the faster (to an extent) the solution is.
One of the best ways to understand this calculation is with examples. Going back to our original example with those three steps of 40, 50, and 80 seconds, a parallel computing solution where two processors are running would take 90 seconds to complete at its fastest.
Why is that?
Well, it's important to first acknowledge that we're working under the assumption that all steps are independent. The 40-second step, for example, doesn't depend on the result of the 80-second step in order to start. Therefore, the processors are free to do the steps in any order or combination.
Generally, you'll be looking for the minimum possible time, so we're going to want to do the longer processes first and at the same time. Let's call the two Processors Processor 1 and Processor 2. To minimize the amount of time needed, Processor 2 should do the 80-second step, and Processor 1 should do the 40 and 50-second steps sequentially. Processor 1 would complete the 40-second and the 50-second step in 90 seconds (taking the sum of each sequential step) and Processor 2 would complete the 80-second step in... well, 80 seconds.
Even though Processor 2 only took 80 seconds, it still has to *"*wait" for Processor 1 before the solution is complete.
In the example above, it was Processor 1’s 40 and 50-second sequential tasks that determined the final speed of the solution. However, this isn't always the case. In some cases, the longest parallel task will determine the final speed. If the task Processor 2 needed to do had taken 100 seconds, then the computing solution would have taken 100 seconds in total because of it.
Still confused? Check out the practice problem below. Practice makes perfect with these questions!
Clearly enough, the parallel computing solution is faster. A way to quantify just how much faster is called the speedup.
Calculating the Speedup
The speedup of a parallel solution is calculated by dividing the time it took to complete the task sequentially by the time it took to complete the task in parallel.
In the example above, that would be 170 (the time it took sequentially) divided by 90, or 1.88.
Speed Limits
Note that a parallel computing model can only be as fast as the speed of its sequential portions. Some steps need to be done sequentially, such as steps that require data from earlier steps in order to begin, and this will affect the overall speed.
For a non-programming example of this, imagine that some students are making a slideshow. One student is in charge of turning in the slideshow at the end. That student has to wait until everyone else is done to turn in the slideshow—that step can't be done in parallel with the steps it takes to work on the slideshow. It is not an independent step.
Before you start a speed calculation problem, make sure you know whether or not all steps are independent. Don't just assume they all are. (The question should tell you if they are or not.)
Eventually, the speedup effect of adding more parallel processors will wane the more and more you add them. This is because, inevitably, you'll need to wait on something that parallel computing can't speed up: either for sequential steps to complete or for other overhead such as communication time between processors. ⌚
Example Problem
Now, let's try this example problem, straight from page 177 of the College Board's CED:
Answer
The answer is C: 80 seconds.
The easiest way to think of this is to walk through how the processors will operate.
We know that the computer has two processors, and that each processor can only run one process at a time. We have three processes to finish: a 60-second, 30-second and 50-second one.
None of the processes are dependent on each other, which means that they're free to run in any order and to run parallel to each other. In other words, you don't need to wait for any of the processes to finish before you start another.
Let's call these processors Processor A and Processor B.
So, what would the processors do?
- The question tells us we're looking for the minimum possible time, so we're going to want to do the longer processes first and at the same time. When computing begins, Processor A starts running the 60-second process and Processor B starts running the 50-second process.
- Processor B finishes the 50-second process and begins the 30-second process while Processor A is still running the 60-second process.
- Processor A finishes running the 60-second process and finds that there aren't any more processes to run. At this point, 60 seconds have passed overall, and Processor B is 10 seconds into running the 30-second process.
- Processor B finishes running 20 seconds later. (It might help to draw a picture if you're having trouble keeping track of all the processes.)
Looking at this list, we can see that it takes 60 + 20 seconds to complete everything, which will add up to make 80 seconds in total.
Another way to think of this is to think about how long it will take the processor with the most work to do to finish its work. One of the processors has to complete both the 50-second and 30-second processes in series (while the other one only needs to do one, 60-second process), which adds to make 80 seconds. The 60-second step, done in parallel, is shorter than the time needed. That means it occurs while the sequential step is still running and doesn't affect the total time.
In Conclusion...
There we go! Another Big Idea squared away.
In Big Idea 5, we'll be talking about the impacts that computing devices and networks have had on our day-to-day lives.
Frequently Asked Questions
How do I calculate speedup for parallel computing problems?
Speedup = (time to run sequentially) ÷ (time to run with parallelism). Per the CED: sequential time is the sum of all steps; parallel time = time for the required sequential parts + the longest parallel task (because parallel subtasks run simultaneously). Quick example: a job takes 100 s sequentially. 80 s of that is parallelizable and 20 s is strictly sequential. If you split the 80 s perfectly across 4 processors, the parallel portion takes 80 ÷ 4 = 20 s. Total parallel time = 20 s (sequential) + 20 s (longest parallel) = 40 s. Speedup = 100 ÷ 40 = 2.5. Also useful: efficiency = speedup ÷ number of processors (measures how well you use extra processors). Remember AP point: adding processors is limited by the sequential portion (see EK CSN-2.A.6 and EK CSN-2.B.5). For more practice, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and lots of practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
What's the difference between parallel computing and distributed computing?
Sequential, parallel, and distributed are three different computational models from the CED. Sequential runs steps one after another—total time = sum of all steps (EK CSN-2.A.1, EK CSN-2.A.5). Parallel splits a program into a sequential portion plus parts that run at the same time; total time = sequential portion + the longest parallel task, and speedup = (sequential time) / (parallel time) (EK CSN-2.A.2, EK CSN-2.A.6–7, EK CSN-2.B.1). Distributed computing runs parts of a program on multiple devices (different machines), letting you solve problems too big or slow for one computer (EK CSN-2.A.3, EK CSN-2.B.3–4). Key tradeoffs: parallel/distributed can be much faster and scale better but are limited by the sequential portion (Amdahl’s idea) and have extra overhead: coordination, communication, and fault tolerance (EK CSN-2.B.5). For AP exam focus: practice comparing solutions and computing efficiency per LO CSN-2.A. For more review, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and try practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
I'm confused about sequential vs parallel computing - can someone explain in simple terms?
Think of it like chores. Sequential computing does one step at a time—total time = sum of all steps (EK CSN-2.A.1, EK CSN-2.A.5). Parallel computing breaks a program into pieces that can run at the same time on one machine (some tasks still run sequentially). Total time ≈ time of the sequential portion plus the longest parallel task (EK CSN-2.A.2, EK CSN-2.A.6). Speedup = (sequential time) / (parallel time) (EK CSN-2.A.7). Distributed computing is like getting help from other devices (multiple computers) to share work or storage when one machine can’t handle it (EK CSN-2.A.3, EK CSN-2.B.3–4). Benefit: big problems finish faster or become solvable. Challenge: adding more parallelism has diminishing returns because the sequential portion still limits you (EK CSN-2.B.5). For AP prep, practice comparing times and computing speedup on the exam (Topic 4.3 study guide: https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild). Want more problems? Try the unit review (https://library.fiveable.me/ap-computer-science-principles/unit-4) and 1000+ practice questions (https://library.fiveable.me/practice/ap-computer-science-principles).
When should I use parallel computing instead of sequential computing for a problem?
Use parallel computing when the problem has parts that can run at the same time and those parts dominate the total work. If a task can be split into independent subtasks (EK CSN-2.A.2)—e.g., processing different chunks of a big dataset, running many simulations, or handling independent requests—parallelizing can reduce wall-clock time because total time ≈ sequential part + longest parallel part (EK CSN-2.A.6). But remember the limit: the sequential portion limits speedup (EK CSN-2.B.5), so if most work is inherently sequential, parallelism gives little benefit. Also use distributed computing when a single machine can’t handle the processing or storage needs (EK CSN-2.B.3–4). For AP exam questions, compare times (sequential sum vs. parallel max) and compute speedup = Ts/Tp (EK CSN-2.A.7). Want more practice on this Topic 4.3? Check the Fiveable study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and the unit overview (https://library.fiveable.me/ap-computer-science-principles/unit-4).
How do I figure out the efficiency of a parallel solution compared to a sequential one?
Think of time: a sequential solution takes the sum of all steps (EK CSN-2.A.5). For a parallel solution, total time = time of any sequential parts + the longest-running parallel task (EK CSN-2.A.6). To compare efficiency compute “speedup”: - T_seq = sum of all step times - T_par = T_sequential_portion + max(time of parallel subtasks) - Speedup = T_seq / T_par (EK CSN-2.A.7) Example: if a job has 100s total sequentially, with 20s that must stay sequential and the rest split into parallel tasks whose longest takes 30s, then T_par = 20 + 30 = 50s and speedup = 100/50 = 2×. Remember the limit: adding more parallel work hits diminishing returns because the sequential portion bounds efficiency (EK CSN-2.B.5). For more practice and AP-aligned examples, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and the AP practice question bank (https://library.fiveable.me/practice/ap-computer-science-principles).
Why does my parallel computing solution not get faster when I add more processors?
Most likely you’ve hit the limits described in the CED: a parallel program has a sequential portion and a parallel portion, and the sequential part limits overall speedup (EK CSN-2.B.1, EK CSN-2.B.5). Even if you add processors, total time ≈ (sequential time) + (longest parallel task) (EK CSN-2.A.6). Also factors like communication/coordination overhead, load imbalance, and contention for shared resources can erase gains or even slow things down. Quick numbers: if 10% of your task is strictly sequential, the theoretical max speedup is about 1/0.1 = 10× (EK CSN-2.A.7 idea). If overhead per processor is significant, real speedup will be much less. What to do: measure where time’s spent (profile), reduce the sequential fraction, balance work among processors, and cut communication/locking. For AP review, link the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and try practice problems (https://library.fiveable.me/practice/ap-computer-science-principles) to see these concepts on the exam.
What's the formula for calculating how long a parallel task takes to complete?
Formula: total parallel runtime = time of the sequential portion + the longest-running parallel chunk. In CED terms (EK CSN-2.A.6), if a solution has some steps that must run in sequence (Ts) and a set of tasks that can run at the same time whose longest takes Tp, then total time Tparallel = Ts + Tp. Example: if setup/merge = 5 s and the slowest parallel worker takes 10 s, the job finishes in 15 s. Speedup = Tsequential / Tparallel (EK CSN-2.A.7). Remember the practical limit: as you add more parallel work, the sequential portion Ts still bounds how much faster you can get (EK CSN-2.B.5). For more AP-aligned review and practice, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild), the Unit 4 overview (https://library.fiveable.me/ap-computer-science-principles/unit-4), and hundreds of practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
I don't understand what the "sequential portion" means in parallel computing - help?
The “sequential portion” is the part of a program that has to run step-by-step on one processor—it can’t be split to run at the same time as other parts. In AP terms: total parallel time = sequential portion + the longest parallel task (EK CSN-2.A.6). Examples: setup/initialization, reading input, or combining results from workers (like summing partial results) are often sequential. That means even if you make 100 tasks parallel, the sequential portion still has to finish, so adding more parallelism gives diminishing returns (EK CSN-2.B.5). To compare efficiency on the AP exam, use time measurements and compute speedup = sequential time ÷ parallel time (EK CSN-2.A.7). Want practice applying this? Check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and the 1,000+ practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
How do I determine if a problem is better solved with distributed computing or just parallel computing?
Think of three things: size, independence, and communication cost. - Size: If one machine’s CPU or memory can handle the data/work in a reasonable time, try parallel (use multiple cores/threads). If the problem needs more storage or total compute than any single machine has, you need distributed (EK CSN-2.B.3). - Independence: If tasks are mostly independent (little need to share intermediate results), parallel or distributed both work. If tasks must share lots of state frequently, parallel on a shared-memory system is usually faster because communication overhead is lower (EK CSN-2.A.6, CSN-2.B.5). - Communication/latency: Distributed systems add network overhead and complexity (coordination, failures). If network communication costs outweigh per-task speed gains, prefer parallel. If you must scale across many devices to finish at all or much faster, go distributed (EK CSN-2.B.4). Use Amdahl’s-like thinking: speedup is limited by the sequential portion—if most work is sequential, adding more parallel/distributed resources won’t help (EK CSN-2.A.7, CSN-2.B.5). Quick examples: image filter across pixels → parallel on one machine. Large web crawler or big-data analytics (too big for one machine) → distributed. For AP review, see the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
What are the main benefits and challenges of using distributed computing systems?
Distributed systems let a program run across multiple devices (EK CSN-2.A.3). Main benefits: they can solve problems too big for one computer (storage or processing) and run much faster by splitting work across machines, so larger problems finish quicker and solutions scale better than purely sequential ones (EK CSN-2.B.3, CSN-2.B.4). You can also get fault tolerance and geographic distribution for latency/reliability (related Topic 4.2). Main challenges: coordination and communication overhead between machines (adds time), data consistency, and more complex debugging and design. Efficiency is still limited by any sequential portion (Amdahl’s idea from EK CSN-2.B.5): after a point, adding more machines doesn’t improve speedup. Security, network failures, and added system complexity are practical hurdles too. For AP exam prep, be ready to compare times and calculate speedup (EK CSN-2.A.4–A.7). Review the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild), the unit overview (https://library.fiveable.me/ap-computer-science-principles/unit-4), and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
Can someone walk me through how to compare the time efficiency of sequential vs parallel solutions?
Start by computing how long each approach takes (CED EK CSN-2.A.5–A.6): - Sequential: time = sum of all steps. - Parallel: time = time of the required sequential parts + the longest running parallel task (because parallel tasks run at the same time). Also include communication/coordination overhead for distributed systems. Use “speedup” to compare (EK CSN-2.A.7): speedup = time(sequential) / time(parallel). Quick numeric example: total work = 100 time units, of which 80 can be parallelized and 20 must stay sequential. - If you run the 80 units on 4 processors evenly: longest parallel task ≈ 80/4 = 20. - Parallel total = sequential 20 + longest parallel 20 = 40. - Speedup = 100 / 40 = 2.5. Remember the limit: even with many processors, the sequential portion caps improvement (CED EK CSN-2.B.5/Amdahl-style idea). For distributed solutions add network/coordination cost, which can reduce speedup. For AP prep, you’ll be expected to do these calculations and state speedup on the exam. See the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles) for more examples.
Why can't parallel computing solutions scale infinitely - what limits them?
You can’t scale parallel computing infinitely because some parts of any program must run sequentially and because of real-world overhead. Per the CED, a parallel solution has a sequential portion plus parallel portions (EK CSN-2.B.1, EK CSN-2.A.6). No matter how many processors you add, the sequential part still takes the same time, so speedup = (sequential time) / (parallel time) is bounded. Beyond that, adding processors creates overhead: tasks need communication and coordination, data must be shared or synchronized (which costs time), and hardware resources (memory, network bandwidth) can become contention points. Those factors cause diminishing returns—at some point extra processors give almost no extra speed. This is exactly what the AP asks you to compare and reason about when evaluating parallel vs sequential efficiency (LO CSN-2.A, LO CSN-2.B). For a concise review, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and do practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).
How do I identify which parts of a program can be done in parallel vs sequentially?
Look for independence and dependencies. Parts you can run in parallel are independent tasks that don’t need results from each other (e.g., separate loop iterations that read/write different data, or associative reductions like sum). Sequential parts are those that must run in order because later steps depend on earlier results (setup, I/O, final combine). Quick checklist: - Identify data dependencies (does step B need output of A?). If yes → sequential. - Find repeated, independent work (many data items processed the same way) → good for parallel. - Look for associative operations (sum, max) that can be split and combined. - Separate the program into “sequential portion” and “parallel portion” (EK CSN-2.B.1). Measure times: T_seq = total sequential time; T_par = time with parallel parts (EK CSN-2.A.6). Speedup = T_seq / T_par (EK CSN-2.A.7). Remember Amdahl’s idea: extra parallelism is limited by the sequential portion (EK CSN-2.B.5). For examples and AP-style practice, check the Topic 4.3 study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and unit resources (https://library.fiveable.me/ap-computer-science-principles/unit-4). For lots of practice questions, use (https://library.fiveable.me/practice/ap-computer-science-principles).
What does it mean when they say parallel computing "scales more effectively" than sequential computing?
“Sscales more effectively” means that as you give a problem more resources (more cores or processors) or make the problem bigger, a parallel solution can reduce total time much more than a purely sequential one. For sequential computing the time = sum of all steps (EK CSN-2.A.5). For parallel computing the time = the sequential parts plus the longest parallel task (EK CSN-2.A.6). So if a large portion of work can run simultaneously, adding processors cuts runtime a lot—that’s why parallel solutions can handle bigger problems faster (EK CSN-2.B.2, EK CSN-2.B.4). But there’s a limit: the sequential portion still bounds speedup (EK CSN-2.B.5). The “speedup” metric is sequential time ÷ parallel time (EK CSN-2.A.7). For AP-style questions, you’ll often compare times or compute speedup, so practice those (see the Topic 4.3 study guide on Fiveable: https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild). For more practice problems, check https://library.fiveable.me/practice/ap-computer-science-principles.
I'm getting confused about when distributed computing is necessary vs just using a faster single computer - help?
Short answer: use a faster single computer when the whole problem fits and runs fast enough on one machine; use distributed computing when one machine can’t finish in a reasonable time or can’t hold the data. Why (CED terms): sequential runs steps one-by-one (EK CSN-2.A.1). Parallel splits a program into simultaneous tasks on one device (EK CSN-2.A.2) and gives speedup limited by the sequential portion (Amdahl’s idea, EK CSN-2.B.5). Distributed uses multiple devices (EK CSN-2.A.3) and is needed when storage or processing time exceed a single computer (EK CSN-2.B.3, EK CSN-2.B.4). Practical checks: - Data size > single machine’s memory/storage → distributed. - Single-machine runtime is days/weeks but tasks can be done independently → distributed. - Tasks are tightly dependent or mostly sequential → faster single CPU helps more. - Also weigh communication overhead and complexity (network latency, coordination). For AP prep, review Topic 4.3 in the Fiveable study guide (https://library.fiveable.me/ap-computer-science-principles/unit-4/parallel-distributed-computing/study-guide/wkNxn30shWZFeNUlcild) and practice problems (https://library.fiveable.me/practice/ap-computer-science-principles).