Seuraa 
Viestejä950
Liittynyt11.12.2010

Jakolasku + C optimointi
30.1.2000
JA

[size=150:1j6gxodr]1. Kokonaislukuinen jakolasku
[/size:1j6gxodr]
Kokonaislukuisen jakolaskun suoritus ilman jakolaskukäskyä (Lead 3 käskykannalla) on mielenkiintoinen optimointiprobleema.

Yhtenä lähtökohtana on, että jaettavasta vähennetään jakaja niin monta kertaa, jotta päädytään nollaan tai sitä pienempään tulokseen.

Tämä tekniikka toimii tehokkaasti silloin, kun jaettava ja jakaja ovat pieniä lukuja Esim. 17 / 5 suppenee nopeasti:

a) 5 <= 17 on tosi, tulos vähintään 1
b) 5+5 <= 17 on tosi, tulos vähintään 2
c) 5+5+5 <= 17 on tosi, tulos vähintään 3
d) 5+5+5+5 <= 17 on epätosi, joten tulos on 3

17 / 5 vaatii noin kolme yhteenlaskua ja vertausta, jotta päädytään jakolaskun lopputulokseen 3. Kun jaettava on suuri ja jakaja pieni luku, niin laskun optimointi on aiheellista.

[size=150:1j6gxodr]2. Jakolaskun interpolointi
[/size:1j6gxodr]
Jakolasku voidaan saattaa binäärihauksi, eli lineaariseksi interpoloinniksi. Binäärihaku on tehokas hakualgoritmi järjestetystä alkiotaulukosta.

Jakolaskun X / Y jaettavalla ja jakajalla on käytännöllinen ominaisuus: jos a on jaettavan bittikenttä ja b jakajan bittikenttä, niin on voimassa ehto;

2^(a-b-1) => X/Y < 2^(a-b+1) , jossa a > b

Tutkimalla kokonaislukuista jakolaskua X / Y kaikilla mahdollisilla arvoilla, niin voidaan todeta, että jakolasku X / Y tulos asettuu aina välille [2^(a-b-1), 2^(a-b+1)].

[size=150:1j6gxodr]3. Jakolaskun pöytämalli binäärihaulla
[/size:1j6gxodr]
Olkoon jakolasku 17853 / 79

Jaettava 17853 asettuu 15 merkin bittikenttään ja jakaja 79 asettuu 7 merkin bittikenttään;

[code:1j6gxodr]17853 = 100 0101 1011 1101 <=> a = bitLength(17853) = 15
79 = 100 1111 <=> b = bitLength(79) = 7
[/code:1j6gxodr]
Hmin = 2^(a-b-1) = 1<<(a-b-1) = 128
Hmax = 2^(a-b+1) = 1<<(a-b+1) = 512

Nyt binäärihaku voidaan aloittaa väliltä (Hmin = 128, Hmax = 512).

[code:1j6gxodr]while (Hmax – Hmin > 1)
{
Hhalf = (Hmin + Hmax)>>1

apu = 79 * Hhalf

if (apu <= 17853)
Hmin = Hhalf
else
Hmax = Hhalf
}
[/code:1j6gxodr]

Silmukka suppenee nopeasti jakolaskun 17853 / 79 tulokseen 225. Taulukkoon 1 on koottu jakolaskun 17853 / 79 ajoesimerkki em. silmukalla;

[code:1j6gxodr]Loop Hmin Hmax
1 128 512
2 128 320
3 224 320
4 224 272
5 224 248
6 224 236
7 224 230
8 224 227
9 225 227
10 225 226
[/code:1j6gxodr]
Taulukko 1. Jakolaskun 17853 / 79 ajoesimerkki.

[size=150:1j6gxodr]4.0 Optimoitu C jakolaskufunktio
[/size:1j6gxodr]
4.1 bitLength

Joissakin käskykannoissa funktio bitLength on valmis yhden kellojakson käsky, joka antaa suoraan argumentin itseisarvon bittipituuden.

Esimerkiksi arvon 6 merkitsevä bittipituus on kolme, 6 = 110. Arvon 155 merkitsevä bittipituus on 8, 155 = 10011011, jne.

Jos käskyä bitLength ei ole sisällytetty käskykantaan, niin arvojen merkitsevät bittipituudet voidaan saattaa taulukoksi, josta argumentin bittipituus saadaan muutaman kellojakson viiveellä.

16-bittisessä ympäristössä bitLength-taulukko on luonnollista määritellä 255 saakka. Arvon nolla bittipituus on 0 (vaikkakin määrittelemätön).

[code:1j6gxodr]const uint16 bitLength[256] =
{
0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
};[/code:1j6gxodr]

Nyt enintään 8-bittisen arvon bittipituus saadaan suoraan bitLength taulukosta;

uint16 esim_arvon_155_bittipituus = bitLength[155];

Kaikkien 16-bittisten arvojen bittipituus saadaan bitLength[256]-taulukosta funktiolla;

[code:1j6gxodr]uint16 getBitLength(uint16 X)
{
uint16 length = bitLength[X>>8];

if (length)
return length+8;
else return bitLength[X];
}[/code:1j6gxodr]

Jos parametri length asettuu X:n ylemmän tavun perusteella, niin silloin X:n alemmassa tavussa kaikki 8 muuta bittiä ovat merkitseviä. Muutoin X on pienempi kuin 256, jolloin X:n bittipituus palautetaan suoraan taulukosta bitLength.

4.2 Jakolaskufunktio

div16-funkton rivit ovat numeroitu. Funktion lopussa oleellisille riveille on annettu lyhyet kommentit:

[code:1j6gxodr] 1: int16 div16(int16 _x, int16 _y)
2: {
3: uint16 a, b, sg, apu;
4: uint16 H_half, X, Y;
5: uint16 H_min, H_max;
6:
7: a=_x<0? _x=-_x, 1: 0;
8: b=_y<0? _y=-_y, 1: 0;
9:
10: X=_x; Y=_y; sg=a^b;
11: if (X < Y) return 0;
12:
13: a = getBitLength(X);
14: b = getBitLength(Y);
15:
16: if (a==b) return sg? -1: 1;
17:
18: H_min = 1<<(a-b-1);
19: H_max = 1<<(a-b+1);
20:
21: while (H_max-H_min > 1)
22: {
23: H_half = (H_min+H_max)>>1;
24: apu = Y*H_half;
25:
26: if (apu <= X)
27: H_min = H_half;
28: else
29: H_max = H_half;
30: }
31:
32: return sg? -H_min: H_min;
33: }
[/code:1j6gxodr]

Kommentit:

1. div16-funktiota voidaan kutsua positiivisilla ja negatiivisilla argumenteilla. Edelleen funktio palauttaa plus tahi miinus tuloksen, riippuen parametrien _x ja _y etumerkeistä.

6. Etumerkkibitit sijoitetaan (temp) parametreihin a ja b. _x ja _y saatetaan samalla itseisarvoiksi.

10. X ja Y ovat nyt itseisarvoja. Jakolaskun etumerkki sijoitetaan parametriin sg. Jos sg on 1, niin tulos on negatiivinen, muutoin positiivinen.

11. Jos jaettava on pienempi kuin jakaja, niin tulos on 0.

12. Arvojen X ja Y bittipituudet sijoitetaan parametreihin a ja b.

16. Jos X:n bittipituus on yhtä suuri kuin Y:n bittipituus, niin jakolaskun tulos on plus tahi miinus 1 (koska se ei ollut 0) riippuen etumerkistä sg.

17. Binäärihaku alustetaan välille [H_min, H_max].

21. H_max – H_min suppenee arvoon 1, jonka jälkeen H_min ja H_max eivät enää muutu.

23. Yhden bitin siirto oikealle on sama asia kuin (H_min + H_max) / 2.

24. Tämä kertolasku voidaan tarvittaessa korvata yhteenlaskulla. Optimointi on tarpeellista silloin, jos kertolasku vaatii enemmän kuin yhden kellojakson.

32. (unsigned) jakolaskun X / Y tulos on arvossa H_min. Laskun etumerkki on parametrissä sign. sg = 1 <=> -1, sg = 0 <=> +1.

Kommentit (7)

NytRiitti
Seuraa 
Viestejä2704
Liittynyt12.9.2012

Kyllä Massive Parallel Processing-ympyröissä koodin optimointijuttuja pohdiskeltiin 20-30 v. sitten, jakolasku vei paljon kallista prosessoriaikaa. Oletan, että nykyisin lisätään vain prosessoritehoa. Tosin jotkut laskeskelivat aivan tosimielessä, kannattaako jotain pitkää simulointia aloittaakkaan vai odottaa raudan nopeutumista ja halpenemista, kun uudella raudalla simulointi ehtisi valmiiksi aikaisemmin.

myl
Seuraa 
Viestejä224
Liittynyt18.11.2010

Kirjoittelin kerran Intelin 16 bitin prosessorille 64 bitin jakolaskun assemblyllä.

Aika tarkkana piti olla että sai kaikki luvut mahtumaan rekistereihin koko laskun ajaksi.

Hyvä siitä tuli, mutta ei voi suositella heikkohermoisille.

- myl

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat