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.
Final Project CSE3100 Final Project CSE3100 Due 2020-12-07 20:00 Final Project This project starts Friday Dec 4 at 8AM and endsMonday 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 onweekdays. 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 di�erent 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 folderQ1. It contains a Makefile andminimal starter code. Your task is to write a program that reads andmultiply matrices. Your program takes, on the command line, 3 arguments denoting the names of files containing twomatrices 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 thematrix multiplication on thematrices in the files m1.txt and m2.txt and use two sub processes to carry out this task. Matrix Refresher Remember that amatrix is a n bym 2D array with n rows andm columns. For instance, a 2x3matrix is A = [ 1 2 3 4 5 6 ] CSE3100 1 Final Project CSE3100 Due 2020-12-07 20:00 while a 3x3 identity matrix is: I = 1 0 0 0 1 0 0 0 1 Therefore computing A * I yields a 2x3 matrix R R = [ 1 2 3 4 5 6 ] In general, we have R = A * B with A ∈ Rn×m, B ∈ Rm×p ∀i ∈ 1..n, j ∈ 1..p : Rij = ∑ k∈1..m Aik ·Bkj Which requiresO(n3) runtime (when n =m = p). Amulti-process approach Given twomatrices 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) bn k c 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 andmultiply 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 kworkers involved and leaves the multiplication algorithms essentially untouched. Putting it together Your programmust read the two inputmatrices, compute the productwith k subprocesses (as specified on the command line) and print the resulting matrix on its standard output (in rowmajor 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 sizedmatrices and should experience a speedup once we usemore 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) = ab mod 256 Tomake 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 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 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 state- ment: 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 themaximum 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 namedq3. 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 canmake 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 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="" 1="" 1="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 2="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 3="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 1="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 4="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 5="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 6="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 1="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 7="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 8="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 0="" 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="" state-="" ment:="" 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="" themaximum="" 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="" namedq3.="" 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="" canmake="" 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="" –="">