AI 助理
备案控制台
开发者社区 人工智能 文章 正文

深入理解并行编程-分割和同步设计（五）

2016-04-08 1785
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

原文链接    作者：paul    译者：谢宝友，鲁阳，陈渝

并行快速路径

细粒度的设计一般要比粗粒度的设计复杂。在许多情况，绝大部分开销只由一小部分代码产生[Knu73]。所以为什么不把精力放在这一小块代码上。

这就是并行快速路径设计模式背后的想法，尽可能地并行化常见情况下的代码路径，同时不产生并行化整个算法所带来的复杂性。您必须理解这一点，不只算法需要并行化，算法所属的工作负载也要并行化。构建这种并行快速路径，需要极大的创造性和设计上的努力。

并行快速路径的设计模式

图1.1并行快速路径的设计模式

并行快速路径结合了两种以上的设计模式（快速路径和其他的），因此也成为了一种模板设计模式。下列并行快速路径的实例结合了其他设计模式，见图1.1。

1. 读写锁（1.1节将描述）。
2. Read-Copy-Update（RCU），多数作为读写锁的高性能代替者使用，将在第8.3节介绍，本章中不会对其进行深入讨论。
3. 层级锁（[Mck96]），第1.2节将进行介绍。
4. 资源分配器缓存（[McK96][MS93]）。第1.3节将进行介绍。

1.1. 读写锁


01 rwlock_t hash_lock;
02  
03 struct hash_table
04 {
05 long nbuckets;
06 struct node **buckets;
07 };
08  
09 typedef struct node {
10 unsigned long key;
11 struct node *next;
12 } node_t;
13  
14 int hash_search(struct hash_table *h, long key)
15 {
16 struct node *cur;
17 int retval;
18  
19 read_lock(&hash_lock);
20 cur = h->buckets[key % h->nbuckets];
21 while (cur != NULL) {
22 if (cur->key >= key) {
23 retval = (cur->key == key);
24 read_unlock(&hash_lock);
25 return retval;
26 }
27 cur = cur->next;
28 }
29 read_unlock(&hash_lock);
30 return 0;
31 }

图1.1：基于读写锁的哈希表搜索算法

如果同步开销可以忽略不计（比如程序使用了粗粒度的并行化），并且只有一小段临界区修改数据，那么让多个读者并行处理可以显著地增加可扩展性。写者与读者互斥，写者和另一写者也互斥。图1.1显示了哈希搜索如何用读写锁实现。

读写锁是非对称锁的一种简单实例。Snaman[ST87]描述了一种叹为观止的非对称锁，带有6个模式，在许多集群系统中使用。第6章进一步介绍了普通锁和读写锁的许多详细信息。

1.2. 层级锁


01 struct hash_table
02 {
03 long nbuckets;
04 struct bucket **buckets;
05 };
06  
07 struct bucket {
08 spinlock_t bucket_lock;
09 node_t *list_head;
10 };
11  
12 typedef struct node {
13 spinlock_t node_lock;
14 unsigned long key;
15 struct node *next;
16 } node_t;
17  
18 int hash_search(struct hash_table *h, long key)
19 {
20 struct bucket *bp;
21 struct node *cur;
22 int retval;
23  
24 bp = h->buckets[key % h->nbuckets];
25 spin_lock(&bp->bucket_lock);
26 cur = bp->list_head;
27 while (cur != NULL) {
28 if (cur->key >= key) {
29 spin_lock(&cur->node_lock);
30 spin_unlock(&bp->bucket_lock);
31 retval = (cur->key == key);
32 spin_unlock(&cur->node_lock);
33 return retval;
34 }
35 cur = cur->next;
36 }
37 spin_unlock(&bp->bucket_lock);
38 return 0;
39 }

图1.2：基于层级锁的哈希表搜索算法

层级锁背后的想法是尽可能长时间的持有一把粗粒度的锁，在此期间持有细粒度的锁。图1.2显示了我们的哈希表搜索如何采用层级锁的方式实现，不过这也显示了该方法的重大弱点：我们付出了获取第二把锁的开销，可以我们只持有它一小段时间。在这种情况下，简单的数据锁方法则更简单且性能又佳。

小问题1.1： 哪种情况下使用层级锁最好？

1.3. 资源分配器缓存

本节展示了一种简明扼要的并行内存分配器，用于分配固定大小的内存。更多信息请见[MG92][MS93][BA01][MSK01]等书，或者参见Linux内核[Tor03]。

1.3.1. 并行资源分配问题

并行内存分配器锁面临的基本问题是在普通情况下快速地进行内存分配和释放，和在不理想情况下有效的分布内存之间的矛盾。

假设有一个直接了当的数据所有权类型的程序——该程序简单地将内存按照CPU数划分，这样每个CPU都有自己的一份。比如，该系统有2个CPU和2G内存（和我正在敲字的这台电脑一样）。我们可以为每个CPU分配1G内存，这样每个CPU都可以访问属于自己的那一半内存，无须加锁，以及不必关心锁带来的复杂性和开销。不幸的是，这种简单的模型存在问题，如果有一种算法，让CPU0分配所有内存，让CPU1释放所有内存，在在生产者-消费者算法中是可能的，这样模型就失效了。

另一个极端，代码锁，则受到大量锁竞争和通信开销的影响。

1.3.2. 资源分配的并行快速路径

分配器缓存概要图

图1.3：分配器缓存概要图

常见的解决方案让每个CPU拥有一块规模适中的内存块缓存，以此作为快速路径，同时提供一块较大的共享内存池分配额外的内存块，该内存池用代码锁保护。为了防止任何CPU独占内存块，我们给每个CPU的缓存可以容纳的内存块大小做一限制。在双核系统中，内存块的数据流如图1.3所示：当某个CPU的缓存池已满时，该CPU释放的内存块将传送到全局缓存池中，类似地，当CPU缓存池为空时，该CPU所要分配的内存块是从全局缓存池中取出来的。

1.3.3. 数据结构


01 #define TARGET_POOL_SIZE 3
02 #define GLOBAL_POOL_SIZE 40
03  
04 struct globalmempool {
05 spinlock_t mutex;
06 int cur;
07 struct memblock *pool[GLOBAL_POOL_SIZE];
08 } globalmem;
09  
10 struct percpumempool {
11 int cur;
12 struct memblock *pool[2 * TARGET_POOL_SIZE];
13 };
14  
15 DEFINE_PER_THREAD(struct percpumempool, percpumem);

图1.4：分配器缓存数据结构

图1.4是一个“玩具式”缓存分配器的数据结构。图1.3的全局缓存池由globalmem实现，类型为strcut globalmempool，两个CPU的缓存池是由每CPU变量percpumem实现，类型为struct percpumempool。这两个数据结构都有一个pool字段，作为指向内存块的指针数组，从下标0开始向上填充。这样，如果globalmem.pool[3]为NULL，那么从下标4开始的数组成员都为NULL。cur字段包含pool数组中下标最大的非空元素，为-1表示所有pool数组的成员为空。从globalmem.pool[0]到globalmem.pool[globalmem.cur]的所有成员必须非空，而剩下的成员必须为空。

分配器缓冲池概要图

图1.5：分配器缓冲池概要图

对pool数据结构的操作见图1.5，图中的六个格子代表pool字段中的数据指针，他们前面的数字代表cur字段。深色的格子代表非空的指针，浅色的格子代表NULL指针。虽然有些让人迷惑，但是请注意该数据结构有一个重要的性质：cur字段总是比非空指针的个数少一个。

1.3.4. 分配函数


01 struct memblock *memblock_alloc(void)
02 {
03 int i;
04 struct memblock *p;
05 struct percpumempool *pcpp;
06  
07 pcpp = &__get_thread_var(percpumem);
08 if (pcpp->cur < 0) {
09 spin_lock(&globalmem.mutex);
10 for (i = 0; i < TARGET_POOL_SIZE &&
11 globalmem.cur >= 0; i++) {
12 pcpp->pool[i] = globalmem.pool[globalmem.cur];
13 globalmem.pool[globalmem.cur--] = NULL;
14 }
15 pcpp->cur = i - 1;
16 spin_unlock(&globalmem.mutex);
17 }
18 if (pcpp->cur >= 0) {
19 p = pcpp->pool[pcpp->cur];
20 pcpp->pool[pcpp->cur--] = NULL;
21 return p;
22 }
23 return NULL;
24 }

图1.6：分配器缓存的分配函数

在图1.6中可以见到分配函数memblock_alloc()。第7行获得当前线程的每线程缓存池，第8行检查缓存池是否为空。

如果为空，第9-16行尝试从全局缓存池中取出内存块填满每线程缓存池，第9行获取自旋锁，第16行释放自旋锁。第10-14行从全局缓存池中取出内存块，移至每线程缓存池，直到每线程缓存池达到目标大小（半满）或者全局缓存池耗尽为止，第15行将每线程缓存池的cur字段设置为合适大小。

接下来，第18行检查每线程缓存池是否还是为空，如果不是，第19-21行取出一个内存块返回。如果为空，第23返回内存耗尽的不幸消息。

1.3.5. 释放函数


01 void memblock_free(struct memblock *p)
02 {
03 int i;
04 struct percpumempool *pcpp;
05  
06 pcpp = &__get_thread_var(percpumem);
07 if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) {
08 spin_lock(&globalmem.mutex);
09 for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) {
10 globalmem.pool[++globalmem.cur] = pcpp->pool[i];
11 pcpp->pool[i] = NULL;
12 }
13 pcpp->cur = i;
14 spin_unlock(&globalmem.mutex);
15 }
16 pcpp->pool[++pcpp->cur] = p;
17 }

图1.7：分配器缓存的释放函数

图1.7是内存块的释放函数。第6行获取当前线程的缓存池指针，第7行检查该缓存池是否已满了。

如果是，第8-15行将每线程缓存池一半的内存块释放给全局缓存池，第8行和第14行获取、释放自旋锁。第9-12行实现将内存块从本地移至全局缓存池的循环，第13行将每线程缓存池的cur字段设置为合适的大小。

接下来，第16行将刚刚释放的内存块放入每线程缓存池。

1.3.6. 性能

分配器缓存的性能

图1.8：分配器缓存的性能

图1.8是粗略的性能数据，在1Ghz（每个CPU 4300 bogomips）的双核Intel x86处理器上运行，每个CPU的缓存至多可以装下6个内存块。在这个微型benchmark中，每个线程重复分配一组内存块，然后释放，一组内存块的数目以“分配运行长度”的名字显示在x轴上。y轴是每毫秒成功分配/释放的数目——失败的分配不计入内，“+”来自于单线程的运行结果。

从图中可以发现，运行长度在6之前拥有线性的扩展性，性能也非常优秀，不过当运行长度大于6以后，性能开始变得低下，扩展性甚至为负值。鉴于此，将TARGET_POOL_SIZE设置的足够大非常重要，幸运的是在实践中很容易做到这点[MSK01]，尤其是内存容量疯涨的今天。比如，在大多数系统中，将TARGET_POOL_SIZE设置为100是很合理的，这样可以保证有99%的时间是使用每线程缓存池分配和释放的。

从图中可知，使用数据所有权思想的例子相较于使用锁的版本，极大地提升了性能。在常规情况中避免使用锁，正是本书不断重复的主题。

小问题1.1：图1.8中存在一个性能提升的模式：增加三个样本中的运行长度，比如10，11和12，为什么不这么做？

小问题1.2：当运行长度为19或更大时，两线程测试开始出现分配失败。如果全局缓存池的大小为40，每CPU缓存池的大小为3，那么可以出现分配失败的最小分配运行长度是多少？

1.3.7. 真实世界中的设计

并行的“玩具”资源分配器非常简单，但是真实世界中的设计在几个方面扩展这个方案。

首先，真实的资源分配器需要处理各种不同的资源大小，在“玩具”中只能分配固定大小。一种比较流行的做法是提供一系列固定大小的资源，恰当地放置以平衡内碎片和外碎片，比如1980年代晚期的的BSD内存分配器[MK88]。这样做就意味着每种资源大小都要有一个“globalmem”变量，同样对应的锁也要每种一个，因此真实的实现将采用数据锁，而非“玩具”程序中的代码锁。

其次，产品级的系统必须可以改变内存的用途，这意味着这些系统必须能将内存块组合成更大的数据结构，比如页[MS93]。这种组合也需要锁的保护，这种锁也必须是一种资源大小一个的。

第三，组合后的内存必须回到内存管理系统，内存页也必须是从内存管理系统分配的。这一层面所需要的锁将依赖于内存管理系统，但也可以是代码锁。在这一层面中使用代码锁通常是可以容忍的，因为在设计良好的系统中很少触及这一级别[MSK01]。

尽管真实世界的设计要复杂许多，但背后的思想是一样的——并行的快速路径。

真实世界中的并行分配器

表1.1：真实世界中的并行分配器

1.5. 性能总结

@@@ summarize performance of the various options. Forward-reference to the RCU/NBS section.

文章标签：
缓存
算法
ali清英
目录
相关文章
croyantssinc&egrave;res.
|
6月前
|
图形学
计算机辅助设计的基本原理与应用 - 副本
计算机辅助设计的基本原理与应用 - 副本
croyantssinc&egrave;res.
73 0
萝卜丝丸子
|
4月前
|
SQL 安全
线程操纵术并行策略问题之调整并行流的并行度问题如何解决
线程操纵术并行策略问题之调整并行流的并行度问题如何解决
萝卜丝丸子
48 0
萝卜丝丸子
|
4月前
|
机器学习/深度学习 Java 数据挖掘
线程操纵术之更优雅的并行策略问题之并发和并行有区别问题如何解决
线程操纵术之更优雅的并行策略问题之并发和并行有区别问题如何解决
萝卜丝丸子
46 0
游客iigf2m33ba53k
|
机器学习/深度学习 编解码 人工智能
高效轻量级语义分割综述
语义分割是自动驾驶中视觉理解的重要组成部分。然而当前SOTA的模型都非常复杂和繁琐，因此不适合部署在计算资源受限且耗时要求较低的车载芯片平台上。本文深入研究了更紧凑、更高效的模型以解决上述问题，这些模型能够部署在低内存嵌入式系统上，同时满足实时推理的需求。本文讨论了该领域一些优秀的工作，根据它们的主要贡献进行归类，最后本文评估了在相同软硬件条件下模型的推理速度，这些条件代表了一个典型的高性能GPU和低内存嵌入式GPU的实际部署场景。本文的实验结果表明，许多工作能够在资源受限的硬件上实现性能和耗时的平衡。
游客iigf2m33ba53k
412 22
高效轻量级语义分割综述
timerring
|
存储 cobar 算法
同步计数器设计与建模
⭐本专栏针对FPGA进行入门学习，从数电中常见的逻辑代数讲起，结合Verilog HDL语言学习与仿真，主要对组合逻辑电路与时序逻辑电路进行分析与设计，对状态机FSM进行剖析与建模。
timerring
160 0
同步计数器设计与建模
5abyqn7wigzqm
|
并行计算 Java 数据挖掘
对于并行和并行概念上的理解与总结
并行和并行概念上的理解与总结
5abyqn7wigzqm
1139 0
黑泽明军
|
Java
注意两个词汇的区别：并行和并发
* 大家注意两个词汇的区别：并行和并发 * 　　 并行：前者是逻辑上同时发生，指在某一个时间内同时运行多个程序。 * 　　 并发：后者是物理上同时发生，指在某一个时间点同时运行多个程序。 　　在java就业班中会有如何解决高并发？我的GitHub地址：https://github.
黑泽明军
1306 0
华章计算机
|
并行计算
《并行计算的编程模型》一3.6.1　全局同步屏障
本节书摘来华章计算机《并行计算的编程模型》一书中的第3章 ，第3.6.1节， ［（美）帕万·巴拉吉（Pavan Balaji）编著；张云泉等译,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
华章计算机
1010 0
华章计算机
|
并行计算 程序员
《并行计算的编程模型》一3.7.3　非全局同步屏障
本节书摘来华章计算机《并行计算的编程模型》一书中的第3章 ，第3.7.3节， ［（美）帕万·巴拉吉（Pavan Balaji）编著；张云泉等译,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
华章计算机
781 0
华章计算机
|
并行计算 程序员
《并行计算的编程模型》一3.6　排序和同步
本节书摘来华章计算机《并行计算的编程模型》一书中的第3章 ，第3.6节， ［（美）帕万·巴拉吉（Pavan Balaji）编著；张云泉等译,更多章节内容可以访问云栖社区“华章计算机”公众号查看。
华章计算机
932 0

热门文章

最新文章

  • 1
    为什么lisp这么强大的语言用的人这么少
  • 2
    数据库中的Schema和Database的区别
  • 3
    MAVEN简介之——settings.xml
  • 4
    小技巧 - 怎样屏蔽群消息（包括 @全体成员）？
  • 5
    深度 ｜ 大数据算法应用的测试发展之路
  • 6
    RDS for SQL server 空间问题排查汇总
  • 7
    JavaScript基本数据类型分析
  • 8
    日本将举办VR食品研讨会，用音效模拟食物入口的质感
  • 9
    df查询磁盘容量
  • 10
    谷歌搜搜不谋而合 “情境搜索”或成未来趋势
  • 1
    如何根据性能检测结果进行 CSS 优化？
    27
  • 2
    如何检测 CSS 性能瓶颈并进行优化？
    29
  • 3
    CSS优化技巧
    28
  • 4
    如何在 JavaScript 中访问和修改 CSS 变量？
    30
  • 5
    CSS 变量的作用域和 JavaScript 变量的作用域有什么不同？
    31
  • 6
    如何在 CSS 变量中使用函数？
    22
  • 7
    CSS 变量的作用域是什么？
    17
  • 8
    京东面试：亿级黑名单 如何设计？亿级查重 呢？（答案含：布隆过滤器、布谷鸟过滤器）
    24
  • 9
    android做中大型项目完美的架构模式是什么？是MVVM吗？如果不是，是什么？
    18
  • 10
    如何使用 JavaScript 动态修改 CSS 变量的值？
    11

    • 相关课程

    更多
  • 【算法实战】14. 利用PCA来简化数据
  • 【算法实战】15. 利用SVD来简化数据

    • 相关电子书

    更多
  • 为并行图数据处理提供高层抽象／语言
  • 典型模型-卷积神经网络入门 从概念原理到应用实现
  • Quanta:Quora的HBase分层计数系统

    • 相关实验场景

    更多
  • 观察进程的并发性
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月