ก้าวแรก HPC #06: อัลกอริทึมประสิทธิภาพสูงและการปรับปรุงประสิทธิภาพ

เกริ่นนำ

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

การแข่งขันเพื่อหาค่า Bernoulli Number

ในบทความที่ผ่านมา ผมใช้อัลกอริทึมอย่างง่าย นั่นคือ Recursive เป็นหาค่า Bernoulli Number ไปจนถึง B(1000) ท่านสงสัยไหมครับว่าค่า Bernoulli Number ที่สูงที่สุดเท่าที่มนุษย์หาได้คือ B ลำดับที่เท่าไร ผมมีคำตอบครับ ลองดูที่ตารางนี้ดูครับ

http://en.wikipedia.org/wiki/Bernoulli_number

 

ข้อมูลจาก http://en.wikipedia.org/wiki/Bernoulli_number

อย่างที่เราทราบกับว่า John Bernoulli ให้กำเนิดเลขลำดับชุดนี้ที่ B(10) ดังที่ผมเคยอธิบายไว้แล้วในบทความ Note G จากวันนั้นเป็นต้นมา ก็มีความพยายามที่จะหาค่า B ในลำดับที่สูงขึ้นๆ อย่างต่อเนื่อง ตามที่เห็นในตารางครับ และเป็น David Harvey ครับ เป็นผู้ที่สามารถหาค่า B ได้สูงสุด นั่นคือ B(100,000,000)  ร้อยล้านครับ B(1000) ของเรากลายเป็นเด็กอนุบาลไปเลยครับ ลองดูที่จำนวนหลักครับ 676,752,569 ประมาณหกร้อยล้านหลัก หรือถ้าเก็บเป็นแฟ้มข้อมูลก็จะได้ 676MB เก็บเลขจำนวนเดียวนะครับ หรือถ้าเป็นหนังสือขนาด A4 มี 1,000 หน้า ก็ต้องใช้ถึง 264 เล่ม ไม่ธรรมดาจริงๆ ครับ

ข้อน่าสังเกตครับ เนื่องจาก Bm ไป Bm+1 นั้นใช้เวลาไม่มากนัก ถ้าเราใช้อัลกอริทึมในบทความก่อนหน้า ดังนั้นมันจะดูจุ๋มจิ๋มเกินไปที่จะมาทำลายสถิติกันรายวัน เขาเลยปรับให้ขั้นขึ้นทีละ 10 เท่า จะได้ท้าทายหน่อย ดังนั้นเราคงต้องคอยลุ้นดูว่าใครจะสามารถหา B ลำดับที่พันล้านได้ก่อนกันครับ

อัลกอริทึมของ Dr. Harvey

บทความนี้ผมจะนำเสนออัลกอริทึมของ Dr. David Harvey แห่ง ม. New South Wales ออสเตรเลีย ซึ่งอัลกอริทึมนี้เป็นอัลกอริทึมที่ใช้ทำสถิติโลก ดังแสดงไว้ข้างต้น แต่อัลกอริทึมที่ก็ไม่ใช้อัลกอริทึมที่เร็วนี้สุดนะครับ เพราะ Dr. Harvey ก็มีการสร้างอัลกอริทึมใหม่ๆ ที่ดึกว่าขึ้นมาอีก แต่ที่ผมเลือกใช้อัลกอริทึมนี้เพราะมีความแพร่หลายสูงสุดครับ ถ้าท่านสนใจในงานของ Dr. Harvey ไปดูได้ที่ http://web.maths.unsw.edu.au/~davidharvey/ ส่วนอัลกอริทึมที่ใช้ทำลายสถิติโลกนั้น Dr. Havary ไม่ได้ตั้งชื่อไว้ แต่ลงรายละเอียดเอาไว้ที่บทความ  A Multimodular Algorithm for Computing Bernoulli Numbers ถ้าท่านสนใจเรื่องเกี่ยวกับ Bernoulli Number นอกเหนือจาก wikpedia แล้วแนะนำให้อ่านบทความนี้เพิ่มเติมครับ

จุดเด่นของอัลกอริทึมนี้คือการรองรับการประมวลผลแบบขนาน ที่อัลกอริทึมที่ขึ้นแท่นเป็นแชมป์ได้ก็เนื่องมาจากเหตุนี้นี่เองครับ แต่ผมจะยังไม่ก้าวล่วงไปถึงเรื่องของการประมวลผลแบบขนานในบทความนี้ ผมจะทิ้งมันเอาไว้ก่อน แต่ผมจะเอาจุดนี้เป็นเชื้อเพื่อใช้จุดไฟในบทความต่อๆ ไป ยิ่งไปกว่านั้นความพิเศษอย่างหนึ่งของอัลกอริทึมตัวนี้คือ ไม่มีการอ้างอิงถึงค่า B ก่อนหน้าครับ สามารถหาได้เลยโดยไม่ต้องสะสมมา

คำว่า ‘multimodular’  คำว่า modular มาจาก modular arithemetic ซึ่งเป็นคณิตศาสตร์แขนงหนึ่งอยู่ในหมวดของ ทฤษฎีจำนวน (Number Theory)  ผมไม่มั่นใจว่าท่านเคยผ่านหูผ่านตามาไหม ทฤษฎีจำนวนนี้ เมื่อก่อนมีแต่เอกคณิตศาสตร์ที่ได้เรียน คนคอมพิวเตอร์อย่างผมก็อดไป แต่ต่อมาเรื่องการเข้ารหัส RSA ได้รับความนิยม ซึ่ง RSA ก็มีพื้นฐานมาจากทฤษฎีจำนวนเช่นเดียวกัน คนคอมพิวเตอร์ในยุคใหม่ๆ ก็น่าจะเคยเรียนมาบ้างครับ หรือใครได้เรียนรู้เรื่องการเข้ารหัสมา จะน่าพอคุ้นเคยกับทฤษฏีจำนวนมาบ้างครับ

เผื่อใครไม่คุ้นเคยเรื่องทฤษฏีจำนวน ผมก็ขอคุยภาพรวมให้ฟังครับ ทฤษฎีจำนวนเป็นเรื่องเกี่ยวกับตัวเลขโดยเน้นที่เลขจำนวนเต็มเป็นหลัก ทศนิยมแทบไม่สนใจ และเมื่อใด้ตัวเลขจำนวนเต็มมาแล้วก็จะหาความสัมพันธ์ของเลขต่างๆ เช่นค่าจำนวนเฉพาะ ปิธากอรัสเป็นต้น ดูเหมือนว่าจะง่ายใช่ไหมครับ เด็กๆ ก็น่าจะพอได้เรียนบ้างจำพวก คูณร่วมน้อยและหารร่วมมาก ไรทำนองนี้ นั่นแหละครับทฤษฎีจำนวน แต่ก็ไม่ได้ง่ายๆ แค่นั้นนะครับ ทุกศาสตร์สามารถเรียนให้ลึกและยากได้ทั้งนั้นครับ ผมอาจจะเขียนเป็นชุดบทความเกี่ยวกับทฤษฎีตัวเลขไปจนถึงการเข้ารหัสถ้ามีคนสนใจ แต่ในบทความนี้ผมจะทำให้ง่ายเข้าไว้ครับ

ผมนำเอาอัลกอริทึมดังกล่าวมาเขียนเป็นภาษา Python เพื่อความเข้าใจ ผมจึงขอตัดบางส่วนของบทความเฉพาะในส่วนอัลกอริทึมที่ผมใช้มาให้ท่านดู ทั้งนี้ไม่ได้มีเจตนาในการละเมิดลิขสิทธิ์แต่อย่างใด อัลกอริทึมมีหน้าตาดังนี้ครับ

bk_algor2

หลักการโดยภาพรวมนะครับ หาค่าจำนวนเฉพาะ เรียงมาตั้งแต่ 2 จนถึงจุดๆ หนึ่งครับตามสมการข้างบน คัดกรองเอาค่าจำนวนเฉพาะที่ตรงตามเงื่อนไขเข้าอัลกอริทึมที่หารเอาเฉพาะเศษออกมาก ซึ่งอัลกอริทึมในส่วนนี้สามารถกระจายหลายเครื่องประมวลผลแบบขนานได้ครับ จากนั้นก็รวบรวมเอาเศษที่ได้ทั้งหมดนำเอามาเข้าสู่อัลกอริทึม การเศษของชาวจีน (Chinese Reminder Theorm : CRT) เพื่อให้ได้ค่าตัวเศษข้างบนของผลลัพธ์ (Nk) ซึ่งเป็นตัวเลขที่ยาวมากครับ ส่วนตัวหารการใช้สูตรที่หา Dk ข้างบนนั่นเอง โดยที่อัลกอริทึมที่ผมกล่าวไว้ข้างต้นว่าสามารถกระจายได้ มีหน้าตาตังนี้ครับ

bk_algor1

ถ้าต้องอธิบายอัลกอริทึมกันจริงๆ คงต้องเขียนกันหลายบทความ เพราะแต่ละบรรทัดที่ท่านเห็นนั้นส่วนใหญ่เป็นเรื่องทฤษฎีจำนวนทั้งสิ้น แต่ละบรรทัดมีอัลกอริทึมเป็นของตนเองและก็มีคนเขียนแข่งกันเพื่อให้ได้ประสิทธิภาพสูงสุดด้วย ผมก็เลขขอข้ามไปดีกว่า ไม่งั้นพายเรืออยู่ในอ่างไม่ได้ไปไหนแน่

การเขียนโปรแกรมภาษา Python v1

ผมนำเอาอัลกอริทึมมาเขียนเป็นภาษา Python เห็นอัลกอริทึมสั้นๆ แต่พอเขียนจริงๆ เกือบสองร้อยบรรทัดครับ ยาวเกินความเหมาะสมที่นำมาแสดงในเว็บนี้ครับ ผมทำ link ให้ไปเปิดอีกหน้าหนึ่งดีกว่า ดังนี้ครับ

https://github.com/hpc-thai/HPCThai/blob/master/introHPC/06/b_modular_v1.py

หรือดูแฟ้มได้จาก HPCThai/introlHPC/06/b_modular_v1.py  การทดสอบอัลกอริทึมเราใช้วิธีเดียวกันกับบทความที่แล้วครับ เปลี่ยน directory ปัจจุบันให้เป็น 06 แล้วใช้ ipython3 สำหรับ *buntu

ลองทดลองดูครับว่าหาคำตอบได้ถูกต้องหรือไม่ น่าจะไม่มีปัญหานะครับเรื่องความถูกต้อง แต่ขอเตือนว่าอย่าหา B ค่าเยอะมากนัก อัลกอริทึมตัวนี้มีปัญหาเรื่องประสิทธิภาพอย่างแรงครับ เรามาลองใช้ bern.py ที่ได้มาจาก บทความก่อนหน้าครับ ได้ผลลัพธ์ดังนี้ครับ

b_list_mod_v1

bern.py อยู่ใน 05 ก็เลยต้องถอยไปเรียกตามวิธีข้างบน ส่วนอัลกอริทึม ผมใช้ m แทน modular algorithm ตอนนี้เป็น m1 ก่อนครับ ผลลัพธ์ที่ได้น่าเกลียดมากครับ ลองทำ curvefit ดูครับ ได้ผลลัพธ์ดังนี้

b_curvefit_mod_v1

 

คงไม่เสียเวลาแสดงกราฟครับ อัลกอริทึมนี้แย่กว่า recursive v1 เสียอีก ทำไมถึงเป็นเช่นนั้น สรุปว่าอัลกอริทึมมันไม่ได้เรื่องรึเปล่า แต่อัลกอริทึมตัวนี้ใช้สร้างสถิติโลกนะครับ พอนึกออกไหมครับปัญหามันอยู่ที่ไหน อัลกอริทึมไม่มีปัญหาหรอกครับ ที่มีปัญหาคือผมเองต่างหาก เขียนห่วย แต่ห่วยตรงไหนผมยังไม่รู้เลยครับ งานนี้ต้องขอตัวช่วยแล้วครับ

ในโลกของการเขียนโปรแกรม เรามีเครื่องมือพื้นฐานอยู่ตัวหนึ่งครับเรียกว่า profiler ที่ช่วยบอกเราได้ว่าฟังก์ชันไหนกินเวลาเท่าไรในการทำงาน หรือจะเอาละเอียดรายบรรทัดก็ยังได้ครับ ถ้าเป็นภาษาที่ต้องคอมไพล์ เวลาคอมไพล์จะต้องแอบแทรก code ในการจับเวลาที่เรียกว่า instrumentation เข้าไปด้วย แต่สำหรับ python ไม่มีอะไรต้องยุ่งยากครับ ทุกอย่างมีพร้อมรออยู่แล้ว แค่บอกว่าเราอยากทำ profiler เวลารันเท่านั้น วิธีการบอกก็คือแทรก -m cProfile  เข้าไปในคำสั่งดังนี้ครับ

ผมเลือกใช้ B ถึง 22 เพราะไม่เร็วไม่ช้าจนเกินไปประมาณ 20 กว่าวินาที และผลลัพธ์ผม redirect ไปออก m1.txt  เมื่อเรียกใช้โปรแกรมจะรันปกติ โปรแกรมจะทำงานแต่แอบเก็บค่าเวลาและจำนวนครั้งในการเรียกแต่ละฟังก์ชันเอาไว้ เมื่อรันเสร็จมันจะแสดงผลลัพธ์ที่จับเวลาทั้งหมดต่อท้าย ทั้งฟังก์ชันที่เราเขียนและฟังก์ชันของระบบ เยอะแยะมากมายครับ แต่ถ้าไล่ดูราย column จะทำความเข้าใจไม่ยากครับ จากซ้ายไปขวา

  1. จำนวนครั้งในการเรียก
  2. เวลาที่ใช้ทั้งหมด  (หักลบเวลาที่ใช้ในฟังก์ชันที่ย่อยลงไปอีกออก)
  3. เวลาที่ใช้ต่อครั้ง   (ข้อ 3 หาร ข้อ 1)
  4. เวลาที่ใช้ทั้งหมด ไม่หักลบใดๆ
  5. เวลาที่ใช้ต่อครั้ง ไม่หักลบใดๆ
  6. ชื่อ module และชื่อฟังก์ชัน

b_profile_mod_v1

จากรูปผมตัดมาเฉพาะส่วนที่น่าสนใจ  ดูบรรทัดก่อนสุดท้ายจะเห็นว่านั่นคือ B ฟังก์ชันหลักของเราเอง อะไรๆ ก็อยู่ในนั้น จึงไม่น่าแปลกใจ ว่ามันจะกินเวลามากที่สุด ดูเวลาที่ใช้รวมทั้งหมดใน col4 ซึ่งเกินเวลา 29.298s แต่เมื่อไปดู col2 จะเห็นว่าตัวมันเองกินเวลาเพียง 0.002s เท่านั้น นอกนั้นเป็นฟังก์ชันอื่นที่ย่อยลงไป พอจับทางถูกแล้วใช้ไหมครับ ถ้าเรามองหา col2 ที่เยอะที่สุด คือตัวมันเองกินเยอะที่สุด ถ้าแก้ตัวนี้ได้ก็จบ ซึ่งจากข้างบนชี้ชัดครับ ผู้ร้ายของเราคือ congruent นั่นเอง กินเวลาเกือบทั้งหมดเลยทั้งที่มีการเรียกใช้งานเพียง 31 ครั้งเท่านั้น แต่ต่อครั้งกินเวลาเกือบ 1 วินาที ต้องแก้ครับ

ก่อนแก้ผมขอสืบสวนเพิ่มเติมก่อนนะครับ ผมอยากให้สังเกตบรรทัด computeCRT  จำได้ไหมครับ CRT คือ Chinese Reminder Theorem หรือทฤษฎีการหาเศษแบบชาวจีน ผมเล่าคร่าวๆ ให้ฟังแล้วว่าอัลกอริทึมของ Dr. Harvey มีสองส่วน ส่วนแรกสามารถกระจายหลายเครื่องเพื่อไปหาค่าเศษ จากนั้นในส่วนที่สองนำค่าเศษนั้นมาเข้าอัลกอริทึม CRT ในการรวมให้ได้ผลลัพธ์ ยังจำได้ไหมครับ ลองดูที่ computeCRT สิครับ col4 กินเวลาเท่ากัน congruent เลยครับนั่นคือ computeCRT จะเรียก congruent ไปใช้นั่นเอง เห็นเงื่อนงำอะไรบางอย่างแล้วหรือยังครับ อัลกอริทึมนี้ต่อให้คุณใช้ Supercomputer ที่เร็วที่สุดในโลกมันก็ไม่เร็วขึ้นครับ เพราะเวลาเกือบทั้งหมดไม่ได้เสียไปกับการกระจายเครื่อง แต่หากเสียไปกับการรวมในฟังก์ชัน CRT ซึ่งทำงานบน CPU เดียว นี่เองครับคือหลุมพราง

แหย่ขาข้างหนึ่งเข้าไปในทฤษฎีจำนวน

เรากลับมาที่ congruent ครับ ผมไม่ได้เขียนผิด มันทำงานถูกต้องครับ เพียงแค่เขียนห่วยไปหน่อยเท่านั้น  ก่อนแก้เรามาเรียนรู้อะไรเล็กน้อยเกี่ยวกับ congruent หน่อยครับ จะได้รู้ที่มาที่ไป คืออย่างนี้ครับ ในโลกของทฤษฎีตัวเลขอย่างที่เคยกล่าวมา มีแต่จำนวนเต็มใช่ไหมครับ ถ้าอย่างนั้นเครื่องทางคณิตศาสตร์พื้นฐานอย่างบวกลบคูณหาร จะเอามาใช้ได้หรือไม่ ลองเครื่องหมายบวกดูก่อนครับ ไม่มีปัญหาใช่ไหมครับ เลขจำนวนเต็มบวกกับจำนวนเต็ม ย่อมได้จำนวนเต็มเสมอ ลบกับคูณก็เหมือนกัน ตัวปัญหาคือหารนั่นเอง 7 / 5 ไม่ใช่จำนวนเต็มแล้วใช่ไหมครับ ดังนั้นเครื่องหมายหารนี้ จึงถูกจำกัดหน้าที่ให้เหลือเพียงการหารที่ลงตัวหรือถ้าไม่ลงตัวก็แค่รับรู้ว่าไม่ลงตัวเท่านั้น แล้วถ้าไม่ลงตัวหละ ก็ใช้วิธีเหลือเศษแทน ฟังดูเหมือนเลขประถมยังไงไม่รู้ แต่จริงๆ ไม่ง่ายนะครับ Gauss เจ้าเก่าของเรา คิดทฤษฎีการคำนวณขึ้นมาใหม่เรียกว่า Modular arithmetic คุ้นๆ แล้วใช้ไหมครับ ชื่ออัลกอริทึมนี้ใช้คณิตศาสตร์ตัวนี้ modular arithematic ถึงว่าเป็นจักรกลหลักในการขับทฤษฎีจำนวนเลยครับ เรามาเรียนพื้นฐานกันนิดหน่อยพอได้ยืดเส้นยืดสายกันดีกว่าครับ

a\equiv b(mod\ c)

เครื่องหมายที่เห็นไม่ใช่เท่ากับนะครับ มีสามขีด รวมกับคำว่า mod เรียกว่า congruent modulo หมายความว่าง่ายๆ ว่า เมื่อเอา a มาหารด้วย c จะเหลือเศษ b  ดูเหมือนจะไม่มีอะไรใช่ไหมครับแต่มีครับ ด้วยการเขียนลักษณะนี้เราเอาตัวเลขบวกทั้งสองข้าง ผลลัพธ์ยังถูกต้อง ลองดูตามนี้ครับ

12 \equiv 2(mod\ 5)
จะได้

12 + 3 \equiv 2 + 3(mod\ 5)

จะใช้การลบหรือการคูณก็ได้ แต่หารไม่ได้นะครับ หารนั้นต้องมีเงื่อนไขพิเศษเกี่ยวของกับการหารร่วมมาก (GCD) อีก มันเกี่ยวเข้าไปยังไงผมขอข้ามไปก่อนครับ คราวนี้เรามาลองดูโจทย์ที่ติดค่าตัวแปรข้อนี้ดูครับ

5x\equiv 7(mod\ 63)

หาคำตอบได้ไหมครับว่า X มีค่าเท่าไร  เอา 5 มาหารทั้งสองข้างไม่ได้นะครับ นั่นแหละครับคือตัวเนื้อหาของฟังก์ชัน congruent มันคือการแก้สมการหาค่า X นั่นเอง โดยระบุค่าสามค่าคือ a, b และ c ในเมื่ออัลกอริทึมตัวนี้ห่วย ผมก็ต้องเปลี่ยนอัลกอริทึม Gauss เจ้าเก่าก็คิดวิธีที่ดีกว่าให้เราแล้วครับ (แต่อาจจะไม่ใช่วิธีที่ดีที่สุด) นั่นคือการหาส่วนกลับของ 5 ในโลกของ modular arithmetic ส่วนกับของ 5 ไม่ใช่ 1/5 นะครับ แต่เป็นเลขอื่น เมื่อนำเอามาคูณแล้วมันจะทำให้ 5 กลายเป็นหนึ่ง ดังนั้นเราจึงหาส่วนกลับก่อน แล้วเอาส่วนกลับนั้นไปคูณทั้งสองข้าง เราก็จะได้คำตอบทันทีครับ ผมเลยเปลี่ยนอัลกอริทึมของ congruent ให้เป็น

จะเห็นได้ว่าตรงไปตรงมาครับ computeInvertMod() ก็มีอยู่แล้ว เมื่อหา invert ได้ก็ได้คำตอบครับ โดยเอา ไปคุณ b แล้วก็ mod กับ c  (ในที่นี้คือ m)

อัลกอริทึม v2

เมื่อ congruent ห่วยที่สุด (ห่วยมากๆ เพราะเวลา 99% ของการทำงานเสียไปกับฟังก์ชันนี้) ผมเลยเปลี่ยนมาใช้วิธีการคูณด้วยส่วนกลับแทน กลายมาเป็นอัลกอริทึม v2 อยู่ที่ HPCThai/IntroHPC/06/b_modular_v2.py  หรือดู online ได้ที่

https://github.com/hpc-thai/HPCThai/blob/master/introHPC/06/b_modular_v2.py

จากนั้นเรามาลองทดสอบความถูกต้องและหา ฺB ค่าน้อยๆ และ จับเวลา B(30) ดูครับ โดยพิมพ์ใน ipython3 ดังนี้

b30_mod_v2

จาก B(26) ของ v1 ใช้เวลา 8395.74s แต่แก้แค่ฟังก์ชันเดียวความเร็วเพิ่มขึ้นมามหาศาล ใช้เวลาเหลือ 23ms คำตอบก็ยังคงถูกต้องนะครับ ไม่มีปัญหาแต่อย่างใด คราวนี้ผมข้ามไปเลย ไปเทียบชั้นกับ Recursive v3 ดูว่าจะเป็นอย่างไร โดยใช้หา B(300) เหมือนกัน จะได้

b300_mod_v2

Recursive v3 ใช้เวลา 17.6s ซึ่งอัลกอริทึมทนี้ใช้เพียง 5.48s ซึ่งเร็วกว่าพอสมควร คราวนี้ B(1000) ไปเลยครับ

b1000_mod_v2

ไม่เลวเลยนะครับ จาก 19:33m เหลือเพียง 1:45m เนื้อหาที่แสดงให้ท่านเห็น เพื่อตอกย้ำถึงความสำคัญที่ต้องให้กับอัลกอริทึมครับ การปรับปรุงอัลกอริทึมสำคัญกว่าการปรับปรุง hardware  อัลกอริทึม v2 นี้มันแค่พอใช้เท่านั้นนะครับ ยังสามารถปรับแต่งในส่วนของอัลกอริทึมได้อีกมากเลย ความเร็วยังเพิ่มได้อีกมาก ยิ่งถ้าทำาการ cache ยิ่งเป็นเสือติดปีก แต่ผมเอาพอสังเขปครับ เอาแค่นี้พอ ไม่ได้จะเอาไปแข่งกับเข้า ขอเอาอัลกอริทึมนี้เป็นฐานในการปรับเป็นอัลกอริทึมสำหรับการประมวลผลแบบขนานต่อไป

เปลี่ยนมาใช้ C++

เมื่อพอใจกับ python ก็มาถึง C++ ผมทำ source code เอาไว้ทั้ง 2 รุ่นเลยครับ ในรุ่นแรกคือ HPCThai/introHPC/06/bern_mod_v1.cpp และรุ่นที่สองคือ HPCThai/introHPC/06/bern_mod_v2.cpp รุ่นแรกนั้นใช้ congruent แบบเดิมซึ่งตรงกับรุ่นแรกของ python ทั้งสองโปรแกรมดูนี้หาได้จาก

bern_mod_v1.cpp
bern_mod_v2.cpp

การคอมไพล์เราย้ายตำแหน่ง directory ปัจจุบันไปที่ HPCThai/introHPC/06 เสียก่อนแล้วใช้คำสั่งดังนี้ครับ

ทดลองรันโปรแกรมรุ่นแรก ให้หา B(22) พิมพ์ดังนี้ครับ

คำสั่ง time นั้นเป็นคำสั่งของ UNIX ที่จับเวลาในการประมวลผลคำสั่งที่ต่อท้าย ผมไม่อยากเขียนตัวจับเวลาในโปรแกรมก็ใช้วิธีนี้ครับ ง่ายดี อย่าไปพิมพ์อย่างนี้บน Windows นะครับ เพราะคำสั่ง time ของ Windows เป็นการตั้งเวลาใหม่ ถ้าอยากใช้เหมือนกับ UNIX แบบนี้ ให้ไป download ptime มาใช้ที่  http://www.pc-tools.net/win32/ptime/

ผลลัพธ์จากการจับเวลา B(22) บน banana pi ปรากฏว่า ใช้เวลา 13.45s เทียบกับ B(22) ของ python ที่ผมทดลองใหม่ ใช้เวลา 29.5s ซึ่งเร็วขึ้นกว่า 2 เท่า ถือว่าใช้ได้ครับ คราวนี้เราลองดูว่า ถ้าเป็น g++ ของ GNU แล้วเราจะทำ profiler เพื่อหาฟังก์ชันที่เป็นปัญหาซึ่งก็คือ congruent เจอหรือไม่ วิธีการคือ เราต้องคอมไพล์โปรแกรมใหม่ครับโดย เพิ่ม -pg เข้าไป คือบอกคอมไพเลอร์ว่าเราต้องการแทรก instrumentation เข้าไปในโปรแกรม จากนั้นก็รันโปรแกรมตามปกติครับ พิมพ์อย่างนี้ครับ

ระหว่างการรันโปรแกรมตัว Instrumentation จะทำงานสะสมค่าเวลาต่างๆ เมื่อรันโปรแกรมเสร็จ มันจะสร้างแฟ้มที่ชื่อว่า gmon.out ออกมา ข้างในเป็นผลลัพธ์ทั้งหมด เราเปิดดูอ่านไม่ได้ครับ ต้องเอามาสร้างเป็นรายงานโดยพิมพ์

ได้เป็นรายงานออกมาแล้วครับ เปิดแฟ้ม report.txt อ่านได้เลย ดังนี้

gprof1

 

ผมตัดมาเฉพาะส่วนหัวนะครับ ส่วนที่เหลือไม่ได้นำมาแสดงนั้นเป็นคำอธิบายครับ ถ้าใครอ่านไม่รู้เรื่องเพราะบรรทัดมันตีกันไปหมด แสดงว่า editor ตัวนั้นมันปัดส่วนที่อยู่ด้านขวาที่เกินจอลงมาเป็นบรรทัดใหม่ ซึ่งเราต้องไปกำหนดค่าไม่ให้มัน “wrap” ครับ ถ้าเป็น vi ให้ใช้ :set nowrap จะได้ผลลัพธ์ดังข้างบน จากรายงานนี้มันเรียงตามลำดับฟังก์ชันที่กินกำลังเครื่องเลยครับ เราไม่ต้องไปค้นหาเอง นั่นคือ เจอแล้วครับ congurent บรรทัดแรกเลยกินเวลาไป 100% อย่างหนักครับ ผมก็เลยเปลี่ยน congruent เป็นแบบใช้ส่วนกลับ จึงได้มาเป็นรุ่นที่สอง เราคงไม่เล่นกันที่ B(22) นะครับ ข้ามไป B(1000) เลย ได้ผลลัพธ์ดังนี้ครับ

b1000_mod_cpp_v2

ใช้เวลา 49.532s เทียบกับ Python ใช้เวลา 1:45m ก็นับได้ว่า C++ เร็วกว่าประมาณ 2 เท่า ซึ่งถือว่าใช้ได้ ท่านอาจจะสงสัยว่าทำไม python ถึงเร็วนักเมื่อเทียบกับ C++ ซึ่ง C++ น่าจะเร็วกว่าสัก 10 เท่าเป็นอย่างน้อย เรื่องนี้เข้าใจไม่ยากครับ ก็ Python ก็ใช้ GMP library เหมือนกันครับ และโปรแกรมนี้งานเกือบทั้งหมดอยู่ที่การประมวลผลตัวเลขขนาดใหญ่ ซึ่ง GMP รับงานไป ดังนั้น C++ และ python จึงไม่ต่างกันมากครับ

มาถึงการบ้านที่ค้างคาในบทก่อน ทำไมอัลกอริทึม Recursive  C++ ถึงช้ากว่า Python ได้ ไม่น่าเชื่อเลย ถ้าท่านยังไม่ทราบ ท่านลองเอาแนวคิดของ profiler ที่เรียนรู้ในบทนี้ลองเอาไปทดสอบดูครับ แล้วท่านจะเห็นว่าจริงๆ แล้วปัญหาอยู่ที่ไหน ผมคงไม่เฉลยไปมากกว่านี้ครับ ท่านทำเองได้โดยไม่ยาก

มีประเด็นหนึ่งครับที่อยากจะเสริมก่อนจากคือ โปรแกรมภาษา C++ ที่ผมเขียนนั้นหาบั๊กค่อนข้างยากครับ ปัญหาเกิดจากตัวแปรพื้นฐานชนิด long ซึ่งมีขนาดจำกัด และงานนี้ จำเป็นต้องใช้ตัวเลขที่เกินขอบเขตของ long ไปมากครับ ซึ่งแน่นอนครับว่าใช้เราใช้ GMP แต่ครั้นที่จะใช้ชนิดตัวแปรใน GMP ทั้งหมด ประสิทธิภาพมันก็ไม่ได้ ดังนั้นจึงต้องผสมกับชนิด int/long ตัวแปรพื้นฐานเหล่านี้เมื่อล้นแล้วก็ไม่เกิด error ครับ แค่ค่าวนกลับทำให้หาบั๊กยากมาก โชคดีที่ผมทำรุ่น python เอาไว้ก่อน จากนั้นไล่ค่าตัวแปรเทียบกัน ถ้ารันแล้วแสดงค่าคนละค่าแสดงว่าเกิดการวนกลับแล้วครับ ถึงหาข้อผิดพลาดเจอได้โดยไม่ยากนัก ถ้าเขียน C++ ตั้งแต่แรกโดยไม่มี python ท่าจะเหนื่อยกว่านี้อีกหลายเท่าครับ

ก่อนจาก

ในบทความนี้ ผมได้นำเสนออัลกอริทึมที่มีประสิทธิภาพสูงในการหาค่า Bernoulli Number รองรับการประมวลผลแบบขนาน ถือว่าตั้งไข่เสร็จแล้วนะครับ นับจากนี้เป็นต้นไปจนหมดบทความชุดนี้ ผมจะใช้อัลกอริทึมตัวนี้มาหลอกหลอนท่าน ทั้ง python และ C++ ครับ

แล้วพบกันไปในบทความหน้า

[Total: 4    Average: 3.3/5]

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *