Difference between revisions of "CSC103 Homework 4 Fall 2012"

From dftwiki3
Jump to: navigation, search
(Problem #4 (Optional and Extra Credits))
 
(41 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
--[[User:Thiebaut|D. Thiebaut]] 13:26, 11 October 2012 (EDT)
 
--[[User:Thiebaut|D. Thiebaut]] 13:26, 11 October 2012 (EDT)
 
----
 
----
<center>
+
<!--center>
 
<font size="+2">Page under construction!</font>
 
<font size="+2">Page under construction!</font>
 
<br \>[[File:UnderConstruction.jpg|300px]]
 
<br \>[[File:UnderConstruction.jpg|300px]]
</center>
+
</center-->
 
<br />
 
<br />
<bluebox>This homework is due on 10/18/12 at 9:00 a.m.</bluebox>
+
<bluebox>This homework is due on 10/18/12 at 9:00 a.m.  You can work in pairs on this homework, but only if the work is done only when both people are together, and not when they are apart.  If you work in pairs, simply put both names at the top of the document you will be handing in or submitting.</bluebox>
 
<br />
 
<br />
  
 
=Misc. Information=
 
=Misc. Information=
If you haven't already read it, there is a lot of good information in the [http://math.hws.edu/TMCM/java/labs/xComputerLab1.html Introdcution to the xComputer]] document.
+
If you haven't already read it, there is a lot of good information in the [http://math.hws.edu/TMCM/java/labs/xComputerLab1.html Introdcution to the xComputer] and [http://math.hws.edu/TMCM/java/labs/xComputerLab2.html Introduction to Assembly Language] documents.
  
 
=Problem #1=
 
=Problem #1=
Line 18: Line 18:
  
 
Note that I have added comments to the program.  This helps make a very cryptic program easier to understand.  In assembly language we can place comments in the code by preceding them with '''semicolons'''.  The words following a semicolons are ignored by the translator when it takes the assembly-language program and puts the ''mnemonics'' in memory.
 
Note that I have added comments to the program.  This helps make a very cryptic program easier to understand.  In assembly language we can place comments in the code by preceding them with '''semicolons'''.  The words following a semicolons are ignored by the translator when it takes the assembly-language program and puts the ''mnemonics'' in memory.
If the comments bother you, you can simply put your cursor on each semicolon and remove the text on the right hand-side of it.
+
If the comments bother you, you can simply put your cursor on each semicolon and remove the text on the right-hand side of it.
 
<br />
 
<br />
 
<code><pre>
 
<code><pre>
Line 28: Line 28:
  
 
@0
 
@0
      jmp start
+
        jmp start
  
 
;
 
;
 
; data section with 2 variables
 
; data section with 2 variables
 
;
 
;
counter: 100
+
 
sum: 0
+
counter: 10
 +
sum:     0
  
 
;
 
;
 
; code section
 
; code section
;  
+
;
 
start:
 
start:
  
 
; sum <- counter
 
; sum <- counter
lod counter
+
        lod   counter
sto sum
+
        sto   sum
  
 
; counter <- counter - 1
 
; counter <- counter - 1
 
loop:
 
loop:
lod counter
+
    lod   counter
dec
+
dec
sto counter
+
sto   counter
  
 
; if counter is 0, then jump out of loop
 
; if counter is 0, then jump out of loop
jmz done
+
 
 +
        jmz   done
  
 
; sum <- sum + counter
 
; sum <- sum + counter
lod sum
+
 
add counter
+
        lod   sum
sto sum
+
        add   counter
 +
        sto   sum
  
 
; go back to compute new sum
 
; go back to compute new sum
jmp loop
+
 
 +
        jmp   loop
  
 
; if we reach this point, then we are done with
 
; if we reach this point, then we are done with
 
; the loop and sum should contain the result
 
; the loop and sum should contain the result
done: hlt
+
 
 +
done:   hlt
 +
 
 +
 
 
</pre></code>
 
</pre></code>
  
 
Just to verify that the program works, copy/paste its code into the simulator (click [http://cs.smith.edu/~thiebaut/classes/103/applets.htm here] to get the applets).  Run the program by selecting the '' '''fastest speed''' '', and then clicking on '''Run'''.
 
Just to verify that the program works, copy/paste its code into the simulator (click [http://cs.smith.edu/~thiebaut/classes/103/applets.htm here] to get the applets).  Run the program by selecting the '' '''fastest speed''' '', and then clicking on '''Run'''.
 +
<br />
 +
 
;Question 1
 
;Question 1
 
: How many instructions are executed by the processor to compute the sum?  In other words, from the time the processor executes the first '''jmp start''' instruction, to the time it executes '''hlt''', how many instructions will it have executed, including the first and last?    Be precise in your answer!   
 
: How many instructions are executed by the processor to compute the sum?  In other words, from the time the processor executes the first '''jmp start''' instruction, to the time it executes '''hlt''', how many instructions will it have executed, including the first and last?    Be precise in your answer!   
Line 78: Line 87:
 
;Question 3
 
;Question 3
 
:How many instructions are executed by the processor to compute the sum of 0 to 100?
 
:How many instructions are executed by the processor to compute the sum of 0 to 100?
 +
<br />
  
 
;Question 4
 
;Question 4
: Assume that the processor has a 3 GHz crystal giving it the frequency of operation and that each instruction takes 1 cycle to execute.
+
: Assume that the processor operates at a 3 GHz frequency (given by the crystal).  Assume furthermore that each instruction takes 1 cycle to execute. In this case a cycle is 1 / 3,000,000,000 second, or 0.33 ns.  How long does it take the program to compute the sum of all the numbers between 0 and 10?  Between 0 and 100?  Between 0 and 1,000,000?
In this case a cycle is 1 / 3,000,000,000 second.  How long does it take the program to compute the sum of all the numbers between 0 and 10?  Between 0 and 100?  Between 0 and 1,000,000?
 
  
 
;As a reminder,  
 
;As a reminder,  
 
*0.001 sec = 1 ms (millisecond).
 
*0.001 sec = 1 ms (millisecond).
*0.000001 sec = 1 us (microsecond).
+
*0.000001 sec = 1 &micro;s (microsecond).
 
* 0.000000001 sec = 1 ns (nanosecond).
 
* 0.000000001 sec = 1 ns (nanosecond).
 +
 +
<br />
 +
 +
==Submission==
 +
 +
Hand in a copy of your answers on a sheet of paper, in class, on the due date.
  
 
=Problem #2=
 
=Problem #2=
  
<tanbox>You need to submit a printed version of the program for this question</tanbox>
+
<tanbox>You will need to submit your code electronically.  More information below.</tanbox>
  
Write an assembly language program that computes the sum of all the '''even''' numbers between 0 and 100.
+
Using the program of Problem #1 as inspiration, write an assembly language program that computes the sum of all the '''even''' numbers between 0 and 100.
  
 
Check your program on the simulator.
 
Check your program on the simulator.
  
Copy/paste a copy of your program in your favorite editor or word-processor and print a copy of it for submission.
+
 
 +
==Submission==
 +
 
 +
* Go to this URL: http://cs.smith.edu/~thiebaut/103/submit4.htm
 +
* You will see a simple submission form for your program.
 +
* Enter the 2 letters that identify your wiki account.  For example, if your wiki account was 103b-ac, then the two letters you need to enter in the box are '''ac'''.
 +
* Enter '''2''' for the problem number
 +
* Erase the line that reads
 +
 
 +
  ; Paste your program below this line (you may erase this line)
 +
 
 +
:and replace it by your name, preceded by a semicolon.  Example
 +
 
 +
  ; Mickey Mouse
 +
 
 +
:If you worked with a partner on this program, write both names on separate lines, each with a semicolon as the first character:
 +
 
 +
  ; Mickey Mouse
 +
  ; Donald Duck
 +
 
 +
 
 +
* Paste your code below the line containing your name(s).
 +
* Click on the '''submit''' button at the bottom of the page.
  
 
=Problem #3=
 
=Problem #3=
  
<tanbox>You need to submit a printed version of the program for this question</tanbox>
+
<tanbox>You need to submit your program electronically, as for Problem 2.</tanbox>
  
Write an assembly language program that computes 2 different sums, in 2 different variables, '''sum1''' and '''sum2'''.  When the program starts, both '''sum1''' and '''sum2''' contain 0.  When the program ends, '''sum1''' contains the sum of all the '''odd''' numbers between 0 and 100, and '''sum2''' contains the sum of all the '''even''' numbers between 0 and 100.
+
Write an assembly language program that computes 2 different sums, in 2 different variables, '''sum1''' and '''sum2'''.  When the program starts, both '''sum1''' and '''sum2''' contain 0.  When the program ends, '''sum1''' contains the sum of all the '''odd''' numbers between 0 and 100, and '''sum2''' contains the sum of all the '''even''' numbers between 0 and 100.  Write your program in such a way that you cannot assume that you already know that the sum of all the numbers between 0 and 100 is 5050.  In other words, the number 5050 should not appear in your program as a constant or declared initially in a variable.
  
 
===Recommentations===
 
===Recommentations===
* Keep an eye for efficiency, although I am more interested in your program computing the correct result than in how short they are.
+
* Keep an eye for efficiency.  A shorter program is usually better than a longer one, but a short program that does not compute the right answer is worth much less than a longer program that computes the correct information.
 
* Test your program with the simulator
 
* Test your program with the simulator
* There are several possible approaches.  My main criterion for this problem is for your program to compute the correct answers, but I will give extra credits for imaginative and elegant solutions.
+
* There are several possible approaches.  My main criterion for this problem is for your program to compute the '''correct''' answers, but it will make me especially happy to see imaginative and elegant solutions.
 +
 
 +
===Submission===
 +
* Follow the same steps as in Problem 2, but this time enter '''3''' in the Problem number box.
  
=Submission=
+
===Submission===
 
* Submit your answers on sheets of paper that should have your name on each one.  
 
* Submit your answers on sheets of paper that should have your name on each one.  
 
* Staple all the sheets of paper together, please!
 
* Staple all the sheets of paper together, please!
  
 
=Problem #4 (Optional and Extra Credits)=
 
=Problem #4 (Optional and Extra Credits)=
 +
<br />
 +
<tanbox>
 +
If you solve this problem, submit your code electronically, as for the previous 2 problems.
 +
</tanbox>
 +
<br />
 
* First, read the section on ''Indirect Addressing'' in [http://math.hws.edu/TMCM/java/labs/xComputerLab2.html this document].
 
* First, read the section on ''Indirect Addressing'' in [http://math.hws.edu/TMCM/java/labs/xComputerLab2.html this document].
* Then play with this program that uses ''indirect addressing'' with the '''sto-i''' instruction:
+
* Then play with the program below that uses ''indirect addressing'' with the '''sto-i''' instruction:
  
 
<br />
 
<br />
 
<code><pre>
 
<code><pre>
 
start:  
 
start:  
lod-c table ; get address of table in memory
+
lod-c table ; get address of table in AC
sto  loc ; store it in loc variable.  Now loc
+
sto  loc ; store it in loc variable.  Now loc
; contains the address of the first memory cell
+
; contains the address of the first memory cell
                  ; starting at table.
+
                ; starting at table.
 
loop:
 
loop:
lod   counter ; get counter in AC
+
lod    counter ; get counter in AC
sto-i loc ; store AC at address contained in loc variable
+
sto-i loc ; store AC at address contained in loc variable
  
inc ; increment AC
+
inc ; increment AC
sto   counter; store back in counter.  Now counter is greater by 1
+
sto   counter ; store back in counter.  Now counter is greater by 1
  
lod   loc ; increment loc variable to "point" to next  
+
lod   loc ; increment loc variable to "point" to next  
inc ; memory cell in RAM.
+
inc ; memory cell in RAM.
sto   loc
+
sto   loc
  
lod  counter ; get counter back
+
lod   counter   ; get counter back
sub-c 11 ; subtract 11 from counter
+
sub-c 11 ; subtract 11 from counter
jmz   done ; if AC is 0, then counter was 11.  We can stop.
+
jmz   done ; if AC is 0, then counter was 11.  We can stop.
 
 
jmp   loop ; otherwise, we loop back
+
jmp   loop ; otherwise, we loop back
  
 
done:
 
done:
Line 160: Line 205:
 
</pre></code>
 
</pre></code>
 
<br />
 
<br />
* Run the program.  Notice that it will store all the numbers from 1 to 10 in the 10 memory words starting with the variable '''table'''.
+
* Read the comments.  See if they make sense.  Try to figure out just by reading the program if you can tell what it's doing.  You need to understand the ''indirect addressing'' property of '''sto-i''' to fully see what is going on, so make sure to read and understand that section of the [http://math.hws.edu/TMCM/java/labs/xComputerLab2.html document] indicated earlier.
Below is an example of the memory contents once the program has finished running:
+
* Run the program.  Notice that it will store all the numbers from 1 to 10 in the 10 memory words starting with the variable '''table'''. Below is an example of the memory contents once the program has finished running:
  
 
<br /><center>[[Image:CSC103SimulatorHomework42012f.png|600px]]</center>
 
<br /><center>[[Image:CSC103SimulatorHomework42012f.png|600px]]</center>
 
<br />
 
<br />
 +
==Your Assignment==
 +
Your assignment for this optional and extra-credit part is to modify the program so that instead of storing the numbers 1 to 10 in memory, it '''computes''' and '''stores''' the  numbers 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512 in memory.
 +
 +
Below is an image of what the memory of my solution program looks like once it has finished executing.  Your data section should look similar, especially the numbers 1, 2, 4, ... 512 in successive memory words.
 +
 +
<br />
 +
<center>[[Image:CSC103Homework4Solution2_2012f.png|600px]]</center>
 +
<br />
 +
 +
==Submission==
 +
Follow the same steps as the programs for Problems 2 and 3, but enter '''4''' in the Problem Number box.
 +
<br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br /><br />
 +
<onlydft>
 +
==Submission software==
 +
* submit4.htm
 +
<code><pre>
 +
<html>
 +
<head>
 +
<title>CSC103 Upload Form</title>
 +
</head>
 +
<body>
 +
<h2>Upload Homework file for CSC103</h2>
 +
 +
<h3>Submission form for Homework 4</h3>
 +
<form enctype="multipart/form-data" action="upload4.php" method="POST">
 +
<P>
 +
<input type="hidden" name="hw" value="hw4" />
 +
<!--P>Which homework assignment (i.e. hw1,  hw2...)? <input type="text" name="hw" /-->
 +
 +
<P>
 +
<P>What are the two letters at the end of your wiki account number(i.e. aa, ab, ac,...ba, bb...)?
 +
<input type="text" name="account" />
 +
<P>
 +
 +
<!--Please choose a program file to upload: <input name="uploaded" type="file" /><br /-->
 +
<P>For which problem are you submitting a program (2, 3, or 4)?
 +
<input type="text" name="problem" />
 +
<P>
 +
<P>
 +
<textarea rows="30" cols="120" name="pde" wrap="physical">; Paste your program below this line (you may erase this line)
 +
 +
</textarea>
 +
<br />
 +
<P>
 +
<P>
 +
<input type="submit" value="Upload" />
 +
</form>
 +
</body>
 +
</html>
 +
</pre></code>
 +
 +
* upload4.php
 +
<code><pre>
 +
<?php
 +
 +
$allowedFiles = array( 'hw4_2.asm', 'hw4_3.asm', 'hw4_4.asm' );
 +
$hw    = $_POST[ "hw" ];
 +
$account = "103b-" . $_POST[ "account" ];
 +
$problem = $_POST[ "problem" ];
 +
 +
if ( strlen( $account ) != 7 ) {
 +
?>
 +
    <html><body><h2>Invalid 2-letter Id!</h2>
 +
    Please go back to the previous page and type in the correct 2-letter Id.
 +
    </body>
 +
    </html>
 +
<?php 
 +
    exit();
 +
}
 +
 +
$account = strtolower( $account );
 +
 +
if ( $account[5] != 'a' && $account[5] != 'b' ) {
 +
    ?>
 +
  <html>
 +
  <body>
 +
  <h2>Invalid 2-letter Id. First letter should be a or b</h2>
 +
  Please go back to the previous page and enter a correct 2-letter Id.
 +
  </body>
 +
  </html>
 +
  <?php
 +
  exit();
 +
}
 +
 +
if ( $account[6] < 'a' || $account[6] > 'z' ) {
 +
?>
 +
  <html>
 +
  <body>
 +
<h2>Invalid 2-letterId</h2>
 +
  Please go back to the previous page and enter a correct 2-letter Id.
 +
  </body>
 +
  </html>
 +
  <?php
 +
  exit();
 +
}
 +
 +
// if we're here, everything went fine
 +
 +
$target = "uploads";
 +
$target = $target . "/" . $hw;
 +
mkdir( $target, 0777 );
 +
$target = $target .  "/" . $account;
 +
mkdir( $target, 0777 );
 +
$target = $target . "/program" . $problem;
 +
$ok=1;
 +
 +
 +
$fp = fopen( $target, "w" );
 +
fwrite( $fp, $_POST[ "pde" ] );
 +
fwrite( $fp, "\n" );
 +
fclose( $fp );
 +
 +
if( true )  {
 +
  ?>
 +
  <html><body>
 +
  <h2>Success!</h2>
 +
  Your Assembly program has been uploaded and saved in your instructor's directory.
 +
  <P><P>You are done with this part of the  homework!
 +
  </body></html>
 +
  <?php
 +
}
 +
else {
 +
  ?>
 +
  <html><body>
 +
  <h2>Error!</h2>
 +
  Sorry, there was a problem uploading your file...
 +
  <P>Please try again...
 +
  </body></html>
 +
  <?php
 +
}
 +
 +
 +
?>
 +
</pre></code>
 +
</onlydft>
 +
[[Category:CSC103]][[Category:Homework]]

Latest revision as of 22:19, 11 October 2012

--D. Thiebaut 13:26, 11 October 2012 (EDT)



This homework is due on 10/18/12 at 9:00 a.m. You can work in pairs on this homework, but only if the work is done only when both people are together, and not when they are apart. If you work in pairs, simply put both names at the top of the document you will be handing in or submitting.


Misc. Information

If you haven't already read it, there is a lot of good information in the Introdcution to the xComputer and Introduction to Assembly Language documents.

Problem #1

You can hand-write the answers to this problem. Typed and printed answers are also acceptable, of course.


The program below computes the sum of all the numbers between 0 and 10. It is the final version of the program we developed in class on Thursday 10/11/12.

Note that I have added comments to the program. This helps make a very cryptic program easier to understand. In assembly language we can place comments in the code by preceding them with semicolons. The words following a semicolons are ignored by the translator when it takes the assembly-language program and puts the mnemonics in memory. If the comments bother you, you can simply put your cursor on each semicolon and remove the text on the right-hand side of it.

; Sum100 program
; D. Thiebaut
; Computes the sum of all the numbers between 0 and 10
; and stores the result in variable sum.
;

@0
        jmp start

;
; data section with 2 variables
;

counter: 10
sum:     0

;
; code section
;
start:

; sum <- counter
         lod    counter
         sto    sum

; counter <- counter - 1
loop:
     	 lod    counter
	 dec
	 sto    counter

; if counter is 0, then jump out of loop

         jmz    done

; sum <- sum + counter

         lod    sum
         add    counter
         sto    sum

; go back to compute new sum

         jmp    loop

; if we reach this point, then we are done with
; the loop and sum should contain the result

done:    hlt


Just to verify that the program works, copy/paste its code into the simulator (click here to get the applets). Run the program by selecting the fastest speed , and then clicking on Run.

Question 1
How many instructions are executed by the processor to compute the sum? In other words, from the time the processor executes the first jmp start instruction, to the time it executes hlt, how many instructions will it have executed, including the first and last? Be precise in your answer!


Question 2
How do you modify the program to make it compute the sum of 0 to 100?


Question 3
How many instructions are executed by the processor to compute the sum of 0 to 100?


Question 4
Assume that the processor operates at a 3 GHz frequency (given by the crystal). Assume furthermore that each instruction takes 1 cycle to execute. In this case a cycle is 1 / 3,000,000,000 second, or 0.33 ns. How long does it take the program to compute the sum of all the numbers between 0 and 10? Between 0 and 100? Between 0 and 1,000,000?
As a reminder,
  • 0.001 sec = 1 ms (millisecond).
  • 0.000001 sec = 1 µs (microsecond).
  • 0.000000001 sec = 1 ns (nanosecond).


Submission

Hand in a copy of your answers on a sheet of paper, in class, on the due date.

Problem #2

You will need to submit your code electronically. More information below.

Using the program of Problem #1 as inspiration, write an assembly language program that computes the sum of all the even numbers between 0 and 100.

Check your program on the simulator.


Submission

  • Go to this URL: http://cs.smith.edu/~thiebaut/103/submit4.htm
  • You will see a simple submission form for your program.
  • Enter the 2 letters that identify your wiki account. For example, if your wiki account was 103b-ac, then the two letters you need to enter in the box are ac.
  • Enter 2 for the problem number
  • Erase the line that reads
  ; Paste your program below this line (you may erase this line)
and replace it by your name, preceded by a semicolon. Example
  ; Mickey Mouse
If you worked with a partner on this program, write both names on separate lines, each with a semicolon as the first character:
  ; Mickey Mouse
  ; Donald Duck


  • Paste your code below the line containing your name(s).
  • Click on the submit button at the bottom of the page.

Problem #3

You need to submit your program electronically, as for Problem 2.

Write an assembly language program that computes 2 different sums, in 2 different variables, sum1 and sum2. When the program starts, both sum1 and sum2 contain 0. When the program ends, sum1 contains the sum of all the odd numbers between 0 and 100, and sum2 contains the sum of all the even numbers between 0 and 100. Write your program in such a way that you cannot assume that you already know that the sum of all the numbers between 0 and 100 is 5050. In other words, the number 5050 should not appear in your program as a constant or declared initially in a variable.

Recommentations

  • Keep an eye for efficiency. A shorter program is usually better than a longer one, but a short program that does not compute the right answer is worth much less than a longer program that computes the correct information.
  • Test your program with the simulator
  • There are several possible approaches. My main criterion for this problem is for your program to compute the correct answers, but it will make me especially happy to see imaginative and elegant solutions.

Submission

  • Follow the same steps as in Problem 2, but this time enter 3 in the Problem number box.

Submission

  • Submit your answers on sheets of paper that should have your name on each one.
  • Staple all the sheets of paper together, please!

Problem #4 (Optional and Extra Credits)


If you solve this problem, submit your code electronically, as for the previous 2 problems.


  • First, read the section on Indirect Addressing in this document.
  • Then play with the program below that uses indirect addressing with the sto-i instruction:


start: 
	lod-c table	; get address of table in AC
	sto   loc	; store it in loc variable.  Now loc
			; contains the address of the first memory cell
                	; starting at table.
loop:
	lod    counter	; get counter in AC
	sto-i  loc	; store AC at address contained in loc variable

	inc		; increment AC
	sto    counter	; store back in counter.  Now counter is greater by 1

	lod    loc	; increment loc variable to "point" to next 
	inc		; memory cell in RAM.
	sto    loc

	lod    counter   ; get counter back
	sub-c  11 	 ; subtract 11 from counter
	jmz    done	 ; if AC is 0, then counter was 11.  We can stop.
	
	jmp    loop	 ; otherwise, we loop back

done:
	hlt

; data section
;
table:   0
         0
         0
         0
         0
         0
         0
         0
         0
         0
loc:     0
counter: 1


  • Read the comments. See if they make sense. Try to figure out just by reading the program if you can tell what it's doing. You need to understand the indirect addressing property of sto-i to fully see what is going on, so make sure to read and understand that section of the document indicated earlier.
  • Run the program. Notice that it will store all the numbers from 1 to 10 in the 10 memory words starting with the variable table. Below is an example of the memory contents once the program has finished running:

CSC103SimulatorHomework42012f.png


Your Assignment

Your assignment for this optional and extra-credit part is to modify the program so that instead of storing the numbers 1 to 10 in memory, it computes and stores the numbers 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512 in memory.

Below is an image of what the memory of my solution program looks like once it has finished executing. Your data section should look similar, especially the numbers 1, 2, 4, ... 512 in successive memory words.


CSC103Homework4Solution2 2012f.png


Submission

Follow the same steps as the programs for Problems 2 and 3, but enter 4 in the Problem Number box.














...