### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: Scalable and relaxed MPMC priority Queue was updated to version 1.06  (Read 2558 times)

#### aminer

• Hero Member
• Posts: 956
##### Scalable and relaxed MPMC priority Queue was updated to version 1.06
« on: April 05, 2014, 12:56:56 am »
Hello,

My scalable and relaxed MPMC priority Queue was updated to version 1.06
now when there is no items in the queue it steals from the other queues in a round robin manner.

Author: Amine Moulay Ramdane

Description:

A scalable and relaxed MPMC priority Queue.

Relaxed means not a strict FIFO, but it's almost a strict FIFO, it processes the jobs in a FIFO order in each queue, and when there is no items in the queue the thread steals from the other queues in a round robin manner, that's good.

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, 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 and the number of producers must be equal to the number of queues that you  pass to the constructor so that it become scalable, 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.

- 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

Thank you,
Amine Moulay Ramdane.

#### aminer

• Hero Member
• Posts: 956
##### Re: Scalable and relaxed MPMC priority Queue was updated to version 1.06
« Reply #1 on: April 05, 2014, 01:47:57 am »

Hello...

My scalable and relaxed MPMC almost FIFO priority Queue was updated to version 1.06, it's an almost strict FIFO.. and you have to be smart when you are using it...

For example when you have 4 producers threads and you have
for example 16 cores, and you want to process your items in all
the cores, and you want my almost FIFO priority Queue to be scalable , you have to model your queues as follows...

You have to create 4 of my scalable and almost strict FIFO queue
each with 4 queues.

And the first producer thread have to distribute the items in a round robin manner to the four queues...and the second, and the third and the fourth producer  threads must do the same... this is how the my almost strict FIFO queues will be scalable.

So be smart and hope you have understood this bright idea.