Electrical computers and digital processing systems: processing – Processing architecture – Data driven or demand driven processor
Reexamination Certificate
2001-02-28
2003-07-22
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing architecture
Data driven or demand driven processor
C712S233000, C711S128000, C711S207000, C711S205000
Reexamination Certificate
active
06598147
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a data processing apparatus and a data processing method, and more particularly, to data processing by a semiconductor intergrated circuit, above all, to data processing employing associative memory.
BACKGROUND ART
In recent years, along with provision of multi-function and higher function of household electrical goods or the like, adaptation of computer technology to household products is rapidly advanced, whereby a virtual storage control unit which was conventionally employed for mainly high-grade workstations, personal computers, or the like is being adopted to operation systems (OS), which cope with the processing of a plurality of task processing also in household equipment such as a Set-Top Box, as an apparatus for connecting CATV or Internet to a television receiver.
The virtual storage control unit is technology employed for effectively utilizing a high speed semiconductor memory that is used as a main memory in a computer, and the virtual storage control unit employs an external storage device such as a hard disk that has generally low speed but has a large capacity as a substitute for a memory. By the use of the virtual storage control unit, even when a capacity of actually installed main memory is small, it is possible to drive software which requires a large capacity memory for its execution, or to deal with a large quantity of data speedily.
In order to realize this, when it comes to a state where there is no empty region in the main memory, a part of the content stored in the main memory is written into the external storage device, and it is read out therefrom when it is needed. In the virtual storage control unit, a logical address space which is larger than physical memory capacity is to be realized. The logical address space is called as a logical space while the physical memory space is called as a physical space. Since the position of the logical space is specified by a logical address and the position on the physical space is specified by a physical address, it is required in a data processing apparatus to provide a mechanism for performing translation between the logical address and the physical address so as to perform virtual storage management.
Generally, while in a computer system a plurality of tasks (a task is a unit of a work which a computer performs) are performed it reduces the processing speed to perform writing/reading of all the content concerning a task stored in a main memory every time the task is changed. Accordingly, a logical task space is divided into pages in unit, and mapping, i.e., making correspondence between a logical space and a physical space is carried out in unit of page, thereby enhancing the efficiency.
In the address translation processing, a search is performed with providing a translation table (page table) showing the correspondence relation in the external memory (main memory device or the like) and the OS referring to the translation table when it is needed. However, because a processing load for such processing is large, there are many cases where the processing speed of the data processing apparatus is decreased due to employing the virtual storage control unit. Accordingly, an address translation buffer (Translation Look-aside Buffer; hereinafter recited “TLB”) which stores pairs of logical address and physical address in frequent use in a high speed memory, i.e., which cashes the same is employed, in order to realize a high speed address translation processing. The TLB may be often constituted as an associative storage device in which when an item is input as a key item an associative item in an associative relation therewith is obtained.
Generally, a cash memory comprises a data area for keeping data itself and a tag area for holding an address indicating a data storage position, or an access history, and the like. Either of the areas is managed divided into a plurality of blocks. The block constituting the data area is called as a line, and inputting/outputting of data in the cash memory is performed in line unit.
As a method for making correspondence between the data on the main memory such as the translation table with the line of the cash memory, there are a set-associative method, a direct-mapping method, and a full-associative method. The set-associative method is a method in which the cash memory and the main memory are divided into plural sets (a set is a collection of lines), and the data on the main memory can only be stored in the prescribed line in each set. When the number of sets is n, it is called n-way-set-associative method. The direct-mapping method corresponds to 1-way-set-associative method wherein the whole cash memory is dealt as one set. On the other hand, a method in which data is stored in an arbitrary line is a full-associative method.
With respect to these methods, considering the rate of making a hit with the cash, the direct-mapping method which has a strong possibility that a replacement occurs has many error hits and the low hit rate, while the full-associative method has the high hit rate by comparison. Besides, in the set-associative method, the hit rate is between those of the both methods. Generally, for the management of the cash memory the set-associative method is employed; however, in case of TLB, the adoption of the full-associative method which has the high hit rate is preferable as an adverse effect on the lowering of the processing efficiency due to the error hits is enormous.
As described above, at the time of changing tasks, content of the cash memory including the TLB is updated. Hereinafter, a TLB managing method at the time of the updating according to a prior art disclosed in Japanese Published Patent Application No. Hei. 8-320829 will be described. At the updating, the nullification processing of a TLB entry is required. In the prior art, at the nullification processing of an entry concerning the specified page, a search is performed specifying a way of the TLB that was IO-mapped employing MOV instruction.
In the nullification processing of the specified entry according to the prior art, provided that a mapping address of each way of the TLB is 0xfn000000 (n=0−7), and logical page number is 0xbeef0, the processing can be realized with the following program.
1) MOV “0xbeef0000” R
0
2) MOV “0xf0000080” R
1
3) MOV “0x01000000” R
2
4) MOV R
0
, (R
1
)
5) ADD R
2
, R
1
At 1), the logical page number to search (0xbeef0) and valid flag (0=invalid) are set to R
0
, and at 2), a mapping address (0xf0) and a flag (0x80) for making a comparison are set to R
1
, then at 3), an offset of the mapping address of each way (0x01000000) is set to R
2
. At 4), writing of the content of R
0
(0xbeef0000) to the address indicated by R
1
(0xf0000080) is performed, and in case where the result of the comparison of the logical page number matches, the content of R
0
(0xbeef0000) is written into the that way of the TLB, while in case of making no hit, writing is not performed. At 5), the offset is added to the mapping address, thereby to create a mapping address of the next way, and the processing returns to 4), and such processing is repeated as many times as the number of the ways of the TLB.
As described above, in the TLB management according to the prior art, the content of TLB entry is searched for each way. Accordingly, the number of steps until the nullification processing is completed depends on the number of ways, that is, in case where the number of way is 1, the above-described 5 steps, 1)-5), are required, and in case where the number of way is n, 2n+2 steps are required. In the above-mentioned Japanese Published Patent Application No. Hei. 8-320829, the case of set-associative method of 2 ways or 4 ways is disclosed. In such a case where the number of ways is not very high, there is no problem in the aspect of the processing efficiency or the like; however, as the number of ways becomes high, the number of required steps is increased, whereby the time required for the processing is also increased. As
Pan Daniel H.
Wenderoth , Lind & Ponack, L.L.P.
LandOfFree
Data processing device and method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing device and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing device and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3063887