3. IDCT Algorithmus optimieren

IDCT Algorithmus optimieren

  • ?

    Mach doch einfach ein Lookuptable. Untegesteter Pseudocode:

    float IDCT::coscalc(int i, int j, int k, int l){
  return discrete_cos(i, j)*discrete_cos(k, l);
}

std::vector<float> make_type()
{
  std::vector<float> ret(8*8);
  for (int i=0; i<8; ++i)
    for (int j=0; j<8; ++j)
      ret[8*i+j] = std::cos((((2*i)+1)*j*PI)/16);
  return ret;
}

float discrete_cos(int i, int j) {
  static vector<float> table = make_type();
  return table[8*i + j];
}
    0
  • F

    Wow das hat schon mal was gebracht! Ich hab es so gemacht:

    void IDCT::iDCT(int startmatrix[8][8], int check){
  Check = check;
  coscalc();
  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      for(int k = 0; k<8; ++k){
        for(int l = 0; l<8; ++l){
          Result += 0.25*(ccalc(k)*ccalc(l)*startmatrix[k][l]*LUT_idct[i][j]*LUT_idct[k][l]);//iDCT
        }//l
      }//k
      Result += 128;
      colorfiller(Result, Check);
      Result = 0;
    }//j
  }//i
  Check = 0;
}

    void IDCT::coscalc(){
  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      LUT_idct[i][j] = std::cos((((2*i)+1)*j*PI)/16);
    }
  }
}

    Na gut das kann man jetzt noch weiter optimieren hab es nur auf die schnelle mal ausprobiert. 😃 Morgen geht es weiter jetzt ist Feierabend.

    0
  • ?

    Oder du lagerst wirklich alles aus und nimmst 4KB overhead in kauf:

    void set_lookup(int i, int j)
{
	for(int i = 0; i<8; ++i){ 
     for(int j = 0; j<8; ++j){ 
       for(int k = 0; k<8; ++k){ 
         for(int l = 0; l<8; ++l){ 
			lookup[i][j][k][l]=	0.25 * std::cos((((2*i)+1)*k*PI)/16)
								* std::cos((((2*j)+1)*l*PI)/16)
								* ccalc(k) * ccalc(l);

}

void IDCT::iDCT(int startmatrix[8][8], int check){ 
   Check = check; 
   for(int i = 0; i<8; ++i){ 
     for(int j = 0; j<8; ++j){ 
       for(int k = 0; k<8; ++k){ 
         for(int l = 0; l<8; ++l){ 
           Result += startmatrix[k][l]*lookup[i][j][k][l]);//iDCT 
         }//l 
       }//k 
       Result += 128; 
       colorfiller(Result, Check); 
       Result = 0; 
     }//j 
   }//i 
   Check = 0; 
} 

/************************************** 
  *********Inline functions imp********* 
  **************************************/ 

float IDCT::ccalc(int wert){ 
   if(wert == 0){ 
     return SQT; //return the define 
   }else{ 
     return 1; 
   } 
}
    0
  • Mod

    Der Cosinus ist hier bloß eine Nebenbaustelle. Das erste sollte wohl die Benutzung einer fast cosinus transform sein. So senkt man die Komplexität von 4096 Berechnungen auf etwas in der Gegend um 384.

    0
  • ?

    Du brauchst natürlich noch nen array

    double lookup[8][8][8][8];

    und set_lookup muss keine argumente nehmen. Und Overhead ist 32KB (8*8*8*8*sizeof(double) / 1024) = 32 KB 😃

    0
  • K

    Transforms of real even/odd data: the discrete cosine transform (DCT) and the discrete sine transform (DST), types I-IV

    www.fftw.org

    0
  • M

    Was für Compileroptionen verwendest du denn? Diesen Algorithmus könnte man prima mit SSE Instruktionen beschleunigen.

    Wenn es nicht so genau sein muss, ist auch eine Annäherung an die Cosinusfunktion möglich. Hierbei ist aber wohl das Lookuptable die bessere Alternative.

    Vielleicht kannst du ccalc auch so schreiben, ich bin mir aber ziemlich sicher, dass der Compileroptimierer aus beidem das gleiche bzw. gleich schnelles macht.

    float ccalc(int k, int l)
{
    static constexpr float array[3]= { 1, SQT, SQT*SQT };
    return array[(k==0)+(l==0)];
}
    0
  • ?
     

    void IDCT::iDCT(int startmatrix[8][8], int check){
  Check = check;
  coscalc();
  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      for(int k = 0; k<8; ++k){
        for(int l = 0; l<8; ++l){
          Result += 0.25*(ccalc(k)*ccalc(l)*startmatrix[k][l]*LUT_idct[i][j]*LUT_idct[k][l]);//iDCT
        }//l
      }//k
      Result += 128;
      colorfiller(Result, Check);
      Result = 0;
    }//j
  }//i
  Check = 0;
}

    Jetzt kommt der nächste Schritt: Schau dir das doch mal an von was das jeweils abhängig ist:

    0.25 // konstante
*ccalc(k)*ccalc(l) // l+k
*startmatrix[k][l]* // l+k
LUT_idct[i][j]* // i+j
LUT_idct[k][l]; // l+k

    Konstanten kann man ausklammern und das, was nur von i+j abhängig ist kann man ausklammern.

    Wenn ich nichts übersehe, wäre das ja:

    void IDCT::iDCT(int startmatrix[8][8], int check){
  Check = check;
  coscalc();

  // der k+l-Teil:
  float kl_result = 0;
      for(int k = 0; k<8; ++k){
        for(int l = 0; l<8; ++l){
          Result += ccalc(k)*ccalc(l)*startmatrix[k][l]*LUT_idct[k][l];// loop unrolling macht hoffentlich das ccalc weg
        }//l
      }//k
  kl_result *= 0.25;

  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      float Result = kl_result * LUT_idct[i][j];
      Result += 128;
      colorfiller(Result, Check);
      Result = 0;
    }//j
  }//i
  Check = 0;
}

    Von O(8^4) auf O(8^2), das bringt mehr als SSE oder Lookup.

    0
  • F

    asdfasdf schrieb:

    Oder du lagerst wirklich alles aus und nimmst 4KB overhead in kauf:

    void set_lookup(int i, int j)
{
	for(int i = 0; i<8; ++i){ 
     for(int j = 0; j<8; ++j){ 
       for(int k = 0; k<8; ++k){ 
         for(int l = 0; l<8; ++l){ 
			lookup[i][j][k][l]=	0.25 * std::cos((((2*i)+1)*k*PI)/16)
								* std::cos((((2*j)+1)*l*PI)/16)
								* ccalc(k) * ccalc(l);
								
}
	
void IDCT::iDCT(int startmatrix[8][8], int check){ 
   Check = check; 
   for(int i = 0; i<8; ++i){ 
     for(int j = 0; j<8; ++j){ 
       for(int k = 0; k<8; ++k){ 
         for(int l = 0; l<8; ++l){ 
           Result += startmatrix[k][l]*lookup[i][j][k][l]);//iDCT 
         }//l 
       }//k 
       Result += 128; 
       colorfiller(Result, Check); 
       Result = 0; 
     }//j 
   }//i 
   Check = 0; 
} 
   
/************************************** 
  *********Inline functions imp********* 
  **************************************/ 
   
float IDCT::ccalc(int wert){ 
   if(wert == 0){ 
     return SQT; //return the define 
   }else{ 
     return 1; 
   } 
}

    Da ist meins was ich gepostet hab schneller.

    0
  • F

    Vielen dank ich werde die weiteren Tipps morgen umsetzen muss jetzt echt nach Hause. 😉 Bin schon viel zu lange hier.

    0

  • @Fuchs aus dem Wald
    Wie geht's deinem JPEG Decoder?

    0
  • F

    lucky uppe schrieb:

    void IDCT::iDCT(int startmatrix[8][8], int check){
  Check = check;
  coscalc();
  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      for(int k = 0; k<8; ++k){
        for(int l = 0; l<8; ++l){
          Result += 0.25*(ccalc(k)*ccalc(l)*startmatrix[k][l]*LUT_idct[i][j]*LUT_idct[k][l]);//iDCT
        }//l
      }//k
      Result += 128;
      colorfiller(Result, Check);
      Result = 0;
    }//j
  }//i
  Check = 0;
}

    Jetzt kommt der nächste Schritt: Schau dir das doch mal an von was das jeweils abhängig ist:

    0.25 // konstante
*ccalc(k)*ccalc(l) // l+k
*startmatrix[k][l]* // l+k
LUT_idct[i][j]* // i+j
LUT_idct[k][l]; // l+k

    Konstanten kann man ausklammern und das, was nur von i+j abhängig ist kann man ausklammern.

    Wenn ich nichts übersehe, wäre das ja:

    void IDCT::iDCT(int startmatrix[8][8], int check){
  Check = check;
  coscalc();

  // der k+l-Teil:
  float kl_result = 0;
      for(int k = 0; k<8; ++k){
        for(int l = 0; l<8; ++l){
          Result += ccalc(k)*ccalc(l)*startmatrix[k][l]*LUT_idct[k][l];// loop unrolling macht hoffentlich das ccalc weg
        }//l
      }//k
  kl_result *= 0.25;

  for(int i = 0; i<8; ++i){
    for(int j = 0; j<8; ++j){
      float Result = kl_result * LUT_idct[i][j];
      Result += 128;
      colorfiller(Result, Check);
      Result = 0;
    }//j
  }//i
  Check = 0;
}

    Von O(8^4) auf O(8^2), das bringt mehr als SSE oder Lookup.

    Wow danke schön das hat wirklich viel gebracht!

    hustbaer schrieb:

    @Fuchs aus dem Wald
    Wie geht's deinem JPEG Devocer?

    Ganz gut läuft zu mindestens. 😃 Wie du siehst optimiere ich grade noch ein bisschen. Also es ist irgendwie nicht wunderschön aber es funktioniert! 😉 Ja geschafft hab ich es!

    EDIT:
    Für die ccalc könnte ich auch einfach ein Array nehmen mit den Werten: array = {0,1,1,1,1,1,1,1}

    EDIT2:
    Bin jetzt mal vorher nachher mit callgrind rüber. ^^
    Von 460.000.000 auf 3.600.000 aufrufe. Ich finde das schon ziemlich gut! 😃

    0
Anmelden zum Antworten