Method of using primary and secondary processors

Details Method of using primary and secondary processors Method of using primary and secondary processors

1998-12-11

2001-04-17

Powell, Mark R. (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

C717S152000, C712S015000, C712S018000, C712S023000, C712S034000, C712S201000

Reexamination Certificate

active

06219833

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the compilation and execution of source code for a processor architecture consisting of a primary processor and one (or more) secondary processors. The invention is particularly, though not exclusively, relevant to the architectures employing a reconfigurable secondary processor.
BACKGROUND OF THE INVENTION
A primary processor—such as a Pentium processor in a conventional PC (Pentium is a Trade Mark of Intel Corporation)—has evolved to be versatile, in that it is adapted to handle a wide range of computational tasks without being optimised for any of them. Such a processor is thus not optimised to handle efficiently computationally intensive operations, such as parallel sub-word tasks. Such tasks can cause significant bottlenecks in the execution of code.
An approach taken to solve this problem is the development of integrated circuits specifically adapted for particular applications. These are known as ASICs, or application-specific integrated circuits. Tasks for which such an ASIC is adapted are generally performed very well: however, the ASIC will generally perform poorly, if at all, on tasks for which it is not configured. Clearly, a specific IC can be built for a particular application, but this is not a desirable solution for applications that are not central to the operation of a computer, or are not yet determined at the time of building the computer. It is thus particularly advantageous for an ASIC to be reconfigurable, so that it can be optimized for different applications as required. The commonest form of architecture for such devices is the field programmable gate array (FPGA), a fine-grained processor structure which can be configured to have a structure which is suited to any given application. Such structures can be used as independent processors in suitable contexts, but are also particularly appropriate to use as coprocessors. Such configurable coprocessors have the potential to improve the performance of the primary processor. For particular tasks, code run inefficiently by the primary processor can be extracted and run more efficiently in an adapted coprocessor which has been optimised for that application. With continued development of such “application-specific” secondary processors, the possibility of improving performance by extracting difficult code to a custom coprocessor becomes more attractive. A particularly important example in general computing is the extraction of loop bodies in image handling.
To obtain the desired efficiency gains, it is necessary to determine as effectively as possible. how code is to be divided between primary and secondary processors, and to configure the secondary processor for optimal execution of its assigned part of the code. One approach is to mark the code appropriately on its creation for mapping to coprocessor structures. In “A C++ compiler for FPGA custom execution units synthesis”, Christian Iseli and Eduardo Sanchez, EEE Symposium on FPGAs for Custom Computing Machines, Napa, California, April 1995, an approach is employed which involves mapping of C++ to FPGAs in VLIW (Very-Long Instruction Word) structures after appropriate tagging of the initial code by the programmer. This approach relies on the initial programmer making a good choice of code to extract initially.
An alternative approach is to assess the initial code to determine which the most appropriate elements to direct to the secondary processor will be “Two-Level Hardware/Software Partitioning Using CoDe-X”, Reiner W. Hartenstein, Jügen Becker and Rainer Kress, in Int. IEEE Symposium on Engineering of Computer Based Systems (ECBS), Friedrichshafen, Germany, March 1996, discusses a codesign tool which incorporates a profiler to assess which parts of an initial code are suitable for allocation to a coprocessor and which should be reserved for the primary processor. This is followed by an iterative procedure allowing for compilation of a subset of C code to a reconfigurable coprocessor architecture so that the extracted code can be mapped to the coprocessor. This approach does expand the usage of secondary processors, but does not fully realize the potential of reconfigurable logic.
Comparable approaches have been proposed in the BRASS research project at the University of Berkeley. An approach discussed in “Datapath-Oriented FPGA Mapping and Placement”, Tim Callahan & John Wawrzynek, a poster presented at FCCM'97, Symposium on Field-Programmable Custom Computing Machines, April 16-18 1997, Napa Valley, Calif. (currently available on the World Wide Web at http:www.cs.berkeley.edu/projects/brass/tjc fccm-poster thumb.ps), uses template structures representative of an FPGA architecture to assist in the mapping of source code on to FPGA structures. Source code samples are rendered as directed acyclic graphs, or DAGs, and then reduced to trees. These and other basic graph concepts are set out, for example, in “High Performance Compilers for Parallel Computing”, Michael Wolfe, pages 49 to 56, Addison-Wesley, Redwood City, 1996, but a brief definition of a DAG and a tree follows here.
A graph consists of a set of nodes, and a set of edges: each edge is defined by a pair of nodes (and can be considered graphically as a line joining those nodes). A graph can be either directed or undirected: in a directed graph, each edge has a direction. If it possible to define a path within a graph from one node back to itself, then the graph is cyclic: if not, then the graph is acyclic. A DAG is a graph that is both directed and acyclic: it is thus a hierarchical structure. A tree is a specific kind of DAG. A tree has a single source node, termed “root”, and there is a unique path from root to every other node in the tree. If there is an edge X∴Y in a tree, then node X is termed the parent of Y, and Y is termed the child of X. In a tree, a “parent node” has one or more “child nodes”, but a child node can have only one parent, whereas in a general DAG, a child can have more than one parent. Nodes of a tree with no children are termed leaf nodes.
In the work of Tim Callahan & John Wawrzynek, these trees are matched with the FPGA structure by use of a “tree covering” program called lburg. lburg is a generally available software tool, and its application is described in “A Retargetable C Compiler: Design and Implementation”, Christopher W. Fraser and David R. Hanson, Benjamin/Cummings Publishing Co., Inc., Redwood City, 1995, especially at pp 373-407. lburg takes as input the source code trees and partitions this input into chunks that correspond to instructions on the target processor. This partition is termed a tree cover. This approach is essentially determined by the user-defined patterns allowable for a chunk, and is relatively complex: it involves a bottomup matching of a tree with patterns, recording all possible matches, followed by a top-down reduction pass to determine which match of patterns provides the lowest cost. Again, this approach requires a significant initial constraint in the form of the predefined set of allowable patterns, and does not filly realize the possibilities of a reconfigurable architecture.
There is thus a need to develop techniques and approaches to further improve computational efficiency of systems involving a primary and secondary processor, by which an optimal choice can be made for allocation of code to a secondary processor, which can then be configured as “efficiently as possible to run the extracted code, with a view to maximising the performance efficiency of the primary and secondary processor system in execution of input code.
SUMMARY OF THE INVENTION
Accordingly, the invention provides a method of compiling source code to a primary and a secondary processor, comprising: selective extraction of dataflows from the source code;transformation of the extracted dataflows into trees; matching of the trees against each other to determine minimum edit cost. relationships for transformation of one tree into another;determining a group or a plurality of grou

Affiliated with

Also associated with

Rating

Method of using primary and secondary processors does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of using primary and secondary processors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of using primary and secondary processors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2471480