> > John Payson wrote in an earlier message to the Piclist that he has a > > 3-wire communication protocol for connecting an arbitrary number of > > devices that may be arbitrarily busy. However, to the best of my > > knowledge, he has not given any further details of his protocol. > > Sorry 'bout that. :-) Lured you out of the hole, finally... :-) Thanks for your illuminating comments! > Well, there are skew and such requirements to be dealt with if cable lengths > are significant, but in most cases uniformity of signal arrival should not > be a problem; the biggest limitation on speed will likely come from the CPU > speeds since the protocol is intended for non-hardware-assisted applications. I'm sorry I was sloppy about clearly stating my assumptions. When I say "self-timed" I mean that the protocol should give the same result regardless of the delays in the wires. You use it in a slightly different (less extreme) meaning, with the very reasonable assumption that wire propagation time is small. I think both of these can be referred to as "self-timed." In my sense, skew cannot be a problem by definition, or otherwise the protocol wouldn't be self-timed. (When I say "self-timed" in the following, I refer to it in this sense unless noted otherwise.) This is a stronger constraint on the algorithms. You are right as you say that the bottleneck is often "ts," the switching time from reading the port to setting it. However, with faster hardware, the bottleneck will be "tp," the propagation delay on the bus. The absolute minimum of tp is c/L, where c is the speed of light, and L is the length of the bus, which means about 3 ns for L = 1 m. That is for an optical bus. For a bus made of copper, tp will be more like an order of magnitude larger, or about 30 ns. For supercomputers and other extreme high performance bus applications where ts<>tp, self-timed protocols will likely be much faster. For ts< Nice scheme. Unfortunately, I think it breaks if master sends a 1 followed > by a 0. Specifically: XYZ are the devices [X master]; for each state the > devices following the name in uppercase are those that are asserting the > line, those in lowercase are those that have last sampled the line as > asserted, and those in lowercase preceded by "!" are those that have last > sampled the line unasserted: > > A=xYZ B=X > A=xyZ B=XY > A=y B=XYZ ; Z has released A; X and Z have polled it and seen it high; Y > hasn't polled it yet. > A=XZ B=Y ; B is still waiting for A to be de-asserted. > > It looks like you account for this in your change-of-master handling (which > you IMHO overcomplicate) but you don't account for it in the bit-sending > protocol. You are absolutely right. This is a bug, but it can be fixed (below). I find some consolation in the fact that you are making precisly the same mistake in your own procedure... :-) If you rename your wires 01K to BCA, your "Send Zero" procedure sends precisely the problematic "10" sequence. > My protocol for three wires or four-wires low-overhead is as follows: > [wire names: "0", "1", "K", and "A" for zero, one, acK, and Attention; > the Attention wire is optional] > > [in four-wire state description "-" means wire asserted by nobody; "M" > means asserted by master only; "S" by slave only; "X" by "everyone"; > "*" by master and [maybe] slaves] > > Idle State: 01KA = --XX > Send Zero : 01KA = M-SX X--X S-MX --XX > Send One : 01KA = -MSX -X-X -SMX --XX If I paraphrase it using the "follow the leader" metaphor, the bug is that if the leader (master) returns to the previous position, a slave will not be able to tell whether it is the leader that holds down the line, or if it is a slow slave that hasn't moved yet. I guess this bug shows how easy it is to make mistakes when designing self-timed circuits. In order to send a bit, there must be a selection of at least two distinguishable states for the master to move to. This seems to require at least four wires in my scheme. If the wires are ABCD, and the initial idle state is A, the first move is A->AB->B, the master *cannot* move B->AB for the above reason, but has to move either B->BC->C or B->BD->D. This selection gives one bit of information. > > Suppose again that the current idle state is A. In order to transfer > > control to a new master, the old master asserts B, releases A, and > > converts to a slave. > > With a protocol like the above, there is no such complex requirement for a > master/slave handoff. Since everyone [including the old and new master] > explicitly acknowleges everything they see, no one except the master needs > to know who's master. Unfortunately, there must be a handoff for the protocol to be strictly self-timed. Your "clobber" and "attention" procedures are asynchronous relative to the bit sending protocol. This is what I find really tricky. It may be the best asynchronous approach, but I would need to consider it more carefully. A read by a master from a slave is an example where you absolutely want to have atomic bus access. The master sends the address to the slave, converts the slave into master, and has the data sent back. Nobody should be let in on the bus until the process is complete. > > The really tricky thing is arbitration in a multi-master system. This > > is impossible in a pure self-timed system, so there are two > > possibilities: > > Why is arbitration impossible in a self-timed system if devices have > unique addresses? I'm sorry I was careless about my formulations. Arbitration between two contenders is not possible (with my definition self-timed) since it introduces dependence on wire delays. Corrections to the final part: Protocols can be constructed in the same way as before, but there is one choice less for the master at every stage, so it should be modified as follows: [Nerd warning] A six-wire protocol can be constructed in the same way as the four-wire scheme. Then we get 1/3 bits/wire/time unit. It can be further generalized to n wires, of which k are asserted in an idle state. I spent saturday night proving [proof still holds] that the maximum bandwidth/wire 2 is log Phi bits/wire/time unit = 0.694, where Phi is the golden ratio = 1.618... . I hadn't expected this ratio to go over 0.5, but one can get arbitrarily close to it for large n (it is a tight bound). Some interesting pairs (n, bits) are (4, 1), (6, 2), (7, 3), (9, 4), (15, 8), (21,12),... > Well, I think for a 10/4 solution an easier approach is to have two control > wires and eight data wires. In the idle state, the wires are > X- lastbyte > To send two bytes of data, the transitions should be > SM -byte 1- > -X -byte 1- > MS -byte 2- > X- -byte 2- > > Not as mathematically elegant as an arithmetic code, but easier I suspect. > BTW, does your formula consider deadlock avoidance as a requirement? Your protocol here is simpler, but it is not self-timed in the sense I have used. My formula does require self-timing, which with my definition implies being deadlock-free. -- Martin Martin Nilsson Swedish Institute of Computer Science E-mail: mn@sics.se Box 1263, S-164 28 Kista Fax: +46-8-751-7230 Sweden Tel: +46-8-752-1574