Electrical computers and digital data processing systems: input/ – Access arbitrating – Hierarchical or multilevel arbitrating
Reexamination Certificate
2001-03-19
2004-05-11
Auve, Glenn A. (Department: 2112)
Electrical computers and digital data processing systems: input/
Access arbitrating
Hierarchical or multilevel arbitrating
C710S120000, C714S051000
Reexamination Certificate
active
06735654
ABSTRACT:
1. FIELD OF THE INVENTION
The present invention relates to the field of multiprocessor computer systems and, more particularly, to the architectural connection of multiple microprocessors within a multiprocessor computer system.
2. BACKGROUND
Multiprocessing computer systems include two or more microprocessors that may be employed to perform computing tasks. A particular computing task may be performed on one microprocessor while other microprocessors perform unrelated computing tasks. Alternatively, components of a particular computing task may be distributed among multiple microprocessors to decrease the time required to perform the computing task as a whole.
A popular architecture in commercial multiprocessing computer systems is the symmetric multiprocessor (SMP) architecture. Typically, an SMP computer system comprises multiple microprocessors connected through a cache hierarchy to a shared bus. Additionally connected to the bus is a memory, which is shared among the microprocessors in the system. Access to any particular memory location within the memory occurs in a similar amount of time as access to any other particular memory location. Since each location in the memory may be accessed in a uniform manner, this structure is often referred to as a uniform memory architecture (UMA).
Processors are often configured with internal caches, and one or more caches are typically included in the cache hierarchy between the microprocessors and the shared bus in an SMP computer system. Multiple copies of data residing at a particular main memory address may be stored in these caches. In order to maintain the shared memory model, in which a particular address stores exactly one data value at any given time, shared bus computer systems employ cache coherency. Generally speaking, an operation is coherent if the effects of the operation upon data stored at a particular memory address are reflected in each copy of the data within the cache hierarchy. For example, when data stored at a particular memory address is updated, the update may be supplied to the caches that are storing copies of the previous data. Alternatively, the copies of the previous data may be invalidated in the caches such that a subsequent access to the particular memory address causes the updated copy to be transferred from main memory. For shared bus systems, a snoop bus protocol is typically employed. Each coherent transaction performed upon the shared bus is examined (or “snooped”) against data in the caches. If a copy of the affected data is found, the state of the cache line containing the data may be updated in response to the coherent transaction.
Unfortunately, shared bus architectures suffer from several drawbacks which limit their usefulness in multiprocessing computer systems. As additional microprocessors are attached to the bus, the bandwidth required to supply the microprocessors with data and instructions may exceed the peak bandwidth of the bus. Thus, some microprocessors may be forced to wait for available bus bandwidth and the performance of the computer system will suffer when the bandwidth requirements of the microprocessors exceed available bus bandwidth.
Additionally, adding more microprocessors to a shared bus increases the capacitive loading on the bus and may even cause the physical length of the bus to be increased. The increased capacitive loading and extended bus length increases the delay in propagating a signal across the bus. Due to the increased propagation delay, transactions may take longer to perform. Therefore, the peak bandwidth of the bus may decrease as more microprocessors are added.
A common way to address the problems incurred as more microprocessors and devices are added to a shared bus system, is to have a hierarchy of buses. In a hierarchical shared bus system, the microprocessors and other bus devices are divided among several low-level buses. These low-level buses are connected by high-level buses. Transactions are originated on a low-level bus, transmitted to the high-level bus, and then driven back down to all the low level-buses by repeaters. Thus, all the bus devices see the transaction at the same time and transactions remain ordered. The hierarchical shared bus logically appears as one large shared bus to all the devices. Additionally, the hierarchical structure overcomes the electrical constraints of a single large shared bus.
3. SUMMARY OF INVENTION
One embodiment of the invention is a computer system including a first repeater; a second repeater coupled to the first repeater; and a third repeater coupled to the first repeater. The second repeater is also coupled to a first client and a second client. The second repeater contains a distributed arbiter that predicts whether the first repeater will send a transaction to the second repeater.
Another embodiment of the invention is a computer system including a first repeater; a second repeater coupled to the first repeater; and a third repeater coupled to the first repeater. The second repeater is also coupled to a first client and a second client. The second repeater contains a distributed arbiter that predicts whether the first repeater will send a transaction to the third repeater.
Still another embodiment of the invention is a computer system including a first repeater; a second repeater coupled to the first repeater; and a third repeater coupled to the first repeater. The second repeater is also coupled to a first client and a second client. The second repeater contains a distributed arbiter that predicts whether the first repeater will send a transaction to the second repeater and whether the first repeater will send a transaction to the third repeater.
REFERENCES:
patent: 5265123 (1993-11-01), Vijeh et al.
patent: 5519838 (1996-05-01), Ziegler et al.
patent: 5546587 (1996-08-01), Silver
patent: 5588125 (1996-12-01), Bennett
patent: 5754877 (1998-05-01), Hagersten et al.
patent: 5796605 (1998-08-01), Hagersten
patent: 5805839 (1998-09-01), Singhal
patent: 5933610 (1999-08-01), Chambers et al.
patent: 5954809 (1999-09-01), Riley et al.
patent: 5960034 (1999-09-01), Lo
patent: 6078337 (2000-06-01), Fukui et al.
patent: 6108736 (2000-08-01), Bell
patent: 6167403 (2000-12-01), Whitmire et al.
patent: 6243411 (2001-06-01), Chiou
patent: 6282588 (2001-08-01), Yamamoto
patent: 6295281 (2001-09-01), Itkowsky et al.
patent: 6411628 (2002-06-01), Hauck et al.
patent: 6446215 (2002-09-01), Meyer et al.
patent: 2002/0133657 (2002-09-01), Quan et al.
patent: 0817094 (1998-01-01), None
U.S. application Ser. No. 09/815,442, Quanet al., Method and Apparatus for Efficiently Broadcasting Transactions between a First Address Repeater and a Second Address Repeater, Mar. 19, 2001.
U.S. application Ser. No. 09/815,443, Quanet al., Method and Apparatus for Verifying Consistency between a First Address Repeater and a Second Address Repeater, Mar. 19, 2001.
Lewis James C.
Quan Tai
Smith Brian L.
Auve Glenn A.
Lee Christopher E.
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Method and apparatus for efficiently broadcasting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for efficiently broadcasting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficiently broadcasting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3205637