Patent
1995-09-14
1998-01-27
Lall, Parshotam S.
395706, 395709, G06F 940
Patent
active
057129967
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
Modern microprocessors mostly comprise a plurality of functional units, which are termed processing units below, which can execute machine instructions in parallel. This property is designated as super-scalar. In order to utilize all the processing units, super-scalar processors would have to provide in one clock cycle a plurality of instructions as a group for execution. Since, however, processing units can mostly execute only specific types of machine instructions such as, for example, load/store or floating-position instructions, when providing instructions it must already be ensured that all the instructions of one group can be executed on appropriate processing units. When grouping instructions, it is necessary, in addition, to take account of data and control-flow dependences between the instructions, in order to satisfy the semantics of the program. Furthermore, it is essential to minimize pipeline conflicts within the processing units, in order to achieve as high as possible a throughput for each individual processing unit.
The grouping of instructions thus plays a substantial role in the effective performance of a super-scalar microprocessor. It is essential to arrange the instructions within an instruction sequence such that as many instructions as possible can be executed in parallel. For this reason, a plurality of approaches to the solution have already been developed and published, which can be subdivided into static and dynamic scheduling processes.
In the case of dynamic scheduling processes, instructions are regrouped during execution. This is mostly performed with the aid of special hardware such as, for example, "score boards" or "reservation tables". Appropriate techniques are described, inter alia, in Tomasulo, R. M., An Efficient Algorithm for Exploring Multiple Arithmetic Units, IBM Journal of Research and Development, January 1967, pages 25 to 33. In part, they require substantial additional outlay on hardware and mostly operate only on a permanently predefined number of instructions (instruction window).
Static scheduling processes already attempt at the compiling time to generate an instruction sequence in .which pipeline conflicts are minimized and as many instructions as possible can be executed in parallel. Various algorithms for this have been developed, in particular for processors having an instruction pipeline, as well as in the field of microprogramming and for VLIW architectures. A survey of the algorithms for super-pipeline architectures is given, for example, in Krishnamurthy, S. M., A Brief Survey of Papers on Scheduling for Pipelined Processors; SIGPLAN Notices, Vol. 25, No. 7, 1990, pages 97-106. These algorithms heuristically generate an instruction sequence with as few pipeline conflicts as possible, although conflicts between data-independent instructions are mostly left out of account.
The problems of instruction grouping, as they occur in super-scalar processors, are treated in terms of formulation in algorithms for code generation for VLIW architectures. In particular, use is made in this case of global scheduling processes such as trace scheduling or percolation scheduling which can shift instructions beyond boundaries of basic blocks (for example, Fisher, J. A., Trace Scheduling: A Technique for Global Microcode Compaction, IEEE Trans. on Comp., July 1981, pages 478-490). By contrast with super-scalar architectures, in the case of VLIW architectures, however, statically long instruction words must already have been generated, that is to say the individual instructions are already assigned at the compiling time to the various processing units, and the instructions of an instruction word are executed synchronously. In this regard, super-scalar architectures offer more free spaces, since in a final analysis groupings of instructions are not undertaken until the run time, and not all the instructions of a group are executed synchronously.
SUMMARY OF THE INVENTION
The object on which the invention is based consists in specifying a f
REFERENCES:
patent: 5021945 (1991-06-01), Morrison et al.
patent: 5317743 (1994-05-01), Imai et al.
patent: 5450585 (1995-09-01), Johnson
"Efficient Instruction Scheduling for a Pipelined Architecture" by P.B. Gibbons and S.S. Muchnick, Sigplan Notices, vol. 21, No. 7, Jul. 1986, pp. 11-16.
"Instruction Scheduling for the IBM RISC System/6000 Processor", by H.S. Warren, Jr., IBM Journal of Research and Development, vol. 34, No. 1, Jan. 1990, pp. 85-92.
"Performance Evaluation for Various Configuration of Superscalar Processors", by A. Inoue and K. Takeda, Computer Architecture News, vol. 21, No. 1, Mar. 1993, pp. 4-11.
"An Efficient Algorithm for Exploiting Multiple Arithmetic Units", by R.M. Tomasulo, IBM Journal of Research and Development, Jan. 1967, pp. 25-33.
"A Brief Survey of Papers on Scheduling for Pipelined Processors", by S.M. Krishnamurthy, Sigplan Notices, vol. 25, No. 7, Jul. 1990, pp. 97-100.
"Trace Scheduling: A Technique for Global Microcode Compaction", by J.A. Fisher, IEEE Transactions on Computers, vol. 30, No. 7, Jul. 1981, pp. 478-490.
Lall Parshotam S.
Patel Gautam R.
Siemens Aktiengesellschaft
LandOfFree
Process for dividing instructions of a computer program into ins does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for dividing instructions of a computer program into ins, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for dividing instructions of a computer program into ins will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-349647