# 内联汇编的性能：一种基于斐波纳契数列计算的分析

## 简介

• 具有指数时间 (exponential time) 复杂度的递归算法
• 具有线性时间复杂度的动态编程算法
• 具有线性时间复杂度的迭代实现
• 具有对数时间复杂度的优化的矩阵乘方算法

IBM XL 编译器基于用户代码的多维分析来执行高度复杂的优化。为了抵消计算机自动执行的各种优化对相对环境的意外影响，本文的所有编译没有指定任何级别的编译器优化。

## 斐波纳契数列的定义

```F0 = 0
F1 = 1
Fn = F(n-2) + F(n-1)  if n >1
or
F1 = 1
F2 = 1
Fn = F(n-2) + F(n-1)  if n >2```

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11
0 1 1 2 3 5 8 13 21 34 55 89

## 递归算法

```Fib(n):
if n in range [0,1]
return n
else
return Fib(n-2) + Fib(n-1)
end if```

```T(n) = T(n-1) + T(n-2)+ Theta(1)
>= 2 T(n-2)
= Theta(2n/2)```

`long long fib_r(int n){ return n <= 1 ? n : fib_r(n-1) + fib_r(n-2) ; }`

## 动态编程算法

### 动态编程方法的默记法版本

```Mem = { }                                 //Data structure storing computed values
Fib(n):
if n in Mem                       //Return existing value from Memory
return Mem[n]             //Early exit when handling known values
end if
if n if n in range [0,1]                 //Base step of the recursion
fib ? n
else                                    //Recursive steps
fib ?  Fib(n-2) + Fib(n-1)
end if
Mem[n] ? fib                   //Memorize new value
return fib                      //Return the new computed value```

## 动态编程的反向遍历（自底向上）版本

```Fib(n):
Mem = {}                                         //the memory
for k in range [0,1,…,n]                         //traverse bottom-up
if k in range [0,1]                         //compute each term
Mem[k] ? k                             //starting with indices 0 and 1
else:
Mem[k] ? Mem[k-1] + Mem[k-2]           //Retrieve known values
end if
end for
return Mem[n]```

```long long fib_d(int n)
{
int k;
long long memory[n];
for ( k = 0 ; k <= n ; ++k ) {
if ( k <= 1 )
memory[k] = k;
else
memory[k] = memory[k-1] + memory[k-2];
}
return memory[n];
}```

## 迭代算法

##### 图 3. 迭代算法的可视化

```long long fib_i(int n)
{
int k;
long long e0 = 0, e1 = 1, res = 0;
for ( k = 0 ; k <= n ; ++k ) {       //iterate from 0 to n
if ( k <= 1 )
res = k;                      //base case for F0 and F1
else {
res = e0 + e1;               //res is the sum of 2 previous terms
e0 = e1;                     //update the 2 previous terms
e1 = res;                    // -------- ditto --------
}
}
return res;                      //return Fn
}```

## 优化的矩阵乘方算法

##### 图 4. 矩阵乘方算法的数学基础

```void multiply(long long M[2][2], long long N[2][2])
{
long long a =  M[0][0]*N[0][0] + M[0][1]*N[1][0];
long long b =  M[0][0]*N[0][1] + M[0][1]*N[1][1];
long long c =  M[1][0]*N[0][0] + M[1][1]*N[1][0];
long long d =  M[1][0]*N[0][1] + M[1][1]*N[1][1];

M[0][0] = a;
M[0][1] = b;
M[1][0] = c;
M[1][1] = d;
}```

An = A A … A

An = A(n/2) A(n/2)

```void power(long long M[2][2], int n)
{
if( n == 0 || n == 1) return;               //no operation needed for base case
long long A[2][2] = {{1,1},{1,0}};

power(M, n/2);                             //recursively call power on n/2
multiply(M, M);                           //a constant time multiplication

if (n%2 != 0)                             //To handle odd n
multiply(M, A);
}```

```long long fib_m(int n)
{
long long A[2][2] = {{1,1},{1,0}};              //matrix A
if (n == 0)
return 0;                                  //base case F0 = 0
power(A, n-1);                                 //raise A to power (n-1)
return A[0][0];                               //Fn is element (0,0)
}```

## 内联汇编实现

### 算法

##### 图 5. 内联汇编方法的可视化表示

```Fib(n):
load F0 to register 0                              //smaller term in register 0
load F1 to register 1                              //greater term in register 1
for k in range [2,3,…,n]
swap the values in two registers              //register 1 holds smaller term
sum up the values in two register             //sum up 2 terms
store the sum to register 1                   //register 1 holds the sum
end for
return register 1	                              //return the sum```

### 通过三异或运算 ( triple exclusive-or operation) 交换两个值

R0 R1 R0 R1 R0 R1 R0 R1
00 0 0 0 0 00
01 1 1 1 0 10
10 1 0 1 1 01
11 0 1 0 1 11

### 汇编指令

XGR R0, R1：

• 存储在第一个和第二个寄存器中的值的异或结果放在第一个操作数位置 (R0)。
• 存储在第 2 个操作数 (R1) 中的值保持不变。
• 这些操作数和结果的长度为 64 位。

AGR R0, R1：

• 将第二个操作数与第一个操作数相加，将两数的和放在第一个操作数所在的位置上。
• 存储在第 2 个操作数 (R1) 中的值保持不变。
• 这些操作数和结果被视为 64 位有符号二进制整数。

BRCT R0，分支地址：

• 从第一个操作数中减去值 1，将结果放回到第一个操作数位置。
• 结果为 0 时，继续执行正常的指令数列。
• 结果不为 0 时，当前程序状态字 (PSW) 中的指令地址替换为分支地址。

### 内联汇编代码

```long long fib_asm(int upto) {
if ( upto < 2 ) return upto;                 //F0 = 0, F1 = 1
int mycount = upto - 1;
long long f0 = 0L, f1 = 1L;
asm ( "0:                 \n"                  //back to this when mycount > 0
"XGR   %0, %1       \n"                  //1st XOR
"XGR   %1, %0       \n"                  //2nd XOR
"XGR   %0, %1       \n"                  //3rd XOR
"AGR   %1, %0       \n"                  //Add 2 terms, store to f1
"BRCT  %2, 0b       \n"                  //back to 0 if mycount > 0
:"+r"(f0), "+r"(f1), "+r"(mycount)
);
return f1;                                     //return f1
}```

## 测试程序

volatile clock_t start、end

volatile float elapsedASM、elapsedI、elapsedR、elapsedM、elapsedD；

```   start = clock();
while ( myCount-- ) { resASM = fib_asm(limit); }
end = clock();
elapsedASM =  ((float) (end - start))*1000 / CLOCKS_PER_SEC ;```

## 参考资料

#### 下载资源

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=10
Zone=Linux
ArticleID=1023791
ArticleTitle=内联汇编的性能：一种基于斐波纳契数列计算的分析
publish-date=12102015