Parallelism vs Multithreading

Processes don't execute code. Threads do. Since processes don't execute code, it doesn't make any sense to "schedule" a process. The Windows scheduler works with threads - it automatically moves threads to idle cores when work needs to be done.

If you spawn two threads, and they're both churning away independent of each other (ie. not blocking or synchronising with each other), then Windows will make use of two cores. You don't need to worry about it - unless you're on a single core system.

When creating a thread specify the which processor to run the thread. This will force the the OS to put that thread on that processor. I will remind you that now you have to check how many processors there are and if a processor is "pegged" and you tell you new thread to run on it oh well. But when you run massivly parallel code ie >4 cpus you almost have to specify what cpu to use. At least this has been my experience. MS(XP,2003) and Linux (cerca '02) do not scale scale well beyond 2 cpus. I do not know about Vista or the newer Kernel of Linux. SGI actaully had the best scaling OS scheduler that I ever used. My 2 cents.

I could be wrong, but AFAIK there is no way to override the os scheduling (perhaps there may be ways to set some parameters though): if the two theads are executed on the same cpu (or core) they will be executed one at a time, no matter what you do. However I suppose that the resolution of the context switch might be high enough to make them appear as running parallel. On the other side, if they are executed on two different cores, you already have parallel processing.

If you need such fine control over your thread, perhaps you should go with a real time targeted OS? (I'm no way an expert)

Quote:

Original post by phil126 When creating a thread specify the which processor to run the thread. This will force the the OS to put that thread on that processor. I will remind you that now you have to check how many processors there are and if a processor is "pegged" and you tell you new thread to run on it oh well. But when you run massivly parallel code ie >4 cpus you almost have to specify what cpu to use. At least this has been my experience. MS(XP,2003) and Linux (cerca '02) do not scale scale well beyond 2 cpus. I do not know about Vista or the newer Kernel of Linux. SGI actaully had the best scaling OS scheduler that I ever used. My 2 cents.

But won't this be the same as running it on the same core? I mean, since you don't know if other threads are running on that core, you are still bound to the scheduler. Or is it guaranteed that a my app will have all the cores available once the scheduler give to it the control?

Quote:

Original post by zaidgs And multithreading has several advantages over multiprocessing.

And vice versa.

Quote:

But the problem is that Multithreading != Parallelism, which is running several threads (or processes) in parallel.

This is incorrect. Both multithreading and multiprocessing will both use whatever processes or cores your operating system sees fit to give out.

Quote:

Is there a way to ensure that two threads are running in parallel on multicore systems?!

Yes, shut down all other processes and threads running beforehand. (Warning: this may render your operating system useless.)

Basically, what I want to do is be sure that a thread is executed when I run it without waiting for a context switch. Maybe there would be a function to check whether a core is idle or busy, and only create that thread if it is idle.

To give you an idea of what I mean, consider this psuedo-code:

function(){int x= f1();int y = f2();return x+y;}

Assume that f1, f2 are simple tasks.. Thats to say, context-time >> time for f1 or f2. So f1 and f2 can be called several times before a context-switch kicks in.

Now, I might want to make use of a dual-core and run f1 and f2 in parallel... But if f1 finishes its processing, and f2 did not (because it was not assigned to a core by the OS), the function's performance will probably decrease rather than increase. In that case, if the thread currently allocated to the CPU is waiting for a thread not scheduled to a CPU, it would actually be better off running that function in its thread.

So I want to avoid this type of situations, and that each function is run by whatever core or thread that is ready to go.

The definition of parallelism is to do more than one thing at a time. There are many paths to parallelism implicit work division e.g. TBB or openMP, explicit work division e.g. threading, vectorization, or distributed methods.

Quote:

Finally, there are two types of threads: Kernel threads, and user threads. Is there any tutorial on how to do multithreading without the load of system calls?!

There aren't any since threading is very platform specific, unless you go with one of the libraries that wraps the system calls into a portable interface such as boost threads.

Quote:

Original post by zaidgs So I want to avoid this type of situations, and that each function is run by whatever core or thread that is ready to go.

Currently, the problem is solved by passing parameters to a fixed thread pool. First thread that is free dequeues the data and runs it. Each thread worker looks like this:

void run() {  while (running()) {    Work * w = scheduler.getWork();    if (w) {      w->run();    } else {      scheduler.wait();    }  }}

void enqueue(Work * w) {  queue.add(w);  queue.notifyOne();  };

The potentially redundant notify step can be eliminated through use of interlocked structures to maintain a queue of available workers. Once a queue is free, it enqueues itself on the free list, and scheduler checks if if there are any waiting threads before putting request in queue.

Quote:

what I want to do is be sure that a thread is executed when I run it without waiting for a context switch

I don't see a way to do this without writing your own kernel. Problem is - your threads are just a few out of hundreds always present in OS. And some of them are critical and may take precedence over yours.

Current ideal multi-threading tries to minimize shared state, keeping threads as busy as possible without relying on other threads. Future trends such as Singularity build on this approach, since some experience has shown that cost of passing data between contexts may be outweighed by the benefits of keeping state non-shared.

Quote:

To give you an idea of what I mean, consider this psuedo-code:

The above is very poor example of concurrency, since you're waiting for result. The common terminology for this is futures.

Unless your f1 and f2 take considerable time, the cost of data passing, thread synchronization and waiting for result will kill you.

As an example, I've used similar approach for parallel Qsort, with the difference of not waiting for result. Running time was about 5-20 times slower than single-threaded approach, despite better core utilization. The cost of intra-thread communication is simply prohibitive for such fine-grained data passing.

It is however possible to design data structures in such a manner that read/write states are always disjoint as invariant, in which case the cost is somewhat decreased, but not even remotely eliminated.

Quote:

So I want to avoid this type of situations, and that each function is run by whatever core or thread that is ready to go.

This happens internally. When a thread needs to run, it will run on any available core.

Quote:

Thats to say, context-time >> time for f1 or f2

That is IMHO impossible. The mere cost of reliably passing data to either thread will be several factors bigger than context switch and f1/f2 time combined, since passing data requires a mutex or lock-less structure which likely involves spin-lock.

Quote:

function(){ int x= f1(); int y = f2(); return x+y; }

To really benefit from concurrency (assuming f1/f2/+ are expensive tasks), the operation should be scheduled in order. Something like:
print(sum(f1, f2)), where each is a function.

As a reference on this approach you can look over attempts of doing that in LISP. Erlang is a good example too.

Common problem is the prohibitive cost of passing data by value, especially once large data sets are affected (such as image manipulation). Other problem as is, as mentioned, the high constant cost of passing data between threads and scheduling, especially in inherently sequential tasks.

Quote:

Original post by stonemetalThere aren't any since threading is very platform specific, unless you go with one of the libraries that wraps the system calls into a portable interface such as boost threads.

This paragraph is from my OS text-book 'Operating System Concepts', and it says:

Quote:

A thread library provides the programmer an API for creating and managing threads. There are primarily two types of implementing a thread library. The first approach is to provide a library entirely in user space with no kernel support. All code and data structures for the library exist in user space. This means that invoking a function in the library results in a local function call in user space and not a system call. The second approach is to implement a kernel-level library supported by the OS. ...etc Three main thread libraries are in use today: (1) Pthreads, (2) Win32, and (3) Java. Pthreads may be provided as either user- or kernel-level library. The Win32 thread library is a kernel-level library available on windows systems. The Java thread API allows thread creation and management directly in Java programs.

Does this mean that we cannot use user-level threads on windows?!

Quote:

Original post by Antheus Currently, the problem is solved by passing parameters to a fixed thread pool. First thread that is free dequeues the data and runs it. Each thread worker looks like this: void run() { while (running()) { Work * w = scheduler.getWork(); if (w) { w->run(); } else { scheduler.wait(); } }} void enqueue(Work * w) { queue.add(w); queue.notifyOne(); };

Is there any place I can read more about this technique?!

Quote:

Original post by Antheus Problem is - your threads are just a few out of hundreds always present in OS. And some of them are critical and may take precedence over yours.

Yes, thats why I need to check that a core is idle before assigning it a job.

I know that multithreading was not designed for the scenario that I am describing, but there should be a way to make efficient use of multi-core processors. But the application at my hand is basically a large number of CPU intensive function calls, all of which depend on one another one way or the other... The process on a single core CPU keeps the CPU at 100% for several minutes. But on my Quad-core, the CPU use is 25% (because it uses only a single thread). [PS: To be specific, it a a chess engine running alphabeta, and I am try to implement a parallel aphabeta using the Young Brothers Waits concept. I have not made the code yet, but I am anticipating severe performance problems if the threads waiting for one another instead of doing their jobs.]

Quote:

Original post by zaidgs Does this mean that we cannot use user-level threads on windows?!

Nope, it just means that you have to implement them yourself. Since they require no kernel-level support, they can be implemented entirely within your program (or find a library that provides them for you). Note that user-level threads do not however help you to utilise multiple cores.

You may also be interested in fibers as they somewhat approximate user threads.

At the end of the day it doesn't really matter whether two threads actually execute simultaneously or not. To the human observer the difference is indistuinguishable, other than how long it takes.
Best to let the OS take care of scheduling.

Quote:

Original post by zaidgs Quote: Original post by Antheus Currently, the problem is solved by passing parameters to a fixed thread pool. First thread that is free dequeues the data and runs it. Each thread worker looks like this: void run() { while (running()) { Work * w = scheduler.getWork(); if (w) { w->run(); } else { scheduler.wait(); } }} void enqueue(Work * w) { queue.add(w); queue.notifyOne(); }; Is there any place I can read more about this technique?!

David Butenhof's book on POSIX threads is pretty solid for low-level stuff. I'd recommend it if you have access to a UNIXy machine. The concepts carry over to Windows rather well, too. Or even if you're using the threads library in boost, then you'll do well with Butenhof's book as the boost threads library "feels" a lot like pthreads. Patterns For Parallel Programming by Mattson et al also discusses a broad array of techniques at a higher level.

Quote:

Quote: Original post by Antheus Problem is - your threads are just a few out of hundreds always present in OS. And some of them are critical and may take precedence over yours. Yes, thats why I need to check that a core is idle before assigning it a job.

You really don't want to do this. You just add jobs to a queue and have N threads processing the queue (where N is approximately the number of cores on your system). If you pump stuff in to your queue fast enough, then the kernel will keep both processors busy automatically. You really really really shouldn't be worrying about scheduling context switches yourself.

Even if you could check if a core was idling at any given instant, by the time you execute the next instruction, it may no longer be idle. In a preemptive threading system, doing any such check is pointless.

Quote:

Original post by zaidgs it a a chess engine running alphabeta, and I am try to implement a parallel aphabeta using the Young Brothers Waits concept

This isn't really a threading problem. The problem you're trying to solve is decomposition of original problem into several disjoint sets, which can then be solved independently.

Simply put, you will not be splitting on function calls, you will try to partition your tree in such a way, that for n threads, each will receive a subset of tree, and solve it independently. In the end, you will collate these results.

Individual work sets will need to be large enough to warrant such distribution. This type of solutions is sometimes referred to as scatter-gather approach, where your work is done in two phases. First you send out jobs, second you collect the results.

I'm not too familiar with these particular algorithms, but for trees, you might want to simply try to have each thread start iterating at some depth d, so that width of tree at d is some reasonable multiple of n. Aside from constant overhead of arriving to d, this gives you enough room to allow for uneven work completion.

Pseudo code would be something like this(worker):

void run() {  while (true) {    int index = interlocked_increment(top);    if (index < max) {      starting_nodes[index].result = traverse_tree(starting_nodex[index].node);    } else {      return;    }  }}

- starting_nodes contains an array which indices of nodes in tree where to start the traversal
- max is size of this array
- top is current node to be processed, initially 0

In pre-processing step, you first populate starting_nodes by iterating through tree to a certain depth. You then add nodes into starting_nodes in such a manner, that concurrent traversal starting at them will be performed on disjoint sets, not causing any sharing concerns.

As long as max is some reasonable multiple of number of cores (and consequently threads), you should see somewhat reasonable improvement over single-threaded approach.