gunrock

Gunrock: การวิเคราะห์กราฟกราฟ GPU CUDA/C ++

ตัวอย่าง	เทมเพลตโครงการ	เอกสาร	การกระทำของ GitHub

Gunrock ¹ เป็นห้องสมุด CUDA สำหรับการประมวลผลกราฟที่ออกแบบมาโดยเฉพาะสำหรับ GPU มันใช้ ระดับสูง เป็นกลุ่มที่มีความสัมพันธ์กันเป็นจำนวนมาก/อะซิงโครนัส , ข้อมูลที่เน้นข้อมูลเป็นศูนย์กลาง โดยมุ่งเน้นไปที่การดำเนินงานบนจุดสุดยอดหรือขอบขอบ Gunrock บรรลุความสมดุลระหว่างประสิทธิภาพและการแสดงออกโดยการเชื่อมต่อการคำนวณ GPU ที่มีประสิทธิภาพสูงและกลยุทธ์การเพิ่มประสิทธิภาพโดยเฉพาะอย่างยิ่งในพื้นที่ของการปรับสมดุลการโหลดแบบละเอียดด้วยรูปแบบการเขียนโปรแกรมระดับสูง

สาขา	วัตถุประสงค์	รุ่น	สถานะ
main	สาขาเริ่มต้นพอร์ตจาก gunrock/essentials ทำหน้าที่เป็นสาขาการปล่อยอย่างเป็นทางการ	$ geq $ 2.xx	คล่องแคล่ว
develop	สาขาการพัฒนาสาขาซึ่งได้รับการพอร์ตจาก gunrock/essentials	$ geq $ 2.xx	คล่องแคล่ว
master	สาขารุ่นก่อนหน้าสำหรับ gunrock/gunrock เวอร์ชัน 1.xx อินเตอร์เฟสเก็บรักษาประวัติการกระทำทั้งหมด	$ leq $ 1.xx	ซึ่งเลิกใช้แล้ว
dev	สาขาการพัฒนาก่อนหน้านี้สำหรับ gunrock/gunrock การเปลี่ยนแปลงทั้งหมดตอนนี้รวมกันเป็น master	$ leq $ 1.xx	ซึ่งเลิกใช้แล้ว

คู่มือเริ่มต้นด่วน

ก่อนที่จะสร้าง Gunrock ตรวจสอบให้แน่ใจว่าคุณติดตั้ง Cuda Toolkit ² ในระบบของคุณ การพึ่งพาภายนอกอื่น ๆ เช่น NVIDIA/thrust , NVIDIA/cub ฯลฯ จะถูกดึงโดยอัตโนมัติโดยใช้ cmake

git clone https://github.com/gunrock/gunrock.git
cd gunrock
mkdir build && cd build
cmake .. 
make sssp # or for all algorithms, use: make -j$(nproc)
bin/sssp ../datasets/chesapeake/chesapeake.mtx

การใช้อัลกอริทึมกราฟ

สำหรับคำอธิบายโดยละเอียดโปรดดูเอกสารฉบับเต็ม ตัวอย่างต่อไปนี้แสดง APIs อย่างง่ายโดยใช้รูปแบบการเขียนโปรแกรมแบบศูนย์ข้อมูลเป็นศูนย์กลางของ Gunrock เราใช้การค้นหาครั้งแรกใน GPU ตัวอย่างนี้ข้ามเฟสการตั้งค่าของการสร้าง problem_t และ enactor_t struct และกระโดดตรงไปยังอัลกอริทึมจริง

ก่อนอื่นเราเตรียมชายแดนของเราด้วยจุดสุดยอดต้นทางเริ่มต้นเพื่อเริ่มต้นการสำรวจ BFS แบบพุช f->push_back(source) อย่างง่ายวางจุดสุดยอดเริ่มต้นที่เราจะใช้สำหรับการทำซ้ำครั้งแรกของเรา

 void prepare_frontier ( frontier_t * f,
                      gcuda:: multi_context_t & context) override {
  auto P = this -> get_problem ();
  f-> push_back (P-> param . single_source );
}

จากนั้นเราเริ่มวนซ้ำวนซ้ำของเราซึ่งวนซ้ำจนกว่าจะมีเงื่อนไขการลู่เข้า หากไม่มีการระบุเงื่อนไขลูปจะบรรจบกันเมื่อชายแดนว่างเปล่า

 void loop (gcuda:: multi_context_t & context) override {
  auto E = this -> get_enactor ();   // Pointer to enactor interface.
  auto P = this -> get_problem ();   // Pointer to problem (data) interface.
  auto G = P-> get_graph ();        // Graph that we are processing.

  auto single_source = P-> param . single_source ;  // Initial source node.
  auto distances = P-> result . distances ;         // Distances array for BFS.
  auto visited = P-> visited . data (). get ();       // Visited map.
  auto iteration = this -> iteration ;             // Iteration we are on.

  // Following lambda expression is applied on every source,
  // neighbor, edge, weight tuple during the traversal.
  // Our intent here is to find and update the minimum distance when found.
  // And return which neighbor goes in the output frontier after traversal.
  auto search = [=] __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);
  };

  // Execute advance operator on the search lambda expression.
  // Uses load_balance_t::block_mapped algorithm (try others for perf. tuning.)
  operators::advance::execute<operators:: load_balance_t ::block_mapped>(
    G, E, search, context);
}

รวม/gunrock/อัลกอริทึม/bfs.hxx

วิธีการอ้างอิง Gunrock & Essentials

ขอบคุณที่อ้างถึงงานของเรา

 @article { Wang:2017:GGG ,
  author =	 { Yangzihao Wang and Yuechao Pan and Andrew Davidson
                  and Yuduo Wu and Carl Yang and Leyuan Wang and
                  Muhammad Osama and Chenshan Yuan and Weitang Liu and
                  Andy T. Riffel and John D. Owens } ,
  title =	 { {G}unrock: {GPU} Graph Analytics } ,
  journal =	 { ACM Transactions on Parallel Computing } ,
  year =	 2017 ,
  volume =	 4 ,
  number =	 1 ,
  month =	 aug,
  pages =	 { 3:1--3:49 } ,
  doi =		 { 10.1145/3108140 } ,
  ee =		 { http://arxiv.org/abs/1701.01170 } ,
  acmauthorize = { https://dl.acm.org/doi/10.1145/3108140?cid=81100458295 } ,
  url =		 { http://escholarship.org/uc/item/9gj6r1dj } ,
  code =	 { https://github.com/gunrock/gunrock } ,
  ucdcite =	 { a115 } ,
}

 @InProceedings { Osama:2022:EOP ,
  author =	 { Muhammad Osama and Serban D. Porumbescu and John D. Owens } ,
  title =	 { Essentials of Parallel Graph Analytics } ,
  booktitle =	 { Proceedings of the Workshop on Graphs,
                  Architectures, Programming, and Learning } ,
  year =	 2022 ,
  series =	 { GrAPL 2022 } ,
  month =	 may,
  pages =	 { 314--317 } ,
  doi =		 { 10.1109/IPDPSW55747.2022.00061 } ,
  url =          { https://escholarship.org/uc/item/2p19z28q } ,
}

ลิขสิทธิ์และใบอนุญาต

Gunrock เป็นลิขสิทธิ์ผู้สำเร็จราชการแห่งมหาวิทยาลัยแคลิฟอร์เนีย ไลบรารีตัวอย่างและซอร์สโค้ดทั้งหมดจะถูกเผยแพร่ภายใต้ Apache 2.0

เชิงอรรถ

1. ที่เก็บนี้ถูกย้ายจาก https://github.com/gunrock/essentials และประวัติก่อนหน้านี้ได้รับการเก็บรักษาไว้ด้วยแท็กและภายใต้สาขา master อ่านเพิ่มเติมเกี่ยวกับ Gunrock และ Essentials ในกระดาษวิสัยทัศน์ของเรา: สิ่งจำเป็นของการวิเคราะห์กราฟแบบขนาน

2. CUDA V11.5.1 หรือสูงกว่า ที่แนะนำเนื่องจากสนับสนุนการจัดสรรหน่วยความจำที่สั่งซื้อสตรีม