Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming.threads > #792
| From | "Chris M. Thomasson" <cristom@charter.net> |
|---|---|
| Newsgroups | comp.programming.threads |
| References | (5 earlier) <0c5cc2bb-e1f6-4f31-89ed-37bef98511c3@u6g2000vbg.googlegroups.com> <8sRIq.32436$%O.17120@newsfe20.iad> <1bab5329-ce78-4b92-8dc8-8567f82480c2@i6g2000vbe.googlegroups.com> <WWSIq.36912$_H.27859@newsfe16.iad> <3547e238-89e9-41e8-b747-fe5f12f5718e@i6g2000vbh.googlegroups.com> |
| Subject | Re: Parallel Gauss-Seidel with relaxation iterative algorithm library version 1.1 |
| Message-ID | <5UTIq.177$ae4.66@newsfe01.iad> (permalink) |
| Date | 2011-12-22 20:59 -0800 |
"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.
Back to comp.programming.threads | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web