Distribution in a round-robin fashion allocates one point at a time per core. There is no reason why that core needs to wait until it gets its full number of points before it sorts, especially if quick sort then needs to run through them sequentially again. The quick sort step should start as soon as the first point arrives.
Similarly, a core that passes a point that is bigger than its' neighbour's lowest value is also just adding another point. Thus the distribution by the main core and the shuffling between cores both need to call the same function (e.g. add_point(...)) and the receiving core needs to sort the incoming point into its' list.
Since quick-sort itself is a linear process, using this parallelised method, there is a chance that a core is not finished with the sort before the next point arrives, especially when the number of points gets large. Therefore, each core should maintain an incoming point list. Perhaps the call would be better named queue_point_for_sort(...).
I also believe that the efficient DeLaunay Triangulation algorithm. Lee and Schachter, () is also a divide and conquer type algorithm. Maybe that can start straight away as well???Statistics: Posted by nickoppen — Mon Apr 28, 2014 6:07 am
]]>