วิธีจัดการโครงสร้างข้อมูลที่แคชด้วยมัลติเธรด (เช่น openmp)

ฉันใช้ OpenMP เพื่อทำให้ไลบรารี C++ ของเราขนานกัน ในนั้น เรามีสถานที่หลายแห่งที่เราหลีกเลี่ยงการคำนวณบางสิ่งใหม่โดยการจัดเก็บผลลัพธ์ไว้ในตัวแปร (เช่น การแคชผลลัพธ์เพื่อนำกลับมาใช้ใหม่) อย่างไรก็ตาม ลักษณะการทำงานนี้ถูกซ่อนไว้สำหรับผู้ใช้ในวิธีการตามคลาส ตัวอย่างเช่น ในการใช้วิธีการครั้งแรก แคชจะถูกเติมเต็ม การใช้งานที่ตามมาทั้งหมดจะอ่านจากแคชเท่านั้น

ปัญหาของฉันคือตอนนี้ในโปรแกรมแบบมัลติเธรด หลายเธรดสามารถเรียกใช้เมธอดดังกล่าวได้พร้อมกัน ส่งผลให้เกิดสภาวะการแข่งขันในการสร้าง/เข้าถึงแคช ขณะนี้ฉันกำลังแก้ไขสิ่งนั้นโดยการวางแคชไว้ในส่วนที่สำคัญ แต่สิ่งนี้จะทำให้ทุกอย่างช้าลงแน่นอน

คลาสตัวอย่างอาจเป็นดังนี้

class A {
public:
   A() : initialized(false)
     {}
   int get(int a)
      { 
#pragma omp critical(CACHING)
        if (!initialized)
          initialize_cache();
        return cache[a];
      }
private:
   bool initialized;
   void initialize_cache()
     {
       // do some heavy stuff
       initialized=true;
     }
   int *cache;
};

มันจะดีกว่าถ้าส่วนที่วิกฤติอยู่ในฟังก์ชัน Initialize_cache() เนื่องจากมันจะล็อคเธรดทั้งหมดเมื่อยังไม่ได้เตรียมใช้งานแคชเท่านั้น (นั่นคือเพียงครั้งเดียว) แต่ดูเหมือนว่าจะเป็นอันตรายเนื่องจากอาจลองใช้หลายเธรดได้ เพื่อเริ่มต้นแคชในเวลาเดียวกัน

ข้อเสนอแนะใด ๆ เพื่อปรับปรุงสิ่งนี้? ตามหลักการแล้วโซลูชันจะเข้ากันได้กับ OpenMP เวอร์ชันเก่ากว่า (แม้แต่ v2 สำหรับ Visual Studio...)

PS: สิ่งนี้อาจถูกถามมาก่อน แต่การค้นหา openmp และแคชทำให้เกิดสิ่งต่าง ๆ มากมายบนแคชตัวประมวลผล ซึ่งไม่ใช่สิ่งที่ฉันอยากรู้...


c++ multithreading openmp caching
person krthie    schedule 16.01.2015    source แหล่งที่มา
comment
คุณสามารถสร้างคลาสใหม่และตัวแปรโกลบอลของคลาสนั้นและให้ ctor ใหม่ทำการเริ่มต้นของคุณได้หรือไม่?   -  person brian beuning    schedule 16.01.2015
comment
ในชีวิตจริง ออบเจ็กต์ของฉันถูก set_up ณ รันไทม์ด้วยพารามิเตอร์ที่แตกต่างกัน เมื่อเป็น set_up แคชจะถูกล้างเนื่องจากไม่เหมาะสมอีกต่อไป ไม่ ฉันไม่สามารถมีตัวแปรร่วมได้ นอกจากนี้ เนื่องจากเวลาในการคำนวณของแคชค่อนข้างสูงและไม่จำเป็นในทุกกรณีการใช้งาน ขณะนี้เราหลีกเลี่ยงการเริ่มต้นแคช เว้นแต่ว่าเราต้องการมันจริงๆ (คุณไม่รู้สิ่งนี้จากคำถาม ฉันเดาว่าสิ่งนี้เกิดขึ้นเมื่อพยายามยกตัวอย่างง่ายๆ)   -  person krthie    schedule 16.01.2015

คำตอบ (2)


arrow_upward
3
arrow_downward

คุณสามารถใช้ "Double-Checked-Locking(DCL) pattern" กับการดำเนินการแบบอะตอมมิกของ OpenMP ต้องใช้ OpenMP v3.1 หรือใหม่กว่า (ตัวเลือก read/write ของ omp atomic pragma)

class A {
public:
   A() : initialized(false)
     {}
   int get(int a)
      {
        bool b;
#pragma omp atomic read
        b = initialized;
        if (!b) {
#pragma omp critical(CACHING)
          // you must recheck in critical section
          if (!initialized)
            initialize_cache();
        }
        return cache[a];
      }
private:
   bool initialized;
   void initialize_cache()
     {
       // do some heavy stuff
#pragma omp atomic write
       initialized = true;
     }
   int *cache;
};

...แต่ฉันขอแนะนำหนึ่งในตัวเลือกต่อไปนี้มากกว่ารูปแบบ DCL:

  • pthread_once() (ไลบรารีเธรด POSIX)
  • std::call_once() (ไลบรารีมาตรฐาน C++11)
  • ตัวแปร static ที่ปลอดภัยสำหรับเธรด (คุณลักษณะภาษาหลัก C ++ 11)
person yohjp    schedule 17.01.2015
comment
มีโอกาสที่จะทำเช่นนี้กับ openmp เวอร์ชันก่อนหน้าหรือไม่? ฉันจำเป็นต้องสามารถใช้งานข้ามแพลตฟอร์มได้มากที่สุดเท่าที่จะเป็นไปได้ วิธีแก้ปัญหานี้เอาชนะปัญหาเกี่ยวกับรูปแบบ DCL ได้หรือไม่ (ดูเช่น michaelsuess.net/publications/suess_leopold_singleton_07.pdf) - person krthie; 21.01.2015
comment
AFAIK ไม่มีวิธีพกพาก่อน OpenMP v3.0 ยกเว้นการใช้ omp critical โครงสร้างโดยตรง และฉันคิดว่าโค้ดนี้ทำงานได้ดีภายใต้โมเดลหน่วยความจำ OpenMP เนื่องจากการเข้าถึงของ initialized ถูกกำหนดให้เป็นอะตอมมิกและได้รับการปกป้องโดยส่วนสำคัญ - person yohjp; 21.01.2015

arrow_upward
2
arrow_downward

ซิงเกิลตันที่มีประสิทธิภาพคือตัวเลือกที่ดีที่สุดสำหรับคุณ โปรดตรวจสอบที่นี่ซิงเกิลตันที่ปลอดภัยสำหรับเธรดที่มีประสิทธิภาพใน C++

นอกจากนี้ Herb Sutter พูดถึงเรื่องนั้นใน CppCon 2014

นี่คือข้อมูลโค้ดแบบเต็มจากวิดีโอที่ฉันแสดงด้านบน:

class Foo {
public:
    static Foo* Instance();
private:
    Foo() {init();}
    void init() { cout << "init done." << endl;} // your init cache function.
    static atomic<Foo*> pinstance;
    static mutex m_;
};

atomic<Foo*> Foo::pinstance { nullptr };
std::mutex Foo::m_;

Foo* Foo::Instance() {
  if(pinstance == nullptr) {
    lock_guard<mutex> lock(m_);
    if(pinstance == nullptr) {
        pinstance = new Foo();
    }
  }
  return pinstance;
}

เรียกใช้โค้ดที่นี่: http://ideone.com/olvK13

person qqibrow    schedule 16.01.2015
comment
ขอบคุณ. แคชของฉันต้องเป็นวัตถุเฉพาะ เช่น ไม่ใช่ซิงเกิลตัน แต่ฉันจะยอมรับว่าความเป็นไปได้นั้นไม่ชัดเจนจากคำถามของฉัน - person krthie; 22.01.2015