Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #772 > unrolled thread

Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1

Back to article view | Back to comp.programming.threads

Contents

  Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 11:14 -0800
    Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 11:18 -0800
      Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 12:06 -0800
        Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 12:13 -0800
    Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 13:37 -0800
      Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 15:56 -0800
        Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 15:57 -0800
          Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 16:46 -0800
            Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 17:09 -0800
              Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 18:12 -0800
                Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 18:29 -0800
                  Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 19:53 -0800
                    Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 20:05 -0800
                      Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 20:59 -0800
                        Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 21:25 -0800
                          Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 22:03 -0800
                        Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 21:16 -0800
                          Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 21:35 -0800
                          Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 22:22 -0800
                Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 19:03 -0800
                  Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 19:13 -0800
                    Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 19:29 -0800
                      Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 aminer <aminer68@gmail.com> - 2011-12-22 19:34 -0800
                        Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 22:29 -0800
                  Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 19:57 -0800
                    Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 20:02 -0800
                  Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 "Chris M. Thomasson" <cristom@charter.net> - 2011-12-22 20:00 -0800

Page 1 of 2  [1] 2  Next page →

#772 — Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1

Hello,

I have reworked my old Parallel Gauss-Seidel with relaxation iterative
program gsp.pas
into a Parallel Gauss-Seidel with relaxation iterative algorithm
library version 1.1.


Description

The Parallel iterative with relaxation method that i programmed here
is designed
to be used to solve large sparse systems of linear equations where the
direct methods
can exceed available machine memory and/or be extremely time-
consuming. for example
the direct method of the Gauss algorithm takes O(n^2) in the back
substitution process
and is dominated by the O(n^3) forward elimination process, that
means, if for example
an operation takes 10^-9 second and we have 1000 equations , the
elimination process
in the Gauss algorithm will takes 0.7 second, but if we have 10000
equations in the system ,
the elimination process in the Gauss algorithm will take 11 minutes !.
This is why i have
develloped for you the Parallel Gauss-Seidel with relaxation iterative
algorithm in Object Pascal,
that is very fast.

And please take a look at my article on my Parallel Gauss-Seidel with
relaxation algorithm: GSRP.

The benchmarks are here: http://pages.videotron.com/aminer/ParallelGaussSeidel/gsrp.htm


And here is how to use the library, as you have noticed you have to
initialize
your vector x first , and set your lambda inside the call to Solve(),
i have set lambda to 0.01 ,
and set the number of cores  in the constructor, and pass you matrix
and vector b to the Solve() method,
and that's all:


Here is the example:

---------------------

program test;


uses parallelgaussseidel,timer;

var gsp:TParallelGaussSeidel;
    i,j,size:integer;
    matrows: arrarrext;
  vecb,vecx: arrext;

begin


gsp:=TParallelGaussSeidel.create(4); // number of cores to use


size:=10000; // set it as you wish...
SetLength(matrows, size);
SetLength(vecb, size);
SetLength(vecx, size);
for I := Low(matrows) to High(matrows) do
  begin
   setlength(matrows[I],High(matrows)+1);
   end;

for I := Low(matrows) to High(matrows)
 do
  begin
   vecb[I]:=100000000;
   vecx[I]:=22222222;
   for J := Low(matrows) to High(matrows) do
   matrows[I][J] := 77770000777;
 end;

if gsp.testconvergence(matrows)
 then writeln('The system converge...')
      else writeln('The system may or may not converge...');

HPT.Timestart;

if gsp.Solve(matrows,vecb,vecx,0.01)

then
 begin
  writeln('Time in microseconds: ',hpt.TimePeriod);

  writeln('The system converge...');
  writeln('The system solved...');
  writeln(vecx[0],' ',vecx[1],' ',vecx[2]); // write here you vecx...
 end

else
 begin
  writeln('The system doesn''t converge...');
 end;

SetLength(matrows, 0);
SetLength(vecb, 0);
SetLength(vecx, 0);

gsp.free;

end.


------



Please look at my parallel program test.pas inside the zip file ,
compile and execute it ... -

Language: FPC Pascal v2.2.0+ / Delphi 7+: 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+ -DDelphi



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#773

Hello,


You can download Parallel Gauss-Seidel with relaxation iterative
algorithm library
version 1.1 from:

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



Thank you.

Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#774

Hello,

Just another thing, to not wait a long time if the system doesn't
converge, please
set max_tries inside ParallelGaussSeidel to somehting like 40 or 20 ,
i have set
it to 100000.

You will find the variable max_tries  inside the Solve() method...



Thank you.

Amine Moulay Ramdane


On Dec 22, 2:18 pm, aminer <amine...@gmail.com> wrote:
> Hello,
>
> You can download Parallel Gauss-Seidel with relaxation iterative
> algorithm library
> version 1.1 from:
>
> http://pages.videotron.com/aminer/
>
> Thank you.
>
> Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#775

Hello,

Or just let max_tries to 100000 , and if the Solve() doesn't
return for a long period, that means that your system doesn't
converge, so that means it will not give a solution, so just click
after that on Cltrl-C and that's all.



Thank you.

Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#776

"aminer" <aminer68@gmail.com> wrote in message 
news:e099112a-4302-415f-9af5-77c638ae4183@p9g2000vbb.googlegroups.com...
>
> Hello,
>
> I have reworked my old Parallel Gauss-Seidel with relaxation iterative
> program gsp.pas
> into a Parallel Gauss-Seidel with relaxation iterative algorithm
> library version 1.1.

[...]

I think you have a problem with you're MPMC queue algorithm; refer here for 
detailed description:

http://groups.google.com/group/comp.programming.threads/msg/9d42e7424d0f2940

;^o 

[toc] | [prev] | [next] | [standalone]

#777

On Dec 22, 4:37 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:e099112a-4302-415f-9af5-77c638ae4183@p9g2000vbb.googlegroups.com...
>
>
>
> > Hello,
>
> > I have reworked my old Parallel Gauss-Seidel with relaxation iterative
> > program gsp.pas
> > into a Parallel Gauss-Seidel with relaxation iterative algorithm
> > library version 1.1.
>
> [...]
>
> I think you have a problem with you're MPMC queue algorithm; refer here for
> detailed description:
>
> http://groups.google.com/group/comp.programming.threads/msg/9d42e7424...
>
> ;^o


Hello,

You don't have the right version, push() have changed between,
please download the right version here...

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



thank you.

Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#778

On Dec 22, 6:56 pm, aminer <amine...@gmail.com> wrote:
> On Dec 22, 4:37 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
>
>
>
>
> > "aminer" <amine...@gmail.com> wrote in message
>
> >news:e099112a-4302-415f-9af5-77c638ae4183@p9g2000vbb.googlegroups.com...
>
> > > Hello,
>
> > > I have reworked my old Parallel Gauss-Seidel with relaxation iterative
> > > program gsp.pas
> > > into a Parallel Gauss-Seidel with relaxation iterative algorithm
> > > library version 1.1.
>
> > [...]
>
> > I think you have a problem with you're MPMC queue algorithm; refer here for
> > detailed description:
>
> >http://groups.google.com/group/comp.programming.threads/msg/9d42e7424...
>
> > ;^o
>
> Hello,
>
> You don't have the right version, push() have changed between,
> please download the right version here...
>
> http://pages.videotron.com/aminer/zip/lockfree_mpmc.zip


Sorry, you can download it from here:

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



>
> thank you.
>
> Amine Moulay Ramdane.- Hide quoted text -
>
> - Show quoted text -

[toc] | [prev] | [next] | [standalone]

#779

"aminer" <aminer68@gmail.com> wrote in message 
news:02ab5fb1-d1c6-4cda-9b14-a15ce7b11f85@z25g2000vbs.googlegroups.com...
On Dec 22, 6:56 pm, aminer <amine...@gmail.com> wrote:
> On Dec 22, 4:37 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
[...]
> > I think you have a problem with you're MPMC queue algorithm; refer here 
> > for
> > detailed description:
>
> >http://groups.google.com/group/comp.programming.threads/msg/9d42e7424...
>
> > ;^o
>
> >
> > You don't have the right version, push() have changed between,
> > please download the right version here...
[...]
> http://pages.videotron.com/aminer/zip/lockfree_queue.zip

That has the exact same problem I have illustrated here:

http://groups.google.com/group/comp.programming.threads/msg/9d42e7424d0f2940 

[toc] | [prev] | [next] | [standalone]

#780

Hello,

Are you speaking about the same algorithm ?


In the push side:rhere is a temp variable that is incremented like
this:

newTemp:=LockedIncLong(temp);


and after that there is an

lastTail:=newTemp-1;
setObject(lastTail,tm);

that means that we are copying the items without incrementing the
tail

and after that we are incrementing the tail in a repeat loop like this

repeat
  if CAS(tail,lasttail,newtemp)
   then
      begin
       exit;
      end;
sleep(0);
 until false;



So where is the problem exactly ?



thank you.
Amine Moulay Ramdane.









On Dec 22, 7:46 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:02ab5fb1-d1c6-4cda-9b14-a15ce7b11f85@z25g2000vbs.googlegroups.com...
> On Dec 22, 6:56 pm, aminer <amine...@gmail.com> wrote:
>
> > On Dec 22, 4:37 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> [...]
> > > I think you have a problem with you're MPMC queue algorithm; refer here
> > > for
> > > detailed description:
>
> > >http://groups.google.com/group/comp.programming.threads/msg/9d42e7424...
>
> > > ;^o
>
> > > You don't have the right version, push() have changed between,
> > > please download the right version here...
> [...]
> >http://pages.videotron.com/aminer/zip/lockfree_queue.zip
>
> That has the exact same problem I have illustrated here:
>
> http://groups.google.com/group/comp.programming.threads/msg/9d42e7424...

[toc] | [prev] | [next] | [standalone]

#781

"aminer" <aminer68@gmail.com> wrote in message 
news:0c5cc2bb-e1f6-4f31-89ed-37bef98511c3@u6g2000vbg.googlegroups.com...

> Are you speaking about the same algorithm ?

OOPS! No. I was referring to the old algorithm. Humm... I think I will 
implement the new one in Relacy.

Okay, so here is my translation of the push function of the new algorithm 
that has XADD and CAS in push:
__________________________________________________
N = 2;
uint tail:=0;
uint head:=0;
uint temp:=0;

bool push(int state)
{
P1:    if (queue_full()) return false;
P2:    uint last_tail = ATOMIC_XADD(temp);
P3:    setobject(last_tail, state);
P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
P5:    return true;
}
__________________________________________________


AFAICT, it can suffer from the same type of problem. I can lose items 
permanently. Imagine the following scenario:

three producer threads PT1, PT2, PT3 all trying to push items 1-3 
respectively...


PT1: P1 - the queue is empty.
PT2: P1 - the queue is empty.
PT3: P1 - the queue is empty.
PT1: P2 - gets last_tail of 0.
PT2: P2 - gets last_tail of 1.
PT3: P2 - gets last_tail of 2.
PT1: P3 - sets record[0] to item1.
PT2: P3 - sets record[1] to item2.
PT3: P3 - sets record[0] to item3; OUCH!!!


In this case, item1 gets lost forever!

Examine my scenario and execution sequence very carefully and please explain 
how this cannot happen? 

[toc] | [prev] | [next] | [standalone]

#782

On Dec 22, 9:12 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:0c5cc2bb-e1f6-4f31-89ed-37bef98511c3@u6g2000vbg.googlegroups.com...
>
> > Are you speaking about the same algorithm ?
>
> OOPS! No. I was referring to the old algorithm. Humm... I think I will
> implement the new one in Relacy.
>
> Okay, so here is my translation of the push function of the new algorithm
> that has XADD and CAS in push:
> __________________________________________________
> N = 2;
> uint tail:=0;
> uint head:=0;
> uint temp:=0;
>
> bool push(int state)
> {
> P1:    if (queue_full()) return false;
> P2:    uint last_tail = ATOMIC_XADD(temp);
> P3:    setobject(last_tail, state);
> P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
> P5:    return true;}
>
> __________________________________________________
>
> AFAICT, it can suffer from the same type of problem. I can lose items
> permanently. Imagine the following scenario:
>
> three producer threads PT1, PT2, PT3 all trying to push items 1-3
> respectively...
>
> PT1: P1 - the queue is empty.
> PT2: P1 - the queue is empty.
> PT3: P1 - the queue is empty.
> PT1: P2 - gets last_tail of 0.
> PT2: P2 - gets last_tail of 1.
> PT3: P2 - gets last_tail of 2.
> PT1: P3 - sets record[0] to item1.
> PT2: P3 - sets record[1] to item2.
> PT3: P3 - sets record[0] to item3; OUCH!!!

I don't understand the follwing:

 PT3: P3 - sets record[0] to item3; OUCH!!!


How this can happen with lockfree_mpmc algorithm ?

i tink it can not happen , last_tail that is 2 will be copied
correctly ..


can you explain more the problem ? where is the problem ?



Amine Moulay Ramdane.










>
> In this case, item1 gets lost forever!
>
> Examine my scenario and execution sequence very carefully and please explain
> how this cannot happen?

[toc] | [prev] | [next] | [standalone]

#787

"aminer" <aminer68@gmail.com> wrote in message 
news:1bab5329-ce78-4b92-8dc8-8567f82480c2@i6g2000vbe.googlegroups.com...
On Dec 22, 9:12 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
[...]
> > PT1: P1 - the queue is empty.
> > PT2: P1 - the queue is empty.
> > PT3: P1 - the queue is empty.
> > PT1: P2 - gets last_tail of 0.
> > PT2: P2 - gets last_tail of 1.
> > PT3: P2 - gets last_tail of 2.
> > PT1: P3 - sets record[0] to item1.
> > PT2: P3 - sets record[1] to item2.
> > PT3: P3 - sets record[0] to item3; OUCH!!!

> I don't understand the follwing:

>  PT3: P3 - sets record[0] to item3; OUCH!!!

> How this can happen with lockfree_mpmc algorithm ?

I just showed you.

AFAICT, this is 100% legit execution sequence which results in item1 being 
lost forever; the getlength function has nothing to do with this.

Think about it. 

[toc] | [prev] | [next] | [standalone]

#791

On Dec 22, 10:53 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:1bab5329-ce78-4b92-8dc8-8567f82480c2@i6g2000vbe.googlegroups.com...
> On Dec 22, 9:12 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> [...]
>
> > > PT1: P1 - the queue is empty.
> > > PT2: P1 - the queue is empty.
> > > PT3: P1 - the queue is empty.
> > > PT1: P2 - gets last_tail of 0.
> > > PT2: P2 - gets last_tail of 1.
> > > PT3: P2 - gets last_tail of 2.
> > > PT1: P3 - sets record[0] to item1.
> > > PT2: P3 - sets record[1] to item2.
> > > PT3: P3 - sets record[0] to item3; OUCH!!!
> > I don't understand the follwing:
> >  PT3: P3 - sets record[0] to item3; OUCH!!!
> > How this can happen with lockfree_mpmc algorithm ?
>
> I just showed you.
>
> AFAICT, this is 100% legit execution sequence which results in item1 being
> lost forever; the getlength function has nothing to do with this.
>
> Think about it.


You have set N = 2 in your example, and that can not happen...

cause the sixe of the queue must be a power of two and superior or
equal to 2^10....

and in the following example that you give

PT1: P1 - the queue is empty.
PT2: P1 - the queue is empty.
PT3: P1 - the queue is empty.
PT1: P2 - gets last_tail of 0.
PT2: P2 - gets last_tail of 1.
PT3: P2 - gets last_tail of 2.
PT1: P3 - sets record[0] to item1.
PT2: P3 - sets record[1] to item2.
PT3: P3 - sets record[0] to item3; OUCH!!!

th following cabn not happen ...

PT3: P3 -   sets record[0] to item3; OUCH!!!

cause there is a margin of 1000..

Please think about it...


Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#792

"aminer" <aminer68@gmail.com> wrote in message 
news:3547e238-89e9-41e8-b747-fe5f12f5718e@i6g2000vbh.googlegroups.com...
On Dec 22, 10:53 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
[...]

> You have set N = 2 in your example, and that can not happen...

That's a rather annoying limitation. However, it does not matter, it's still 
broken.


> cause the sixe of the queue must be a power of two and superior or
> equal to 2^10....

So what happens if I have N = 1024 and 1025 producers hit it at the same 
time? Please note that any number of producers can easily pass the getlength 
 >= fsize constraint, therefore, it's still broken in the exact way I 
describe...

__________________________________________________
N = 1024;
uint tail:=0;
uint head:=0;
uint temp:=0;

bool push(int state)
{
P1:    if (queue_full()) return false;
P2:    uint last_tail = ATOMIC_XADD(temp);
P3:    setobject(last_tail, state);
P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
P5:    return true;
}
__________________________________________________


Scenario:

1025 producer threads PT[1-1025] are all trying to push items item[1-1025] 
respectively...

Execution Sequence:

PT[1-1025]: P1 - the queue is empty; they all pass the getlength test!
PT[1-1025]: P2 - gets last_tail of [0-1024] respectively from XADD
PT[1-1025]: P3 - setobject item[1-1025] on record[0-1024] respectively; 
OUCH!

Keep in mind that TN == 1025 and N == 1024. This means that producer PT1025 
will get a last_tail value of 1024 which rolls the masked index counter back 
to record[0]. This will simply overwrite the item that PT1 produced with the 
item that PT1025 produced. In other words, item[1] is lost forever. 

[toc] | [prev] | [next] | [standalone]

#793

On Dec 22, 11:59 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:3547e238-89e9-41e8-b747-fe5f12f5718e@i6g2000vbh.googlegroups.com...
> On Dec 22, 10:53 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> [...]
>
> > You have set N = 2 in your example, and that can not happen...
>
> That's a rather annoying limitation. However, it does not matter, it's still
> broken.
>
> > cause the sixe of the queue must be a power of two and superior or
> > equal to 2^10....
>
> So what happens if I have N = 1024 and 1025 producers hit it at the same
> time? Please note that any number of producers can easily pass the getlength
>  >= fsize constraint, therefore, it's still broken in the exact way I
> describe...
>
> __________________________________________________
> N = 1024;
> uint tail:=0;
> uint head:=0;
> uint temp:=0;
>
> bool push(int state)
> {
> P1:    if (queue_full()) return false;
> P2:    uint last_tail = ATOMIC_XADD(temp);
> P3:    setobject(last_tail, state);
> P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
> P5:    return true;}
>
> __________________________________________________
>
> Scenario:
>
> 1025 producer threads PT[1-1025] are all trying to push items item[1-1025]
> respectively...
>
> Execution Sequence:
>
> PT[1-1025]: P1 - the queue is empty; they all pass the getlength test!
> PT[1-1025]: P2 - gets last_tail of [0-1024] respectively from XADD
> PT[1-1025]: P3 - setobject item[1-1025] on record[0-1024] respectively;
> OUCH!
>
> Keep in mind that TN == 1025 and N == 1024. This means that producer PT1025
> will get a last_tail value of 1024 which rolls the masked index counter back
> to record[0]. This will simply overwrite the item that PT1 produced with the
> item that PT1025 produced. In other words, item[1] is lost forever.



You said: 1025 producer threads

I have limited margin to 1000 threads...



Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#796

"aminer" <aminer68@gmail.com> wrote in message
news:f276977e-6a71-4cf3-ab96-853c15a083e3@j9g2000vby.googlegroups.com...
On Dec 22, 11:59 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:

[...]

> You said: 1025 producer threads

> I have limited margin to 1000 threads...

Why should N have any bearing on the total limit of threads I can use? ;^/ 

[toc] | [prev] | [next] | [standalone]

#794

On Dec 22, 11:59 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:3547e238-89e9-41e8-b747-fe5f12f5718e@i6g2000vbh.googlegroups.com...
> On Dec 22, 10:53 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> [...]
>
> > You have set N = 2 in your example, and that can not happen...
>
> That's a rather annoying limitation. However, it does not matter, it's still
> broken.
>
> > cause the sixe of the queue must be a power of two and superior or
> > equal to 2^10....
>
> So what happens if I have N = 1024 and 1025 producers hit it at the same
> time? Please note that any number of producers can easily pass the getlength
>  >= fsize constraint, therefore, it's still broken in the exact way I
> describe...
>
> __________________________________________________
> N = 1024;
> uint tail:=0;
> uint head:=0;
> uint temp:=0;
>
> bool push(int state)
> {
> P1:    if (queue_full()) return false;
> P2:    uint last_tail = ATOMIC_XADD(temp);
> P3:    setobject(last_tail, state);
> P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
> P5:    return true;}
>
> __________________________________________________
>
> Scenario:
>
> 1025 producer threads PT[1-1025] are all trying to push items item[1-1025]
> respectively...
>
> Execution Sequence:
>
> PT[1-1025]: P1 - the queue is empty; they all pass the getlength test!
> PT[1-1025]: P2 - gets last_tail of [0-1024] respectively from XADD
> PT[1-1025]: P3 - setobject item[1-1025] on record[0-1024] respectively;
> OUCH!
>
> Keep in mind that TN == 1025 and N == 1024. This means that producer PT1025
> will get a last_tail value of 1024 which rolls the masked index counter back
> to record[0]. This will simply overwrite the item that PT1 produced with the
> item that PT1025 produced. In other words, item[1] is lost forever.

If N equal 1024 , fsize of the queue will be equal to 24 ...

No the item will not be lost.  cause there is a margin of 1000,
please look at the algorithm again and look especially at  how margin
is used and you will understand what i mean...



Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#795

On Dec 23, 12:16 am, aminer <amine...@gmail.com> wrote:
> On Dec 22, 11:59 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
>
>
>
>
>
> > "aminer" <amine...@gmail.com> wrote in message
>
> >news:3547e238-89e9-41e8-b747-fe5f12f5718e@i6g2000vbh.googlegroups.com...
> > On Dec 22, 10:53 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> > [...]
>
> > > You have set N = 2 in your example, and that can not happen...
>
> > That's a rather annoying limitation. However, it does not matter, it's still
> > broken.
>
> > > cause the sixe of the queue must be a power of two and superior or
> > > equal to 2^10....
>
> > So what happens if I have N = 1024 and 1025 producers hit it at the same
> > time? Please note that any number of producers can easily pass the getlength
> >  >= fsize constraint, therefore, it's still broken in the exact way I
> > describe...
>
> > __________________________________________________
> > N = 1024;
> > uint tail:=0;
> > uint head:=0;
> > uint temp:=0;
>
> > bool push(int state)
> > {
> > P1:    if (queue_full()) return false;
> > P2:    uint last_tail = ATOMIC_XADD(temp);
> > P3:    setobject(last_tail, state);
> > P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
> > P5:    return true;}
>
> > __________________________________________________
>
> > Scenario:
>
> > 1025 producer threads PT[1-1025] are all trying to push items item[1-1025]
> > respectively...
>
> > Execution Sequence:
>
> > PT[1-1025]: P1 - the queue is empty; they all pass the getlength test!
> > PT[1-1025]: P2 - gets last_tail of [0-1024] respectively from XADD
> > PT[1-1025]: P3 - setobject item[1-1025] on record[0-1024] respectively;
> > OUCH!
>
> > Keep in mind that TN == 1025 and N == 1024. This means that producer PT1025
> > will get a last_tail value of 1024 which rolls the masked index counter back
> > to record[0]. This will simply overwrite the item that PT1 produced with the
> > item that PT1025 produced. In other words, item[1] is lost forever.
>
> If N equal 1024 , fsize of the queue will be equal to 24 ...
>
> No the item will not be lost.  cause there is a margin of 1000,
> please look at the algorithm again and look especially at  how margin
> is used and you will understand what i mean...
>
> Amine Moulay Ramdane.- Hide quoted text -
>
> - Show quoted text -


You said: 1025 producer threads


Please set the number of producers threads to a number <= 1000

I have limited margin to 1000 threads...


Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#797

"aminer" <aminer68@gmail.com> wrote in message 
news:5aa7eb2c-13af-47af-ae76-7be0a6b9da2b@z17g2000vbe.googlegroups.com...
On Dec 22, 11:59 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
[...]

> If N equal 1024 , fsize of the queue will be equal to 24 ...

IMHO, if I set N to 1024 I simply expect to be able to store 1024 items in 
there. BTW, on a side note wrt N= 1024, if fsize is equal to 24, then after 
there are 24 items pushed the queue will report a full condition even though 
there are a 1000 unused records left! IMVHO, that is a pretty big waste of 
space. Having N depend on total number of threads and vise versa is not too 
good of an idea, IMVHO, that is...


> No the item will not be lost.  cause there is a margin of 1000,
> please look at the algorithm again and look especially at  how margin
> is used and you will understand what i mean...

I think you need to document these limitations and requirements. 

[toc] | [prev] | [next] | [standalone]

#783

On Dec 22, 9:12 pm, "Chris M. Thomasson" <cris...@charter.net> wrote:
> "aminer" <amine...@gmail.com> wrote in message
>
> news:0c5cc2bb-e1f6-4f31-89ed-37bef98511c3@u6g2000vbg.googlegroups.com...
>
> > Are you speaking about the same algorithm ?
>
> OOPS! No. I was referring to the old algorithm. Humm... I think I will
> implement the new one in Relacy.
>
> Okay, so here is my translation of the push function of the new algorithm
> that has XADD and CAS in push:
> __________________________________________________
> N = 2;
> uint tail:=0;
> uint head:=0;
> uint temp:=0;
>
> bool push(int state)
> {
> P1:    if (queue_full()) return false;
> P2:    uint last_tail = ATOMIC_XADD(temp);
> P3:    setobject(last_tail, state);
> P4:    while (! ATOMIC_CAS(&tail, last_tail, last_tail + 1));
> P5:    return true;}
>
> __________________________________________________
>
> AFAICT, it can suffer from the same type of problem. I can lose items
> permanently. Imagine the following scenario:
>
> three producer threads PT1, PT2, PT3 all trying to push items 1-3
> respectively...
>
> PT1: P1 - the queue is empty.
> PT2: P1 - the queue is empty.
> PT3: P1 - the queue is empty.
> PT1: P2 - gets last_tail of 0.
> PT2: P2 - gets last_tail of 1.
> PT3: P2 - gets last_tail of 2.
> PT1: P3 - sets record[0] to item1.
> PT2: P3 - sets record[1] to item2.
> PT3: P3 - sets record[0] to item3; OUCH!!!
>
> In this case, item1 gets lost forever!
>
> Examine my scenario and execution sequence very carefully and please explain
> how this cannot happen?


But look at

fSize:=(1 shl aPower) - margin;


there is a margin of 1000.


Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming.threads

csiph-web