.. (לתיקייה המכילה) | ||
May we use data structures from STL? | |
No, use only ANSI C. |
may we use helper files, or should we put all our code in tsp_static.c and tsp.c? | |
You should put all the code in tsp_static.c and tsp.c , because we will use our make file ,and you won't be able to modify the it. |
in part 1: if we have 10 cities and 8 threads, would the following division be considered 'equal chunks': decide which city will follow city 0, and RR the options between the threads (so one thread actually checks 2 subtrees, while all the others check 1)? | |
It doesn't depend on number of cities , with 10 cities you may get to 10! (or 9!) chunks.., think about the solution and you will answer this by your self. |
Should the static solution finish with 18 cities input? and in part 2 ? | |
No. The static solution will be checked with up to 14 cities input. The dynamic solution should finish up to 18 cities. Both must finish within no more than 5 minutes, when using 8 processes. |
There can be more than one minimal path. Can we return any minimal path or should it be a specific one? | |
You can return any one of the minimal paths. |
Can I make any assumptions about the number of cities and processors? | |
If it makes data partitioning easier for you, you may assume there are at least 5 cities (like in our implementation). You may also assume that there won't be more processors than the number of 4-city long sub-routes (so you can limit the partitioning granularity on the static part). Note, however, that an ideal solution would not have to make these assumptions. Therefore, if you do make them, make sure you check the input at the beginning of the run, and document your limitations. |
On the static part, who should do the partitioning? | |
The partitioning of the input can either be done by the root process, which will the distribute the parts to the rest, or you can have each process calculate its part based on its rank. |
How balanced should the partitioning be on the static part? | |
As balanced as possible... You may have differences if the numbers can't be split nicely, but they should be minimal. If difference is large, you should probably use finer partitioning. |
How should we measure the speedup? | |
Add timing to the main function, and print it on the master process. You can use something along these lines: clock_t begin = clock(); // run tsp_main clock_t end = clock(); if (rank == 0) printf("execution time: %ld ticks", end - begin); You can get the actual time by dividing the diff in CLOCKS_PER_SEC, but it's unnecessary. We're only interested in the speedup. |