I continuously read that the daisy-chained bus grant arbitration algorithm, such as is used in VMEbus, STEbus, Apple II bus, etc., is "unfair." I'd like to know exactly what this means. Searching for additional detail or explanation yields only additional documents which repeats this mantra as though it were religious truth. I never see any justification for the claim.

That being said, I want to make absolutely clear that I do not disbelieve the claim. Implemented poorly or with uncooperative bus masters, I can readily see how a card can deny lower-priority cards access to the bus. However, these are, I think, pathological cases -- a busted PCI card will quite happily sieze up the entire PCI bus on an Intel motherboard, rendering the entire computer useless for as long as its in its slot. Yet, PCI relies, ostensibly, on a bus arbitration system which guarantees bus fairness.

As I understand the algorithm, a daisy-chained bus arbitration system relies on four signals:

* BR_O -- Bus Request, output.

* BR_I -- Bus Request, input. This signal is the logical-OR of all BR_O pins on all expansion slots. It also feeds the highest priority card's BG_I signal.

* BG_I -- Bus Grant, input. Together with BG_O, this signal grants the peripheral access to the bus. The card holds onto the bus for as long as it keeps BG_O low.

* BG_O -- Bus Grant, output. When the peripheral has completed its use of the bus, or if it never requested the bus in the first place, it passes BG_I to BG_O.

The general algorithm being:

1. If the peripheral does not want the bus, it just sets BG_O directly to the state of BG_I.

2. If BR_I is negated, nobody is using the bus, and so all BG_I and BG_O pins are similarly negated.

3. If the peripheral wants the bus AND BR_I is asserted AND BG_I is low (meaning, it has not yet received its turn to use the bus), it asserts its local BR_O and waits for BG_I high.

4. If the peripheral wants the bus AND BR_I is asserted AND BG_I is already high, at least one lower-priority peripheral is already using the bus. Wait until its both BR_I and its local BG_I are negated, thus bringing the card into state 3.

5. When the peripheral has completed use of the bus, it negates BR_O and sets BG_O equal to BG_I.

It's states 3 and 4 which I think preserves the quality of "fairness," assuming I have an understanding of what "fairness" means in this context.

Please let me know if my understanding of "fair" is incorrect here; this algorithm seems every bit as fair as the arbitration algorithm used by PCI and other ostensibly "fair" algorithms.

Since my STD 65816 project is on hold due to my final year design project taking up too much time. However I am dealing with a Bus system in my final year design project I'll mention it, the CANbus used in automotive/aerospace/medical applications.

It uses a twisted pair connection, with a high and low, however both lines are positive lines, and not a negative and positive voltage that flip flops like RS-485.

To control the bus, there is no "master" node per say. Just a bunch of various nodes that can send messages along the entire bus. A 11 bit, or 29 bit message ID and up to 8 bytes of data that follow it, including error detection (not correction) check sums.

A node watches the bus to be idol state for 11 cycles before it will attempt to message. Which gives the controller nodes enough time to process the information received.

Additionally when any one node transmits a logical 1, the whole bus goes to a logical one state, whether or not another node is trying to transmit. Which kills any signals, and the nodes on the system know that there was a fault cause the checksums will not match and they will disregard the package.

When nodes go dark, there is no real way to know it. Cause the "Acknowledged" signal is actually given out by the transmitting node and not the receiving nodes. Which means, if there is one, or one thousand nodes accepting the messages, the node that transmits the signal will never know (Unless you design your application layer so that nodes will respond with NEW messages after receiving a specific message ID/data).

It also means, when a single node goes "dark" the transmitting node is not wasting bus time trying to transmit the message repeatedly with no acknowledge response from the node it believes should be accepting it.

Dimitri

I was searching on the net and to my surprise I didn't find much (I assume you already did that anyway...). There is some wikipedia article on fair scheduling and fair queueing, like here http://en.wikipedia.org/wiki/Fair_queuing Fair there means that any single sender cannot "cannot take more than its fair share of the link capacity".

In your context that means that a single requester that gets a bus grant can take an "unfair" share of the bus. If you have N devices, a fair share would be 1/Nth of the bus bandwidth if all devices try to get the bus at the same time. Free bandwidth can also be distributed in a "fair" way, e.g. if half of the devices don't need the bus right now, the available bandwidth should not go to a single device, but be distributed evenly.
Fair can also be defined in terms of latency. Even if devices can get their share of the bandwidth, if higher priority devices can interrupt lower priority devices and not vice versa, they have a much better average latency. One important thing to achieve fairness seems to be that a single transfer has a defined maximum length, or can be interrupted by an arbiter to schedule bandwidth to another requester.

A bus scheduling algorithm is thus inherently unfair if is it cooperative, i.e. it relies on the devices to release the bus and transfers cannot be interrupted.


I think your quote "The card holds onto the bus for as long as it keeps BG_O low" says it - the bus transfer cannot be interrupted, thus it is inherently unfair...

At least that's what I understand.

André

I was hoping that it'd be obvious that my question related specifically to backplane buses. I can't think of a single network protocol which makes use of an explicit request/grant channel-access method. It would be amusing, though, to see what a CSMA/CD system of backplane bus design would look like.

That being said, as bandwidths go up, point-to-point network links (e.g., HyperTransport) become more appealing, but then you need switches to route traffic (a hub is just a bus by any other name).

Though, your suggestion is singularly relevant in one very important way: networks guarantee fairness by limiting network packet size. Any device which talks for too long is punished by simply having its packet dropped on the floor by its intended receiver. Thus, if it wants to really communicate, it will have to obey packet length limits. These limits, then, allow other algorithms like CSMA, token ring, etc. to help ensure everyone gets their fair share of link bandwidth.

Then every system on the planet intended to be fair is itself unfair. PCI peripherals hold the bus as long as FRAME# is asserted. Microchannel, often cited as the quintessential fair bus arbitration scheme, still allows a peripheral to hold onto the bus as long as an EOT condition isn't detected. And so on.

This is what I meant when I said that these are all pathological cases -- the whole issue of bus fairness seems like a needless concern and a source of unnecessary complexity, provided cards adhere to a fairness protocol instead. And, by reading the specifications of both PCI and what's available on the web for Microchannel, it seems to me that protocol adherence is a card function there too.

Dmitri brought up CAN, which is a specific case of a network protocol. Networks ensure fairness usually by limiting how big any single packet can get. Why couldn't we just do the same for a daisy-chain solution? E.g., you can hold the bus no more than N clock cycles. Exceeding this limit may result in punitive action by the bus controller.

And, it seems a lot easier to punish a card with daisy-chaining than with other systems. Mixing a daisy-chain and a credit-based bus access protocol, we can embed logic on the backplane that simply re-routes any given slot's BG_IN to BG_OUT without the card ever seeing its BG_IN until it has re-earned enough credit to participate in the bus arbitration cycle again. Re-routing two signals seems a lot easier than re-routing 64 or more.

It just seems totally unfair to me that the concept of daisy-chained bus arbitration receives such a "bad rap" when they should instead be cherry-picking individual bad implementations instead.

First hit on google, for me, is to a presentation on bus arbitration, and the previous slide in that presentation has this definition:

while the slide I hit first contains this statement about daisy chains:


The intended contrast seems to be with distributed or centralised approaches where, perhaps, a device cannot be locked out by a very busy competitor.

(I'm only mentioning this presentation, neither defending it nor necessarily understanding it.)

Right, which is why I feel that the only way to truly achieve fairness is to require that all peripherals agree to never consume more than some well-known measure of time on the bus. My point is that everyone naively picks on daisy-chaining while heralding such schemes as centralized arbitration, or distributed arbitration with a back-off algorithm (such as that used in Microchannel and NuBus), when these other schemes still must wait for the current master to voluntarily release the bus.

I think the main point is that the protocol - if implemented correctly - should restrict the message size, i.e. the number of bytes to be transferred.



A daisy chain solution has an implicit prioritization. A device "higher" on the bus can always stop lower priority devices from getting the bus at all. I.e. here limiting the packet size is not enough to ensure fairness.

André

To guarantee fairness in this case I think that each of N devices must agree not consume more than about 1/Nth of the bus. Assume all but the lowest priority device to be fully utilizing their bus share. If the N-1 devices take up the full bus the lowest priority device is locked out.

But this scheme is very inefficient when only a few devices need the bus at any one time, lots of bandwidth is wasted as it is reserved for lower priority devices.

One could think of a scheme where a high priority device receives the lower priority device bus request and gives up the bus (after its share has been used) to allow for lower prio bus transfers, but keeps on using the bus if it is no lower device needs the bus. But that can again lock out even higher priority devices that can only use the bus if the device gives up the bus. Of course one could devise a scheme to avoid that again.

All that makes a daisy chain bus more complex - and as far as I understand few if any have implemented this complexity - and just relied on the devices being "nice"...

André

Please tell me how PCI and Microchannel devices guarantee (not just agree, but guarantee) to not consume more than 1/N of the available bus bandwidth?



You keep assuming daisy-chaining assumes the existence of priorities.

If you examine my engagement rules above, you'll find that bus ownership travels around the bus in a ring, thus ensuring no one peripheral has any higher priority than any other.



Which is, in effect, exactly how Microchannel works. When a bus master sees PREEMPT# asserted, it knows at least one other peripheral on the bus wants to become master. It has 7.8 microseconds to release the bus.



Can you find me even one example of a PCI, Microchannel, NuBus, or for that matter any other bus system where the peripherals aren't trusted to be "nice"? Even one? I can't find any.

I think they don't. They just behave.



Ah, now I see it, I have overlooked it before. In step 4 the device waits until all other requests have been serviced, not just the lower priority ones.


Interesting, I didn't know that.



I can't find any in the sense of that they must always follow the specs. Like not overusing the bus, or giving up the bus on request.

So to answer your first question, as I understand it, as long as your devices release the bus after a sensible interval, your algorithm seems as fair as any other algorithm like the ones used for PCI...

André

I was assuming next-neighbor interactions only. In this case I think (without any proof) there is some kind of priority implied.

I didn't think of global signals like your BR_I (which on one hand is some kind of "master" signal, but on the other hand can be implemented with wire-OR)

André

Sorry, perhaps I could have phrased it differently to better avoid confusion. You are correct that if daisy-chaining occurs in the absence of a global "bus in use" status indication, then strict, and static, prioritization occurs.

One disadvantage of using daisy-chaining with a single "bus in use" signal is that you lose any kind of priorities at all. Multiple bus priorities can be implemented with multiple bus in use lines, but at this point, it's cheaper (on a pin-count basis) to use an open-collector arbitration bus like what NuBus or MCA uses.

Thanks for being my sounding board. I've some things to think about w.r.t. a future Kestrel-related experiment. Since I figure I'm going to get myself some kind of FPGA development kit for Christmas this year, I figure I better start thinking of these kinds of things ahead of time.

A CANbus device, can just broadcast the message ID, or it can broadcast up to 8 bytes of data. Which limits "unneeded" talk. Not the best method, especially for high data transfer rate requirements (CANbus is limited to 1Mbit/s) however, its a good model for multi-master bus systems. Since every node can access the bus to transmit data, without being "told" to, which allows listening devices to aquire data without wasting time on the bus to "request" data.

Even if its not inherently a back plane bus it does have some unique features. Which is why I mentioned it.

Dimitri