June 2008 - Posts

Engineer, Physicist and Mathematician
18 June 08 03:58 AM | norman | with no comments

To Engineer, his mathematical model is the correct representation of the real world.

To Physicist, the real world follows his mathematical model.

To Mathematician, he does not care!

Smile

What about Computer Scientist? To Computer Scientist, he is interested in these attributes of the model:

  • Can the model be solved? (Decideability)
  • How long will it take to solve it? (Tractability)

So, they all work with the model! Smile

Share this post: | | | |
Parallel Implementation of Simpson’s Rule for Numerical Integration to approximate the value of Pi
13 June 08 07:32 AM | norman | 1 comment(s)

In previous posts I talked more on theoretical aspects of parallel computing. In this post I'm going to show some code example of a parallel program that I did. The code is in C and uses the MPI (Message Pasing Interface) library that is part of Microsoft Compute Cluster Pack, part of Microsoft High Performance Computing.

MPI is actually a spec. It's been implemented in Fortran and in C. An attempt to implement it in .NET has been made as well. Note that MPI uses Message Passing approach that is different from Shared Memory approach uses in ParallelFX from Microsoft. In other words, there is no production level library for Parallelism that uses Message Passing in managed code. To really understand parallelism, learning ParallelFX alone is not enough.

Back to the code, here it goes:

#include "stdafx.h"
#include <stdio.h>
#include <mpi.h>

double Function(double x)
{
      return 4/(1+(x*x));
}

double IntegrateUsingSimpson(int n, double x0, double xn)
{
      double h = (1.0-0.0)/n; // Note: in general (xn-x0)/n, this is for Pi only
      int i = 0;
      double x = x0;
      double result = 0.0;
 
      while(x <= xn)
      {
            if(i != 0 | i != n-1)
            {
                 if(i%2 == 0)
                 {
                        result += 2*Function(x);
                 }
                 else
                 {
                        result += 4*Function(x);
                 }
            }
            else
            {
                   result += Function(x);
            }

            i++;
            x += h;
      }

      result = result / (3*n);

      return result;
}

int main(int argc, char** argv)
{
      int size, rank, i;
      int n = 500000;
      MPI_Status status;

      MPI_Init(&argc, &argv);
 
      MPI_Comm_size(MPI_COMM_WORLD, &size);
      MPI_Comm_rank(MPI_COMM_WORLD, &rank);
 
      if(rank == 0)
      {
          double GlobalPi = 0.0;
          double bufferPi;

          for(i = 1; i < size; i++)
          {
                 MPI_Recv(&bufferPi, 1, MPI_DOUBLE, i, 1, MPI_COMM_WORLD, &status);
                 GlobalPi += bufferPi;
          }
   
          printf("Pi = %f\n", GlobalPi);
      }
     else
     {  
            double localPi;  
            double x0 = (rank-1)/(size-1);
            double xn = (rank)/(size-1);

            localPi = IntegrateUsingSimpson(n, x0, xn);
            MPI_Send(&localPi, 1, MPI_DOUBLE, 0, 1, MPI_COMM_WORLD);
      }

     MPI_Finalize();

     return 0;
}

What this code is all about?

To understand more, please download the paper I wrote on the subject here: http://geeks.netindonesia.net/files/folders/norman/entry52033.aspx

Here's the abstract of the paper:

Parallel implementation of an algorithm is of high interest because it brings speed up to the execution time of that algorithm. Numerical Integration such as Simpson’s Rule is an example of Numerical Method that can be fully implemented in parallel thru data parallelism (domain decomposition). This paper shows the parallel implementation of Simpson’s Rule to approximate the value of Pi by following Foster’s methodology and using the message passing mechanism. This paper also highlights that parallelism in Numerical Methods is not without problem; parallelism may produce less accuracy due to Error Propagation. It is something that needs to be seriously considered in implementing Numerical Methods in parallel.

Share this post: | | | |
New Family of Microsoft Certifications for Developers (.NET 3.5 Certifications)
12 June 08 05:26 PM | norman | 2 comment(s)

I summarized the info in the websites of Microsoft new family of Certifications for developers, the certifications for .NET 3.5 (Visual Studio 2008). It can be used as a "map" while you're browsing the certifications web sites.

You can download the PDF file here: http://geeks.netindonesia.net/files/folders/normslides/entry51962.aspx

Share this post: | | | |
Fitter Happier from OK Computer
03 June 08 03:11 AM | norman | 1 comment(s)

Fitter, happier more productive
Comfortable, not drinking too much
Regular exercise at the gym 3 days a week
Getting on better with your associate employee contemporaries

At ease, eating well
No more microwave dinners and saturated fats
A patient better driver, a safer car, baby smiling in back seat
Sleeping well, no bad dreams, no paranoia
Careful to all animals, never washing spiders down the plughole

Keep in contact with old friends, enjoy a drink now and then
Will frequently check credit at Moral Bank hole in wall
Favours for favours, fond but not in love
Charity, standing orders, on sundays ring road supermarket

No killing moths or putting boiling water on the ants
Car wash also on sundays
No longer afraid of the dark or midday shadows
Nothing so ridiculously teenage and desperate
Nothing so childish

At a better pace, slower and more calculated
No chance of escape, now self-employed
Concerned but powerless
An empowered and informed member of society

Pragmatism, not idealism
Will not cry in public
Less chance of illness
Tires that grip in the wet
Shot of baby strapped in back seat
A good memory

Still cries at a good film
Still kisses with saliva
No longer empty and frantic
Like a cat tied to a stick
That's driven into frozen winter ***

The ability to laugh at weakness
Calm, fitter, healthier and more productive
A pig in a cage on antibiotics

"Thom Yorke (Radiohead) is a genius"

Share this post: | | | |
General Strategy in Seeking Solution to a Computational Problem (An Algorithm Design Technique)
01 June 08 03:44 PM | norman | 3 comment(s)

The basic general strategy is: Replace a difficult problem with an easier one that has the same solution (or closely related solution). In other words, transform the representation of your difficult problem into a different representation that is easier to solve and producing solution that is a solution to your original problem.

As a simple example, how would you compute 2^3? Simple. You only have to do this: 2*2*2 (multiply three 2s). In general, for a^b, you just have to multiply a, b times. Here you just have to compute it straight away as this is a simple problem. No need to change the representation. But now what about 2000^(1/3)? (Remember, don't use library such as System.Math.Pow - the point here is for you to be able to create such library)

The solution to 2000^(1/3) is actually to find x such that x^3 = 2000. So, you got a Polynomial x^3-2000 = 0 (A different representation of the original problem, but the solution is the solution to the original problem). To solve it you just simply write code to implement the Bisection, Newton or Secant Method. Numerical Methods in Rootfinding Problem. You change a Power Problem into Root Finding Problem which is easier to solve. Numerical Methods for this problem has been established. Writing codes of Bisection, Newton or Secant Method is trivial.

Another example, solution to a linear systems Ax = B (here A & B are matrices), where you want to find the vector x. What you need to do is to change the matrix A into triangular form using Gaussian Elimination, then solving a linear system with A that is triangular matrix is simple. You can simply use Backward Substitution. Here you change the matrix A into a triangular matrix.

Here are more Examples (got it from Michael T. Heath):

  • Replacing infinite processes with finite processes, such as replacing integrals or infinite series with finite sums, or derivatives with finitie different quotients
  • Replacing general matrices with matrices having a simpler form (like the example above)
  • Replacing complicated functions with simple functions, such as polynomials
  • Replacing nonlinear problems with linear problems
  • Replacing differential equations with algebraic equations
  • Replacing high-order systems with low-order systems
  • Replacing infinite-dimensional spaces with finite-dimensional spaces

This general strategy is actually an algorithm design technique called Transform and Conquer. Another design techniques thay you may have heard are: Brute Force, Divide and Conquer, Decrease and Conquer, Greedy Technique and Dynamic Programming. Anany Levitin has a good book on this algorithm design techniques. If you want to be a serious software developer, you should live and breath these algorithm design techniques. The using C#, .NET Framework, Visual Studio is the easiest part! You need to master the more important thing: Algorithms.

PS: You cannot see the implementation of Syste.Math.Pow. When you ILDASM or use Reflector you will get that the body of the method is actually a function call to nternal method, that is method that exists within the CLR! Yes, folks, a method in the CLR, not in the Framework Library. So, you cannot see it. Smile. It also means that this internal method is so important that is has to be in the CLR. It also means it was built using C++.

Share this post: | | | |

This Blog

About Me

Syndication