Design Pattern Language สำหรับ Parallel computing

[เป็นบทความแปลสรุป ไม่ได้คิดเอง]

บทความนี้เอารายละเอียดเนื้อหามาจากทีมวิจัยของ Berkeley ตอนนี้มีเป็นเว็บแล้ว https://patterns.eecs.berkeley.edu/ อาจจะมีใส่ความคิดเห็นหรือบทวิเคราะห์ส่วนตัวเข้าไปบ้างเท่านั้น ถ้ารุ่นเดอะหน่อย อาจารย์ผมชอบเรียกว่า 13-dwarfs (https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf)เป็นเนื้อหารายละเอียดเกี่ยวกับว่า โปรแกรมที่เราเขียนขึ้นมาเนี่ยมีลักษณะโครงสร้างแบบไหน, ใกล้เคียง model อะไร, สามารถทำงานแบบ parallel ได้อย่างไร, มีลักษณะการสื่อสารหรือการใช้หน่วยความจำยังไง เพื่อให้สามารถเอาโมเดลไปจับกับปัญหาได้ถูกต้อง (มี forums ไว้ discussion ด้วย เข้าไปดูแล้วช๊อก)

สิ่งที่ต้องย้ำอีกที คือมันคือ Parallel design ไม่ใช่ Distributed design ซึ่ง parallel เนี่ยมันมี scope ที่เล็กกว่า เช่น อยู่ในเครื่องเดียวกัน, cluster เดียวกันบลาๆ ดังนั้นไอเดียหลายๆอย่างมันก็เอาไปใช้กับ distributed computing ตรงๆไม่ได้ เช่น SIMD แต่ไอเดียบางอย่างทั้ง parallel กับ distributed ก็เหมือนกัน เช่น MapReduce, ForkJoin, etc.

ผมชอบงานแนวนี้มากเลยนะ ทำไมปัญหาบางอย่างถึง parallel ได้ทำไมบางอย่าง parallel ไม่ได้ คำตอบหลายคนจะออกไปในเชิงยกตัวอย่างของปัญหา serial ที่มี localization กับการใช้งาน memory สูง กับปัญหาที่แบ่งงานได้ชัดเจนมากตระกูล embarrassingly parallel (เช่น Monte Carlo หาค่า PI) มันก็เห็นแหละ แต่แล้วปัญหาอื่นๆตรงกลางระหว่าง 2 อันนี้ละ อะไร parallel ได้เยอะน้อยแค่ไหน ให้อารมณ์คล้ายๆ CAP theorem เลย เห็นแหละว่ามันมี CA, AP, CP แล้วอยู่ดีๆก็มี eventually consistency โผล่มาตรงกลาง 5555 แถมยังมีตัวใหม่เป็น PACELC อีก บทความนี้ยังไม่ได้ไปถึงขั้นตั้งทฤษฎี แต่เป็นความพยายามในการ generalize แบ่งประเภทของงานที่ดี

เริ่มต้นจากมุมมองของทางทีมก่อน งานวิจัยนี้มันออกมาตอบโจทย์ยุคสมัยที่ เขามองว่ากุญแจสำคัญในการเขียนโปรแกรม parallel ที่ดีเนี่ย อยู่ที่ robust (เกลียดคำนี้ มันออกแนว buzzword แปลไม่ถูก 555) software design ซึ่งรวมทั้งโครงสร้างภาพรวมของโปรแกรม และ low-level layer ของ software ที่จัดการกับ concurrency จากนั้นเขาก็อธิบายวนไปมานิดนึง แต่ภาพรวมผมเข้าใจว่า เราควร generalize หรือ reduce problem ไปอยู่ในรูปแบบของ problem ที่เราทราบอยู่แล้วว่าควรเขียนท่าไหน ชีวิตจะง่ายขึ้นเยอะ อารมณ์ประมาณว่า ต่อให้คุณมีระบบ hadoop ถ้าคุณไม่เข้าใจว่าโปรแกรมของคุณมันเป็นปัญหาแบบไหน ดันไปเขียนแบบ serial เครื่องมือก็ช่วยอะไรคุณไม่ได้ ประมาณนั้น เลยสรุปว่าที่ผ่านมาเราเรียนรู้ 2 อย่าง

• Automatic parallelism สามารถช่วยได้แค่บางส่วน เช่น การคาดเดาล่วงหน้า, การดึง data ให้ล่วงหน้า การเรียงลำดับ instruction ให้ใหม่ แต่มันก็ทำได้แค่นั้น ไม่สามารถดู serial algorithm กากๆที่เราเขียน แล้วจัด parallel algorithm ให้เราแบบอัตโนมัติได้ — ผมว่าฟังดูสมเหตุสมผล มันยังเป็นความประหลาดของธรรมชาติอยู่ที่การแก้ปัญหา 1 อย่าง มันดันสามารถเขียนได้หลายแบบ (เช่น sort) และแต่ละแบบอาจจะไม่เหมือนกันเลยก็ได้ บางแบบสามารถ parallel ได้ง่ายกว่า เช่น quick sort หรือ merge sort ถ้าเราเขียน quick sort มันคงมีเครื่องมือบางอย่าง auto-parallel ให้ได้ แต่ถ้าเขียน bubble sort ไปก็น่าจะไม่รอด
• New languages มีภาษาใหม่ๆเกิดขึ้นมากมาย มีการทำ high level abstraction ต่างๆให้เขียน parallel ได้ง่ายขึ้น แต่สุดท้ายก็ไม่เห็นจะโตขึ้นเท่าไรเลย openMP และ MPI ก็ยังครองตลาดอยู่ ดังนั้นไม่มีแนวโน้มที่เราควรจะเชื่อว่าภาษาใหม่คือคำตอบ — อันนี้ผมเห็นด้วยครึ่งนึงละกัน จากการศึกษาในช่วงปี 2010 มันออกมาในแนวนี้จริงๆ แต่สำหรับปีหลังๆ ช่วง 2020 แล้วเนี่ย มันมีงานใหม่ๆเกิดขึ้นเยอะ เช่น ตระกูล ML ด้วย ดังนั้นงานวิจัยด้านระบบใหม่ภาษาใหม่ที่ทำให้เขียนง่ายกว่ามันก็เกิดขึ้นมาเยอะขึ้น ลองอ่านอันนี้เพิ่มเติมได้ https://www.dursi.ca/post/hpc-is-dying-and-mpi-is-killing-it (ผมก็ไม่ใช่ผู้เชี่ยวชาญ MPI จะมาฟังธงอะไร แต่ในฐานะโปรแกรมเมอร์เนี่ย ถ้าโปรแกรม abstraction ดีเขียนง่าย มันดีกว่างม assembly หรือ c เองอยู่แล้วอะ)

โอเคจะเห็นด้วยหรือไม่ก็ตามแต่ แต่สิ่งเหล่านี้เป็นสาเหตุสำคัญที่ทีมวิจัย berkeley มองว่าการแก้ปัญหา parallel เนี่ยต้องเริ่มจากความเข้าใจ software architecture พื้นฐานของมันก่อน จากนั้นถึงค่อยตามมาด้วยการเลือกเครื่องมือและระบบที่เหมาะสมไปประมวลผลอีกที ซึ่งเป็นก็เป็นกระบวนการออกแบบ software ที่ดี

software architecture ก็ไม่ใช่การระบุอันเดียวแล้วจบ แต่จริงๆมันเป็นชั้นๆ hierarchical ทีมวิจัยเขาเลยร่างแบบออกมาเป็นชั้นๆเช่นกัน แต่คนที่นำไปใช้ ไม่จำเป็นต้อง top-down หรือ bottom-up สามารถเลือกจุดที่เหมาะสมกับตัวเองได้เลย

Pattern ของทางทีม berkeley แบ่งออกมาเป็น 5 ส่วนด้วยกัน โดย 2 ตัวบนสำหรับการเขียนโปรแกรม ส่วนสามตัวล่างสำหรับการออกแบบระบบ

1. Structural patterns อธิบายการทำงานภาพรวมของโปรแกรมว่ามีลักษณะการทำงานอย่างไร อธิบายความสัมพันธ์ของสิ่งต่างๆ ถ้าให้พูดภาษาคนมันคือ “boxes and arrows” ชี้ไปชี้มา ให้ vertex เป็นอะไร เส้นเป็นอะไร หรือจริงๆมองเป็น layer ไปเลย อะไรทำอะไรกับอะไร ประมาณนั้น
2. Computational patterns เป็นการอธิบายตัวการประมวลผลเลย มันคือ 13 dwarfs นั่นแหละ ดูว่าการประมวลผลมีลักษณะอย่างไร มีการสื่อสารอย่างไร มากกว่าแค่การมองโครงสร้าง อาจสามารถเอาไปจับกับ library สำหรับแก้ปัญหาได้ทันที
3. Concurrent Algorithm strategies เป็นการอธิบายชั้นสูงว่าระบบจะทำงานแบบขนานท่าไหนได้บ้าง เช่น ทุกคนถือ data ไว้คนละก้อน แล้วรับงานเหมือนกันหมดไปทำอะไรสักอย่างกับ data ก้อนนี้ เรียกว่า data parallelism จะเห็นว่าไม่ได้ระบุถึงว่าปัญหาคืออะไรเลย เป็นเพียงการอธิบายวิธีทำงานแบบขนานของระบบเท่านั้น
4. Implementation strategies เป็นแบบแผนของโค้ดในระดับการเขียนโปรแกรม parallel เพื่อให้การจัดการของโปรแกรมและ data structure มีความเหมาะสม
5. Parallel execution patterns คือรูปแบบการเขียนโปรแกรมให้มันทำงานแบบ parallel ได้ แบ่งเป็นสองส่วน คือ ส่วนการควบคุมโปรเซสการประมวลผล กับส่วนการสื่อสาร

ส่วนชั้นบนสุด (ข้อ 1 และ 2) มันมีลูกศรชี้ไปมา เพราะสองข้อนี้มีความสัมพันธ์กันอย่างแนบแน่นอยู่ ผู้ใช้งานอาจเลือกใช้ตัวใดตัวหนึ่งก่อนพิจารณาอีกตัว หรือเลือกแล้วพบว่าต้องกลับไปพิจารณาอีกตัวใหม่ วนไปมาจนกว่าจะพอใจได้เช่นกัน

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

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

ดังนั้นคำถาม Map Reduce และ Fork/Join ต่างกันยังไง มันคล้ายกันโคตรๆ เพราะทั้งหมดนี้มันเชื่อมโยงกับปัญหาเดียวกัน แค่อยู่คนละ layer หรือเป็นการมองคนละแบบครับ ส่วน Monte Carlo ที่มักจะเป็นตัวอย่างใช้ท่า Fork/Join บ่อยๆ มันเป็นอัลกอริทึมการประมวลผลเลย
- Map Reduce — โครงสร้างของการคำนวณแบบขนาน
- Fork/Join — pattern การ implement
- Monte Carlo — algorithm pattern (random sample) ที่ใช้ Fork/Join ได้เหมือน Map Reduce

ก่อนจะไปดูตัวอย่างการเอาไปจับกับงานจริง มาดูคำอธิบายของแต่ละตัวในแต่ละ layer กันแบบสั้นๆก่อน แต่ละ layer จะมี goal กับ output ประกอบเพื่อให้เข้าใจได้ง่ายขึ้น (ง่ายแล้วเรอะ!!?)

คำอธิบายของ Pattern แต่ละ Layer

Structural patterns

Goal: อธิบาย structure ภาพใหญ่ของโปรแกรม
Output: ได้ high-level design ของโปรแกรมแบบไม่เป็นทางการ (คิดว่าเป็นกล่องและเส้น หรือการออกแบบแบบวาดบนกระดาน)

• Pipe-and-filter เป็นการมองรูปแบบการคำนวณ โดยให้การประมวลผลเป็นจุด (filters) ส่วนการสื่อสาร data เป็นเส้นระหว่างจุด (pipes) ภาพรวมของระบบจะเป็น data flow ผ่านการประมวลผลต่าง ๆ แบ่งแหล่งอ้างอิงเรียกรูปแบบนี้ว่า producer consumer
• Agent and Repository รองรับการประมวลผลและการจัดการกับ data ที่มีลักษณะไม่ชัดเจน ยืดยุ่นได้กับงานหลากหลายประเภท จึงมีตัว repository คอย schedule ให้ agent เข้ามาประมวลผลอย่าง consistent
• Process control สำหรับปัญหาที่จำเป็นต้องมี process คอย control and monitor อยู่ตลอดเวลาจนกว่าจะทำงานเสร็จ เช่น อุปกรณ์หรือเครื่องวัดค่าต่าง ๆ
• Event-based implicit invocation เป็นโครงสร้างที่มี medium สำหรับเก็บ event โดย process ที่ประมวณผล parallel อยู่สามารถดึง event ขึ้นมาตอบสนอง หรือแจ้ง event กลับเข้าไปใน medium นี้ได้
• Model-view-controller เป็นการแบ่งการทำงานภาพรวมของโปรแกรมออกมาเป็นสามส่วน คือ ส่วนโมเดลสำหรับรักษา persistent ของ program state, ส่วน controller สำหรับ update state และส่วน agent สำหรับ view model
• Iterative refinement งานเป็นประเภทโครงสร้างเป็นลักษณะ iterative จนกว่าจะได้คำตอบ ซึ่งอาจจะมีจำนวนที่ชัดเจนหรือไม่ก็ได้ โดยมีตัว check if (termination condition) เพื่อตัดสินใจว่าควรจะจบ iteration หรือควรไปต่อ
• Map Reduce เป็นโครงสร้างของกลุ่มของงานที่สามารถถูกแบ่งออกได้เป็นสอง phase ส่วนแรกคือการนำชุดคำสั่งเดียวกันกระจายออกไปประมวลผลตามกลุ่ม data ที่แตกต่างกัน จากนั้นส่วนสองคือการนำผลลัพธ์สุดท้ายมา aggregate รวม
• Layered systems เป็นโครงสร้างของ problem ที่มีการ evolve โดยที่ระบบแบ่งเป็นชั้นๆ โดยแต่ละชั้นจะมี complexity มากกว่าชั้นก่อนหน้า การแบ่งชั้น คือการแบ่งหน้าที่กันชัดเจน (separation of concerns) โครงสร้างนี้มีเงื่อนไขสองอย่าง 1. interact ได้เฉพาะ layer ที่อยู่ติดกันเท่านั้น และ 2. จึงจำเป็นต้องทราบเฉพาะ interfaces ของ layer ข้างเคียง (มัน iterative refinement ตรงไหน? ผมก็ไม่ทราบเหมือนกัน)
• Puppeteer เป็นโครงสร้างทีมีกลุ่ม agents คอยรับงานที่สามารถ complex และ dynamic ได้ แต่ละ agents ก็สามารถมี communication กันได้เพื่อทำงานร่วมกันได้ โครงสร้างนี้สามารถมีตัวกลาง เช่น manager สำหรับประสานงาน agents ทุกตัว (อารมณ์จัดการเรื่อง lock/sync/shared ไรงี้มั้ง)
• Arbitrary static task graph หมายถึงโครงสร้างกราฟที่ไม่มีการเปลี่ยนแปลงขณะประมวลผล เป็นโครงสร้างสุดท้ายสำหรับกรณีที่ไม่รู้จะ software ไป map กับ pattern ไหนอีก วิธีการคือการแตกโปรแกรมใหญ่ออกเป็นกลุ่มคำสั่งย่อยๆ (vertex) และกลุ่มคำสั่งย่อยแต่ละตัวมีสัมพันธ์ข้ามกัน, สื่อสารกัน, หรือส่งผลลัพธ์ให้กันด้วยเส้น (edge) ส่วนคำสั่งย่อยควรย่อยขนาดไหน ต้นทางไม่ได้เขียน แต่มันก็คือ คำสั่งย่อยที่ภายในกลุ่มมี data dependency ภายในสูง (locality) ถ้าแบ่งอีกจะฉิบหายเรื่องเส้น จึงไม่ควรแบ่งแล้ว ประมาณนี้ ตัวอย่างของงานที่ใช้โครงสร้างนี้ ได้แก่ การเรียงลำดับแบบขนาน (parallel quick sort), การคูณเมตริกซ์ที่มากเลขศูนย์ (sparse matrix multiplication) เป็นต้น

(ต้นทางมันจัดให้ Map Reduce, Layered, Puppeteer กับ Task Graph เป็นส่วนย่อยของ Iterative Refinement แต่ผมมั่นใจว่ามัน indent ผิดแน่ๆ ถถถ)

Computational patterns

Goal: อธิบายการประมวลผลโดย component ต่าง ๆ ทำให้เกิดเป็นโปรแกรม
Output: ได้ชนิดของการประมวลผล ในบางครั้งมีคำสั่ง library ให้ด้วย
(ผมคงไม่ลงรายละเอียดทุกตัว เพราะย้าวยาว)

• Backtrack, branch and bound
• Circuits สำหรับงานที่มี operation เป็น boolean op และมี input เป็น boolean หรือ bit-vector จะให้โครงสร้างเป็น combinational circuit และ memory element (เช่น flip-flop) ในกรณีที่ต้องใช้ persistent state
• Dynamic programming
• Dense linear algebra เป็นปัญหาในรูปของ linear operation สำหรับ matrices และ vectors โดยที่ค่าส่วนใหญ่ไม่เป็นศูนย์ มี well-defined pattern สำหรับการประมวลผลและ data access ที่หาได้จากคณิตศาสตร์ เพื่อให้ dataสามารถ pre-fetched และให้ความสามารถของการประมวลผลเข้าใกล้ความเป็นไปได้สูงสุดในทางทฤษฎี (ส่วนตัว: โหดสัสครับ) มี standard building block ชัดเจนอยู่แล้ว เช่น Level 1 BLAS (Basic Linear Algebra Subprograms) สำหรับ scalar, vector และ vector-vector operations และมี level อื่น ๆ สำหรับการคูณ vectors/matrices ต่าง ๆ
• Sparse Linear Algebra เป็นปัญหาในรูปของ linear operation เช่นกัน แต่ค่าส่วนใหญ่ใน matrices และ vectors มีค่าเป็นศูนย์ solution ของปัญหาในกลุ่มนี้มีหลากหลายมาก ตัวอย่างเช่น ถ้า matrices ค่าส่วนใหญ่เป็นศูนย์
  ตัวอย่างของหนึ่งใน solution ที่เป็นไปได้ — แทนที่จะเก็บ datastruct ของ matrix 2d เป็น row-col ปกติ ให้เก็บแต่ละ row มีค่า list ของ tuple[index,val] เช่น แทนที่จะเก็บว่า [0,0,0,0,0,0,3,7] ก็จะเหลือแค่ [(6,3), (7,7)] ก็จะประหยัดเนื้อที่ศูนย์ไปได้เยอะมาก พอจะคูณ ก็ iterate แค่เฉพาะ tuple นี้ (เพราะค่าที่เป็นศูนย์คูณไปก็ได้ศูนย์) ก็จะสามารถ solve ได้อย่างรวดเร็ว (โอ๊วววว)
• Finite state machine
• Graph algorithms กลุ่ม algorithm ที่ต้องแก้ปัญหาด้วยการสร้างกราฟด้วย vertices และ edges จากนั้น apply graph traversal หรือ graph partition ที่เหมาะสม
• Graphical models — (อันนี้ผมอ่อนจริงๆ เอา original ไป) graphs of random variables, where the edges represent correlations between variables. Typical problems include inferring probability distributions over a set of hidden states, given observations on a set of observed states observed states, or estimating the most likely state of a set of hidden states, given observations.
• Monte Carlo เป็น algorithm ที่ใช้ random samples จำนวนมากในการทำความเข้าใจหรือหาคำตอบสุดท้าย
• N-body คือ ปัญหาที่แต่ละ node ในระบบ depends กับ node อื่น ๆ ทั้งหมดในระบบ ถ้าวิธีแก้ปัญหาแบบโง่ที่สุดก็เป็น O(N²) คือไล่แต่ละ node และในแต่ละ node หาผลกระทบจาก node อื่นๆทุก node อีกที แต่ปัญหานี้มีวิธีการแก้แบบจัดกลุ่มของ node แล้วคำนวณแบบ approximate ซึ่งเร็วกว่า
• Spectral methods (wiki เขียนอธิบายดีกว่ามาก ขอหยิบมาแทน) เป็นกลุ่มของเทคนิคสำหรับใช้ในคณิตศาสตร์และวิทยาศาสตร์ในการแก้ differential equations บางตัว โดยมีไอเดียคือการเปลี่ยนวิธีการเขียน representation ใหม่ เช่น การเปลี่ยนเป็น frequency basis ใน Fourier Series
• Structured mesh เป็นปัญหาที่ระบบประกอบไปด้วยกลุ่มของจุดที่ประกอบกันขึ้นเป็น mesh แต่ละจุดจะ dependent กับจุดข้างเคียง (neighbor) สำหรับ structured mesh แต่ละจุดจะโดนผูกกับ geography ของ domain วิธีการแก้ปัญหามีสองแบบ หนึ่งคือ การวนลูปแต่ละจุด โดยแต่ละจุดจะพิจารณาจุดโดยรอบมันอีกที (explicit) หรือ แบบสองคือ แก้ปัญหาด้วย linear system of equations (implicit)
• Unstructured mesh คล้าย structured mesh แต่ต่างกันที่แต่ละจุดในระบบ จะไม่โดนบังคับว่าต้องผูกกับ geography ของ domain วิธีแก้จะคล้ายกับ structured mesh แต่ในกรณีของ sparse ก็มีวิธีอื่นในการแก้ด้วย

ผมเห็นว่า computational pattern ทั้งหมดนี้เป็นชุดของงานในกลุ่ม scientific and math computation จ๋ามากๆ ส่วนถ้า general computing ทั่วไปน่าจะเลือกใช้ structural pattern มากกว่า

Algorithm Strategy patterns

Goal: เป็น pattern ชั้นสูง (high-level strategy) สำหรับ parallel algorithm ที่จะนำไปใช้ในการ implement computational pattern (เป็นระบบ base สำหรับให้ algorithm บนเรียกใช้)
Output: ได้ตัวเลือกของ concurrency ที่จะนำมาใช้งาน

• Task Parallelism เป็นลักษณะของปัญหาที่มีกลุ่มของงาน และแก้ปัญหาด้วยการ มี schedule สำหรับกระจายงานไปทำแต่ละเครื่องให้ balance และคอย manage dependencies ของแต่ละงานให้คำตอบออกมาถูกต้อง Embarrassingly Parallel เป็น subset ของกลุ่มนี้ในกรณีที่ไม่มี dependency เลย
  ตัวอย่างที่ง่ายที่สุดคือ if CPU=="A": do A() else if CPU=="B": do B()
• Data parallelism เป็นการ partition data ให้ไปอยู่ในแต่ละ node (หรือ CPU, GPU, etc.) แล้วมีการสั่ง operation ให้ไปทำงานพร้อมๆกันแบบ parallel
• Pipeline (คือ pipelining ที่เรียนกันใน com sys arch เลย) เป็นปัญหาที่มี data กับ transformation ค่อยๆทะยอยเข้ามา สามารถทำ concurrency ได้ด้วยการจัดการให้ลักษณะออกมาแนว assembly-line (data X ต้องทำ op A,B,C ในขณะที่ทำ op B อยู่ ก็ให้ data Y มาทำ op A ต่อได้เลย ไม่ต้องรอให้ X เสร็จ op C)
• Discrete event เป็นลักษณะของปัญหาที่มีกลุ่มของงานที่ loosely connected (สื่อสารกันน้อย) แต่ยังมีลำดับอยู่ (sequence) จึงแก้ด้วยการมี event handler และให้งานแต่ละตัวมัน interact ผ่าน event handler ตัวนี้แทน ลักษณะนี้มักพบใน GUI application (ถ้าผมเข้าใจไม่ผิด มันคือ event loop ในหลายๆภาษานั่นแหละ)
• Speculation (เดา if และคำนวณล่วงหน้า แบบที่เรียนใน com sys arch) สำหรับงานที่ควรจะแบ่งกันคำนวณได้ แต่มี unpredicatable dependency คาเอาไว้อยู่ วิธีแก้ก็ให้คำนวณล่วงหน้าไปก่อนแล้วจะใช้ไม่ใช้ก็ดูอีกที ปัญหานี้ประกอบด้วยหัวใจหลักสองส่วน 1. ต้องมี condition สำหรับตรวจสอบว่าตัวที่ compute ไปแล้วจะ commit หรือไม่ commit 2. มีขั้นตอนการ revert หรือ compute ใหม่ในกรณีที่ speculate ผิดพลาด
• Recursive splitting สำหรับงานที่อยู่ในรูปของ recursion แต่มีเงื่อนไขว่าจะ parallelize ได้เนี่ย ปัญหาของงานนี้ต้องสามารถแตก recursion ออกเป็นงานย่อยมากกว่า 1 งานในแต่ละ call (ถ้า dependency แบบ 1:1 มันก็คงเป็น serial อะนะ) ส่วนไอเดียการแก้ปัญหาอื่นๆ คือ 2. การใช้ balanced tree 3. ใช้ fork/join หรือ task-queue จากนั้น 4. optimize locality
• Geometric decomposition เป็นการทำงานกับข้อมูลที่สามารถแบ่ง partition แล้วแต่ละส่วนอาจจะ overlap กันได้ การ partition จะทำให้คำนวณแบบ parallel กันได้ แต่ data ที่ขอบ (boundary) ในแต่ละ partition อาจจะยังมี dependency กับขอบที่อยู่ใน partition อื่นๆ เลยต้องมีการ communication และ solve ตรงนี้ด้วย

Implementation strategy patterns

Goal: ตรงตามชื่อเลยครับ ใช้ตอน implement แบ่งออกเป็น program structure patterns กับ data structure patterns
Output: ได้เป็น pseudocode

Program structure:

• Single-Program Multiple Data (SPMD) เป็นแนวทางที่ใช้วิธี เขียนโปรแกรมขึ้นมาหนึ่งชุด กระจายโปรแกรมไปตาม thread/proc/machine ต่างๆ แล้วส่ง data ไปทำงาน ดีตรงจัดการง่าย เขียนโปรแกรมชุดเดียวพอ (Basic MPI ที่สอนในห้อง น่าจะเป็นตัวนี้)
• Strict data parallel เป็นลักษณะแนวทางที่มี data ที่เก็บแยกกันหลายๆจุด แล้วเอา instructions ไป apply กับ data เหล่านี้แบบขนาน (ส่วนตัวผมไม่เข้าใจว่าต่างจาก MIMD/SPMD ยังไง)
• Fork/join แบ่งเป็นสองจังหวะ จังหวะ Fork สร้าง thread/proc เพื่อคำนวณแบบขนาน และจังหวะ Join เป็นการ terminate เพื่อรวมผลลัพธ์
• Actors เป็นการเขียนให้มี agents ที่จริงๆก็เป็น object ในโปรแกรมนั่นแหละ แต่มีชีวิตยาวๆ คอยจัดการกับ message channel ต่างๆ (message passing)
• Master-worker มี Master สำหรับคอยจัดการกับกลุ่มของงาน (scheduling, aggregation) แล้วก็มี worker คอยรับงานไปทำได้ผลลัพธ์ส่งกลับ วนไปเรื่อยๆ
• Task queue ในเมื่อการ schedule แบ่งงานมันยาก อาจจะใช้ pattern queue ได้ แบ่ง task ย่อยๆยัดลง queue แล้วให้ runtime คอยหยิบ task จาก queue ไปประมวลผล ลักษณะใกล้เคียงกับ master-worker แต่ task queue จริงๆก็ใช้กับระบบอื่นได้ด้วยเหมือนกัน
• Graph Partitioning แบ่งกราฟออกเป็นส่วนๆ โดยให้แต่ละส่วนมีขนาดใกล้เคียง และจำเป็นต้องใช้ synchronization (สื่อสารเพื่อให้ consistent) น้อยที่สุด (บอกมาแค่เนี้ย? implementation pattern ยังไงเนี่ย 555)
• Loop-level parallelism บางครั้งเราเขียนโปรแกรมแบบ loop โดยแต่ละ iteration อาจจะไม่ได้ dependent กันทำให้เราสามารถ transform loop ให้ถูกนำไปคำนวณแบบขนานได้

BSP (https://people.cs.rutgers.edu/~pxk/417/notes/pregel.html)

• BSP (Bulk Synchronous Parallel) เป็นการแบ่งโปรแกรมใหญ่ออกเป็นส่วน จากนั้นในแต่ละส่วนสามารถทำขนานกันได้ และจะมาหยุดที่ barrier ทั้งหมดแล้วถึงไปส่วนถัดไปพร้อมกัน (ความรู้สึกผมคิดว่าเหมือน Fork/Join หลายๆครั้งอะ 555)

Data Structure Patterns:

• Shared queue
• Distributed array
• Shared hash table
• Shared data

ทั้ง 4 ตัวนี้ผมไม่แน่ใจจะแบ่งออกมาทำไม เพราะผมมองว่า data structure มันก็ไม่ได้มีแค่ 4 ตัวอะ ไอเดียมันคือ ถ้าข้อมูลขนาดใหญ่มหาศาล มันเก็บลงเครื่องเดียว หรือ memory ก้อนเดียวไม่ได้ ก็ต้องหั่นมัน แต่จะหั่นยังไงให้ load-balance ได้ดี, safe, performance ดี เป็นต้น ถ้า lib ตัวนึงที่น่าจะชัดเจนกับเรื่องนี้มาก คือ dask

Parallel Execution Patterns

Goal: มองว่า algorithm จะถูกแปลงเป็น software ที่ไปจับกับ hardware อย่างไร
Output: ได้แนวทางของการประมวลผลแบบขนานที่มีประสิทธิภาพกับการทำงานบน hardware ได้ดี

Pattern ที่จัดการกับ program/instruction (เขาเขียนว่า advancing program counter):

• MIMD (Multiple instructions, multiple data)
• SIMD (Single instruction, multiple data) เป็นการจัดการกับ data หลายๆก้อนให้อยู่ในรูปที่สามารถโยนเข้าไปทำงานใน instruction เดียวได้ เช่น พวก vector instruction
• Data flow คือ sequence of transformations applied to a stream of data elements
• Task-graph เป็นการมอง computation ในรูปแบบของกราฟที่สามารถนำไป map กับ thread, process หรือ parallel computers ได้
• Thread pool มีการแตก thread เอาไว้แล้วเป็น pool โยนงานเข้าไปเพื่อจะได้ไม่ต้องแตก/ทำลาย thread ทุกครั้งที่ใช้
• Speculative execution
• Digital circuits เขียนโปรแกรมแบบยัดการประมวลผลลง circuit ไปเลย

Pattern ที่จัดการกับ coordination ระหว่าง thread/process:

• Message passing สำหรับระบบที่ใช้ shared memory ไม่ได้ ต้องมีการสื่อสารข้าม network ก็ต้องแปลง object เป็น message ก่อน
• Collective communication เป็นชุดคำสั่งสำหรับการสั่งงานเป็นกลุ่ม ตัวอย่างที่ดีที่สุดคือ MPI
• Mutual exclusion เป็นชุดคำสั่งสำหรับการบังคับให้การประมวลผลเป็นไปตามลำดับที่ควรเป็น เพื่อป้องกัน race condition ตระกูลนี้เช่น mutex lock, condition, etc.
• Point to point synchronization อันนี้ผมไม่ทราบจริงๆ จะแปลตรงๆก็เป็นการจัดการ synchronize ระหว่าง 2 thread ชัดเจน (นึกภาพไม่ออกเลย แต่ search google แล้วก็ขึ้นมาเยอะอยู่)
• Collective synchronization เป็น synchronization เหมือนกัน แต่เป็นกลุ่ม เป็น high-level กว่า แปลว่าใช้ง่ายกว่าบัคน้อยกว่า แต่ก็แลกมาด้วย design ที่จำกัด เช่น barrier synchronization
• Transactional memory เป็นไอเดียสำหรับให้ memory สามารถ rollback ได้เมื่อเกิด conflict (ถ้าใน database หรือ distributed system ขนาดใหญ่ มีชื่อเรียกว่า Saga pattern ผมว่าน่าจะเคสเดียวกัน)

สรุป

Design Pattern ของทาง Berkeley ก็ไม่ได้สมบูรณ์ perfect ที่จริงถ้าพูด pattern ทั้งหมดบนโลก มันยังมีพวก software design pattern อันนี้เขาเจาะจงแค่ parallel pattern เฉยๆ ส่วนตัว pattern เองยังถือว่าเป็น “work-in-progress” อยู่ วิธีที่เขาหา pattern ก็จะหยิบ application จริงๆมาแล้ว mining ดูว่าขาด pattern อะไรไปบ้างไหม (manual ด้นสดนั่นแหละ) ก็เห็นว่ามีเพิ่มมาเรื่อยๆแหละ แต่ทั้งนี้ทั้งนั้น ถึงแม้ว่า pattern มันจะ incomplete แต่มันก็เพียงพอในระดับที่ดีในการเอาไปใช้งานจริงนะ เชื่อว่า pattern นี้จะเป็นกุญแจสำคัญในการแก้ปัญหา parallel programming ได้

ความคิดเห็นส่วนตัวเกี่ยวกับ pattern ทั้งหมด

ที่จริงที่ผ่านมา ผมก็ใส่ความเห็นส่วนตัวกับความรู้อื่นๆที่ไม่ได้มาจากในเว็บโดยตรงเข้าไปหลายจุด อันนี้พูดมุมมองภาพรวมละกัน คิดว่าบาง pattern มีประโยชน์มากเลยนะ แบบถ้ารู้ว่าปัญหาที่เราทำอยู่มันคืออะไร หยิบไปจับตอบได้เลย การมี list ว่าเรามีเครื่องมืออะไรให้ใช้บ้าง มันก็ดีกว่าไม่รู้อะไรเลยเสมอแหละ ส่วนที่ผมรู้สึกอี้ๆ ก็ไม่รู้ว่าเพราะผมไม่ได้คลุกคลีกับ layer ล่างๆด้วยหรือปล่าว บางตัวรู้สึกว่าไม่สมเหตุสมผลเลย แยกมาทำไม (เช่น task graph layer ล่างสุด หรือ graph partition เงี้ยะ รายละเอียดก็ไม่มีอธิบายว่าต่างจาก graph algorithm layer อื่นยังไง) แต่ก็เข้าใจว่าทั้งหมดนี้คือ เอาความรู้ที่มีอยู่ในปัจจุบัน (ตอนเขาคิดก็เป็นอดีตหลายสิบปีละ) มาจับกลุ่ม ดังที่เขาสรุปไว้ว่าจะมีอะไรเปลี่ยนอะไรเพิ่มก็ไม่แปลก สุดท้ายมองว่าไม่ถึงกับต้อง map layer เป๊ะๆ มองผ่านๆก็สามารถเอาไปใช้งานได้ดีทีเดียว

ตัวอย่างการใช้งานกับระบบ Content-Based Image Retrieval

Content-Based Image Retrieval หรือ CBIR เป็น application สำหรับให้ user query ด้วยรูป แล้วได้คำตอบเป็นรูปอื่น ๆ ที่ใกล้เคียงกับ input ที่ใส่เข้าไป อธิบาย architecture ภาพรวมของระบบนี้ได้ตามรูปข้างล่าง

ถ้าเอาตรงๆเลย ผมว่ารูปนี้ค่อนข้างประหลาด (search google ว่า CBIR model ก็ไม่ใช่รูปนี้แล้วอะ) แต่ถ้าข้ามความถูกต้องของ model ไปก่อน มาดูที่ตัว model จะเห็นว่าการที่เราสามารถวาดภาพรวมออกมาเป็น flow แบบนี้ได้ มันคือ pipe-and-filter structure (ซึ่ง application ส่วนใหญ่ก็เป็น structure แบบนี้แหละ) กล่องสี่เหลี่ยมแต่ละตัวเป็น filter ส่วนเส้นเป็น data flow

แต่ application ภาพรวมมันกว้างไป เราสามารถแตกเป็นส่วนย่อยๆได้อีก โดยสมมติว่าตัว classifier ใช้ SVM ละกัน เราจะสามารถแตกออกมาได้เป็นรูปข้างล่าง คือ SVM เนี่ยเป็นการคำนวณ dot products ซึ่งสามารถ map เข้ากับ pattern Dense Linear Algebra ได้พอดี (ไม่ต้องไปนั่งเขียนเอง มี lib ให้) ส่วนขั้นตอนคำนวณ kernel และ sum ไม่มี computation pattern เราเลยใช้ structural pattern แทน มองเป็น MapReduce ได้

สำหรับชั้น Concurrent Algorithmic Strategy ในการรองรับ MapReduce เราอาจจะเลือกใช้ data parallel หรือ geometric decomposition ก็ได้ ถ้า data parallel ก็คำนวณ kernel value ของแต่ละ dot product แยกชัดเจนไปเลย ถ้า geometric ก็ซอย dot product ออกมาเป็นย่อยๆ apply dot product แต่ละส่วนย่อย จากนั้นใช้ global reduce เพื่อหาผลรวมของส่วนย่อยทั้งหมดอีกที (หั่น matrix เป็นส่วนๆแหละ) ซึ่งสุดท้ายก็เลือกว่า data parallel น่าจะทำ concurrent และ scaling ได้ดีกว่า

สำหรับ data parallelism strategy ก็เลือกใช้ strict data parallel กับ loop parallel เข้ามาจัดการ MapReduce (ส่วนตัว: ถ้า dev บ่อยๆ ขั้นตอนนี้มันไม่ต้องเลือกแล้วปะนะ 555)

ส่วน parallel execution เนี่ย มีการใช้ collective synchronize คือ barrier ในการทำให้มั่นใจว่างานทั้งหมดจะทำตามลำดับที่ควรจะเป็น ส่วน SIMD,MIMD บทความไม่ได้พูดถึง ถ้าจะรวมด้วย ก็ต้องวิเคราะห์ว่าจะคูณ dot product ยังไงให้ใช้ vector instruction ได้ แทนที่จะคูณเลข 1*a อาจจะใช้ท่า [1,2,…,8]*a ทีเดียวเร็วกว่าไหม ไรงี้

จากที่วิเคราะห์ทั้งหมด ก็จะได้โค้ดออกมา

function ComputeMapReduce( DataArray, Result) {

1 for i ← 1 to n {
2 LocalValue[i] ← ComputeKernelValue(DataArray[i]);
3                  }
4        Barrier();
5        for reduceLevel ← 1 to MaxReduceLevel {
6         for i ← 1 to n {
7                            if (NeedReduce(i, reduceLevel) ) {
8                                offset ← ComputeOffset(i, reduceLevel);
9                                LocalValue[i] ← Reduce(LocalValue[i], LocalValue[i+offset]);
10                               }
11                        }
12         Barrier();
13        }

สรุปเป็นข้อๆทีละ layer ได้แบบนี้

• SVM classifier can be viewed as a composition of the pipe-and-filter, dense linear algebra, and MapReduce patterns.
• To parallelize the MapReduce computation, we used the data parallelism pattern.
• To implement the data parallelism Algorithmic Strategy, both the strict-data-parallel and loop-parallel patterns are applicable.
• To map the strict-data-parallel pattern onto a platform for execution, we chose SIMD pattern.
• We used the shared-data pattern to define the synchronization protocols for the reduction and the collective synchronization pattern to describe the barrier construct.

22 June 2023