浮点运算和代码优化

1.浮点运算问题

浮点运算在工业中应用非常广泛，但嵌入式CPU通常没有对浮点运算提供直接的硬件支持。而采用标准库提供的软件计算方案，性能又很差。这时就需要使用浮点运算协处理器加速浮点运算。（486之前的PC，CPU和浮点运算协处理器FPU也是分开的，例如i486DX是有FPU的型号，而i486SX则是没有FPU的型号。）

硬件的支持离不开软件的使用。如果在添加了FPU的硬件上，使用浮点计算的软件方案的话，FPU也是不起作用的。因此必须用FPU驱动库函数替换标准库提供的软件方案的相应函数。

最直观的做法是将所有用到浮点计算的地方都替换成FPU函数。例如如下代码：

float a,b,c;
a = b + c;

假设FPU加法函数的原型为：

float Add(float a, float b);

如果我们要使用FPU硬件加速的话，只需要将上述代码改为：

float a,b,c;
a = Add(b,c);

就可以了。

上面的这种方法显然是直观而正确的，但是却不方便。需要将源代码中，所有涉及到浮点运算的地方都做相应的修改，而且以函数的方式取代C语言中的运算符，本身书写起来也很麻烦。

我们可以这样思考一下，C语言是如何将运算符转换成机器指令的呢？首先编译阶段肯定要做类型判断，整数加法和浮点数加法的指令显然不会相同。而链接阶段，只有符号表的概念，类型也好、运算符也好，都灰飞烟灭了。

因此，我们只要看一看浮点加法的汇编指令，就可以找到相关的符号表了。经查浮点加法对应的符号是__adddf3（gcc下）。因此它的原型就是：

float64 __adddf3(float64 x, float64 y)

将FPU函数写成这个样子，然后在链接阶段替换标准库函数就可以了。具体操作如下：

1.使用nm命令查看libgcc.a中的符号表，可以查到__adddf3在_addsub_df.o中。

2.使用ar -d从libgcc.a中去掉_addsub_df.o。

3.在链接时使用FPU函数库

2.立即数计算量的问题

请看以下代码：

float64 a, b,c;
a = 2 * PI * (b - c) / 365.25;

机器执行这段代码会进行几次运算呢？

答案是3次。虽然有4个运算符，但2*PI是在编译阶段运算的。（这可以通过查看生成的汇编代码来验证。）基于同样的理由，我们还可以改进这段代码：

a = 2*PI / 365.25 * (b - c);

这样只需要2次运算了。

需要说明的是括号如果不改变运算的顺序的话，是不会改变计算次数的。因此

a = (2*PI / 365.25) * (b - c);

a = 2*PI / 365.25 * (b - c);

是等效的，都只需要2次运算。

3.冗余代码的问题

假设我们定义了a函数，但是在其他地方并未使用该函数，我们是否可以认为a函数的代码不会出现在最终的可执行文件中呢？

这个问题至少在gcc没有设置任何参数时，是否定的。不管a函数使用与否，它的代码都会包含在最终的可执行文件中。

对于PC来说，这不是个太大的问题，但对于嵌入式设备来说，任何空间的浪费都是不可接受的。

写到这里，有人会说，使用gcc的-o2选项优化代码，不就可以了吗？遗憾的是，这是不行的。

-o2有什么作用呢？还是上面的例子：

void main()
{
  float64 a, b,c;
  a = 2 * PI * (b - c) / 365.25;
}

如果是-o2选项的话，机器会进行几次运算呢？

答案是0次。这种不涉及到输出结果的计算，直接被忽略掉了。

回到第一个问题。如何做才能在最终的可执行文件中不包含未使用的函数呢？步骤如下：

1.gcc添加-ffunction-sections选项。我们通常的做法是一个.c文件编译生成一个.o文件。而这个.c文件中的函数代码都会包含在.o文件的.text段（section）中。而-ffunction-sections选项会将每个函数放在单独的段中，例如a函数，会被放到.text.a段中。

2.ld添加–gc-sections选项。这个选项的作用是不链接未使用的段。

从上面的步骤可以看出，链接的最小单位既不是.o文件，也不是单个函数，而是段。

使用以上方法生成的程序，理论上没什么问题，但实际中，还是有不方便之处：为每一个函数生成一个段，可以想象可执行文件中会有多少段，而在某些平台上，代码在段之间的跳转是要比段内跳转消耗资源的。

我们可以在链接脚本中合并这些段，以下是一个简单的实例：

.text :
{
  . = ALIGN(4);
  text_start = .;
  *(.text.*)
  . = ALIGN(4);
  text_end = .;
}

并行计算的必要性：

美国Sandia国家实验室一项模拟测试证明：由于存储机制和内存带宽的限制，16核、32核甚至64核处理器对于超级计算机来说，不仅不能带来性能提升，甚至可能导致效率的大幅度下降。必须研究并行计算的算法，才能有效克服这些缺陷。

最早的并行计算项目是斯坦福大学的BrookGPU：

http://graphics.stanford.edu/projects/brookgpu/

科学家们很早就意识到GPU进行通用数值计算的可行性。然而GPU从创建之初，就主要针对图形渲染，早期的通用计算需要通过很复杂的处理，才能安排到GPU的pipeline中进行运算。BrookGPU的作用就是给通用数值计算提供一个相对简单的接口。

随着GPU厂商逐渐意识到通用数值计算的重要性，并陆续提出了一些新框架。BrookGPU项目也就过时了。

常见并行计算框架

其他的并行计算框架还有：OpenACC、AMD stream、PGI。

OpenCL vs CUDA

OpenMp

https://github.com/lapesd/libgomp

集群可以很好解决单节点计算力不足的问题，但在集群中大规模的数据交换是很耗费时间的，因此需要一种在多节点的情况下能快速进行数据交流的标准，这就是Message passing interface(MPI)。

MPI的主流实现主要是：mpich和openmpi。

https://zhuanlan.zhihu.com/p/69497154

高性能计算–mpi

http://blog.csdn.net/augusdi/article/details/12833235

这是一篇转帖的CUDA教程，原帖比较分散，不好看。

稀疏矩阵的存储

Dictionary of keys (DOK)

这种方法是最直观，也最容易想到的：将非零元素用{(row, column): value}的形式保存。

List of lists (LIL)

一行数据就是一个list，这样每个数据只需要保存column index和value即可。

Coordinate list (COO)

这个方法在DOK的基础上，给同一行的元素建立行索引，给同一列的元素建立列索引。显然DOK适用于硬盘存储，而LIL和COO更适合内存存储，因为后者更需要元素访问的便利性。

Compressed sparse row (CSR, CRS or Yale format)

[0 0 0 0
5 8 0 0
0 0 3 0
0 6 0 0]

A  = [ 5 8 3 6 ]
JA = [ 0 1 2 1 ]
IA = [ 0 0 2 3 4 ]

其中，A是非零元素的value，JA是非零元素的column index。

IA是每行的非零元素在A的offset（类似于文件操作中的游标）。比如第一行没有非零元素，因此第一行的offset为0，第二行也为0。但是第二行有两个非零元素，因此第三行的offset需要+2。依此类推。

按照这个规则，可以看出A和JA中的元素个数相等，而IA的元素个数=行数+1。由于IA的最后一个元素必然和A中的元素个数相等（矩阵都遍历完了，offset当然到末尾了），因此有时也会把它省略。

Optimizer软件

在前ML时代，工业界已经有不少Optimizer软件用于求解凸优化问题，这些软件从原理上基本都属于传统统计学的范畴。

比较知名的Optimizer软件有：CPlex, Gurobi, Mosek, cvx, LINGO。

https://mp.weixin.qq.com/s/kdfGUzY6KnI3tpcDg0GX6w

运筹优化问题求解工具Lingo

https://mp.weixin.qq.com/s/ooYg7-pI9axo8Z_vUwMGzg

离散优化求解器大搜罗

https://mp.weixin.qq.com/s/_uGNwcvsIpzQyH6fI_HIPw

MOSEK，一个专注而卓越的优化求解器（一）

https://mp.weixin.qq.com/s/q0x9pXz7p7OciWqBOIV5JQ

XPROG: 简单实用的鲁棒优化(RO, DRO)编程语言

https://mp.weixin.qq.com/s/wJAt-RqmsoyECLGgdlH6RA

基于数据的分布式鲁棒优化算法及其应用

Zookeeper

http://zookeeper.apache.org/

bin/zkServer.sh status

http://www.cnblogs.com/lpshou/archive/2013/06/14/3136904.html

zookeeper原理

https://mp.weixin.qq.com/s/WPyJC4nyLQGWk-OQylUHHw

Zookeeper简单介绍

http://www.ibm.com/developerworks/cn/opensource/os-cn-zookeeper/index.html

分布式服务框架Zookeeper–管理分布式环境中的数据

https://mp.weixin.qq.com/s/uMj3JEhgyYw4CaIhP1-GTQ

阿里巴巴为什么不用ZooKeeper做服务发现？

https://mp.weixin.qq.com/s/KFzJAxL_xvrrjhubd7zH-Q

Facebook为何放弃ZooKeeper转用自研配置管理系统？

https://mp.weixin.qq.com/s/DigeE4YxuT55cSeyb1q1tQ

ZooKeeper源码和实践揭秘

https://mp.weixin.qq.com/s/Tb670Jdt4s7CKzGZZQRL_A

用大白话给你解释Zookeeper的选举机制

https://mp.weixin.qq.com/s/BejPSfvEe98nSch81WKgAg

Zookeeper九个问题

https://mp.weixin.qq.com/s/03A4LnDqNhNgQ5bSRIgR_Q

一举拿下高可用与分布式协调系统设计