May 2008 - Posts

Going Parallel? See how big your Serial Fraction First!
29 May 08 03:26 PM | norman | 2 comment(s)

As promised in my earlier post, here I'd like to talk about Amdahl's Law, thru which you'll get the formal idea that speed up by parallelism only really works for certain kind of problems. Problems which algorithms to solve have small serial fractions. My goal with this post is to give you a fair understanding that you won't subscribe to the overrated view on parallelism, especially from those who sell multicore machines and Parallel APIs. Another thing is that to make you see that learning and optimizing sequential algorithm is still very important even if we have all multicore machines in the market.

First, let's look at what is defined as Serial Fraction.

In an algorithm to solve a problem, there is always part that has to be done sequentially (serial), and there is part that can be made to run in parallel. So, the time needed to run this algorithm on a single processor can be expressed as follow:

TSeq = S + P

Where,
TSeg = Time spent to run an algorithm on a single processor
S = Time spent on the sequential part of the algorithm on a single processor
P = Time spent on the parallel part of the algorithm on a single processor

Now, if you run the algorithm in N processors you would have:

TPar = S + (P/N)

Note that the number of processors only affect to the parallel part of the algorithm.

Then the Speed Up that you will get is:

SN = TSeq/TPar
     = (S+P) / (S+(P/N))

Lets back to TSeq = S + P, we divide both sides by TSeq we will have:

1 = (S/TSeq) + (P/TSeq)

Now we define S/TSeq as Serial Fraction and name it F.

F = S/TSeq

We now have 1 = F + (P/TSeq) or we can put it this way:

P = (1-F)*TSeq

Let's substitute this back to Speed Up, so we have:

SN = (F*TSeq + (1-F)*TSeq) / (F*TSeq + ((1-F)*TSeq)/N)
     = (F + (1-F)) / (F + (1-F)/N)
  
 SN = 1 / (F + (1-F)/N)

Here we have Speed Up as a function of Serial Fraction and number of processors.

So,

• Ideal Speed Up only happens if F = 0 (there's no Serial Fraction in the algorithm) as it will give you N times Speed Up.
• If F = 1 (the whole part is Serial), then no matter how many processors you use you won't get any Speed Up, as the Speed Up is 1.

As an example, your program is made up of 0.7 Serial Fraction and 0.3 Parallel Fraction. You use 4 processors to run this algorithm (as if your Parallel Fraction is reduced into 1/4th, you get Speed Up by 1/(0.7+(0.3/4)) that is 1.29 times faster compared to if it was run on a single processor. If you can tweak your Serial Fraction by come up with better Sequential Algorithm and let say you only get it twice faster (as if your Serial Fraction is reduced by half), then even if with still just one processor you would have 1/(0.35+0.3) Speed Up that is 1.54. Faster. Better than running it on 4 processors without working on the sequential algorithm.

What does it tell you?

• Parallelism only provides significant Speed Up if your algorithm has small Serial Fraction. The bigger the Serial Fraction, the more the number of processors become not really matters.
• Even if in this new era of multicore machines in the market, it is still important to learn and optimize sequential algorithms (as there are many problems that need to be solve in sequential by nature).

In other words, for problems that has bigger Serial Fraction, working on the algorithm introduce more siginificant speed up compared to adding more processors. As I always say, algorithm is always be the corner stone of computing. Not machines, not Products/APIs, not programming languages. It is Algorithm.

Please note as well that we're still not considering load balancing and communication overhead here. If we include them, then we will get lower Speed Up for the Parallel Fraction. The P/N is too ideal.

So, put it all in one sentence: Speed Up of Parallel Algorithm is effectively limited by the number of operations that need to be done sequentially, i.e. its Serial Fraction.

That's Amdahl's Law!

Share this post: | | | |

Filed under: Algorithm, Parallel Computing

n processors won't make your program runs n times faster
28 May 08 03:47 PM | norman | 2 comment(s)

Let say it takes 6 minutes to do a computation on a set of data in a single processor. Then you have 3 processors altogether. Would your task finish in 2 minutes (6 divided by 3)? NO IT WON'T!

Why? Because your algorithm is a sequential algorithm. Even if with 100 processors your computation would still need 6 minutes to complete. To be able to exploit multiprocessors you would also need PARALLEL ALGORITHM. That said algorithm that was designed from the ground up with parallelism in mind.

Now let's see the other way around. Let say it takes 2 minutes to finish a computation using a parallel algorithm on 3 processors. Would it take 6 minutes if you run that algorithm in a single processor? Maybe. If you are lucky. Chances are it would take more than 6 minutes. Parallel algorithm that runs in a single processor may have worst performance compared to a sequential algorithm runs in a single processor (I'll show you the example on future posts). It is because a parallel algorithm was designed to run on multiprocessors, not on single processor. And it maybe the case that your parallel algorithm will choke in a single processor.

Summary of paragraphs above: 

• The number of processors is irelevant if your algorithm is not a parallel algorithm, you would need a parallel algorithm to exploit multiprocessors.
• Parallel algorithm is superior only on multiprocessors, in single processor it may not run properly, or it will run with worst performance compared to its sequential algorithm counterpart.

So, algorithm is still the most important factor, more important than the number of processors itself.

It is also dangerous to believe that it is a good thing if a language construct/compiler/API can adapt/switch an algorithm to run on multiprocessors or single processor automatically. The optimal sequential and parallel algorithm for the same problem maybe totally different. The parallel algorithm works best on multiprocessors, and the sequential algorithm works best on single processor. If your language construct/API can make your parallel algorithm to run on a single processor, then it may not be better compared to algorithm designed with sequential in mind. Similar with that, if your algorithm was designed with sequential in mind, then using a language construct/API that automatically make it run on multiprocessors may not result program that runs faster than program with algorithm designed with parallelism in mind.

Again, there's no silver bullet. If you will use multiprocessors, design/use a parallel algorithm. If you use only a single processor, use the best sequential algorithm there is. It is the algorithm that matters, language construct/compiler/API is just a helper.

Design your algorithm properly!

Speed Up & Efficiency

Now I'd like to talk about some terms you may need to understand to explore further on parallelism.

Let's start with the definition of Speed Up. Speed Up is defined as:

SN = Ts/Tp

Where,
SN = Speed Up
Ts = Time taken to run the fastest sequential algorithm on a single processor
Tp = Time taken by a parallel algorithm on N processors

As one can see, Speed Up is determined by algorithm used. Not by number of processors. SpeedUp is about comparing a parallel algorithm runs on N processors with the fastest sequential allgorithm runs on a single processor.

Then we define Efficiency as follow:

EN = SN/N

Where,
EN = Efficiency of a parallel algorithm on N processors.
SN = Speed Up (as defined above).
N = number of processors.

As one can see, the efficiency here means the efficiency of the parallel algorithms. For a given number of processors, two different parallel algorithm may have their own Speed Up and Efficiency.

So, these metrics are measuring algorithms!

100% Efficiency is only achieved when Speed Up is equal with the number of processors, or in other words, when Time Taken by a parallel algorithm run on N processors is equal to 1/N time taken by fastest sequential algorithm. Which may never be achieved due to several factors that limit the Speed Up as follow:

• Software Overhead; there will always be softare overhead, even with a completely equivalent algorithm with sequential algorithm. As an example, there may be additional index calculations needed by the manner in which data are "split up" among process. There is genrally more lines of code to be executed in parallel progam compared to sequential progam. 
• Load Balancing Overhead; Speed Up is generally limited by the slowest node. So, it is an important consideration to balance the load of work thru out all nodes. It also means a load balancing mechanism must be applied, and it means additional work.
• Communication Overhead; It is clear that communicating data between processors degrades the Speed Up. So, it is important to keep all processors busy but at the same time reduce the amount of communications. Larger grain size of Tasks is generally better. There is a metric related to Communication cost called Machine Dependent Ratio (MDR) defined as:

 MDR = Tcomm/calc
 
Where,
Tcomm = Time to transfer a single word (byte) between nodes
Tcalc = Time to perform some floating point calculation

The lower the MDR, the better it is. We become less dependent to the machine (lower communication cost).

• Amdahl's Law; I will make a dedicated post on this. For now I can summarize it as follow: not all portion of algorithm can be made parallel. There is still a fraction that needs to stay sequential. So, parallelism is really be of help if the fraction that can be made parallel is bigger. If most portion cannot be made parallel, then parallelism is not so helpful on that kind of problem. In short, again, parallelism is not silver bullet.

As one can see, there are overheads you must pay for parallelism (Software Overhead, Load Balancing Overhead and Communication Overhead). Ensure what you pay is worth it. Parallelism is useful only if the Speed Up produced by a parallel algorithm is far bigger than these overheads you have to pay. In addition to that, Amdahl's Law helps you to stay aware whether the parallel fraction of your problem is significant. Otherwise, you make this parallel portion to run faster (with big efforts) but then you only get insignificant improvement in total (in case the sequential part is a lot bigger).

Then it is clear that n processors won't make your program runs n times faster. It depends on the algorithm you use, whether parallelism cost is cheaper than the Speed Up gain, and it depends to the nature of the problem, whether the parallel fraction is significant.

So, now you can be more critical to those who sells multicore machines or APIs that says parallelism can solve all your problems faster. They are just trying to sell you their machines or API. Machines & APIs cannot compensate algorithm design ignorance.

Reference:

• Seminar, Kudang B., "TM5 Speed Up & Efficiency", Lecture Notes, Deparment of Computer Science - Faculty of Mathematics and Natural Sciences, IPB, Bogor.

Share this post: | | | |

Filed under: Algorithm, Parallel Computing

Foster's Methodology: A Parallel Algorithm Design Methodology
28 May 08 08:06 AM | norman | with no comments

Last time I talked about the several kinds of parallelism, now I'd like to talk about the methodology we can use in designing a parallel algorithms, The Foster's Methodology.

First, let's define first a Unit of Computation and call it a Task. A Parallel Computation is merely a set of Tasks. A Task can consist of:

• Program
• Local Memory
• Collection of IO Ports

The Tasks in a Parallel Computation interact one another by sending messages thru channel.

Foster's Methodology is basically a sequence of steps to partitioning computation/data into pieces (tasks), determining communication between these pieces (tasks), grouping the pieces (tasks) that have intense communication to one another, then finally mapping these groups into several processors we have. We will look at these steps in more detail one by one.

Foster's Methodology:

1. Partitioning
2. Communication
3. Agglomeration
4. Mapping

1. Partitioning

Here we divide computation and data into pieces. There are two kind of partitioning:

• Domain Decomposition: Here we divide data into pieces, then determine how to associate computations with the data. In other words, here we break Data Structure into smaller structure that build the original Data Structure. Let say, break a Matrix into smaller Matrices (subsets of the original Matrix), or maybe break a Matrix into its scalar elements if necessary. Then we determine how to do computation to these Matrices (subsets) or scalar elements. From there, we can see whether there are computations to the pieces that can be performed at the same time (read: in parallel).
• Functional Decomposition: Here we divide computation into pieces, then determine how to associate data with the computations. In other words, we're recognizing the functions needed in a computation and how these functions related one another (the relation structure between these functions, which function has to be computed first, which functions need results from which functions, etc). Then we determine how data (in a particular Data Structure) flows thru these functions. From there, we can see whether there are computations that can be performed at the same time (read: in parallel).

Here's some Partitioning Guidenes:

• Minimize redundant computations and redundant data storage.
• Primitive Tasks (Pieces) are roughly the same size.
• Number of Tasks (Pieces) is an increasing function of problem size.

2. Communication

Here we're looking at the communication structure between Tasks (Pieces) we have. We determine the Data Structure and values passed among tasks. There are two kinds of comunication:

• Local Communication: Task needs value from a small number of other Tasks. We need to create channels ilustrating data flow.
• Global Communication: Significant number of Tasks contribute data to perform a communication. It is not recommended to create channels for them early in the design. We will look into this later.

Here's some Communication guidelines:

• Communication operations are balanced among Tasks.
• Each Task communicate with only small group of neighbours.
• Tasks can perform communications concurrently.
• Tasks can perform computations concurrently.

3. Agglomeration

Here we group several Tasks (Pieces) into larger parts, larger Tasks. You might be wondering; "We've broken the computations into pieces then now we need to group the pieces again, what's the point?" Well, in this step, we're not putting the pieces back into the original size. We're just grouping "close" Tasks so that we can increase performance, maintain sclability of the program and simplify programming. Let say, we group two or more tasks that are intensely communicate one another into a larger group of Tasks. In MPI (Message Passing Interface) Programming, the goal is often to create one agglomerated Tasks per processor.

How Agglomeration can increase performance? As I said before, we increase performance by eliminating communication between primitive Tasks into consolidated Tasks. We can also combine Tasks into groups of "Sending Tasks" and "Receiving Tasks".

Here's some Agglomeration guidelines:

• Locality of Parallel Algorithm has increased.
• Replicated computations take less time than communications they replace..
• Data replications doesn't affect scalability.
• Agglomerated task has similiar computational (remember the Big-Oh? [:]) and communication costs.
• Number of Tasks increases with problem size.
• Number of Tasks suitable for likely target systems.
• Trade-Off between agglomeration and code modification is reasonable.

4. Mapping

This is the process of assigning Tasks (Agglomerated Tasks) into processors that we have. There are situations where mapping is done by Operating System (centralized multiprocessor), and there are situations where we manually do the mapping (distributed memory system).

There is a conflicting goals in mapping activities:

• To maximize processors utilization
• To minimize interprocessor communcation

Finding an optimal mapping of tasks itself is an NP-Hard problem. Like it or not, we need to rely on heuristics here.

Here's Mapping Decision Tree that can be used as a strategy:

•  If you have Static number of tasks:
• If you have Structured Communication: 
• If you have constant computation per task: Agglomerate tasks to minimize communication, create one task per processor
• If you have variable computation per task: Cyclycally map tasks to processors
• If you have Unstructure Communication: Use a static load balancing algorithm
• If you have Dynamic number of tasks:
• If you have frequent communication between tasks: Use a dynamic load balancing algorithm
• If you have many short lived task: Use a run-time task scheduling algorithm

Here's some Mapping guidelines:

• Consider designs based on one task per processor and multiple task per processor
• Evaluate Static and Dynamic task allocation
• If Dynamic Allocation is chosen, the task allocator should not be a bottleneck to the system
• If Static Allocation is chosen, ratio of tasks to processor at least 10:1.

 

That's about it. I will talk more on this on future posts, along with examples. Again, my message is that using a parallel API (or even just a multithreading API) is "easy". Designing Parallel Algorithms to solve a problem is where the "real challange" is.

Reference:

• Quinn, Michael J., "Parallel Programming in C with MPI and OpenMP - Chapter 3 Parallel Algorithm Design", McGrawHill 

Share this post: | | | |

Filed under: Algorithm, Parallel Computing

Age++;
22 May 08 01:24 AM | norman | 10 comment(s)

"Age" is actually a real number (represented as "float" in computers). But by convention, human celebrates only the annual incremental, so it becomes an integer.

Today, May 22, I celebrate the day when my property of "age" is increased by one. So, I am officially one year older now.

Please note that this "age" property is the property of my flesh & blood. Cos I believe, as a spirit I am older than that, and the spirit lives longer than this flesh & blood. Anyway, I thank The Lord to give my spirit a chance to actually walk on earth, feel the sun on my face, taste the water and encountered to Mathematics. Thanks to My Parents too as thru them I could come into this three dimensional world.

O, I'd like to thank the first 10 persons that congratulate me on this birthday too

1. Firsa Hanita
2. Rini Anggraini
3. Sevatrina Devi 
4. Estrelita Maya Zefanya
5. Novia Dhyah Kartika Sari
6. Yusnita Fadilah
7. Anastasia Erika Indrawati
8. Sherly Veronica
9. Silvana Hernawati Aguila
10. Veridiana Tricahyanti

For others that are not in the list, come on, it's not such a big deal. I have limited space in this blog anyway.

Btw, Adrian Godong gave me a You Tube URL as a b'day gift. And it is indeed fantastic, as a die hard fan of U2 I can say that this kid Sungha Jung is awesome: http://www.youtube.com/watch?v=L4CR3GoB3YY

Share this post: | | | |

Filed under: Birthday

Presidential Lecture from Bill Gates at JCC this morning (May 9)
09 May 08 07:27 AM | norman | 1 comment(s)

Here's a summary I wrote in a citizen journalism website about Bill Gates' lecture this morning.

This is not my first Bill G meeting experience, met him couple of times in US, but this is my first President SBY meeting experience.

 

Share this post: | | | |

Filed under: SBY, Bill Gates

Talk at Universitas Pakuan
03 May 08 04:40 AM | norman | with no comments

Baru aja deliver talk di seminar sehari di Universitas Pakuan, Bogor. Memenuhi undangan dari Himpunan Mahasiswa Ilmu Koputer-nya. Sesuai permintaan, saya membawakan topik "From C++ to C#". Intinya adalah belajar C# bagi mereka yang punya C++ background. Jd, learn C# thru C++. By comparing the two, looking at the differences and similarities. Some comparison with Java was also shown.

Saya juga mengajak Basir untuk share tentang BIND-C-nya, community .NET di Bogor.

Pembicara lainnya adalah orang dari LAPAN, yang membawakan materi tentang "Role of Computer Science in Aerospace", interesting talk kayaknya. Tapi saya gak bisa ikutan. Mesti ke kampus.

Share this post: | | | |

Filed under: C#, Universitas Pakuan

Probabilistic Neural Networks works better for classification problems
02 May 08 04:30 PM | norman | 4 comment(s)

If you have checked out my paper about the using of Feed-Forward Backpropagation Neural Networks, here's another approach that I used. It is called the Probabilistic Neural Networks. This approach can forecast the onset of Diabetes Mellitus with 100% accuracy. Compared to the Feed-Forward Backpropagation approach that could give no more than 93%.

Probabilistic Neural Networks was actually designed for such classification problems. No wonder.

Share this post: | | | |

Filed under: Algorithm, Computational Intelligence, Neural Network