Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
2000-03-24
2002-10-15
Siek, Vuthe (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06467075
ABSTRACT:
BACKGROUNDS OF THE INVENTION
1. Field of the Invention
The present invention relates to a device of synthesizing a program with a function of pointers and dynamic allocation/deallocation, and a method of synthesizing a program with a function of pointers and dynamic allocation/deallocation.
2. Description of the Related Art
Different languages have been used as input to high-level synthesis. Hardware Description Languages (HDLs), such as Verilog HDL and VHDL, are the most commonly used. However, designers often write system-level models using programming languages, such as C or C++, to estimate the system performance and verify the functional correctness of the design. Using C/C++ offers higher-level of abstraction, fast simulation as well as the possibility of leveraging a vast amount of legacy code and libraries, which facilitates the task of system modeling.
The use of C/C++ or a subset of C/C++ to describe both hardware and software would accelerate the design process and facilitate the software/hardware migration. Designers could describe their system using C. The system would then be partitioned into software and hardware blocks, implemented using synthesis tools. The new SystemC initative is an attempt to standardize a C/C++-based language for both hardware and software design.
C was originally designed to develop the UNIX operating system. It provides constructs to directly access memory (through pointers) and to manage memories and I/O using the standard C library (malloc, free, . . . ). These constructs are widely used in software. Nevertheless, many of the networking and multimedia applications implemented in hardware or mixed hardware/software systems are also using complex data structures stored in one or multiple memory banks. As a result, many of the C/C++ features which were originally designed for software applications are now making their way into hardware.
In order to help designers refine their code from a simulation model to a synthesizable behavioral description, this inventors are trying to efficiently synthesize the full ANSI C standard. This task turns out to be particularly difficult because of dynamic memory allocation/deallocation, function calls, recursions, goto's, type castings and pointers.
In the past few month, different synthesis tools have been announced to ease the mapping of C code into hardware (Abhijit Ghosh, Joachim Kunkel, Stan Liao, “Hardware Synthesis from C/C++,” proceedings of the Design, Automation and Test in Europe DATE'99, pp.387-389, Munich, 1999.), (Kazutoshi Wakabayashi, “C-based Synthesis with Behavioral Synthesizer, Cyber,” proceedings of the Design, Automation and Test in Europe DATE'99, pp.390-391, Munich, 1999.). And other many more companies and research projects work on synthesis of hardware from C. All of these tools support a subset of the language (e.g. restrictions on pointers, function calls, etc.). In particular, they do not support dynamic memory allocation/deallocation using the ANSI standard library functions malloc and free
In this inventors tool SpC (Luc Semeria, Giovanni De Micheli, “SpC: Synthesis of Pointers in C.Application of Pointer Analysis to the Behavioral Synthesis from C”, proceedings of the International Conference on Computer-Aided Design ICCAD'98, pp.321-326, San Jose, November 98.), pointer variables are resolved at compile-time to synthesize c functional models in hardware efficiently. In description of the preferred embodiment, this inventors will focus on an implementation of dynamic memory allocation/deallocation (malloc, free) in hardware. By definition, in general, storage for dynamically allocated data structures cannot be assigned at compile time. The synthesis of C code involving dynamic memory allocation/deallocation requires access to some allocation and deallocation primitives implemented either in software, as in an operating system, or in hardware.
Dynamic memory allocation/deallocation is tightly coupled with pointers and the notion of a single address space. Pointer dereferences (load, stores, etc.) as well as memory allocation/deallocation are all referring to a main memory. However, in application-specific hardware, designers may want to optimize the memory architecture by using register banks, multiple memories etc. Therefore, memory allocations may be distributed onto multiple memories and pointers may reference data stored in registers, memories or even wires (e.g. output of a functional unit). To enable efficient mapping of C code with pointers and malloc's into hardware, the synthesis tool has to automatically generate the appropriate circuit to dynamically allocate, access (read/write) and deallocate data. Memory management as well as accurate pointers resolution are key features for C-based synthesis. They are enablers for the efficient design of applications involving complex data structures.
The contribution of description of the preferred embodiment is to present a solution for efficiently mapping arbitrary program code with pointers and dynamic allocation allocation/deallocation into hardware. This solution fits current memory management methodologies. It consists of instantiating a hardware allocator tailored to an application and a memory architecture. This work also supports the resolution and optimization of pointers without restriction on the data structures.
METHODOLOGY AND RELATED WORK
For decades, memory management has been one of the major development area both for software and computer architecture. In software, at the user-level, memory management is typically performed by the operating system. In hardware, memory bandwidth is often a bottleneck in applications such as networking, signal processing, graphics and encryption. Memory architecture exploration and efficient memory management technology are key to the design of new high-performance systems. Memory generators commercially available today enable fast integration of memories in a system. Scheduling of memory accesses has also been integrated into most commercial high level synthesis (ELS) tools. Most of the refinement and compilations steps developed for software applications can also be used for hardware. Nevertheless, a software methodology usually assumes a fixed memory architecture which may be general purpose or application specific like in a DSP or ASIP. In hardware, at the behavioral level, designers would typically explore different memory architectures in order to trade-off area and power for a given timing constraint.
A few projects and tools have recently been announced to ease the mapping of C models into hardware. In practice, current tools don't support dynamic memory allocation/deallocation and have restriction on pointers' usage (Giovanni De Micheli , “Hardware Synthesis from c/c++,” in the proceeding of the Design, Automation and Test in Europe DATE'99, pp.382-383, Munich, 1999.). SpC , enables the behavioral synthesis of C code with pointer variables to variables and arrays. In description of the preferred embodiment, this inventors present how pointers in general (e.g. array of pointers, pointers in structures, pointers to structures etc.) and dynamic memory allocation/deallocation can also be efficiently synthesized.
A methodology for the design of custom memory systems has been described by Catthoor et al. (Francky Catthoor, Sven Wuytack, Eddy De Greef, Florin Balasa, Lode Nachtergaele, Arnout Vandecappelle, “Custom Memory Management Methodology,” Kluwer Academic Publishers, Dordrecht, June 98.). It is defined for two sets of applications, networking and signal processing, and supports a limited subset of C/C++. The basic concepts presented in Catthoor's work can be generalized to support a larger subset of the C syntax for an extended set of applications. Two main steps can be distinguished in the methodology: this inventors describe briefly here the transformations performed first at the system level, and then at the architectural level.
A
De Micheli Giovanni
Sato Koichi
Semeria Lcu
Lee Jr. Granvill D
Siek Vuthe
Sughrue & Mion, PLLC
LandOfFree
Resolution of dynamic memory allocation/deallocation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Resolution of dynamic memory allocation/deallocation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resolution of dynamic memory allocation/deallocation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2988940