平方数数字和

无心人 · 发表于 2008-7-30 07:47:31

找到不进行分支而进位的SIMD写法假设 XMM0保存平方 XMM7保存Delta XMM6保存四个10000 XMM5保存四个1 pmovdqa xmm3, xmm0 pcmpged xmm3, xmm6 pmovdqa xmm4, xmm3 pand xmm3, xmm6 paddd xmm0, xmm3 psldq xmm4, 4 pand xmm4, xmm5 psubd xmm0, xmm4 则顺序执行三次就可调整三个进位现在问题是如果一次装8个word，执行7次，则可完全调整如果像上面一次4个dword，还需要中间把最高位双字单独处理次还有就是不知道这么多条指令并行度如何？粗略略计算是6个时钟感觉是用dword做好些，重复7次完成调整同样道理delta的加2也可重复三次完成至于溢出，我想暂时遇不到，呵呵毕竟好几年才能溢出的谁测试下啊？

gxqcn · 发表于 2008-7-30 09:12:12

其实，本算法主要是加减、进位等算术指令，用 ALU 算术单元足矣，比 SIMD 更划算，尤其是涉及到有进位处理的过程。 ALU 指令可以 U、V 双通道并行，且进位处理过程中的跳转指令完全可由非跳转指令替代（需手工编写汇编代码，我不相信编译有如此智能），即可完全消除因跳转预测失败带来的惩罚，由此速度将可大幅提高，甚至提速1倍以上！但我不想在此花这个功夫去优化了，因为需要手工编写大量的汇编代码。

无心人 · 发表于 2008-7-30 09:51:18

老大啊你还说U, V通道么？你应该知道U, V是PIII之前的东西了 P4是5个执行单元哦另外，写汇编不比C代码复杂多少呵呵，就是打字多点，调试麻烦些吧你说的非跳转调整方式是什么意思？ ALU方式和SSE2 ALU方式延迟时间比是1:4，吞吐量比是1:2 但SSE2能一次处理8个word，正好是我们所用的范围另外，我考虑用BTS指令处理位组合，似乎比数组写标志要好些？还有，似乎压缩数据大小到L1 Data是有可能实现的? P4以上的CPU L1 Data Cache到底多大？ 8k还是16k ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝刚知道了Free Pascal如何嵌入汇编了考虑在学校的机器上也装个呵呵反正到汇编这个级别什么编译器都能写优化代码了

无心人 · 发表于 2008-7-30 12:51:42

GxQ是否打算使用CMOVcc指令？

mov eax, square
add eax, delta
mov ebx, square+4
add ebx, delta+4
mvo ecx, square+8
add ecx, delta+8
mov edx, square+12
add edx, delta+12
mov esi, eax
sub esi, 10000
cmovnc eax, esi
cmc
adc ebx, 0
mov edi, ebx
sub edi, 10000
cmovnc ebx, edi
cmc
adc ecx, 0
mov esi, ecx
sub esi, 10000
cmovnc ecx, esi
cmc
adc edx, 0
mov edi, edx
sub edi, 10000
cmovnc edx, edi
cmc
adc square+16, 0
....
....

复制代码

突然发现上面的代码很有意思可能能大幅度减少代码使用条数可以连数位和都一起算了不过寄存器要节约点用了呵呵 =========================== PS: ADC, CMOVcc, CMC在P4上都是慢操作，Core2上好多了可能这么写代码在Core2以上效果好很多吧 P4上不知道如何了，哎

无心人 · 发表于 2008-7-30 20:07:11

下午测试了，似乎效果不很显著因为一开始的计算不如原始的多算了很多在考虑是否先把目前的算法翻译成汇编另外刚更新了137＃的结果和GxQ的结果持平了再继续挂就会出新结果了他计算了8小时，我想我这里要挂24小时出新结果吧大概是明天这个时候看吧如果还不出，恐怕以后出一个新结果就要等几天了呵呵

gxqcn · 发表于 2008-7-30 22:04:33

注意到我在 96# 中将几个数组合并为一个大数组，这样在写汇编时可以更方便通过偏移进行定位。另外，想请教一下：CMOVcc系列指令是否在后期的CPU都支持？包括64位系统下的？

无心人 · 发表于 2008-7-31 08:41:32

似乎是P5引入的吧都支持的，包括64位而且支持所有标志的但似乎P4的延迟高些 Core2低的多了

无心人 · 发表于 2008-7-31 08:43:04

我把我新写的尽量少分支的Pasal贴上来GxQ看看吧还有两个跳转无法消除，哎另外程序得到和GxQ相同的结果后已运行了14小时了还没出新结果，效率大约相当于GxQ程序的1/2 所以过4个小时将超越38小时的运行结果哦

program square;
uses SysUtils;
const
TenPower = 10000;
StatusFileName = 'Square.Status';
LogFileName = 'Square.Log';
BlockSize = 8;
BoolSize = 320;
type
TStatus = record
S:array[0..BoolSize - 1] of integer;
SquareValue:array[0..BlockSize - 1] of integer;
Delta:array[0..BlockSize - 1] of integer;
end;
var
Status:TStatus;
StatusFile: File of TStatus;
LogFile:TextFile;
SumOfDigit4: array[0..TenPower - 1] of integer;
ExeFilePath: string;
Counter:Integer;
s: integer;
procedure WriteLog (s:string);
begin
Assign (LogFile, ExeFilePath + LogFileName);
if FileExists(ExeFilePath + LogFileName) then
Append (LogFile)
else
Rewrite (LogFile);
writeln (LogFile, s);
Close (LogFile);
end;
procedure InitStatus;
var
i:integer;
begin
for I := 0 to BoolSize - 1 do
Status.s[i]:= 0;
for i := 0 to BlockSize - 1 do
begin
status.SquareValue[i]:= 0;
status.delta[i]:= 0;
end;
Status.Delta[0]:= 1;
end;
procedure ReadStatus;
begin
Assign (StatusFile, ExeFilePath + StatusFileName);
if FileExists(ExeFilePath + StatusFileName) then
begin
Reset (StatusFile);
Read (StatusFile, Status);
Close (StatusFile);
end
else
InitStatus;
end;
procedure WriteStatus;
begin
Assign (StatusFile, ExeFilePath + StatusFileName);
Rewrite (StatusFile);
Write (StatusFile, Status);
Close (StatusFile);
end;
procedure InitSumOfDigit4;
var
i3, i2, i1, i0, k:integer;
begin
k:= 0;
for I3 := 0 to 9 do
for I2 := 0 to 9 do
for I1 := 0 to 9 do
for I0 := 0 to 9 do
begin
SumOfDigit4[k]:= i3 + i2 + i1 + i0;
INC (k);
end;
end;
procedure WriteResult;
var
Str:String[128];
i:integer;
begin
Str:= '';
for i := BlockSize-1 downto 0 do
if Status.SquareValue[i] > 0 then
Str:= str + Format ('%4d', [Status.SquareValue[i]]);
writeln (DateTimeToStr (now) + ': ' + IntToStr (s) + ' ' + str);
writelog (DateTimeToStr (now) + ': ' + IntToStr (s) + ' ' + str);
end;
label label0, label1;
begin
WriteLog ('程序启动: ' + DateTimeToStr (now));
WriteLn ('程序启动: ' + DateTimeToStr (now));
ExeFilePath:= ExtractFilePath (ParamStr(0));
Counter:= 0;
InitSumOfDigit4;
ReadStatus;
WriteLog ('初始化完成: ' + DateTimeToStr (now));
WriteLn ('初始化完成: ' + DateTimeToStr (now));
//ADDDelta
asm
label0:
mov eax, dword ptr [Status.SquareValue]
add eax,dword ptr [Status.Delta]
mov ebx,dword ptr [Status.SquareValue + 4]
add ebx,dword ptr [Status.Delta + 4]
mov esi, eax
sub esi, TenPower
cmovnc eax, esi
cmc
adc ebx, 0
mov edx,dword ptr [SumOfDigit4 + 4 * eax]
mov dword ptr [Status.SquareValue], eax
mov eax,dword ptr [Status.SquareValue + 8]
add eax,dword ptr [Status.Delta + 8]
mov edi, ebx
sub edi, TenPower
cmovnc ebx, edi
cmc
adc eax, 0
mov dword ptr [Status.SquareValue + 4], ebx
add edx,dword ptr [SumOfDigit4 + 4 * ebx]
mov ebx,dword ptr [Status.SquareValue + 12]
add ebx,dword ptr [Status.Delta + 12]
mov esi, eax
sub esi, TenPower
cmovnc eax, esi
cmc
adc ebx, 0
mov dword ptr [Status.SquareValue + 8], eax
add edx,dword ptr [SumOfDigit4 + 4 * eax]
mov eax,dword ptr [Status.SquareValue + 16]
mov edi, ebx
sub edi, TenPower
cmovnc ebx, edi
cmc
adc eax, 0
mov dword ptr [Status.SquareValue + 12], ebx
add edx,dword ptr [SumOfDigit4 + 4 * ebx]
mov ebx,dword ptr [Status.SquareValue + 20]
mov esi, eax
sub esi, TenPower
cmovnc eax, esi
cmc
adc ebx, 0
mov dword ptr [Status.SquareValue + 16], eax
add edx,dword ptr [SumOfDigit4 + 4 * eax]
mov eax,dword ptr [Status.SquareValue + 24]
mov edi, ebx
sub edi, TenPower
cmovnc ebx, edi
cmc
adc eax, 0
mov dword ptr [Status.SquareValue + 20], ebx
add edx,dword ptr [SumOfDigit4 + 4 * ebx]
mov ebx,dword ptr [Status.SquareValue + 28]
mov esi, eax
sub esi, TenPower
cmovnc eax, esi
cmc
adc ebx, 0
mov dword ptr [Status.SquareValue + 24], eax
mov dword ptr [Status.SquareValue + 28], ebx
add edx,dword ptr [SumOfDigit4 + 4 * eax]
add edx,dword ptr [SumOfDigit4 + 4 * ebx]
mov dword ptr [s], edx
mov eax, 1
xchg eax,dword ptr [Status.S + 4 * edx]
cmp eax, 1
je label1
call WriteResult;
label1:
mov eax,dword ptr [Status.Delta]
mov ebx,dword ptr [Status.Delta + 4]
mov ecx,dword ptr [Status.Delta + 8]
mov edx,dword ptr [Status.Delta + 12]
add eax, 2
mov esi, eax
sub esi, TenPower
cmovnc eax, esi
cmc
adc ebx, 0
mov edi, ebx
sub edi, TenPower
cmovnc ebx, edi
cmc
adc ecx, 0
mov esi, ecx
sub esi, TenPower
cmovnc ecx, esi
cmc
adc edx, 0
mov dword ptr [Status.Delta], eax
mov dword ptr [Status.Delta + 4], ebx
mov dword ptr [Status.Delta + 8], ecx
mov dword ptr [Status.Delta + 12], edx
inc dword ptr [Counter]
jne Label0
call WriteStatus
jmp label0
end;
end.

复制代码

下面是三个我编译的程序 GxQ运行下，因为有中断运行后自动恢复机制，要在不同目录运行，运行到产生157的地方停止帮我看下在你机器上的时间信息

1.tar.bz2 (47.79 KB, 下载次数: 3)

gxqcn · 发表于 2008-7-31 10:21:25

对不起，我不会用Pasal。

无心人 · 发表于 2008-7-31 11:14:07

编译好了的

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 平方数数字和

回复 144# 无心人的帖子

[擂台] 平方数数字和

回复 144# 无心人 的帖子

回复 144# 无心人的帖子