April 24, 2010

Kick Ass (2010), was funny!!



“I can’t read your mind, but I can kick your ass”

Today, I watched movie Kick Ass (2010). It's directed by Matthew Vaughn, who also directed "Wanted". His movie seems always satisfy the deviant desires of salaryman like me. ★★★★★!!!

When I watched a preview of this movie, it was too babyish. But, there are many scenes of brutality, and it was very impressive to me. Especially, the rescue scene of Kick Ass/Big Daddy part of the final act brought tears to my eyes. (-_-;;)

April 15, 2010

Installing SciPy

Original article: Installing SciPy

If one couldn't guess from my having built this site using Django, I happen to be a big fan of using Python in various stages of software development. My focus on graphics and image processing requires more robust array and matrix datatypes and their associated operations than what Python includes in its standard library. There are two extensions to Python that provide this functionality: numpy, for efficient, native memory arrays and matrices, and scipy for numerical tools such as solvers, optimization, and Fourier transforms.

While the default installs of these modules are significantly faster than any Python-native implementation, they are still quite slow. The code included in with numpy and scipy to perform this computation is not very efficient. Optimized libraries have been written for the methods that numpy and scipy rely on, so the best of both worlds would be the ease-of-use provided by Python and the performance of tuned architecture-specific math methods, which is what this explains how to install.

This article is a step-by-step set of instructions on how to install the latest Python, numpy, and scipy along with optimized versions of the native code libraries they depend on. It's most useful if your operating system does not have pre-packaged versions available, you'd like to install a potentially faster version of the modules than provided, or you don't have root access to use the package system on your platform.

Questions, comments? Email me: site+python@matttrent.com.

Alternatives

I'll preface this entire process with the fact that it's a rather large pain in the ass. In many cases, you can get pre-compiled versions of the libraries for your platform. They might not be as optimized as the result of my instructions here, but could serve your needs well enough. If you just want to install them to investigate what they are capable of, I'd forgo the heavy optimized version for now. Basically, if you can avoid compiling all the source and just use packages, I advise doing so.

Windows

All the steps outlined below assume you are using an operating system similar to UNIX and have the GNU toolchain available. Unless you are attempting to do this under Cygwin or similar, the steps don't work. All the modules are pre-compiled for Windows, and it's probably your best bet. They are linked against the same ATLAS library we are using, so I imagine they are reasonably fast.




OS X

OS X users have a slightly more involved process than Windows users, but end up with a more optimized version of the setup. The fine folks over at trichech.us have collected all the modules we need into single scipy Superpack for both PowerPC and Intel hardware. These are all built against the ActiveState version of Python 2.4, which you will need to install as well:




Linux

Several flavors of Linux contain the numpy and scipy modules in their distro sets. This is covered by the scipy installation docs.

Starting out

OK. Assuming none of the previous options cover your needs, let's get down to business. I'm not entirely sure what the full set of requirements for Python is. It's covered in the documentation on the site, and the README in the source tarball. It installs fine with the standard developer set on my SuSE 10.1 machine. You will definitely need the ability to compile C/C++, which gcc does more than adequately. Also, because numpy and scipy are still under very active development, I grab the bleeding edge version using Subversion, which you will need the client for.

The only requirement that I know of that might not be installed is the g77 portion of the GNU compiler for compiling FORTRAN programs.
(Yes, this is 2007 and we're still using FORTRAN. Lots of linear algebra libraries do. Get over it.)

Having ensured we have these in place, pick a temp location to download and compile our libraries in:

cd /var/tmp
mkdir Python
cd Python

Install Python

The first order of business is to install Python, which is currently 2.5. So, get the latest version and unpack it:

wget http://www.python.org/ftp/python/2.5/Python-2.5.tgz
tar xzf Python-2.5.tgz
cd Python-2.5
Python installs using the standard autoconf procedure, so the first step is to configure the source:

./configure --enable-shared --with-threads
If you are installing to a non-standard location, you can alter the directory prefix with the flag:

./configure --enable-shared --with-threads --prefix=$SOMELOCATION
Once that has completed checking for various modules, we compile the source and test to make sure the interpreter is functioning correctly:

make
make test
Assuming there are no errors in compilation or testing, then install the software:

make install

Path update

If you installed to a different location, and haven't already made use of other software in that location, you'll need to update your $PATH variable to select the new Python install over the standard system install.

In .cshrc add:

setenv PATH $SOMELOCATION/bin:$PATH
or in .bashrc add:

export PATH=$SOMELOCATION/bin:$PATH
Then type source .bashrc or source .cshrc depending on which you use. And check to make sure you have the right version. Start the Python interpreter and check that the version is 2.5 and location of the executable is the one we installed:

>>> import sys
>>> sys.version
'2.5 (r25:51908, Nov 1 2006, 14:57:46) \n[GCC 4.1.0 (SUSE Linux)]'
>>> sys.executable
'/usr/local/bin/python'
Having verified that to be correct, you now have the latest version of Python installed.

Installing FFTW

The next task is to install the Fastest Fourier Transform in the West, better known as FFTW. This library provides efficient Fourier transforms, which I shouldn't have to tell you are very useful for signal processing tasks.

Returning to our top directory, we grab that code

cd /var/tmp/Python
wget http://www.fftw.org/fftw-3.1.2.tar.gz
tar xzf fftw-3.1.2.tar.gz
cd fftw-3.1.2
We need to build the code twice, once to create the single precision library, and once to create the double precision library. We'll start with the default, double precision:

./configure --enable-shared --enable-sse2 --enable-portable-binary \
--enable-threads
Or add the --prefix flag to put it somewhere else:

./configure --enable-shared --enable-sse2 --enable-portable-binary \
--enable-threads --prefix=$SOMELOCATION
We then build the software and install it

make
make install
Now, we repeat the exercise for the single precision library, adding the --prefix argument if needed:

./configure --enable-shared --enable-sse --enable-float \
--enable-portable-binary --enable-threads
And once again build the software and install it

make
make install
Having completed that, we now have a working version of FFTW.

Install ATLAS and LAPACK

The second library to install provides efficient routines for linear algebra, and is a bit more complicated than the FFTW. The library consists of two parts:


  • BLAS (Basic Linear Algebra Subprograms) which covers basic vector-vector, matrix-vector, and matrix-matrix operations
  • LAPACK (Linear Algebra PACKage) which provides higher-lever routines like solvers and eigenvalue decomposition

The source of LAPACK you can download from the site contains an implementation of BLAS, but that BLAS version does not have very well optimized routines. Instead, we use a different BLAS implementation called ATLAS which can automatically tune itself for whichever platform we are compiling it on. So, it ends up being a somewhat complicated method of building the full numerical package LAPACK, but replacing the parts of BLAS and LAPACK with ones provided by ATLAS, which are considerably more efficient.

Build LAPACK

Go back to the top level temp directory if you install Python

cd /var/tmp/Python
Get the LAPACK source

wget http://www.netlib.org/lapack/lapack.tgz
tar xzf lapack.tgz
cd lapack-3.1.0
and build the library after copying the appropriate Makefile into place

cp INSTALL/make.inc.LINUX make.inc
make lapacklib
Having compiled the static LAPACK library, copy it to the same library name as the ATLAS library we will make in the next part:

cp lapack_LINUX.a liblapack.a

Get ATLAS

You have 2 options on building ATLAS: compiling the source yourself and tuning it to your platform, or grabbing a pre-built version for your hardware architecture. While the compiling and tuning ATLAS will result in the absolute best performance, it also takes several hours to complete. I'll cover the latter option, as it's worked well enough for me. If you choose to build it from scratch, it's pretty similar in nature. From the ATLAS site:

https://sourceforge.net/projects/math-atlas/

grab the Linux binary for your architecture and drop it in the same temp location you made. As of current, the latest stable build is version 3.6.0, and I'll assume this is being done on a Pentium 4 class machine with SSE2 instructions.

Unzip the library:

tar xzf atlas3.6.0_Linux_P4SSE2.tar.gz

Combine ATLAS and LAPACK

From here, we need to integrate the partial ATLAS LAPACK implementation with our full LAPACK implementation. We create a temporary directory, extract all the object files from the partial LAPACK implementation contained in ATLAS.
cd Linux_P4SSE2/lib
mkdir tmp
cd tmp
ar x ../liblapack.a
We then overwrite the object files in the static library of LAPACK we created previously with the ones from the ATLAS library:

cp ../../../../LAPACK/liblapack.a ../liblapack.a
ar r ../liblapack.a *.o
cd ..

Install the result

Having created the full ATLAS/LAPACK hybrid, copy it to the necessary location:

cd ..
su
cp include/* /usr/local/include
cp lib/* /usr/local/include
or if you don't have root, you can use the same path as you did for your Python install

cp include/* $SOMELOCATION/include
cp lib/* $SOMELOCATION/lib

Installing numpy

Alright. Now we have all the parts required to build numpy, so lets check that out of it Subversion repository. From the top main directory of this working space, to get the latest version of numpy:

cd /var/tmp/Python
svn co http://svn.scipy.org/svn/numpy/trunk numpy
cd numpy
We'll need to instruct it where to find the ATLAS/LAPACK hybrid and FFTW libraries we made, so we need to edit the site config file:

pico site.cfg
and add the text

[atlas]
library_dirs = /usr/local/lib
atlas_libs = lapack, f77blas, cblas, atlas

[fftw3]
library_dirs = /usr/local/lib
include_dirs = /usr/local/include
fftw3_libs = fftw3, fftw3f
fftw3_opt_libs = fftw3_threads, fftw3f_threads
where library_dirs is where you copied the ATLAS/LAPACK and FFTW library files to, and similarly include_dirs is where the include files for FFTW ended up. If you installed in the default location, it's prefix is /usr/local, otherwise it's whatever you have been using for $SOMELOCATION.

From here we need to build numpy:

./setup.py build
It will dump out a lot of configure and build results. Near the top of the resulting contents you should see text notifying you that it found the ATLAS/LAPACK files to the effect of:

atlas_blas_threads_info:
Setting PTATLAS=ATLAS
Setting PTATLAS=ATLAS
Setting PTATLAS=ATLAS
FOUND:
libraries = ['lapack', 'f77blas', 'cblas', 'atlas']
library_dirs = ['/usr/local/lib']
language = c
If that is found, we can install the library:

./setup.py install
Assuming you have the command python associated with the proper install on your system (if there are several) it will install it in the proper place.

Next, we go about testing our install. Due to the way python imports modules, if it sees the local numpy directories it will try to use those over the ones installed. This will do the wrong thing, and cause a massive headache trying to figure out why nothing works right. For sanity's sake, the easiest way to avoid this very confusing outcome is to switch to some other directory entirely:

cd /
So, run python and on the python shell enter:

>>> import numpy
>>> numpy.test( 10 )
And it should display some text ending in something like:

----------------------------------------------------------------------
Ran 530 tests in 2.093s

OK
Congratulations. You now have a working version of numpy.

Installing scipy

Installing scipy follows in roughly the same process as that of numpy. In fact, all the hard work has been done in the site.cfg we make for numpy, as scipy scans the same file to learn where its libraries are

Returning to our working directory, we check out scipy:

cd /var/tmp/Python
svn co http://svn.scipy.org/svn/scipy/trunk scipy
cd scipy
Since it reads the site.cfg file that numpy conveniently moved into its own install directory, we can just run setup

./setup.py build
It will spit out a lot of text. Assuming that the entries in the site.cfg are correct, you should see a piece of text similar to:

fftw3_info:
FOUND:
libraries = ['fftw3', 'fftw3f']
library_dirs = ['/usr/local/lib']
define_macros = [('SCIPY_FFTW3_H', None)]
include_dirs = ['/usr/local/include']

atlas_blas_threads_info:
Setting PTATLAS=ATLAS
Setting PTATLAS=ATLAS
Setting PTATLAS=ATLAS
FOUND:
libraries = ['lapack', 'f77blas', 'cblas', 'atlas']
library_dirs = ['/usr/local/lib']
language = c
If that is found, we install the library:

./setup.py install
Assuming you have the command python associated with the proper install on your system (if there are several) it will install it in the proper place.

We now test the install once again moving to somewhere to avoid import confusion:

cd /
So, run python and on the python shell enter:

>>> import scipy
>>> scipy.test( 10 )
This time, it'll spit out a lot of text for all its test results. Once done you'll get something like:

----------------------------------------------------------------------
Ran 1618 tests in 67.706s

OK
Don't freak out too badly if you get a couple failures. They usually deal with numerical precision issues. Depending on your needs this may or may not be a problem. I'm not an expert on how to go about fixing them. I've never had any problems with them in my work.

Assuming you're pleased with the outcome, you now have working, optimized copies of numpy and scipy.

April 12, 2010

Deleting files that have a minus symbol as file name

아래와 같은 (-) 심볼을 갖은 파일이 생겨서 지우고 싶었는데, 도저히 지울수가 없었다.

-rw-r--r--   1 edwardyoon other          0 Apr 12 01:43 --no-check-certificate
-rw-r--r--   1 edwardyoon other          0 Apr 12 01:46 -S

-bash-3.00$ rm -rf **certificate
mv: illegal option -- no-check-certificate
..

지우고 싶은데 명령어 option 으로 인식되니까.. 그런데 나도 참 바보다. (-_-;)
아래처럼 지우면 되는 것을.

-bash-3.00$ rm -rf ./-S

April 7, 2010

A Multi-Threaded Pi Estimator

Hadoop 의 Map/Reduce 로 Pi estimator가 구현되어있는데,
이를 Hama, BSP로 처리하면 M/R과 어떠한 성능/코드복잡도 차이를 보여줄까?
물론 안봐도 비디오로 예측되는 바, 이 예제로는 딱히 큰 매리트가 없을것도 같으나..

어쨌건 연습삼아 아래와 같은 Pi 계산 알고리즘을 multi-threaded 프로그래밍을써서 간단하게 만들어 봤다.

iterations = 10000
circle_count = 0

do j = 1,iterations
  generate 2 random numbers between 0 and 1
  xcoordinate = random1
  ycoordinate = random2
  if (xcoordinate, ycoordinate) inside circle
  then circle_count = circle_count + 1
end do

PI = 4.0*circle_count/iterations

이를 자바로 구현해보면 아래와 같다.

public class PiEstimator {
  private double pi = 0.0;
  private final int numTasks = 10;
  private int allFinished = 0;
  private long starttime = 0;

  class PiEstimatorTask extends Thread {
    private PiEstimator Parent = null;
    private static final int iterations = 100000;

    public PiEstimatorTask(PiEstimator Parent) {
      this.Parent = Parent;
    }

    public void run() {
      int in = 0, out = 0;
      for (int i = 0; i < iterations; i++) {
        double x = 2.0 * Math.random() - 1.0, y = 2.0 * Math.random() - 1.0;
        if ((Math.sqrt(x * x + y * y) < 1.0)) {
          in++;
        } else {
          out++;
        }
      }
      double estimate = 4.0 * (double) in / (double) iterations;
      ((PiEstimator) Parent).sync(estimate);
    }
  }
  
  public synchronized void sync(double est) {
    long rt = System.currentTimeMillis() - starttime;
    System.out.println("Terminated at " + rt + " ms, est " + est);
    pi = (allFinished == 0) ? est : (pi + est) / 2;
    allFinished++;
  }

  public double getPi() {
    return pi;
  }

  public void run() throws Exception {
    PiEstimatorTask[] PiTask = new PiEstimatorTask[numTasks];
    System.out.println("Instantiating " + numTasks + " threads");
    for (int i = 0; i < numTasks; i++) {
      PiTask[i] = new PiEstimatorTask(this);
    }
    starttime = System.currentTimeMillis();
    System.out.println("Starting threads, time = 0 ms");
    for (int i = 0; i < numTasks; i++) {
      (PiTask[i]).start();
    }
    
    for (int i = 0; i < numTasks; i++) {
      (PiTask[i]).join();
    }
  }

  public static void main(String[] args) throws Exception {
    PiEstimator pi = new PiEstimator();
    pi.run();
    System.out.println("Final estimate is: " + pi.getPi());
  }
}