Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Minimum Delay LRU Bus Arbitrator

IP.com Disclosure Number: IPCOM000044655D
Original Publication Date: 1984-Dec-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 2 page(s) / 37K

Publishing Venue

IBM

Related People

Awsienko, O: AUTHOR [+4]

Abstract

A technique is described whereby input and output (I/O) devices, such as controllers, channels and busses, are shared in computer systems utilizing bus arbitration. The concept is based on an algorithm of least recently used (LRU) arbitration. Discussed is an LRU-based solution which allows arbitration between two requesting devices in a one-half clock cycle. When the LRU bus arbitrator, as shown in Fig. 1, receives request signals, +R1 and +R2, from two different I/O devices, the arbitrator sends signals, +G1 and +G2, to each of the devices to indicate the appropriate granting of the bus. The reset, clock and scan inputs are provided for the necessary level sensitive scan design (LSSD) controls. The arbitration algorithm used with the LRU concept is defined as follows: 1.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Minimum Delay LRU Bus Arbitrator

A technique is described whereby input and output (I/O) devices, such as controllers, channels and busses, are shared in computer systems utilizing bus arbitration. The concept is based on an algorithm of least recently used (LRU) arbitration. Discussed is an LRU-based solution which allows arbitration between two requesting devices in a one-half clock cycle. When the LRU bus arbitrator, as shown in Fig. 1, receives request signals, +R1 and +R2, from two different I/O devices, the arbitrator sends signals, +G1 and +G2, to each of the devices to indicate the appropriate granting of the bus. The reset, clock and scan inputs are provided for the necessary level sensitive scan design (LSSD) controls. The arbitration algorithm used with the LRU concept is defined as follows: 1. Should a bus be in use when a request from another device is made for use, the arbitrator will force the other device to wait until the bus is free. 2. If the bus is not in use, grant the bus to the first requester on a first-come, first-serve basis. 3. If the requests for bus use are concurrent, and the bus is not granted, the arbitrator will grant the bus to the least recent user. The LRU circuit, as shown in Fig. 2, uses four shift register latches, master latches 10a and 10b, and slave latches 11a and 11b. Master latches 10a and 10b are used to store the grant state of the bus and slave latches 11a and 11b are used to store the previous grant state. Reset signals first initialize master latches 10a and 10b to a binary zero while the slave latches 11a and 11b are initializ...