When talking about computer architectures (or systems in general where calculations are involved) and performance, a lot is done at design stage. In this article, I would like to talk about the usefulness of the Amdahl's law and its potential. The main topic here is designing or re-engineering systems in order to improve them.
A model to describe systems and improvements
Here are the main hypothesis. Let us consider to have a system made of several components. I will use the following formalism to concisely describe such a system: $S(\pi\sb{1},\pi\sb{2},\dots,\pi\sb{n})$, where $S$ is the system and $\pi\sb{i} \subseteq \Pi$ (where $\Pi$ is the space of components) represents a single component of it on a total of $n$ components.
The problem here is improving the system $S$ by acting on its parts $\pi\sb{i}$ (components). Of course I am keeping myself generic on purpose, in order to depict every possible situation. The system itself will be seen as a variable and its components as well. Each component is devoted to be part of an overall job performed by the system, every part is evaluated (or runs) only once. Given these assumption the system $S$ can be generalized as a collection of sequential tasks $\pi\sb{i}$, each task to be performed to reach the final goal.
Just some notes about involved quantities
The system $S$ we are dealing with is a generic problem described in terms of frequency and period (which includes the notion of time). Involved quantities will be the following:
- Arbitrary quantity: It is the quantity that describes the system. It depends by the system being described. Dimensionally speaking, this quantity will be described by the symbol: $[\xi]$.
- Time: The most important quantity. The system will be improved in terms of time. Dimensionally speaking it will be classically treated with expression: $[s]$.
- Frequency or speed: It is the quantity (dimensionally dependent on $\xi$) which describes the rapidity of the system or one of its components. This quantity will be dimensionally described by the following expression: $[\xi \cdot s\sp{-1}]$ (explicit notation for speed) or simply: $[s\sp{-1}]$.
Modelling improvement
But I mentioned the word improvement. How to model this? Actually our purpose, here, is improving single parts and see how the system, in general, improves.
Detailing components
I introduced components in a very general way, actually each part $\pi\sb{i}$ of the system represents a set of quantities for that component. In particular two variables. Given a certain component $\pi\sb{i} \in \Pi$, I introduce $\nu\sb{i} \in \mathbb{R}$ as the speed or frequency of that component, and $\tau\sb{i} \in \mathbb{R}$ as its running time.
Every ordered couple $\left( \nu\sb{i},\tau\sb{i} \right)$ describes each component. So it is natural to think about $\pi\sb{i}$ as that tuple. So, we have that $\Pi \subseteq \mathbb{R}\sp{2}$.
Making improvements
Consider that every component $\pi\sb{i}$ is assigned with a function $\phi\sb{i} : \Pi \mapsto \Pi$ that returns the same component with some changes. The following relation holds:
\begin{equation}
\phi\sb{i}(\pi\sb{i}) = \pi\sb{i}\sp{\ast}
\end{equation}
So, here we are. When a set of improvement functions $\phi\sb{i}$ is considered, by using these new components $\pi\sb{i}\sp{\ast}$, the same system will be: $S(\pi\sb{1}\sp{\ast},\pi\sb{2}\sp{\ast},\dots,\pi\sb{n}\sp{\ast})$. In a more concise way, having $\pi = (\pi\sb{1},\pi\sb{2},\dots,\pi\sb{n})$, $\phi = (\phi\sb{1},\phi\sb{2},\dots,\phi\sb{n})$, the original system $S(\pi)$ will be improved in the system $S(\phi(\pi)) = S(\pi\sp{\ast})$.
Important! Note also that improvement does not mean: $\pi\sb{i}\sp{\ast} \geq \pi\sb{i}$. Here I am intending operator $\geq$ in a different way, so the previous expression simply means: "Component $\pi\sb{i}\sp{\ast}$ is better or equal than component $\pi\sb{i}$". If, after modifying a component, it happens that the final speed is lower than the original one, we still talk about improvement (a negative one in this case).
Ratios is what matters most
Nobody says that we need to know the exact quantities during an improvement process. When improving, or better enhancing, a certain component $\pi\sb{i}$, we can always consider the following ratio:
\begin{equation}
\label{etaq}
\eta\sb{i} = \frac{\nu\sb{i}\sp{\ast}}{\nu\sb{i}} = \frac{\tau\sb{i}}{\tau\sb{i}\sp{\ast}}
\end{equation}
The previous ratio tells us how much the component has improved from its original state. Eta quantities in Equation \ref{etaq} will be referred to as: component enhancement ratios. Note that the second equality stands because the main assumption is that the quantity of work to be done by each component is the same across optimization.
If the initial system is given, so the same goes for its components, it is possible to compute the enhanced system $S(\pi\sp{\ast})$ just by using the ratios in Equation \ref{etaq}.
Partitioning the system
Considering that every component is part of a job, it is interesting to evaluate how much each component $\pi\sb{i}$ affects the overall system. This point is quite important because I am now talking about the importance (somehow) of each part of the system. So let us introduce weights: $\omega\sb{i} \in \Omega$ is component $\pi\sb{i}$'s weight and it represents the following ratio:
\begin{equation}
\label{weights}
\omega\sb{i} = \frac{\tau\sb{i}}{T} = \frac{\tau\sb{i}}{\sum\sb{j=1}\sp{n}\tau\sb{j}}
\end{equation}
So, considering the initial system, when running it, all components will run as well. The system will use a certain time $T$ to complete the job. What portion of $T$ does each component $\pi\sb{i}$ consume? The answer to this question is $\omega\sb{i}$. Weights do describe how much each part of the system affects it.
System performance
What about measuring system performance? So far, I just introduced a way to deal with performance for components. In fact, although I did not explicitly introduced those quantities as a performance measure, given a component $\pi\sb{i} = \left( \nu\sb{i},\tau\sb{i} \right)$, $\nu\sb{i}$ and $\tau\sb{i}$ (inverted order) can be performance measures. But focusing on single performances is not really our purpose, as, here, we consider a certain enhancement for each component, so we use ratios. The system as well will be provided with such a quantity.
System $S$'s performance can be measured in terms of time of execution or mean speed. So, given a system $S(\pi\sb{1},\pi\sb{2},\dots,\pi\sb{n})$, its execution time is:
\begin{equation}
\label{tautimes}
T \left[ S(\pi) \right] = \sum\sb{i=1}\sp{n} \tau\sb{i}
\end{equation}
While its mean speed is:
\begin{equation}
V \left[ S(\pi) \right] = \sum\sb{i=1}\sp{n} \nu\sb{i} \cdot \omega\sb{i}
\end{equation}
Concerning enhancement ratios, as anticipated before, considering a certain set of enhancement functions $\phi$, the system improvement ratio is:
\begin{equation}
\label{syseta}
H = \frac{V \left[ S(\pi\sp{\ast}) \right]}{V \left[ S(\pi) \right]} = \frac{T \left[ S(\pi) \right]}{T \left[ S(\pi\sp{\ast}) \right]}
\end{equation}
Theorem 1: Proving system improvement ratio equality
Equation \ref{syseta} states that it is possible to calculate the system enhancement ratio in a similar way as described for each component by Equation \ref{etaq}. The difference is that in this case, here, we use, for speed, the mean speed. In order to prove Equation \ref{syseta}, I am going to start from the first equality (mean speeds) and reach the second expression (the one involving times). Proving such equality is easy as it is possible to see below:
\begin{equation}
\frac{V \left[ S(\pi\sp{\ast}) \right]}{V \left[ S(\pi) \right]} = \frac{\sum\sb{i=1}\sp{n} \nu\sb{i}\sp{\ast} \cdot \omega\sb{i}\sp{\ast}}{\sum\sb{i=1}\sp{n} \nu\sb{i} \cdot \omega\sb{i}} = \frac{\sum\sb{i=1}\sp{n} \frac{\sigma\sb{i}}{\tau\sb{i}\sp{\ast}} \cdot \frac{\tau\sb{i}\sp{\ast}}{\sum\sb{i} \tau\sb{i}\sp{\ast}}}{\sum\sb{i=1}\sp{n} \frac{\sigma\sb{i}}{\tau\sb{i}} \cdot \frac{\tau\sb{i}}{\sum\sb{i} \tau\sb{i}}} = \frac{\sum\sb{i=1}\sp{n} \frac{\sigma\sb{i}}{\sum\sb{i} \tau\sb{i}\sp{\ast}}}{\sum\sb{i=1}\sp{n} \frac{\sigma\sb{i}}{\sum\sb{i} \tau\sb{i}}} = \frac{\sum\sb{i} \tau\sb{i}}{\sum\sb{i} \tau\sb{i}\sp{\ast}} = \frac{T \left[ S(\pi) \right]}{T \left[ S(\pi\sp{\ast}) \right]}\nonumber
\end{equation}
The previous calculations are based on the important and quite straightforward assumptions: $\nu\sb{i} = \frac{\sigma\sb{i}}{\tau\sb{i}}$, $\nu\sb{i}\sp{\ast} = \frac{\sigma\sb{i}}{\tau\sb{i}\sp{\ast}}$ (remember that, as I said before, the component is structurally the same, it is the speed that changes), $\omega\sb{i} = \frac{\tau\sb{i}}{\sum\sb{i} \tau\sb{i}}$ and $\omega\sb{i}\sp{\ast} = \frac{\tau\sb{i}\sp{\ast}}{\sum\sb{i} \tau\sb{i}\sp{\ast}}$. QED!
Amdahl's law
We are now ready to introduce Amdahl's law. So far, I introduced our system $S$ using its descriptive quantities: speeds and times of running. The point is that, after what I said in the previous part of this article, system $S$'s improvement can be described either by its components: $S(\pi\sb{1},\dots,\pi\sb{n},\pi\sb{1}\sp{\ast},\dots,\pi\sb{n}\sp{\ast})$, by its initial components and enhancement functions: $S(\pi\sb{1},\dots,\pi\sb{n},\phi\sb{1},\dots,\phi\sb{n})$; or either by enhancement ratios and weights: $S(\eta\sb{1},\dots,\eta\sb{n},\omega\sb{1},\dots,\omega\sb{n})$. Amdahl prefers using the last solution. So from now on I am going to focus on system $S$ and its improvement represented by the set of improvement ratios and weights: $S(\eta\sb{1},\dots,\eta\sb{n},\omega\sb{1},\dots,\omega\sb{n})$. Such a notation is very important because it lets us consider proportional quantities only, rather than exact values; let's say that it is a more succinct way to depict the system improvement.
I am going to introduce Amdahl's law as it is, then I will prove it. So, here we go. Considering a generic system $S$ described by its compact form $S(\eta\sb{1},\dots,\eta\sb{n},\omega\sb{1},\dots,\omega\sb{n})$ handling the system and its enhancement; then the system improvement ratio is:
\begin{equation}
\label{amdl}
H = \left( \sum\sb{i=1}\sp{n} \frac{\omega\sb{i}}{\eta\sb{i}} \right)\sp{-1}
\end{equation}
Theorem 2: Proving Amdahl's equation
In order to prove that Equation \ref{amdl} holds, we need to verify the following:
\begin{equation}
\label{amdver}
\frac{T \left[ S(\pi) \right]}{T \left[ S(\pi\sp{\ast}) \right]} = \left( \sum\sb{i=1}\sp{n} \frac{\omega\sb{i}}{\eta\sb{i}} \right)\sp{-1}
\end{equation}
We should also verify that the same happens also when considering mean speeds, but Theorem 1 has been proved true, so we only need to verify the aforementioned equation which involves times only (I chose times because there are less calculations in this case). I start by re-writing Equation \ref{amdver} and expanding the first member according to Equation \ref{tautimes}:
\begin{equation}
\label{thm2}
\frac{\sum\sb{i=1}\sp{n}\tau\sb{i}}{\sum\sb{i=1}\sp{n}\tau\sb{i}\sp{\ast}} = \left( \sum\sb{i=1}\sp{n} \frac{\omega\sb{i}}{\eta\sb{i}} \right)\sp{-1}
\end{equation}
Equation \ref{thm2} will be the target expression to prove. Now I will focus on the second member and expand it according to Equation \ref{weights} and Equation \ref{etaq}.
\begin{equation}
\left( \sum\sb{i=1}\sp{n} \frac{\omega\sb{i}}{\eta\sb{i}} \right)\sp{-1} = \left( \sum\sb{i=1}\sp{n} \frac{\tau\sb{i}}{\sum\sb{j=1}\sp{n}\tau\sb{j}} \cdot \frac{\tau\sb{i}\sp{\ast}}{\tau\sb{i}} \right)\sp{-1} = \left( \sum\sb{i=1}\sp{n} \frac{\tau\sb{i}\sp{\ast}}{\sum\sb{j=1}\sp{n}\tau\sb{j}}\right)\sp{-1} \nonumber
\end{equation}
Extracting denominator from sum and after applying the inversion, we reach this expression:
\begin{equation}
\left( \sum\sb{i=1}\sp{n} \frac{\tau\sb{i}\sp{\ast}}{\sum\sb{j=1}\sp{n}\tau\sb{j}}\right)\sp{-1} = \left( \frac{\sum\sb{i=1}\sp{n}\tau\sb{i}\sp{\ast}}{\sum\sb{i=1}\sp{n}\tau\sb{i}}\right)\sp{-1} = \frac{\sum\sb{i=1}\sp{n}\tau\sb{i}}{\sum\sb{i=1}\sp{n}\tau\sb{i}\sp{\ast}} = \frac{T \left[ S(\pi) \right]}{T \left[ S(\pi\sp{\ast}) \right]} \nonumber
\end{equation}
Which proves Equation \ref{thm2}. QED!
Amdahl's law's special case: single improvement
When the enhanced component is just one, it does not really matters how many components the system is composed of. When single improvement occurs on a system $S(\pi\sb{1},\pi\sb{2},\dots,\pi\sb{n})$, let's say that component $\pi\sb{1}$ is the enhanced one (without generality loss), then all enhancement ratios are: $\eta\sb{i} = 1, \forall i = 2 \dots n$. So Equation \ref{amdl} is reshaped as follows:
\begin{equation}
H = \left( \frac{\omega\sb{1}}{\eta\sb{1}} + \frac{\omega\sb{2}}{\eta\sb{2}} + \dots + \frac{\omega\sb{n}}{\eta\sb{n}} \right)\sp{-1} = \left( \omega\sb{2} + \omega\sb{3} + \dots + \omega\sb{n} + \frac{\omega\sb{1}}{\eta\sb{1}} \right)\sp{-1} \nonumber
\end{equation}
Considering that, obviously: $\sum\sb{i=1}\sp{n}\omega\sb{i} = 1$, we have that, as said before, all components other than $\pi\sb{1}$ do not matter. The previous expression, becomes the Amdahl's law handling single improvement:
\begin{equation}
\label{amdlsngli}
H = \left( 1 - \omega\sb{1} + \frac{\omega\sb{1}}{\eta\sb{1}} \right)\sp{-1}
\end{equation}
Equation \ref{amdlsngli} is the most common and famous form of the Amdahl's law.
Why Amdahl's law is useful
There is a very large variety of systems whose improvement can be described by the approach written so far. The point is that Amdahl's approach using only component improvement ratios $\eta\sb{i}$ and weights $\omega\sb{i}$ is the easiest one. Why? Because it is the most generic. Often we do not need all exact quantities in order to evaluate the system improvement. In order to evaluate the enhancement of a generic system $S$, we only need to now how much each component affects the entire system and how much each component has been improved. Such data can be collected just by observing the system rather than knowing all facts about it.
More importantly, it is also possible to have very generic discussions like: "What if I improved this part of my system by a certain factor considering that this component affects a certain percentage of my system?". All we need to know about the system is just its complete partition scheme, represented by the set of all weights $\omega\sb{i}$.
Example 1: Freeway
A freeway consists of 3 parts:
- Track 1: An initial track going through the mountains. It has been observed that, generally, all cars do spend the 30% of the total travel time here.
- Track 2: A bridge. The bridge is a special one because it is a lift bridge. When a ship needs to pass, the bridge requires some time to lift and then going back in its initial position. Because of this, cars usually spend the 45% of their travel time on this part of the freeway.
- Track 3: The final part is quite straight with no particular singularities. Cars spend the remaining 25% of the travel time here.
It looks quite logic to improve the bridge, so we manage to make the bridge lifting faster, so much that cars will be two times faster than before. System is: $S(\eta\sb{1},\eta\sb{2},\eta\sb{3},\omega\sb{1},\omega\sb{2},\omega\sb{3})$ where $\omega\sb{1} = 0.3$, $\omega\sb{2} = 0.45$, $\omega\sb{3} = 0.25$ and we also have: $\eta\sb{1} = 1$ (no improvement for part 1), $\eta\sb{2} = 2$ (second track is improved twice the speed, half the time) and $\eta\sb{3} = 1$ (last track is not enhanced). By applying Amdahl's law (Equation \ref{amdl}) we get:
\begin{equation}
H = \left( \frac{\omega\sb{1}}{\eta\sb{1}} + \frac{\omega\sb{2}}{\eta\sb{2}} + \frac{\omega\sb{3}}{\eta\sb{3}} \right)\sp{-1} = \left( 0.3 + \frac{0.45}{2} + 0.25 \right)\sp{-1} = \left( 0.55 + 0.225 \right)\sp{-1} = 0.775\sp{-1} \simeq 1.29 \nonumber
\end{equation}
The system has been globally improved by 129% about.
Example 2: Task management
Amdahl's law can also be applied in abstract contexts. Consider, for example, $n$ different tasks to be performed. It can be a sequence of operations performed by a program, it can be a simple list of things to do written on post-it or it can also be a planning arrangement for a certain event. In our case, I will consider the example involving a program that will execute a certain number of jobs (tasks); sorry but I am also a Computer Scientist after all. Let us consider $n=5$ jobs with the following characteristics:
- Job 1: It is performed in 30 ms. After enhancement this job executes in 10 ms.
- Job 2: It is performed in 50 ms. After enhancement this job executes in 10 ms.
- Job 3: It is performed in 150 ms. After enhancement this job executes in 140 ms.
- Job 4: It is performed in 10 ms. This job is not enhanced.
- Job 5: It is performed in 20 ms. After enhancement this job executes in 10 ms.
As we can see almost all tasks have been improved in order to make them all run at 10 ms. Job 3 has been improved by a very little percentage by the way. Let's now calculate ratios and weights. Before enhancement the total running time is $T = T(S) = 30 + 50 + 150 + 10 + 20 = 260$. We have that: $\omega\sb{1} = \frac{30}{260} \simeq 0.115$, $\omega\sb{2} = \frac{50}{260} \simeq 0.192$, $\omega\sb{3} = \frac{150}{260} \simeq 0.576$, $\omega\sb{4} = \frac{10}{260} \simeq 0.038$ and $\omega\sb{5} = 1 - 0.115 + 0.192 + 0.576 + 0.038 = 0.079$. When calculating improvement ratios, we get: $\eta\sb{1}=\frac{30}{10} = 3$, $\eta\sb{2}=\frac{50}{10} = 5$, $\eta\sb{3}=\frac{150}{140} \simeq 1.07$, $\eta\sb{4}=1$ (no improvement) and $\eta\sb{5}=\frac{20}{10} = 2$. We can calculate the overall system improvement:
\begin{equation}
H = \left( \frac{\omega\sb{1}}{\eta\sb{1}} + \dots + \frac{\omega\sb{5}}{\eta\sb{5}}\right)\sp{-1} = \left( \frac{0.115}{3} + \frac{0.192}{5} + \frac{0.576}{1.07} + 0.038 + \frac{0.079}{2} \right)\sp{-1} = \dots = 0.691\sp{-1} \simeq 1.45 \nonumber
\end{equation}
The system has globally improved by 145%. Which means that after spending so much effort improving more than twice almost all components, we just get a total enhancement that cannot even reach 50% of the initial system. This point is important to note because it underlines the effort we had to put compared with the final result we got.
To better understand this point, let us consider another enhancement, I will always refer to the same initial system, but I will only improve, this time, the third component only: its running time was 150 ms, after this new enhancement it will run in 70 ms, so we have $\eta\sb{3} = \frac{150}{70} = 2.14$. I am making the system 80 ms faster by just acting on one component only, but the difference here is that I will obtain the same system enhancement by just improving one component only by a little more than twice (instead acting on more components and improving them more than twice). Making calculations as before we get:
\begin{equation}
H = \left( \frac{\omega\sb{1}}{\eta\sb{1}} + \dots + \frac{\omega\sb{5}}{\eta\sb{5}}\right)\sp{-1} = \left( 0.115 + 0.192 + \frac{0.576}{2.14} + 0.038 + 0.079 \right)\sp{-1} = \dots \simeq 1.45 \nonumber
\end{equation}
As anticipated before, the same imrovement is experienced by the system, but this time the effort to reach such an enhancement is much less than before.
Example 3: CPU architecture
This example is a very classic one (that's why I am writing it as the last). Actually it is the application for which, at the time when Amdahl proposed its theory, Equation \ref{amdl} was designed. I am talking about computer architectures.
So, let us consider a very simplified microprocessor architectural system composed by an elaboration unit and a simple I/O unit. Current trends do show that modern architectures behave like this:
- Input and Output: Generally it takes the 10% of the global elaboration time.
- Elaboration: Pure elaboration takes the remaining 90% of the time.
Please note that these statistics do refer to programs that use CPU a lot compared to I/O time. These programs have very few instructions were external devices access is required.
So far we have behaved in the same way: we have improved always the component whose weight was the highest. Considering that we have $\omega\sb{1} = 0.1$ and $\omega\sb{2} = 0.9$, we want to enhance CPU twice, so: $\eta\sb{2} = 2$ while $\eta\sb{1} = 1$. Considering that we have a single improvement, Equation \ref{amdlsngli}:
\begin{equation}
H = \left( 1 - \omega\sb{2} + \frac{\omega\sb{2}}{\eta\sb{2}}\right)\sp{-1} = \left( 1 - 0.9 + \frac{0.9}{2}\right)\sp{-1} = \left( 0.1 + 0.45\right)\sp{-1} = 0.55\sp{-1} = 1.81 \nonumber
\end{equation}
The architecture has been improved by almost twice.
From Amdahl's equation to Amdahl's law
In the past three examples we could see Equation \ref{amdl}'s application. The contexts where the equation can be applied are several and involved calculations are quite easy. Actually, Equation \ref{amdl}, named after its creator Amdahl, also causes a principle or law to be formulated. This law is a direct consequence of Amdahl's equation and it states the following:
Make the common case fast.
This principle states that, given a certain system $S$, its components $\pi\sb{i} \in \Pi$ and one improvement ratio $\eta\sb{x}$ to be applied to a certain component, one should choose to apply such a ratio to the part of the system whose weight is the highest. This will ensure the highest possible system enhancement. Actually it is the rule I applied in some of the examples I made before, let's try now to understand, mathematically, why Amdahl's law is true, by proving the aforementioned statement.
Proving Amdahl's law
Verifying the law is quite straightforward. Let $\omega\sb{1}$ and $\omega\sb{2}$ be the weights of two arbitrary components of the system so that: $\omega\sb{1} > \omega\sb{2}$. Let us consider a certain improvement ratio $\eta\sb{x}$ to be applied once to $\pi\sb{1}$ and once to $\pi\sb{2}$ (in separate times); only one component at a time is enhanced, all remaining ones are left unchanged. Let $H\sb{1}$ be the system enhancement when $\eta\sb{x}$ is applied to $\pi\sb{1}$, let also $H\sb{2}$ be the system enhancement when $\eta\sb{x}$ is applied to $\pi\sb{2}$. If the law is true, then we should have that: $H\sb{1} > H\sb{2}$. Let us start from this hypothesis and perform calculations, I expect not to reach an absurd in this case:
\begin{equation}
H\sb{1} > H\sb{2} \implies \left( 1 - \omega\sb{1} + \frac{\omega\sb{1}}{\eta\sb{x}} \right)\sp{-1} > \left( 1 - \omega\sb{2} + \frac{\omega\sb{2}}{\eta\sb{x}} \right)\sp{-1} \implies 1 - \omega\sb{1} + \frac{\omega\sb{1}}{\eta\sb{x}} < 1 - \omega\sb{2} + \frac{\omega\sb{2}}{\eta\sb{x}} \nonumber
\end{equation}
By rearranging quantities we get:
\begin{equation}
- \omega\sb{1} + \frac{\omega\sb{1}}{\eta\sb{x}} < - \omega\sb{2} + \frac{\omega\sb{2}}{\eta\sb{x}} \implies - \eta\sb{x} \cdot \omega\sb{1} + \omega\sb{1} < - \eta\sb{x} \cdot \omega\sb{2} + \omega\sb{2} \implies ( 1 - \eta\sb{x} ) \cdot \omega\sb{1} < ( 1 - \eta\sb{x} ) \cdot \omega\sb{2} \nonumber
\end{equation}
Considering that $\eta\sb{x} > 1$ because we are considering an improvement (a positive one) of the component, by dividing both members of the last inequality by $1 - \eta\sb{x} < 1$, we get: $\omega\sb{1} > \omega\sb{2}$ which is the original hypothesis. QED!
Amdahl's principle
The aforementioned law is useful because it points out one of the most important consequences of Equation \ref{amdl}: enhancements should be made on the most common components. Common, in this case, is to be intended as: "The component which affects the system the most".
Actually, Amdahl's law's purpose is not calculating improvements
After many lines of text and examples where I have tried to convince you that Amdahl's law can be used to calculate the improvement of a system after improving its components, now I am turning the table trying to say something different. Well, this is actually true but only by 50%. Because the point, here, is just focusing on the real power of Amdahl's equation, which is not calculating improvements (although this is one of its powers). So what have I been hiding so far? I want to consider the following problem:
Considering a certain system $S(\pi\sb{1},\dots,\pi\sb{k},\pi\sb{k+1},\dots,\pi\sb{n})$, we want to separate its components in two groups: a group of $\pi\sb{1}, \pi\sb{2} , \dots , \pi\sb{k}$ improvable components and a group of $\pi\sb{k+1}, \pi\sb{k+2} , \dots , \pi\sb{n}$ non-improvable ones.
Improvable components are those ones that can, theoretically, be enhanced with no limits, while the non-improvable ones are those that cannot be tuned (some sort of physical limitation of the system).
Considering such a condition, what is the highest possible enhancement that the system $S$ can experience?
The separation of components does inspire a classification:
- Improvable components: These components are actually those ones where it is possible to act on in the context of the considered enhancement. When a certain system is given, its improvement will be possible, for the context in exam, by touching some of its parts, while there will be other elements where no tuning will be possible or feasible. When talking about improvable components, I mean those components $\pi\sb{i}, \forall i = 1 \dots k$ where the following condition simply holds: $\eta\sb{i} > 1$.
- Non-improvable components: On the other hand, when talking about non improvable components, I mean those elements of $S$: $\pi\sb{i}, \forall i = k+1 \dots n$ where the following condition holds: $\eta\sb{i} = 1$.
Maximum improvement
Such a classification like the one described before generally occurs in all systems, and the question posed before is a really valid one; why? Because it points out how much proper, or not, is going through such an improvement. I am now going to introduce a new concept called: Maximum improvement, which refers to the system's one. So, under the hypothesis introduced before, let us improve all improvable components by infinite and see what happens.
We have, of course, that $\eta\sb{i} > 1, \forall i = 1 \dots k$ and $\eta\sb{i} = 1, \forall i = k+1 \dots n$. So, the maximum improvement is the system improvement $H$ considered when: $\eta\sb{i} \rightarrow +\infty, \forall i = 1 \dots k$. So we have that:
\begin{equation}
H\sb{M} = \lim\sb{\eta\sb{i} \rightarrow +\infty} \left( \sum\sb{i=1}\sp{n} \frac{\omega\sb{i}}{\eta\sb{i}} \right)\sp{-1} = \lim\sb{\eta\sb{i} \rightarrow +\infty} \left( \sum\sb{i=1}\sp{k} \frac{\omega\sb{i}}{\eta\sb{i}} + \sum\sb{j=k+1}\sp{n} \frac{\omega\sb{j}}{\eta\sb{j}} \right)\sp{-1} = \lim\sb{\eta\sb{i} \rightarrow +\infty} \left( \sum\sb{i=1}\sp{k} \frac{\omega\sb{i}}{\eta\sb{i}} + \sum\sb{j=k+1}\sp{n} \omega\sb{j} \right)\sp{-1} \nonumber
\end{equation}
Applying limit, the previous expression becomes:
\begin{equation}
H\sb{M} = \lim\sb{\eta\sb{i} \rightarrow +\infty} \left( \sum\sb{i=1}\sp{k} \frac{\omega\sb{i}}{\eta\sb{i}} + \sum\sb{j=k+1}\sp{n} \omega\sb{j} \right)\sp{-1} = \left( 0 + \sum\sb{i=k+1}\sp{n} \omega\sb{i} \right)\sp{-1} = \left( \sum\sb{i=k+1}\sp{n} \omega\sb{i} \right)\sp{-1} \nonumber
\end{equation}
By aliasing the percentage of system made of non-improvable components as follows: $W\sb{\text{n.i.}} = \sum\sb{i=k+1}\sp{n} \omega\sb{i}$, then we can simply write the maximum improvement as follows:
\begin{equation}
\label{maximp}
H\sb{M} = W\sb{\text{n.i.}}\sp{-1}
\end{equation}
Equation \ref{maximp} is very important. As we can see, the higher is the percentage of non-improvable components, the lower is the maximum improvement experienced by the system. This allows us to find an upper bound to system improvement which is:
\begin{equation}
H \leq H\sb{M}
\end{equation}
An application of maximum improvement: computer architectures
To understand better what said in the last few lines, I will write a very classic example. In the last years CPUs have been improved dramatically in order to be a lot faster than their predecessors. Actually it is incredible, an exponential growth that was able to make our systems faster every year. However, there is something to say about this. Computer architectures are made of many components, here I will only focus on two of them: the CPU (of course) and I/O: the Input and Output system which is associated with all those peripherals like disk, CD driver and other devices. As we all know, when running some program, total execution time heavily depends on what kind of instructions are to be performed. CPUs are fast, so if such a program only involved mathematical calculations, no problem, but if a file were to be accessed, than we would experience slower trends.
Of course, a program speed depends by its needs. There are all sorts of programs out there, but in this case the classification will involve CPU programs and I/O programs. The former are those programs that generally use CPU a lot, while the latter are those applications handling much I/O (slow programs actually). So, let us say that CPU applications generally use the 90% of their execution time in CPU instructions, while the remaining 10% is spent in I/O operations. On the other hand, let us consider that I/O programs have the opposite trend: 90% of time spent in I/O operations and 10% in simple CPU instructions.
The problem is that, while CPUs have been improved dramatically in these years, I/O did not really experience such enhancement. I/O is really slow to enhance. So I will consider I/O as the non-improvable part of our system. The maximum improvement for CPU program is: $H\sb{M} = 0.1\sp{-1} = 10$, for I/O programs: $H\sb{M} = 0.9\sp{-1} = 1.11$.
It is obvious that CPU programs can be improved more, but the point is not this. The point is that non-improvable parts, in a system, will always represent a bottleneck. No matter how much their components are enhanced, the non-improvable percentage of the system will always represent an hindrance for the system, so, talking about the future, enhancing improvable components is ok, but those parts that are difficult to improve, they should also be considered. In the case of this example, current trends are those ones I described here: it is hard to improve I/O, but, instead of making CPUs faster and faster every year, we should pay attention making I/O faster as well.
Final considerations
In this article I just wanted to describe Andahl's law in a more detailed analysis. Generally in Computer Science courses or Engineering lectures, Amdahl's equation is introduced in a very simplistic way, which is good, but, on the other hand, such an approach will not, in my opinion, show the real power of this theory. I hope this article was useful to better understand such important topics like system optimization and enhancement; although Amdahl's theory is not the only one approach to face such problems, it sure represents a fast and good direction when trying to reason about possible choices of enhancement (also) in everyday life.