Lookaside buffer for address translation in a computer system

Details Lookaside buffer for address translation in a computer system Lookaside buffer for address translation in a computer system

1997-01-15

1999-04-13

Lane, Jack A.

Electrical computers and digital processing systems: memory

Address formation

Address mapping

711207, G06F 1210

Patent

active

058939318

ABSTRACT:
A method and apparatus for performing address translation in a computer system supporting virtual memory by searching a translation lookaside buffer (TLB) and, possibly, a translation table held in memory and implemented as a B-tree data structure. The TLB is initially searched for a translation for a specified input address. If exactly one valid entry of the TLB stores a translation for the specified input address then the output address corresponding to the specified input address is determined from the contents of that entry. Otherwise, the translation table is searched for a translation for the specified input address. If two or more valid entries of the TLB store a translation for the specified input address then these entries are invalidated. If a search of the translation table is required then the method involves the retrieval from the translation table, and insertion into the TLB, of a translation for the specified input address and possibly one or more translations for other input addresses that are stored together with the translation for the specified input address in one node of the B-tree implementing the translation table. During the insertion into the TLB of a translation for a particular input address that was retrieved from the translation table it is determined if there is exactly one valid entry in the TLB that stores a translation for the particular input address. If so, then the translation retrieved from the memory is inserted into that entry, thereby avoiding the creation of multiple TLB entries for the same input address.

REFERENCES:
patent: 4473878 (1984-09-01), Zolnowsky et al.
patent: 4611272 (1986-09-01), Lomet
patent: 4628451 (1986-12-01), Sawada et al.
patent: 4736287 (1988-04-01), Druke et al.
patent: 4792897 (1988-12-01), Gotou et al.
patent: 4811215 (1989-03-01), Smith
patent: 4827419 (1989-05-01), Selby, III
patent: 4914577 (1990-04-01), Stewart et al.
patent: 4985828 (1991-01-01), Shimizu et al.
patent: 4989134 (1991-01-01), Shaw
patent: 5091846 (1992-02-01), Sachs et al.
patent: 5109335 (1992-04-01), Watanabe
patent: 5148533 (1992-09-01), Joyce et al.
patent: 5155824 (1992-10-01), Edenfield et al.
patent: 5202986 (1993-04-01), Nickel
patent: 5222222 (1993-06-01), Mehring et al.
patent: 5222223 (1993-06-01), Webb, Jr. et al.
patent: 5237671 (1993-08-01), Freitas et al.
patent: 5247666 (1993-09-01), Buckwold
patent: 5255384 (1993-10-01), Sachs et al.
patent: 5263080 (1993-11-01), Jones et al.
patent: 5301287 (1994-04-01), Herrell et al.
patent: 5305444 (1994-04-01), Becker et al.
patent: 5319760 (1994-06-01), Mason et al.
patent: 5369744 (1994-11-01), Fukushima et al.
patent: 5386527 (1995-01-01), Bosshart
patent: 5388215 (1995-02-01), Baker et al.
patent: 5426750 (1995-06-01), Becker et al.
patent: 5479627 (1995-12-01), Khalidi et al.
patent: 5493660 (1996-02-01), DeLano et al.
patent: 5539892 (1996-07-01), Reininger et al.
patent: 5544357 (1996-08-01), Huei
patent: 5581737 (1996-12-01), Dahlen et al.
D. Comer: "The Ubiquitous B-Tree" ACM Computing Surveys, vol. 11, No. 2, Jun. 1979, pp. 121-137, XP002066573.
J.-L. Baer: "Concurrent Accesses of B-Trees in a Paging Environment" Proceedings of the 1978 International Conference on Parallel Processing, 22--Aug. 15, 1978, New York, US, pp. 235-237, XP002066574.
"Software Table Look-Up Buffer for B-Tree Implementation" IBM Technical Disclosure Bulletin, vol. 30, No. 6, Nov. 1987, pp. 145/146 XP000021944.
W. Pugh: "Slow Optimally Balanced Search Strategies vs. Cached Fast Uniformly Balanced Strategies" Information Processing Letters, vol. 34, No. 5, May 1990, NL, pp. 251-254, XP002066575.

Affiliated with

Also associated with

Rating

Lookaside buffer for address translation in a computer system does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Lookaside buffer for address translation in a computer system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lookaside buffer for address translation in a computer system will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-223056