Selection of variable memory-access size

A method for dynamically selecting a size of a memory access may be provided. The method comprises accessing blocks having a variable number of consecutive cache lines, maintaining a vector with entries of past utilizations for each block size, and adapting said block size before a next access to the blocks.

BACKGROUND

Cache architectures have a long history in the design of computer systems. In many cases, they help to increase an access speed—or in other words, to decrease the access time—between a CPU (central processing unit) and a main memory. This helps to reduce the so-called Von-Neumann bottleneck and may increase the speed of processing dramatically.

Different cache architectures have been introduced over time, including L1, L2 and L3 caches, e.g., as inclusive or exclusive caches. Today, load and store instructions to and from the main memory are performed with a fixed amount of payload, e.g., 64 bytes or 128 bytes. This may be sub-optimal during various phases of workload execution. E.g., during workload phases with a lot of scattered data with sizes of only a few bites to be loaded or stored, a large payload size (large cache line size) may result in loading a lot of data that are not used by the workload, or storing data that have not been updated. This results in a waste of precious memory bandwidth and potentially increased latencies and may furthermore result in conflicts for unused data.

On the other side, during workload phases with accesses to a large amount of continuous data (e.g., simple one-dimensional arrays) to be loaded or stored, a small payload size may result in many concurrent load or store instructions in flight or even in serialization of request execution. Both of these scenarios will result in a decrease of throughput and add to an unnecessary consumption of computing resources, like number of gates and required power.

SUMMARY

Aspects of the disclosure may include a computer implemented method, computer program product, computing device and system for dynamically selecting a size of a memory access is provided. An example method comprises blocks having a variable number of consecutive cache lines, maintaining a vector with entries of past utilizations for each block size, and adapting the block size before a next access to the blocks. It may be noted that the blocks may refer to blocks of accessed data.

DETAILED DESCRIPTION

The term ‘dynamically selecting’, in particular dynamically selecting the ‘size of a memory access’ denotes that the amount of data accessed—either for a movement from main memory to the CPU cache or the other way around—is selected during an execution of programs. The data mentioned may be a mixture of instructions and data. This may be performed by dynamically exchanging load and/or store instructions that reflect individually the amount of transferred data, i.e., the block size.

The term ‘runtime’ denotes a time during an execution of a program, e.g., a system program or a user program.

The term ‘block’ denotes a group of data—i.e., real data and/or instructions—comprising a consecutive number of cache lines.

The term ‘cache line’ denotes a certain number of words to be transferred from the main memory to the CPU cache. Typically, the cache line has a fixed size and may represent the smallest amount of data being transferred between the CPU cache and the main memory, or vice versa.

The term ‘vector with entries of past utilizations’ denotes—mathematically spoken—a group of elements, wherein each element may represent a utilization of historic block sizes during data transfers between the CPU cache and a main memory or vice versa. Again, the blocks may comprise one or more cache lines.

The term ‘cache’ denotes a hardware or software component that may store data, so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation, or the duplicate of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot be found in a cache. Cache hits are served by reading data from the cache, which is faster than re-computing a result or reading from a slower data store; thus, the more requests can be served from the cache, the faster the system performs. In the context of the here proposed concept, the cache may be a CPU cache allowing faster access to data on the main memory.

The proposed method for dynamically selecting a size of a memory access may offer multiple advantages and technical effects. For example, the increased flexibility in the cache management may help to increase processing speed of the CPU/cache/main memory combination without having to decrease the cycle time, i.e., increase the operating frequency, with the known negative effects (e.g., higher currents, more heat dissipation requirements and so on). Depending on recent accesses to the memory and depending on a vector with information about the recent accesses, a variable block size may be applied in order to vary the number of consecutive cache lines to be transferred from the main memory to the CPU cache, or vice versa.

It may be pointed out that it is not required to change the size of the individual cache line or the size of the cache itself. Such an alternative approach may require a lot of complex design changes as well as a large number address recalculations during operation. The proposed solution does not have these negative effects. Using different load and store instructions, the number of consecutive cache lines accessed (i.e., moved from main memory to the CPU cache, or vice versa) may be varied. Consequently, also the size defined by the number of bytes required for accessing one or more cache lines at the same time may not change. Consequently, the instructions for accessing a different number of consecutive cache lines may be exchanged dynamically “on the fly” during execution of a workload.

This may help to adapt the cooperation between the CPU, the cache memory and the main memory depending on the type of workload. If only individual words are accessed during execution, the number of consecutive cache lines may be reduced to e.g., one; if on the other side, a larger number of consecutive addresses spanning a plurality of the cache line size may be accessed, the number of consecutive cache lines loaded or stored may be increased by simply changing the load/store instruction dynamically.

This may be completely transparent to a user program and to a large degree also transparent to the existing cache management of operating systems. The dynamical adaption of the variable number of consecutive cache lines may be completely implemented in hardware modules or as microcode. Its functionality may also be completely independent from software dependencies, e.g., single-user environment, multi-user environment, hypervisor-based execution, operating systems, and so on.

According to one embodiment of the method, the adapting the block size may be performed by the following: upon the utilization of a past block size being below a low threshold value, decreasing the block size to an adapted block size or, upon the utilization of a past block size being greater than a high threshold value, increasing the block size to the adapted block size. As default value, the block size may remain unchanged. Hence, depending on the size of recent accesses (i.e., to the cache or to the main memory), the size for the next access may be changed dynamically, i.e., during runtime of any program. This method alternative focusses on the past utilization and compares the threshold values.

According to one alternative embodiment of the method, the adapting the block size may be performed by applying an algorithm—in particular a cognitive algorithm, e.g., a neural network, or in form of a time series algorithm or in form of a linear regression algorithm—to the vectors of past utilizations for predicting the utilization of the block size. Hence, using this alternatively preferred embodiment, the dynamic adaption of the block size may not be performed simply based on historic values—e.g., by building an average number—but by an active prediction of an expected suitable block size in the future.

Thus, the proposed method and system may change its behavior between the option “past” and “future”.

According to another embodiment of the method, the adapting the block size may be performed after an actual memory access by one of the load or store instructions. Thus, the adapted block size may be applied to future accesses, i.e., future data transfers from the main memory to the CPU cache or vice versa. The method and the system may allow the switch between the alternatives “after” and “during”.

According to another embodiment of the method, the adapting the block size may be performed during an actual memory access by one of the load or a store instruction and may thus be applied to the current memory access. Hence, the instruction relating to a larger number of consecutive cache lines may be selected or exchanged during the instruction fetch operation.

According to another embodiment of the method, the method may also comprise using different load instructions for different block sizes. If the load instruction is coupled to the block size, different block sizes may be accessed by using different load instructions. The total length of the load and store instructions, measured in number of bits required, do not vary.

In this sense and according to another embodiment of the method, the different load instructions may differ in the size of the loaded or accessed block sizes by predefined factors. The factor may be any integer number (e.g. 2 or 3 or 4, etc.). Practical boundary conditions may limit the factor to a single digit integer value. Hence, the instruction set design is flexible. The additional instruction(s) may be implemented in micro-code or may be implemented in hardware; also, a mixture of both implementation alternatives may be possible.

The same thought may be applicable for storage instructions. Hence, according to another embodiment, the method may comprise using different store instructions for different block sizes. Consequently, and according to a further preferred embodiment of the method, the different store instructions differ in the size of the stored block sizes by predefined factors compared to a basic store instruction. Regarding the factors, the same thought as for the load instruction may apply also here.

According to one optional embodiment, the method may comprise determining the most recent past utilization value of the entries of a past utilization. This way the related vector may have a limited size and may thus only require limited storage space.

According to another optional embodiment, the method may also comprise determining an average of past utilization values of the entries of past utilizations in constant time intervals. That may be, e.g., the last 10 utilizations (alternatively, 2, 4, 8, 16 or any other integer number). This way, more storage capacity may be required for the vector of past utilizations of a block size if compared to a usage of the most recent past utilization. As an example: for e.g. for n=10 utilizations a vector may look like this: [0.3, 0.5, 0.2, 0.6, 0.8, 0.7, 0.9, 0.8, 0.7, 0.9].

According to another embodiment of the method, the applying the algorithm to the vectors of past utilizations may be at least based on one selected out of the group comprising time-series-based forecasting, a linear regression and a suitable neural network algorithm. This may be instrumental to an implementation of a machine learning and self-adapting function regarding the selected block size.

In the following, a detailed description of the figures will be given. All instructions in the figures are schematic. Firstly, a block diagram of an embodiment of one example method for dynamically selecting a size of a memory access is given. Afterwards, further embodiments, as well as embodiments of the method for dynamically selecting a size of a memory access, will be described.

FIG. 1shows a block diagram of an embodiment of the proposed method100for dynamically selecting a size of a memory access—in particular, measured in number of consecutive cache lines—at runtime, i.e., during an execution time of software programs. The method100comprises accessing,102, blocks—in particular by loading and/or storing instructions and data—having a variable number of consecutive cache lines; maintaining,104, a vector with entries of past utilizations for each block size (again defined by number of cache lines per block); and adapting,106, the block size before a next access to the block. It may be mentioned that the number of consecutive cache lines may start at 1.

FIG. 2shows a block diagram of a flowchart200for adapting dynamically the number of cache lines transferred between the CPU cache and a main memory. The instruction “ldi” stands for “load i cache lines” from main memory to the CPU cache, whereas “sti” stands for “store i cache lines from the CPU cache to the main memory”, wherein i=1, 2, 3, . . . . The process of the adaption of the load and store instructions may start at202. At a current point in time, the load and store instructions ldi, stiare used, block204.

During the determination206, it may be determined if the utilization of the most recent evicted block is larger than a high water mark, i.e., a high threshold, an adaption of the used load and/or store instruction may be performed dynamically. It may be noted that a block is called “evicted” if one cache line of the block is evicted. In case of yes (“Y”) either the load ldiand/or the store stiinstruction may be changed—block208—to a load and/or store instruction with an increased number of consecutive cache lines to be loaded or stored, i.e., ldi+1and/or sti+1. Consequently, the next access to the cache—either load or store—may use the dynamically exchanged load and/or store operation.

If on the other side—case “N” of determination206—during the determination210the utilization of the most recent evicted block is smaller than a low-water mark, i.e., a low threshold, and a different adaption to the used load and/or store instruction may be performed dynamically. In case of no (“N”) of the determination210, either the load ldiand/or the store stiinstruction may be changed—block212—to a load/and/or store instruction with a decreased number of consecutive cache lines to be loaded or stored, i.e., ldo−1and/or stü1. Consequently, the next access to the cache—either load or store—may use the dynamically changed—here with a decreased number of cache lines—load and/or store operation. The adaption process may end at214.

As discussed above, the adaption process may be performed after an actual memory access or alternatively during an actual memory access.

FIG. 3shows a block diagram of an alternative flowchart300for adapting dynamically the number of cache lines transferred between the CPU cache and a main memory. Again, the instruction “ldi” stands for “load i cache lines” from main memory to the CPU cache, whereas “sti” stands for “store i cache lines from the CPU cache to main memory”. The process of the adaption of the load and store instructions may start at302. At a current point in time, the load and store instructions ldi, stiare used, block304.

Next, a forecasting or prediction for a future cache line utilization may be calculated, block306. As an example, a time series algorithm may be applied, however, also alternative algorithms including linear regression or other machine learning algorithms, like any type of cognitive computing algorithm for predicting a future block size/cache line utilization, may be implemented.

Next, during the determination208it may be determined if the predicted utilization “predictedUtilization” is larger than a high water mark, i.e., a high threshold, an adaption of the used load and/or store instruction may be performed dynamically. In case of yes (“Y”) either the load ldiand/or the store stiinstruction may be changed—block310—to a load and/or store instruction with an increased number of consecutive cache lines to be loaded or stored, i.e., ldi+1and/or sti−1. Consequently, the next access to the cache—either load or store—may use the dynamically exchanged load and/or store operation.

If on the other side—case “N” of determination308—during the determination312the predicted utilization of bocks is smaller than a low-water mark, i.e., a low threshold, and a different adaption to the used load and/or store instruction may be performed dynamically. In case of yes (“Y”) of the determination312, either the load ldiand/or the store stiinstruction may be changed—block314—to a load/and/or store instruction with a decreased number of consecutive cache lines to be loaded or stored, i.e., ldi−1and/or sti−1. Consequently, the next access to the cache—either load or store—may use the dynamically exchanged—here with a decreased number of cache lines—load and/or store operation. The adaption process may end at316.

Also, as in the case above, the adaption process may be performed after an actual memory access, or alternatively, during or just before an actual memory access.

FIG. 4shows possible scenarios in a more concrete form. This process400may start at402. The currently used load/store instruction may be either an ld2or an st2instruction, block404. During the determination process for the load/store instruction adaption, three different alternatives may become part of the process. In one case the number of consecutive cache lines to be loaded or stored is unchanged, block410. If it may be determined that the number of consecutive cache lines has to be decreased for a load/store access, the left alternative, block408is used, resulting in using an ld1and/or st1instruction loading and/or storing just one cache line. If the ld1/st1instruction has been the current access instruction, it is not reduced further; it simply stays as ld1/st1in case of a decrease.

If, on the other hand, it may be determined that the number of consecutive cache lines has to be increased for a load/store access, the right alternative, block412is used, resulting in using an ld3and/or st3instruction loading and/or storing three consecutive cache lines. A skilled person will know how other examples with more than three cache lines can easily be imagined and implemented. The determination process406may be one of the alternatives discussed in the context ofFIG. 2orFIG. 3. This process flow ends at block414.

In one embodiment using the predictive model (compareFIG. 3), the following sequence of steps may be implemented: (i) For each eviction event, the average utilization of the blocks per block size is measured and appended to the vector of utilizations corresponding to the related block size. (ii) For each load/store event, the predicted utilization of the current block size is fetched and used in combination with the high and low thresholds to decide about the decrease or the increase of the block size of the next access. (iii) The predicted utilization would be given by a cognitive model corresponding to the current block size. (iv) The cognitive model would be built with utilization data specific to the block size.

This may assume the existence of a bookkeeping mechanism like: (1) whether the cache line has been used or not (a 1/0 bit per cache line); and (2) a utilization vector (of limited sizes to avoid infinite growth) per block size. When a maximum size is reached, the least recent calculated utilization will take the place of the oldest utilization data. Hence, under the condition of (1), the utilization of a block is basically the number of “1s” divided by the cache lines in the block.

The task of the cognitive model would be to predict the next “b” (typically b=1) utilizations given the most recent “a” utilizations. One model per block size may be possible.

The cognitive model can be trained with N sequences of (a+b) successive utilizations. The training data will be a set of N tuples (“a” utilizations, “b” utilizations). At inference time, the model of the current block size will be used to predict the next utilization, given the most recent calculated “a” utilization data. Optionally, the cognitive model can be trained periodically. After a re-training, the old model can be swapped with the new model.

FIG. 5shows an embodiment of the system500for dynamically selecting a size of a memory access at runtime. The system comprises a cache management unit502adapted for accessing blocks having a variable number of consecutive cache lines, a maintaining unit504adapted for maintaining a vector with entries of past utilizations for each block size, and an adaption unit506adapting the block size before a next access to the blocks. It may be noted that the adaption unit may, e.g., be a component of a cache control/management logic, or alternatively, the memory management unit of a computer or a part of the fetch unit of the processor.

Embodiments of the invention may be implemented together with any type of computer, regardless of the platform being suitable for storing and/or executing program code.

FIG. 6shows, as an example, a computing system600suitable for executing program code to implement the methods described above with respect toFIGS. 1-4. Additionally, computing system600can be configured to execute program code to implement one or all of the functions of cache management unit502, maintaining unit504, and adaption unit506discussed above with respect toFIG. 5.

As shown in the figure, computer system/server600is shown in the form of a general-purpose computing device. The components of computer system/server600may include, but are not limited to, one or more processors or processing units602, a system memory604, and a bus606that couples various system components including system memory604to the processor602. Bus606represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnects (PCI) bus. Computer system/server600typically includes a variety of computer system readable media. Such media may be any available media that is accessible by computer system/server600, and it includes both, volatile and non-volatile media, removable and non-removable media.

The program/utility, having a set (at least one) of program modules616, may be stored in memory604by way of example, and not limitation, as well as an operating system, one or more application programs, other program modules, and program data. Each of the operating system, one or more application programs, other program modules, and program data or some combination thereof, may include an implementation of a networking environment. Program modules616generally carry out the functions and/or methodologies of embodiments described herein.

The computer system/server600may also communicate with one or more external devices618such as a keyboard, a pointing device, a display620, etc.; one or more devices that enable a user to interact with computer system/server600; and/or any devices (e.g., network card, modem, etc.) that enable computer system/server600to communicate with one or more other computing devices. Such communication can occur via Input/Output (I/O) interfaces614. Still yet, computer system/server600may communicate with one or more networks such as a local area network (LAN), a general wide area network (WAN), and/or a public network (e.g., the Internet) via network adapter622. As depicted, network adapter622may communicate with the other components of computer system/server600via bus606. It should be understood that although not shown, other hardware and/or software components could be used in conjunction with computer system/server600. Examples, include, but are not limited to: microcode, device drivers, redundant processing units, external disk drive arrays, RAID systems, tape drives, and data archival storage systems, etc.

Additionally, the system500for dynamically selecting a size of a memory access is integrated into the block610of the cache memory to symbolize that its function is closely related to the data transfer between the CPU and the main memory/RAM608.