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.