US 5,548,739 AGranted

Method and apparatus for rapidly retrieving data from a physically addressed data storage structure using address page crossing predictive annotations

AssigneeSun Microsystems, Inc.

InventorRobert Yung

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a computer system having a number of page partitioned and virtually addressed address spaces, a physically addressed data storage structure and its complementary selection data storage structure is provided with a complementary memory page crossing prediction storage structure, a latch, and a comparator. The memory page crossing prediction storage structure is used to store a number of memory page crossing predictive annotations corresponding to the contents of the data and selection data storage structures. Each memory page crossing predictive annotation predicts whether the current access crosses into a new memory page. The latch is used to successively record a first portion of each accessing physical address translated from a corresponding portion of each accessing virtual address. The recorded first portion of the physical address of the immediately preceding access is used to select data currently being read out of the storage structures, if the memory page crossing predictive annotation currently being read out predicts no memory page crossing. The comparator is used to determine whether the first portions of the physical addresses of the current and immediately preceding accesses are equal, if the first portion of the physical address of the immediately preceding access is used to select data for the current access. Remedial actions including invalidating the selected data and correcting the incorrect memory page crossing predictive annotation are taken, if the two physical address portions are determined to be unequal. As a result, most of the data retrievals are made without having to wait for the first portions of the accessing physical addresses to be translated, thereby improving the performance of retrieving data from the physically addressed data storage structure.

Claims18

Dependent claims

In a computer system comprising a data storage structure having a plurality of data vectors, said data storage structure being physically addressed with physical addresses of a physical address space partitioned into a plurality of address pages, and each of said plurality of data vectors having a plurality of data blocks, wherein a currently addressed one of said plurality of data vectors is retrieved during a current access based on a first portion of a current physical address of the current access, a method for rapidly retrieving data from said data storage structure, said method comprising the steps of:

a) storing a plurality of description vectors corresponding to said plurality of data vectors in a description storage structure, the description storage structure being physically addressed with said physical addresses also, each of said plurality of description vectors comprising a plurality of descriptors corresponding to said plurality of data blocks;
b) storing a plurality of predictive annotations corresponding to said plurality of data vectors in a predictive annotation storage structure, the predictive annotation storage structure being physically addressed with said physical addresses also, each of said plurality of predictive annotations predicting whether a next access will cross into a new address page;
c) retrieving a corresponding one of said plurality of descriptors and a corresponding one of said plurality of predictive annotations concurrently with the current retrieval of the currently addressed data vector based on the first portion of the current physical address during the current access;
and
d) selecting a data block from the currently retrieved data vector based on either a second portion of the current physical address of the current access or a second portion of a prior physical address of a prior access, depending on whether a retrieved predictive annotation predicts address page crossing or not, the retrieved predictive annotation being retrieved during either the current or an earlier access, and whether the retrieved predictive annotation of the current access or the retrieved predictive annotation of an earlier access, including which particular earlier access, is to be used for the data block selection is predetermined.

2 more elements

In a computer system comprising a first storage unit for storing a data storage structure having a plurality of data vectors, said data storage structure being physically addressed with physical addresses of a physical address space partitioned into a plurality of address pages, and each of said plurality of data vectors having a plurality of data blocks, wherein said first storage unit outputs a currently addressed one of said data vectors during a current access in response to a first portion of a current physical address of the current access, an apparatus for rapidly retrieving data from said physically addressed data storage structure, said apparatus comprising:

a) a second storage unit for storing a plurality of description vectors corresponding to plurality of in a description storage structure, the description storage structure being physically addressed with said physical addresses also, and each of said plurality of description vectors comprising a plurality of descriptors corresponding to said plurality of data blocks, wherein said second storage unit outputs a corresponding one of said plurality of descriptor vectors concurrently with the outputting of the currently addressed data vector by said first storage unit in response to the first portion of the current physical address;
b) a third storage unit for storing a plurality of predictive annotations corresponding to said plurality of data vectors of a predictive annotation storage structure corresponding to said data storage structure, said predictive annotation storage structure being physically addressed with said physical addresses also, and each of said plurality of predictive annotations predicting whether a next access will cross into a new address page, wherein said third storage unit outputs a corresponding one of said plurality of predictive annotations concurrently with the outputting of the currently addressed data vector output by said first storage unit in response to the first portion of the current physical address;
and
c) selection circuitry coupled to said first, second and third storage units for selecting a data block from the currently retrieved data vector based on either a second portion of the current physical address of the current access or a second portion of a prior physical address of a prior access, depending on whether a retrieved predictive annotation predicts address page crossing or not, the retrieved predictive annotation being retrieved during either the current or an earlier access, and whether the retrieved predictive annotation of the current access or the retrieved predictive annotation of an earlier access, including which particular earlier access, is to be used for the data block selection is predetermined.

1 more element

Dependencies are inferred from the claim text.