Maximum Parallel Machine ------- -------- ------- The maximum parallel machine (MAXPAR) has an extremely wide instruction that can perform in parallel one opera- tion for each register. More specifically, in a single instruction, each register can be set to the output of an arithmetic operation applied to values read from two register operands. You have been asked to write a compiler for this machine, which given a program written in a typical programming language plus sufficient input data to determine the entire control flow of the program when it is run, will compile a MAXPAR program to perform the same computation. As an initial exercise, you are going to solve this problem in a simplified case. In this simplified case all data are 32 bit signed integers, the only memory are 26 registers named A, B, C, ..., Z, and instructions can only reference registers. The registers are given initial values before the program starts and register values when the program ends are the program output. Input Programming Language ----- ----------- -------- The input programming language has the syntax: program ::= statements statements ::= statement ; | statements statement ; statement ::= arithmetic-statement | loop | exit-statement arithmetic-statement ::= register = register op register register ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z op ::= + | - | * loop ::= begin; statements end exit-statement ::= exit | exit if register cop register cop ::= <= | == | != If execution arrives at the end of a loop, execution continues at the beginning of the loop. An exit-state- ment can only appear in a loop and exits the smallest loop containing the exit-statement. Whitespace, including line breaks, is optional ANYWHERE, and can be completely deleted before syntax analysis. Registers that appear in exit-statements are called `control' registers, and registers input to arithmetic statements that compute control registers are also control registers. All other registers are called `data' registers. In an arithmetic-statement, ALL registers must be control or ALL must be data. You are being asked to compile the input program into a MAXPAR program, given the initial values of the control registers, without knowing the values of the data registers. The MAXPAR program contains nothing but data register arithmetic statements, and is designed to be run by giv- ing all data register initial values, running the pro- gram, and then taking output from the register values at the end of the program. However you are just compiling the MAXPAR program, and not running it. MAXPAR Programming Language ------ ----------- -------- The MAXPAR programming language has the syntax: program ::= statements statements ::= statement ; | statements statement ; statement ::= substatements substatements ::= substatement | substatements , substatement substatement ::= arithmetic-statement arithmetic-statement ::= see Input Programming Language above Whitespace, including line breaks, is optional ANYWHERE, and can be completely deleted before syntax analysis. The substatements of a single statement are executed in parallel. That is, all the operands of all the sub- statements are read first, then all the operations are performed, then all the operation values are written last. All the registers appearing in the MAXPAR program are data registers. Input ----- For each test case, first a line that gives the test case name. Then lines containing one input program followed by a line containing just `$'. Then one or more sets of control register values. Each set consists of zero or more lines of the form register value where value is an integer. Each set ends with a line containing just `$'. The test case ends with an additional line containing just `#'. Each set of control register values will have exactly one value for EACH control register in the input program. Some input programs may have no control registers. Input ends with an end of file. No input line is longer than 80 characters, and the input program in its entirety contains no more than 10,000 non-whitespace characters. The input is guaranteed to be syntactically correct and execute no more than 100,000 statements when run on any set of initial control register values. Registers store 32-bit signed integers and integer arithmetic is modulo 2^32 (as in C, C++, and JAVA). Control register input values are guaranteed to have no more than 9 digits. Output ------ For each test case, first an exact copy of the test case name line. Then for each control register set a MAXPAR program that computes the same thing as the input pro- gram when it is run with the initial control register values given by the register set. Each MAXPAR program is followed by a line containing just `$'. Lastly, at the end of the test case, output one more line containing just '#'. In the execution of either the input program or the MAX- PAR program the different values of a register can be tagged with the order of their computation, so that the 0'th value is the initial value, the 1'st value is the first value computed, etc. Given this we require that substatements of the MAXPAR program correspond 1-1 to data register arithmetic-statement executions in the input program such that: (1) The arithmetic-statement of an execution is syntactically identical to its corresponding MAXPAR substatement (with whitespace removed). (2) If a substatement computes the n'th value of its destination register, its corresponding input arithmetic-statement execution computes the n'th value of its destination register. (3) If a substatement inputs the m'th value of its first (or second) operand register, its correspond- ing input arithmetic-statement execution inputs the m'th value of its first (or second) operand regis- ter. Among all possible MAXPAR programs, you must output one with the fewest possible number of statements. If there are several answers, any one will do. Sample Input ------ ----- -- SAMPLE 1 -- Z = Z + Y; Z = Z + Y; X = Z + Y; Y = Y + W; $ $ # -- SAMPLE 2 -- X = Y + Z; Z = Y + X; begin; exit if C == D; C = C + B; Z = Z + X; Y = Y + X; end; $ B 1 C 1 D 4 $ # -- SAMPLE 3 -- begin; exit if A == B; R = X * Y; exit if A <= B; S = X - Y; exit if A != B; T = X + Y; exit; end; $ A 0 B 0 $ A 0 B 1 $ A 1 B 0 $ # Sample Output ------ ------ -- SAMPLE 1 -- Z=Z+Y; Z=Z+Y; X=Z+Y,Y=Y+W; $ # -- SAMPLE 2 -- X=Y+Z; Y=Y+X,Z=Y+X; Y=Y+X,Z=Z+X; Y=Y+X,Z=Z+X; Z=Z+X; $ # -- SAMPLE 3 -- $ R=X*Y; $ R=X*Y,S=X-Y; $ # Note ---- Similar techniques have been used to translate traces of real program executions into MAXPAR-like code in order to determine the maximum parallelism possible in these executions. One such is the ORACLE code in the `Limits of control flow parallelism', ISCA '92, Monica S. Lam and Robert P. Wilson, ACM Digital Library. The ORACLE machine is like the MAXPAR machine except that ORACLE has an unbounded number of registers and never writes a register more than once. Typical results are that gcc and latex executions translate into ORACLE code with an average of 100 to 200 substatements per statement, thus giving an upper bound of 200 on the factor that paral- lelism can speed up gcc and latex (without reorganizing the code completely). File: maxparallel.txt Author: Bob Walton Date: Sat Oct 6 11:55:17 EDT 2018 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file.