最近把项目中负责矢量瓦片切割的功能模块做成了并行计算模式，写一篇博客来总结一下。

1. 技术简介

1.1 矢量瓦片

传统的栅格地图切片，是服务器端预先绘制的PNG或JPG切片集合。而矢量地图切片将矢量数据通过不同的描述文件来组织和定义，通常通过自定义文件或json文件进行传输，在前端按需请求不同的矢量瓦片数据文件，并利用CANVAS等技术进行绘制。使用这种技术有不少好处，例如不再需要为不同的样式而反复进行制图、渲染、切片、更新service等过程，并且在当前各种高分屏、视网膜屏大肆发展的阶段，避开按照特定DPI和分辨率渲染的栅格图片在不同的显示设备上无法以统一清晰的效果呈现，等等。

1.2 线程池

线程池类似于操作系统中的缓冲区的概念，它的流程如下：先启动若干数量的线程，并让这些线程都处于睡眠状态，当需要一个开辟一个线程去做具体的工作时，就会唤醒线程池中的某一个睡眠线程，让它去做具体工作，当工作完成后，线程又处于睡眠状态，而不是将线程销毁。

1.3 任务队列

任务队列是一种能够把封装了数据和操作的任务在多线程之间传递的线程安全的FIFO(First In First Out)队列。其概念类似于生产者-消费者模型中的缓冲区。生产者生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

2. 实验设计

2.1 瓦片切割流程

读取shp文件的范围，计算出x与y方向的差值；
设定单张瓦片的尺寸为256×256像素，通过比例尺放缩计算出瓦片在当前比例尺下，对应的x与y方向上的数量；
每张瓦片由(level, row, col)三元组唯一标识，并且由一个数据结构Tile来存储相关信息；
遍历瓦片集合，将每张瓦片与shp文件中的所有feature进行相交判断。若相交，则将feature的空间坐标记录在Tile中；
将Tile序列化为json文件存储在文件系统中。

2.2 数据处理模式

本程序包含两个角色，分别是：Master线程（唯一）与Worker线程（多个），其中Master负责①生产任务，并将任务添加至任务队列、②调度Worker线程完成任务。而Worker负责执行矢量瓦片切割的逻辑。如下所示：

2.3 任务队列的具体定义

在本次实验中，一个任务对应一个瓦片的处理逻辑，即取得任务的线程需要完成任务指定瓦片的生产。由于瓦片可由(level, row, col)三元组唯一标识。因此任务也同样可以通过(level, row, col)三元组唯一标识。因此构建一个数据结构TileTask，其包含了level, row, col等属性。线程取得任务后，可通过这些属性明确自己需要处理哪张瓦片。

存储多个TileTask的集合称为任务队列。由于采用先进先出的任务处理方式，故采用Queue作为TileTask的容器，即Queue<TileTask> taskQueue = new Queue<TileTask>();

3. 实验数据与环境

3.1 矢量数据

使用中国行政区划图作为实验数据。以1: 69,885,283作为0级比例尺进行切割（参考Google地图）。该图层的最大经度为东经135.085831度，最大纬度为北纬53.557926度，最小经度为东经73.446960度，最小纬度为北纬18.160896度。如下图所示：

3.2 实验环境

表 1 硬件信息

处理器	型号	主频	核数
配置参数	Intel(R) Core(TM)i7-8700K	3.70Ghz	6

表 2 软件信息

操作系统	Windows
开发环境	.NET Framework (C#)
线程库	System.Threading.Tasks
计时库	System.Diagnostics

4. 实验结果

本实验对1-5层级的矢量瓦片分别用串行与并行模式（每个CPU对应一个线程）进行计算，并记录下了计算使用的时间。对于实验结果计算了并行效率和加速比，公式如下：

对于加速比计算公式：其中Sr为加速比，Ts为整个任务在串行机上执行所需的时间，Tp为整个任务在并行机上执行所需的时间。对于并行效率计算公式：其中E为效率，N为核心数。实验结果如下：

表 3 实验结果统计

瓦片层级	瓦片总数	串行/s	2核/s	3核/s	4核/s	5核/s	6核/s
1	13	1.52	0.96	0.75	0.69	0.55	0.60
2	43	5.47	3.06	2.42	2.22	1.99	1.98
3	151	19.84	11.23	9.45	8.25	7.39	7.43
4	559	76.44	46.34	37.60	31.51	29.09	27.90
5	2157	312.37	189.32	147.59	126.66	120.28	109.46

图 3 核数-时间关系图

观察以上统计数据可以发现，随着瓦片的数量以近似4倍的速率增多，计算耗时也以近似4倍的速率扩大。

以下数据计算了采用不同数量的CPU所得到的加速比一级并行效率。

表 4 双核计算结果

瓦片层级	瓦片总数	串行/s	2核/s	加速比	并行效率
1	13	1.52	0.96	1.58	0.79
2	43	5.47	3.06	1.79	0.89
3	151	19.84	11.23	1.77	0.88
4	559	76.44	46.34	1.65	0.82
5	2157	312.37	189.32	1.65	0.82

表 5 三核计算结果

瓦片层级	瓦片总数	串行/s	3核/s	加速比	并行效率
1	13	1.52	0.75	2.03	0.68
2	43	5.47	2.42	2.26	0.75
3	151	19.84	9.45	2.10	0.70
4	559	76.44	37.60	2.03	0.68
5	2157	312.37	147.59	2.12	0.71

表 6 四核计算结果

瓦片层级	瓦片总数	串行/s	4核/s	加速比	并行效率
1	13	1.52	0.69	2.20	0.55
2	43	5.47	2.22	2.46	0.62
3	151	19.84	8.25	2.40	0.60
4	559	76.44	31.51	2.43	0.61
5	2157	312.37	126.66	2.47	0.62

表 7 五核计算结果

瓦片层级	瓦片总数	串行/s	5核/s	加速比	并行效率
1	13	1.52	0.55	2.76	0.55
2	43	5.47	1.99	2.75	0.55
3	151	19.84	7.39	2.68	0.54
4	559	76.44	29.09	2.63	0.53
5	2157	312.37	120.28	2.60	0.52

表 8 六核计算结果

瓦片层级	瓦片总数	串行/s	6核/s	加速比	并行效率
1	13	1.52	0.60	2.53	0.42
2	43	5.47	1.98	2.76	0.46
3	151	19.84	7.43	2.67	0.45
4	559	76.44	27.90	2.74	0.46
5	2157	312.37	109.46	2.85	0.48

对表4至表8进行综合统计分析，得到加速比与并行效率随着核心数的变化数据，如下表所示：

表 9 核数对加速比以及并行效率的影响

核心数	平均加速比	平均并行效率
2	1.69	0.84
3	2.11	0.7
4	2.39	0.6
5	2.68	0.54
6	2.71	0.45

根据表9中的数据，分别绘制图4与图5以直观地表达核心数对加速比与并行效率的影响。

综上，并行计算能明显提高瓦片切割的效率，提高的效率与参与计算的CPU核心数呈正相关。随着核心数增加，加速比不断增加，但是增加的幅度逐渐减小。而并行效率随着核心数的增加而线性减小。

『项目总结』基于线程池的矢量瓦片切割技术