Data processing device, method of executing a program and method of compiling

• US 6,615,333 B1
• Filed: 05/03/2000
• Issued: 09/02/2003
• Est. Priority Date: 05/06/1999
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Hoogerbrugge, Jan, Augusteijn, Alexander
• Primary Examiner(s): Nguyen, Hiep T.
• Application Number:
  US09/563,369
• Time in Patent Office: 1,217 Days
• Field of Search: 711/169, 712/214, 712/215, 712/216, 712/226
• US Class Current: 711/169
• CPC Class Codes: G06F 9/3834 Maintaining memory consistency
• CPC Class Codes: G06F 9/3867 using instruction pipelines

Abstract

A data processing device has a circuit for correcting an effect of executing memory access instructions out of order with respect to one another in a pipeline. A detector detects whether a same memory location is addressed by a first and second memory address used to access memory for a first and second memory access instruction that are processing at a predetermined relative distance in the pipeline respectively. A correction circuit modifies data handling in a pipeline stage processing the first memory access instruction when the detector signals the addressing of the same memory location and the first and/or second memory access instruction programs a command to compensate said effect of out of order execution of the first memory access instruction with respect to said second memory access instruction.

Claims

1. A data processing device having an instruction set with memory access instructions, the device comprising a circuit for correcting an effect of executing the memory access instructions out of order with respect to one another, the device comprising a pipeline for instruction execution, the device comprising:

a detector for detecting whether a same memory location is addressed by a first and second memory address used to access memory for a first and second memory access instruction that are processing at a predetermined relative distance in the pipeline respectively;

a correction circuit for modifying data handling in a pipeline stage processing the first memory access instruction when the detector signals said addressing of the same memory location and for causing the first and/or second memory access instruction programs a command to compensate said effect of out of order execution of the first memory access instruction with respect to said second memory access instruction.

2. A data processing device according to claim 1, the instruction set comprising a class of memory access instructions for the same type of access operation, different instructions of the class commanding compensation of said effect for different sets of one or more relative distances.

3. A data processing device according to claim 1, the first and second memory access instruction being a memory load and a memory store instruction respectively, the correction circuit substituting data written to memory by the memory store instruction for data read from memory by the memory load instruction when the memory store instruction is processed in a further pipeline stage upstream from said pipeline stage that processes the memory load access instruction.

4. A data processing device according to claim 1, the first and second memory access instruction both being memory store instructions, the correction circuit preventing a write to memory by the first instruction when the second instruction is processed in a further pipeline stage downstream from the pipeline stage that processes the first instruction.

5. A data processing device according to claim 1, the first and second memory access instruction both being memory store instructions, the correction circuit substituting data written by the second instruction into data that is to be written to memory by the first memory access instruction when the second instruction is processed in a further pipeline stage downstream from the pipeline stage that processes the first instruction.

6. A method of executing a program in a data processing device, the method comprising

pipeline execution of instructions from the program in an instruction execution pipeline;

detection whether a first and second memory access instruction in a first and a second predetermined stage of the pipeline address a same memory location;

modifying data handling by the first memory access instruction in the pipeline if said addressing the same memory location is detected by causing the first and/or second memory access instruction programs a command to compensate an effect of out of order execution of the first memory access instruction with respect to said second memory access instruction.

7. A method according to claim 6, the instruction set comprising a class of memory access instructions for the same type of access operation, different instructions of the class commanding compensation of said effect for different sets of relative distances between the first and second predetermined stage.

8. A method according to claim 6, the first and second memory access instruction being a memory load and a memory store instruction respectively, the first stage of the pipeline being downstream from the second stage of the pipeline, said modifying comprising substituting data written to memory by the memory store instruction for data read from memory by the memory load instruction.

9. A method according to claim 6, the first and second memory access instruction both being memory store instructions, the first stage of the pipeline being upstream from the second stage of the pipeline, the modifying comprising preventing a write to memory by the first instruction.

10. A method according to claim 6, the first and second memory access instruction both being memory store instructions, the first stage of the pipeline being upstream from the second stage of the pipeline, the modifying comprising substituting data written by the second instruction into data that is to be written to memory by the first memory access instruction.

11. A method of compiling a program for a pipelined processor, wherein the processor has an instruction set with a normal version and an out of order version of a first memory access instruction, the out of order version commanding modified execution of the first memory access instruction or a second memory access instruction, so as to compensate an effect of out of order execution of the first and second memory access instruction, in case the first and second memory access instruction are at a predetermined position relative to one another in the pipeline and address a same memory location, the method comprising

receiving a program with memory access instructions and information specifying an order of execution of the memory access instructions;

scheduling an instruction execution sequence, wherein pairs of memory access instructions are scheduled out of order with respect to one another, at a distance of a number of instruction cycles that is smaller than a length of the pipeline;

selecting a version among the versions of the memory access instructions, depending on whether the memory access instructions are part of such pairs.

12. A method according to claim 11, wherein the version is selected dependent on the distance.