Homework 2: When Harry Met Sally

ECE 2035 Homework 2: When Harry Met Sally
Summary: This assignment explores the use of basic conditional execution, nested iteration, and
memory accesses to analyze time/space data such as information collected by GPS-enabled
applications In particular, you will write a program that analyzes two timelines, each of which
gives a history of major cities in which a person has lived in chronological order. Your program
will determine the earliest year in which both people lived in the same city.
Data in each timeline TL is stored as a sparse vector of ten elements in the following format (for
i=0, 1, …, 4):
TL[i*2] = Duration: number of years a person lived in the city
that is specified in TL[i*2+1].
TL[i*2+1] = City in which the person lived for TL[i*2] years.
Objective: For this assignment, you will write two programs, one in C and one in MIPS, to
compute the earliest year at which Harry and Sally both lived in the same city. More details are
described below.
Assume that the two people were both born in the year 1990 and the current year is 2019. So the
total number of years (sum of TL[i*2] for i=0,1,…,4) is always 30. Each city is an integer
between 0 and 9, inclusive. Also, assume that the total number of moves in each timeline is
exactly five. For example, the timelines shown in Figure 1 are represented in C as:
HarryTimeline[] = {4, 4, 9, 3, 3, 8, 2, 4, 12, 2};
SallyTimeline[] = {1, 3, 11, 2, 4, 4, 6, 2, 8, 4};
Miami has city code 4 and Harry spent 4 years living there, then moved to Atlanta (city code 3),
where he lived for 9 years. For this example, your program should compute 2008 as the correct
answer.
Figure 1: Timelines showing how long Harry and Sally lived in certain cites. The earliest year in which they both
lived in the same city is 2008 (when Harry moved to Paris where Sally was already living).
Note that this sparse vector representation is much more storage efficient than storing the city for
each time point in the range 1990-2019.
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. The only exception to this is that
you may use code provided in tutorial-0.zip or in the examples on the course website/Canvas as
a starting point for your programs (http://ece2035.ece.gatech.edu/examples/index.html or
CanvasFilesLecture SlidesCode Examples).
HW2-1: For this part, design and implement a C program to compute and print the earliest year
at which Harry and Sally both lived in the same city. If there is no year in which they are both in
the same city, print 0.
1
ECE 2035 Homework 2: When Harry Met Sally
As a starting point, use the file HW2-1-shell.c. This program includes a reader function
Load_Mem that loads the values from a text file. You should use gcc under Linux/Unix to
develop your program. Sample test files (fa19-test1990.txt, fa19-test0.txt, fa19-
test2004.txt, fa19-test2008.txt) are provided – the number in the name of each file
indicates the correct answer. You should compile and run your program using the Linux
command lines:
gcc HW2-1.c –g –Wall –o HW2-1
./HW2-1 fa19-test2008.txt
You can create additional test files: using MiSaSiM to run HW2-2-shell.asm, go to the end
of the trace, and use the “Dump” memory menu button to save the memory to a text file with the
correct answer (the value in $3) in the name of the file.
Name the file HW2-1.C and upload it to Canvas by the scheduled due date.
HW2-2: For this part, design and implement a MIPS version of your program. A description of
the MIPS library routines you need is given below. Use the file HW2-2-shell.asm as a
starting point. The result should be stored by your program in $2 and reported as an answer by
software interrupt swi 587 as described below. You must use these register conventions or the
automated grader will score your program incorrectly. Memory should only be used for input to
your program. 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. Name the file HW2-2.asm and upload it to Canvas by the scheduled due date.
MIPS Library Routine: There are two library routines (accessible via the swi instruction).
SWI 597: Create Duration Timelines: This routine generates and displays the timelines as
shown in the example in Figure 1. It initializes memory with the 20 integers beginning at the
specified base address (e.g., Harry). INPUTS: $1 should contain the base address of the 20
words (80 bytes total) already allocated in memory. OUTPUTS: the 20 words allocated in
memory contain the 20 sparse vector elements (alternating duration and city) to be used as input
data.
SWI 587: Report Earliest Overlap: This routine allows you to report your answer and an
oracle provides the correct answer so that you can validate your code during testing.
INPUTS: $2 should contain the year you computed as your answer.
OUTPUTS: $3 gives the correct answer.
If you call swi 587 more than once in your code, only the first answer that you provide will be
recorded.
Easter egg: As a debugging feature, you can load in a previously dumped testcase (pair of timelines) by putting -1 into register $2 before you call swi 597. This will tell swi 597 to prompt for
an input txt file that contains a testcase (e.g., fa19-test1990.txt).
2