ก้าวแรก HPC #07: เตรียมเสบียงเลี้ยงตัว สู่โลกแห่งการประมวลผลแบบขนาน

เกริ่นนำ

ผมเริ่มเขียนบทความเรื่อง Apache Spark ปรากฏว่ามันเริ่มบวมใหญ่ เลยตัดสินใจแยกเนื้อหาที่ไม่เข้าพวกที่ต้องเกริ่นนำเป็นพื้นฐานออกมาเป็นบทความอีกบทความหนึ่ง กลายเป็นสะพานเชื่อมจากโลกการประมวลผลแบบเดี่ยวมาสู่การประมวลผลแบบขนานได้ ระหว่างการเขียนบทความนี้ก็บวมใหญ่อีก ผมเลยตัดเนื้อหาในส่วนที่ซับซ้อนไปไว้ในบทความชุดใหม่ “ก้าวสอง” ทั้งนี้เพื่อให้บทความชุดก้าวแรกนี้ยังคงง่ายสบายๆ นั่นเอง ดังนั้นบทความนี้จึงเหลือเท่าที่เห็น ไม่ง่ายและไม่ยากจนเกินไปนัก

ในบทความนี้ผมขอเน้นการวิเคราะห์โปรแกรมที่เราเขียนกันผ่านมา พิจารณาดูว่าโปรแกรมส่วนไหนควรปรับให้เป็นการประมวลผลแบบขนานและมีข้อควรระวังอะไรบ้าง เรามาเริ่มกันเลยครับ

**หมายเหตุ ในบทความนี้ผมใช้คำว่า “ตัวประมวลผล” แทนคำว่าคอร์ เพราะความหมายมันกว้างกว่า แต่ถ้าท่านคุ้นเคยกับกับว่าคอร์ก็ให้ทราบว่าเป็นเรื่องเดียวกัน

Dr. Gene Amdahl ผู้นิยามขอบเขตการประมวลผลแบบขนาน

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

thread1

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

thread2

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

thread3

เพื่อให้คำนวณง่าย ผมให้เป็น 5ถ้าเรากำหนดตัวแปร P เป็นอัตราเวลาที่สามารถประมวลผลแบบขนานได้ ในที่นี้คือ 50%  หรือคะแนนเต็ม 1 ก็ได้ 0.5 นั่นเอง ส่วนเวลาที่ต้องประมวลผลแบบเดี่ยวนั้นก็ไม่จำเป็นต้องสร้างตัวแปรใหม่ให้วุ่นวายก็คือส่วนที่เหลือทั้งหมด มีค่าเท่ากับ (1 – P) นั่นเอง ในอีกมุมมองหนึ่ง เวลาทั้งหมดที่ใช้ในการประมวลผลรวมทั้งตัวประมวลเดี่ยวและขนานเป็น 1 หน่วย ถ้าเราลดเวลาในการทำงานเหลือครึ่งหนึ่ง นั่นคือเหลือ 0.5 คำถามคือระบบนี้เร็วขึ้นกี่เท่า ตอบได้ทันทีเลยใช่ไหมครับ ก็เร็วขึ้นสองเท่าอย่างแน่นอน ดังนั้น การแปลงจาก 0.5 ให้กลายเป็น 2 ได้นั้น ก็คือการเอา ไปหารด้วยหนึ่งครับ   1/1 ได้  1  และ 1/0.5 ได้ 2 นั่นเอง ดังนั้นเราสามารถตั้งสมการอย่างได้ว่า

 S=\frac{1}{(1-P)+P}

S คือความเร็วที่เร็วขึ้นหน่วยเป็นจำนวนเท่า เช่นถ้า 2 ก็คือเร็วขึ้นเป็น 2 เท่านั้นเอง สมการนี้ถ้ายุบรูปแล้วจะเห็นว่ากลายเป็น 1/1 ก็คือเร็วเท่าเดิมตลอดเวลา ไม่ต้องแปลกใจครับ ก็สำหรับตัวประมวลผลเดี่ยวไงครับ ไม่ว่าแยกส่วนการประมวลผลออกเป็นแบบเดี่ยวแบบขนาน แต่ความสามารถของตัวประมวลผลมีเพียงหน่วยเดียว มันก็ไม่เร็วขึ้นหรือช้าลงครับ ถือว่าเป็นฐานเวลานั้นเอง แต่ถ้าเรามีตัวประมวลผลแบบขนาน N ตัว เราจะปรับโปรแกรมตรงไหนครับ แน่นอนครับ เราต้องลดค่า P ลง โดยการนำมันไปหาร N นั่นเอง ส่วน (1 – P) นั้นมันก็คงเดิมเปลี่ยนไม่ได้ ผลลัพธ์ได้ดังนี้ครับ

S(N)=\frac{1}{(1-P)+\frac{P}{N}}

สมการนี้เองครับคิดค้นโดย 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 ที่เร็วที่สุดในโลก ณ วันที่ผมเขียนบทความนี้ เป็นเครื่องที่มีหน่วยประมวลผลหลายล้านตัว โปรแกรมของผมจะใช้เวลาเหลือเท่าไหร่  เพื่อหาคำตอบผมก็เลยแทนค่าลงไปในสมการได้ดังนี้ครับ

S({\infty})=\frac{1}{(1-0.5)+\frac{0.5}{\infty }}

ผมจำไม่ได้แล้วว่าเทียนเหอ-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 ในการประมวลผลแบบขนานหลายตัว ซึ่งผมอยากจะวัดประสิทธิภาพว่าวิธีไหนเร็วกว่ากัน ซึ่งความเร็วนั้นแปรผันตามจำนวนหน่วยประมวลผลอีกต่างหาก กฏของแอมดาลไม่สามารถตอบโจทย์นี้ได้ ผมเลยคิดสมการเพื่อประเมินประสิทธิภาพขึ้นมาเอง (อาจซ้ำเพราะมีคนเคยคิดมาก่อนแล้ว แต่ด้วยความอ่อนด้อยของผมเองทำให้ผมไม่รู้จัก) ผมตั้งชื่อมันว่า กฏของอู๋ (ไม่ต้องถามผมนะครับว่าอู๋คืออะไร ผมไม่บอกท่านหรอก)

กำหนดให้

  • T_{1} คือเวลาที่ใช้ในการประมวลผลทั้งหมดเมื่อใช้ตัวประมวลผลเดี่ยว
  • T_{N} คือเวลาที่ใช้การประมวลผลทั้งหมดเมื่อใช้งานตัวประมวลผล N ตัว

ทั้งสองค่าได้มาจากการจับเวลาจริงทั้งคู่ครับ  เรานิยากฏของอู๋นิยามได้โดย

\frac{N(T_{1}-T_{N})}{T_{1}(N-1)}

ที่มาที่ไปดูได้จากกระดานดำเลยครับ
uh

ดูที่มาของตารางก่อนครับ ตามกฏของแอมดาลแล้ว จากเวลา T_{1} ถ้าเราเพิ่มหน่วยประมวลผล N ตัวเข้าไป เวลาที่ดีที่สุดที่ลดได้จะเหลือ \frac{T_{1}}{N} ถ้าเมื่อจับเวลาจริงแล้วได้ตามนี้ถือว่า 100% ผมจึงกำหนดให้เป็น 1  กรณีที่แย่มาก คือใส่ตัวประมวลผลไป N ตัวแต่เมื่อจับเวลาแล้วได้เวลาเท่ากับตัวประมวลผลตัวเดียว แบบนี้ผมกำหนดให้ได้ 0% แต่ถ้าเกินนี้ก็ติดลบแล้วครับ ซึ่งหมายความว่าแย่สุดๆ อย่าใช้เลยครับตัวประมวลหลายตัว เพราะทำเวลาได้แย่กว่าตัวประมวลผลเดี่ยวเสียอีก ข้อมูลนี้วาดเป็นกราฟได้ตามบนกระดานดำครับ

T_{N} คือค่าจริงที่เราจับเวลาเมื่อใช้ตัวประมวลผลหลายตัว ซึ่งเป็นจุดใดจุดหนึ่งบนแกน X ที่อยู่ตั้งแต่ \frac{T_{1}}{N} ขึ้นไป สิ่งที่เราต้องการก็คือเราต้องหาค่าที่ตัดกับแกน Y ตามความสัมพันธ์แบบเส้นตรงตามเส้นสีฟ้านั่นเอง ผมเลือกใช้สมการ Interpolation ดังสมการสีชมพู แทนค่าตรงๆ ก็จะได้สมการเส้นสีฟ้าครับ และเมื่อจัดรูปใหม่แล้วจะเหลือ

\frac{N(T_{1}-T_{N})}{T_{1}(N-1)}

 นี่แหละครับกฎของอู๋ ถ้าใครใล่ตามที่มาที่ผมอธิบายก็คงเข้าใจว่ากฏนี้คำนวณหาค่าอะไร  แต่ถ้ายังไม่ทราบผมอธิบายอย่างนี้ครับ กฏข้อนี้เอาไว้วัดศักยภาพในการประมวลผลแบบขนานของทั้ง Framework และโปรแกรมที่เราเขียนเองครับ เมื่อใส่ค่าสามค่าตามพารามิเตอร์เสร็จเรียบร้อยแล้ว สมมติว่า Framework A ได้ค่า 0.8 ส่วน Framework B นั้นได้ค่า 0.7 อู๋นั้นทำให้เราใช้ฐานเดียวกันในการเปรียบเทียบ แม้ว่าจำนวนหน่วยประมวลผลจะไม่เท่ากันก็ตาม จากตัวอย่างนั้นบอกได้อย่างชัดเจนว่า Framework A ที่มีค่าอู๋สูงกว่านั้น มีศักยภาพในการประมวลผลแบบขนานสูงกว่านั่นเอง

กลับมาที่อัลกอริทึมการหา Bernoulli Number ของ Dr. Harvey

จากทฤษฎีมาสู่การปฏิบัติบ้าง ผมอยากหาค่า P ของโปรแกรม Bernoulli Number ที่ใช้อัลกอริทึมของ Dr. Harvey ซึ่งเป็นที่ทราบกันว่าอัลกอริทึมของ Dr. Harvey นั้นจุดเด่นก็คือการการกระจายงานออกไปให้แก่ตัวประมวลผลทุกตัวเท่าที่มีได้ ว่าแต่ว่าส่วนไหนของโปรแกรมหละที่สามารถกระจายออกได้ ลองดูส่วนของโปรแกรมข้างล่างครับ


ผมเปลี่ยนมาใช้ 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 เป็นตัวแจกงาน สร้างเป็นการวนรอบแจกงาน ดังนี้ครับ


จะสังเกตว่าผมสร้างฟังก์ชัน distribute() ขึ้นมา เพื่อคำนวณค่า computeBkModP(p, k) โดยเฉพาะ ในอนาคตเมื่อเราเรียนรู้การเขียนโปรแกรมแบบขนาน เราจะแก้แค่ฟังก์ชันนี้เพียงฟังก์ชันเดียวเท่านั้นครับ เนื้อหาของฟังก์ชัน distribute() มีรายละเอียดดังนี้ครับ


 กลับมาเนื้องานของเรา ถ้าผมจับเวลาทั้งหมดบรรทัดแรกของ main() คร่อมไปปิดบรรทัดสุดท้าย จับเวลาได้เท่าไหร่ก็ตาม มันก็คือเวลาทั้งหมด หรือ 1 ตามกฏของแอมดาล และถ้าผมจับเวลาเฉพาะส่วนการวนรอบ computeBkModP(p, k) ก็คือการคร่อมการทำงานภายใน distribute() นั่นเอง โปรแกรมเต็มดูได้จาก HPCThai/introHPC/07/bern_amdahl.cpp

ถ้าเราจับเวลาคร่อมภายใน distribute() เราจะคำนวณได้ค่า P ตามกฏของแอมดาล แต่การที่จะได้ค่า P นั้น จะต้อเทียบกับเวลาที่ใช้ทั้งโปรแกรม ซึ่งประกอบด้วยส่วนประมวลผลแบบขนานคือฟังก์ชัน distribute และส่วนประมวลผลเดี่ยวคือที่เหลือทั้งหมด  ถ้าผมจับเวลาที่ main() บรรทัดแรกคร่อมถึงบรรทัดสุดท้าย ผมจะได้เวลารวมทั้งหมด  เอาไปลองรันดูก่อนครับ ได้ผลลัพธ์ดังนี้

bern_amdahl

โปรแกรมนี้ทำงานบน Banana Pi  ตรวจคำตอบแล้วถูกต้อง ลอจิกการทำงานไม่ผิดเพี้ยน ถือว่าผ่าน สิ่งที่เราสนใจก็คือเวลาที่ใช้ บรรทัดล่างสุด ผมจับเวลาคร่อม main() ทั้งหมด ได้ 48,852 msecs หรือ เกือบๆ 49 วินาที นั่นคือเวลาทั้งหมดตามกฏของแอมดาลหรือ 1 นั่นเอง ส่วนเวลาที่ใช้ในการประมวลผลแบบขนานได้ทั้งหมดอยู่ข้างบนครับนั่นคือ 48,542 msecs  เมื่อเทียบเป็นอัตราก็จะได้ 48,542/48,852 หรือ 0.993654 ซึ่งก็คือค่า P ตามกฏของแอมดาลนั่นเอง อาจกล่าวว่า เวลาที่ใช้ส่วนใหญ่คือมากกว่า 99% นั้นอยู่ในส่วนที่ประมวลผลแบบขนานได้ โปรแกรมลักษณะนี้คุ้มครับที่จะประมวลผลแบบขนาน

เมื่อได้ค่า P มาแล้ว เราลองมาเอาเข้ากฏเต็มรูปดูครับ จะได้

S(N)=\frac{1}{(1-0.993654) + \frac{0.993654}{N}}

เมื่อ N คือจำนวนตัวประมวลผล ผมลองปั่นจำนวนหน่วยประมวลผลจาก 1 ไปถึง 10 ดูว่าผลตอบสนองเป็นอย่างไร จะเร็วขึ้นได้กี่เท่า เรามาทดลองกันดีกว่าครับ วันนี้ผมขอแนะนำโปรแกรมเพิ่มอีกตัวหนึ่งครับ ถือได้ว่าเป็นสนามเด็กเล่นของชาว HPC เลยครับ นั่นก็คือ ipython notebook ครับ ไม่พูดพล่ามทำเพลง ไปที่ shell ไม่ว่าจะเป็น windows หรือ linux ก็ได้ พิมพ์คำว่าเลยครับ

ipython notebook --pylab inline

โปรแกรมจะเปิดหน้าเว็ปขึ้นมา เหมือนกับ sagemath.org เราก็เลือก ‘new notebook’ จากนั้นก็พิมพ์โปรแกรมนี้ตามเลยครับ

def amdahl(N):
    return 1/( (1-0.993654) + 0.993654/N)

N = numpy.arange(1, 11)
plot(N, amdahl(N), 'r-')
grid()

จากนั้นกดปุ่มรัน จะได้ผลลัพธ์ตามนี้ครับ

bern_amdahl_10

โปรแกรมที่เขียนอาจจะดูแปลกไปเล็กน้อย เพราะไม่ได้อ้างถึง matplotlib เลย ผมใช้ pylab ครับเป็น library ที่ขี่อยู่บน matplotlib อีกที ลักษณะคล้ายๆ MATLAB ครับ ใครมาทางสาย MATLAB จะคุ้นเคยครับ เรามาดูกราฟกัน ในแกน X คือจำนวนหน่วยประมวลผลที่เพิ่มขึ้น ส่วนแกน Y เป็นผลตอบสนองเป็นจำนวนเท่าที่ทำงานเร็วขึ้นหรือ S นั่นเอง เห็นอะไรไหมครับ อัลกอริทึมของเราดีมาก แทบจะตอบสนองกันเป็นเส้นตรง เพิ่มตัวประมวลผลหนึ่งตัวความเร็วเพิ่มขึ้นอีกหนึ่งเท่า

เดี๋ยวก่อนครับ โลกมันไม่ได้สวยงามขนาดนั้นครับ  สมมติว่าผมไปใช้ Supercomputer ขนาดกลางๆ มีตัวประมวลผล 10,000 ตัว มันจะเร็วขึ้นอีกแค่ไหน ท่านลองเปลี่ยนตัวเลข 11 เป็น 10001 ดูครับ แล้วกดรันใหม่ จะได้ผลลัพธ์ทันทีเลย REPL แบบ graphics ตัวนี้ยอดเยี่ยมมาก ฟรีอีกต่างหาก ผลลัพธ์ชวนอึ้ง ดังนี้ครับ

bern_amdahl_10000

ผลลัพธ์ชวนอึ้งไหมครับ ใส่ตัวประมวลผลเข้าไป 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 แล้วเราติดตั้งได้โดย

sudo apt-get install libpython3.4-dev

แต่ถ้าเป็น Windows และใช้ Anaconda ไม่ต้องทำอะไรครับ มีให้มาในตัวเสร็จเรียบร้อยแล้ว เวลาต้องการใช้เราต้อง #include ในโปรแกรมภาษาตระกูล C เพิ่มดังนี้ครับ

#include <Python.h>

สังเกตนะครับว่า P เป็นตัวอักษรใหญ่ คราวนี้มาดูตัวโปรแกรมกันครับ ผมเขียนใหม่แยกเป็นอีกแฟ้มหนึ่งเลยตั้งชื่อว่า HPCThai/introHPC/07/bern_tgraph.cpp ผมขอแสดงเฉพาะส่วนของการจับเวลาและสะสมค่าเวลา นั่นก็คือฟังก์ชัน distribute() นั่นเอง ดังนี้


 จะเห็นได้ว่าผมจับเวลาคร่อมบรรทัดที่ 223 เอาไว้ ผลลัพธ์ที่ได้คือค่า p และ time ซึ่งเป็นเวลาที่จับได้หน่วยเป็น msecs นั้นเอาไปต่อเป็น string ชื่อ ssP และ ssTime โดยใช้ stringstream ถ้าดูกันให้ดีแล้วจะเห็นว่า ใน string ทั้งสองเป็นการสร้างตัวแปรของ Python ชื่อ p และ time นั่นเอง และข้อมูลที่เอาไปต่อก็จะเป็น list แบบธรรมดา 

เมื่อสะสมข้อมูลเสร็จเรียบร้อยแล้ว ผมก็เรียกฟังก์ชัน genGraph() ซึ่งนิยามมีดังนี้ครับ


ผมเลือกที่ใช้งานให้ง่ายที่สุด โดยทำ string ให้สำเร็จเรียบร้อยแล้วป้อนเข้าไปสู่ PyRun_SimpleString()  โดยที่ก่อนใช้งานนั้นก็ใช้ Py_Initialize() และปิดท้ายด้วย Py_Finalize()  ภายในผมเรียกเอา matplotlib มาสร้างกราฟครับ ผลลัพธ์เป็นแฟ้มชื่อว่า tgraph.png

ก่อนรันต้องคอมไพล์โปรแกรมก่อนครับ อาจดูยุ่งยากเล็กน้อย ถ้าเป็น *buntu ใช้คำสั่งนี้ครับ

g++ -std=c++11 -O3 -o bern_tgraph bern_tgraph.cpp -lgmpxx -lgmp -lpython3.4m -I /usr/include/python3.4

แต่ถ้าเป็น Windows ให้ใช้

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

เมื่อรันโปรแกรม

./bern_tgraph 1000

จะได้ผลลัพธ์เป็นกราฟ tgraph.png  ดังนี้

tgraph

ผลลัพธ์ที่ได้น่าสนใจมากครับ พบว่ามีฐานเป็นเส้นตรงที่เฉียงขึ้นเรื่อยๆ แต่ก็มีบางค่าใช้เวลามากกระโดดขึ้นไปเลย สิ่งที่ตอบคำถามได้อย่างชัดเจนก็คือแต่ละ 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 ทำอย่างไรให้เครื่องจักรที่เรามีนั้นสามารถทำงานได้มีประสิทธิภาพสูงสุดตลอดเวลา

 

ทิ้งท้าย

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

You may also like...

Leave a Reply

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