atino.name (the blog of Andrea Tino)
Andry
Welcome to my blog   

Hello everyone! This is my blog. According to my interests, you'll find here many topics and arguments I like to talk about. All entries are organized using tags (labels) so you can easily move through them. I am sorry but I cannot yet provide you a search engine (this is a first-basic version of my web site, things are going to get better in time).

Because of security reasons I cannot let everyone post comments here, you need to be recognized by the system. Everyone registered has a username and a password, please use those couple of credentials (whenever you have any) to post comments. To get an account and start posting (if don't have any), follow instructions here.

Published on: Wednesday 24th October 2012 at 22:20, Last modified on: Wednesday 24th October 2012 at 22:20, Number of views: 0
先生へ、長沼学校とヴルカヌスの十二月のプレゼンテーション - 先生に届け

このポストは私が日本語を勉強した時の先生へです。では:谷津先生、小山先生、宮本先生、石川先生、加賀谷先生、さとう先生、西村先生に届けます。そして、しほ・きたざわさんにも届けたいんです。

じゃ、やっぱり遅れたようですね。今は2012年十月です、去年先生に約束をしたんですけど、ちょっと守っていません。何の約束?えと、私のプレゼンテーションをアップロードしてあげる約束でした。けれども、今守りたいんですから、やっと2011十二月のプレゼンテーションをアップロード出来たんですよ!よかった!先生、遅れてしまって、ごめんなさい。

プレゼンテーションについて

まだこのプレゼンテーションを覚えていますか。アニメーションだったんですから、先生が覚えていると思います。タイトルは「フィリアス・フォッグのような八日間東京一周」でした。思い出せましたか?。ハイ!それはそうですよ!私のプレゼンテーションは先生をちょっとびっくりさせたんですよ!けれども楽しかったと思います。聞いた時に、先生に「楽しい」と言われました。じゃ、それを信じます!

プレゼンテーションはあの人気がある小説についてですよ。「Jules Verne」が書いた小説です。けれども、今解説をあげません。プレゼンテーションの時に、私の話が紙に書いてありましたね、覚えていますか。そうですよ、プレゼンテーションの前に、先生はそれを書くのを手伝ってくれました。私はその話をこのポストに書きますから、解説がもう一つ必要はありません。

プレゼンテーションを見るために

プレゼンテーションをアップロードしたところです。リンクはこれです:Presentation SWF format (requires Adobe Flash Player 10+)

プレゼンテーションの話

プレゼンテーションの時にスライドを読みながら話すのがきらいんですから、別な話を書いた。スライドが各自の話が以下に書きます。

イントロダクションのスライド

話は以下のでした:

皆さんの中で、だれかフィリアス・フォッグを知っていますか。 ジュール・ヴェルネが書いた小説のキャラクターです。 むかし、長い旅行をしました。世界中の旅行でした。80日間かかりましたね。 これから、私は皆さんに新しい小説をお話しします。ジュール・ヴェルネの小説をアレンジしたいと思っています。 メインキャラクターはフィリアスです、けれども世界の旅行じゃありません、東京です。そして80日間はちょっと長そうなので、8日間だけです。 では、始めましょう。

一つ目のスライド

話は以下のでした:

一日目はとても大切な日です。フィリアスたちは日本語を習わなければなりません。どこで日本語を勉強すればいいでしょうか。もちろん、学校で。 ですから、フィリアスたちは長沼日本語学校へ行って、たくさん日本語を勉強して、上手になります。 一日間だけでは十分じゃありませんね。でも、これは私の小説ですから、出来ますよ。

二つ目のスライド

話は以下のでした:

二日目に、フィリアスたちは皇居を見に行きます。日本人に大切な所ですね。 フィリアスは日本のれきしについてたくさん習います。 それに、皇居の回りを走る人が多いですから、フィリアスも走りたいと思います。その時に、日本人の友達が出来ます。

三つ目のスライド

話は以下のでした:

三日目はお台場へ行きます。見る所がたくさんあって、とても有名な場所です。 お台場はベイエリアにあって、皆は水に入ります。 フィリアスたちは「自由の女神」があって、ちょっとびっくりします。 この日、フィリアスは新しい場所を見るし、日本人と話すし、たくさんのことを習います。

四つ目のスライド

話は以下のでした:

四日目は日本の文化の日です。落語の日です。 日本人の友達がフィリアスたちを落語のイベントにさそいます。でも、フィリアスたちは落語について何も知りません。 けれども、大丈夫です。「かつら・かいし」は落語を見せて、落語について教えてくれます。 フィリアスたちは落語を習って、日本の文化をもっとしります。

五つ目のスライド

話は以下のでした:

フィリアはまだ一度も神社を見た事が無いので、日本人の友達が浅草寺を案内してくれます。 浅草寺は本当に大きいですね。フィリアたちは神社を見たり、ちょっとおみやげを買ったりします。 この日は神社を案内してもらうだけじゃありません。フィリアスは日本の文化としゅうかんを習います。

六つ目のスライド

話は以下のでした:

六日目に、フィリアスたちは囲碁を習います。日本で囲碁はとても有名なゲームです。 フィリアスたちはチェスが出来ますが、囲碁はあまり出来ません。 ヨーロッパで「ヒカルの碁」と言うアニメを見ました。 フィリアスは、帰る時、囲碁のチャンピオンになりたいと思います。

七つ目のスライド

話は以下のでした:

この日、フィリアスたちは明治神宮へ行きます。 公園に遊びに行ってから、弓道の道場を見に行きます。フィリアスはヨーロッパで子どもの時に、アーチェリーをしたので、弓道が面白いと思います。 午後は明治神宮で日本の結婚式を見ます。日本のはヨーロッパのと違いますが、面白そうです。

八つ目のスライド

話は以下のでした:

皆さん、これで最後の日になりました。 けれども、もう分かりましたね。 じつは、これは小説じゃありません。私が本当にけいけんことです。 四ヶ月は速く過ぎました。けれども、フィリアスの旅行はまだ続きますよ。皆さんの旅行もまだ続きますね。 ですから、皆さんは想像(イマジネーション)を使って、最後の日思い描いて(イマジン)、最後のページを書いて下さい。 ありがとうございました。

気持ち

プレゼンテーションの日に、私は本当に緊張でした。皆が自分の目の前にいて、最初何も言えない見たかったんですけど、後少し自信があるようになりました。「プレゼンテーションがうまくなってよかった」と思いました。今ではそのプレゼンテーションを見ると、びっりします。四ヶ月だけで、日本語がそんなに上手なるのをまだ信じていませんが、先生が手伝ってくれましたので、それは当たり前でしょう。

じゃ先生もう一度、心からありがとう!

Comments
Please, before posting, read carefully the How To guide.
Username:Passphrase:(0 chars)
Published on: Tuesday 18th September 2012 at 23:13, Last modified on: Tuesday 18th September 2012 at 23:13, Number of views: 0
Systems and performance improvement: introducing Amdahl's law

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:

  1. 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.
  2. 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.
  3. 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:

  1. Job 1: It is performed in 30 ms. After enhancement this job executes in 10 ms.
  2. Job 2: It is performed in 50 ms. After enhancement this job executes in 10 ms.
  3. Job 3: It is performed in 150 ms. After enhancement this job executes in 140 ms.
  4. Job 4: It is performed in 10 ms. This job is not enhanced.
  5. 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:

  1. Input and Output: Generally it takes the 10% of the global elaboration time.
  2. 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.

Comments
Please, before posting, read carefully the How To guide.
Username:Passphrase:(0 chars)
Published on: Saturday 1st September 2012 at 4:0, Last modified on: Saturday 1st September 2012 at 4:0, Number of views: 0
Ciao e また今度 Emi-yan - Trecentosessantaseiesimo giorno

Nel post di ieri avevo erroneamente detto che quello sarebbe stato l'ultima trasmissione dal Giappone. Però non ho ancora raccontato come poi è finita ieri sera con Emi-yan. Per essere precisi, comunque, diciamo che sono in fallo al 50% visto che mi trovo in aeroporto davanti al mio gate di imbarco, quindi in zona internazionale. Questo ultimo post lo sto scrivendo in terra di nessuno praticamente.

Il tempo qui a Narita è come lo scorso 1 Settembre: piove ed è nuvoloso. Se penso che in questo momento stano anche atterrando i nuovi studenti Vulcanus, beh inizio a diventare davvero nostalgico.

Serata... umida

Ieri sera ho portato Emi-yan allo spettacolo acquatico di Tokyo Middle Town (東京ミドル・タウン). E' stato molto bello e anche se per me era la seconda volta, hanno fatto una performance non proprio identica a quella precedente. Emi-yan non se lo aspettava e appena i cannoni hanno iniziato a sparare acqua in alto fra spruzzi e schizzi lei ha iniziato a maledirmi. Ma si è divertita in fondo. A ogni cannonata di acqua verso il cielo si sentivano bambini strillare e si vedevano persone iniziare a scappare un poco dappertutto. E' stato, di nuovo, molto bello, la serata inoltre era particolarmente fresca e un bel venticello miticava il caldo. Il cielo era limpidissimo ed era pure luna piena (in Giapponese: 満月 ovvero: Mangetsu che letteralmente significa: luna riempita).

Lo spettacolo è durato giusto 15 minuti, ma sono stati intensi. Alla fine siamo stati a mangiare in una Izakaya (居酒屋, ovvero i bar tipici Giapponesi dove si va in genere per bere ma anche per mangiare, una sottospecie di pub alla Giapponese). Emi-yan, che era tornata proprio qualche ora prima da un viaggio di lavoro nel Kansai, mi ha portato degli omiyage (お土産, ovvero i regali che si portano alle persone dopo un viaggio): una maglietta, dei calzini con su scritto qualosa nel dialetto di Osaka (大阪弁: l'Osaka-ben) e, cosa più bella, delle carte con le espressioni comuni più famose dell'Osaka-ben. Sono sempre stato curioso riguardo al Kansai-ben (関西弁: il dialetto parlato in genere nel Kansai con le dovute variazioni nelle varie città); grazie Emi-yan!

Ci vediamo alla prossima

Ci siamo salutati con Emi-yan verso le 10.45 alla stazione di Roppongi (六本木駅) sulla linea Chiyoda (千代田線). Un abbraccio e, come ormai sono solito fare, un arrivederci. Sono sicuro che con Emi-yan mi incontrerò di nuovo. Grazie di tutto Emi-yan!

エミやんへ

Non posso lascere il post così dopo aver parlato tanto di Emi-yan senza che lei possa capire un accidenti di quello che ho scritto. Quindi di seguito le faccio una piccola traduzione del post.

エミやんごめん、イタリア語は難しいんですね。このポストは昨日の夜についてだから、ちょっとエミやんについてのポストだ、ちょっとだけ。

変な事を書いていないんだよ、心配しないでね。エミやんがちょっとビックリしたと書いたんだけどさ、エミやんが怖かったと書いていないよ。約束だったね、守ったよ!

昨日にエミやんと遊んだり、いっしょうに東京ミドル・タウンで「Water works」を見たり、そのあと居酒屋で食べたりすると書いた。楽しかったんだけどさ、10時45分に終わっちゃったんだ。そしてエミやんにありがたいがあると書いた。それは本当だ。

エミやん色々ありがとうございます。また今度ね!

Comments

Antonella-Dell-Aquila said:

vengo meno anche io alla promessa fatta e scrivo veramente il mio ultimo post. emi-yan, è l'ultimo dei nomi giapponesi che hanno riempito le pagine di questo blog in questo anno. voglio dire anche io grazie a tutte queste persone che in un anno hanno aiutato, accompagnato, condiviso la vita di mio figlio. so che resteranno sempre nel suo cuore e quindi sono care anche a me. Sono contenta inoltre perchè so che con il tuo essere hai portato in una terra lontana una immagine bella del nostro paese. corro a prenderti!!!!

This comment was posted on Sat 1st Sep 2012 at 12:18

Andrea-Tino said:

エミやん、上のコメントは母からのコメントですよ!母はエミやんが友達になってよかったと言ったんですよ。じゃ、僕もエミやんに会って友達になってよかったと言う!

This comment was posted on Sun 2nd Sep 2012 at 18:56

Please, before posting, read carefully the How To guide.
Username:Passphrase:(0 chars)

As you can see my blog works as a personal and work posting system. You can find scientific entries or travel entries and so on. Of course, when posting your comments, please be aware of what you write being respectful of the others (no mention about spam or bad language). Thankyou.

Time Zone info
This web site uses a time server with the following characteristics.
It is now: 11H 57M
TZ ID/Name: W. Europe Standard Time/W. Europe Standard Time
UTC offset: 0D 1H 0m 0s
Daylight ID/Status: W. Europe Daylight Time/Supported
Calendar
August 2014
MonTueWedThuFriSatSun
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567
Vulcanus in Japan Programme (over) days counter
Into Vulcanus in Japan for:
366 days
+ 728 days
Blog status

Blog status: Active

Commenting status: Active

Blog pages navigation
Use the following tree to navigate through the pages if this blog.
Blog visualization
It is possible to view the blog posts using several view, choose the one you prefer.

Choose how to sort posts.

Print the blog
You can use this tool to get a printable version of the blog. Select the options you desire.

From date:

To date:

Get printable version

Andrea Tino (atino.name) © 2011. Current version name: SailorMan (3.0.0.0)
Web site optimized for a visualization on 1024x768 px and higher resolution screens. | Color gamma: 56K minimum required
Web site W3C XHTML 1.0 Strict compliant. | Developed targeting Microsoft Internet Explorer 9.0+, Mozilla Firefox 4.0+ web browsers.
Required javascript 1.1+ | Required standard western utf-8 character set | Required standard eastern Japanese character set (Hiragana, Katakana and basic Chinese Kanji).
Graphics components: Microsoft Clip Art. | All other images are properties of the respective owners and treated accordingly to the corresponding use license.
All content is managed and administrated by Andrea Tino, atino.name represents Andrea Tino on the Internet as a private subject.

Contact me at the following addresses.
me(AT)atino.name - Use this address to send emails directly to me for any purpose.
info(AT)atino.name - Use this address to ask information about the web site.
flames(AT)atino.name - In order to be compliant to netiquette, send flames at this address.
blog(AT)atino.name - Use this address to ask or write me something about a specific post in the blog. Remember to specify the post title.
rate(AT)atino.name - Use this address to send me specific information regarding this web site (what you like or dislike).