Optimized virtual memory management for dynamic data types

Details Optimized virtual memory management for dynamic data types Optimized virtual memory management for dynamic data types

1999-07-23

2003-06-10

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

C711S203000, C707S793000

Reexamination Certificate

active

06578129

ABSTRACT:

FIELD OF THE PRESENT INVENTION
Optimal design of virtual memory management schemes for applications with dynamic data types, for instance network components, is presented. Said virtual memory management design fits into an overall dynamic memory management design flow. This flow is part of an overall system design flow for embedded hardware/software processors. The overall design flow focuses on data storage and transfer issues and their relation with power consumption and memory size.
BACKGROUND OF THE PRESENT INVENTION
Virtual memory management deals with the allocating of a memory block (in which data can be stored) for an application request and recycling the memory block when it is not used anymore by the application. As such the virtual memory concept defines an interface between the application and the physical memory used by the application.
As the power consumption of data-dominated applications (applications in which the power consumption is due to the huge amount of data to be processed and not due to the computation or arithmetic complexity) is heavily dominated by data storage and transfers, systematic design methodologies in which the dynamic storage related issues are globally optimized before doing detailed realization of an embedded processor are needed (F. Catthoor, et al., “
Global communication and memory optimizing transformations for low power signal processing systems
”, IEEE workshop on VLSI signal processing, La Jolla Calif., October 1994. Also in VLSI Signal Processing VII, J. Rabaey, P. Chau, J. Eldon (eds.), IEEE Press, New York, pp.178-187, 1994.) (V. Tiwari, et al., “
Instruction
-
level power analysis and optimization of software
”, Journal of VLSI Signal Processing, No.13, Kluwer, Boston, pp.223-238, 1996.) (R. W. Brodersen, “
The network computer and its future
”, Proc. IEEE Int. Solid-State Circuits Conf., San Francisco, Calif., pp.32-36, February 1997.). It is clear that for data-dominated applications with dynamic data types the optimal design of virtual memory management must be part of such an overall design methodology. For RMSP applications much of the memory management can be decided at compile time while according to the subject matter of the present invention the virtual memory management must deal with the memory organization at run-time.
The optimal design of the virtual memory management can be organized in three steps (further called the dynamic memory management design flow). In a first step abstract data types are refined into concrete data types (abstract data type refinement) (S. Wuytack, F. Catthoor, H. De Man, “
Transforming Set Data Types to Power Optimal Data Structures
”, IEEE Transactions on Computer-aided Design, Vol.CAD-15, No.6, pp.619-629, June 1996.). In the second step (the virtual memory management step) defines a number of virtual memory segments (VMSes) and their corresponding custom memory managers. The third step (the physical memory management stage) assigns these VMSes to a number of allocated physical memories. The present invention deals with the second step, the so-called virtual memory management step.
Different virtual memory management schemes are known in the software community (G. Attardi, T. Flagea, “
A Customisable Memory Management Framework
”, Proc. of the USENIX C++ Conference, Cambridge, Mass., 1994.) (P. R. Wilson, et al., “
Dynamic Storage Allocation: A Survey and Critical Review
”, Proc. Intnl. Wsh. on Memory Management, Kinross, Scotland, UK, September 1995.) but no complete overview of the possible choices is currently available. Moreover for software the main criteria for selection of an appropriate scheme are speed and memory usage whereas for embedded processors power consumption is an important criterion.
In the context of software systems generally applicable (i.e. for all applications, thus not exploiting characteristics of the application) virtual memory management schemes are usual. The only exception is that often the possibility to implement a dedicated virtual memory manager by the user is provided, enabling some exploration. In some cases some libraries of virtual memory management schemes are available (G. Attardi, T. Flagea, “
A Customisable Memory Management Framework
”, Proc. of the USENIX C++ Conference, Cambridge, Mass., 1994.). For embedded processors implementing, as focussed in the present invention, a general virtual memory management scheme is not feasible however. A specific scheme for each specific application is necessary.
In the context of software the application is assumed to run on a given hardware architecture while in the present invention virtual memory management design is part of a methodology for design of the hardware. In the software community a given VMM scheme is implemented starting from a predefined memory architecture. For instance, the word size is already defined. Overhead in VMM schemes is likely to be significant, since it is not possible to allocate less than one word for storing information such as used/free or boundary tags. In embedded software or hardware implementations the memory architecture will be defined during the synthesis of the application. For instance, number of memories and memory word sizes are not fixed before synthesis. Thus, overhead can be made as small as the minimum necessary in opposition to fixed architecture target.
In the article by M. Johnstone, P. R. Wilson. “
The Memory Fragmentation Problem: Solved
?”, Proc. of Object-Oriented Programming Systems, Languages and Applications—Wsh. on Garbage Collection and Memory Management, Atlanta Ga., October 1997, a broad comparison between different VMM schemes is presented. These VMM schemes are compared based on the fragmentation caused by each of the mechanisms. It is demonstrated that among the six best schemes, fragmentation is nearly the same and very small. Among these cases, fragmentation could be neglected when compared to overhead necessary for implementing the VMM mechanism. It is assumed in the present invention that also the freedom regarding the number of memories to be used, the number of words needed for each memory, and the memory hierarchy is available for further power optimization.
Known memory-oriented synthesis techniques deal with data types which can easily be analyzed at compile time, for instance multi-media signal processing applications dealing with multi-dimensional array signals. The applications, focussed in the present invention, using dynamic data types, such as network components, in which only a little information is available at compile time, cannot be treated in the same manner. Nevertheless, it is important to exploit the small amount of information as much as possible. Previous work on network components (B. Svantesson, et al., “
Modeling and synthesis of operational aid management system
(OAM)
of ATM switch fabrics
”, Proc. 13th Norchip Conf., pp.115-122, November 1995.) (characterized by dynamic data types) has focussed at low abstraction levels but has not dealt with virtual memory management issues.
Other power-oriented work has been focussing on data-path and control logic design (“
Low power CMOS design
”, (eds. A. Chandrakasan, R. Brodersen), IEEE Press, 1998.) and programmable processors. For the target field of embedded hardware/software processors no such work is known. Previous algorithm-level low power work (S. Wuytack, et al., “
Power Exploration for Data Dominated Video Applications
”, Proc. IEEE Intnl. Symp. on Low Power Design, Monterey Calif., pp.359-364, August 1996.) (P. Slock, et al., “
Fast and Extensive System
-
Level Memory Exploration for ATM Applications
”, Proceedings 10
th
ACM/IEEE International Symposium on System-Level Synthesis, Antwerp, Belgium, September 1997.) has focused on signal processing applications.
As a summary it can be stated that the present invention deals with dedicated (application specific) virtual memory management design for data-dominated applications with dynamic data types as part of design of embedded processors (no fixed architecture is given at the sta

Affiliated with

Also associated with

Rating

Optimized virtual memory management for dynamic data types does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimized virtual memory management for dynamic data types, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized virtual memory management for dynamic data types will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3130033