forked from uva-cs/pdr
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
236 lines (236 loc) · 17.9 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="generator" content="pandoc">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<title>PDR: Laboratory 7: IBCM Programming</title>
<style type="text/css">code{white-space: pre;}</style>
<link rel="stylesheet" href="../../markdown.css">
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="pdr-laboratory-7-ibcm-programming">PDR: Laboratory 7: IBCM Programming</h1>
<p><a href="../index.html">Go up to the Labs table of contents page</a></p>
<h3 id="objective">Objective</h3>
<p>To become familiar with programming with IBCM and understand how high-level language programs are represented at the machine level.</p>
<h3 id="background">Background</h3>
<p>IBCM (Itty Bitty Computing Machine) is a simulated computer with a minimal instruction set. Despite its tiny instruction set, IBCM can compute anything that a modern computer can.</p>
<h3 id="tutorial">Tutorial</h3>
<p>The tutorial for this lab is the remainder of the <a href="https://en.wikibooks.org/wiki/Bash_Shell_Scripting">Wikibooks article on Bash Shell Scripting</a>. The tutorial will be necessary for the post-lab, though you may read through it earlier if you'd like.</p>
<h3 id="recommended-readings">Recommended Readings</h3>
<ol type="1">
<li>Read the <a href="../../slides/07-ibcm.html">slides on IBCM</a></li>
<li>Read <a href="../../book/ibcm-chapter.pdf">IBCM book chapter</a> (PDF), especially sections 1.6 (Writing IBCM Programs) and 1.7 (Example Programs)</li>
<li>Run IBCM code online <a href="https://pegasus.cs.virginia.edu/ibcm/">here</a>. The sample code in the book chapter is also in the repo: <a href="../../ibcm/summation.ibcm">summation.ibcm</a> and <a href="../../ibcm/array-summation.ibcm">array-summation.ibcm</a></li>
</ol>
<h2 id="procedure">Procedure</h2>
<h3 id="pre-lab">Pre-lab</h3>
<ol type="1">
<li>Write two IBCM programs to familiarize yourself with IBCM</li>
<li>Files to download: None</li>
<li>Files to submit: addition.ibcm, array.ibcm</li>
</ol>
<h3 id="in-lab">In-lab</h3>
<ol type="1">
<li>Implement bubble sort in IBCM</li>
<li>Files to download: <a href="bubblesort.cpp.html">bubblesort.cpp</a> (<a href="bubblesort.cpp">src</a>)</li>
<li>Files to submit: bubblesort.ibcm</li>
</ol>
<h3 id="post-lab">Post-lab</h3>
<ol type="1">
<li>Implement a quine in IBCM</li>
<li>Improve your <code>averagetime.sh</code> shell script by adding control structures</li>
<li>Files to download: <a href="counter.cpp.html">counter.cpp</a> (<a href="counter.cpp">src</a>), <a href="timer.cpp.html">timer.cpp</a> (<a href="timer.cpp">src</a>), <a href="timer.h.html">timer.h</a> (<a href="timer.h">src</a>)</li>
<li>Files to submit: quine.ibcm, averagetime.sh</li>
</ol>
<hr />
<h2 id="pre-lab-1">Pre-lab</h2>
<p>For the pre-lab, you will need to write two IBCM programs. The programs will need to have an .ibcm extension when submitting, but they are text files, so you can still edit them in Emacs.</p>
<h3 id="addition.ibcm">addition.ibcm</h3>
<p>Write an IBCM program that:</p>
<ul>
<li>Gets three values from user input</li>
<li>Stores the values into three variables</li>
<li>Adds the variables together, and prints the sum (you may use additional memory if you wish)</li>
<li>If the sum is zero, prints the three values and stops</li>
<li>If the sum is not zero, starts over (tries to get three values, etc.)</li>
</ul>
<h3 id="sample-addition.ibcm-run">Sample addition.ibcm Run</h3>
<p>Below is a sample execution run to show you the input and output format we are looking for. The output shown is a result of running addition.ibcm in the ibcm simulator.</p>
<pre><code># input
1
2
3
-1
-2
3
# output
0006
0000
ffff
fffe
0003</code></pre>
<h3 id="array.ibcm">array.ibcm</h3>
<p>Write another IBCM program that reads in an array and prints its elements forwards and backwards. Your program will first be given the <strong>array size</strong> <em>n</em> as input. The next <em>n</em> lines of input will contain the contents of the array.</p>
<ul>
<li>The array base address is hard-coded into memory, meaning it's a pre-set value that isn't obtained by user input. We will be inputting arrays of many different sizes into your program, so make sure you carefully choose where to store your array in memory.</li>
<li>Before your program halts, it should print out the array both forwards and backwards.</li>
</ul>
<p>You <strong><em>MUST</em></strong> iterate through the array by creating the array load instruction, similarly as was done in lecture in the <a href="../../ibcm/array-summation.ibcm">array-ssummation.ibcm</a> program. You may <strong><em>NOT</em></strong> have a series of separate instructions to each load a separate value from the array -- such a program will receive zero credit.</p>
<h3 id="sample-array.ibcm-run">Sample array.ibcm Run</h3>
<p>Below is a sample execution run to show you the output we are looking for. The output shown is a result of running array.ibcm in the ibcm simulator.</p>
<pre><code># input
# First input is size of the array (3)
# Next inputs are the array contents (1,2,3)
3
1
2
3
# output
0001
0002
0003
0003
0002
0001</code></pre>
<h3 id="writing-ibcm-code">Writing IBCM Code</h3>
<p>You <strong>MUST</strong> comment your IBCM code copiously. This means (practically) every line should have a comment describing what you are doing. However, you cannot have a line that is only comments, as the emulator will have trouble reading that line! The examples provided in the handouts posted on the course website and discussed in class illustrate a good way of doing this, where there are columns for each of the following:</p>
<ol type="1">
<li>the hexadecimal values that will go into that memory location</li>
<li>the address of that memory location</li>
<li>labels for jumps or variable names</li>
<li>the operation-name for the instruction on that line</li>
<li>a symbolic name for the address the instruction references</li>
<li>comments (that explain what's happening in a higher-level form)</li>
</ol>
<p>Note that together the operation name and the address are sort of an assembly language version of the hexadecimal version of the operations in the first column. You probably want to write those first, and then turn these into the hex instruction that will go into column 1.</p>
<p>The simulator will only read the first 4 characters on each line of a file. So you can't have entire lines with comments, or blank lines. The simulator can't handle these (and doesn't check for this), and you will get a strange error.</p>
<h3 id="running-ibcm-code">Running IBCM Code</h3>
<p>You may run your IBCM code via the online simulator at <a href="https://pegasus.cs.virginia.edu/ibcm/" class="uri">https://pegasus.cs.virginia.edu/ibcm/</a>.</p>
<p>Beware of the following quirks of the simulator:</p>
<ul>
<li>If your code contains an infinite loop, the simulator will hang your browser</li>
<li>The simulator will not work if there are blank lines at the end of the file</li>
</ul>
<h3 id="submission">Submission</h3>
<p>Submit addition.ibcm and array.ibcm with comments explaining your code. <strong>Your files MUST be called addition.ibcm and array.ibcm exactly</strong>.</p>
<h3 id="hints">Hints</h3>
<h4 id="leave-room-for-mistakes">Leave room for mistakes</h4>
<p>Sprinkle some <code>nop</code> (opcode: B) instructions throughout your program that can be replaced later in case you realize that you need some extra variables or are missing some instructions.</p>
<h4 id="working-with-arrays">Working with arrays</h4>
<p>Arrays can be difficult to work with in IBCM given the extremely limited instruction set. We'll walk through the array summation example again from the slides to point out some helpful concepts.</p>
<p>How do you add variables in IBCM? Why, with the <code>add</code> instruction, of course.<br />
However, for arrays, the address you want to <code>add</code> from changes every time! How do we account for that?</p>
<p>We need to dynamically change the <code>add</code> instruction before executing it to make it point to the right address. If we can generate the appropriate instruction based off of the starting address of the array and the index we want (hint: look back to lab 4), we can then <code>store</code> that later on in our program to execute automatically!</p>
<p>Thus, if we wanted to sum an array, we would:</p>
<ol type="1">
<li>Create a variable set to <code>5000</code> -- notice how it's just an <code>add</code> instruction without an address. This is <code>adit</code> in the slides.</li>
<li>Load that instruction into the accumulator</li>
<li>Use actual <code>add</code> instructions to add the base array address <code>a</code> and the current array index <code>i</code> to the accumulator
<ul>
<li>The accumulator should now contain something like <code>5xyz</code>, where <code>xyz</code> is the location of <code>a[i]</code> in your program.</li>
<li>The accumulator now contains a valid <code>add</code> instruction!</li>
</ul></li>
<li>Store that instruction in the line where step 6 would be running</li>
<li>Load your accumulated sum</li>
<li>Whatever was here previously was overwritten by step 4, and so now we execute the instruction <code>5xyz</code> to add the value of <code>a[i]</code> to the sum. This is <code>doit</code> in the slides.</li>
<li>Store the sum!</li>
<li>Repeat steps 2-7 until the end of the array</li>
</ol>
<p>While this deals specifically with the example in the slides, it will hopefully clarify the general approach of iterating through arrays and give you more insight into how to print them out.</p>
<hr />
<h2 id="in-lab-1">In-lab</h2>
<h3 id="bubble-sort">Bubble sort</h3>
<p>Download and look at the <a href="bubblesort.cpp.html">bubblesort.cpp</a> (<a href="bubblesort.cpp">src</a>) algorithm. You will need to read in 10 array elements and sort them with this algorithm in IBCM.</p>
<p>To encode this program, follow these steps:</p>
<ol type="1">
<li>Write up high-level pseudo-code for your design on paper (make sure that it is absolutely correct, or you will probably regret it later)</li>
<li>Refine this pseudo-code, making it closer to the assembly code level</li>
<li>Alter your code into IBCM assembly code with labels instead of addresses</li>
<li>Run through a sufficient number of test cases by hand of your IBCM code from step (3) to convince yourself that it is correct</li>
<li>Encode into actual hex IBCM code and addresses, and test it using the simulator</li>
<li>Identify and fix the errors that you did not pick up in the previous steps</li>
</ol>
<p>The file should be called bubblesort.ibcm. As with the last assignment, you <em>MUST</em> comment your code.</p>
<p><strong>NOTE:</strong> Just like for the pre-lab array.ibcm file, you must create an array load instruction. If your program has separate instructions for loading separate values from the array, you will receive zero credit for this in-lab.</p>
<h3 id="sample-execution-run">Sample Execution Run</h3>
<p>Below is a sample execution run to show you the output we are looking for. The output shown is a result of running array.ibcm in the ibcm simulator.</p>
<pre><code># input
# Note that we are NOT providing the array size as input
# because it always 10. Input is the 10 array elements unsorted.
2
3
4
8
1
5
9
0
6
7
# output
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009</code></pre>
<hr />
<h2 id="post-lab-1">Post-lab</h2>
<h3 id="quines">Quines</h3>
<p>For the postlab, you will be writing an IBCM program that prints itself. This type of program is known as a <em>quine</em>.</p>
<blockquote>
<p>quine: /kwi:n/ /n./ [from the name of the logician Willard van Orman Quine, via Douglas Hofstadter] A program that generates a copy of its own source text as its complete output. Devising the shortest possible quine in some given programming language is a common hackish amusement.</p>
</blockquote>
<p>Wikipedia has a good <a href="https://en.wikipedia.org/wiki/Quine_%28computing%29">article about quines</a>, including examples in a few programming languages. The smallest C/C++ quine is described <a href="https://www.ioccc.org/1994/smr.hint">here</a> for your enjoyment.</p>
<p>While at first this idea may sound like a serious mind-bender, in reality it is a rather short program that is not too tough to do in IBCM. Your program will be carefully crafted to only print itself out and will most likely contain very specific information such as a variable that holds the length of the program.</p>
<p>The lines you print out may differ from the original file read into the IBCM simulator in a couple of places; as long as your output is still a valid quine that can be executed to output itself yet again, you do not have to worry about those differences. It is possible to write this program in as few as 8 lines of IBCM code, but most likely you will have closer to 15-20 lines.</p>
<p>You may <strong><em>NOT</em></strong> submit a zero line quine! Even though this is technically valid, it will not earn credit for this lab.</p>
<p>We will test your program by running it, recording the output, and running that output as a program. You should do the same.</p>
<h3 id="more-shell-scripting">More shell scripting</h3>
<p>The tutorial for this lab is the remainder of the <a href="https://en.wikibooks.org/wiki/Bash_Shell_Scripting">Wikibooks article on Bash Shell Scripting</a>.</p>
<p>For this lab, you will need to work a bit more on the shell script that you wrote for the last lab. The shell script will also compute the average running time for 5 executions of a program. The difference is that you will be using control structures, such as conditionals (if-then-else) and loops (for or while) in this shell script.</p>
<p>First, download the <a href="counter.cpp.html">counter.cpp</a> (<a href="counter.cpp">src</a>), <a href="timer.cpp.html">timer.cpp</a> (<a href="timer.cpp">src</a>), and <a href="timer.h.html">timer.h</a> (<a href="timer.h">src</a>) files. The timer program has been modified from lab 6 to print out the time in milliseconds. counter.cpp doesn't actually do anything useful; it just takes in a numeric command line parameter <em>e</em> and runs through an idle loop 10<sup><em>e</em></sup> times. You should not enter a value for <em>e</em> greater than 9, as 10<sup>9</sup> (1 billion) is the largest power of 10 that an <code>int</code> value can hold. On a modern computer, entering 9 as the parameter should take between 1 and 5 seconds to run.</p>
<p>Do not compile your program with <code>-O2</code>, as clang++ is smart enough to recognize that your for loop is not doing any work and will remove it from the optimized binary!</p>
<p>Your <code>averagetime.sh</code> shell script should take in the number of iterations as a single input value (not as a command line parameter). If that input is <code>quit</code>, then the script should exit. Otherwise, execute the program a total of 5 times, printing and keeping track of the execution time taken for each one. Your script should then print the average time taken for each execution. <strong>You MUST call your executable program <code>a.out</code> in your shell script.</strong></p>
<p>Your shell script <strong>MUST</strong> have an <code>if</code> statement (to see if it should exit), and <strong>MUST</strong> have a <code>for</code> or <code>while</code> loop. The number of times to iterate through the <code>for</code> or <code>while</code> loop (initially set to 5) should be a variable set previously in the script.</p>
<p>Below are a few notes to keep in mind when writing your shell script. Bash is a very powerful language, but it can be rather finicky and unforgiving with syntax.</p>
<ul>
<li>Your program should be called <code>averagetime.sh</code>, and should have <code>#!/bin/bash</code> as the very first line of the script</li>
<li>When setting variables, do <strong>NOT</strong> have spaces around the equals sign</li>
<li>When adding up values (using arithmetic expansion <code>$(( ... ))</code>), there <strong>SHOULD</strong> be spaces around the arithmetic operators as well as an equals sign within the parentheses.</li>
<li>A <code>for</code> loop requires a <code>do</code> keyword before the for loop body; likewise, an <code>if</code> statement has a <code>then</code> before the body. Either these words must be on the next line, or a semi-colon must be there before the <code>do</code> or <code>then</code></li>
<li>To grab program output (such as the output of the binary program), you use back quotes (i.e. `)</li>
<li>To execute your script, you can just enter <code>./averagetime.sh</code>. If your computer denies you permission, remind it who's boss and put it in its place with <code>chmod +x averagetime.sh</code>. This tells your Unix system that averagetime.sh is a program that can be executed (remember chmod?).</li>
</ul>
<p>Below is the output when we wrote this shell script. Obviously, your times may vary.</p>
<pre><code>enter the exponent for counter.cpp:
9
Running iteration 1...
time taken: 1256 ms
Running iteration 2...
time taken: 1232 ms
Running iteration 3...
time taken: 1238 ms
Running iteration 4...
time taken: 1240 ms
Running iteration 5...
time taken: 1256 ms
5 iterations took 6222 ms
Average time was 1244 ms</code></pre>
<h3 id="hints-1">Hints</h3>
<h4 id="thinking-about-the-quine-is-hurting-my-head">Thinking about the quine is hurting my head :(</h4>
<p>The most important thing to remember is that there is no distinction between instructions and variables in IBCM!</p>
<p>What is one way you can figure out what instructions your program contains?<br />
Hint: You know how to iterate through arrays; is there any way you could apply that concept here?</p>
<h4 id="comparing-values-in-bash">Comparing values in Bash</h4>
<p>If you want to compare values in an if or while expression (such as the bash equivalent of <code>while (i < s)</code>), you should see <a href="https://tldp.org/HOWTO/Bash-Prog-Intro-HOWTO-7.html">here</a>. In particular, you need to use <code>-lt</code> for the less than operator, and square brackets instead of the parentheses.</p>
</body>
</html>