Has someone already created a unit for light weight threads?

Something like: Create a group of 4 threads named 0,1,2,3 and execute a procedure/method?

Mattias

Mattias Gaertner wrote

Has someone already created a unit for light weight threads? Something like: Create a group of 4 threads named 0,1,2,3 and execute a procedure/method?

for i := 0 to 3 do
   Handle[i] := tThreadId(BeginThread (Func {tThreadFunc},
                                       @FuncArg[i]));
for i := 0 to 3 do
   Result[i] := WaitForThreadTerminate (Handle[i], 0);

Mattias Gaertner wrote

Has someone already created a unit for light weight threads?

I don't know much on the subject, but Is TThread heavy? What are the disadvantages of using it?

thanks,

Felipe Monteiro de Carvalho wrote

On Dec 13, 2007 7:55 PM, Mattias Gaertner

> Has someone already created a unit for light weight threads? I don't know much on the subject, but Is TThread heavy? What are the disadvantages of using it?

No, TThread is either heavy or middle-weight, according to the definitions at

http://whatis.techtarget.com/definition/0,,sid9_gci814910,00.html

depending on the actual implementation. On Linux 2.4 it would be heavyweight, on Win32 systems and Linux kernel 2.6+ it would be middle-weight. (Well, the context switching times mentioned there are not really up to date, usually not even context switching between processes takes several milliseconds, or "thousands of microseconds" as they liked to say.)

But actually, I don't know how much more "light" a thread can take:

"When all context and thread operations are exposed at the user level, each application needs only the minimal amount of context saved with it, so that context switching can be reduced to tens of microseconds. Therefore, user-level threads are considered lightweight threads."

Which is something that you simply never want to do outside of bare-metal embedded systems. And even there you'd normally wrap your threading implementation in something more "middle-weight" before you expose that API to the user.

Vinzent.

I think some thread pool class is more important, it would be basically the same as above

for i := 0 to 3 do
  Handle[i] := TTask(ThreadPool.QueueTask(Func {tThreadFunc},
                                        @FuncArg[i]));
for i := 0 to 3 do
  Result[i] := WaitForTask(Handle[i], 0);

but the threads are already idling and taking their tasks from a queue. It allows also scaling with the cores: the more cores you have, the more threads you put into your pool.

Mattias Gaertner wrote

Has someone already created a unit for light weight threads?

What do you mean by "light weight threads" ? How can it get "lighter" than TThread, that offers close to no built-in "comfort"-functionality ?

-Michael

Yes, that would be something nice and useful, indeed.

Vinzent.

What do you mean by "light weight threads" ? How can it get "lighter"

than TThread,

that offers close to no built-in "comfort"-functionality ?

TThread (and BeginThread) are quite heavy for small tasks, not because of the Pascal code, but because of the OS overhead involved in creating, starting and cleaning up a thread.
Florian's ThreadPool suggestion is what "lightweight" threads could be about.

Also a construct like

for i := 0 to 3 do Result[i] := WaitForTask(Handle[i], 0);

isn't very desirable, as it involves polling and can result in multiple thread switchings.
A WaitForMultipleTasks(...some task handle list...) is a more preferable approach, as it can be mapped to OS functions such as WaitForMultipleObjects under windows, which will hopefully handle it at the kernel/thread scheduling level.

Eric

Has someone already created a unit for light weight threads?

Is there really an issue about tthread overhead, or are you searching for really lighter threads ? Fibers/clone/rfork etc.

Of course it would be possible to include a multitasking scheduler in the RTL to avoid any system calls and share any resources. (AFAIK, for Linux there somewhere was an alternate PThread library that does exactly in order to avoid slight Posix incompatibilities caused by "Linux Threads". But same is not necessary any more as the OS-based NPTL is said to perform just as good and Posix-compatible.)

I.e. if using Linux with NPTL (or that old special PThread library), I don't see how you could use "lighter" threads than with TThread.

If using Windows, (with it's quite heavy native Threads), pure user mode threads might be a lot "lighter". I do suppose that there are (C based) libraries that could be used here.

Anyway, the target for "lighter" threads is not really TThread itself, but the underlying scheduler.

-Michael

Hehe. I mainly choose the term to provoke.

TThread is a class and has more functionality than needed, but misses the ability to work in teams. For many parallel algorithms you don't need events, priority or synchronize. But you need to easily and fast start a set of threads with IDs 0..N. N can be computed from the number of cores or IO queues. But many algorithms simply compute N from the input size (e.g. N=n/log(n)). A pool with threads, each running and eating tasks in loops are 'lighter' than starting N real threads. For example starting a procedure "100 times in parallel" means on a dual core: Two threads execute the procedure 50 times. This is much lighter than 100 TThreads. And if one of the threads 'runs slower' than it will automatically load balance.

So, I hope that someone already implemented some 'light weight' threads for FPC and I can adapt and extend them.

Mattias

That's why I proposed this thread pool approach :)

Windows has built-in support for user-space scheduled threads. They're called fibers (multiple fibers are bound to one thread; the OS schedules threads and you pick which fiber runs).

Jonas

Mattias Gaertner wrote

For many parallel algorithms you don't need events, priority or synchronize. But you need to easily and fast start a set of threads with IDs 0..N.

Ok, so you're mostly caring about the thread creation overhead, it seems.

So yes, here I'd go with Florians thread pools advice. And no, it's not implemented yet, AFAIK.

You still can implement such thread pools on top of OpenMP(I) (or similar APIs), if you need to get much lighter. ;)

Vinzent.

Windows has built-in support for user-space scheduled threads. They're called fibers (multiple fibers are bound to one thread; the OS schedules threads and you pick which fiber runs).

Ahh. I did not know this.

So adding a UseFibers" property for the windows implementation of TThread might be a good way to provide a lighter version of same.

-Michael

You still can implement such thread pools on top of OpenMP(I) (or similar APIs), if you need to get much lighter. ;)

Afaik there are threadpool classes in Indy, and they work. Also there is a start of fiber support, but it was not finished.

On the other hand, particularly in the case where you are running a large number of iterations of a parallelised job it's useful to be able to time each thread so that the distribution of work can be optimised "on the fly".

As an example, looking at a big cellular automaton you might have a few hundred million cells and want to run for a billion or so generations. I think it's going to be significantly more efficient to have a set of N threads waiting for their worklists, on completion looking at the time each thread took and optimising the next generation than starting a pool of threads per generation.

One thing that would be useful would be a processor-affinity property on the basic TThread.

This is true for static load balancing.
But the thread pool would do dynamic load balancing. The jobs will not be distributed at the beginning, but on the fly.
Each thread should run something like this:

while GetNextTask do ExecuteTask;

When starting a procedure 100 times, the pool will "add" 100 tasks and wake up the sleeping threads. The threads will then process the tasks. There is no guarantee that a task will run in a specific thread. If a task fetches a small task, it will start earlier with the next. So if you are able to split up the problem in enough small tasks, you get dynamic load balancing for free.

One thing that would be useful would be a processor-affinity property on the basic TThread.

See the OpenMP specs for more possible tuning parameters. The pool can be extended by some of these abilities later, but for now I only need a simple pool to demonstrate/test FPC with parallel algorithms.

Mattias

See the OpenMP specs for more possible tuning parameters. The pool can be extended by some of these abilities later, but for now I only need a simple pool to demonstrate/test FPC with parallel algorithms.

Such a thread pool can get rather tricky: first, you need some heuristics to detect if all worker threads are sleeping/in use and you need more worker threads. Further, making a good queueing implementation is not easy either because it should block as little as possible.

> Has someone already created a unit for light weight threads? Is there really an issue about tthread overhead, or are you searching for really lighter threads ? Fibers/clone/rfork etc.

Basically I'm searching for units handling groups of threads, where each thread is less important and can therefore be very simple / optimized. So, yes, Fibers/clone/rfork can all be used for this.

Mattias

> You still can implement such thread pools on top of OpenMP(I) (or > similar APIs), if you need to get much lighter. ;) Afaik there are threadpool classes in Indy, and they work.

Thanks. I will take a look.

Also there is a start of fiber support, but it was not finished.

Mattias

Very true.
That's why I don't want to reinvent the wheel and asked on this list for existing code.

Mattias

Please keep me informed, I'll have to do something like this soon too. (though for now windows only). I did some thinking and have some urls. he most importnant one for Windows can be found if you search for "Martin Harvey" + threading faq (or threads faq) for primitives.

For me the calculated results also need to be retired (reconstructed), and the task queue needs to be fifo.

My initial scheme is a bit like this:
http://www.stack.nl/~marcov/threads.png

Some points:

- the producer threads produce pieces of data, (20-40 /s typically.) total data (image) production rate 20-100MB/s (mbytes that is) With this scheme I hope to further increase this (e.g. 150-200MB/s tops)
- each datum is possibly splitted 2,3,4 way before being passed on to the calculation part. The splitting is governed by symmetry concerns (for easy joining) and a target of about 5-20ms of calculation time. The calculation time is not entirely constant but it has to cope well with the worst case situation and be decent with the typical situation.
- A very small part of the calculation is not paralellisable, and has to be done when all parts are calculated. (in pic shown as the collection thread,

  which keeps track if the parts of a data packed are all calculated, and then
  does the final calculation)

- Probably some of the final results need to go to the mainthread for displaying and serial I/O. (I use TComport atm, which is meant for the mainthread t.b.d.)
- Threads is the amount of free cores. Since the production threads also copy the data (which is already good for 10% cpu at these datarates) I'm thinking about using the cheapest (read: coolest) Core 2 quad core and have 3 worker threads operating maximally, and keep the other core free for the copying. (bind if necessary).

Main problem is how to efficiently implement the dispatching of tasks and retiring them. I still need to take time to figure this out.

But as soon as you have more threads than processors you're losing your cache contents all the time. If you have 16x processors (I'm told that a 4-CPU system where each CPU is quad-core approximates this) you want to save a couple for general-purpose overheads and lock the remainder down for the high-performance stuff so that as far as possible they don't waste time reloading their cache every time there's a context switch.

The reason I suggest this is that it could be easily retrofitted to existing programs without any need to get a new API involved.

Yes, for HPC you need a lot of tuning parameters.
My goal is more humble: To use recent multi cores more easily.

Yes, but this is another problem. You want to improve the speed of parallel code, I want to make writing parallel programs easier.

Mattias

Hello all,

Has someone already created a unit for light weight threads? Something like: Create a group of 4 threads named 0,1,2,3 and execute a procedure/method?

Indy for Lazarus [1] has a fibers implementation.

Regarding the heavy load you are planning here:

When thinking about "lightweight threads" to make use of multiple _CPUs_, wouldn't it be viable to consider splitting the tasks across multiple _PCs_ as well ?

Thus: If planning an implementation of parallelism in the language itself (with support of the RTL), IMHO this should be done in a way that the user optionally can feed PC arrays with the same syntax.

-Michael

Well, there is the problem of data. I'm not a cluster expert, but I do know that getting the right data to the right calculation is then a severe bottleneck. In the first Linux clusters of yore, the switching equipment was the only part that wasn't the cheapeast that Dell had to offer :_)

Thus: If planning an implementation of parallelism in the language itself (with support of the RTL), IMHO this should be done in a way that the user optionally can feed PC arrays with the same syntax.

That would need also management of data, not just code execution points, so IMHO that is out of the question.

Yes, for HPC you need a lot of tuning parameters.

Supposedly the most important tuning parameter of course is the count of usable CPUs, the next important being the predicted percentage of the effort to start a thread regarding the runtime the thread needs to complete. For "lightweight threads" (requesting for a thread pool at least in Windows) this percentage might be rather low, for normal Threads somewhat larger. IMHO we should consider PC arrays as well. Here this percentage of course is a lot larger (transferring parameters and results through a Network), but here we might have a huge number of processors.

My goal is more humble: To use recent multi cores more easily.

Too humble, IMHO, changes to the language should be very well considered. :)

-Michael

IMHO the language itself might be enhanced for parallel processing.

The implementation should be done in the RTL (or supposedly rather a special library). Here the methods of distributing potentially parallel tasks on "executors" is defined. It should work according to a set of parameters (e.g. Count of available processors, a parameter list for the processors (e.g. speed), a penalty estimation for starting an "executor" (small for lightweight threads, high for cluster machines), ...) Moreover the library of course holds the code to create thread pools, assign tasks to threads, transport parameters to the thread, retrieve results from an "executor", etc.

A first implementation of course should just provide (light weight) threads (supposedly with a thread pool at least in Windows). Maybe the only primary tuning parameter being the count of CPUs. But it should be done in a way, that it can be extended to more sophisticated parameters and finally to cluster controlling, just by enhancing the library code.

IMHO, all this should not impose any problems for the implementation with "light weight threads".

-Michael

For clusters there is already a de facto standard: MPI. It works with FPC.

IMHO, all this should not impose any problems for the implementation with "light weight threads".

AFAIK OpenMP and MPI work well together and are separate.

Mattias

A big difference between threads and fibers in Windows is that threads are preemtively scheduled, while fibers are co-operatively scheduled.

Unfortunately, Windows' fiber implementation has severe limitations.

To get around this I created a library that does real light-weight "fibers".

See here for some documentation I wrote on the subject:

http://www.eternallines.com/microthreads/doc.html

Right now my concerns are not about how and what features should be implemented (in the libraries), but only about how they are presented by _language_extensions. (And about the interface the libraries offer to the user)

Here an as broad as possible range of ways to do parallel processing should be allowed - hiding the details (i.e. if using MPI or OpenMP or something else) should be hidden in the implementation in the library in a way as transparent as possible to the user.

-Michael

David Butler wrote

A big difference between threads and fibers in Windows is that threads are preemtively scheduled, while fibers are co-operatively scheduled.

That sounds very logical.

I gather cooperative scheduling is not possible when distributing the work on multiple processors. So using fibers are no option for the kind of "light weight threads" requested by the OP.

Unfortunately, Windows' fiber implementation has severe limitations.

No wonder :)

To get around this I created a library that does real light-weight "fibers".

I suppose as they run in a single system thread they are no option for the kind of "light weight threads" requested by the OP.

-Michael

I agree, that the library should be implemented open minded. But light weight threads only work fast, when each thread has equally fast access to all resources. This is not the case for distributed memory.

Mattias

But light weight threads only work fast, when each thread has equally fast access to all resources. This is not the case for distributed memory.

Right you are. The language and the library interface should of course support this as an option.

-Michael

Is there really much difference between what Windows terms "a fiber" and what Modula-2 etc. terms "a coroutine"? A thread is little more than a preemptively-scheduled coroutine, and it's always seemed slightly perverse to define fibers in terms of threads rather than the other way round.

I think that modifying the language to incorporate MPI would be extremely difficult and would be so near the bleeding edge of computer science that the next person to do it would design something equally good but utterly different. As I understand it MPI is generally used to pass a result vector between nodes, at that point determining the extent of the vector and when it's ready for transfer is going to be highly application-specific i.e. a library issue.

Looking elsewhere in this thread, I believe that the number of CPUs can be got as part of the thread-affinity API which I believe would be of use in TThread, at worst if you set the affinity to 0xffffffff you get back a vector showing which CPUs actually exist.

However an interesting issue is that on some architectures the list of available CPUs can have "holes" in it, e.g. I've got a system here with CPUs 0, 1 4..15 available.

I think that modifying the language to incorporate MPI would be extremely difficult and would be so near the bleeding edge of computer science

I assume that language support for any kind of parallel processing is hard to do That is why some days ago I said that I don't think that anybody will start to implement this (some kind of "parallel" keyword) any tome soon.

OTOH, doing _explicit_ multithreading (and thus multiprocessing with OS support) and integrate this in a more "Delphi-Language" like way than TThread can be done with no or (for a little bit more straight forward use) with just a little support from the language itself. That is why I suggested the EventThread / ThreadEvent paradigm. (which of course is not "light weight").

-Michael