Warum Standardmatrizenmultiplikationsalgorithmus schneller als Winograd?

[Lord Nikon]

Hi,
liegt es daran, das ich den Winograd zu schlecht implementiert habe,
oder wieso ist bei einer 1000x1000 Matrix dieser Algorthmus viel schlechter?

Winograd
public Matrices Winograd_multiply(Matrices B)
{
Matrices Result=new Matrices(this.m,B.n);
final int end=this.n/2;

float value[]=new float[this.n];
float value2[]=new float[this.n];
float value3[][]=new float[this.m][this.n];
float result=0.0f;
int tmp;
int tmp2;

for(int i=0;i!=this.m;i++)
{ value[i]=0;
value2[i]=0;
for(int k=1;k<=end;k++)
{
tmp=(2*k)-2;
tmp2=(2*k)-1;
value[i]+=this.A[i][tmp]*this.A[i][tmp2];
value2[i]+=B.A[tmp2][i]*B.A[tmp][i];

}

}
for(int i=0;i!=this.m;i++)
for(int j=0;j!=this.n;j++)
{
value3[i][j]=value[i]+value2[j];
}



for(int i=0;i!=this.m;i++)
{
for(int j=0;j!=this.n;j++)
{
for(int k=1;k<=end;k++)
{
tmp=(2*k)-2;
tmp2=(2*k)-1;
result+=(this.A[i][tmp]+B.A[tmp2][j])*(this.A[i][tmp2]+B.A[tmp][j])-value3[i][j];


}

Result.insert(j,i,result);
result=0.0f;
}


}



return Result;

}



Standardalgorithmus:


private float get_sum(int am,int bn)
{


float value=0.0f;
for(int i=0;i<this.n;i++)
{

value+=this.A[am][i]*tmp.A[i][bn];
}

return value;
}


public Matrices multiply(Matrices B)
{

float value=0.0f;
tmp=B;
Matrices Result=new Matrices(this.m,B.n);
if(this.n==B.m)
{
for(int i=0;i!=this.m;i++)
{
for(int y=0;y!=B.n;y++)
{
value=this.get_sum(i,y);
Result.insert(y,i,value);
}
}
return Result;
}
else
{
return null;
}
}

Bei 3 Multiplikation von 1000x1000 braucht der Standardalgorithmus 54 Sekunden, während der Winograd Algorithmus174 Sekunden braucht.
Programmiersprache ist Java. In der Theorie sollte Winograd schneller sein,
oder?

[Coda]

Wieso steht in deiner Signatur "Standard" extra mit d um es dann doch falsch zu schreiben? :|

[Lord Nikon]

Ich hab das Wort schon zu oft falsch geschrieben gesehen und
nun hat sich die falsche Rechtschreibung eingeprägt.

Gibt es noch was zum Thema von dir?

[zeckensack]

Da kann man 'ne Menge verbessern, auch stilistisch, aber der absolute Performance-Hammer ist das:Lord Nikon[/POST]']

for(int i=0;i!=this.m;i++)
for(int j=0;j!=this.n;j++)
{
value3[i ][j]=value[i ]+value2[j];
}Wozu? Totale Zeitverschwendung. Addieren ist viel schneller als ein Speicherzugriff. Weg damit.
Stattdessen direkt so machen: for(int i=0;i!=this.m;i++)
{
for(int j=0;j!=this.n;j++)
{
for(int k=1;k<=end;k++)
{
tmp=(2*k)-2;
tmp2=(2*k)-1;
result+=(this.A[i ][tmp]+B.A[tmp2][j])*(this.A[i ][tmp2]+B.A[tmp][j])
//Achtung: hier kommt's:
-(value[i ]+value2[j]);


}

Result.insert(j,i,result);
result=0.0f;
}
}Und auch das ist noch reichlich ineffizient, denn value+value2[j] ist [i]invariant! Raus aus der inneren Schleife damit, und stattdessen nur einmal, multipliziert mit der Anzahl der Schleifendurchläufe (end), dazuaddieren.

[zeckensack]

Vergesst alles was ich gesagt habe ... der Performance-Hammer ist natürlich die letzte Schleife, die immerhin 500Mio Mal durchlaufen wird. Die die ich bemäkelt habe würde "nur" 1Mio mal laufen.

[Lord Nikon]

Ich muss wohl blind gewesen sein, als ich den Code geschrieben habe.
55 Sekunden mit dem herkömmlichen, 51 mit Winiograd.
Vielen Dank für die Antworten Zeckensack.