ก้าวแรก HPC #07: เตรียมเสบียงเลี้ยงตัว สู่โลกแห่งการประมวลผลแบบขนาน
เกริ่นนำ
ผมเริ่มเขียนบทความเรื่อง Apache Spark ปรากฏว่ามันเริ่มบวมใหญ่ เลยตัดสินใจแยกเนื้อหาที่ไม่เข้าพวกที่ต้องเกริ่นนำเป็นพื้นฐานออกมาเป็นบทความอีกบทความหนึ่ง กลายเป็นสะพานเชื่อมจากโลกการประมวลผลแบบเดี่ยวมาสู่การประมวลผลแบบขนานได้ ระหว่างการเขียนบทความนี้ก็บวมใหญ่อีก ผมเลยตัดเนื้อหาในส่วนที่ซับซ้อนไปไว้ในบทความชุดใหม่ “ก้าวสอง” ทั้งนี้เพื่อให้บทความชุดก้าวแรกนี้ยังคงง่ายสบายๆ นั่นเอง ดังนั้นบทความนี้จึงเหลือเท่าที่เห็น ไม่ง่ายและไม่ยากจนเกินไปนัก
ในบทความนี้ผมขอเน้นการวิเคราะห์โปรแกรมที่เราเขียนกันผ่านมา พิจารณาดูว่าโปรแกรมส่วนไหนควรปรับให้เป็นการประมวลผลแบบขนานและมีข้อควรระวังอะไรบ้าง เรามาเริ่มกันเลยครับ
**หมายเหตุ ในบทความนี้ผมใช้คำว่า “ตัวประมวลผล” แทนคำว่าคอร์ เพราะความหมายมันกว้างกว่า แต่ถ้าท่านคุ้นเคยกับกับว่าคอร์ก็ให้ทราบว่าเป็นเรื่องเดียวกัน
Dr. Gene Amdahl ผู้นิยามขอบเขตการประมวลผลแบบขนาน
ธรรมชาติการประมวลผลแบบขนานนั้น ในชั่วอายุของการทำงานของโปรแกรมนั้นไม่ใช่ว่าจะสามารถประมวลผลแบบขนานได้ตลอดเวลา บางเวลาโดยเฉพาะอย่างยิ่งตอนเริ่มและการสิ้นสุดการทำงานนั้นจะเป็นการประมวลผลแบบเดี่ยว เพื่อให้เห็นภาพผมเลยวาดให้ดูดังนี้
จากภาพจะเห็นได้ชัดเจนครับ การเริ่มทำงานนั้น จะเริ่มที่ตัวประมวลผลเดี่ยว จะนั้นเมื่อก็จะเปลี่ยนไปเป็นการทำงานแบบขนานในบางเวลา สลับกับการทำงานแบบเดี่ยวไปเรื่อยๆ จนจบการทำงานที่ตัวประมวลผลเดี่ยว เวลาที่ใช้ในการทำงานของตัวประมวลผลเดี่ยวนั้นคงที่ครับไม่เปลี่ยนแปลง แต่การประมวลผลในส่วนของขนานนั้น เวลาที่ใช้จะแปรผันจำนวนตัวประมวลผลแบบขนานที่เพิ่มเข้ามาในระบบ โดยทางทฤษฎีแล้วเรายิ่งเพิ่มหน่วยประมวลผลเข้าสู่ระบบการทำงานยิ่งเร็วขึ้น ดังภาพครับ
จากภาพเราจะเห็นว่าในส่วนที่เป็นสีชมพูด้านซ้ายและขวาทำงานด้วยเวลาคงที่ครับ ผิดกับสีน้ำเงินที่ยิ่งมีตัวประมวลผลมากยิ่งใช้เวลาลดลง เพื่อความสะดวกในการวิเคราะห์ ผมจึงเปลี่ยนจากการมองมิติเวลาจากค่าตัวเลขมาเป็นเปอร์เซ็นต์เปรียบเทียบ การทำเช่นนี้ต้องคิดที่ระบบทั้งหมดเป็นระบบที่ใช้ตัวประมวลผลเดี่ยว ยกตัวอย่างเช่น การใช้ตัวประมวลผลของโปรแกรมหนึ่ง 80% เป็นแบบตัวประมวลผลเดี่ยว อีก 20% สามารถใช้ตัวประมวลผลแบบขนานได้ ดังภาพ
เพื่อให้คำนวณง่าย ผมให้เป็น 5ถ้าเรากำหนดตัวแปร P เป็นอัตราเวลาที่สามารถประมวลผลแบบขนานได้ ในที่นี้คือ 50% หรือคะแนนเต็ม 1 ก็ได้ 0.5 นั่นเอง ส่วนเวลาที่ต้องประมวลผลแบบเดี่ยวนั้นก็ไม่จำเป็นต้องสร้างตัวแปรใหม่ให้วุ่นวายก็คือส่วนที่เหลือทั้งหมด มีค่าเท่ากับ (1 – P) นั่นเอง ในอีกมุมมองหนึ่ง เวลาทั้งหมดที่ใช้ในการประมวลผลรวมทั้งตัวประมวลเดี่ยวและขนานเป็น 1 หน่วย ถ้าเราลดเวลาในการทำงานเหลือครึ่งหนึ่ง นั่นคือเหลือ 0.5 คำถามคือระบบนี้เร็วขึ้นกี่เท่า ตอบได้ทันทีเลยใช่ไหมครับ ก็เร็วขึ้นสองเท่าอย่างแน่นอน ดังนั้น การแปลงจาก 0.5 ให้กลายเป็น 2 ได้นั้น ก็คือการเอา ไปหารด้วยหนึ่งครับ 1/1 ได้ 1 และ 1/0.5 ได้ 2 นั่นเอง ดังนั้นเราสามารถตั้งสมการอย่างได้ว่า
S คือความเร็วที่เร็วขึ้นหน่วยเป็นจำนวนเท่า เช่นถ้า 2 ก็คือเร็วขึ้นเป็น 2 เท่านั้นเอง สมการนี้ถ้ายุบรูปแล้วจะเห็นว่ากลายเป็น 1/1 ก็คือเร็วเท่าเดิมตลอดเวลา ไม่ต้องแปลกใจครับ ก็สำหรับตัวประมวลผลเดี่ยวไงครับ ไม่ว่าแยกส่วนการประมวลผลออกเป็นแบบเดี่ยวแบบขนาน แต่ความสามารถของตัวประมวลผลมีเพียงหน่วยเดียว มันก็ไม่เร็วขึ้นหรือช้าลงครับ ถือว่าเป็นฐานเวลานั้นเอง แต่ถ้าเรามีตัวประมวลผลแบบขนาน N ตัว เราจะปรับโปรแกรมตรงไหนครับ แน่นอนครับ เราต้องลดค่า P ลง โดยการนำมันไปหาร N นั่นเอง ส่วน (1 – P) นั้นมันก็คงเดิมเปลี่ยนไม่ได้ ผลลัพธ์ได้ดังนี้ครับ
สมการนี้เองครับคิดค้นโดย Gene Amdahl ผู้เพิ่งฉลองครบรอบอายุ 92 ปี เมื่ออาทิตย์ที่แล้ว (วันหวยออก พ.ย. 57) รู้จักกันดีในชื่อว่า “กฏของแอมดาล” (Amdahl’s law) ซึ่งกำเนิดขึ้นจากบทความในปี 1967 เรื่อง Validity of the single processor approach to achieving large scale computing capabilities การเรียนเรื่องการประมวลผลแบบขนานต้องเรียนกฏนี้เปรียบเหมือนกับเป็น Hello, World ครับ กฏนี้บอกอะไรให้เรารู้ครับ เรามาลองวิเคราะห์เล่นๆ กัน สมมติตามตัวอย่างข้างบนเลยครับ โปรแกรมของเราสามารถประมวลผลโดยใช้ตัวประมวลผลเดี่ยวใช้เวลา 1 วัน โปรแกรมนี้มีส่วนเวลาที่สามารถประมวลผลแบบขนานได้ครึ่งหนึ่งและอีกครึ่งต้องใช้ตัวประมวลผลเดี่ยว ถามว่า ถ้าผมมีโอกาสใช้เครื่องเทียนเหอ-2 ที่เป็น Supercomputer ที่เร็วที่สุดในโลก ณ วันที่ผมเขียนบทความนี้ เป็นเครื่องที่มีหน่วยประมวลผลหลายล้านตัว โปรแกรมของผมจะใช้เวลาเหลือเท่าไหร่ เพื่อหาคำตอบผมก็เลยแทนค่าลงไปในสมการได้ดังนี้ครับ
ผมจำไม่ได้แล้วว่าเทียนเหอ-2 ของจีนนั้นมีตัวประมวลผลกี่ตัว ผมว่าเยอะเลยแทนค่าเป็นอนันต์ไปเลย เมื่ออนันต์ใช้เป็นตัวหาร มันก็เลยฉุดให้พจน์ P/N เป็น 0 หมายความว่าเวลาที่ใช้ในส่วนของการประมวลผลแบบขนานเป็น 0 หมายความว่าเร็วจนไม่กินเวลาเลยนั่นเอง แต่พจน์ (1-P) อย่างไรก็ไม่มีใครไปแต่ต้องมันได้ มันจึงยังคงอยู่และทำให้ได้ผลลัพธ์ 1/(0.5) ซึ่งก็คือ 2 เท่านั่นเอง น่าตกใจไหมครับ โปรแกรมที่ครึ่งหนึ่งทำงานแบบขนานได้ อีกครึ่งหนึ่งต้องเป็นแบบเดี่ยวนั้น ต่อให้ใช้เครื่องที่เร็วที่สุดในโลกก็สามารถลดการทำงานจาก 1 วันเหลือได้เพียงแค่ครึ่งวันเท่านั้น ผมถึงบอกไงว่า อัลกอริทึมนั่นสำคัญกว่า Hardware เราต้องเพิ่มค่า P ในโปรแกรมของเราให้ได้ ค่า P ยิ่งดี การทำงานยิ่งเร็ว
ต่อไปครับ ถ้าผมสามารถตัดส่วนของการทำงานตัวประมวลผลเดี่ยวให้กลายเป็นศูนย์ (ในโลกความเป็นจริงคงเป็นไปไม่ได้) เหลือเพียงส่วนการประมวลผลแบบขนาน 1 / (P/N) ทำให้อยู่ในรูปอย่างง่ายโดยการพลิกกลับจะได้ N/P และ P เป็น 1 ดังนั้นจำนวนเท่าที่ได้ขึ้นอยู่กับ N เช่น N = 5 ก็จะได้ความเร็วเป็น 5 เท่า ตามที่ฝันอยากให้เป็น แต่มันเร็วจริงหรือ ลองคิดในมุมนี้ดูครับ สมมติว่าเรามีงานชิ้นหนึ่งใช้เวลาทำงาน 100 วันบนตัวประมวลผลเดี่ยว ถ้าเราเพิ่มตัวประมวลผลอีกตัวจะทำให้วันลดลงครึ่งหนึ่ง เหลือเพียง 50 วัน ซึ่งเราก็พอใจ แต่มาถึงวันหนึ่งเมื่อเราอยากให้มันเร็วขึ้นอีกเท่าหนึ่งจากเดิม 50 วัน ให้เหลือ 25 วัน เราเพิ่มหน่วยประมวลผลเพียงตัวเดียวไม่ได้แล้วครับ ต้องเพิ่มอีกสองตัว จากสองต้องเป็นสี่ ทุกๆ เท่าที่ได้มา ต้องเพิ่มหน่วยประมวลผลอีกเป็นเท่าตัวเช่นเดียวกัน ด้วยตรรกะนี้ ถ้าปัจจุบัน เราใช้หน่วยประมวลผล 1,000 ตัว ทำงานเสร็จใช้เวลา 1 วัน ถ้าอยากให้เหลือครึ่งวัน ต้องเพิ่มอีกหน่วยประมวลผลอีกเท่าหนึ่งคือ 1,000 ตัวครับ เริ่มมองเห็นพาราด๊อกซ์ตัวนี้หรือยังครับ
ค่าที่ได้จากกฏของแอมดาลกับในโลกของความเป็นจริงมันต่างกันนะครับ เป็นไปได้ยากมากที่เมื่อเราจับเวลาทำงานแล้วผลลัพธ์ใกล้เคียงกับค่าที่ได้จากสูตร ทั้งนี้เพราะในการประมวลผลแบบขนานนั้นต้องเสียเวลาพอสมควร ตั้งแต่การติดต่อเริ่มต้น กันแลกเปลี่ยนข้อมูลต่างๆ เป็นต้น ดังนั้นกฏของแอมดาลนี้จึงใช้สำหรับนิยามผลลัพธ์ในกรณีอุดมคติที่ดีที่สุดเท่านั้น ซึ่งก็ทำให้เรารู้ว่าขอบเขตประสิทธิภาพสูงสุดนั้นมันอยู่ตรงไหน
กฏของอู๋
ในบทความต่อๆ ไปเราจะเรียนรู้ถึง framework ในการประมวลผลแบบขนานหลายตัว ซึ่งผมอยากจะวัดประสิทธิภาพว่าวิธีไหนเร็วกว่ากัน ซึ่งความเร็วนั้นแปรผันตามจำนวนหน่วยประมวลผลอีกต่างหาก กฏของแอมดาลไม่สามารถตอบโจทย์นี้ได้ ผมเลยคิดสมการเพื่อประเมินประสิทธิภาพขึ้นมาเอง (อาจซ้ำเพราะมีคนเคยคิดมาก่อนแล้ว แต่ด้วยความอ่อนด้อยของผมเองทำให้ผมไม่รู้จัก) ผมตั้งชื่อมันว่า กฏของอู๋ (ไม่ต้องถามผมนะครับว่าอู๋คืออะไร ผมไม่บอกท่านหรอก)
กำหนดให้
คือเวลาที่ใช้ในการประมวลผลทั้งหมดเมื่อใช้ตัวประมวลผลเดี่ยว
คือเวลาที่ใช้การประมวลผลทั้งหมดเมื่อใช้งานตัวประมวลผล N ตัว
ทั้งสองค่าได้มาจากการจับเวลาจริงทั้งคู่ครับ เรานิยากฏของอู๋นิยามได้โดย
ที่มาที่ไปดูได้จากกระดานดำเลยครับ
ดูที่มาของตารางก่อนครับ ตามกฏของแอมดาลแล้ว จากเวลา ถ้าเราเพิ่มหน่วยประมวลผล N ตัวเข้าไป เวลาที่ดีที่สุดที่ลดได้จะเหลือ
ถ้าเมื่อจับเวลาจริงแล้วได้ตามนี้ถือว่า 100% ผมจึงกำหนดให้เป็น 1 กรณีที่แย่มาก คือใส่ตัวประมวลผลไป N ตัวแต่เมื่อจับเวลาแล้วได้เวลาเท่ากับตัวประมวลผลตัวเดียว แบบนี้ผมกำหนดให้ได้ 0% แต่ถ้าเกินนี้ก็ติดลบแล้วครับ ซึ่งหมายความว่าแย่สุดๆ อย่าใช้เลยครับตัวประมวลหลายตัว เพราะทำเวลาได้แย่กว่าตัวประมวลผลเดี่ยวเสียอีก ข้อมูลนี้วาดเป็นกราฟได้ตามบนกระดานดำครับ
คือค่าจริงที่เราจับเวลาเมื่อใช้ตัวประมวลผลหลายตัว ซึ่งเป็นจุดใดจุดหนึ่งบนแกน X ที่อยู่ตั้งแต่
ขึ้นไป สิ่งที่เราต้องการก็คือเราต้องหาค่าที่ตัดกับแกน Y ตามความสัมพันธ์แบบเส้นตรงตามเส้นสีฟ้านั่นเอง ผมเลือกใช้สมการ Interpolation ดังสมการสีชมพู แทนค่าตรงๆ ก็จะได้สมการเส้นสีฟ้าครับ และเมื่อจัดรูปใหม่แล้วจะเหลือ
นี่แหละครับกฎของอู๋ ถ้าใครใล่ตามที่มาที่ผมอธิบายก็คงเข้าใจว่ากฏนี้คำนวณหาค่าอะไร แต่ถ้ายังไม่ทราบผมอธิบายอย่างนี้ครับ กฏข้อนี้เอาไว้วัดศักยภาพในการประมวลผลแบบขนานของทั้ง Framework และโปรแกรมที่เราเขียนเองครับ เมื่อใส่ค่าสามค่าตามพารามิเตอร์เสร็จเรียบร้อยแล้ว สมมติว่า Framework A ได้ค่า 0.8 ส่วน Framework B นั้นได้ค่า 0.7 อู๋นั้นทำให้เราใช้ฐานเดียวกันในการเปรียบเทียบ แม้ว่าจำนวนหน่วยประมวลผลจะไม่เท่ากันก็ตาม จากตัวอย่างนั้นบอกได้อย่างชัดเจนว่า Framework A ที่มีค่าอู๋สูงกว่านั้น มีศักยภาพในการประมวลผลแบบขนานสูงกว่านั่นเอง
กลับมาที่อัลกอริทึมการหา Bernoulli Number ของ Dr. Harvey
จากทฤษฎีมาสู่การปฏิบัติบ้าง ผมอยากหาค่า P ของโปรแกรม Bernoulli Number ที่ใช้อัลกอริทึมของ Dr. Harvey ซึ่งเป็นที่ทราบกันว่าอัลกอริทึมของ Dr. Harvey นั้นจุดเด่นก็คือการการกระจายงานออกไปให้แก่ตัวประมวลผลทุกตัวเท่าที่มีได้ ว่าแต่ว่าส่วนไหนของโปรแกรมหละที่สามารถกระจายออกได้ ลองดูส่วนของโปรแกรมข้างล่างครับ
226 227 228 229 230 231 232 233 234 235 236 237 |
long X = p; mpz_class M {1}; p = 2; vector <tuple<mpz_class, long>> rp; while (p <= X) { if (k % (p-1) != 0) { rp.push_back(make_tuple(computeBkModP(p, k), p)); M *= p; } p = primeTable.nextPrime(p); } |
ผมเปลี่ยนมาใช้ C++ บ้าง เพราะในบทความที่ผ่านมาเน้นแต่ Python เปลี่ยนเป็น C+ บ้างจะได้มีทางเลือกครับ ส่วนของโปรแกรมที่เห็นนี้อยู่ในฟังก์ชัน B() ซึ่งเป็นฟังก์ชันหลักในการคำนวณนั่นเอง ผมตัดมาจากบทความก่อนหน้า HPCThai/introHPC/06/bern_mod_v2.cpp อัลกอริทึมนี้โดยรวมอาจจะซับซ้อน แต่ส่วนที่ตัดออกมาให้ท่านดูนั้น เข้าใจไม่ยากลองไล่ตามดู ลองพิจารณาการวนรอบจากส่วนของโปรแกรมข้างต้นดู แต่ละรอบจะได้จำนวนเฉพาะใหม่ๆ (ค่า p) ไล่ขึ้นมาตั้งแต่ 2, 3, 5, 7, 11, … แต่ก็ไม่ใช่ค่าจำนวนเฉพาะทุกตัวสามารถนำเอาไปใช้งานได้ ต้องผ่านเงื่อนไข k หารด้วย (p – 1) ต้องไม่ลงตัวเท่านั้น จากนั้นจึงนำค่า p ไปคำนวณค่า computeBkModP(p, k) คำนวณเสร็จ ก็เก็บผลลัพธ์ลงใน vector
สิ่งที่เห็นชัดก็คือการเรียกใช้ฟังก์ชัน computeBkModP(p, k) นั้น ค่า k คือค่าโจทย์ตัวเลข Bernoulli ที่เราต้องการหา (กรณีนี้คือ 1,000) การหา computeBkModP(2, 1000) และ computeBkModP(3, 1000) หรือ ค่า p ใดๆ นั้นสามารถหาค่าได้พร้อมกันเพราะอิสระต่อกัน ดังนั้นจึงเหมาะอย่างยิ่งที่นำมาประมวลผลแบบขนาน ส่วนของโปรแกรมนี้ยังไม่ดีครับ เพราะค่า p นั้นคำนวณใหม่ทุกครั้งเมื่อเรียก computeBkModP(p, k) การหาค่า p นั้นเป็นส่วนของการประมวลผลเดี่ยวครับ ผมจึงปรับเอาการหาค่า p รวบยอดที่เดียวก่อน แล้วเอาค่า p ทั้งหมดที่ใช้งานบรรจุลงบน Queue จากนั้นใช้ Queue เป็นตัวแจกงาน สร้างเป็นการวนรอบแจกงาน ดังนี้ครับ
229 230 231 232 233 234 235 236 237 238 239 240 241 242 |
long X = p; mpz_class M {1}; p = 2; primeList_t primeList; while (p <= X) { if (k % (p-1) != 0) { primeList.push_back(p); M *= p; } p = primeTable.nextPrime(p); } auto rp = distribute(k, primeList); |
จะสังเกตว่าผมสร้างฟังก์ชัน distribute() ขึ้นมา เพื่อคำนวณค่า computeBkModP(p, k) โดยเฉพาะ ในอนาคตเมื่อเราเรียนรู้การเขียนโปรแกรมแบบขนาน เราจะแก้แค่ฟังก์ชันนี้เพียงฟังก์ชันเดียวเท่านั้นครับ เนื้อหาของฟังก์ชัน distribute() มีรายละเอียดดังนี้ครับ
188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 |
<a href="/features" class="py-2 lh-condensed-ultra d-block link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Features">Features <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a> <ul class="list-style-none f5 pb-3"> <li class="edge-item-fix"><a href="/features/code-review/" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Code review">Code review</a></li> <li class="edge-item-fix"><a href="/features/project-management/" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Project management">Project management</a></li> <li class="edge-item-fix"><a href="/features/integrations" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Integrations">Integrations</a></li> <li class="edge-item-fix"><a href="/features/actions" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Actions">Actions</a></li> <li class="edge-item-fix"><a href="/features/packages" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to GitHub Packages">Packages</a></li> <li class="edge-item-fix"><a href="/features/security" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Security">Security</a></li> <li class="edge-item-fix"><a href="/features#team-management" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Team management">Team management</a></li> <li class="edge-item-fix"><a href="/features#hosting" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Code hosting">Hosting</a></li> <li class="edge-item-fix hide-xl"><a href="/mobile" class="py-2 lh-condensed-ultra d-block link-gray no-underline f5" data-ga-click="(Logged out) Header, go to Mobile">Mobile</a></li> </ul> <ul class="list-style-none mb-0 border-lg-top pt-lg-3"> <li class="edge-item-fix"><a href="/customer-stories" class="py-2 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Customer stories">Customer stories <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li> <li class="edge-item-fix"><a href="/security" class="py-2 lh-condensed-ultra d-block no-underline link-gray-dark no-underline h5 Bump-link--hover" data-ga-click="(Logged out) Header, go to Security">Security <span class="Bump-link-symbol float-right text-normal text-gray-light">→</span></a></li> </ul> |
กลับมาเนื้องานของเรา ถ้าผมจับเวลาทั้งหมดบรรทัดแรกของ main() คร่อมไปปิดบรรทัดสุดท้าย จับเวลาได้เท่าไหร่ก็ตาม มันก็คือเวลาทั้งหมด หรือ 1 ตามกฏของแอมดาล และถ้าผมจับเวลาเฉพาะส่วนการวนรอบ computeBkModP(p, k) ก็คือการคร่อมการทำงานภายใน distribute() นั่นเอง โปรแกรมเต็มดูได้จาก HPCThai/introHPC/07/bern_amdahl.cpp
ถ้าเราจับเวลาคร่อมภายใน distribute() เราจะคำนวณได้ค่า P ตามกฏของแอมดาล แต่การที่จะได้ค่า P นั้น จะต้อเทียบกับเวลาที่ใช้ทั้งโปรแกรม ซึ่งประกอบด้วยส่วนประมวลผลแบบขนานคือฟังก์ชัน distribute และส่วนประมวลผลเดี่ยวคือที่เหลือทั้งหมด ถ้าผมจับเวลาที่ main() บรรทัดแรกคร่อมถึงบรรทัดสุดท้าย ผมจะได้เวลารวมทั้งหมด เอาไปลองรันดูก่อนครับ ได้ผลลัพธ์ดังนี้
โปรแกรมนี้ทำงานบน Banana Pi ตรวจคำตอบแล้วถูกต้อง ลอจิกการทำงานไม่ผิดเพี้ยน ถือว่าผ่าน สิ่งที่เราสนใจก็คือเวลาที่ใช้ บรรทัดล่างสุด ผมจับเวลาคร่อม main() ทั้งหมด ได้ 48,852 msecs หรือ เกือบๆ 49 วินาที นั่นคือเวลาทั้งหมดตามกฏของแอมดาลหรือ 1 นั่นเอง ส่วนเวลาที่ใช้ในการประมวลผลแบบขนานได้ทั้งหมดอยู่ข้างบนครับนั่นคือ 48,542 msecs เมื่อเทียบเป็นอัตราก็จะได้ 48,542/48,852 หรือ 0.993654 ซึ่งก็คือค่า P ตามกฏของแอมดาลนั่นเอง อาจกล่าวว่า เวลาที่ใช้ส่วนใหญ่คือมากกว่า 99% นั้นอยู่ในส่วนที่ประมวลผลแบบขนานได้ โปรแกรมลักษณะนี้คุ้มครับที่จะประมวลผลแบบขนาน
เมื่อได้ค่า P มาแล้ว เราลองมาเอาเข้ากฏเต็มรูปดูครับ จะได้
เมื่อ N คือจำนวนตัวประมวลผล ผมลองปั่นจำนวนหน่วยประมวลผลจาก 1 ไปถึง 10 ดูว่าผลตอบสนองเป็นอย่างไร จะเร็วขึ้นได้กี่เท่า เรามาทดลองกันดีกว่าครับ วันนี้ผมขอแนะนำโปรแกรมเพิ่มอีกตัวหนึ่งครับ ถือได้ว่าเป็นสนามเด็กเล่นของชาว HPC เลยครับ นั่นก็คือ ipython notebook ครับ ไม่พูดพล่ามทำเพลง ไปที่ shell ไม่ว่าจะเป็น windows หรือ linux ก็ได้ พิมพ์คำว่าเลยครับ
1 |
ipython notebook --pylab inline |
โปรแกรมจะเปิดหน้าเว็ปขึ้นมา เหมือนกับ sagemath.org เราก็เลือก ‘new notebook’ จากนั้นก็พิมพ์โปรแกรมนี้ตามเลยครับ
1 2 3 4 5 6 |
def amdahl(N): return 1/( (1-0.993654) + 0.993654/N) N = numpy.arange(1, 11) plot(N, amdahl(N), 'r-') grid() |
จากนั้นกดปุ่มรัน จะได้ผลลัพธ์ตามนี้ครับ
โปรแกรมที่เขียนอาจจะดูแปลกไปเล็กน้อย เพราะไม่ได้อ้างถึง matplotlib เลย ผมใช้ pylab ครับเป็น library ที่ขี่อยู่บน matplotlib อีกที ลักษณะคล้ายๆ MATLAB ครับ ใครมาทางสาย MATLAB จะคุ้นเคยครับ เรามาดูกราฟกัน ในแกน X คือจำนวนหน่วยประมวลผลที่เพิ่มขึ้น ส่วนแกน Y เป็นผลตอบสนองเป็นจำนวนเท่าที่ทำงานเร็วขึ้นหรือ S นั่นเอง เห็นอะไรไหมครับ อัลกอริทึมของเราดีมาก แทบจะตอบสนองกันเป็นเส้นตรง เพิ่มตัวประมวลผลหนึ่งตัวความเร็วเพิ่มขึ้นอีกหนึ่งเท่า
เดี๋ยวก่อนครับ โลกมันไม่ได้สวยงามขนาดนั้นครับ สมมติว่าผมไปใช้ Supercomputer ขนาดกลางๆ มีตัวประมวลผล 10,000 ตัว มันจะเร็วขึ้นอีกแค่ไหน ท่านลองเปลี่ยนตัวเลข 11 เป็น 10001 ดูครับ แล้วกดรันใหม่ จะได้ผลลัพธ์ทันทีเลย REPL แบบ graphics ตัวนี้ยอดเยี่ยมมาก ฟรีอีกต่างหาก ผลลัพธ์ชวนอึ้ง ดังนี้ครับ
ผลลัพธ์ชวนอึ้งไหมครับ ใส่ตัวประมวลผลเข้าไป 10,000 ตัว แต่ผลตอบสนองกับได้แค่ไม่ถึง 160 เท่า อย่าไปตกใจหรือแปลกใจครับ มันเป็นกฏธรรมชาติเข้าใจได้โดยไม่ยากครับ ตัวเลขอย่างนี้เพราะโจทย์ของเราเป็นโจทย์ง่ายครับ หา B(1000) ใช้เวลาประมาณหนึ่งนาที จะให้ใส่ตัวประมวลผลไป 10,000 ตัวแล้วกระพริบตาให้เสร็จเลย มันก็คงไม่ใช่ครับ แต่ถ้าหา B(2000) ค่า P จะสูงกว่านี้พอสมควรครับ ค่ายิ่งสูงยิ่งทำให้กราฟถดถอยช้าลง
ขอย้ำอีกทีนะครับ ตัวเลขที่หานั้นเป็นแค่เชิงทฤษฎีเท่านั้น ในทางปฏิบัติตัวเลขที่ได้แย่กว่านี้อีกมากครับ
จับความเร็ว computeBkModP(p, k)
ผมขอพักเรื่องทางทฤษฎีของแอมดาลเอาไว้ก่อนครับ เรามาดูปฏิบัติของจริงกันบ้าง จะได้เห็นโลกอีกมุม จากข้างต้น ผมแสดงให้ท่านเห็นแล้วว่า computeBkModP(p, k) นั้นสามารถประมวลผลแบบขนานได้ ผมลองใช้ตัวแปรสะสมค่าดู พบว่า มีค่า p อยู่ 568 จำนวนที่ต้องคำนวณ คำถามก็คือถ้าผมมีหน่วยประมวลผล 568 ตัว ส่งฟังก์ชันดังกล่าวขึ้นไปทำงาน คำถามก็คือใช้เวลาเท่าไหร่จึงจะเสร็จ คำตอบที่ท่านตอบจะก่อให้เกิดคำถามใหม่ ท่านคงตอบว่า ความเร็วที่ได้ขึ้นอยู่กับว่าตัวประมวลผลตัวไหนทำงานช้าที่สุด ตัวหน่วยประมวลผลที่ทำงานเสร็จแล้วก็ได้ไปพัก ที่ไม่เสร็จก็ต้องทำต่อไป ถ้าท่านพูดอย่างนี้ก็แสดงว่า ความเร็วที่ได้ก็จะเท่ากับเวลาที่ใช้ไปของตัวประมวลผลตัวที่ช้าที่สุด ในเมื่อตัวประมวลผลที่มีทุกตัวสเปคเดียวกันหมด จึงเร็วช้าก็ไม่น่าต่างกันมากนัก ถ้าอย่างนั้น แสดงว่าเวลาที่ใช้ในการประมวลผลในแต่ละค่าของ p ไม่เท่ากันใช่หรือไม่
ผมจะตอบคำถามนี้ด้วยการเขียนโปรแกรมครับ คือเอาโปรแกรมเดิมมาแก้ คราวนี้ผมจับเวลาที่ใช้ในการเรียกฟังก์ชันแต่ละครั้งกันเลย และเพื่อให้เห็นภาพผมจะนำผลมาแสดงเป็นกราฟ ซึ่งยังคงไว้ซึ่งจุดยืนครับคือใช้ภาษา C++ ถ้าเป็น Python ก็คงไม่กระไรนักเพราะเราคุ้นเคยกับ Matplotlib อยู่แล้ว แต่ใน Standard Library ของ C++ ไม่มีเรื่อง Graphics ครับ ต้องใช้ Library ภายนอก ตัวทำกราฟที่นิยมที่สุดของภาษาตระกูล C ก็คือ gnuplot ความสามารถสูสีกับ Matplotlib แถมยังรองรับภาษาคอมพิวเตอร์ได้หลากหลายกว่าครับ ที่พูดมาทั้งหมดนี้ ผมไม่ใช้ครับ เพราะมันจะทำเว็ปนี้ที่มันบวมอยู่แล้วมันจะบวมขึ้นอีก ผมจะใช้ Matplotlib ครับ
ภาษา Python กับภาษาตระกูล C นั้นมีความสัมพันธ์กันค่อนข้างแนบแน่น เราสามารถใช้ Python มาเรียก library ภาษา C ได้และในทางกลับกัน เราสามารถเขียนภาษา Python ภายในภาษา C ก็ยังได้ ถ้านึกตามไม่ออกว่ามันเป็นแบบไหน ก็ให้นึกถึงการเขียนภาษา SQL ในรูปแบบของ string ภายในภาษาที่เป็น host อื่น อารมณ์เดียวกันเลยครับ
เราต้องใช้ library ที่ชื่อว่า libpython สำหรับ *buntu แล้วเราติดตั้งได้โดย
1 |
sudo apt-get install libpython3.4-dev |
แต่ถ้าเป็น Windows และใช้ Anaconda ไม่ต้องทำอะไรครับ มีให้มาในตัวเสร็จเรียบร้อยแล้ว เวลาต้องการใช้เราต้อง #include ในโปรแกรมภาษาตระกูล C เพิ่มดังนี้ครับ
1 |
#include <Python.h> |
สังเกตนะครับว่า P เป็นตัวอักษรใหญ่ คราวนี้มาดูตัวโปรแกรมกันครับ ผมเขียนใหม่แยกเป็นอีกแฟ้มหนึ่งเลยตั้งชื่อว่า HPCThai/introHPC/07/bern_tgraph.cpp ผมขอแสดงเฉพาะส่วนของการจับเวลาและสะสมค่าเวลา นั่นก็คือฟังก์ชัน distribute() นั่นเอง ดังนี้
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 |
auto distribute(long k, primeList_t primeList) -> vector<crt_t> { vector<crt_t> rp; stringstream ssP, ssTime; ssP << "p = ["; ssTime << "time = ["; cout << "Prime Queue Size = " << primeList.size() << endl; while (!primeList.empty()) { long pp = primeList.front(); primeList.pop_front(); auto p_stime = chrono::high_resolution_clock::now(); crt_t tt = make_tuple(computeBkModP(pp,k), pp); auto p_etime = chrono::high_resolution_clock::now(); ssP << pp << ", "; ssTime << chrono::duration_cast<chrono::milliseconds>(p_etime - p_stime).count() << ", "; rp.push_back(tt); } ssP << "]"; ssTime << "]"; genGraph(ssP.str(), ssTime.str()); return rp; } |
จะเห็นได้ว่าผมจับเวลาคร่อมบรรทัดที่ 223 เอาไว้ ผลลัพธ์ที่ได้คือค่า p และ time ซึ่งเป็นเวลาที่จับได้หน่วยเป็น msecs นั้นเอาไปต่อเป็น string ชื่อ ssP และ ssTime โดยใช้ stringstream ถ้าดูกันให้ดีแล้วจะเห็นว่า ใน string ทั้งสองเป็นการสร้างตัวแปรของ Python ชื่อ p และ time นั่นเอง และข้อมูลที่เอาไปต่อก็จะเป็น list แบบธรรมดา
เมื่อสะสมข้อมูลเสร็จเรียบร้อยแล้ว ผมก็เรียกฟังก์ชัน genGraph() ซึ่งนิยามมีดังนี้ครับ
190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
auto genGraph(std::string strP, std::string strTime) -> void { Py_Initialize(); PyRun_SimpleString("import matplotlib"); PyRun_SimpleString("matplotlib.use('Agg')"); PyRun_SimpleString("import matplotlib.pyplot as plt"); PyRun_SimpleString(strP.c_str()); PyRun_SimpleString(strTime.c_str()); PyRun_SimpleString("plt.plot(p, time, 'g*-')"); PyRun_SimpleString("plt.title('Elapsed Time for each P')"); PyRun_SimpleString("plt.xlabel('P')"); PyRun_SimpleString("plt.ylabel('Time used (msecs)')"); PyRun_SimpleString("plt.grid()"); PyRun_SimpleString("plt.savefig('tgraph.png')"); Py_Finalize(); cout << "Generated tgraph.png" << endl; } |
ผมเลือกที่ใช้งานให้ง่ายที่สุด โดยทำ string ให้สำเร็จเรียบร้อยแล้วป้อนเข้าไปสู่ PyRun_SimpleString() โดยที่ก่อนใช้งานนั้นก็ใช้ Py_Initialize() และปิดท้ายด้วย Py_Finalize() ภายในผมเรียกเอา matplotlib มาสร้างกราฟครับ ผลลัพธ์เป็นแฟ้มชื่อว่า tgraph.png
ก่อนรันต้องคอมไพล์โปรแกรมก่อนครับ อาจดูยุ่งยากเล็กน้อย ถ้าเป็น *buntu ใช้คำสั่งนี้ครับ
1 |
g++ -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython3.4m -I /usr/include/python3.4 |
แต่ถ้าเป็น Windows ให้ใช้
1 |
g++ -Wall -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython34 -Ic:\mingw\include -Ic:\python\include -Lc:\mingw\lib -Lc:\python\libs |
เมื่อรันโปรแกรม
1 |
./bern_tgraph 1000 |
จะได้ผลลัพธ์เป็นกราฟ tgraph.png ดังนี้
ผลลัพธ์ที่ได้น่าสนใจมากครับ พบว่ามีฐานเป็นเส้นตรงที่เฉียงขึ้นเรื่อยๆ แต่ก็มีบางค่าใช้เวลามากกระโดดขึ้นไปเลย สิ่งที่ตอบคำถามได้อย่างชัดเจนก็คือแต่ละ p ใช้เวลาไม่เท่ากันและมีแนวโน้มว่าค่า p ยิ่งมากขึ้นยิ่งมีฐานที่สูงขึ้น โอกาสที่กระโดดสูงขึ้นก็มีมากกว่า ทำให้ใช้เวลามากกว่า ดังนั้นจากคำถามว่าถ้าเรามีตัวประมวลผล 568 ตัวเท่ากับจำนวน p นั้น งานจะเสร็จเร็วแค่ไหน บอกได้เลยว่า ใครเสร็จก่อนก็รอตัวเปล่าครับ ถ้า p ที่ประมาณ 3,000 ยังไม่เสร็จงานนี้ก็ไม่จบไปกระบวนการต่อไปไม่ได้ ซึ่ง p ที่ประมาณ 3,000 ใช้เวลาถึง 550msecs
ในชีวิตจริงเราคงไม่ได้มีหน่วยประมวลผลได้มากถึง 568 ตัวหรอกครับ ผมมี Banana Pi อยู่ 3 บอร์ดหรือ 6 cores ผมเอาตัวเลข 6 ตรงนี้มาใช้ก็แล้วกัน 568/6 ได้ประมาณ 95 หมายความว่าผมแบ่งให้แต่ละคอร์ประมวลผลค่า p 95 ค่าหรือเรียกฟังก์ชัน computeBkModP(p, k) 95 ครั้งนั่นเอง ถ้าผมแบ่งแบบง่ายๆ อย่างเช่น 95 ค่าแรก ใช้คอร์แรกและ 95 ค่าต่อไปใช้คอร์ถัดไป แบ่งแบบนี้ไปจนครบ แบบนี้จะทำงานได้เร็วไหม
เดาไม่ยากใช่ไหมครับคอร์สุดท้ายทำงานหนักสุดๆ ผิดกับคอร์แรกเสร็จก่อนแล้วนั่งเฉย วิธีนี้เป็นวิธีที่ไม่มีประสิทธิภาพอย่างแรงครับ โจทย์จะยิ่งยากกว่านี้ถ้าเราเพิ่มตัวแปรเข้าไปอีกก็คือ ความเร็วในการประมวลผลแต่ละคอร์ไม่เท่ากัน ดังนั้นจึงมีศาสตร์แยกออกเป็นแขนงหนึ่งเลยครับว่าด้วยการจัด Schduling ทำอย่างไรให้เครื่องจักรที่เรามีนั้นสามารถทำงานได้มีประสิทธิภาพสูงสุดตลอดเวลา
ทิ้งท้าย
บทความนี้เราเริ่มจากกฏของแอมดาล ผมใช้มันเป็นฐานในการนิยามกฏของอู๋ ซึ่งจะใช้เพื่อวัดศักภาพของเนื้อหาที่เราจะกล่าวถึงในบทต่อๆ ไป ในบทนี้ผมได้ปูพื้นเกี่ยวกับทฤษฎีการประมวลผลแบบขนานอย่างง่ายให้ท่านได้อ่านกันเพลินๆ แล้ว ในบทต่อไปคงถึงเวลาเสียทีทีที่โปรแกรมเราจะทำงานแบบขนานได้ ไว้ให้ถึงวันนั้นครับ