Browse Prior Art Database

Multi-Processor Bus Distributed Arbitration with Centralized Fairness

IP.com Disclosure Number: IPCOM000108015D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 9 page(s) / 348K

Publishing Venue

IBM

Related People

Sotolongo, HH: AUTHOR

Abstract

Described is a high speed distributed arbitration technique and hardware implementation for a synchronous multi-processor (MP) bus as used in personal systems. The fast arbitration provides prioritized, distributed and a one-way arbitration path delay with a centralized fairness approach which grants the memory bus without increasing the arbitration time. The concept utilizes a prioritized fairness window algorithm to ensure fairness in arbitration and thereby prevents lock- out conditions.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 30% of the total text.

Multi-Processor Bus Distributed Arbitration with Centralized Fairness

       Described is a high speed distributed arbitration
technique and hardware implementation for a synchronous
multi-processor (MP) bus as used in personal systems.  The fast
arbitration provides prioritized, distributed and a one-way
arbitration path delay with a centralized fairness approach which
grants the memory bus without increasing the arbitration time.  The
concept utilizes a prioritized fairness window algorithm to ensure
fairness in arbitration and thereby prevents lock- out conditions.

      The arbitration concept, as shown in Fig. 1, is intended for a
tightly coupled multi-processor system with shared memory.  Bus and
memory bandwidth are often limiting performance factors in such a
system.  Providing fast arbitration and a means to effectively
utilize the available bus and memory bandwidth with the disconnect
function mitigates these factors to some extent.

      The arbitration concept lends itself very well to synchronous
systems with fast clocks in that two clock cycles are used in the
arbitration.  In the first clock cycle, the bus requests are
presented. The full clock cycle is allowed for the requests to
propagate to all other requesters and the memory controller (MC).
During the second cycle, the arbitration function is performed in a
distributed manner by all bus requesters, including the MC.

      Only one-way propagation delay for the arbitration signals is
incurred in the arbitration sequence.  Typical prior-art arbitration
methods produce two-way or multi-way delays.  Aside from the common
clock, there are no external synchronizing signals in this concept.
All bus requesters may request during any cycle without regard to the
request states of other units.  A fairness window algorithm combines
the speed of the distribution arbitration with the central control
afforded by centralized arbitration.  The combination of the two
provides maximum speed without sacrificing fair operation on the bus.

      Although the arbitration method shown in Fig. 1 shows the
design for an eight-processor system, the concept is not limited to
eight.  In actual operation, the MC accesses memory and interfaces
with the MP bus and the system bus. The MC contains the fairness
window logic and buffers to hold data and request information.  The
buffers are used to implement the disconnect feature.  A disconnected
operation is one in which an operation is placed on the bus with all
the required parameters such that the information is buffered in the
MC.  The requesting unit then disconnects, giving up the bus until
such time that the memory operation is completed.  At this time, the
operation is reconnected and data transfers will follow.  The
disconnect feature utilizes bus bandwidth by removing dead time from
a bus transaction. Similarly, memory bandwidth is also better
utilized because a memory operation can start immediately after...