Patent Description:
Memory address translation from virtual address to physical address is a process that allows a computer system to access data stored in memory. A virtual address is an abstract representation of a memory location that is independent of the actual physical address. A physical address is the actual location of a memory cell in the hardware. To translate a virtual address to a physical address, the system uses a data structure called a page table, which maps each virtual page (a fixed-size memory block) to a physical frame (a corresponding memory block in the hardware). The page table also contains information about the status and protection of each page, such as whether it is valid, present, read-only, or writable. The system divides the virtual address into two parts: a page number and an offset. The page number is used to index the page table and find the corresponding physical frame number. The offset is added to the physical frame number to obtain the final physical address. The system then accesses the data stored at that physical address.

A translation lookaside buffer (TLB) is for translating the virtual address to physical address according to the page table. The TLB usually contain a specialized cache that stores the mappings between virtual addresses and physical addresses. It is used to speed up the translation process and avoid accessing the page table for every memory access. A TLB entry includes of a tag, which is the virtual address or a part of it, and a piece of data, which is the corresponding physical address or a part of it. The TLB is usually implemented as an associative memory, which allows fast parallel lookup of multiple entries. However, this also means that the TLB has a limited size and may suffer from conflicts and misses. When a TLB miss occurs, the MMU has to consult the page table and update the TLB with the new entry. This can cause significant performance degradation if the page table is not cached or if it is too large to fit in the cache. TLB management is an important aspect of memory system design.

Table walk is usually defined as the process of walking through page tables to find the physical address corresponding to the virtual address. The table walk process starts with the virtual address. The first step is to look up the virtual address in the page table. The page table is a data structure that maps virtual addresses to physical addresses. If the page table is found according to virtual address, the page table is returned. If the page table is not found according to virtual address, a page fault occurs. A page fault is an error that occurs when the processor tries to access a memory location that is not in the page table. When a page fault occurs, usually the operating system takes over and loads the page into memory. The operating system then updates the page table to include the new physical address. The processor then retries the memory access. The table walk process can be a relatively slow process, especially if the virtual address is not found in the page table. To improve performance, many computer systems use a technique called caching. Caching involves storing recently used page table entries in a cache memory. If the virtual address is found in the cache, the physical address can be returned without having to look up the page table.

A memory transaction merge is a process of combining two or more memory transactions into a single transaction. This can be done to improve memory efficiency, reduce memory usage, or to ensure that all changes made to a data set are committed or rolled back together. However, some of the drawbacks of using memory transaction merge include complexity and computing overhead (excess or indirect computation time and memory), especially for large transactions.

Memory address translation and merge cause latency that can affect the performance of applications accessing memory frequently, such as databases, operating systems, and virtual machines. There are several techniques to reduce latency, such as caching, prefetching, and parallelism. However, these techniques also have trade-offs, such as increased power consumption, complexity, and hardware cost. It is important to design and optimize memory address translation schemes that balance the benefits and drawbacks of different approaches.

<CIT> discloses an apparatus and method performing neighborhood-aware virtual to physical address translations.

<NPL>" discloses compression mechanisms for address translations to improve GPU TLB hit rates.

<NPL>" discloses foundation for designing memory management units (MMUs) for GPUs in CPU/GPU systems.

<CIT> discloses a system and method for forwarding cache misses to another level of the cache hierarchy.

A memory transaction merge is a process of combining two or more memory transactions into a single transaction. This can be done to improve performance and reduce memory usage. In a real-time application, memory transaction merge can reduce memory access to different frames by combining multiple transactions with the same page (or frame) into a single memory transaction Address translation is the process of converting a virtual address into a physical address. The virtual address is the address that is used by a program to access memory, while the physical address is the actual address of the memory location in the computer's memory. When a program accesses memory, it generates a virtual address. The virtual address is translated into a physical address by the memory management unit (MMU) using a page table. The page table is stored in memory and is used to translate virtual addresses into physical addresses. The MMU uses the page tables to translate the virtual address into a physical address by performing a hardware called translation lookaside buffer (TLB). TLB can carry out the process of walking through the page tables to find the physical address corresponding to the virtual address. The page table is organized in a tree-like structure with multiple levels. Each level of the page table contains page table entries (PTEs) that map virtual addresses to physical addresses. A table walk involves accessing multiple levels of tables, each containing entries that point to the next level or to the final physical address. The number and size of the tables depend on the architecture and configuration of the MMU. A table walk can be costly in terms of time and energy, so it is desirable to minimize the frequency and duration of table walks by using efficient caching and prefetching techniques.

The above-mentioned two processes, i.e., memory transaction merge and address translation in MMU, can be done simultaneously to enhance efficiency in memory processing. The system and method of such memory processing with enhanced efficiency are described in this disclosure.

<FIG> illustrates a memory processing system <NUM> of an embodiment. The memory processing system <NUM> includes a processor <NUM>, a main memory <NUM>, and a memory management unit (MMU) <NUM> coupled to the processor <NUM> and the main memory <NUM>. The processor <NUM> is used to generate a plurality of virtual addresses. Each virtual address of the plurality of virtual addresses includes a base address an offset. The main memory <NUM> includes data corresponding to physical addresses in a main page table <NUM> that stores physical addresses. Each physical address of the plurality of physical addresses includes a base address and an offset. The main page table <NUM> is used to map the plurality of virtual addresses to the plurality of physical addresses. The memory management unit <NUM> includes a translation lookaside buffer (TLB) <NUM> coupled to the processor <NUM> and the main memory <NUM>, a table walk unit <NUM> coupled to the TLB <NUM> and the main memory <NUM>, and a merger <NUM> coupled to the TLB <NUM> and the processor <NUM>. The TLB <NUM> is used to store a first page table mapping a first set of base addresses of virtual addresses to a first set of base addresses of physical addresses and to perform address translation. The table walk unit <NUM> is used to access a main page table <NUM> in the main memory <NUM>, and to store a second page table mapping a second set of base addresses of virtual addresses to a second set of base addresses. The merger <NUM> is used to merge memory transactions. The TLB <NUM> performs address translation by retrieving a physical address according to a virtual address in the first page table in the TLB <NUM>, the second page table in the table walk unit <NUM> or the main page table <NUM> in the main memory <NUM>.

It should be noted that the term memory transaction in the context of this disclosure means read-write operations of data to memory locations. A read transaction occurs when the processor <NUM> requests data from the main memory <NUM>, and a write transaction occurs when the processor <NUM> sends data to the main memory <NUM>.

Preferably, there may be multiple page tables stored in the MMU <NUM> or the main memory <NUM>, and the TLB <NUM> may access each one of these page tables. A person having ordinary skill in the art can easily modify the embodiment according to this disclosure.

The processor <NUM> can be any type of general purpose processor or application specific processor, including but not limited to digital signal processor (DSP), graphics processing unit (GPU), application-specific integrated circuit (ASIC), and field-programmable gate array (FPGA) and central processing unit (CPU). The main memory <NUM> can include any type of data-storing device, such as random access memory (RAM), flash memory, and hard-drive. The table walk unit <NUM> can be implemented by caches for storing page table entries.

A virtual address is a logical address used by a process or thread in an operating system (OS) to access the main memory <NUM>. Virtual addresses are not the same as physical addresses, but rather they are translated by the TLB <NUM> into physical addresses before being used to access the main memory <NUM>. A virtual address has of two parts: a base address (or page number) and an offset. The base address, also called page number, is an index into the main page table <NUM>. The main page table <NUM> is a data structure that maps virtual addresses to physical addresses. The offset is the byte offset within the page. The offset is used to access the specific byte of data within the page.

On the other hand, a physical address is a unique address that identifies a specific location in a physical memory. Physical addresses are used by the hardware to access physical memory directly. Physical addresses are typically represented as a sequence of binary digits, or bits. The number of bits used to represent a physical address depends on the size of the computer's memory. For example, a computer with 4GB of memory would use <NUM> bits to represent each physical address. Physical addresses are also divided into two parts: a base address (or frame number) and an offset. The base address, also called frame number, identifies the specific frame of memory that contains the data. The offset identifies the specific byte of data within the frame. For example, a <NUM>-bit physical address may have <NUM> bits for the frame number and <NUM> bits for the offset.

To convert a virtual address to a physical address, address translation is required because virtual addresses are typically larger in size than physical addresses. This is because virtual addresses can be used to access memory that is not currently in physical memory.

The TLB <NUM> is a memory cache that stores recently used translations of virtual addresses to physical addresses. It can be used to reduce the time taken to access a user memory location. It can be part of memory-management unit (MMU) <NUM>. The TLB <NUM> may reside between the processor <NUM> and the main memory <NUM>. Preferably, it may reside between the different levels of a multi-level cache.

Preferably, the TLB <NUM> can be a piece of hardware for translating a virtual address to a physical address by using page tables stored in the MMU <NUM> or the main memory <NUM>. Preferably, it can be implemented as a fast lookup hardware cache with data processing capability. The TLB <NUM> can include a fixed number of slots of page table entries. The page table entries map virtual addresses to physical addresses. Each entry in the TLB <NUM> has of two parts: a page number and a frame number. If the page number of the incoming virtual address matches the page number in the TLB <NUM>, the corresponding frame number is returned. Then, the frame number with offset is the physical address stored in the main page table <NUM>. Since the TLB lookup is usually a part of the instruction pipeline, searches are fast and cause essentially no performance penalty. However, in order to be able to search within the instruction pipeline, the TLB <NUM> usually has to be small in size.

When there is a TLB miss, meaning that the requested address is not cached in the TLB <NUM>, the table walk unit <NUM> begins to look up the virtual address in the page table entries in the table walk unit <NUM>. If the virtual address is found, a page table is returned. If the virtual address is not found in the table walk unit <NUM>, then the table walk unit <NUM> would access the main page table <NUM> in the main memory <NUM>. The main page table <NUM> in the main memory <NUM> is a larger, slower memory that stores all of the translations for a process's virtual address space. Accessing the main page table <NUM> in the main memory <NUM> generally takes a lot more time than accessing the TLB <NUM> and the table walk unit <NUM>.

While the above-described address translation is being performed, the memory transaction merge is also performed by the merger <NUM> at substantially the same time (i.e., the same clock cycles) by implementing specific instructions. By perform memory transaction merge and table walk process in parallel (i.e., at substantially the same clock cycles), the two processes can hid each other's latency, thus improving the overall performance.

<FIG> illustrates memory transaction merge performed by the merger <NUM>. Memory transaction merge is a process of combining two or more memory transactions into a single transaction. In the invention, multiple memory transactions having the same base address and consecutive offsets within a merge window are merged into a single memory transaction. The merger <NUM> is a piece of hardware implemented to perform such task.

In an example, within merge window one, three separate memory transactions (i.e., address <NUM>, address <NUM> and address <NUM>) have an identical base address (i.e., the same page number) and consecutive offsets, the merger <NUM> can merge these three memory transactions (i.e., address <NUM>, address <NUM> and address <NUM>) into a single memory transaction with consecutive offsets.

In another example, within merge window two, two separate memory transactions (i.e., address <NUM> and address <NUM>) have an identical base address (i.e., the same page number) and consecutive offsets, the merger <NUM> can merge these two memory transactions (i.e., address <NUM> and address <NUM>) into a single memory transaction with consecutive offsets.

Preferably, the merge window for write access is greater that or equal to <NUM> clock cycles. Preferably, the merge window for read access is greater than or equal to <NUM> clock cycles.

Furthermore, the merger <NUM> can discard a memory transaction if a data corruption occurs in the main memory <NUM> or an error occurs in the MMU <NUM> related to the memory transaction. Some examples of data corruptions include bit flip, memory leaks, buffer overflows, etc. Some examples of errors occurring in the MMU <NUM> include invalid page, page table corruption, TLB shutdown, etc..

In more detail, a bit flip happens when a single bit of data changes from <NUM> to <NUM> or vice versa, due to electromagnetic interference, or faulty hardware. Bit flips can cause data to become unreadable, invalid, or inconsistent. On the other hand, a memory leak happens when a program fails to release the memory it has allocated after it is no longer needed, causing the memory to be wasted and unavailable for other programs. Memory leaks can degrade the performance of the system and eventually lead to crashes or hangs. Moreover, a buffer overflow happens when a program writes more data to a memory location than it can hold, causing the excess data to overwrite adjacent memory locations. Buffer overflows can corrupt data, cause unexpected behavior, or allow attackers to execute malicious code.

In some circumstances, invalid page happens when a process tries to access a virtual address that is not mapped to any physical address or that is not allowed by the access permissions. In other circumstances, page table corruption happens when the page table is corrupted by a hardware failure, a software bug, or a malicious attack. Moreover, TLB shutdown happens when multiple processors share the same physical memory and have different TLBs; when one processor updates a page table entry, it has to invalidate the corresponding TLB entries on other processors, which may cause synchronization overhead. The above illustrations are merely example. There may be various methods of memory transaction merge with certain modifications and alterations and the invention is not limited thereto. Combining multiple memory transactions into a single transaction can reduce the frequency of accessing different frames in the main memory <NUM>, thus enhancing efficiency.

<FIG> is a flowchart of a memory processing method <NUM> of an embodiment implemented by the memory processing system <NUM>. The memory processing method <NUM> includes the following steps:.

The memory processing method <NUM> summarizes the description in the above paragraphs. Thus, the details are not repeated herein.

During the processing time of the MMU <NUM>, the merger <NUM> performs transaction merge simultaneously. That is, step S304 is performed in parallel with steps S306-S312. The address translation, and the memory transaction merge can hide each other's latency, therefore improving the overall memory processing efficiency.

<FIG> is a flowchart of a memory processing method <NUM> of another embodiment implemented by the memory processing system <NUM>. The memory processing method <NUM> includes the following steps:.

The memory processing method <NUM> summarizes the description in the above paragraphs. The details are not repeated herein.

In step S412, the data is access after the TLB <NUM>, table walk unit <NUM> and merger <NUM> all finished the current transaction process. Also, the set of physical addresses can include one or more physical addresses.

Step S404 is performed in parallel with steps S406-S412. Thus, the address translation and the memory transaction merge can hide each other's latency, therefore improving the overall memory processing efficiency.

The memory processing method and system described above may be implemented by one or more computers. In further detail, software and hardware hybrid implementations of some of the embodiments disclosed may be implemented on a programmable network resident device (which should be understood to include intermittently connected network-aware device) selectively activated or reconfigured by a computer program stored in memory. Such network devices may have multiple network interfaces that may be configured or designed to utilize different types of network communication protocols. A general architecture for some of these devices may be disclosed herein in order to illustrate one or more examples by which a given unit of functionality may be implemented. Preferably, at least some of the features or functionalities disclosed herein may be implemented on one or more general-purpose computers associated with one or more networks, such as an end-user computer system, a client computer, a network server or other server system, a mobile computing device (e.g., tablet computing device, mobile phone, smartphone, laptop, and the like), a consumer electronic device or any other suitable electronic device, or any combination thereof. Preferably, at least some of the features or functionalities of the various embodiments disclosed may be implemented in one or more virtualized computing environments (e.g., network computing clouds, virtual machines hosted on one or more physical computing machines, or the like).

Preferably, the computing instructions may be carried out by an operating system, for example, Microsoft Windows™, Apple Mac OS/X or iOS operating systems, some variety of the Linux operating system, Google Android™ operating system, or the like.

Preferably, the computers may be on a distributed computing network, such as one having any number of clients and/or servers. Each client may run software for implementing client-side portions of the embodiments. In addition, any number of servers may be provided for handling requests received from one or more clients. Clients and servers may communicate with one another via one or more electronic networks, which may be in various embodiments such as the Internet, a wide area network, a mobile telephone network, a wireless network (e.g., Wi-Fi, <NUM>, and so forth), or a local area network. Networks may be implemented using any known network protocols.

Reference has been made in detail to implementations, examples of which are illustrated in the accompanying drawings. In the detailed description above, numerous specific details have been set forth in order to provide a thorough understanding of the various described implementations. However, it will be apparent to one of ordinary skill in the art that the various described implementations may be practiced without these specific details. In other instances, well-known methods, procedures, components, circuits, and networks have not been described in detail so as not to unnecessarily obscure aspects of the implementations.

The terminology used in the description of the various described implementations herein is for the purpose of describing particular implementations only and is not intended to be limiting. As used in the description of the various described implementations and the appended claims, the singular forms "a", "an" and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms "includes," "including," "comprises," and/or "comprising," when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

For situations in which the systems discussed above collect information about users, the users may be provided with an opportunity to opt in/out of programs or features that may collect personal information (e.g., information about a user's preferences or usage of a smart device). In addition, in some implementations, certain data may be anonymized in one or more ways before it is stored or used, so that personally identifiable information is removed. For example, a user's identity may be anonymized so that the personally identifiable information cannot be determined for or associated with the user, and so that user preferences or user interactions are generalized (for example, generalized based on user demographics) rather than associated with a particular user.

Additionally, such computer-readable media may be downloaded as a computer program product, wherein the program may be transferred from a remote computer (e.g., a server) to a requesting computer (e.g., a client) by way of data signals provided in a carrier wave or other propagation medium via a communication link (e.g., a bus, a modem, or a network connection).

Reference in the specification to "one embodiment" or "an embodiment" means that a particular feature, structure, and/or characteristic described in connection with the embodiment may be included in at least an implementation. The appearances of the phrase "in one embodiment" in various places in the specification may or may not be all referring to the same embodiment.

Claim 1:
A memory processing system (<NUM>) comprising:
a processor (<NUM>) configured to generate a plurality of virtual addresses, each virtual address of the plurality of virtual addresses comprising a base address and an offset;
a main memory (<NUM>) comprising:
a plurality of data corresponding to a plurality of physical addresses, each physical address of the plurality of physical addresses comprising a base address and an offset; and
a main page table (<NUM>) configured to map the plurality of virtual addresses to the plurality of physical addresses;
a memory management unit (<NUM>), in the following also referred to as MMU, coupled to the processor (<NUM>) and the main memory (<NUM>), comprising:
a translation lookaside buffer (<NUM>), in the following also referred to as TLB, coupled to the processor (<NUM>) and the main memory (<NUM>), configured to store a first page table mapping a first set of base addresses of virtual addresses to a first set of base addresses of physical addresses, and to perform address translation;
a table walk unit (<NUM>) coupled to the TLB (<NUM>) and the main memory (<NUM>), configured to access the plurality of physical addresses in the main memory (<NUM>), and to store a second page table mapping a second set of base addresses of virtual addresses to a second set of base addresses of physical addresses;
a merger (<NUM>) coupled to the TLB (<NUM>) and the processor (<NUM>), configured to merge memory transactions;
wherein the TLB (<NUM>) performs address translation by retrieving a physical address according to a virtual address from the first page table in the TLB (<NUM>), the second page table in the table walk unit (<NUM>) or the main page table (<NUM>) in the main memory (<NUM>); and
the merger (<NUM>) merges the memory transactions and the TLB (<NUM>) performs address translation in same clock cycles;
the merger (<NUM>) merges a plurality of memory transactions
having consecutive offsets with an identical base address within a merge window into a single memory transaction;
characterized in that if the merge window is for write access, the merge window is greater than or equal to <NUM> clock cycles; and
if the merge window is for read access, the merge window is greater than or equal to <NUM> clock cycles.