Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-08-24
2004-02-17
Das, Chameli C. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S151000, C717S152000, C717S155000, C717S156000, C717S157000, C717S158000, C713S500000, C713S502000
Reexamination Certificate
active
06694512
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data processing device, data processing method and a supply medium and relates in particular to a data processing device, data processing method and a supply medium for performing superoptimization based on the number of clock pulses.
2. Description of Related Art
Ideally, the program (machine instructions) processed by the computer are processed as quickly as possible. In view of this need, optimization is performed to reduce as much as possible, the number of instructions or the number of clock pulses.
A method also referred to as superoptimization has further been proposed to achieve optimization by receiving an input consisting of a program written in machine language and checking all possible programs in order to find a program with the same functions as the original program. This superoptimization method has been disclosed for instance in “Superoptimizer—A Look at the Smallest Program, Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, 1987, PP.122-126” by Massalin, H.
In the superoptimization method described in the above mentioned paper however, a program (machine instructions) is found having the smallest number of instructions for calculating the supplied functions based on a search of all programs. However, with the establishment in recent years of pipeline type processors, scheduling the execution of instructions on the pipeline has become essential so that the program execution time is not always shortened even if the number of instructions has been reduced.
In view of the situation, this invention has the object of creating programs capable of faster processing by utilizing the number of clock pulses to perform superoptimization.
SUMMARY OF THE INVENTION
In view of the above problems with the conventional art, this invention has the object of providing an information processing device as claimed in claim
1
, comprising an analysis means to analyze the input, a generation means to generate instructions according to the results analyzed by said analysis means, an execution means to execute the instructions created by said generation means and a search means to search for an instruction having the smallest number of clock pulses required to execute the instruction with said execution means.
Another object of this invention is to provide a data processing device as claimed in claim
1
, wherein said generation means generates a directed acyclic graph according to the input and performs pruning according to the number of clock pulses.
A further object of this invention is to provide a data processing device as claimed in claim
1
, wherein said generation means generates a directed acyclic graph according to the input and performs pruning by means of the critical path.
A still further object of this invention is to provide a data processing method also containing an analysis step to analyze the input, a generation step to generate instructions according to the results analyzed in said analysis step, an execution step to execute the instructions generated in said generation step, and a search step to search for the instructions having the smallest number of clock pulses required to execute the instruction with said execution step.
A yet further object of this invention is to provide a data processing device as claimed in claim
2
, wherein said generation step generates a directed acyclic graph according to the input and performs pruning according to the number of clock pulses.
A still further object of this invention is to provide a data processing device as claimed in claim
2
, wherein said generation step generates a directed acyclic graph according to the input and performs pruning by means of the critical path.
An even further object of this invention is to provide a supply medium to provide a program capable of being loaded by a computer to run the data processing device to execute processing including an analysis step to analyze the input, a generation step to generate instructions according to the results analyzed in said analysis step, an execution step to execute the instructions generated in said generation step, and a search step to search for the instructions having the smallest number of clock pulses required to execute the instruction with said execution step.
A still further object of this invention is to provide a supply medium as claimed in claim
3
, wherein said generation step generates a directed acyclic graph according to the input and performs pruning according to the number of clock pulses.
A yet further object of this invention is to provide a supply medium as claimed in claim
3
, wherein said generation step generates a directed acyclic graph according to the input and performs pruning according to the critical path.
REFERENCES:
patent: 4365311 (1982-12-01), Fukunaga et al.
patent: 5202975 (1993-04-01), Rasbold et al.
patent: 5287490 (1994-02-01), Sites
patent: 5307478 (1994-04-01), Rasbold et al.
patent: 5317740 (1994-05-01), Sites
patent: 5491823 (1996-02-01), Ruttenberg
patent: 5507030 (1996-04-01), Sites
patent: 5680626 (1997-10-01), Chu et al.
patent: 5889999 (1999-03-01), Breternitz, Jr. et al.
patent: 5894576 (1999-04-01), Bharadwaj
patent: 5923883 (1999-07-01), Tanaka et al.
patent: 6006033 (1999-12-01), Heisch
patent: 6026497 (2000-02-01), Myszewski
patent: 6058266 (2000-05-01), Megiddo et al.
patent: 6126329 (2000-10-01), Bennett et al.
patent: 6131189 (2000-10-01), Chow et al.
patent: 6189141 (2001-02-01), Benitez et al.
patent: 6219833 (2001-04-01), Solomon et al.
patent: 6233678 (2001-05-01), Bala
patent: 6286132 (2001-09-01), Tanaka et al.
patent: 6381739 (2002-04-01), Breternitz et al.
patent: 6456996 (2002-09-01), Crawford et al.
patent: 6539542 (2003-03-01), Cousins et al.
TITLE: Optimally Profiling and Tracing Programs, author: Ball et al, ACM, 1994.*
TITLE: Introducing a CPS Style Optimizer into an Existing Compiler, author: Ferrante et al, ACM, Dec. 1996.*
TITLE: Complete Removal of Redundant Expressions, author: Bodik et al, ACM, 1998.*
Title: Eliminating branches using a superoptimizer and the GNU C Compiler, ACM sigplan, author: Granlund et al, 1992.*
Title: Placement for clock period minimization with multiple wave propagation, ACM/IEEE, author: Joy et al, 1991.*
H. Massalin, “Superoptimizer—A Look at the Small Program,” Proceedings of the Second International Conference on Architectural Support for Programming Language and Operating Systems, Oct. 5, 1987, pp. 122-126.
Bell Boyd & Lloyd LLC
Das Chameli C.
Sony Corporation
LandOfFree
Data processing device, data processing method and supply... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing device, data processing method and supply..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing device, data processing method and supply... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3277753