Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-08-30
2001-11-27
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S016000
Reexamination Certificate
active
06324680
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to high level, register transfer and logic synthesis for circuitry, and more particularly to a method for synthesizing aggregate data types, such as arrays and records, in a general manner.
2. Description of the Related Art
Aggregate data types, such as arrays and records, are often used in describing circuit designs at higher-levels of abstraction. These complex data types are useful for grouping related data into a single object, which makes the description more readable and concise.
From a design style point of view, the use of aggregate data types makes a design description more maintainable. For example, if records are used as ports in a design, it is very easy to add new inputs and outputs by simply adding fields to the existing records, without having to change the other parts of the design which instantiate the changed design component. This effectively helps maintain a fixed I/O definition for all components in the design.
Another reason for the frequent usage of arrays and records originates from their frequent usage in software languages. Many methodologies today, for example, incorporate the use of the C programming language for algorithmic development. This ‘C’ description is then translated to a hardware description language (HDL) (e.g., VHDL (very high speed integration circuit HDL) or Verilog) for synthesis. Synthesis includes realizing a physical layout based on the programming language algorithm and data structure. The arrays and records used in the ‘C’ description can be mapped directly to arrays and records in the HDL. Thus, it is important to be able to synthesize these data types efficiently.
One problem in synthesizing arrays and records lies in being able to implement in hardware the different ways in which these arrays and records may be read from or written to. For example, an array object may be assigned as a whole to another array object or accessed with an index (an indexed operation) or with a range of indexes (a slice operation). Similarly, records may be accessed as a whole, or via separate fields. From a synthesis point of view, an indexed operation on a 1-dimensional array requires an address decoder. Multi-dimensional arrays will require multiple levels of address decoding. The address decoding logic can get very complex when multiple levels of nesting of arrays and records are used.
Moreover, one should be able to use arrays and records for variables and signals which may or may not be inferred as registers. In other words, there should be no predefined assumption that arrays are only to be used by variables or signals which are implemented as registers. This generalization makes the synthesis task more complex because there may not be a single register bank representing the array, but the array variable may be implemented as multiple nets in the network.
Commercial synthesis systems can handle record and array types in a limited way. From a specification point of view, these systems usually restrict the data types that can be defined in a design as well as the set of operations that can be used on them. For instance, multi-dimensional arrays, mixing of record and array structures are typically not supported. These restrictions severely limit the advantages of using high-level languages and constrain the designer's ability to specify the design succinctly. From an implementation point of view, most of the existing work has focused on mapping objects of array type onto physical memory modules. The main problems addressed by these works are the partitioning and/or grouping of array objects of different sizes into physical memories of fixed sizes. The problem of synthesizing pointers and arrays has also been addressed in a limited way.
Therefore, a need exists for a system and method for synthesizing complex data types. A further need exists, for synthesizing arrays and records.
SUMMARY OF THE INVENTION
A method for synthesizing aggregate data types, in accordance with the present invention, includes representing aggregate data types in a control data flow graph, by representing aggregate objects as operand nodes, and operations on the aggregate objects as operation nodes. One-dimensional bit vectors are formed for the operand nodes, by recursively traversing through fields of the aggregate data type associated with the aggregate objects. Read and write operation nodes are formed in the control data flow graph for representing language constructs for accessing the aggregate objects. The control data flow graph is mapped onto hardware.
Another method for synthesizing aggregate data types, including multi-dimensional arrays, records and nested data structures, in accordance with the invention, includes representing aggregate data types in a control data flow graph, by representing aggregate objects as operand nodes, and operations on the aggregate objects as operation nodes. One-dimensional bit vectors are formed for the operand nodes, by recursively traversing through fields of the aggregate data type associated with the aggregate objects. Read and write operation nodes are formed in the control data flow graph for representing language constructs for accessing the aggregate objects. The control data flow graph is mapped onto hardware by representing the operand nodes as one of at least one storage element and a net, based on register inference rules of very high speed integration circuit hardware description language (VHDL) synthesis. The control data flow graph is also mapped onto hardware by mapping the operation nodes of the control data flow graph for a plurality of addressing methods.
In alternate methods, the step of representing aggregate data types in a control data flow graph may include the steps of representing language constructs for accessing the aggregate objects of the operand nodes as the operation nodes, and connecting nodes corresponding to aggregate objects and operations on the aggregate objects by directed edges. The step of representing language constructs for accessing the aggregate objects may include the steps of representing access operations with a constant index as a slice operation on bit vector representations of the aggregate objects, and generating a read/write operation for access operations with a variable index. The step of mapping the control data flow graph onto hardware may include the step of representing the operand nodes as one of at least one storage element and a net, based on register inference rules of very high speed integration circuit hardware description language (VHDL) synthesis. The step of forming one-dimensional bit vectors may include the step of flattening each aggregate data type into a bit-vector by concatenating elements of the aggregate data type in a hierarchical manner.
In other methods, the step of mapping the control data flow graph onto hardware may include the step of mapping operation nodes of the control data flow graph for a plurality of addressing methods. The steps of storing bias information for indicating where a dimension starts in the one-dimensional bit vectors, storing left and right bounds and a size of the dimension wherein the bias information, the left and right bounds and the size are inputs to at least one of the read operation and the write operation to provide access to the aggregate data types in a plurality of different addressing methods may also be included. The step of mapping the control data flow graph onto hardware may include the step of synthesizing a read operation by employing a set of multiplexers connected in series wherein inputs and outputs of the multiplexers are dependent on bias information, left and right bounds and a size of each dimension being accessed during operations. The step of mapping the control data flow graph onto hardware may include the step of synthesizing a write operation by employing a plurality of multiplexers and decoding logic wherein inputs and outputs of the multiplexers are dependent on bias information, left and right bounds and
Barnfield Stephen
Bergamaschi Reinaldo A.
Jha Pradip K.
Mukherjee Rudra
Weaver John D.
F. Chau & Associates LLP
International Business Machines - Corporation
Kik Phallaka
Smith Matthew
LandOfFree
Synthesis of arrays and records does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Synthesis of arrays and records, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Synthesis of arrays and records will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2602211