Programming Assignment 5 - Hyperthreading!

See the assignment turn-in page (last modified on 9 February 2004) for instructions on turning in your assignment.

A hyperthreading CPU has an almost traditional architecture . It has functional units (an adder, a multiplier, and so on) and the functional units share access to the same set of CPU registers and to primary store. The architecture has eight CPU registers named r0 through r7; addresses in primary store are referenced by the names of the associated variables (which are assumed to be different from the register names). The initial value of primary-store locations and the registers is an arbitrary value; different locations and registers may have different values (or they may not - it's arbitrary).

A CPU instruction is either a move instruction or an operator instruction. All instructions execute in one clock tick. A move instruction has the form

and moves the value stored in src to the location given by dst. Both src and dst can be either memory addresses or registers, with the restriction that both cannot be memory addresses; that is at least one must be a register.

An operator instruction has the form

where opr is one of the usual operators +, - and so on and both src and dst are registers. An operator instruction performs the computation

Each operator has its own functional unit; that is, the add operator + uses the addition functional unit, the division operator / uses the division functional unit and so on.

The three parts of a CPU or move instruction are separated from each other by at least one non-newline space character. Memory locations are referred to using C++-syntax variable names.

The translation from high-level language statements to instructions is straightforward. For example, the high-level statement

can be translated into the instructions

move r0  b
move r1  c
+    r1 r0
move  a r1

Hyperthreading occurs when the CPU issues and executes two instructions at the same time; the instructions can be from the same program or from two different programs. Two instructions can be executed simultaneously if they use disjoint sets of resources (registers and functional units). For example, two add instructions could not be issued at the same time because they would conflict over the adder; similarly, two instructions that used register i, either as a source or target, could not be issued together.

A hyperthread schedule is a sequence of composite instructions, in which each composite instruction is either a single CPU instruction or a pair of non-conflicting CPU instructions. For example, the simple program

move r0  b
move r1  c

produces the hyperthread schedule

move r0  b ; move r1  c

A composite instruction also executes in one clock tick, but it executes all its component simple instructions in parallel.

Valid hyperthread schedules should obey these constraints:

• A composite issue contains one or two CPU instructions.

• If a composite issue contains two CPU instructions, the instructions should use disjoint registers and functional units.

• The hyperthread schedule should produce exactly the same results in memory that would be produced if the two input programs were run sequentially. The initial and final values of registers are not important.

A program consists of a sequence of one or more CPU instructions. Each instruction appears in a single line, and a single line contains exactly one instruction. Instructions in a program appear consecutively; there is no blank line between instructions in a program.

Operators can be any of the standard C++ binary operators except for the short-circuit operators && and ||; see Appendix A of Deitel and Deitel for details. Assume there is a functional unit for each operator.

A composite issue is either a single CPU instruction, or two CPU instructions separated by a semicolon.

If your program detects an input error, it should write an informative error message (starting, as always, with bang space "! ") to std-err and exit with no further processing.