Split transactions and pipelined arbitration of microprocessors in multiprocessing computer systems

• US 5,553,310 A
• Filed: 10/02/1992
• Issued: 09/03/1996
• Est. Priority Date: 10/02/1992
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Tipley, Roger E., Culley, Paul R., Taylor, Mark, Melo, Maria L.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): PERVEEN, REHANA
• Application Number:
  US07/955,930
• Time in Patent Office: 1,432 Days
• Field of Search: 395/200, 395/325, 395/275, 395/550, 395/425, 395/478, 395/728, 395/860, 364/900, 370/85
• US Class Current: 710/40
• CPC Class Codes: G06F 13/364 using independent requests or grants, e.g. using separated request and grant lines

Abstract

Three prioritization schemes for determining which of several CPUs receives priority to become bus master of a host bus in a multiprocessor system, and an arbitration scheme for transferring control from one bus master to another. Each prioritization scheme prioritizes n elements, where a total of (n/2)×(n-1) priority bits monitors the relative priority between each pair of elements. An element receives the highest priority when each of the n-1 priority bits associated with that element points to it. In the arbitration scheme, the current bus master of the host bus determines when transfer of control of the host bus occurs as governed by one of the prioritization schemes. The arbitration scheme gives EISA bus masters, RAM refresh and DMA greater priority than CPUs acting as bus masters, and allows a temporary bus master to interrupt the current bus master to perform a write-back cache intervention cycle. The arbitration scheme also supports address pipelining, bursting, split transactions and reservations of CPUs aborted when attempting a locked cycle. Address pipelining allows the next bus master to assert its address and status signals before the beginning of the data transfer phase of the next bus master. Split transactions allows a CPU posting a read to the EISA bus to arbitrate the host bus to another device without re-arbitrating for the host bus to retrieve the data. The data is asserted on the host bus when it is idle even if the host bus is being controlled by another device.

Claims

1. A computer system, comprising:

a system bus including a busy line, a plurality of request lines and a plurality of acknowledge lines;

a plurality of microprocessors coupled to said system bus, said plurality of microprocessors numbering n, each said microprocessor including means for providing a request signal on a corresponding one of said system bus request lines, means for detecting an acknowledge signal on a corresponding one of said system bus acknowledge lines, and means for detecting and providing a busy signal on said system busy line; and

a prioritizer coupled to said system bus for receiving said request signals, for receiving said busy signal and providing said acknowledge signals, said prioritizer prioritizing between said plurality of microprocessors based on said received request signals, providing said acknowledge signals on said system bus acknowledge lines wherein only one acknowledge signal is provided at a time on one of said acknowledge lines corresponding to said microprocessor having the highest priority, said prioritizer further including;

means for providing a plurality of bus control signals, each said bus control signal indicating whether a corresponding microprocessor has control of said system bus;

a plurality of relative priority storage means, each said relative priority storage means corresponding to a unique pair of said plurality of microprocessors, each said unique pair being formed by combining a first microprocessor with a second microprocessor, each microprocessor being paired n-1 times, each microprocessor combining with a different microprocessor, each said relative priority storage means for providing a relative priority signal indicative of the relative priority between said microprocessors of said corresponding unique pair, each said relative priority storage means receiving said bus control signal corresponding to the first said microprocessor of said unique pair, each said relative priority storage means including an update input receiving an update signal for indicating that said value of said microprocessor bus control signal is to be stored, said stored value indicating the relative priority between said microprocessors of said corresponding unique pair;

means receiving the plurality of microprocessor bus control signals for providing an update signal to a particular relative priority storage means storage update input when either of said microprocessors corresponding to said unique pair of microprocessors of said particular relative priority storage means has had control of said system bus; and

means receiving all of said relative priority signals for combining said relative priority signals relating to each individual microprocessor and for indicating that a particular microprocessor has the highest priority of all of said plurality of microprocessors if all of said relative priority signals for said particular microprocessor indicate said particular microprocessor has priority relative to the other microprocessor of said unique pair,

wherein each of said plurality of relative priority storage means further receives the request signals corresponding to the particular microprocessors of said unique pair and provides an output signal indicative of said stored value and further includes a passing and inverting means receiving said stored value output signal and said corresponding request signals and providing said relative priority signal for passing said stored value output signal as said relative priority signal if said stored value output signal indicates a particular microprocessor and said particular microprocessor request signal is provided and for inverting said stored value output signal and providing said inverted signal as said relative priority signal if said stored value output signal indicates a particular microprocessor, said particular microprocessor request signal is not provided and said other microprocessor request signal is provided and

wherein said microprocessor means for detecting and providing a busy signal removes said busy signal when said microprocessor releases control of said bus and provides said busy signal when said acknowledge line for said microprocessor is provided and said bus signal is removed.

2. The computer system of claim 1,

wherein said passing and inverting means further passes said stored value output signal as said relative priority signal if neither of said request signals from said corresponding microprocessors are provided.

3. The computer system of claim 1,

wherein said passing and inverting means further inverts said stored value output signal and provides said inverted signal as said relative priority signal if neither of said request signals from said corresponding microprocessors are provided.

4. A computer system, comprising:

a system bus including a busy line, a plurality of request lines and a plurality of acknowledge lines;

a plurality of microprocessors coupled to said system bus, said plurality of microprocessors numbering n, each said microprocessor including means for providing a request signal on a corresponding one of said system bus request lines, means for detecting an acknowledge signal on a corresponding one of said system bus acknowledge lines, and means for detecting and providing a busy signal on said system busy line; and

a prioritizer coupled to said system bus for receiving said request signals, for receiving said busy signal and providing said acknowledge signals, said prioritizer prioritizing between said plurality of microprocessors based on said received request signals, providing said acknowledge signals on said system bus acknowledge lines wherein only one acknowledge signal is provided at a time on one of said acknowledge lines corresponding to said microprocessor having the highest priority, said prioritizer further including;

means for providing a plurality of bus control signals, each said bus control signal indicating whether a corresponding microprocessor has control of said system bus;

a plurality of relative priority storage means, each said relative priority storage means corresponding to a unique pair of said plurality of microprocessors, each said unique pair being formed by combining a first microprocessor with a second microprocessor, each microprocessor being paired n-1 times, each microprocessor combining with a different microprocessor, each said relative priority storage means providing a relative priority signal indicative of the relative priority between said microprocessors of said unique pair, each said relative priority storage means having a storage input;

means receiving all of said relative priority signals for combining said relative priority signals relating to each individual microprocessor and for indicating that a particular microprocessor has the highest priority of all of said plurality of microprocessors if all said relative priority signals for said particular microprocessor indicate said particular microprocessor has priority relative to the other microprocessor of said unique pair; and

a plurality of passing and inverting means receiving said request signals and said relative priority signals, each said passing and inverting means corresponding to a particular said relative priority storage means, each said passing and inverting means receiving the request signals corresponding to the particular microprocessors in the unique pair of said corresponding relative priority storage means and the relative priority signal from said corresponding relative priority storage means, each said passing and inverting means having a relative requested priority signal which is connected to said storage input of said corresponding relative priority storage means, each said passing and inverting means for passing said relative priority signal as said relative requested priority signal if said relative priority signal indicates a particular microprocessor and said particular microprocessor request signal is provided and for inverting said relative priority signal and providing said inverted signal as said relative requested priority signal if said relative priority signal indicates a particular microprocessor, said particular microprocessor request signal is not provided and said other microprocessor request signal is provided,

wherein said microprocessor means for detecting and providing a busy signal removes said busy signal when said microprocessor releases control of said bus and provides said busy signal when said acknowledge line for said microprocessor is provided and said busy signal is removed.

5. The computer system of claim 4,

wherein said passing and inverting means further passes said stored value output signal as said relative priority signal if neither of said request signals from said corresponding microprocessors are provided.

6. The computer system of claim 4,

wherein said passing and inverting means further inverts said stored value output signal and provides said inverted signal as said relative priority signal if neither of said request signals from said corresponding microprocessors are provided.

7. A computer system, comprising:

a system bus including a data bus, an address bus, a busy line, a plurality of request lines and a plurality of acknowledge lines;

a plurality of microprocessors coupled to said system bus, said plurality of microprocessors numbering n, each said microprocessor including means for providing an address on said address bus, means for receiving and providing data on said data bus, means for providing a request signal on a corresponding one of said system bus request lines, means for detecting an acknowledge Signal on a corresponding one of said system bus acknowledge lines, and means for detecting and providing a busy signal on said system busy line; and

a prioritizer coupled to said system bus for receiving said request signals, for receiving said busy signal and providing said acknowledge signals, said prioritizer prioritizing between said plurality of microprocessors based on said received request signals, providing said acknowledge signals on said system bus acknowledge lines wherein only one acknowledge signal is provided at a time on one of said acknowledge lines corresponding to said microprocessor having the highest priority,

wherein said microprocessor means for detecting and providing a busy signal removes said busy signal when said microprocessor releases control of said bus and provides said busy signal when said acknowledge line for said microprocessor is provided and said busy signal is removed, and

wherein a first microprocessor means for detecting and providing a busy signal removes said busy signal prior to completion of a data transfer cycle and said first microprocessor means for providing addresses removes said addresses prior to completion of said data cycle and a second microprocessor means for detecting and providing a busy signal provides said busy signal prior to completion of said data transfer cycle and said second microprocessor means for providing addresses provides addresses prior to completion of said data transfer cycle.

8. A computer system, comprising:

a system bus including a data bus, an address bust a backoff line, a busy line, a plurality of request lines and a plurality of acknowledge lines;

a plurality of microprocessors coupled to said system bus, said plurality of microprocessors numbering n, each said microprocessor including means for providing an address on said address bus, means for receiving and providing data on said data bus, means for providing a request signal on a corresponding one of said system bus request lines, means for detecting an acknowledge signal on a corresponding one of said system bus acknowledge lines, and means for detecting and providing a busy signal on said system busy line, and

a prioritizer coupled to said system bus for receiving said request signals, for receiving said busy signal and providing said acknowledge signals, said prioritizer prioritizing between said plurality of microprocessors based on said received request signals, providing said acknowledge signals on said system bus acknowledge lines wherein only one acknowledge signal is provided at a time on one of said acknowledge lines corresponding to said microprocessor having the highest priority,

wherein said microprocessor means for detecting and providing a busy signal removes said busy signal when said microprocessor releases control of said bus and provides said busy signal when said acknowledge line for said microprocessor is provided and said busy signal is removed;

wherein at least one microprocessor further includes means for providing a backoff signal to said backoff line to indicate need for temporary control; and

wherein a first microprocessor means for providing an address and means for providing data receive said backoff signal and cease providing an address and data while said backoff signal is provided and said first microprocessor means for detecting and providing a busy signal continues to provide said busy signal while said backoff signal is provided.

9. A computer system, comprising:

a system bus including a busy line, a plurality of request lines, a plurality of acknowledge lines, a data bus, an address bus, a ready line, a data bus request line and a read-write line;

an I/O bus;

a device coupled to said I/O bus;

a plurality of microprocessors coupled to said system bus, said plurality of microprocessors numbering n, each said microprocessor including means for providing a request signal on a corresponding one of said system bus request lines, means for detecting an acknowledge signal on a corresponding one of said system bus acknowledge lines, and means for detecting and providing a busy signal on said system busy line, each said microprocessor including means for initiating a read cycle which is posted by providing an address on said address bus for selecting said device coupled to said I/O bus and providing a read signal on said read-write line and receiving a ready signal, wherein each said microprocessor releases control of said system bus after receiving said ready signal and retrieves data from said data bus when a data bus request signal is negated after being asserted on said data bus request line while another of said plurality of microprocessors is in control of said system bus;

a prioritizer coupled to said system bus for receiving said request signals, for receiving said busy signal and providing said acknowledge signals, said prioritizer prioritizing between said plurality of microprocessors based on said received request signals, providing said acknowledge signals on said system bus acknowledge lines wherein only one acknowledge signal is provided at a time on one of said acknowledge lines corresponding to said microprocessor having the highest priority wherein said microprocessor means for detecting and providing a busy signal removes said busy signal when said microprocessor releases control of said bus and provides said busy signal when said acknowledge line for said microprocessor is provided and said busy signal is removed; and

an I/O bus controller means coupled to said system bus and said I/O bus, said I/O bus controller means comprising;

means for posting a read cycle on said system bus to said I/O bus, wherein said posting means receives said address on said address bus for selecting said device coupled to said I/O bus and further receives said read signal on said read-write line, wherein said posting means provides said ready signal on said ready line in response to posting said read cycle;

means coupled to said read cycle posting means and said I/O bus for providing said posted address and read signal to said I/O bus and controlling a read cycle on said I/O bus to perform the read operation of said device;

means coupled to said I/O bus for retrieving said data from said device coupled to said I/O bus in response to said read cycle being performed by said device;

means for determining when said data bus is idle and for providing an idle signal when said data bus is idle; and

means receiving said idle signal for providing said data from said device coupled to said I/O bus to said data bus, wherein said providing means includes means for asserting said data bus request signal on said data bus request line after said read cycle is posted by said read cycle posting means and before said idle signal is received and for asserting said data on said data bus and negating said data bus request signal when said idle signal is received.