Sheen Space

多处理器系统下的伪共享(false sharing)问题

leave a comment »


从CSDN博客搬家过来,原文发表于2006年09月05日06:18:00

1. 背景介绍

首先简单说一下计算机中处理器-内存体系结构。由于CPU速度远大于内存访问速度,现代CPU设计中都引入了缓存(cache)作为CPU和内存两者之间交流的缓冲中介。缓存的速度也介于两者之间。缓存中存放了最经常被访问的内存数据,CPU在很大程度上只需要访问高速缓存,大大提高了系统性能。系统对缓存进行读写的单位被称作缓存行(cache line)。大家知道系统对内存的操作单位一般是word,如果对缓存操作也用word作单位,就显得太小,缺乏效率,因此一般cache line大概是8个word,这是缓存与内存沟通的最小单位。

在可以预见的几年内,计算机系统会逐渐向多核心CPU或者多CPU结构过渡,出现多个处理核心共享内存的局面。一个很自然的问题马上出现,那就是多个处理核心对单一内存资源的访问冲突。这个冲突本来不难解决,只要给内存访问加锁就可以了。但是,当把缓存纳入考虑范围时,情况就复杂了。缓存是集成在每个CPU内部的小内存,除了这个CPU,其他CPU不能访问。而按照单CPU系统的简单缓存设计,缓存并不能察觉除本CPU以外的外部因素对内存内容的修改。因此,假设出现下面的情况:处理器A将内存中某块内容C读入自己的缓存,并在缓存中修改了该内容,然后处理器B也将内存中这块内容C读入自己的缓存,那么,B看到的只是原始版本的内容,而看不到存在于A缓存中的更新的内容,这就产生了内容不一致的问题。多处理器系统一般是设计控制协议来协调各个CPU缓存读写,保证内容一致,以解决这种冲突。

2. 伪共享

顾名思义,“伪共享”就是“其实不是共享”。那什么是“共享”?多CPU同时访问同一块内存区域就是“共享”,就会产生冲突,需要控制协议来协调访问。会引起“共享”的最小内存区域大小就是一个cache line。因此,当两个以上CPU都要访问同一个cache line大小的内存区域时,就会引起冲突,这种情况就叫“共享”。但是,这种情况里面又包含了“其实不是共享”的“伪共享”情况。比如,两个处理器各要访问一个word,这两个word却存在于同一个cache line大小的区域里,这时,从应用逻辑层面说,这两个处理器并没有共享内存,因为他们访问的是不同的内容(不同的word)。但是因为cache line的存在和限制,这两个CPU要访问这两个不同的word时,却一定要访问同一个cache line块,产生了事实上的“共享”。显然,由于cache line大小限制带来的这种“伪共享”是我们不想要的,会浪费系统资源。

举例来说,当多进程程序操作同一个int型数组int a[100]时,如果进程0只访问a[0],进程1只访问a[1],进程2只访问a[2],… 那么,实际上每个进程不应该发生数据共享。但是,一般cache line可以包含几个int,因此访问同一个cache line内int数组元素的几个进程就需要系统花费额外资源和时间运用控制协议来协调,这是不必要的。在这种情况下,把每个数组元素单独放在一个cache line大小的内存区域里在时间上是最有效率的,然而空间上就变成最没效率的了。

计算机设计就是处理矛盾的艺术。

3. 程序演示

下面用一个简单的小程序来验证False Sharing对性能的影响。

这个小程序同时运行两个线程,对同一块内存区域的临近位置进行int大小的多次读写。线程1读写第1个int值,线程2读写第2个int值。按照预想,如果两个int相隔太近,落入同一个cache line,两个线程就会因为”伪共享”而花费额外的时间进行缓存一致性通信和维护,造成性能下降。

TestFalseSharing.cpp 是主程序,Thread.h/cpp 是对Win32 Thread API的简单封装,Timer.h/cpp是对CRT time函数的简单封装。

TestFalseSharing.cpp

// TestFalseSharing.cpp

#include "stdafx.h"
#include "Thread.h"
#include "Timer.h"

#define COUNT 3000000000
#define DISTANCE 4

DWORD WINAPI t1_p(void* a)
{
	int* arr = (int*)a;
	for (int i=0; ii++)
		arr[0] = 30;

	return 0;
}

DWORD WINAPI t2_p(void* a)
{
	int* arr = (int*)a;
	for (int i=0; i<COUNT; i++)
		arr[DISTANCE] = 30;

	return 0;
}

int arr[64];

int main(int argc, char* argv[])
{
	yshi::Timer timer(std::cout);

	// Start threads
	yshi::WinThread t1(t1_p, arr);
	yshi::WinThread t2(t2_p, arr);

	// Wait for all threads to terminate
	t1.Wait();
	t2.Wait();

	timer.Stop();

	return 0;
}

Thread.h

// Thread.h

namespace yshi
{

typedef LPTHREAD_START_ROUTINE WinThreadProc; // int func_name(void*)

// This class is exported from the Win32.dll
class WIN32_API WinThread
{
public:
	WinThread(WinThreadProc aProc, void* aParam, bool aSuspend = false);
	void Resume();
	void Wait();
	virtual ~WinThread();
private:
	HANDLE _handle;
private:
	WinThread(const WinThread&);
	WinThread& operator=(const WinThread&);
};

}

Thread.cpp

// Thread.cpp

#include "stdafx.h"
#include "Thread.h"

namespace yshi
{

WinThread::WinThread(WinThreadProc aProc, void* aParam, bool aSuspend)
{
	HANDLE h = CreateThread(NULL, 0, aProc, aParam, aSuspend ? 0x04 : 0x00, NULL);
	if (h == NULL)
	{
		throw GetLastError();
	}

	_handle = h;
}

void WinThread::Resume()
{
	DWORD ret = ResumeThread(_handle);
	if (ret == -1)
	{
		throw GetLastError();
	}
}

void WinThread::Wait()
{
	DWORD ret = WaitForSingleObject(_handle, INFINITE);
	if (ret == WAIT_FAILED)
		throw GetLastError();
}

WinThread::~WinThread()
{
	if (_handle != 0)
		CloseHandle(_handle);
}

}

Timer.h

// Timer.h

namespace yshi
{

class DEBUGUTIL_API Timer
{
public:
	Timer(std::ostream& aOutput);
	~Timer();
	void Start();
	void Stop();
private:
	void Print(std::ostream& aOutput);
private:
	std::ostream& mOutput;
	unsigned long long mTimeDiff;
private:
	Timer& operator=(const Timer&);
};

}

Timer.cpp

// Timer.cpp

#include "Timer.h"

#include <ctime>

namespace yshi
{

Timer::Timer(std::ostream& aOutput) : mOutput(aOutput)
{
	Start();
}

Timer::~Timer()
{
}

void Timer::Start()
{
	mTimeDiff = time(0);
}

void Timer::Stop()
{
	mTimeDiff = time(0) - mTimeDiff;
	Print(mOutput);
}

void Timer::Print(std::ostream& aOutput)
{
	aOutput << "Time spent: " << mTimeDiff << " seconds\n";
}

}

4. 运行结果

数据距离(DISTANCE)    花费时间(秒)

4                                                    21
8                                                    21
16                                                  10
32                                                  10

可以看到,当距离达到16个int,也就是64字节的时候,”伪共享”消失,而64字节也就是我的机器的cache line大小。

Advertisements

Written by Ying

20/09/2010 at 18:31

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: