tasks.md

Tasks

Aayush

• Write a minimal GPU-friendly graph library (use classes not structs)
  • Implement adjacency matrices (linearized representation)
  • Implement a structure to represent a path
  • Auxiliary graph operations (get neighbors, calc path weight, etc...)
  • Write dataloader for TSP dataset(s)

Matt

• Implement generic ACO algorithm
• Implement ACO for TSP on the CPU, sequentially
• Write tests

GPU:

• GPU Initialization / kernel wrapper
• Write Kernels
  • Tour construction
  • Parallel pheromone update
• Write GPU-safe sampling function
• Benchmark
  • Benchmark the CPU impl
  • Benchmark the real GPU impl

Now:

• [-] Implement ACO for TSP on the GPU, using parallelism
• Benchmark
  • Benchmark the CPU impl
  • Benchmark the real GPU impl
• Compare correctness (how are we going to do this? answer: comparing path lengths)
• Search the project for TODO since I added some potential stuff

Known problems

• CPU
  • Invalid reads on paths in iter_ts
  • Not reaching optimal on dj38 and above
  • Freeing heap alloc arrays with delete[] causes path in iter_t to be null
• Search the project for TODO since I added some potential stuff