CPSC 3300 - Spring 2017 - Project 2 Assignment [4/6/17 - extended due date] Due date: before midnight on the night of Monday, April 17 Submission: use handin.cs.clemson.edu to turn in your file(s) (you may submit either uncompressed source files or a tar ball [optionally gzipped]; please check with me first regarding other compressed formats) Grading weights: 80% basic data flow analysis 5% extended load latency 15% register renaming Late penalty: 10% off per day late, up to five days Concepts needed: assembly language instruction formats, registers, and data dependencies This can be an individual assignment or a team of two assignment You may discuss the requirements of the assignment and the sample inputs and outputs given below with anyone, but you may not discuss the programming solution at either the algorithmic level or the code level with anyone other than a teammate. MINI-DFA Write a program to read a file of MIPS-like instructions and generate the data flow levels based on register usage. You should omit tracking the memory data flow. The program can be written in any language that runs on SoC Linux servers. The program should accept from one to three command line values: [optional] -r # indicates register renaming [optional] -l # indicates a load delay of specified cycles input-file-name The options and file name will always appear in the above ordering. The input will be limited to a MIPS-like subset of instructions of the following forms: add ,, sub ,, addi ,, # no src2 register subi ,, # no src2 register lw ,() # no src2 register sw ,() # no dest register The architected registers are $0 through $7. If renaming is specified, start the physical register numbering at 10. Other than the load, each instruction will be assumed to require one cycle of delay. The delay for the load instruction has a default of one cycle but can be increased by use of the l option. The program should determine the data flow among all the input instructions (i.e., RAW, WAR, WAW). All instructions that can be executed immediately should be printed as level 0 instructions. All dependent instructions that can be executed after one-cycle-delay level 0 instructions finish should be should be printed as level 1 instructions. And so on. Note that load instructions can optionally be made to require multiple cycles to complete; instructions that are dependent on a load must not be assigned a level until the load finishes. Example input and output follows. The input will be given in fixed fields to make the parsing trivial: the opcode starts in the first column, and the parameters start in sixth column and will contain no embedded spaces or tabs. The instructions in the output are annotated with sequence numbers based on the original program order. You will notice in the first example that the subtract instruction can be executed out of program order because it is register-independent of the earlier instructions. input file: mips1.in lw $2,0($1) add $1,$2,$3 sub $4,$5,$6 add $7,$1,$4 addi $7,$7,1 sw $7,0($1) output for "./dfa mips1.in" load delay set to 1 level 0 instructions: 0 lw $2,0($1) 2 sub $4,$5,$6 level 1 instructions: 1 add $1,$2,$3 level 2 instructions: 3 add $7,$1,$4 level 3 instructions: 4 addi $7,$7,1 level 4 instructions: 5 sw $7,0($1) the data flow can be executed in 5 cycles output for "./dfa -l3 mips1.in" load delay set to 3 level 0 instructions: 0 lw $2,0($1) 2 sub $4,$5,$6 level 3 instructions: 1 add $1,$2,$3 level 4 instructions: 3 add $7,$1,$4 level 5 instructions: 4 addi $7,$7,1 level 6 instructions: 5 sw $7,0($1) the data flow can be executed in 7 cycles input file: mips2.in lw $2,0($1) addi $3,$2,1 sub $2,$5,$6 addi $7,$2,1 output for "./dfa -l2 mips1.in" load delay set to 2 level 0 instructions: 0 lw $2,0($1) level 2 instructions: 1 addi $3,$2,1 level 3 instructions: 2 sub $2,$5,$6 level 4 instructions: 3 addi $7,$2,1 the data flow can be executed in 5 cycles output for "./dfa -r -l2 mips2.in" load delay set to 2 level 0 instructions: 0 lw $2,0($1) with renaming d/s1/s2 regs to 10 1 - 2 sub $2,$5,$6 with renaming d/s1/s2 regs to 12 5 6 level 1 instructions: 3 addi $7,$2,1 with renaming d/s1/s2 regs to 13 12 - level 2 instructions: 1 addi $3,$2,1 with renaming d/s1/s2 regs to 11 10 - the data flow can be executed in 3 cycles input file: mips3.in add $3,$1,$2 addi $4,$3,1 sub $3,$5,$6 subi $3,$3,1 output for "./dfa mips3.in" load delay set to 1 level 0 instructions: 0 add $3,$1,$2 level 1 instructions: 1 addi $4,$3,1 level 2 instructions: 2 sub $3,$5,$6 level 3 instructions: 3 subi $3,$3,1 the data flow can be executed in 4 cycles output for "./dfa -r mips3.in" load delay set to 1 level 0 instructions: 0 add $3,$1,$2 with renaming d/s1/s2 regs to 10 1 2 2 sub $3,$5,$6 with renaming d/s1/s2 regs to 12 5 6 level 1 instructions: 1 addi $4,$3,1 with renaming d/s1/s2 regs to 11 10 - 3 subi $3,$3,1 with renaming d/s1/s2 regs to 13 12 - the data flow can be executed in 2 cycles Note: in testing, you may find it helpful to add a verbose option (-v) to print out the dependencies. E.g., for mips1.in without renaming: inst 1 WAR dependent on inst 0 through reg 1 inst 1 RAW dependent on inst 0 through reg 2 inst 3 RAW dependent on inst 1 through reg 1 inst 3 RAW dependent on inst 2 through reg 4 inst 4 WAW dependent on inst 3 through reg 7 inst 4 RAW dependent on inst 3 through reg 7 inst 5 RAW dependent on inst 1 through reg 1 inst 5 RAW dependent on inst 4 through reg 7 and with renaming: inst 1 RAW dependent on inst 0 through reg 10 inst 3 RAW dependent on inst 1 through reg 11 inst 3 RAW dependent on inst 2 through reg 12 inst 4 RAW dependent on inst 3 through reg 13 inst 5 RAW dependent on inst 1 through reg 11 inst 5 RAW dependent on inst 4 through reg 14