Data processing: structural design – modeling – simulation – and em – Emulation – Of peripheral device
Reexamination Certificate
1998-05-21
2001-10-23
Frejd, Russel W. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Emulation
Of peripheral device
C710S004000, C711S006000, C711S203000
Reexamination Certificate
active
06308147
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This application relates in general to software data structures and in specific to a mechanism for synthesizing software data structures in hardware using memory transaction translation techniques.
BACKGROUND OF THE INVENTION
The basic concept of memory transaction translation is commonly used in modern computing systems. The translation process typically involves the replacement of a memory address, and is based on a masking and table lookup operation. For example, memory management software or hardware is often used to take an original virtual memory page address, and replace a portion of it with a value that results in a physical memory address. The replacement is based on a page table entry, as indexed by the virtual address. This is illustrated in FIG.
5
. Virtual memory translation is used to provide the illusion that more memory is accessible than actually exists. Virtual memory translation is also used to effect the various types of swapping techniques and caching algorithms. Bus converters or bus bridging circuits typically implement a restricted version of translation to allow address translation between the two busses that they connect.
FIG. 5
depicts a prior art translation mechanism
50
. A memory address is placed onto memory bus
51
by a processing element (not shown). Mechanism
50
would recognize that the address is a virtual address, which would have to be translated into a physical address which actually exists. The mechanism
50
may operate to replace a certain number of address bits with other address bits, or the entire address may be replaced with a different address, similar to content addressable memory. The address is captured by the address in buffer
52
from memory bus
51
. This address is used to reference a new address or a portion of a new address in page mapping table
53
. Table
53
may have one or more entries, which are indexed by the address. This address is also combined by and
55
with a mask
54
. This combination will mask off a portion of the address or possibly the entire address. The remaining portion, if any, if combined by or
56
with the new address portion from table
53
to form the new address. This new address is sent to address out buffer
57
, which will then place the new address onto memory bus
51
. The new address will associate a physical memory location (not shown) with the request from the processing element. Note that when the table
53
is used in a bridge, typically the table has one entry, and the address in
52
is then translated into some other address
57
for use in a different bus domain.
One problem with the prior art translation mechanism
50
is that the translation function is relatively static. The translation table
53
tends to remain unchanged for long periods of time, as the mapping schemes are complex and time consuming from a processor point of view. Thus, re-mapping of the tables
53
is relatively prohibitive. The tables are typically initialized at one point during operations and are changed infrequently if at all. For example, tables for bus bridges are initialized during power on or a system reset, and are not changed until a major reconfiguration event occurs. The table is re-mapped by interrupting the processing element, and blocking the bus and bridge. The processor then re-maps or updates the table. Thus, the processor will be operating on the table and not on other duties, and the bridge will not be managing the bus. Therefore, re-mapping the table requires an investment of a significant amount of processing resources, as well as lost bridge access time. The prior art address translation mechanism cannot serve in a dynamic environment.
For example, consider the operation of the prior art translation mechanism on FIFO or queue data structure. A FIFO, from a virtual memory address perspective, has either one or two addresses, where the read and write addresses may be the same or different. Writing to the FIFO address adds elements to the FIFO, while reading removes elements from the FIFO. Thus, each time an element is added to the FIFO, the next available physical address of the FIFO for a write is the current address plus one. Similarly, each time an element is removed from the FIFO, then next address for a read is the current address minus one. Thus, the actual physical address to be generated is dependent upon the state of the FIFO. After each operation or access to the FIFO, the hardware memory management unit (MMU) would need to interrupt the main processing element, so that its paging information could be updated, such that it would point to the next FIFO element. Thus, each access to the FIFO would require the processor to update the tables. This greatly reduces the efficiency of the processor, and makes each access to the FIFO very costly in terms of processor time.
Furthermore, note that the translation function only operates on the address phase of the transaction. Thus, the MMU would somehow need to recognize the existence of FIFO boundary conditions, i.e. full or empty. This also includes having a mechanism for informing an accessing device or processing element that their requested transaction cannot be completed until the boundary conditions are satisfied. Thus, prior art translation mechanism is insufficient to handle the dynamic translation required for the emulation of complex data structures.
Therefore, there is a need in the art for a mechanism which permits dynamic memory transaction translation such that complex data structures can be emulated or synthesized by software.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which uses a mechanism to synthesize complex software data structures in hardware with memory transaction translation techniques. The resultant emulated data structures provide versatile, performance enhancing programming resources.
The inventive mechanism performs enhanced memory transaction translation by using a finite state machine instead of a translation table, and manipulates the bus control primitives outside of the address phase, in order to manipulate memory control strobes and communicate to the memory bus and bridge. Note that the inventive mechanism is described in terms of emulating a FIFO structure, however, this structure is by way of example only, as other types of structures could be synthesized via the inventive mechanism, for example, queues FILOs, LIFOs, stacks, semaphores, link lists, scatter/gather structures, and other structures. Since the mechanism is dynamic instead of static in nature, then the state machine can include a specific algorithm that defines the dynamic behavior of the synthesized structure.
The operation of software data structures is synthesized or emulated in standard memory by altering the address. The inventive mechanism synthesizes the operation via dynamic memory translation which modifies the address of the original transaction based on a algorithm. When a transaction references the virtual structure, the inventive mechanism processes the address of the request into a new address based upon the state of the virtual structure. A finite state machine is used by the inventive mechanism to track the current state of the structure and calculate the new state or address. The mechanism then sends out the new address, which is processed by the memory device. Note that the prior art would always supply the same address, however the inventive mechanism will provide an address based upon the current state of the virtual structure.
For example, the virtual structure is a virtual FIFO. Thus, memory requests to the FIFO will only reference the FIFO and not to a particular location in the FIFO. The inventive mechanism would track the current status of the FIFO and route read/write requests to the appropriate locations within the FIFO. Note that the inventive mechanism operates without using processor resources.
The inventive mechanism can also manipulate the read and write aspects of transactions, in addition
Frejd Russel W.
Hewlett--Packard Company
LandOfFree
Data structure synthesis in hardware using memory... 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 structure synthesis in hardware using memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure synthesis in hardware using memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598443