Cache arrangement for performing simultaneous read/write operations

• US 4,208,716 A
• Filed: 12/11/1978
• Issued: 06/17/1980
• Est. Priority Date: 12/11/1978
• Status: Expired due to Term

• Current Assignee: Honeywell Information Systems, Inc. (Honeywell International Inc.)
• Original Assignee: Honeywell Information Systems, Inc. (Honeywell International Inc.)
• Inventors: Shelly, William A., Norman, Robert W. Jr., Porter, Marion G.
• Primary Examiner(s): Springborn, Harvey E.
• Application Number:
  US05/968,521
• Time in Patent Office: 554 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible
• CPC Class Codes: G06F 12/0855 Overlapped cache accessing, e.g. pipeline G06F12/0846 takes precedence
• CPC Class Codes: G06F 12/0859 with reload from main memory

Abstract

A cache system includes a storage unit organized into a plurality of levels, each including a number of multiword blocks and a corresponding number of address selection switches and address registers. Each address selection switch has a plurality of different positions connected to receive address signals from a plurality of address sources. A decoder circuit generates output signals for controlling the operation of the address selection switches. In response to previously defined level signals, the decoder circuit conditions a specified one of the number of switches to switch from a first position to a second position. An address specifying the location into which memory data is to be written is clocked into one address register while the address specifying the location from which an instruction is to be fetched is clocked into the remaining address registers. A comparator circuit compares signals indicating the level into which memory data is to be written with signals indicating the level from which a next instruction is to be fetched. The comparator circuit generates signals which cause the delay of instruction access when there is a conflict between writing memory data and accessing instructions.

Claims

1. A cache unit for use with a data processing unit for providing fast access to information fetched from a main store coupled to said cache unit in response to commands received from said data processing unit, said cache unit comprising:

a buffer store comprising a plurality of word locations energized into a plurality of levels for storing said information;

a plurality of address switch selection means corresponding in number to said plurality of levels, each said address switch selection means having a number of inputs connected to receive a corresponding number of addresses from a corresponding number of identical address sources and an output;

a plurality of address register means corresponding in number to said plurality of levels, each said address register means being coupled to a different one of said plurality of address switch selection means and to a different one of said plurality of said levels, each said address register means for storing the address specifying the word location to be accessed during a cache cycle of operation; and

,

control circuit means coupled to each of said address switch selection means and to one of said address sources for receiving a set of level signals, said control circuit means for generating a plurality of sets of control signals identifying which one of said plurality of said address sources is connected to supply said address to be loaded into each of said address register means, said control circuit means being operative in response to said set of level signals to cause one of said plurality of sets of control signals to condition the address switch selection means designated by said set of level signals to select for loading into said address register means associated therewith an address from said one of said address sources and also to condition the remaining ones of said plurality of address switch selection means to select for loading into the remaining address register means an address from another one of said address sources enabling information to be written into said one level simultaneously with the accessing of information from the remaining levels during said cache cycle of operation.

2. The cache unit of claim 1 wherein said cache unit further includes:

comparator circuit means for detecting the presence of a conflict condition, said comparator circuit means having a pair of sets of inputs, one set of said pair being coupled to receive said set of level signals and the other set of said pair being coupled to receive another set of level signals from said another one of said address sources, said comparator circuit means being operative to generate an output signal indicative of said conflict condition when the operation of writing said information and the operation of accessing information both involve the same level and said comparator means being coupled to a predetermined one of said address sources for enabling the delay of a predetermined one of said operations until said conflict condition is detected as being no longer present.

3. The cache unit of claim 2 wherein said information includes data and instructions and wherein said another one of said address sources includes:

instruction address register means operatively coupled to said data processing unit, to said comparator circuit means and to one of said inputs of each of said address switch selection means, said instruction address register means including a number of bit positions, a first group of said bit positions for storing an address specifying a next location within said buffer store from which an instruction word is to be accessed and a second group of said bit positions for storing said another set of level signals designating the level from which said instruction word is to be accessed.

4. The cache unit of claim 3 wherein said predetermined operation corresponds to accessing instructions and said predetermined one of said address sources corresponds to said another one of said address sources, said cache unit further including:

instruction ready control circuit means for generating an output signal to said data processing unit for signalling when said next instruction word can be accessed from said buffer store; and

,

inhibit control means coupled to said instruction ready means and to said comparator means, said inhibit control means being conditioned by said comparator means to inhibit said instruction ready means from generating said output signal during said conflict condition delaying said access of said instruction word.

5. The cache unit of claim 4 wherein said control circuit means includes:

decoder circuit means having a plurality of input terminals connected to receive said set of level signals, an enabling input terminal connected to receive a memory write request signal and first and second sets of output terminals;

a first multiplexer circuit having a plurality of input terminals connected to said first set of output terminals and a plurality of output terminals, each connected to a different one of said plurality of address switch selection means; and

,

a second multiplexer circuit having a plurality of input terminals connected to said second set of output terminals, an enabling input terminal connected to receive an address enable signal and a plurality of output terminals, each connected to said different one of said plurality of address switch selection means;

said decoder circuit means in response to said memory write request signal being operative to switch one of said first output terminals designated by said set of level signals from a first state to a second state and a corresponding one of said second output terminals from said second state to said first state when said second multiplexer circuit is enabled for operation by said address enable signal, said first and second multiplexer circuits conditioning only said designated address switch selection means to select said one address source address.

6. The cache unit of claim 5 wherein each of said plurality of said address switch selection means includes a pair of control input terminals coupled to a corresponding one of said output terminals of each of said first and second multiplexer circuits and wherein said first state and said second state correspond to a binary ZERO and a binary ONE, respectively, and each of said number of inputs of each address switch selection means including a set of input terminals, one of said set of input terminals corresponding to a first position being connected to said another address source and another one of said set of input terminals corresponding to a second position being connected to said one address source.

7. The cache unit of claim 6 wherein said one address source includes:

a buffer operatively coupled to said data processing unit, said buffer for storing at least one command which has a command code specifying a read type operation, signals corresponding to an address specifying the location within said buffer store into which memory data requested by said one command is to be written and said set of level signals for specifying which one of said levels into which said memory data is to be written; and

,

means coupling said buffer to said another set of input terminals of each address switch selection means and to said decoder circuit means, said means being operative to apply said address and said set of level signals to said plurality of address switch selection means and to said decoder circuit means respectively in response to said memory write request signal enabling the writing of said memory data into a designated one of said plurality of levels of said buffer store.

8. The cache unit of claim 4 wherein said instruction address register means further includes increment circuit means for incrementing by one, the address stored in said first group of bit positions to specify the location of the next instruction word to be accessed during a next cache cycle and said increment circuit means being coupled to said comparator circuit means, said increment circuit being conditioned by said output signal to inhibit the incrementing of said address until said conflict condition is no longer present.

9. The cache unit of claim 8 wherein said cache unit further includes:

output multiposition switch means including a number of sets of input terminals corresponding to the number of levels, a plurality of output terminals and a set of control input terminals; and

,

a number of conductor means, each coupling a different one of said number of sets of input terminals to a different one of said levels of said buffer store and means coupling said control input terminals to said instruction address register means to receive said set of level signals, said multiposition switch means being conditioned by said set of level signals to apply to said output terminals, an instruction word accessed from the level designated by said set of level signals.

10. The cache unit of claim 9 wherein said cache unit further includes an output register coupled to said data processing unit, to said plurality of output terminals of said output multiposition switch means and to said comparator circuit means, said output signal inhibiting the loading of said output register with said instruction word until said conflict condition is no longer present.

11. The cache unit of claim 1 wherein said plurality of levels corresponds to a predetermined number of levels, said predetermined number being selected to minimize potential conflicts among the addressing sources in writing and reading information within the same level.

12. The cache unit of claim 11 wherein said predetermined number equals 8.

13. The cache unit of claim 1 wherein said cache unit further includes:

timing circuit means for generating timing signals for defining first and second halves of said cache cycle, said timing means being coupled to said control circuit means for conditioning said plurality of address switch selection means for loading said plurality of address register means with addresses from said one and said another address sources during said second half of a previous cache cycle for enabling the writing of information into said one level simultaneously with the accessing of information from the remaining levels during said first half of said cache cycle.

14. The cache unit of claim 13 wherein said cache unit further includes:

comparator circuit means for detecting the presence of a conflict condition, said comparator circuit means having a pair of sets of inputs, one set of inputs being coupled to receive said set of level signals from said one of said address sources and the other set of inputs being coupled to receive another set of level signals from said another one of said address sources, said comparator circuit means being operative to generate an output signal indicative of said conflict condition when the operation of writing said information and the operation of accessing information both involve the same level and said comparator means being coupled to a predetermined one of said address sources for enabling the delay of a predetermined one of said operations until said conflict condition is detected as being no longer present.

15. The cache unit of claim 14 wherein said information includes data and instruction words and wherein said one address source includes:

a buffer operatively coupled to said data processing unit, said buffer for storing at least one command which has a command code specifying a read type operation, signals corresponding to an address specifying the location within said buffer store into which memory data requested by said one command is to be written and said set of level signals for specifying which one of said levels into which said memory data is to be written during said first half of said cache cycle; and

,

means coupling said buffer to said another set of input terminals of each address switch selection means and to said decoder circuit means, said means being operative to apply said address and said set of level signals to said plurality of address switch selection means and to said decoder circuit means respectively in response to said memory write request signal enabling the writing of said memory data into a designated one of said plurality of levels of said buffer store.

16. The cache unit of claim 15 wherein said another address source includes:

instruction address register means operatively coupled to said data processing unit, to said comparator circuit means and to one of said inputs of each of said address switch selection means, said instruction address register means including a number of bit positions, a first group of said bit positions for storing an address specifying a next location within said buffer store from which an instruction word is to be accessed and a second group of said bit positions for storing said another set of level signals designating the level from which said instruction word is to be accessed during said first half of said cache cycle.

17. The cache unit of claim 16 wherein during the detection of said conflict condition, said memory data is written into said designated level during the first half of said cache cycle and the following cache cycles.

18. The cache unit of claim 17 wherein when said conflict condition is detected as being no longer present, said instruction address register means is conditioned to load an address into all of said address register means during said second half of a cache cycle to fetch said next instruction during said first half of a next cache cycle of operation.

19. The cache unit of claim 16 wherein each of said commands includes a command code and an address and said another address source includes:

an input circuit means coupled to receive said address of each said command from said processing unit and said input circuit means being connected to said second one of said sets of input terminals of each of said address switch selection means, said input circuit means being operative to apply to said second one of said sets of input terminals, said address of a command generated by said processing unit specifying a location within said buffer store from which an operand word is to be fetched or into which an operand word is to be written during said second half of said cache cycle.

20. The cache unit of claim 19 wherein each level of said buffer store contains a number of blocks of said word locations, each level and each block being defined by a level address and a block address respectively and said cache unit further including:

a directory having a plurality of locations corresponding in number to the number of levels in said buffer store and being addressable by said level addresses, each location of said directory storing block addresses of blocks of words within the associated level stored in said buffer store, said directory responsive to said level address corresponding to a low order portion of said command address to read out said block addresses corresponding to a high order portion of said command address;

comparison means coupled to said directory for comparing said block addresses read out from said directory with the high order portion of said command address and generating hit detection signals indicative of whether or not the operand being requested is stored in said buffer store;

directory level control means coupled to said split cycle timing means to said comparison means, to said buffer store and to said comparator circuit means, said directory level control means in response to said hit detection signals being operative to generate said another set of level signals during said second interval of a next cache cycle; and

,

hold control circuit means coupled to said comparator circuit means and to said data processing unit, said hold control means being conditioned by said signal from said comparator circuit means generated when the level into which memory data is being written is the same as the level from which the requested operand word is being accessed, to inhibit further operations of said data processing unit, simulating a miss condition until said conflict condition is no longer present.

21. The cache unit of claim 20 wherein during the detection of said conflict condition, said memory data is written into said designated level during the second half of said cache cycle and following cache cycles until all of said memory data requested is written into said buffer store.

22. The cache unit of claim 20 wherein when said conflict condition is detected as being no longer present, said input circuit means is conditioned to load said low order portion of said command address into all of said address register means during said first half of a cache cycle to enable the fetching of said operand word or the writing of said operand word specified by said command, at the level designated by said another set of level signals generated in accordance with the results of a directory search operation performed during the cache cycle in which said conflict condition was detected.

35. The cache system of claim 21 wherein said one address source includes:

a buffer operatively coupled to said data processing unit, said buffer for storing at least one command which has a command code specifying a read type operation, signals corresponding to an address specifying the location within said buffer store into which memory data requested by said one command is to be written and said set of level signals for specifying into which one of said levels said memory data is to be written; and

,

means coupling said buffer to the same one of said sets of input terminals of each address switch and to said control circuit means, said means for applying said address and said set of level signals to said plurality of address switch selection means and to said control circuit means in response to a memory write request signal to enable said memory data to be written into a designated one of said plurality of levels of said buffer store during one of said halves of said cache cycle notwithstanding the detection of said conflict condition.

23. A cache unit for use with a data processing unit for providing fast access to data and instructions fetched from a main store coupled to said cache unit in response to commands received from said data processing unit, said cache unit comprising:

25. The cache unit of claim 23 including means wherein said simultaneous writing and reading is enabled during said first half.

26. The cache unit of claim 23 including means wherein said simultaneous writing and reading is enabled during said second half.

27. The cache unit of claim 23 wherein said cache unit further includes:

comparator circuit means for detecting the presence of a conflict condition, said comparator circuit means having a pair of sets of inputs, one set of inputs being coupled to receive said level signals from said one of said address sources and the other set of inputs being coupled to receive another set of level signals associated with the operation being performed by said another address source, said comparator circuit means being operative to generate an output signal indicative of said conflict condition when the operation of writing said memory data and the operation of accessing instructions/operand data involve the same level and said comparator means being coupled to a predetermined one of said address sources for enabling the delay of a predetermined one of said operations until said conflict condition is detected as being no longer present.

28. The cache unit of claim 26 wherein said one address source includes:

a buffer operatively coupled to said data processing unit, said buffer for storing at least one command which has a command code specifying a read type operation, signals corresponding to an address specifying the location within said buffer store into which memory data requested by said one command is to be written and said set of level signals for specifying which one of said levels said memory data is to be written; and

,

means coupling said buffer to the same one of said sets of input terminals of each address switch selection means and to said control circuit means, said means for applying said address and said set of level signals to said plurality of address switch selection means and to said control circuit means in response to a memory write request signal to enable said memory data to be written into a designated one of said plurality of levels of said buffer store during one of said halves of said cache cycle notwithstanding the presence of said conflict condition.

29. The cache unit of claim 23 wherein said plurality of levels corresponds to a predetermined number of levels selected to minimize potential conflicts among the addressing sources in writing and reading information within the same level.

30. The cache unit of claim 28 wherein said another one of said address sources includes:

32. The cache unit of claim 28 wherein each of said commands includes a command code and an address and said another one of said address sources includes:

an input circuit means coupled to receive said address of each said command from said processing unit, said input circuit means being connected to the same another one of said sets of input terminals of each of said address switch selection means and to said comparator circuit means, said input circuit means being operative to apply said address of a command generated by said processing unit specifying a location within said buffer store from which an operand word is to be fetched or into which an operand word is to be written during said second half of said cache cycle in the absence of said conflict condition.

39. The cache system of claim 32 wherein said another one of said address sources includes:

instruction address register means operatively coupled to said data processing unit, to said comparator circuit means and to the same one of said sets of input terminals of each of said address switches, said address register means including a number of bit positions, a first group of said bit positions for storing an address specifying a next location within said cache store from which an instruction word is to be accessed and a second group of said bit positions for storing said another set of level signals designating the level from which said instruction word is to be accessed during said first half of said cache cycle in the absence of said conflict condition.

40. The cache system of claim 32 wherein each of said commands includes a command code and an address and said another one of said address sources includes:

an input circuit means coupled to receive said address of each said command from said processing unit and said input circuit means being connected to the same another one of said sets of input terminals of each of said address switches and to said comparator circuit means, said input circuit means being operative to apply said address of a command generated by said processing unit specifying a location within said buffer store from which an operand word is to be fetched or into which an operand word is to be written during said second half of said cache cycle in the absence of said conflict condition.

42. The cache system of claim 32 wherein said control circuit means includes:

decoder circuit means having a plurality of input terminals connected to receive said set of level signals, an enabling input terminal connected to receive said memory write request signal and first and second sets of output terminals;

a first multiplexer circuit having a plurality of input terminals connected to said first set of output terminals and a plurality of output terminals, each connected to a different one of said address switches; and

,

a second multiplexer circuit having a plurality of input terminals connected to said second set of output terminals, an enabling input terminal connected to receive an address enable signal and a plurality of output terminals, each connected to said different one of said plurality of address switches;

said decoder circuit means in response to said memory write request signal being operative to switch one of said first output terminals designated by said set of level signals from a first state to a second state and a corresponding one of said second output terminals from said second state to said first state when said second multiplexer circuit is enabled for operation by said address enable signal, said first and second multiplexer circuits causing only said one of said plurality of sets of control signals to condition only said designated address switch to select an address from said one of said address source addresses to be loaded into said address register during said second half of said cache cycle.

24. a buffer store comprising a plurality of word locations organized into a plurality of levels for storing said data and instructions;

a plurality of multiposition address switch selection means corresponding in number to said plurality of levels, each said address switch selection means having a number of sets of input terminals connected to receive a corresponding number of addresses from a corresponding number of identical address sources, a plurality of output terminals and a plurality of control input terminals;

a plurality of address register means corresponding in number to said plurality of levels, each said address register means being coupled to a different one of said address switch selection means plurality of output terminals and to a different one of said plurality of said levels, each said address register means for storing the address specifying the word location to be accessed during a cache cycle;

split cycle timing means for generating timing signals for defining first and second halves of said cache cycle;

control circuit means coupled to said timing means and to each plurality of control terminals of each said address switch selection means and to one of said plurality of said address sources for receiving a set of level signals, said control circuit means for generating a plurality of sets of control signals for application to said address switch selection means control terminals coded for identifying which address source is connected to supply said address to be loaded into each of said address register means during said first and second halves of said cache cycle, said control circuit means being operative in response to said set of level signals to cause one of said plurality of sets of control signals to condition one of said plurality of address switch selection means designated by said set of level signals to select for loading into said address register means associated therewith an address from said one address source also to condition and the remaining ones of said plurality of address switch selection means to select for loading into the remaining address register means an address from another one of said address sources enabling memory data to be written into said one level simultaneously with the accessing of instructions/operand data from the remaining levels during one of said halves of said cache cycle.

31. instruction address register means operatively coupled to said data processing unit, to said comparator circuit means and to the same another one of said sets of input terminals of each of said address switch selection means, said address register means including a number of bit positions, a first group of said bit positions for storing an address specifying a next location within said buffer store from which an instruction word is to be accessed and a second group of said bit positions for storing said another set of level signals designating the level from which said instruction word is to be accessed during said first half of said cache cycle in the absence of said conflict condition.

36. The cache system of claim 31 wherein said plurality of levels corresponds to a predetermined number of levels selected to minimize potential conflicts among the addressing sources in writing and reading said data/instructions within the same level.

37. The cache system of claim 31 or 32 including means wherein said simultaneous writing and reading is enabled during said first half.

38. The cache system of claim 31 or 32 including means wherein said simultaneous writing and reading is enabled during said second half.

41. The cache system of claim 37 wherein said command code is coded to specify a read type operation and wherein each level of said cache store contains a number of blocks of said word locations, each level and each block being defined by a set address and a block address respectively and said cache system further including:

a directory coupled to said input circuit means, said directory having a plurality of locations corresponding in number to the number of levels in said buffer store and being addressable by said set addresses, each location of said directory storing block addresses of blocks of words within the associated level stored in said buffer store, said directory responsive to said set address corresponding to a low order portion of said command address applied by said input circuit means to read out said block addresses corresponding to a high order portion of said command address;

comparison means coupled to said directory for comparing said block addresses read out from said directory with the high order portion of said command address and generating hit detection signals indicative of whether or not the operand being requested is stored in said cache store;

directory level control means coupled to said split cycle timing means to said comparison means, to said cache store and to said comparator circuit means, said directory level control means in response to said hit detection signals being operative to generate said another set of level signals during said second half of a next cache cycle; and

,

hold control circuit means coupled to said comparator circuit means and to said data processing unit, said hold control means being conditioned by said output signal from said comparator circuit means when the level into which memory data is being written is the same as level from which the requested operand word is being accessed to inhibit further operations of said data processing unit.

33. A cache system for use with a data processing unit for providing fast access to instructions and data fetched from a main store coupled to said cache unit in response to commands received from said data processing unit, said cache unit comprising:

a cache store comprising a plurality of word locations organized into a plurality of levels for storing said data and instructions;

a plurality of multiposition address switches corresponding in number to said plurality of levels, each said address switch having a number of sets of input terminals connected to receive a corresponding number of addresses from a corresponding number of identical address sources, a plurality of output terminals and a plurality of control input terminals;

a plurality of address registers corresponding in number to said plurality of levels, each said address register being coupled to a different one of said plurality of output terminals of said plurality of address switches and to a different one of said plurality of said levels, each said address register for storing the address specifying the word location to be accessed during a cache cycle of operation;

split cycle timing means for generating timing signals for defining first and second halves of each cache cycle;

comparator circuit means for detecting the presence of a conflict condition between a pair of said address sources, said comparator circuit means having a pair of sets of inputs, one set of inputs being coupled to receive said level signals from said one of said address sources and the other set of inputs being coupled to receive another set of level signals associated with the operation being performed by said another address source, said comparator circuit means being operative to generate an output signal indicative of said conflict condition when the operation of writing memory data received from said main store and the operation of accessing data/instructions involves the same level and said comparator means being coupled to a predetermined one of said address sources for enabling the delay of a predetermined one of said operations until said conflict condition is detected as being no longer present; and

,

34. control circuit means coupled to said timing means, to said plurality of control input terminals of each of said address switches and to one of said address sources for receiving a set of level signals, said control circuit means for generating a plurality of sets of control signals identifying which address source is connected to supply said address to be loaded into each of said address registers, said control circuit means being operative during a cache cycle of operation in response to said set of level signals to cause one of said plurality of sets of control signals to condition one of said plurality of address switches designated by said set of level signals to select for loading into said address register associated therewith an address from said one address source and also conditioning the remaining ones of said plurality of address switches to select for loading into the remaining address registers an address from another one of said address sources enabling information to be written into said one level simultaneously with the accessing of information from the remaining levels during one of said halves of said cache cycle.