Jump to content
  • Advertisement
Sign in to follow this  
MrFiber

Introducing a C++ multicore task library

This topic is 3445 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello, I'm not a game developer but maybe the library I wrote can be helpful in programming scalable games for multicore processors. A short description: The library provides a multithreaded task scheduler using a thread pool where all tasks are executed on fibers. Fibers are the key feature because fibers can block without blocking the thread. If you're familiar with fibers, you know that it's a pain programming them. Here, this is not the case because all about fibers is encapsulated in the library. Instead, the library contains header files with user-mode lock-free implementations of fiber synchronization primitives like CriticalSection, Event or Semaphore that you can use to block your task. That said, you can write a task as if you were writing a thread but without overhead. When a task blocks, the scheduler immediately starts/resumes another task in order to keep the thread busy. The library is still under development. You can get more information at http://www.fiberpool.de/en/index.html I'd be grateful for any comments and feedback MrFiber

Share this post


Link to post
Share on other sites
Advertisement
Quote:
A task scheduler for multiprocessor systems
(this method is patent pending)


I was under impression that EU put a ban on software patents.

Threads.

Quote:
Threads are sometimes implemented in userspace libraries, thus called user threads. The kernel is not aware of them, they are managed and scheduled in userspace. Some implementations base their user threads on top of several kernel threads to benefit from multi-processor machines (N:M model). In this article the term "thread" (without kernel or user qualifier) defaults to referring to kernel threads. User threads as implemented by virtual machines are also called green threads.


Quote:
Fibers are an even lighter unit of scheduling which are cooperatively scheduled: a running fiber must explicitly "yield" to allow another fiber to run, which makes their implementation much easier than kernel or user threads. A fiber can be scheduled to run in any thread in the same process. This permits applications to gain performance improvements by managing scheduling themselves, instead of relying on the kernel scheduler (which may not be tuned for the application). Microsoft SQL Server 2000's user mode scheduler, running in fiber mode, is an example of doing this. Parallel programming environments such as OpenMP typically implements their tasks through fibers.

Share this post


Link to post
Share on other sites
Quote:
I was under impression that EU put a ban on software patents.

This is right, but a method is not software. Scheduling methods can be implemented as software as well as with hardware. But this should not be a discussion about patents...

Thanks for the Wikipedia quotes.

Quote:
A fiber can be scheduled to run in any thread in the same process.

This is a nice feature but when using it thread-affine functions must not be called. This is also true when programming tasks with my library.

Share this post


Link to post
Share on other sites
Quote:
Original post by MrFiber

But this should not be a discussion about patents...


Considering that distribution of products which use the library has no licensing terms specified, and that patented technology might be used in that library, it has all to do with them.

Let's say I purchase the commercial technology license. I sell 500 copies and pay corresponding fee. 2 years later, patent is approved, and I get sued for patent infringement in 500 copies, considering there is already proven paper trail of me using patented method.

But since the products using the library are non-distributable as per 2.c in developer's license, the library as it stands has no practical use.

Since it doesn't come with source it also doesn't have educational value, and the only documentation is the patent application.

Which brings me to:
Quote:
maybe the library I wrote can be helpful in programming scalable games for multicore processors.


A license that cannot be distributed and is potentially encumbered by unspecified patent is not helpful. And until a clear license is released for distribution, the library has severely limited practical use.

But to each their own. I'm not condoning selling libraries or technologies, I'm merely pointing out that in current form, given information available, this is an IP minefield.

Share this post


Link to post
Share on other sites
Quote:
Original post by MrFiber
Quote:
I was under impression that EU put a ban on software patents.

This is right, but a method is not software.

Yes, it is. A method by itself is not patentable in the EU, unless it is specifically tied to, and dependent on, a hardware implementation. A purely software based implementation of your method can therefore not be protected under EU patent law.

Note that while the EPO generally doesn't have the expertise to reject algorithmic patents (in fact they often grant them, and some fishy lawyers exploit this fact to pretend to be able to have your algorithm patented, usually for a large fee), they are unenforceable in court later on. Once rejected, you will lose all priority rights to them, including possible hardware implementations. In some cases, you might even have to pay litigation fees to the infringing party !

Be very careful when trying to patent methods and algorithms in the EU. Even if you only intend to patent it for a specific hardware implementation, it can very easily backfire. An incorrectly worded comment on your website ("this method is patent pending") can already be enough.

(IANAL, etc, etc. But I have a lot of experience fighting against the EPO and USPTO ;)

Share this post


Link to post
Share on other sites
Antheus, your thoughts are right.

My intention writing to this forum was pure scientific, requesting feedback for the idea.

The reason why the license terms for distribution are not specified is simple: As long as I don't know if the idea is good or bad, I don't want to spend money to hire an attorney to specify the license terms for me. This is a one-man-show and nowadays you have to think twice where to spend your money.

I have to clarify that the library and the patent pending scheduler are two different things. The library cannot implement this scheduler, it's just simulating a small part of it. The library won't be protected by this patent.

Quote:
Original post by Yann L
Yes, it is. A method by itself is not patentable in the EU, unless it is specifically tied to, and dependent on, a hardware implementation. A purely software based implementation of your method can therefore not be protected under EU patent law.

This is right, therefore the recommended way is to have a patent attorney for such patents.

AFAIK, the EPO office in the Netherlands has a department specialized on scheduling methods.

Quote:
An incorrectly worded comment on your website ("this method is patent pending") can already be enough.

Thanks for the hint. I think I will remove it.

Share this post


Link to post
Share on other sites
OK, so just ignoring the licensing/patent issues for the time-being...

I'm not sure this library would be worth the trouble. If you're going to be using fibres, you would therefore also need to provide an implementation of every function that can possibly block. For example, you'll need to create a wrapper around CreateFile, WriteFile, ReadFile, socket, recv, send, WaitForSingleObject, WaitForMultipleObjects, Sleep, and the list goes on. You also have to avoid using thread-local state.

That also means any third-party libraries that are not aware of your library are out of the question (so no libpng for loading png files, no third-party networking implementation, etc). You could do your third-party stuff in a non-fibre thread, but then is there much point?

And what happens if somebody creates a job that takes 10 minutes to execute? You're going to starve the process waiting for that job to finish. It's up to the programmer to ensure that all jobs finish in as short a time as possible.

You mentioned on the website that in the future, you'd be able to automatically generate the code that splits a sequential program into jobs that can be scheduled. That would be an interesting tool, but how is a fibre-based thread pool by itself is going to be worth the effort?

Sorry to play the devil's advocate here [smile] but it would help greatly if you can provide some benchmarks or real-world example of where this library could really help...

Share this post


Link to post
Share on other sites
Quote:
Original post by Codeka
I'm not sure this library would be worth the trouble. If you're going to be using fibres, you would therefore also need to provide an implementation of every function that can possibly block. For example, you'll need to create a wrapper around CreateFile, WriteFile, ReadFile, socket, recv, send, WaitForSingleObject, WaitForMultipleObjects, Sleep, and the list goes on. You also have to avoid using thread-local state.

This is something you can expect from me - or possibly from the community. A simple File class already exists and for fiber synchronization I have implemented the most important primitves.

Quote:
That also means any third-party libraries that are not aware of your library are out of the question (so no libpng for loading png files, no third-party networking implementation, etc). You could do your third-party stuff in a non-fibre thread, but then is there much point?

I don't know much of libpng but as for GDIplus you can pass an IStream* as argument. Using my library you would only have to implement this interface and use the File class. All fiber locking would be done there.

The situation when to use the library is when you have existing serial code that you want parallelize.

For example, if your game code would look like this:
head = CalculateHead();
torso(left, right) = CalculateTorso(head);
CalculateLeftArm(leftTorso);
CalculateRightArm(rightTorso);
CalculateLeftLeg(torso);
CalculateRightLeg(torso);

This is just a fragment, imagine you have thousands lines of code.

Parallelizing this code with threads and kernel synchronization would be a mission impossible.

With my library you would use a RestrictedTaskGroup object and add all the tasks to the group. The scheduler would feed the threads then, the sync vars would block or resume the dependent tasks. The task group would be responsible to stop parallelizing when a good granularity has been reached.

Quote:
You mentioned on the website that in the future, you'd be able to automatically generate the code that splits a sequential program into jobs that can be scheduled. That would be an interesting tool, but how is a fibre-based thread pool by itself is going to be worth the effort?

You can see the fiber-based thread pool as a proof of concept.

The idea behind this is to have the whole program written sequentially (even producer/consumer) then let the compiler find the parallel parts and let the scheduler scale.

Example (pseudocode):
Stack stack(5);
Producer p;
Consumer c;
p.Produce(stack, 1000);
c.Consume(stack, 1000);
DoSomethingElse();

Because scaling begins at 1 this code should also be able to run on one processor on one thread. This is not possible with the imperative paradigm so something else must be used instead. With fibers I can simulate the intended behaviour on an existing system.

Quote:
Sorry to play the devil's advocate here [smile] but it would help greatly if you can provide some benchmarks or real-world example of where this library could really help...

The only benchmark I have is the comparison of my sort algorithm with the TBB's: On an Intel Q9450 64bit sorting 100 million __int64 the TBB takes about 7.1 secs while my lib takes about 7.5 secs which is pretty good because my focus is not independent tasks.

For dependent tasks there is nothing I could compare with. I could create 1000 threads with dependencies but it should be obvious that this would be much slower then running 1000 tasks with dependencies on 4 threads.

Quote:
Original post by the_edd
You might be interested in this. It sounds roughly similar to what you're doing.

Are you the author? If I understood it correctly this is limited to one thread?

Share this post


Link to post
Share on other sites
@ OP:

It sounds like a simple coroutine library. I assume the special part of the library is that it runs fiber scheduling on multiple threads. Is that correct?

If so, you still need locking if tasks on separate threads access the same data. At that point, the problem becomes so complex that I see no advantages over standard multithreaded programming patterns.

If not, then... it's just coroutines? Which are very cool for working around cumbersome imperative design, but don't offer any multicore advantages.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!