Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1999-02-25
2001-08-28
Pan, Daniel H. (Department: 2171)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C712S024000, C712S216000
Reexamination Certificate
active
06282708
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method for structuring a multi-instruction computer program as containing a plurality of basic blocks, that each compose from internal instructions and external jumps organized in an internal directed acyclic graph. Structuring such multi-instructional computer programs for faster execution is a continual target of industry. A particular feature is to enable parallel processing on the level of a single instruction, which has become feasible by the introductions of so-called Very Long Word Instruction (VLIW) processors and so-called SuperScalar processors. State of the art is the book by David A. Patterson & John L. Hennessy, Computer Architecture, a Quantitative Approach, Morgan Kaufmann 1996, p. 240-288, herein incorporated by reference. Patterson and Hennessy describes how VLIWs use multiple, independent functional unit which packages multiple operations into one long instruction. The parallelism in Superscalars may be attained in a program of which the scheduling is being executed at actual execution. Alternatively, in VLIW, the effects may be partially exploited by scheduling at compiling time. A general rule is that parallelism may be exploited better when a greater number of operations can be processed coexistently, given the available extent of hardware facilities. Such amount of operations will hereinafter be called a scheduling unit or basic block. In its most simple embodiment such a scheduling unit may be organized on a Directed Acyclic Graph (DAG) that consists of internal operations and one or more external (conditional) jumps to other scheduling units. The graph may be reached from one or more other graphs via respectively associated input operations, that read an initial value from an associated specific register. Likewise, output will also involve a write operation to a possibly selectible specific register.
P. Y. T. Hsu and E. S. Davidson, Highly Concurrent Scalar Processing, Univ. of Illinois at Urbana-Champaign, Proc. 13th Ann. Int. Symp. on Computer Architecture, June 1986, p.386-395, have proposed to expand the size of scheduling units by introducing guarded instructions to reduce the penalty of conditional branches, in combination with decision tree (dtree) scheduling.
Alternatively, S. A. Mahlke et al, Effective Compiler Support for Predicated Execution Using the Hyperblock, Univ. of Illinois at Urbana-Champaign, Proc. 25th Ann. Int. Workshop on Microprogramming, Portland OR Dec. 1992, p.45-54, have mapped their basic blocks on a linear chain of basic blocks by duplicating basic blocks, so that each internal basic block has only a single predecessor.
However, the present inventors have found that in many cases the above guarding may be amended as well as amplified to attain an improved degree of parallelism, by mapping a Directed Acyclic Graph of basic blocks on a single higher level basic block for inclusion in a higher level tree of higher level basic blocks.
SUMMARY TO THE INVENTION
In consequence, amongst other things, it is an object of the present invention to introduce a combination of guarding and joining in a decision tree to link multiple basic blocks into a single higher level basic block. Now therefore, according to one of its aspects the invention is characterized by executing a guarding on successor instructions that each collectively emanate from a respectively associated single predecessor instruction, all guardings being mutually exclusive with respect to their respectively associated basic block, unconditionally joining a subset of joined instructions that converge onto a single join/target instruction, by letting each respective instruction in the subset of joined instructions being executed under mutually non-related conditions, specifying all operations with respect to a jump instruction specifying all operations that must have been executed previously, and linking various basic blocks comprising subsets of successor instructions in a directed acyclic graph which allows parallel execution of any further subset of instructions contained therein and being usable as a single higher level basic block for inclusion in a higher level tree of higher level basic blocks.
Advantageously, a method according to the invention implements one or more conditional jumps between an overall predecessor non-jump instruction of the internal Directed Acyclic Graph, and displacing said external jump instruction towards a lower end of its chain. In this manner, both predecessors and jumps are combined in an advantageous method.
The invention also relates to a programmed processor attained by loading with a program produced by executing a method as claimed in claim
1
. Further advantageous aspects of the invention are recited in dependent Claims. The invention may be applied to VLIW processors as explained supra, but also on so-called Superscalar processors, of which the commercially available Pentium Pro controller is a prime example.
REFERENCES:
David A. Patterson & John L. Hennessy, Computer Architecture A Quantitative Approach, Morgan Kaufmann 1996, p. 240-288.
P.Y.T. Hsu and E.S. Davidson, Highly Concurrent Scalar Processing, Univ. of Illinois at Urbana-Champaign, Proc. 13th Ann. Int. Symp. on Computer Architecture, Jun. 1986, p. 386-395.
S. A. Mahlke et al, Effective Compiler Support or Predicated Execution Using the Hyperblock, Univ. of Illinois at Urbana-Champaign, Proc. 2th Ann. Int. Workshop on Microprogramming, Portland, OR, Dec. 1992, p. 45-54.
Augusteijn Alexander
Hoogerbrugge Jan
Chen Te Yu
Pan Daniel H.
U.S. Philips Corporation
LandOfFree
Method and processor for structuring a multi-instruction... 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 and processor for structuring a multi-instruction..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and processor for structuring a multi-instruction... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2509385