C#.NET: คิดแบบขนาน, แก้ปัญหาแบบขนาน (Think like parallel, act like parallel)

สวัสดีครับ 

ทิ้งระยะนานมาก กลับมาเขียนบล็อคทีหนึ่ง บล็อคนี้ก็มานำเสนอ โปรแกรมเมอร์ หรือนักแก้ปัญหาทั้งหลายให้มาคิดแก้ปัญหาแบบขนาน แต่งเป็นหัวข้อว่า “คิดแบบขนาน, แก้ปัญหาแบบขนาน” (Think like parallel, act like parallel)

ตัวอย่าง ผมขอใช้ภาษา C#.NET version 4 ขึ้นไปครับ

คำว่าขนาน ในที่นี้ก็ คือ การออกแบบงานให้สามารถทำไปพร้อมๆกัน หรือขนานกันได้ ดูภาพ (001-concept.png)

001-concept

จากภาพ เส้นบนสุด t คือเส้นเวลา กล่องสีฟ้าๆ คือ เนื้องาน ที่ต้องทำเพื่อใช้แก้ปัญหา ปัญหาในที่นี้ เช่น งานที่ต้องทำเพื่อส่งมอบของตามความต้องการ, การคํานวณตัวเลขเพื่อใช้แก้ปัญหา หรือตั้งค่าบางอย่างให้เครื่องจักรทำงานผลิต เป็นต้น

การออกแบบงานแบบ ผมแบ่งกรอบให้คิด ออกเป็น 2 ขั้นตอน คือ

1- วางแผนแบ่งแยก (Plan partitioning)

เป็นขั้นตอนวิเคราะห์ปัญหา ประกอบไปด้วยสองส่วนหลักที่ต้องวิเคราะห์เพื่อแยกแยะออกมาให้ครบถ้วน คือ โครงสร้างข้อมูล (Data structure) และขั้นตอนวิธีแก้ปัญหา (Algorithm)

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

ขั้นตอนวิธีแก้ปัญหา (Algorithm) ขั้นตอนวิธี ซึ่งประกอบไปด้วย งานแมพ (Map) และงานลดค่า (Reduce) โดย

งานแมพ คือขั้นตอนวิธี การกลองข้อมูล, จัดลำดับข้อมูล ซึ่งมีการเปลี่ยนแปลงข้อมูล หรือโครงสร้างข้อมูล เพื่อให้พร้อมใช้แก้ปัญหาในขั้นตอนถัดไป

งานลดค่า คือขั้นตอนวิธีการรวม คำนวณค่า หรือ ก็คือการสรุปข้อมูลให้ออกมาเป็นผลลัพธ์ตามต้องการ

2- ทำแบบขนาน (Do parallel)

เป็นขั้นตอน execute [1] งานในแบบขนาน หรือทำหลายๆงานไปพร้อมกัน งานที่ว่าก็คืองานที่เราวิเคราะห์ แล้วแบ่งแยกได้แล้วจากขั้นตอนแรก เพื่อให้ได้ผลเฉลยของปัญหาตามต้องการ

ตัวอย่าง: จงคํานวณผลรวมของ function foo(bar) = bar * bar + bar + 1 ตั้งแต่ bar = 1 ถึง 3,000,000

เขียน code ตัวงานได้เป็น

long foo(long bar)
{

return bar * bar + bar + 1;

}

[1] execute ก็คือ การทำงานของบางสิ่งบางอย่างตามชุดคำสั่งที่เรากำหนดไว้ ในที่นี้ ชุดคำสั่งที่เรากำหนดเขียนด้วย code C# จากนั้นนำไปให้เครื่องคอมพิวเตอร์ทำงานตามชุดคำสั่ง หรือ execute คำสั่งให้เรานั่นเอง

ผมจะเริ่มจาก ทำแบบเป็นลำดับตรงๆ คือการทำงานแบบปกติก่อน หลังจากนั้น ผมจะนำเสนอการแก้ปัญหาแบบ คิดแบบขนาน, แก้ปัญหาแบบขนาน ผมก็จะได้ผลลัพธ์ออกมาเป็น สองผลลัพธ์ เพื่อนำมาเปลียบเทียบกัน ให้ผู้อ่านได้เห็นภาพในแบบ ก่อน/หลัง (before/after) ได้

ทำแบบเป็นลำดับตรงๆ

var stopWatch = Stopwatch.StartNew();
var sum = Enumerable.Range(1, 3000000).Select(bar => foo(bar)).Sum();
Console.WriteLine(“Sum: {0}, Elapsed: {1}s”, sum, stopWatch.Elapsed);

ผลลัพธ์ ดูภาพ (001-result-1.png)

001-result-1

จากภาพ ผลลัพธ์ที่ต้องการเท่ากับ 9000000000001999999

ใช้เวลาไป 0.1504391 วินาที ถ้าอ้างอิงจากภาพ (001-concept.png) คือ t1 – t0 เท่ากับ 0.1504391 วินาที

ทำแบบขนาน

var stopWatch = Stopwatch.StartNew();
var sum = default(long);
var results = new List<long>(); // เตรียมข้อมูลไว้ใส่ผลลัพธ์ที่ผ่านขั้นตอน map
Parallel.ForEach(

Partitioner.Create(1, 3000000), // วางแผนแบ่งงาน
range =>
{

// งาน map

long r = 0;

// ข้อมูลถูกแบ่งด้วย Partitioner.Create เป็นส่วนๆ จาก Item1 ถึง Item2
for (int bar = range.Item1; bar < range.Item2; bar++)
{

r += foo(bar);

}
results.Add(r); // การ emit ข้อมูลที่ map เสร็จแล้วเพื่อส่งต่อไปงาน reduce

}

);
sum = results.Sum(); // งาน reduce
Console.WriteLine(“Sum: {0}, Elapsed: {1}s”, sum, stopWatch.Elapsed);

ผลลัพธ์ ดูภาพ (001-result-2.png)

001-result-2

จากภาพ ผลลัพธ์ที่ต้องการเท่ากับ 9000000000001999999 (ผลลัพธ์เท่ากับทำแบบเป็นลำดับตรงๆ)

ใช้เวลาไป 0.0602625 วินาที ถ้าอ้างอิงจากภาพ (001-concept.png) จากเครื่องของผู้เขียนเอง สามารถทำงานพร้อมๆกันได้สูงสุด 4 งาน ดังนั้นการวางแผนแบ่งงาน จึงสามารถแบ่งงานได้ 4 งานจากงานใหญ่

โดยใช้ class Partitioner สร้างงานให้ ผมจึงไม่จำเป็นต้องกำหนดขนาดของข้อมูลเพื่อแบ่ง partition เองก็ง่ายดี แสดงเป็น ภาพใหม่ได้ แบบบนี้ (001-concept2.png)

001-concept2

เมื่ออ้างอิงเวลาทำงานจากภาพใหม่ (001-concept2.png) ที่มี CPU ประมวลผลได้ 4 งานพร้อมๆกัน เวลาที่ใช้คือ t0.25 – t0 เท่ากับ 0.0602625 วินาที

สรุปได้ว่า คิดแบบขนาน และทำแบบขนานนั้นใช้เวลาน้อยกว่า คิดแบบเป็นลำดับตรงๆ ใช้เวลาน้อยกว่าเท่าไรนั้น ขึ้นกับจำนวน CPU ของเครื่องที่เราใช้ execute นั้นเอง ดังนั้น เราจำเป็นต้องเขียน code ให้สามารถทำงานแบบขนานให้ได้เสมอ จึงสามารถใช้ประโยชน์จากเครื่องที่มี CPU หลายๆตัวได้อย่างมีประสิทธิภาพสูงที่สุด… เรามา “คิดแบบขนาน, แก้ปัญหาแบบขนาน” กันเถอะครับ มันมีประโยชน์ดีนะ ฝากไว้ไปคิด ไปทำกันต่อไป

ขอบคุณครับ

#:P

Advertisements