Parallel addressing of a storage hierarchy in a data processing system using virtual addressing

Claim 2

A data processing system including: a central processing unit which provides address signals that represent virtual addresses, a main store coupled to said central processing unit, said main store storing a plurality of blocks of data, a buffer store coupled to said central processing unit and said main store, said buffer store storing a plurality of blocks of data which correspond to a sub-multiple of said blocks of data stored in said main store, an associative storage device coupled to said central processing unit, said associative storage device storing virtual address signals and corresponding real address signals for said main store, first means coupled to said associative storage device for comparing virtual address signals provided by said central processing unit with said virtual address signals stored in said associative storage device for producing a first signal which indicates whether or not a successful comparison is made, second means connected to said first means which responds to said first signal and transfers to said main store real address signals assoCiated with given virtual address signals whenever such virtual address signals compare with said virtual address signals from said central processing unit, and third means coupled to said first means, said central processing unit and said buffer store which responds to virtual address signals from said central processing unit and said first signal to provide a second signal to said buffer store for accessing an address in said buffer store which corresponds to the address specified by said virtual address signals from said central processing unit.

Claim 3

The apparatus of claim 1 which includes fourth means to inhibit operation of said second means when access is made to said buffer store during a fetch operation by said central processing unit.

Claim 4

A data processing system which uses virtual addresses to transfer data selectively between units within said system, said data processing system comprising: a central processing unit which supplies virtual address signals representing data, a main store coupled to said central processing unit, said main store storing a plurality of blocks of data, a buffer store coupled to said central processing unit and said main store, said buffer store storing a plurality of blocks of data corresponding to a portion of said plurality of blocks of data stored in said main store, an associative storage device coupled to said central processing unit, said associative storage device storing virtual address signals and corresponding real address signals for said main store, first means coupled to said associative storage device and said central processing unit for comparing virtual address signals from said central processing unit with the virtual address signal in said associative storage device for producing a first signal which indicates whether or not a successful comparison is made, second means connected to said first means, said associative storage device, and said main store which responds to said first signal and transfers to said main store real address signals associated with given virtual address signals whenever such given virtual address signals compare with virtual address signals from said central processing unit, third means coupled to said first means and said central processing unit which responds to virtual address signals from the central processing unit and said first signal from said second means to produce a second signal, said buffer store including fourth means responsive to said first signal, said second signal, and virtual address signals from said central processing unit for accessing said buffer store at an address corresponding to said virtual address signals from said central processing unit, and fifth means which inhibits operation of said second means whenever access is made to said buffer store during a fetch operation by said central processing unit.

Claim 5

A data processing system which uses virtual addresses to transfer data selectively between units within said system, said data processing system comprising: a central processing unit which supplies virtual address signals representing data, a main store coupled to said central processing unit, said main store storing a plurality of blocks of data, a buffer store coupled to said central processing unit and said main store, said buffer store storing a plurality of blocks of data corresponding to a portion of said plurality of blocks of data stored in said main store, an associative storage device coupled to said central processing unit, said associative storage device storing virtual address signals and corresponding real address signals for said main store, first means coupled to said associative storage device and said central processing unit for comparing virtual address signals from said central processing unit with the virtual address signal in said associative storage device for producing a first signal which indicates whether or not a successful comparison is made, second means connected to said first means, said associative storage device, and said main store which responds to said first signal and transfers to said main store real address signals associated with given virtual address signals whenever such given virtual address signals compare with virtual address signals from said central processing unit, third means coupled to said first means and said central processing unit which responds to virtual address signals from the central processing unit and said first signal from said second means to produce a second signal, said buffer store including fourth means responsive to said first signal, said second signal, and virtual address signals from said central processing unit for accessing said buffer store at an address corresponding to said virtual address signals from said central processing unit, and fifth means which inhibits operation of said second means whenever access is made to said buffer store during a fetch operation by said central processing unit.

Claim 6

A data processing system including a central processing unit, a buffer store, and a main store, said central processing unit being coupled to said buffer store and said main store, a first register, means connecting said central processing unit to said first register, said central processing unit supplying address control words having a virtual address portion and a real address portion to said first register, said first register including a virtual address portion and a real address portion for storing the respective virtual address portions and the real address portion of each address control word, an associative array including a plurality of registers each having a virtual address portion and a real address portion, comparing means responsive to the virtual address portion of said first register and the virtual address portion of each register in said associative array for identifying any register in said associative array having a virtual address equal to the virtual address stored in said first register, transfer means coupled to said associative array for transferring to Said main store the real address portion of any register in said associative array which has its virtual address portion equal to the virtual address of said first register whenever the requested information is not available in said buffer store during a fetch operation, a plurality of sector address registers, a plurality of link registers, said plurality of sector address registers and said plurality of link registers being arranged in pairs whereby a given sector address register is associated with a given link register, first means to insert information in any link register which identifies any one of said registers in said associative array whereby any sector address register may be linked to any register of said associative array, and second means responsive to said comparing means, said sector address register, and said link registers which accesses said buffer store to fetch or store information at a location specified by the address control word in said first register.

Claim 7

A data processing system including a central processing unit, a buffer store, and a main store, said central processing unit being coupled to said buffer store and said main store, a first register, means connecting said central processing unit to said first register, said central processing unit supplying address control words having a virtual address portion and a real address portion to said first register, said first register including a virtual address portion and a real address portion for storing the respective virtual address portions and the real address portion of each address control word, an associative array including a plurality of registers each having a virtual address portion and a real address portion, comparing means responsive to the virtual address portion of said first register and the virtual address portion of each register in said associative array for identifying any register in said associative array having a virtual address equal to the virtual address stored in said first register, transfer means coupled to said associative array for transferring to Said main store the real address portion of any register in said associative array which has its virtual address portion equal to the virtual address of said first register whenever the requested information is not available in said buffer store during a fetch operation, a plurality of sector address registers, a plurality of link registers, said plurality of sector address registers and said plurality of link registers being arranged in pairs whereby a given sector address register is associated with a given link register, first means to insert information in any link register which identifies any one of said registers in said associative array whereby any sector address register may be linked to any register of said associative array, and second means responsive to said comparing means, said sector address register, and said link registers which accesses said buffer store to fetch or store information at a location specified by the address control word in said first register.

Claim 8

The apparatus of claim 4 wherein said first means includes a device for selecting that link register which has been used the least during the recent time period whenever a change is made in the content of any link register.

Claim 9

The apparatus of claim 4 wherein said second means includes third means which inhibits access to the selected address in said buffer store unless such address holds valid information.

Claim 10

A data processing system including a central processing unit, a buffer store, and a main store, said central processing unit being connected to said buffer store and said main store, an address control register, means connecting said central processing unit to said address control register for supplying address control words to said address control register, said address control register including a virtual address portion and a real address portion, an associative array including a plurality of registers each having a virtual address portion and a real address portion, said associative array further including means responsive to the virtual address portion of said address control register and the virtual address portion of each register in said associative array for identifying which register in said associative array has a virtual address equal to the virtual address stored in said address control register, transfer means coupled to said associative array for transferring to said main store the real address portion of any register in said associative array which has its virtual address portion equal to the virtual address of said address control register during all store operations and during fetch operations whenever the requested information is not available in said buffer store, a plurality of sector address register, a plurality of link registers, said plurality of sector address registers and said plurality of link registers being arranged in pairs whereby each sector address register is associated with a given link register, first means connected to said link registers for inserting information in any link register which identifies any one of said registers in said associative array whereby any sector address register may be linked to any register of said associative array, and second means responsive to said identifying means, said sector address register, and said link registers which accesses said buffer store to fetch or store information at a location specified by said address control register.

Claim 11

A data processing system including a central processing unit, a buffer store, and a main store, said central processing unit being connected to said buffer store and said main store, an address control register, means connecting said central processing unit to said address control register for supplying address control words to said address control register, said address control register including a virtual address portion and a real address portion, an associative array including a plurality of registers each having a virtual address portion and a real address portion, said associative array further including means responsive to the virtual address portion of said address control register and the virtual address portion of each register in said associative array for identifying which register in said associative array has a virtual address equal to the virtual address stored in said address control register, transfer means coupled to said associative array for transferring to said main store the real address portion of any register in said associative array which has its virtual address portion equal to the virtual address of said address control register during all store operations and during fetch operations whenever the requested information is not available in said buffer store, a plurality of sector address register, a plurality of link registers, said plurality of sector address registers and said plurality of link registers being arranged in pairs whereby each sector address register is associated with a given link register, first means connected to said link registers for inserting information in any link register which identifies any one of said registers in said associative array whereby any sector address register may be linked to any register of said associative array, and second means responsive to said identifying means, said sector address register, and said link registers which accesses said buffer store to fetch or store information at a location specified by said address control register.

Claim 12

The apparatus of claim 7 wherein said first means includes a device for selecting that link register which has been used the least over the recent time period whenever a change is made in the content of any link register.

Claim 13

The apparatus of claim 7 wherein said second means includes a matrix which inhibits access of the selected address in said buffer store unless it holds valid information.

Claim 14

A data processing system including a central processing unit, a main store, and a buffer store, said daTa processing unit being coupled to said main store and said buffer store whereby information may be exchanged with said main store and said buffer store, the central processing unit utilizing address control words to access said main store and said buffer store, the address control words each having a virtual address portion and a real address portion, an associative array having a plurality of registers with each register having a virtual address portion and a real address portion, first means responsive to the virtual address portion of each address control word and the virtual address portion of each register in said associative array which determines a given register in said associative array which has a virtual address portion identical to the virtual address portion of an address control word from said central processing unit, second means for transferring the real address portion of said given register in said associative array to said main store for the purpose of accessing said main store during store operations and during fetch operations whenever requested information is not available in said buffer store, and third means including a plurality of link registers and a plurality of sector address registers responsive to said first means and the real address portion of an address control word from said central processing unit for accessing a selected location in said buffer store whenever said buffer store holds valid information in such address.

Claim 15

A data processing system including a central processing unit, a main store, and a buffer store, said daTa processing unit being coupled to said main store and said buffer store whereby information may be exchanged with said main store and said buffer store, the central processing unit utilizing address control words to access said main store and said buffer store, the address control words each having a virtual address portion and a real address portion, an associative array having a plurality of registers with each register having a virtual address portion and a real address portion, first means responsive to the virtual address portion of each address control word and the virtual address portion of each register in said associative array which determines a given register in said associative array which has a virtual address portion identical to the virtual address portion of an address control word from said central processing unit, second means for transferring the real address portion of said given register in said associative array to said main store for the purpose of accessing said main store during store operations and during fetch operations whenever requested information is not available in said buffer store, and third means including a plurality of link registers and a plurality of sector address registers responsive to said first means and the real address portion of an address control word from said central processing unit for accessing a selected location in said buffer store whenever said buffer store holds valid information in such address.

Claim 16

The apparatus of claim 10 wherein said first means includes a plurality of compare circuits each having an output, means connecting the virtual address portion of each associative register as one input to the associated compare circuit, and means connecting the virtual address portion of each address control word from said central processing unit as a second input to all of the compare circuits, said plurality of sector address registers and said plurality of link registers being arranged in pairs whereby a given sector address register is associated with a given link register, fourth means coupled to said link registers for inserting information in any link register which identifies any one of the registers in said associative array whereby any sector address register may be linked to any one of the registers in said associative array, and fifth means responsive to the outputs of said compare circuits, said sector address registers, and said link registers which accesses the buffer store to fetch or store information at a location specified by an address control word from said central processing unit.

Claim 17

The apparatus of claim 10 wherein said fifth means includes a matrix which inhibits access of the selected address in said buffer store unless such address holds valid information.

Claim 18

The apparatus of claim 10 wherein said address control word having one portion thereof designated as a sector address and including a plurality of decoders, one for each link register, means connecting each link register to its associated decoder, a plurality of second compare circuits, one for each of said sector address registers, each of said second compare circuits having two inputs and an output, each sector address register being connected as one input to its associated one of said second compare circuits, means connecting said sector address portion of said address control word to the second input of all of said second compare circuits, and means responsive to the outputs of said first compare circuits, the outputs of said second compare circuits, the outputs of said plurality of decoders, and real address portion of said address control word for accessing the location of said buffer store specified by said address control word.

Claim 19

A data processing system including a central processing unit, a main store, and a buffer store, said data processing unit being coupled to said main store and said buffer store, said central processing unit utilizing address control woRds to access said main store and said buffer store, the address control words each having a virtual address portion and a real address portion, an address control register, means connecting said central processing unit to said address control register, said central processing unit supplying address control words to said address control register, an associative array having a plurality of registers with each register having a virtual address portion and a real address portion, a plurality of first compare circuits, one for each register in said associative array, each one of said compare circuits having two inputs and an output, means connecting the virtual address portion of each register in said associative array to one input of its associated compare circuit, means connecting the virtual address portion of said address control register to the second input of all of said compare circuits, said compare circuits serving to determine a given register in said associative array which has a virtual address portion identical to the virtual address portion of said address control register, transfer control means responsive to the output of said compare circuits for transferring the real address portion of said given register in said associative array to said main store for the purpose of accessing said main store whenever an access cannot be made to said buffer store at the address specified by the address control word in said address control register, a plurality of sector address registers, a plurality of link registers, said sector address registers and said link registers being arranged in pairs whereby a given sector address register is permanently associated with a given link register, a plurality of second compare circuits, one for each of said sector address registers, each of said second compare circuits having two inputs and an output, each sector address register being connected as one input to an associated one of said second compare circuits, said address control register having one portion thereof designated as a sector address, means connecting said sector address portion of said address control register as a second input to all of said second compare circuits, a plurality of decoders, one for each link register, means connecting each link register to an associated decoder, each decoder having a plurality of output lines, a plurality of first And circuits, one for each output line of said decoders, means connecting each output line of said decoders to an associated one of said And circuits, means connecting the outputs of said plurality of first compare circuits to selected ones of said plurality of first And circuits, a plurality of Or circuits, one associated with each of said decoders, means connecting said And circuits of each decoder to the Or circuit associated with such decoder, each Or circuit having an output, a plurality of second And circuits, one associated with each of said Or circuits, means connecting the output of each Or circuit to an associated one of said plurality of second And circuits, means connecting the output of each one of said second compare circuits to a different one of said second And circuits, means responsive to the outputs of said plurality of second And circuits and the real address portion of said address control register for accessing the location of said buffer store specified by the control word in said address control register.

Claim 20

A data processing system including a central processing unit, a main store, and a buffer store, said data processing unit being coupled to said main store and said buffer store, said central processing unit utilizing address control woRds to access said main store and said buffer store, the address control words each having a virtual address portion and a real address portion, an address control register, means connecting said central processing unit to said address control register, said central processing unit supplying address control words to said address control register, an associative array having a plurality of registers with each register having a virtual address portion and a real address portion, a plurality of first compare circuits, one for each register in said associative array, each one of said compare circuits having two inputs and an output, means connecting the virtual address portion of each register in said associative array to one input of its associated compare circuit, means connecting the virtual address portion of said address control register to the second input of all of said compare circuits, said compare circuits serving to determine a given register in said associative array which has a virtual address portion identical to the virtual address portion of said address control register, transfer control means responsive to the output of said compare circuits for transferring the real address portion of said given register in said associative array to said main store for the purpose of accessing said main store whenever an access cannot be made to said buffer store at the address specified by the address control word in said address control register, a plurality of sector address registers, a plurality of link registers, said sector address registers and said link registers being arranged in pairs whereby a given sector address register is permanently associated with a given link register, a plurality of second compare circuits, one for each of said sector address registers, each of said second compare circuits having two inputs and an output, each sector address register being connected as one input to an associated one of said second compare circuits, said address control register having one portion thereof designated as a sector address, means connecting said sector address portion of said address control register as a second input to all of said second compare circuits, a plurality of decoders, one for each link register, means connecting each link register to an associated decoder, each decoder having a plurality of output lines, a plurality of first And circuits, one for each output line of said decoders, means connecting each output line of said decoders to an associated one of said And circuits, means connecting the outputs of said plurality of first compare circuits to selected ones of said plurality of first And circuits, a plurality of Or circuits, one associated with each of said decoders, means connecting said And circuits of each decoder to the Or circuit associated with such decoder, each Or circuit having an output, a plurality of second And circuits, one associated with each of said Or circuits, means connecting the output of each Or circuit to an associated one of said plurality of second And circuits, means connecting the output of each one of said second compare circuits to a different one of said second And circuits, means responsive to the outputs of said plurality of second And circuits and the real address portion of said address control register for accessing the location of said buffer store specified by the control word in said address control register.

Claim 21

The apparatus of claim 14 which further includes means for inserting in a selected link register information which identifies said given register in said associative array whenever all of the second And circuits do not operate.

Claim 22

The apparatus of claim 14 which further includes means to inhibit access to the selected address in said buffer store unless such address holds valid information.

Claim 23

The apparatus of claim 14 further including an encoder, the Outputs of said second And circuits being connected to said encoder, means responsive to said encoder and the real address portion of said address control register for accessing the location of said buffer store specified by the control word in said address control register.

Claim 24

The apparatus of claim 14 further including a matrix, the outputs of said second And circuits being connected to said matrix and the block portion of said address control register being connected to said matrix, said matrix providing an output which inhibits operation of said accessing means thereby to prevent access to said buffer store whenever the selected address does not hold valid information.

Claim 25

The apparatus of claim 17 further including: an activity list circuit, means coupling the outputs of said second And circuits to said activity list circuit, a second encoder, the outputs of said first compare circuits being connected to said second encoder, second gating means disposed between said second encoder and each one of said link registers, and third gating means disposed between the sector address portion of said address control register and each one of said sector address registers, said activity list circuit being connected to said second and third gating means to selectively operate said second and third gating means to insert the identity of the given register in said associative array into a selected link register and simultaneously to insert the sector address portion of said address control register in said second address register associated with said selected link register.

Claim 26

Apparatus for controlling the transfer of data in a virtual storage system comprising: a data handling device, a main store coupled to said data handling device, said main store storing a plurality of blocks of data, each block consisting of groups of data with each group being a sub-multiple of said blocks, a buffer store coupled to said data handling device and said main store, said buffer store including addressing means for storing group addresses and data storage means for storing data, the group addresses in said addressing means corresponding to groups of data in said main store, said data handling device providing an address signal having a virtual portion designating the virtual location of a block of data in said main store and a real portion designated a group of data within said block and a data word location within said group, means for storing virtual block address signals and associated real block address signals, means for comparing the virtual block address signal provided by said data handling device with the virtual block address signals stored in said storing means and providing a first signal indicating a successful comparison, means associated with the group addresses in said addressing means for providing second signals indicating the group addresses in said addressing means which correspond to the virtual block addresses in said storing means, means for comparing said first signal with said second signals and providing a third signal indicating a group address that corresponds to the virtual block address of said storing means which compared with the virtual block address provided by said data handling device, means for comparing the real portion of said address signal designating a group of data with the group addresses in said addressing means and providing a fourth signal indicating a successful comparison, means enabled by said third and fourth signals for providing a group address signal designating the location of a group of data in said buffer store, and means responsive to said group address signal and to the real portion of said address signal designating a data word location for accessing said buffer store.

Claim 27

Apparatus for controlling the transfer of data in a virtual storage system comprising: a data handling device, a main store coupled to said data handling device, said main store storing a plurality of blocks of data, each block consisting of groups of data with each group being a sub-multiple of said blocks, a buffer store coupled to said data handling device and said main store, said buffer store including addressing means for storing group addresses and data storage means for storing data, the group addresses in said addressing means corresponding to groups of data in said main store, said data handling device providing an address signal having a virtual portion designating the virtual location of a block of data in said main store and a real portion designated a group of data within said block and a data word location within said group, means for storing virtual block address signals and associated real block address signals, means for comparing the virtual block address signal provided by said data handling device with the virtual block address signals stored in said storing means and providing a first signal indicating a successful comparison, means associated with the group addresses in said addressing means for providing second signals indicating the group addresses in said addressing means which correspond to the virtual block addresses in said storing means, means for comparing said first signal with said second signals and providing a third signal indicating a group address that corresponds to the virtual block address of said storing means which compared with the virtual block address provided by said data handling device, means for comparing the real portion of said address signal designating a group of data with the group addresses in said addressing means and providing a fourth signal indicating a successful comparison, means enabled by said third and fourth signals for providing a group address signal designating the location of a group of data in said buffer store, and means responsive to said group address signal and to the real portion of said address signal designating a data word location for accessing said buffer store.