CSE3100编程语言辅导、讲解c/c++，Java程序设计、Python辅导
- 首页 >> Matlab编程 Final Project CSE3100 Due 2020-12-07 20:00
Final Project
This project starts Friday Dec 4 at 8AM and ends Monday Dec 7 at 8PM. It should not take anywhere
this long to complete it. The ample padding is to deflect issues that may occur with MIMIR. I encourage
you to take into account the fact that MIMIR is open during business hours on weekdays. You are unlikely
to get assistance from them over the week-end. So please, plan accordingly.
You may use your notes, textbook, PDF of textbooks and laptop to access Mimir. You cannot use
StackOverflow, Chegg, or any other online sources. Plagiarism checks are in full force. Cheating on the
project will be severely punished (it will lead to an immediate ‘F’).
Each question is evaluated with several test scripts that exercise dierent capabilities of your program.
Therefore you can earn partial credit on a question by only passing some of those tests. Also note that
each question come with some base including a Makefile. We urge you to test in your environment
and not simply submit to Mimir as this increases the load on their servers. Once again, we emphasize
that gdb and valgrind are extremely useful tools that you should not neglect.
There are a handful of questions on this test. Read the description carefully and attentively before
diving into the code. I wish to emphasize that hard coding answers to test scripts will not earn you
any points. You need to write the code that solves the problem.
I have Spoken. - Kuill
Q1. We shall multiply 20 points
For this question, head into the folder Q1. It contains a Makefile and minimal starter code. Your task
is to write a program that reads and multiply matrices. Your program takes, on the command line, 3
arguments denoting the names of files containing two matrices and the number of processes you are
expected to use to carry out your task. For instance, running
1 ./matrix m1.txt m2.txt 2
Will execute the matrix multiplication on the matrices in the files m1.txt and m2.txt and use two sub
processes to carry out this task.
Matrix Refresher
Remember that a matrix is a n by m 2D array with n rows and m columns. For instance,
A multi-process approach
Given two matrices A and B, where A has n rows, to speed up the task with k processes, it is natural to
slice the first matrix into k bands, in which each band contains (approximately)
rows. (If n does not divides equally into k, spread the r remaining rows over the first r bands. For
instance, with n=10 and k=4, 10/4=2 with a remainder of 2 and therefore we would have 4 bands with
[3,3,2,2] rows each. Then each child process is tasked with computing his part of the product for the
rows entrusted to it. In this example, the first worker would multiply the first 3 rows of the first matrix
by the second to obtain the first 3 rows of the result while the second worker would work on the next 3
rows of the first matrix and multiply them by the second to obtain the second block of three rows of
the result.
This division of labor technique splits the work as evenly as possible among the k workers involved
and leaves the multiplication algorithms essentially untouched.
Putting it together
Your program must read the two input matrices, compute the product with k sub processes (as specified
on the command line) and print the resulting matrix on its standard output (in row major mode), one
row of the matrix per line of output (do not output the size of the result, only its content). Your code
CSE3100 2
Final Project CSE3100 Due 2020-12-07 20:00
should be able to handle arbitrarily sized matrices and should experience a speedup once we use more
than one process.
You are free to use the communication technology of your choice to answer this question (though
some are easier than others for this purpose). Recall that you should not be using threads.
Q2. It’s the ship that made the Kessel run in less than twelve parsecs. 40 points
For this question, head into the folder Q2. Your task is to compute a histogram for a function f of a
text (sequence of bytes) as quickly as possible. Interestingly, your grade is a function of how fast your
code is going to be. I suggest compiling with the optimization flags turned on (i.e., -O3). Naturally, you
should expect to use the best algorithms and technique you know as well as threads to get to where
you want to be.
Consider that a text is a sequence of n bytes [t0, t1, ..., tn − 1], then your task is to compute a histogram
h over the sequence of n-1 pairs [f(t0t1)f(t1t2), ..., f(tn−2tn−1)] where the function f is modular
exponentiation and is defined as
f(a, b) = a
b mod 256
To make your task easier, we provide a C function for modular exponentiation:
1 long modPow(long base,long exp,long m) {
2 if (m == 1) return 0;
3 long c = 1;
4 for (long ep=0;ep <= exp - 1;ep++)
5 c = (c * base) % m;
6 return c;
7 }
Observe how all the values in [f(t0, t1)f(t1, t2), ..., f(tn−2, tn−1)] belong in the interval (0..255) and
you can therefore compute the histogram of this sequence, i.e., the number of occurrences of each
value in the range 0..255.
∀i ∈ 0..255 : hi = |{k ∈ 0..n − 2 : i =
t
tk+1
k mod 256
}|
Implementation
It might be wise to first obtain a sequential implementation. If you create a program seqHisto, then
executing the command
1 ./seqHisto file.txt
CSE3100 3
Final Project CSE3100 Due 2020-12-07 20:00
on a file containing the four bytes ['a','b','c','d'] would produce the histogram
Conveying that the values 0,81 and 193 appeared once while all the other values (252 of them) are
absent.
Note how the four bytes array is an array of 4 “characters”, i.e., it could be defined in C by the statement:
1 char t[4] = {'a','b','c','d'};
Since its length is 4, it yields 3 windows, i.e., [('a','b'), ('b','c'), ('c','d')] and thus,
using modPow one obtains the three values [193,0,81]. Indeed, the ASCII code of ['a','b','c','
d'] are, in decimal, [97,98,99,100] and therefore one computes
[9798 mod 256, 9899 mod 256, 99100 mod 256]
which is equal to [193,0,81].
Once you have a correct version of the program, the fun begins. Your task is to pull all the stops to
make your submission as fast as possible. Your graded submission will be named histo and take two
arguments. First the name of a file to read and second, an upper bound on the maximum number of
threads you can use. For instance, doing
1 ./histo file.txt 10
would invoke histo on a file named file.txt and can use up to 10 threads. Note that you can prefix
your command with the keyword time to measure the runtime of your executable. Namely,
1 time ./histo file.txt 10
outputs the runtime of the command.
We provide one test file (E.coli) in your handout to test with.
Your submission will be compared against several implementation that are increasingly better at this
game. Keep in mind that you will be tested on large files (megabytes).
CSE3100 4
Final Project CSE3100 Due 2020-12-07 20:00
Q3. Stayin’ alive, stayin’ alive. Ah, ha, ha, ha, stayin’ alive, stayin’ alive 40 points
Preliminaries
For this question, head into the folder named Q3. John Conway invented a fun 0-player game known
as the Game of Life. You should first head to https://playgameoflife.com and play with the web-based
so ware to see what can be done. The “game of life” is played on a nxm board which you can make
infinite by wrapping around in both directions, turning it into a donut (thoroid). The board evolves
through generations. At each generation, each cell present on the board will see its state change based
on its own current value and the value of its neighbors (the 8 cells surrounding it).
.
The Figure above shown in gray the 8 cells surrounding cell (i, j). The update rule for cell (i, j) is
simply:
• (i, j) is ALIVE in generation k. Then the status of cell (i, j) in generation k+1 depends on the
number of neighbors that are alive in generation k.
– 0,1 living neighbors: (i, j) is dead in generation k+1
– 2,3 living neighbors: (i, j) survives and is alive in generation k+1
– 4,5,6,7,8 living neighbors: It’s too crowded. Cell (i, j) is dead in generation k+1.
• (i, j) is DEAD in generation k. Then life may sprout in (i, j) at generation k+1 if there are exactly
3 live neighbors of (i, j) at generation k.
To produce interesting behavior one can start with an initial board containing a specific pattern. For
instance, a provided text file data.txt contains a glider pattern. You will find in your git repository a
sequential implementation of the game of Life that runs the simulation starting from a n × m board
stored in a text file whose name is given in argument. The C implementation is straightforward and
animates the computation on the terminal. At the end, it saves the final board to a text file named
final.txt
CSE3100 5
Final Project CSE3100 Due 2020-12-07 20:00
Your task
Since you receive the sequential implementation, you should first study it to make sure you understand
how it works. Once this is done, you can turn your attention to your task.
Your are to implement a multi-threaded version lifeMT that takes on its command line the name of a
file holding a starting board, the number of generations to simulate and the number of threads to use
to speed up the simulation.
For instance, doing
1 time ./liveMT board.txt 10000 4
runs the simulation on the board.txt for 10000 iterations using 4 threads and spits out the final board in
a file named final.txt. As you might expect, to speed up the simulation, you should no longer drawn
the board a er each generation and only produce the final result.
You are to be judged on correctness and performance. You should have the correct board at the end of
the game and if you use multiple threads, you should see shorter computation times. You are free to
devise a strategy for decomposing the work amongst the participating threads. Let’s observe though
that the board is a 2D matrix that is nxm in size and that using the same banding trick as in Q1 might
prove handy.
Nonetheless, the necessity to handle all generations adds a level of complexity over what you already
mastered in Q1.
CSE3100 6
Final Project
This project starts Friday Dec 4 at 8AM and ends Monday Dec 7 at 8PM. It should not take anywhere
this long to complete it. The ample padding is to deflect issues that may occur with MIMIR. I encourage
you to take into account the fact that MIMIR is open during business hours on weekdays. You are unlikely
to get assistance from them over the week-end. So please, plan accordingly.
You may use your notes, textbook, PDF of textbooks and laptop to access Mimir. You cannot use
StackOverflow, Chegg, or any other online sources. Plagiarism checks are in full force. Cheating on the
project will be severely punished (it will lead to an immediate ‘F’).
Each question is evaluated with several test scripts that exercise dierent capabilities of your program.
Therefore you can earn partial credit on a question by only passing some of those tests. Also note that
each question come with some base including a Makefile. We urge you to test in your environment
and not simply submit to Mimir as this increases the load on their servers. Once again, we emphasize
that gdb and valgrind are extremely useful tools that you should not neglect.
There are a handful of questions on this test. Read the description carefully and attentively before
diving into the code. I wish to emphasize that hard coding answers to test scripts will not earn you
any points. You need to write the code that solves the problem.
I have Spoken. - Kuill
Q1. We shall multiply 20 points
For this question, head into the folder Q1. It contains a Makefile and minimal starter code. Your task
is to write a program that reads and multiply matrices. Your program takes, on the command line, 3
arguments denoting the names of files containing two matrices and the number of processes you are
expected to use to carry out your task. For instance, running
1 ./matrix m1.txt m2.txt 2
Will execute the matrix multiplication on the matrices in the files m1.txt and m2.txt and use two sub
processes to carry out this task.
Matrix Refresher
Remember that a matrix is a n by m 2D array with n rows and m columns. For instance,
A multi-process approach
Given two matrices A and B, where A has n rows, to speed up the task with k processes, it is natural to
slice the first matrix into k bands, in which each band contains (approximately)
rows. (If n does not divides equally into k, spread the r remaining rows over the first r bands. For
instance, with n=10 and k=4, 10/4=2 with a remainder of 2 and therefore we would have 4 bands with
[3,3,2,2] rows each. Then each child process is tasked with computing his part of the product for the
rows entrusted to it. In this example, the first worker would multiply the first 3 rows of the first matrix
by the second to obtain the first 3 rows of the result while the second worker would work on the next 3
rows of the first matrix and multiply them by the second to obtain the second block of three rows of
the result.
This division of labor technique splits the work as evenly as possible among the k workers involved
and leaves the multiplication algorithms essentially untouched.
Putting it together
Your program must read the two input matrices, compute the product with k sub processes (as specified
on the command line) and print the resulting matrix on its standard output (in row major mode), one
row of the matrix per line of output (do not output the size of the result, only its content). Your code
CSE3100 2
Final Project CSE3100 Due 2020-12-07 20:00
should be able to handle arbitrarily sized matrices and should experience a speedup once we use more
than one process.
You are free to use the communication technology of your choice to answer this question (though
some are easier than others for this purpose). Recall that you should not be using threads.
Q2. It’s the ship that made the Kessel run in less than twelve parsecs. 40 points
For this question, head into the folder Q2. Your task is to compute a histogram for a function f of a
text (sequence of bytes) as quickly as possible. Interestingly, your grade is a function of how fast your
code is going to be. I suggest compiling with the optimization flags turned on (i.e., -O3). Naturally, you
should expect to use the best algorithms and technique you know as well as threads to get to where
you want to be.
Consider that a text is a sequence of n bytes [t0, t1, ..., tn − 1], then your task is to compute a histogram
h over the sequence of n-1 pairs [f(t0t1)f(t1t2), ..., f(tn−2tn−1)] where the function f is modular
exponentiation and is defined as
f(a, b) = a
b mod 256
To make your task easier, we provide a C function for modular exponentiation:
1 long modPow(long base,long exp,long m) {
2 if (m == 1) return 0;
3 long c = 1;
4 for (long ep=0;ep <= exp - 1;ep++)
5 c = (c * base) % m;
6 return c;
7 }
Observe how all the values in [f(t0, t1)f(t1, t2), ..., f(tn−2, tn−1)] belong in the interval (0..255) and
you can therefore compute the histogram of this sequence, i.e., the number of occurrences of each
value in the range 0..255.
∀i ∈ 0..255 : hi = |{k ∈ 0..n − 2 : i =
t
tk+1
k mod 256
}|
Implementation
It might be wise to first obtain a sequential implementation. If you create a program seqHisto, then
executing the command
1 ./seqHisto file.txt
CSE3100 3
Final Project CSE3100 Due 2020-12-07 20:00
on a file containing the four bytes ['a','b','c','d'] would produce the histogram
Conveying that the values 0,81 and 193 appeared once while all the other values (252 of them) are
absent.
Note how the four bytes array is an array of 4 “characters”, i.e., it could be defined in C by the statement:
1 char t[4] = {'a','b','c','d'};
Since its length is 4, it yields 3 windows, i.e., [('a','b'), ('b','c'), ('c','d')] and thus,
using modPow one obtains the three values [193,0,81]. Indeed, the ASCII code of ['a','b','c','
d'] are, in decimal, [97,98,99,100] and therefore one computes
[9798 mod 256, 9899 mod 256, 99100 mod 256]
which is equal to [193,0,81].
Once you have a correct version of the program, the fun begins. Your task is to pull all the stops to
make your submission as fast as possible. Your graded submission will be named histo and take two
arguments. First the name of a file to read and second, an upper bound on the maximum number of
threads you can use. For instance, doing
1 ./histo file.txt 10
would invoke histo on a file named file.txt and can use up to 10 threads. Note that you can prefix
your command with the keyword time to measure the runtime of your executable. Namely,
1 time ./histo file.txt 10
outputs the runtime of the command.
We provide one test file (E.coli) in your handout to test with.
Your submission will be compared against several implementation that are increasingly better at this
game. Keep in mind that you will be tested on large files (megabytes).
CSE3100 4
Final Project CSE3100 Due 2020-12-07 20:00
Q3. Stayin’ alive, stayin’ alive. Ah, ha, ha, ha, stayin’ alive, stayin’ alive 40 points
Preliminaries
For this question, head into the folder named Q3. John Conway invented a fun 0-player game known
as the Game of Life. You should first head to https://playgameoflife.com and play with the web-based
so ware to see what can be done. The “game of life” is played on a nxm board which you can make
infinite by wrapping around in both directions, turning it into a donut (thoroid). The board evolves
through generations. At each generation, each cell present on the board will see its state change based
on its own current value and the value of its neighbors (the 8 cells surrounding it).
.
The Figure above shown in gray the 8 cells surrounding cell (i, j). The update rule for cell (i, j) is
simply:
• (i, j) is ALIVE in generation k. Then the status of cell (i, j) in generation k+1 depends on the
number of neighbors that are alive in generation k.
– 0,1 living neighbors: (i, j) is dead in generation k+1
– 2,3 living neighbors: (i, j) survives and is alive in generation k+1
– 4,5,6,7,8 living neighbors: It’s too crowded. Cell (i, j) is dead in generation k+1.
• (i, j) is DEAD in generation k. Then life may sprout in (i, j) at generation k+1 if there are exactly
3 live neighbors of (i, j) at generation k.
To produce interesting behavior one can start with an initial board containing a specific pattern. For
instance, a provided text file data.txt contains a glider pattern. You will find in your git repository a
sequential implementation of the game of Life that runs the simulation starting from a n × m board
stored in a text file whose name is given in argument. The C implementation is straightforward and
animates the computation on the terminal. At the end, it saves the final board to a text file named
final.txt
CSE3100 5
Final Project CSE3100 Due 2020-12-07 20:00
Your task
Since you receive the sequential implementation, you should first study it to make sure you understand
how it works. Once this is done, you can turn your attention to your task.
Your are to implement a multi-threaded version lifeMT that takes on its command line the name of a
file holding a starting board, the number of generations to simulate and the number of threads to use
to speed up the simulation.
For instance, doing
1 time ./liveMT board.txt 10000 4
runs the simulation on the board.txt for 10000 iterations using 4 threads and spits out the final board in
a file named final.txt. As you might expect, to speed up the simulation, you should no longer drawn
the board a er each generation and only produce the final result.
You are to be judged on correctness and performance. You should have the correct board at the end of
the game and if you use multiple threads, you should see shorter computation times. You are free to
devise a strategy for decomposing the work amongst the participating threads. Let’s observe though
that the board is a 2D matrix that is nxm in size and that using the same banding trick as in Q1 might
prove handy.
Nonetheless, the necessity to handle all generations adds a level of complexity over what you already
mastered in Q1.
CSE3100 6