dave@dtg.nsc.com (David Hawley) (12/14/89)
Arbitration: an often-neglected but critical part of system design. With so many standard and proprietary bus designs out there, I'm curious how different approaches trade off flexibility, speed, and number of bus lines. This posting briefly comments on the Futurebus+ mechanism. I wasn't planning to post, except for this request: > From: Andy 'Krazy' Glew <afgg6490@uxa.cso.uiuc.edu> > Please post your response. It's time that comp.arch discussed things like > this, instead of the microeconomics of computer centers. Or CPU MIPS wars! > From: afgg6490@uxa.cso.uiuc.edu > Message-ID: <112400008@uxa.cso.uiuc.edu> > > I have worked with several systems where bus arbitration time > was one of the principal bottlenecks. IE. full bus bandwidth > could never be acheived in a real system because (1) all those > asynch signals were being synchronized, and (2) the system > spent much of its time asking "please can I use the bus" > instead of actually using it. (1) Big problem. A certain amount of synchronization is unavoidable; the key is to limit it to the request/grant handshake only. (2) Two problems here - board access latency and bus arbitration cycle time vs. bus tenure. Consider both bus idle and occupied conditions. > Nubus distributed arbitration seems simple enough, but the wave > form of scheduling probably is not acceptable to hard real time > (fixed priority) scheduling (see Shan "a bus access should be > scheduled at the same priority as a bus access"). Nubus, Multibus II, and Futurebus all use the same basic parallel contention logic for resolving multiple requests. A "fairness" protocol is layered over this logic. In order to allow real-time priority scheduling, a priority protocol also must be layered. None of this is easy; all of it takes time, bus lines, or both. > Futurebus+ distributed arbitration seems to further complicate things. > [O(N) settling of arbitration codes, asynch signals, slow/synchronous > implementations, long and short arb cycles, priority manipulation rules] Without getting into details, or trying to rebut specific comments - Some aspects of Futurebus+ arbitration are limited by the slowest logic in the system, some by the slowest in a group of competitors, and some only by the speed of the winning board. This makes the implementation of the protocol critical. Synchronizing to any clock is suicide. The protocol is complex, but the committee had a number of historical, political, and schedule constraints, as well as functional ones (eg, real-time priority scheduling). Bus interface silicon should eventually hide some of this complexity, as well as improve speed. > What we need is a distributed arbitration scheme that > (1) is positive - instead of waiting for a potentially long time > interval for stability of of the arbitration code, grants when > all contestants acknowledge the same winner (ok, that's already been done) This can be done by assigning one line per board and/or priority level. Typically, however, some compromises have to be made if you want true fairness, or dynamic priority selection. > (2) is fast in special circumstances - like idle bus (without requiring > a special arbitration mode) The best way is to make the protocol fast enough so that it doesn't really matter. Idle bus arbitration is a special (optional) mode in Futurebus+. I would be interested in seeing a protocol that can seamlessly integrate it into normal arbitration. > (3) supports stripped down priority manipulation (like, none) > in systems where it is appropriate. Ah! A special arbitration mode! :-) > Yes, I have seen how FUTUREBUS+ can derive a different timing parameter for > every board in its arbitration contest. I don't ever want to have to > debug it (meaning, if you can give me a guaranteed implementation, > I'll be happy). Seems fragile. Proof of existence: Tektronix ships systems based on the old (1987) Futurebus protocols. Designs based on the new protocols are underway. Dave Hawley National Semiconductor Corp. dave@dtg.nsc.com (408)721-6742