Electrical computers and digital processing systems: memory – Addressing combined with specific memory configuration or... – Addressing cache memories
Reexamination Certificate
1997-11-17
2001-05-01
Gossage, Glenn (Department: 2759)
Electrical computers and digital processing systems: memory
Addressing combined with specific memory configuration or...
Addressing cache memories
C711S005000, C711S157000, C711S201000
Reexamination Certificate
active
06226707
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and system for data processing that utilizes cache memory, and more particularly to a method and system that utilizes dual access to cache memory.
DESCRIPTION OF THE RELATED ART
Cache memory is a special high speed memory designed to supply a processor with the anticipated most frequently requested instructions and data. Instructions and data located in cache memory can be accessed many times faster than instructions and data located in main memory. The more instructions and data the processor can access directly from cache memory, the faster a computer will operate.
In general, there are two levels of cache memory, internal cache, which is typically located inside the processor chip, and external cache, which is normally located on the system board. Internal cache is sometimes referred to as primary cache or level one (L1) cache. External cache is sometimes referred to as secondary cache or level two (L2) cache., In most desktop personal computers, the internal cache will range from 1 kilobyte(KB) 32 KB (1,000 to 32,000 bytes) in size. In contrast, external cache configurations are usually much larger, ranging in size from 64 KB to 1 megabyte (MB) (64,000 to 1,000,000 bytes). Cache memory is usually arranged in a series of cache lines. Each cache line has a fixed capacity. For example, a typical cache line has a capacity to store 32 bytes. A cache memory of 32 KB would consist of one thousand 32-byte cache lines.
FIG. 1
is a depiction of a known configuration of a computer system
10
that utilizes cache memory. The cache memory
14
is usually placed operationally between the data processor
18
and the main memory
12
. When the processor requires access to specific information, a request is transmitted to the fetch unit
19
. The fetch unit looks first to the cache memory to determine whether the information required is available in the cache.
Data and/or instructions are stored in the cache based on what data and/or instructions are likely to be needed next by the processor. The fetch unit looks first to cache memory because if the requested data is located in the cache memory, access time is greatly reduced relative to the time necessary to access the main memory. If the data is not present in the cache, the main memory is accessed to obtain the desired data. In addition to obtaining the data from the main memory for execution, the desired data and data surrounding the desired data are copied from the main memory and stored in the cache. Data surrounding the desired data is stored in the cache because there is a statistical likelihood that the surrounding data will be needed next by the processor for execution. If the surrounding data is subsequently needed, it will be available for fast access in the cache memory.
Again referring to
FIG. 1
, once data is accessed from the cache, the data is transferred to a switch
16
. At the switch, the data is delivered to the processor. Typical processors are able to process 16, 32, or 64 bits of information per clock cycle.
Information stored in the cache is usually packaged in groups of bytes that are integer multiples of the processor bandwidth and the cache line capacity. However, some processors allow variable length information packages to be processed. In the case of variable length information packages, the information, either data or instructions, may not be an integer multiple of the cache line capacity. As a result, one instruction that is comprised of multiple bytes may begin on one cache line and end on the next sequential cache line. This is referred to as data that crosses a cache line.
In a typical architecture, only one cache line can be accessed per clock cycle. If one instruction crosses a cache line, then the processor must access the cache two times to obtain both cache lines. Consequently, the processor requires two clock cycles to access the complete instruction which is located on two distinct cache lines. The additional clock cycle slows the overall operation of the computer system.
What is needed is a system and method for accessing instructions that cross a cache line without requiring an extra clock cycle.
SUMMARY OF THE INVENTION
The present invention allows for accessing information that crosses cache lines without requiring an additional clock cycle. The invention involves splitting a cache memory into two cache memories. Each cache memory is comprised of a column of cache lines. Each cache column has an associated content addressable memory (CAM).
Information in the form of instructions and/or data is stored in the cache columns from a main memory in a sequential and alternating format. The two cache columns in the cache memory are designated as an even cache column and an odd cache column.
A typical cache column is made up of cache lines that have the capacity to store 32 bytes of information per line. In the preferred embodiment of the invention, information is stored in 32-byte increments in sequential alternating cache lines. That is, a first block of 32 bytes of data is stored in an even cache line and the next sequential block of 32 bytes of data is stored in a next sequential odd cache line. An address associated with both cache lines of information is stored in respective CAMs.
To initiate cache access, the fetch unit within the processor of a computer system makes an information request. The information may be computer instructions or database information. For purposes of the disclosure, the information is referred to as “instructions.” The program computer (PC) block of the fetch unit generates an instruction request using a predefined 32-bit address format that includes a line index number or tag.
In parallel with the generation of the initial instruction request, the fetch unit creates a second instruction request. The second instruction request is created by advancing the initial instruction request to the next sequential instruction address. The address advancement involves toggling an indicator bit or adding one address unit to the initial instruction tag. The second instruction request is also directed to the column opposite the column that the initial instruction request identified. Therefore, if the initial instruction request identifies a cache line in the even cache column, then the second instruction request will identify the next sequential cache line in the odd cache column.
Once the fetch unit has established two instruction requests, the fetch unit simultaneously accesses the CAMs of the even and odd cache columns according to the two instruction requests. If a cache hit is found in either cache column, the appropriate cache lines are delivered in parallel to a switch.
The switch receives the two cache lines containing the requested instructions and determines from the cache line address whether or not the requested instruction crosses a cache line. If the requested instruction is in the last double-word of the cache line, the requested instruction crosses the cache line and the switch identifies the requested instruction segments in both cache lines combining the segments into the desired instruction. Once the desired instruction has been combined from the two cache lines, the switch delivers the desired instruction to the processor.
By dividing cached information into two cache columns, two cache lines can be accessed simultaneously. As a result, instructions and/or data that cross cache lines can be accessed without requiring extra computer clock cycles. Because more data can be accessed in fewer clock cycles, the overall performance of the computer is enhanced.
REFERENCES:
patent: 5414824 (1995-05-01), Grochowski
patent: 5446850 (1995-08-01), Jeremiah et al.
patent: 5557768 (1996-09-01), Braceras et al.
patent: 5559986 (1996-09-01), Alpert et al.
patent: 5572700 (1996-11-01), Hays et al.
patent: 5574880 (1996-11-01), Shaw
patent: 5640526 (1997-06-01), Mahin et al.
patent: 5701430 (1997-12-01), Jeremiah et al.
patent: 5854761 (1998-12-01), Patel et al.
patent: 5854914 (1998-12-01), Bodas et al.
paten
Afsar Muhammad
Mattela Venkat
Gossage Glenn
Siemens Aktiengesellschaft
LandOfFree
System and method for arranging, accessing and distributing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for arranging, accessing and distributing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for arranging, accessing and distributing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2439073