A scalable and relaxed MPMC priority Queue version 1.01

[aminer]

Hello,


A scalable and relaxed MPMC priority Queue version 1.01


Author: Amine Moulay Ramdane

Description:

A scalable and relaxed MPMC priority Queue. Relaxed means not a strict FIFO, but even if  it's not a strict FIFO it processes the jobs in a FIFO order in each queue, that's also interresting.

Where can my scalable and relaxed MPMC priority Queue be useful ?

When for example you want to do something like a threadpool that do parallel tasks without the need that the queue be strict FIFO, and you can find that in many applications that do parallel mathematical calculations or parallel mechanical or graphic calculations and  many parallel tasks... so you will reduce on those applications the S part in the Amdahl equation using my scalable and relaxed MPMC priority Queue.

You have to start the same number of consumer threads than the number of queues that you will pass to the constructor and use many producer threads and use the exec() method not the execute() method, so that it become scalable.

The following have been added:

- You can give the following priorities to jobs:

LOW_PRIORITY
NORMAL_PRIORITY
HIGH_PRIORITY

- A queue for each worker thread and it uses work-stealing - for more efficiency -

- Enters in a wait state when there is no job in the queue - for more efficiency -

- Uses O(1) complexity on enqueue and O(3) worst case complexity on dequeue.

Look into defines.inc there is many options:

CPU32: for 32 bits architecture
CPU64: for 64 bits architecture

Look test.pas and  at test1.pas examples inside the zip file that shows you that my PQueue is scaling.


Language: FPC Pascal v2.2.0+ / Delphi 5+: http://www.freepascal.org/

Operating Systems: Win , Linux and Mac (x86).

Required FPC switches: -O3 -Sd -dFPC -dWin32 -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -DMSWINDOWS -$H+

For Delphi 5,6,7 use -DDelphi

For Delphi 2005,2006,2007,2009,2010+ use the switch -DDELPHI2005+




Thank you,
Amine Moulay Ramdane

[aminer]

Hello,


I have updated my scalable and relaxed MPMC priority Queue to
version 1.02, now it is working correctly in both the push() and the pop() side and i have tested it myself and it is now working correctly...

But there is a mandatory requirement: The number of  consumer threads must be equal or greater to the number of queues that you  pass to the constructor.


Author: Amine Moulay Ramdane


Language: FPC Pascal v2.2.0+ / Delphi 5+: http://www.freepascal.org/

Operating Systems: Win , Linux and Mac (x86).


Description:

A scalable and relaxed MPMC priority Queue.
Relaxed means not a strict FIFO, but even if  it's not a strict FIFO it processes the jobs in a FIFO order in each queue, that's also interresting.

Where can my scalable and relaxed MPMC priority Queue be useful ?

When for example you want to do something like a threadpool that do parallel tasks without the need that the queue be strict FIFO, and you can find that in many applications that do parallel mathematical calculations or parallel mechanical or graphic calculations and  many parallel tasks... so you will reduce on those applications the S part in the Amdahl equation using my scalable and relaxed MPMC priority Queue.

The number of  consumer threads must be equal or greater to the number of queues that you  pass to the constructor and use many producer threads and you have to initialize first the Push() method with high(pqueue.long), look at how to do it inside the test1.pas example inside the zip file,   so that it become scalable.

The following have been added:

- You can give the following priorities to jobs:

LOW_PRIORITY
NORMAL_PRIORITY
HIGH_PRIORITY

- A queue for each worker thread and it uses work-stealing - for more efficiency -

- Enters in a wait state when there is no job in the queue - for more efficiency -

- Uses O(1) complexity on enqueue and O(3) worst case complexity on dequeue.


Look into defines.inc there is many options:

CPU32: for 32 bits architecture
CPU64: for 64 bits architecture

Look test.pas and  at test1.pas examples inside the zip file that shows you that my PQueue is scaling.

Required FPC switches: -O3 -Sd -dFPC -dWin32 -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -DMSWINDOWS -$H+

For Delphi 5,6,7 use -DDelphi

For Delphi 2005,2006,2007,2009,2010+ use the switch -DDELPHI2005+



You can download scalable and relaxed MPMC priority Queue to
version 1.02 from:

http://pages.videotron.com/aminer/


Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,

There is some scalable FIFO queues there that are patented , the like the one with elimination and another one with Speculative Pairing...

Here is the one with elimination:

http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/SPAA2005.pdf

and here is the Speculative Pairing queue:

https://repository.ist.ac.at/124/


But those scalable queues are patented , so i think you have
to pay for them if you want to use them on your commercial project.


But my scalable and relaxed MPMC priority Queue is a freeware
and you can use it in your commercial project without paying anything.

Where can my scalable and relaxed MPMC priority Queue be useful ?

When for example you want to do something like a Threadpool that do parallel tasks without the need that the queue be strict FIFO, and you can find that in many applications that do parallel mathematical calculations or parallel mechanical or graphic calculations and  many parallel tasks... so you will reduce on those applications the S part in the Amdahl equation using my scalable and relaxed MPMC priority Queue.

The number of  consumer threads must be equal or greater to the number of queues that you  pass to the constructor and use many producer threads and you have to initialize first the Push() method with high(pqueue.long), look at how to do it inside the test1.pas example inside the zip file,   so that it become scalable.

The following have been added:

- You can give the following priorities to jobs:

LOW_PRIORITY
NORMAL_PRIORITY
HIGH_PRIORITY

- A queue for each worker thread and it uses work-stealing - for more efficiency -

- Enters in a wait state when there is no job in the queue - for more efficiency -

- Uses O(1) complexity on enqueue and O(3) worst case complexity on dequeue.


You can download scalable and relaxed MPMC priority Queue version 1.02 from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.

[aminer]

I wrote:
"There is some scalable FIFO queues there that are patented , the like the one with elimination and another one with Speculative Pairing.."

 
What kind of Protection does a Patent offer?

Patent protection means that the invention cannot be commercially made, used, distributed or sold without the patent owner's consent. These patent rights are usually enforced in a court, which, in most systems, holds the authority to stop patent infringement. Conversely, a court can also declare a patent invalid upon a successful challenge by a third party.


Read this:

http://www.wipo.int/patentscope/en/patents_faq.html#protection



Thank you,
Amine Moulay Ramdane.

[Jurassic Pork]

i wrote :

" how to become a super hero member of the forum ? "

"response : Post all my thought in the forum"