Data processing: measuring – calibrating – or testing – Measurement system – Performance or efficiency evaluation
Reexamination Certificate
2001-03-30
2002-07-09
Bui, Bryan (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system
Performance or efficiency evaluation
C702S182000, C712S223000, C706S013000
Reexamination Certificate
active
06418399
ABSTRACT:
BACKGROUND OF THE INVENTION
Field of the Invention
The invention relates to a method for executing individual algorithms using a reconfigurable circuit, and to an apparatus for carrying out such a method.
The size and hence resources of reconfigurable circuits are limited. Often, the resources of such a circuit are not sufficient to execute two or more algorithms at the same time or one individual, relatively large algorithm.
A relatively large algorithm, which requires more resources than are available in the reconfigurable circuit and which needs to be executed using this circuit alone, is generally broken down into a plurality of subalgorithms, each of which itself represents a respective algorithm in turn and is chosen such that the circuit has sufficient resources for executing this subalgorithm.
These subalgorithms are executed in the circuit successively in time such that each of these subalgorithms is executed using the circuit which is configured for this subalgorithm and that, after execution of one subalgorithm, a succeeding subalgorithm is executed, the circuit being reconfigured for this succeeding subalgorithm after execution of this one subalgorithm, in so far as this succeeding subalgorithm is different from this one subalgorithm.
Data-dependent branch operations mean that it is not until at the time of execution, i.e. during the actual execution or processing of the larger algorithm, that it is known which of these subalgorithms of the larger algorithm is actually needed. At the compile time, i.e. before the time of execution, there is no indication available of which subalgorithms and hence configurations of the circuit are actually needed.
One way of still executing the larger algorithm using the reconfigurable circuit which has too few resources for this purpose is to configure this circuit individually for all subalgorithms of the larger algorithm in succession, for example on the basis of a prescribed program flow. In this context, only the configured subalgorithms which are needed are executed. If a subalgorithm is not needed, the configuration for this subalgorithm is erased without executing this subalgorithm.
Configuring the circuit during the time of execution for an unneeded part of the larger algorithm costs valuable execution time. A method is therefore required which recognizes and loads the necessary configurations in good time during execution.
M. Vasilko and Djamel Ait-Boudaoud: “Architectural Synthesis Techniques for Dynamically Reconfigurable Logic” in Reiner W. Hartenstein, Manfred Glesner (Eds.): “Field-Programmable Logic, Smart Applications, New Paradigms and Compilers”, 6th Int'l Workshop on Field-Programmable Logic and Applications, FPL '96, Darmstadt, Germany, Sep. 23-25, 1996, Proceedings, Springer-Verlag, pp. 290-296 discloses the practice of calculating for the compile time the order on the basis of which the individual subalgorithms of a larger algorithm are configured in a circuit. In this case, a reconfiguration controller is obtained in which the sequence on the basis of which the subalgorithms are configured is fixed. In this case, the result of a branch operation is required in order to determine the correct subalgorithm which is to be configured.
SUMMARY OF THE INVENTION
The object of the present invention is to provide a method of processing individual algorithms with a reconfigurable circuit and an apparatus for carrying out the method which overcome the above-noted deficiencies and disadvantages of the prior art devices and methods of this general kind, and which further enable shortening the execution time in a method for executing individual algorithms using the reconfigurable circuit which has sufficient resources for executing each individual algorithm, and in which the algorithms which are to be executed are configured and executed in the circuit successively in time.
With the above and other objects in view there is provided, in accordance with the invention, a method of executing individual algorithms, which comprises:
providing a reconfigurable circuit with sufficient resources for executing each individual algorithm of a plurality of algorithms, and executing a plurality of algorithms in the circuit successively in time; and
during execution of a given algorithm, reconfiguring the circuit for a following algorithm so far as the following algorithm is different from the given algorithm currently being executed.
On the basis of this solution, each algorithm is executed using the circuit which is configured for this algorithm, and, during execution of one algorithm, a succeeding algorithm is executed, the circuit being reconfigured for this succeeding algorithm during actual execution of this one algorithm, at least in so far as this succeeding algorithm is different from this one algorithm.
On this basis, the following algorithm is advantageously configured in the circuit during the actual time of execution of an algorithm and may, under some circumstances, start to operate during the actual time of execution of the one algorithm. However, a prerequisite for this is a circuit which can be dynamically configured in such a manner. Suitable circuits for this are particular products from the company Xilinx, e.g. the chip XC62xx, which already afford the basic opportunities for such dynamic configuration. The chips can be configured in the same way as writing to a memory. A configuration memory cell is addressed and then has information written to it. Accordingly, the chip can be configured during the time of execution.
With the above and other objects in view there is also provided, in accordance with an alternative mode, a method of executing individual algorithms, which comprises:
providing a reconfigurable circuit with sufficient resources for executing each individual algorithm of a plurality of algorithms, and executing a plurality of algorithms in the circuit successively in time;
reconfiguring the circuit for a following algorithm during and/or after execution of a given algorithm, at least in so far as the following algorithm to be executed is different from the given algorithm; and
if a variety algorithms may need to be executed after execution of the given algorithm, reconfiguring the circuit for a following algorithm having a greatest probability of requiring execution after the given algorithm.
On the basis of this solution, each algorithm is executed using the circuit which is configured for this algorithm, and, during and/or after execution of one algorithm, a succeeding algorithm is executed, the circuit being reconfigured for this succeeding algorithm during and/or after execution of this one algorithm, at least in so far as this succeeding algorithm is different from this one algorithm, where at least one particular algorithm has at least two associated algorithms, each of which has a respectively different particular probability of being suitable for being executed as succeeding algorithm during and/or after execution of this particular algorithm, and where, of these associated algorithms, the one which is actually executed as the succeeding algorithm is the one which has the greatest probability.
Unlike the known method specified above, in which the order of configuration of the individual sub-algorithms of a larger algorithm is calculated for the compile time, and which is a static method, this method has the advantage that it is possible to infer an algorithm which is to be executed as succeeding algorithm for a particular algorithm earlier, which increases the parallelism between configuration and calculation, and hence the system performance, in particular reduces the execution time.
In this method, the circuit can be configured for a succeeding algorithm after execution of an algorithm, and/or it can be configured for a succeeding algorithm during execution of an algorithm, i.e. can be configured dynamically.
Irrespective of whether a circuit is configured for the succeeding algorithm after or during execution of an algorithm, this method is itself a dynamic method, since the succeedin
Buchenrieder Klaus
Kress Rainer
Bui Bryan
Greenberg Laurence A.
Infineon - Technologies AG
Lerner Herbert L.
Stemer Werner H.
LandOfFree
Method for executing individual algorithms using a... 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 for executing individual algorithms using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for executing individual algorithms using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2891094