Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-02-17
2001-09-25
Nguyen, Than (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06295594
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to dynamic memory allocation for computer systems.
2. Description of the Related Art
Modem microprocessors are demanding increasing memory bandwidth to support the increased performance achievable by the microprocessors. Increasing clock frequencies (i.e. shortening clock cycles) employed by the microprocessors allow for more data and instructions to be processed per second, thereby increasing bandwidth requirements. Furthermore, modern microprocessor microarchitectures are improving the efficiency at which the microprocessor can process data and instructions. Bandwidth requirements are increased even further due to the improved processing efficiency.
Computer systems typically have a relatively large, relatively slow main memory. Typically, multiple dynamic random access memory (DRAM) modules comprise the main memory system. The large main memory provides storage for a large number of instructions and/or a large amount of data for use by the microprocessor, providing faster access to the instructions and/or data then may be achieved from a disk storage, for example. However, the access times of modem DRAMs are significantly longer than the clock cycle length of modern microprocessors. The memory access time for each set of bytes being transferred to the microprocessor is therefore long. Accordingly, the main memory system is not a low latency system Microprocessor performance may suffer due to the latency of the memory system.
In order to increase performance, microprocessors may employ prefetching to “guess” which data will be requested in the future by the program being executed. If the guess is correct, the delay of fetching the data from memory has already occurred when the data is requested (i.e. the requested data may be available within the microprocessor). In other words, the effective latency of the data is reduced. The microprocessor may employ a cache, for example, and the data may be prefetched from memory into the cache. The term prefetch, as used herein, refers to transferring data into a microprocessor (or cache memory attached to the microprocessor) prior to a request for the data being generated via execution of an instruction within the microprocessor. Generally, prefetch algorithms are based upon the pattern of accesses which have been performed in response to the program being executed. A popular data prefetch algorithm is the stride-based prefetch algorithm in which the difference between the addresses of consecutive accesses (the “stride”) is added to subsequent access addresses to generate a prefetch address.
Stride-based prefetch algorithms often work well with statically allocated data structures. Data structures are statically allocated if they are allocated memory at the initiation of a program and remain allocated in that same memory throughout execution of the program Because the data structure is statically allocated, it is generally laid out in contiguous memory locations. Stride-based prefetch algorithms work well because the memory storing the data structure is contiguous and the reference patterns are regular. A statically allocated array, for example, may be traversed by reading memory locations which are separated from each other by a regular interval. After just a few memory fetches, the stride-based prefetch algorithm may have learned the regular interval and may correctly predict subsequent memory fetches.
On the other hand, data structures are dynamically allocated if the memory for the data structures is allocated and deallocated as needed during the execution of the program. Dynamically allocated data structures have a variety of advantages in programs in which the amount of memory needed for the data structure varies widely and is difficult or impossible to predict ahead of time. Instead of statically allocating a very large amount of memory, the memory is allocated as needed. Memory space is thereby conserved.
Unfortunately, dynamic memory allocation algorithms are typically not conducive to prefetch algorithms. Dynamic memory allocation algorithms typically employ a “first fit” approach in which the first available memory block which includes at least the number of bytes requested for allocation is selected, or a “best fit” approach in which the available memory is scanned for a memory block which is closest in size to the requested number of bytes or causes the least amount of fragmentation if allocated to the request. These approaches select memory locations which may have no logical relation to other memory locations allocated to the data structure. Therefore, traversing the data structure generally does not involve regular intervals between the elements. A stride-based prefetch algorithm would have a low likelihood of prefetching the correct memory locations for such a dynamically allocated data structure. Other prefetch algorithms have similar difficulties, as the pattern of accesses is ill-defined. As used herein, a “memory block” comprises one or more contiguous bytes of memory allocated in response to a dynamic memory allocation request.
SUMMARY OF THE INVENTION
The problems outlined above are in large part solved by a dynamic memory allocation routine in accordance with the present invention. The dynamic memory allocation routine maintains an allocation size cache which records the address of a most recently allocated memory block for each different size of memory block that has been allocated. Upon receiving a dynamic memory allocation request, the dynamic memory allocation routine determines if the requested size is equal to one of the sizes recorded in the allocation size cache If a matching size is found, the dynamic memory allocation routine attempts to allocate a memory block contiguous to the most recently allocated memory block of that matching size. If the contiguous memory block has been allocated to another memory block, the dynamic memory allocation routine attempts to reserve a reserved memory block having a size which is a predetermined multiple of the requested size. The requested memory block is then allocated at the beginning of the reserved memory block. By reserving the reserved memory block, the dynamic memory allocation routine may increase the likelihood that subsequent requests for memory blocks having the requested size can be allocated in contiguous memory locations. Upon allocating a memory block in response to a dynamic memory allocation request, the dynamic memory allocation routine updates the size allocation cache to reflect the allocation.
Advantageously, elements of a dynamic memory structure (e.g. a dynamic data structure) may be allocated memory which is contiguous to other elements of the data structure. A stride-based data prefetch mechanism may thereby more accurately predict addresses to be fetched when the dynamic data structure is repeatedly accessed (e.g. to traverse the dynamic data structure). Performance of computer programs which use dynamic data structures may be improved when executing upon a computer system employing the dynamic memory allocation routine described herein.
The dynamic memory allocation routine described herein takes advantage of the characteristics exhibited by many programs employing dynamic data structures. Often, these programs may employ several dynamic data structures. Each data structure generally includes data elements having a fixed size, but the size of the data elements in different data structures may often differ. Therefore, memory allocation requests for data elements of a particular size may typically be requests corresponding to data elements within the same data structure. Allocating contiguous memory to data elements having a particular size may thereby lead to regular access patterns when accessing these elements within the corresponding dynamic data structure. In this manner, stride-based prefetching may become more useful in accessing dynamic data structures.
Broadly speaking, the present invention contemplates a method for dynamic memory allocation in a comput
Advanced Micro Devices , Inc.
Conley Rose & Tayon PC
Merkel Lawrence J.
Nguyen Than
LandOfFree
Dynamic memory allocation suitable for stride-based prefetching does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic memory allocation suitable for stride-based prefetching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic memory allocation suitable for stride-based prefetching will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2494994