概述
编写正确且高效的串行程序是困难的，编写正确且高效的并行程序则更加困难
编写的难度随着所利用的并发性粒度的降低而增长。我们在上面看到过，程序员必须注意数据局部性以获取高性能。此外，把一个已有的串行程序并行化的任务是极端困难的。找出程序中的所有依赖关系很困难，当这个程序并不是我们所熟悉的类型时尤其如此
调试一个并行也很困难，因为错误可能是不正确的
在理想情况下，一个并行的编译器自动地把普通的串行程序翻译成高效的并行程序，并对这些程序的局部性进行优化
遗憾的是，编译器并不知道有关这个应用的高层知识，它只能保持原算法的语义，而这些算法未必适合进行并行化。而且，程序员也可能随意地做出选择，结果限制了程序的并行性
一些Fortran数值应用显示了并行性和局部性优化的成功。这些应用以仿射访问的方式对数组进行操作。因为没有指针和指针运算，所以对Fortran的分析相对容易。请注意，不是所有的应用都有仿射访问。最值得注意的是，很多数值应用都是在稀疏矩阵上运算的。这些矩阵的元素通过另一个数组间接访问的。
并行性和局部优化
概述
并行性和局部性优化需要我们考虑一个循环的不同实例以及实例之间的关系。这个情况和数据流分析有着很大的不同。在数据流分析中，我们把所有实例的相关信息组合在一起考虑
对于带有数组访问的循环的优化问题，我们使用三种类型的空间。每个空间可以看成是一维或多维栅格中的点集
迭代空间（iteration space）
迭代空间是在一次计算过程中动态执行实例的集合，也就是各个循环下标的取值的组合
数据空间(data space)
数据空间是被访问的数组元素的集合
处理器空间(processor space)
处理器空间是系统中的处理器集合。通常情况下，这些处理器使用整数或者整数向量进行编号，以便相互区分
优化问题的输入是各个迭代被执行的串行顺序以及一个仿射的数组访问函数(例如， X[i,j+1]). 这个函数描述了迭代空间中的哪个实例访问数据空间中的哪个元素
这个优化的输出也是用仿射函数表示的，它定义了每个处理器在什么时候做什么事情。为了指明每个处理器所做的工作，我们使用一个仿射函数把原迭代空间中的实例映射到各个处理器上。
为了描述什么时候执行迭代，我们使用一个仿射函数把迭代空间中的实例映射成为一个新的顺序。通过分析程序中的数组访问函数所蕴涵的数据依赖关系和复用模式，就可以得到调度方案
例子
这三个空间和它们之间的映射如下:
迭代空间
迭代空间是循环的迭代集合。各个迭代的ID通过循环下标变量的取值给出
一个深度为d的循环嵌套结构(即有d层嵌套的循环)有d个下标变量，因此被建模为一个d维空间
迭代空间通过循环下标变量的上下界来限定。这个例子的循环定义了一个由10个迭代组成的一个一维空间
空间中的迭代用循环下标变量的值: i = 0, 1, …, 9 表示
数据空间
数据空间由数组声明直接给出
在这个例子里，数组中的元素用 a = 0, 1, …, 9作为下标
虽然所有的数组在一个程序的地址空间中线性存放的，我们还是把n维向量当作n维空间处理，并假设各个下标总在它们的界限之内
当然，这个例子里的数组是一维的
处理器空间
在我们开始并行化时，假设系统中无限多个虚拟处理器
这些处理器以多维空间的方式进行组织，每一个维度对应于我们试图并行化的循环嵌套结构中的一个循环。
在并行化完成之后，如果我们拥有的物理处理器少于虚拟处理器，就把虚拟处理器等分成多个块，每一块分配给一个物理处理器
在这个例子中，只需要10个处理器，循环的每一个迭代分配器。在图例中，假设处理器被组织成一个一维空间且用0,1,…9进行编号
循环的第i个迭代被分配给处理器i。假如只有5个处理器，我们可以把迭代0和1分配给处理0，迭代2和3分配给处理器1。以此类推。因为迭代是独立的。所以只要5个处理器的每一个分得两个迭代，我们怎么进行分配并不重要
仿射数组下标函数
代码中的每个数组访问都描述了一个从迭代空间的迭代到数据空间的数组元素的映射
如果这个访问函数是把各个循环下标变量乘以常量并求和，然后加上一些常量值，那么这个函数就是仿射的
在例子中，两个数组下标函数i + 10和i都是仿射的。可以根据访问函数求出被访问数据的维度(dimension)
在本例中，因为每个下标函数只有一个循环变量，所以被访问数组元素的空间是一堆的
仿射分划
我们使用一个仿射函数把一个迭代空间中的各个迭代分配给处理器空间中的各个处理器，由此把一个循环并行化
在例子中，直接把迭代i分配给处理器，也可以使用仿射函数来指定一个新的执行顺序
如果我们希望以相反的顺序串行地执行上面的循环，那么可以用一个仿射表达式10 - i明确指定排序函数
这样，第9个迭代就是被第一个执行的迭代，以此类推
被访问数据的区域
知道一个迭代所访问数据的区域有助于找到最好的仿射划分
把迭代空间的信息和数组下标函数结合起来，就可以得到被访问数据的区域
在本例子中，数组访问 Z[i+10] 触及的空间是{a|10 <= a < 20}， 而数组访问Z[i]触及的空间是{a|0<= a< 10}
数据依赖
为了确定被处理的循环是否可被并行化，需要知道各个迭代之间是否存在数据依赖关系
在这个例子中，首先考虑该循环中的写访问之间的依赖关系。因为访问函数Z[i+10]把不同迭代映射到不同的数组位置，不同迭代向数组写顺序上不存在依赖关系
那么在读访问和写访问之间存在依赖关系吗？因为只有Z[10],Z[11],…,Z[19] (通过访问Z[i+10]) 被写。而只有Z[0],Z[1],…,Z[9] （通过访问Z[i]）被读，因此一个读访问和一个写访问的相对顺序不存在依赖关系
因此，这个循环是可并行化。也就是说，这个循环的各个迭代独立于其他所有迭代，我们可以并行地执行这些迭代，或者按照我们选择的任意顺序执行这些迭代
总结
并并行化问题写成多维空间和这些空间之间的仿射映射使得我们可以使用标准的数学技术来解决并行化和局部优化问题
比如，可以通过使用Fourier-Motzkin 消除算法消除相应的变量，找出被访问数据的区域。已经证明数据依赖性和整数线性规划问题等价
最后，寻找仿射分划的问题则对应于对一组线性约束求解