Tabard on Sourceforge!

I’ve created a project on sourceforge for Tabard, here’s the Tabard project page and there’s also a mailing list for development and another one with automated mail-outs of CVS commits. I would love to have more people testing the code and giving feedback and I hope this is a starting point for that.

For testing

game of life
matrix arithmetic
nreserve on 100-element list 2000 times for accuracy
swi-prolog benchmarks

Testing: Examples of/for Performance Evaluation

Update: I’m now considering using this other programs for testing too.

Inductive Logic Programming system Aleph (link)

• a branch of machine learning that synthesises logic programs using other logic programs as input.
• Used by Jan Wielemaker (SWI-Prolog) to show speedup with threads on SMP systems.

Benchmark suite by Fernando Pereira (link)

• Used by Jan Wielemaker (SWI-Prolog) for comparing the single threaded to the multi-threaded version.
• Its purpose is to try to identify strengths and weaknesses in the basic engine of a Prolog system.
• “Also, I must say that I have relatively little faith on small benchmark programs. I find that performance (both time and space) on substantial programs, reliability, adherence to de facto standards and ease of use are far more important in practice. I’ve tried several Prolog systems that performed very well on small benchmarks (including mine), but that failed badly on one or more of these criteria.“

Dining Philosophers (link)

• Classic multi-process synchronization problem,
• It’s a toy program,
• More to do with concurrency that distributed/parallel computing.

Where it will be speedup for sure:

1) serialized program that now becames distributed.
2) multi-threaded program that distributed executes faster.

Threads in Linux

When we talk about threads in Linux we’re talking about one of two things:

1) LinuxThreads - an implementation of the Posix 1003.1c (discussion saying they aren’t really POSIX) thread package for Linux, now obsolete and being replaced by a library called NPTL (Native POSIX Thread Library). Unlike other implementations of Posix threads for Linux, LinuxThreads provides kernel-level threads: threads are created with the new clone() system call and all scheduling is done in the kernel. The main strength of this approach is that it can take full advantage of multiprocessors. It also results in a simpler, more robust thread library, especially w.r.t. blocking system calls.

2) Native POSIX Thread Library (NPTL)

• Threads use and exist within these process resources, yet are able to be scheduled by the operating system and run as independent entities largely because they duplicate only the bare essential resources that enable them to exist as executable code.
• This independent flow of control is accomplished because a thread maintains its own:

  * Stack pointer
  * Registers
  * Scheduling properties (such as policy or priority)
  * Set of pending and blocked signals
  * Thread specific data.

• So, in summary, in the UNIX environment a thread:

  * Exists within a process and uses the process resources
  * Has its own independent flow of control as long as its parent process exists and the OS supports it
  * Duplicates only the essential resources it needs to be independently schedulable
  * May share the process resources with other threads that act equally independently (and dependently)
  * Dies if the parent process dies - or something similar
  * Is “lightweight” because most of the overhead has already been accomplished through the creation of its process.

• Because threads within the same process share resources:

  * Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads.
  * Two pointers having the same value point to the same data.
  * Reading and writing to the same memory locations is possible, and therefore requires explicit synchronization by the programmer.

GNU Prolog and POSIX Threads

I was trying to play with gprolog+pthreads to run multiple Prolog engines. As Daniel Diaz explains, it doesn’t seem possible:

“The functions Start_Prolog() and Stop_Prolog() shoud be called only once since Stop_Prolog does not free allocated stacks (will be done in a next version). Try to use Reset_Prolog() (which reset all Prolog stacks, but NOT dynamic predicates (thus asserted clauses remain after a Reset_Prolog).”

Joseph Benden also explains:

“This is what I am doing with success:

On Linux: I am using multiple process (a preforking) server, and after the accept and fork, then call Start_Prolog.

On Windows: I have the GNU Prolog wrapped into a DLL. On the DLL_PROCESS_ATATCH I call Start_Prolog. Then each thread waits on a master critical section before calling any prolog routines (inside the dll, on each call).

I do not believe GNU Prolog is thread-safe because it uses global memory space for its’ stacks. If you only ever read the memory, you should be safe, but writing is a different story. One could put mutex locks in the term reading and writing functions. But that would be a big project, and would slow the prolog down. GNU Prolog would have to use thread-local stacks, but that would require a re-write of the entire prolog, and would make multiple thread unable to access other threads stacks.

To get the same performance under windows as linux, load multiple instances of the DLL and marshal into them. “

The pthread library gets us two things (essentially) - a function to create threads, which you could pretty easily replace with clone(), and other functions to handle mutexes and conditions. If you replace pthread_create with clone you have a lot of work to do to implement the locking stuff… Of
course, if you’re willing to do this work, then more power to you.

Dining Philosophers Problem

Update: I have made available my Prolog implementation as this URL.

It’s time to start testing with real problems. The dining philosophers is a classic problem for this kind of testing since it involves thread/process concurrency and synchronization. It’s all around in the literature.

So, I’m now looking for a clean and elegant Prolog implementation of a solution to the dining philosophers problem. I’ve searched the web for something meaningful but since I wasn’t able to find anything in Prolog I’ve rolled out my own implementation.

There are several solutions proposed to solve the dining philosophers. The easiest one I found consisted of having each chopstick be a monitor (mutex), and each philosopher will attempt to pick up the chopstick on his left first, then right, then eat, then put down the right one, and then put down the left one.

This is prone to deadlock, although on this system you really won’t ever see it because of the granularity of timeslicing between threads. The only time that this solution is a problem is if a philosopher’s thread gets preempted between picking up the first and the second mutex. That doesn’t really ever happen here, so it looks like it works just fine.

I’ve tested with SWI-Prolog 5.2.13 multi-threaded.

Ditching SYS V Message Queues

The one-thread-per-VP prototype is basically finished. I’ve used one message-queue by thread and the PID to access it. I didn’t use any mutual exclusion mechanisms yet but I’ll probably need them if we decide to go this way because msgget(2) man page says there is currently no intrinsic way for a process to ensure exclusive access to a message queue.

Suggested improvements include the use of a shared-memory structure instead of the SYS V message queues. This will definitely include the use of user-level mutexes or SYS V semaphores and will be a lot simplier too. I’ve created a svn branch where I’ll ditch the use of them in favor of my own queues.

Plans to expand the cluster are in the way. I have to look for fun problems to use in testing.

Message Queue to communicate between processes in different machines

I was thinking about either it was possible to use a single SYS V message queue to communicate between processes that reside in different machines in a scenario where the queue (the ftok()’s file) resides in a NFS shared location. Message queues where made to use in local IPC but since all the machines have access to it on the filesystem it would make some sense if they could use it. According to my tests it is not possible. Although the file resides in a NFS shared location, remember that as far as you can tell there is no usable message queue on the other machines. Note: could we use a shared file to communicate?

Thread Communication

The API will be based on the existing SWI-Prolog’s Thread communication API, that uses message queues. This will allow communication between any two threads.

Local Communication (Two threads that reside on the same processing node)

Prolog threads can exchange data using dynamic predicates, database records, and other globally shared data. These provide no suitable means to wait for data or a condition as they can only be checked in an expensive polling loop. Message queues provide a means for threads to wait for data or conditions without using the CPU.

Each thread has a message-queue attached to it that is identified by the thread. Additional queues are created using message_queue_create/1.

Remote Communication (Two threads that reside on different processing nodes)

If one thread reside on node X and the second in node Y then:
- send msg to node Y via Madeleine.
- thread listener on node Y will proxy message to thread message queue.

I’ll be mainly using SYS V IPC, more precisely message queues and eventually semaphores.

Explicit message queues are designed with the worker-pool model in mind, where multiple threads wait on a single queue and pick up the first goal to execute. I don’t know if the user will need to protect the queue against concurrent access (two or more threads reading from the queue at the same time) or if the SYS V message queues will take care of that.

If it will involve protecting the queues, then the handling of user-level mutexes or semaphores might get handy. A mutex is a MUTual EXclusive device and the difference between a mutex and a semaphore (as my good friend Pedro told me) is that a mutex is only for mutual exclusion and semaphores can be used for more complicated stuff. For example, with a mutex protecting a resource, only one process at a time can access it. With semaphores (depending on the implementation, of course), you can have two, or three, or as much processes as you like accessing the resource at a time.

What to do next

Last thing I did was to start a prototype that consisted on having 1 thread per VP. The program starts a Prolog thread in each VP and initialization/1 gets called on every node. I’ve explained this on the previous post.

Now, for the 1 thread/VP prototype is considered finished I need to be able to:
- kill a thread on a VP
- know what threads are running and where (done)
- be kill resistent
- create msg queues (to communicate with threads) - maybe use SYS V IPC since now I’m using clone(2).
- read from msg queues
- write to msg queues

The switch in the lab is dead. I had to replace it with one of my own.