Method for optimizing execution time of parallel processor programs

A computer-readable medium having computer-executable instructions for performing a method for optimizing execution time of a parallel processor program, said method comprising:

• (a) receiving said parallel processor program;
• (b) performing dummy jumps optimization;
• (c) performing linear code optimization, wherein for a current subcommand included in a current command in a current domain in said parallel processor program said linear code optimization further comprises:
• 1) evaluating a first list comprising objects that are used in an exclusive mode by the current subcornmand and a second list comprising objects that are used by the current subcommand, but not changed by the current subcommand,
• 2) determining a first maximal address that is less than the address of the current command and greater than or equal to an address of a first command of the current domain such that a second command with said first maximal address includes a second subcommand, wherein a third list, comprising objects that are used in an exclusive mode by the second subcommand, intersects with said first list comprising objects that are used in an exclusive mode by the current subcommand, and assigning a value representing a null address to said first maximal address when no first maximal address is found.
• 3) determining a second maximal address that is less than the address of the current command and greater than or equal to an address of the first command of the current domain such that a third command with said second maximal address includes a third subcommand, wherein a fourth list, comprising objects that are used by the third subcommand, but not changed by the third subcommand, intersects with said first list comprising objects that are used in an exclusive mode by the current subcommand, and assigning said value representing said null address to said second maximal address when no second maximal address is found,
• 4) determining a third maximal address that is less than the address of the current command and greater than or equal to an address of the first command of the current domain such that a fourth command with said third maximal address includes a fourth subcommand, wherein a fifth list, comprising objects that are used in an exclusive mode by the fourth subcommand, intersects with said second list comprising objects that are used by the current subcommand, but not chanced by the current subcommand, and assigning said value representing said null address to said third maximal address when no third maximal address is found, and
• 5) defining a fourth maximal address as a maximum value of the group consisting of (i) said address of said first command of the current domain, (ii) said first maximal address incremented by one, (iii) said second maximal address and (iv) said third maximal address incremented by one, where said fourth maximal address is less than the address of the current command and greater than or eaual to the address of the first command of the current domain;
• (d) performing jumps optimization;
• (e) returning back to said step (b) when there is any change made in said steps (b), (c), and (d);
• and
• (f) outputting a resulted new processor program when there is no change made in said steps (b), (c), and (d).

A method for optimizing execution time of a parallel processor program, comprising:

• (A) receiving said parallel processor program;
• (B) performing dummy jumps optimization;
• (C) performing linear code optimization;
• (D) performing jumps optimization, wherein for a current command having a previous command immediately preceding said current command, said jumps optimization comprises:
• (1) when (i) said previous command has no jump-subcommand, (ii) said current command has at least one jump-subcommand and does not depend from said previous command, and (iii) a sum of a number of subcommands contained in said previous command plus a number of subcommands contained in said current command is less than or equal to a predetermined maximum number of sub-commands in a processor command, performing the steps of:
• a) when said current command is not a jump-target command, replacing said previous command with a union of said previous command and said current command, and removing said current command;
• and
• b) when said current command is a jump-target command, and said current command contains either a jump-subcommand of type JUMP or a jump-subcommand of type RETURN, replacing said previous command with a union of said previous command and said current command;
• (2) when (i) said previous command has at least one jump-subcommand but has no jump-subcommands of types CALL, RETURN and JUMP, and (ii) said current command does not depend from said previous command, performing the steps of:
• a) when said current command is not a jump-target command, and the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than or equal to the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command, and removing said current command;
• b) when (i) said current command is a jump-target command and contains either a jump-subcommand of type JUMP or a jump-subcommand of type RETURN, and (ii) the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than or equal to the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command;
• and
• c) when (i) said current command is a jump-target command, (ii) said step b) of said step (2) is not applicable, and (iii) the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command, and appending a subcommand of type JUMP, with an address argument set to an address of said current command plus one, to an end of said newly replaced previous command;
• (3) when (i) said current command has either a jump-subcommand of type JUMP or a jump-subcommand of type CALL, (ii) a jump-target command of said jump-subcommand has no jump-subcommand and does not depend from said current command, and (iii) a sum of the number of subcommands in said current command plus a number of subcommands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command, inserting all subcommands of said jump-target command into said current command at a location before said jump-subcommand, and increasing a jump-address in said jump-subcommand by one;
• and
• (4) when (i) said current command has a jump-subcommand of type JUMP and (ii) a jump-target command of said jump-subcommand has at least one jump-subcommand and does not depend from said current command, performing the steps of:
• a) when (i) said jump-target command has only one jump-subcommand of either type JUMP or type CALL and has no more jump-subcommands, and (ii) a sum of the number of subcommands in said current command plus a number of sub-commands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command plus one, inserting all subcommands of said jump-target command into said current command before said jump-subcommand, and removing said jump-subcommand from said current command;
• b) when (i) said jump-target command has at least one non-jump-subcommand of any type and at least one jump-subcommand having a type selected from the group consisting of LOOP_INC_NOLESS, LOOP_INC_NOMORE, LOOP_DEC_NOLESS, LOOP_DEC_NOMORE, ZERO_JUMP and NONZERO_JUMP, and (ii) a sum of the number of subcommands in said current command plus a number of sub-commands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command, inserting all subcommands of said jump-target command into said current command at a location before said jump-subcommand, and replacing said jump-subcommand with a subcommand of type JUMP having an address argument set to an address of said jump-target command plus one;
• (E) returning back to said step (B) when there is any change made in said steps (B), (C), and (D);
• and
• (F) outputting a resulted new processor program when there is no change made in said steps (B), (C), and (D).

A computer-readable medium having computer-executable instructions for performing a method for optimizing execution time of a parallel processor program, said method comprising:

• (A) receiving said parallel processor program;
• (B) performing dummy jumps optimization;
• (C) performing linear code optimization;
• (D) performing jumps optimization, wherein for a current command having a previous command immediately preceding said current command, said jumps optimization comprises:
• (1) when (i) said previous command has no jump-subcommand, (ii) said current command has at least one jump-subcommand and does not depend from said previous command, and (iii) a sum of a number of subcommands contained in said previous command plus a number of subcommands contained in said current command is less than or equal to a predetermined maximum number of sub-commands in a processor command, performing the steps of:
• a) when said current command is not a jump-target command, replacing said previous command with a union of said previous command and said current command, and removing said current command;
• and
• b) when said current command is a jump-target command, and said current command contains either a jump-subcommand of type JUMP or a jump-subcommand of type RETURN, replacing said previous command with a union of said previous command and said current command;
• (2) when (i) said previous command has at least one jump-subcommand but has no jump-subcommands of types CALL, RETURN and JUMP, and (ii) said current command does not depend from said previous command, performing the steps of:
• a) when said current command is not a jump-target command, and the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than or equal to the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command, and removing said current command;
• b) when (i) said current command is a jump-target command and contains either a jump-subcommand of type JUMP or a jump-subcommand of type RETURN, and (ii) the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than or equal to the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command;
• and
• c) when (i) said current command is a jump-target command, (ii) said step b) of said step (2) is not applicable, and (iii) the sum of the number of subcommands in said previous command plus the number of subcommands in said current command is less than the predetermined maximum number of subcommands in a processor command, replacing said previous command with a union of said previous command and said current command, and appending a subcommand of type JUMP, with an address argument set to an address of said current command plus one, to an end of said newly replaced previous command;
• (3) when (i) said current command has either a jump-subcommand of type JUMP or a jump-subcommand of type CALL, (ii) a jump-target command of said jump-subcommand has no jump-subcommand and does not depend from said current command, and (iii) a sum of the number of subcommands in said current command plus a number of subcommands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command, inserting all subcommands of said jump-target command into said current command at a location before said jump-subcommand, and increasing a jump-address in said jump-subcommand by one;
• and
• (4) when (i) said current command has a jump-subcommand of type JUMP and (ii) a jump-target command of said jump-subcommand has at least one jump-subcommand and does not depend from said current command, performing the steps of:
• a) when (i) said jump-target command has only one jump-subcommand of either type JUMP or type CALL and has no more jump-subcommands, and (ii) a sum of the number of subcommands in said current command plus a number of sub-commands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command plus one, inserting all subcommands of said jump-target command into said current command before said jump-subcommand, and removing said jump-subcommand from said current command;
• b) when (i) said jump-target command has at least one non-jump-subcommand of any type and at least one jump-subcommand having a type selected from the group consisting of LOOP_INC_NOLESS, LOOP_INC_NOMORE, LOOP_DEC_NOLESS, LOOP_DEC_NOMORE, ZERO_JUMP and NONZERO_JUMP, and (ii) a sum of the number of subcommands in said current command plus a number of sub-commands in said jump-target command is less than or equal to the predetermined maximum number of subcommands in a processor command, inserting all subcommands of said jump-target command into said current command at a location before said jump-subcommand, and replacing said jump-subcommand with a subcommand of type JUMP having an address argument set to an address of said jump-target command plus one;
• (E) returning back to said step (B) when there is any change made in said steps (B), (C), and (D);
• and
• (F) outputting a resulted new processor program when there is no change made in said steps (B), (C), and (D).