Metning aritmetikk - Saturation arithmetic

Metningsaritmetikk er en versjon av aritmetikk der alle operasjoner som tillegg og multiplikasjon er begrenset til et fast område mellom en minimums- og maksimumsverdi.

Hvis resultatet av en operasjon er større enn maksimumet, settes det (" fastspent ") til maksimum; hvis det er under minimum, blir det festet til et minimum. Navnet kommer fra hvordan verdien blir "mettet" når den når ekstreme verdier; ytterligere tillegg til et maksimum eller subtraksjoner fra et minimum vil ikke endre resultatet.

For eksempel, hvis det gyldige verdiområdet er fra −100 til 100, gir følgende mettende aritmetiske operasjoner følgende verdier:

  • 60 + 30 → 90.
  • 60 + 43 → 100. ( ikke forventet 103.)
  • (60 + 43) - (75 + 75) → 0. ( ikke forventet −47.) (100 - 100 → 0.)
  • 10 × 11 → 100. ( ikke forventet 110.)
  • 99 × 99 → 100. ( ikke forventet 9801.)
  • 30 × (5 - 1) → 100. ( ikke forventet 120.) (30 × 4 → 100.)
  • (30 × 5) - (30 × 1) → 70. ( ikke forventet 120. ikke forrige 100.) (100 - 30 → 70.)

Som det kan sees fra disse eksemplene, kan kjente egenskaper som assosiativitet og distribusjon mislykkes i metning aritmetikk. Dette gjør det ubehagelig å håndtere i abstrakt matematikk, men det har en viktig rolle å spille i digital maskinvare og algoritmer der verdier har maksimale og minimale representable områder.

Moderne bruk

Vanligvis implementerer mikroprosessorer for generelle formål ikke heltalsberegninger ved bruk av metningsregning; I stedet bruker de den enklere å implementere modulære aritmetikk , der verdier som overstiger maksimumsverdien " vikles rundt " til minimumsverdien, som timer på en klokke som går fra 12 til 1. I maskinvare, modulær aritmetikk med et minimum av null og maksimalt r n - 1, hvor r er radiksen, kan implementeres ved å bare forkaste alle bortsett fra de laveste n sifrene. For binær maskinvare, som det store flertallet av moderne maskinvare er, er radiksen 2, og sifrene er biter.

Imidlertid har metning aritmetikk mange praktiske fordeler, selv om det er vanskeligere å implementere. Resultatet er så numerisk nær det sanne svaret som mulig; for 8-bits binær signert aritmetikk, når det riktige svaret er 130, er det betydelig mindre overraskende å få svaret 127 fra mettende aritmetikk enn å få svaret −126 fra modulær aritmetikk. På samme måte, for 8-bits binær usignert aritmetikk, når det riktige svaret er 258, er det mindre overraskende å få et svar på 255 fra mettende aritmetikk enn å få et svar på 2 fra modulær aritmetikk.

Metningsaritmetikk gjør det også mulig å oppdage overløp av tillegg og multiplikasjoner konsekvent uten en overflowbit eller overdreven beregning, ved enkel sammenligning med maksimums- eller minimumsverdien (forutsatt at referansen ikke er tillatt å ta på seg disse verdiene).

I tillegg muliggjør metningsaritmetikk effektive algoritmer for mange problemer, spesielt innen digital signalbehandling . For eksempel kan justering av volumnivået til et lydsignal føre til overløp, og metning fører til betydelig mindre forvrengning av lyden enn omslaget. Med ord fra forskerne GA Constantinides et al .:

Når du legger til to tall ved hjelp av tos komplementrepresentasjon, resulterer overflow i et "wrap-around" fenomen. Resultatet kan være et katastrofalt tap i signal / støy-forhold i et DSP-system. Signaler i DSP-design er derfor vanligvis enten skalert på riktig måte for å unngå overløp for alle unntatt de mest ekstreme inngangsvektorene, eller produsert ved bruk av metning aritmetiske komponenter.

Implementeringer

Metningsregning er tilgjengelig på mange moderne plattformer, og var spesielt en av utvidelsene laget av Intel MMX- plattformen, spesielt for slike signalbehandlingsapplikasjoner. Denne funksjonaliteten er også tilgjengelig i bredere versjoner i SSE2 og AVX2 heltals instruksjonssett.

Metningsaritmetikk for heltall er også implementert i programvare for en rekke programmeringsspråk inkludert C , C ++ , for eksempel GNU Compiler Collection , LLVM IR og Eiffel . Dette hjelper programmerere å forutse og forstå effekten av overflow bedre, og når det gjelder kompilatorer, velger de vanligvis den optimale løsningen.

Metning er utfordrende å implementere effektivt i programvare på en maskin med bare modulære aritmetiske operasjoner, siden enkle implementeringer krever grener som skaper store forsinkelser i rørledningen. Det er imidlertid mulig å implementere metningstillegg og subtraksjon i programvare uten filialer , bare ved hjelp av modulære aritmetiske og bitvise logiske operasjoner som er tilgjengelige på alle moderne CPUer og deres forgjengere, inkludert alle x86-CPUer (tilbake til den opprinnelige Intel 8086 ) og noen populære 8-biters CPUer (hvorav noen, for eksempel Zilog Z80 , fortsatt er i produksjon). På den annen side, på enkle 8-biters og 16-biters CPUer, kan en forgreningsalgoritme faktisk være raskere hvis den er programmert i montering, siden det ikke er noen rørledninger å stoppe, og hver instruksjon tar alltid flere klokkesykluser. På x86, som gir overløpsflagg og betingede bevegelser , er veldig enkel grenfri kode mulig.

Selv om metning aritmetikk er mindre populær for heltall aritmetikk i maskinvare, bruker IEEE floating point standard , den mest populære abstraksjonen for å håndtere omtrentlige reelle tall , en form for metning der overløp konverteres til "uendelig" eller "negativ uendelig", og enhver annen operasjon på dette resultatet fortsetter å produsere den samme verdien. Dette har fordelen i forhold til enkel metning at senere operasjoner som reduserer verdien ikke ender med å gi et misvisende "rimelig" resultat, slik som i beregningen . Alternativt kan det være spesielle tilstander som "eksponent overflow" (og "exponent underflow") som på samme måte vil vedvare gjennom påfølgende operasjoner, eller forårsake øyeblikkelig avslutning, eller testes for som i FORTRAN for IBM704 (oktober 1956). IF ACCUMULATOR OVERFLOW ...

Se også

Merknader

Eksterne linker