US 5,329,627 AGranted

Method and apparatus for a translation lookaside buffer with built-in replacement scheme in a computer system

AssigneeSun Microsystems, Inc.

InventorsSunil Nanda, Norman M. Hayes

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and apparatus for selecting an entry to be replaced in a translation lookaside buffer in a computer system. The translation lookaside buffer stores a plurality of entries of virtual-to-physical address translations with each entry having a used bit and a valid bit. The circuit comprises a validity circuit coupled to the valid bit of each entry for determining whether the entry is valid and if not, the validity circuit causes a first signal to be asserted; a use circuit coupled to the used bit of each entry and to the validity circuit for determining whether the entry is used when a control signal is present and if not, the use circuit asserts a second signal to the validity circuit, the asserted second signal causing the first signal to be asserted; a ripple circuit coupled to each entry, its previous entry and its next entry, the ripple circuit receiving the first signal from the validity circuit of each entry and a first FOUND signal from its previous entry, the ripple circuit outputting a second FOUND signal, the ripple circuit causing the second FOUND signal to be asserted when the first signal is asserted and the first FOUND signal is de-asserted, the ripple circuit causing the second FOUND signal to be asserted when the first FOUND signal is asserted, the second FOUND signal being input to the ripple circuit of its next entry, wherein an asserted second FOUND signal for an entry causes the second FOUND signal for its next entry to be asserted, such that an entry with an asserted second FOUND signal propagates the asserted second FOUND signal through its next consecutive entries.

Claims12

Dependent claims

In a computer system using virtual addressing for its memory operations, a circuit for selecting an entry in a translation lookaside buffer to be replaced, wherein said translation lookaside buffer stores a plurality of entries of virtual-to-physical address translations, each of said plurality of entries has a used bit and a valid bit, said used bit for indicating when an entry is accessed for said memory operations, said valid bit for indicating when the virtual-to-physical translation of an entry is not valid, said circuit comprising:

a plurality of validity means, each of said plurality of validity means coupled to the valid bit of each entry for determining whether said entry is valid and if not, said validity means causing a first signal to be asserted;
a plurality of use means, each of said plurality of use means coupled to the used bit of each entry and to said validity means for determining whether said entry is used when a control signal is present and if not, said use means asserting a second signal to said validity means, said asserted second signal causing said first signal to be asserted;
a plurality of ripple means, each of said plurality of ripple means coupled to each entry, to an immediately previous entry and to a next consecutive entry, said ripple means receiving said first signal from the validity means of each entry and a first FOUND signal from said immediately previous entry, said ripple means outputting a second FOUND signal, said ripple means causing said second FOUND signal to be asserted when said first signal is asserted and said first FOUND signal is de-asserted, said ripple means causing said second FOUND signal to be asserted when said first FOUND signal is asserted, said second FOUND signal being input to the ripple means of said next consecutive entry, wherein an asserted second FOUND signal for an entry causes the second FOUND signal for said next consecutive entry to be asserted, such that an entry with an asserted second FOUND signal propagates said asserted second FOUND signal through next consecutive entries.

In a computer system using virtual addressing for its memory operations, a method of selecting an entry in a translation lookaside buffer to be replaced using a circuit, wherein said translation lookaside buffer stores a plurality of entries of virtual-to-physical address translations, each of said plurality of entries has a used bit and a valid bit, said used bit for indicating when an entry is accessed for said memory operations, said valid bit for indicating when the virtual-to-physical translation of an entry is not valid, and wherein said circuit comprises a plurality of validity means, a plurality of use means and a plurality of ripple means wherein each of said plurality of validity means is coupled to said valid bit of each entry, each of said plurality of use means is coupled to said used bit of each entry, and each of said ripple means is coupled to each entry, said method comprising the steps of:

determining whether said entry is valid by said validity means coupled to the valid bit of each entry, and if not, said validity means causing a first signal to be asserted;
determining whether said entry is used when a control signal is present by said use means coupled to the used bit of each entry and to said validity means and if not, said use means asserting a second signal to said validity means, said asserted second signal causing said first signal to be asserted;
receiving said first signal from the validity means of each entry and a first FOUND signal from an immediately previous entry by said ripple means coupled to each entry, to said immediately previous entry and to a next consecutive entry, said ripple means outputting a second FOUND signal, said ripple means causing said second FOUND signal to be asserted when said first signal is asserted and said first FOUND signal is de-asserted, said ripple means causing said second FOUND signal to be asserted when said first FOUND signal is asserted, said second FOUND signal being input to the ripples means of said next consecutive entry, wherein an asserted second FOUND signal for an entry causes the second FOUND signal for said next consecutive entry to be asserted, such that an entry with an asserted second FOUND signal propagates said asserted second FOUND signal through next consecutive entries.

Dependencies are inferred from the claim text.