Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-08-20
2001-10-02
Phan, Trong (Department: 2818)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06298471
ABSTRACT:
BACKGROUND OF THE INVENTIONS
1. Field of the Invention
These inventions relate to processor design, and more specifically to interconnection of hardware components in processor design, such as for systolic processors and application specific integrated processors (ASIPs).
2. Related Art
Processor design is a very time intensive and expensive process. For new and unique processor designs, no automated design techniques exist for selecting and designing the mix of processor components or for efficiently interconnecting those components that would be incorporated into the final processor design. While there exist algorithms incorporated into software packages that can help in designing new processors, such software packages do not give a result which is a final design, let alone an optimal design. Typically, those software packages provide approximate solutions to a design problem, typically leading to additional design effort and over-design to account for the lack of precision in those software packages. Additionally, the design process may start entirely from scratch, which would result in substantial time being consumed analyzing possible design configurations before designing the details of the processor. On the other hand, designing a new processor using preexisting designs necessarily incorporates the design benefits and flaws of the preexisting design, which may or may not be acceptable or optimal for the new design.
All conventional processor design software packages are heuristic in nature. In other words, they rely on design criteria and/or methods that in the past have proven more effective than other criteria or methods. However, in order to apply to more than one processor design or design methodology, such design criteria and methods must be sufficiently general to provide predictable results. Therefore, such heuristic software packages provide relatively high-level solutions without a complete contribution to details of the design. Additionally, heuristic software packages necessarily lead to significant trial and error in an attempt to optimize the processor design. Consequently, design of new processors is time intensive and expensive.
Processors are often designed to incorporate pipelined data paths to speed processing throughput, reduce initiation intervals and to optimize use of the various function units, such as adders, multipliers, comparators, dividers, registers and the like. These data paths are formed from an interconnected assembly of function units and register files. The function units and register files may be interconnected by busses. Because these data paths may include a large number of function units, register files and bus segments, the job of selecting the function units, register files and bus segments is very difficult, to say the least. The task is made more difficult if one desires to find an efficient configuration.
Pipelined data paths are particularly useful in processing iterative instructions, such as those found in instruction loops, and especially nested instruction loops. When considering a subset of situations where the instruction loops are known, such as those used with embedded processors, the task of designing the optimal, low-cost processor still exists because of the large number of different function units, register configurations and bus configurations that are possible. Heuristic software design solutions used for designing processors are not suitable for finding solutions to such multi-dimensional problems. Because there are so many variables to consider, it is too difficult to optimize all of variables to arrive at a suitable solution without great expenditure of time and effort.
SUMMARY OF THE INVENTIONS
The present inventions provide methods and apparatus for more easily and efficiently producing computing systems, for example those incorporating processor arrays having processors with function or execution units, register files, bus arrays, and the like. These methods and apparatus reduce the time required for designing these processors, and reduce the amount of trial and error used in processor design. They find more efficient configurations for interconnecting function units and registers, and they can do so much faster and more reliably than conventional methods and apparatus. They also reduce some of the costs associated with starting the design of a new processor from scratch, which often may be necessary in the design of embedded processors.
These and other aspects of the present inventions are provided by methods and apparatus for assembling a set of hardware component and bus assemblies, such as for an embedded processor having pipelined data paths. The hardware components could be function units such as adders, multipliers, arithmetic logic units, registers and the like. The methods could be carried out on, and the apparatus could include, any manner of equipment, such as computers and other processors including mainframes, workstations, and the like, as well as apparatus containing instructions or data for use in controlling such processors, such as disk drives, removable storage media, and temporary storage. In one aspect of the present inventions, the process includes identifying busses and hardware components to which each bus is assigned for a given operation, and identifying bus assignments for which operations occur on the same hardware component. In the preferred embodiment, at least some of the hardware components for which different operations occur on the same hardware component are assigned to the same bus. With this procedure, the process of designing inter-connects between hardware components is easier and more reliable. The resulting architecture of the processor is improved and the layout of the bus structure is simplified. By way of a simple example, some design techniques may assign different busses to the same set of hardware components where data is being transferred between the hardware components within the set during two different cycles. The present procedure more easily identifies such redundancy and assigns a single bus to the set of hardware components, even though the design may treat the data transfers as separate operations. Therefore, identifying redundant bus structures between hardware components related by common data transfers occurring over different cycles allows for consolidation of those redundant bus structures.
In another preferred form of the inventions, the process includes the steps of comparing a table of bus assignments for each of a number of operations to be carried out over a number of known cycles. The table may be a matrix or other representation of a relationship between a set of busses and hardware components. The hardware components may be function or execution units and registers or register files, or other comparable components. In the preferred embodiment, different matrices will represent the relationships for different cycles. The matrices, or other representations of the relationships, are then processed to identify potential redundancies in the assignment of a bus to one or more hardware components. The bus assignments are then redistributed to reduce or eliminate the redundancies. In one preferred embodiment, the matrices are processed two at a time to optimize the bus assignment and interconnect configuration by solving a conventional assignment problem. For example, the matrix product of a first matrix with the transpose of a second matrix produces a series of numbers in a correlation matrix whose diagonal represents busses having common connections. If the columns of the transposed matrix, representing the bus connections for that matrix, are permuted until the cross product produces a diagonal whose sum is a maximum, the permuted matrix producing the maximum has a bus connection configuration which is optimum relative to the bus configuration of the first matrix. Thus, if the busses and hardware components are connected in accordance with the first matrix and the permuted second matrix for the two cycles represented by those matrices, a more
Hewlett--Packard Company
Phan Trong
LandOfFree
Interconnect minimization in processor design does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interconnect minimization in processor design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interconnect minimization in processor design will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2605345