Request for CPU and GPU code review and optimization for DAWN algorithm implementation

[lxrzlyr]

Is your feature request related to a problem? Please describe.
Yes. I have submitted a pull request for the DAWN algorithm implementation, but I need help with reviewing and improving the CPU and GPU versions of the code.

Describe the solution you'd like
I am looking for suggestions on how to improve the performance of the CPU implementation and how to optimize the code for parallel execution on GPUs.

Describe alternatives you've considered
I have considered trying to optimize the code on my own, but I am not an expert in CPU or GPU programming and do not have the necessary knowledge to fully optimize the code. Therefore, I am requesting help from experts in these areas.

Additional context
I have already submitted a pull request for the DAWN algorithm implementation and would greatly appreciate any feedback or assistance in improving the code for both CPU and GPU platforms.

PS. DAWN for CPU already works, the GPU version doesn't work yet.

@neoblizz

[lxrzlyr]

Pull Request: #1051 (comment)

[neoblizz]

@lxrzlyr hey, I just want to update that I have been very busy but have not forgotten about this. I will take a look at it when I get a chance.

[lxrzlyr]

@neoblizz We have completed the implementation of advanced DAWN. After consolidating functions and further reducing operations, we found it to be highly analogous to the BFS implementation. In essence, with minimal modifications, DAWN can be realized.

### DAWN
auto iteration = this->iteration + 1;
auto sovm = [distances, single_source, iteration] __host__ __device__(
                    vertex_t const& source,    // ... source
                    vertex_t const& neighbor,  // neighbor
                    edge_t const& edge,        // edge
                    weight_t const& weight     // weight (tuple).
                    ) -> bool {
      auto old_distance = math::atomic::min(&distances[neighbor], iteration);
      return (iteration < old_distance);
    };

### BFS
auto bfs = [distances, single_source, iteration] __host__ __device__(
                    vertex_t const& source,    // ... source
                    vertex_t const& neighbor,  // neighbor
                    edge_t const& edge,        // edge
                    weight_t const& weight     // weight (tuple).
                    ) -> bool {
      auto old_distance = math::atomic::min(&distances[neighbor], iteration + 1);
      return (iteration + 1 < old_distance);
    };

The correctness of this slight modification actually stems from the consolidation of the following two functions, where DAWN reduces two additions in each update compared to the original BFS.

    auto iteration = this->iteration + 1;
    auto sovm = [visited, single_source, iteration] __host__ __device__(
                    vertex_t const& source,    // ... source
                    vertex_t const& neighbor,  // neighbor
                    edge_t const& edge,        // edge
                    weight_t const& weight     // weight (tuple).
                    ) -> bool {
      visited[neighbor] = iteration;
      return true;
    };
    auto merge = [visited, distances, iteration] __host__ __device__(
                     vertex_t const& vertex) -> bool {
      auto update_distance = thread::load(&(visited[vertex]));
      auto recover_distance =
          math::atomic::min(&(distances[vertex]), update_distance);
      return (update_distance < recover_distance);
    };

Since DAWN can be implemented with very small modifications based on the current BFS API, we suggest enhancing performance by directly modifying the existing BFS API, rather than setting up a separate algorithm. This approach can also reduce the complexity of the testing process. Once you have determined the specific approach for integrating DAWN or modifying BFS, please inform me.

Looking forward to your reply. Thanks!

[neoblizz]

Hi @lxrzlyr, thanks for the update. I'll check this out in ~1.5 weeks timeline. I am on a break right now. Thanks for your contribution!

[lxrzlyr]

Hi @neoblizz , I hope you're doing well. I understand you're on a break. If possible, I wanted to check in on the progress of the update I mentioned earlier. Thank you very much for your time and assistance!