GB2052118A

GB2052118A - Disc Cache Subsystem

Info

Publication number: GB2052118A
Application number: GB8018167A
Authority: GB
Original assignee: Memorex Corp
Current assignee: Memorex Corp
Priority date: 1979-06-04
Filing date: 1980-06-03
Publication date: 1981-01-21
Also published as: DE3021227A1; FR2458846A1; FR2458846B3

Abstract

Data memory sub-system for connection to a data processing system includes a magnetic disc store 14, and a disc controller 20 incorporating a high speed semiconductor cache buffer 16. The memory operates in a broadly conventional manner. The cache may be divided into two levels. The first level may be arranged to store complete disc tracks. The second (slower) level may be formed of CCDs. The controller also includes a microprocessor arranged to manage the stores. <IMAGE>

Description

SPECIFICATION Disc Cache Subsystem The invention relates to the field of rotating magnetic computer disc memories. The invention proposes an improved subsystem architecture wherein a high-speed semiconductor memory of small size permits more rapid retrieval of information that is frequently accessed by the central processing unit.

2. Description of the Prior Art Since the introduction of the System 360, a standard architecture has been established for the attachment of input/output devices to IBM (Registered Trade Mark) central processing units. The central processing unit communicates via a "channel" with peripheral input/output devices. The channel interface permits connection of a storage control unit (SCU) which interprets the commands from the central processing unit and directs writing of information to or retrieval of information from disc devices. In practice, the SCU attaches to a disc controller which in turn can accommodate a plurality of rotating magnetic disc storage drives. A storage control unit of the type hereinabove discussed is the Memorex 3673 storage control unit (described in Memorex Publication 3674.21-00 entitled "3674 Storage Control Unit Theory of Operation").A disc controller of the type hereinabove discussed is the Memorex 3674 disc controller (described in Memorex Publication 3673.21-02 entitled "3673/75/70 Disc Storage Subsystem Theory of Operation"). Disc storage devices of the type hereinabove discussed are the Memorex 3670 and 3675 disc drive modules (described in Memorex Publication 3673.21-02 entitled 3673/75/70 Disc Storage Subsystem Theory of Operation. The interconnection of the channel to the SCU disc controller and disc drive modules is described in Memorex Publication 3673/75/70 Disc Storage Subsystem Theory of Operations (Memorex Publication 3673.21-02).

It is also known in the prior art that a disc controller of the type exemplified by the Memorex 3673 disc controller with a plurality of disc drive modules attached thereto may be attached to a plurality of storage control units via a feature known as the string switch. The string switch feature is an array of hardware and microcode defining an intelligent interface which allows a plurality of storage control units to communicate with a single string of disc drives controlled by a 3673 type disc controller.

A request for storage of a particular piece of data or a request for retrieval of a particular piece of data is initiated by the channel. Through the storage control unit and the disc controller, the disc string will obtain access to the particular piece of information. However, a delay is involved in this process due to the mechanical and electronic configuration of the components. Particular to the mechanical configuration of the disc storage devices, magnetic read/write recording heads are rigidly affixed to a moving carriage which can access a plurality of prerecorded tracks on the disc spindle. A request for information often necessitates movement of the carriage carrying the read/write magnetic transducers to the track upon which the data is stored.The time for the carriage to complete such an access can be as little as ten (10) milliseconds or as great as fifty (50) milliseconds. In addition, once a particular track has been accessed and the carriage electronically locked into place by following the servo tracking information, another delay is encountered while the disc rotates to the proper position where the desired information is stored. Disc rotational delay or "latency" can be negligible or as great as approximately seventeen (17) milliseconds for discs rotating at 3600 RPM. On the average, latency amounts to a delay of approximately eight (8) milliseconds for discs rotating at 3600 RPM. Both the access time and latency delays can amount to significant overheads upon the performance of the central processing unit to accomplish its desired tasks. in residence in much larger capacity direct access storage devices.

United States Patent 4,075,686 to Calle, et al. and United States Patent 4,070,706 to Scheuneman both described system configurations utilizing a cache memory for the rapid access of priority information in order to enhance system performance. Both Calle, et al. and Scheuneman however do not specifically describe or suggest the application of a high-speed semiconductor cache memory to conventional disc string architecture. United States Patent 3,949,369 to Churchill describes a digital computing system utilizing a high-speed cache buffer. Churchill points out that information in the cache buffer might practically be structured so that a priority system is established with respect to such information on the basis of its frequency of use.The most frequently used information would receive the highest priority and the least frequently used information would receive the lowest priority. If additional information needed to be stored within the high-speed cache memory and space was not available, the least frequently used information presently within the cache buffer would be erased. The concept of the least recently used (LRU) algorithm has been explored in the United States Patent 3,737,881 to Corde, et al. Corde, et al. specifically addresses the requirements of application of the caching concept to "pages" of information in a high-speed magnetic buffle domain memory. "Pages" are understood in the computer industry to be predetermined blocks of a certain size dictated by the system control programming or operating system.

In general, the introduction of virtual storage or virtual memory techniques as employed in the configuration of the system control programming or operating system has brought with it the concept of a high-speed storage which might be used for more rapid access of the central processing unit (CPU) to frequently used information as opposed to requiring access by the CPU to the much larger capacity direct access storage devices. A generally described paging system utilizing a high-speed cache memory in conjunction with a larger disc memory is described by United States Patent 3,647,348 to Smith, et al. In addition, the concept of an "apparent store" is explored by United States Patent 3,569,938 to Eden in which, again, high-speed storage is used as an intermediary buffer between the CPU and much larger main storage to enhance the performance of the CPU.However, all references as hereinabove cited specifically do not teach nor do they suggest the application of a high-speed semiconductor cache memory utilizing an LRU algorithm as might be efficiently applied to a disc string.

Summary of the Invention The invention (hereafter sometimes referred to as "disc cache" or "disc cache subsystem") utilizes high speed semiconductor memory devices placed at the disc controller of a string of disc drives to provide more rapid access to frequently requested data than would otherwise be achievable in the prior art. The disc cache is constructed of four main components: 1. interface to disc controller 2. cache control microprocessor 3. load/monitor microprocessor 4. cache memory.

The interface (1) consists of control and data bus electronics to permit connection of the disc cache within the disc controller. In such a manner, it is then possible for the storage control unit to alternatively communicate with the disc cache or the disc string. Moreover, under certain circumstances, the disc cache may take control of the disc string communicating directly with the disc drives and raise a "string busy" condition to the storage control unit. In addition, it is also possible for the disc cache to be effectively severed from the string subsystem so that storage control unit commands simply "pass through" the disc controller to the disc storage devices.

The cache control microprocessor (2) is basically an assemblage of a high speed bit slice microprocessor, scratch pad memories, and storage registers. The cache control microprocessor is the central component of the disc cache subsystem employing a microprogram to control the response of the disc cache to storage control unit commands and the storage of data modules within the cache memory.

Load/monitor microprocessor (3) is an assemblage of components designed to load the cache control microprogram from an external storage medium to writable control storage memory Cache memory (4) is high speed semiconductor memory used to store information that is most frequently required by the central processing unit. The cache control microprocessor determines which information is to be stored as well as keeping track of data module addresses as said information resides upon the disc storage devices.

The disc cache subsystem is under control of a microprogram. In a suitable embodiment, a least recently used (LRU) algorithm is programmed so that the disc cache will store those data modules that are most frequently accessed and erase from the cache memory those data modules with little activity.

If a data module resides within the disc cache and it is desired by the CPU, said data module may be transferred directly from the disc cache to the storage control unit and on to the CPU. Such a data transfer is not dependent upon disc rotation, and it is thus an advantage of the disc cache subsystem that information may be transferred from the disc cache memory to the storage control unit through a "direct memory access" at a speed only limited by the data channel.

In addition, if a particular data module residues in cache memory and a portion of said data module is required by the CPU, the concept of the disc cache permits the advantage of skipping within that data module directly to the desired information. This data skipping advantage is permitted because the data module is in random access semiconductor memory which may be accessed by mere address selection rather than being dependent upon disc rotation.

It is thus an object of the invention to permit the central processing unit of a computer system more rapid access to frequently used data than would otherwise be possible.

It is another object of the invention to utilize high speed semiconductor memory under microprocessor control to store frequently used information.

It is further an object of the invention to control the storage of information within cache memory according to an algorithm.

It is another object of the invention to situate the disc cache at the disc controller of a disc string so that the disc cache may interact with the storage control unit and communicate with the disc storage devices.

Brief Description of the Drawings Figure 1 is a schematic representation of a computer system of the prior art.

Figure 2 is a schematic representation of a computer system employing a disc cache subsystem.

Figure 3 is a diagram showing the assembly of Figures 6, 7a and 7b.

Figure 4 is a schematic representation of an alternative embodiment of the disc cache as applied to a computer system not using a storage control unit.

Figure 5 is a schematic representation of the major hardware components of the disc cache.

Figure 6 is a schematic representation of the interface of the disc cache to the disc controller.

Figure 7a is a schematic representation of the disc cache interface control logic.

Figure 7b is a schematic representation of the cache control microprocessor, load/monitor microprocessor and cache memory.

Figure 8 is a simplified hardware configuration for the disc cache.

Figure 9 is a diagram of tag 0 mode with respect to hardware control.

Figure 10 is a diagram of SCU mode with respect to hardware control.

Figure 11 is a diagram of control mode with respect to hardware control.

Figure 12 is a diagram of pass through mode with respect to hardware control.

Figure 1 3 is a microprogram flow diagram of the disc cache.

Figure 14 is a pulse train diagram of the SYNC IN/SYNC OUT pulses for the prior art.

Figure 1 5 is a pulse train diagram of the SYNC IN/SYNC OUT pulses for the variable data rate feature of the disc cache.

Description of the Preferred Embodiment Contents of Description of the Preferred Embodiment 1. General 2. Disc Cache Hardware 3. Disc Cache Operation Hardware Modes 4. Disc Cache Subsystem Software 5. Storage Management 6. Tag Zero Commands 7. Variable Data Rate 1. General By reference to Figure 1 (prior art), it can be seen that a data processing system as is known in the art is commonly configured by having a central processing unit 2 communicate via memory bus 4 with main memory 6. Central processing unit 2 alternatively can communicate along input-output or channel bus 8 with storage control unit 10. When data is desired to be retrieved from or written to the disc storage medium, central processing unit 2 initiates a suitable command.The command is translated by storage control unit 10 into a series of commands that are specific to the type of device being addressed; in this case, storage control unit 10 would translate the commands from the central processing unit 2 into commands recognizable by disc controller 12. Storage control unit 10 communicates along system CTL interface 13 with disc controller 12. In turn, the commands from the storage control unit 10 are further interpreted and executed by disc controller 12 so that particular information may be written to or retrieved from disc drive(s) 14 via disc drive interface 1 5. Definitions of the prior art computer architecture including hardware interfaces and data and control line definitions can be found in the references cited in the Description of the Prior Art above.

By reference to Figure 2, it can be seen that the disc cache subsystem of the present invention is similar to the subsystem of the prior art as shown in Figure 1. However, disc cache 16 is attached in the component hierarchy to disc controller 20 via cache CTL interface 78. In fact, disc cache 16 is actually located in front of the drive controller logic (reference 62 of Figure 6) and disc drive 14. The disc cache 1 6 represents a level of memory hierarchy between the slower type storage as exemplified by typical disc systems and the faster type of storage as exemplified by main memory 6. Disc cache 1 6 contains internal intelligence which is utilized to manipulate data modules which are shared by the attached disc controller 20 and the string of attached disc drives 14. As used herein, a data module is a generic term for a fixed block or unit of data of some convenient dimensions.

When communicating with the disc controller 20 and disc drives 14, the disc cache 16 performs input/output operations at a speed limited to the rotational speed of disc drives 14. However, input/output operations between the storage control unit 18 and the disc cache 16 can be performed at a much higher transfer rate (decreased "wait" or "latency") than would otherwise be possible with the configuration and architecture of the prior art, which is more fully explained in the variable data rate section hereinbelow.

In the subsystem of Figure 2 which contains disc cache 16 adapted to be connected via CTL interface 78 to disc controller 20 and the string of disc drives 14, the operation is generally as follows: For a data retrieval operation, CPU 2 makes an input/output request for a certain data module or modules residing on disc drives 14 through channel bus 8 to the storage control unit 18. The storage control unit 18 translates the request of CPU 2 into a set of commands acceptable by the disc cache 1 6. Referring to Figure 5, if the requested data module is present in cache memory 54 residing within disc cache 16, it is transferred to the storage control unit 18 via system CTL interface 13 and cache CTL interface 78.If the data module requested is not present in cache memory 54, the disc cache 1 6 will retrieve via cache CTL interface 78 and bus 1 5 the required data module from disc driyes 14 through disc controller 20 to store it within cache storage 54 of disc cache 1 6. The required data module is then transferred to the storage control unit 1 8 from disc cache memory 54 residing within disc cache 1 6 (Note: The ordering of disc cache operations may vary with the particular embodiment of the invention, and said ordering is clearly micropgram dependent).

If the central processing unit 2 desires to update information to the storage medium (i.e., a "write" type of request) it is possible for the storage or updating of such information to occur either directly in disc drives 14 through disc controller 20 or to update or write said information directly to disc cache memory 54 of disc cache 16 (Again, ordering of disc cache subsystem operations is microprogram dependent). If said information is written directly to disc cache memory 54, it would normally later be transferred to disc drives 14 for permanent storage.

It is within the concept of the invention that in certain data processing architectures, a storage control unit might not be employed and that the intelligence or functions of said storage control unit would reside within the central processing unit. Referring to Figure 4, it is within in the concept of the invention that the disc cache 1 6 could communicate directly with central processing unit 36 along a suitable data control bus 13 via cache CTL interface 78. In this embodiment, central processing unit 36 contains suitable intelligence so as to permit communication directly with disc cache 16 through input/output bus 13. Disc cache 1 6 thereafter communicates with disc controller 20 and disc drives 14 through control input/output bus 15.

Thus, in its most general embodiment, the disc cache is an intelligent, disc type specific, high speed memory interposed within the input/output subsystem architecture permitting under certain circumstances the retrieval of information from the input/output subsystem at a higher speed not otherwise achievable by the prior art.

2. Disc Cache Hardware The disc cache subsystem as disclosed herein is an apparatus combining hardware and software techniques to achieve the desired objects as detailed above. The particular implementation of the apparatus (in this case the hardware) can take many forms, but an embodiment of disc cache 1 6 of Figure 2 that has been found to be suitable is set forth in Figure 5. It can be seen that that the major hardware components of the-disc cache subsystem consist of the following: interface control logic 48, disc cache, disc cache control microprocessor 50, load/monitor microprocessor 52, and the cache memory 54.

The first major hardware component is interface 48 between disc cache control microprocessor 50 and disc controller 20. The cache CTL interface serves the function of providing a means for attachment of the disc cache subsystem to the disc controller as shown in Figure 6. This controller can be of a type such as the Memorex 3673 disc storage controller which generally is defined in Memorex Publication 3673.21-03. As shown in Figure 6, disc controller 20 has been modified to permit the attachment of the disc cache 1 6 by the addition of interface 58 within the CTL interface of the disc controller. Note that interface 58 is positioned between the system CTL interface 13 3 after string switch 68 and before drive controller logic 62.CTL lines 64 connect string switches 68 with cache interface 58, and CTL lines 34 connect the drive controller logic 62 with cache interface 58. In the particular embodiment being described, it is necessary that the Memorex 3673 disc controller have installed the string switch 68 as described in Memorex Publication 3673.21-03. Cache interface 58 provides data buses and control lines required by the CTL interface. Cache control lines 70 permits the disc cache subsystem to exert control over the string switch interface resident within the disc controller. Full access to the CTL interfaces is provided into the disc cache by System CTL lines 72 and from the disc cache by cache CTL lines 74.

The second main hardware component of the disc cache 16 is the disc cache control microprocessor 50 of Figure 5 (shown in greater detail in Figure 7b). In a particular embodiment it has been found suitable to use a high speed bit slice microprocessor capable of 4,000,000 instructions per second as the microprocessor 76 of Figure 7b. For this particular embodiment, it has been found suitable to employ a custom microprocessor developed from the Advanced Micro Devices 2900 family of LSI processor chips. However, many other processor designs are possible within the concept of the disc cache subsystem invention that would be capable of handling the disc cache tasks.The basic tasks of the disc cache control microprocessor 50 are: 1) respond to control and data transfer commands from the cache CTL interface 78 of Figure 6, (2) maintain a directory of data available presently within the cache memory 54 of Figures 5 and 7b (described below), (3) control and fill the cache memory 54 with the disc drive data most likely to be required (described below), (4) perform error detection and recovery procedures, and (5) communicate performance data to load/monitor microprocessor 52.

The third major hardware component of a suitable embodiment of the disc cache subsystem is the load/monitor microprocessor 52 of Figure 5. For the load/monitor microprocessor 52, it has been found suitable to employ an Intel 8080A microprocessor. The Intel 8080A is a complete 8-bit parallel central processing unit that operates at 2 million cycles per second. These are substitute microprocessors commercially available which might be alternatively employed in lieu of the Intel microprocessor. The basic tasks of the load/monitor microprocessor 52 are: (1) control loading of control memory information from flexible disc drive 84 (described below), and (2) perform performance monitoring tasks for the disc cache subsystem.

The last major hardware component of the disc cache subsystem as displayed in Figure 5 is the cache memory 54. In a suitable embodiment of the disc cache the cache memory 54 is composed of two levels of semiconductor memory. The first level of semiconductor memory is the full track buffer 86 shown in Figure 7b. While it is not mandated by the concept of the invention that two levels of semiconductor memory comprise cache memory 54 and while it is, likewise not mandated by the conception of the invention that the unit of information to be stored by disc cache 16 be a full track of disc drive data, it has been found convenient to configure the hardware of the disc cache as such.Thus, the first level of semiconductor memory, the full track buffer 86, contains at least one full track of disc drive data and may be constructed from a variety of static or dynamic random access memory chips. It has been found suitable that said full track buffer 86 be constructed from Intel 2147 or Intel 211 7 integrated circuits. The second level of cache memory 54 has been configured of lower speed devices, and charge coupled devices (CCD's) have been successfully employed for the said lower speed level of cache memory 54. In the particular embodiment up to 12 megabytes of charge coupled devices have been employed in a configuration using Fairchild F464 charge coupled devices (each device can store a maximum of 64,000 bits of information).In actuality, the cache memory 54 is actually two levels of a three-memory hierarchy of the disc cache subsystem wherein the first level of storage is the disc storage devices 14 and the subsequent two levels of memory are the semiconductor memories as hereinabove described. As will be described below, the function of the cache memory 54 is to store disc drive data in conformance with an algorithm which stores disc drive data most likely to be required by the computer system (more specifically described below).

By referring to Figures 7a and 7b, a more detailed definition of the major hardware components of disc cache 1 6 can be seen. In order to understand the description as shown in Figures 7a and 7b, the following definitions are helpful: Interface 90 Two interface control printed circuit boards containing logic for generation of data buses and control signals for the cache CTL Interface 78.

Storage Control A typical DMA ("Direct Memory Access") port that contains memory Unit Direct Memory request logic and address and word counters for control of data transfers Access 92 between the cache memory 54 and storage control unit 18.

Drive Direct A typical DMA ("Direct Memory Access") port that contains memory Memory Access 94 request logic and address and word counters to control data transfers between the cache memory and disc drives 14.

Cache Control -- A four million instruction per second bit slice microprocessor utilizing Microprocessor 76 AMD 2900 family of LSI processor chips.

Load/Monitor A microprocessor with the Intel 8080A single chip CPU as its basic Microprocessor 82 component. It runs at 2 MHz and has 2Kx8 EProm for control~ memory.

Scratch Pad 96 8Kx16 of static RAM memory for support of cache control microprocessor 76.

Scratch Pad 98 Two 16 bytex8 FIFO (First In First Out) cache control microprocessor memories utilized as data buffers for communication with load/monitor microprocessor 82.

Writable Control 4Kx40 bits of Intel 2147 static RAM memory utilized as the control Store 100 memory of cache control microprocessor 76.

Online A control register whose bits are set by the Online switches from the Register 102 operator's panel 104. Cache control microprocessor 76 monitors this register to determine what drives should be cached.

Operator's Contains power on and cache enable switches for Panel 104 each drive.

Flexible Disc A flexible disc drive used for microprogram load. May be of standard Drive 84 Memorex 550-type.

Error Correction Error detection and correction Logic, ("Hamming Scheme") used for Code 106 (ECC) single bit error correction and double bit error detection.

Full Track 4Kx40 bits (including ECC) of static RAM memory using Intel 2147 Buffer 86 chips.

Charge Coupled 1 to 12 megabytes of CCD memory using the Device Memory 88 Fairchild CCD.

Basic Data Bi-directional data bus for data transfers between SCU or Drive DMA Bus 108 ports and full track buffer 86.

Basic Address Tri-stated memory address supplied to full track buffer 86 from SCU Bus 110 DMA 92 or drive DMA 94.

C-Bus 138 Bi-directional data bus for data transfers between full track buffer 86 and CCD memory 88.

C-Bus 140 Tri-stated source bus for all external ports available to cache control microprocessor 76.

Y-Bus 142 Tri-stated destination bus for all external ports available to cache control microprocessor 76.

B-Bus 144 Tri-stated data bus used to access ECC logic 106 by full track buffer 86.

Memory Address Memory address bus used by cache control microprocessor 76 to Bus 148 address writable control store 100.

Pipeline Bus 1 50 Pipeline instruction bus by which cache control microprocessor 76 obtains its microinstructions from writable control store 100 and communicates with scratch pad 98.

Cache Bus-In 1 50 8 Bit "bus-In" Data Bus; this is the System CTL lines 72 data "bus-in" for data transfers from cache to the system SCU.

Bus-In 152 8 bit "bus-In" data bus; this is cache CTL lines 74 data "bus-In" used for data transfer from the disc drives to the cache memory.

Bus-Out 156 8 Bit "bus-put", the System CTL lines 72 "bus-out" used for data transfers and control command data from the system SCU 18 to the disc cache 16.

Cache Bus-Out 158 8 Bit "bus-out", the Cache CTL lines 74 bus-out used for data and control commands when the disc cache 16 controls the disc drives 14.

CTL Lines 160 CTL Interface control lines generated in the interface 90 logic.

Cache Control A set of control signals generated in interface logic by cache control Lines 70 microprocessor 76 to control switching of the multiplexers of interface 58 of Figure 6 to select the desired interface communication path.

BC,xx All lines shown in Figure 7b with the BCixx are to indicate that a bus or control communication path does exist but it is not explicitly defined herein.

To more fully explain the invention, Figures 6, 7a and 7b should be oriented as shown in Figure 3.

Referring to Figures 7a and 7b, microprocessor 76 is the controlling component of disc cache 16.

Microprocessor 76 receives all external data via tri-stated 16 bit data bus 140 and writes to all external ports via 16 bit tri-stated output data bus 142. As described above, one of the basic functions of the disc cache subsystem is to respond to data transfer and control commands received from the system storage control unit 18 of Figure 2 via cache CTL interface 78. The cache control microprocessor 50 monitors the system commands received from interface control logic 48 in turn from the cache CTL interface 78. Cache control microprocessor 50 responds to commands by setting the proper response in control registers in interface control logic 48. These commands are then gated to the cache CTL interface 78 as required by the CTL interface specifications as defined in the prior art.

Microprocessor 76 receives its micro instructions from writable control store 100 along pipeline bus 148. Microprocessor 76 addresses writable control store 100 via memory address bus 146.

Scratch pad 96 is primarily used by microprocessor 76 to store a listing of disc drive track addresses that currently reside in cache memory 54. The track list addresses as stored in scratch pad 96 can be searched and dynamically updated by microprocessor 76 as data in cache memory 54 is accessed.

Microprocessor 76 uses D-bus 140 and Y-bus 142 to access scratch pad 96. In addition, other relevant disc cache control data is stored in scratch pad 96 as defined by the disc cache microprogram (described below). Microprocessor 76 also integrates the information in online register 102 determining which disc drives 14 on the string are subject to "caching".-The storage control unit direct memory access 92 and drive direct memory access 94 are used for data transfers between the full track buffer 86 and the system storage control unit 18 and disc drives 14 respectively. The direct memory access ports are programmed and monitored via D-bus 140 and Y-bus 142 by microprocessor 76.

Full track buffer 86 is addressed via the basic address bus 110 and its contents are transferred to or from either direct memory access port via basic data bus 108.

Full track buffer 86 and CCD memory 88 share common error detection and correction logic 106.

Data transfers between full track buffer 86 and CCD memory 88 are of what is known in the art as a direct memory access-type of operation via bi-directional C-bus 183 controlled by microprocessor 76.

In addition, cache control microprocessor 50 programs the direct memory access logic included within the charge coupled device memory via Y-bus 142.

3. Disc Cache Operational Hardware Modes While it is possible to practice the concept of the disc cache invention in many configurations, a configuration which has been found to be particularly suitable is that which is compatible with IBM subsystem channel/control unit/device architecture well known in the prior art. Referring to Figure 8, storage control unit 18 connects to disc controller 20 via system CTL interface 13. Disc controller 20 connects to disc cache 16 via cache CTL interface 78. Disc controller 20 connects to disc drives 14 via interface 15. It is something of a simplification to show interfaces 1 3, 1 5, and 78 connected together within disc controller 20 at point 610.In fact, 610 is not a hardwired connection but rather a juncture within the disc controller which will in fact vary depending upon the hardware mode of operation as defined hereinbelow.

There are basically four hardware modes of operation for the disc cache 1 6 as determined by commands from storage control unit 18 in a suitable embodiment to practice the invention. They are as follows: 1) Tag Zero Mode. When in tag zero mode as shown in Figure 9, all tag commands except tag zero commands (as described herein under subsection heading "Tag Zero Commands"), are transferred between storage control unit 18 through interface 13 to disc controller 20 and onto disc drives 14 through bus 1 5. For all commands except tag zero commands, the disc cache 1 6 is effectively not present on the string. Tag zero commands, however, are transferred from the storage control unit 18 through interface 13 to disc controller 20, but disc controller 20 routes these commands to disc cache 16 through interface 78.The response to tag zero commands is from disc cache 1 6 to disc controller 20 and storage control unit 18 through interfaces 78 and 13 respectively. Thus, tag zero mode can be understood as a hardware mode in which all other tag commahds except tag zero are routed to disc drives 14, but disc controller 20 routes tag zero commands to disc cache 16 through interface 78. The response to tag zero commands is from disc cache 16 to disc controller 20 and storage control unit 18 through interfaces 78 and 13, respectively. Thus, tag zero mode can be understood as an operational hardware mode in which typical tag commands are handled on the disc subsystem in a manner consistent with the prior art except for the specialized tag zero commands which are routed to the disc cache.

2. SCU Mode. If the disc cache 16 is in SCU Mode, all tag commands are transferred from the storage control unit 18 (referring to Figure 10) through interface 13 to disc controller 20 on to disc cache 16 through interface 78. The disc cache 16 is in the "active" state in the microprogram sense (see Software description hereinbelow). In the SCU Mode, no communication is possible between the storage control unit 1 8 and disc drives 14; this is the primary operational mode for the disc cache 1 6.

3. Control Mode. If in this hardware mode, disc cache 16 as shown in Figure 11 communicates directly with disc drive(s) 14 through disc controller 20 through interfaces 78 and 15, respectively. In this mode, storage control unit 1 8 will receive a "busy" status from disc controller 20 which means that no connection can be attempted between storage control unit 18 and disc controller 20 through interface 13. Disc cache 1 6 has effectively usurped control of the disc string subsystem and controls its operations.

4. Pass Through Mode. Pass through mode as shown in Figure 12 is effectively a hardware mode allowing direct communication between the storage control unit 18 and disc drives 14 through disc controller 20 and associated interfaces 13 and 15. During this operational mode, no tag commands are routed to the disc cache 16 through interface 78. The disc cache is effectively disconnected from the disc storage string subsystem and the subsystem behaves as if no disc cache 16 were connected.

The hardware operational modes as hereinabove described work integrally and are under the control of the sybsystem microprogram resident in cache control microprocessor 50. As described below in the section entitled ~'Disc Cache Subsystem Software", it is the initiation by storage control unit 18 of appropriate tag zero commands which catalyzes the microprogram to change microprogram state (defined below) to effect changes in hardware operational modes of the subsystem.

4. Disc Cache Subsystem Software The concept of the disc cache invention can be practiced in many different ways. In a particularly suitable embodiment, the hardware as described hereinabove works in conjunction with a microprogram that is loaded through flexible disc drive 84 into writable control store 100 that is addressed by microprocessor 76. in the sense of the microprogram for a suitable embodiment of the invention, the microprogram employs four "states" which describe software conditions of the device with respect to its desired functions. A "state" can be understood as a condition of the microprogram which remains static unless changed and/or altered by external input. Referring to Figure 13, there are four microprogram states in the preferred embodiment: (1) wait state 400, (2) select state 414, (3) active state 424, and (4) passive state 432.

In wait state 400, the disc cache as well as the entire disc subsystem is in a "quiet" condition as evidenced by the system CTL interface 13 between the storage control unit 18 and disc controller 20 being quiescent; there are no signals on system CTL interface 13 of Figure 6. As shown in Figure 13, wait state 400 can be understood as an infinite programming loop that begins with the condition of the select hold line of CTL interface 78. If the select hold line is low (i.e., a "no" condition 402), the microprogram will begin to time for a "scan timeout" 404. If the disc cache subsystem remains in its quiet condition so that a scan timeout is achieved (i.3., "yes" 406), then the disc cache subsystem will enter a scan processing 408 mode in which internal "housekeeping" functions for the disc cache are performed.Upon completion of the scan processing 410, the microprogram returns to the wait state 400 and again monitors the condition of select hold on system CTL interface 13 in Figure 6. Scan processing 408 is not a "state" which the microprogram enters in a "stable" condition. That is, scan processing 408 is merely a function through which the programming always flows to an end condition and returns to the wait state 400. Scan processing is a function of the microcode which is analogous to hardware "control mode" as defined in hereinabove while wait state 400 can be understood as a hardware tag zero mode.

If the select hold line goes "high" (yes 412) during the wait state, then the disc cache microprogram enters the "select" state 414. The "select" state 414 is defined as a condition wherein the select hold line is "high"; the storage control unit has notified all strings of drives connected thereto of an impending selection of one of the strings. At all times during the select state 414, the condition of the select hold line is monitored. If the select hold line goes "low", then select hold is inactive and a yes 416 condition as shown in Figure 13 will return the disc cache microprogram to the wait state 400. If the select hold line remains "high" (i.e., not inactive 41 8), then the microprogram monitors for a tag zero command upon cache CTL Interface 78 of Figure 6.If a tag zero "active" command is not received (reference 420), the microprogram stops in "select" state unless "select" hold goes "inactive" (i.e., "low" 416) in which case the microprogram returns to the wait state 400. If a tag zero active command is received (reference yes 422), then the microprogram will enter the "active" state 424. As is the case for wait state 400, select state 414 is also a hardware tag zero mode.

The "active" state 424 is defined as a condition of the microprogram in which the storage control unit 18 has already selected a specific drive controller 20 and if the disc cache 1 6 is attached to said drive controller 20 and disc string subsystem, then a tag zero "active" command will "activate" the disc cache microprogram. In the "active" state 424, the disc cache intercepts and/or receives all instructions emanating from the storage control unit 18 and therewithin data processing operations take place. This could also be called "caching" state and can be understood as the main cache operational state. In the hardware sense, this is "SCU mode" as described hereinabove. If, during the "active" state 424, the tag zero "passive"command 425 is not received by the disc cache microprogram (reference 426), then the disc cache will perform disc caching commands 428.The performance of disc caching commands 428 as shown in Figure 13 is not a "state" but more properly a condition of the microprogram through which functions are performed and, upon completion, the microprogram returns to the "active" state 424. The performance of cache commands can be thought of as "SCU mode" in the hardware sense. If, during the "active" state 424, a tag zero "passive" command is received (reference 430 in Figure 13), the microprogram will enter the "passive"state 432.

The "passive"state 432 is defined as a microprogram condition in which the storage control unit 18 communicates directly with the disc storage devices 14. Notice that this is in distinction to the "active" state 424 in which the disc cache receives all instructions and there is no communication between the storage control unit 18 and the disc storage devices 14 directly. Prior to the initiation of the "passive" state 432, the storage control unit 1 8 has originated a tag zero command of specific decode to "drop" the disc cache microprogram into a "passive" state allowing communication between the storage control unit 18 and the disc drives directly (this is the tag zero passive command 430).In the "passive" state 432, the disc cache 1 6 is continually monitoring tag zero commands (i.e., hardware tag zero mode). If a tag zero "active" command is received as shown by yes 434 in Figure 13, the disc cache 1 6 will return to the "active" state 424. If a tag zero "active command 437 is not received during the "passive" state (reference 436), the condition of the select hold line as hereinabove described is monitored. If a select hold goes "active" (yes 439) during the "pa#ssive" state, the disc cache microprogram becomes poised for receipt of a tag zero "active' command.If in fact a tag zero "active" command is received (i.e., yes 434), then the disc cache 1 6 will return to the "active" state 424. If the select hold line goes "low" (i.e., no 440) then the disc cache will proceed with fill processing 442.

While passive state 432 is a hardware tag zero mode as described hereinabove, fill processing 442 is a hardware control mode. During fill processing 442, the disc cache 1 6 takes control of the string of disc storage devices and fills into the full track buffer 86 information which at this point may only reside upon the magnetic discs 14. During fill processing 442, a full track of information will be transferred from the disc storage devices 14 to the full track buffer 86. Appropriately, since the track to be transferred to the full track buffer 86 is the one most recently requested, said track will receive the status of the most recently used track in the storage management tables residing in scratch pad memory 96 of Figure 7b. Moreover, this track table entry will be adjusted in said memory to accommodate the track loaded into the full track buffer 86 with respect to disc device number cylinder location, and head address. Upon the completion of fill processing 442 (which is not a "state"), the microprogram will return to the wait state 400 and again monitor the status of the select hold line. In a "hardware" sense, the initiation of fill processing 442 causes the disc cache to take "control" of the disc string subsystem. During fill processing 442, the storage control unit 18 may not communicate with the disc string, and a "string busy" condition exists to the storage control units attached to the string.

It can thus be understood that the hardware and microprogram of the disc cache subsystem can integrally respond as follows in a typical situation.

Time To A select hold "active" is received from the storage control unit 18 by disc cache 16.

Time T,: A tag zero command is received from storage control unit 18.

Time T2: Cache microprogram changes state (if required).

Time T3: Cache requests hardware to change mode.

Time T4: Function is performed (microprogram is in new state and hardware is in new mode).

Time T5: Process proceeds as required as shown in Figure 13.

While a suitable embodiment to practice the invention of the disc cache subsystem includes error recovery and other programming embellishments to enhance operation a suitable logical configuration for the microprogram is as hereinabove described and shown in Figure 1 3.

5. Storage Management The disc cache subsystem uses tables which generally reside within scratch pad 96 of Figure 7b for management of cache storage. While within the concept of the invention, many implementations for achieving the objects are possible, a particular scheme of storage management within the preferred disc cache embodiment has been found to be suitable. While generally data modules residing within the cache memory 54 can be based upon discreet units of information of any size, in the preferred embodiment CCD storage 88 contains full tracks of information, which in the case of the Memorex 3670 and 3675 disc storage devices amounts to 13,030 bytes of information. Each of the data tracks are loaded from the disc drives 14.Each track of data that is stored within charge coupled device memory 88 and full track buffer 86 has corresponding entries in the tables available to the microprocessor 76 created by the necessity for management of the data.

The disc cache scratch pad 96 maintains three types of storage management tables: the dynamic table, the track lock table, and the list of empty storage. The dynamic table is continuously updated based upon cache memory 54 usage criteria. An LRU Algorithm as known in the art has been successfully employed for this purpose. The track lock table contains parameters for that portion of the CCD memory 88 which is "locked" into cache memory 54. Within the meaning of this invention, "locking" a track into the cache means that a data track is not replaced based upon an algorithm as is the case with the dynamic table (i.e., it is permanently in cache memory 54).The list of empty storage is a table which keeps track of available space within CCD memory 88; the contents of the table listing empty storage is that storage currently not being used and consequently available to be filled with data from the disc drives 14.

Every data track stored within cache memory 54 has corresponding entries within the dynamic table wherein each entry consists of a plurality of parameters or items. Two parameters link the table together based upon the most recent usage and least recent usage of the tracks listed therein respectively. Every time a data track is requested from the cache memory 54, the item related to this track is put on the top of the list (i.e., most recently used) and the item on the bottom of the list becomes the least recently used. Other parameters contain information relating to the disc tracks to specific cylinder addresses, head addresses and device addresses in the disc storage devices 14 from whence they came. Taken together, address pointers link together by known linking techniques items of the dynamic table which allows updating of the table based on track usage.

If the cache memory 54 is filled and another data track is required to be filled from the disc storage devices 14 into the cache memory 54, the least recently used data track on the bottom of the table will be dropped from the table and the new data track just filled from the disc storage devices 14 will be put on the top of the table becoming the most recently used data track. This algorithm is well known in the prior art and guarantees that the most recently used tracks are in the cache storage while data tracks with low activity are dropped from cache memory 54.

The dynamic table also contains a second set of link pointers which link together data tracks filled from a particular disc storage device, i.e., with the same disc storage device address. These tables are also updated when most recently used/least recently used linkage information is updated. In this manner, searching the cache memory 54 for a particular track can be shortened as it is always known that the storage control unit's fetch for a particular track will specify the particular disc storage device.

Thus, it is considerably shorter to search a table of most recently used/least recently used tracks if said table is linked by specific disc storage device. Naturally, if only one disc storage device is being cached at any given time, then the entire contents of cache memory 54 will have to be searched, but if more than one disc drive is cached, then significant economies of searching can be realized.

6. Tag Zero Commands The standard architecture of the IBM compatible disc storage device subsystem utilizes certain commands known as "tag" commands whereby the storage control unit 18 communicates with the drive controller 20 on the system CTL interface 13. For a complete definition of the system CTL interface and tag commands as well as a definition of bus-in and bus-out lines, see Memorex 3673/3675/3670 Disc Storage Subsystem Theory of Operations (Publication 3673.21-02).

However, it is not possible within the standard architecture for the storage control unit to activate and control a disc storage subsystem where said subsystem includes a disc cache 16; it is necessary in order to employ the concept of the disc cache invention to generate or utilize a special tag command which will activate the disc cache 1 6 logic and permit caching operations to proceed as herein described. Any number of tag commands could be so employed with the only requirement being that a tag command so chosen as the specific command which is intended to activate the disc cache not be ambiguous and confused with other tag commands that are decoded to have different meanings within the architecture of the disc I/O subsystem.In a particular embodiment, it has been found suitable to employ tag decode 00 (hex) with variable values on bus-out as that tag command which will initiate cache functions. When a tag zero command is received by the disc cache 1 6 from the storage contrgl unit 1 8, the disc cache may take control of the disc subsystem and perform whatever operations are required as hereinabove described. Within the definition of the Input/Output subsystem that is IBM channel-compatible, tag decode 00 is an unused CTL tag out bus (tag bits 0, 3,4, 5, 6, and 7, all equal zero) which is used in conjunction with the CTL bus out lines.

Variable Data Rate Because of the disc cache subsystem architecture as hereinabove described and generally shown in Figure 2, it is possible to obtain a beneficial effect that can be called variable data rate. Variable data rate allows the channel to transfer data at its own data rate rather than being limited as in the prior art to a data rate established for transfer between the disc storage devices and the control unit dependent upon the rotational rate of disc storage devices. In a suitable embodiment of the disc cache 16 invention, when a full track of information is stored within full track buffer 86 of Figure 7b and said information is desired by the central processing unit, the data transfer rate between, the disc cache subsystem and the channel need not be at a constant data rate and is not controlled by the data transfer rate of the rotating media.As the data transfer rate of the cache CTL interface 78 is not required to be constant, the transfer rate of the channel is the controlling factor.

In order to understand the concept of the variable data rate aspect of the disc cache 1 6 invention, it Is necessary to first understand the limitations of the prior art. Referring to Figure 1 4, SYNC IN and SYNC OUT lines of a prior art data transfer are displayed. The basic timing relationship is defined by the time between edges 200 and 204, 204 and 208, 208 and 212. The time between those pulses is equal and controlled by clocking pulses defined directly by servo encoded information on the rotating disc memory. The time between edges 200 and 201,204 and 205, 208 and 209, and 212 and 213 is controlled by hardware within the disc string controller 12 of Figure 1.The time relationship between the leading edge of SYNC IN pulses (references 200,204, 208 and 212) and the leading edge of SYNC OUT pulses (references 202, 206, 210 and 214), and the time relationship between the trailing edge of SYNC IN pulses (references 201,205,209 and 213) and the trailing edge of SYNC OUT pulses (references 203,207,211 and 215) is controlled by CTL cable delays and hardware delays within storage control unit 10. The time between the leading and trailing edges of the SYNC OUT pulses (time between 202 and 203,206 and 207,210 and 211, and 214 and 215) is controlled by storage control unit 10 hardware and its delayed recognition of SYNC IN.

Implementation of the variable data rate concept produces a pulse sequence significantly different from the prior art SYNC IN/SYNC OUT relationship. Using the variable data rate concept, the leading edge of SYNC IN pulses will not bear a repetitive temporal relationship with respect to the SYNC OUT pulses. Referred to Figure 15, the time between points 216 and 220 and between 220 and 224 is controlled by the hardware transfer rate of the disc cache 1 6 and control electronics and not controlled by the rotational rate of the disc storage devices. Notice that the time between edges 21 6 and 220, and between 220 and 224 is less than that shown in Figure 14 between edges 200 and 204, 204 and 208, and 208 and 212, the prior art train of SYNC IN pulses.That is, the transfer rate under the variable data rate embodiment is higher than that of the prior art because the transfer rate is controlled by the electronics of the disc cache 1 6 and not rotation mechanical components.

The time between edges 224 and 228 and between 228 and 232 is controlled by a monitoring by the control electronics of the trailing edge of SYNC OUT. It is the recognition of edges 227 and 231 of the SYNC OUT trail of pulses that controls the temporal relationship between edges 224 and 228, and between 228 and 232. Edges 228 and 232 of the SYNC IN pulses can only occur after recognition of the trailing edges 227 and 231 of the SYNC out pulses. Trailing edges 227 and 231 of the SYNC OUT pulses are shown significantly delayed from the leading edges 226 and 230, respectively, because they are delayed by the storage control unit hardware whenever the internal storage control unit data buffers are unavailable for further CTL data transfer. The internal stoage control unit data buffers become unavailable when the CTL data transfer rate exceeds the channel data transfer rate.

Therefore, in the variable data rate embodiment of the disc cache subsystem invention, the time between the leading edge 226 and trailing edge 227 and the time between the leading edge 230 and trailing edge 231 of the SYNC OUT pulses includes the time needed so that the channel data transfer rate will meet or exceed the CTL data transfer rate. Thus, there is a "synchronizing" of CTL data transfer rates and channel transfer rates. The data transfer rate is "variable". The time between edges 224 and 228, and between edges 228 and 232, therefore, consists of delays caused by subsystem hardware, the CTL cable including line drivers and receivers, and the disc cache 16 memory and control electronics.As is the case with the prior art system, the time between the leading edge of SYNC IN pulses and the leading edge of the SYNC OUT pulses (that is between points 216 and 218,220 and 222, 224 and 226, 228 and 230, and 232 and 234) consists of CTL cable delays and storage control unit hardware delays (that is, line drivers and receivers).

As is the case in the prior art, SYNC IN/SYNC OUT temporal relationship, the time between edges 21 7 and 219, 221 and 223, and between 233 and 235 is similarly comprised of CTL cable delays, storage control unit hardware delays to monitor the availability of internal buffers, and storage control unit line driver/line receiver delays. What is not the case in the prior art and which is an aspect of the variable data rate implementation is the additional delay between edges 225 and 227, and between edges 229 and 231 caused by the delay of the channel to transfer a byte of information (that is, to make an internal storage control unit data buffer available). The time between points 216 and 217, 220 and 221, 224 and 225, 228 and 229, and between 232 and 233 is controlled by the disc cache 1 6 which is designed to provide well-shaped pulses of sufficient duration.

Thus, it can be seen that the variable data rate embodiment allows data transfer between the disc cache 16 and the channel 8 at a rate which is not otherwise possible in the configuration of the prior art. The data transfer rate is essentially controlled by the data rate of the channel 8.

Claims

1. A direct access storage device cache subsystem for use with a data processing system to decrease the time required to retrieve predetermined data comprising: direct access storage device means for storing data therein and retrieving data therefrom; data memory means for storing said predetermined data; and control means interconnecting said direct access storage device means, said data memory means and said data processing system and for controlling communication therebetween, where the time required to retrieve said predetermined data from said data memory means is less than the time required to retrieve said predetermined data from said direct access storage device means.

2. The subsystem of Claim 1, including storage control unit means interconnecting said control means with said data processing system.

3. The subsystem of Claims 1 or 2 wherein said control means includes a direct access storage device controller interconnecting said first access storage device means to said data processing system; and data memory controller means interconnecting said data memory means to said direct access storage device controller, said data memory means controller being adapted to cause predetermined data to be stored in said data memory means.

4. The subsystem of Claim 3 wherein said data memory controller includes microprocessor means connected to direct access storage device controller means and said data memory means; control store memory means connected to said microprocessor means to control the operation of said microprocessor means such that predetermined data may be stored in said data memory means; and scratch pad memory means records the direct access storage device address of said predetermined data stored within said data memory means.

5. The subsystem of Claim 4 including interface control means interconnecting said data memory controller means and said direct access storage device controller means.

6. The subsystem of Claim 5 wherein said interface control means includes direct memory access means permitting direct memory access data transfer between data memory means and said data processing system and between data memory means and said direct access storage device means.

7. The subsystem of Claim 4 wherein said control store memory means includes a microprogram which causes the storage of information within said data memory means to take place in accordance with a least recently used algorithm.

8. The subsystem of Claim 4 including load/monitor microprocessor means connected to said data memory controller means to load a microprogram into said control store memory means for execution by said microprocessor means and to monitor the performance of said direct access storage device subsystem.

9. The subsystem of Claims 1 or 2 wherein the storage media included within said data memory means comprises random access semiconductor memory means.

10. The subsystem of Claim 9 wherein said random access semiconductor memory means includes at least primary storage means and secondary storage means.

11. The subsystem of Claim 10 wherein said primary storage means is capable of a data transfer rate greater than the data transfer rate of said secondary storage means.

12. The subsystem of Claims 1 or 2 wherein said predetermined data is of a fixed field dimension which corresponds to the data field architecture of said direct access storage devices.

13. The subsystem of Claim 7 wherein the data storage capacity of said data memory means is less than the storage capacity of said direct access storage device means.

14. The subsystem of Claims 1 or 2 or 3 or 4 wherein said direct access storage device means comprise rotating magnetic disc storage devices.

15. The subsystem of Claim 14 wherein the units of said predetermined data correspond to full tacks of information as stored upon said rotating magnetic disc storage devices.