目录
0. 序言
多核CPU缓存Cache架构参考
影响多线程速度的因素参考
1. 缓存行同步问题/共享数据竞争
由于CPU一次性读入的字节是固定的, 不能再分割变小的, 这个值被称为机器字长, 在64位机上, 它是64字节.
当并行时, 多个CPU可能会读入同一缓存行, 每个CPU的数据是相互独立的, 每个CPU对缓存行的更改, 就会导致数据在每个CPU内不一致,
这时候就需要对数据进行同步，我的CPU是6核12线程i5
1.1 测试代码
- 通用global.h::avgTime: 求函数执行时间的平均值
#pragma once
#include <chrono>
// 只支持一个参数(如果想要使用多个参数, 请用一个结构体将他们再封装一层)
template <typename Duration, typename Fn, typename Repeat, typename Args>
double avgTime(Fn& const fn, Repeat&& count, Args&& args) {
using namespace std::chrono;
high_resolution_clock::time_point t1 = high_resolution_clock::now();
// repeat execute to make time avg and exact
for (int i = 0; i < count; ++i) {
fn(std::forward<Args>(args)); // 不是调用拷贝函数不应该用forward, 不过问题不大
}
high_resolution_clock::time_point t2 = high_resolution_clock::now();
return duration_cast<Duration>(t2 - t1).count() / (double)count;
}
- Synchronization.h
#include <thread>
#include <chrono>
#include <iostream>
#include <vector>
#include "global.h"
inline long long b[1024] = { 1 };
inline std::vector<std::thread> threads(10);
// 在数组指定索引位置累加
inline int SimpleTask(int ix) {
for (int i = 0; i < 10e6; i++) {
b[ix] += i;
}
return b[ix];
}
// 同步问题
inline void IfSynchronization(int elementSpace){
for (int i = 0; i < threads.size(); ++i) {
threads[i] = std::thread(SimpleTask, i * elementSpace);
}
for (int i = 0; i < threads.size(); ++i) {
threads[i].join();
}
}
inline void TestForSync() {
using namespace std;
typedef chrono::milliseconds ms;
double time, time02, time03;
// 导致缓存行同步
time = avgTime<ms>(IfSynchronization, 100, 1);
cout << "01 finished in " << time << "milliseconds\n";
// 不导致缓存行同步
time02 = avgTime<ms>(IfSynchronization, 100, 8);
cout << "02 finished in " << time02 << "milliseconds\n";
// 共享资源
time03 = avgTime<ms>(IfSynchronization, 100, 0);
cout << "03 finished in " << time03 << "milliseconds\n";
}
1.2 测试逻辑
其中先申请一个数组, 数组元素在内存中地址是连续的
inline long long b[1024] = { 1 };
long long类型变量长度为8字节, 这就意味着CPU读入数据时, 一次性读入8个long long类型的元素
创建10个线程, 每个线程访问数组的一个位置
IfSynchronization(1), 表示每个线程每隔一个位置访问数组
IfSynchronization(8), 表示每个线程每隔八个位置访问数组
IfSynchronization(0), 表示每个线程都访问数组索引0的位置
对于IfSynchronization(1)， 每个CPU缓存行对应的数组元素索引如下
可以看出, 第一个CPU修改数组索引0位置的元素时, 其它CPU内没有索引0的数据, 不需要进行同步. 但第八个CPU修改索引为7的元素时, CPU1到7都需要进行同步. 以免其它CPU将错误的数据覆盖写入到内存中.
对于IfSynchronization(8)， 每个CPU缓存行对应的数组元素索引如下
可以看出，每个CPU缓存行内的数据都是独一无二的, 因此不需要进行同步
对于IfSynchronization(0)， 每个CPU缓存行对应的数组元素索引如下
每个CPU对任何一个数据的修改都会使其它全部CPU数据进行同步.
更糟的是, 对共享数据的并行操作, 会导致最后结果不可预测, 且是错的, 加锁能够实现代码串行化, 但会严重影响效率.
1.3 测试结果
测试时不要使用VisualStudio的Release发布模式, 它会帮你优化代码, 影响测试结果
1.4 小结
为了避免缓存行同步问题, 应该保证每个线程处理连续一片的数据
多个线程之间处理的数据不要挨得太近， 缓存行同步问题在线程任务颗粒度较大时少有发生
2. 任务颗粒度过小问题
操作系统新建和销毁线程是需要时间花销的，如果线程执行的任务过于简单，管理它的代价胜于它干的活加速的时间，那么将会得不偿失。
2.1 测试代码
#include <iostream>
#include <thread>
#include <chrono>
#include <vector>
#include "global.h"
// 6线程, 执行细颗粒度任务, 线程每次处理数组1000个元素
// 6线程, 执行非细颗粒度任务, 线程每次处理数组100e3的元素
inline size_t numEntities = 100e4;
inline size_t numThreads = 6;
inline std::vector<double> v;
inline void ThreadWork(int startIx, int endIx){
// simple work. sum all value between startIx and endIx
double sum = 0L;
for (int i = startIx; i <= endIx; i++) {
sum += v[i];
}
}
inline void LaunchThread(size_t numPerThread) {
int curIx = 0;
while (curIx < numEntities) {
std::vector<std::thread> threads;
threads.reserve(numThreads);
// per thread handle 'numPerThread' value at once
for (int i = 0; i < numThreads; i++) {
int endIx = (curIx + numPerThread - 1);
std::thread t;
// Cannot cross the index scope
if (endIx >= numEntities) {
endIx = numEntities - 1;
t = std::thread(ThreadWork, curIx, endIx);
threads.push_back(std::move(t));
curIx += numPerThread;
break;
}
t = std::thread(ThreadWork, curIx, endIx);
threads.push_back(std::move(t));
curIx += numPerThread;
}
for (int i = 0; i < threads.size(); i++) {
threads[i].join();
}
}
}
inline void SingleThreadWork(std::vector<double>& v) {
double sum = 0;
for (int i = 0; i < v.size(); ++i) {
sum += v[i];
}
}
inline void TestForGrained(){
using namespace std;
typedef chrono::microseconds ms;
for (int i=0; i< numEntities; ++i){
v.push_back(i);
}
double avgFineGrained = 0, avgNoFineGrained = 0 , avgSingleThread = 0;
// execute many time in order to imporve resolution.
// fine-grained 细颗粒度线程(执行任务过于简单)
avgFineGrained = avgTime<ms>(LaunchThread, 100, 1000);
// less fine-grained
avgNoFineGrained = avgTime<ms>(LaunchThread, 100, 100e3);
// single thread
avgSingleThread = avgTime<ms>(SingleThreadWork, 100, v);
cout << "avgFineGrained finished in " << avgFineGrained << "milliseconds\n";
cout << "avgNoFineGrained finished in " << avgNoFineGrained << "milliseconds\n";
cout << "avgSingleThread finished in " << avgSingleThread << "microseconds\n";
}
2.1 测试逻辑
共需要执行100e4加法运算, 三种执行方式
- 细颗粒度多线程, 每个线程执行1000次加法
- 非细颗粒度多线程，每个线程执行100e3次加法，只需要创建10个子线程即可
- 单线程执行100e4次加法
2.2 测试结果
2.3 小结
线程并非越多越好, 因为管理新线程需要消耗CPU资源, 开辟多线程就像老板请员工, 不可能请太多的人, 每个人不可能只做一点点工作.为了充分压榨CPU的资源，应该开辟合适数量的多线程, 每个多线程做合适的工作. (CPU每秒执行约10e6次语句?)。另外，这里没有测试，但多线程数量不应该超过cpu超线程数. 使用大颗粒任务往往能避免缓存行同步问题。
3. 缓存未命中问题
计组课学习到主存和CPU速度仍然差很多，为了提高CPU利用率，而不是干等数据到来，在其中加入了三级高速缓存，高速缓存也叫Cache。有关CPU缓存的属性, 在/sys/devices/system/cpu/文件下, Linux就是这点好, 万物皆文件, 硬件也是文件, 查配置简单
因为虚拟机设置了2核4线程, 所以这里显示最多只有cpu3
CPU缓存相关在./cpu/cpu[/d+]/cache下
index0是一级数据缓存, index1是一级指令缓存, index2是二级指令和数据缓存, index3是指令和数据缓存, cache coherency缓存一致性
各级缓存大小
其中index0, index1, index2每个CPU都有, index3所有CPU共享
3.1 测试代码
#include <chrono>
#include <iostream>
#include <thread>
#include "global.h"
// 缓存行未命中 163840=10*1024*16 | 16
// 1级数据缓存 320 | 32K=1024*32B 8192
// 2及数据缓存 40 | 256K=1024*256 65536
#define ROW 320
#define COL 8192
#define REPEATCOUNT 100
inline int RowPriorityCol(int a[ROW][COL]) {
int sum = 0;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
sum += a[i][j];
}
}
return sum;
}
inline int ColPriorityRow(int a[ROW][COL]) {
int sum = 0;
for (int j = 0; j < COL; ++j) {
for (int i = 0; i < ROW; ++i) {
sum += a[i][j];
}
}
return sum;
}
inline void TestForCacheNoHit(){
using namespace std;
//int a[ROW][COL];
int (*a)[COL] = new int[ROW][COL];
double avgRowPriorityCol = 0, avgColPriorityRow = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
a[i][j] = i * j;
}
}
avgRowPriorityCol = avgTime<chrono::milliseconds>(RowPriorityCol, REPEATCOUNT, a);
avgColPriorityRow = avgTime<chrono::milliseconds>(ColPriorityRow, REPEATCOUNT, a);
delete[] a;
cout << "avgColPriorityRow finished in " << avgColPriorityRow << "milliseconds\n";
cout << "avgRowPriorityCol finished in " << avgRowPriorityCol << "milliseconds\n";
}
3.2 测试逻辑
现在有两种遍历二维数组的方式: 一种是行优先, 另一种是列优先.
行优先
inline int RowPriorityCol(int a[ROW][COL]) {
int sum = 0;
for (int i = 0; i < ROW; ++i) {
for (int j = 0; j < COL; ++j) {
sum += a[i][j];
}
}
return sum;
}
列优先
inline int ColPriorityRow(int a[ROW][COL]) {
int sum = 0;
for (int j = 0; j < COL; ++j) {
for (int i = 0; i < ROW; ++i) {
sum += a[i][j];
}
}
return sum;
}
C语言中二维数组在内存里是以一维的方式存放的. 行优先每次访问数组元素的地址是连续的, 而列优先是离散的, 会跳过一行的元素
现在只要让每次跳过元素的总大小大于64B, 32KB或256KB, 就能够模拟未击中缓存行, 未击中一级缓存和未击中二级缓存的场景. 三级缓存太大就不模拟了
例如一级缓存是32KB, 每个int类型是4B, COL * 4 >= 32K = 1024 * 32B, 解得COL => 8192, 所以只要每行有8192个元素, 隔行访问就能够一下跳过32KB的空间.
3.3 测试结果
3.4 小结
由于程序的局部性效应, CPU执行的下一条指令很可能就在缓存里. 通过减少CPU访问主存的次数来提高CPU执行效率. 所以, 尽可能让CPU读取的数据, 其内存地址跨度不要太大. 避免未命中缓存.
有关C语言数据在内存的存储方式以及C程序的内存结构可以参考
第1篇:C/C++ 内存中的数据表示 - 知乎 (zhihu.com)
第5篇:C/C++ 内存布局与程序栈 - 知乎 (zhihu.com)
4. mutex锁
当两个线程访问临界资源时, 由于执行顺序的不确定性, 会导致最后的结果不唯一, 并且是错误的. 常见的做法是加锁, 实现两个进程执行的串行化.
4.1 测试代码
#include <thread>
#include <iostream>
#include <vector>
#include <mutex>
inline int num = 0;
inline std::vector<int> vn(1);
inline std::mutex myMutex;
// num+=1不是原子操作
inline void OperateN() {
for (int i = 0; i < 10e7; ++i) {
num += 1;
}
}
// vector也不带锁
inline void OperateVN() {
for (int i = 0; i < 10e7; ++i) {
vn[0] += 1;
}
}
inline void OperateNLock() {
std::lock_guard<std::mutex> guard(myMutex);
for (int i = 0; i < 10e7; ++i) {
num += 1;
}
}
inline void TestForOperateN() {
std::thread t01 = std::thread(OperateN);
std::thread t02 = std::thread(OperateN);
t01.join();
t02.join();
std::cout << "The value of num is: " << num << std::endl;
vn[0] = 0;
t01 = std::thread(OperateVN);
t02 = std::thread(OperateVN);
t01.join();
t02.join();
std::cout << "The value of vn[0] is: " << vn[0] << std::endl;
num = 0;
t01 = std::thread(OperateNLock);
t02 = std::thread(OperateNLock);
t01.join();
t02.join();
std::cout << "The value of num is: " << num << std::endl;
}
4.2 测试原理
有两个线程, 分别使变量sum自增10e7次, 那么正确的结果应该是2 * 10e7. 但看后面测试结果, 不加锁时, 计算的结果是错误的
通过加锁, A线程在执行num += 1语句时; B线程不能够执行, 也就是说num += 1变为原子操作. 但这样明显会有问题, 也就是AB不能同时执行了. 关于锁,操作系统原理笔记写起来, 刚好这个学期学.
4.3 测试结果
两个线程修改共享数据, 即使存在缓存行同步, 依旧导致最后的结果不正确.
假设上面的线程为A,B. 要得出正确结果, 执行顺序应该为
A 读 sum -> A 执行 sum + 1 -> A 写入自增结果 -> B缓存行同步 -> B 读 sum -> B 执行 sum + 1 -> B写入自增结果 - > A缓存行同步
而事实上可能发生
A 读 sum -> B 读 sum -> A 执行 sum + 1 -> B 执行 sum + 1 -> A 写入自增结果 -> B缓存行同步 -> B写入自增结果 - > A缓存行同步
注意两种方式中, A和B读入sum值的位置, 后者对同一值的sum分别执行两次+1然后写入, 就相当于只执行一次+1.
4.4 小结
当两个线程访问临界资源时, 记得加锁. 当记住, 锁会影响多线程的执行效率. 因为当一个线程访问临界资源时, 另一个线程需要等待.
5. 总结
标签：缓存,记录,int,sum,c++,线程,inline,多线程,CPU From： https://www.cnblogs.com/laijianwei/p/17229775.html一开始对多线程理解不够, 总以为线程越多越快, 实际上线程只是交给操作系统的计划单. 真正执行还是CPU(可怜打工人). 一般程序就不要使用多线程了, 因为它较难理解. 还要注意临界资源, 缓存行同步, 共享资源竞争, 任务颗粒度等, . 但它适合计算量大的领域. 如图像处理, 我知道的两个渲染方法----光栅化和光线追踪, 处理每个屏幕像素的算法是一样且独立的(意味着不需要考虑线程之间的通讯), GPU就是因为高并行,所以适合做图像处理的(也适合挖矿).