平方数数字和

无心人 · 发表于 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# 无心人的帖子