Vài câu hỏi rất quan trọng

[binhlt]

Tôi đang viết một chương trình khá phức tạp trên dsPic30F3013 (24K Flash, 2k RAM) hiện nay vì mã lệnh đã khá lớn và thời gian tính toán chưa đạt được mức cho phép nên cần phải tối ưu nhiều từ đó xuất hiện vài vấn đề cần hỏi mong các bạn đã có kinh nghiệm chỉ bảo thêm:

1: Giả sử tôi có 1 chương trình rất đơn giản như sau:

const char B[]={0,1,2,3,4,5,6,7,8,9};
short k;

int main(void)
{
while (1)
{
k++;
}
}
như bạn thấy mảng B chỉ 10 byte nhưng khi kiểm tra lại tôi thấy mảng B chiếm 5 intructions tức là mất 5*3 = 15 byte. Từ đó có thể thấy rằng nếu lưu mảng vào trong bộ nhớ chương trình thì bỏ phí mất 1/3 dung lượng.
Vậy câu hỏi là có cách nào lưu trữ mảng vào bộ nhớ mà không để phí không?

2: Chương trình hiện tại tôi viết hiện đã chiếm 1998 byte RAM như vậy lượng RAM trống còn lại rất ít. Câu hỏi ở đây là lượng RAM đo bằng chương trình đó có thể tin cậy 100% không? Liệu khi chạy thực tế có thể bị tràn bộ nhớ không?

3: Trong chương trình có nhiều đoạn dùng hàm sin, cos, tan, atan, sqrt, các phép nhân, chia các số 32bit. Nếu sử dụng các hàm sin, cos, tan, atan của C thì tốc độ rất chậm, phép chia cho số 16bit thì có các hàm __builtin_ đã rất hay nhưng chia cho các số 32 bit thì phải dùng mẹo để chuyển về 16 bit nhưng thời gian không khá hơn nhiều. Để tăng tốc tôi đã phải viết khá nhiều hàm sử dụng bảng tra nhưng vẫn chưa ưng ý lắm rất mong các bạn đưa lên diễn đàn nhiều thuật toán hay để làm giảm thời gian tính toán. Như vậy cần các thuật toán nhanh (dùng nội suy kết hợp bảng tra) cho các hàm hay dùng như:
- thuật toán cho hàm sin, cos, tan, atan
- thuật toán cho hàm sqrt
Đối với dsPic còn có các hàm Q15, Q16 nhưng giá trị vào bị bó hẹp trong khoảng -1 đến 0.999 có cách nào để dùng các hàm Q15, Q16 cho các giá trị bình thường không?

4: Cuối cùng trong quá trình sử dụng tôi thấy quyển sách "Hackers Delight" có nhiều phương pháp nhằm tăng tốc rất hay xin được giới thiệu với các bạn trang chủ của nó đây http://www.hackersdelight.org/

[namqn]

Nguyên văn bởi binhlt

Tôi đang viết một chương trình khá phức tạp trên dsPic30F3013 (24K Flash, 2k RAM) hiện nay vì mã lệnh đã khá lớn và thời gian tính toán chưa đạt được mức cho phép nên cần phải tối ưu nhiều từ đó xuất hiện vài vấn đề cần hỏi mong các bạn đã có kinh nghiệm chỉ bảo thêm:

1: Giả sử tôi có 1 chương trình rất đơn giản như sau:

const char B[]={0,1,2,3,4,5,6,7,8,9};
short k;

int main(void)
{
while (1)
{
k++;
}
}
như bạn thấy mảng B chỉ 10 byte nhưng khi kiểm tra lại tôi thấy mảng B chiếm 5 intructions tức là mất 5*3 = 15 byte. Từ đó có thể thấy rằng nếu lưu mảng vào trong bộ nhớ chương trình thì bỏ phí mất 1/3 dung lượng.
Vậy câu hỏi là có cách nào lưu trữ mảng vào bộ nhớ mà không để phí không?

2: Chương trình hiện tại tôi viết hiện đã chiếm 1998 byte RAM như vậy lượng RAM trống còn lại rất ít. Câu hỏi ở đây là lượng RAM đo bằng chương trình đó có thể tin cậy 100% không? Liệu khi chạy thực tế có thể bị tràn bộ nhớ không?

3: Trong chương trình có nhiều đoạn dùng hàm sin, cos, tan, atan, sqrt, các phép nhân, chia các số 32bit. Nếu sử dụng các hàm sin, cos, tan, atan của C thì tốc độ rất chậm, phép chia cho số 16bit thì có các hàm __builtin_ đã rất hay nhưng chia cho các số 32 bit thì phải dùng mẹo để chuyển về 16 bit nhưng thời gian không khá hơn nhiều. Để tăng tốc tôi đã phải viết khá nhiều hàm sử dụng bảng tra nhưng vẫn chưa ưng ý lắm rất mong các bạn đưa lên diễn đàn nhiều thuật toán hay để làm giảm thời gian tính toán. Như vậy cần các thuật toán nhanh (dùng nội suy kết hợp bảng tra) cho các hàm hay dùng như:
- thuật toán cho hàm sin, cos, tan, atan
- thuật toán cho hàm sqrt
Đối với dsPic còn có các hàm Q15, Q16 nhưng giá trị vào bị bó hẹp trong khoảng -1 đến 0.999 có cách nào để dùng các hàm Q15, Q16 cho các giá trị bình thường không?

4: Cuối cùng trong quá trình sử dụng tôi thấy quyển sách "Hackers Delight" có nhiều phương pháp nhằm tăng tốc rất hay xin được giới thiệu với các bạn trang chủ của nó đây http://www.hackersdelight.org/

1. Tôi cho rằng bạn có thể dùng các lệnh về bảng (TBLRDH, TBLRDL, TBLWTH, TBLWTL). Tham khảo các hàm built-in của MPLAB C Compiler for dsPIC DSCs, nếu bạn đang dùng trình biên dịch này. Tôi chưa từng có nhu cầu sử dụng cả 3 byte của 1 từ nhớ chương trình, nên chưa từng thử dùng những hàm này.

2. Tôi cho rằng trình biên dịch rất đáng tin cậy trong việc xác định dung lượng RAM đã được sử dụng.

3. Bạn đã dùng thư viện mới nhất (phiên bản mới nhất) của trình biên dịch chưa? Việc tối ưu các hàm thư viện nên dành cho nhà phát triển trình biên dịch, chứ không nên là công việc của người sử dụng. Bạn đã tham khảo www.piclist.com về những thủ thuật hiện thực các hàm siêu việt chưa?

Thân,

[binhlt]

Cảm ơn namqn tôi mới chỉ bắt đầu làm việc với PIC chừng 1 tháng nay nên còn rất nhiều điều cần phải học hỏi

1: Nói như bạn thì biết chắc là chẳng còn cách nào rồi. Những lệnh đó tôi cũng xem qua và nếu làm theo thì sẽ cần 1 bước để chuẩn bị dữ liệu (nạp vào chẳng hạn) chứ không thể chỉ bằng cách khai báo trực tiếp trong C

2: Nói như bạn nghĩa là cũng chưa có minh chứng gì cụ thể vì vậy mặc dù tôi cũng nghĩ giống bạn nhưng để chắc ăn chắc phải chỉnh lại để RAM cho còn nhiều chỗ trống hơn

3: Trang web bạn đưa giờ tôi mới biết rất cảm ơn bạn. Tôi cũng dùng bản mới nhất rồi nhưng cũng nhận thấy là yêu cầu của mình chắc nhà phát triển không đáp ứng được vì mỗi người khi sử dụng đến những hàm đó sẽ cần đến một sự chính xác khác nhau. Vì thế khi phát triển những hàm đó các nhà phát triển chỉ đi theo 1 con đường duy nhất là chính xác gần tuyệt đối và do đó hàm sin, cos, tan, ... tốn nhiều thời gian hơn những hàm tự phát triển
4: Sau 1 hồi tìm tòi tôi đã có hàm sqrt cực nhanh (tôi có chỉnh 1 chút cho phù hợp với dsPic

inline  short __attribute__((always_inline)) isqrt(unsigned long x)
{static const unsigned char sqq_table[] 
={ 0,  16,  22,  27,  32,  35,  39,  42,  45,  48,  50,  53,  55,  57,
  59,  61,  64,  65,  67,  69,  71,  73,  75,  76,  78,  80,  81,  83,
  84,  86,  87,  89,  90,  91,  93,  94,  96,  97,  98,  99, 101, 102,
 103, 104, 106, 107, 108, 109, 110, 112, 113, 114, 115, 116, 117, 118,
 119, 120, 121, 122, 123, 124, 125, 126, 128, 128, 129, 130, 131, 132,
 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 144, 145,
 146, 147, 148, 149, 150, 150, 151, 152, 153, 154, 155, 155, 156, 157,
 158, 159, 160, 160, 161, 162, 163, 163, 164, 165, 166, 167, 167, 168,
 169, 170, 170, 171, 172, 173, 173, 174, 175, 176, 176, 177, 178, 178,
 179, 180, 181, 181, 182, 183, 183, 184, 185, 185, 186, 187, 187, 188,
 189, 189, 190, 191, 192, 192, 193, 193, 194, 195, 195, 196, 197, 197,
 198, 199, 199, 200, 201, 201, 202, 203, 203, 204, 204, 205, 206, 206,
 207, 208, 208, 209, 209, 210, 211, 211, 212, 212, 213, 214, 214, 215,
 215, 216, 217, 217, 218, 218, 219, 219, 220, 221, 221, 222, 222, 223,
 224, 224, 225, 225, 226, 226, 227, 227, 228, 229, 229, 230, 230, 231,
 231, 232, 232, 233, 234, 234, 235, 235, 236, 236, 237, 237, 238, 238,
 239, 240, 240, 241, 241, 242, 242, 243, 243, 244, 244, 245, 245, 246,
 246, 247, 247, 248, 248, 249, 249, 250, 250, 251, 251, 252, 252, 253,
 253, 254, 254, 255};

    register unsigned long xn;

    if (x >= 0x10000)
        if (x >= 0x1000000)
            if (x >= 0x10000000)
                if (x >= 0x40000000) {
                    if (x >= 65535UL*65535UL)
                        return 65535;
                    xn = sqq_table[x>>24] << 8;
                } else
                    xn = sqq_table[x>>22] << 7;
            else
                if (x >= 0x4000000)
                    xn = sqq_table[x>>20] << 6;
                else
                    xn = sqq_table[x>>18] << 5;
        else {
            if (x >= 0x100000)
                if (x >= 0x400000)
                    xn = sqq_table[x>>16] << 4;
                else
                    xn = sqq_table[x>>14] << 3;
            else
                if (x >= 0x40000)
                    xn = sqq_table[x>>12] << 2;
                else
                    xn = sqq_table[x>>10] << 1;

            goto nr1;
        }
    else
        if (x >= 0x100) {
            if (x >= 0x1000)
                if (x >= 0x4000)
                    xn = (sqq_table[x>>8] >> 0) + 1;
                else
                    xn = (sqq_table[x>>6] >> 1) + 1;
            else
                if (x >= 0x400)
                    xn = (sqq_table[x>>4] >> 2) + 1;
                else
                    xn = (sqq_table[x>>2] >> 3) + 1;

            goto adj;
        } else
            return sqq_table[x] >> 4;

	/* Run two iterations of the standard convergence formula */
    xn = (xn + 1 + __builtin_divud(x, xn)) >> 1;
nr1:
    xn = (xn + 1 + __builtin_divud(x, xn)) >> 1;
adj:
    if (__builtin_muluu(xn, xn) > x) /* Correct rounding if necessary */
       xn--;
    return xn;
}