Deadlock avoidance in a computer system having unordered slaves

Details Deadlock avoidance in a computer system having unordered slaves Deadlock avoidance in a computer system having unordered slaves

1997-01-07

1999-07-27

Sheikh, Ayaz R.

395290, 395293, 395308, G06F 1314, G06F 1340

Patent

active

059304855

ABSTRACT:
A mechanism is provided for reordering bus transactions to increase bus utilization in a computer system in which a split-transaction bus is bridged to a single-envelope bus. In one embodiment, both masters and slaves are ordered, simplifying implementation. In another embodiment, the system is more loosely coupled with only masters being ordered. Greater bus utilization is thereby achieved. To avoid deadlock, transactions begun on said split-transaction bus are monitored. When a combination of transactions would, if a predetermined further transaction were to begin, result in deadlock, this condition is detected. In the more tightly coupled system, the predetermined further transaction, if it is requested, is refused, thereby avoiding deadlock. In the more loosely-coupled system, the flexibility afforded by unordered slaves is taken advantage of to, in the typical case, reorder the transactions and avoid deadlock without killing any transaction. Where a data dependency exists that would prevent such reordering, the further transactions is killed as in the more tightly-coupled embodiment. Data dependencies are detected in accordance with address-coincidence signals generated by slave devices on a cache-line basis. In accordance with a further optimization, at least one slave device (e.g., DRAM) generates page-coincidence bits. When two transactions to the slave device are to the same address page, the transactions are reordered if necessary to ensure that they are executed one after another without any intervening transaction. Latency of the slave is thereby reduced.

REFERENCES:
patent: 4494193 (1985-01-01), Brahm et al.
patent: 5305442 (1994-04-01), Pedersen et al.
patent: 5355455 (1994-10-01), Hilgendorf et al.
patent: 5363485 (1994-11-01), Nguyen et al.
patent: 5418914 (1995-05-01), Heil et al.
patent: 5442763 (1995-08-01), Bartfai et al.
patent: 5469435 (1995-11-01), Krein et al.
patent: 5473762 (1995-12-01), Krein et al.
patent: 5542056 (1996-07-01), Jaffa et al.
patent: 5544332 (1996-08-01), Chen
patent: 5546546 (1996-08-01), Bell et al.
patent: 5592631 (1997-01-01), Kelly et al.
patent: 5592670 (1997-01-01), Pletcher
patent: 5615343 (1997-03-01), Sarangdhar et al.
patent: 5680402 (1997-10-01), Olnowich et al.
patent: 5708794 (1998-01-01), Parks et al.

Affiliated with

Also associated with

Rating

Deadlock avoidance in a computer system having unordered slaves does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deadlock avoidance in a computer system having unordered slaves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadlock avoidance in a computer system having unordered slaves will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-889722