dohashi

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

I've had a few request to provide some more information on External Calling, so I thought I would make a few posts about it. This first post will be a high level description of External Calling and how it works, with examples coming later. As External Calling is an advanced topic, I am going to assume you know how to compile a shared library and are generally familiar with the C language. Although this first post won't require any real programming knowledge.

What is External Calling?

External Calling is the name for Maple's ability to connect to and call functions from other programming languages. Maple uses this for various reasons. We have written our own libraries in C, C++ and Java to solve particular problems. We partner with various labs around the world who have developed code, often in languages like C or C++, so external calling is used to interface with their code. We also connect to high performance libraries like NAG and BLAS to provide those high performance routines in Maple. Of course, you can use External Calling to connect Maple to your code as well.

Although Maple can call various programming languages, the most common languages we connect to are C and C++, and those are the languages I am going to focus on.

How does it work?

In Maple, you call ?define_external or use the ?ExternalCalling package. Both these methods take a description of the function that you want to call and returns a Maple procedure. Normally you would assign the procedure to a name and then call the externally defined function just like any other Maple procedure.

There are a couple different ways to use define_external to connect to a shared library, the differences are mostly concerned with how the parameters given in Maple are converted to parameters used in the external function.

• Wrapperless external calling. With wrapperless external calling, Maple calls a function implemented in the shared library by automatically converting the values given in Maple into valid types for the external function.
• Generated wrappers: With generated wrappers, Maple automatically generates a small C library that handles conversions from Maple values to the values used in the external function. Using generated wrappers allows Maple to handle more data types, like call back procedures.
• Custom wrappers: A custom wrapper is a C function that you write yourself. This function accepts arguments as Maple data structures and returns a Maple data structure. You are responsible for converting the Maple data structures into whatever forms you need and converting your computed value back into a Maple data structure. Maple provides the External Calling API to assist in working with Maple from the externally defined function.

The first two forms of external calling are the easiest to do, however they are also the most limited. Internally we exclusively (I think) use the third, custom wrapper, form of external calling. That is the form I am going to talk about.

Custom Wrapper

The name "custom wrapper" is a bit of a misnomer. The function that you write does not need to "wrap" anything, it can implement anything you want. As long as you can convert the result into a Maple data structure, you can pass it back into Maple. In fact Maple also supports returning generic data, via the ?MaplePointer routines, but that is a more complex topic for a later blog post.

Your external function is simply a C function with the following calling convention:

ALGEB CustomWrapper( MKernelVector kv, ALGEB args )

ALGEB is the C data type that represents a Maple data structure. The MKernelVector is a data structure that acts as an intermediary between your external calling routines and the Maple engine. You will need to pass this structure back into the External Calling API functions. Both of these types, plus the External Calling API functions are defined in a header, maplec.h, that needs to be included in your code. I will provide more details when I provide examples.

The External Calling API

The External Calling API is a set of functions that we make available for working with the Maple Engine from external code. Maple also allows third party applications to load the Maple engine as a shared library, we call this ?OpenMaple. The External Calling functions are also available in OpenMaple, so you will often see OpenMaple used in the Maple help pages. Most functions can be used in both OpenMaple and External Calling, except for a few that are OpenMaple specific and involve starting and stopping the Maple Engine.

Maple's help system documents all the External Calling functions so you can see what is available. There is an overview of the external calling functions on this page, ?ExternalCalling,C,API. Briefly, however there are functions for converting Maple types to C and back, creating and interacting with Maple data structures (list, set, rtable, table, string, etc), creating and interacting with Maple language elements (names, procedures, etc), printing to the Maple interface, memory allocation, evaluating Maple statements and raising exceptions. There is even a C interface to the Task Programming Model.

Next Time...

In my next post I will provide some examples of using the External Calling API to actually do stuff in an externally defined procedure.  However, I am going to spend some time trying to figure out the easiest way for you to get the tools you'll need to be able to develop externally defined functions yourself, so my next post might take a bit of time.

Darin

Although I mostly post about parallel programming, my background is in algorithms and data structures.  I have a soft spot for sorting algorithms.  It probably started when I did some research into adaptive sorting as part of my coursework.  Anyway, someone added sound to visualizations of different sorting algorithms.  I'm not sure if it really helps explain the algorithms any better, but it does make them more interesting to watch.

http://www.geek.com/articles/geek-cetera/sorting-algorithms-quite-boring-until-you-add-sound-effects-20100819/

Darin

Consider the following C code:

It has been a while since my last post, mostly because of a combination of getting Maple 14 ready to ship and a lack of meaty topics to write about. I am trying to get back into the habit of posting more regularly. You can help me achieve my goal by posting questions about parallel programming. I'll do my best to answer. However for now, I'll give a brief overview of the new parallel programming features in Maple 14.

A new function has been added to the Task Programming Model. The Threads:-Task:-Return function allows a parallel algorithm implemented on top of the Task Programming Model to perform an early bail out. Lets imagine that you have implemented a parallel search. You are looking for a particular element in a large set of data. Using the Task Programming Model, you've created a bunch of tasks, each searching a particular subset of the data. However one of the first tasks to execute finds the element you are looking for. In Maple 13, there was no built in way of telling the other tasks that the result have been found and they they should not execute. In Maple 14, the Return function allows one task to specify a return value (which will be returned from Threads:-Task:-Start) and signal the other tasks that the algorithm is complete and that additional tasks should not be executed. Tasks that are already running will still run to completion, but tasks that have not started executing will not be started.

You may have noticed that there is a race condition with Return. What happens if two tasks both call Return in parallel? Only one of the values will become the value that is passed to Threads:-Task:-Start. I suppose I could say the "first" value is the one that is used, but really, what does that mean? If you call Return, then the value passed to Return should be an acceptable result for the algorithm.  If you call Return more than once, any of those values should be valid, thus it shouldn't matter which one becomes the return value.  That said, the Return function does give some feedback. In the task that succeeds in having its value accepted, Return will return true. In all other tasks that call Return, it will return false. This allows the code to know if a particular result was or was not accepted.

Maple 14 also adds the Task Programming Model to the C External Calling API. This means that you can write your algorithms in C and make use of the Task Programming Model. The C API is similar to the Maple API, with a few differences. In particular, you need to create each child task individually, instead of as a single call to Continue, as you would in Maple. As well, because it is C code, you need to worry about a few details like memory management that are handled automatically in Maple.  Using External Call is fairly advanced, so I won't go into too much detail here.  If you'd like to see more details of using the Task Programming Model in External Calling, I can write a seperated post dedicated to that.

As with every release of Maple, we spent some time trying to make our existing functionality faster and more stable. For parallel programming, we reduced the overhead of using the Task Programming Model, as well as reducing the locking in the kernel (which should help improve parallelism). Of course many bugs have been fixed, which should make parallel programming more reliable in Maple 14.

Amdahl's Law is a formula for determining the theoretical speed up when parallelizing a function. For example, imagine we wanted to parallelize a function that spends 90% of its time in one algorithm. If there is a parallel version of that algorithm, how much faster would the entire function run with 2, 4 or more cores?

Consider the following situation.  A thread acquires a mutex, then enters a critical section.  However when executing in the critical section, the thread access a memory location.  If that memory location is not in cache, the thread will wait for a few hundred cycles.  If accessing the memory location causes a page fault (the memory was swapped out to disk), the thread may need to wait a few million cycles.  However while this thread is waiting, it is still holding the mutex.  This means that other threads will not be able to enter the critical section, and may

It has been a while since my last post.  I'm sorry about that, but I have been busy trying to the fix bugs reported as part of the Maple Beta program.  I'm also running low of good parallel programming topics.  So, as always, if you have topics you'd like to hear about (or hear more about) feel free to ask.

Today I am going to post a brief note about a blog that I find quite interesting.

Cliff Click Jr's Blog: http://blogs.azulsystems.com/cliff/

I realized the other day that I had not mentioned the Threads:-Add, Threads:-Map, Threads:-Mul and Threads:-Seq functions.  These are parallel implementations of the standard Maple functions, add, map, mul and seq.  They expect the sam

This post is a quick book review of

The Art of Multiprocessor Programming
by Maurice Herlihy and Nir Shavit

Yesterday I attended a lecture by Fran Allen, as part of the "David R. Cheriton School of Computer Science, University of Waterloo, Distinguished Lecture Series".  Allen worked a IBM Research from 1957 to 2002, she was awarded the ACM's Turing Award in 2006.  Here is her biography from Wikipedia (let's hope it is accurate). 

Aside from some technical issues (why can't a room full of computer science professors and students successfully attach a laptop to a projector?) the talk was quite interesting.  There were two main sections, the first discussed Allen's career at IBM and the second was about the future of computer science.  Allen's work at IBM focused mostly on compilers and high performance computing.  She made a few interesting comments about the importance of high performance computing.  For example, one of the systems she worked on was designed and used to model the detonations of nuclear weapons.  The development of this system ended the need for the United Stated to perform actual test detonations.

Atomic operations are CPU instructions that are guaranteed to execute in a single CPU cycle. This means that the operation is guaranteed to complete without being interrupted by the actions of another thread. Although this may not sound too exciting, careful programming using these instructions can lead to algorithms and data structures that can be used in parallel without needing locks. Maple currently does not support atomic operations, however they are an interesting tool and are used in the kernel to help improve Maple's parallelism in general.

I recieved this comment on an older post of mine, and I was going to post a reply, but I noticed my reply was pretty long, and I was also missing a post for last friday, so I figured I'd cheat and make the reply a blog post of its own.

In this post I'll take a closer look at the ways in which Maple code can be thread unsafe. If you have not already seen my post on Thread Safety, consider reading that post first. As a brief review, a procedure is thread safe if it works correctly when run in parallel.

The most obvious way in which procedures can be thread unsafe is if they share data without synchronizing access (using a Mutex, for example). So how can two threads share data?

I am going to wander away from parallel programming in Maple, to talk about GPU programming. However I will show an example of connecting Maple to a CUDA accelerated external library, so that's close enough.  This post is not intended to be a tutorial on CUDA or OpenCL programming, but an introduction to how the technology works.