Utveckling med OpenCL

Efter att länge ha varit nyfiken, har jag nu tagit steget och börjat använda OpenCL. För dig som inte vet vad det är, är det ett standardiserat sätt att kunna använda en grafikprocessor till generell beräkning, inte bara grafik. Den råa prestandan i ett modernt grafikkort är många gånger större än för en normal processor, men har helt andra egenskaper och kan inte alltid utnyttjas för alla typer av problem.

Jag tog en existerande algoritm jag jobbat mycket med och implementerade delar av den. På min medelmåttiga laptop, med teoretisk prestanda 155 GFLOPS lyckades jag genomföra beräkningarna en faktor 30 snabbare än på cpu:n! Detta helt utan att försöka optimera koden. Ett grafikkort för stationära datorer i 5000 kr-klassen når ca 3000 GFLOPS. Med ett sådant kort skulle alltså prestanda kunna öka till en faktor 600 gånger snabbare än cpu, för mitt problem. Tack alla ni som spelar datorspel och finansierar denna fantastiska utveckling!

Det tog ett tag att läsa igenom dokumentationen och förstå hur det är tänkt att fungera. Jag rekommenderar att läsa många olika tutorials innan man börjar, eftersom det är ganska annorlunda mot "vanlig" programmering och varje författare förklarar på olika sätt.

En liten disclaimer:
för att nå höga prestanda behöver man göra avkall på beräkningsprecisionen, samt kunna dela upp sitt problem i parallella delar. Därutöver tillkommer fördröjning när problemet ska flyttas till grafikkortsminnet, och kerneln kompileras. Och så behöver man installera ickefri programvara...

Använda alla bibliotek från boost

Jag träffade nyligen en c++-utvecklare som precis som jag är en varm anhängare av boost. Han hade använt, med något enstaka undantag, alla boostbibliotek! Jag blev omedelbart imponerad.

Jag går igenom listan själv och konstaterar att jag faktiskt använt 27 av biblioteken i verkliga projekt. Har satt en asterisk framför de jag använt hittills.
Listan finns här för version 1.48 (senaste i skrivande stund). Den innehåller imponerande 111 bibliotek! (en del listas förvissa som flera).

Jag får en viss lust att gå igenom de resterande och skriva ett litet program för var och en av dom. Det får vänta till nån sömnlös natt...

1. Accumulators
2. *Any
3. *Array
4. *Asio
5. *Assign
6. *Bimap
7. *Bind
8. Call Traits
9. Chrono
10. *Circular Buffer
11. Compatibility
12. Compressed Pair
13. Concept Check
14. Config
15. Container
16. Conversion
17. *CRC
18. *Date Time
19. Disjoint Sets
20. Dynamic Bitset
21. Enable If
22. Exception
23. *Filesystem
24. Flyweight
25. *Foreach
26. Format
27. Function
28. Function Types
29. Functional
30. Functional/Factory
31. Functional/Forward
32. Functional/Hash
33. Fusion
34. Geometry
35. GIL
36. *Graph
37. ICL
38. In Place Factory, Typed In Place Factory
39. *Integer
40. *Interprocess
41. Interval
42. Intrusive
43. *IO State Savers
44. *Iostreams
45. Iterators
46. Lambda
47. Lexical Cast
48. Locale
49. Math
50. Math Common Factor
51. Math Octonion
52. Math Quaternion
53. Math/Special Functions
54. Math/Statistical Distributions
55. Member Function
56. Meta State Machine
57. Min-Max
58. Move
59. MPI
60. MPL
61. Multi-Array
62. Multi-Index
63. *Numeric Conversion
64. Operators
65. Optional
66. Parameter
67. Phoenix
68. Pointer Container
69. Polygon
70. Pool
71. Preprocessor
72. *Program Options
73. *Property Map
74. *Property Tree
75. Proto
76. Python
77. *Random
78. Range
79. Ratio
80. Rational
81. *Ref
82. *Regex
83. Result Of
84. Scope Exit
85. *Serialization
86. Signals
87. Signals2
88. *Smart Ptr
89. Spirit
90. Statechart
91. Static Assert
92. String Algo
93. Swap
94. System
95. *Test
96. *Thread
97. Timer
98. Tokenizer
99. TR1
100. Tribool
101. *Tuple
102. Type Traits
103. Typeof
104. Units
105. Unordered
106. Utility
107. *Uuid
108. Value Initialized
109. Variant
110. Wave
111. Xpressive

Avsiktligt felaktig kod

Nyligen dök det upp anklagelser om avsiktligt inplacerade felaktigheter i krypteringsfunktioner i openbsd. Felaktigheterna skulle göra att FBI kan avkryptera information lättare. Väldigt obehagligt, men verkar inte vara så farligt som det lät.
I efterdiskussionerna kom en intressant tävling upp: en tävling där det gäller att avsiktlig programmera fel, på ett sådant sätt att funktionen ser helt korrekt ut men att koden utför något annat än man tror.

Här visas ett program som tar en bildfil och målar svart i en rektangel, t ex för att dölja ett ansikte eller text. Programmet fungerar som avsett, men lyckas ändå gömma bildinformation i den behandlade bilden. Den som blankar ut rektangeln tror att bildinformationen är borta, men den som känner till hemligheten kan delvis återskapa informationen. Koden ser helt oskyldig ut! Se själv här för noggrann diskussion.

Beräkning av medelvärde i vektor

Den här funktionen beräknar medelvärdet av talen i en vektor.
Jag får den bara att gå i ca 0.7 element per klockcykel, mätt på en miljon anrop med en 100 element lång vektor. (optimeringsnivå -O3, gcc 4.2.3, Intel core 2 quad)
Någon som vet något sätt att få koden snabbare? Eller är det här den prestanda man kan förvänta sig?

   int AverageLU(const std::vector<double>& x,

         double& result) {
    result=0.0;
    
    const size_t N=x.size();

    if(0==N) {
      return -1;
    }


    size_t i=0;
    double r0=0.0;
    double r1=0.0;

    double r2=0.0;
    double r3=0.0;
    if(N>=4) {

      //how many full groups of 4 do we have?
      const size_t N4=(N/4-1)*4;
      for(i=0; i<N4; i+=4) {      
 r0+=x[i  ];

 r1+=x[i+1];
 r2+=x[i+2];

 r3+=x[i+3];
      }
    }
    for(; i<N; ++i) {

      r0+=x[i];
    }
      
    result=(r0+r1+r2+r3)/double(N);

return 0;
}

Räkna rader i filer

Jag undrade hur många rader kod jag skrivit i ett projekt - såhär enkelt var det att göra ett bashscript som räknade rader!

#!/bin/bash
echo -n "The number of source lines is "
( echo 0;
for ending in cc hh ; do
find . -name "*."$ending -print | (
while read banan ; do
wc -l <"$banan"
echo '+'
done
)
done ; echo p
) | dc

Fundering

Jag sitter just nu och kodar en algoritm i c++. Har stött på ett intressant problem!

Låt x vara en icketom mängd reella, ändliga tal. Vi kan för enkelhetens skull bortse från möjligheten att några av dem är noll. Vi bortser också från specialfall där median(x)=0
Jag behöver funktionaliteten sign(median(x)) vilken är lite knepig att räkna ut utan att skriva lite kod (med std::nth_element(...) såklart...). Är det ekvivalent att vända uttrycket? (detta gör att det går att implementera enklare i mitt fall)
dvs, är
sign(median(x))=a ====>>>>> median(sign(x))=a
sant i allmänhet?





(mer fundering längre ner, låt bli att läs om du vill fundera ifred)






Det verkar som att så är fallet. Om sign(median(x))=1 betyder det att medianen av x är>0. Då är minst 50% av värdena i x positiva. Om minst 50% av värdena i x är positiva kommer minst 50% av värdena i sign(x) vara positiva. Då kommer median(sign(x)) att vara 1. Samma resonemang kan tillämpas med minst bytt mot högst för sign(median(x))=-1.
Andra riktningen då?
Om median(sign(x))=1 betyder det att minst 50% av sign(x)=1. Det betyder att minst 50% av x är >0. Då är median(x)>0 och sign(median(x))=1. Samma med minst bytt mot högst.

Kul, det är alltså ekvivalent bortsett från specialfall!

Skriva bra kod

Jag har tidigare skrivit om en mycket bra text om hur kan man skriva effektiv kod. (se http://paulsundvall.blogspot.com/2008/01/optimera-kod.html)

Nu har jag råkat på en annan liknande text från AMD, inriktad på just deras arkitektur. Även om den riktar sig till just AMD är några av råden allmängiltiga.
Det är kapitel två som jag avser, i denna pdffil:
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/40546.pdf

Optimera kod

Den här pdf-filen innehåller mycket intressanta tips om hur optimering av kod kan gå till. Exempel på vad som är snabbt och långsamt att göra på de vanligaste processorerna gås igenom.
Rekommenderas till nyfikna programmerare!

http://www.agner.org/optimize/optimizing_cpp.pdf

Uppdatering:
trots att jag faktiskt läst igenom filen ovan så missade jag en ganska lätt grej:
Koden nedan ska leta efter den första positiva nollgenomgången i vektorn x.

Originalkoden ser ut så här:

const size_t N=x.size();
size_t Ihigh=0;//index of right point
size_t Ilow=0; //index of left point
for(size_t i=1;i<n;++i) {
  if(x(i-1)<=0.0 && x(i)>0.0) {           
      Ihigh=i;         
      continue;
    }  //end if
} //end for

Jag vet att x nästan alltid är negativ i början och positiv på slutet. Därför kommer första villkoret i nästan alltid vara sann och andra villkoret måste också evalueras.
En bättre lösning är alltså att byta ordning på testen så att det första testet är falskt oftast.

const size_t N=x.size();
size_t Ihigh=0;//index of right point
size_t Ilow=0; //index of left point
for(size_t i=1;i<n;++i) {
  if(x(i)>0.0 && x(i-1)<=0.0) {   //<---här är ändringen        
      Ihigh=i;         
      continue;
    }  //end if
} //end for

Ergonomiska keyboards

Fick ett tips om ergonomiska keyboards:
http://www.kinesis-ergo.com/keyboards.htm
Själv kör jag ett fujitsu siemens delat keyboard, jättebra för handlederna.

Ett problem för många programmere är att tecken som [] {} är väldigt styvmoderligt behandlade. Möjliga botemedel:

• använd amerikansk layout
• dvorak-layout
• göra en egen layout baserat på vad man skriver (otroligt! hörde om en kille som hade gjort en sådan)