Parallel with Java

ทำไมต้อง Parallel

สมมุติว่าได้รายงานมาหนึ่งหัวข้อมี 4 บทกับกลุ่ม 4 คน

แน่นอนการมีสี่คนแล้วให้คนเดียวทำเป็นอะไรที่ส้นตีนมาก

เช่นเดียวกัน การใช้คอมมี 4 Core แต่โปรแกรมมันรันทีละคอร์ก็ส้นตีนมาก

ใน Java เวลาเขียนโปรแกรมแล้วโปรแกรมจะรันคำสั่งจากต้นไปจนจบตามลำดับกัน ซึ่งมันรันโดยการที่ใช้แค่คอร์เดียวเท่านั้น อีก 3 core ปล่อยว่าง บางทีแล้วเราอาจจะสามารถแบ่งงานให้ 3 core ที่เหลือได้แล้วงานจะเร็วขึ้น คำสำคัญตอนนี้คือ แบ่งงาน ถ้างานแบ่งไม่ได้ ก็แตกคอร์ไม่ได้

งานยังไงบ้างล่ะที่จะแบ่งได้? สำคัญคือต้องสามารถทำงานแยกกันได้โดยอิสระ

งานคำนวณบางอย่าง เช่น มีข้อมูลในฐานข้อมูล 1,000,000 ข้อมูล ต้องการหาผลรวมของช่องคะแนน (แบ่งได้หลายวิธี เช่น แบ่งตามหมายเลขข้อมูล 1-100,000, 100,001-200,000, ...) บางอย่างก็แบ่งไม่ได้ เช่น Factorial เพราะผลมันเกิดจากคำตอบก่อนหน้า
งานที่มันแยกกันสนิทแต่ใช้รวมกัน เช่น ในใน BioShock ภาคแรกแบ่งระบบต่างๆ แยกออกจากกันได้แก่ ระบบจำลองเกม, ระบบ GUI, ระบบแสดงผล, ระบบเล่นเสียง, ระบบเอฟเฟกท์เสียง, ระบบโหลดภาพพื้นผิว, ระบบโหลดไฟล์, ระบบจำลองฟิสิกส์
งานที่เป็น I/O Bound (Input/Output) เช่นการโหลดข้อมูลจากเน็ต ถ้าไม่แตก Threads ออกไปโปรแกรมจะค้างขณะโหลด
การเขียน GUI นั้นทุกอย่างที่ไม่ได้ยุ่งกับ GUI (เช่น การเซฟไฟล์) ควรแตกไปทำข้างหลังเพื่อไม่ให้ GUI ค้าง

Threads

Threads (เธรด) เป็นความสามารถของระบบปฏิบัติการที่ทำให้โปรแกรมสามารถแยกตัวเองเป็นหลายๆ ส่วนเพื่อประมวลผลพร้อมๆ กันได้

Java นั้นมีคลาส Thread สำหรับใช้สร้างเธรด

class ThreadByThread extends Thread{
    @Override
    public void run(){
        // สิ่งที่ต้องการประมวลผล
    }
}
class ThreadByRunnable implements Runnable{
    @Override
    public void run(){
        // สิ่งที่ต้องการประมวลผล
    }
}
class Main{
    public static void main(String[] args){
        ThreadByThread t1 = new ThreadByThread();
        t1.start(); // เรียก start ไม่ใช่ run
        Thread t2 = new Thread(new ThreadByRunnable());
        t2.start();
    }
}

สังเกตว่าเราสามารถใช้ได้ทั้งสองแบบ โดยแบบที่ใช้ implements Runnable จะเป็นประโยชน์ในกรณีที่ต้องการ extends class ที่มีอยู่แล้ว และทำให้เป็นเธรด

เมื่อสั่ง start (ไม่ใช่ run) แล้ว Java จะแตกเธรดออกไปและรันโค้ดใน run โดยไม่รอให้ run ทำงานเสร็จก่อน การ start นี้เรียกว่า "fork"

Race condition

เมื่อมีโค้ดทำงานพร้อมๆ กัน บางครั้งจึงเกิดกรณีที่เรียกว่า race condition หรือการที่ 2 threads แย่งกันใช้ตัวแปร

class BankAccount{
    private int balance;
    public boolean withdraw(int amount){
        if(balance-amount <= 0){
            return false;
        }
        // หยุดตรงนี้
        balance -= amount;
        return true;
    }
}

ตัวอย่างเช่นในกรณีนี้ ถ้ามี 2 เธรดทำงานพร้อมกันอยู่แล้วเรียกใช้ withdraw พร้อมกัน ตัวหนึ่งอาจจะทำงานถึง comment แล้วและพักการทำงานให้อีกเธรดทำงาน อีกเธรดนั้นรันคำสั่ง withdraw จนจบแล้วเธรดแรกจึงทำที่เหลือของ withdraw ต่อ

สิ่งที่เกิดขึ้นคือสามารถถอนเงินเกินบัญชีได้ เพราะเธรดแรกผ่านการเช็คแล้ว และ balance เกิดเปลี่ยนแปลง

Flow chart of execution

วิธีการแก้ปัญหานี้คือการใช้ synchronized

class Synchronized{
    int x = 0;
    public synchronized void syncMethod(){
        x += 1;
    }
    public void syncBlock(){
        synchronized(this){
            x += 1;
        }
    }
}

สองเมธอดนี้โค้ดเหมือนกัน อันหนึ่งใช้ synchronized ในหัวเมธอด อีกอันใช้ใน body เรียกว่า synchronized block

เมื่อโค้ดมาถึงจุดที่มีการใส่ synchronized คร่อมไว้จะต้องเข้าคิวกันทำงาน เมื่อคนหนึ่งเข้าไปแล้วจะต้องรอให้เสร็จก่อนจึงจะเรียกคิวต่อไป

ตัวอย่างเช่นถ้าเอา BankAccount มาเติม `synchronized

class BankAccount{
    private int balance;
    public synchronized boolean withdraw(int amount){
        if(balance-amount <= 0){
            return false;
        }
        // หยุดตรงนี้
        balance -= amount;
        return true;
    }
}

Flowchart

กรณีนี้แล้วจะไม่มีการรัน withdraw ครึ่งๆ กลางๆ จะต้องรันให้จบก่อนคนอื่นจึงจะสามารถเข้า withdraw ต่อได้

สิ่งที่อยู่ใน synchronized(..) นั้นคือชื่อของคิว นั่นหมายความว่าถ้าคิวคนละชื่อกันถึงจะมีโค้ดรันอยู่ใน synchronized(a) อยู่ก็สามารถเข้า synchronized(b) ได้ ไม่เกี่ยวข้องกัน

แบ่งงาน

อ้างอิงจาก Lois S. and Rajkuma B. Parallel Programming Models and Paradigms.

Master-Slave

การแบ่งงานแบบ Master-Slave คือมีตัว master เป็นหัวหน้ากลุ่ม และมีลูกน้อง (slave) ภายในกลุ่ม

master สร้าง slave มาจำนวนหนึ่ง (อาจจะตาม cores ของ CPU)
slave ของานจาก master
master แบ่งงานมาหนึ่งชิ้นแล้วให้ slave
slave ทำงานเสร็จแล้วส่งคำตอบให้ master
วนซ้ำข้อ 2 จนกว่าจะไม่ได้งานจาก master
master รวบรวมคำตอบและสรุปผล

ข้อดีของวิธีนี้คือกรณีสถานการณ์มีการเปลี่ยนแปลง เช่น งานเพิ่มขึ้นขณะที่กำลังทำงานอยู่ หรือต้องการสร้าง slave เพิ่มเติมอีกก็สามารถทำได้ ข้อเสียคือการขอข้อมูลจาก master มันช้า ทำบ่อยๆ ยิ่งช้า

Divide and Conquer

วิธีนี้เหมือน Phantom Lancer คือตัดปัญหาเป็นชิ้นย่อยๆ ที่ทำงานแยกจากกันแล้ว slave แบ่งไปทำ

Divide 1

Juxtapose

ฟาร์ม

บางกรณีเราอาจจะทำให้ slave อาจจะมองเห็นงานที่แบ่งแล้วว่ายังใหญ่อยู่ และแบ่งต่อเข้าไปอีกเรื่อยๆ

Divide Recurse

Phantom Edge

ฟาร์มรัวๆ

Single-Program Multiple-Data (SPMD)

วิธีนี้และหลังจากนี้ไม่มีสอนในที่เรียน ข้ามไปก็ได้

master สร้าง slave มาจำนวนหนึ่ง
master แบ่งงานและส่งให้ slave ทั้งหมด
slave ประมวลผล และอาจจะมีการสื่อสารหรือดึงข้อมูลระหว่างกัน
master รวบรวมคำตอบและสรุปผล

SPMD

วิธีนี้มีข้อสังเกตคือมีการแบ่งงานก่อนแล้วค่อยทำ และมีการสื่อสารกันระหว่าง slave (เหมือนการทำงานกลุ่ม) ซึ่งอาจจะจำเป็นในการแก้ปัญหาบางประเภท

ข้อเสียของวิธีนี้คือหาก slave บางตัวเกิดตาย (เช่นเกิด exception) อาจทำให้ระบบเกิด deadlock คือ slave ตัวอื่นอาจจะต้องการสื่อสารกับ slave ที่ตายแล้ว และจะหยุดรอไปเรื่อยๆ ไม่ทำงาน

Data Pipelining

Pipeline

วิธีนี้ใช้สำหรับปัญหาที่แตกเป็นข้อย่อยๆ ที่แก้แยกจากกันเป็นอิสระได้แล้วเอาคำตอบมารวมกัน การทำงานคือ

แตกงานเป็นข้อๆ
เอาข้อแรกส่งให้เธรดที่ 1
เธรดที่ 1 หาคำตอบและส่งต่อให้เธรดที่ 2 ที่จะทำขั้นต่อไป
เธรดที่ 1 รับข้อใหม่มาทำไปเรื่อยๆ จนกว่าจะหมด
เช่นเดียวกัน เธรดที่ 2 เสร็จงานแล้วก็ส่งต่อให้เธรดที่ 3 ไปเรื่อยๆ

วิธีนี้อาจจะเหมือนการส่งถังน้ำ แทนที่จะให้แต่ละคนยกน้ำไปก็ยืนเฉยๆ แล้วส่งถังให้เพื่อนคนถัดไปแทน

Fork Join

สังเกตว่าการแบ่งงานหลักๆ แล้วคือ

สร้างลูก
ให้ลูกทำงาน
สรุปผล

ขั้นตอนที่ 1 นี้เรียกว่า fork ที่แปลว่าส้อม เหมือนส้อมที่ด้ามเป็นเส้นตรงแล้วแยกออกเป็นกิ่งๆ

โลโก้ Yamaha เป็นส้อมเสียง 3 อันซ้อนกัน

และขั้นตอนที่ 3 เรียกว่า join คือการรวมกิ่งที่แยกออกไปให้กลับเข้ามาเป็นกิ่งเดียว

การ Fork ใน Java ทำได้ด้วยการใช้เธรดตามหัวข้อด้านบน ส่วนการ Join สามารถทำได้ดังนี้

class Main{
    public static void main(String[] args){
        ThreadByThread t1 = new ThreadByThread();
        t1.start(); // fork
        System.out.println("thread started");

        try{
            t1.join();
        }catch(InterruptedException e){
        }
        System.out.println(t1.getResult()); // เมธอดนี้ไปเขียนเอง
    }
}

คำสั่ง join จะหยุดการทำงานของเธรดปัจจุบันจนกว่าเธรดที่สั่ง join จะหลุดออกจาก run แล้วจึงจะทำงานต่อ

Technical

หัวข้อนี้เป็นข้อมูลเพิ่มเติม งงก็งงต่อไป

กรณีที่คอมพิวเตอร์ใช้คอร์เดียว หรือคอร์จองทำงานเต็ม ระบบปฏิบัติการจะมีกระบวนการ Time sharing คือแบ่งเวลาให้โปรแกรมต่างๆ ตามความเหมาะสมและลำดับความสำคัญ เมื่อหมดเวลาแล้วระบบปฏิบัติการจะพักการทำงานของโปรแกรมไว้แล้วให้โปรแกรมอื่นผลัดกันทำงาน