Apparatus for reducing memory fetches in program loops

Claim 2

A programmed digital data processor including a main memory and two auxiliary memories comprising: means for extracting from each main memory a transferee instruction to which a transfer is allowed by other, transfer, instructions; means for storing a selected portion of said transferee instruction in one of said two auxiliary memories; means for incrementing and then storing the incremented main memory address of said transferee instruction in the other of said two auxiliary memories; means for extracting from said main memory a transfer instruction whose designation is said transferee instruction; and means responsive to said transfer instruction for retrieving both said stored selected portion of said transferee instruction and said incremented stored address from said auxiliary memories.

Claim 3

storing the address of the second instruction of each said loop in a local, fast-access storage medium;

Claim 4

storing the address of the second instruction of each said loop in a local, fast-access storage medium;

Claim 5

storing each of said detected transferee instructions and the addresses of the next sequential instruction following each of said detected transferee instructions in a high-speed memory;

Claim 6

storing each of said detected transferee instructions and the addresses of the next sequential instruction following each of said detected transferee instructions in a high-speed memory;

Claim 7

Apparatus as in claim 1 wherein said auxiliary memories comprise last-in-first-out buffers.

Claim 8

storing said detected transferee instruction and the address of the next sequential instruction following said detected transferee instruction in a high-speed memory;

Claim 9

storing said detected transferee instruction and the address of the next sequential instruction following said detected transferee instruction in a high-speed memory;

Claim 10

executing program instructions until a conditional transfer instruction has been executed;

Claim 11

executing program instructions until a conditional transfer instruction has been executed;

Claim 12

Apparatus for decreasing the execution time of program loops in a digital computer comprising: means for temporarily storing both the first, or transferee, instruction in each of said program loops and the address of the next sequential instruction following each said transferee instruction; and means responsive to the last, or conditional transfer, instruction in each of said program loops for fetching both said transferee instruction and said address from said temporary storage means.

Claim 13

Apparatus for decreasing the execution time of program loops in a digital computer comprising: means for temporarily storing both the first, or transferee, instruction in each of said program loops and the address of the next sequential instruction following each said transferee instruction; and means responsive to the last, or conditional transfer, instruction in each of said program loops for fetching both said transferee instruction and said address from said temporary storage means.

Claim 14

executing program instructions until a conditional transfer instruction has been executed;

Claim 15

executing program instructions until a conditional transfer instruction has been executed;

Claim 16

utilizing said first instruction and said address of said second instruction from said local fast-access storage medium each time said loop is traversed.

Claim 17

utilizing said first instruction and said address of said second instruction from said local fast-access storage medium each time said loop is traversed.

Claim 18

determining whether said execution of said conditional transfer instruction has resulted in the generation of said terminating signal;

Claim 19

determining whether said execution of said conditional transfer instruction has resulted in the generation of said terminating signal;

Claim 20

In combination with a digital computer of the type wherein the first, or transferee, instruction in each program loop contains a suffix portion, the improvement which comprises: means for Using said suffix portion to detect the first execution of said transferee instruction in each particular program loop; means for temporarily storing each of said transferee instructions at the time of said first execution; means for temporarily storing the contents of the program address register contemporaneously with said storing of each of said transferee instructions; means for detecting the end-of-loop, or conditional transfer, instruction corresponding to each of said transferee instructions; and means responsive to each of said conditional transfer instructions for fetching both the corresponding transferee instruction and program address register contents from said temporary storage means.

Claim 21

In combination with a digital computer of the type wherein the first, or transferee, instruction in each program loop contains a suffix portion, the improvement which comprises: means for Using said suffix portion to detect the first execution of said transferee instruction in each particular program loop; means for temporarily storing each of said transferee instructions at the time of said first execution; means for temporarily storing the contents of the program address register contemporaneously with said storing of each of said transferee instructions; means for detecting the end-of-loop, or conditional transfer, instruction corresponding to each of said transferee instructions; and means responsive to each of said conditional transfer instructions for fetching both the corresponding transferee instruction and program address register contents from said temporary storage means.

Claim 22

determining whether said execution of said conditional transfer instruction has resulted in the generation of said terminating signal;

Claim 23

determining whether said execution of said conditional transfer instruction has resulted in the generation of said terminating signal;

Claim 24

fetching said transferee instruction and said next sequential address from said high-speed memory and returning to step (3) if said terminating signal has not been generated;

Claim 25

fetching said transferee instruction and said next sequential address from said high-speed memory and returning to step (3) if said terminating signal has not been generated;

Claim 28

fetching the most recently stored transferee instruction and address from said high-speed memory and returning to step (3) if said terminating signal has not been generated;

Claim 29

fetching the most recently stored transferee instruction and address from said high-speed memory and returning to step (3) if said terminating signal has not been generated;

Claim 30

executing the next sequential instruction following said conditional transfer instruction if said terminating signal has been generated;

Claim 31

executing the next sequential instruction following said conditional transfer instruction if said terminating signal has been generated;

Claim 32

and executing the next sequential instruction following said conditional transfer instruction if said terminating signal has been generated.

Claim 33

and executing the next sequential instruction following said conditional transfer instruction if said terminating signal has been generated.

Claim 36

and repeating steps (3) through (6) until at least one terminating signal has been generated by each of said repetitively executed sequences.

Claim 37

and repeating steps (3) through (6) until at least one terminating signal has been generated by each of said repetitively executed sequences.

Claim 40

The method according to claim 7 further including the step of: entering said first instruction and said address of said second instruction into pushdown storage media for executing nested program loops.