Optimizing Data Structure Layout for Improved Memory Performance

Project Overview

This project implements LLVM passes to transform data structures from Array of Structures (AoS) to Structure of Arrays (SoA) format, enhancing memory access patterns and performance in applications with significant data processing needs.

Project Resources

Timeline

^B: Tasks assigned to both team members.
^Y: Tasks assigned to Yufei Shi.
^S: Tasks assigned to Sun A Cho.

• Week 1 (Oct 20): ^BLiterature review and brainstorm project ideas.
• Week 2 (Oct 27): ^BRevise and finalize project proposal.
  ^BSet up development environment and build system.
  ^BCreate an initial benchmark suite (3-5 small kernels with different data layouts).
  ^BStudy LLVM's GEP instruction and StructType.
  ^YSkeleton analysis pass.
• Week 3 (Nov 3): ^SAccess pattern analysis.
  ^YLoop traversal and struct array detection.
  ^BIntegrate and finish the analysis implementation, validate on benchmarks.
• Week 4 (Nov 10): ^SStart SoA struct type generation.
  ^SAdd cache-line-aligned padding between SoA arrays (if time permits).
  ^YStart memory access rewriting for SoA accesses.
  ^YDraft a basic profitability heuristic (if time permits).
• Week 5 (Nov 17): ^SComplete AoS to SoA struct transformation.
  ^YComplete memory access rewriting.
  ^BIntegrate, initial testing on the benchmarks, and debug if necessary.
• Milestone (Nov 20): By November 20th, we hope to have completed the basic analysis pass for identifying AoS for possible transformation and are close to completing the compiler pass for transforming AoS to SoA.
• Week 6 (Nov 24): ^BEvaluate the optimization using the benchmarks.
  ^BStart working on the project report and poster.
  ^BIn-depth sensitivity studies (if time permits).
• Week 7 (Dec 1): ^BWork on the project report and poster.
  ^BDec 3: Submit final report.
  ^BDec 4: Poster session.