Efficient data processor instrumentation for systematic program debugging and development

Claim 2

In a data processing system comprising at least one processor for executing instructions stored in memory, execution of instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, a method of determining a maximum level of parallel execution of instructions that is possible with execution of a program comprised of a plurality of instructions, said method comprising the steps of: a) simulating execution of the program in multiprocessors having unlimited processing capability with respect to the program by executing the program in the at least one processor one program step at a time, each program step after a first program step processing all tokens generated in a previous program step, each program step comprising: processing with the at least one processor all tokens which are available at the start of the program step, the processing of the tokens initiating execution of all of the executable instructions whose execution is free of dependency upon unavailable operands; and storing new tokens generated during the program step for processing during a subsequent program step; and b) for each program step, counting and recording a number of instructions that are executed during the program step to produce a parallelism characteristic of the program.

Claim 3

A method as recited in claim 1 wherein the simulating step simulates the data processing system as having no delay in communications among a plurality of parallel processors.

Claim 4

A method as recited in claim 1 further comprising the step of plotting the number of instructions completed during each program step versus the number of the program step to produce a graphical representation of performance of the simulated second data processing system assuming an infinite number of parallel processors for comparison to actual performance with a finite number of parallel processors.

Claim 5

A method as recited in claim 1 wherein the first and second data processing systems are data flow processing system.

Claim 8

A method as recited in claim 5 wherein the data processing system is a data flow processing system.

Claim 9

A data processing system for determining a maximum level of parallel execution of instructions achievable upon execution of a program, said program being comprised of a plurality of instructions stored in memory, the execution of said instructions being initiated by processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions causing the generation of new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising: a) at least one processor for executing the program a program step at a time to simulate execution of the program in multiprocessors with unlimited processing capability with respect to the program, each program step after a first program step processing all tokens generated in a previous program step, execution of a program step comprising: processing with the at least one processor all tokens which are available at the start of the program step, processing of the tokens initiating the execution of all executable instructions whose execution is free of dependency upon unavailable operands; storing tokens generated during the program step for processing during a subsequent program step; b) means for counting and recording a number of instructions executed at each program step to produce a parallelism characteristic of the program; and c) in each processing element, at least one token queue for storing tokens whose processing initiates execution of instructions of the program step and tokens whose processing initiates execution of instructions of the subsequent program step.

Claim 10

A data processing system for determining a maximum level of parallel execution of instructions achievable upon execution of a program, said program being comprised of a plurality of instructions stored in memory, the execution of said instructions being initiated by processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions causing the generation of new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising: a) at least one processor for executing the program a program step at a time to simulate execution of the program in multiprocessors with unlimited processing capability with respect to the program, each program step after a first program step processing all tokens generated in a previous program step, execution of a program step comprising: processing with the at least one processor all tokens which are available at the start of the program step, processing of the tokens initiating the execution of all executable instructions whose execution is free of dependency upon unavailable operands; storing tokens generated during the program step for processing during a subsequent program step; b) means for counting and recording a number of instructions executed at each program step to produce a parallelism characteristic of the program; and c) in each processing element, at least one token queue for storing tokens whose processing initiates execution of instructions of the program step and tokens whose processing initiates execution of instructions of the subsequent program step.

Claim 11

A data processing system as recited in claim 7 wherein the data processing system comprises a data flow processing system.

Claim 12

A data processing system as recited in claim 7 wherein during execution, a first token queue stores tokens for the step being executed and a second token queue stores tokens for the subsequent step to be executed.

Claim 13

In a data processing system having at least one processor, a method of determining a maximum level of parallel execution of instructions that may be achieved when a program is executed, said program being comprised of a plurality of instructions stored in memory, execution of instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instruction, the at least one processor comprising at least one token queue for storing tokens, said method comprising the steps of: a) for the at least one processor, storing tokens whose processing initiates execution of a program step in one of its at least one token queues, each program step after a first program step processing all tokens generated in a previous program step, in the at least one processor, processing all tokens which are available in the at least one token queue at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step; b) counting a number of instructions completed during the program step and associating the number with the program step; and c) repeating steps a and b for subsequent program steps to generate a parallelism characteristic for the program.

Claim 14

In a data processing system having at least one processor, a method of determining a maximum level of parallel execution of instructions that may be achieved when a program is executed, said program being comprised of a plurality of instructions stored in memory, execution of instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instruction, the at least one processor comprising at least one token queue for storing tokens, said method comprising the steps of: a) for the at least one processor, storing tokens whose processing initiates execution of a program step in one of its at least one token queues, each program step after a first program step processing all tokens generated in a previous program step, in the at least one processor, processing all tokens which are available in the at least one token queue at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step; b) counting a number of instructions completed during the program step and associating the number with the program step; and c) repeating steps a and b for subsequent program steps to generate a parallelism characteristic for the program.

Claim 15

A method as recited in claim 10 wherein the data processing system is a data flow processing system.

Claim 16

A method as recited in claim 10 further comprising the step of adjusting the parallelism characteristic according to processing limitations of the plurality of parallel processors to derive the maximum achievable level of parallelism that may be achieved in executing the program with the plurality of parallel processors.

Claim 17

A data processing system for determining a maximum level of parallel execution of instructions of a program which is achievable when the program is executed, said program being comprised of a plurality of instructions stored in memory, execution of the instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising: a) at least one processor for processing tokens and executing instructions to execute the program in program steps, each program step after a first program step processing all tokens generated in a previous program step, the at least on processor processing all tokens which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step, the at least one processor comprising a means for counting a number of instructions that are executed during each program step; and b) at least one pair of token queues for holding tokens to be processed by the at least one processor wherein, during each program step, tokens held in one of the pair of token queues are processed until the token queue is empty, and new tokens generated during the program step are stored in the other token queue of the pair.

Claim 18

A data processing system for determining a maximum level of parallel execution of instructions of a program which is achievable when the program is executed, said program being comprised of a plurality of instructions stored in memory, execution of the instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising: a) at least one processor for processing tokens and executing instructions to execute the program in program steps, each program step after a first program step processing all tokens generated in a previous program step, the at least on processor processing all tokens which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step, the at least one processor comprising a means for counting a number of instructions that are executed during each program step; and b) at least one pair of token queues for holding tokens to be processed by the at least one processor wherein, during each program step, tokens held in one of the pair of token queues are processed until the token queue is empty, and new tokens generated during the program step are stored in the other token queue of the pair.

Claim 19

A data processing system as recited in claim 13 wherein the data processing system comprises a data flow processing system.

Claim 20

In a data processing system having at least one processor, a method of determining a maximum level of parallel execution of instructions of a program which is achievable when the program is executed, said program being comprised of a plurality of instructions stored in memory, execution of the instruction being initiated by the precessing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising, for the at least one processor, a pair of token queues for holding tokens to be processed by the at least one processor, said method comprising the steps of: a) filling a first token queue of the pair of token queues with tokens of a program step, each program step after a first program step processing all tokens generated in a previous program step, processing with the at least one processor all tokens in the first token queue which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing new tokens generated during the program step in a second token queue for processing during a subsequent program step; b) counting a number of instructions executed during the program step and associating this number of instructions with a number of the program step; and c) repeating steps a and b for subsequent program steps to generate a parallelism characteristic for the program, the first token queue of a program step being the second token queue of the next succeeding program step and the second token queue of a program step being the first token queue of the next succeeding program step.

Claim 21

In a data processing system having at least one processor, a method of determining a maximum level of parallel execution of instructions of a program which is achievable when the program is executed, said program being comprised of a plurality of instructions stored in memory, execution of the instruction being initiated by the precessing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, said data processing system comprising, for the at least one processor, a pair of token queues for holding tokens to be processed by the at least one processor, said method comprising the steps of: a) filling a first token queue of the pair of token queues with tokens of a program step, each program step after a first program step processing all tokens generated in a previous program step, processing with the at least one processor all tokens in the first token queue which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing new tokens generated during the program step in a second token queue for processing during a subsequent program step; b) counting a number of instructions executed during the program step and associating this number of instructions with a number of the program step; and c) repeating steps a and b for subsequent program steps to generate a parallelism characteristic for the program, the first token queue of a program step being the second token queue of the next succeeding program step and the second token queue of a program step being the first token queue of the next succeeding program step.

Claim 22

A method as recited in claim 15 wherein the data processing system is a data flow processing system.

Claim 23

A method as recited in claim 15 further comprising the step of adjusting the parallelism characteristic according to processing limitations of the plurality of parallel processors to derive the maximum achievable level of parallelism that may be achieved in executing the program with the plurality of parallel processors.

Claim 24

In a data processing system having at least one processor, a method of executing a program to facilitate debugging of the program, said program being comprised of a plurality of instructions stored in memory, execution of the instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, the at least one processor comprising at least one token queue for storing tokens, said method comprising: a) storing tokens of a program step in the at least one token queue, each program step after a first program step processing all tokens generated in a previous program step, processing all tokens which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step; b) if an error occurs, halting execution of the program after the program step and determining the source of the error; and c) otherwise, continuing execution by processing tokens of a next program step.

Claim 25

In a data processing system having at least one processor, a method of executing a program to facilitate debugging of the program, said program being comprised of a plurality of instructions stored in memory, execution of the instructions being initiated by the processing of tokens which carry operands, an instruction being executed only after all required operands are available, and the execution of some instructions generating new tokens to be processed in order to initiate execution of new instructions, the at least one processor comprising at least one token queue for storing tokens, said method comprising: a) storing tokens of a program step in the at least one token queue, each program step after a first program step processing all tokens generated in a previous program step, processing all tokens which are available at the start of the program step, the processing of the tokens initiating execution of all executable instructions initiated by tokens whose execution is free of dependency upon unavailable operands, and storing tokens generated during the program step for processing during a subsequent program step; b) if an error occurs, halting execution of the program after the program step and determining the source of the error; and c) otherwise, continuing execution by processing tokens of a next program step.

Claim 26

A method as recited in claim 18 further comprising the step of accumulating statistics in a memory element during processing of the tokens.