mips汇编代写

 

 

 

 

The goal of this project is to write programs that solve a minesweeper game.   If you’ve never played  Minesweeper1   (or  Mines  in  Linux),  your  first  task  is  to  play  the  game  for  hours  (as important  research).    In  Minesweeper,  there  is  an  8xminefield  of  squares,  originally  all unopened.   Hidden mines are buried under m squares in the field.   Normally, if you step on a mine by opening one of these squares, Game Over … except in this class project!   In ours, it is not fatal to step on a mine if you are making a “necessary guess” when no local inferences are possible, as explained below.   As you open squares, numbers are revealed (unless  you open a mined square, in which case a bomb is shown).  A number on a square indicates how many mines are in the immediately adjacent squares surrounding it.  Based on this information, the object of the game is to infer where the mines are and to place flags on those squares.

 

 

 

 

 

 

 

 

 

 

 

Opening squares, revealed these counts (the blank squares have a count of 0), indicating the number of mines in immediately surrounding neighbors.

 

 

 

 

 

 

 

 

 

From the “3” count, it can be inferred that all of that square’s unopened neighbors are mines, so they have been flagged.

Opening the upper left corner revealed a mine, but was it a necessary guess?  If so, we are safe and game continues. If not, Game Over!

 

 

Note: If you make an unnecessary guess, the game is lost, even if a mine was not buried under the square that was guessed.

 

 

 

 

 

 

 

 

 

 

Since the “1” count in the upper left corner is accounted for by the flag, it is safe to open all other squares around it.

Result of opening the surrounding squares.

 

 

There  is  an  element  of  chance  in  the  game  because  it  is  not  always  possible  to  infer  all  the positions  of  mines.   In  those  cases,  a  necessary  guess  must  be  made,  which  might  uncover  a mine. In this project, if you make a necessary guess of a mined square, it will not blow up to lose the game.   However, your program can still fail if unnecessary guesses are made.   A guess is unnecessary if there is at least one square P for which an inference can be made based solely on P and its immediate neighbors (a one-square inference).

 

 

 

1    If you do not have Minesweeper, you can find it online at: http://minesweeperonline.com/#intermediate

 

 

 

 

Your  program  will  be  able  to  perform  one  of  three  different  actions  on  a  square  in  a  given minefield:

 

  1. Open – indicating that a square is clear of mines; this will reveal a count of surrounding mines (unless the square is mined).

 

  1. Flag – indicating that a square holds a mine.

 

  1. Guess – a cautious open, indicating that there is uncertainty about whether the square is clear (when your guess is necessary, the move is safe even if a mine is buried there); this will reveal either a count or a mine.

 

To solve the puzzle, your program must take these actions on squares to infer where the mines are and flag them.

 

Your program succeeds if it:

  1. makes no unnecessary guesses,
  2. opens no square containing a mine,
  3. does not overwrite (open, flag, or guess) any square that was already opened, flagged, or guessed,
  4. flags only squares that actually hold mines, and
  5. accounts for all m mines either by flagging them or making necessary guesses that reveal them.

If all guesses made by your program are necessary, they are correct even if they reveal a mine. However, your program fails if it makes an unnecessary guess, even if there is no mine buried at the square guessed.

 

Strategy: Unlike many “function only” programming tasks where a solution can be quickly en- visioned and implemented, this task requires a different strategy.

 

  1. Before writing any code, reflect on the task requirements and constraints. Mentally ex- plore  different  approaches  and  algorithms,  considering  their  potential  performance  and costs. The metrics of merit are static code length, dynamic execution time, and storage requirements. There are often trade-offs between these parameters. Sometimes back of the envelope calculations (e.g., how many memory accesses will be performed) can help illuminate the potential of an approach.

 

  1. Once a promising approach is chosen, a high level language (HLL) implementation (e.g., in C) can deepen its understanding. The HLL implementation is more flexible and conve- nient for exploring the solution space and should be written before constructing the as- sembly version where design changes are more costly and difficult to make. For P1-1, you will write a C implementation of the program.

 

  1. Once a working C version is created, it’s time to “be the compiler” and see how it trans- lates to MIPS assembly. This is an opportunity to see how HLL constructs are supported on a machine platform (at the ISA level). This level requires the greatest programming ef- fort; but it also uncovers many new opportunities to increase performance and efficiency. You will write the assembly version for P1-2.

 

 

 

 

 

P1-1: High Level Language Implementation:

 

In this section, the first two steps described above will be completed. It’s fine to start with a sim- ple implementation that produces an answer; this will help deepen your understanding. Then ex- periment with your best mentally-formed ideas for a better performing solution. Use any instru- mentation techniques that help to assess how much work is being done. Each hour spent explor- ing here will cut many hours from the assembly level implementation exercise.

 

The back-end of the game has already been written for you; you are responsible for writing the code that will decide which moves to perform.  The following files are provided in a zip file:

 

minefield.h, minefield.o, Makefile, and P1-1-shell.c

Be sure to download the zip file (P1-1-32bit or P1-1-64bit) that is appropriate for your platform. You can only modify P1-1-shell.c (and rename it to P1-1.c). Inside P1-1.c, you must

complete the solver function such that your program can successfully complete the game.

 

The solver function has the following prototype:

void solver(int total_mine_num);

 

The backend will initialize the minefield randomly, and then call solver(…) with one param- eter:  the total number of mines in the field.

 

To solve the game, you will use functions defined in minefield.h:

  • open(r,c):Call this function if you are certain a square is clear. One of 2 events will occur:
  1. If you were correct, it will return the number of mines in adjacent squares.
  2. If you were incorrect, Game Over – the game will end (in failure).
  • flag(r,c): Call this  function  if  you  are  certain  a  square  contains  a  mine.  Nothing happens until you have flagged, or uncovered by necessary guesses, all m mines. As soon as you flag the mth     mine, the backend will ‘open’ all the remaining squares. The game will end (in failure) if any of those remaining squares have mines (i.e. you have flagged some squares incorrectly).

 

  • guess(r,c): Call this  function  if  it  is  impossible  to  make  a  move  based  solely  on logic involving single squares (1-square inferences).  If the square has a mine, the game will pretend you flagged it; if the square is clear, it will function as an open()call. (Re- fer to minefield.h to see how to tell which happened.) You may only call guessif there is no certain move; if there is any way to logically use  flag or open when guess is called, the game will end (in failure).

 

  • display_field_discovered_so_far(): textual print  out  of  minefield;  not technically needed to complete the project, but useful for debugging.

 

The input parameters (rand c) of open, flag, and guessindicate the following:

 

r:  row number of the cell to be opened (0 is top row).

c:  column number of the cell to be opened (0 is leftmost column). The game will end in one of the following scenarios:

  1. a mine is opened
  2. an unnecessary guess is made

 

 

 

 

  1. total_mine_num flags are marked

Scenarios 1 and 2 are failures.   For Scenario 3, after the last mine is flagged, the backend will immediately ‘open’ all the remaining unflagged and unopened squares. If any of these squares has a mine, the game ends in failure; otherwise, the game is successfully solved.

 

Compiling/Running your code:

In a terminal window, run the “make” command, which will look for a Makefile in the cur- rent  directory  and  execute  it,  compiling  and/or  linking  any  files  that  are  necessary  for  your project to run.  For example, if you type the following commands (the text in black), the results of your commands are shown in blue:

> cd /mnt/c/Users/gburdell/2035/P1

> mv P1-1-shell.c P1-1.c

> ls

Makefile  minefield.h  minefield.o   P1-1.c

> make

gcc -Wall -O3 -c P1-1.c

gcc -Wall -O3 P1-1.o minefield.o -o msweep

Once you use this to create an executable, called “msweep”, you can run it at the command line:

./msweep p s v

where p, s, vare the following:

  • p is the probability of any square being occupied by a mine 0<p<1. For example, 0.1.

Note: it is only a probability, so do not expect the actual number of mines to be exactly

8*8*probability. The actual number of mines is passed to your  solver() func- tion as its second argument.

 

  • s is the seed that determines the placement of mines in the field (e.g., a number such as

2046 or 5787). You may find it helpful to reuse a seed to recreate the same minefield and debug specific scenarios. However, your program will ultimately be expected to handle any seed thrown at it. Enter -1 to test with a different random seed each time.

  • vspecifies whether or not you want the “verbose” print out: 1 is yes, 0 is no. For example:

> ./msweep 0.25 -1 1

program runs w/ 25% bomb density, a random seed, verbose printing

> ./msweep 0.50 5302 0

program runs w/ 50% bomb density, reusable seed, non-verbose

When you run your program, the backend will tell you whether you correctly solved the field or whether you made an error and what it was.   In this version, we are enforcing these additional constraints:

 

  1. You may only make one action per square. In other words, you may not unflag or open a square that you have flagged.

 

  1. Your code does not need to do anything special when it has finished the game; the game code will detect and take care of the end of the game

 

  1. Unlike the normal game, large sections of squares will not be cleared with a single com- mand – you must manually open all squares, including squares adjacent to ones with ‘0’ adjacent mines.

 

 

 

 

When have completed the assignment, submit the single file P1-1.c to Canvas. Although it is good practice to employ a header file (e.g., P1-1.h) for declarations, external variables, etc., in this project please include this information at the beginning of your submitted program file. For your solution to be properly received and graded, there are a few requirements:

  1. The file must be named P1-1.c. Do not submit the executable P1-1.
  2. Your program must compile and run with the provided Makefile under Linux.
  3. Your solution  must  be  properly  uploaded  to  Canvas  before  the  scheduled  due  date,

5:00pm on Friday, 28 September 2018.

 

During grading, your C code will be compiled and subjected to

  • 50 random runs with mine probability 0.25 and
  • 50 random runs with mine probability 0.50.

 

It will be evaluated according to the following criteria: your program

  • has good coding style (well-formatted and commented),
  • compiles without any errors or warnings using the -Wallflag,
  • does not crash, and
  • successfully solves all 100 games.

 

P1-2 Assembly  Level  Implementation:  In  this  part  of  the  project,  you  will  write  the  perfor- mance-focused assembly program that solves minesweeper. A shell program is provided to get you started (P1-2-shell.asm). Rename it to  P1-2.asm.

 

In this  version, execution performance  and cost is often  equally  important. The  assessment  of your  submission  will  include  functional  accuracy  during  100  trials  and  performance  and  effi- ciency. The code size, dynamic execution length, and operand storage requirements are scored empirically, relative to a baseline solution. The baseline numbers for this project are static code size: 110 instructions, dynamic instruction length:  20,195  instructions  (avg.), storage required:

38 words (not including dedicated registers $0, $31).  The dynamic instruction length metric is the maximum of the baseline metric and the average dynamic instruction length of the five fastest student submissions.

 

Your score will be determined through the following equation:

 

PercentCredit = 2MetricYourProgram       

Metric

BaselineProgram

 

Percent Credit is then used to determine the number of points for the corresponding points cate- gory. Important note: while the total score for each part can exceed 100%, especially bad perfor- mance can earn negative credit. The sum of the combined performance metrics scores (code size, execution length, and storage) will not be less than zero points. Finally, the performance scores will be reduced by 10% for each incorrect trial (out of 100 trials). You cannot earn perfor- mance credit if your implementation fails ten or more of the 100 trials.

 

Library Routines: There are two library routines (accessible via the swiinstruction).

 

SWI 567: Bury Mines: This routine internally creates a hidden representation of an  8×8 mine- field and randomly places mines in it.  The mine density is set to 25%.

INPUTS: There are no inputs to this routine.

OUTPUTS: The number of mines buried is returned in register $1.

 

 

 

 

A visualization  of  the  minefield  is  also  produced  and  displayed  in  which  all  squares  are  un- opened (shown as lightblue).   To help with debugging, the positions of hidden mines are indi- cated by a small dashed rectangle within each square in which a mine is buried.

 

SWI 568: Open, Flag, or Guess Square: A square position is given to this routine along with a command to either, open, flag, or guess it.

INPUTS:  Register $2 gives a square position as a linear index between 0 and 63 (one of 8×8 =

64 positions).

Register $3 gives the command:

-1: Guess

0: Open

1: Flag

OUTPUTS: Register $4 gives the result:

-1: mine is uncovered

n: number of mines in immediate neighbors (integer from 0 to 8)

9: flag

The -1 or n is returned regardless of whether the square was opened or guessed and regardless of whether a guess was necessary or not.

This routine also detects Overwrite Errors which occur if the square specified has already been previously opened/flagged/guessed.  These are reported in the lower left window in MiSaSiM.

 

The minefield visualization displays the results of this routine:

  1. Necessary Guess of S: turns  the square green  and either a  mine or a  count is revealed

(blank if the count is 0);

  1. Unnecessary Guess of S: turns the square red and puts a diagonal line through it and ei- ther a mine or a count is revealed (blank if the count is 0);
  2. Flag of S: square stays blue, but flag is displayed;
  3. Open of S: If a mine is buried at S, square turns red and mine is revealed; Otherwise, square turns white and the count is revealed (blank if the count is 0).

 

Differences from P1-1 (C implementation): Your MIPS code must keep track of the number of mines found or flagged and end the program when this count reaches the number of mines origi- nally buried (the result returned from swi 567).   This is unlike the C code which automatically ends when the last mine is found/flagged.  Also, the C backend automatically ends your program when a mined square is opened or a guess is unnecessary.  MiSaSiM will not halt your program under these conditions.  Instead, the visualization indicates these conditions so that you can move through the trace to see where they occur and what caused them.  Also, the mine density (25%) is a constant in the MIPS version, while it is an input parameter to the C program.

 

In order for your solution to be properly received and graded, there are a few requirements.

 

  1. The file must be named P1-2.asm.

 

  1. Your program must return to the operating system via the jr instruction. Programs that include infinite loops or produce simulator warnings or errors will receive zero credit.

 

  1. Your solution  must  be  properly  uploaded  to  Canvas  before  the  scheduled  due  date,

5:00pm on Friday, 12 October 2018.

 

Implementation Evaluation:

 

In this project, the functional implementation of MineSweeper in C (P1-1) will be evaluated on whether  the  correct  answer  is  computed.  Although  proper  coding  technique  (e.g.,  using  the

 

 

 

 

proper  data  types,  operations,  control  mechanisms,  etc.)  will  be  evaluated,  parametric  perfor- mance will not be considered.

 

The performance implementation of the MineSweeper program in MIPS assembly (P1-2) will be evaluated both in terms of correctness and performance. The correctness evaluation employs the same  criterion  described  for  the  functional  implementation.  The  performance  criteria  include static code size (# of instructions), dynamic instruction length (# executed instructions), and stor- age requirements (total number of words in registers or memory, including stack memory). All of these metrics are used to determine the quality of the overall implementation.

 

Once  a  candidate  algorithm  is  selected,  an  implementation  is  created,  debugged,  tested,  and tuned. In MIPS assembly language, small changes to the implementation can have a large impact on overall execution performance. Often trade-offs arise between static code size, dynamic exe- cution  length,  and  operand  storage  requirements.  Creative  approaches  and  a  thorough  under- standing of the algorithm and programming mechanisms will often yield impressive results.

 

One final note on design strategy: while optimizing MIPS assembly language might, at times, seem like a job best left to automated processes (i.e., compilers), it underscores a key element of engineering. Almost all engineering problems require multidimensional evaluation of alternative design approaches. Knowledge and creativity are critical to effective problem solving.

 

Tips for success:

  • Play the game yourself until you are familiar with it.
  • Attempt to write out your logic for playing as though you were instructing a friend on how to play the game.
  • Translate this logic into computer code.
  • Be sure to start early! This project may appear deceptively easy.

 

Project Grading: The project weighting will be determined as follows:

part                                 description                                      due date 5:00pm            percent

P1-1    Minesweeper (C implementation)                         Fri., 28 September 2018          25

P1-2    Minesweeper (Assembly)                                        Fri., 12 October 2018

correct operation, technique & style                                                                25 static code size                                                                                                 15 dynamic execution length                                                                                25 operand storage requirements                                                                          10

total                                                                                                                        100

 

 

Honor Policy: In all programming assignments, you should design, implement, and test your own code. Any submitted assignment containing non-shell code that is not fully created and debugged by the student constitutes academic misconduct. You should not share code, debug code, or discuss its performance with anyone. Once you begin implementing your solution, you must work alone.

 

 

 

Good luck and happy coding!