1. Mở đầu

Lý thuyết xác suất là một phân nhánh của toán học liên quan đến việc phân tích, đánh giá các sự kiện ngẫu nhiên. Một trong những ngành mà lý thuyết xác suất được sử dụng rất nhiều là truyền thông (communication). Bài viết này sẽ trình bày một ứng dụng của lý thuyết xác suất trong việc đánh giá độ tin cậy của giao thức ALOHA.

Một chút về lịch sử: ALOHA là hệ thống mạng máy tính đầu tiên, được phát triển ở đại học Hawaii. ALOHA được đưa vào sử dụng năm 1971, trở thành hình mẫu đầu tiên của mạng không dây truyền gói dữ liệu (wireless packet data network).

2. Tại sao giao thức ALOHA được coi là thiếu ổn định?

Trong phần này, dựa trên lý thuyết xác suất, chúng ta sẽ chứng minh sự thiếu ổn định của giao thức ALOHA.

Xét một communications facility ở đó: chia thời gian thành các slot có cùng period, số lượng bản tin đến tại thời điểm đầu mỗi slot n = 1, 2, … là các biến ngẫu nhiên độc lập với nhau và phân bố đồng dạng (indepedent and identically distributed). Đặt ai = P{có i bản tin đến} và giả sử rằng a0 + a1 < 1, tức là vẫn có khả năng nhiều hơn 2 bản tin sẽ đến. Mỗi bản tin đến sẽ được truyền đi tại cuối slot mà nó đến. Nếu có đúng một bản tin được truyền đi, việc truyền tin thành công và bản tin sẽ rời khỏi hệ thống. Trong trường hợp ngược lại, nếu cuối một slot nào đó, ít nhất 2 bản tin đồng thời được truyền, sẽ xảy ra xung đột và những bản tin này vẫn ở lại trong hệ thống. Khi một bản tin gặp xung đột, nó sẽ độc lập với các bản tin khác truyền đi tại cuối slot tiếp theo với xác suất p. Ta sẽ chứng minh hệ thống như vậy sẽ không ổn định theo nghĩa: số lượng các lần truyền tin thành công là hữu hạn, với xác suất là 1.

Đặt Xn là số lượng bản tin trong hệ thống tại bắt đầu slot thứ n. Để ý rằng {Xn, n > = 0} là một chuỗi Markov. Đưa vào một biến Ik như sau:

**Ik = 1**, nếu lần đầu tiên chuỗi rời trạng thái k, nó sẽ đi trực tiếp sang trạng thái k-1. **Ik = 0** trong các trường hợp còn lại, bao gồm cả trường hợp hệ thống không bao giờ ở trạng thái k. Lấy ví dụ, nếu chuỗi Markov là 0, 1, 3, 4… thì I3 = 0 do khi chuỗi rời khỏi trạng thái 3 thì nó sẽ đi sang trạng thái 4, không phải trạng thái 2. Ngược lại, nếu chuỗi là 0, 3, 3, 2, … thì I3 = 1 vì ở lần đầu tiên nó đi ra khỏi trạng thái 3 thì nó sẽ sang trạng thái 2. Hiểu một cách đơn giản, biến Ik là một biến xác định tại trạng thái k, hệ thống có gửi được bản tin nào đi không, nếu gửi được thì hệ thống nhảy sang trạng thái k-1 và biến Ik nhận giá trị 1 (true).

Bây giờ ta tính giá trị trung bình (mean) sau:

Bây giờ, P{Ik = 1 | k is ever visited} là xác suất khi rời khỏi trạng thái k, trạng thái tiếp theo sẽ là k-1. Đây là xác suất có điều kiện của sự kiện: chuyển trạng thái từ k sang k-1, biết rằng hệ thống sẽ không quay trở lại trạng thái k. Do đó:

Ở đây, P{i,j} là xác suất của chuỗi Markov chuyển từ trạng thái i sang trạng thái j. Ta tính P{k,k-1} như sau: nhận thấy nếu có k bản tin ở đầu một slot thì sẽ có k-1 bản tin ở đầu slot tiếp theo nếu không có bản tin nào đến ở slot đó và chỉ có đúng một trong số k bản tin được truyền đi. Như vậy:

Đối với P{k,k}: nếu có k bản tin ở đầu một slot thì sẽ có k bản tin ở đầu slot tiếp theo nếu:

• không có bản tin nào đến và không xảy ra trường hợp: chỉ có đúng một trong số k bản tin được truyền đi. Tức là có thể không có bản tin nào truyền đi, như vậy vẫn chỉ có k bản tin. Hoặc là có 2 bản tin trở lên được truyền đi, nhưng như thế lại có xung đột và các bản tin này không được truyền và vẫn nằm nguyên trong hệ thống.

• có đúng một bản tin đến (và nó sẽ tự động được truyền đi) và không có bất cứ bản tin nào trong số k bản tin được truyền.

Đưa vào công thức, ta có:

Tổng kết lại, ta có:

Trong công thức trên, để ý khi k đủ lớn, mẫu số của biểu thức sẽ hội tụ về 1-a0, còn trên tử số ta có:

Do đó, giá trị trung bình (mean) của tổng tất cả Ik sẽ nhỏ hơn vô cùng. Điều đó chứng tỏ, tổng tất cả các Ik sẽ nhỏ hơn vô cùng với xác suất là 1 (vì ngược lại, nếu có xác suất dương là tổng này có thể bằng vô cùng, thì giá trị trung bình của nó sẽ phải là vô cùng). Như vậy, với xác suất là 1, sẽ chỉ có hữu hạn trạng thái mà chuỗi Markov có thể rời khỏi nhờ truyền bản tin thành công. Cũng có nghĩa là, sẽ có một số nguyên hữu hạn N nào đó, mà khi có ít nhất N bản tin trong hệ thống, sẽ không thể có truyền tin thành công nào nữa. Xác suất có ít nhất 2 bản tin đến là dương, trong trường hợp đó, hệ thống sẽ không có bản tin nào truyền đi cả, và số lượng bản tin sẽ tăng lên ít nhất 2 bản tin. Vậy nên, hệ thống cuối cùng sẽ đạt đến trạng thái có ít nhất N bản tin ở trên, và không thể có truyền tin thành công nữa.

Vậy là ta đã thấy, giao thức ALOHA, trên phương diện lý thuyết xác suất, không ổn định về đảm bảo truyền tin thành công.

Tài liệu tham khảo

1. Introduction to Probability Models - Sheldon Ross

Lời nói đầu

Là một lập trình viên mà đã từng phải thao tác với cơ sở dữ liệu, hay đơn thuần là đã từng là một trang web bán hàng ,chắc hẳn các bạn đã từng nghe qua về khái niệm “Full text search”. Khái niệm này đã được định nghĩa khá cụ thể và đầy đủ trên wikipedia. Nói một cách đơn giản, “Full text search” là kĩ thuật tìm kiếm trên “Full text database”, ở đây “Full text database” là cơ sở dữ liệu chứa “toàn bộ” các kí tự (text) của một hoặc một số các tài liệu, bài báo.. (document), hoặc là của websites. Trong loạt bài viết này, mình sẽ giới thiệu về Full Text Search, từ khái niệm đến ứng dụng thực tiễn của kĩ thuật này. Chuỗi bài viết không nhằm giúp bạn tìm hiểu cụ thể về Full Text Search technique trong MySQL, Lucene hay bất kì search engine nào nói riêng, mà sẽ giúp bạn hiểu thêm vầ bản chất của kĩ thuật này nói chung. Ở bài viết cuối cùng, mình sẽ cùng các bạn implement thử một “Full Text Search engine” sử dụng python, qua đó giúp các bạn nắm rõ hơn cốt lõi của vấn đề.

Trong phần đầu tiên mình sẽ giới thiệu về định nghĩa của Full text search, và khái niệm cơ bản nhất trong Full Text Search, đó là Inverted Index.

Introduction

1
2
3

SELECT column_name(s)
FROM table_name
WHERE column_name LIKE pattern;

Sử dụng LIKE, các bạn sẽ chỉ phải tìm kiếm ở column đã định trước, do đó lượng thông tin phải tìm giới hạn lại chỉ trong các column đó. Câu lệnh LIKE cũng tương đương với việc bạn matching pattern cho “từng” chuỗi của từng dòng (rows) của field tương ứng, do đó về độ phức tạp sẽ là tuyến tính với số dòng, và số kí tự của từng dòng, hay chính là “toàn bộ kí tự chứa trong field cần tìm kiếm”. Do đó sử dụng LIKE query sẽ có 2 vấn đề: - 1) Chỉ search được trong row đã định trươc - 2) Performance không tốt.

Như vậy chúng ta cần một kĩ thuật tìm kiếm khác, tốt hơn LIKE query, mềm dẻo hơn, tốt về performance hơn, đó chính là Full text searchi.

Cơ bản về kĩ thuật Full text search

Về mặt cơ bản, điều làm nên sự khác biệt giữa Full text search và các kĩ thuật search thông thường khác chính là “Inverted Index”. Vậy đầu tiên chúng ta sẽ tìm hiểu về Inverted Index

Inverted Index là gì

Inverted Index là kĩ thuật thay vì index theo đơn vị row(document) giống như mysql thì chúng ta sẽ tiến hành index theo đơn vị term. Cụ thể hơn, Inverted Index là một cấu trúc dữ liệu, nhằm mục đích map giữa term, và các document chứa term đó

1
2
3

D1 = "This is first document"
D2 = "This is second one"
D3 = "one two"

Inverted Index của 3 documents đó sẽ được lưu dưới dạng như sau:

1
2
3
4
5
6
7

"this" => {D1, D2}
"is" => {D1, D2}
"first" => {D1}
"document" => {D1}
"second" => {D2}
"one" => {D2, D3}
"two" => {D3}

Từ ví dụ trên các bạn có thể hình dung được về thế nào là Inverted Index. Vậy việc tạo index theo term như trên có lợi thế nào? Việc đầu tiên là inverted index giúp cho việc tìm kiếm trên full text database trở nên nhanh hơn bao giờ hết. Hãy giả sử bạn muốn query cụm từ “This is first”, thì thay vì việc phải scan từng document một, bài toán tìm kiếm document chứa 3 term trên sẽ trở thành phép toán union của 3 tập hợp (document sets) của 3 term đó trong inverted index.

1

{D1, D2} union {D1, D2} union {D1} = {D1}

Một điểm lợi nữa chính là việc inverted index cực kì flexible trong việc tìm kiếm. Query đầu vào của bạn có thể là “This is first”, “first This is” hay “This first is” thì độ phức tạp tính toán của phép union kia vẫn là không đổi.

Như vậy chúng ta đã hiểu phần nào về khái niệm “Thế nào là Inverted Index”. Trong phần tiếp theo chúng ta sẽ tìm hiểu về cụ thể về cách implement của inverted index, và ứng dụng của inverted index vào việc tìm kiếm thông tin thông qua các kĩ thuật chính như: tokenization technique (thông qua N-Gram hoặc Morphological Analysis), query technique và scoring technique.

Giới thiệu

“Không ngôn ngữ lập trình nào có thể sinh mã chạy nhanh hơn mã assembly được viết cẩn thận”

Đây là điều đã được nói đến rất nhiều tại nhiều diễn đàn và blog công nghệ nhưng hầu như không có ví dụ minh hoạ nào cụ thể?? Để kiểm chứng tuyên bố trên, mình đã thử viết 1 chương trình bằng ngôn ngữ C, sau đó thử optimize chương trình bằng mã assembly, và cuối cùng đo thời gian chạy của 2 phiên bản. Điều mình rút ra là thực sự 1 chương trình assembly chạy nhanh hơn hẳn chương trình C tương tự, đúng như tuyên bố.

Bài viết này viết về quá trình mình kiểm chứng cũng như những điều rút ra từ quá trình này.

Bài toán

Ta sẽ giải quyết bài toán: “biểu diễn tập con bằng số nhị phân”.

Ta có thể biểu diễn tập hợp con của 1 tập hợp bằng 1 chuỗi bit. Ví dụ xét tập hợp 4 phần tử, thì “0101” là 1 tập con. Ta có thể diễn giải chuỗi trên như sau: tập con có sự xuất hiện của phần tử vị trí 0 và 2. Nói 1 cách mình hoạ xét chuỗi ký tự “abcd” thì với chuỗi nhị phân ở trên ta có tập con “bd”.

Bài toán là làm thế nào để liệt kê tất cả các tập con 2 phần tử của tập hợp trên. Nói cách khác liệt kê các xâu có 2 ký tự từ xâu “abcd”

Thuật toán

Ta sẽ sử dụng thuật toán được nghĩ ra bởi Bill Gosper được lưu lại trong HAKMEM số 175 (Hacker Memo) nổi tiếng của phóng thí nghiệm trí tuệ nhân tạo của trường MIT.

Thuật toán như sau: Giả sử có chuỗi bit x = xxx0 1111 0000 (xxx là 1 chuỗi bit 0 bất kỳ). Ta cần tìm cách sinh ra chuỗi bit có số lượng bit 1 không đổi. Nói cách khác kết quả của hàm sinh sẽ từ chuỗi hiện tại phải là xxx1 0000 0111. Các bước sinh diễn ra như sau:

1. Thuật toán bắt đầu bằng cách tìm bit 1 cuối cùng bên phải bằng công thức s = x & -x cho ra kết quả xxx0 0001 0000
2. Cộng kết quả hiện tại với x cho ra kết quả r = xxx1 0000 0000. Bit 1 ở đây là 1 bit trong kết quả.
3. Đối với các bit kết quả còn lại, chúng ta tiến hành điều chỉnh n-1 bit 1, trong đấy n là số lượng bit 1 của nhóm bit 1 nằm bên phải nhất. Cụ thể ở đây là nhóm 1111. Ta có thể làm điều này bằng cách đầu tiên exclusive or (xor) r với x cho kết quả xxx1 1111 0000. Ta chia kết quả này cho s (là luỹ thừa của 2) và dịch kết quả có được thêm 2 vị trí nữa để loại bỏ bit không cần thiết. Kết quả có được là giá trị điểu chỉnh cuối cùng này or với r.

Công thức đại số để tính các bước ở trên như sau:

 s <- x & -x
 y <- s + x
 y <- r | (((x xor r) >> 2) / s)

Chương trình.

Ta sẽ benchmark bằng cách đo thời gian chạy của thuật toán viết bằng ngôn ngữ C và assembly rồi so sánh thời gian chạy của 2 chương trình viết bằng 2 ngôn ngữ với nhau.

Chương trình viết bằng C

Để benchmark ta viết chương trình C biểu diễn thuật toán trên. binreprlà hàm giúp in giá trị nhị phân giúp quá trình kiểm tra được dễ dàng hơn. Nội dung thuật toán được viết trong hàm snoob_c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <stdio.h>

void binrepr(unsigned a) {
    char r[32] = {0};
    int i;
    for (i = 0; i < 32; ++i) {
        r[31 - i] = ((a >> i) & 1) + '0';
    }
    puts(r);
}

unsigned snoob_c(unsigned x)
{
        unsigned smallest, ripple, ones;

        smallest = x & -x;
        ripple = x + smallest;
        ones = x ^ ripple;
        ones = (ones >> 2) / smallest;
        return ripple | ones;
}

int main()
{
    int a, b;
    scanf("%d", &a);
    binrepr(a);
    b = snoob_c(a);
    binrepr(b);
    return 0;
}

$ gcc -o snoob snoob.c
$ ./snoob
752
00000000000000000000001011110000
00000000000000000000001100000111

Tuyệt thuật toán chạy đúng! Ta sẽ cho thuật toán trên chạy 100 000 000 lần và đo tổng thời gian. Ta sửa lại hàm main như dưới đây:

1
2
3
4
5
6
7
8
9
10

int main()
{
    int a, b;
  int i;
  a = 752;
    for (i = 0; i < 100000000; ++i) {
        b = snoob_c(a);
    }
    return 0;
}

$ gcc -o snoob snoob.c
$ time ./snoob
./snoob  0.83s user 0.00s system 99% cpu 0.832 total

Chương trình chạy 100 triệu lần hết 0.83s! C quả thực rất nhanh.

Chương trình viết bằng assembly

Để có thể optimize hàm snoob, ta sẽ thử quan sát mã assembly của hàm snoob_c do gcc sinh ra:

$ gdb snoob
(gdb) disassemble snoob_c
Dump of assembler code for function snoob_c:
0x0000000100000e20 <snoob_c+0>: push   rbp
0x0000000100000e21 <snoob_c+1>: mov    rbp,rsp
0x0000000100000e24 <snoob_c+4>: mov    DWORD PTR [rbp-0x4],edi
0x0000000100000e27 <snoob_c+7>: mov    eax,DWORD PTR [rbp-0x4]
0x0000000100000e2a <snoob_c+10>:        mov    ecx,0x0
0x0000000100000e2f <snoob_c+15>:        sub    ecx,eax
0x0000000100000e31 <snoob_c+17>:        mov    eax,DWORD PTR [rbp-0x4]
0x0000000100000e34 <snoob_c+20>:        and    ecx,eax
0x0000000100000e36 <snoob_c+22>:        mov    DWORD PTR [rbp-0x10],ecx
0x0000000100000e39 <snoob_c+25>:        mov    eax,DWORD PTR [rbp-0x4]
0x0000000100000e3c <snoob_c+28>:        mov    ecx,DWORD PTR [rbp-0x10]
0x0000000100000e3f <snoob_c+31>:        add    eax,ecx
0x0000000100000e41 <snoob_c+33>:        mov    DWORD PTR [rbp-0x14],eax
0x0000000100000e44 <snoob_c+36>:        mov    eax,DWORD PTR [rbp-0x4]
0x0000000100000e47 <snoob_c+39>:        mov    ecx,DWORD PTR [rbp-0x14]
0x0000000100000e4a <snoob_c+42>:        xor    eax,ecx
0x0000000100000e4c <snoob_c+44>:        mov    DWORD PTR [rbp-0x18],eax
0x0000000100000e4f <snoob_c+47>:        mov    eax,DWORD PTR [rbp-0x18]
0x0000000100000e52 <snoob_c+50>:        shr    eax,0x2
0x0000000100000e55 <snoob_c+53>:        mov    ecx,DWORD PTR [rbp-0x10]
0x0000000100000e58 <snoob_c+56>:        xor    edx,edx
0x0000000100000e5a <snoob_c+58>:        div    ecx
0x0000000100000e5c <snoob_c+60>:        mov    DWORD PTR [rbp-0x18],eax
0x0000000100000e5f <snoob_c+63>:        mov    ecx,DWORD PTR [rbp-0x14]
0x0000000100000e62 <snoob_c+66>:        or     ecx,eax
0x0000000100000e64 <snoob_c+68>:        mov    DWORD PTR [rbp-0xc],ecx
0x0000000100000e67 <snoob_c+71>:        mov    DWORD PTR [rbp-0x8],ecx
0x0000000100000e6a <snoob_c+74>:        mov    eax,DWORD PTR [rbp-0x8]
0x0000000100000e6d <snoob_c+77>:        pop    rbp
0x0000000100000e6e <snoob_c+78>:        ret
0x0000000100000e6f <snoob_c+79>:        nop
End of assembler dump.
(gdb)

Quan sát mã assembly ta có vài nhận xét sau:

• Mã rất dài. Bên cạnh các instruction dùng để tính toán, các instruction dùng để di chuyển dữ liệu cũng chiếm khá nhiều thời gian chạy.
• Các kết quả tính toán trung gian được ghi ra bộ nhớ (do ta dùng các biến smalless, ripples, ones)

Theo như “con số về độ trễ mà mọi lập trình viên nên biết”, thì truy cập bộ nhớ / cache dù rất nhanh (tốn 0.5ns) vẫn chậm hơn rất nhiều so với truy cập trực tiếp từ thanh ghi. Ta đặt câu hỏi liệu có thể giảm thiểu lượt truy cập bộ nhớ cache được không?

Quay trở lại thuật toán, ta thấy công thức đại số dùng 6 phép tính. Số lượng biến sử dụng chỉ có 4 biến. Do đó ta hoàn toàn có thể loại bổ các truy cập bộ nhớ, tính toán trực tiếp bằng các thanh ghi. Ta có hàm snoob viết bằng assembly như sau:

section .text
                global _snoob

;;; HAK Item 175
_snoob:
                push ebp
                mov ebp, esp
                mov ecx, [ebp + 8]
                mov ebx, ecx
                mov eax, ecx
                neg ebx
                and ebx, ecx
                add eax, ebx
                mov edi, eax
                xor eax, ecx
                shr eax, 2
                xor edx, edx
                div ebx
                or eax, edi
                pop ebp

Ta thay code hàm main thay vì gọi đến snoob_c ta gọi đến hàm snoob ở trên:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <stdio.h>

extern unsigned snoob(unsigned a);

void binrepr(unsigned a) {
    char r[32] = {0};
    int i;
    for (i = 0; i < 32; ++i) {
        r[31 - i] = ((a >> i) & 1) + '0';
    }
    puts(r);
}

int main()
{
    int a, b;
    scanf("%d", &a);
    binrepr(a);
    b = snoob(a);
    binrepr(b);
    return 0;
}

$ yasm -a x86 -f macho binrepr.asm
$ gcc -m32 -c snoob.c
$ gcc -m32 -o snoob snoob.o binrepr.o
$ ./snoob
752
00000000000000000000001011110000
00000000000000000000001100000111

Chương trình chạy đúng! Giờ đến phẩn benchmark. Ta sử dụng lại đoạn code benchmark, lần này thay vì gọi hàm snoob_c ta gọi hàm snoob viết bằng assembly. Ta có kết quả như sau:

$ gcc -m32 -c snoob.c
$ gcc -m32 -o snoob snoob.o binrepr.o
$ time ./snoob
./snoob  0.53s user 0.00s system 99% cpu 0.536 total

Ta có thể thấy tốc độ thay đổi 1 cách đáng kể! Thời gian chạy chỉ bằng 63.85% thời gian chạy lần trước đấy.

※Các đoạn code được chạy trên máy tính có phần cứng: cpu corei7, 8G Ram

Kết luận

• Bằng việc trực tiếp kiểm chứng, ta công nhận rằng mã viết bằng assembly nếu được optimize cẩn thận sẽ chạy nhanh hơn hẳn mã sinh bởi các ngôn ngữ bậc cao như C.
• Assembly rất thú vị. Ta có cảm giác kiểm soát toàn bộ máy tính!

Tham khảo

1. Hacker Delights
2. HAKMEM