OpenMP กับ race condition

ความรู้เบื้องต้น

  • C – programing
  • OpenMP

การเขียนโปรแกรมบนสถาปัตยกรรม shared momory ปัญหาหนึ่งที่เรามักจะพบคือ race condition หรือ “ภาวะแข่งขัน”   ยกตัวอย่าง การเขียนโปรแกรมด้วย OpenMP ในลักษณะนี้นะครับ

1:  int i=0;
2:  #pragma omp parallel
3:   i++;
4:  printf(“%3d”,i);

โค๊ดนี้ผมนำไปรันบน intel processor แบบ quad core ปรากฏว่าผลลัพธ์ให้ค่าที่เหวี่ยงไปมา ตัวอย่าง ผลลัพธ์ของเครื่องผม 20 รอบคำสั่งคือ

3  3  4  3  4 3  3 4  4  4  4  4  3  2  4  3  3  3  4  4

บรรทัดที่ 3 ของโปรแกรม เกิด race condition ขึ้น เนื่องจากตัวแปร i เป็นตัวแปรที่ใช้ร่วมกัน สำหรับ thread ทั้ง 4 ตัว ดังนั้นจังหวะที่อ่านและเขียนข้อมูลถ้าไม่มีลักษะเป็น atomic จะทำให้เกิดปัญหานี้ขึ้นได้

OpenMP มี directive ชื่อว่า atomic สำหรับช่วยให้ thread ใดๆ สามารถอัปเดตของตัวแปรใด ๆ ได้โดยที่ไม่ต้องกังวลว่า ณ เวลานั้นจะมี thread ตัวอื่นเข้ามาเรียกใช้งาน ดังนั้นจากตัวอย่างข้างบนเราสามารถแก้ไขโดยใช้ atomic ได้ดังนี้

1:  int i=0;
2:  #pragma omp parallel
3: {
4:   #pragma omp atomic
5:      i++;
6:  }
7:  printf(“%3d”,i);

ผลลัพธ์ 20 รอบคำสั่ง เมื่อแก้ไขโปรแกรมแล้ว

4  4  4  4  4  4  4 4  4  4  4  4  4  4  4  4  4  4  4  4

สำหรับ directive atomic นั้นไม่สามารถกำหนดให้ block ของ code ได้ ถ้าต้องการป้องกันตัวแปรมากกว่า 1 ตัว วิธีการหนึ่งคือ ต้องเขียน #pragma omp atomic ให้กับทุกๆตัวแปร ดังนี้

1:  int i=0,j=0;
2:  #pragma omp parallel
3: {
4:   #pragma omp atomic
5:      i++;
6:   #pragma omp atomic
7:     j++;
8:  }
9:  printf(“i=%d,j=%d\n”,i,j);

OpenMP มี directive อีกตัวหนึ่งที่ให้ใช้ได้ง่ายกว่า คือ critical ซึ่งหน้าที่จะเหมือนกับ atomic เพียงแต่เราสามารถกำหนดส่วนของ block ลงไปได้เลย ซึ่งจะช่วยลดความยุ่งยากในการเขียนโปรแกรมไปได้พอสมควร

1:  int i=0,j=0;
2:  #pragma omp parallel
3: {
4:   #pragma omp critical
5:   {
6:      i++;
7:      j++;
8:    }
9:  }
10:  printf(“i=%d,j=%d\n”,i);

Advertisements

การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 2(จบ)

บทความนี้ เป็นตอนจบ  ของการประมาณค่า PI ด้วย Monte Carlo Method  ครับ ใครยังไม่ได้อ่านตอนแรก สามารถตามไปอ่านได้ที่นี่ครับ

การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 1

พิจารณาพื้นที่ใน quadrant ที่ 1 ของวงกลม จะได้ว่า พื้นที่สี่เหลี่ยมจัตุรัสที่มีความยาวของแต่ละด้านเป็น r มีค่าเท่ากับ r^2 ดังรูป

ถ้ากำหนดให้ r = 1  จะได้พื้นที่ของ สี่เหลี่ยมจัตุรัสมีค่าเท่ากับ 1  ด้วย(1^2=1)

ดังนั้นขนาดของพื้นที่ สี่เหลี่ยมทั้งหมดที่ครอบคลุมพื้นที่ของ วงกลมที่มีรัศมี 1 หน่วย จึงมีค่าเป็น 1*4 = 4 หน่วย จากข้อมูลดังกล่าว เราสามารถประมาณค่า Pi ด้วยสายตาได้ว่า ค่าของ Pi นั้นจะมีค่าน้อยกว่า 4

แนวคิดของ Monte Carlo Method ที่นำมาใช้ในการหาพื้นที่ของ Pi คือการใช้คอมพิวเตอร์ในการสุ่มจำนวนจุดทั้งหมดใน quadrant ที่ 1 แล้วนับอัตราส่วนของจำนวนจุดที่อยู่ในรัศมีต่อจำนวนจุดทั้งหมด เราก็จะได้พื้นที่ 1 ใน 4 ของ Pi นั่นเอง

ตัวอย่างเช่น ถ้าเราสุ่มจำนวนจุดขึ้นมา 10 จุด ปรากฏว่า มี 9 จุดอยู่ภายในรัศมีของวงกลม และอีก 1 จุดอยู่นอกรัศมีของวงกลม ดังนั้นเราจะได้ว่า ค่าของ Pi ที่หาได้ด้วยวิธีการนี้มีค่าเป็น   4*9/10  = 3.6

ข้อสังเกตของวิธีการนี้คือ หากเราสุ่มค่าออกมาแล้ว ตกอยู่ในพื้นที่ของวงกลมทั้งหมด ค่าของ Pi ที่หาได้จะมีค่าเป็น 4*1  หรือหากค่าที่สุ่มตกอยู่นอกพื้นที่ของวงกลมทั้งหมดเราจะได้ค่าของ Pi เท่ากับ 4*0 ซึ่งก็คือขอบเขตของคำตอบที่เราต้องการหานั่นเอง

ถ้าเราเพิ่มจำนวนครั้งในการสุ่ม หรือในที่นี้คือการเพิ่มจำนวนจุด ให้มากขึ้นค่าของ Pi ที่หาได้จะยิ่งมีความคลาดเคลื่อนน้อย หรือเข้าใกล้สู่ค่าที่ใกล้เคียง(โดยประมาณ) ค่า Pi(22/7) มากขึ้นเท่านั้น

หลักคิดของ Monte Carlo Method ก็มีเพียงเท่านี้ครับ ในส่วนต่อไปผมจะได้อธิบายถึงวิธีขั้นตอน(Algorithm) ในการหาค่า Pi ด้วยวิธีทางคอมพิวเตอร์ครับ ก่อนอื่นพิจารณาค่าของจุดที่เกิดจากการสุ่ม 1 จุดใน quadrant ที่ 1

[ ภาพประกอบ ]

ถ้าให้ระยะห่างจากแนวแกน x เป็น x1 และ ระยะห่างจากแนวแกน y เป็น y1 จากทฤษฎีของปิทากอรัส จะได้ว่า พิกัดของจุด  x1,y1  นั้นห่างจากจุดศูนย์กลางเท่ากับ รากที่สองของ x1^2+y1^2 ในที่นี้แทนที่ด้วยค่า d ดังสมการ

เนื่องจากรัศมีของวงกลมมีค่าเป็น 1 ดังนั้น ระยะห่างของจุดที่มีพิกัด  x,y ใดๆ จะอยู่ในพื้นที่วงกลมก็ต่อเมื่อ d มีค่าน้อยกว่าหรือเท่ากับ 1 นั่นเอง

เมื่อเราได้ระยะห่างจากจุดศูนย์กลางของแต่ละจุดออกมาแล้ว ขั้นตอนต่อไปก็คือการนับจำนวนจุดทั้งหมดแล้ว นำมาเปรียบเทียบอัตราส่วนเพื่อคำนวณหาค่า Pi ต่อไป ผมขอสรุปเป็นลำดับขั้นตอนดังนี้ครับ

  1. สุ่มค่า x และ y โดยให้ x และ y เป็นทศนิยมมีค่าอยู่ระหว่าง 0 ถึง 1
  2. หาค่า d ออกมาตามสมการข้างบน
  3. ถ้า ค่า d น้อยกว่าหรือเท่ากับ 1 ให้นับจำนวนไว้ (ในที่นี้ขอแทนที่ด้วย n )
  4. วนรอบทำข้อ 1-3 ซ้ำ โดยจำนวนรอบเท่ากับจำนวนจุดทั้งหมดที่ต้องการสุ่ม (ในที่นี้ขอแทนที่ด้วย N )
  5. Pi มีค่าเท่ากับ  4* n/N

จบแล้วครับสำหรับบทความ การหาค่า Pi โดยใช้  Monte Carlo Method  จากการทดสอบของผมเมื่อนำไปเขียนเป็นโปรแกรม พบว่าค่าที่หาได้มีค่าใกล้เคียงกับค่า Pi จริงๆ ยิ่งเราเพิ่มจำนวนรอบในการสุ่ม ค่าที่ได้ยิ่งใกล้เคียงกับค่าจริงมากเท่านั้น อย่างไรก็ตามวิธีการนี้เป็นแค่การประมาณค่าเท่านั้น ไม่สามารถเทียบเท่ากับการหาด้วยอัตราส่วน 22/7 ได้  ใครไม่เชื่อก็ลองทดสอบด้วยตัวเองดูนะครับ

การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 1

จำได้ว่า ตอนเรียนวิชาคณิตศาสตร์ ม.ต้น

อาจารย์จะให้หาพื้นที่ของรูปทรงเรขาคณิต ต่าง ๆ เช่น สี่เหลี่ยม สามเหลี่ยม วงกลม วงรี ทรงกลม กรวย (เอาเท่าที่นึกออกพอ) ซึ่งสมัยนั้น อาจารย์จะให้สูตรในการคำนวณมาเลย เช่น

พื้นที่สี่เหลี่ยม =  ฐาน * สูง

พื้นที่สามเหลี่ยม =  1/2  * ฐาน * สูง ( ครึ่งหนึ่งของสี่เหลี่ยม)

พื้นที่วงกลม =  Pi * รัศมียกกำลังสอง                                                 ——(1)

พื้นที่วงรี = เอ… จำไม่ได้ครับ – -‘  ( จำได้แต่ว่าจะเอารัศมีแนวนอนกับแนวตั้งมาใช้ ) -> ดูคำตอบจาก wikipedia

โดยค่าของ Pi   = 22/7 หรือ 3.1416 โดยประมาณ(จริงๆผมจำได้แค่ 3.14) เป็นค่าคงที่  แล้วค่า Pi นี้มีที่มาที่ไปอย่างไร เลข 22/7 หามาจากไหนไว้ถ้ามีโอกาสจะนำมาเล่าสู่กันฟังครับ

นอกจากอัตราส่วนคงที่ที่ใช้ในการคำนวณหาค่า Pi แล้ว ถ้าเรายึดเอา สมการเป็นหลักว่า พื้นที่วงกลม = π *รัศมียกกำลังสอง แล้ว ยังมีวิธีที่เราจะสามารถหา Pi ได้ หากเรารู้ว่า พื้นที่ของวงกลมนั้นมีค่าเท่าใดครับ

จาก (1) จะได้ว่า

Pi = พื้นที่วงกลม / รัศมียกกำลังสอง

ถ้าเราให้ค่าของ รัศมี เท่ากับ 1 เราจะได้ว่า

Pi = พื้นที่วงกลม                                                                                 ——(2)

ดังนั้นถ้ามีใครถามเราว่า ค่า Pi มีค่าเป็นเท่าไหร่ นอกจากเราจะตอบว่า 3.14 หรือ 22/7 แล้ว เรายังสามารถตอบแบบหล่อๆ ว่า เท่ากับ พื้นที่ของวงกลมที่มีรัศมี 1 หน่วยได้อีกต่างหากครับ : )

เนื่องจากรูปทรงที่สมมาตรของวงกลม ดังนั้นหากเราแบ่งพื้นที่ออกเป็น 4 ส่วน  เราจะสามารถอินทิเกรตเพื่อหาพื้นที่ใต้ส่วนโค้งตามสมการที่ (3) ของกราฟวงกลมขนาด 1 หน่วยได้ โดยพื้นที่ที่หาได้จากการอินทิเกรต คือ 1ใน 4 ส่วนของพื้นที่วงกลมทั้งหมด ซึ่งเราก็จะได้ค่า Pi ออกมา

จากสมการควบคุมของวงกลม

x^2 + y^2 = r^2

เมื่อ r = 1 จะได้ว่า

y = sqrt( 1-x^2 )                                                          ——(3)

มีวิธีการอีกวิธีหนึ่งซึ่งเป็นวิธีการทางคอมพิวเตอร์ ที่เรียกว่า Monte Carlo Method  ซึ่งใช้หลักของการสุ่มค่า เพื่อแก้ปัญหาหลายๆอย่างทางคณิตศาสตร์ หรือฟิสิกส์ได้ [อ้างอิง]  คนที่ตั้งชื่อวิธีการนี้ขึ้นมามีสองคน หนึ่งในนั้นถ้าบอกชื่อหลายคนคงจะร้องอ๋อขึ้นมาทันที เพราะเขาคนนั้นถูกยกย่องให้เป็นบิดาของคอมพิวเตอร์นั่นเอง  ถูกต้องแล้วครับ เขาคนนั้นก็คือ John Von Neumann นั่นเอง อีกคนก็คือ Stanislaw Ulam


บิดาของคอมพิวเตอร์ รูปหล่อทีเดียวใช่ไหมครับ

ที่มาของชื่อมาจาก บ่อนคาสิโนที่ชื่อ Monte Carlo ในเมือง Monaco ของฝรั่งเศสครับ ทำไมเอาชื่อบ่อนมาใช้อันนี้ผมก็ไม่ทราบได้ครับ ถ้าอยากรู้ลองไปอ่านเอกสารอ้างอิงดูครับ [ 2 ]

บทความนี้ชักจะยาว และตัวผมเองชักจะเมื่อย เอาไว้ผมมีเวลาจะมาเขียนตอนที่ 2 ต่อในโอกาสต่อไปนะครับ

ขอขอบคุณแหล่งอ้างอิงของบทความและรูปภาพประกอบ

  1. http://en.wikipedia.org/wiki/Monte_Carlo_method
  2. Nicholas Metropolis (1987). “The beginning of the Monte Carlo method”. Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130.

บทความที่เกี่ยวข้อง
การประมาณค่า PI โดยใช้ Monte Carlo Method ตอนที่ 2