How closely does the real speedup of multithreaded matrix multiplication match the predicted speedup by Amdahl's Law?
This project compares the actual measured speedup of a Java multithreaded matrix multiplication program against the predicted speedup from Amdahl's Law.
The experiment uses 1024 x 1024 square matrices and tests several thread counts:
1, 2, 4, 6, 8, 10, 12
The main goal is to answer this question:
Does adding more threads continue to improve performance, and how close is the real speedup to the theoretical speedup predicted by Amdahl's Law?
The program performs standard matrix multiplication.
For two matrices A and B, each value in the result matrix C is calculated as:
C[i][j] = sum(A[i][k] * B[k][j])
This problem is naturally parallelizable because different rows of the result matrix can be computed independently.
In this project:
- The sequential version computes all rows using one thread.
- The parallel version divides the result matrix into row blocks.
- Each worker thread computes a different block of rows.
- The main thread waits until all worker tasks finish.
The multithreaded version uses Java's ExecutorService with a fixed-size thread pool.
The general process is:
1. Create the result matrix.
2. Create a fixed thread pool with N threads.
3. Divide the result matrix rows into N row blocks.
4. Submit each row block as a task.
5. Each task computes its assigned rows.
6. Shut down the executor.
7. Wait for all tasks to finish.
8. Return the completed result matrix.
The measured runtime includes the real cost of this implementation, including executor creation, task submission, worker execution, shutdown, and waiting for termination.
That means this project measures practical speedup, not an idealized overhead-free model.
Amdahl's Law predicts the maximum possible speedup of a program when only part of the program can be parallelized.
S(N) = 1 / ((1 - P) + (P / N))
Where:
| Symbol | Meaning |
|---|---|
S(N) |
predicted speedup using N threads |
N |
number of threads/processors |
P |
parallelizable fraction of the program |
1 - P |
serial fraction of the program |
The key idea is that the serial part of the program limits total speedup, even when more processors or threads are added.
Instead of guessing the parallel fraction, this project estimates it from the measured runtime data using the Karp-Flatt metric.
e(N) = ((1 / S(N)) - (1 / N)) / (1 - (1 / N))
Where:
| Symbol | Meaning |
|---|---|
e(N) |
effective serial fraction |
S(N) |
measured speedup |
N |
number of threads |
This is useful because it captures real-world overhead, not just the theoretical serial part of the algorithm.
The practical parallel fraction is then estimated as:
P = 1 - e(N)
The Java program was run multiple times for each thread count. The runtimes were saved in:
results/data/MultiThreadedResults.txt
The data was then parsed and analyzed in a Jupyter Notebook.
The first two one-thread measurements were removed because they were startup outliers compared to the rest of the one-thread results.
| Threads | Average Runtime (ms) | Actual Speedup | Karp-Flatt e | Estimated P | Amdahl Predicted Speedup |
|---|---|---|---|---|---|
| 1 | 1248.472182 | 1.000000 | N/A | N/A | 1.000000 |
| 2 | 674.536882 | 1.850858 | 0.080580 | 0.919420 | 1.648546 |
| 4 | 398.573013 | 3.132355 | 0.092331 | 0.907669 | 2.439661 |
| 6 | 358.215021 | 3.485259 | 0.144307 | 0.855693 | 2.904229 |
| 8 | 391.772814 | 3.186725 | 0.215773 | 0.784227 | 3.209843 |
| 10 | 533.705776 | 2.339252 | 0.363875 | 0.636125 | 3.426165 |
| 12 | 541.529666 | 2.305455 | 0.382277 | 0.617723 | 3.587341 |
The runtime improved from 1 thread to 6 threads. The best average runtime was:
6 threads = 358.215 ms
After 6 threads, runtime increased again. This shows that adding more threads eventually introduced more overhead than benefit.
The actual speedup improved up to 6 threads:
1 thread = 1.00x
2 threads = 1.85x
4 threads = 3.13x
6 threads = 3.49x
The best actual speedup was:
6 threads = 3.49x speedup
After 6 threads, the actual speedup decreased:
8 threads = 3.19x
10 threads = 2.34x
12 threads = 2.31x
This shows that Amdahl's Law gives a useful theoretical trend, but the real Java implementation does not continue scaling at higher thread counts because practical overhead becomes significant.
The effective serial fraction increased as more threads were added:
2 threads = 0.080580
4 threads = 0.092331
6 threads = 0.144307
8 threads = 0.215773
10 threads = 0.363875
12 threads = 0.382277
This means the program became less efficient at higher thread counts. The matrix multiplication work itself is still highly parallel, but the real implementation experiences overhead from thread management, task scheduling, memory effects, and hardware resource competition.
This project shows that multithreading improved matrix multiplication performance, but only up to a point.
The best result occurred at 6 threads:
Best runtime: 358.215 ms
Best speedup: 3.49x
After 6 threads, adding more threads made performance worse. This demonstrates that:
more threads does not always mean faster runtime
The results support the main idea behind Amdahl's Law: total speedup is limited by the portion of runtime that does not scale perfectly in parallel.
They also show that real implementation overhead matters. Thread creation, task submission, executor shutdown, waiting, scheduling, cache behavior, and memory bandwidth can all reduce actual speedup.
This experiment has a few limitations:
- Only one matrix size was tested:
1024 x 1024. - The experiment was run on one machine.
- Java runtime behavior and JVM warmup can affect timing.
- Executor creation and shutdown were included in every timed run.
- Hardware limits such as CPU cores, cache, and memory bandwidth can affect results.
- The first two one-thread measurements were removed as startup outliers.
These limitations do not invalidate the results. They explain why real measured speedup can differ from ideal predicted speedup.
Possible improvements include:
- Test multiple matrix sizes.
- Add a warmup phase before timing.
- Compare executor reuse vs creating a new executor each run.
- Compare
ExecutorService, manual threads, and Fork/Join. - Measure CPU utilization.
- Measure memory/cache effects.
- Run the experiment on different machines.
- Increase the number of trials.
General workflow:
1. Run the Java matrix multiplication benchmark.
2. Save runtimes to MultiThreadedResults.txt.
3. Open the Jupyter Notebook.
4. Parse the runtime file.
5. Compute average runtime for each thread count.
6. Compute actual speedup.
7. Compute Karp-Flatt effective serial fraction.
8. Estimate practical parallel fraction.
9. Compute Amdahl predicted speedup.
10. Generate the plots.
- Amdahl, G. M. (1967). Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities. AFIPS Conference Proceedings.
- Karp, A. H., & Flatt, H. P. (1990). Measuring Parallel Processor Performance. Communications of the ACM.
- Oracle Java Documentation. Executors and ExecutorService.
For 1024 x 1024 matrix multiplication, the Java multithreaded implementation achieved a clear speedup over the single-threaded version.
The best result was:
6 threads: 3.49x actual speedup
However, performance decreased when using 8, 10, and 12 threads. This shows that practical speedup depends not only on how parallel the algorithm is, but also on how efficiently the implementation manages threads and system resources.