Your exercise answers are saved by the browser in local storage
associated with this webpage. You can use the buttons below
to load/save the answers on your system.
Save all answers:
Load all answers (this will overwrite any answers currently saved by the browser):
Authored by Chris Terman
Procedures and Stacks
When entering numeric values in the answer fields, you can use
integers (1000, 0x3E8, 0b1111101000), floating-point numbers
(1000.0), scientific notation (1e3), engineering scale factors
(1K), or numeric expressions (3*300 + 100).
Problem 1. Beta ISA
For each of the Beta instruction sequences shown below, indicate the
values of the specified registers after the sequence has been
executed by an unpipelined Beta. Consider each sequence separately
and assume that execution begins at location 0 and halts when the
HALT() instruction is about to be executed. Also assume that all
registers have been initialized to 0 before execution begins.
Remember that even though the Beta reads and writes 32-bit
words from memory, all addresses are byte addresses, i.e.,
the addresses of successive words in memory differ by 4.
You can find detailed descriptions of each Beta instruction in
the "Beta Documentation" handout -- see link above.
Hint: You can enter answers in hex by specifying a
"0x" prefix, e.g., 16 could be entered as "0x10". Usually
one would enter addresses, values in memory, etc. using hex.
Suppose that the instructions above were relocated so that the
first instruction were at location 0x100 instead of location 0.
Assuming we then started execution at location 0x100 and we wanted
the instructions to perform the same computation, which
instruction encodings should be changed when relocating the
Problem 2. Design Problem: Quicksort
See the instructions below.
Use the Bsim instance below to enter your code. To complete this design problem, you should
assemble your program, then run the simulation to completion.
The built-in test will either report any discrepencies between the
expected and actual outputs, or, if your code is correct, it will
record the test passed.
Suppose you have an array of N integers, and wish to sort them
into ascending order. There are a variety of approaches you might
use, ranging from the
malignedbubble sort which takes $O(N^2)$ time, to faster approaches
such as quicksort that averages $O(N \log N)$ time. Quicksort
uses an elegantly simple divide and conquer
approach to sorting an array:
Pick a pivot value from among the array elements,
and remove that element from the array.
Partition the array into two smaller arrays, containing
elements whose values are smaller or larger than the pivot value,
Call quicksort recursively to sort each of the two smaller
Finally, combine the sorted smaller-value array, the pivot
element, and the sorted larger-value array into a single sorted
This description glosses over several details which may vary by
implementation; for example, which of the two smaller arrays should
contain elements that are equal to the pivot value.
A high-level Python approach to quicksort of a list is:
if list == : return 
pivot = list # arbitrarily choose first element
lesser = qsort1([x for x in list[1:] if x < pivot])
greater = qsort1([x for x in list[1:] if x >= pivot])
return lesser + [pivot] + greater
Often it is preferable to sort an array in place, rather
than allocating space for the resulting new array. A version of
quicksort for in-place sorting is given in
# in-place partition of subarray
# left is the index of the leftmost element of the subarray
# right is the index of the rightmost element of the
# subarray (inclusive)
# choose middle element of array as pivot
pivotIndex = (left+right) >> 1
pivotValue = array[pivotIndex]
# swap array[right] and array[pivotIndex]
# note that we already store array[pivotIndex] in pivotValue
array[pivotIndex] = array[right]
# elements <= the pivot are moved to the left (smaller indices)
storeIndex = left
for i in xrange(left,right): # don't include array[right]
temp = array[i]
if temp <= pivotValue:
array[i] = array[storeIndex]
array[storeIndex] = temp
storeIndex += 1
# move pivot to its final place
array[right] = array[storeIndex]
array[storeIndex] = pivotValue
def quicksort(array, left, right):
if left < right:
pivotIndex = partition(array,left,right)
Although this code is nominally in Python, it is substantially
identical to C code.
Note that the code for both quicksort and partition
identifies a range of consecutive elements in the array by
two integers, left and right, that identify the
array indices of the leftmost and rightmost elements within the range
respectively. In contrast to usual C and Python practice, the indicated
range includes both the left and right elements: thus, the only way
to designate an empty (zero-length) subrange is by having
Your job is to translate this in-place version of quicksort to
Beta assembly language. The template.uasm tab in the BSim
editor contains the appropriate checkoff setup and dummy (empty)
definitions for the procedures quicksort
and partition. It also includes the above Python/C
versions of the code as comments.
Arrays are stored in consecutive locations of memory. In this
lab, we're dealing with arrays of integers, so each array element
occupies a 32-bit word. Since the memory is byte addressed,
consecutive elements of an integer array have addresses that differ by 4.
Integer arrays are always word aligned, i.e., the byte
addresses of array elements have 00 as the low-order two address
bits. When a program refers to an entire array, the value that gets
passed around is the address of the first array element, i.e.,
the address of array. For example,
here's a simple procedure that adds two consecutive array elements:
PUSH(LP) // standard entry sequence
PUSH(R1) // save registers we use below
LD(BP,-12,R1) // R1 = address of array
LD(BP,-16,R0) // R0 = i
// now we have to convert index i into the appropriate
// address offset from the start of the array. Since
// each array element occupies 4 bytes, we multiply the
// index by 4 to convert it to a byte offset.
SHLC(R0,2,R0) // shift left by 2 = multiply by 4
ADD(R0,R1,R1) // R1 = address of array[i]
LD(R1,0,R0) // R0 = array[i]
LD(R1,4,R1) // R1 = array[i+1]
ADD(R1,R0,R0) // R0 = array[i] + array[i+1]
POP(R1) // restore saved registers
MOVE(BP,SP) // standard exit sequence
The Quicksort tab in the BSim window has been initialized with the code from
the template.uasm tab. Look it over briefly;
notice that the dummy procedures included are valid (e.g., they
obey stack discipline and our linkage conventions) but devoid of any
Select the Quicksort tab in the BSim window, click Assemble
to translate it to binary. If successful, you'll now see a
window onto an operating (simulated) Beta running the binary
translation of your program. The upper-left displays the contents
of the Beta's registers, the lower-left a region of memory containing
the translated code, and to the right two regions of memory (one
near the top of the stack. Explore this view a bit: scroll the
lower-left region and observe labels, hex values, and (where
sensible) values decoded as Beta instructions.
Most of these are from the checkoff program and associated infrastructure;
but at the end of the non-zero contents, you'll see your empty
partition and quicksort procedures.
Run the code, by hitting the play button; you'll see the
Beta stepping through instructions, updating the display.
Hint: You can click on the "Split" button to configure the BSim window to show
both your editor windows and the Beta simulation display. The simulator
will highlight the line in your source code that generated the current
Beta instruction, assuming that source line came from the currently
selected editor window. You can watch the Beta scroll through your
program making it easy to watch your code being executed.
When you get tired of watching this show, hit pause and
then fast forward to execute without the tedious display
updates. You should see some output from the checkoff program in
the console window at the bottom of your screen.
Good news - you've passed the first two test cases! Looking
at the console output, notice that Test 1 involves a sequence of 1
element, and Test 2 involves a sequence of length 2 thats already in
order. These trivial test cases are already sorted, so your do-nothing
quicksort (which, in its defense, at least does no damage) passes these
tests. The third test, which actually needs some sorting, should fail.
Lets focus on the failed test: change the LONG(0) in the location
labeled TestCase near the beginning of your Quicksort file
to read LONG(3). This tells the checkoff program to run only the
third test, making debugging that test a bit less tedious.
Our principal debugging tool is the breakpoint, a marker that
can be inserted into our program at interesting points to cause it to pause and let us poke
Insert the line
in your empty quicksort procedure, immediately following the line
// Fill in your code here...
and run it again. The simulation should stop when you hit the inserted
breakpoint, allowing you to examine the state of the Beta and its memory
at that point.
Looking at the state of the Beta, determine the value in R20.
In fact, you'll notice systematic values in registers; these are used by
the checkoff program to check that you're properly saving/restoring registers.
Your next project, and the main task of this lab, is to fill in
the code for the two procedures and get them working correctly.
Although you may code these procedures however you like, we recommend
paying careful attention to details in the Python/C versions supplied;
seemingly minor variations (< rather than <=,
including/excluding the rightmost element in a loop) can cause errors
taking hours to debug.
While you may vary the order in which you approach the coding of
these procedures, we suggest the following sequence of steps:
quicksort stub: Implement the first part
of quicksort: the call to partition. Using
a breakpoint in partition, ensure that its called with
the proper arguments (identical to those of quicksort).
Try it on the first few test cases by varying the value
partition: Implement the code in partition,
and debug it (again, using various test cases). Although this code is
more complex than quicksort, it avoids the complication
of recursive calls, making debugging easier. Once you're
convinced partition works properly, move on to the next
Hint: The partition code involves a number of local variables.
Although you can allocate these variables in the stack frame (as we have
done in examples given in lecture), your code may be both smaller and
more readable if you allocate registers to hold local variables. One
convenient way to do this is to define symbolic names, e.g.,
p_array=R2 // base address of array (arg 0)
p_pivotIndex=R5 // Corresponds to PivotIndex in C program
Note that the p_ prefixes are prepended to avoid name conflicts
with other such assignments. Of course, you must remember to save and
restore the values of any register you use in this (or any other) fashion!
Even if you choose to store these variables in the local stack frame,
you will likely find symbolic names (defined as the variable offsets)
easier to use than generic Rx register names.
Remember: A procedure can use R0 with impunity, since the caller is expecting
that to change to contain the return value. But if you use any other register
(R1, R2, ...) it must have the same value after the procedure as it did when the
procedure is called. For each register Rx that the procedure uses, there should be
a PUSH(Rx) in the entry sequence and a POP(Rx) at the corresponding
part of the exit sequence.
Complete the quicksort procedure, and get it to run correctly
on all the test cases by setting the value in TestCase to zero.
The left and right values passed
to quicksort are described as indices
of array elements, implying that they range from zero
through one less than the length of array. This
constraint turns out to be not strictly true in all cases in our
implementation. As our last exercise, we'll explore an exception that
arises during execution of our quicksort implementation.
Insert a breakpoint in your quicksort procedure,
after the stack frame has been set up and interesting values
(e.g., arguments) have been loaded into registers.
Set TestCase to contain 13 (running only the last test
case), and run your code.
When it stops at your breakpoint, check the value that was passed
as the right argument. If its non-negative,
click fast forward to continue until you hit the breakpoint
again; click again, and keep clicking until you get to the breakpoint
with a negative value for right.
At this point, you are several calls deep in the recursion of
quicksort. By inspecting values in registers and on the stack, you
can determine both the current state of the computation and the call
history that led us here.
Find the two arguments to the current call:
What's the current value in element zero of the array?
Note the relation between the element zero value and the other
values in the array. If you look a bit at the code and think about
the behavior of your two procedures, you can see how the negative
value arises and convince yourself that it does no harm to the
computation. It is, however, a bit sloppy for the author of this code
not to have documented this anomaly in an explanatory comment!
Observe where BP points into your stack frame, and the location
of the saved LP value relative to this point. Scroll the disassembly
window of BSim and find the two recursive calls within quicksort;
note the hex locations of the instructions following each call.
Write down these values;
they will be saved LP values in stack frames associated with
recursive calls, and can be used to distinguish recursive calls from
the original call by the checkoff code.
By inspecting the saved LP value, determine whether the current
recursive call to quicksort is from the first recursive
call (sorting the array of smaller elements) or the second within
Find the saved BP, which points to the stack frame for
the prior call to quicksort; find the arguments to that call.
Follow the BP chain back to the original call, and report
the recursion depth (number of active calls) when the
negative argument is encountered. Note that a couple of
frames at the bottom of the stack belong to procedures
in the testing code -- we only want you to count frames
belonging to quicksort. Think about how you can distinguish
quicksort frames from test code frames.