July 19th, 2012 | Categories: Condor, Guest posts, programming | Tags:

This is a guest post by colleague and friend, Ian Cottam of The University of Manchester.

I recently implemented a lint program for Condor (unsurprisingly called: condor_lint), analogous to the famous one for C of days of yore. That is, it points out the fluff in a Condor script and suggests improvements. It is based on our local knowledge of how our Condor Pool is set up, here in Manchester, and also reflects recent changes to Condor.

Why I did it is interesting and may have wider applicability. Everything it reports is already written up on our extensive internal web site which users rarely read. I suspect the usual modus operandi of our users is to find, or be given, a Condor script, relevant to their domain, and make the minimum modifications to it that means it ‘works’. Subsequently, its basic structure is never updated (apart from referencing new data files, etc).

To be fair, that’s what we all do — is it not?

Ignoring our continually updated documentation means that a user’s job may make poor use of the Condor Pool, affecting others, and costing real money (in wasted energy) through such “bad throughput”.

Now, although we always run the user’s job if Condor’s basic condor_submit command accepts it, we first automatically run condor_lint. This directly tells them any “bad news” and also, in many cases, gives them the link to the specific web page that explains the issue in detail.

Clearly, even such “in your face” advice can still be ignored, but we are starting to see improvements.

Obviously such an approach is not limited to Condor, and we would be interested in hearing of “lint approaches” with other systems.

Links

Other WalkingRandomly posts by Ian Cottam

July 14th, 2012 | Categories: general math, math software, programming, python, sage interactions | Tags:

If you have an interest in mathematics, you’ve almost certainly stumbled across The Wolfram Demonstrations Project at some time or other.  Based upon Wolfram Research’s proprietary Mathematica software and containing over 8000 interactive demonstrations, The Wolfram Demonstrations Project is a fantastic resource for anyone interested in mathematics and related sciences; and now it has some competition.

Sage is a free, open source alternative to software such as Mathematica and, thanks to its interact function, it is fully capable of producing advanced, interactive mathematical demonstrations with just a few lines of code.  The Sage language is based on Python and is incredibly easy to learn.

The Sage Interactive Database has been launched to showcase this functionality and its looking great.  There’s currently only 31 demonstrations available but, since anyone can sign up and contribute, I expect this number to increase rapidly.  For example, I took the simple applet I created back in 2009 and had it up on the database in less than 10 minutes!  Unlike the Wolfram Demonstrations Project, you don’t need to purchase an expensive piece of software before you can start writing Sage Interactions….Sage is free to everyone.

Fourier Series

Not everything is perfect, however.  For example, there is no native Windows version of Sage.  Windows users have to make use of a Virtualbox virtual machine which puts off many people from trying this great piece of software.  Furthermore, the interactive ‘applets’ produced from Sage’s interact function are not as smooth running as those produced by Mathematica’s Manipulate function.  Finally, Sage’s interact doesn’t have as many control options as Mathematica’s Manipulate (There’s no Locator control for example and my bounty still stands).

The Sage Interactive Database is a great new project and I encourage all of you to head over there, take a look around and maybe contribute something.

July 10th, 2012 | Categories: applications, Free software, Open Source | Tags:

I work for The University of Manchester where, among other things, I assist in the support of various high performance and high throughput computing systems.  Exchanges such as the following are, sadly, becoming all too commonplace

Researcher: “Hi, I have an embarrassingly parallel research problem that needs a lot of compute resource.  Can you help?”

Support: “Almost certainly, you could have access to our 2500 core Condor pool or maybe our 2000 core HPC system or any number of smaller systems depending on the department you are in.  Let’s meet to discuss your requirements in more detail”

Researcher: “Sounds great.  I am using [insert expensive commercial package here], could we install that on your systems?”

Support: “Not unless you pay a HUGE amount of money because you’ll need dozens or maybe hundreds of licenses.  The licenses will cost more than our machines!  Could you use [insert open source equivalent here] instead?”

Researcher: “A member of your team suggested that about 2 years ago but [insert expensive commercial package here] is easier to use, looks pretty and a single license didn’t seem all that expensive.  It’ll take me ages to convert to [insert open source equivalent here].  Instead of splitting the job up and spreading it around lots of machines, can’t I just run it on a faster machine?”

Support: “Sorry but parallelism is the only real game in town when it comes to making stuff faster these days.  I’m afraid that you’ll have to convert to [insert open source equivalent here], open your chequebook or wait until 2076 for your results to complete on your workstation.”

The moral of the story is that if you want your compute to scale, you need to ensure that your licensing scales too.

July 3rd, 2012 | Categories: Science | Tags:
June 30th, 2012 | Categories: Month of Math Software | Tags:

Welcome to the June 2012 edition of A Month of Math Software.  The archive to all previous editions is here.  Feel free to contact me if you have news that you’d like including in next month’s edition.

A list of packages based upon SuiteSparse

  • Tim Davis has put together a list of projects and packages that rely on the various sparse matrix codes he’s written or co-authored over the years (UMFPACK, CHOLMOD, SuiteSparseQR, KLU, CSparse, and the ordering codes AMD and COLAMD).  The list is very impressive but is incomplete.  Drop Tim a line if you work on a project that uses his codes.

Python based software

  • Sage, the superb computer algebra system based on Python and dozens of other open source projects, has seen a minor update to 5.0.1.  Take a look at the changelog for the new stuff.
  • Pandas, the Python Data Analysis Library, is now at release 0.8.0.  This is a major update on the old 0.7.3 and has significantly improved timeseries data analysis in pandas.

Try a spreadsheet that isn’t Excel

  • Gnumeric, the free spreadsheet that’s part of the GNOME office suite, was updated to 1.11.4 in June.  Find out what’s new here.
  • A new version of LibreOffice (version 3.5.4) was released at the end of May but I missed it in May’s update.  LibreOffice is the fork of OpenOffice that everyone should be using these days and includes a great spreadsheet program.

Math-o-mir – The mathematical notepad

  • Danijel gorupec contacted me to tell me of a new release of his free software, Math-o-mir.  According to Danijel ‘The Math-o-mir is a software tool designed to write and edit mathematical equations as easily as possible. The goal was to achieve the same level of simplicity as with pencil and a sheet of paper. It is designed to act as your personal math notepad where you can write down your quick and informal calculations.’  I haven’t had chance to try it myself but it looks interesting.  See what’s new in the 1.7 release over at Danijel’s blog.

Gnu Regression, Econometrics and Time-series Library

Numerical Libraries

Blogs, Bits and Bobs

  • Planet Octave is now up and running.  This is a collection of blogs related to Octave and is currently made up of posts from the Google Summer of Code students. Some great stuff on the Just in Time (JIT) compiler development, Octave GUI and more.
  • PTC’s MathCAD blog turns 3 years old. Head over and take a look at their 5 most popular posts.  If you can’t afford Mathcad, why not try the free Mathcad clone, SMath Studio which saw a new release this month.
  • Geogebra now has a blog.  The June newsletter is also worth checking out.  Wikipedia tells us that ‘GeoGebra is an interactive geometry, algebra, and calculus application, intended for teachers and students.’
  • Version 0.97 of Eureqa/Formulize has been released.  If you don’t know what this is, take a look at the video.  In a nutshell, you plug in data and it figures out the formula that best models it.
June 21st, 2012 | Categories: general math, mathematica | Tags:

In a recent tweet, Cliff Pickover told the world that 
7272727272727272727272727272727272727272727272727272727272727272727272727272727272727272727­27272727 is prime. That’s a nice looking prime and it took my laptop 1/100th of a second to confirm using Mathematica 8.

PrimeQ[727272727272727272727272727272727272727272727272727272727272727\
272727272727272727272727272727272727] // AbsoluteTiming

Out[1]= {0.0100000, True}

Can anyone else suggest some nice looking primes?

June 19th, 2012 | Categories: general math | Tags:

It is possible to write many integers as the sum of the cubes of three integers.  For example

99 = (-5)^3 + 2^3+ 6^3

A more complicated example is

91 = (-67134)^3 + (-65453)^3+(83538)^3

Your task is to find integers x,y and z such that

33 = x^3 + y^3 + z^3

Hint: This is not a trivial problem and will (probably) require the use of a computer. Extra credit given if you also post your source code.

Update 3: If you are serious about attempting to crack this problem (and some people seem to be, judging from the comments), the following reference may be of help.  The bibliography includes other jumping off points for this problem.

  • Michael Beck, Eric Pine, Wayne Tarrant and Kim Yarbrough Jensen: New integer representations as the sum of three cubes Math. Comp. 76 (2007), 1683-1690 (Link)

Update 2: This problem is, in fact, a long-standing unsolved problem in number theory.  If my memory serves me correctly, it is mentioned in the book Unsolved Problems in Number Theory

Update 1: 33 is very VERY difficult so why not use 16 as a warm up problem. MUCH smaller search space.

June 14th, 2012 | Categories: Making MATLAB faster, matlab, programming, tutorials | Tags:

I recently got access to a shiny new (new to me at least) set of compilers, The Portland PGI compiler suite which comes with a great set of technologies to play with including AVX vector support, CUDA for x86 and GPU pragma-based acceleration.  So naturally, it wasn’t long before I wondered if I could use the PGI suite as compilers for MATLAB mex files.  The bad news is that The Mathworks don’t support the PGI Compilers out of the box but that leads to the good news…I get to dig down and figure out how to add support for unsupported compilers.

In what follows I made use of MATLAB 2012a on 64bit Windows 7 with Version 12.5 of the PGI Portland Compiler Suite.

In order to set up a C mex-compiler in MATLAB you execute the following

mex -setup

which causes MATLAB to execute a Perl script at C:\Program Files\MATLAB\R2012a\bin\mexsetup.pm.  This script scans the directory C:\Program Files\MATLAB\R2012a\bin\win64\mexopts looking for Perl scripts with the extension .stp and running whatever it finds. Each .stp file looks for a particular compiler.  After all .stp files have been executed, a list of compilers found gets returned to the user. When the user chooses a compiler, the corresponding .bat file gets copied to the directory returned by MATLAB’s prefdir function. This sets up the compiler for use.  All of this is nicely documented in the mexsetup.pm file itself.

So, I’ve had my first crack at this and the results are the following two files.

These are crude, and there’s probably lots missing/wrong but they seem to work.  Copy them to C:\Program Files\MATLAB\R2012a\bin\win64\mexopts. The location of the compiler is hard-coded in pgi.stp so you’ll need to change the following line if your compiler location differs from mine

my $default_location = "C:\\Program Files\\PGI\\win64\\12.5\\bin";

Now, when you do mex -setup, you should get an entry PGI Workstation 12.5 64bit 12.5 in C:\Program Files\PGI\win64\12.5\bin which you can select as normal.

An example compilation and some details.

Let’s compile the following very simple mex file, mex_sin.c, using the PGI compiler which does little more than take an elementwise sine of the input matrix.

#include <math.h>
#include "mex.h"

void mexFunction( int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[] )
{
    double *in,*out;
    double dist,a,b;
    int rows,cols,outsize;
    int i,j,k;

    /*Get pointers to input matrix*/
    in = mxGetPr(prhs[0]);
    /*Get rows and columns of input*/
    rows = mxGetM(prhs[0]);
    cols = mxGetN(prhs[0]);

    /* Create output matrix */
    outsize = rows*cols;
    plhs[0] = mxCreateDoubleMatrix(rows, cols, mxREAL);
    /* Assign pointer to the output */
    out = mxGetPr(plhs[0]);

    for(i=0;i<outsize;i++){
        out[i] = sin(in[i]);
    }

}

Compile using the -v switch to get verbose information about the compilation

mex sin_mex.c -v

You’ll see that the compiled mex file is actually a renamed .dll file that was compiled and linked with the following flags

pgcc -c -Bdynamic  -Minfo -fast
pgcc --Mmakedll=export_all  -L"C:\Program Files\MATLAB\R2012a\extern\lib\win64\microsoft" libmx.lib libmex.lib libmat.lib

The switch –Mmakedll=export_all is actually not supported by PGI which makes this whole setup doubly unsupported! However, I couldn’t find a way to export the required symbols without modifying the mex source code so I lived with it.  Maybe I’ll figure out a better way in the future.  Let’s try the new function out

>> a=[1 2 3];
>> mex_sin(a)
Invalid MEX-file 'C:\Work\mex_sin.mexw64': The specified module could not be found.

The reason for the error message is that a required PGI .dll file, pgc.dll, is not on my system path so I need to do the following in MATLAB.

setenv('PATH', [getenv('PATH') ';C:\Program Files\PGI\win64\12.5\bin\']);

This fixes things

>> mex_sin(a)
ans =
    0.8415    0.9093    0.1411

Performance

I took a quick look at the performance of this mex function using my quad-core, Sandy Bridge laptop. I highly doubted that I was going to beat MATLAB’s built in sin function (which is highly optimised and multithreaded) with so little work and I was right:

>> a=rand(1,100000000);
>> tic;mex_sin(a);toc
Elapsed time is 1.320855 seconds.
>> tic;sin(a);toc
Elapsed time is 0.486369 seconds.

That’s not really a fair comparison though since I am purposely leaving mutithreading out of the PGI mex equation for now.  It’s a much fairer comparison to compare the exact same mex file using different compilers so let’s do that.  I created three different compiled mex routines from the source code above using the three compilers installed on my laptop and performed a very crude time test as follows

>> a=rand(1,100000000);
>> tic;mex_sin_pgi(a);toc              %PGI 12.5 run 1
Elapsed time is 1.317122 seconds.
>> tic;mex_sin_pgi(a);toc              %PGI 12.5 run 2
Elapsed time is 1.338271 seconds.

>> tic;mex_sin_vs(a);toc               %Visual Studio 2008 run 1
Elapsed time is 1.459463 seconds.
>> tic;mex_sin_vs(a);toc
Elapsed time is 1.446947 seconds.      %Visual Studio 2008 run 2

>> tic;mex_sin_intel(a);toc             %Intel Compiler 12.0 run 1
Elapsed time is 0.907018 seconds.
>> tic;mex_sin_intel(a);toc             %Intel Compiler 12.0 run 2
Elapsed time is 0.860218 seconds.

PGI did a little better than Visual Studio 2008 but was beaten by Intel. I’m hoping that I’ll be able to get more performance out of the PGI compiler as I learn more about the compilation flags.

Getting PGI to make use of SSE extensions

Part of the output of the mex sin_mex.c -v compilation command is the following notice

mexFunction:
     23, Loop not vectorized: data dependency

This notice is a result of the -Minfo compilation switch and indicates that the PGI compiler can’t determine if the in and out arrays overlap or not.  If they don’t overlap then it would be safe to unroll the loop and make use of SSE or AVX instructions to make better use of my Sandy Bridge processor.  This should hopefully speed things up a little.

As the programmer, I am sure that the two arrays don’t overlap so I need to give the compiler a hand.  One way to do this would be to modify the pgi.dat file to include the compilation switch -Msafeptr which tells the compiler that arrays never overlap anywhere.  This might not be a good idea since it may not always be true so I decided to be more cautious and make use of  the restrict keyword.  That is, I changed the mex source code so that

double *in,*out;

becomes

double * restrict in,* restrict out;

Now when I compile using the PGI compiler, the notice from -Mifno becomes

mexFunction:
     23, Generated 3 alternate versions of the loop
         Generated vector sse code for the loop
         Generated a prefetch instruction for the loop

which demonstrates that the compiler is much happier! So, what did this do for performance?

>> tic;mex_sin_pgi(a);toc
Elapsed time is 1.450002 seconds.
>> tic;mex_sin_pgi(a);toc
Elapsed time is 1.460536 seconds.

This is slower than when SSE instructions weren’t being used which isn’t what I was expecting at all! If anyone has any insight into what’s going on here, I’d love to hear from you.

Future Work

I’m happy that I’ve got this compiler working in MATLAB but there is a lot to do including:

  • Tidy up the pgi.dat and pgi.stp files so that they look and act more professionally.
  • Figure out the best set of compiler switches to use– it is almost certain that what I’m using now is sub-optimal since I am new to the PGI compiler.
  • Get OpenMP support working.  I tried using the -Mconcur compilation flag which auto-parallelised the loop but it crashed MATLAB when I ran it. This needs investigating
  • Get PGI accelerator support working so I can offload work to the GPU.
  • Figure out why the SSE version of this function is slower than the non-SSE version
  • Figure out how to determine whether or not the compiler is emitting AVX instructions.  The documentation suggests that if the compiler is called on a Sandy Bridge machine, and if vectorisation is possible then it will produce AVX instructions but AVX is not mentioned in the output of -Minfo.  Nothing changes if you explicity set the target to Sandy Bridge with the compiler switch tp sandybridge64.

Look out for more articles on this in the future.

Related WalkingRandomly Articles

My setup

  • Laptop model: Dell XPS L702X
  • CPU: Intel Core i7-2630QM @2Ghz software overclockable to 2.9Ghz. 4 physical cores but total 8 virtual cores due to Hyperthreading.
  • GPU: GeForce GT 555M with 144 CUDA Cores.  Graphics clock: 590Mhz.  Processor Clock:1180 Mhz. 3072 Mb DDR3 Memeory
  • RAM: 8 Gb
  • OS: Windows 7 Home Premium 64 bit.
  • MATLAB: 2012a
  • PGI Compiler: 12.5
June 12th, 2012 | Categories: general math, just for fun | Tags:

A friend recently asked me how to optimally tile the shape below on the plane such that no two instances touch.

How to tile this?

Off the top off my head I suggested considering the minimal enclosing circle and then pack hexagonally but he thinks one could do better. I thought I’d ask on here to see what others might come up with.

June 9th, 2012 | Categories: matlab | Tags:

As the resident MATLAB support guy (among other things) at The University of Manchester, I often get asked which language MATLAB is written in.  Many people seem to argue over whether or not it is Fortran or C with the prevailing wisdom being ‘It was originally written in Fortran for the free version 1 and then was re-written in C when it went commercial’.

Well, I am not sure about the history but looking at moden MATLAB, the question should be which languages, rather than which language!  The list I have so far is

  • C (many built in compiled mex functions are written in C)
  • C++ (MATLAB makes use of the Boost C++ libraries..thanks to M in the comments for this one)
  • CIL (Common Intermediate Langauge, used to be called MSIL, – The windows version of MATLAB uses this for various .NET stuff.  Thanks to ‘pmcs’ in the comments for this one)
  • NVidia CUDA (Routines in the GPU part of the parallel computing toolbox)
  • Bash shell script (On Linux, the startup ‘binary’ is a shell script)
  • Fortran (MATLAB uses the MKL and I’m fairly sure this is written in Fortran)
  • Java (Many of  the ticks in Yair Altman’s excellent book, Undocumented Secrets of MATLAB-Java Programming make use of the Java elements in MATLAB
  • MATLAB (many MATLAB functions are written in .m code)
  • Perl (Many mex-related scripts are written in Perl)
  • Windows batch files (I’ve seen some simple .bat files as part of the mex machinery)