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

Groups > comp.programming > #3929 > unrolled thread

There is a solution to satisfy the energy efficiency requirement

Started byaminer <aminer@toto.net>
First post2013-10-12 18:55 -0700
Last post2013-10-12 19:28 -0700
Articles 3 — 1 participant

Back to article view | Back to comp.programming

Contents

  There is a solution to satisfy the energy efficiency requirement aminer <aminer@toto.net> - 2013-10-12 18:55 -0700
    Re: There is a solution to satisfy the energy efficiency requirement aminer <aminer@toto.net> - 2013-10-12 18:57 -0700
    Re: There is a solution to satisfy the energy efficiency requirement aminer <aminer@toto.net> - 2013-10-12 19:28 -0700

#3929 — There is a solution to satisfy the energy efficiency requirement

Fromaminer <aminer@toto.net>
Date2013-10-12 18:55 -0700
SubjectThere is a solution to satisfy the energy efficiency requirement
Message-ID<l3ck10$t7b$1@news.albasani.net>
Hello,

I wrote:
"Question:
But Amine, why do you want to satisfy many requirements for your FIFO 
queue, such
as minimizing efficiently the cache-coherence traffic,
and the FIFO fairness, and also the energy efficiency ? why
the energy efficiency ?
answer:
Energy efficieny is also important, cause we must not think just
for today , we must think for the future when there will be many
more cores, this requirement of energy efficiency will become much more
important, so as i told you it's sad that those waitfree and lockfree
FIFO queue algorithms must use spin-wait when there no item in the queue 
and the threads must wait for new items etc. so as i told you, to 
satisfy the requirement of energy efficiency we must use my FIFO fair 
SemaCondvar or FIFO fair Semaphores inside the FIFO queue, but since my 
SemaCondvar
and Smeaphores are slow , this will slow the FIFO queue, and that's sad."



I think there is a solution to satisfy the energy efficiency requirement 
, you have to use my manual event object that is supported by FreePascal 
and Delphi and that is portable,
so after you push an item in the queue you have to call SetEvent() of 
the manual event object, and in the pop() side you have to use something 
like this:

--

if self.count <> 0
         then continue;

        if self.count=0
            then
             begin
               self.event.waitfor(INFINITE);
               self.event.resetevent;
             end;
         end;

---

This method is more energy efficient, so when there is no items in the
queue the push() method will wait on the manual event object so
it will not use CPU ressources like with the spin-wait mechanism,
and i think you have to avoid Semaphores cause semaphores are slow.

Here is the complete source code:

===


unit Lockfree_MPMC;

{$IFDEF FPC}
{$ASMMODE intel}
{$ENDIF}


interface

uses
syncobjs,
{$IFDEF Delphi}expbackoff,sysutils;{$ENDIF}
{$IFDEF FPC}expbackoff,sysutils;{$ENDIF}

{$I defines.inc}

const margin=1000; // limited to 1000 threads...
{$IFDEF CPU64}
INFINITE = qword($FFFFFFFFFFFFFFFF);
{$ENDIF CPU64}
{$IFDEF CPU32}
INFINITE = longword($FFFFFFFF);
{$ENDIF CPU32}
type
{$IFDEF CPU64}
long = qword;
{$ENDIF CPU64}
{$IFDEF CPU32}
long = longword;
{$ENDIF CPU32}


   tNodeQueue = tObject;
   typecache1  = array[0..15] of longword;

  // TLockfree_MPMC = class(TFreelist)
   TLockfree_MPMC = class
   private
       tail:long;
       tmp1:typecache1;
       head: long;
       fMask : long;
       fSize : long;
       temp:long;
       backoff1,backoff2:texpbackoff;
       event:TSimpleEvent;
       tab : array of tNodeQueue;
       procedure setobject(lp : long;const aobject : tNodeQueue);
       function getLength:long;
       function getSize:long;
       function getObject(lp : long):tNodeQueue;
   public
      {$IFDEF CPU64}
      constructor create(aPower : int64 =20);  {allocate tab with size 
equal 2^aPower, for 20 size is equal 1048576}
      {$ENDIF CPU64}
      {$IFDEF CPU32}
      constructor create(aPower : integer =20);  {allocate tab with size 
equal 2^aPower, for 20 size is equal 1048576}
      {$ENDIF CPU32}


       destructor Destroy; override;
       function push(tm : tNodeQueue):boolean;
       function pop(var obj:tNodeQueue;wait:boolean=false):boolean;
       property length : long read getLength;
       property count: long read getLength;
       property size : long read getSize;

   end;


implementation

function LockedIncLong(var Target: long): long;
asm
         {$IFDEF CPU32}
         // --> EAX Target
         // <-- EAX Result
         MOV     ECX, EAX
         MOV     EAX, 1
         //sfence
        LOCK XADD [ECX], EAX
         inc     eax
         {$ENDIF CPU32}
         {$IFDEF CPU64}
         // --> RCX Target
         // <-- EAX Result
         MOV     rax, 1
         //sfence
         LOCK XADD [rcx], rax
         INC     rax
         {$ENDIF CPU64}
end;

function CAS(var Target:long;Comp ,Exch : long): boolean;assembler;stdcall;
asm
{$IFDEF CPU64}
   mov   rax, comp
   lock cmpxchg [Target], Exch
   setz  al
{$ENDIF CPU64}
{$IFDEF CPU32}
   mov   eax, comp
   mov   ecx,Target
   mov   edx,exch
  lock cmpxchg [ecx], edx
   setz  al

{$ENDIF CPU32}

end; { CAS }



{function CAS(var Target: long; Comperand: long;NewValue: long ): 
boolean; assembler;stdcall;
asm
         mov    ecx,Target
         mov    edx,NewValue
         mov    eax,Comperand
        //sfence
        lock        cmpxchg   [ecx],edx
        JNZ @@2
        MOV AL,01
        JMP @@Exit
        @@2:
        XOR AL,AL
        @@Exit:
end;}
{$IFDEF CPU64}
constructor TLockfree_MPMC.create(aPower : int64 );
{$ENDIF CPU64}
{$IFDEF CPU32}
constructor TLockfree_MPMC.create(aPower : integer );
{$ENDIF CPU32}


begin
   if aPower < 10
     then
      begin
       writeln('Constructor argument must be greater or equal to 10');
        halt;
      end;
  if (aPower < 0) or (aPower > high(integer))
     then
      begin
       writeln('Constructor argument is incorrect');
        halt;
      end;
   backoff1:=texpbackoff.create(1,2);
   backoff2:=texpbackoff.create(1,2);
{$IFDEF CPU64}
fMask:=not($FFFFFFFFFFFFFFFF shl aPower);{$ENDIF CPU64}
{$IFDEF CPU32}
fMask:=not($FFFFFFFF shl aPower);
{$ENDIF CPU32}

   fSize:=(1 shl aPower) - margin;
   setLength(tab,1 shl aPower);
   tail:=0;
   head:=0;
   temp:=0;
  Event := TSimpleEvent.Create;

end;

destructor  TLockfree_MPMC.Destroy;

begin
   event.free;
    backoff1.free;
    backoff2.free;
    setLength(tab,0);
    inherited Destroy;
end;


procedure TLockfree_MPMC.setObject(lp : long;const aobject : tNodeQueue);
begin
   tab[lp and fMask]:=aObject;
end;

function TLockfree_MPMC.getObject(lp : long):tNodeQueue;
begin
   result:=tab[lp and fMask];
end;


function TLockfree_MPMC.push(tm : tNodeQueue):boolean;
var lasttail,newtemp:long;
i,j:integer;
begin

  if getlength >= fsize
   then
       begin
           result:=false;
           exit;
       end;
result:=true;

newTemp:=LockedIncLong(temp);

lastTail:=newTemp-1;
//asm mfence end;
setObject(lastTail,tm);

repeat

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

end;


function TLockfree_MPMC.pop(var obj:tNodeQueue;wait:boolean=false):boolean;

var lastHead : long;
begin
   repeat
   lastHead:=head;
   if tail<>head
    then
     begin
       obj:=getObject(lastHead);

           if CAS(head,lasthead,lasthead+1)
           then
            begin
             result:=true;
            exit;
            end
           else  sleep(0); //backoff2.delay;

      end
    else
        begin
         if wait=false
           then
            begin
             result:=false;
              exit;
            end;

        if self.count <> 0
         then continue;

        if self.count=0
            then
             begin
               self.event.waitfor(INFINITE);
               self.event.resetevent;
             end;
         end;
   until false;
end;

function TLockfree_MPMC.getLength:long;
var head1,tail1:long;
begin
head1:=head;
tail1:=tail;
   if tail1 < head1
        then result:= (High(long)-head1)+(1+tail1)
        else result:=(tail1-head1);
end;

function TLockfree_MPMC.getSize:long;

begin
   result:=fSize;
end;

end.
===




Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#3930

Fromaminer <aminer@toto.net>
Date2013-10-12 18:57 -0700
Message-ID<l3ck5m$t7b$4@news.albasani.net>
In reply to#3929
Hello.

So as you have noticed this method that i am using is
more efficient  cause you will not wait on the manual event object until 
self.count = 0.


Thank you,
Amine Moulay Ramdane.

On 10/12/2013 6:55 PM, aminer wrote:
>
> Hello,
>
> I wrote:
> "Question:
> But Amine, why do you want to satisfy many requirements for your FIFO
> queue, such
> as minimizing efficiently the cache-coherence traffic,
> and the FIFO fairness, and also the energy efficiency ? why
> the energy efficiency ?
> answer:
> Energy efficieny is also important, cause we must not think just
> for today , we must think for the future when there will be many
> more cores, this requirement of energy efficiency will become much more
> important, so as i told you it's sad that those waitfree and lockfree
> FIFO queue algorithms must use spin-wait when there no item in the queue
> and the threads must wait for new items etc. so as i told you, to
> satisfy the requirement of energy efficiency we must use my FIFO fair
> SemaCondvar or FIFO fair Semaphores inside the FIFO queue, but since my
> SemaCondvar
> and Smeaphores are slow , this will slow the FIFO queue, and that's sad."
>
>
>
> I think there is a solution to satisfy the energy efficiency requirement
> , you have to use my manual event object that is supported by FreePascal
> and Delphi and that is portable,
> so after you push an item in the queue you have to call SetEvent() of
> the manual event object, and in the pop() side you have to use something
> like this:
>
> --
>
> if self.count <> 0
>          then continue;
>
>         if self.count=0
>             then
>              begin
>                self.event.waitfor(INFINITE);
>                self.event.resetevent;
>              end;
>          end;
>
> ---
>
> This method is more energy efficient, so when there is no items in the
> queue the push() method will wait on the manual event object so
> it will not use CPU ressources like with the spin-wait mechanism,
> and i think you have to avoid Semaphores cause semaphores are slow.
>
> Here is the complete source code:
>
> ===
>
>
> unit Lockfree_MPMC;
>
> {$IFDEF FPC}
> {$ASMMODE intel}
> {$ENDIF}
>
>
> interface
>
> uses
> syncobjs,
> {$IFDEF Delphi}expbackoff,sysutils;{$ENDIF}
> {$IFDEF FPC}expbackoff,sysutils;{$ENDIF}
>
> {$I defines.inc}
>
> const margin=1000; // limited to 1000 threads...
> {$IFDEF CPU64}
> INFINITE = qword($FFFFFFFFFFFFFFFF);
> {$ENDIF CPU64}
> {$IFDEF CPU32}
> INFINITE = longword($FFFFFFFF);
> {$ENDIF CPU32}
> type
> {$IFDEF CPU64}
> long = qword;
> {$ENDIF CPU64}
> {$IFDEF CPU32}
> long = longword;
> {$ENDIF CPU32}
>
>
>    tNodeQueue = tObject;
>    typecache1  = array[0..15] of longword;
>
>   // TLockfree_MPMC = class(TFreelist)
>    TLockfree_MPMC = class
>    private
>        tail:long;
>        tmp1:typecache1;
>        head: long;
>        fMask : long;
>        fSize : long;
>        temp:long;
>        backoff1,backoff2:texpbackoff;
>        event:TSimpleEvent;
>        tab : array of tNodeQueue;
>        procedure setobject(lp : long;const aobject : tNodeQueue);
>        function getLength:long;
>        function getSize:long;
>        function getObject(lp : long):tNodeQueue;
>    public
>       {$IFDEF CPU64}
>       constructor create(aPower : int64 =20);  {allocate tab with size
> equal 2^aPower, for 20 size is equal 1048576}
>       {$ENDIF CPU64}
>       {$IFDEF CPU32}
>       constructor create(aPower : integer =20);  {allocate tab with size
> equal 2^aPower, for 20 size is equal 1048576}
>       {$ENDIF CPU32}
>
>
>        destructor Destroy; override;
>        function push(tm : tNodeQueue):boolean;
>        function pop(var obj:tNodeQueue;wait:boolean=false):boolean;
>        property length : long read getLength;
>        property count: long read getLength;
>        property size : long read getSize;
>
>    end;
>
>
> implementation
>
> function LockedIncLong(var Target: long): long;
> asm
>          {$IFDEF CPU32}
>          // --> EAX Target
>          // <-- EAX Result
>          MOV     ECX, EAX
>          MOV     EAX, 1
>          //sfence
>         LOCK XADD [ECX], EAX
>          inc     eax
>          {$ENDIF CPU32}
>          {$IFDEF CPU64}
>          // --> RCX Target
>          // <-- EAX Result
>          MOV     rax, 1
>          //sfence
>          LOCK XADD [rcx], rax
>          INC     rax
>          {$ENDIF CPU64}
> end;
>
> function CAS(var Target:long;Comp ,Exch : long): boolean;assembler;stdcall;
> asm
> {$IFDEF CPU64}
>    mov   rax, comp
>    lock cmpxchg [Target], Exch
>    setz  al
> {$ENDIF CPU64}
> {$IFDEF CPU32}
>    mov   eax, comp
>    mov   ecx,Target
>    mov   edx,exch
>   lock cmpxchg [ecx], edx
>    setz  al
>
> {$ENDIF CPU32}
>
> end; { CAS }
>
>
>
> {function CAS(var Target: long; Comperand: long;NewValue: long ):
> boolean; assembler;stdcall;
> asm
>          mov    ecx,Target
>          mov    edx,NewValue
>          mov    eax,Comperand
>         //sfence
>         lock        cmpxchg   [ecx],edx
>         JNZ @@2
>         MOV AL,01
>         JMP @@Exit
>         @@2:
>         XOR AL,AL
>         @@Exit:
> end;}
> {$IFDEF CPU64}
> constructor TLockfree_MPMC.create(aPower : int64 );
> {$ENDIF CPU64}
> {$IFDEF CPU32}
> constructor TLockfree_MPMC.create(aPower : integer );
> {$ENDIF CPU32}
>
>
> begin
>    if aPower < 10
>      then
>       begin
>        writeln('Constructor argument must be greater or equal to 10');
>         halt;
>       end;
>   if (aPower < 0) or (aPower > high(integer))
>      then
>       begin
>        writeln('Constructor argument is incorrect');
>         halt;
>       end;
>    backoff1:=texpbackoff.create(1,2);
>    backoff2:=texpbackoff.create(1,2);
> {$IFDEF CPU64}
> fMask:=not($FFFFFFFFFFFFFFFF shl aPower);{$ENDIF CPU64}
> {$IFDEF CPU32}
> fMask:=not($FFFFFFFF shl aPower);
> {$ENDIF CPU32}
>
>    fSize:=(1 shl aPower) - margin;
>    setLength(tab,1 shl aPower);
>    tail:=0;
>    head:=0;
>    temp:=0;
>   Event := TSimpleEvent.Create;
>
> end;
>
> destructor  TLockfree_MPMC.Destroy;
>
> begin
>    event.free;
>     backoff1.free;
>     backoff2.free;
>     setLength(tab,0);
>     inherited Destroy;
> end;
>
>
> procedure TLockfree_MPMC.setObject(lp : long;const aobject : tNodeQueue);
> begin
>    tab[lp and fMask]:=aObject;
> end;
>
> function TLockfree_MPMC.getObject(lp : long):tNodeQueue;
> begin
>    result:=tab[lp and fMask];
> end;
>
>
> function TLockfree_MPMC.push(tm : tNodeQueue):boolean;
> var lasttail,newtemp:long;
> i,j:integer;
> begin
>
>   if getlength >= fsize
>    then
>        begin
>            result:=false;
>            exit;
>        end;
> result:=true;
>
> newTemp:=LockedIncLong(temp);
>
> lastTail:=newTemp-1;
> //asm mfence end;
> setObject(lastTail,tm);
>
> repeat
>
>   if CAS(tail,lasttail,newtemp)
>     then
>        begin
>         event.setevent;
>         exit;
>        end;
> sleep(0);
>   until false;
>
> end;
>
>
> function TLockfree_MPMC.pop(var obj:tNodeQueue;wait:boolean=false):boolean;
>
> var lastHead : long;
> begin
>    repeat
>    lastHead:=head;
>    if tail<>head
>     then
>      begin
>        obj:=getObject(lastHead);
>
>            if CAS(head,lasthead,lasthead+1)
>            then
>             begin
>              result:=true;
>             exit;
>             end
>            else  sleep(0); //backoff2.delay;
>
>       end
>     else
>         begin
>          if wait=false
>            then
>             begin
>              result:=false;
>               exit;
>             end;
>
>         if self.count <> 0
>          then continue;
>
>         if self.count=0
>             then
>              begin
>                self.event.waitfor(INFINITE);
>                self.event.resetevent;
>              end;
>          end;
>    until false;
> end;
>
> function TLockfree_MPMC.getLength:long;
> var head1,tail1:long;
> begin
> head1:=head;
> tail1:=tail;
>    if tail1 < head1
>         then result:= (High(long)-head1)+(1+tail1)
>         else result:=(tail1-head1);
> end;
>
> function TLockfree_MPMC.getSize:long;
>
> begin
>    result:=fSize;
> end;
>
> end.
> ===
>
>
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>
>
>

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

#3931

Fromaminer <aminer@toto.net>
Date2013-10-12 19:28 -0700
Message-ID<l3clup$vun$1@news.albasani.net>
In reply to#3929
On 10/12/2013 6:55 PM, aminer wrote:
> if self.count=0
>             then
>              begin
>                self.event.waitfor(INFINITE);
>                self.event.resetevent;
>              end;
>          end;


This method doesn't work , cause if a thread1 was on
"self.event.waitfor(INFINITE)" and another thread2 corossed
the "if self.count=0" , and if thread2 has not arrive yet to 
"self.event.waitfor(INFINITE)" , and  thread1 has
received two setevent() from the push() method and it has called after
that  "self.event.resetevent" , so thread2 will stop and wait
on "self.event.waitfor(INFINITE)" even if there is  items in the queue, 
so this is a problem.



I will still think more about a method to satisfy the efficency 
requirement without using SemaCondvar or Semaphore cause they are slow.



Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web