Well, the z80 is unusual in that writes are atomic even with regards to opcode-reads, which is why the SMC-TaS's work. I was thinking, maybe there's some other SMC hack that has a consensus number of higher than 2?
harold wrote:
Well, the z80 is unusual in that writes are atomic even with regards to opcode-reads, which is why the SMC-TaS's work. I was thinking, maybe there's some other SMC hack that has a consensus number of higher than 2?
I looked up "consensus number" and I think I have a vague idea of what it means, but could I get a concrete example, perhaps?
The consensus number is the maximum threads for which it can solve the consensus problem in a wait-free way.
For example with TaS:
Code:
With Test and Set this only works for 2 threads (assumed to have ID's 0 and 1, without loss of generality) as shown.
For example with TaS:
Code:
int proposal[2];
testandset arbiter;
int submit(int x)
{
proposal[processID] = x;
if (arbiter.TaS() == 1)
return proposal[processID ^ 1]; // return the Other threads x
else
return x; // this thread "won" so return own
}With Test and Set this only works for 2 threads (assumed to have ID's 0 and 1, without loss of generality) as shown.
Ok I just figured out a way to get "atomic fetch-and-increment" - with only 8 states though.
It works with autocopy:
Code:
Only 1 bit should be set (or only one reset) in the byte at (hl).
You can now rrca to get the old state, and obviously it also works when shifting the other way around.
edit: it doesn't improve the situation much though, it also has a consensus number of 2 and that means it can be implemented by Test and Set - the TaS implementation of Fetch-and-Inc uses a number of bytes linear in the number of different states it has to support though.
edit2: w00t I just figured out how to do much better! A consensus number of "as big as your RAM is"! The key to that is LDI (or LDD) which helps because it is an atomic mem-to-mem move. The algorithm to get consensus from that is a bit long to post here in ASM, but in pseudo code it is:
Code:
Where r[x,1] is initialized to 1 and r[x,2] to 0. P is the threadID
It works with autocopy:
Code:
rlc a,(ix+0)Only 1 bit should be set (or only one reset) in the byte at (hl).
You can now rrca to get the old state, and obviously it also works when shifting the other way around.
edit: it doesn't improve the situation much though, it also has a consensus number of 2 and that means it can be implemented by Test and Set - the TaS implementation of Fetch-and-Inc uses a number of bytes linear in the number of different states it has to support though.
edit2: w00t I just figured out how to do much better! A consensus number of "as big as your RAM is"! The key to that is LDI (or LDD) which helps because it is an atomic mem-to-mem move. The algorithm to get consensus from that is a bit long to post here in ASM, but in pseudo code it is:
Code:
decide(input: value) returns(value]
prefer[P] := input
r[P,2] := r[P,1]
for i in P+l to n do
r[i, 1] := 0
end for
for i in n downto 1 do
if r[i,2] == 1
then return prefer[i]
end if
end for
end decideWhere r[x,1] is initialized to 1 and r[x,2] to 0. P is the threadID
I don't know if I would have thought of something like that. 
Register to Join the Conversation
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Advertisement