aysylu / project2 Goto Github PK

based on our findings in part 4.6

Measure the performance impact that this has on the runtime.

Briefly comment on why this did or did not have a performance impact.

Note that you should use intersect() from IntersectionDetection.cpp to test if two line segments will intersect in the next time step.

To simplify your implementation, consider destroying the quadtree and reconstructing it at each time step.

Measure and report how long it takes for the program to execute with the more efficient collision detection. Compare with the original runtime. Was the speedup what you expected?

Record the number of collisions detected during the screensaver’s execution. These numbers should be close to the numbers you recorded for the unmodified code. Since the simulation is sensitive to the order in which collisions are resolved and the calculations are done in floating point, your new results may not be exactly the same as the original version’s.

Here are some optimization ideas to help you get started:

• A large percentage of calculations are repeated with each time step. For example, the collision detection code recalculates the length of each line segment in each time step. This is an expensive calculation that is unnecessarily repeated in each time step. For calculations that are repeated in each time step, it might be worthwhile to precompute these calculations and store results for reuse.

• To simplify the implementation, we suggested that you destroy and recreate the quadtree on each time step to avoid having to figure out how to effectively update the quadtree. While this does make things simple, it is a bit wasteful. You can try finding an effective way to update the quadtree so that you don’t need to destroy it.

• Our method for testing if two lines intersect is fairly efficient. However, you could try finding a more efficient way of testing if two lines intersect.

For example, once you built a quadtree, how did you use it to extract collisions?

How did you store line segments in each quadtree node?

Describe any decisions, trade offs, and further optimizations that you made.

At the meeting with a mentor, one of the good ideas we discussed was to sort the lines and detect collisions only among those that might be colliding, reducing the number of lines we're considering.

Also, we might want to consider how we could use the method we learned about in 2.1 for detecting forces that act on planets in nbodies.

According to the mentor, switching all the calculations to ints instead of floats might not give us a huge speedup, but it's worth looking into.

Vary the maximum depth and measure the performance impact this has on the runtime.

Briefly comment on why this did or did not have a performance impact.

Before beginning, it is useful to profile your application to determine where you should focus your time when parallelizing your code. The goal is to identify a region of code that comprises of a large percentage of the total execution time, but is amenable to a potentially large degree of coarse grained parallelism. To do this, build a gprof-enabled version of the screensaver binary by typing make Line.prof, then run it for 1000 frames via CQ using cqsub ./Line.prof 1000, and finally run gprof ./Line.prof to see the
resulting profiling statistics.

Alternatively, use the perf tools to profile your code.

Once profiled, examine the results, which are ordered by self seconds. This gives you the amount of time spent in each function. The top of this list gives you the names of functions that, if parallelized, could offer significant performance improvements to the running time of the application as a whole. List the top six functions on the list. Unfortunately, since many functions do not contain code that can be executed concurrently, not all functions are good candidates for parallelization.