lunduniversity.lu.se

# Projects

• The deadline for participating in the annual competition 2018 is Friday May 25 at 23:59.
• You must have passed the project (code by Forsete and report by me) before writing the exam. To be safe, it is a good idea to mail me the report on May 30 the latest and Forsete the code a few hours before the exam starts (each run takes a bit more than 10 minutes).
• You can mail in solutions any number of times (actually, at most 100,000 times and then Forsete gets annoyed).
• I have office hours 12.30-13.00 during the LP1 and LP4. At other times you can email me to set up a meeting.
• The description of the algorithm is available online to LU students here. See pages 81--92.
• For the competition, which is completely voluntary, groups of one or two persons compete in the two projects as follows. Both projects aim at getting as good performance as possible, and each of the two projects will be ranked so that the fastest group gets 1 point, second fastest 2 points etc. Then the sum of points for each participating group will be used to see which group won. The difficult aspect of this competition is to strike a good balance between the two projects. Winning one and getting a fifth position on the other will certainly  not lead to winning the competition.
• PDF with documentation of POWER instructions is here
• The projects should be performed by groups of at most two persons.
• There are two projects, one to write a fast version of Fourier-Motzkin Elimination, described below, and the other to make an as small as possible version of your code. You see the size of the code of an object file using the size command which is present in the distributed makefile.
• Go to the directory project and type make.
• Look at the files in eval. There are input files A3.0 c3.0, etc and corresponding output files with solutions created by Mathematica. Recall you do not have to generate the solutions.
• The first information in the file A is the number of rows and columns.
• Your function should be able to determine the correct answer to each of the 10 systems in eval and the 300 systems in input. There is a huge number of additional systems in /opt/fm/input on power.cs.lth.se
• For the fast version, the main program counts the number of times each system in eval can be solved in one second (but Forsete uses 60 s for better accuracy. This count is divided by the corresponding count for the reference implementation. For the systems in eval, the geometric mean of the ratios is the score.
• For the small version, it is simply the size of the static data and instructions in the file small.o, as reported by the Unix command size.
• Your function is not allowed to take the matrix contents into account when trying to make your code fast --- except the matrix sizes. For instance, matching the test cases with pre-computed results stored somewhere is not permitted.
• You can hand in one file for the fast code version and a different for the small code version.
• Your files will be compiled with the same flags to gcc as are used in the makefile.
• You are not allowed to have any memory leaks or other serious errors.
• You should hand in the following:
• Source code in an email sent to edaf15@forsete.net
• For fast: Subject: assignment fast by stilid
• Attachment must be fast.c
• Similar for small.
• Measurements using oprofile that identify which parts take time in your implementation.
• Summarize the measurements in half an A4 with a discussion of what you think about your representation of the systems and the memory allocation strategies you used.
• Comment whether your program uses expensive instructions unnecessarily?
• The report should be mailed to jonas.skeppstedt@cs.lth.se
• Hints
• Make a simple and correct version first before any kind of optimization. This will probably save you time.
• If you use floating-point numbers, your code will be slower and you will get problems with precision.
• Since you only have to determine whether a system has a solution or not, you can skip certain parts of the distributed algorithm (you don't need to enumerate the solution...).
• If you wish you can use the IBM simulator to improve your code. Contact Jonas for instructions.