Có thật nhân ma trận nhanh hơn với PHP multithread ?

Bài viết này nằm trong series bài viết về PHP Multithreading và như đã đề cập trong các bài viết trước bài viết này không khuyến khích mang những gì mà mình nêu ở đây lên production của bạn hay công ty bạn. Tại thời điểm 2021 này nếu bạn muốn tìm hiểu về threading trong PHP thì thật sự không có nhiều tài liệu hay tài nguyên bằng tiếng Việt thì khá là khó khăn.

Ôn lại tí về nhân ma trận

Nhân hai ma trận là phép tính khá cơ bản mà đâu đó chúng ta bắt đầu biết về nó tử những năm cấp 3, sau đó thì nó mà nếu không có vụ Deep learning thì chắc mình cũng quăng nó trong góc nhà. Để đơn giản thì anh em cứ niệm thần chú lấy hàng nhân với cột là ổn rồi.

Giả sử bạn cần nhân 2 ma trận A[m:n] và ma trận B [n:t], thì độ phức tạp của phép toán này là vào khoản m.n.t. Việc này sẽ không có gì để bàn nếu mình thực hiện nhân 2 ma trận với kích thước nhỏ như 10×10 hay 100×100. Tuy nhiên chuyện gì sẽ xảy ra nếu bạn thực hiện nhân ma trận A[200:1000] và B[1000:200], khi đó máy phải thực hiện 200 x 1000 x 200 là khoản 40 triệu phép tính. Với tốc độ của con chip I7-8850H của máy mình vào nó vào khoản 8 giây.

Bạn nào cần code mẫu có thể copy cái này nhé.

<?php
 
function matrix_gen($row, $col)
{
    $result = [];
    for ($i = 0; $i < $row; $i++) {
        $column = [];
        for ($j = 0; $j < $col; $j++) {
            $column[] = rand(1, 9);
        }
        $result[] = $column;
    }
    return $result;
}
 
function matrix_mult($m1, $m2): array
{
    $r = count($m1);
    $c = count($m2[0]);
    $p = count($m2);
    if (count($m1[0]) != $p) {
        throw new Exception('Incompatible matrixes');
    }
    $m3 = [];
    for ($i = 0; $i < $r; $i++) {
        for ($j = 0; $j < $c; $j++) {
            $m3[$i][$j] = 0;
            for ($k = 0; $k < $p; $k++) {
                $m3[$i][$j] += $m1[$i][$k] * $m2[$k][$j];
            }
        }
    }
 
    return ($m3);
}
 
$matrix_1 = matrix_gen(200, 1000);
$matrix_2 = matrix_gen(1000, 200);
 
$start = microtime(true);
$matrix_3 = matrix_mult($matrix_1, $matrix_2);
$result = microtime(true) - $start;
echo sprintf("Result: %f", $result);

Mà 8s này nó chỉ thực hiện trên một core mà thôi. Cái này là giới hạn của PHP tại thời điểm hiện tại. Cho dù code bạn có pro cỡ nào đi chăng nữa thì PHP official cũng chỉ chạy trong 1 thread mà thôi. …2021 rồi mà nhìn PHP vẫn chán!

Ý tưởng tối ưu nhân ma trận bằng multithreading

Vậy nếu có cách nào đó mà mình có thể  tận dụng được cả 8 core trên máy thì biết đâu mình có thể tăng tốc xử lý cho nó từ 8s xuống còn 1s thì sao ta? Ý tưởng sẽ là chúng ta thực hiện nhân ma trận A[3,2] với ma trận B [2, 3] thì ta sẽ thực hiện phép tính của dòng 1 ma trận A với toàn ma trận B trong 1 thread, dòng 2 của ma trận A với ma trận B trong 1 thread khác nữa. Với ma trận có 5 dòng thì ta sẽ dùng 5 thread để xử lý.

Nếu ma trận A ban đầu có nhiều dòng hơn thì ta sẽ giới hạn số thread lại sao cho tổng sổ thread bằng với tổng số core mà máy bạn có. Ví dụ máy mình có 8 cores thì mình chỉ nên chạy cái này trong 8 threads thôi. Tức là từ dòng thứ 1 -> 8 sẽ được xử lý trước còn còn thứ 9 -> 16 thì sẽ nằm trong Pool và đợi khi nào 8 thread kia xử lý xong sẽ xử lý tiếp 8 cái kế tiếp. Theo lý thuyết thì cách làm này có thể làm cho code bạn chạy nhanh hơn 8 lần vì nó sẽ tận dụng hết sức mạnh của CPU mà bạn đang có.

Nói tới đây được rồi, giờ tới lúc show hand thôi, code đây. Do code khá dài nên mình bỏ nó trên đây luôn.

<?php

class MatrixThreaded extends Threaded
{

    public function __construct($rowIndex, $row, $matrix2)
    {
        $this->rowIndex = $rowIndex;
        $this->row = $row;
        $this->matrix2 = $matrix2;
        $this->rowResult = [];
        $this->done = false;
    }

    public function run()
    {
        $c = count($this->matrix2[0]);
        $p = count($this->matrix2);

        for ($j = 0; $j < $c; $j++) {
            $this->rowResult[$j] = 0;
            for ($k = 0; $k < $p; $k++) {
                $this->rowResult[$j] += $this->row[$k] * $this->matrix2[$k][$j];
            }
        }

        $this->done = true;
    }

    public function getResult()
    {
        return $this->rowResult;
    }

    public function getRowIndex()
    {
        return $this->rowIndex;
    }

    public function isDone(): bool
    {
        return $this->done;
    }

}

class MatrixPool extends Pool
{
    protected $result = [];

    public function process($matrix1, &$matrix2)
    {
        $r = count($matrix1);
        for ($i = 0; $i < $r; $i++) {
            $this->submit(new MatrixThreaded($i, $matrix1[$i], $matrix2));
        }
        while(count($this->result) < $r) {
            $this->collect(function (MatrixThreaded $threaded) {
                if ($threaded->isDone()) {
                    $this->result[$threaded->getRowIndex()] = $threaded->getResult();
                }
                return $threaded->isDone();
            });
        }

        $this->shutdown();

        return $this->result;
    }

}

function matrix_gen($row, $col)
{
    $result = [];
    for ($i = 0; $i < $row; $i++) {
        $column = [];
        for ($j = 0; $j < $col; $j++) {
            $column[] = rand(1, 9);
        }
        $result[] = $column;
    }
    return $result;
}

function matrix_mult($m1, $m2): array
{
    $r = count($m1);
    $c = count($m2[0]);
    $p = count($m2);
    if (count($m1[0]) != $p) {
        throw new Exception('Incompatible matrixes');
    }
    $m3 = [];
    for ($i = 0; $i < $r; $i++) {
        for ($j = 0; $j < $c; $j++) {
            $m3[$i][$j] = 0;
            for ($k = 0; $k < $p; $k++) {
                $m3[$i][$j] += $m1[$i][$k] * $m2[$k][$j];
            }
        }
    }
    return ($m3);
}

function compare_matrix($m1, $m2): bool
{
    $r = count($m1);
    $c = count($m1[0]);
    if (count($m2) !== $r || count($m2[0]) !== $c) {
        return false;
    }
    for ($i = 0; $i < $r; $i++) {
        for ($j = 0; $j < $c; $j++) {
            if ($m1[$i][$j] !== $m2[$i][$j]) {
                return false;
            }
        }
    }
    return true;
}


$matrix_1 = matrix_gen(100, 1000);
$matrix_2 = matrix_gen(1000, 100);

$start = microtime(true);
$matrix_3 = matrix_mult($matrix_1, $matrix_2);
$result = microtime(true) - $start;
echo sprintf("normal: %f \n", $result);

$start = microtime(true);
$pool = new MatrixPool(8);

$matrix_4 = $pool->process($matrix_1, $matrix_2);
$result = microtime(true) - $start;
$label = compare_matrix($matrix_3, $matrix_4) ? 'pthread' : 'pthread (incorrect): ';
echo sprintf("%s: %f \n", $label, $result);

Kết quả ngoài mong đợi, chậm hơn 2 lần!

Cái này tới đây thì các bạn cũng hiểu là đời hok có gì dễ ăn cả, không phải cứ cái gì nhiều thread là sẽ chạy nhanh hơn âu nhé! Nguyên nhân của vấn đề vì sao chạy multithread nó chậm vì mấy cái ma trận này cần copy data qua lại giữa các thread nên nó sẽ cost bạn thời gian transfer dữ liệu. Bạn chậm vì chuyển data chứ không phải chậm vì xử lý data.

Ý mình muốn nhắn gửi là gì, viết phần mềm xịn khá khó, bạn sẽ bị ăn hành từ các thể loại như thế này rất nhiều! Nên anh em cứ vui vẻ mà code, hàng còn dài dài ha!