实验题目：
 
OPT算法实验
 
实验内容：
 
已知页面访问序列，采用OPT页面置换算法，求缺页次数、页面置换次数和缺页率。
 
实验目的：
 
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
 
实验原理：问题分析及算法设计（流程图）
 
 
实验源代码：
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int toNextPageLen[50];//当前页面位置下一次被访问的位置,下标为当前页面位置,值为下一次访问位置 
//OPT算法 
void OPT(int page_access[],int PBC,int PAC,int result[][50]){
	int k = 0;
	int nextPageAccessIndex[50];//存储当前页面的位置,作为该页面上一次被访问的下一次访问位置 ,下标为页面,值为下一次访问位置 
	memset(nextPageAccessIndex,0,sizeof(nextPageAccessIndex));//初始化为0,代表没再访问过 
	//1.获取当前位置页面下次访问该页面的位置 
	for(int i = PAC-1; i>=0; i--){
		int nextIndex = nextPageAccessIndex[page_access[i]]; 
		if(nextIndex <= 0){//没在访问过则位置设为无穷 
			toNextPageLen[i] = INT_MAX;
		}else{
			toNextPageLen[i] =  nextIndex;
		}
		nextPageAccessIndex[page_access[i]] = i;
	}
	
	//2.计算每一次访问的每个物理块存放的当前页面 
	int flagBlock[50];//存储页面是否在物理块中,用于去重,下标为页面,值为访问位置 
	memset(flagBlock,-1,sizeof(flagBlock));//不存在物理块中为-1 
	for(int i = 0 ; i < PAC; i++){//遍历访问位置 
		int len = 0;//存储下一次访问该页的最大长度 
		int block = -1;//要替换的物理块中页面 
		
		if(flagBlock[page_access[i]]!=-1){//如果存在物理块中,直接复制前一次数据 
			for(int j = 0; j < k; j++){
				result[j][i] = result[j][i-1];
			}
			flagBlock[page_access[i]] = i; 
			continue;
		}
		for(int j = 0; j < PBC; j++){//遍历物理块 
			if(k < PBC){//如果当前使用的物理块数少于总共物理块数,复制上一次访问页面,在剩下的物理块中添加当前页面 
				if(j == k){//如果为新的物理块,直接存储当前页面 
					result[k][i] = page_access[i];//存储当前页面 
					flagBlock[page_access[i]] = i;// 标记为存在物理块中 
					k++; //使用的物理块数+1
					result[PBC][i] = 1;  //判断是否缺页,有增加则缺页 
					break;
				}else{//复制上一次的页面 
					result[j][i] = result[j][i-1];
				}
			}else{//如果物理块满 
				result[j][i] = result[j][i-1];//复制上一次页面 
				int s = toNextPageLen[flagBlock[result[j][i-1]]]-i;
			
				if(len < s){//找到下次访问最长页面替换 ,即判断物理块中页面 上次的下标 的下一次访问位置减去当前位置,得到距离长度 
					block = j;
					len = s;
				}
			}
		}
		if(block!=-1){
			flagBlock[result[block][i]] = -1;
			flagBlock[page_access[i]] = i;
			result[block][i] = page_access[i];//替换下次访问最长的页面 
			result[PBC][i] = 1;
		}
	}
}
int main(){
	int PBC;//物理块数 physical block count 
	int PAC;//页面访问次数 Page access count 
	int page_access[50];//存储访问的页面,下标代表第几次访问 
	int result[50][50];//0~PBC-1行0~PAC-1列代表每个物理块存储每次访问的页面,PBC行存储是否缺页,是为1,否为0 
	memset(result, -1, sizeof(result)); 
	printf("请输入物理块数:"); 
	scanf("%d",&PBC);
	printf("请输入访问次数:"); 
	scanf("%d",&PAC);
	for(int i = 0 ; i < PAC; i++){
		printf("请输入第%d次访问的页面:",i+1);
		scanf("%d",&page_access[i]); 
	}
	
	//OPT 
	OPT(page_access, PBC, PAC, result);
	
	//输出 
	printf("\n\n页面访问\t");
	for(int i = 0 ; i < PAC; i++){
		printf("%d\t",page_access[i]);
	}
	printf("\n");
	for(int i = 0; i < PBC; i++){
		printf("物理块%d\t\t",i+1);
		for(int j = 0; j < PAC; j++){
			if(result[i][j]!=-1&&result[PBC][j]!=-1){
				printf("%d\t",result[i][j]);
			}else{
				printf("\t");
			}
		}
		printf("\n");
	}
	int lack_page_number = 0;//缺页次数 
	printf("是否缺页\t");
	for(int i = 0; i < PAC; i++){
		printf("%c\t",result[PBC][i]==1?'Y':'N');
		if(result[PBC][i]==1)lack_page_number++;
	} 
	printf("\n"); 
	
	int exchange_numbber = lack_page_number - PBC;
	double lack_page_rate = lack_page_number/(double)PAC;
	printf("缺页次数: %d\n", lack_page_number);
	printf("置换次数: %d\n",exchange_numbber);
	printf("缺页率: %0.2lf%%\n",lack_page_rate) ;

}
/*
3
12
2
3
2
1
5
2
4
5
3
2 
5 
2

3
20
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
*/
 
实验结果：（截图）
 
 
实验总结：（心得体会）
 
通过此次实验，我熟练掌握了几种页面置换算法，自己独立写出了OPT算法的代码实现，对虚拟存储技术的特点有了更深的了解。

题目
 
实验三 请求调页存储管理方式的模拟
 1．实验目的
 通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
 2．实验内容
 （1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。
 （2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
 （3）置换算法：采用先进先出（FIFO）、最近最久未使用（LRU）和最佳置换（OPT）算法置换算法。
 （4）通过随机数产生一个指令序列，共320条指令。
 1）指令的地址按下述原则生成：
 ① 50%的指令是顺序执行的；
 ② 25%的指令是均匀分布在前地址部分；
 ③ 25%的指令是均匀分布在后地址部分；
 具体的实施方法是：
 ① 在[0，319]的指令地址之间随机选取一起点m；
 ② 顺序执行一条指令，即执行序号为m+1的指令；
 ③ 在前地址[0，m-1]中随机选取一条指令并执行，该指令的序号为m1；
 ④ 顺序执行一条指令，其序号为m1+1的指令；
 ⑤ 在后地址[m1+2，319]中随机选取一条指令并执行,该指令的序号为m2；
 ⑥ 顺序执行一条指令，其序号为m2+1的指令；
 重复上述步骤①～⑥，直到执行320次指令。
 2）将指令序列变换为页地址流
 设页面大小为1K， 用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
 第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
 第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
 ……
 ……
 第310条～第319条指令为第31页（对应虚存地址为[310，319]）。
 按以上方式，用户指令可组成32页。
 3.思考
 （1）如果增加分配给作业的内存块数，将会对作业运行过程中的缺页产生什么影响？
 （2）为什么一般情况下，LRU具有比FIFO更好的性能？
 
首先要注意的是，实验文档那个获取随机指令的方法非常糟糕，很多种情况会导致程序奔溃或者获得的指令不在范围内，需要特判。
 
FIFO算法
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320;

typedef struct Node{
    int a[10];
    bool is_empty = true;
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int head = 0;
int tail = 0;
int instruction[maxn_n];    ///指令

int search(int id){
    for(int i = 0; i < maxn; i++){
        if(!block[i].is_empty){
            for(int j = 0; j < 10; j++){
                if(block[i].a[j] == id){
                    return 0 * printf("已存在，物理地址为：%d\n", i * 10 + j);
                }
            }
        }
    }
    return -1;
}

void adjust(int id){
    if(tail < maxn){
        block[tail].is_empty = false;
        for(int i = 0; i < 10; i++){
            block[tail].a[i] = id / 10 * 10 + i;

        }
        printf("调入内存后物理地址为：%d\n", tail * 10 + id % 10);
        tail++;
    }else{
        for(int i = 0; i < 10; i++){
            block[head].a[i] = id / 10 * 10 + i;
        }
        printf("调入内存后物理地址为：%d\n", head * 10 + id % 10);
        head = (head + 1) % maxn;
    }
}

void solve(int id){
    if(search(id) == -1){
        cnt++;
        adjust(id);
    }
}

int main(){
    srand(int(time(0)));
    int n = 320;
    int cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    for(int i = 0; i < 320; i++){
        solve(instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / 320);
    return 0;
}
 
LRU算法
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;

int cnt;                ///发生缺页的次数
int now_time;           ///当前时间
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;

typedef struct Node{
    int id;                 ///块序号
    int a[10];
    int passage = -1;       ///页
    int recent_time = -1;   ///上次使用的时间，越大说明越接近现在我们所处的时间
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int instruction[maxn_n];    ///指令

bool search(int id, int passage){
    for(int i = 0; i < maxn; i++){
        if(block[i].passage == passage){
            block[i].recent_time = now_time;
            printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);
            return true;
        }
    }
    return false;
}

bool cmp(Node a, Node b){
    return a.recent_time < b.recent_time;///从小到大排序，小的离现在最久远
}

void adjust(int id, int passage){
    sort(block, block + maxn, cmp);
    for(int i = 0; i < 10; i++){
        block[0].a[i] = id / 10 * 10 + i;
    }
    block[0].passage = passage;
    block[0].recent_time = now_time;
    printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);
}

void solve(int id){
    if(!search(id, id / 10)){///找不到该页
        cnt++;
        adjust(id, id / 10);
    }
    now_time++;
}

int main(){
    srand(int(time(0)));
    int n = 320, cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    for(int i = 0; i < maxn; i++){
        block[i].id = i;
    }
    for(int i = 0; i < n; i++){
        solve(instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / n);
    return 0;
}
 
OPT算法
 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <time.h>
using namespace std;
int now;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;
const int INF = 0x3f3f3f3f;

typedef struct Node{
    int id;                 ///块序号
    int a[10];
    int passage = -1;       ///页
    int next_use = INF;     ///这个页面下次要用到的位置
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面

int next_use[maxn];         ///第i条指令所处的页面下次要使用到的位置
int instruction[maxn_n];    ///指令

bool search(int pos, int id, int passage){
    for(int i = 0; i < maxn; i++){
        if(block[i].passage == passage){
            block[i].next_use = next_use[pos];
            printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);
            return true;
        }
    }
    return false;
}

bool cmp(Node a, Node b){
    return a.next_use - now > b.next_use - now;///大到小排序，最晚用到的替代掉
}

void adjust(int pos,int id, int passage){
    sort(block, block + maxn, cmp);
    if(block[3].next_use - pos <= 0){
        for(int i = 0; i < 10; i++){
        block[3].a[i] = id / 10 * 10 + i;
        }
        block[3].passage = passage;
        block[3].next_use = next_use[pos];
        printf("调入内存后，物理地址为：%d\n", block[3].id * 10 + id % 10);
    }
    else
    {
        for(int i = 0; i < 10; i++){
            block[0].a[i] = id / 10 * 10 + i;
        }
        block[0].passage = passage;
        block[0].next_use = next_use[pos];
        printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);
    }
}

void solve(int pos, int id){
    if(!search(pos, id, id / 10)){///找不到该页
        cnt++;
        adjust(pos, id, id / 10);
    }
}

int main(){
    srand(int(time(0)));
    int n = 320, cnt_n = 0;
    while(cnt_n < 320){
        int m = rand() % n;
        instruction[cnt_n++] = m + 1;

        if(m == 0)
            continue;
        int m1 = rand() % m;
        if(m1 + 1 >= n)
            continue;
        instruction[cnt_n++] = m1;
        instruction[cnt_n++] = m1 + 1;

        if(n - m1 - 2 <= 0)
            continue;
        int m2 = rand() % (n - m1 - 2) + m1 + 2;
        instruction[cnt_n++] = m2;
        instruction[cnt_n++] = m2 + 1;
    }
    //预处理出多久后会再使用
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j <= n; j++){
            if(j == n){
                next_use[i] = INF;
                break;
            }
            if(instruction[i] >= instruction[j] / 10 * 10 && instruction[i] < (instruction[j] / 10 + 1) * 10){
                next_use[i] = j;
                break;
            }
        }
    }
    for(int i = 0; i < maxn; i++){
        block[i].id = i;
    }
    for(int i = 0; i < n; i++){
        now = i;
        solve(i, instruction[i]);
    }
    printf("缺页次数为：%d\n", cnt);
    printf("缺页率为：%f\n", 1.0 * cnt / n);
    return 0;
}

目录
 
一、算法简介
 
二、连接重组方式
 
三、代码实现
 
1.预先生成所有组合
 
2.计算不同连接方式下的路径距离
 
3.选择最优连接方式
 
四、复杂度分析
 
五.不足之处
 
六.代码分享
 

一、算法简介
 
    3-opt算法是一种针对TSP问题的局部搜索算法，通过选取路径中不相邻的三个节点之间的连接删除，然后尝试其他7种不同连接方式，并计算不同连接方式之后的路径长度，选取路径长度最短的连接方式作为新的连接方式。对于路径种不同的三个连接重复次过程，直到所有的三个连接都没有新的连接方式。
 
二、连接重组方式
 
 
三、代码实现
 
1.预先生成所有组合
 
 
2.计算不同连接方式下的路径距离
 
 
3.选择最优连接方式
 
 
四、复杂度分析
 
    在单次执行3选择具有时间复杂性,
 
五.不足之处
 
    在预先生成左右组合时，并没有去除相同三条链接，如果去除运行速度可能会更快一点
 
六.代码分享
 
    分享了一个动态展示算法运行过程的代码，下载链接

旅行商问题2-OPT算法的并行与优化
 
 
 
GCC-6.2.0
 
 
OpenMPI/2.0.0
 
 
OpenMp 4.5 (2015-11)
 
 
本文代码下载
 
介绍
 
废话不多说，查阅下面链接。
 
 
 
旅行商问题-百度百科
 
 
2-OPT贪心算法-百度百科
 
 
串行2-OPT的思路如下：
 
假如我们有{0, 1, 2, 3, 4, 5}这5个城市，初始路线为
 
0-1-2-3-4-5-0。我们通过两个指针i和k各指向一个城市进行遍历。每次遍历，我们会尝试对当前的**(i,k)对**做一次2optSwap（后面简称reverse），将ik之间的路线反转。
 
这个操作将会重复，直到我们无法找到更短的路径，我们便找到了局部最优解，也就是最终的结果。
 
例如我们遍历到i=1, k=3。我们对这个(i,k)对进行一次reverse，得到一个新路线：0-3-2-1-4-5-0，如果新路线可以比之前的路线更短，我们就记下当前的i和k，以及reverse之后能缩短的距离。然后我们继续遍历，最后选择最短的那一条结果进行reverse。
这里原版的串行化2-opt会在找到第一个可以缩短路径的(i, k)之后马上reverse，然后将i和k设为初始值（i=1,k=2）从头开始遍历，并不会每次遍历所有城市然后取当前的最优解。如果使用原版，我们将无法对比并行优化的结果，因为每次的跳转完全随机且取决于具体的数据。
在计算新旧路线的距离差时有一个细节，即我们不需要计算路线的总长。以上面i=1,k=3为例，我们只需要计算distance(0, 1), distance(0, 3), distance(1, 4), distance(3, 4)。而其他路线是不变的。
 
2-opt-WikiPedia的伪代码，
 
//最直观的伪代码
procedure 2optSwap(route, i, k) {
    1. 将 route[0] 到 route[i-1] 按顺序加入new_route
    2. 将 route[i] 到 route[k] 倒序加入new_route
    3. 将 route[k+1] 及之后的元素按顺序加入new_route
    return new_route;
}
//稍微贴近实现的伪代码
repeat until no improvement is made {
    start_again:
    best_distance = calculateTotalDistance(existing_route)
    for (i = 1; i <= number of nodes eligible to be swapped - 1; i++) {
        for (k = i + 1; k <= number of nodes eligible to be swapped; k++) {
            new_route = 2optSwap(existing_route, i, k)
            new_distance = calculateTotalDistance(new_route)
            if (new_distance < best_distance) {//如上所述，本文中的实现在这里稍有区别
                existing_route = new_route
                best_distance = new_distance
                goto start_again 
            }
        }
    }
}
 
串行2-opt的C语言实现，参照伪代码并修改为每次遍历所有城市，选择这次遍历中找到的最短路径进行reverse：
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <sys/time.h>
#include <stdint.h>

#define swap(a, b) {float tmp = a;  a = b;  b = tmp;}

void reverse(int len, int* route) {
    for (int i=0; i<len/2; i++) {
        swap(route[i], route[len-1-i]);
    }
}
int get_distance(int x1,int y1, int x2, int y2){
    return (int)sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
}
int TSPDistance(int size, int route[size+1], int x[size], int y[size]) {
    int sum = 0;
    for (int i=1;i<size+1;i++) {
        sum += get_distance(x[route[i-1]], y[route[i-1]], x[route[i]], y[route[i]]);

    }
    return sum;
}
void twoOptTSP(int size, int route[size+1], int x[size], int y[size]) {
    //initial route
    for (int i=0;i<size;i++) {
        route[i] = i;
    }
    route[size]=0;
    int change;
    int minchange;
    int mini;
    int mink;
    int improvement = 0;//c
    LOOP: do {//if negative changes, then it is still improving
        minchange=0;
        mini=0;
        mink=0;
        improvement = 0;
        for (int i = 1; i < size-1; i++) {
            for (int k = i + 1; k < size; k++) {
                change = get_distance(x[route[i-1]], y[route[i-1]], x[route[k]], y[route[k]])
                + get_distance(x[route[i]], y[route[i]], x[route[k+1]], y[route[k+1]])
                - get_distance(x[route[i-1]], y[route[i-1]], x[route[i]], y[route[i]])
                - get_distance(x[route[k]], y[route[k]], x[route[k+1]], y[route[k+1]]);
                
                if (change < minchange) {
                    improvement = 1;
                    minchange=change;
                    mini=i;
                    mink=k; 
                }
            }
        }
        // printf("minchange %d i %d k %d\n", minchange, mini, mink);
        reverse(mink-mini+1, &route[mini]);
    } while(improvement);
    int curr_distance = TSPDistance(size, route, x, y);
    printf("curr_distance %d\n", curr_distance);
}
 
针对这个串行版本，我们将设计和实现2-OPT的分布式并行算法。算法用C语言实现，我们会使用openMP进行单机多核并行，使用openMPI进行多机并行。
 
实现思路
 
并行化这个算法，最直观的切入点便是：将指针i或k的遍历分配给不同的核。
 
仔细分析后，我们可以发现，因为k的初始值为i+1，所以随着i的增大，k的遍历数量会越来越小。
 
如果我们将i简单拆分给不同的机器，那么每个机器的工作量是不一样的。而工作量不同，必然导致有的机器先到达同步点，等待其他机器完成计算，造成资源浪费。因此我们要进行负载均衡。
 
i        | 1 2 3 4 | 5 6 7 8 | 9 10 11 12 | 13 14 15 16 |
machine       A         B          C             D       
 
本文中使用的方案是：像高斯求和等差数列一样，从头部和尾部同时分派i的任务。这样，每台机器需要计算的(i,k)对是相同的, 如果城市数无法整除机器数，最多只会造成一台机器的资源浪费。即：
 
i        | 1 2 | 3 4 | 5 6 | 7 8 | 9 10 | 11 12 | 13 14 | 15 16 |
machine     A     B     C     D     D       C       B       A
 
如果机器是多核，我们可以进一步将k的遍历拆分给每一个核。
 
在遍历完i,k之后，我们得到了每个核中的最小值。我们需要将他们汇总在机器A，即master上进行比较，获得全局最小值。然后将reverse的结果分发回每个机器。
 
这里有一个细节，即我们仅发送最后要进行变更的i和k，而不发送master变换后的整个路径。这样可以最大程度减少通信时间。
 
以上，我们就完成了算法的并行化。接下来我们来对这个并行算法进行针对性优化。
 
优化
 
仔细观察后我们就能够发现，2-opt算法中存在大量互相不干扰的(i,k)对（下面简称兼容），遍历一次然后reverse其中最优的一个，和在同一次遍历中reverse多个兼容的ik对，得到的结果是一样的。下面是几个兼容的情况：
 
(i,k)范围不重叠
 
假设以下的情况：
 
我们有路径：0-1-2-3-4-5-6-7-8-9-0，我们在master汇总了三个(i, k)对：(1,2), (4,5), (7,8)。按照上面的算法，我们只会选择那个能得到最短的路径的ik进行reverse。
 
但实际上，我们换了其中一个ik对，假如是(1,2)，reverse后得到0-2-1-3-4-5-6-7-8-9-0。然后我们在下一次遍历后，我们仍然会得到另外两个ik对，即(4,5), (7,8)。而如果我们直接对上面的三个ik同时进行reverse，就节省了两次遍历。
 
因此，如果我们得到的多个ik之间的范围不重叠，就可以同时进行reverse。
 
这里有一个细节，如果我们获得的是(1,2), (3,4)， 他们看似兼容，实际上需要计算的城市是不同的。
reverse(1,2)之前，路径为0-1-2-3-4-5-6-7-8-9-0，计算reverse(3,4)能缩短的距离，需要计算的是distance(2,3), distance(4,5), disntance(2,4), disntance(3,5)
reverse(1,2)之后，路径变成了0-2-1-3-4-5-6-7-8-9-0，这时再计算(3,4)能缩短的距离，则需要计算distance(1,3), distance(4,5), distance(1,4), distance(3,5)
 
(i,k)有包含关系
 
假如我们还是有路径``0-1-2-3-4-5-6-7-8-9-0`，这次我们在master汇总了这样三个ik对：
 
(1,6), (3,4), (4,7)。仔细观察会发现，(3,4)是被包含在(1,6)里面的。但是(4,7)又与(1,6)不兼容。如果reverse(4,7)之后路线最短，那我们显然应该直接reverse(4,7)，然后进行下一次遍历。可以，并且reverse(1,6)之后路线是最短的，我们是不是可以同时reverse(1,6), (3,4)呢？
 
我们需要分情况讨论：
 
首先，我们reverse(1,6)之后的结果是：0-6-5-4-3-2-1-7-8-9-0。那么下一次遍历，我们需要比较reverse(3,4)和(4,7)谁更短。
 
如果(3,4)更短，我们就可以同时reverse(1,6), (3,4)，反之则不行。
 
实现方法
 
将上面的情况推到一般，我们实际需要做的就是对所有汇总到master的结果按照reverse后路线长度从短到长进行排序。求出从下标0开始的最长子序列，序列中的每一个元素都与在它之前的所有元素兼容。
 
比如说排序后结果为[(1,2), (5,6), (4,8), (10,11)]，我们从(5,6)开始遍历，发现(5,6)与(1,2)兼容，而(4,8)虽然与(1,2)兼容，但不与(5,6)兼容。所以我们就不用再检查(10,11)了，即使它与第一和第二个元素兼容，我们也不能保证在reverse第一和第二个元素后，不会出现比(10,11)更优且不兼容的解。
 
当然了，如果我们不在意最后的结果是否与串行化算法的结果一致，我们也可以直接reverse所有与第一个元素兼容的元素（因为烦人的死线，本文中仅实现了这种算法，当然这个得到的结果是不那么严谨的）。
 
伪代码
 
//parallel pseudocode
2opt(x, y, route):
  do:
    //phase 1
    minchange[number of threads] = (0, 0, 0);//三个值分别为：(change in distance, i, k)
    for ii = 0 to (size-1)/2 do in parallel:
      processor p thread t does:
      i = ii + 1 //负载均衡
      for k = i + 1 to size-1:
        change = get_change(route, i, k)
        if (change < minchange[0])
          minchange[t] = (change, i, k);
      i = size-2-ii //负载均衡
      for k = i + 1 to size-1:
        change = get_change(route, i, k)
        if (change < minchange[t][0])
          minchange = (change, i, k);
    //phase 2
    gather minchange from all processors to processor_results of processor 0
    processor 0 does:
      add changes that can be performed together to send_results
      broadcast send_results to all processors
    //phase 3
    all processor does locally:
      for change in send_results:
        reverse(route, change[1], change[2])
  while there is improvement in distance

      
//寻找与最优解兼容的解
buildChangeMat(idx, minchange, mat):
	If mat[idx].length == 0: 
		add minchange to mat[idx];
		return;
	Check idx:
		If (not compatible): 
			return;
		Else if (compatible): 
			add minchange to mat[idx]; 
			return;
		Else if (inside range of an element): 
			buildChangeMat(element, minchange, mat);

 
串行版，并行版和编译运行的shell代码，我都贴到文件里，有需要自取。
 
不太严谨的实验结果
 
城市数量
串行结果 （距离）
并行结果（距离）
1000
25287
25077
2000
35549
35373
3000
42951
43108
5000
55260
55240
Table 1 两台机器每个12核的运行结果
 
这里可以看到结果是不一样的。因为我们实现的是不严谨的版本。
 
城市数量
串行时间（s）
并行时间（s）
Speedup
并行效率
1000
16.40
0.50
32.80
1.37
2000
133.45
1.54
86.66
3.61
3000
473.46
4.42
107.12
4.46
5000
2259.01
51.02
44.28
1.85
Table 2 两台机器，每个12核的运行时间
 
城市数量
串行结果（距离）
并行结果（距离）
5000
55260
55235
Table 3 四台机器每个12核的运行结果
 
城市数量
串行时间（s）
并行时间（s）
Speedup
并行效率
5000
2249.84
20.81
108.11
2.25
Table 4 四台机器每个12核的运行时间
 
最后
 
总的来说，这个算法应该还有优化的空间。目前每个线程只会提供一个(i,k)对。我们可以把它变成两个或者更多，这样我们就有可能获得更多兼容的解。同时兼容的情况也可能不止上文中提到的两种。
 
我们可以赠机器只有n个局部最小值，我们可能错过了一些可以同时在一轮迭代中reverse的机会。如果能够储存更多的候选路径，我们可能可以获得更大的speedup。
 
不过，这个并行算法的缺憾也很直观：
 
一个是speedup取决于数据是否提供了在一轮迭代中进行多次变换的可能，所以speedup并不稳定。不过如果城市数量足够大，肯定会在早期的遍历中获得巨大的speedup。
另一个就是没有实现与串行化结果一致的版本。我们无法获得与串行算法相同的值，也就无法更准确地计算speedup。因为串行和并行的结果不同，所以我们无法确保双方的总计算量相同，有可能并行算法多进行了或者少进行了几轮迭代，才得出了最终的speedup。
不过总的来说，我们也可以看到这个并行算法取得的speedup有时完全超出预期，并行效率（=speedup/总核数）远大于1。