Description
CENG311 PROGRAMMING ASSIGNMENT 1 binary search tree
In this assignment, you are required to implement binary search tree creation in C and Python
languages and compare the performance of your implementations.
In your C implementation, you are not allowed to use any struct or pointers to build your tree. You
should use the same data structures/tree format in your Python code.
The property that makes a binary tree into a binary search tree is that for every node, X, in the tree,
the values of all the keys in its left subtree are smaller than the key value in X, and the values of all
the keys in its right subtree are larger than the key value in X (More information in “Data Structures
and Algorithm Analysis in C, Mark A. Weiss, Addison Wesley”).
Your program should start by reading a set of integer values (separated by space) from a text file
into an array and build a binary search tree by using the values in the (unordered) array. After
building the tree, your program should save the binary search tree in a text file in sorted order (inorder traversal).
Your program should measure and report the execution time for building the tree. The measured
time should not include the I/O operations. Time measurement should be done in the following
order:
read the input file into an array // file read operation
start time
build tree // the operation we want to measure
stop time
print tree in the output file // file write operation
You can assume that the input file does not contain any duplicate values. You can limit the number
of nodes in your tree (by specifying the maximum number of nodes it can include). It should be
large enough to demonstrate the performance of the execution.
Requirements:
You are required to execute your programs written in C and Python for the same input files
by including (at least 3) cases with different number of integer values.
You are required to submit the source code and a report that includes implementation details,
performance results and explanations about the results by including possible reasons.
You need to work individually, no group work is allowed.
If you use any source code available on the web, give the reference in your report.
No late homework will be accepted.
Submission: You are required to submit your commented source code and report to LMS. Please
create a compressed file including all source files and report; and name it as
yourstudentnumber_P1.zip (e.g. If your student number is 202012345678, the file name must be
202012345678_P1.zip).
CENG311 PROGRAMMING ASSIGNMENT 2 SPIM simulator
In this assignment, you are required to implement some binary search tree operations in MIPS
assembly language. You will use SPIM simulator [1] to develop and test your code.
First of all, you will implement a binary search tree with nodes which have the following structure:
Byte Address: Contents
X: Value of the node
X + 4: Address of the left child
X + 8: Address of the right child
X + 12: Address of the parent
Each node of your tree should be stored in 16-byte address which holds the value of the node, the
address of the left child, the address of the right child, the address of the parent node respectively.
When there is no left child or right child or parent, the memory address is 0.
The property that makes a binary tree into a binary search tree is that for every node, X, in the tree,
the values of all the keys in its left subtree are smaller than the key value in X, and the values of all
the keys in its right subtree are larger than the key value in X (More information on [2]).
Procedures to be Implemented:
build (list, tree)
This procedure will construct a binary search tree data structure from a list of integers. The address
of the first integer is in the list argument (assume the list is terminated by a special value,
-MAXINT (the negative integer with the largest possible absolute value)), and the address of the
place where the procedure should create the data structure in tree argument (assume there is enough
space for the tree structure).
insert (value, tree)
This procedure will create and put a new node (the value is given in $a0 register) to the binary
search tree (the address of the root node of the tree is in tree argument). The procedure will require
new space in memory for the new tree node, which can be obtained with the MIPS system call sbrk.
The address of the location where the new node was inserted should be stored in $v0 register.
find (value, tree)
This procedure will try to find the value (given in $a0 register) in the binary search tree (the address
of the root node of the tree is in tree argument). The search result should be stored in $v0 register (If
found $v0 = 0, if not $v0 = 1). If the value is found in the tree, $v1 should should contain its
address.
print (tree)
This procedure will print the binary search tree (the address of the root node of the tree is in tree
argument) to the screen. Each line in the screen output will have one level of the tree. If there is no
children (left or right), there will be “x” character to represent no node.
Example binary search tree:
Example output:
8
3-10
1-6 x-14
x-x 4-7 x-x 13-x
Assumptions:
The arguments to the procedures are stored in $a registers, the first is in $a0, the second is in
$a1, and so on.
Only valid arguments are passed into the procedures. You do net need to check the
arguments for their validity.
The input and output lists have maximum 100 characters-length.
Requirements:
The values in all $a registers should be as they were at the time of call at the end of the
procedure.
Your code should be ready for a test program (provided by your TA) which checks flow and
result of the procedures.
You are required to submit the source code and a report that includes implementation details
and screenshots of your sample executions.
You need to work individually, no group work is allowed.
No late homework will be accepted.
Submission: You are required to submit your commented source code and report to LMS. Please
create a compressed file including all source files and report; and name it as
yourstudentnumber_P2.zip (e.g. If your student number is 201812345678, the file name must be
201812345678_P2.zip).
[1] http://spimsimulator.sourceforge.net/
[2] Data Structures and Algorithm Analysis in C, Mark A. Weiss, Addison Wesley
CENG311 PROGRAMMING ASSIGNMENT 3 MIPS-lite single-cycle
In this assignment, you are required to extend the MIPS-lite single-cycle implementation (provided
in your lab) by implementing additional instructions.
You will use ModelSim simulator in Windows
or Icarus Verilog + GTKWave packages in Linux to develop and test your code. The following 12
instructions are to be implemented:
R-format: jr, nor
I-format: addi, andi, ori, bne, bgez, bgtz, blez, bltz
J-format: jal, j
You can find the specifications of the above instructions in the Appendix A of your textbook. You
must design the revised single-cycle datapath and revised control units which make a processor that
executes all 12 instructions as well as the instructions implemented already in the design. You must
make sure that all the instructions working in the current implementation will continue working
correctly. After designing the new enhanced processor, you will implement it in Verilog HDL.
You are required to submit a report and commented code. Your report should include the design
details of the revised datapath and control unit with related drawings if necessary. Your
implementation detail should be provided in the source code comment.
Requirements:
You need to justify that the new instructions are being executed correctly by providing
examples.
You are required to submit the source code and a report that includes implementation details.
You need to work individually, no group work is allowed.
No late homework will be accepted.
Submission: You are required to submit your commented source code and report to LMS. Please
create a compressed file including all source files and report; and name it as
yourstudentnumber_P3.zip (e.g. If your student number is 201812345678, the file name must be
201812345678_P3.zip).
CENG311 PROGRAMMING ASSIGNMENT 4 cache simulator
In this assignment, you are required to run a set of experiments and analyze the results in order to
understand the cache behavior of programs, how different cache designs affect program execution.
You will use the cache simulator (dcache) provided in Pin tool [1] to collect cache miss rates. You
need to compile and run the matrix multiplication code provided as part of this assignment, then
you will run the program by using the simulator as discussed in the lab session (or you can learn
from the Pin user guide: https://software.intel.com/sites/landingpage/pintool/docs/98314/Pin/html/ )
You will run the matrix multiplication program for a set of configurations with the following L1
cache parameters in the cache simulator:
L1 Size [KB] Block size [B] L1 Associativity
8 32 1
8 32 2
8 32 4
16 16 1
16 32 1
16 64 1
16 16 2
16 32 2
16 64 2
16 16 4
16 32 4
16 64 4
32 32 1
32 32 2
32 32 4
After executing the experiments with the default matrix size (N=1000), you will repeat the same set
of experiments by setting the matrix size (N)=10. You will have 30 different executions (15 cache
configurations, 2 input size).
After executing each experiment, collect the L1 data cache load miss rates (and/or any other
relevant values), and draw graphs to demonstrate the effect of the cache parameters on miss rates.
You need to show the L1 load miss rates in the graphs, you can use the other values to explain your
results. Examine the results and explain them by providing your comments.
Notes:
• You can modify the simulator code such that it will get the cache parameters from the
command line instead of compiling the code for each test case. It is not mandatory, but will
decrease the time for the assignment completion substantially. It is also recommended to
prepare a test script including all the experiments (which is also not mandatory).
• You are required to submit a report that includes your results with graphs and comments
about the results.
• You need to work individually, no group work is allowed.
• No late homework will be accepted.
Submission: You are required to submit your report to LMS in pdf format named as
yourstudentnumber_P4.pdf (e.g. If your student number is 201812345678, the file name must be
201812345678_P4.pdf).
References:
[1] Pin – A Dynamic Binary Instrumentation Tool, https://software.intel.com/en-us/articles/pin-adynamic-binary-instrumentation-tool
