Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #3930
| From | aminer <aminer@toto.net> |
|---|---|
| Newsgroups | comp.programming.threads, comp.programming |
| Subject | Re: There is a solution to satisfy the energy efficiency requirement |
| Date | 2013-10-12 18:57 -0700 |
| Organization | albasani.net |
| Message-ID | <l3ck5m$t7b$4@news.albasani.net> (permalink) |
| References | <l3ck10$t7b$1@news.albasani.net> |
Cross-posted to 2 groups.
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.
>
>
>
>
Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web