Patent ID: 12248406

DETAILED DESCRIPTION

The following disclosure provides various different embodiments or examples for implementing different features of the present disclosure. Specific examples of components and arrangements are described below to simplify the present disclosure. These are, of course, merely examples and are not intended to be limiting. For example, the formation of a first feature over or on a second feature in the description that follows may include embodiments in which the first and second features are formed in direct contact and may also include embodiments in which additional features may be formed between the first and second features, such that the first and second features may not be in direct contact. In addition, the present disclosure may repeat reference numerals and/or letters in the various embodiments. This repetition is for the purpose of simplicity and clarity and does not in itself dictate a relationship between the various embodiments and/or configurations discussed.

Notwithstanding that the numerical ranges and parameters setting forth the broad scope of the invention are approximations, the numerical values set forth in the specific examples are reported as precisely as possible. Any numerical value, however, inherently contains certain errors necessarily resulting from the standard deviation found in the respective testing measurements. Also, as used herein, the term “about” generally means within 10%, 5%, 1%, or 0.5% of a given value or range. Alternatively, the term “generally” means within an acceptable standard error of the mean when considered by one of ordinary skill in the art. As could be appreciated, other than in the operating/working examples, or unless otherwise expressly specified, all of the numerical ranges, amounts, values, and percentages (such as those for quantities of materials, duration of times, temperatures, operating conditions, portions of amounts, and the likes) disclosed herein should be understood as modified in all instances by the term “generally.” Accordingly, unless indicated to the contrary, the numerical parameters set forth in the present disclosure and attached claims are approximations that can vary as desired. At the very least, each numerical parameter should at least be construed in light of the number of reported significant digits and by applying ordinary rounding techniques. Here, ranges can be expressed herein as from one endpoint to another endpoint or between two endpoints. All ranges disclosed herein are inclusive of the endpoints, unless specified otherwise.

FIG.1is a schematic diagram illustrating a computing system according to one embodiment of the present application. As shown inFIG.1, a computing system100can include a memory110, a master computing device120and a slave computing device130. In the present embodiment, the master computing device120can be, for example, a central processing unit (CPU) in the computing system100, whereas the slave computing device130can be, for example, a graphic processing unit (GPU) in the computing system100. Moreover, the master computing device120and the slave computing device130can use a shared virtual memory, that is, the master computing device120and the slave computing device130may share a same virtual-physical translation mechanism for accessing the memory110.

The master computing device120can include a memory controller122, at least one processing unit124and an input-output memory management unit (IOMMU)126. The memory controller122can perform a read operation and a write operation on the memory110, whereas the processing unit124can access the data and/or instruction stored in the memory110via the memory controller122to execute a program. Moreover, the slave computing device130can include a plurality of computing units1321to132X and a translation lookaside buffer (TLB)134, wherein X is an integer greater than 1. Each of the computing units1321to132X can be configured to perform multiple computations in parallel in a single instruction multiple data manner, and when a computing unit accesses a specific virtual address, for example, when the computing unit1321needs to access the data in the virtual address VADD1, the computing unit1321can use the translation lookaside buffer134to lookup a plurality of virtual address entries TVA1_A to TVAN_A stored therein so as to obtain a physical address corresponding to the virtual address VADD1, wherein N is an integer greater than 1. As such, the slave computing device130can use the physical address corresponding to the virtual address VADD1to access the data in the memory110.

However, if the translation lookaside buffer134does not store any entry that includes the virtual address VADD1, then the translation lookaside buffer134may further send a translation request TREQ1to the input-output memory management unit126in the master computing device120. When the input-output memory management unit126receives the translation request TREQ issued from the translation lookaside buffer134of the slave computing device130, the input-output memory management unit126can first check if any entry in the translation lookaside buffer1261stored therein has included the virtual address VADD1so as to obtain the physical address corresponding to the virtual address VADD1. If the translation lookaside buffer1261does not store any virtual address entry including the virtual address VADD1, the input-output memory management unit126can then traverse a plurality of the page tables PT1to PTM in the memory controller122to obtain the physical address PADD1corresponding to the virtual address VADD1, and then store the information of the virtual address VADD1and its physical address PADD1in the translation lookaside buffer1261, wherein M is an integer greater than 1.

Since the computing units1321to132X must obtain multiple entries of data in advance when performing computations in the single instruction multiple data manner, the computing units1321to132X may send out inquires for a plurality of virtual addresses to the translation lookaside buffer134within at once, which may result in a plurality of translation requests being received by the input-output memory management unit126in a short period of time. Moreover, according to way that the single instruction multiple data is executed, the computing units1321to132X must obtain all the required data before the parallel computations of multiple entries of data begin. In such case, if certain computing units send out more translation requests, it may cause the input-output memory management unit126to be occupied for a long time, so that other computing units that only send out a few translation requests need to wait for a long time to obtain the translation service of the memory management unit126, thereby reducing the overall computing performance.

In the present embodiment, the memory management unit126can eliminate the virtual address entry in the translation lookaside buffer1261according to a short job first (SJF) mechanism, so that the computing unit sending out fewer translation requests can be served first. Consequently, the overall waiting time for address translation of the computing units1321to132X can be reduced, thereby increasing the performance of the computing system100.

FIG.2is a schematic diagram illustrating a computing system method according to one embodiment of the present application. In the present embodiment, the computing system method M1can include Steps S210to S290, and the computing system method M1can be applied to the computing system100.

In Step S210, when a computing unit in the slave computing device130accesses a specific virtual address, for example, when the computing unit1321needs to access the virtual address VADD1, the computing unit1321can look for the physical address PADD1corresponding to the virtual address VADD1in the translation lookaside buffer134. In some embodiments, the slave computing device130can further include X translation lookaside buffers, so that each of the computing units1321to132X can have its own translation lookaside buffer. In such case, each of the computing units1321to132X can perform the lookup in its own translation lookaside buffer, and then perform the lookup in the translation lookaside buffer134shared by the computing units1321to132X after finding no physical address PADD1of the virtual address VADD1in its own translation lookaside buffer; however, the present application is not limited thereto.

In Step S220, if the translation lookaside buffer134has a virtual address entry including the virtual address VADD1, then next in Step S230, the translation lookaside buffer134can provide the physical address PADD1corresponding to the virtual address VADD1according to the content of the virtual address entry, so that the data in the memory can be accessed accordingly.

However, in Step S220, if the translation lookaside buffer134does not have any virtual address entry including the virtual address VADD1, then next in Step S240, the translation lookaside buffer134would send a translation request TREQ1to the input-output memory management unit126to obtain the physical address PADD1corresponding to the virtual address VADD1.

When the input-output memory management unit126receives the translation request TREQ1, it can perform Step250to check if the translation lookaside buffer1261has a virtual address entry including the virtual address VADD1stored therein. If the translation lookaside buffer1261already has a virtual address entry including the virtual address VADD1, then next in Step S260, the translation lookaside buffer1261can provide the physical address PADD1corresponding to the virtual address VADD1according to the content of the virtual address entry, so that the data in the memory can be accessed accordingly.

However, in Step S250, if the translation lookaside buffer1261does not have a virtual address entry including the virtual address VADD1, then next in Step S270, a plurality of the page tables PT1to PTM stored in the memory controller122in the master computing device120would be traversed, thereby retrieving the physical address PADD1corresponding to the virtual address VADD1. In the present embodiment, the input-output memory management unit126can further include a translation request cache1262and a page table walker1263. The Translation request cache1262can store a plurality of translation requests sent from the translation lookaside buffer134, whereas the page table walker1263, while being idle, can select at least one translation request from a plurality of translation requests stored in the translation request cache1262, and traverse the page tables PT1to PTM of the memory controller122to retrieve at least one physical address corresponding to at least one virtual address in the at least one translation request. That is, in the present embodiment, the input-output memory management unit126can use the translation request cache1262and the page table walker1263to perform Step S270; however, the present application is not limited thereto.

In the present embodiment, as shown inFIG.1, the input-output memory management unit126has already stored a plurality of virtual address entries TVA1_B to TVAP_B in the translation lookaside buffer1261due to previous operations, wherein P is an integer greater than 1. In such case, if storage of the translation lookaside buffer1261is full, then one virtual address entry of the virtual address entries TVA1_B to TVAP_B should be cleared, so as to store the virtual address VADD1and the physical address PADD1newly obtained in Step S270. In the present embodiment, in order to preferentially satisfy computing units that send out fewer translation requests first, in Step S280, the translation lookaside buffer1261can select the virtual address entry that should be eliminated first from the virtual address entries TVA1_B to TVAP_B according to a recent use time and a dependent workload of each virtual address entry in the virtual address entries TVA1_B to TVAP_B, and in Step S290, clear the virtual address entry that should be eliminated so as to create a virtual address entry for the virtual address VADD1, and store the physical address PADD1in virtual address entry of the virtual address VADD1.

FIG.3is a schematic diagram illustrating the virtual address entries TVA1_B to TVAP_B in the translation lookaside buffer1261according to one embodiment. As shown inFIG.3, using the virtual address entry TVA1_B as an example, the virtual address entry TVA1_B can include four columns COL1to COL4for storing a virtual address VADD0, a physical address PADD0corresponding to the virtual address VADD0, a recent use time RUT0of the virtual address entry TVA1_B and a dependent workload DWA0of the virtual address entry TVA1_B respectively. In some embodiments, the translation lookaside buffer3261can include a timer, configured to calculate the time since the virtual address entries TVA1_B to TVAP_B were last used. Moreover, for ease of management, in some embodiments, the virtual address entries TVA1_B to TVAP_B may be arranged according to the recent use time, for example, from the virtual address entry with the longest recent use time to the virtual address entry with the shortest recent use time. In such case, each time when a virtual address entry is selected, the recent used time of said virtual address entry would be reset to zero and moved to a position designated for the virtual address entry with the shortest recent used tome; however, the present application is not limited thereto.

In the present embodiment, each virtual address entry TVA1_B to TVAP_B is created after traversing the page table PT1to PTM because of the translation requests sent by a specific computing unit for execution of a specific instruction, and the dependent workload in each virtual address entry is the number of translation requests sent by the same computing unit for the same instruction. For example, if the computing unit1321sends translation requests for five virtual addresses (including the virtual address VADD0) during the execution of a specific instruction, the dependent workload DWA0in the virtual address entry TVA1_B is 5. By storing the dependent workload corresponding to each virtual address in the virtual address entries TVA1_B to TVAP_B, the input-output memory management unit126can then know which virtual address entries involve fewer other translations and can preferentially reserve them in the translation lookaside buffer1261to increase the chance that the computing unit with fewer translation requests can hit the desired virtual address entry in the translation lookaside buffer1261. In contrast, the input-output memory management unit126may prioritize the elimination of the virtual address entries in the translation lookaside buffer1261having a larger dependent workload, so as to prevent the computing units with more translation requests from occupying the resources of the translation lookaside buffer1261and causing the other computing units to wait for too long.

In the present embodiment, in Step S280, the input-output memory management unit126can select a virtual address entry with the longest recent use time and the largest dependent workload from the virtual address entries TVA1_B to TVAP_B in the translation lookaside buffer1261(e.g., virtual address entry TVA1_B), and in Step S290, clear the content of the selected virtual address entry TVA1_B so as to store the virtual address VADD1and its related information.

In the present embodiment, the slave computing device130can calculate the amount of translation requests of virtual addresses corresponding to the same computing unit and the same instruction at the time when the translation lookaside buffer134sends the translation request, thereby setting a dependent workload for each virtual address and including the virtual address and information of its dependent workload in the translation request. In this way, when the translation lookaside buffer1261receives the translation request, it can obtain the dependent workload corresponding to the requested virtual address, and can store a physical address corresponding to the virtual address and its dependent workload together into the virtual address entry, after traversing and retrieving the physical addresses.

Moreover, in some embodiments, if a recent use time of the virtual address entry has exceeded a system threshold value, it means that the virtual address entry has not been used for a long time, thus, the input-output memory management unit126can eliminate and clear this virtual address entry first. That is, in some embodiments, in Step S280, the input-output memory management unit126can first determine whether there is any virtual address entry having a recent use time exceeding the system threshold value, and if there is any virtual address entry having a recent use time exceeding the system threshold value, then said virtual address entry can be cleared first. However, if there is no virtual address entry having a recent use time exceeding the system threshold value, then the input-output memory management unit126can choose to clear the virtual address entry having the longest recent use time and largest dependent workload.

Furthermore, different computing units can send translation requests for the same virtual address. In such case, even if a translation request sent earlier does not find a corresponding virtual address entry in the translation lookaside buffer1261, the input-output memory management unit126can still traverse the page tables PT1to PTM using the page table walker1263and create a corresponding virtual address entry in the translation lookaside buffer1261; thus, the later sent translation request has certain possibility to find the corresponding virtual address entry in the translation lookaside buffer1261. In the present embodiment, in order to maintain the aforementioned mechanism of eliminating a virtual address entry in the translation lookaside buffer1261, when the input-output memory management unit126receives a translation request, and the translation lookaside buffer1261has stored therein a virtual address entry including the virtual address in the translation request, the input-output memory management unit126can reset the recent use time of the virtual address entry as 0, and can update the dependent workload of the virtual address entry according to the dependent workload of the later sent translation request.

For example, as shown inFIG.3, the virtual address entry TVA2_B has stored therein the virtual address VADD2and its corresponding physical address PADD2. Thus, when the input-output memory management unit126receives another translation request including the virtual address VADD2and the dependent workload DWA2′, the translation lookaside buffer1261can change the dependent workload DWA2previously recorded in the virtual address entry TVA2_B to the second dependent workload DWA2′, and can reset the recent use time RUT2of the virtual address entry TVA2_B.

In the embodiment shown inFIG.1, the slave computing device130can calculate the amount of translation requests of virtual addresses corresponding to the same computing unit and the same instruction when the translation lookaside buffer134sends the translation request, thereby setting a dependent workload for each virtual address and including the virtual address and information of its dependent workload in the translation request. However, the present application is not limited thereto; in some other embodiments, the translation lookaside buffer134can set a dependent work number of the virtual address according to the computing unit and the instruction corresponding to the requested virtual address and include the information of the dependent work number in the translation request when sending the translation request. In such case, the input-output memory management unit126can calculate the number of virtual address having the same dependent work number when receiving the translation request, thereby setting a dependent workload for each virtual address entry in the translation lookaside buffer1261, and then eliminating virtual address entry in the translation lookaside buffer1261according to the aforementioned mechanism.

FIG.4is a schematic diagram illustrating a computing system according to another embodiment of the present application. The computing system300and the computing system100have similar structures and can operate according to the same principle. The computing system300can include a memory110, a master computing device320and a slave computing device320. In the computing system300, when the computing unit1321looks for the physical address of the virtual address VADD1in a translation lookaside buffer334, and the translation lookaside buffer334does not contain an entry including the virtual address VADD1, the translation lookaside buffer334can set a dependent work number of the virtual address VADD1according to the computing unit1321and the instruction that trigger the translation request for the virtual address VADD1, and include the dependent work number in the translation request TREQ1for the virtual address VADD1. Consequently, the input-output memory management unit326would be able to calculate a dependent workload corresponding to each virtual address according to the dependent work number of each virtual address.

FIG.5is a schematic diagram illustrating virtual address entries TVA1_C to TVAP_C in the translation lookaside buffer3261according to one embodiment. As shown inFIG.5, for example, the virtual address entry TVA1_C can have five columns COL1to COL5, which can be used to respectively store the virtual address VADD1, the physical address PADD1corresponding to the virtual address VADD1, a recent use time RUT1of the virtual address entry TVA1_C, a dependent work number TS1of the virtual address entry TVA1_C, and a dependent workload DWA1of the virtual address entry TVA1_C.

In the present embodiment, when the translation lookaside buffer3261stores the virtual address VADD1to the virtual address entry TVA1_C, the translation lookaside buffer3261not only stores the dependent work number TS1in the virtual address entry TVA1_C, but also increase the dependent workload of the virtual address entry in the translation lookaside buffer3261that also includes the same dependent work number TS by one, so as to obtain an updated dependent workload DWA1, and store the dependent workload DWA1in the virtual address entry TVA1_C. For example, before storing the virtual address VADD1to the virtual address entry TVA1_C, if the virtual address entries TVA2_C and TVAP_C in the translation lookaside buffer3261have stored a dependent work number that is the same as the dependent work number TS1of the virtual address VADD1, and the dependent workload of the virtual address entries TVA2_C and TVAP_C is DWA2, then when storing the virtual address VADD1to the virtual address entry TVA1_C, the translation lookaside buffer3261can increase the dependent workload DWA2of the virtual address entries TVA2_C and TVAP_C by one to become DWA1′, and change the dependent workload of all of the virtual address entries TVA1_C, tVA2_C and TVAP_C to the dependent workload DWA1′. In this way, the translation lookaside buffer3261can maintain the correctness of the dependent workload of each virtual address entry.

Moreover, when the input-output memory management unit326receives a translation request, and the translation lookaside buffer3261has stored a virtual address entry including the virtual address of the translation request, the input-output memory management unit326can reset the recent use time of the virtual address entry to 0, and can change the dependent work number of the virtual address entry to the dependent work number in the translation request. In addition, the input-output memory management unit326can further increase the dependent workload of a virtual address entry in the translation lookaside buffer3261having the same dependent work number as the translation request by one, so as to update its dependent workload, and store the updated dependent workload in the virtual address entry.

FIG.6is a schematic diagram illustrating virtual address entries TVA1_C to TVAP_C in the translation lookaside buffer3261according to another embodiment. As shown inFIG.6, the virtual address entry TVA1_C has stored therein the virtual address VADD1and the physical address PADD1corresponding thereto. Thus, when the input-output memory management unit326receives a translation request including the virtual address VADD1and a dependent work number TS2, the translation lookaside buffer3261can change the dependent work number TS1previously recorded in the virtual address entry TVA1_C to the dependent work number TS2recorded in the present translation request, and can reset the recent use time RUT1of the virtual address entry TVA1_C to zero. Furthermore, if the virtual address entry TVA3_C in the translation lookaside buffer3261has the same dependent work number TS2as the virtual address entry TVA1_C, then the translation lookaside buffer3261can further increase the dependent workload DWA3of the virtual address entry TVA3_C by one to become DWA1′, and set the dependent workload of both the virtual address entries TVA1_C and TVA3_C as the dependent workload DWA1′. In this way, the translation lookaside buffer3261can maintain the correctness of the dependent workload of each virtual address entry.

In summary, the computing system, master computing device, slave computing device and associated method of the present application can select the virtual address entries in the translation lookaside buffer that should be prioritized for elimination based on the relative workload of translation requests, so that computing units with fewer translation requests can have a higher chance of hitting in the translation lookaside buffer, thereby achieving a short job first mechanism, reducing the overall waiting time of computing units for translation, and improving the performance of the computing system.

The foregoing description briefly sets forth the features of some embodiments of the present application so that persons having ordinary skill in the art more fully understand the various aspects of the disclosure of the present application. It will be apparent to those having ordinary skill in the art that they can easily use the disclosure of the present application as a basis for designing or modifying other processes and structures to achieve the same purposes and/or benefits as the embodiments herein. It should be understood by those having ordinary skill in the art that these equivalent implementations still fall within the spirit and scope of the disclosure of the present application and that they may be subject to various variations, substitutions, and alterations without departing from the spirit and scope of the present disclosure.