Hybrid semiconductor memory with on-chip associative page addressing, page replacement and control

• US 4,084,230 A
• Filed: 11/29/1976
• Issued: 04/11/1978
• Est. Priority Date: 11/29/1976
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Matick, Richard Edward
• Primary Examiner(s): Chapnick, Melvin B.
• Application Number:
  US05/746,033
• Time in Patent Office: 498 Days
• Field of Search: 340/173 R, 340/173 AM, 364/200, 364/900
• US Class Current: 711/5
• CPC Class Codes: G06F 12/0661 and decentralised selection
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1063 the data cache being concurrently virtually addressed
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel

Abstract

An associative system for providing virtual paged stores with on-chip associative address translation and control functions. Each of a plurality of integrated circuit chips contains the storage cells for a unit of data and at least one associative circuit including a virtual page address register for storing the virtual address bits assigned to each page. The CPU includes a virtual page address register and a real address register, with the CPU virtual page address register being connected to the virtual address register on each chip for interrogating the chips when a page request is made. The real address register holds the real address bits for selecting a byte of data from the chips. An interrogate virtual page address is applied to each of the chips for comparison with the address stored in the virtual page address registers, whereby a match will directly enable the selected chip to be read and/or written into. In addition to the virtual page address translation performed directly on the chip, there may also be provided on each chip a page usage information register, a page update register, as well as other control registers for storing page data which is used to determine eligibility of a page for replacement when a page fault is detected.

Claims

1. An associative page addressing system for providing virtual paged stores, comprising:

a plurality of integrated circuit chips, each said chip containing the storage cells for data, at least one associative circuit including a virtual page address register for receiving and storing the virtual address bits assigned to each page located on one or more chips, and means for comparing a stored virtual address with an interrogate virtual address from a CPU and providing a direct page enable output upon a match thereof;

address decoder means connected to receive said page enable output and locate data addressed in said storage cells; and

Cpu means including a virtual page address register and a real address register, said virtual page address register of said CPU means being connected to said virtual address register on each chip for interrogating said chips when a page request is made, said real address register storing the real address bits which are applied to said address decoder means for selecting a byte of data from said storage cells in the chips;

whereby a matched virtual page address produces an enable output from said comparing means and directly enables the selected chip to be accessed at those locations addressed by said real address register.

2. A system as recited in claim 1, further comprising, on each of said chips, at least on page usage information register for storing data relating to the usage of a given page for determining eligibility of a page for replacement.

3. A system as recited in claim 2, wherein each said page information register includes means for storing page usage control bits and means for comparing the stored page usage control bits with interrogate control bits and providing a flag output upon a match thereof for selecting a page for replacement.

4. A system as recited in claim 2, further comprising page fault gating means connected to the outputs of each of said virtual address comparing means, for detecting that none of said chips have been enabled by a match of its virtual address interrogated by the CPU means, thereby providing a page fault indication.

5. A system as recited in claim 4, further comprising a page replacement scanner, responsive to said page fault gating means, for interrogating said page usage information registers on each chip.

6. A system as recited in claim 2, wherein one of said page usage information registers includes a reference bit register for indicating whether a page has been used over a given time period, and means for updating said reference bit register when its respective page has been used.

7. A system as recited in claim 2, wherein the page usage information registers include a modified bit register for indicating whether a page has been written into, and means for updating said modified bit register.

8. A system as recited in claim 2, further comprising multiple match selection means for selecting a page determined to be eligible for replacement, said multiple match selection means including gating means for preventing more than one of said pages from being replaced at a time.

9. A system as recited in claim 8, further comprising register reset means connected for receiving the output of said multiple match selection means and initiating accessing of the page and the resetting of control information registers located on each chip for storing data relating to the usage of a given page.

10. A system as recited in claim 9, wherein said multiple match selection means provides a page enabled signal which is used to initiate a page swapping cycle for the enabled chip or page.

11. A system as recited in claim 2, further comprising means for interrogating the page usage information registers on each chip, and bit update means, responsive to said interrogating means, for setting the information contained in such registers in accordance with whether its respective page was enabled or selected in a last scan cycle.

12. A system as recited in claim 11, further comprising a programmable control means associated with said interrogation means and said bit update means for setting the conditions under which the pages are replaced.

13. A system as recited in claim 2, further comprising means for detecting the control information stored in said page usage information registers on each chip, page select means responsive to said detecting means, for selecting one page for replacement, and means for writing a virtual address into any virtual page address register upon replacement of a respective page.

14. A system as recited in claim 1, further comprising gating means connected between said enable output of said comparing means and said address decoder means for enabling said chip storage cells to be accessed, each of said gating means being serially connected to each other and each chip enable output such that the first chip to be enabled in the serial line will thereby prevent any subsequent chips from being enabled at that time for access, whereby said gating means provides for the selection of one chip of a multiple chip match condition.

15. A system as recited in claim 1, further comprising on each chip a control register means for storing page usage data concerning the usage of a given page and its eligibility for replacement, the output of said control register means being connected to a page fault and multiple match detector which indicates whether a page has been enabled.

16. A system as recited in claim 15, further comprising a page scanner connected to the output of said page fault and multiple match detector, said page scanner connected to each chip for interrogating said control register means thereon for updating said control register means and replacing pages.

17. A system as recited in claim 15, wherein said direct enable output from said virtual address comparing means is applied on a common flag line with the output from said page usage control register means, said flag line being connected to the input to a page fault and multiple match detector for indicating whether a page has been enabled and for selecting one of a multiple page match.

18. A system as recited in claim 1 wherein each chip contains one page.

19. A system as recited in claim 1, wherein said address decoder means includes a bit decoder and a real word decoder for receiving the word and bit comprising the real address in said real address register.

20. A system as recited in claim 1, wherein said virtual page address register of said CPU means is connected to the virtual address register on each chip, and interrogate means are provided for interrogating each virtual address register at the same time that said address decoder means locates data in said storage cells, whereby decoding of the virtual page address registers is overlapped with the decoding of bit group and word line selection of the storage cells.

21. A system as recited in claim 1, wherein said virtual page address register on each chip comprises a basic four FET device flip-flop and said comparing means comprises FET transistors for comparing the virtual address stored in said virtual address register with the bits comprising the virtual address received on bit lines for interrogation.

22. A system as recited in claim 21, further comprising, at the output of said comparing means, an enable gate for enabling the output of said comparing means to be provided on an output enable line only when an interrogate signal is provided at said enable gate.

23. A two level, hierarchical storage device for providing a fully associative virtual page address translation function, comprising:

a plurality of integrated circuit chips, each of which includes an associative virtual page address register physically located on chip including both means for receiving and storing the virtual address bits assigned to a page located on one or more chips, and means for comparing a stored virtual address with an interrogate virtual address from a CPU and providing a direct chip or page enable output upon a match thereof for directly enabling a chip memory to be accessed at those locations addressed by the CPU, whereby fully associative compare operations are carried out with all virtual addresses directly on chip.

24. A device as recited in claim 23, further comprising, on each chip, address decoder means for locating data stored in the chip memory and addressed by the CPU, said address decoder means being connected to be enabled by said page enable output.

25. A device as recited in claim 23, further comprising, on each of said circuit chips, one or more control registers of storing page usage and update information for providing information to a CPU control means for selecting a page for replacement when a page fault occurs.

26. A device as recited in claim 25, wherein the output of said means for comparing said stored virtual addresses is connected to the output of said control registers to provide a common associative flag line.

27. A device as recited in claim 25, wherein said control registers include a reference bit register for indicating whether a page has been used over some period of time.

28. A device as recited in claim 25, wherein said control registers include a modified bit register containing a bit for indicating whether a page has been modified or written into.

29. A device as recited in claim 25, wherein said control registers include an unreferenced interval count register containing a bit for specifying the number of scan intervals over which its respective page was not referenced.

30. A device as recited in claim 25, wherein each of said control registers for storing page usage and update information includes means for comparing control data stored in said control registers with interrogate control data from the CPU and producing a flag match output.

31. A device as recited in claim 30, further comprising gating means connecting said control registers including the outputs of their comparing means in a series arrangement, said gating means selecting the first page in the series sequence which produces a flag match output.

32. A device as recited in claim 23, further comprising gating means connected to said page enable output for detecting a page fault condition whereby none of the pages produces a match of their stored virtual addresses with the interrogated virtual address.

33. A two level, hierarchical storage device for providing a fully associative virtual page address translation function, comprising:

a plurality of integrated circuit chips, each of which includes an associative virtual page address register physically located on chip and having both means for receiving and storing the virtual address bits assigned to a page, and means for comparing a stored virtual address with an interrogate virtual address from a CPU and providing a chip or page enable directly on chip, a data storage array on each chip, and address decoder means for locating data addressed in the data storage arrays from the CPU, said chip enable serving to directly enable the data storage array to be accessed at those locations in said address decoder means;

whereby a fully associative virtual page address translation function is provided directly on chip.

34. A device as recited in claim 33, further comprising on each of said circuit chips one or more control registers for storing page usage and update information, and a CPU storage control for selecting a page for replacement when a page fault occurs.

35. A device as recited in claim 34, wherein each of said control registers is an associative register having a means for comparing control data stored in said control registers with interrogate control data from the CPU storage control and producing a flag match output.

36. A device as recited in claim 35, wherein the output of said means for comparing said virtual addresses is connected to the output of said means for comparing said control data to provide a common associative flag line.