This post is an index page for reading the Parallel Programming blog posts.

I made a small change to the Task Filtering code I uploaded a few weeks ago.  The new code has better memory performance and, most importantly has more stable memory usage which means it can actually run very large examples.  Here is the new version of the code:

FilterCombPara := module( )
    local ModuleApply,
            doSplit,
            splitCombs,
            makeNewPrefix,
            lessThanX,
            filterCombs;

    lessThanX := proc( x, i ) x<=i; end;

    doSplit := proc( i::integer, prefix::set(posint), rest::set(posint),
                                                k::posint, filter::appliable, $ )
        splitCombs( prefix union {i}, remove( lessThanX, rest, i ), k-1, filter );
    end;

    splitCombs := proc( prefix::set(posint), rest::set(posint), k::posint,
                                                                filter::appliable, $ )
        if ( numelems( rest ) < k ) then
            NULL;
        elif ( k = 1 ) then
            filterCombs( prefix, rest, filter );
        else
            op( Threads:-Map( doSplit, rest, prefix, rest, k, filter ) );
        end;
    end;

    makeNewPrefix := proc( i, prefix ) { i, op( prefix ) } end;
    filterCombs := proc( prefix::set(posint), rest::set(posint), filter::appliable, $ )
        local i, f;

        op(select( filter, map( makeNewPrefix, rest, prefix ) )):
    end;

    ModuleApply := proc( n::posint, k::posint, filter::appliable, $ )
        [ splitCombs( {}, {seq( i,i=1..n )}, k, filter ) ];
    end;

end:

This code has the small mapping functions as module members instead of declared inline.  This means that less memory is churned as this code is excuted.  For a long runs, this helps keeps the memory stable.

As an example, I ran the following example:

> CodeTools:-Usage( FilterCombPara( 113,7, x->false ) );

memory used=17.39TiB, alloc change=460.02MiB, cpu time=88.52h, real time=20.15h
                                                  []

It used 88 CPU hours to run, but only 20 hours of real time (go parallelism!)  It used 17 Terabytes of memory, but only allocated 500 M.  This example is pretty trival, as the filter returned false for all combinations, so it did not collect any matches during the run.  However as long as the number of matches is small, that shouldn't be an issue.  If the number of matches is too large to fit in memory, then this code may need to be modified to write the matches out to disk instead of trying to hold them all in memory at once.

Darin

-- Kernel Developer Maplesoft

FilterComb.mw

This blog post is a response to a post on MaplePrimes.  MaplePrimes user wkehowski asked how the Task Model could be used to filter combinations.  The basic problem is formalated like this:  We want a function, I'll call it FilterComb, that accepts positive integers...

For the last few releases of Maple, we have been adding features to take advantage of multi-core processors.  Most of this work has focused on particular algorithms or on tools that allow users to author their own parallel code.  Although this was very useful for those users who were able to use those tools, many users did not see a performance improvement.  To help all users we need to integrate parallelism into the core algorithms of Maple.  In Maple 17 we have taken the first step towards general parallelism in the core algorithms by implementing a parallel garbage collector.

This post will explain how to configure the compiler and other tools that will be necessary for you to build the External Calling examples that will come in later posts.  This is an advanced topic and so this post is fairly complex.

First, I am going to be using the compilers via the command line, so you will need to familarize yourself with the terminal program on your particular OS.  You'll have to do this for yourself, but here are a few starting points:

Windows

Apple

I am going to assume that Linux and Solaris users are familar with using the terminal.

For Linux, Apple and Solaris, I am going to use gcc as the compiler.  For Linux you should use your distribution's package management system to get it, for Apple you need to install Xcode and for Solaris, well, gcc is probably already installed or you'll want to talk to you sys admin to have it installed (or if you are your own sys admin, you probably know how to install gcc for yourself).  For Windows, you need to install the Windows Software Development Kit.  If you already have a copy of Visual Studio C++ (Express or Professional) installed, then you already have these tools.

I am also going to use the "make" program to manage the building of the examples, thus you will need to install a version of make as well (you won't need to learn how make works unless you want to modify the examples).  I will be using gnu make, which should be easy to install on Linux and Solaris (similar to how you installed gcc) and it is included in Xcode for Apple.  For Windows, use this:

http://gnuwin32.sourceforge.net/packages/make.htm

Installing 32 bit make on 64 bit windows is fine.

Now you'll need to launch a terminal.  For Linux, Apple and Solaris this should be easy, on Windows go to the Windows SDK folder (or Windows Visual Studio folder) on the Start menu, there should be an icon for Windows SDK Command Prompt.  Click that to launch the terminal.  This version of the terminal has the environment configured to run the compiler.

On Windows you'll also have to add the location you installed make to your path, which can be done on 32 bit windows like this:

path=%PATH%;C:\Program Files\GnuWin32\bin

and on 64 bit Windows like this:

path=%PATH%;C:\Program Files (x86)\GnuWin32\bin

assuing you used the default install location for make.

You can test this by running "make" in the terminal.  If everything is set up correctly, make should run but not find a Makefile and it will raise an error.  If the path is not set properly, make won't be found you'll get a message saying that.

Path not set properly:

C:\Program Files\Microsoft SDKs\Windows\v7.1>make
'make' is not recognized as an internal or external command,
operable program or batch file.

Set the path:

C:\Program Files\Microsoft SDKs\Windows\v7.1>path=%PATH%;"C:\Program Files (x86)
\GnuWin32\bin"

Make is now found, but there is no makefile in the current directory

C:\Program Files\Microsoft SDKs\Windows\v7.1>make
make: *** No targets specified and no makefile found.  Stop.

As a final test, I've attached a small example (test.zip) that contains a Makefile and a simple source file.  If you extract the files to a new directory, go to that new directoy in the terminal and run make (with make added to the path as described above) it should build an executable (test or test.exe).  You can run the executable by executing "test" on the command line.

By default the Makefile is configured for Windows, so Windows users won't need to change it, however other users will need to comment out the

WINDOWS=true

line in Makefile by changing it to

#WINDOWS=true

I know this is a little confusing, especially if you are not familar with the command line interface, therefore I encourage you post replies if you have problems.  Hopefully we will be able to answer your questions.  Once everyone has figured out how to get this simple example to compile and run on their system, the upcoming external calling examples will be (relatively) easy.

Good Luck!

Darin