In this assignment, we count distances between points in 3-dimensional space. One possibility to think of this is as cells, whose coordinates were obtained by diagnostics and which require further processing.

Distances are symmetric, i.e. distance between two cells c_1 and c_2 and the distance in reverse direction c_2 to c_1 should be counted once.

Implementation

Implement a program in C, called distances, that uses OpenMP for parallelization and that:

Your program should accept command line arguments

./distances -t5

The argument to -t give the number of OpenMP threads that you may use. You may only use OpenMP parallelism.

Input

Coordinates are given in a file, in which each row corresponds to one cell. The three coordinates are separated by exactly one blank space. Each coordinate is given exactly as follows: A sign '+' or '-', two digits, a decimal point '.', and three digits. For instance, the following is a valid input of 10 cells.

+01.330 -09.035 +03.489
-03.718 +02.517 -05.995
+09.568 -03.464 +02.645
-09.620 +09.279 +08.828
+07.630 -02.290 +00.679
+04.113 -03.399 +05.299
-00.994 +07.313 -06.523
+03.376 -03.614 -06.657
+01.304 +09.381 -01.559
-04.238 -07.514 +08.942

Output

A valid output to the above input is

03.00 1
05.54 1
05.85 1
05.91 1
06.07 1
06.54 1
07.94 1
08.58 1
09.40 1
09.59 1
09.65 1
09.98 1
10.00 1
11.18 1
11.68 1
11.77 1
11.98 1
13.46 1
14.02 1
14.11 1
14.77 1
14.78 1
14.96 1
15.07 1
15.38 1
15.71 1
15.78 1
15.84 1
16.75 1
16.94 1
17.33 1
17.63 1
17.66 1
17.72 1
17.79 1
18.00 1
19.02 1
19.10 1
19.31 1
20.65 1
21.67 1
22.00 1
22.31 1
23.85 1
23.98 1

Implementation details: Simplifications

Implementation details: Memory consumption

Implementation details: Precision

In case of doubt use the test script from below.

Implementation strategy

The following is an outline of aspects that play into designing an efficient implementation.

Splitting the assignment into smaller tasks

This assignment comprises four interdependent task, i.e. design choices influence each other.

Computing the distance of two points

Here is a list of observations and questions that can help you designing a good solution to this subtask.

Most relevant videos are Algbraic Expressions, Operand Type, perf.

Parsing the file

When parsing the file or parts of it, it is a huge advantage to benefit from the fixed input format. The following observations and questions can guide your implementation.

Most relevant videos are Binary vs. Text Files, String Encoding and Handling, Memory and File Access.

Memory management

There are three aspects of memory management that you have to balance. Recall that block iteration was a technique you saw in the videos.

Most relevant videos are Locality, Locality and Block Access.

Parallization

Parallelization can enter at several points of the program. Parsing and counting distances are the two most beneficial ones.

Most relevant videos are Parallel For, Sections, and Single, Advanced Reduction.