Electrical computers and digital data processing systems: input/ – Intrasystem connection
Reexamination Certificate
2000-02-24
2003-08-12
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
C710S055000, C710S105000, C710S107000, C710S113000, C710S054000
Reexamination Certificate
active
06606674
ABSTRACT:
BACKGROUND
This invention relates generally to host controllers.
A host controller provides a hardware and software interface between a bus device and software associated with a processor-based system that controls the device. A host controller interface for Universal Serial Bus (USB) (Universal Serial Bus Specification, Revision 1.0, published in January 1996) devices is disclosed in the Universal Host Controller Interface (UHCI) Rev. 1.1, March 1996, available from Intel Corporation, Santa Clara, Calif.
The host controller moves data between the system memory and devices on the USB by processing data structures in system memory and generating transactions on the USB. The collection of data structures is a schedule of transactions that is set up in system memory by the host controller driver software. For example, the host controller may be a Peripheral Component Interconnect (PCI) (see PCI Local Bus Specification, Rev. 2.1, available from the PCI Special Interest Group, Portland, Oreg. 97214) bus device. The host controller may be a PCI bus master in some implementations.
Using USB as an example, there are four transfer types. The isochronous type is characterized by a constant fixed rate transfer between the USB device and the host. Small spontaneous data transfers from a device are called interrupt transfers. The interrupt transfer type supports devices that require a predictable service interval but do not necessarily produce a predictable flow of data. Isochronous and interrupt transfer types are managed as a periodic bandwidth resource. Control transfers convey device control, status and configuration information. Bulk transfers provide a guaranteed transmission of data between client and host under a lax latency requirement. Control and bulk transfer types are managed as an asynchronous bandwidth resource.
A transfer descriptor is a schedule data structure that contains a pointer to a data buffer and contains control and status fields for the data transmission or reception. Transfer descriptors are used for all transfer types. Bulk, control and interrupt transfer types use additional queuing data structures to allow the transfer descriptors (for these transfer types) to be managed as a queue.
USB is a Time/Data Multiplexed (TDM) bus. A USB frame is a one-millisecond period during which the host controller issues transactions to transfer data. In UHCI, if there is isochronous data to be transferred, a host controller driver schedules these transactions first. The host controller driver manages periodic bandwidth on the USB (e.g. isochronous and interrupt), and ensures that it does not schedule more isochronous and interrupt transactions than can complete in 90% of a USB frame. The remaining time left in the frame (after the periodic transactions have completed) is used to execute asynchronous transactions (e.g. bulk and control).
Control and bulk transfers are scheduled last to take advantage of bandwidth reclamation on a lightly loaded USB. Bandwidth reclamation allows the hardware to continue executing a schedule until time runs out in a frame, cycling through queue entries as frame time allows.
The schedule in main memory is constructed so asynchronous transaction items follow the periodic transaction items. When a control or bulk transfer is in the schedule, the last item in the frame's periodic list points to the beginning of the asynchronous list. The periodic list contains isochronous transfer descriptors and interrupt queues. The asynchronous list contains bulk and control queues. Bandwidth reclamation is implemented by simply pointing the last queue on the asynchronous list to the first queue on the asynchronous list to construct a circular list. As long as time remains on the frame, the full speed control and bulk queues continue to be processed.
A transfer queue includes a queue head and a series of aligned transfer descriptors. Queue heads are data structures that organize transfer descriptors into queues. A queue head and associated transfer descriptor list form a queue context. Interrupt, control and bulk data transfer types can be placed in queues.
Thus, if time permits, the host controller executes transfer descriptors in the bulk and control queue heads. Thus, a plurality of queue heads may be arranged above a plurality of transfer descriptors in a plurality of queues. The host controller executes the top transfer descriptor under each queue head in series. After each bus transaction, the host controller evaluates whether to advance the queue to the next transfer descriptor, before proceeding to the next queue head. At end of the series of queue heads, the host controller circles back and begins processing from the first queue head, repeating transactions for queues that did not advance in the last iteration and executing new transactions for queues that did advance.
If the available transfer descriptors have all been processed or if the bulk and control queue heads are all empty, the host controller thrashes the system bus continually, cycling through the bulk and control queue heads. The host controller spins over the circular list of queue heads looking for work to do and at the same time taking as much as seventy percent of the available PCI bandwidth to basically busy-wait on the circular list.
Thus, there is need for a way to reduce the busy-wait conditions arising from empty queue head lists during reclamation in host controllers.
REFERENCES:
patent: 4263649 (1981-04-01), Lapp, Jr.
patent: 4644472 (1987-02-01), Montgomery
patent: 4664541 (1987-05-01), Stefani
patent: 4682284 (1987-07-01), Schrofer
patent: 4692893 (1987-09-01), Casper
patent: 4816996 (1989-03-01), Hill et al.
patent: 4851987 (1989-07-01), Day
patent: 4958277 (1990-09-01), Hill et al.
patent: 5163016 (1992-11-01), Har'El et al.
patent: 5265229 (1993-11-01), Sareen
patent: 5363485 (1994-11-01), Nguyen et al.
patent: 5386514 (1995-01-01), Lary et al.
patent: 5555266 (1996-09-01), Buchholz et al.
patent: 5692168 (1997-11-01), McMahan
patent: 5805922 (1998-09-01), Sim et al.
patent: 5956742 (1999-09-01), Fandrich et al.
patent: 5983292 (1999-11-01), Nordstrom et al.
patent: 6119190 (2000-09-01), Garney
patent: 6128673 (2000-10-01), Aronson et al.
patent: 6308167 (2001-10-01), Brinkmeyer
Simon Borst, “Polling Systems (Queues)”, 1994, Katholieke Universiteit Brabant, Netherlands, abstract.*
Thomas Cormen, Charles Leiserson, Ronald Rivest, “Introduction To Algorithms”, 1990, Massachusetts Institute of Technology, pp 200-203.
Intel Corporation
King Justin
Ray Gopal C.
Trop Pruner & Hu P.C.
LandOfFree
Method and apparatus for reducing circular list's... 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 reducing circular list's..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing circular list's... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3126154