Background Finding the lowest cost path through a graph is a

Background: Finding the lowest cost path through a graph is a common challenge in many applications. While it can be an expensive process in general, often constraints of the graph structure simplify the search. In this project, we’ll examine exiting a diamond grid (shown tilted 45 degrees counterclockwise below). The weights between points are randomly generated integers between -99 and 99, inclusive. Non-participating array cells (the padding) have weights set to 10,000. Note that the linearized array offset is shown in blue in each square. The goal is to find the minimum cost path between the center and any exit edge where cost is the sum of all weights encountered along the path. All paths must have a length of five squares not counting the center square. The problem is considerably more difficult if this path requirement is relaxed.  

Assembly Level Implementation ; write the performance-focused version of the DiamondSearch program in MIPS assembly. . A shell program (P1-2-shell.asm) is provided to get you started. Rename it to P1-2.asm. Your code should store the cost of the minimum path in $4 and then call swi 591. Weights are generated (through the Create Diamond SWI 514) in memory as a padded two dimensional array of size 11 by 11. (Think of the diamond above as part of a larger 11 x 11 grid tilted 45 degrees counterclockwise.) Library Routine: There are two library routines (accessible via the swi instruction). SWI 514: Create Diamond: This routine initializes memory beginning at the specified base address with 121 entries representing the incoming weights and padding values for the 11 x 11 array. A pop up window graphically represents the map. INPUTS: $1 should contain the base address (memory should already be allocated). OUTPUTS: 121 values stored in memory. The generated map is mutable (i.e., your program may modify it). The entire memory contents can be dumped to a file using the “Dump” menu button. If this is performed immediately following execution of the Create Diamond SWI, the resulting map can be read into the C version to establish the weight array using the Load_Mem function in P1-1shell.c. SWI 591: Minimum Cost Path: This routine allows you to specify the cost of the shortest path that your code has identified. INPUTS: $4 should contain an integer. This answer is used by an automatic grader to check the correctness of your code. OUTPUTS: $3 gives the correct answer. You can use this to validate your answer during testing. If you call swi 591 more than once in your code, only the first answer that you provide will be recorded.

SHELL CODE:

# This program finds the shortest path out of a diamond of weighted squares.
#
# <insert date> <Your Name>

.data
Array:   .alloc   121   # allocate static space for padded weight map

.text
PathOut:   addi   $1, $0, Array   # set memory base
swi   514       # create weight map in memory

# your code goes here

   addi $4, $0, 42   # TEMP: give 42 as the answer
       swi 591 # report the answer
       jr   $31       # return to caller

Diamond Search 1.0 41 65 98 64 51 -41 32 74 15 85 53 84 12 29 94 43 105 85 34 45 59 59 53 59 15 9 76 85 92 10-8 15 co 69 30 78 85 17 41 2 40 40 >

Solution

#include <stdio.h>
#include <stdlib.h>

#define ArraySize 121

int main(int argc, char *argv[]) {
int Array[ArraySize];
int Length, MinCost = 10000;
int Load_Mem(char *, int *);

if (argc != 2) {
printf(\"usage: P1-1 valuefile\ \");
exit(1);
}
Length = Load_Mem(argv[1], Array);
if (Length != ArraySize) {
printf(\"valuefile does not contain valid data.\ \");
exit(1);
}

int a=0;

int b=0;
int col=0;
int row=0;
int c=0;
int cj=0;
int ck=0;
int cost[121];
for(a=0; a<121; a++){
cost[a]=10000;
}
for (row=5; row<11; row++){
for(col=5; col<11; col++){
a=row*11+col;
if (cost[a]>=10000)
cost[a]=0;
b=((row+1)*11)+col;
c=(row*11)+(col+1);
cj=cost[a]+Array[b];
ck=cost[a]+Array[c];

printf(\"cost Mat-> cur:(%d,%d):[%d], row+1: [%d], col+1: [%d]\ \",row,col, cost[a],cj,ck );

if (cj<cost[b])
cost[b]=cj;
if (ck<cost[c])
cost[c]=ck;
}
}
int MinCost=10000;
for (int u=65; u<=115; u+=10){
if(MinCost>cost[u])
MinCost=cost[u];
else
MinCost=MinCost;
}
/* include this print statement. */
printf(\"The shortest path cost is [%d]\ \", MinCost);
return 0;
printf(\"\ \");
printf(\"\ \");
}

int Load_Mem(char *InputFileName, int IntArray[]) {

int   N, Addr, Value, NumVals;
FILE   *FP;

FP = fopen(InputFileName, \"r\");
if (FP == NULL) {
printf(\"%s could not be opened; check the filename\ \", InputFileName);
return 0;
} else {
for (N=0; N < ArraySize; N++) {
NumVals = fscanf(FP, \"%d: %d\", &Addr, &Value);
if (NumVals == 2)
IntArray[N] = Value;
else
break;
}
fclose(FP);
return N;
}
}